Utility Benchmarks for Privatized Heatmaps

A heatmap is not a table of counts that happens to be coloured — it is a ranking rendered as a colour ramp, and people read it by comparing regions to each other rather than by reading values. That difference decides which benchmarks are meaningful. A privatized heatmap can be badly wrong cell by cell and perfectly right as a map, or numerically tight and visually misleading, and only a ranking-aware benchmark separates the two. This guide defines the benchmark suite, sitting under privacy–utility trade-off measurement in Core Fundamentals & Architecture for Spatial Privacy; the rendering pipeline it benchmarks is described in building differentially private heatmaps.

Parameter Configuration and Calibration

Four knobs decide what the benchmark measures, and each maps to something a viewer perceives.

• k — the hotspot list length. The single most important benchmark parameter, because it encodes how the map is read. If operations act on “the top 10 cells”, benchmark at $k = 10$; if the map is scanned for general structure, $k = 100$ is closer to the truth. Benchmark at least two values — short lists are far more fragile than long ones, and a suite that only reports $k = 100$ will pass releases that reorder the visible peak.
• n_bins — the colour-ramp quantisation. Viewers do not perceive counts, they perceive the band a cell was assigned. A release that moves a cell by 300 counts within one band is visually identical; one that moves it 20 counts across a band boundary is visibly different. Benchmark agreement after quantisation into the same bins the renderer uses, typically 5–7.
• smoothing_radius — the kernel applied before rendering. Most heatmaps are kernel-smoothed, and smoothing is post-processing: free in budget and a genuine noise reducer, since it averages independent draws over neighbouring cells. Benchmark with smoothing on, exactly as rendered, or the numbers will understate the release badly.
• report_floor — the count below which a cell is rendered as empty. Whether a sparse cell shows as “no data” or as “low” changes both the map and the benchmark. Fix it, state it, and hold it constant across the sweep.

Reference Implementation

from __future__ import annotations

from dataclasses import dataclass
from typing import Sequence

import numpy as np
from scipy.stats import spearmanr


@dataclass(frozen=True)
class HeatmapBenchmark:
    """One release measured against the unprotected truth."""

    topk_overlap: dict[int, float]
    band_agreement: float
    spearman_rho: float
    empty_agreement: float
    n_draws: int


def _quantise(values: np.ndarray, edges: np.ndarray) -> np.ndarray:
    """Assign each cell to the colour band the renderer would give it."""
    return np.digitize(values, edges)


def _smooth(grid: np.ndarray, neighbours: Sequence[np.ndarray], weight: float) -> np.ndarray:
    """One pass of neighbour averaging — the post-processing the renderer applies.

    `neighbours[i]` holds the indices adjacent to cell i. Smoothing is free under
    differential privacy (it touches only released values) and reduces variance by
    averaging independent noise draws, so benchmarks must run with it enabled.
    """
    out = grid.copy()
    for i, nbrs in enumerate(neighbours):
        if len(nbrs):
            out[i] = (1 - weight) * grid[i] + weight * float(np.mean(grid[nbrs]))
    return out


def benchmark_heatmap(
    truth: np.ndarray,
    neighbours: Sequence[np.ndarray],
    *,
    epsilon: float,
    ks: Sequence[int] = (10, 50),
    n_bins: int = 6,
    smoothing: float = 0.35,
    report_floor: float = 25.0,
    draws: int = 40,
    seed: int = 5,
) -> HeatmapBenchmark:
    """Benchmark a privatized heatmap the way a viewer reads it."""
    rng = np.random.default_rng(seed)
    scale = 1.0 / epsilon

    # Band edges come from the TRUE distribution, because the legend is fixed by
    # the product design and does not move release to release.
    edges = np.quantile(truth[truth >= report_floor], np.linspace(0, 1, n_bins + 1)[1:-1])
    true_bands = _quantise(truth, edges)
    true_empty = truth < report_floor
    true_rank_order = np.argsort(-truth)
    true_tops = {k: set(true_rank_order[:k].tolist()) for k in ks}

    overlaps = {k: [] for k in ks}
    bands, rhos, empties = [], [], []

    for _ in range(draws):
        noisy = np.maximum(truth + rng.laplace(0.0, scale, size=truth.shape), 0.0)
        rendered = _smooth(noisy, neighbours, smoothing)

        order = np.argsort(-rendered)
        for k in ks:
            overlaps[k].append(len(true_tops[k] & set(order[:k].tolist())) / k)
        bands.append(float(np.mean(_quantise(rendered, edges) == true_bands)))
        rhos.append(float(spearmanr(truth, rendered).statistic))
        empties.append(float(np.mean((rendered < report_floor) == true_empty)))

    return HeatmapBenchmark(
        topk_overlap={k: float(np.mean(v)) for k, v in overlaps.items()},
        band_agreement=float(np.mean(bands)),
        spearman_rho=float(np.mean(rhos)),
        empty_agreement=float(np.mean(empties)),
        n_draws=draws,
    )

