💻 computer science

Metric Differential Privacy at the User-Level Via the Earth Mover's Distance

本文通过使用推土机距离（Earth Mover's Distance）开启了对用户级度量差分隐私的研究，提出了针对线性查询和项目级查询的新颖机制，实现了从无界到有界设置的归约，并证明了其相对于标准用户级差分隐私具有更高的效用。

原作者： Jacob Imola, Amrita Roy Chowdhury, Kamalika Chaudhuri

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

原作者： Jacob Imola, Amrita Roy Chowdhury, Kamalika Chaudhuri

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

想象一下，你正试图保护人们的隐私数据，比如他们的日常位置或短信内容。多年来，差分隐私（Differential Privacy, DP）一直是保护隐私的金标准。你可以把标准的 DP 想象成一种“一刀切”的安全毯。它将数据集中的每一次变化都视为同样危险。

如果一个用户将位置从“家”变为“公司”，标准的 DP 会加入大量的“噪声”（随机的混乱）来隐藏这一信息。但如果用户只是从“家”移动到了“邻居家”，它也会做同样的事情。实际上，第一种变化意义重大，而第二种变化微乎其微。标准 DP 无法区分这两者，因此往往会加入过多的噪声，导致数据在分析时变得不再那么有用。

这篇论文介绍了一种更聪明、更灵活的方法，称为度量差分隐私（Metric Differential Privacy, Metric DP），它是专门为**用户级（User-Level）**数据量身定制的（即一个人贡献多个数据点，例如一个月的 GPS 定位点）。

以下是他们新构想——**推土机距离（Earth Mover's Distance, dEM）**及其运作原理的拆解，并使用简单的类比进行说明。

核心思想：“搬运泥土”类比

作者使用了**推土机距离（dEM）**的概念。想象你的数据是散布在田野里的土堆。

标准 DP 会问：“你移动了任何土吗？”如果是，它就会恐慌并加入最大程度的噪声。
dEM-DP 则会问：“你移动了多少土，以及移动了多远？”

如果你移动了一小撮土一英寸，那是很小的变化。如果你把一整卡车的土搬到了田野的另一头，那是巨大的变化。dEM 衡量的是移动这些土的成本。

成本小 = 敏感度低。 隐私系统加入的噪声较少。
成本大 = 敏感度高。 隐私系统加入的噪声较多。

这使得系统可以实现“细粒度”化。它会严密保护重大的秘密，但允许微小的、无害的细节显现出来，从而使最终的数据在分析中更加有用。

三大主要贡献

论文提出了三个主要的技术“工具”来实现这一目标：

1. 新的回答问题方式（机制）

作者设计了两种新方法，在保持这种“搬运泥土”式隐私的同时回答问题。

线性查询（“平均值”问题）： 想象询问：“人们距离特定公园的平均距离是多少？”作者创建了一种方法来回答这个问题，该方法能够理解答案是发生了轻微变化（微小的搬土）还是剧烈变化（大幅度的搬土）。他们证明，如果问题本身是“平滑”的（不会剧烈跳变），他们可以加入比标准方法少得多的噪声。
逐项查询（“列表”问题）： 想象发布一份经过打乱的人们在聊天中使用的所有词汇列表。标准方法会将每一个词的变化都视为巨大的风险。作者使用了一个巧妙的技巧，叫做**“洗牌”（Shuffling）**。
- 类比： 想象 100 个人每人写了一张秘密便条。如果按顺序交给收集者，收集者会知道谁写了什么。但如果把所有便条扔进搅拌机，混合均匀后再把这一堆东西交出来，收集者能看到这组便条的集合，却无法分辨出哪张便条来自哪个人。
- 作者证明，这种“搅拌”（洗牌）过程让隐私保证比之前认为的要强大得多，从而可以使用更少的噪声并获得更好的数据质量。

2. 处理“杂乱”的数据量（归约）

在现实世界中，人们贡献的数据量并不总是相同的。一个人可能有 100 个位置点，而另一个人可能只有 10 个。标准方法在处理这种“无界”的混乱情况时会遇到困难。

解决方案： 作者创建了一个“黑盒”转换器。想象你有一台机器，它只有在每个人都带来正好 10 件物品时才能工作。作者构建了一个预处理器，可以将一个人的 100 件物品随机采样减少到 10 件，或者将一个人的 5 件物品采样增加到 10 件。
神奇之处： 他们证明了这种采样过程不会过度扭曲“搬土”距离。这意味着你可以将他们设计的这些简单工具（专为等规模群体设计）应用于杂乱的现实世界数据，而不会破坏隐私规则。

3. 证明其优越性（效用提升）

