Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation
Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation
复制标题
DOI：
10.1145/3447548.3467295
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Binghui Wang;Jinyuan Jia;Xiaoyu Cao;N. Gong
中科院分区：
文献类型：
--
作者：
Binghui Wang;Jinyuan Jia;Xiaoyu Cao;N. Gong
图神经网络(GNN)近年来在图结构数据的节点分类和图分类任务中得到了广泛的关注。然而，最近的多项工作表明，攻击者可以通过扰乱图的结构，即在图中添加或删除边，很容易使GNN预测错误。我们的目标是通过开发可证明可靠的GNN来防御此类攻击。具体地说，我们证明了任何GNN对于结点分类和图分类对结构扰动的第一个证明的健壮性保证。此外，我们还证明了我们的认证稳健性保证是严格的。我们的结果是基于最近提出的一种称为随机化平滑的技术，我们将其扩展到图形数据。我们还在多个GNN和多个基准数据集上对我们的方法进行了经验评估，包括节点分类和图分类。例如，在CORA数据集上，当攻击者可以任意添加/删除图中的最多15条边时，使用我们的随机化平滑的Graph卷积网络可以达到0.49的认证精度。
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 first 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.