跳到正文
原文

迈向 GNN 的高效通用鲁棒训练框架

Towards an Efficient and General Framework of Robust Training for Graph Neural Networks

arXiv· arXiv:2002.10947· ICASSP 2020· Kaidi Xu, Sijia Liu, Pin-Yu Chen, Mengshu Sun, Caiwen Ding, Bhavya Kailkhura, Xue LinElectrical & Computer Engineering, Northeastern University; MIT-IBM Watson AI Lab, IBM Research; Computer Science and Engineering, University of Connecticut; Lawrence Livermore National Laboratory本站收录· 23 天前· 原文发表防御

论文速读

防御

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

作者提出基于贪心搜索与零阶方法的 GNN 鲁棒训练框架,在 Cora 上 GTA 攻击耗时 37 秒,低于 CE-PGD 的 147 秒(Table 3)。

威胁模型攻击者在测试时对图结构做拓扑扰动(增删边),扰动边数上限为 M,邻接矩阵保持对称且元素为 0/1;攻击阶段可使用由独立预训练模型生成的测试节点预测标签。

问题
GNN 容易被图结构上的对抗扰动误导,而现有基于凸松弛的鲁棒训练方法计算开销大、难以用于大图,且依赖梯度信息,在模型参数不可用时失效。
方法
作者提出贪心拓扑攻击 GTA 及其零阶版本 ZO-GTA 生成离散结构扰动,并将其嵌入 min-max 对抗训练的内层最大化,构成可替换攻击模块的通用鲁棒训练框架。
实验与结果
在 Cora、Citeseer、Pubmed 上,GTA/ZO-GTA 的误分类率与 CE-PGD、CW-PGD 接近,运行时间更低(Cora 上 37 秒对 147 秒);基于 GTA 的鲁棒训练在 Cora 上与 CE-PGD 训练的鲁棒性接近。
局限与可以继续做的
论文未专门讨论局限。实验仅覆盖 GCN 与三个引用网络数据集,防御评估只在 Cora 上进行,攻击仅考虑拓扑扰动,CE-PGD 与 CW-PGD 在 Pubmed 上不可行。
实验设置Graph Convolutional Network (GCN) · Cora、Citeseer 等 · misclassification rate、running time
威胁模型
攻击者在测试时对图结构做拓扑扰动(增删边),扰动边数上限为 M,邻接矩阵保持对称且元素为 0/1;攻击阶段可使用由独立预训练模型生成的测试节点预测标签。防御方为 GCN 节点分类模型,鲁棒训练分两种设定:已知模型参数与梯度(GTA),以及梯度不可用(ZO-GTA,gradient-free)。
被测模型
Graph Convolutional Network (GCN)
基准
CoraCiteseerPubmed
指标
misclassification raterunning time
AI 导读一种面向 GNN 的通用鲁棒训练框架结合贪心搜索与零阶方法,用于抵御图结构或节点属性扰动,在多个应用中显著降低计算开销,部分场景的鲁棒性优于当前最优方法。现有鲁棒 GNN 方法多局限于已知模型参数、依赖梯度和凸松弛的白盒设置,难以扩展到时间敏感任务与大规模图数据;该框架针对这些限制,可覆盖传统鲁棒训练难以处理的大规模问题。

一种面向 GNN 的通用鲁棒训练框架结合贪心搜索与零阶方法,用于抵御图结构或节点属性扰动,在多个应用中显著降低计算开销,部分场景的鲁棒性优于当前最优方法。现有鲁棒 GNN 方法多局限于已知模型参数、依赖梯度和凸松弛的白盒设置,难以扩展到时间敏感任务与大规模图数据;该框架针对这些限制,可覆盖传统鲁棒训练难以处理的大规模问题。

深度解读

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

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

    作者称现有 GNN 鲁棒训练计算开销大、依赖梯度,提出基于贪心与零阶方法的通用框架。

    核心问题:如何在大规模图数据上、甚至在梯度不可用时,对 GNN 做对抗鲁棒训练。

    • 问题场景:GNN 已用于节点分类等任务,但作者称精心设计的图结构或节点属性扰动会使其预测出错,在 high-regret 应用中带来安全顾虑。
    • 现有方法不足:作者称现有鲁棒训练方法(如 [12, 13])依赖对离散图域做凸松弛,引入额外计算,在大图上不可行;且只适用于已知模型参数的 white-box 设定。
    • 核心观察:对抗训练的性能取决于对抗样本质量和攻击算法的效率;离散约束使梯度下降不能直接用于内层最大化,作者用贪心搜索和零阶方法处理离散约束。
    • 论文提出:两个攻击方法 GTA(Greedy Topology Attack)和 ZO-GTA(Zeroth-order GTA),以及一个可替换攻击模块的通用鲁棒训练框架(Algorithm 3)。
    • 威胁模型:
      • 攻击者目标:通过扰动图结构(增删边)使 GCN 在测试节点上误分类。
      • 知识与能力:扰动边数上限为 M,邻接矩阵保持对称且元素为 0/1;攻击时可使用由独立预训练模型生成的测试节点预测标签(非真实标签)。
      • 梯度可得性:GTA 对应梯度可用的 white-box 设定;ZO-GTA 针对梯度不可用(模型参数不可访问或模型本身离散)的 gradient-free 设定。
      • 受害系统:在 Cora、Citeseer、Pubmed 上做节点分类的 GCN。
  2. 有哪些相关研究?

    相关工作分 GNN 攻击与防御两类,本文以 [13] 的 CE-PGD/CW-PGD 为主要对比基线。

    GNN 上的对抗攻击

    • Dai 等 [14](2018)——研究测试时非定向攻击,通过增删边攻击图分类与节点分类。
    • Zügner 等 [15](2018)——同时考虑测试时(evasion)与训练时(data poisoning)攻击,允许修改节点属性,针对单个节点的定向攻击;论文指出其与 [14] 的不同在于允许修改节点属性。
    • Zügner 与 Günnemann [16](2019)——训练时攻击,用 meta-gradients 解 min-max 问题,把图拓扑当作超参数优化。

    GNN 上的防御

    • Xu 等 [13](IJCAI 2019)——提出 GNN 对抗训练;论文指出该方法需要凸松弛、概率采样和二分搜索,额外计算开销大,对大图数据集不可行。
    • Zügner 与 Günnemann [12](KDD 2019)——研究可认证鲁棒性(certifiable robustness),在预先给定的界内得到鲁棒模型;论文指出其不同于对抗训练路线。

    基线与基准

    • 基线攻击方法:DICE [20]、CE-PGD 与 CW-PGD [13],攻击实验沿用 [13] 的超参数与实验设置。
    • 基线防御方法:[13] 的 CE-PGD 对抗训练,在 Cora 上对比。
    • 基准:Cora、Citeseer、Pubmed 三个节点分类数据集 [18]。

    作者将本文定位为:用贪心搜索与零阶方法替代凸松弛路线,使鲁棒训练在大图和梯度不可用的场景下仍可行,并称这是 general 的框架。

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

    用贪心搜索(GTA)或零阶贪心(ZO-GTA)生成离散拓扑攻击,嵌入 min-max 对抗训练内层。

    整体思路:把图对抗训练写成 min-max 问题,内层用能处理离散约束的贪心攻击近似最大化损失,外层用梯度下降更新模型权重,框架名为 GTA/ZO-GTA + Robust Training(Algorithm 3)。

    问题形式化

    • 采用 [17] 的对抗训练形式:minW maxA′ ∈ C L(A′, W; X, yL),其中 L 为训练节点上的交叉熵损失,A' 为扰动后的邻接矩阵。
    • 约束 C 包括:最多扰动 M 条边、A' 对称、A' ∈ {0,1}^(N×N);离散约束使梯度下降不能直接用于内层最大化。

    Greedy Topology Attack(GTA,Algorithm 1)

    • 固定节点属性 X,只扰动边;攻击目标是最大化训练损失,即最小化 −L(A'; W, X, y_L)。
    • 每轮计算损失对 A' 的梯度,与翻转后的邻接矩阵做逐元素乘,得到可增删边的候选及梯度值;一次取梯度最大的至多 n 条边同时修改,作者称这使攻击加速约 n 倍。
    • 只扰动上三角并镜像到下三角以保持对称,因此循环条件为扰动量小于 2M;已修改的边记入集合 R 避免重复改动。

    Zeroth-order GTA(ZO-GTA,Algorithm 2)

    • 针对梯度不可得或 g_A' 过密导致 GTA 在超大图上不可行的场景,不计算梯度。
    • 每轮随机选 n 个元素翻转,若训练损失增大则保留,否则翻回;保持 A' 的离散性。

    鲁棒训练流程(Algorithm 3)

    • 共 T 轮:内层固定 W,用 GTA(或 ZO-GTA、CE-PGD)解最大化得到 A';外层固定 A',以学习率 β 做一步梯度下降更新 W。
    • 作者称该框架通用,内层可替换为任何满足约束的攻击方法,不同攻击得到不同鲁棒程度的模型。
    • 实验中使用的参数:T = 1000,β = 0.01,M = 0.05N,n = 0.05N。
  4. 论文做了哪些实验?

    在三个引用网络上测攻击误分类率与耗时,并在 Cora 上比较 GTA 与 CE-PGD 鲁棒训练。

    实验设置

    • 被测模型:GCN [2],做节点分类。
    • 数据集:Cora(2,708 节点、5,429 边、7 类)、Citeseer(3,327 节点、4,732 边、6 类)、Pubmed(19,717 节点、44,338 边、3 类)(Table 1)。
    • 基线攻击:DICE、CE-PGD、CW-PGD,沿用 [13] 的超参数与设置。
    • 指标:误分类率(1 − 测试节点预测准确率)与运行时间(秒)。
    • 协议:重复 5 次、不同训练/测试划分,报告 mean ± std;攻击时使用独立预训练模型生成的测试节点预测标签(沿用 [16, 13])。
    • 参数:M = 0.05N;n 在 [0.01N, 0.2N] 内搜索后取 n = 0.05N;鲁棒训练 T = 1000、β = 0.01。

    主结果

    攻击性能(误分类率 %,据 Table 2)与运行时间(秒,据 Table 3):

    表格较宽,可左右滑动

    方法Cora 误分率Citeseer 误分率Pubmed 误分率Cora 时间Citeseer 时间
    Clean18.2 ± 0.128.9 ± 0.316.9 ± 0.5——
    GTA25.8 ± 0.135.2 ± 0.119.3 ± 0.437 ± 136 ± 1
    ZO-GTA24.9 ± 0.333.1 ± 0.318.8 ± 0.519 ± 321 ± 3
    DICE18.9 ± 0.329.8 ± 0.417.4 ± 0.6未报告未报告
    CE-PGD28.0 ± 0.136.0 ± 0.2不可行147 ± 4144 ± 4
    CW-PGD27.8 ± 0.437.1 ± 0.5不可行151 ± 5142 ± 2
    • 作者称 GTA/ZO-GTA 与梯度方法 CE-PGD、CW-PGD 表现相当(competitive),误分类率略低但计算效率更高。
    • Pubmed 上 GTA 耗时 109 ± 5 秒、ZO-GTA 43 ± 5 秒,CE-PGD 与 CW-PGD 在该数据集上不可行(Table 3)。
    • ZO-GTA 误分类率低于 GTA,作者认为这是由于 ZO-GTA 是不用梯度的近似方案。

    防御性能(Table 4)

    • 测了什么:在 Cora 上比较 GTA 鲁棒训练与 CE-PGD 鲁棒训练,分别用 GTA 和 CE-PGD 攻击评测。
    • 结果:GTA 训练模型在 clean 下 18.1 ± 0.2%、GTA 攻击下 20.4 ± 0.3%、CE-PGD 攻击下 22.7 ± 3%;CE-PGD 训练模型对应为 18.0 ± 0.3%、20.8 ± 0.4%、22.0 ± 0.2%。
    • 作者解读:两者鲁棒性相当,但 GTA 训练计算开销低,适合时间敏感任务与大图。

    超参数 n 的影响(Figure 1)

    • 测了什么:固定 M = 0.05N,n 从 0.01N 变化到 0.2N,观察 GTA/ZO-GTA 在 Cora 与 Citeseer 上的误分类率。
    • 结果:作者称误分类率随 n 增大而下降,且 GTA 整体高于 ZO-GTA;n 越小需要的攻击迭代越多。后续实验取 n = 0.05N。

    其他消融与分析

    • 贪心步长 n:Figure 1,n ∈ [0.01N, 0.2N],误分类率随 n 增大而下降(作者称)。
    • 内层攻击选择:防御实验用 GTA 而非 ZO-GTA 做内层最大化,理由是 GTA 误分类率更高(4.3 节)。
    • 例外:CE-PGD 攻击下 GTA 训练模型的标准差为 ± 3,大于其他设置(Table 4),论文未解释。
  5. 有什么可以进一步探索的点?

    论文未专门讨论局限;实验仅覆盖 GCN、三个引用网络,防御评估只在 Cora 上。

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

    论文未专门讨论局限,没有 Limitations 或 Future Work 小节。Conclusion 中作者称所提方法是大规模和时间敏感问题的潜在可行方案(potentially viable candidate),未列出明确的后续研究方向。

    实验覆盖范围

    • 被测模型仅为 GCN 一种架构(4.1 节)。
    • 数据集为 Cora、Citeseer、Pubmed 三个引用网络(Table 1);攻击实验覆盖全部三个,防御(鲁棒训练)评估只在 Cora 上进行(4.3 节)。
    • 攻击仅考虑拓扑扰动(增删边),GTA 固定节点属性 X(3.2.1 节);扰动预算固定为 M = 0.05N(4.2、4.3 节)。
    • 防御评估只与 [13] 的 CE-PGD 对抗训练对比,评测攻击为 GTA 与 CE-PGD 两种(4.3 节)。
    • 每个实验重复 5 次并报告 mean ± std(4.1 节);论文未报告鲁棒训练的总训练耗时,只报告了攻击生成时间(Table 3)。
  6. 总结一下论文的主要内容

    作者提出 GTA/ZO-GTA 攻击与通用 GNN 鲁棒训练框架,称其在保持鲁棒性的同时降低计算开销。

    一篇关于 GNN 对抗鲁棒训练的防御类论文,针对现有基于凸松弛的鲁棒训练在大图上不可行、且依赖梯度的问题。

    • 方法:提出贪心拓扑攻击 GTA(利用梯度、每轮最多改 n 条边)与零阶版本 ZO-GTA(随机翻转、按损失取舍),嵌入 min-max 对抗训练的内层;框架允许替换任意满足离散约束的攻击(Algorithm 3)。
    • 攻击效果:在 Cora 上 GTA 误分类率 25.8 ± 0.1%,CE-PGD 为 28.0 ± 0.1%;Citeseer 上分别为 35.2 ± 0.1% 与 36.0 ± 0.2%(Table 2)。
    • 效率:Cora 上 GTA 耗时 37 ± 1 秒,CE-PGD 147 ± 4 秒;Pubmed 上 GTA 109 ± 5 秒,CE-PGD/CW-PGD 不可行(Table 3)。
    • 防御效果:Cora 上 GTA 鲁棒训练模型在 GTA 攻击下误分类率 20.4 ± 0.3%、CE-PGD 攻击下 22.7 ± 3%,与 CE-PGD 训练模型(20.8 ± 0.4%、22.0 ± 0.2%)接近(Table 4)。
    • 作者结论:作者称该框架计算开销明显更低、在某些情况下更鲁棒,使大规模、时间敏感场景下的 GNN 鲁棒训练成为可能。

相关论文

共同使用 Citeseer
再看 3 篇
共同使用 Citeseer
阅读原文ICASSP 2020