最后，他们通过数据对比显示，他们的新方法确实比旧的“一刀切”方法表现更好。

结果： 对于某些类型的查询（如寻找平均值或统计单词出现的频率），他们的方法产生的数据误差更小。
原因： 因为标准 DP 害怕任何变化，它会加入如此多的噪声，以至于答案变得模糊不清。dEM-DP 则意识到有些变化是微不足道的，因此会加入较少的噪声，从而保持答案的清晰和有用。

论文中的现实世界案例

作者使用三个场景来解释为什么这很重要：

位置数据：
- 场景： 用户从“家”移动到“公司”（大变化）对比从“家”移动到“邻居家”（极小变化）。
- 标准 DP： 将两者视为同样危险。加入巨大噪声。
- dEM-DP： 意识到“邻居家”的移动风险较低。加入微小噪声。数据依然足够准确，可以观察整体交通模式，而不会泄露具体某人在哪里。
文本数据：
- 场景： 用户将对话内容从“数学”变为“古典音乐”（巨大的语义转变）对比从“代数”变为“三角函数”（微小的语义偏移）。
- dEM-DP： 理解“代数到三角函数”是一个微小的偏移。它对用户的保护不会过于激进，从而保留了对话中的细微差别，便于分析。
社交图谱（好友关系）：
- 场景： 用户增加了一个新朋友对比更换了整个朋友圈。
- dEM-DP： 识别出增加一个朋友是一个微小的“搬土”动作。它允许系统发布关于网络结构的数据，而不会模糊整个图谱的轮廓。

总结

这篇论文认为，我们不需要将每一次数据的变化都视为核威胁。通过测量数据变化了多少以及变化了多远（使用推土机距离），我们可以创建出既更聪明（理解大秘密与小细节的区别）、更有用（添加更少噪声，保持数据准确）、又更灵活（适用于不同数据量的用户）的隐私系统。

这就像是从一个“只要有叶子吹过就锁门”的安保系统，升级到了一个“只有当有人尝试翻墙入室时才锁门”的系统。房子依然安全，但你不必再被风吹叶落的噪音所困扰。

技术摘要：基于推土机距离（Earth Mover's Distance）的用户级度量差分隐私

问题陈述

差分隐私（Differential Privacy, DP）已成为数据分析的标准，传统上它提供统一的隐私保证，即每一对输入数据集都被视为具有同等的敏感性。然而，在许多实际应用中，数据表现出异质性；例如，泄露用户的确切居住城市比泄露其所属国家更为敏感。**度量差分隐私（Metric Differential Privacy, Metric DP）**通过让隐私保证随输入对之间的距离线性退化来解决这一问题，从而在输入相似时获得更好的效用。

虽然之前的度量 DP 研究集中在项目级（item-level）设置（即每个用户贡献单个数据项），但现实世界的场景通常涉及用户级（user-level）贡献，即单个用户提供一组数据项（例如，位置历史或一组单词）。现有的用户级 DP 框架依赖于标准 DP，将用户整个数据集的所有变化都视为具有相同的敏感性，而不考虑变化的幅度或性质。本文开启了对用户级度量 DP 的研究，特别是在使用**推土机距离（Earth Mover's Distance, dEM）**作为底层度量的情况下。目标是定义一种隐私概念，其敏感性不仅取决于数据变化的比例，还取决于这些变化的距离，从而捕捉比标准用户级 DP 更细致的隐私语义。

方法论

1. 定义 dEM-DP

作者通过使用推土机距离（也称为 1-Wasserstein 距离）来衡量两个用户数据集 $K$ 和 $K'$ 之间的距离，从而定义了 dEM-DP。

