Policy Graphs for Generalized Differential Privacy

11 concepts5 papers2 proposals

Standard differential privacy operates on a binary assumption: either two databases are neighbors (differing by exactly one record), or they are not. While this mathematical clean-cut simplifies algorithm design, it imposes a rigid "one-size-fits-all" constraint on real-world data. In applications like location privacy, this rigidity forces an unnatural choice: either protect all spatial transitions equally—destroying the utility of the data for local analytics—or relax privacy globally.

To bridge this gap, a powerful generalization has emerged: policy graphs. By modeling privacy constraints as topological networks, researchers have unified disparate privacy definitions and unlocked highly customizable privacy-utility trade-offs.

The Core Intuition: Privacy as a Graph

Instead of treating indistinguishability as a fixed global property, we can represent a privacy policy as an undirected graph $G = (V, E)$.

Standard DP (Complete Graph)         Custom Policy Graph
     [A] --- [B]                         [A] --- [B]
      |   X   |                           |       
     [C] --- [D]                         [C] --- [D]
(All states indistinguishable)     (A-B and C-D/A-C are protected;
                                    B-D transition is exposed)

In this formulation:

  • Nodes ($V$) represent discrete sensitive states, such as physical locations or entire database instances.
  • Edges ($E$) represent pairs of states that must remain indistinguishable to an outside observer.

If an edge exists between node $A$ and node $B$, any algorithm operating on the data must ensure that its output distributions for $A$ and $B$ are mathematically close (typically bounded by an $\epsilon$ privacy parameter). If no edge exists, the algorithm is free to distinguish between them with high fidelity.

This simple shift from a uniform neighboring relation to a customizable graph structure provides immense flexibility. For instance, in location-based services, nodes can represent coordinates. By connecting only nearby locations with edges, we can guarantee that an adversary cannot pinpoint a user's exact neighborhood, while still allowing the system to easily distinguish whether the user is in New York or Los Angeles.

Unifying Privacy Frameworks

This graph-theoretic view is not just a new tool; it is a Rosetta Stone for existing privacy models. By reconfiguring the topology of the policy graph, a single system architecture can emulate and generalize multiple distinct privacy notions.

In the context of relational databases, Samuel Haney et al. (2015) introduced the Blowfish privacy framework. In two parallel papers, Samuel Haney et al. (2015) and the authors demonstrated that adjusting the policy graph allows database administrators to specify exactly which sensitive attributes or record combinations require protection. This avoids the utility degradation that comes from blindly applying standard differential privacy to complex schemas.

A similar unification occurred in spatial privacy. Yang Cao et al. (2020) introduced PGLP (Policy Graph Location Privacy), showing that standard models like Geo-Indistinguishability and $\delta$-Location Set Privacy are merely specific topological configurations of a generalized policy graph. In subsequent work on epidemic surveillance, Yang Cao et al. (2020) utilized this framework to balance public health tracking with individual privacy, demonstrating that policy graphs allow systems to dynamically adjust constraints based on the specific utility needs of a task (e.g., macro-level movement monitoring versus micro-level contact tracing).

Why It Works: Transformational Equivalence

The primary challenge of introducing a generalized privacy definition is that it usually requires inventing new algorithms from scratch. Policy graphs circumvent this issue through transformational equivalence.

As shown by Samuel Haney et al. (2015), generalized privacy problems can be mapped back to standard differential privacy mechanisms. For example, the widely used matrix mechanism—which answers linear queries by adding structured noise—can be extended to support policy graphs. By computing a linear transformation derived directly from the structure of the policy graph, the mechanism can concentrate noise only on the relations protected by the edges, leaving unprotected data relationships sharp and accurate.

The Topological Catch: Graph Diameter and Leakage

While policy graphs offer unprecedented freedom, changing the graph topology has profound, sometimes counterintuitive, consequences for global privacy.

Privacy constraints are local: they dictate indistinguishability between adjacent nodes. However, an adversary is often interested in global properties. If node $A$ is connected to node $B$, and $B$ is connected to $C$, then even if there is no direct edge between $A$ and $C$, they inherit a degree of protection via the privacy property's transitivity (the triangle inequality of differential privacy).

This relationship creates a fundamental tension between local policy definitions and global information leakage. Tobias Edwards et al. (2022) investigated this phenomenon by bounding channel information leakage (specifically min-entropy leakage) under Blowfish privacy. They proved a vital geometric truth: the maximum potential for global information leakage is determined by the topological diameter of the connected components within the policy graph.

Longer Path (Larger Diameter) -> Higher Global Uncertainty -> Lower Leakage Bound
[A] --- [B] --- [C] --- [D] --- [E]

Shorter Path (Smaller Diameter) -> Lower Global Uncertainty -> Higher Leakage Bound
[A] --- [B]

This leads to a fascinating paradox: if a data designer decides to protect fewer secrets by removing edges from the policy graph, they might expect the system to become less private overall. However, removing edges can break paths, altering the shortest-path distances between nodes. As Tobias Edwards et al. (2022) demonstrated, expanding the diameter of the database adjacency graph changes the global bounds on what an adversary can learn, revealing that local policy tweaks can radically reshape global information disclosure in non-linear ways.

Key Foundational Work

PGLP: Customizable and Rigorous Location Privacy Through Policy Graph (2020) — contributed 3 concept elements to this direction.
PANDA: Policy-aware Location Privacy for Epidemic Surveillance (2020) — contributed 3 concept elements to this direction.
Design of Policy-Aware Differentially Private Algorithms (2015) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_indistinguishability_a2069efd,
  title = {graph-based indistinguishability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-indistinguishability/rdr_a2069efd48054bc49b182e241658ec10},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_based_indistinguishability_a2069efd_v1,
  title = {graph-based indistinguishability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-indistinguishability/rdr_a2069efd48054bc49b182e241658ec10/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake