Calibrating Gaussian Noise for Spatial Aggregate Queries

For an $(\varepsilon, \delta)$-differentially private spatial aggregate — a per-cell count vector — set the Gaussian standard deviation to $\sigma \ge \Delta_2 \sqrt{2 \ln(1.25/\delta)}\,/\,\varepsilon$, where $\Delta_2$ is the L2 sensitivity of the query, then add independent noise to each cell and clamp negatives to zero.

Core Calculation # permalink

The Gaussian mechanism releases $M(D) = f(D) + \mathcal{N}(0, \sigma^2 I)$, adding independent zero-mean Gaussian noise to every component of the vector-valued query $f$. Unlike the Laplace mechanism — which underpins applying Laplace noise to latitude/longitude pairs and calibrates to L1 sensitivity — the Gaussian mechanism calibrates to L2 (Euclidean) sensitivity:

taken over all neighbouring datasets $D, D'$ that differ by one record. The classic calibration theorem states that for $\varepsilon \in (0, 1)$ and $\delta \in (0, 1)$, the mechanism satisfies $(\varepsilon, \delta)$-differential privacy whenever:

Why L2 wins for wide queries # permalink

Consider a histogram where a single user contributes to at most $k$ cells, each by a count of one. Removing that user changes $k$ cells by one:

The Laplace mechanism scales noise with $\Delta_1 = k$; the Gaussian mechanism scales with $\Delta_2 = \sqrt{k}$. For a user who touches $k = 100$ cells, the Gaussian sensitivity is $10\times$ smaller, which is the decisive advantage for high-dimensional spatial releases such as fine-grained hexagon grids.

If a user may contribute more than once per cell, bound it: enforce a contribution cap $c_{\max}$ per user, which fixes $\Delta_2$ regardless of the raw data.

Worked numeric example — an H3 count query # permalink

• Query: number of unique check-ins per H3 resolution-8 cell across a city.
• Contribution cap: each user counted in at most $c_{\max} = 4$ cells, at most once each.
• Privacy budget: $\varepsilon = 0.5$; failure parameter $\delta = 10^{-6}$.

L2 sensitivity of a bounded-contribution count query:

Compute the log term:

So each cell count is released with independent Gaussian noise of standard deviation $\approx 21.2$ counts. A cell whose true count is 3 will frequently be swamped; a cell whose true count is 5,000 is barely affected — the defining property of additive noise on aggregates and the reason low-count cells need suppression.

Python Implementation # permalink

The function below computes $\sigma$ from the calibration theorem and applies it to a vector of cell counts, with a contribution cap and post-processing clamp. The count vector is assumed to come from an H3 hexagon aggregation over data in WGS84 (EPSG:4326), where each element is one resolution-8 cell.

import numpy as np
from numpy.typing import NDArray


def gaussian_sigma(
    l2_sensitivity: float,
    epsilon: float,
    delta: float,
) -> float:
    """
    Standard deviation for the (epsilon, delta)-DP Gaussian mechanism.

    Uses the classic closed form sigma >= Delta2 * sqrt(2 ln(1.25/delta)) / epsilon,
    which is valid only for epsilon in (0, 1]. For larger epsilon use the analytic
    Gaussian mechanism instead.

    Args:
        l2_sensitivity: Delta2, the max Euclidean change in the count vector
            when one user is added or removed (sqrt of the contribution cap
            for a bounded 0/1 count query).
        epsilon: Privacy budget, must be in (0, 1].
        delta: Failure probability, e.g. 1e-6; keep < 1 / number_of_users.

    Returns:
        The per-cell Gaussian standard deviation sigma.
    """
    if not 0 < epsilon <= 1:
        raise ValueError("Closed-form calibration requires 0 < epsilon <= 1.")
    if not 0 < delta < 1:
        raise ValueError("delta must be in (0, 1).")
    return l2_sensitivity * np.sqrt(2.0 * np.log(1.25 / delta)) / epsilon


