SoK: Metric Differential Privacy in Theory and Practice
Xinpeng Xie (Paper author · University of North Texas), Chenyang Yu (Paper author · University of North Texas), Yan Huang (Paper author · University of North Texas), Yang Cao (Paper author · Institute of Science Tokyo), Chenxi Qiu (Paper author · University of North Texas)
Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Moose
Overview
This talk, presented at PETS, delves into the intricate world of Metric Differential Privacy (MDP), a sophisticated extension of traditional Differential Privacy (DP). The presentation, based on a "Survey of Knowledge" (SoK) paper, provides a comprehensive framework for understanding, categorizing, and applying MDP mechanisms. It highlights the fundamental difference between DP and MDP: while classical DP treats all neighboring datasets as uniformly important, MDP introduces a metric to quantify the varying importance or "distance" between neighbors, thereby offering greater flexibility and utility in diverse applications.

Key moments
- 0:00 Introduction to Metric Differential Privacy and paper motivation
- 2:00 Taxonomy: Three types of Metric Differential Privacy mechanisms
- 4:00 Comparing advantages and limitations of MDP mechanisms
- 5:00 Utility measurements and recent trends in MDP research
- 6:00 Applying MDP to graph, image, voice, location, text
- 8:00 Summary of MDP application observations and hybrid settings
- 8:50 Future research directions and open challenges in MDP
SoK: Metric Differential Privacy in Theory and Practice
Speakers: Xinpeng Xie (Paper author, University of North Texas), Chenyang Yu (Paper author, University of North Texas), Yan Huang (Paper author, University of North Texas), Yang Cao (Paper author, Institute of Science Tokyo), Chenxi Qiu (Paper author, University of North Texas)
Conference: PETS
YouTube: https://www.youtube.com/watch?v=zgjw16k63is
Overview
This talk, presented at PETS, delves into the intricate world of Metric Differential Privacy (MDP), a sophisticated extension of traditional Differential Privacy (DP). The presentation, based on a "Survey of Knowledge" (SoK) paper, provides a comprehensive framework for understanding, categorizing, and applying MDP mechanisms. It highlights the fundamental difference between DP and MDP: while classical DP treats all neighboring datasets as uniformly important, MDP introduces a metric to quantify the varying importance or "distance" between neighbors, thereby offering greater flexibility and utility in diverse applications.
The core motivation behind this SoK paper is to address a significant gap in existing literature. Although surveys on DP and location privacy (a key application area for MDP) exist, none thoroughly analyze how MDP mechanisms are designed, their underlying patterns, or their applicability across different domains. The authors, a collaborative team from the University of North Texas and the Institute of Science Tokyo, aim to provide a mechanism-level taxonomy, explore current and future applications, and identify open challenges within the MDP landscape. This work is crucial for researchers and practitioners seeking to design more effective and privacy-preserving systems, particularly in scenarios where the notion of "closeness" between data points is inherently non-uniform.
Background
▶ Watch: Introduction to Metric Differential Privacy and paper motivation (0:00)
The concept of Differential Privacy (DP) has emerged as a gold standard for quantifying and enforcing privacy guarantees in data analysis. At its core, DP ensures that the output of a data analysis mechanism is nearly identical whether a specific individual's data is included or excluded from the dataset. This property provides strong privacy guarantees, making it difficult for an adversary to infer sensitive information about individuals. However, traditional DP often operates under a simplified assumption: all "neighboring" datasets (those differing by a single individual's record) are considered equally impactful on the output.
This uniform treatment, while simplifying the theoretical framework, can be overly restrictive in real-world scenarios where the "distance" or "similarity" between data points varies significantly. For instance, in location privacy, two locations might be considered "neighbors" if they are geographically close, but their impact on a query might depend on the specific road network or points of interest. This is where Metric Differential Privacy (MDP) offers a more nuanced approach. MDP extends DP by incorporating a metric (a distance function) that quantifies the relationship between neighboring datasets. This metric allows the privacy mechanism to perturb data in a way that is sensitive to these distances, rather than applying a uniform level of noise. For example, if two locations are very close, a smaller perturbation might be acceptable compared to two locations that are further apart, allowing for better utility while maintaining privacy guarantees tailored to the metric.
The evolution of MDP has seen a significant focus on location privacy, where the inherent spatial relationships lend themselves naturally to metric-based definitions. However, as the research landscape has matured, MDP has found applications across a broader spectrum of domains, including graph analysis, image processing, voice recognition, and text analysis. Despite this proliferation of applications and existing surveys on specific areas like location privacy, a holistic understanding of the design principles and underlying mechanisms of MDP has been lacking. The authors of this SoK paper were motivated to fill this void, providing a structured taxonomy that dissects how these diverse MDP mechanisms are constructed and applied, ultimately guiding future research and development in this critical field.
Key Findings
▶ Watch: Comparing advantages and limitations of MDP mechanisms (4:00)
The talk presented several critical findings derived from the comprehensive survey of existing MDP literature, categorizing mechanisms, identifying prevalent practices, and highlighting emerging trends.
Firstly, the authors established a mechanism-level taxonomy, identifying three fundamental types of MDP mechanisms:
- Homogeneous Distance Metrics (HTM): These mechanisms are characterized by a straightforward definition of the metric, allowing for a closed-form function to describe the perturbation distribution. They are particularly well-suited for continuous domains where distances can be easily and uniformly calculated.
- Non-Homogeneous Distance Mechanisms (NHDM): Unlike HTM, NHDM mechanisms incorporate additional constraints on the output domain. This means the output space is not necessarily continuous or fully accessible, but rather restricted to a candidate set. This type is highly useful in scenarios with finite output domains or specific structural limitations, such as road networks in location privacy or discrete states in neural networks.
- Optimized Perturbation Mechanisms (OPM): These are the most complex, involving a minimization problem to design the perturbation mechanism. OPMs are designed to optimize a specific utility metric or cost function, making them ideal when the task-specific utility can be clearly defined. They aim to find the optimal perturbation strategy given a prior distribution and a defined cost function.
Secondly, the survey provided a comparative analysis of these mechanisms, highlighting their respective advantages and limitations. HTM excels in continuous domains due to its simplicity and closed-form solutions. NHDM is invaluable for finite or constrained output spaces, offering practical solutions for real-world limitations. OPM stands out when a task-specific utility function is known, allowing for tailored privacy-utility trade-offs.
Thirdly, the research identified patterns in utility measurement and mechanism adoption. The predominant utility measurement across existing papers was found to be expected distance. In terms of mechanism usage, HTM is the most common, especially for simpler tasks. However, OPM is widely employed for more complicated tasks, such as spatial querying or sorting, where defining a specific utility function is feasible and beneficial. A notable trend observed in recent experimental papers is the tendency to study larger domain sizes (referred to as "key scale"), indicating a move towards evaluating MDP in more complex and realistic settings.
Finally, the survey meticulously mapped MDP applications across various data modalities, identifying the specific metrics utilized in each:
- Graph Privacy: Often employs node edit distance or structured distance to quantify changes in graph topology.
- Image Privacy: Uses latent space distance or distances between different embeddings to measure visual similarity.
- Voice Privacy: Primarily relies on angular X-vector or other voice embedding distances to differentiate voice prints.
- Location Privacy: Commonly uses Euclidean distance for simple spatial relationships or road network shortest path for more realistic urban environments.
- Text Privacy: Leverages Word Movers Distance or embedding distance to capture semantic similarity between text segments.
The findings also revealed that for location data, HTM is preferred for simple tasks, while OPM is chosen for complex tasks like spatial crowdsourcing. Furthermore, there's an emerging trend of hybrid settings, combining different mechanisms to balance various benefits and trade-offs.
Technical Deep Dive
▶ Watch: Utility measurements and recent trends in MDP research (5:00)
The theoretical framework presented by the authors meticulously categorizes existing MDP mechanisms into three distinct types, each with its unique mathematical underpinnings and applicability.
Homogeneous Distance Metrics (HTM)
Homogeneous Distance Metrics (HTM) represent the most straightforward category of MDP mechanisms. In this paradigm, once a metric (a distance function) is defined over the domain, it is possible to derive a closed-form distribution for the perturbation mechanism. This means that for a given input X, the probability distribution of the output Y satisfying the MDP properties can be expressed as a direct mathematical function. For instance, if the metric is Euclidean distance in a continuous space, the perturbation might follow a Laplace or Gaussian distribution whose parameters are directly related to the privacy budget and the chosen metric.
The primary advantage of HTM lies in its suitability for continuous domains. When data points reside in a space where distances can be uniformly and consistently measured (e.g., real numbers, geometric coordinates without complex constraints), HTM provides an elegant and often computationally efficient solution. The "homogeneity" implies that the cost of perturbing a data point by a certain distance is consistent across the domain, simplifying the design of the noise-adding mechanism. This makes HTM a frequently adopted approach, particularly for simpler tasks where the underlying data space is well-behaved.
Non-Homogeneous Distance Mechanisms (NHDM)
Non-Homogeneous Distance Mechanisms (NHDM) address scenarios where the output space is not continuous or uniform, but rather subject to additional constraints. This often manifests as a finite output domain or a set of candidate outputs. Unlike HTM, where any point in the continuous space might be a valid output, NHDM acknowledges that only a subset of possibilities is legitimate.
A prime example is location privacy in road networks. While Euclidean distance might define proximity between any two points on a map, a person cannot stand in the middle of a lake or a building. The actual "neighbors" are constrained by the road infrastructure. NHDM mechanisms are designed to operate within these constrained spaces, ensuring that the perturbed output remains within the valid set of locations. This approach is also relevant in settings like neural networks, where the output might be restricted to a discrete set of labels or embeddings. The "non-homogeneous" aspect refers to the fact that while neighbors might have a defined distance, the ability to reach certain neighbors or the cost of doing so might vary due to these domain-specific constraints.
Optimized Perturbation Mechanisms (OPM)
Optimized Perturbation Mechanisms (OPM) represent the most sophisticated category, characterized by their reliance on optimization problems to design the perturbation strategy. In OPM, the goal is not merely to add noise, but to add noise in a way that minimizes a specific utility metric or cost function while still satisfying the MDP privacy guarantees.
The core of an OPM is often formulated as a minimization problem, as shown in the talk:
minimize Z given prior distribution pi and cost C
Here, Z represents the perturbation mechanism, pi is the prior distribution of the input data, and C is a cost function or utility metric that quantifies the desired properties of the output. This cost function is task-specific, meaning it must be carefully defined based on the application's objectives. For instance, in a spatial query task, C might represent the accuracy of the query results. By explicitly incorporating utility into the mechanism design, OPMs can achieve a superior balance between privacy and utility, especially for complex tasks. This makes them highly valuable when the exact task is known, and its performance can be quantitatively measured. Examples include spatial crowdsourcing or complex data sorting tasks where specific utility functions can be designed.
Comparison and Utility Measurement
The authors provide a comparative analysis, highlighting that HTM is best for continuous domains, NHDM for finite/constrained domains, and OPM for scenarios with well-defined, task-specific utility functions. Across all mechanisms, the most common utility measurement found in existing literature is expected distance, which quantifies the average deviation between the true and perturbed data points.
Application-Specific Metrics
A crucial part of the technical deep dive involves examining how different data modalities necessitate distinct metrics for MDP:
- Graph Privacy: For data structured as graphs, metrics like node edit distance (the minimum number of node or edge operations to transform one graph into another) or structured distance are used. These metrics are vital for preserving privacy while allowing analysis of network properties.
- Image Privacy: In image processing, privacy often involves perturbing image features. Latent space distance or distances between embeddings (vector representations of images derived from deep learning models) are employed to measure the similarity or difference between images in a high-dimensional feature space.
- Voice Privacy: Protecting voice data involves obscuring individual voice characteristics. The angular X-vector is a prominent metric here, representing the distance between voice embeddings. This metric is particularly effective because it can accurately differentiate between distinct voice prints, ensuring that perturbations effectively mask identity without destroying useful phonetic information.
- Location Privacy: This domain uses intuitive metrics like Euclidean distance for simple spatial separation. However, for real-world applications, road network shortest path distance is more accurate, reflecting the actual travel time or distance between locations within a defined network.
- Text Privacy: When dealing with textual data, metrics such as Word Movers Distance (WMD) or various embedding distances (e.g., cosine similarity of word or sentence embeddings) are used. WMD, for instance, measures the minimum "cost" to transform one document into another by moving words, reflecting semantic similarity.
The observed trend towards studying larger domain sizes (key scale) in recent experiments underscores the increasing complexity and scale of real-world datasets, pushing the boundaries of MDP applicability and efficiency. The emergence of hybrid settings, combining different mechanism types, further indicates a move towards more adaptive and context-aware privacy solutions.
Demo / Proof of Concept
▶ Watch: Summary of MDP application observations and hybrid settings (8:00)
As an "SoK" (Survey of Knowledge) paper, the primary contribution of this work is a comprehensive review, categorization, and analysis of existing Metric Differential Privacy mechanisms and applications. The talk and the underlying paper do not present a novel algorithm or system that would typically feature a live demonstration or proof of concept. Instead, the authors' focus is on synthesizing existing knowledge, providing a taxonomy, and identifying future research directions. Therefore, no specific demo or proof of concept was presented during this talk.
Defensive Implications
▶ Watch: Future research directions and open challenges in MDP (8:50)
Understanding the nuances of Metric Differential Privacy (MDP) mechanisms, as outlined in this SoK paper, provides critical insights for defenders tasked with building privacy-preserving systems. The taxonomy and analysis offer a roadmap for selecting, implementing, and evaluating MDP in diverse real-world scenarios.
- Informed Mechanism Selection: Defenders must choose the appropriate MDP mechanism based on the nature of their data and the specific privacy task.
- For continuous data domains where distances are straightforward (e.g., GPS coordinates without road network constraints, simple numerical data), Homogeneous Distance Metrics (HTM) offer efficient and well-understood solutions with closed-form distributions.
- When dealing with constrained or finite output domains (e.g., locations on a road network, discrete categories, specific states in a system), Non-Homogeneous Distance Mechanisms (NHDM) are essential. Defenders should identify and incorporate these real-world constraints into their privacy design to ensure practicality and utility.
- For tasks where specific utility goals can be quantified (e.g., maintaining accuracy for a particular query type, preserving the utility of a recommendation system), Optimized Perturbation Mechanisms (OPM) provide the most tailored approach. This requires careful definition of the cost function and understanding the prior distribution of the data.
- Context-Aware Metric Design: The choice of the underlying metric is paramount. Defenders need to move beyond simple Euclidean distances and adopt metrics that truly reflect the "distance" or "similarity" relevant to their data modality and application.
- For graph data, metrics like node edit distance are crucial for preserving structural properties.
- For image and voice data, using latent space distances or embedding distances (like angular X-vector for voice) ensures that privacy mechanisms operate on meaningful feature representations.
- In location privacy, transitioning from simple Euclidean distance to road network shortest path significantly improves the realism and utility of privacy-preserving location data.
- For text data, employing Word Movers Distance or sophisticated embedding distances helps maintain semantic coherence while adding privacy.
- Utility-Privacy Trade-off Management: The finding that expected distance is the most common utility measurement highlights a universal concern. Defenders must rigorously evaluate how their chosen MDP mechanism impacts the utility of the data for its intended purpose. OPMs, by design, attempt to optimize this trade-off, but even with HTM and NHDM, careful parameter tuning and empirical evaluation are necessary. The trend towards larger domain sizes in research suggests that scalability and performance of MDP mechanisms are becoming increasingly important for real-world deployment.
- Addressing Open Challenges: The identified open challenges provide a roadmap for proactive defensive strategies:
- Mechanism Selection: Developing automated or semi-automated tools for optimal mechanism selection based on data characteristics and task requirements would greatly assist defenders.
- Scalability Optimization: As datasets grow, the computational overhead of MDP can become prohibitive. Defenders need to explore and implement optimized algorithms for larger-scale data.
- Composition: Understanding how privacy guarantees compose when multiple MDP mechanisms are applied sequentially is critical for complex systems. Robust composition theorems for MDP are needed.
- Amplification (e.g., Shuffle DP): Exploring how MDP can be integrated with advanced privacy models like shuffle DP could offer stronger privacy guarantees or improved utility in distributed settings.
- Local Models: Applying MDP in local DP models (where each user perturbs their own data before sharing) presents unique challenges and opportunities for enhanced privacy.
- Context-Aware Metrics: Further research into context-aware metrics that dynamically adapt based on environmental factors or user behavior will lead to more intelligent and effective privacy mechanisms.
By thoroughly understanding these aspects, defenders can move beyond generic privacy solutions and implement MDP mechanisms that are precisely tailored to their specific data, application, and threat model, ultimately building more robust and trustworthy systems.
Key Takeaways
- Metric Differential Privacy (MDP) extends traditional DP by incorporating a distance metric, allowing for more flexible and context-aware privacy guarantees based on the varying importance of neighboring data points.
- Three primary mechanism types exist: Homogeneous Distance Metrics (HTM) for continuous domains and closed-form solutions; Non-Homogeneous Distance Mechanisms (NHDM) for constrained or finite output domains (e.g., road networks); and Optimized Perturbation Mechanisms (OPM) for tasks with specific, definable utility functions, solved via optimization problems.
- Mechanism choice depends on data and task: HTM is common for simple, continuous tasks; NHDM is crucial for real-world constraints; OPM excels in complex tasks like spatial crowdsourcing where utility can be optimized.
- Application-specific metrics are vital: Different data modalities (graph, image, voice, location, text) require tailored distance metrics, such as node edit distance, latent space distance, angular X-vector, road network shortest path, and Word Movers Distance, respectively.
- Research trends highlight increasing complexity: Recent studies tend to investigate larger domain sizes, and there's a growing interest in hybrid settings that combine different MDP mechanisms to achieve better trade-offs.
- Significant open challenges remain: Key areas for future research include mechanism selection, scalability optimization, composition of privacy guarantees, integration with models like shuffle DP, local models, and the development of more context-aware metrics.
About the Speaker(s)
The talk was presented by Yang Cao, a PhD student from the National Institute of Science Tokyo. This work is a collaborative effort with researchers from the University of North Texas, including Xinpeng Xie, Chenyang Yu, Yan Huang, and Chenxi Qiu, all credited as paper authors. Their collective expertise spans the theoretical foundations and practical applications of differential privacy, with a particular focus on the nuances of Metric Differential Privacy.
Reviews
Dr. Zero (Offensive Security Researcher) — SOLID
This is a Systematization of Knowledge (SoK) paper mapping the current landscape of Metric Differential Privacy. It doesn't drop any novel math, but it categorizes existing mechanisms cleanly into a usable taxonomy. It's solid academic groundwork that saves privacy engineers months of literature review.
Heather Calloway (CISO) — SOLID
This is an academic survey of Metric Differential Privacy (MDP)—the mathematical layer that allows us to apply privacy controls to complex datasets without destroying their business utility. It is not for your security operators, but it is required reading for your Chief Data Officer and privacy engineering leads. If your business is training models on location, voice, or text data, this is how you satisfy both the regulator and the product team.
→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026
All talks from Privacy Enhancing Technologies Symposium (PETS) 2026