Abstract
Entity resolution (ER), also known as record linkage or deduplication, is the critical process of identifying and linking records that refer to the same real-world entities within or across databases. This paper introduces a robust Bayesian graphical framework for ER that links records to latent entities using an exchangeable prior representation of the linkage structure. By adopting the Ewens-Pitman family of random partition priors, refining the distortion model for categorical attributes, and implementing a partially collapsed Gibbs sampler, the proposed model achieves superior accuracy and consistency across diverse datasets. Experimental results demonstrate that this approach outperforms existing Bayesian alternatives, particularly in maintaining high F1 scores across varying duplication rates and data scales.
Introduction
In modern data science, Entity Resolution (ER) is a fundamental challenge. As databases grow in complexity and volume, the absence of unique identifiers and the presence of noise—such as typographical errors, missing fields, and inconsistent formatting—make it difficult to consolidate records accurately. Traditional ER methods often rely on pairwise comparisons, which can be computationally expensive and difficult to scale.
Graphical ER offers a generative alternative: it treats records as noisy observations of a latent population of "true" entities. However, previous Bayesian graphical models have struggled with rigid priors that inadvertently bias the estimated number of entities and logically inconsistent distortion models for categorical data. This paper addresses these limitations by introducing a flexible, exchangeable prior structure and a more realistic model for attribute distortion.
Methodological Innovations
1. Exchangeable Random Partition Priors
The authors utilize the Ewens-Pitman (EP) family of priors (including Pitman-Yor and Ewens partitions) to model the linkage structure. These priors are mathematically "exchangeable," meaning the probability of a partition is invariant to the ordering of the records. This property ensures that the model remains consistent as new data is added, providing a more principled foundation for clustering records into entities than the uniform priors used in earlier models.
2. Refined Distortion Modeling
A significant contribution of this work is the correction of the "hit-miss" model typically used for categorical attributes. In standard models, a distorted attribute could, by chance, match the true entity value—a logical inconsistency. The proposed model explicitly forbids a distorted attribute from matching the latent true value, creating a more robust representation of how data becomes corrupted in real-world scenarios.
3. Hyperpriors and Flexibility
To reduce the need for manual parameter tuning, the researchers incorporated hyperpriors on the partition parameters. This allows the model to "learn" the underlying clustering behavior of the dataset—such as whether the data contains many small clusters or a few large ones—directly from the evidence. This makes the model more adaptable to different data regimes without requiring expert-level prior knowledge.
4. Computational Efficiency
To address the computational demands of Bayesian inference, the paper introduces a partially collapsed Gibbs sampler. By marginalizing out certain variables, the algorithm achieves faster convergence and better mixing than standard MCMC approaches. This innovation allows the model to scale to datasets of approximately 10,000 records while maintaining the benefits of a fully Bayesian treatment.
Experimental Evaluation
The model was evaluated against two primary baselines—blink and Sadinle—using a variety of datasets, including:
- nltcs: De-identified records from the National Long Term Care Survey.
- RLdata: A synthetic benchmark dataset of person records.
- cora and rest: "Dirty" datasets containing research citations and restaurant listings.
- Household Survey Simulator: A custom simulator designed to mimic complex family dependencies (e.g., shared addresses and surnames).
Key Findings
- Accuracy: The proposed model consistently achieved the highest or equal-highest F1 scores across all test cases. It proved particularly effective at balancing precision and recall, avoiding the "blink" bias where distortion is often over-estimated.
- Robustness: In simulation studies, the model remained stable even under low duplication rates, a scenario where other models frequently fail by over-linking records.
- Hybrid Matching: For multi-token strings like addresses, the implementation of a hybrid distance measure (combining token-based and edit-distance matching) significantly improved the handling of word swaps and typos.
Discussion and Future Directions
While this research represents a significant advancement in Bayesian ER, several avenues for future work remain. Current scalability is limited to roughly 10,000 records; scaling to millions of records will require the integration of advanced "blocking" techniques or parallelized inference. Additionally, the authors suggest exploring "microclustering" priors for datasets where the number of records per entity remains small regardless of total dataset size. Finally, explicitly modeling dependencies between attributes (e.g., the correlation between First Name and Gender) could further refine the model's predictive power.
By providing open-source software and a rigorous framework for exchangeable partitions, this work offers a powerful tool for practitioners seeking to clean and link complex administrative and survey data.
Summary updated