Lethe: Link Inference Attacks For Evaluation of Edge Unlearning Methods

会议: NeurIPS 2026
arXiv: 2610.21869
OpenReview: https://openreview.net/forum?id=5Fexig0zwY
代码: https://github.com/dangeloandrea14/Lethe
领域: 安全
关键词: 图遗忘学习, 边遗忘, 链路推理攻击, WalkCentrality, 隐私评测

一句话总结

针对现有图神经网边遗忘评估过度依赖小图与无信息准确率的缺陷，本文提出了首个覆盖 15 种算法与 8 个数据集的系统基准 Lethe，设计了基于游走中心性的遗忘边难度分级与链路推理攻击评测体系。

研究背景与动机

随着通用数据保护条例（GDPR）对“被遗忘权”的法律刚性约束，图遗忘学习（Graph Unlearning, GU）成为图学习安全与隐私领域的研究热点。在很多涉及敏感个人信息的应用（如社交网络好友交互、金融交易、医疗关联）中，敏感信息往往天然由图中的“边”承载。边遗忘（Edge Unlearning, EU）的目标是在完全不重新全量训练模型的前提下，抹除特定边在图神经网络（GNN）参数与隐藏表示中的痕迹，同时保留其余图拓扑与节点的预测效用。

然而，现有边遗忘评估方案存在两大约束性的系统漏洞。第一，学术界长期局限于 Cora、Citeseer、Pubmed 等极小规模且特征占绝对主导的数据集；在这些小图上，从头重新训练（Gold Model）只需数秒，专用遗忘算法非但没有计算加速，反而由于框架开销或高阶感染节点传播，导致遗忘耗时甚至大幅超过从头重训。第二，传统评估以测试集分类准确率作为遗忘质量的代理指标，但在节点特征丰富或拓扑稀疏的大图上，即使随机移除高达 50% 的边，重新训练的模型分类准确率波动也低于 5%（与 DropEdge 现象一致），导致传统准确率与经典的成员推理攻击（如 UMIA）在边遗忘上完全失效，根本无法反映模型是否真正抹除了被删边的隐私痕迹。

本文的切入角度是：边遗忘本质上由图拓扑结构驱动，必须在大规模图上通过对抗性链路重构来检验隐私泄漏，并依据边在消息传递机制中的结构冗余度划分遗忘难度。核心 idea：构建首个大规模边遗忘基准 Lethe，基于消息传递传播强度提出 WalkCentrality 难度切分指标，并标准化三种对抗性链路推理攻击替代代理准确率，系统揭示现有遗忘算法对低中心性关键边防御普遍崩溃的真实缺陷。

方法详解

整体框架

Lethe 包含规范化的数据集筛选准则、结构驱动的遗忘集选取机制、统一的黑盒对抗链路推理攻击，以及支持 15 种遗忘算法的模块化执行流水线。评测流程首先在大规模图上训练原始模型；随后根据边在归一化邻接矩阵上的消息传递冗余度（WalkCentrality）将遗忘任务划分为低中心性（高暴露度）与高中心性（高冗余度）不同难度；接着运行目标遗忘算法生成遗忘后模型；最后在保留图上同时发起三种链路推理攻击与下游分类效用评估，以对抗攻击的 ROC-AUC 指标（理想无泄漏基线为 0.5）客观量化信息遗忘程度。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入大图与训练集<br/>G=(N,E,X) & 初始模型 M*"] --> B["WalkCentrality 难度分级<br/>计算边在消息传递中的冗余度"]
    B --> C["遗忘集构建与切分<br/>低中心性 / 高中心性 5% 边集"]
    C --> D["边遗忘算法执行<br/>通用机器遗忘 / 专用图遗忘"]
    D --> E["保留图 G' 上的链路推理攻击<br/>E-UMIA / LinkTeller / LinkStealing"]
    E --> F["双重指标综合评估<br/>模型效用保留 vs 隐私防泄漏 AUC"]

关键设计

1. 基于游走中心性（WalkCentrality）的遗忘难度建模：量化边在消息传递路径中的拓扑冗余度

