Timezone: »

 
Spotlight
Certified Robustness of Graph Convolution Networks for Graph Classification under Topological Attacks
Hongwei Jin · Zhan Shi · Venkata Jaya Shankar Ashish Peruri · Xinhua Zhang

Thu Dec 10 07:30 AM -- 07:40 AM (PST) @ Orals & Spotlights: Graph/Relational/Theory

Graph convolution networks (GCNs) have become effective models for graph classification. Similar to many deep networks, GCNs are vulnerable to adversarial attacks on graph topology and node attributes. Recently, a number of effective attack and defense algorithms have been developed, but certificates of robustness against \emph{topological perturbations} are currently available only for PageRank and label/feature propagation, while none has been designed for GCNs. We propose the first algorithm for certifying the robustness of GCNs to topological attacks in the application of \emph{graph classification}. Our method is based on Lagrange dualization and convex envelope, which result in tight approximation bounds that are efficiently computable by dynamic programming. When used in conjunction with robust training, it allows an increased number of graphs to be certified as robust.

Author Information

Hongwei Jin (University of Illinois at Chicago)
Zhan Shi (University of Illinois at Chicago)
Ashish Peruri (University of Illinois at Chicago)
Xinhua Zhang (UIC)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors