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.

本研究针对图形结构数据，基于随机平滑技术，开发出可证明鲁棒性的图神经网络，证明其对于节点和图分类具有结构扰动的认证鲁棒性保证，并在多个 GNN 和多个基准数据集上进行了实证评估。