度量： $d_{EM}(\tilde{K}, \tilde{K}')$ 代表将数据集 $K$ 的概率分布传输到 $K'$ 的最小成本，其中成本是移动的数据量乘以项目之间的距离 $d_X$ 。
隐私保证： 一个机制 $M$ 满足 $(\alpha, \delta)$ -有界 dEM-DP，如果对于任何大小相同的两个数据集 $K, K'$ ：
$\Pr[M(K) \in O] \le e^{\alpha \cdot d_{EM}(\tilde{K}, \tilde{K}')} \Pr[M(K') \in O] + \delta$
这里，隐私参数随距离缩放。如果 $d_{EM}$ 很小（数据集相似），则隐私保证更强（相比于标准 DP 而言，其有效 $\epsilon$ 更低），而标准 DP 会应用一个统一的 $\epsilon$ 。

2. 机制设计

论文提出了两种新的机制，用于在本地模型（用户在发送前进行私有化处理）和中心模型（信任的聚合器持有数据）下发布查询。

A. 线性查询 (PrivEMDLinear)

对于形式为 $F\tilde{K}$ 的线性查询，作者分析了其在 dEM 下的敏感性。

敏感性分析： 与要求查询函数必须有界的标准 DP 不同，dEM-DP 分析要求函数 $f$ （代表查询）是 Lipschitz 连续的。
结果： 作者证明了线性查询在 dEM 下的敏感性由查询函数的 Lipschitz 常数上界约束。这允许添加经过校准的噪声（例如，使用 K-norm 机制或高斯机制），该噪声与 Lipschitz 常数成正比而非最坏情况下的全局界限，从而提高了效用。

B. 无序项目式查询 (PrivEMDItemWise)

对于发布用户数据集中每个项目的噪声输出（例如直方图），该机制对每个项目应用基础的项目级度量 DP 机制 $A$ ，然后**打乱（shuffle）**结果。

通过打乱实现的隐私放大： 作者将“通过打乱实现隐私放大”的结果推广到了度量 DP 设置中。由于输出是一个无序列表，攻击者无法将特定输出与特定的输入索引联系起来。
技术创新： 他们证明了打乱 $m$ 个项目可以将隐私成本从通过组合得到的 $O(m\alpha)$ 降低到 $O(\alpha\sqrt{m})$ 。这一结果是通过分析输入向量之间的耦合并利用打乱模型的特性推导出来的。

3. 向无界数据的扩展

现实世界的数据集通常具有变化的规模（无界设置），这使得 dEM 分析变得复杂，因为数据集的大小本身也会成为隐私问题。

归约： 作者提出了一个从无界到有界 dEM-DP 的黑盒归约。
机制： 他们使用有放回抽样将任何用户数据集投影到固定大小 $s$ 上。他们证明了这种投影是“平滑的”，这意味着投影后数据集之间的 dEM 距离与原始数据集之间的 dEM 距离接近（仅存在一个小的加性因子）。
离散 dEM-DP： 为了处理抽样带来的加性误差，他们引入了一个“离散”的 dEM-DP 定义，其中距离 $\le r$ 的变化受到统一保护。他们表明，对于足够大的样本量，无界 dEM-DP 可以归约为有界 dEM-DP，且隐私语义损失极小。

核心贡献

定义用户级度量 DP： 本文建立了一个使用推土机距离来定义用户级度量 DP 的正式定义，捕捉了数据变化的规模和空间特征。
新型机制：
- PrivEMDLinear： 一种用于线性查询的机制，利用 Lipschitz 连续性来限制敏感性，对于特定类型的查询，其效用优于标准用户级 DP。
- PrivEMDItemWise： 一种通用的项目式查询机制，利用打乱技术。作者提供了广义的隐私放大分析，显示出相对于标准组合界限具有 $\sqrt{m}$ 的改进。
无界归约： 一种黑盒归约技术，通过抽样将有界 dEM-DP 机制转换为无界机制，从而能够处理用户贡献规模可变的数据集。
效用提升： 理论分析表明，对于以下情况，dEM-DP 机制可以实现比标准用户级 DP 基准更高的效用（更低的误差）：
- 线性嵌入查询： 在中心模型和本地模型中，特别是当隐私参数 $\alpha$ 允许大于不相似输入对应的标准 $\epsilon$ 时。
- 频率估计： 在本地模型中，当领域规模和隐私参数满足特定条件时，利用数据具有结构（如聚类度量）的特性，频率估计的误差得到改善。

结果与意义

论文声称 dEM-DP 提供了一种更精细的隐私定义，这更符合现实世界的隐私语义。

隐私语义： 在标准 DP 中，改变用户一个月的数据与改变一天的数据被视为具有同等的敏感性。在 dEM-DP 中，一天的变化被认为敏感性较低（ $d_{EM}$ 较小），因此可以减少噪声并提高效用；而一个月的变化则会受到更强的保证。
效用增益： 理论界限显示，对于线性嵌入查询和频率估计，当数据具有结构（例如聚类度量）时，dEM-DP 机制在领域规模 $k$ 和隐私参数方面的误差表现优于标准用户级 DP。
泛化性： 对有界设置的归约以及通用的打乱分析表明，这些技术可以广泛应用于各种度量空间和查询类型，而不仅仅局限于文中提供的特定示例（如位置、文本、图）。

作者将这项工作定位为第一个提出通过 dEM 实现通用用户级度量 DP 的研究，超越了特定的文本应用，转向一个适用于通用度量空间的框架。他们强调，虽然 dEM-DP 是对标准 DP 的一种放宽，但它为数据相似性与敏感性相关的应用提供了一个更实用的权衡。