CRII: SaTC: Towards Understanding the Robustness of Graph Neural Networks against Graph Perturbations

利用图进行学习，如社会网络、生物网络和金融网络，最近不断引起人们的关注，其中图神经网络(GNN)已经成为最重要的方法论。然而，最近的研究表明，GNN容易受到图的扰动攻击：对图的结构进行轻微的扰动会使GNN模型的性能严重下降。GNN缺乏健壮性，这使得它们的潜在应用面临风险。然而，现有关于GNN攻击和防御的研究范围非常有限：假设攻击是在较不实用的场景下进行的(即攻击者对GNN模型有全部或部分了解)，而防御要么是基于启发式的，容易被破解的，要么是缺乏防御的健壮性。这个项目旨在了解如何执行图形扰动攻击来愚弄任何GNN，而对GNN模型知之甚少或一无所知。因此，该项目设计了对任意GNN的受限和严格黑盒图扰动攻击，分别受到影响函数和Bandit算法的启发。接下来，该项目旨在了解如何通过健壮性保证来保护任何GNN免受最强的白盒攻击。为此，通过新的随机化平滑技术设计了针对白盒图扰动攻击的可证明防御，并设计了原则性方法来优化防御性能，该项目的创新之处在于全面了解了GNN对抗图扰动攻击的健壮性，并研究了更实用的攻击，最后设计了更可证明的防御。该项目的更广泛的意义和影响是1)不仅促进安全和值得信赖的机器学习领域，而且还促进其他领域(例如，社会科学和经济)，其中图形数据模型和图形学习被广泛应用；2)开发一个新的研讨会课程“对抗性环境下的图形学习”，以及3)支持本科生和研究生的跨学科研究。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Learning with graphs, such as social networks, biological networks, and financial networks, has drawn continuous attention recently, wherein graph neural networks (GNNs) have been emerging as the most prominent methodology. However, recent studies show that GNNs are vulnerable to graph perturbation attacks: slightly perturbing the graph structure can make GNN model's performance severely degraded. The lack of robustness of GNNs makes them risky for their potential applications. However, existing studies on GNN attacks and defenses are very limited in scope: the attacks are assumed under less practical scenarios (i.e., the attacker has a full or partial knowledge about the GNN model), while the defenses are either heuristic-based that can be easily broken or their robustness in defense is lacking. This project aims to understand how to perform the graph perturbation attack to fool any GNNs with least/no knowledge about the GNN model. Accordingly, the project designs both restricted and stringent black-box graph perturbation attacks to any GNNs, which are inspired by the influence function and bandit algorithms, respectively. Next, the project aims to understand how to protect any GNNs from the strongest white-box attack with robustness guarantees. To this end, it designs provable defenses for any GNNs against white-box graph perturbation attacks via novel randomized smoothing techniques and designs principled methods to optimize the defense performance.The project’s novelties are to gain a holistic understanding on the robustness of GNNs against graph perturbation attacks, to look into more practicable attacks and lastly to devise a more provable defenses. The project’s broader significance and impact are 1)advancing not only the field of secure and trustworthy machine learning, but also other fields (e.g., social science and economy) where graph data model and graph learning are widely used; 2) developing a new seminar course “Graph Learning in the Adversarial Settings”, and 3)supporting cross-disciplinary research for both undergraduate and graduate students.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.