Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation
This addresses the security problem of GNNs in graph-structured data for applications like node and graph classification, though it is incremental as it extends an existing technique to a new domain.
The paper tackles the vulnerability of graph neural networks (GNNs) to adversarial structural perturbations by developing a certifiably robust defense using randomized smoothing, achieving a certified accuracy of 0.49 on the Cora dataset when attackers can modify up to 15 edges.
Graph neural networks (GNNs) have recently gained much attention for node and graph classification tasks on graph-structured data. However, multiple recent works showed that an attacker can easily make GNNs predict incorrectly via perturbing the graph structure, i.e., adding or deleting edges in the graph. We aim to defend against such attacks via developing certifiably robust GNNs. Specifically, we prove the certified robustness guarantee of any GNN for both node and graph classifications against structural perturbation. Moreover, we show that our certified robustness guarantee is tight. Our results are based on a recently proposed technique called randomized smoothing, which we extend to graph data. We also empirically evaluate our method for both node and graph classifications on multiple GNNs and multiple benchmark datasets. For instance, on the Cora dataset, Graph Convolutional Network with our randomized smoothing can achieve a certified accuracy of 0.49 when the attacker can arbitrarily add/delete at most 15 edges in the graph.