VERITAS：抗投毒的本地差分隐私图学习协议

在同时保护节点特征与图结构的本地差分隐私（local differential privacy, LDP）图学习中，如何抵御伪造节点投毒并保持下游效用。

• 场景：每个用户在本地扰动节点特征与邻接信息后再交给不可信服务器做图学习，原始数据不出设备。作者认为开放参与使攻击者可用sybil账户与合法用户建边，提交精心构造的扰动报告，经消息传递污染表示并降低节点分类等下游任务。
• 现有不足：作者给出三点。服务器看不到原始特征与邻接，常规异常检测与鲁棒聚合不适用；LDP噪声使恶意注入与良性扰动难以区分；已有图投毒防御面向中心化学习并假设能看到未扰动图，在本地隐私下不成立。作者称该设定下有效防御仍 largely unexplored。
• 核心观察：恶意节点为扩大影响会给目标邻居打高信任，良性节点按本地观察给结构异常邻居低信任。这种双边背书不对称在LDP噪声下仍可被服务器识别。
• 提出方法：作者提出 VERITAS，采用 trust-but-verify：先信任全部报告，再用编码分级同伴信任的 verification list，在用户侧联合私有化特征与结构，在服务器侧利用双边背书不对称识别并剪除恶意节点。四阶段为本地扰动、背书驱动剪枝、双重去噪恢复效用、鲁棒私有图学习。
• 威胁模型：
  • 目标：攻击者在隐蔽预算 Δ 内最大化影响度量 ℧(Fθ(G†))；节点分类中 ℧ 通常对应提高误分类率。另有半诚实服务器在遵守协议时试图从扰动报告或训练后的 GNN 做属性、链接或成员推理。
  • 知识：作者采用 realistic black-box。攻击者只知道公开协议 P、扰动机制 Mx、Ma 及隐私预算 ϵx、ϵa；看不到真实特征、标签、真实邻域，也看不到服务器 GNN 的架构、参数与训练动态。
  • 能力：最多注入 nmax 个伪造节点（1 < |Vatk| ≪ |V|），由策略 Sx、Starget、Satk 任意构造特征与邻接，并连到目标受害者集合 Vt。
  • 受害系统：用户侧对 (xv, av) 做 LDP 后上传，不可信服务器只在噪声图上训练 GNN 的本地私有图学习协议。

• 本地差分隐私：LDP [24] 让用户在传输前扰动敏感数据，从而不依赖可信数据管理者。分类数据用 randomized response [40]、[41]；数值数据用 Laplace [36]、Gaussian [37]、piecewise [39]、multi-bit [13]、square wave [38]。后续工作覆盖私有频率估计、分布学习与机器学习。工业部署包括 Google [26]、Apple [27]、Microsoft [28]。近期 LDP 从表格数据扩展到图数据 [14]、[21]、[35]。
• 图神经网络：GNN [2]、[3] 通过邻域聚合同时利用拓扑与节点属性，用于节点分类 [2]、链接预测 [4]、图聚类 [5]。节点特征与边可能含敏感信息。作者称已有工作显示对手可利用训练后的 GNN 做属性推理 [9]、成员推理 [12] 与链接推理 [10]，从而推动隐私保护图学习。
• 本地私有图学习：该方向把 LDP 用到图上，使协作学习时不向服务器暴露原始特征或拓扑 [13]–[23]。作者称这些方法利用 GNN 消息传递对噪声的容忍 [2]、[13]，在隐私约束下仍能学到有用表示。近期研究 [16] 指出恶意参与者可同时利用特征与结构扰动通道注入对抗信号，并经邻域聚合传播放大。作者对比中心化图学习：异常检测可利用全局图统计与特征相关 [30]、[32]、[33]，而 LDP 故意混淆结构与属性，使许多既有防御失效。
• 基线与数据：实验把无防御的投毒模型作为 Baseline。特征 LDP 包括 1-bit（1B）[28]、Laplace（LP）[36]、Analytic Gaussian（AG）[37]、piecewise（PM）[39]、multi-bit（MB）[13]、square wave（SW）[38]；结构用 KRR。GNN 为 GCN [2]、GraphSAGE [1]、GAT [44]。数据集为 Cora、Citeseer [42] 与 LastFM、Twitch [43]。效用恢复采用 [15] 的 NFR 与 HOA。

作者把本文定位为面向 LDP 设定的投毒防御：既有本地私有图学习关注效用与隐私，[16] 展示了投毒威胁，而中心化防御的数据假设在本地隐私下不成立。

VERITAS 先信任用户报告，再在服务器上用双边背书不对称核验并剪枝，然后去噪并训练 GNN。用户侧满足 ϵ-LDP，ϵ = ϵx + ϵa。

问题设定与隐私

• 数据：图 G = (V, X, A)。用户 v 本地持有 (xv, av)，特征与结构都视为敏感。服务器不可信，不直接看到 X 与 A。
• ϵ-LDP：对任意两输入与任意输出，输出概率比不超过 e^ϵ。边保护用 ϵ-link LDP：邻接向量只差一条边时，输出落入任意可测集的概率比不超过 e^ϵ。
• 组合：后处理不增加隐私预算；对同一数据依次施加机制，预算相加。特征与验证列表作用于不相交属性，故总预算为 ϵx + ϵa。服务器后续操作只作用于已收集报告。

