认证图神经网络抵御标签和结构投毒
Certifying Graph Neural Networks Against Label and Structure Poisoning
作者提出 ST-GPA,用伪标签和伪边增强图分区,作者称在 Cora-ML、PubMed 等基准上提升了对标签与结构投毒的认证精度。
针对 transductive 节点分类的训练时投毒:攻击者可在预算 rl 内翻转节点标签(label flipping)、在预算 rs 内增删改边(structure perturbations),或两者同时;防御方用分区聚合集成给出多数投票预测不变的认证。
- 图神经网络缺乏针对训练时标签翻转与结构投毒的可证鲁棒性保证;图像领域主流的 partition-and-aggregate 认证直接套用到图上时,会因标签和边的稀疏而失效。
- 提出 ST-GPA:把图的标签或边哈希分区,在每个稀疏分区上用 label propagation 协同训练与 GNN 自训练生成伪标签、用基于置信度的链接预测生成伪边,再训练 GNN 基分类器并多数投票,给出认证。
- 在 Cora-ML、PubMed 等数据集上,作者称 ST-GPA 把集成干净精度恢复到约 70%–80% 并提升认证精度;二分类 Cora-ML 上 10% 标签扰动时认证精度 36.2%,高于 LabelCert 的 32.6%(Table 4)。
- 作者指出半监督组件依赖同配性,异配图需新方法;链接预测在大而密的图上开销大,结构认证难以扩展到 ogbn-arxiv;证书紧度仅靠非自适应迁移攻击粗略检验。
- 被测模型
- GCNGATAPPNPNodeFormer
- 基准
- Cora-MLCiteSeerCoraPubMedWiki-CSAmazon-ComputersAmazon-Photoogbn-arxivCSBM 合成图
- 指标
- certified accuracyclean accuracyrobust margin
研究提出半监督框架 ST-GPA,用于在图数据标签和结构稀疏的条件下认证图神经网络抵御标签投毒与结构投毒。该方法为每个图分区补充伪标签和合成边,可适配不同架构并扩展到大量分区。在多个基准上,ST-GPA 持续且显著提升了对标签和结构投毒的鲁棒性保证,同时保持较强的干净准确率。
深度解读
这篇论文试图解决什么问题?
作者要解决图神经网络在标签与结构投毒下缺乏有效可证鲁棒性保证的问题。
核心问题:如何为图神经网络(GNN)在训练时标签翻转和结构投毒下给出有效(非空泛)的可证鲁棒性认证,同时保持干净精度。
- 场景与重要性:GNN 易受测试时和训练时的对抗扰动;作者称测试时攻击的认证已有进展,但针对训练时投毒(操纵图结构或节点标签)的认证基本未被探索。
- 现有方法的不足:图像领域最有效的投毒认证基于 partition-and-aggregate(如 DPA),但作者指出其直接用于节点分类时会失效:图数据集标签率和边密度低,分区后每个分区标签常少于类别数、子图近乎不连通,导致标签认证弱、结构认证空泛。
- 核心观察:失效根源是稀疏性。Cora-ML 用 40% 节点训练、k=281 个分区时,每分区平均仅 4 个标签(共 7 类),认证上限被限制在 140 次标签翻转;k>50 时分区内平均度接近 0(Figure 2、3)。
- 论文方案:提出半监督框架 ST-GPA(deep Self-Training Graph Partition Aggregation),为每个分区生成伪标签和伪边,再训练 GNN 集成并多数投票认证;作者称其为首个针对节点分类标签与结构投毒的有效认证。
- 威胁模型:
- 攻击者目标:在训练时污染图数据,使节点分类预测改变。
- 扰动类型:label flipping(预算 rl 内翻转标签)、structure perturbations(预算 rs 内增删改边),或两者联合(Eq. (1))。
- 受害系统:transductive 半监督节点分类的 GNN(GCN、GAT、APPNP 等)。
- 防御目标:给出多数投票预测在预算内不变的认证(certified accuracy)。
有哪些相关研究?
相关工作分四类:图对抗攻击与测试时认证、图像投毒认证、图投毒认证、半监督自训练。
图上的对抗攻击与测试时认证
- Zügner et al. (2018)、Dai et al. (2018)、Zügner & Günnemann (2019)、Mujkanovic et al. (2022) 等——研究消息传递 GNN 在测试时和训练时扰动下的对抗鲁棒性上界;Foth et al. (2025) 扩展到 graph transformer。
- Günnemann (2022)、Scholten et al. (2022, 2023)、Hojny et al. (2024)——图领域测试时攻击的鲁棒性认证。
图像领域的投毒认证
- Levine & Feizi (2021) 的 Deep Partition Aggregation(DPA)——分区训练独立分类器并多数投票,是本文直接推广的对象;后续工作包括 Wang et al. (2022)、Chen et al. (2022)、Rezaei et al. (2023) 等,论文指出该范式主要在图像领域研究。
- Weber et al. (2023)(训练数据上的随机平滑)与 Ma et al. (2019)(差分隐私)——图像投毒认证的另外两条路线。
图上的投毒认证
- Lai et al. (2024b)——针对节点注入的集体概率认证(基于随机平滑),论文指出其不适用于本文的扰动模型。
- Gosch et al. (2025)、Sabanayagam et al. (2025)(LabelCert)——节点特征与标签投毒认证,论文指出其限于 infinite-width GNN,且 LabelCert 只能处理 100–200 个训练标签以内的数据集;Mohgaonkar et al. (2026) 将其扩展到图像,但同样限于 infinite-width 且未研究图。
- Li et al. (2025)(PGNNCert)——用分区做 GNN 投毒认证;论文指出其不认证标签翻转,结构认证低于 MLP 基线(即空泛),特征认证只适用于图分类。
半监督与自训练
- Li et al. (2018)——用 ParWalks 生成伪标签配合自训练应对低标签率,本文改用 label propagation 替代 ParWalks 以提升可扩展性;Li et al. (2024)、Lee & Park (2025) 将自训练用于经验防御。
基线与基准:对比基线为无半监督学习的朴素分区集成、MLP 基线(结构扰动下天然鲁棒)、LabelCert(Table 4)与 PGNNCert(附录 E.2);基准为 Cora-ML、CiteSeer、Cora、PubMed 等节点分类数据集。
作者定位:本文是首个在节点分类任务上同时对标签与结构投毒给出有效、非空泛认证的方法。
论文如何解决这个问题?
ST-GPA:把 DPA 推广到非 i.i.d 图数据,再用伪标签与伪边克服分区后的稀疏性。
整体思路:先把图像领域的 partition-and-aggregate 认证推广到非 i.i.d. 结构化数据(Generalized DPA),再在ST-GPA 框架下用半监督学习给每个稀疏分区补充伪标签和伪边,使分区集成在图上既保持干净精度又能给出认证。
问题设定与扰动模型
- 研究属性无向图上的半监督 transductive 节点分类:训练时可见全图,但只有部分节点有标签(yi = −1 表示未标注)。
- 投毒图集合定义为以干净图为中心的球 Brl,rs(G) = {G̃ ∣ δ(ỹ,y) ≤ rl, Δ(Ẽ,E) ≤ rs},其中 δ 是标签向量的 Hamming 距离,∆ 是边集的对称差;rl、rs 分别约束标签与结构扰动预算,覆盖标签翻转、结构投毒及两者联合三种模型。
Generalized DPA 与图的认证条件
- 关键观察:认证不依赖数据 i.i.d.,而依赖分区方案 h 使任一被毒化对象只影响一个分区。论文给出 Generalized DPA(Thm. 3.1):当 dh·d(D, D̃) 不超过鲁棒边际 rm(D, x) = ⌊(nc − maxc′≠c (nc′ + 1c′<c))/2⌋ 时,多数投票预测不变。
- 图的分区哈希基于节点特征:边用两端节点特征拼接哈希,标签用对应节点特征哈希(Eq. (5)),实验中用 MD5;每条边/每个标签恰属一个分区,故 dh = 1。
- 三种威胁模型分别用 Hamming 距离、边集对称差、两者之和作为距离(修改一条边计 ∆=2、影响两个分区),代入 Thm. 3.1 得到 Eq. (6)–(8) 的认证条件。
伪标签生成(针对标签翻转)
- 协同训练(co-training):用 label propagation(Zhu & Ghahramani, 2003)替代 Li et al. (2018) 的 ParWalks,按 S(i+1) = α Ã S(i) + (1−α)Y 传播标签分数(1−α 为 teleport 概率),避免求 Laplacian 逆,可扩展到大图。
- 自训练(self-training):在现有标签上训练 GNN,取 softmax 置信度最高的预测作为伪标签进入后续训练。
- 超参数 t 控制每类添加的高分伪标签数量;两种方法可串联,论文采用先协同训练再自训练的顺序(Algo. 1)。
伪边生成(针对结构投毒)
- 基于同配性假设:在每个分区内先训一个 GNN 得到节点预测与置信度,迭代地在最可能同类的节点对之间加边,再用扩充后的边集训第二个 GNN 用于认证(Algo. 2)。
- 超参数 ε 控制每个分区添加的边数相对于原图的倍数;论文指出现代链接预测方法在稀疏分区上效果差,故采用该置信度方案。
- 朴素实现约 O(kn²) 时空复杂度,论文在附录 D.1 给出基于全局边候选堆的近线性算法。
联合认证与成功判定
- 联合认证:同时分区标签与边,按链接预测 → label propagation 协同训练 → 自训练的顺序迭代生成伪边和伪标签,再训练基分类器、多数投票并计算鲁棒边际(附录 D.2,Algo. 4)。
- 评测指标为 certified accuracy:预测正确且鲁棒边际满足认证条件的测试节点比例,报告为扰动大小的函数。
论文做了哪些实验?
在 4 个引用数据集、3 种 GNN 上评测三种投毒模型的认证精度,并含扩展性、同配性与迁移攻击分析。
实验设置
- 被测模型:GCN、GAT、APPNP 作为基分类器(附录 B.4 另测 NodeFormer);MLP 作为结构扰动下的对照基线(不用边,天然鲁棒)。
- 数据集:Cora-ML、CiteSeer、Cora、PubMed(30%-10%-30% 划分,仅 30% 训练标签可用);标签认证另在 Wiki-CS、ogbn-arxiv(取 1/10 训练标签)和 Amazon-Computers、Amazon-Photo 上评测;附录 H 用 CSBM 合成图。
- 基线:无半监督学习的朴素分区集成(虚线)、MLP 基线(结构扰动图)、LabelCert 与 PGNNCert(附录 E)。
- 指标:certified accuracy(预测正确且满足认证条件的测试节点比例),随扰动数量变化作曲线。
- 默认超参数(Table 3):k 默认 LF=80、SP=800、LF&SP=200;t=50;α=0.9;ε 按数据集设定、上限 20;训练 200 epoch、Adam、lr=0.01。
- 重复次数:至少 3 个确定性种子,图中彩色区域为标准差。
主结果
主结果以认证精度曲线呈现(Figure 4),坐标轴上可读的关键数值如下(据 Figure 4 及正文):
设置 数据集 / k 关键数值 标签翻转(LF) Cora-ML, k=80 朴素分区集成干净精度仅约 40%;ST-GPA 恢复到约 70%–80% 标签翻转(LF) PubMed, k=500 作者称认证精度同样有提升(曲线 Figure 4(b)) 结构投毒(SP) Cora-ML, k=800 朴素集成干净精度低于 MLP 基线(约 74%),认证空泛;ST-GPA 恢复并减缓下降 结构投毒(SP) PubMed, k=800 同上趋势(Figure 4(d)) 联合(LF&SP) PubMed, k=250 ST-GPA 相对朴素分区有提升(Figure 4(e)) - 作者称 ST-GPA 把集成干净精度恢复到约 70%–80%,并使认证精度曲线下降更慢,即同等扰动下认证精度更高。
- 作者指出 Cora-ML 上朴素结构分区的集成干净精度甚至低于 MLP,使朴素方法无效。
- 不分区训练的 GCN 干净精度作为参考(Cora-ML 约 78.77%,Table 2),其非零扰动下认证精度为 0%。
架构通用性与分区数扩展性
- 测了什么:Figure 6(a)–(c) 对 GCN、GAT、APPNP 比较有无 ST-GPA 的认证精度。
- 结果:作者报告三种模型趋势一致,干净精度提升到 LF 约 80%、SP 约 76%、联合约 67%;附录 B.4 报告 NodeFormer 上认证精度从 20% 提升到 70% 以上(Cora-ML,k=40)。
- 作者解读:认证与架构无关,可兼容更强的 GNN。
- 分区数 k:Figure 6(d)–(f) 与 Figure 11 显示 k 增大时基线因稀疏性下降,而 ST-GPA 在 k 高达 1600(结构)时仍保持;作者称链接预测使 k 理论上不受限。标签分区超过约 100 时(Cora-ML,30% 训练标签)会出现无标签分区,训练不可行。
与现有认证的对比
- LabelCert(附录 E.1,Table 4):二分类 Cora-ML 上,5% 标签扰动时 ST-GPA 66.5% vs LabelCert 68.7%;10% 扰动时 ST-GPA 36.2% vs LabelCert 32.6%。作者称自家方法在 10% 预算下更优,且可扩展到 LabelCert 无法处理的规模。
- PGNNCert(附录 E.2,Figure 17):在 Li et al. (2025) 的数据划分上,PGNNCert-N(k=60)在 Cora-ML、CiteSeer、Cora 上均低于 MLP 基线;ST-GPA(k=60 与 k=600)高于 MLP 基线。
- 大图扩展(附录 B.3,Figure 12):标签认证在 Wiki-CS、Amazon-Computers、Amazon-Photo、ogbn-arxiv 上恢复干净精度并提升认证精度;作者称结构认证难以扩展到这类大而密的图。
其他消融与分析
- 训练顺序(Figure 5(a)、Figure 8):先协同训练再自训练在标签翻转上效果最好,各数据集一致。
- LP vs ParWalks(Figure 5(b)、Figure 10):两者认证精度接近,CiteSeer 上 LP 约低 10%;作者称 LP 训练时间更短、可扩展。
- 联合认证轮数(Figure 5(c)、Figure 9):第一轮提升最大,更多轮数收益递减;小数据集上联合认证受 k 限制(约 10),对 1 次扰动也几乎无可用认证,但干净精度提升 15%–20%。
- 超参数(Figure 14、15):Cora-ML 上 t 的合适区间约 50≤t≤200;α 在 0.01–0.99 间性能平稳;最优 ε 因数据集而异。
- 迁移攻击(附录 G,Figure 18):用 Meta-PGD 从 GCN 代理迁移对抗边(k=800),鲁棒精度基本不降;作者归因于攻击的非自适应性,并指出针对分区集成的自适应投毒攻击是未来方向。
- 同配性(附录 H,Figure 19、20):CSBM 上两类认证从 60% 同配性开始产生收益,70% 以上效果强(Cora 为 81%)。
有什么可以进一步探索的点?
作者指出同配性依赖与链接预测开销两大局限;实验覆盖 3 种 GNN 与 8 个数据集。
作者指出的局限与后续方向
- 异配图适用性(Sec. 8):半监督组件依赖同配性,作者称这限制了对异配图的适用性;应对异配性需要新的 label propagation 或链接预测方法,各自是独立的研究挑战,但分区与自训练的核心思想仍适用。
- 链接预测的计算开销(Sec. 8):结构认证所需的链接预测在更密、更大的图上内存与耗时增加,无法有效扩展到 ogbn-arxiv 这类大数据集(附录 F 的扩展性分析);作者称多数链接预测算法面向完整图而非稀疏分区,替代方案并非易事。
- 证书紧度与自适应攻击(附录 G):迁移攻击无法评估紧度,作者认为需要针对分区集成方法的自适应投毒攻击,同时优化对抗边与分区方案及集成决策,是重要的未来方向。
- 紧度行为推测(附录 G):作者引用 Mohgaonkar et al. (2026) 在图像上的发现(小 k 偏保守、大 k 趋紧),认为图上可能类似。
实验覆盖范围
- 被测基分类器为 GCN、GAT、APPNP 共 3 种,附录 B.4 另测 NodeFormer;主实验在 Cora-ML、CiteSeer、Cora、PubMed 上进行。
- 标签认证另在 Wiki-CS、Amazon-Computers、Amazon-Photo、ogbn-arxiv 上评测;结构认证未在大而密的数据集上报告结果(Sec. 8、附录 B.3)。
- 与现有认证的对比:LabelCert 仅在二分类 Cora-ML 上(Table 4),PGNNCert 仅在 Cora-ML、CiteSeer、Cora 上(Figure 17)。
- 紧度检验仅用 Meta-PGD 从 GCN 代理的迁移攻击(k=800),论文未报告自适应攻击实验。
- 每个实验至少 3 个种子;训练用单张 NVIDIA GTX1080Ti,链接预测用单 CPU 核(附录 F)。
总结一下论文的主要内容
ST-GPA 用自训练增强图分区,作者称实现了节点分类上标签与结构投毒的有效认证。
一篇关于 GNN 投毒鲁棒性认证的防御论文,提出 ST-GPA 框架。
- 问题:图像领域的 partition-and-aggregate 投毒认证直接用于图节点分类时,因标签与结构稀疏而失效——Cora-ML 上 k=281 个标签分区时每分区平均仅 4 个标签(7 类),认证上限 140 次翻转;k>50 时结构分区近乎不连通。
- 方法:先将 DPA 推广到非 i.i.d. 结构化数据(Generalized DPA,Thm. 3.1),再用 label propagation 协同训练与 GNN 自训练生成伪标签、用基于置信度的链接预测生成伪边,训练分区集成并多数投票认证。
- 结果 1:作者称 ST-GPA 把分区集成干净精度恢复到约 70%–80%,并在 Cora-ML、PubMed 上对标签翻转、结构投毒及两者联合提升认证精度(Figure 4)。
- 结果 2:对 GCN、GAT、APPNP 趋势一致(LF 约 80%、SP 约 76%、联合约 67%),NodeFormer 上认证精度从 20% 升至 70% 以上;结构认证可扩展到 k=1600。
- 结果 3:二分类 Cora-ML 上 10% 标签扰动时认证精度 36.2%,高于 LabelCert 的 32.6%(Table 4);PGNNCert-N 在三个数据集上均低于 MLP 基线,而 ST-GPA 高于之(Figure 17)。
- 结果 4:CSBM 实验显示两类认证从 60% 同配性起产生收益;Meta-PGD 迁移攻击对 k=800 的集成基本无效。
- 作者结论:自训练对图上的分区认证是关键,该方向对图以外的半监督场景可能也有价值;局限在于同配性依赖和链接预测在大图上的开销。