现有文献均采用随机均匀采样构建遗忘边集，忽略了不同边在 GNN 邻域聚合中所处拓扑位置的根本差异。在 GCN 类对称归一化传播体系 \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\)（其中 \(\tilde{A}=A+I\)）下，任意一条边参与的 \(k\) 步随机游走构成了节点表示对该边的依赖程度。如果一条边两端的节点本身具有极高连通度，替代路径众多，则该边被移除后其信号极易被周围拓扑吸收；相反，桥接稀疏区域的关键边被移除后，其端点表示将发生不可代偿的显著偏移。为了剥离边自身权重的自环干扰并精确刻画局部传播环境，Lethe 将边 \((i, j)\) 在 \(k\) 层网络中的游走中心性定义为各阶段流入源与流出目标的双向游走加权和：

\[\text{WalkCentrality}(i,j) = \sum_{t=0}^{k-1} (\mathbf{1}^\top \hat{A}^t)_i \cdot (\hat{A}^{k-t-1} \mathbf{1})_j\]

该指标通过预计算游走向量可在 \(O(k \cdot |E|)\) 的线性时间内高效完成。在 Lethe 中，按 WalkCentrality 最低与最高选取 5% 边分别构建低中心性（困难任务）与高中心性（简单任务）遗忘集，为边遗忘算法提供了严格的拓扑难度上下界。

2. 结构化对抗链路推理攻击标准化：替代失真的分类准确率

