EvA: Evolutionary Attacks on Graphs¶
会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=EzXzGRngYb
代码: github.com/UoC-tail/EvA
领域: 图学习 / 图对抗攻击 / 进化算法
关键词: 图神经网络, 对抗攻击, 进化算法, 组合优化, 黑盒攻击, 保形预测, 鲁棒性证书
一句话总结¶
用精心设计的遗传算法直接在离散的边翻转空间里搜索对抗扰动，绕开梯度松弛与可微代理损失，在节点分类攻击上比 SOTA 的 PRBCD 平均再掉约 11% 准确率，并首次实现对保形预测和鲁棒性证书的图结构攻击。
研究背景与动机¶
领域现状：图神经网络（GNN）对结构扰动极其脆弱，仅增删几条边就能让准确率跌破连图都不看的 MLP。绝大多数图对抗攻击都是梯度型的——以 PRBCD / LRBCD 为代表，对邻接矩阵求 tanh-margin 损失的梯度，再用块坐标下降（BCD）采样翻转哪些边。
现有痛点：本文逐条列出梯度攻击的七宗罪。(i) 原问题是 \(\{0,1\}\) 上的组合优化，梯度法必须松弛到 \([0,1]\)，解远离最优；(ii) 梯度只给局部信息，无法反映边翻转后真实的损失地形（论文 Fig.1 左：梯度说降，损失实际升）；(iii) 梯度只刻画"单独翻一条边"的效果，多条边同时翻时效果可能完全相反（Fig.1 中）；(iv) 准确率本身不可微，必须找可微代理损失（交叉熵是次优代理）；(v) 需要白盒访问，否则得训代理模型；(vi) 防御方只要混淆梯度就能制造"虚假安全感"；(vii) 邻接矩阵稀疏但其梯度不稀疏，内存随节点数平方增长。
核心矛盾：要解的本来是离散组合优化，梯度法为了能求导被迫松弛、被迫造代理损失、被迫白盒——这些妥协既损失最优性又限制了适用范围。
本文目标：直接在二值矩阵空间上求解原始组合优化问题，不依赖任何梯度信息，做到黑盒、任意目标、可扩展到大图。
核心 idea：搜索而非求导——重拾被遗忘的进化/遗传算法（GA）。早年 Dai et al. (2018) 的 GA 攻击因为损失函数和变异策略设计糟糕而打不过梯度法，被业界遗忘。本文证明，只要把元启发式流水线的各个组件（适应度函数、编码、变异、初始化、分治）重新精心设计，纯搜索就能大幅反超 SOTA 梯度攻击。
方法详解¶
整体框架¶
EvA 把"翻哪些边"建模成遗传算法上的离散搜索：种群里每个个体是一组待翻转的边索引，通过适应度评估、锦标赛选择、交叉、变异迭代进化。围绕这个骨架，本文做了五处关键改造——稀疏编码省内存、用准确率本身当适应度、把搜索限制在攻击目标的感受野内、自适应靶向变异、以及面向大图的分治策略——并利用黑盒特性把目标换成保形预测/证书攻击。
flowchart TD
A[初始种群: 每个个体=δ条边索引<br/>至少一端落在攻击目标 Vatt] --> B[适应度评估<br/>全局攻击用扰动后准确率<br/>靶向攻击用tanh-margin]
B --> C[锦标赛选择 ntour 取最优两个]
C --> D[交叉: 拼接父代片段]
D --> E[自适应靶向变异 ATM<br/>新边一端限定在未攻陷的Vatt节点]
E --> F{达到迭代上限?}
F -- 否 --> B
F -- 是 --> G[输出最优扰动 P]
H[大图: 分治拆分Vatt<br/>逐子集累积攻击] -.增强.-> A
I[稀疏编码: 个体存O(δ)索引<br/>而非O(N²)布尔向量] -.贯穿.-> A关键设计¶
1. 稀疏编码 + O(1) 索引映射：把内存从平方降到线性。 朴素做法是用 \(N^2\) 维布尔向量标记翻转哪些边，内存 \(O(|S|N^2)\)，完全无视邻接矩阵的稀疏性。EvA 改为把每个候选个体表示成"待翻转边索引的列表"，个体维度恰好是预算 \(\delta=\lfloor\epsilon\cdot|E[V_{att}:V]|\rfloor\)，每个分量 \(z[i]\in\{1,\dots,n(n-1)/2\}\) 是上三角矩阵的对角枚举索引，通过映射 \(\Pi\) 以 \(O(1)\) 代价在一维索引和二维无向边之间互转。这样内存复杂度降到 \(O(\epsilon\cdot E\cdot P)\)（\(P\) 为种群大小，是小常数，可简化为 \(O(\epsilon\cdot E)\)），既照顾了稀疏性，又因为个体长度上限就是预算而天然满足全局约束，不必额外投影。
2. 用准确率本身当适应度，而非可微代理：搜索的最大红利。 梯度法被迫用交叉熵或 tanh-margin 这类可微代理，但消融（Fig.2 左）显示交叉熵会把预算浪费在已经分错的节点上、而非去攻陷新节点；tanh-margin（Geisler et al. 2023 为缓解此问题而提出）相关性更好；可在 EvA 里，直接拿不可微的准确率当适应度反而最优。由于搜索完全不需要求导，这个无法被梯度法利用的目标对 EvA 是免费的。更关键的是，PRBCD 已经用了 tanh-margin 却仍被 EvA 大幅甩开，说明 EvA 的优势不只来自损失质量——GA 的探索能力让它能跳出局部最优，而 PRBCD 容易卡死。
3. 感受野约束 + 自适应靶向变异（ATM）：把预算花在刀刃上。 核心洞察是把搜索空间从整张图的 \(\frac{n(n-1)}{2}\) 条边收缩到攻击目标 \(V_{att}\) 的感受野内：两端都在训练子图里的扰动会被记忆轻易还原，感受野外的翻转又不影响 \(V_{att}\) 的预测，都是浪费预算。于是初始化时强制每条边至少一端落在 \(V_{att}\)。变异上从朴素的均匀变异（UM，全图随机加索引）逐步进化：靶向变异（TM）把新边一端限定在 \(V_{att}\)；自适应靶向变异（ATM）进一步——当某节点已被成功攻陷，就把它从受限端点中剔除（再扰动它已无收益），但仍允许它去连接其他 \(V_{att}\) 节点以贡献于他人的误分类风险。这套从 UM→TM→ATM 的递进显著提升攻击效果。
4. 分治（D&C）：把指数级搜索空间砍小，大图也能打。 大图上搜索空间随节点数平方膨胀。D&C 把 \(V_{att}=V_1\cup V_2\) 拆开，按各自连边比例分配预算 \(\delta=\delta_1+\delta_2\)，先用 \(\delta_1\) 攻 \(V_1\)，把改后的图作为起点再用 \(\delta_2\) 攻 \(V_2\)，最后合并重评。标准攻击要在 \(\binom{n/2}{\delta}\) 的空间里搜，D&C 只需搜 \(\binom{n/2}{\delta_1}+\binom{n/2}{\delta_2}\)——指数级缩小。代价是这个松弛可能让解偏离全局最优，所以它对大图（Ogbn-Arxiv 提升约 8%）有效、对小图 CoraML 反而无益。值得一提的是 D&C 同样能提升 PRBCD（在不增内存的前提下），凸显它是通用的扩展性技巧。此外 EvA 还把保形预测覆盖率、平滑证书的认证比例等不可微目标直接设为适应度，配合"堆叠扰动"（把整个种群拼成一张大图一次前向评估）和重采样技巧控制开销，实现了首个针对保形集和鲁棒性证书的图结构攻击。
实验关键数据¶
主实验：CoraML 上不同攻击在各预算下的扰动后准确率（越低越强）¶
| Attack | 0.01 | 0.02 | 0.05 | 0.10 | 0.15 |
|---|---|---|---|---|---|
| DICE | 80.93 | 80.93 | 80.78 | 80.57 | 80.07 |
| PGA | 79.58 | 76.92 | 70.94 | 64.62 | 60.46 |
| PGD | 78.22 | 75.37 | 67.18 | 59.14 | 53.09 |
| GRPCD | 78.07 | 75.08 | 66.76 | 58.29 | 54.80 |
| PRBCD (SOTA) | 76.44 | 73.17 | 66.48 | 58.51 | 52.67 |
| EvA | 74.80 | 68.97 | 52.95 | 41.99 | 37.65 |
在 \(\epsilon=0.10\) 时 EvA 把准确率打到 41.99%，比次优的 PGD（59.14%）再低约 17 个百分点，平均比最佳前作多掉约 11%、比基线 GA 攻击多掉高达约 40%。
攻击鲁棒防御模型（CoraML，准确率越低越强）¶
| Defense | Attack | 0.01 | 0.02 | 0.05 | 0.10 |
|---|---|---|---|---|---|
| GCN-SVD | EvA / PRBCD | 0.70/0.76 | 0.64/0.75 | 0.54/0.73 | 0.41/0.70 |
| GNNGuard | EvA / PRBCD | 0.71/0.74 | 0.67/0.72 | 0.55/0.70 | 0.45/0.66 |
| Robust-GCN | EvA / PRBCD | 0.75/0.77 | 0.70/0.73 | 0.59/0.68 | 0.52/0.63 |
| Soft-Median | EvA / PRBCD | 0.75/0.77 | 0.72/0.76 | 0.69/0.73 | 0.62/0.68 |
EvA 对所有鲁棒防御都比 PRBCD 更具穿透力；在多个 vanilla/robust 模型上，仅需 \(\epsilon\sim0.05\) 就能把准确率打到 MLP（完全忽略边）之下——即"用了图结构反而不如不用"。
消融与关键发现¶
- 适应度函数（Fig.2 左）：准确率 > tanh-margin > 交叉熵；交叉熵浪费预算在已分错节点上。
- 变异策略（Fig.2 中）：ATM > TM > UM，自适应剔除已攻陷节点持续受益。
- 扩展性（Fig.3）：种群规模/迭代数增大时 EvA 持续提升（开放式搜索），而 PRBCD 增大块大小或步数几乎无改进——EvA 能"吃下"额外时间/内存，PRBCD 不能；EvA 在更广的时间-内存-性能权衡上更常 Pareto 最优。
- 局部约束（Fig.2 右）：即使不加局部约束，EvA 的度违例也远少于 PRBCD，扰动更分散；加上基于"种群内边频率" \(s(e)=\sum_{s\in S}\mathbb{I}[e\in s]/|S|+u\) 的局部投影后可严格满足度约束。
亮点与洞察¶
- 范式回潮的有力证明：被遗忘的搜索/进化攻击不是不行，而是当年没设计好；组件级精调就能反超梯度 SOTA，警示社区不要过度依赖梯度攻击来评估鲁棒性。
- 黑盒 + 任意目标是真正的杀手锏：因为不需要梯度，把目标换成"认证比例""保形覆盖率""集合大小"这类含分位数、多数投票、蒙特卡洛采样的不可微复合目标几乎零成本，由此诞生了图上首个保形/证书攻击。
- 开放式搜索的可扩展性：性能随算力（时间或内存）单调上升的特性，让 EvA 在评估上限上比"收敛即停"的梯度法更可怕。
- 工程细节扎实：O(1) 索引映射、稀疏编码、整个种群堆叠成一张大图一次前向、对证书攻击只对变动边重采样——这些把 GA 从"慢且占内存"做成了可扩展方案。
局限与展望¶
- 靶向单节点攻击需换损失：0-1 准确率在单节点上只有两个值，GA 退化成随机搜索，必须改用 tanh-margin 代理，说明纯准确率适应度并非万能。
- D&C 的松弛是双刃剑：小图上反而有害，分治带来的解偏离需要按图规模/预算谨慎开启。
- 超参较多：种群大小、锦标赛规模、变异概率、分治块数 \(k_{dc}\)、热身迭代 \(t_{warm}\) 等都需调，泛化到新图/新目标时的调参成本未充分讨论。
- 评估范围：主结果集中在 CoraML/Citeseer/Pubmed/Ogbn-Arxiv 等引用网络与节点分类，跨任务（图分类、链接预测）与更大规模工业图上的表现仍待验证。
相关工作与启发¶
- 梯度攻击主线：PRBCD（Geisler et al. 2021）、LRBCD（Gosch et al. 2024）用 tanh-margin 梯度 + 块坐标下降，是本文的直接对手与"被反超"对象。
- 搜索攻击前身：Dai et al. (2018) 的 GA 攻击是被遗忘的起点，本文相当于给它做了彻底的组件升级。
- 评估方法论：沿用 Gosch et al. (2024) 的归纳式（inductive）设定，避免转导式下"记忆干净图"带来的虚假鲁棒；按 Lingam et al. (2023) 的可交换采样划分数据。
- 启发：对于任何"原问题离散、被迫松弛/造代理"的对抗或优化场景，回到组合搜索 + 精心设计的元启发式可能比硬凑可微性更有效；黑盒目标的可插拔性是搜索法相对梯度法的结构性优势。
评分¶
- 新颖性: ⭐⭐⭐⭐ — 不在于发明 GA，而在于系统性证明"精调搜索能反超梯度 SOTA"，并据此打开保形/证书这类全新攻击面，视角有冲击力。
- 实验充分度: ⭐⭐⭐⭐ — 多数据集、多防御模型、多预算 + 适应度/变异/扩展性/局部约束全套消融，归纳式设定严谨；跨任务与超大图覆盖略欠。
- 写作质量: ⭐⭐⭐⭐ — 七条痛点逐项拆解、图示直观、动机到方法逻辑顺畅；超参与若干技巧推到附录稍增阅读负担。
- 价值: ⭐⭐⭐⭐ — 实质性提升攻击上限（平均再掉约 11%）并警示鲁棒性评估的盲区，对图对抗鲁棒社区有方法论级别的提醒价值。