Entity Resolution That Can Forget: History-Independent Clustering Under Record Deletions

Entity resolution is the task of deciding which records, mentions or rows refer to the same real-world thing. Production systems run it on streams, and those streams are not append-only. Documents get unpublished, voters drop off a registry, bot accounts are purged, and a bad merge has to be undone. Streaming entity resolution systems avoid comparing every record against every other by using hashing and greedy clustering. They stay fast only because they assume records arrive and never leave. Cross-document coreference with a doubling clustering algorithm (Streaming Cross Document Entity Coreference Resolution) and incremental metric-learning resolution (An Incremental Entity Resolution Approach based on Deep Metric Learning) both make this assumption. Once a record that tied two groups together is deleted, neither system can split the merged entity without replaying history.

We propose to make the clustering a fixed function of the records currently present, rather than of the order in which records arrived. Each record gets a permanent pseudo-random rank from a hash of its identifier. Clusters are then formed by the classic PIVOT rule, run over a sparse "match graph" whose edges come only from pairs that share a blocking key. In this rule, the lowest-ranked unclustered record grabs all its unclustered matches. The rule is history-independent: inserting a record and later deleting it leaves exactly the state the system would have had if the record had never arrived. Deleting a record therefore triggers only a local repair, and the repaired output can be checked for exact equality against a batch re-run. What remains to measure is cost: how many calls to the expensive pairwise matcher each deletion requires, and how that cost behaves when deletions are not random.

Core Claim

Our claim is that, in dynamic entity resolution, deletions are a clustering-state problem and not a candidate-generation problem. A blocking index that lists records under hashed keys supports deletion trivially, because a record is simply removed from its buckets. The hard part is undoing merges.

We claim that hash-ranked PIVOT over a blocked match graph gives three properties together:

  1. Output exactly equal to batch re-clustering of the current record set, so the quality-versus-staleness tradeoff disappears.
  2. Repair after a deletion whose expected cost depends on the deleted record's local neighborhood, not on the size of the dataset.
  3. Matcher calls confined to pivot-to-candidate pairs, rather than all pairs within a block.

The precise rule is the following. Let $r(v)$ be the hash rank of record $v$, and let $N(v)$ be the records that share a block with $v$ and that the matcher scores as a match. Then $v$ is a pivot if and only if no lower-ranked neighbor $u \in N(v)$ is itself a pivot, and every non-pivot joins its lowest-ranked pivot neighbor.

Because ranks are fixed and independent of content, an adversary who cannot see the hash cannot target pivots more often than chance. This is precisely the condition under which Dynamic Correlation Clustering in Sublinear Update Time proves its polylogarithmic bounds; there, deletions are assumed uniformly random and targeted anchor deletions are left open. We do not claim to close that open problem for adaptive adversaries. Instead, we measure where hash ranking stops protecting against realistic, content-correlated deletions: purging a whole data source, or deleting high-degree hub records.

Research Program

The system has three parts.

Blocking index with deletion. We build an inverted blocking index with deletion support. It uses attribute-combination keys and capped block sizes in the style of MERAI (A Robust and Efficient Pipeline for Enterprise-Level Large-Scale Entity Resolution), which scales batch resolution to 15.7 million records but does not maintain clusters dynamically.

Pairwise matcher with a score cache. The matcher is held fixed across every method so that comparisons isolate clustering maintenance from matching quality. It is a fine-tuned language-model matcher, or the IER-DML metric model. Its scores are cached only for pairs that the PIVOT rule actually inspects.

Repair procedure. When a pivot is deleted, its members become unclustered. They are re-examined in rank order, and the repair spreads only to records whose pivot status changes. When a non-pivot is deleted, the system drops it and does nothing else. Insertions use the same rule in reverse.

On the analysis side, we will bound the expected cascade size of a deletion in terms of the local degree distribution of the match graph, assuming an oblivious adversary. We will then characterize empirically how the cascade grows under three deletion schedules: source-correlated deletions, degree-targeted deletions, and an adaptive adversary that watches cluster outputs and deletes apparent pivots.

We will also study the second axis of the problem, the number of quadratic comparisons. We count matcher calls per update and compare them to the number of within-block pairs that a block-exhaustive approach would score. This connects to the learning-augmented view of Learning-Augmented Streaming Algorithms for Correlation Clustering, which assumes predicted pairwise distances are available for free and does not address the cost of producing them. In our setting those predictions are the dominant expense.

Baselines

Do nothing: insertion-only greedy clustering. This is the naive reference point. We run a doubling-style streaming clusterer with hash-bucket candidate selection, after Streaming Cross Document Entity Coreference Resolution, which reports F-scores of 80–83% on ACE 2008. Deleted records are simply removed from their clusters, and no cluster is ever split. It uses the same blocking keys and the same matcher as our method. We beat it if, after deletions, its partition is measurably worse than our exactly-batch-equivalent partition at comparable matcher calls per update.