为了解决传统准确率与基于损失的成员推理攻击对边删除完全不敏感的痛点，Lethe 建立了规范化的白盒模型与保留图黑盒攻击威胁模型。攻击者掌握遗忘后模型 \(M_u\) 与保留图 \(G'=(N, E \setminus E_f, X)\)，目标是将候选边判别为已遗忘边（正例）或从未存在的无关联边（负例）。Lethe 统合了三类机制互补的推断攻击： - 边成员推理（E-UMIA）：针对遗忘边 \(k\)-跳邻域内受影响的“受感染节点”，提取交叉熵损失分布并训练逻辑回归分类器。 - 影响函数推断（LinkTeller, LT）：利用一阶有限差分探测端点特征扰动对目标节点隐藏表示的定向导数：

\[s(u,v) = \left\lVert \frac{M_u(X + \varepsilon \mathbf{x}_v \mathbf{e}_v^\top, G')[u] - M_u(X, G')[u]}{\varepsilon} \right\rVert_2\]

若模型参数仍残留边记忆，该扰动影响将显著超出真实负样本。 - 输出后验推断（Link Stealing, LS）：衡量候选节点对预测概率分布之间的余弦距离：

\[s(u,v) = 1 - \frac{p_u \cdot p_v}{\|p_u\|_2 \|p_v\|_2}\]

由于 GNN 会平滑连通节点的后验分布，有效遗忘必须使正例边的后验距离彻底退化至负例分布（ROC-AUC 趋近 0.5）。

3. 大规模跨架构与通用/专用算法大一统评测体系

针对以往研究各自为战的问题，Lethe 统一了 15 种前沿算法并将其拓展至图边遗忘场景。体系涵盖两类阵营：一类是图原生专用遗忘算法（如基于影响函数理论认证的 CEU、CGU、IDEA、ScaleGUN，即时推断掩码的 UnlinkToUnlearn，以及插入参数算子的 GNNDelete）；另一类是首次系统引入图领域的通用机器遗忘算法（如微调 Fine-tuning、梯度上升 NegGrad、AdvNegGrad、扰动修复 UNSIR、教师学生蒸馏 BadTeaching / SCRUB，以及基于 Fisher 信息的参数修剪 Fisher Forgetting 与 SSD、显著性掩码 SalUn）。评测图规模全部提升至节点数超 5K、边数超 100K 的主流基准（Amazon Computers、Amazon Photos、DBLP、Flickr、ogbn-arxiv），并在 GCN、GIN、GAT、GraphSAGE、SGC 5 种骨干模型上验证可泛化性。

实验关键数据

主实验

在 5 种大规模真实图结构数据集上，以 2 层 GCN 骨干模型、高中心性 5% 遗忘集为例，测试准确率（Acc）、边成员推理（UMIA）、影响推断（LT）与链路窃取（LS）的实验表现如下（摘录代表性算法，AUC 越接近 0.5 表明遗忘越彻底）：

数据集	算法	Acc (%) ↑	E-UMIA AUC (≈0.5)	LinkTeller (LT) AUC	Link Stealing (LS) AUC
Amazon Photos	原始模型 (Original)	90.8	0.526	0.480	0.639
	从头重训 (Gold Model)	90.3	0.524	0.490	0.635
	Fine-tuning	88.8	0.507	0.493	0.714
	NegGrad	80.6	0.515	0.475	0.597
	SCRUB	85.4	0.497	0.484	0.605
	SalUn	89.7	0.525	0.467	0.727
	IDEA	90.8	0.515	0.467	0.641
	GNNDelete	34.6	0.520	0.450	0.530
Amazon Computers	原始模型 (Original)	79.9	0.500	0.564	0.525
	从头重训 (Gold Model)	81.6	0.505	0.569	0.587
	Fine-tuning	79.1	0.491	0.557	0.554
	NegGrad	76.3	0.512	0.558	0.661
	SCRUB	47.9	0.511	0.532	0.839
	SalUn	83.8	0.514	0.541	0.543
	IDEA	79.9	0.508	0.551	0.525
	GNNDelete	37.9	0.516	0.497	0.826
ogbn-arxiv	原始模型 (Original)	53.1	0.505	0.636	0.833
	从头重训 (Gold Model)	53.3	0.508	0.628	0.833
	Fine-tuning	52.3	0.505	0.619	0.829
	AdvNegGrad	51.4	0.503	0.621	0.816
	Fisher Forgetting	52.8	0.501	0.627	0.832
	SSD	52.5	0.505	0.626	0.826
	IDEA	53.3	0.504	0.626	0.833
	GNNDelete	22.6	0.508	0.606	0.682

消融实验

基于 WalkCentrality 划分的低中心性与高中心性遗忘集下，边移除对节点表示端点位移 \(m(e)\) 的理论影响，以及实际图结构下 LinkTeller 攻击在真实社区、时间窗口划分下的难度对比（以 DBLP 和 Amazon Photos 为代表）：

实验切片 / 数据集	难度划分设置	端点位移 \(m(e)\) / LT AUC	说明与结论
端点位移 \(m(e)\) (Photos)	低 WalkCentrality 边集	0.309	稀疏局部边移除对隐层表示扰动剧烈（位移为高中心性的 5.2 倍）
	高 WalkCentrality 边集	0.060	拓扑冗余路径有效吸收了边移除对表示的影响
端点位移 \(m(e)\) (Computers)	低 WalkCentrality 边集	0.274	位移倍率达到高中心性的 6.7 倍
	高 WalkCentrality 边集	0.042	节点两端表示几乎无位移
DBLP (LinkTeller 真实性消融)	低中心性 (Low Centrality)	0.7486 (Gold) / 0.7788 (NegGrad)	极易被 LinkTeller 恢复，攻击暴露面极高
	高中心性 (High Centrality)	0.4589 (Gold) / 0.4487 (NegGrad)	攻击难度接近完全随机（基准下界）
	社区划分 (Community)	0.6773 (Gold) / 0.6701 (NegGrad)	真实社区兼具两类边，LT 得分精准落在低高中心性区间内
ogbn-arxiv (时序遗忘消融)	低中心性 (Low Centrality)	0.7707 (Gold) / 0.7677 (FT)	难度上限锚点
	高中心性 (High Centrality)	0.6284 (Gold) / 0.6191 (FT)	难度下限锚点
	时间窗口 (Temporal Window)	0.7185 (Gold) / 0.7183 (FT)	按引用时间遗忘历史边，难度严格介于两极端之间

关键发现

• 传统准确率与 UMIA 指标的虚无性：在所有测试数据集上，几乎全部非崩溃算法的测试准确率变化均在原始模型的 \(\pm 2\%\) 之间；E-UMIA 在全部算法上 AUC 均紧贴 0.48–0.53，完全失去区分度。相反，Link Stealing 在各方法间展现出超 20 个百分点的动态方差，能精准刻画遗忘质量。
• 低中心性边的致命脆弱性：在 Wilcoxon 符号秩检验中，全部非崩溃算法在低中心性边的 LinkTeller AUC 均显著高于高中心性边（\(p < 10^{-23}\)，达到理论极大检验量 \(W=9591\)），表明当前学术界现有的任何遗忘算法在面对非冗余的关键拓扑边时，均无法抵御基于节点影响的有偏探测。
• 理论认证算法的实践壁垒：CEU、CGU、ScaleGUN 等严格 \((\epsilon, \delta)\) 认证算法严格受限于无激活函数的线性架构（SGC），其基础分类精度天生落后 GCN 1.2–4.2 个百分点。且当遗忘比例达 5% 时，其二阶海森逆估计或梯度近似开销远超重新全量训练，失去了机器遗忘的效率初衷。
• 结构算子 GNNDelete 的灾难性崩溃：GNNDelete 在多个数据集上出现严重的模型塌陷（如 Photos 准确率暴跌至 34.6%，arxiv 暴跌至 22.6%），表明现有可学习删除算子难以稳定适配大规模复杂图结构。

亮点与洞察

• WalkCentrality 的力学解释与极速计算：将 GCN 谱卷积的幂矩阵直接转化为游走计数，既严谨反映了邻域平滑与特征消解的机理，又把图拓扑评分复杂度降到了边数的线性级别。
• 破解“边遗忘不掉准确率”的认知假象：直接点出传统文献用分类精度验证遗忘的根本谬误，揭示了 GNN 本身具备容忍拓扑扰动的 DropEdge 特性，强调图隐私评估必须走向对抗链路恢复。
• 通用机器遗忘方法在图领域的横向潜力：系统证实了无需专门构筑复杂图理论，精细调优的轻量通用方法（如 SCRUB 蒸馏与 Fisher 剪枝）在推理对抗防御与运行耗时上往往超越了过度复杂的图原生方法。

局限与展望

• 作者指出的局限性：由于图任务的复杂多样性，目前基准核心实验集中在节点分类任务，虽在附录拓展了链路预测验证，但尚未覆盖图分类与异构图推理；同时链路推理攻击类型未来仍需不断丰富。
• 潜在不足与适用边界：WalkCentrality 计算强绑定在对称归一化拉普拉斯算子，对于依赖注意力权重的动态架构（如 GAT、Transformer-based Graph Models），边权会随模型参数更新而动态变化，静态拓扑游走无法完全等价动态注意力传播。
• 改进与拓展思路：后续可将基于影响力的对抗链路攻击内化为遗忘过程中的鉴别器正则项，探索在保持图效用的同时针对性抹除低中心性边梯度痕迹的端到端主动防御框架。

相关工作与启发

• vs OpenGU / Jain et al. (2026)：现有综合性图遗忘基准主要针对节点删除任务，在边遗忘上仅简单堆砌常规指标；Lethe 是首个专门针对边遗忘结构驱动特性的专用基准，引入了拓扑中心性分级与专属对抗推断。
• vs GNNDelete / CEU / IDEA：前期孤立的边遗忘方法均在 Cora、Citeseer 等小图上验证，掩盖了重训耗时更短与准确率钝化的缺陷；Lethe 的统一协议暴露了认证方法依赖线性网络以及 GNNDelete 模型崩溃等现实瓶颈。

评分

• 新颖性: ⭐⭐⭐⭐⭐ 首次从拓扑冗余度与链路对抗推断视角重构边遗忘评测，提出的 WalkCentrality 指标优雅深刻。
• 实验充分度: ⭐⭐⭐⭐⭐ 涵盖 15 种算法、8 个数据集、5 种架构以及 3 种对抗攻击，统计检验严谨扎实。
• 写作质量: ⭐⭐⭐⭐⭐ 逻辑层层递进，对领域评估盲区的批判一针见血，附录消融极度丰富。
• 价值: ⭐⭐⭐⭐⭐ 为图遗忘学习树立了亟需的严谨基准，有力推动该领域从虚假准确率走向真实对抗隐私防护。

相关论文

• [NeurIPS 2026] Improving Evaluation Realism with Inference-Time Compute and Deployment Scaffolds
• [NeurIPS 2026] Beyond Fixed Benchmarks and Worst-Case Attacks: Dynamic Boundary Evaluation for LLM Safety
• [ICLR 2026] Unlearning Evaluation through Subset Statistical Independence
• [ACL 2025] SpeechFake: A Large-Scale Multilingual Speech Deepfake Dataset Incorporating Cutting-Edge Generation Methods
• [ICML 2026] PipeSD: An Efficient Cloud-Edge Collaborative Pipeline Inference Framework with Speculative Decoding