PaperlayerView exact revision on arXiv

Source-linked AI summary

A Bayesian Approach to Graphical Record Linkage and De-duplication

Rebecca C. Steorts, Rob Hall, Stephen E. Fienberg

arXiv:1312.4645v4stat.ME

TL;DR

Record linkage must determine whether records refer to the same or distinct individuals, even when files lack unique identifiers. The paper proposes a unified Bayesian approach to record linkage and de-duplication, with reported runtime and comparative advantages, while noting that an approximation can introduce potential errors.

  • Problem

    Record linkage must determine whether distinct records refer to the same or distinct individuals when files lack unique identifiers.

  • Method

    The paper proposes a Bayesian approach based on a unified representation of record linkage and de-duplication.

  • Results

    Our method takes 3 hours rather than roughly 1500 hours, and SMERED beats Tancredi and Liseo (2011) for every region of Italy from the FWIW.

  • Takeaways & Limitations

    The unified approach supports treating record linkage and de-duplication within one methodological framework.

  • Takeaways & Limitations

    The paper notes that an assumption is at best an approximation and thus introduces potential errors.

Abstract

from arXiv · show

We propose an unsupervised approach for linking records across arbitrarily many files, while simultaneously detecting duplicate records within files. Our key innovation involves the representation of the pattern of links between records as a bipartite graph, in which records are directly linked to latent true individuals, and only indirectly linked to other records. This flexible representation of the linkage structure naturally allows us to estimate the attributes of the unique observable people in the population, calculate transitive linkage probabilities across records (and represent this visually), and propagate the uncertainty of record linkage into later analyses. Our method makes it particularly easy to integrate record linkage with post-processing procedures such as logistic regression, capture-recapture, etc. Our linkage structure lends itself to an efficient, linear-time, hybrid Markov chain Monte Carlo algorithm, which overcomes many obstacles encountered by previously record linkage approaches, despite the high-dimensional parameter space. We illustrate our method using longitudinal data from the National Long Term Care Survey and with data from the Italian Survey on Household and Wealth, where we assess the accuracy of our method and show it to be better in terms of error rates and empirical scalability than other approaches in the literature.

1 Introduction

The paper presents a Bayesian framework for linking records across multiple files while detecting duplicates, using a latent-individual bipartite graph that also supports uncertainty propagation and population estimation. It combines this representation with a linear-time hybrid MCMC algorithm and evaluates the method on survey data and simulations.

  • Motivation: Record linkage is difficult because noisy, distorted files make it ambiguous whether records represent the same individual.The problem is also high-dimensional and affects downstream statistical analysis.
  • Method: The method represents records as nodes linked to latent true individuals, unifying record linkage and within-file de-duplication.Records are linked indirectly through shared latent individuals, allowing multiple files to be handled simultaneously.
  • Scope and limitations: The paper identifies approximation of dependence as a source of potential errors and presents the method as the most basic and minimal member of its model family.Its simplicity is used to demonstrate what even a simple model can accomplish.
  • Method: The linkage structure supports estimation of unique population attributes and Bayesian propagation of matching uncertainty into later analyses.The paper also develops posterior matching probabilities and integrates linkage with analytic procedures.
  • Algorithm: A hybrid MCMC algorithm runs in linear time in the number of records and iterations, with further speed gains from blocking.The algorithm supports duplicates across and within lists, while known absence of within-list duplicates permits faster computation.
  • Evaluation: On the NLTCS, the competitor would take roughly 1500 hours while the proposed method takes 3 hours.The paper also evaluates the approach on the Italian Survey on Household and Wealth and simulated data.
  • Evaluation: SMERED beats Tancredi and Liseo’s method for every Italian region, while the paper compares its methods with baselines and simulations.For each region, the proposed method takes 17 minutes versus 90 minutes for the competitor approach.

2 Motivating Example

Records are distorted versions of latent individuals, and limited shared information can make it unclear which records refer to the same person. The motivating example frames linkage as distinguishing shared identities from distinct individuals under noisy fields.

  • Data-generating challenge: Records may contain measurement, transcription, or other unmodeled distortions, while files lack shared unique identifiers.These features make it ambiguous whether records refer to the same individuals.
  • Data-generating challenge: Gender and state alone permit multiple explanations, including one person with an error, several correctly recorded people, or several people with address errors.The example explicitly lists alternative identity configurations consistent with the observed fields.
  • Linkage objective: The linkage goal is to determine whether distinct records refer to the same individual or to distinct individuals.Additional fields such as date of birth and race can improve matching decisions but do not eliminate uncertainty.
  • Linkage objective: Records lacking identifying information such as names and addresses make matching inherently difficult and potentially indeterminate.The proposed method is intended to address this type of noisy-record setting.

3 Notation, Assumptions, and Linkage Structure

