跳到正文
原文

图神经网络的拓扑攻击与防御:优化视角

Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective

arXiv· arXiv:1906.04214· Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, Xue LinElectrical & Computer Engineering, Northeastern University; Electrical Engineering & Computer Science, Massachusetts Institute of Technology; MIT-IBM Watson AI Lab, IBM Research; Electrical & Computer Engineering, University of Minnesota本站收录· 23 天前· 原文发表攻击

论文速读

攻击

据论文 PDF 整理(AI 生成),以原文为准

作者提出基于凸松弛的 GNN 拓扑攻击(PGD 与 min-max)及对抗训练,在 Cora/Citeseer 上 5% 边扰动下误分类率优于 DICE、Greedy 和 Meta-Self。

威胁模型攻击者通过添加或删除边(edge perturbation,论文称 topology attack)误导 GNN 节点分类,扰动预算为原始图已有边数的 5%(部分实验至 20%)。

问题
GNN 在半监督节点分类上表现好,但针对离散图结构的对抗鲁棒性研究少;一阶连续优化方法难以直接用于增删边的拓扑攻击。
方法
把布尔边扰动变量凸松弛到 [0,1],用 PGD 和 min-max 交替优化生成拓扑攻击,再经随机采样还原为二进制扰动;并据此构建 min-max 对抗训练提升 GCN 鲁棒性。
实验与结果
在 Cora/Citeseer 上,5% 边扰动下 CE-PGD/CW-PGD 对 natural GCN 的误分类率高于 DICE、Greedy、Meta-Self;ε=5% 对抗训练把 Cora 上 CE-PGD 攻击误分类率从 28.0% 降到 22.0%,原始图精度基本不变。
局限与可以继续做的
论文未专门讨论局限。实验仅覆盖 GCN 与 Cora、Citeseer 两个数据集,评测指标为测试节点误分类率,每组重复 5 次;未报告攻击运行时间、与图像领域对抗训练的查询成本对比等。
实验设置GCN · Cora、Citeseer · misclassification rate (1 − prediction accuracy)、attack loss (CE-type / CW-type)
威胁模型
攻击者通过添加或删除边(edge perturbation,论文称 topology attack)误导 GNN 节点分类,扰动预算为原始图已有边数的 5%(部分实验至 20%)。两种场景:a) 攻击权重 W 已知的 pre-defined GNN;b) 攻击 W 可重训练的 interactive GNN。论文聚焦 untargeted attack,受害系统为 GCN。
被测模型
GCN
基准
CoraCiteseer
指标
misclassification rate (1 − prediction accuracy)attack loss (CE-type / CW-type)
AI 导读研究者提出一种基于梯度优化的图神经网络拓扑攻击方法,与现有 GNN 对抗攻击相比,仅需少量边的增删扰动即可使半监督节点分类性能明显下降。作者称这是首个基于优化的 GNN 对抗训练方法,在面对基于梯度和贪心两类攻击时鲁棒性更高,且不牺牲原始图上的分类精度。

研究者提出一种基于梯度优化的图神经网络拓扑攻击方法,与现有 GNN 对抗攻击相比,仅需少量边的增删扰动即可使半监督节点分类性能明显下降。作者称这是首个基于优化的 GNN 对抗训练方法,在面对基于梯度和贪心两类攻击时鲁棒性更高,且不牺牲原始图上的分类精度。

深度解读