阶段①：本地数据扰动

• 特征：预算 ϵx。从 d 维中均匀抽 m 维，m = max(1, min(d, ⌊δ·ϵ⌋))；抽中维用 (ϵx/m)-LDP（如 PM、MB、SW），其余置零，可选 RECT 做无偏校正，使 E[x̃v] ≈ xv。
• 验证列表：不用常规二值随机响应。每个节点维护 ăv ∈ {0, 1, …, κ}^|V|：非邻居为 0，确认邻居取 1 到 κ 的信任等级。0 只表示结构缺失。每项用 K-ary randomized response（KRR）扰动：报真值概率为 e^{ϵa}/(e^{ϵa}+κ)，报其他值各为 1/(e^{ϵa}+κ)。作者称该机制满足 ϵa-link LDP（Proposition 1）。上传 (x̃v, r̃v)。

阶段②：背书驱动剪枝

• 三条边信号：结构存在 sexist_uv 要求双方都不报 0；信任一致性 scons_uv 取双方信任的较小值，作者称这是为抵消恶意节点一律报最高信任 κ；背书不对称 sasym_uv 为两边信任差的绝对值。
• 边置信度：c_uv = sexist_uv · (scons_uv / κ) · exp(−λ · sasym_uv)，λ > 0。存在项作硬门，一致性给分级互信，不对称项惩罚单方背书。
• 可疑分与剪枝：ϕv 为邻居方向偏差的平均，N̂v 为任一方声称有关系的节点集合。正的 ϕv 表示 v 给别人的信任高于别人给 v 的信任。Proposition 2：伪造节点对所有邻居报 κ、诚实邻居因异常观察报 1 时，E[ϕ_vm] = (2pa − 1)(κ − 1) > 0，pa = e^{ϵa}/(e^{ϵa}+κ)；对称评估的诚实节点期望为 0。ϕv > γ 的节点被删，只保留双边支持为正的边。

阶段③④与复杂度

• 双重去噪：沿用 [15]。NFR 用 L1 正则降低有效特征维以减小每维估计误差；HOA 用个性化多跳聚合扩大有效邻域、降低噪声方差，得到 X̂、Â。
• 学习：在去噪图上用标注节点 Vl ∩ V̂ 训练 GNN Fθ，再对 Vu = V̂ \ Vl 推理。默认两层、隐藏维 64，GCN 为默认骨干。
• 复杂度：剪枝为 O(|V|+|E|)；HOA 为 O(K|E|d)，NFR 为 O(|V|d)。作者称两阶段相对图规模接近线性。

成功判定是下游节点分类的测试准确率，不是单独的检测率。攻击按 Algorithm 1：在预算内造最多 nmax 个假节点，用 Sx、Starget、Satk 构造特征、指向目标的边以及假节点之间的协调。

实验设置

• 数据：Table I。Cora：2,708 节点、5,278 边、1,433 特征、7 类；Citeseer：3,327、4,552、3,703、6；LastFM：7,624、27,806、7,842、18；Twitch：4,648、61,706、128、2。划分 50% 训练、25% 验证、25% 测试。
• 模型与机制：GCN、GraphSAGE、GAT，两层、隐藏维 64，GCN 默认。特征 LDP 为 1B、LP、AG、PM、MB、SW，PM 默认；结构用 KRR。效用恢复按 [15]。
• 参数：ϵx ∈ {0.01, 0.1, 1.0, 2.0, 3.0}，ϵa ∈ {1.0, 3.0, 5.0, 7.0, 9.0}，默认 ϵx = 0.1、ϵa = 5.0。κ = 5。注入率 r⋆ ∈ {0.001, 0.005, 0.01, 0.02, 0.04}，默认 0.01。γ、λ 在验证集上调节，论文未给出具体值。采样规模 m 的公式含 δ，论文未报告 δ。
• 指标与重复：节点分类测试准确率（%）。10 次独立运行的均值，带 95% 置信区间。基线是无防御的投毒模型。
• 硬件：Ubuntu 20.04、两颗 Intel Xeon Gold 6348、100GB 内存、NVIDIA A800 80GB。论文未报告查询次数或训练轮数。

主结果

Figure 3 比较六种特征 LDP 下 Ours 与 Baseline 的准确率，但图中柱高未以数字标出，正文也未逐机制列出准确率，故不填具体百分数。作者称在全部四个数据集与全部机制上 VERITAS 都提高了准确率。

Table II 给出 GraphSAGE 与 GAT 的准确率（%）。GCN 的分数据集数字未在表中给出。

表格较宽，可左右滑动

GNN	方法	Cora	Citeseer	LastFM	Twitch
GraphSAGE	Baseline	69.2	67.6	72.4	72.7
GraphSAGE	Ours	75.7	72.9	76.3	76.9
GAT	Baseline	67.4	65.1	69.6	70.1
GAT	Ours	71.8	70.3	75.2	75.4

