Mitigating Co-location Inference Across Joined Datasets

Every control on this site protects an individual record. Co-location is the linkage attack that does not need one: it infers that two people were in the same place at the same time, which is a disclosure about a relationship, and a relationship is inferable from two perfectly anonymised releases. Who met whom is often more sensitive than where either of them lives.

Core Calculation # permalink

Two masked records co-locate when their uncertainty regions overlap in space and time. Under a fuzz radius $R$ and a temporal cloak $\tau$, an encounter between records $i$ and $j$ is possible when

Possibility is not evidence. The encounter strength is what makes it evidence — the ratio of observed co-occurrences to those expected under independence:

where $p_i(c, w)$ is $i$’s marginal probability of being in cell $c$ during window $w$. Two strangers who both commute through a busy interchange have $\lambda \approx 1$. Two people who meet deliberately have $\lambda$ in the tens or hundreds, because the meeting happens in places and at times where neither would otherwise be.

The disclosure is the tail, and it concentrates exactly where privacy matters most:

giving a bounded relationship-inference score. What makes co-location resistant to standard controls is that $\lambda$ rises as the venue gets rarer: a meeting in a crowded station is unremarkable, and one in an empty industrial estate at 3 a.m. is close to proof, precisely because the expected count in the denominator is near zero.

Worked numeric example # permalink

Two masked mobility releases, $R = 200$ m, $\tau = 15$ min, 90 days. A pair of subjects co-occur 34 times.

Expected co-occurrences under independence, from their marginals: 2.1. So

Now the same pair after each control:

Tripling the fuzz radius — a large utility sacrifice — cuts PPI from 0.76 to 0.51. Quadrupling the temporal cloak does slightly better. Neither gets below 0.4 alone, because the meetings that drive $\lambda$ are the repeated ones, and repetition survives any per-event noise: 34 independent draws around the truth still cluster around the truth.

Combining a temporal cloak with rare-cell suppression reaches 0.23. That is the shape of the answer — co-location needs the venue removed, not the position blurred.

Python Implementation # permalink

from __future__ import annotations

from itertools import combinations

import numpy as np
import pandas as pd


def encounter_strength(traces: pd.DataFrame, cell_col: str = "cell",
                       window_col: str = "window",
                       subject_col: str = "subject") -> pd.DataFrame:
    """Observed co-occurrences over those expected under independence.

    The ratio matters, not the raw count: two commuters sharing a busy
    interchange co-occur constantly and mean nothing, while two people who
    meet four times in an empty cell mean a great deal.
    """
    presence = (traces.groupby([subject_col, cell_col, window_col])
                      .size().rename("n").reset_index())

    # Marginal probability of each subject being in each (cell, window).
    totals = presence.groupby(subject_col)["n"].transform("sum")
    presence["p"] = presence["n"] / totals
    n_slots = presence[[cell_col, window_col]].drop_duplicates().shape[0]

    pivot = presence.pivot_table(index=subject_col,
                                 columns=[cell_col, window_col],
                                 values="p", fill_value=0.0)
    subjects = list(pivot.index)
    p = pivot.to_numpy()

    # Observed co-occurrence: both present in the same slot.
    seen = (pivot.to_numpy() > 0).astype(float)
    observed = seen @ seen.T
    expected = (p @ p.T) * n_slots

    rows = []
    for a, b in combinations(range(len(subjects)), 2):
        exp = max(expected[a, b], 1e-9)
        lam = observed[a, b] / exp
        rows.append({
            "subject_a": subjects[a], "subject_b": subjects[b],
            "observed": float(observed[a, b]), "expected": float(exp),
            "lambda": float(lam), "ppi": float(lam / (lam + 5.0)),
        })
    return pd.DataFrame(rows).sort_values("ppi", ascending=False)


def suppress_rare_cells(traces: pd.DataFrame, min_subjects: int = 20,
                        cell_col: str = "cell",
                        window_col: str = "window",
                        subject_col: str = "subject") -> pd.DataFrame:
    """Drop (cell, window) slots too sparse to hide a meeting.

    This is the control that works, because lambda's denominator is the
    expected count: a slot nobody else occupies makes any co-occurrence in it
    arbitrarily strong evidence, no matter how much the positions were fuzzed.
    """
    occupancy = (traces.groupby([cell_col, window_col])[subject_col]
                       .nunique().rename("subjects").reset_index())
    keep = occupancy[occupancy["subjects"] >= min_subjects][[cell_col, window_col]]
    return traces.merge(keep, on=[cell_col, window_col], how="inner")


