Certifying Robust Graph Classification under Orthogonal Gromov-Wasserstein Threats
Certifying Robust Graph Classification under Orthogonal Gromov-Wasserstein Threats
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Hongwei Jin;Zishun Yu;Xinhua Zhang
中科院分区：
文献类型：
--
作者：
Hongwei Jin;Zishun Yu;Xinhua Zhang
图分类器容易受到拓扑攻击。虽然最近已经开发了鲁棒性证书，但它们的威胁模型只计算局部和全局边缘扰动，这实际上忽略了重要的图结构，如同构。为了解决这个问题，我们建议测量的扰动与正交Gromov-Wasserstein差异，并建立其Fenchel双共轭，以促进凸优化。我们的关键见解是从匹配损失，其根通过单调算子连接两个变量，它产生一个紧密的外凸近似图节点上的电阻距离。当应用于图卷积网络的图分类时，我们的证书和攻击算法都是有效的。
Graph classifiers are vulnerable to topological attacks. Although certificates of robustness have been recently developed, their threat model only counts local and global edge perturbations, which effectively ignores important graph structures such as isomorphism. To address this issue, we propose measuring the perturbation with the orthogonal Gromov-Wasserstein discrepancy, and building its Fenchel biconjugate to facilitate convex optimization. Our key insight is drawn from the matching loss whose root connects two variables via a monotone operator, and it yields a tight outer convex approximation for resistance distance on graph nodes. When applied to graph classification by graph convolutional networks, both our certificate and attack algorithm are demonstrated effective.