Applying Complementary Suppression to Choropleth Maps

Withholding the sub-threshold polygons is step one of three. Step two is suppressing enough additional polygons that no published total is left with a single unknown, and step three is proving it by solving the system a reader could solve. Skipping step three is how primary suppression ships with the withheld values recoverable.

Core Calculation permalink

A choropleth release publishes a value $n_c$ per polygon and, almost always, a set of totals. Each total is an equation

\sum_{c \in L} n_c = T_L

Let $S$ be the set of suppressed polygons. The safety condition is that no equation contains exactly one member of $S$ :

\bigl|\,S \cap L\,\bigr| \ne 1 \quad \text{for every } L \in \mathcal{L}

Satisfying it is necessary and not sufficient, because several equations together can pin a value even when each holds two unknowns. The sufficient test bounds each withheld value by linear programming over the published system:

n_c^{\min} = \min\{\, n_c \mid An = T,\ n \ge 0 \,\}, \qquad n_c^{\max} = \max\{\, \cdot \,\}

and requires $n_c^{\max} - n_c^{\min} \ge p$ for the declared protection level $p$ .

Worked numeric example permalink

Six wards nested in two districts, cycling counts, $k = 20$ , $p = 10$ :

Ward	Count	District
A	84	North
B	12	North
C	61	North
D	9	South
E	47	South
F	38	South

Primary suppression withholds B (12) and D (9). North’s total of 157 leaves one unknown — B is recoverable as $157 - 84 - 61$ . South’s total of 94 likewise gives D. Suppressing one more ward in each district closes both equations; picking the smallest, C (61) and F (38), yields intervals: B lies in $[0, 73]$ and D in $[0, 47]$ , both far wider than $p = 10$ .

The cost is that two large, uninteresting wards are now missing from the map. Choosing A and E instead would give the same safety and remove the two most-populated wards, which is worse cartographically for identical privacy — the objective function matters.

Complements are always chosen from published cells, so the cost is real. The greedy rule minimises suppressed count; a cartographic release may prefer to minimise suppressed area or visual disruption instead.

Python Implementation permalink

from __future__ import annotations

import numpy as np
import pandas as pd
from scipy.optimize import linprog

def complementary_suppress(
    cells: pd.DataFrame,
    groups: list[list[str]],
    k: int,
    protection: int,
    cost_col: str = "n_persons",
) -> dict:
    """Primary + complementary suppression for a choropleth release.

    `groups` must list every published total as a set of cell ids — including
    hierarchy levels published separately and totals added for reader convenience.
    A forgotten group is an equation the reader still has.

    Returns the suppression set, the derived interval for each primary cell, and
    whether every one clears the protection level.
    """
    ids = cells["cell_id"].tolist()
    idx = {c: i for i, c in enumerate(ids)}
    values = cells.set_index("cell_id")[cost_col].to_dict()

    primary = {c for c in ids if 0 < values[c] < k}
    suppressed = set(primary)

    # Close every equation left with exactly one unknown, cheapest cell first,
    # preferring cells that also appear in another still-open equation.
    changed = True
    while changed:
        changed = False
        for g in groups:
            unknown = [c for c in g if c in suppressed]
            if len(unknown) != 1:
                continue
            options = [c for c in g if c not in suppressed]
            if not options:
                continue
            reach = {c: sum(1 for h in groups if c in h) for c in options}
            suppressed.add(min(options, key=lambda c: (values[c], -reach[c])))
            changed = True

    # Verify by solving the system a reader could solve.
    A = np.zeros((len(groups), len(ids)))
    b = np.zeros(len(groups))
    for r, g in enumerate(groups):
        for c in g:
            A[r, idx[c]] = 1.0
        b[r] = sum(values[c] for c in g)
    known = [c for c in ids if c not in suppressed]
    bounds = [(values[c], values[c]) if c in known else (0, None) for c in ids]

    intervals = {}
    for c in primary:
        obj = np.zeros(len(ids)); obj[idx[c]] = 1.0
        lo = linprog(obj, A_eq=A, b_eq=b, bounds=bounds)
        hi = linprog(-obj, A_eq=A, b_eq=b, bounds=bounds)
        width = float(-hi.fun - lo.fun) if (lo.success and hi.success) else 0.0
        intervals[c] = {"low": float(lo.fun) if lo.success else 0.0,
                        "width": width, "protected": width >= protection}

    return {
        "primary": sorted(primary),
        "suppressed": sorted(suppressed),
        "complements": sorted(suppressed - primary),
        "intervals": intervals,
        "all_protected": all(v["protected"] for v in intervals.values()),
        "suppressed_fraction": len(suppressed) / max(len(ids), 1),
    }

