Skip to yearly menu bar Skip to main content


Certifying Robust Graph Classification under Orthogonal Gromov-Wasserstein Threats

Hongwei Jin · Zishun Yu · Xinhua Zhang

Hall J (level 1) #910

Keywords: [ certification of robustness ] [ Gromov-Wasserstein distance ] [ convex relaxation ]


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.

Chat is not available.