Bayesian Graphical Entity Resolution Using Exchangeable Random Partition Priors

Neil G. Marchant, Benjamin I. P. Rubinstein, Rebecca C. Steorts

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

Abstract

Entity resolution (record linkage or deduplication) is the process of identifying and linking duplicate records in databases. In this paper, we propose a Bayesian graphical approach for entity resolution that links records to latent entities, where the prior representation on the linkage structure is exchangeable. First, we adopt a flexible and tractable set of priors for the linkage structure, which corresponds to a special class of random partition models. Second, we propose a more realistic distortion model for categorical/discrete record attributes, which corrects a logical inconsistency with the standard hit-miss model. Third, we incorporate hyperpriors to improve flexibility. Fourth, we employ a partially collapsed Gibbs sampler for inferential speedups. Using a selection of private and nonprivate data sets, we investigate the impact of our modeling contributions and compare our model with two alternative Bayesian models. In addition, we conduct a simulation study for household survey data, where we vary distortion, duplication rates and data set size. We find that our model performs more consistently than the alternatives across a variety of scenarios and typically achieves the highest entity resolution accuracy (F1 score). Open source software is available for our proposed methodology, and we provide a discussion regarding our work and future directions.
BibTeX
@article{marchant2023bayesian,
  author = {Neil G. Marchant and Benjamin I. P. Rubinstein and Rebecca C. Steorts},
  title = {{Bayesian Graphical Entity Resolution Using Exchangeable Random Partition Priors}},
  journal = {Journal of Survey Statistics and Methodology},
  year = {2023},
  doi = {10.1093/jssam/smac030},
}
Figure