Abstract
Entity Resolution (ER) is a critical task in data integration, aimed at identifying records that refer to the same real-world entity. In "Clean-Clean" ER (CCER), where two datasets are individually duplicate-free, the matching process must satisfy a 1-1 constraint. This paper provides the first comprehensive empirical evaluation of eight bipartite graph matching algorithms. By analyzing over 700 similarity graphs from 10 real-world datasets, we identify the most effective and efficient strategies for large-scale entity matching.
Introduction
The challenge of Clean-Clean Entity Resolution lies in the final decision step: given a set of potential matches and their similarity scores, which pairs should be officially linked? This problem is naturally modeled as a bipartite graph matching task, where nodes represent records from two sources and edges represent similarity scores. Despite its importance, this step is often treated as a secondary concern compared to blocking or similarity scoring.
The Bipartite Matching Problem
In CCER, the input is a bipartite similarity graph $G = (V_A \cup V_B, E, w)$, where $V_A$ and $V_B$ are disjoint sets of records, $E$ is the set of candidate matches, and $w$ is a weight function representing similarity. The goal is to find a matching $M \subseteq E$ such that no two edges in $M$ share a common vertex, typically maximizing the total weight or the F1-measure.
Evaluated Algorithms
The study benchmarks eight learning-free algorithms with a maximum time complexity of $O(n^2)$:
- Connected Components (CNC): Groups nodes into components and retains only 1-1 pairs.
- Ricochet Sequential Rippling (RSR): Iteratively assigns nodes to the most similar "seed" nodes.
- Row Column Assignment (RCA): A heuristic approach to the linear assignment problem.
- Best Assignment Heuristic (BAH): A stochastic search using random edge swaps.
- Best Match Clustering (BMC): Matches each node to its most similar neighbor.
- Exact Clustering (EXC): A stricter version of BMC requiring mutual best-neighbor status.
- Király’s Clustering (KRC): A linear-time approximation for the stable marriage problem.
- Unique Mapping Clustering (UMC): A greedy approach that processes edges in descending order of weight.
Experimental Setup and Results
The evaluation utilized 10 real-world datasets (e.g., Amazon-Google, IMDb-DBpedia) to generate 739 similarity graphs using various representation models (n-grams, embeddings) and similarity measures.
Effectiveness
UMC and KRC emerged as the top performers in terms of F1-measure. UMC is particularly noted for its robustness and balance between precision and recall. While KRC often achieves the highest absolute F1-measure in "scarce" data scenarios, it is computationally more intensive than greedy alternatives.
Efficiency and Scalability
While CNC is the fastest, its accuracy is often poor due to low recall. EXC was identified as the "Goldilocks" algorithm, providing a superior balance of speed and accuracy, making it ideal for large-scale applications where UMC might be too slow.
Key Insights
- Threshold Sensitivity: The similarity threshold ($t$) often has a greater impact on performance than the choice of algorithm.
- Semantic Noise: Modern semantic embeddings (like ALBERT) can introduce noise into similarity graphs, making the matching task more difficult for traditional algorithms compared to syntactic methods.
- Scalability: Most evaluated algorithms scale linearly with the number of edges, confirming their suitability for big data contexts.
Conclusion
For most CCER tasks, Unique Mapping Clustering (UMC) is the recommended default due to its balanced performance. For scenarios requiring extreme efficiency without sacrificing too much accuracy, Exact Clustering (EXC) is the preferred choice. Future research should explore the integration of reinforcement learning to automate threshold selection and improve matching logic.
Summary updated