The model represents each record as a potentially distorted observation of a latent individual and estimates linkage, latent attributes, and distortion indicators jointly. A hybrid MCMC algorithm explores linkage structures while supporting duplicates, transitive matching sets, and posterior linkage probabilities.

  • Assumptions: The framework uses categorical common fields and allows missing-at-random fields as a minor Bayesian extension, but does not handle missingness across databases.The model assumes files are conditionally independent given latent individuals and fields.
  • Notation and model: The linkage structure Λ assigns each record to a latent individual, whose true field vector may generate a distorted record.Distortion indicators identify fields that differ from the latent values.
  • Linkage structure: Distinct records within the same list may correspond to the same individual, so de-duplication is modeled directly rather than assumed beforehand.Allowing duplicates simplifies the hybrid MCMC implementation by avoiding undefined linkages from pre-deduplicated data.
  • Computation: A hybrid MCMC algorithm uses split-merge proposals to explore possible linkage structures in linear time instead of quadratic-time linkage checks for every record.The split-merge strategy is designed to traverse high-probability modes efficiently.
  • Posterior matching: Maximal matching sets summarize posterior linkage relationships, and shared most probable matching sets produce a transitive estimated linkage structure.The framework also represents posterior matching probabilities for pairs and larger record sets.

4 Assessing Accuracy of Matching and Application to NLTCS

The NLTCS application tests linkage across three survey waves using four noisy variables and ground-truth identifiers. The model performs well at low to moderate distortion, with low error rates and posterior matching structures that expose uncertainty and likely errors.

  • Application setup: The NLTCS experiment links the 1982, 1989, and 1994 waves using only date of birth, sex, state, and regional office.Unique identifiers provide ground truth, although some model assumptions do not strictly hold because individuals can move between states.
  • Robustness and review: As distortion increases, both the false negative rate and false positive rate increase, while simulations show the method handles low to moderate distortion.Shared most probable matching sets form transitive components and can identify low-probability links for possible clerical review.
  • Accuracy results: 0.11 FNR and 0.046 FPR are reported for the NLTCS.These posterior link-error summaries accompany comparisons of estimated and actual linkage patterns.
  • Accuracy results: The confusion matrix is diagonally dominated, and its largest off-diagonal entry is 0.07, indicating generally probable correct linkage-pattern classifications.An example linkage pattern involving the 1982 and 1989 waves has 90% probability of being correct.
  • Posterior matching sets: A posterior matching set links three records with probability 0.995, and unique identifiers confirm that they represent the same individual.The example concerns records from 1982, 1989, and 1994 sharing observed demographic and location attributes.
  • Accuracy results: 0.11% relative error occurs for the first wave, while relative errors range from 8% to 15% as waves are combined using limited information.The authors attribute the larger cross-wave errors to matching people with limited available information.

5 De-duplication

The paper extends its linkage model to simultaneous record linkage and de-duplication, evaluating SMERED on longitudinal survey data and comparing its error tradeoffs with baselines and prior methods.

  • Method: SMERED extends the framework to detect duplicates within files while linking records across files.The NLTCS application runs SMERED both on separate waves and on a combined file containing induced duplicates.
  • NLTCS evaluation: 22,132 duplicate records were created by combining three NLTCS files, and SMERED recovered them with FNR 0.10 and FPR 0.17.
  • NLTCS evaluation: SMERED with shared MPMMS lowers FPR nearly by half while preserving the combined linkage and de-duplication task.SMERE has the best separate FNR and FPR, but SMERED supports both tasks simultaneously.
  • Matching difficulty: With five categorical fields, identical and near-identical records create 2,558 exact-match pairs and 353,536 near-twin pairs.These ambiguities explain why matching is difficult when names and addresses are unavailable.
  • Baseline comparisons: Against exact matching, SMERED has FNR 0.10 and FPR 0.37, whereas the baseline has FNR 0.09 and FPR 0.09.The near-twins baseline has FNR 0.05 and FPR 12.61, making it far more prone to lumping distinct individuals.
  • Thresholded linkage: Thresholding shared MPMMS produces FNR 0.10 and FPR 0.17 while preserving transitivity and reducing the number of links.
  • SHIW evaluation: Across SHIW regions, SMERED is reported superior to Tancredi and Liseo (2011) in FNR and FPR, while taking 17 minutes versus 90 minutes.

6 A User’s Guide to Record Linkage

The user guide presents the model’s assumptions and tuning choices, emphasizing that priors, blocking, field overlap, and list dependence constrain record-linkage performance and require application-specific judgment.

  • Assumptions: The method assumes conditionally independent lists, categorical data, minimal overlapping fields, independent blocks, and list-invariant distortion probabilities.
  • Assumptions: The categorical assumption is reasonable for anonymized applications but may introduce errors elsewhere, while dependence among lists remains context dependent.
  • Practical linkage: Matching to MPMMS is optimal for squared error loss, preserves transitivity, and supports posterior-probability thresholding for clerical review.
  • Practical linkage: Blocking is necessary for scalability, but choosing an appropriate blocking strategy remains an important unresolved issue.
  • Open problems: The paper identifies robust, domain-informed prior selection and model-misspecification as major directions for future research.
  • Choosing M: The prior’s latent-population size M controls overall linking tendency, with larger M making links less likely and smaller M excluding some linkage structures.
  • Prior behavior: Both the proposed and Sadinle’s priors are highly informative about the number of unique individuals, with tails that are too light for larger samples.

