Measuring Utility Loss in Differentially Private Heatmaps

Quantify heatmap degradation with a small suite of complementary metrics — MAE and RMSE for cell-count magnitude, Spearman rank correlation and top-$k$ overlap for hotspot structure, KL divergence for distribution shape, and Moran’s I preservation for spatial autocorrelation — each checked against an explicit threshold.

Core Calculation # permalink

A differentially private heatmap replaces each true cell count $t_i$ with a noisy count $n_i$. Utility loss is not one number: magnitude error, rank structure, and spatial structure fail independently, so measure all three.

Magnitude error. Root mean squared error penalises large per-cell deviations:

For the Gaussian mechanism with per-cell standard deviation $\sigma$, the expected RMSE is exactly $\sigma$, giving a theoretical baseline to compare against.

Rank / hotspot structure. Spearman’s rank correlation $\rho_s$ is Pearson correlation on the rank-transformed counts:

where $d_i$ is the difference in rank of cell $i$ between the true and noisy grids. The top-$k$ overlap is the Jaccard-style fraction of shared cells among the $k$ highest-count cells:

with $T_k, N_k$ the top-$k$ cell sets of the true and noisy grids.

Distributional divergence. Normalise each grid to a probability distribution $p_i = t_i / \sum t$, $q_i = n_i / \sum n$, and compute the Kullback–Leibler divergence:

Spatial autocorrelation. Track global Moran’s I before and after masking; the dedicated method is covered in computing Moran’s I on masked spatial data.

Worked numeric example # permalink

A 3-cell toy grid, true counts $t = (100, 40, 10)$, noisy counts $n = (108, 35, 18)$:

Ranks are unchanged (both order cell 1 > cell 2 > cell 3), so $\sum d_i^2 = 0$ and $\rho_s = 1.0$. The top-1 hotspot (cell 1) survives, so $\text{overlap}_1 = 1.0$. Normalising: $p = (0.667, 0.267, 0.067)$, $q = (0.671, 0.217, 0.112)$, giving $D_{\mathrm{KL}}(p \parallel q) \approx 0.667\ln\frac{0.667}{0.671} + 0.267\ln\frac{0.267}{0.217} + 0.067\ln\frac{0.067}{0.112} \approx 0.015$ nats — a low, healthy divergence. Magnitude moved but structure held: exactly the distinction the suite exists to expose.

Python Implementation # permalink

The suite below takes aligned true and noisy grids (same cell ordering, same CRS — here EPSG:3857 web-Mercator tiles) and returns every metric plus a pass/fail verdict against thresholds.

import numpy as np
from numpy.typing import NDArray
from scipy.stats import spearmanr, entropy


def heatmap_utility_metrics(
    true_grid: NDArray[np.float64],
    noisy_grid: NDArray[np.float64],
    top_k: int = 10,
    eps_smoothing: float = 1e-9,
) -> dict:
    """
    Quantify utility loss between a true and a differentially private heatmap.

    Both grids must share the same cell ordering and coordinate reference
    system (e.g. EPSG:3857 tiles). Privacy note: only the noisy_grid is ever
    released; true_grid is used internally for offline utility evaluation and
    must not be published, since it would reveal the raw counts the DP
    mechanism was meant to protect.

    Args:
        true_grid: Flattened true cell counts, non-negative.
        noisy_grid: Flattened DP cell counts (may be clamped at 0).
        top_k: Number of highest cells to compare for hotspot overlap.
        eps_smoothing: Additive smoothing so KL divergence stays finite
            when a cell is zero in one grid.

    Returns:
        Dict of metric name -> value.
    """
    t = np.asarray(true_grid, dtype=float).ravel()
    n = np.asarray(noisy_grid, dtype=float).ravel()
    if t.shape != n.shape:
        raise ValueError("Grids must have identical shape and cell ordering.")

    # --- Magnitude error ---
    diff = n - t
    mae = np.mean(np.abs(diff))
    rmse = np.sqrt(np.mean(diff ** 2))

    # --- Rank / hotspot structure ---
    rho_s, _ = spearmanr(t, n)  # rank correlation across all cells
    true_top = set(np.argsort(t)[::-1][:top_k])
    noisy_top = set(np.argsort(n)[::-1][:top_k])
    top_k_overlap = len(true_top & noisy_top) / top_k

    # --- Distributional divergence (normalise to probability vectors) ---
    p = t + eps_smoothing
    q = n + eps_smoothing
    p /= p.sum()
    q /= q.sum()
    kl = float(entropy(p, q))  # KL(p || q) in nats

    return {
        "mae": round(float(mae), 3),
        "rmse": round(float(rmse), 3),
        "spearman_rho": round(float(rho_s), 4),
        "top_k_overlap": round(float(top_k_overlap), 3),
        "kl_divergence": round(kl, 5),
    }