Validation Checkpoint

def _validate() -> None:
    rng = np.random.default_rng(19)
    n = 900
    truth = np.clip(rng.lognormal(4.6, 1.0, size=n), 0, None)
    # A ring lattice stands in for hex adjacency in the test.
    neighbours = [np.array([(i - 1) % n, (i + 1) % n]) for i in range(n)]

    loose = benchmark_heatmap(truth, neighbours, epsilon=0.25)
    tight = benchmark_heatmap(truth, neighbours, epsilon=4.0)

    # 1. Every benchmark must improve monotonically with budget.
    assert tight.topk_overlap[10] >= loose.topk_overlap[10]
    assert tight.band_agreement >= loose.band_agreement
    assert tight.spearman_rho >= loose.spearman_rho

    # 2. Long lists are more robust than short ones at the same budget.
    assert loose.topk_overlap[50] > loose.topk_overlap[10]

    # 3. Smoothing must not make the benchmark worse on a smooth field.
    unsmoothed = benchmark_heatmap(truth, neighbours, epsilon=1.0, smoothing=0.0)
    smoothed = benchmark_heatmap(truth, neighbours, epsilon=1.0, smoothing=0.35)
    assert smoothed.spearman_rho >= unsmoothed.spearman_rho - 0.02

    # 4. At a generous budget the ordering is essentially preserved.
    assert tight.spearman_rho > 0.98

    print("heatmap benchmarks: all assertions passed")


_validate()

Assertion 2 is the finding that most often changes a product decision. If the map’s job is “show where the busy areas are”, a $k$ of 50 at $\varepsilon = 0.5$ often outperforms a $k$ of 10 at $\varepsilon = 2$ — the cheaper release satisfies the actual task, and the difference is budget the pipeline keeps for something else.

Incident Response and Edge Cases

• The map looks speckled where the truth is smooth. Independent per-cell noise with no smoothing. Turn on the kernel and re-benchmark before touching $\varepsilon$; smoothing is free and often recovers the entire visual loss.
• A hotspot appears in an area with no activity. The clamp-to-zero estimator is one-sided, so sparse regions drift upward, and smoothing spreads that drift into a plausible-looking blob. Raise the report_floor so those cells render as “no data” rather than as low activity, and check the empty-cell agreement benchmark, which is the one designed to catch this.
• Band agreement is poor while Spearman ρ is excellent. The ordering survived but cells are sitting near legend boundaries. Re-derive the band edges on a wider quantile spacing, or use a perceptually coarser legend; this is a rendering fix, not a privacy one.
• Benchmarks pass but the map changes visibly week to week. Each release draws fresh noise, so the difference between releases is twice the noise of one. If viewers compare consecutive maps, benchmark that comparison too, and consider publishing a smoothed rolling release rather than an independent draw per period.
• The legend moves between releases. Then no cross-release comparison means anything. Fix the band edges once from a long historical baseline and keep them until a deliberate, announced change.

A final note on presentation, which is part of utility whether or not anyone measures it. A privatized heatmap should carry its parameters and its uncertainty on the face of the map, not in a methodology appendix: the epsilon, the cell resolution, the reporting floor, and a one-line statement that cells below the floor render as no-data rather than as zero. Viewers who know the map is noisy read it correctly; viewers who do not will read a suppressed rural region as an empty one, which is a failure of the release rather than of the reader.

Frequently Asked Questions

Related

• Privacy–Utility Trade-off Measurement — the parent method.
• Building Differentially Private Heatmaps — the pipeline under benchmark.
• Measuring Spatial Query Error Under Differential Privacy — the count-oriented counterpart to these ranking benchmarks.
• Private Quadtree Spatial Histograms — an adaptive alternative to the uniform grid benchmarked here.

Up one level: Privacy–Utility Trade-off Measurement · Section: Core Fundamentals & Architecture for Spatial Privacy.