用进化算法直接优化图结构攻击，无需梯度信息
EvA: Evolutionary Attacks on Graphs
- 基于进化算法直接处理离散图结构优化问题
- 相比最优已有攻击平均再降低11%准确率
- 适用于任意黑盒模型，可突破鲁棒性认证
图神经网络（GNN）对图结构的微小扰动极为敏感。现有攻击多依赖梯度信息进行边扰动，将离散优化问题松弛为连续空间，导致解不理想，且无法处理非可导目标。我们提出一种基于进化算法的直接离散优化方法——进化攻击（EvA），可适配任意黑盒模型与目标函数，无需可导代理损失。由此设计出两种新攻击，能削弱鲁棒性证书并破坏置信集。攻击内存复杂度与攻击预算呈线性关系。实验显示，相较最佳已有攻击，EvA在平均上额外降低约11%的准确率，揭示了攻击设计的巨大潜力。
原文摘要 · Abstract (English)
Even a slight perturbation in the graph structure can cause a significant drop in the accuracy of graph neural networks (GNNs). Most existing attacks leverage gradient information to perturb edges. This relaxes the attack's optimization problem from a discrete to a continuous space, resulting in solutions far from optimal. It also restricts the adaptability of the attack to non-differentiable objectives. Instead, we introduce a few simple yet effective enhancements of an evolutionary-based algorithm to solve the discrete optimization problem directly. Our Evolutionary Attack (EvA) works with any black-box model and objective, eliminating the need for a differentiable proxy loss. This allows us to design two novel attacks that reduce the effectiveness of robustness certificates and break conformal sets. The memory complexity of our attack is linear in the attack budget. Among our experiments, EvA shows $\sim$11\% additional drop in accuracy on average compared to the best previous attack, revealing significant untapped potential in designing attacks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。