Bayesian Graphical Entity Resolution using Exchangeable Random Partition Priors

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

In the world of data science, Entity Resolution (ER)—the art of figuring out which records in a database refer to the same real-world person, place, or thing—is a notoriously "dirty" job. Whether you're merging hospital records or de-duplicating a mailing list, you’re constantly fighting typos, missing fields, and the lack of unique IDs.

A recent paper by Neil G. Marchant, Benjamin I. P. Rubinstein, and Rebecca C. Steorts, published in the Journal of Survey Statistics and Methodology, introduces a more robust way to tackle this using Bayesian Graphical Models. By rethinking how we model the "linkage structure" and how data gets distorted, they’ve created a system that is more accurate and requires less manual tuning than previous state-of-the-art methods.

TL;DR

The authors propose a Bayesian graphical approach to entity resolution that uses flexible Ewens-Pitman random partition priors and a refined attribute distortion model. This combination allows the model to better estimate the number of unique entities in a dataset and achieve higher accuracy (F1 scores) across diverse real-world and synthetic datasets compared to existing baselines.

What Problem Does This Paper Address?

Most traditional ER methods (like the classic Fellegi-Sunter model) look at pairs of records and decide if they match. Graphical ER, however, treats the problem as a generative process: there is a latent population of "true" entities, and each record in your database is a noisy observation of one of those entities.

However, previous Bayesian graphical models had two major flaws:

  1. Rigid Priors: They often used "uniform" priors on the linkage structure, which were unintentionally very opinionated about how many unique entities should exist. This made the models perform poorly if the user didn't guess the number of entities correctly.
  2. Illogical Distortion Models: They used a "hit-miss" model where a distorted attribute (like a misspelled name) could, by pure chance, end up being the correct name. This is logically inconsistent for categorical data.

Methods

The researchers introduced four key innovations to solve these issues:

  • Exchangeable Random Partition Priors: Instead of a uniform prior, they adopted the Ewens-Pitman (EP) family of priors (including Pitman-Yor and Ewens partitions). These are mathematically "exchangeable" (the order of records doesn't matter) and "consistent" (the model works the same way as you add more data).
  • Hyperpriors for Flexibility: They placed hyperpriors on the parameters of these partitions. This allows the model to "learn" the clustering behavior of the data (e.g., whether there are many small clusters or a few large ones) rather than forcing the user to hard-code those assumptions.
  • A "Nuanced" Distortion Model: They fixed the "hit-miss" logic. In their model, if a record attribute is marked as "distorted," it is explicitly forbidden from matching the true entity value. This makes the model more robust, especially for string-type data.
  • Partially Collapsed Gibbs Sampler: To make the math tractable and the software fast, they designed a custom MCMC (Markov Chain Monte Carlo) algorithm that "collapses" (marginalizes out) certain variables, leading to faster convergence and better scaling.

Datasets

The model was put to the test on a mix of private, public, and synthetic data:

  • nltcs: De-identified respondent records from the National Long Term Care Survey.
  • RLdata: A synthetic dataset of person records commonly used as a benchmark in ER research.
  • cora: A "dirty" dataset of computer science research citations.
  • rest: Restaurant listings from Fodor’s and Zagat’s guides.
  • Household Survey Simulator: The authors built a new simulator (detailed in Appendix C) that mimics the complex dependencies found in real surveys, such as family members sharing addresses and surnames.

Key Insights and Ideas

  • The Power of "Vague" Hyperpriors: One of the most significant findings was that by using vague hyperpriors, the model became largely indifferent to which specific "regime" of the Ewens-Pitman family was used. This is a huge win for practitioners who don't want to spend weeks tuning prior parameters.
  • Fixing the "Blink" Bias: The authors compared their work to a popular model called blink. They found that blink tends to over-estimate distortion (sometimes claiming a name is 100% distorted), which hurts precision. Their refined model forces a more realistic balance.
  • Handling Multi-token Strings: For attributes like addresses or full names, they implemented a Hybrid Distance Measure that combines token-based matching with edit distances, allowing the model to handle word swaps and typos simultaneously.

Key Results

  • Superior Accuracy: Their model achieved the highest (or equal-highest) F1 score across all four primary datasets when compared to two major baselines (blink and Sadinle).
  • Robustness to Duplication: In simulation studies, the model remained stable even when the rate of duplication was very low—a scenario where other models often fail by "over-linking" records.
  • Speedups: The partially collapsed Gibbs sampler allowed them to handle datasets of ~10,000 records, which was previously a struggle for fully Bayesian graphical models without significant approximations.

Limitations and Future Work

While the paper represents a major step forward, the authors acknowledge some hurdles:

  • Scalability: While 10,000 records is good, real-world administrative data often hits the millions. Future work will need to look at parallelizing the inference or integrating "blocking" techniques more deeply into the Bayesian framework.
  • Microclustering: The current model assumes an infinite population of entities. The authors suggest exploring "microclustering" priors for cases where the number of records per entity is expected to stay very small even as the total dataset grows.
  • Dependency Modeling: Currently, the model assumes attributes (like First Name and Gender) are independent. In reality, they are highly correlated, and modeling that could further improve accuracy.

Paper Citation: Marchant, N. G., Rubinstein, B. I. P., and Steorts, R. C. (2023). "Bayesian Graphical Entity Resolution using Exchangeable Random Partition Priors." Journal of Survey Statistics and Methodology. arXiv:2301.02962v1

Summary updated

Abstract

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},
}

Loading related content...

Figure