def coloc_gate(traces: pd.DataFrame, ppi_max: float = 0.30,
               tail_share_max: float = 0.001) -> dict:
    """Block a release whose relationship tail is informative."""
    strengths = encounter_strength(traces)
    over = strengths[strengths["ppi"] > ppi_max]
    return {
        "pairs": len(strengths),
        "max_ppi": float(strengths["ppi"].max()) if len(strengths) else 0.0,
        "pairs_over_threshold": len(over),
        "tail_share": len(over) / max(len(strengths), 1),
        "worst_pairs": over.head(10).to_dict("records"),
        "passes": (len(over) / max(len(strengths), 1)) <= tail_share_max,
    }

Verification # permalink

The gate must reject a planted relationship. Inject a synthetic pair who meet weekly in a quiet cell, and confirm the gate blocks:

def test_gate_detects_planted_meeting():
    """A check that has never rejected anything proves nothing."""
    traces = load_background_traces()          # ~2000 subjects, no relationships
    planted = pd.DataFrame([
        {"subject": s, "cell": "quiet_industrial_7", "window": f"w{week}"}
        for week in range(12) for s in ("X", "Y")
    ])
    result = coloc_gate(pd.concat([traces, planted]))
    assert not result["passes"]
    worst = result["worst_pairs"][0]
    assert {worst["subject_a"], worst["subject_b"]} == {"X", "Y"}

Measure across releases, not within one. The attack joins two products, so the gate must run over their union. A per-release gate that passes twice can still permit a strong inference on the join:

def cross_release_gate(releases: list[pd.DataFrame], **kw) -> dict:
    """Co-location lives in the union, so the gate must too."""
    per_release = [coloc_gate(r, **kw) for r in releases]
    joined = coloc_gate(pd.concat(releases, ignore_index=True), **kw)
    return {
        "per_release_pass": all(r["passes"] for r in per_release),
        "joined_pass": joined["passes"],
        # The interesting failure: each release is fine and the union is not.
        "emergent_risk": all(r["passes"] for r in per_release) and not joined["passes"],
        "joined": joined,
    }

Check that suppression did not simply move the tail. After suppressing rare cells, re-run the strength calculation. If the top pairs are the same pairs with slightly lower scores, the suppression threshold is too low; if they are different pairs at much lower scores, it worked.

Confirm the expected-count model is not the weak link. $\lambda$ depends entirely on $\mathbb{E}[n_{ij}]$, and an independence model that ignores commuting structure will call every pair of colleagues a relationship. Validate the denominator against pairs known to be unrelated — if they average well above 1, the model is under-predicting and the tail is full of false positives.

Edge Cases & Adjustments # permalink

• Households. People who live together co-locate constantly and legitimately. Their $\lambda$ is enormous and the inference is not news. Where household structure is known, treat co-resident pairs as a single unit; where it is not, expect the tail to be dominated by them and say so, because a gate that fires only on households is a gate that gets disabled.
• Group events. A concert produces $\binom{n}{2}$ high-$\lambda$ pairs at once. Detect slots with anomalously many simultaneous subjects and treat them as a venue rather than as pairwise evidence.
• Asymmetric sensitivity. The inference “A met B” is more sensitive for some pairs than others — a journalist and a source, a patient and a clinic. You cannot generally identify which, which is an argument for a uniform threshold rather than a risk-weighted one.
• Co-location without co-occurrence. Sequential presence in the same rare cell — A at 14:00, B at 14:20, repeatedly — is a dead-drop pattern that a simultaneity test misses entirely. Extend the window comparison to a lag if the threat model includes it.
• The control that actually works. If the analysis does not need cross-subject comparison, release per-subject aggregates rather than event-level traces. Co-location inference requires two subjects in one queryable space, and the cheapest mitigation is to never put them there.

FAQ # permalink

Why does more fuzzing help so little?

Because repetition beats per-event noise. Thirty-four independent draws around a true meeting point still cluster around it, so the co-occurrence count barely falls while the expected count rises only in proportion to area. The ratio is stubborn.

Is a PPI threshold of 0.30 standard?

No — it is a working value corresponding to $\lambda \approx 2.1$, roughly twice chance. Set it from the sensitivity of the relationships in your population, and state the $\lambda$ it corresponds to so the number is interpretable.

Does differential privacy solve this?

Event-level DP does not: it protects single records, and the inference is built from many. Subject-level DP over the whole trace does help, at a utility cost most mobility releases cannot absorb.

Should the gate run on the raw data or the release?

The release, and on the union of releases. Raw-data co-location is expected; the question is what survives masking into the published artefact.

Related # permalink

• Spatial Linkage Attack Vectors & Mitigation — the attack family this belongs to
• Simulating Auxiliary Data Joins Against a Masked Release — the identity attack this outlives
• Choosing Temporal Cloaking Windows for Transit Feeds — sizing the τ that helps most
• Setting Minimum Count Thresholds for Published Map Cells — the rare-cell suppression this depends on
• Suppressing Home and Work Anchors in GPS Logs — removing the venues that dominate the tail

← Back to Spatial Linkage Attack Vectors & Mitigation