# --- Example: 40x40 grid, Gaussian DP noise sigma = 21.2 (epsilon = 0.5) ---
rng = np.random.default_rng(0)
true_grid = rng.poisson(lam=60, size=1600).astype(float)
noisy_grid = np.maximum(true_grid + rng.normal(0, 21.2, size=1600), 0.0)
print(heatmap_utility_metrics(true_grid, noisy_grid, top_k=10))

Key decisions: the true grid is evaluation-only and must never be released; KL divergence uses additive smoothing so zero cells do not produce infinities; and spearmanr operates on ranks so it is insensitive to the absolute noise scale — isolating structural loss from magnitude loss.

Verification checklist # permalink

Confirm the private heatmap meets utility targets before publishing:

def passes_utility_gate(metrics: dict, mean_true_count: float) -> dict:
    """Check each metric against its threshold; return per-check booleans."""
    checks = {
        "rmse_reasonable": metrics["rmse"] <= 0.5 * mean_true_count,
        "rank_preserved": metrics["spearman_rho"] >= 0.8,
        "hotspots_survive": metrics["top_k_overlap"] >= 0.8,
        "distribution_close": metrics["kl_divergence"] <= 0.05,
    }
    checks["all_passed"] = all(checks.values())
    return checks

• RMSE close to the theoretical $\sigma$ RMSE close to the theoretical $\sigma$ and small relative to the mean cell count.
• Spearman $\rho_s \ge 0.8$ Spearman $\rho_s \ge 0.8$ (rank order of cells preserved).
• Top-$k$ overlap $\ge 0.8$ Top-$k$ overlap $\ge 0.8$ (at least 8 of the top 10 hotspots survive).
• KL divergence $\le 0.05$ KL divergence $\le 0.05$ nats (distribution shape intact).
• Moran’s I within $\pm 10\%$ Moran's I within $\pm 10\%$ of the true grid (spatial clustering preserved).

If any check fails, raise the privacy budget (ε) or coarsen the grid so counts are larger relative to the noise.

Edge Cases & Adjustments # permalink

• Sparse grids dominated by zeros. When most cells are empty, RMSE looks tiny yet the hotspot overlap can still collapse. Weight your judgment toward top-$k$ overlap and Spearman correlation, or restrict metrics to cells above a minimum true count.
• Clamping bias. Clamping negative noisy counts to zero inflates sparse-cell totals, biasing KL divergence and the grid sum. Normalise consistently and report the clamped fraction alongside the metrics.
• Grid resolution mismatch. Utility depends heavily on cell size; a map that fails at fine resolution often passes when aggregated coarser. Evaluate at the resolution you will actually publish, and re-derive the accuracy vs. utility tradeoff at each candidate resolution.
• Rank ties in flat regions. Large uniform low-count areas create many tied ranks, destabilising Spearman correlation. Break ties deterministically or exclude the flat background before computing rank metrics.

FAQ # permalink

Which single metric best captures heatmap utility loss?

None — magnitude error and structural error are distinct failure modes. RMSE measures how far each cell moved but says nothing about whether hotspots are still ranked correctly; Spearman correlation and top-$k$ overlap measure hotspot survival but ignore absolute scale; KL divergence and Moran’s I capture distribution and clustering. Always report at least one metric from each family.

What is a reasonable top-k overlap threshold for a hotspot map?

For operational use, target top-$k$ overlap $\ge 0.8$ for $k$ around 10–20 — at least 8 of the top 10 hotspots preserved. Below roughly 0.6 the map can no longer be trusted to show where activity concentrates, and you should increase $\varepsilon$ or coarsen the grid.

Why measure Moran’s I on a private heatmap?

Moran’s I measures spatial autocorrelation — whether neighbouring cells hold similar values. Independent per-cell noise attacks exactly that structure, so a sharp drop in Moran’s I reveals lost clustering even when per-cell error looks fine. Keeping it within about 10% of the true value confirms the spatial pattern survived; see computing Moran’s I on masked spatial data for the procedure.

How does epsilon affect these metrics?

Lower $\varepsilon$ means larger noise: MAE and RMSE rise, Spearman correlation and top-$k$ overlap fall, and KL divergence grows. Running the suite across candidate $\varepsilon$ values turns the privacy-utility tradeoff into a measurable search for the smallest budget that still clears every threshold.

Related

• Accuracy vs. Utility Tradeoffs in Geospatial DP — parent guide framing the privacy-utility balance
• Utility-Preservation Metrics for Masked Maps — the broader metric family this suite belongs to
• Computing Moran’s I on Masked Spatial Data — the spatial-autocorrelation check referenced above
• Calibrating Gaussian Noise for Spatial Aggregate Queries — where the per-cell σ these metrics react to comes from
• Privacy Budget Allocation for Spatial Queries — tuning ε to hit the thresholds above

← Back to Accuracy vs. Utility Tradeoffs in Geospatial DP