7 Discussion

The discussion presents a unified Bayesian linkage structure for simultaneous record linkage and de-duplication, with exact uncertainty propagation and scalable computation. It also identifies model assumptions and computational challenges as boundaries for future extensions.

  • The linkage structure connects observed records to latent individuals, unifying record linkage and de-duplication.
  • The specific Bayesian model enables efficient inference, exact error-rate calculation, posterior matching probabilities, and integration with capture-recapture methods.
  • Because the method is parametric, its assumptions apply only to certain problems, making the work a starting point rather than a universal solution.
  • The framework supports extensions for missing fields, data fusion, complex strings, population heterogeneity, and dependence across fields, time, or individuals.These extensions enlarge the parameter space and may require computational speed-ups such as online learning, variational inference, or approximation.
  • The approach is presented as a first basis for simultaneously solving linkage and de-duplication with a noisy Bayesian model for large-scale databases.

A Motivating Example of Linkage Structure and Distortion

The motivating example represents records from multiple lists as observations linked to latent individuals, with distortion indicators describing field errors. A bipartite graph then makes shared latent identities and transitive record relationships explicit.

  • The example treats the population as individuals represented in at least one list, with latent attributes such as state, age, and sex.
  • Observed records are organized into three lists, represented as a three-dimensional array for the example.
  • Only age is distorted in the simplified illustration, and comparing observed records with latent attributes identifies the intended linkage and distortions.
  • Each linkage-structure edge connects a record to a latent individual, so records referring to the same person are indirectly connected through that individual.
  • The example shows X11 and X22 sharing one individual, while X13, X21, and X34 share another.

B Hybrid MCMC Algorithm (SMERED)

SMERED uses split-merge proposals within a Metropolis-within-Gibbs sampler to update latent-individual assignments, attributes, distortions, and model parameters. The algorithm accepts or rejects proposed linkage states using a Metropolis probability.

  • When two records share a latent individual, the proposal splits their assignments, reallocates associated records, and constructs new latent attributes and distortion indicators.
  • The split proposal partitions other records between the two new latent individuals and resamples distortion indicators from conditional distributions.
  • Proposed states containing Λ, y, and z are accepted with a Metropolis probability or rejected while retaining the current state, followed by parameter resampling.
  • SMERED repeatedly samples record pairs and performs split-merge operations within each Metropolis-Hastings step.
  • When the selected records have different latent assignments, the proposal merges their associated records into a new individual and resamples fields and distortions.

B.1 Time Complexity

The time analysis shows that the Gibbs sampler has complexity driven by the number of fields, latent individuals, records, and MCMC iterations. When the field-value and latent-individual counts are much smaller than Nmax, the runtime is linear in Nmax.

  • The method’s runtime is proportional to the number of Gibbs iterations SG, so the analysis focuses first on one Gibbs step.
  • A Gibbs step is dominated by conditional-distribution sampling, including β and y at O(pNmax), θ and z at O(pMN), and Λ at O(pNmaxM).
  • The algorithm’s overall runtime for SG Gibbs iterations is O(pMNmaxSGSM).
  • When p and M are much smaller than Nmax, the runtime becomes O(NmaxSGSM), which is linear in Nmax.
  • Adequate posterior approximation depends on convergence properties of the hybrid Markov chain, which are outside the scope of the analysis.

C Simulation Study

The simulation evaluates the MCMC matching algorithm under increasing record distortion. Performance remains strong under moderate distortion but deteriorates sharply at high distortion levels.

  • Simulation design: The simulation runs NLTCS-based data with distortion levels of 0, 0.25%, 0.5%, 1%, 2%, and 5% through the MCMC algorithm.The study assesses matching under increasingly noisy data.
  • Matching errors: FPR increases approximately linearly with distortion, while FNR rises sharply between 2% and 5% distortion.This pattern is shown in Figure 8.
  • Population-size recovery: At moderate distortion levels, posterior densities estimate the true number of observed individuals extremely well.The simulation indicates that the model captures moderate per-field distortion effectively.
  • Population-size recovery: Once distortion becomes too noisy, the model has difficulty recovering the true number of observed individuals.Figure 9 reports overmatching near 2% per field and undermatching at 5% per field.
  • Overall accuracy: At higher noise levels, the algorithm matches fewer than 80% of individuals and recovers approximately 65% at around 5% distortion.The authors describe this accuracy as encouraging given the noise and limited identifying variables in the data.

D Confusion Matrix for NLTCS

The NLTCS confusion-matrix section presents the matching outcomes and their misclassification errors in separate tables.

  • Table 7 presents the confusion matrix for the NLTCS.
  • Table 8 presents the misclassification errors derived from the NLTCS confusion matrix.
Loading 1312.4645v4…