Probabilistic linkage with graphs: leveraging cluster structure to improve the accuracy of entity resolution at scale
Abstract
Probabilistic record linkage identifies records belonging to the same entity even when identifiers are incomplete or imperfect, and is increasingly used to conduct population-level inferences from administrative data at scale. Linkage produces noisy pairwise links that must then be resolved into distinct individuals. The standard approach, transitive closure, applies a fixed threshold to each link independently and assigns clusters from the resulting connected components. However, the risk of merging distinct individuals grows with population size, motivating approaches that use graph structure to improve linkage accuracy. Clustering algorithms from adjacent fields solve the same graph-clustering task in other domains, yet have never been systematically evaluated for entity resolution. We evaluated eleven clustering algorithms -- five established in entity resolution and six from adjacent fields -- across three simulated datasets and one real-world dataset, and propose an adaptation tailored to linkage graphs. Cross-field algorithms -- Leiden, Louvain, label propagation -- were among the most accurate, reducing linkage error by up to 66% relative to transitive closure. The three algorithms also ran up to 40 times faster than Markov clustering (a leading approach in the entity resolution literature) and integrate directly into existing pipelines at scale.
Related
- High-resolution Calibrated Probabilistic Hourly Precipitation from a Deterministic Forecast
- The Markov Accessibility Topology and its Probabilistic Structure
- The Probabilistic Structure of Large Language Models
- Spectral Reconstruction of Lorentz Structure from the χ‑Operator An Operator‑Theoretic Resolution of Non‑Transitivity in Special Relativity
- Noncommutative Hourglasses II 1/2: Derived Category of Birational Linkage with Well-Formed Singularities
BibTeX
@misc{lauren2026probabilistic,
title = {{Probabilistic linkage with graphs: leveraging cluster structure to improve the accuracy of entity resolution at scale}},
author = {Evelyn Lauren and Laura White and Trevor Graham Bell and Jacob Bor},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00566},
eprint = {2610.00566},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00566},
}
RIS
TY - UNPB
TI - Probabilistic linkage with graphs: leveraging cluster structure to improve the accuracy of entity resolution at scale
AU - Evelyn Lauren
AU - Laura White
AU - Trevor Graham Bell
AU - Jacob Bor
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00566
UR - https://arxiv.org/abs/2610.00566
AB - Probabilistic record linkage identifies records belonging to the same entity even when identifiers are incomplete or imperfect, and is increasingly used to conduct population-level inferences from administrative data at scale. Linkage produces noisy pairwise links that must then be resolved into distinct individuals. The standard approach, transitive closure, applies a fixed threshold to each link independently and assigns clusters from the resulting connected components. However, the risk of merging distinct individuals grows with population size, motivating approaches that use graph structure to improve linkage accuracy. Clustering algorithms from adjacent fields solve the same graph-clustering task in other domains, yet have never been systematically evaluated for entity resolution. We evaluated eleven clustering algorithms -- five established in entity resolution and six from adjacent fields -- across three simulated datasets and one real-world dataset, and propose an adaptation tailored to linkage graphs. Cross-field algorithms -- Leiden, Louvain, label propagation -- were among the most accurate, reducing linkage error by up to 66% relative to transitive closure. The three algorithms also ran up to 40 times faster than Markov clustering (a leading approach in the entity resolution literature) and integrate directly into existing pipelines at scale.
ER -