提出可精确验证图神经网络对抗鲁棒性的新方法，支持多种聚合函数。
Exact Verification of Graph Neural Networks with Incremental Constraint Solving
- 基于增量约束求解与边界紧化，逐轮优化验证效率。
- 在真实欺诈和生物化学数据集上表现优异，节点分类效果领先。
- 首次支持max和mean聚合函数的精确验证，适合高风险场景应用。
图神经网络（GNN）在欺诈检测、医疗等高风险领域广泛应用，但易受对抗攻击。现有方法对消息传递GNN中常见的聚合函数支持不足。本文提出GNNev，一种精确（可靠且完整）的验证方法，可计算针对属性和结构扰动（含边增删）的鲁棒性保证，且满足预算约束。该方法结合约束求解与边界紧化，利用求解器的增量求解能力，迭代求解一系列松弛后的约束满足问题，提升效率。GNNev支持sum、max、mean三种聚合函数，其中后两者首次实现精确验证。在Amazon、Yelp等真实欺诈数据集，以及MUTAG、ENZYMES等生物化学数据集上的实验表明，其在节点分类任务上优于现有工具，在图分类任务上具有竞争力。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) are increasingly often employed in high-stakes applications, such as fraud detection or healthcare, but are susceptible to adversarial attacks. A number of techniques have been proposed to provide adversarial robustness guarantees, but support for commonly used aggregation functions in message-passing GNNs is lacking. In this paper, we develop an exact (sound and complete) verification method for GNNs to compute guarantees against attribute and structural perturbations that involve edge addition or deletion, subject to budget constraints. Our method employs constraint solving with bound tightening, and iteratively solves a sequence of relaxed constraint satisfaction problems while relying on incremental solving capabilities of solvers to improve efficiency. We implement GNNev, a versatile exact verifier for message-passing neural networks, which supports three aggregation functions -- sum, max and mean -- with the latter two considered here for the first time. Extensive experimental evaluation of GNNev on real-world fraud datasets (Amazon and Yelp) and biochemical datasets (MUTAG and ENZYMES) demonstrates its usability and effectiveness, as well as superior performance on node classification and competitiveness on graph classification compared to existing exact verification tools on sum-aggregated GNNs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。