🤖 machine learning

Differentially Private Relational Learning with Entity-level Privacy Guarantees

本文提出了一个原则性的差分隐私关系学习框架，通过引入自适应梯度裁剪和扩展的隐私放大分析，解决了高实体敏感性和耦合采样带来的挑战，从而在实现强效效用的同时，实现了形式化的实体级隐私保证。

原作者： Yinan Huang, Haoteng Yin, Eli Chien, Rongzhe Wei, Pan Li

发布于 2026-02-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Yinan Huang, Haoteng Yin, Eli Chien, Rongzhe Wei, Pan Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试教一台计算机理解人们是如何相互连接的——比如弄清楚谁和谁是朋友，或者哪些产品经常被一起购买。这被称为关系学习（Relational Learning）。计算机通过观察一张巨大的连接图谱（图/Graph）来学习，这张图谱中，点代表实体（人），线代表它们之间的关系。

问题在于？这些图谱通常包含敏感的秘密。也许这张图谱展示了谁去看过哪位医生，或者谁购买了哪种药物。如果你直接用这些数据来训练计算机，它可能会在无意中“记住”这些秘密，并在日后泄露它们。

为了阻止这种情况，科学家们使用了一个名为**差分隐私（Differential Privacy, DP）**的护盾。你可以把 DP 想象成一个“噪声机”，它在计算机的学习过程中加入静电噪声，使得无法判断某个人是否出现在训练数据中。

然而，本文的作者发现，这种标准的隐私护盾（称为 DP-SGD）在应用于这些连接图谱时会失效。以下是原因以及他们如何解决的方法，我们使用简单的类比来解释：

两个大问题

1. “一人多角”问题（高敏感度）
在普通数据中，一个人通常只是一个数据点。但在连接图谱中，一个人可以参与到数十个关系中。

类比： 想象一位老师正在给班级评分。在普通的班级里，如果一个学生离开，老师只会错过一份作业。但在这种“关系型班级”里，如果一个学生离开，他会带走所有的分组项目、同行评审以及学习伙伴。突然之间，老师的成绩单发生了剧烈变化，因为一个人的缺失影响了太多环节。
风险： 因为一个人会影响很多部分的数学计算，所以为了隐藏他而需要的“噪声”必须非常巨大，这会破坏计算机学习有用知识的能力。

2. “两步舞”问题（耦合采样）
为了教导计算机，我们不会一次性展示整张图谱。我们会展示一些小块数据（小批量/Mini-batches）。为了构建这样一个小块，我们首先挑选一些真实的连接（正样本），然后发明一些虚假的连接（负样本），以此来告诉计算机什么是不应该预期的。

类比： 想象你正在制作一个播放列表。首先，你挑选了 5 首你喜欢的真实歌曲。然后，为了让播放列表更有趣，你又挑选了 5 首随机的、你不喜欢的歌曲，用来与前 5 首进行对比。
风险： 第二步（挑选“不喜欢”的歌曲）完全取决于第一步。如果你改变了前 5 首歌，后 5 首歌也会随之改变。标准的隐私数学假设这两个步骤是独立的，就像挑选两个完全不同的播放列表一样。但由于它们是相互关联的，旧的隐私数学方法就不再适用了，我们也无法确定数据的安全性究竟如何。

解决方案：更聪明的隐私护盾

作者为这些连接图谱构建了一个新版本的隐私护盾。他们通过两个巧妙的技巧解决了上述两个问题：

1. “公平裁剪器”（自适应梯度裁剪）
他们没有使用“一刀切”的规则来限制一个人的影响力，而是制定了一个动态规则。

修复方案： 如果一个人在当前的小块数据中出现在许多关系中，系统会自动比平时更大幅度地“调低音量”，以限制其贡献。如果他出现的次数很少，音量则保持正常。
结果： 这保持了数学上的稳定性。它防止了一个“受欢迎的人”主导整个学习过程，这意味着我们不需要添加那么多“噪声”来保护他。这就像一位老师知道，如果一个学生参加了 10 个小组活动，在计算最终成绩时，该学生只算作一个学生，而不是十个。

2. “严格有序的舞蹈”（依赖基数的采样）
他们改变了挑选虚假（负面）连接的方式，使得这两步舞蹈之间的联系变得非常微弱。

修复方案： 他们不再根据所选的特定真实连接来挑选虚假连接，而是先挑选固定数量的随机人员，然后再将他们配对。
结果： 这使得两个步骤在数学上变得可预测。它让作者能够证明，即使这些步骤是相互关联的，隐私保护依然得到了严格保障。这就像是在说：“无论我们之前选了哪 5 首歌，我们都会为‘不喜欢’的列表挑选恰好 10 个随机的人。”

实验结果

团队在真实世界的数据上测试了这种新方法，具体是通过微调大型语言模型（例如驱动聊天机器人的模型）来理解科学论文网络和在线购物数据中的关系。

更好的隐私： 他们从数学上证明了，他们的方法提供了强大的保证，确保任何单个人的数据都无法被逆向工程还原。
更好的学习： 由于他们的方法不需要像旧方法那样添加那么多“噪声”，计算机的学习效果也更好。与之前的隐私保护方法相比，它能更准确地预测关系（例如“谁接下来会购买这个产品”）。

总结

本文探讨的是如何教计算机从复杂的社交/关系网络中学习，同时又不暴露网络中个人的秘密。作者意识到旧有的隐私工具对于这项工作来说过于粗糙，因此他们构建了一个定制工具，该工具能根据每个人的活跃程度以及数据的采样方式来动态调整隐私规则。其结果是一个既能保护秘密，又能让计算机高效学习的系统。

技术摘要：具有实体级隐私保证的差分隐私关系学习

1. 问题定义

