用轻量级求解器提升图神经网络结构鲁棒性验证效率
Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing
- 用多项式时间的局部求解器替代复杂整数规划求解器
- 在多个图神经网络和数据集上验证了更强的结构鲁棒性
- 适合关注图模型安全性的研究人员与工程师
图神经网络（GNN）是图结构学习的主要架构。如同其他机器学习模型，其面临对抗攻击问题——攻击者可通过输入微小扰动改变输出。现有对抗鲁棒性验证方法最初针对图像分类设计，在图学习场景中，攻击常作用于图结构而非仅特征数值。当前最优技术将问题转化为约束求解，依赖强大的求解器（如混合整数规划求解器）。本文提出，通过调用高效但可能不完整的局部求解器，取代传统强求解器，可显著提升结构鲁棒性验证效率。我们在多种GNN变体和数据集上评估了工具RobLight，结果表明该方法在保持高精度的同时实现更快验证速度。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) are the predominant architecture for learning over graphs. As with any machine learning model, an important issue is the detection of attacks, where an adversary can change the output with a small perturbation of the input. Techniques for solving the adversarial robustness problem - determining whether an attack exists - were originally developed for image classification. In the case of graph learning, the attack model usually considers changes to the graph structure in addition to or instead of the numerical features of the input, and the state of the art techniques proceed via reduction to constraint solving, working on top of powerful solvers, e.g. for mixed integer programming. We show that it is possible to improve on the state of the art in structural robustness by replacing the use of powerful solvers by calls to efficient partial solvers, which run in polynomial time but may be incomplete. We evaluate our tool RobLight on a diverse set of GNN variants and datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。