Spatial Epi Public Health GIS

Allocating a Privacy Budget Across Nested Geographies

Releasing counts at state, county, and tract level from the same individuals is not three independent releases — the privacy loss composes, and spending a full epsilon at each level over-discloses. This guide, part of Differential Privacy for Spatial Aggregates, shows how to split one total budget across the hierarchy, add noise per level, and reconcile child counts to their parent while accounting for every unit of epsilon spent.

Problem Context & Constraints

The naive approach treats each geographic level as its own project: run the Laplace mechanism at ε=1\varepsilon = 1 on the state totals, then again at ε=1\varepsilon = 1 on the counties, then again on the tracts, and publish all three. It feels safe because each table individually satisfies ε=1\varepsilon = 1. It is not safe, because all three tables describe the same people. Under differential privacy, answering multiple queries about one population accumulates privacy loss, so the combined release does not satisfy ε=1\varepsilon = 1 — it satisfies ε=3\varepsilon = 3, three times the exposure the policy authorized. An attacker who holds all three levels gets the benefit of all three noisy views to triangulate an individual.

Three constraints make nested releases distinct from the single-level recipe:

  • Levels are not disjoint partitions, so composition is sequential, not parallel. A single choropleth of non-overlapping tracts is parallel composition — each person sits in exactly one tract, so the whole map costs only one ε\varepsilon. But a hierarchy re-uses each person at every level (they are in one tract, one county, and one state), so the levels stack under sequential composition and their budgets add.
  • The total is fixed; the split is the design decision. You do not get to spend the policy budget three times. You get one total, and the engineering task is dividing it across levels to match where accuracy matters — usually more to the coarse levels that anchor totals, less to the noisy fine levels, or the reverse if tract detail is the product.
  • Independent noisy levels will not agree. Add noise separately to a state total and to its tracts and the tracts will not sum to the state. A released hierarchy that is internally inconsistent is both confusing to users and a subtle information leak, so the levels must be reconciled — as post-processing, using only the noisy values.

The budget flows down the hierarchy while consistency is enforced back up it:

Splitting a Privacy Budget Across a Nested Geography On the left, a horizontal budget bar divides a total epsilon into three segments: a state share, a county share, and a tract share, whose sum equals the total. On the right, a tree shows a state node at the top branching to two county nodes and then to four tract nodes; solid arrows carry the budget allocation downward while a dashed arrow carries consistency reconciliation, children summing to parent, back upward as post-processing. One total budget is split across levels — the split, not the total, is the design decision Total budget ε ε s ε c ε t ε s + ε c + ε t = ε each level debits the shared budget State spends ε s County ε c share County ε c share Tract Tract Tract Tract Σ = parent solid: budget allocated down under sequential composition dashed: noisy children reconciled to sum to parent (post-processing) Spend the budget once across levels, then make the noisy hierarchy self-consistent for free

Prerequisites

Pin the stack so per-level seeds and the accounting reproduce across reviewers:

  • python 3.11
  • numpy 1.26.4 — per-level Laplace draws and the consistency arithmetic
  • geopandas 0.14.4 (pulls shapely 2.0.x, pyproj 3.6.x) — the tract layer carrying a geoid plus parent county_geoid and state_geoid keys

Input state assumed by the code below:

  • A tract GeoDataFrame whose rows already carry their parent identifiers, so children can be grouped under each parent deterministically. The true counts roll up exactly — tract counts sum to their county, counties to their state — before any noise is added.
  • A single total budget εtotal\varepsilon_{\text{total}} set by policy, and a chosen split across levels. The per-level mechanism itself is the seeded Laplace draw described in adding Laplace noise to census-tract case counts; this guide adds the accounting and reconciliation around it.

Step-by-Step Solution

Sequential composition is the theorem that governs the split. If mechanisms M1,…,Mk\mathcal{M}_1, \dots, \mathcal{M}_k run on the same dataset with budgets ε1,…,εk\varepsilon_1, \dots, \varepsilon_k, their combined release satisfies differential privacy with

εtotal=∑i=1kεi.\varepsilon_{\text{total}} = \sum_{i=1}^{k} \varepsilon_i.

So a three-level hierarchy must satisfy εs+εc+εt≤εtotal\varepsilon_s + \varepsilon_c + \varepsilon_t \le \varepsilon_{\text{total}}, and the split is where you encode which levels deserve accuracy. At each level ℓ\ell the Laplace scale is 1/εℓ1/\varepsilon_\ell, so a level that receives a larger share gets less noise. The routine below allocates the budget by weights, draws seeded noise per level, and logs the per-level epsilon against the total.

# Allocate a total epsilon across nested levels and add per-level Laplace noise.
# python 3.11
# numpy==1.26.4, geopandas==0.14.4
import json
import logging
import numpy as np
import geopandas as gpd

logging.basicConfig(level=logging.INFO, format="%(asctime)s %(levelname)s %(message)s")
log = logging.getLogger("dp.hierarchy")

def split_budget(epsilon_total: float, weights: dict[str, float]) -> dict[str, float]:
    """Divide a total epsilon across levels in proportion to weights."""
    w_sum = sum(weights.values())
    alloc = {level: epsilon_total * w / w_sum for level, w in weights.items()}
    # Sequential composition: the parts must sum to the whole (within fp error).
    assert abs(sum(alloc.values()) - epsilon_total) < 1e-9, "budget split must sum to total"
    log.info("budget split: total=%.3f alloc=%s", epsilon_total,
             json.dumps({k: round(v, 4) for k, v in alloc.items()}))
    return alloc