本文解决了在提供正式的实体级（节点级）差分隐私 (DP) 保证的同时，在关系型和网络结构化数据上训练机器学习模型的挑战。在关系学习中，模型（如节点属性编码器）通过对比损失函数被训练来预测实体（节点）之间的关系（边）。

标准的差分隐私随机梯度下降 (DP-SGD) 是为非结构化的、独立的数据设计的，在直接应用于关系学习时面临两个关键失效：

高敏感度： 在图数据中，单个实体（节点）通常参与多个关系。因此，移除或修改单个节点可能会改变一个小批次（mini-batch）内的多个边元组，导致梯度在许多项中发生显著变化。这会导致敏感度过高或无界，从而需要极大量的噪声来掩盖实体的贡献。
耦合采样： 关系学习的小批次通常通过多阶段过程构建：首先采样正边（观测到的关系），然后基于正样本生成负边（缺失的关系）。这种相互依赖性违反了标准 DP-SGD 的独立单步采样假设，使得传统的隐私放大分析（依赖于对独立数据集的子采样）无法适用。

2. 方法论

作者提出了一个定制的 DP-SGD 框架，通过集成三个核心组件来克服这些挑战：

A. 自适应梯度裁剪 (FREQ-CLIP)
为了解决高敏感度问题，本文引入了一种自适应梯度裁剪方案。与对所有样本使用固定阈值 $C$ 的标准裁剪不同，该方法根据节点在小批次中出现的频率动态调整裁剪阈值。

机制： 对于每个边元组 $T_i$ ，裁剪阈值根据出现在该元组中的任何节点的最高频率进行缩放（包括正边和负边中的节点）。
效果： 这确保了小批次梯度相对于移除单个节点的局部敏感度被限制在一个常数以内，即使该节点出现在多个关系中也是如此。具体而言，它将敏感度限制在 $(1 + |B^-(u^*)|) \cdot C$ 以内，其中 $|B^-(u^*)|$ 是该节点仅出现在负边中的边元组计数。

B. 基于基数依赖的耦合采样
为了处理多阶段采样的隐私分析，作者形式化了一个耦合采样的子类，其中阶段之间的依赖性仅源于样本量约束（基数），而非样本的具体内容。

实现： 他们提出了一种特定的负采样策略（算法 2：无放回负采样）。在该方案中，负边通过将从节点集中独立采样的节点与已采样的正边的端点进行配对来构建。
益处： 这种设计确保了负采样步骤仅取决于采样正边的数量，而非其具体的身份。这种解耦使得复杂的两阶段过程可以被分析为一个可处理的基数依赖型采样机制。

C. 隐私放大分析
作者为这种特定设置下的基数依赖耦合采样推导了严谨的隐私放大界限。

结果： 他们证明了对于第一阶段是泊松采样且第二阶段是无放回采样（仅依赖于第一阶段的大小）的复合数据集，可以使用 Rényi 差分隐私 (RDP) 紧凑地界定隐私成本。
集成： 通过结合自适应裁剪（用于限制敏感度）与特定的采样策略（用于实现放大界限），作者为整个训练过程提供了可证明的 $(\alpha, \epsilon(\alpha))$ -RDP 保证。

3. 核心贡献

敏感度分析与自适应裁剪： 对关系学习中的梯度敏感度进行了严谨分析，由此产生了一种基于频率的自适应梯度裁剪算法，能够有效地控制敏感度，而无需假设最坏情况下的节点度。
耦合采样的形式化： 将隐私放大理论扩展到一种可处理的耦合采样子类，其中依赖性仅限于样本大小，从而提供了此类设置下的首次放大界限。
定制化 DP-SGD 变体： 一个完整的算法（算法 3），集成了度数限制（degree capping）、自适应裁剪和基数依赖采样，以实现实体级隐私保证。
实证验证： 展示了该方法在文本属性网络（如 MAG 引文网络和 Amazon 共同购买网络）上微调预训练文本编码器（如 BERT, Llama2）进行零样本关系预测的有效性。

4. 实验结果

作者在文本属性网络数据集（MAG 引文网络和 Amazon 共同购买网络）上评估了其方法，目标是微调用于关系预测的编码器。

隐私界限： 对推导出的 RDP 界限（公式 3）进行数值分析表明，与朴素高斯机制以及使用固定裁剪的标准 DP-SGD 相比，所提方法实现了显著更紧凑的隐私界限。
效用-隐私权衡： 在关系预测任务（以 PREC@1 和 MRR 衡量）中，所提方法始终优于：
- 非隐私微调（符合预期，但带有隐私保证）。
- 未经微调的基础模型。
- 在相同隐私预算（ $\epsilon = 4$ 和 $\epsilon = 10$ ）下使用固定梯度裁剪的标准 DP-SGD。
消融研究： 实验表明，在固定隐私约束下，增加每个正边的负样本数量和限制节点度通常可以提高模型的效用。

5. 重要性与主张

本文声称提供了第一个针对实体级差分隐私关系学习的原则性框架，并提供了正式保证。其重要性在于：

弥合差距： 它解决了阻碍直接应用标准 DP-SGD 的图数据的特定结构性挑战（高敏感度和耦合采样）。
理论严谨性： 它超越了对图进行启发式应用 DP 的做法，通过提供严谨的敏感度分析和一种新的针对依赖采样过程的隐私放大定理，提升了理论深度。
实际效用： 它证明了可以在不造成灾难性性能损失的情况下保持严格的实体级隐私，这使得该方法在医疗保健和金融等关系数据盛行的敏感领域具有可行性。

作者强调，他们的方法允许在保护个体实体隐私的同时，在关系数据上微调基础模型，而此前由于缺乏适用于耦合关系采样的合适隐私机制，这一能力一直受到阻碍。