Periodic batch re-clustering. This is the strongest quality competitor. We buffer updates and re-run the full MERAI-style pipeline at fixed intervals, using PIVOT, the same blocking, and the same matcher. The paper reports F1 above 96% for record linkage, and 100% precision with 92.5–95% recall for deduplication on North Carolina voter data. Because our output equals a batch run on the current record set, the comparison is about staleness and total matcher calls over a stream. We beat it if we reach the same final quality with fewer cumulative matcher calls and zero staleness.

Dynamic Agreement. This is the strongest dynamic-clustering competitor: the anchor-based method from Dynamic Correlation Clustering in Sublinear Update Time. The file reports no millisecond numbers for it, only that its runtime "remained nearly constant" as average degree rose from 42.25 to 253.36 on the Drift dataset. We give it the match graph that our blocking produces as its database, with an identical matcher and an identical tuning budget for its sample sizes. We beat it if we match or improve its clustering cost under random deletions, and degrade less than it does under targeted deletions.

Ablation of the key ingredient. The ablation is "fresh-rank local repair." Each repair re-runs PIVOT on the affected neighborhood with new random ranks. This keeps locality but gives up history independence, so it isolates whether fixed ranks matter.

Why not just…?

Why not just re-cluster the affected cluster locally from cached scores? This is the most serious threat, and we treat it as one. If clusters are small, re-scoring all pairs inside a deleted record's cluster is cheap and simple. It loses in two places. The first is the heavy head of a Zipfian entity distribution, a skew the streaming coreference work explicitly exploits: there, cluster-wide re-scoring is quadratic in cluster size. The second is that greedy local re-clustering drifts away from what a batch run would produce. The fresh-rank ablation is exactly this alternative made concrete. If it matches our matcher-call counts and history gap on the voter and TAC-KBP data, the contribution reduces to the analysis of targeted deletions, and we will say so.

Why not just re-run the batch pipeline periodically? Batch tools fail at scale; MERAI reports that Dedupe degrades sharply beyond 2 million records. Even a scalable batch pipeline also re-scores unchanged pairs every period and serves stale merges between runs. The stream experiments report both costs directly.

Why not use linear sketches, which handle deletions natively? Linear sketches would have the system recover connected components under deletions in near-linear space. They suit transitive-closure entity resolution, which suffers from chaining: one false match joins two entities. Space is also rarely the binding constraint, since a sparse match graph fits in memory. The dynamic-stream lower bounds in Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams and Space Complexity of Minimum Cut Problems in Single-Pass Streams constrain space-limited designs, not designs that are limited by matcher calls. We will include connected components over the same match graph as a quality reference to show the cost of chaining.

Why not use deletion-safe similarity sketches for candidate generation? Odd sketches (A Fast Sketch Method for Mining User Similarities over Fully Dynamic Graph Streams) and ghost-edge pairing (DTC) solve a sampling-bias problem that an exact inverted index does not have. They become relevant only if the blocking index itself exceeds memory, which none of our benchmarks do.

Proposed Experiments

Data and deletion regimes. The centerpiece is the North Carolina voter snapshots for 2010, 2015 and 2020. Moving between snapshots produces real, non-random deletions alongside insertions, so turnstile entity resolution is tested on naturally occurring retractions.

The second setting is the incremental benchmarks Amazon-Google, DBLP-Scholar, DBLP-ACM and Fodors-Zagats, as used by IER-DML. IER-DML reports relative F1 gains of up to 5.49% on Amazon-Google and 4.64% on DBLP-ACM over its baselines; the file gives no absolute scores. On these benchmarks we inject deletions at rates up to 50%, mirroring the deletion rate used in the odd-sketch evaluation.

The third setting is TAC-KBP 2009 and ACE 2008 cross-document coreference, with simulated document unpublishing. Each dataset is run under three deletion schedules: uniform random, source-correlated, and degree-targeted. An adaptive pivot-hunting adversary is added as a stress test.

Metrics. For quality we report pairwise F1 and B-cubed against gold clusters. For cost we report matcher calls per update, and cascade size per deletion broken out by percentile. We also report a "history gap": the fraction of records whose cluster differs from a batch run on the current record set. This gap must be exactly zero for our method, which serves as a correctness check. It is nonzero, and grows over time, for the insertion-only and fresh-rank baselines.

Decisive checks. The proposal succeeds only if all three of the following hold:

  1. Under source-correlated deletions on the voter data, the insertion-only baseline loses measurable F1 relative to batch.
  2. Our method's matcher calls per deletion stay within a small constant factor of those per insertion, with no heavy tail in cascade size, while Dynamic Agreement's cost or quality worsens under degree-targeted deletions.
  3. Fresh-rank local repair shows a growing history gap or higher call counts.

If the third check fails, fixed ranks do not matter in practice. If the adaptive adversary produces cascades proportional to cluster size, then hash ranking is not a defense against output-observing attackers, and we will report that as a negative result.