Verification permalink

The all_protected flag is the release gate. Two further checks matter in practice.

def assert_release(result: dict, tolerance: float = 0.30) -> None:
    assert result["all_protected"], (
        "a withheld cell can be bounded more tightly than the protection level: "
        + ", ".join(c for c, v in result["intervals"].items() if not v["protected"])
    )
    assert result["suppressed_fraction"] <= tolerance, (
        f"{result['suppressed_fraction']:.0%} of cells withheld — coarsen instead"
    )

A release that passes the first and fails the second is telling you the geometry is wrong, not the suppression. Coarsening the polygons raises every count and usually removes the primary set entirely, which is a better map than one with a third of its polygons blank.

Publishing fewer totals is the cheapest lever available and the first one to try. Each aggregate a release adds has to be paid for in withheld polygons.

The safety condition constrains which sets are admissible and says nothing about which to prefer. That choice belongs to whoever knows what the map is being read for.

Edge Cases & Adjustments permalink

Totals published elsewhere. A summary in a press release, a figure in an annual report, a previous coarser map — all are equations. Build the group list from an inventory of what the organisation publishes, not from what this job emits.
Non-negativity is not the only bound. If the release also states a maximum, or if a cell’s population is publicly known, add those as bounds to the linear program. They narrow the intervals, sometimes below the protection level.
Time series. Successive releases from the same geography add one equation per period. Run the suppression jointly across the series or fix the suppressed set for its whole duration.
Choosing complements for cartography. Swap the objective from suppressed count to suppressed area, or to a visual-disruption score, and re-run. The safety condition is untouched; only which cells go dark changes.
When everything fails. If no complement set clears the protection level, the release publishes too many totals at too fine a geometry. Coarsen, drop a total, or move to noise on the counts rather than suppression — the comparison made in small-cell suppression and complementary rules.

FAQ permalink

Is the greedy pass optimal?

No. Minimum-cost complementary suppression is an integer program and the greedy rule can suppress more than necessary. It is used because it is auditable and fast, and because the linear-programming check catches the case where it suppresses too little. Optimality costs cells, not safety.

Can I round instead of suppressing?

Rounding to a base leaves the true value inside a known band and is defeated by the same linear algebra over rounded totals — with the added problem that the rounded totals no longer sum exactly, which readers notice. If perturbation is acceptable, use a calibrated mechanism rather than rounding.

Do I need this if my map has no totals?

Check the inventory before answering. Legends imply maxima, downloadable tables imply record counts, and any earlier release at another resolution implies differences. Maps with genuinely no constraints are rarer than they look.

How do I explain the withheld cells to readers?

Publish the count of withheld polygons and the threshold, not their identities. That satisfies the reasonable transparency expectation without handing back the map of small cells.

Small-Cell Suppression & Complementary Suppression Rules — the theory and the safety condition
Setting Minimum Count Thresholds for Published Map Cells — choosing k and p first
Grid Aggregation & Spatial Binning Strategies — the coarsening alternative
Setting Epsilon Values for Spatial Heatmap Generation — the noise-based alternative when suppression costs too much

← Back to Small-Cell Suppression & Complementary Suppression Rules

Applying Complementary Suppression to Choropleth Maps

Core Calculation # permalink

Worked numeric example # permalink

Python Implementation # permalink

Verification # permalink

Edge Cases & Adjustments # permalink

FAQ # permalink

Related # permalink

Related topics