• 作者称剪枝在数据与参与者过滤层进行，不改模型结构，因此对 GNN 设计 largely independent，并在隐私机制与 GNN 上具有泛化性。
• 表中每个 GNN×数据集上 Ours 都高于对应 Baseline。Table II 未含 GCN 行。
• 论文未报告检测精确率、召回率或误剪诚实节点的比例。

消融

• 设置：Figure 4(a) 比较 Baseline（投毒且无防御）、w/o II（去掉背书剪枝）、w/o III（去掉双重去噪）与完整 VERITAS。纵轴为 Accuracy (%)，图中未标注具体读数。
• 结果：作者称去掉任一阶段都相对完整模型下降；去掉 Stage II 下降最大，去掉 Stage III 也会降低准确率；完整模型最好。
• 作者解读：剪枝是主要防御，效用恢复也有作用，两阶段互补且都不可或缺。

参数分析

• 预算：Figure 4(b)(c) 中，作者称 ϵx 或 ϵa 增大时节点分类准确率持续提高，因为更大预算带来更少扰动，留下更多用于检测的特征与结构信号。横轴分别为 ϵx（0.01 到 3.0）与 ϵa（1.0 到 9.0），图中未标出各点准确率。
• 注入率：Figure 4(d) 横轴为 r⋆（0.001 到 0.04）。作者称恶意节点比例较低时性能稳定；随 r⋆ 增大准确率逐渐下降，但下降保持 moderate，因而认为能承受更强投毒。各点准确率未在正文给出。

其他消融与分析

• 论文未再报告其他消融数字。Proposition 2 给出恶意与诚实节点可疑分期望差为 (2pa−1)(κ−1)，实验部分未用该差做检测率验证。
• 理论隐私：用户侧 (ϵx+ϵa)-LDP，服务器侧后处理不追加预算（Sect. IV-E）。实验未测量属性、链接或成员推理的成功率。
• 复杂度分析为 O(|V|+|E|)、O(K|E|d)、O(|V|d)，实验未报告墙钟时间。

作者未在结果中给出 Ours 低于 Baseline 的设置。Figure 3、Figure 4 的具体柱高或曲线端点无法从文字读出。

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

论文的 Conclusion 在所给文本中于 “V ERITAS effectively” 处截断，未见 Limitations、Discussion 或 Future Work 专节写出局限或后续工作。正文仅写代码 will be made publicly available upon acceptance，即作者计划在接收后公开代码。除此之外，论文未专门讨论局限。

实验覆盖范围

• 数据集为 Cora、Citeseer、LastFM、Twitch 共四个，统计见 Table I；任务为节点分类测试准确率（Sect. V）。
• 被测 GNN 为 GCN、GraphSAGE、GAT；Table II 报告后两者，GCN 为默认骨干，其分数据集数字未列入 Table II。
• 特征机制为 1B、LP、AG、PM、MB、SW，结构为 KRR；默认 ϵx = 0.1、ϵa = 5.0、κ = 5、r⋆ = 0.01（Sect. V-A）。
• 每个结果为 10 次独立运行的均值及 95% 置信区间；γ 与 λ 在验证集调节，论文未报告二者取值，也未报告 δ。
• 消融为去掉 Stage II 或 Stage III（Figure 4(a)）；参数扫描覆盖 ϵx、ϵa 与 r⋆（Figure 4(b)–(d)）。论文未报告剪枝的精确率或召回率，也未报告隐私推理攻击的实测成功率。

VERITAS 是面向本地差分隐私图学习的投毒防御协议，按 trust-but-verify 在保持 ϵ-LDP 的同时剪除伪造节点。

• 问题：用户本地扰动特征与邻接后交给不可信服务器。black-box 攻击者只知协议与隐私预算，可注入至多 nmax 个伪造节点并连到目标节点，以提高 GNN 误分类率。半诚实服务器还可能做属性、链接或成员推理。作者认为服务器看不到原始图，且 LDP 噪声使恶意与良性报告难分，中心化投毒防御的假设不成立。
• 方法：用户用抽样后的数值 LDP 扰动特征，并用信任等级 0 到 κ 的验证列表经 KRR 保护结构。服务器从双边报告提取存在、一致性与不对称，合成边置信度，再按方向偏差的可疑分 ϕv > γ 剪枝。随后用 NFR 与 HOA 去噪，在干净图上训练 GNN。总隐私预算为 ϵx + ϵa，服务器后处理不追加预算。
• 结果：四个数据集、六种特征 LDP 上，作者称相对无防御投毒基线准确率均提高。Table II 中 GraphSAGE 的 Cora 准确率从 69.2% 到 75.7%，Twitch 从 72.7% 到 76.9%；GAT 的 Cora 从 67.4% 到 71.8%，Twitch 从 70.1% 到 75.4%。消融中去掉剪枝下降最大。ϵx 或 ϵa 增大时作者称准确率提高；注入率升高时准确率下降但作者称降幅 moderate。
• 结论：作者认为双边背书不对称可在噪声报告上识别恶意参与者，剪枝与去噪互补，且防御不依赖特定 GNN 架构。作者计划在论文接收后公开代码。