6个问题,点开问题读完整回答

  1. 这篇论文试图解决什么问题?

    解决离散图结构使一阶对抗攻击难以直接用于 GNN 的问题,并给出攻击与对抗训练方法。

    核心问题:如何对图神经网络(GNN)生成基于一阶优化的拓扑攻击(增删边),并在此基础上提升 GNN 的对抗鲁棒性。

    • 场景与重要性:GNN 在半监督节点分类上表现突出,并用于区块链、通信网络等安全相关领域,但作者称针对 GNN 对抗鲁棒性的研究很少。
    • 现有方法不足:作者称,近期工作指出传统一阶连续优化方法因图的离散性无法直接用于边操纵(topology attack);已有攻击多为贪心搜索或基于替代模型、meta-gradient 的方法。
    • 核心观察:把布尔边扰动变量松弛到其凸包 [0,1] 后,可以用 PGD 等一阶方法求解连续攻击问题,再经随机采样还原为二进制扰动。
    • 论文提出:两种拓扑攻击(PGD topology attack、min-max topology attack)和作者称为首个面向 GNN 的基于优化的对抗训练方法。
    • 威胁模型:
      • 目标:通过添加或删除边误导 GNN 的节点分类,论文聚焦 untargeted attack(也给出 targeted 的扩展形式)。
      • 知识:场景 a 攻击权重 W 已知的 pre-defined GNN;场景 b 攻击 W 可重训练的 interactive GNN。
      • 能力:只能修改边(增/删),扰动预算为已有边数的 5%(部分实验至 20%)。
      • 受害系统:GCN,在 Cora、Citeseer 上做半监督节点分类。
  2. 有哪些相关研究?

    相关工作包括图对抗攻击(Dai、Zügner 等)、图像领域一阶攻击与对抗训练(CW、Madry),作者以凸松弛一阶方法定位差异。

    图数据上的对抗攻击

    • Dai et al. (2018):研究 test-time non-targeted 攻击,只允许增删边,覆盖 white-box、practical black-box 和 restricted black-box 场景,针对图分类和节点分类。
    • Zügner et al. (2018):研究 test-time(evasion)与 training-time(data poisoning)攻击,除增删边外还可修改节点属性;基于静态替代模型设计攻击,针对单节点的 targeted attack。
    • Bojcheski and Günnemann (2018):针对无监督节点嵌入(DeepWalk)的 data poisoning 攻击,基于扰动理论最大化损失。
    • Zügner and Günnemann (2019):training-time 攻击,把图拓扑当作超参数,用 meta-gradient 解 min-max 问题;其 Meta-Self 攻击是本文在 retrained 模型场景下对比的 state-of-the-art。

    图像/音频领域的一阶攻击与鲁棒训练

    • Carlini and Wagner (2017):CW 攻击,本文借鉴其 CW-type 攻击损失和 targeted attack 的约束形式。
    • Madry et al. (2017):图像分类器的 min-max 对抗训练,本文鲁棒训练沿用该形式,并借鉴其增加模型容量(隐藏单元 16→32)的做法。

    基线与基准:攻击对比 DICE(Waniek et al., 2018)、Greedy attack(Meta-Self 去掉权重重训练的变体)和 Meta-Self;基准为 Cora 和 Citeseer 节点分类。

    定位:作者称已有工作指出一阶连续优化不适用于离散边攻击,本文通过凸松弛补上这一缺口,使梯度攻击对 GNN 可行,并称其对抗训练是首个基于优化的 GNN 对抗训练。

  3. 论文如何解决这个问题?

    将布尔边扰动凸松弛后用 PGD/min-max 一阶优化求解攻击,再用随机采样还原,并据此做 min-max 对抗训练。

    整体思路:把离散的边增删问题写成连续优化问题,用一阶方法求解后再离散化,并把同一攻击器嵌入对抗训练。方法包括 PGD topology attack、min-max topology attack 和 robust training(Algorithm 4)。

    问题形式化

    • 用布尔对称矩阵 S 编码边是否被修改,扰动后的邻接矩阵为 A′ = A + C ◦ S,其中 C = Ā − A,正项表示可添加的边、负项表示可删除的边。
    • 攻击损失可选 CE-type(负交叉熵)或 CW-type:fi = max{Zi,yi − maxc≠ yi Zi,c, −κ},κ 为置信度。
    • 两种威胁模型对应两个优化问题:固定 W 时在预算 1ᵀs ≤ ε 下最小化各节点攻击损失之和;W 可重训练时为 min-max 形式,内层对 W 最大化攻击损失以模拟重训练。

    PGD 拓扑攻击(Algorithm 2)

    • 把 s ∈ {0,1}ⁿ 松弛到凸包 [0,1]ⁿ,在约束集 S = {s | 1ᵀs ≤ ε, s ∈ [0,1]ⁿ} 上做投影梯度下降:s(t) = ΠS[s(t−1) − ηt ∇ f(s(t−1))]。
    • Proposition 1 给出投影的闭式解,涉及的对偶变量 µ 用二分法求解,作者称其在 log 速率收敛。
    • 连续解经 Algorithm 1 随机采样还原:以 s 为概率向量采样 K = 20 个二进制向量,取满足预算且攻击损失最小(实验中改为误分类率最高)的一个。

    Min-max 拓扑攻击(Algorithm 3)

    • 针对可重训练场景,用一阶交替优化:内层对 W 做梯度上升(实验设 20 步),外层对 s 做 PGD。
    • 作者称可在每次外层迭代内做多次内层最大化,以平衡计算效率与收敛精度。

    对抗训练(Algorithm 4)

    • 解 min-max 鲁棒优化问题,损失限定为 CE-type;内层对 s 跑 PGD(20 步),外层对 W 梯度上升式更新(即最小化 −f)。
    • Proposition 2 给出该问题与 max-min 形式的等价关系及 (22) ≤ (20) 的界;作者称因 f 对 s 非凸、对 W 非凹,该式与攻击问题 (7) 并不等价。
    • 设置:T = 1000,βt = 0.01,ηt = 200/√t;借鉴 Madry et al. 把 GCN 隐藏单元从 16 增至 32。
  4. 论文做了哪些实验?

    在 Cora/Citeseer 上以 5% 边扰动比较四种攻击与三个基线,并评测 ε=5%–20% 的对抗训练效果。

    实验设置

    • 被测模型:GCN(Kipf and Welling, 2016),隐藏单元默认 16,对抗训练中增至 32。
    • 数据集:Cora 和 Citeseer,无向无权边、稀疏 bag-of-words 特征;训练标记节点 Cora 140 个、Citeseer 120 个,测试标记节点均为 1000 个。
    • 基线:DICE、Greedy attack(Meta-Self 去掉权重重训练)、Meta-Self。
    • 指标:测试节点误分类率(1 − prediction accuracy),mean ± std;评测沿用 Meta-Self 的准则,用一个独立预训练模型在攻击中预测测试节点标签。
    • 重复次数:每组实验按不同训练/测试划分重复 5 次。
    • 扰动预算:默认 ε = 已有边数的 5%;对抗训练实验 ε 取 5%–20%。

    主结果

    Table 1:5% 边扰动下的误分类率(%,mean ± std)。

    表格较宽,可左右滑动

    设置方法CoraCiteseer
    —clean(无攻击)18.2 ± 0.128.9 ± 0.3
    fixed natural modelDICE18.9 ± 0.229.8 ± 0.4
    fixed natural modelGreedy25.2 ± 0.234.6 ± 0.3
    fixed natural modelMeta-Self22.7 ± 0.331.2 ± 0.5
    fixed natural modelCE-PGD28.0 ± 0.136.0 ± 0.2
    fixed natural modelCW-PGD27.8 ± 0.437.1 ± 0.5
    fixed natural modelCE-min-max26.4 ± 0.134.1 ± 0.3
    fixed natural modelCW-min-max26.0 ± 0.334.7 ± 0.6
    retrained model (20)Meta-Self29.6 ± 0.439.7 ± 0.3
    retrained model (20)CE-min-max30.8 ± 0.237.5 ± 0.3
    retrained model (20)CW-min-max30.5 ± 0.539.6 ± 0.4
    • 作者称攻击 natural model 时,CE-PGD 与 CW-PGD 的误分类率高于所有基线;PGD 攻击优于 min-max 攻击,因为攻击预定义 GCN 更容易。
    • 对 retrained model,作者称 min-max 攻击与 Meta-Self 相比有竞争力:Cora 上 CE-min-max 更高、Citeseer 上 Meta-Self 更高;作者同时指出在 (20) 的重训练模型上评测不完全公平,因为重训练权重可能是次优的。
    • Figure 1 显示 CE-PGD/CW-PGD 的攻击损失随迭代下降(T = 200,ηt = 200/√t),作者称 PGD 收敛平稳。

    对抗训练效果(Table 2、Figure 2)

    • 测了什么:Algorithm 4 在 ε = 5% 下训练 robust GCN,比较 natural/robust 模型在原始图 A 与对抗图 A′(CE-PGD 生成)上的误分类率。
    • 结果:Cora 上 A′/natural 28.0 ± 0.1 降至 A′/robust 22.0 ± 0.2,Citeseer 上 36.0 ± 0.2 降至 32.2 ± 0.4;原始图上 Cora 18.2 → 18.1、Citeseer 28.9 → 28.7(Table 2)。
    • 作者解读:作者称 ε = 5% 的鲁棒训练不损害原始图测试精度,同时降低攻击成功率;Figure 2 显示鲁棒训练损失在 1000 次迭代内下降,作者称普通训练只需 200 次迭代,鲁棒训练需要更多。

    训练预算 ε 的影响(Table 3、Figure 3)

    • 测了什么:Cora 上训练 ε ∈ {0,5,10,15,20}%、攻击 ε 同范围变化时的 CE-PGD 误分类率。
    • 结果:攻击 ε = 5% 时,训练 ε = 5% 的模型误分类率最低(22.0),训练 ε = 20% 时升到 26.5;攻击 ε = 20% 时,训练 ε = 20% 的模型为 33.5,低于 natural model 的 40.2(Table 3)。
    • 作者解读:作者称模型在训练所用 ε 约束下获得鲁棒性,并建议在 ε = 0.1 下训练以兼顾原始图性能;Figure 3 显示随 ε 增大,测试精度与 CE-PGD 攻击精度的差距增大,作者据此称大 ε 的鲁棒模型更难获得,并称鲁棒模型对 CE-PGD、CW-PGD、Greedy 三种攻击均有效。

    其他消融与分析

    • 攻击损失类型:Cora 上 CE-PGD 略高于 CW-PGD(28.0 vs 27.8),Citeseer 上 CW-PGD 更高(37.1 vs 36.0)(Table 1)。
    • min-max 内层最大化步数:固定为 20 步(6.2 节)。
    • 鲁棒训练内层最小化步数:20 步(6.3 节)。
    • 模型容量:对抗训练把隐藏单元 16 → 32(6.3 节)。
  5. 有什么可以进一步探索的点?

    论文未专门讨论局限;实验仅覆盖 GCN、两个引用网络数据集和 5%–20% 边扰动预算。

    作者指出的局限与后续方向

    • 论文未专门讨论局限。
    • 作者在 Conclusion 中称,本文可能为图数据上深度学习模型鲁棒性的理论研究和改进提供潜在途径(属作者展望,非具体局限或计划)。

    实验覆盖范围

    • 被测模型为 GCN 一种(6.1 节),隐藏单元 16(对抗训练中 32)。
    • 数据集为 Cora 和 Citeseer 两个引用网络(6.1 节),训练标记节点 140/120,测试 1000。
    • 攻击评测覆盖 DICE、Greedy、Meta-Self 三个基线和四种本文变体,预算 5%(Table 1);对抗训练评测覆盖 CE-PGD、CW-PGD、Greedy 三种攻击,训练与攻击 ε 在 5%–20%(Table 3、Figure 3)。
    • 每组实验重复 5 次,报告 mean ± std(6.1 节)。
    • 论文未报告攻击的运行时间、PGD 迭代在 min-max 攻击中的具体查询成本,也未报告 targeted attack 的实验结果(4.1 节称本文聚焦 untargeted)。
  6. 总结一下论文的主要内容

    面向 GNN 的凸松弛一阶拓扑攻击与对抗训练,在 Cora/Citeseer 上攻击强于基线、防御降低攻击成功率。

    一篇关于 GNN 对抗鲁棒性的攻击+防御论文,研究半监督节点分类中增删边(topology attack)的生成与防御。

    • 问题:图的离散性使一阶连续优化攻击难以直接用于边操纵;作者称此前 GNN 鲁棒性研究很少。
    • 方法:把布尔边扰动矩阵松弛到 [0,1],用 PGD(固定权重场景)和 min-max 交替优化(可重训练场景)求解攻击,随机采样还原二进制扰动;再把该攻击器嵌入 min-max 对抗训练(Algorithm 4),损失用 CE-type。
    • 攻击结果:5% 边扰动下,CE-PGD 在 Cora 上误分类率 28.0%、Citeseer 上 36.0%,CW-PGD 在 Citeseer 上 37.1%,均高于 DICE、Greedy、Meta-Self(Table 1);对 retrained model,CE-min-max 在 Cora 上 30.8% 高于 Meta-Self 的 29.6%,Citeseer 上则低于 Meta-Self。
    • 防御结果:ε = 5% 对抗训练把 Cora 上 CE-PGD 攻击误分类率从 28.0% 降到 22.0%,原始图误分类率 18.2% → 18.1% 基本不变(Table 2);作者称鲁棒模型对 CE-PGD、CW-PGD、Greedy 均有效,并建议训练 ε 取 0.1。
    • 作者结论:作者称只需改动少量边即可使 GNN 性能下降,其对抗训练在不损失原始图精度的情况下提升对梯度与贪心攻击的鲁棒性,并认为本文为图数据模型鲁棒性的理论研究提供了潜在途径。

相关论文

共同使用 Citeseer
再看 2 篇
共同使用 Citeseer
阅读原文arxiv.org