Lune

CCS2026Top-tier venue

A Graph-Based Framework for Extending Metric Differential Privacy Mechanisms

Ruiyao Liu, Chenxi Qiu

Abstract

Metric differential privacy (mDP) is well suited to structured secret domains, but directly constructing utility-aware mechanisms over large or fine-grained domains is often computationally prohibitive. We study 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. To our knowledge, this is the first work to systematically formulate extension as a general design paradigm for mDP rather than a method-specific construction. We present a graph-based extension framework, identify three requirements for correctness, local mDP constraints, overlap consistency, and successor-level mDP preservation, and show that, under these conditions, the induced global mechanism is well defined and satisfies ϵ\epsilon-mDP on the target domain. We further instantiate the framework with a tree-based extension algorithm for multi-resolution grids, where multi-dimensional extension is realized through one-dimensional interpolation and dimension-wise composition. Experiments on road-map datasets demonstrate that our approach achieves a strong utility-scalability trade-off while preserving exact mDP guarantees.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained Domains cites Dynamic Differential Location Privacy with Personalized Error Bounds
  • Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained Domains cites Perceptual Indistinguishability-Net (PI-Net): Facial Image Obfuscation With Manipulable Semantics
  • PAnDA: Rethinking Metric Differential Privacy Optimization at Scale with Anchor-Based Approximation cites Dynamic Differential Location Privacy with Personalized Error Bounds
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on4

  1. Dynamic Differential Location Privacy with Personalized Error BoundsLei Yu, Ling Liu, Calton PuNDSS 2017 · 100 citations
  2. Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained DomainsChenxi QiuUSENIX Security 2026 · 3 citations
  3. PAnDA: Rethinking Metric Differential Privacy Optimization at Scale with Anchor-Based ApproximationRuiyao Liu, Chenxi QiuCCS 2025
  4. Perceptual Indistinguishability-Net (PI-Net): Facial Image Obfuscation With Manipulable SemanticsJia-Wei Chen, Li-Ju Chen, Chia-Mu Yu, Chun-Shien LuCVPR 2021

Related papers

  1. A General Framework for Per-record Differential PrivacyXinghe Chen, Dajun Sun, Quanqing Xu, Wei DongSIGMOD 2026
  2. Enhancing Local Differential Privacy Accuracy by Exploiting Inherent UncertaintyPeng Tang, Xiya Shao, Rui Chen, Ning Wang et al.SIGMOD 2026
  3. Metric Differential Privacy at the User-Level via the Earth-Mover's DistanceJacob Imola, Amrita Roy Chowdhury, Kamalika ChaudhuriCCS 2024
  4. Differentially Private Release of Synthetic GraphsMarek Eliás, Michael Kapralov, Janardhan Kulkarni, Yin Tat LeeSODA 2020 · 19 citations
  5. Differentially Private Selection Using Smooth SensitivityIago C. Chaves, Victor A. E. de Farias, Amanda Perez, Diego Mesquita et al.S&P 2025
Dusk over the sea between two cliffs drawn in fine vertical lines