💻 computer science

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

This paper initiates the study of user-level metric differential privacy using the Earth Mover's Distance, proposing novel mechanisms for linear and item-wise queries, a reduction from unbounded to bounded settings, and demonstrating improved utility over standard user-level DP.

Original authors: Jacob Imola, Amrita Roy Chowdhury, Kamalika Chaudhuri

Published 2026-07-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jacob Imola, Amrita Roy Chowdhury, Kamalika Chaudhuri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to protect people's private data, like their daily locations or their text messages. For years, the gold standard for privacy has been Differential Privacy (DP). Think of standard DP like a "one-size-fits-all" security blanket. It treats every single change to a dataset as equally dangerous.

If a user changes their location from "Home" to "Work," standard DP adds a huge amount of "noise" (random confusion) to the data to hide it. But it does the exact same thing if a user changes their location from "Home" to "Home's Next Door Neighbor." In reality, the first change is a big deal, but the second is tiny. Standard DP doesn't distinguish between them, so it often adds too much noise, making the data less useful for analysis.

This paper introduces a smarter, more flexible approach called Metric Differential Privacy (Metric DP), specifically tailored for User-Level data (where one person contributes many data points, like a month's worth of GPS pings).

Here is the breakdown of their new idea, Earth Mover's Distance (dEM), and how it works, using simple analogies.

The Core Idea: The "Moving Dirt" Analogy

The authors use a concept called Earth Mover's Distance (dEM). Imagine your data is a pile of dirt spread out on a field.

Standard DP asks: "Did you move any dirt?" If yes, it panics and adds maximum noise.
dEM-DP asks: "How much dirt did you move, and how far did you move it?"

If you move a tiny speck of dirt one inch, that's a small change. If you move a whole truckload of dirt across the field, that's a huge change. dEM measures the cost of moving the dirt.

Small cost = Less sensitive. The privacy system adds less noise.
Big cost = More sensitive. The privacy system adds more noise.

This allows the system to be "fine-grained." It protects the big secrets fiercely but lets the small, harmless details shine through, making the final data much more useful.

The Three Main Contributions

The paper presents three main technical "tools" to make this work:

1. New Ways to Answer Questions (Mechanisms)

The authors designed two new methods to answer questions about data while keeping this "dirt-moving" privacy.

Linear Queries (The "Average" Question): Imagine asking, "What is the average distance people live from a specific park?" The authors created a way to answer this that understands if the answer changes slightly (a small dirt move) versus drastically. They proved that if the question itself is "smooth" (doesn't jump around wildly), they can add much less noise than standard methods.
Item-Wise Queries (The "List" Question): Imagine releasing a list of all the words people used in a chat, but scrambled. Standard methods would treat every word change as a massive risk. The authors used a clever trick called "Shuffling."
- Analogy: Imagine 100 people each write a secret note. If you hand them to a collector in order, the collector knows who wrote what. But if you throw all the notes into a blender, mix them up, and hand out the pile, the collector sees the collection of notes but can't tell which note came from which person.
- The authors proved that this "blending" (shuffling) makes the privacy guarantee much stronger than previously thought, allowing for less noise and better data quality.

2. Handling "Messy" Data Sizes (The Reduction)

In the real world, people don't always contribute the same amount of data. One person might have 100 location points; another might have 10. Standard methods struggle with this "unbounded" mess.

The Solution: The authors created a "black-box" translator. Imagine you have a machine that only works if everyone brings exactly 10 items. The authors built a pre-processor that takes a person's 100 items and randomly samples them down to 10, or a person's 5 items and samples them up to 10.
The Magic: They proved that this sampling process doesn't distort the "dirt-moving" distance too much. This means you can use their simple tools (designed for equal-sized groups) on messy, real-world data without breaking the privacy rules.

3. Proving It's Better (The Utility Boost)

Finally, they ran the numbers to show that their new method actually works better than the old "one-size-fits-all" method.

The Result: For certain types of questions (like finding averages or counting how often words appear), their method produces data with less error.
Why? Because standard DP is scared of any change, it adds so much noise that the answer becomes fuzzy. dEM-DP realizes that some changes are trivial, so it adds less noise, keeping the answer sharp and useful.

Real-World Examples from the Paper

The authors use three scenarios to explain why this matters:

Location Data:
- Scenario: A user moves from "Home" to "Work" (a big change) vs. "Home" to "Home's Next Door" (a tiny change).
- Standard DP: Treats both as equally dangerous. Adds huge noise.
- dEM-DP: Realizes the "Next Door" move is low risk. Adds tiny noise. The data remains accurate enough to see general traffic patterns without revealing exactly who is where.
Text Data:
- Scenario: A user changes a conversation from "Math" to "Classical Music" (a huge semantic shift) vs. "Algebra" to "Trigonometry" (a tiny shift).
- dEM-DP: Understands that "Algebra to Trigonometry" is a small shift in meaning. It protects the user less aggressively, preserving the nuance of the conversation for analysis.
Social Graphs (Friends):
- Scenario: A user adds one new friend vs. changing their entire friend group.
- dEM-DP: Recognizes that changing one friend is a small "dirt move." It allows the system to release data about the network structure without blurring the whole picture.

The Bottom Line

This paper argues that we don't need to treat every change in data as a nuclear threat. By measuring how much and how far data changes (using the Earth Mover's Distance), we can create privacy systems that are:

Smarter: They understand the difference between a big secret and a small detail.
More Useful: They add less "noise," so the data is more accurate.
Flexible: They work even when people contribute different amounts of data.

It's like upgrading from a security system that locks the door whenever a leaf blows against it, to a system that only locks the door when a burglar tries to climb in. The house stays secure, but you don't have to deal with the constant noise of the wind.

Technical Summary: Metric Differential Privacy at the User-Level via the Earth Mover's Distance

Problem Statement

Differential Privacy (DP) has become the standard for data analysis, traditionally offering uniform privacy guarantees where every pair of input datasets is treated as equally sensitive. However, in many practical applications, data exhibits heterogeneity; for instance, revealing a user's exact city of residence is more sensitive than revealing their country. Metric Differential Privacy (Metric DP) addresses this by degrading the privacy guarantee linearly with the distance between input pairs, allowing for better utility when inputs are similar.

While prior work in Metric DP has focused on the item-level setting (where each user contributes a single data item), real-world scenarios often involve user-level contributions, where a single user provides a collection of items (e.g., a history of locations or a set of words). Existing user-level DP frameworks rely on standard DP, treating all changes to a user's entire dataset as equally sensitive regardless of the magnitude or nature of the change. This paper initiates the study of Metric DP at the user-level, specifically utilizing the Earth Mover's Distance (dEM) as the underlying metric. The goal is to define a privacy notion where the sensitivity of a user's contribution depends on both the fraction of data changed and the distance of those changes, capturing a more nuanced privacy semantics than standard user-level DP.

Methodology

1. Defining dEM-DP

The authors define dEM-DP by measuring the distance between two user datasets $K$ and $K'$ using the Earth Mover's Distance (also known as the 1-Wasserstein distance).

Metric: $d_{EM}(\tilde{K}, \tilde{K}')$ represents the minimum cost of transporting the probability distribution of dataset $K$ to $K'$ , where the cost is the quantity of data moved multiplied by the distance $d_X$ between items.
Privacy Guarantee: A mechanism $M$ satisfies $(\alpha, \delta)$ -bounded dEM-DP if for any two datasets $K, K'$ of the same size:
$\Pr[M(K) \in O] \le e^{\alpha \cdot d_{EM}(\tilde{K}, \tilde{K}')} \Pr[M(K') \in O] + \delta$
Here, the privacy parameter scales with the distance. If $d_{EM}$ is small (similar datasets), the privacy guarantee is stronger (lower effective $\epsilon$ ) compared to standard DP, which would apply a uniform $\epsilon$ .

2. Mechanism Design

The paper proposes two novel mechanisms for releasing queries under dEM-DP in both the Local Model (users privatize data before sending) and the Central Model (trusted aggregator holds data).

A. Linear Queries (PrivEMDLinear)

For linear queries of the form $F\tilde{K}$ , the authors analyze the sensitivity under dEM.

Sensitivity Analysis: Unlike standard DP which requires the query function to be bounded, dEM-DP analysis requires the function $f$ (representing the query) to be Lipschitz continuous.
Result: The authors prove that the sensitivity of a linear query under dEM is upper-bounded by the Lipschitz constant of the query function. This allows for the addition of calibrated noise (e.g., using the K-norm mechanism or Gaussian mechanism) that is proportional to the Lipschitz constant rather than a worst-case global bound, improving utility.

B. Unordered Item-wise Queries (PrivEMDItemWise)

For releasing a set of noisy outputs for each item in a user's dataset (e.g., a histogram), the mechanism applies a base item-level metric DP mechanism $A$ to each item and then shuffles the results.

Privacy Amplification by Shuffling: The authors generalize the "privacy amplification by shuffling" result to the metric DP setting. Since the output is an unordered list, an adversary cannot link specific outputs to specific input indices.
Technical Novelty: They prove that shuffling $m$ items reduces the privacy cost from $O(m\alpha)$ (via composition) to $O(\alpha\sqrt{m})$ . This result is derived by analyzing the coupling between input vectors and leveraging the properties of the shuffle model.

3. Extension to Unbounded Data

Real-world datasets often have varying sizes per user (unbounded setting), which complicates dEM analysis because the dataset size itself becomes a privacy concern.

Reduction: The authors propose a black-box reduction from unbounded to bounded dEM-DP.
Mechanism: They use sampling with replacement to project any user dataset onto a fixed size $s$ . They prove that this projection is "smooth," meaning the dEM distance between the projected datasets is close to the dEM distance between the original datasets (up to a small additive factor).
Discrete dEM-DP: To handle the additive error from sampling, they introduce a "discrete" definition of dEM-DP where changes with distance $\le r$ are protected uniformly. They show that for sufficiently large sample sizes, unbounded dEM-DP can be reduced to bounded dEM-DP with negligible loss in privacy semantics.

Key Contributions

Definition of User-Level Metric DP: The paper establishes a formal definition of Metric DP at the user level using Earth Mover's Distance, capturing both the magnitude and spatial aspects of data changes.
Novel Mechanisms:
- PrivEMDLinear: A mechanism for linear queries that leverages Lipschitz continuity to bound sensitivity, offering better utility than standard user-level DP for specific query types.
- PrivEMDItemWise: A general mechanism for item-wise queries that utilizes shuffling. The authors provide a generalized privacy amplification analysis showing a $\sqrt{m}$ improvement over standard composition bounds.
Unbounded Reduction: A black-box reduction technique that converts bounded dEM-DP mechanisms into unbounded ones via sampling, enabling the application of these mechanisms to datasets with variable user contribution sizes.
Utility Improvements: Theoretical analysis demonstrates that dEM-DP mechanisms can achieve strictly better utility (lower error) than standard user-level DP baselines for:
- Linear Embedding Queries: In both central and local models, particularly when the privacy parameter $\alpha$ is allowed to be larger than the standard $\epsilon$ for dissimilar inputs.
- Frequency Estimation: In the local model, the error is improved when the domain size and privacy parameters satisfy specific conditions, leveraging the fact that only "close" items (within clusters) require strong privacy.

Results and Significance

The paper claims that dEM-DP offers a more fine-grained privacy definition that aligns better with real-world privacy semantics.

Privacy Semantics: In standard DP, changing a user's data for an entire month is treated as equally sensitive as changing a single day's data. In dEM-DP, the single-day change is considered less sensitive (smaller $d_{EM}$ ), allowing for less noise and higher utility, while the month-long change receives a stronger guarantee.
Utility Gains: Theoretical bounds show that for linear embedding queries and frequency estimation, dEM-DP mechanisms can outperform standard user-level DP. For example, in frequency estimation, the error dependence on the domain size $k$ and the privacy parameter is improved under dEM-DP when the data exhibits structure (e.g., clustered metrics).
Generalizability: The reduction to bounded settings and the general shuffling analysis suggest that these techniques can be applied broadly to various metric spaces and query types beyond the specific examples (location, text, graphs) provided.

The authors position this work as the first to propose a general definition of user-level Metric DP via dEM, moving beyond specific text-based applications to a framework applicable to general metric spaces. They emphasize that while dEM-DP is a relaxation of standard DP, it provides a more practical trade-off for applications where data similarity correlates with sensitivity.