论文标题
基于扰动的黑盒攻击，以理论保证来绘制神经网络的匪徒的匪徒
Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees
论文作者
论文摘要
图形神经网络（GNN）已在许多基于图的任务（例如节点分类和图形分类）中实现了最先进的性能。但是，许多最近的作品表明，攻击者可以通过稍微扰动图形结构来误导GNN模型。对GNN的现有攻击要么是在较不实用的威胁模型下，因此假定攻击者可以访问GNN模型参数，或者在实用的黑盒威胁模型下，但考虑扰动节点功能，这些特征被证明不够有效。在本文中，我们旨在弥合这一差距，并考虑具有结构扰动以及理论保证的GNN的黑盒攻击。我们建议通过强盗技术应对这一挑战。具体来说，我们将攻击作为在线优化，并通过强盗反馈进行优化。这个原始问题本质上是NP-HARD，因为扰动图形结构是二进制优化问题。然后，我们提出了一种基于强盗优化的在线攻击，该攻击被证明是{sublinear}到查询号$ t $，即$ \ Mathcal {o}（\ sqrt {n} t^{3/4}）$中，其中$ n $是图中的nodes。最后，我们通过对多个数据集和GNN模型进行实验来评估我们提出的攻击。各种引文图和图像图的实验结果表明，我们的攻击既有效又有效。源代码可在〜\ url {https://github.com/metaoblivion/bandit_gnn_attack}获得
Graph neural networks (GNNs) have achieved state-of-the-art performance in many graph-based tasks such as node classification and graph classification. However, many recent works have demonstrated that an attacker can mislead GNN models by slightly perturbing the graph structure. Existing attacks to GNNs are either under the less practical threat model where the attacker is assumed to access the GNN model parameters, or under the practical black-box threat model but consider perturbing node features that are shown to be not enough effective. In this paper, we aim to bridge this gap and consider black-box attacks to GNNs with structure perturbation as well as with theoretical guarantees. We propose to address this challenge through bandit techniques. Specifically, we formulate our attack as an online optimization with bandit feedback. This original problem is essentially NP-hard due to the fact that perturbing the graph structure is a binary optimization problem. We then propose an online attack based on bandit optimization which is proven to be {sublinear} to the query number $T$, i.e., $\mathcal{O}(\sqrt{N}T^{3/4})$ where $N$ is the number of nodes in the graph. Finally, we evaluate our proposed attack by conducting experiments over multiple datasets and GNN models. The experimental results on various citation graphs and image graphs show that our attack is both effective and efficient. Source code is available at~\url{https://github.com/Metaoblivion/Bandit_GNN_Attack}