def noisy_level(values: np.ndarray, epsilon_level: float, seed: int) -> np.ndarray:
    """Laplace(0, 1/epsilon_level) on a count vector (sensitivity = 1)."""
    rng = np.random.default_rng(seed)          # per-level seed, logged in provenance
    return values + rng.laplace(0.0, 1.0 / epsilon_level, size=values.size)

With the budget split and per-level noise in hand, the noisy levels are reconciled from the top down so children sum to their parent. A simple, defensible reconciliation distributes each parent’s discrepancy equally across its noisy children — an operation that reads only the noisy values and therefore adds no privacy cost:

def reconcile_children(parent_val: float, child_vals: np.ndarray) -> np.ndarray:
    """Adjust noisy children so they sum to the (noisy) parent. Post-processing only."""
    gap = parent_val - child_vals.sum()
    adjusted = child_vals + gap / child_vals.size   # equal additive redistribution
    return np.clip(adjusted, 0.0, None)             # non-negativity after reconciliation

def release_hierarchy(gdf: gpd.GeoDataFrame, epsilon_total: float,
                      weights: dict[str, float], base_seed: int = 20260713):
    alloc = split_budget(epsilon_total, weights)

    # True roll-ups (assumed exact in the input).
    state = gdf.groupby("state_geoid")["case_count"].sum()
    county = gdf.groupby("county_geoid")["case_count"].sum()
    tract = gdf.set_index("geoid")["case_count"]

    # Independent seeded noise per level.
    dp_state = noisy_level(state.to_numpy(float), alloc["state"], base_seed + 1)
    dp_county = noisy_level(county.to_numpy(float), alloc["county"], base_seed + 2)
    dp_tract = noisy_level(tract.to_numpy(float), alloc["tract"], base_seed + 3)

    state_dp = dict(zip(state.index, dp_state))
    county_dp = dict(zip(county.index, dp_county))

    # Reconcile counties to their state, then tracts to their county (top-down).
    for s_id, s_val in state_dp.items():
        kids = county[county.index.isin(
            gdf.loc[gdf.state_geoid == s_id, "county_geoid"].unique())].index
        adj = reconcile_children(s_val, np.array([county_dp[k] for k in kids]))
        county_dp.update(dict(zip(kids, adj)))

    provenance = {"epsilon_total": epsilon_total, "per_level": alloc,
                  "seeds": {"state": base_seed + 1, "county": base_seed + 2,
                            "tract": base_seed + 3}}
    log.info("hierarchy release provenance: %s", json.dumps(provenance))
    return state_dp, county_dp, dp_tract, provenance

The order matters: reconcile from the top down so each level is snapped to an already-finalized parent, never to a moving target. The state totals are fixed first, counties are pulled to sum to their state, and tracts are pulled to sum to their reconciled county.

Validation & Edge Cases

Two invariants must hold on every run, and both are cheap to assert.

1. The spent budget equals the total. The single most common error is a split that quietly sums to more than the policy budget — a fourth level added later, or a weight typo. Assert it directly and refuse to release otherwise:

def assert_budget(alloc: dict[str, float], epsilon_total: float, tol: float = 1e-9):
    spent = sum(alloc.values())
    if spent > epsilon_total + tol:
        raise ValueError(f"budget overrun: spent={spent} > total={epsilon_total}")
    log.info("budget check ok: spent=%.4f of %.4f", spent, epsilon_total)
INFO budget check ok: spent=1.0000 of 1.0000

2. Children sum to their parent after reconciliation. Verify consistency on the released numbers, not the intermediate noisy ones:

def assert_consistency(parent_val, child_vals, tol=0.5):
    if abs(parent_val - sum(child_vals)) > tol:
        raise ValueError("children do not sum to parent after reconciliation")

Beyond the invariants, three edge cases recur. First, rounding breaks exact consistency: if each level is rounded to integers independently after reconciliation, the sums drift by a unit or two. Round the parent first, then use a largest-remainder allocation so integer children still sum exactly. Second, a thin split starves the fine level: giving tracts a tiny εt\varepsilon_t makes their noise scale 1/εt1/\varepsilon_t enormous, and reconciliation cannot rescue a level that is almost pure noise — if tract detail is the product, weight it accordingly, or coarsen the geography as adaptive areal aggregation for rare disease counts describes. Third, negative reconciled children: additive redistribution can push a small child below zero, so clamp after reconciliation and log how often it happens as a bias diagnostic, mirroring the clamp accounting a paired dasymetric population suppression denominator layer would carry.

Compliance Notes

A nested release is defensible only if the accounting is explicit and enforced, not merely intended:

  • Per-level epsilon and the running total. Log each level’s εℓ\varepsilon_\ell and the sum against the policy budget, and enforce the sum programmatically so a release that would overrun is refused. Under sequential composition the total is the binding guarantee — the individual levels are not.
  • Per-level seeds, held privately. Each level draws from its own seeded generator; store the seeds in the access-controlled provenance record so the whole hierarchy reproduces for audit while staying secret before release. This is the same secret-but-reproducible discipline the parent guide requires, applied per level.
  • The reconciliation rule. Record which consistency method was used and confirm it touched only noisy values, so a reviewer can verify the post-processing theorem still holds and the released hierarchy is both internally consistent and genuinely private. The boundary and CRS vintage the counts are keyed to should be frozen exactly as coordinate reference systems for public health prescribes, so parent-child roll-ups are unambiguous.