Title
Certified Robustness of Graph Convolution Networks for Graph Classification under Topological Attacks
Abstract
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 designed, but no certificate of robustness has been developed for GCN-based graph classification under topological perturbations with both local and global budgets. In this paper, we propose the first certificate for this problem. 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.
Year
Venue
DocType
2020
NIPS 2020
Conference
Volume
Citations 
PageRank 
33
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Hongwei Jin110.72
Shi, Zhan221.38
Venkata Jaya Shankar Ashish Peruri300.34
Zhang, Xinhua425730.98