Differential Privacy Mechanisms Compared for Spatial Data

Choosing a differential privacy mechanism for a synthetic spatial generator is a design decision with irreversible downstream consequences: the mechanism fixes what “one record” means, how sensitivity is measured, how budget composes across releases, and how much spatial signal survives. This page is part of Synthetic Spatial Data Architecture & Fundamentals: where the privacy-preserving generation frameworks reference shows how to wire a budgeted mechanism into a generation DAG, this page is the comparison you consult before wiring — Laplace, Gaussian, exponential, and planar-Laplace (geo-indistinguishability) set side by side on the axes that actually decide the outcome. The wrong choice does not fail loudly; it ships a release whose $\varepsilon$ is honest for scalars but meaningless for correlated coordinates, or whose noise is calibrated in degrees and therefore latitude-dependent.

Problem Framing: The Mechanism Is the Guarantee

The engineering failure this page prevents is the misapplied mechanism — a differential privacy claim that is technically stated but does not hold for the query it protects. It shows up in four recurring forms.

• Wrong sensitivity norm. Adding Gaussian noise but bounding sensitivity in $\ell_1$, or adding Laplace noise sized against an $\ell_2$ bound, under-noises the output. The audited $\varepsilon$ is a number in a config file, not a property of the release.
• Degree-space calibration. Sensitivity and noise scale computed in EPSG:4326 degrees make the guarantee latitude-dependent: a scale tuned near the equator over-protects at the poles and under-protects nowhere consistently. Every mechanism here assumes a projected metric CRS.
• Naive composition. Summing per-stage $\varepsilon_i$ across a coordinate pipeline and many releases is correct but wasteful for Laplace, and the wrong accountant entirely for Gaussian, which needs Rényi or zero-concentrated accounting to avoid spending the budget an order of magnitude too fast.
• Category leakage through numeric noise. Trying to privatize a discrete choice — which synthetic zone a facility lands in, which land-use class an attribute takes — by adding continuous noise and rounding. The rounding boundary leaks, and the exponential mechanism exists precisely for this case.

None of these fail a unit test. They fail an adversary, which is why the mechanism decision must be made deliberately and then falsified empirically through adversarial privacy testing. This page gives the decision; that page gives the check.

Prerequisites & Toolchain

The comparison assumes the standard synthetic-spatial stack, with a DP accountant pinned alongside the geometry libraries so composition math is reproducible across environments:

Copy
python >= 3.10
numpy == 1.26.*
scipy == 1.11.*        # statistical distances, distributions
geopandas == 0.14.*
shapely == 2.*         # GEOS 3.11+; validity after perturbation
pyproj == 3.*          # PROJ 9.x; project to metres before noise
opacus                 # Rényi DP accountant (Gaussian composition)
scipy.special.lambertw # planar-Laplace inverse-CDF sampling

Two environment invariants dominate the version pins. First, project before you perturb. Every scale and sensitivity below is in metres; run to_crs("EPSG:6933") (equal-area, global) or a local UTM zone before any mechanism touches a coordinate, exactly as the realism metrics evaluation stage expects metric inputs. Second, seed the mechanism RNG from an explicit integer with np.random.default_rng(seed); a mechanism seeded from wall-clock time cannot be replayed for an audit, and reproducibility is itself part of the privacy record.

Core Concept: One Definition, Four Ways to Satisfy It

All four mechanisms target the same definition. A randomized mechanism $\mathcal{M}$ satisfies $(\varepsilon, \delta)$-differential privacy if for all datasets $D, D'$ differing in one record and all output sets $S$,

$$\Pr[\mathcal{M}(D) \in S] \le e^{\varepsilon}\,\Pr[\mathcal{M}(D') \in S] + \delta.$$

When $\delta = 0$ this is pure $\varepsilon$-DP. The mechanisms differ in how they inject the randomness that buys this bound, and in what “one record differs” is measured against.

Laplace answers a numeric query by adding double-exponential noise scaled to the $\ell_1$ sensitivity $\Delta_1 f$ — the maximum change in the answer, in absolute value, from adding or removing one record:

$$b = \frac{\Delta_1 f}{\varepsilon}, \qquad \tilde f = f(D) + \mathrm{Lap}(0, b).$$

It gives pure $\varepsilon$-DP with no $\delta$, which makes it the honest default for aggregate counts, histograms, and density surfaces where the output is a low-dimensional non-negative quantity. Its heavy tails are the cost: a single draw can be large, so per-cell counts in a sparse synthetic density map get noisy fast.

Gaussian adds normal noise scaled to the $\ell_2$ sensitivity, and pays a $\delta > 0$ for the privilege:

$$\sigma = \frac{\Delta_2 f\,\sqrt{2\ln(1.25/\delta)}}{\varepsilon}, \qquad \tilde f = f(D) + \mathcal{N}(0, \sigma^2 I).$$

The $\ell_2$ norm is why Gaussian dominates for high-dimensional coordinate vectors and gradients: when one record moves a whole vector of outputs, $\Delta_2 f$ grows as $\sqrt{k}$ rather than $k$, so the noise per dimension stays bounded. This is exactly the regime of DP-SGD when stabilizing GAN training on coordinates, and it composes tightly under Rényi accounting across the many releases a production generator ships.

Exponential is the odd one out: it privatizes a choice, not a number. Given a candidate set $\mathcal{R}$ and a utility score $u(D, r)$, it samples

$$\Pr[\mathcal{M}(D) = r] \propto \exp\!\left(\frac{\varepsilon\,u(D, r)}{2\,\Delta u}\right),$$

so higher-utility candidates are exponentially more likely, with $\Delta u$ the score’s sensitivity. It is the correct mechanism when the output is inherently discrete — selecting which synthetic zone a point falls in, which land-use category an attribute takes, or which of a finite set of routing endpoints an agent uses — because there is no numeric axis to add noise along without leaking at the rounding boundary.

Planar-Laplace is the spatial specialization, the mechanism behind geo-indistinguishability. Instead of protecting membership in a dataset, it protects a single reported location by guaranteeing that two nearby points produce nearly indistinguishable outputs, with the indistinguishability scaled to their distance:

$$\Pr[\mathcal{M}(x) \in S] \le e^{\varepsilon\, d(x, x')}\,\Pr[\mathcal{M}(x') \in S].$$

Here $\varepsilon$ has units of privacy-per-metre, and a point is obfuscated by adding two-dimensional noise whose radius follows a polar Laplace distribution — draw an angle uniformly and a radius from the inverse CDF, which uses the Lambert-W function. It is the natural fit for location-based services and single-point reporting, and it degrades gracefully: points far apart are still distinguishable, points close together are not, which is precisely the semantics a check-in or a synthetic device ping wants. The coordinate-level calibration of these draws is worked through in implementing differential privacy for coordinate generation.

Decision Framework

The mechanism follows from four questions, answered in order. Each block shows the calibration in code so the decision is concrete rather than rhetorical.

Step 1 — Is the protected output a number, a vector, a choice, or a location? This single question eliminates three of the four options. A scalar count or histogram bin points to Laplace; a coordinate vector or gradient points to Gaussian; a selection from a finite candidate set points to exponential; a single reported point that must stay near its truth points to planar-Laplace.

pythonCopy
def choose_family(output_kind: str) -> str:
    return {
        "scalar_count":   "laplace",       # pure ε, ℓ1
        "histogram":      "laplace",       # per-bin ℓ1
        "coord_vector":   "gaussian",      # ℓ2, composes under RDP
        "gradient":       "gaussian",      # DP-SGD regime
        "discrete_choice":"exponential",   # pick from a candidate set
        "single_point":   "planar_laplace" # geo-indistinguishability
    }[output_kind]

Step 2 — Measure sensitivity in the norm the mechanism requires, in metres. Laplace needs $\Delta_1 f$, Gaussian needs $\Delta_2 f$, exponential needs $\Delta u$. Bounding the wrong norm is the most common silent error.

pythonCopy
import numpy as np

def l1_sensitivity(query_matrix: np.ndarray) -> float:
    # max ℓ1 change from one record: column with the largest absolute mass
    return float(np.max(np.sum(np.abs(query_matrix), axis=0)))

def l2_sensitivity(per_record_vectors: np.ndarray) -> float:
    # max ℓ2 norm of any single record's contribution (metres)
    return float(np.max(np.linalg.norm(per_record_vectors, axis=1)))

Step 3 — Calibrate the noise and draw it from a seeded RNG. The scale is a deterministic function of sensitivity, $\varepsilon$, and (for Gaussian) $\delta$.

pythonCopy
def laplace_noise(value, delta_1, eps, rng):
    b = delta_1 / eps
    return value + rng.laplace(0.0, b, size=np.shape(value))

def gaussian_noise(value, delta_2, eps, delta, rng):
    sigma = delta_2 * np.sqrt(2.0 * np.log(1.25 / delta)) / eps
    return value + rng.normal(0.0, sigma, size=np.shape(value))

def planar_laplace(x, y, eps_per_m, rng):
    from scipy.special import lambertw
    theta = rng.uniform(0.0, 2.0 * np.pi)
    p = rng.uniform(0.0, 1.0)
    # inverse CDF of the radial Laplace; principal (k=-1) branch of W
    r = -1.0 / eps_per_m * (np.real(lambertw((p - 1.0) / np.e, k=-1)) + 1.0)
    return x + r * np.cos(theta), y + r * np.sin(theta)

Step 4 — Pick the composition accountant and choose $\varepsilon$ against the whole release history, not one call. Laplace and exponential compose by summing $\varepsilon_i$ (use advanced composition for many draws); Gaussian must use Rényi DP or zCDP to avoid over-spending. Choosing the number itself is an ongoing accounting problem: a per-release $\varepsilon$ that looks generous can exhaust the standing budget after enough releases, the failure mode dissected in diagnosing epsilon budget exhaustion across releases. As a starting frame: $\varepsilon \le 1$ per release is conservative, $1 < \varepsilon \le 3$ is a common utility-privacy compromise, and $\varepsilon > 10$ provides little meaningful protection regardless of the mechanism.

pythonCopy
from opacus.accountants import RDPAccountant

def gaussian_budget(steps, sample_rate, sigma_noise_multiplier, delta):
    acct = RDPAccountant()
    for _ in range(steps):
        acct.step(noise_multiplier=sigma_noise_multiplier, sample_rate=sample_rate)
    eps = acct.get_epsilon(delta=delta)   # tight composed ε at this δ
    return eps

Validation & Testing

A mechanism choice is only defensible if a gate proves the noise scale matches the claimed $\varepsilon$ and the output stays spatially valid. Three checks belong in CI.

pythonCopy
import numpy as np

def test_laplace_scale_matches_epsilon():
    rng = np.random.default_rng(7)
    delta_1, eps = 4.0, 0.5
    draws = rng.laplace(0.0, delta_1 / eps, size=2_000_000)
    # empirical scale b = mean(|X|); must match Δ1f/ε within tolerance
    assert abs(np.mean(np.abs(draws)) - delta_1 / eps) / (delta_1 / eps) < 0.02

def test_gaussian_sigma_matches_epsilon_delta():
    delta_2, eps, delta = 30.0, 1.0, 1e-6
    sigma = delta_2 * np.sqrt(2.0 * np.log(1.25 / delta)) / eps
    rng = np.random.default_rng(11)
    draws = rng.normal(0.0, sigma, size=2_000_000)
    assert abs(np.std(draws) - sigma) / sigma < 0.02

def test_perturbed_points_stay_in_bounds(points, bounds):
    # planar-Laplace can push a point outside the extent; clip, then re-check
    minx, miny, maxx, maxy = bounds
    assert (points[:, 0] >= minx).all() and (points[:, 0] <= maxx).all()
    assert (points[:, 1] >= miny).all() and (points[:, 1] <= maxy).all()

The empirical-scale tests catch the wrong-norm error directly: if someone wires an $\ell_1$ bound into the Gaussian $\sigma$, the standard deviation no longer matches and the assertion fails. Beyond scale, gate on utility: the perturbed output must still pass the distance-based fidelity checks the realism metrics evaluation stage runs, because a mechanism that protects perfectly but destroys the spatial signal is as useless as one that leaks. The final and non-negotiable check is empirical: no scale test proves a release is safe, so pair every mechanism with the attack suite in adversarial privacy testing before promotion.

Performance & Scale Considerations

Mechanism choice interacts with throughput once a generator runs at continental scale.

• Vectorize the draw. All four mechanisms reduce to a NumPy call over the whole array — rng.laplace, rng.normal, a single Lambert-W evaluation vectorized over points. Never loop in Python per coordinate; the per-object overhead dominates and destroys reproducibility guarantees that depend on draw order.
• Composition cost, not noise cost, is the scaling bottleneck. Adding noise is $O(n)$ and trivial. The expensive resource is the privacy budget: Gaussian under Rényi accounting lets you ship far more releases at a fixed standing $\varepsilon$ than Laplace under basic composition, which is often the deciding factor for a pipeline that regenerates nightly.
• Planar-Laplace needs a clip-and-remap pass. Radial noise can push points outside the extent or across a coastline; budget a bounded post-step that reflects or clips out-of-domain points and re-validates topology, and account for that cost per tile rather than globally.
• Seed derivation must be parallel-safe. Derive each shard’s RNG seed from a base integer and the shard index so concurrent workers produce disjoint, replayable noise streams — the same discipline the CI/CD integration layer relies on to reproduce a release from its manifest.

Failure Modes & Troubleshooting

Frequently Asked Questions

Related

• Privacy-Preserving Generation Frameworks — how to embed the chosen mechanism into a generation DAG with a shared budget ledger.
• Implementing Differential Privacy for Coordinate Generation — the coordinate-level sensitivity derivation and planar-Laplace calibration this comparison assumes.
• Diagnosing Epsilon Budget Exhaustion Across Releases — what goes wrong when composition accounting is neglected over many releases.
• Adversarial Privacy Testing for Synthetic Spatial Data — the empirical falsification that must accompany any mechanism choice.
• Realism Metrics & Evaluation — the utility side of the trade-off each mechanism forces.
• Synthetic Spatial Data Architecture & Fundamentals — the parent reference tying scoping, privacy, and evaluation together.