Timezone: »

Certifying Robust Graph Classification under Orthogonal Gromov-Wasserstein Threats
Hongwei Jin · Zishun Yu · Xinhua Zhang

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #910

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.

Author Information

Hongwei Jin (Argonne National Laboratory)
Zishun Yu (University of Illinois, Chicago)
Xinhua Zhang (University of Illinois at Chicago (UIC))

More from the Same Authors