Policy-graph privacy lets a data owner choose which pairs of sensitive values must look alike to an observer. For example, "do not reveal which of these two clinics I visited" can be required while "you may learn which district I was in" is allowed. A policy graph encodes this: nodes are possible values, and each edge says two values must stay indistinguishable up to a privacy budget $\epsilon$. Location systems that use it, such as PGLP and its epidemic-surveillance follow-up PANDA, first chop continuous space into grid cells or points of interest. They then build the graph on those pieces and spend $\epsilon$ per edge. This note argues that the grid size is a hidden privacy parameter. The worst-case leakage bound for policy graphs grows with the number of edge hops across the graph, so refining a grid with a fixed per-edge budget inflates it. In the limit of infinitely fine resolution, a "fixed" policy guarantees nothing. This is the policy-graph form of the familiar problem that information measures blow up when a finite domain is replaced by a continuous one.
We propose to make policy graphs consistent across resolution. A continuous policy becomes a length structure on the domain: a cost for moving between locations, with infinite-cost barriers where the owner permits disclosure. Leakage is then measured against an adversary who only needs to guess the true location to within a radius $\rho$. That adversary's resolution, not the mechanism's grid, is what makes the problem effectively finite. The deliverables are four. First, an empirical audit of whether current grid mechanisms actually leak more as the grid is refined. Second, a calibration rule and leakage bound that do not depend on grid size. Third, a tightness construction. Fourth, a matched-leakage utility comparison against planar Laplace noise on Geolife, Gowalla and Peopleflow.
Core Claim
Edwards et al. bound Blowfish leakage in terms of graph shape. Blowfish privacy is the policy-graph generalization of differential privacy introduced by He et al.. The leakage measure is min-entropy leakage, roughly how much one observed output multiplies an adversary's best chance of guessing the secret in one try. Their bound is $\log\sum_t e^{\epsilon d_t}$, where $d_t$ is the hop diameter of the $t$-th connected component. For a connected graph this is $\epsilon \cdot \mathrm{Diam}$. They prove the bound with a symmetrization argument that assumes a finite set of values, and they leave continuous domains open.
Our first observation is deflationary, and we state it up front. The diameter form of the bound holds for any domain, by a one-line argument. Every output's likelihood under any secret is within $e^{\epsilon d}$ of its likelihood under a fixed reference secret, so $\int \sup_x p(z\mid x)\,dz \le e^{\epsilon d}$. The symmetrization machinery matters for tightness, not for the bound itself. The open problem is therefore not "extend the bound to continuous space." The real questions are these: hop diameter is not a continuum quantity, and the bound degenerates under refinement; and nobody has checked whether deployed mechanisms actually attain the degenerate leakage.
Concretely, a grid of side $h$ over a region of Euclidean extent $D$, with adjacent-cell edges at budget $\epsilon$ each, has hop diameter of order $D/h$. The bound $\epsilon D/h$ therefore diverges as $h \to 0$. We claim, and will test, that this divergence is genuine for per-edge-calibrated mechanisms and not an artifact of the bound. We further claim that the fix is to treat the policy as a metric. Replacing hops with a policy geodesic distance $d_G(x,x')$ gives the condition
$$p(z\mid x) \le e^{\epsilon\, d_G(x,x')}\, p(z\mid x') \quad \text{for all outputs } z \text{ and secrets } x, x'.$$
Here $d_G$ is the cheapest path between $x$ and $x'$ under the owner's cost density, and it is infinite across a permitted-disclosure barrier. Under this condition, leakage depends on intrinsic geometry rather than on $h$.
The second claim is about the adversary's resolution. Exact-guess leakage is ill-posed for a continuous secret under a non-degenerate prior. The prior-free capacity stays finite, but it rewards distinctions finer than any real attacker needs. The "identity gain" limitation flagged by Alvim et al. is the same issue. We therefore use a ball gain: the adversary scores if its guess lands within $\rho$ of the truth. Our target theorem is a multiscale bound of the form
$$\mathcal{L}_\rho \le \log \sum_{i} \exp\!\big(\epsilon \cdot \mathrm{diam}_{G}(C_i)\big).$$
In it, $\mathcal{L}_\rho$ is the worst-case ball-gain leakage, $\{C_i\}$ is a partition of the domain into cells, each coverable by a $\rho$-ball, and $\mathrm{diam}_G(C_i)$ is a cell's diameter measured in the policy metric. The form is a guess: it is the Edwards component bound with "connected components" replaced by "adversary-resolution cells," and it interpolates between $\log N_\rho$ (a covering-number bound) and $\epsilon \cdot \mathrm{diam}_G$. Proving it, or finding the right correction, is part of the work.
Research Program
The work has three parts, ordered so that the cheapest one can kill the idea.
The first part is the resolution audit. We take PGLP-style grid policies, including adjacent-cell, semantic point-of-interest and geo-indistinguishability-induced graphs, and their mechanisms, the Policy-based Laplace and Planar Isotropic mechanisms. We instantiate them at grid sides $h$ from coarse to fine over the same region. For mechanisms with finite outputs, prior-free min-entropy capacity is exactly $\log\sum_z \max_x p(z\mid x)$, so we compute it from the channel matrix with no estimation error. Ball-gain leakage is computed by a linear program over priors at small scale and by a greedy lower bound at large scale. For mechanisms with continuous outputs we integrate the upper envelope of the output densities on a fine output grid. As a distribution-level cross-check we use the maximum-mean-discrepancy estimator, which Kuskonmaz et al. found to scale stably in dimension where histograms and optimal transport hit memory walls. We use it only as a sanity check, because that paper also shows it is a lower bound on information, not an exact measure. The question is simply whether measured leakage tracks $\epsilon D/h$.
The second part is the continuous formulation. It involves defining policies as cost densities with barriers, proving the resolution-free diameter bound and the multiscale ball-gain bound, and proving tightness. For tightness we adapt Edwards et al.'s block-diagonal channel family, whose leakage-to-bound ratio approaches 1. In continuous space we replace their automorphism orbits with cells that are approximately isometric in the policy metric.
This part also has to handle the second continuity issue that PGLP raises: adversarial background knowledge that removes nodes. In PGLP this creates "isolated nodes" and requires graph repair. In the metric view, deleting regions can disconnect the domain or lengthen geodesics, and we will bound the resulting leakage increase in terms of how much $d_G$ grows. This gives a quantitative, resolution-free criterion for when repair is needed.
The third part is mechanism design. We build a mechanism calibrated to $d_G$ in two variants. One is an exponential mechanism over the policy metric. The other is a planar Laplace mechanism run independently inside each barrier-delimited region. We give a calibration rule so that a mechanism discretized at any $h$ inherits the continuous guarantee up to an $O(\epsilon h)$ correction, which comes from the triangle inequality on cells of side $h$.
Baselines
The naive reference point is current practice. It is PGLP with a fixed per-edge budget at whatever grid the deployment chose, and its reported guarantee is "$\epsilon$ per edge." We run it at the identical grid sides, trajectories and $\epsilon$ values as our mechanism. Our method beats it if, at equal utility, its measured ball-gain leakage is resolution-stable while the baseline's grows with $1/h$. If the baseline's measured leakage is flat in $h$, the proposal's motivation collapses and we will report that.
The strongest existing competitor is geo-indistinguishability via planar Laplace noise. It is metric differential privacy with Euclidean distance, surveyed by Xie et al., and PGLP shows it to be a special case of a policy graph. It is the strongest competitor because it is already resolution-free; our continuous formulation contains it as the case of uniform cost with no barriers. The fair comparison fixes worst-case ball-gain leakage $\mathcal{L}_\rho$, measured by the same exact computation, rather than fixing the nominal $\epsilon$, since the two mechanisms' nominal budgets mean different things. Both get the same tuning grid over their single noise parameter. We beat it if, at matched $\mathcal{L}_\rho$, we get lower error on the task the policy targets: point-of-interest category queries on Peopleflow, contact-tracing accuracy on Gowalla, and reproduction-number estimates on Geolife as in PANDA.
The file reports no scalar for either PGLP mechanism or for planar Laplace on these datasets. PGLP states only that the Planar Isotropic mechanism consistently outperforms the Laplace one, and that custom policies give "full usability" on Peopleflow category queries; we found no reported number on Lacuna for either. We will therefore rerun both from the descriptions.
The third baseline is the spanning-tree route of Haney et al.. It maps tree policies exactly to standard differential privacy, so off-the-shelf algorithms can run on them. Non-tree policies are handled through a spanning tree at a stretch cost $\ell$ that inflates the guarantee to $\ell\epsilon$. We run it on the same grids and report both its nominal and measured leakage. Beating it means lower leakage at equal utility on grids with many cycles.
Two ablations isolate the key ingredient. The first keeps our mechanism but replaces the policy geodesic with hop count. This tests whether the metric, rather than the mechanism family, produces resolution stability. The second removes barriers, which tests whether semantic disconnection, the thing Euclidean metric privacy cannot express, is where any utility gain comes from.
On the theory side, the reference is Edwards et al.'s finite bound, whose reported tightness is a leakage-to-bound ratio approaching 1 as their free parameter goes to 0, on distance-threshold, cycle and complete graphs. Our continuous tightness construction should reproduce a ratio approaching 1 in the continuum limit.
Why not just…?
Why not just discretize finely and apply the existing finite bound? The finite bound applies, but it is $\epsilon$ times hop diameter, which grows as the grid shrinks. Discretizing more finely makes the certified guarantee worse, not better, unless the per-edge budget is rescaled. Rescaling the per-edge budget with grid size is exactly the calibration this proposal formalizes. Separately, Kuskonmaz et al. show histogram-style binning becomes infeasible in memory by five dimensions. That matters once location is joined with time or other attributes. The resolution audit shows directly whether the naive route is harmful in practice.
Why not just use metric differential privacy with Euclidean distance? This is the real threat. Our continuous formulation is metric privacy under a non-Euclidean, possibly infinite, policy metric, and we do not claim otherwise. What Euclidean metric privacy cannot do is give zero protection across a barrier while giving strong protection within it. PGLP's Peopleflow results suggest such semantic policies matter for usability. But the advantage could vanish once leakage, rather than nominal $\epsilon$, is matched. The matched-$\mathcal{L}_\rho$ comparison with the barrier ablation settles this. If planar Laplace ties us, the contribution reduces to the audit and the bound, and we will say so.
Why not just take a spanning tree and use transformational equivalence? Haney et al. themselves show that the tree embedding stretches distances by $\ell$ and inflates privacy loss to $\ell\epsilon$. On fine grids, which contain many cycles, $\ell$ grows with resolution. Brenner and Nissim further show that cycles and branching are exactly where no single mechanism is optimal for every user's loss function. So discarding cycles discards the structure that governs the trade-off. We test this rather than assume it, by reporting spanning-tree leakage across $h$.
Proposed Experiments
The data are Geolife (Beijing GPS trajectories), Gowalla (Los Angeles check-ins) and Peopleflow (Tokyo semantic locations), all used by PGLP and PANDA. They are supplemented by synthetic two-dimensional domains with hand-placed barriers, where ground-truth policy geodesics are known exactly. Each mechanism is run at five grid sides spanning a factor of 16, at $\epsilon$ values matching PGLP's range, and at adversary radii $\rho$ from 50 m to 1 km.
The decisive checks are four. The first is whether measured leakage of fixed-per-edge mechanisms scales like $1/h$; this is the go/no-go for the whole project. The second is whether our calibrated mechanism's measured leakage is flat in $h$ to within the predicted $O(\epsilon h)$ correction. The third is whether the multiscale bound is within a small constant of measured ball-gain leakage on the synthetic domains, and approaches tightness under the constructed channel family. The fourth is whether, at matched $\mathcal{L}_\rho$, the barrier-aware mechanism beats planar Laplace on task utility on Peopleflow and Geolife, with the barrier ablation showing where any gain comes from.
References
- PGLP: Customizable and Rigorous Location Privacy Through Policy Graph
- PANDA: Policy-aware Location Privacy for Epidemic Surveillance
- A Graph Symmetrization Bound on Channel Information Leakage Under Blowfish Privacy
- Blowfish privacy: tuning privacy-utility trade-offs using policies
- On the information leakage of differentially-private mechanisms
- Investigation of Alternative Measures for Mutual Information
- A Decade of Metric Differential Privacy: Advancements and Applications
- Design of Policy-Aware Differentially Private Algorithms
- Impossibility of Differentially Private Universally Optimal Mechanisms