def privatize_cell_counts(
    counts: NDArray[np.float64],
    epsilon: float,
    delta: float,
    contribution_cap: int = 1,
    seed: int | None = None,
) -> NDArray[np.float64]:
    """
    Release a differentially private version of a spatial cell-count vector.

    Privacy model: each user contributes to at most `contribution_cap` cells,
    at most once per cell, so the L2 sensitivity is sqrt(contribution_cap).
    Callers MUST enforce that cap upstream (e.g. dedupe and truncate per user)
    for the guarantee to hold — the noise calibration assumes it.

    Args:
        counts: Non-negative true counts, one element per grid cell (H3 res-8).
        epsilon: Privacy budget spent on this release, in (0, 1].
        delta: Failure probability.
        contribution_cap: Max cells a single user may influence.
        seed: Optional RNG seed for reproducible tests.

    Returns:
        Noisy, non-negative count vector, same shape as `counts`.
    """
    rng = np.random.default_rng(seed)

    # L2 sensitivity of a capped 0/1 count query = sqrt(cap).
    l2 = np.sqrt(float(contribution_cap))
    sigma = gaussian_sigma(l2, epsilon, delta)

    # Independent Gaussian noise per cell (spherical covariance sigma^2 * I).
    noise = rng.normal(loc=0.0, scale=sigma, size=counts.shape)
    noisy = counts + noise

    # Post-processing: clamp negatives to zero. Post-processing a DP output
    # never weakens the (epsilon, delta) guarantee, but biases sparse cells up.
    return np.maximum(noisy, 0.0)


# --- Example: 2,000 H3 res-8 cells, epsilon = 0.5, delta = 1e-6, cap = 4 ---
true_counts = np.random.default_rng(0).poisson(lam=50, size=2000).astype(float)
released = privatize_cell_counts(
    true_counts, epsilon=0.5, delta=1e-6, contribution_cap=4, seed=7
)
print("sigma =", round(gaussian_sigma(np.sqrt(4), 0.5, 1e-6), 2))  # ~21.20

Key decisions:

• Contribution cap sets sensitivity. contribution_cap is the single most important privacy knob: it must be enforced upstream (deduplicate and truncate each user’s cells) so the assumed $\Delta_2 = \sqrt{c_{\max}}$ is real. Without the cap, a heavy user could blow the sensitivity and void the guarantee.
• Spherical noise. Independent per-cell draws implement $\mathcal{N}(0, \sigma^2 I)$, which is what the L2 calibration assumes.
• Clamp as post-processing. Negative counts are meaningless; clamping is safe under the post-processing property but introduces a small upward bias in sparse regions.

Verification # permalink

Confirm empirically that the injected per-cell noise matches the theoretical $\sigma$ and that the aggregate error is consistent with the calibration:

import numpy as np

def verify_gaussian_calibration(
    epsilon: float = 0.5,
    delta: float = 1e-6,
    contribution_cap: int = 4,
    n_cells: int = 5000,
    trials: int = 400,
) -> dict:
    """Monte Carlo check that empirical noise sd ~ theoretical sigma."""
    l2 = np.sqrt(contribution_cap)
    sigma = gaussian_sigma(l2, epsilon, delta)

    rng = np.random.default_rng(123)
    true_counts = rng.poisson(50, size=n_cells).astype(float)

    # Measure per-cell error before clamping to isolate the raw mechanism.
    errors = []
    for _ in range(trials):
        noise = rng.normal(0.0, sigma, size=n_cells)
        errors.append(noise)
    errors = np.asarray(errors)

    empirical_sd = errors.std()
    theoretical_rmse = sigma  # E[error^2]^0.5 per cell equals sigma
    ratio = empirical_sd / sigma
    assert 0.95 < ratio < 1.05, f"noise sd off: ratio={ratio:.3f}"

    return {
        "theoretical_sigma": round(sigma, 3),
        "empirical_noise_sd": round(empirical_sd, 3),
        "theoretical_per_cell_rmse": round(theoretical_rmse, 3),
        "ratio": round(ratio, 4),
    }

