Certifiable Robustness and Robust Training for Graph Convolutional Networks

By Daniel Zügner, Stephan Günnemann. 2019

180 citations recorded by the source corpus.

Recent works show that Graph Neural Networks (GNNs) are highly non-robust with respect to adversarial attacks on both the graph structure and the node attributes, making their outcomes unreliable. We propose the first method for certifiable (non-)robustness of graph convolutional networks with respect to perturbations of the node attributes. We consider the case of binary node attributes (e.g. bag-of-words) and perturbations that are L_0-bounded. If a node has been certified with our method, it is guaranteed to be robust under any possible perturbation given the attack model. Likewise, we can certify non-robustness. Finally, we propose a robust semi-supervised training procedure that treats the labeled and unlabeled nodes jointly. As shown in our experimental evaluation, our method significantly improves the robustness of the GNN with only minimal effect on the predictive accuracy.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Attacking Graph-based Classification via Manipulating the Graph Structure (2019, background): “/deleted edges via maximizing a surrogate loss function with respect to the graph structure, where the optimization problem is subject to the node degree distribution constraint. Several recent works [8, 78, 79] further studied attacks and defenses for graph neural networks, which are concurrent to ”
Adversarial Attacks on Neural Networks for Graph Data (2018, background): “Since then, there has been increasing interest in adversarial attacks [Zügner and Günnemann, 2019a; Bojchevski and Günnemann, 2019] and the first work about defenses [Zügner and Günnemann, 2019b].”
Adversarial Attacks on Node Embeddings via Graph Poisoning (2018, methodology): “Z¨ugner & G¨unnemann (2019) develop a general attack on the training procedure of GCN using meta-gradients.”
Adversarial Attack and Defense on Graph Data: A Survey (2018, methodology): “Citation Network Node/Link Citeseer [87] 3,327 4,732 3,703 6 [145], [28], [23], [106], [92], [8], [147], [12], [129], [120], [125], [17], [127], [40], [140], [89], [22], [144], [105] , [57], [148], [9], [52], [53], [107], [36], [134], [96], [20], [54], [29], [56], [31], [76], [77], [146], [59], [49]”
Graph Structure Learning for Robust Graph Neural Networks (2020, background): “Although increasing efforts have been devoted to developing adversarial attacks on graph data, the research about improving the robustness of GNNs has just started recently [27, 31, 37, 40].”
Graph Information Bottleneck (2020, unknown): “Accordingly, several defense models are proposed to increase the robustness by injecting random noise in the representations [33], removing suspicious and uninformative edges [34], low-rank approximation of the adjacency matrix [35], additional hinge loss for certified robustness [36].”
Subgraph Federated Learning with Missing Neighbor Generation (2021, background): “Current robust GNNs focus on the sensitivity towards modifications on node features [16, 17] or adding/removing edges on the graph [18].”
GNNGuard: Defending Graph Neural Networks against Adversarial Attacks (2020, background): “, [46, 47]) focus on theoretical certificates for GNN robustness instead of defense mechanisms.”
Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond (2020, methodology): “[49] implemented LiRPA for convolutional ResNet on computer vision tasks; Zügner & Günnemann [58] extended [47] to graph convolutional networks; Ko et al.”