[KDD 2020] Certifiable Robustness of Graph Convolutional Networks under Structure Perturbations
Aug 13, 20205 views
Recent works show that message-passing neural networks (MPNNs),can be fooled by adversarial attacks on both the node attributes,and the graph structure. Since MPNNs are currently being rapidly,adopted in real-world applications, it is thus crucial to improve,their reliablility and robustness. While there has been progress,on robustness certification of MPNNs under perturbation of the,node attributes, no existing method can handle structural perturbations. These perturbations are especially challenging because they,alter the,message passing scheme itself,. In this work we close this,gap and propose the first method to certify robustness of Graph,Convolutional Networks (GCNs) under perturbations of the graph,structure. We show how this problem can be expressed as a jointly,constrained bilinear program – a challenging, yet well-studied class,of problems – and propose a novel branch-and-bound algorithm to,obtain lower bounds on the global optimum. These lower bounds,are significantly tighter and can certify up to twice as many nodes,compared to a standard linear relaxation.