print(verify_gaussian_calibration())
# {'theoretical_sigma': 21.196, 'empirical_noise_sd': ~21.19,
#  'theoretical_per_cell_rmse': 21.196, 'ratio': ~1.000}

The empirical standard deviation of the injected noise should sit within a few percent of $\sigma$, and the per-cell RMSE equals $\sigma$ by construction because the Gaussian error has zero mean. If the empirical value is systematically higher, the contribution cap is not being enforced and $\Delta_2$ is wrong.

Edge Cases & Adjustments # permalink

• Sparse / low-count cells. Cells with true counts below roughly $3\sigma$ are dominated by noise and, after clamping, biased upward. Suppress cells whose noisy count falls under a released threshold, or aggregate to a coarser grid resolution before adding noise so counts are large relative to $\sigma$.
• Epsilon above one. The closed form is only valid for $\varepsilon \le 1$. For larger budgets use the analytic Gaussian mechanism (numerical inversion of the exact privacy-loss integral), which yields a smaller, correct $\sigma$.
• Composition across queries. Releasing several noisy aggregates from the same data spends privacy budget (ε) cumulatively. The Gaussian mechanism composes cleanly under zero-concentrated DP: convert each release to a $\rho$ value, sum the $\rho$, then convert back to $(\varepsilon, \delta)$ for a far tighter bound than naive summation.
• Unbounded per-cell contribution. If a user can appear many times in one cell (repeated pings), a 0/1 count is not enough — cap per-user per-cell contribution or switch to a bounded-sum query whose $\Delta_2$ reflects the value range, not just the cell count.

FAQ # permalink

When does Gaussian noise beat Laplace for spatial aggregates?

When a single record influences many output cells simultaneously. The Laplace mechanism scales with L1 sensitivity, which grows linearly in the number of touched cells $k$, while the Gaussian mechanism scales with L2 sensitivity, which grows as $\sqrt{k}$. For a wide histogram query where one user spans dozens of hexagons, Gaussian injects dramatically less total noise. The trade-off is that Gaussian only achieves the relaxed $(\varepsilon, \delta)$ guarantee, not pure $\varepsilon$-differential privacy — so it is the right default for multi-cell aggregate releases but not for single scalar queries where Laplace’s cleaner guarantee is preferable.

How should I choose delta for a spatial count release?

Keep $\delta$ well below $1/n$, where $n$ is the number of contributing users, so the probability of a total privacy failure is negligible relative to the population. Values of $10^{-5}$ to $10^{-7}$ are typical. Because $\delta$ enters through $\ln(1.25/\delta)$, tightening it by a factor of ten raises $\sigma$ by only a small amount — cheap insurance.

Why clamp negative noisy counts to zero?

Gaussian noise is symmetric and unbounded, so empty or low-count cells frequently receive negative values that are nonsensical as counts. Clamping is a post-processing operation, and post-processing a differentially private release cannot degrade its guarantee. Document the resulting small positive bias in sparse regions when you report utility.

Does the classic sigma formula hold at high epsilon?

No. The closed form $\sigma \ge \Delta_2 \sqrt{2\ln(1.25/\delta)}/\varepsilon$ is derived under $\varepsilon \le 1$ and becomes loose or invalid beyond that. For $\varepsilon > 1$, use the analytic Gaussian mechanism, which numerically inverts the exact privacy-loss condition and returns the smallest correct $\sigma$.

Related

• Laplace & Gaussian Noise for Coordinate Data — parent guide comparing both mechanisms and their sensitivity models
• Applying Laplace Noise to Latitude/Longitude Pairs — the L1-calibrated counterpart for point coordinates
• Privacy Budget Allocation for Spatial Queries — tracking and composing ε across multiple releases
• Accuracy vs. Utility Tradeoffs in Geospatial DP — how much spatial signal survives calibrated noise
• Grid Aggregation & Spatial Binning Strategies — building the count vector before noise is added

← Back to Laplace & Gaussian Noise for Coordinate Data