A Graph-Based Framework for Extending Metric Differential Privacy Mechanisms

Formulating extension as a general design paradigm for metric differential privacy over large structured domains

Ruiyao Liu; Chenxi Qiu· 2026· DOI 10.48550/arXiv.2609.14125

The core problem

Metric differential privacy (mDP) is a privacy notion well suited to structured secret domains, where the sensitivity of a secret depends on a metric distance between domain elements. However, directly constructing utility-aware mDP mechanisms over large or fine-grained domains is often computationally prohibitive. This paper studies **extension-based mDP design**, where a mechanism is first specified on a finite set of *seed records* and then extended to a larger *target domain*. The authors argue that, to their knowledge, this is the first work to systematically formulate extension as a general design paradigm for mDP rather than a method-specific construction. The central research question is: under what conditions does an extension of a locally specified mechanism yield a well-defined global mechanism that satisfies ε -mDP on the target domain? The paper answers this by proposing a graph-based extension framework, identifying three correctness requirements, and instantiating the framework with a tree-based algorithm for multi-resolution grids.

The paper reports experiments on **road-map datasets**. The evaluation demonstrates that the proposed approach achieves a strong **utility-scalability trade-off** while preserving **exact mDP guarantees**. In other words, the extension framework allows mechanisms to be constructed efficiently over large, fine-grained domains without sacrificing the formal privacy guarantee. The experiments compare the utility of the extended mechanism against the scalability benefits, showing that the graph-based extension and its tree-based instantiation can handle multi-resolution grid domains effectively. The abstract does not provide specific numerical results, but the qualitative claim is that the method balances utility and scalability better than direct construction over the full domain.

Metric differential privacy (mDP) is a privacy notion well suited to structured secret domains, where the sensitivity of a secret depends on a metric distance between domain elements. However, directly constructing utility-aware mDP mechanisms over large or fine-grained domains is often computationally prohibitive. This paper studies **extension-based mDP design**, where a mechanism is first specified on a finite set of *seed records* and then extended to a larger *target domain*. The authors argue that, to their knowledge, this is the first work to systematically formulate extension as a general design paradigm for mDP rather than a method-specific construction. The central research question is: under what conditions does an extension of a locally specified mechanism yield a well-defined global mechanism that satisfies ε -mDP on the target domain? The paper answers this by proposing a graph-based extension framework, identifying three correctness requirements, and instantiating the framework with a tree-based algorithm for multi-resolution grids.

The authors formalize extension-based mDP design using a graph-based framework. The target domain is represented as a graph whose vertices are records and whose edges encode adjacency or successor relations. A mechanism is first defined on a finite set of seed records, and then extended to the full domain by propagating the mechanism along the graph structure.

The main contribution of this work is conceptual: it reframes extension as a general design paradigm for mDP, rather than a collection of method-specific tricks. By identifying three correctness requirements—local mDP constraints, overlap consistency, and successor-level mDP preservation—the authors provide a reusable blueprint for extending any locally specified mDP mechanism to a larger structured domain. The graph-based framework is general and can in principle accommodate different graph structures and extension rules. The tree-based instantiation for multi-resolution grids shows one concrete way to realize the framework, using one-dimensional interpolation and dimension-wise composition to handle multi-dimensional domains. The approach is particularly relevant for domains such as road networks, where the secret is a location and the metric is road distance. Directly constructing an mDP mechanism over all fine-grained locations would be computationally prohibitive, but extension from a set of seed records makes the problem tractable. The preservation of exact ε -mDP guarantees is a key strength, as it ensures that the scalability gains do not come at the cost of privacy. Future work may explore other graph structures, alternative extension rules, and applications beyond road-map datasets. The framework also opens the door to a modular design approach, where local mechanisms and extension algorithms can be developed and analyzed independently.

CS practitioners and researchers

Opening member content…