Graph-based Approaches for Organization Entity Resolution in MapReduce

Hakan Kardes, Deepak Konidena, Siddharth Agrawal, Micah Huff, Ang SunEMNLP 2013

TL;DR

This paper tackles the challenge of accurately resolving organization entities in massive datasets by introducing novel graph-based blocking and clustering algorithms designed for MapReduce. Their approach, called sClust, effectively handles variations in organization names and relationships, significantly improving recall compared to traditional methods while maintaining scalability.

What Problem Does This Paper Address?

Entity Resolution (ER) is the crucial task of identifying records that refer to the same real-world entity within a database. This is particularly challenging for organization entities due to variations in names (e.g., abbreviations, legal names, typos), mergers, and acquisitions. For instance, "University of Washington," "UW," and "U. of Washington" all refer to the same institution. Inaccurate ER can lead to flawed data analysis, incorrect relationship mapping, and a degraded user experience in applications like people search engines. Standard ER pipelines involve blocking (grouping potential duplicates), pairwise linkage (scoring pairs), and clustering (grouping records into entities). However, scaling these steps to billions of records, as required by large commercial applications, is computationally intensive and requires efficient, distributed algorithms.

Methods

The authors propose a two-step approach for organization entity resolution optimized for MapReduce:

  • Graph-based Blocking: They introduce a novel blocking strategy that leverages graph structures and a binomial tree to efficiently partition records. This method groups organizations based on shared properties (like words in their names) and relationships (co-occurrences in person profiles). The algorithm recursively subdivides large blocks until they are manageable, aiming to create overlapping blocks that aid the subsequent clustering step.
  • sClust: Soft Agglomerative Clustering: This is the core novel contribution. After initial connected components are identified (using a standard transitive closure approach on high-scoring pairs), sClust further refines these components into distinct clusters. sClust is a "soft" clustering algorithm, meaning records can potentially belong to multiple clusters, and it explicitly handles "conflict sets" – pairs of records that should not be in the same cluster. This soft approach and conflict set management are key to handling complex relationships and avoiding the "black hole" problem where a single component incorrectly absorbs many disparate entities. The algorithm is designed to be parallelized using MapReduce.

Datasets

  • Freebase Dataset: A list of 150K organizations with aliases was used for training the pairwise linkage model and evaluating the system's precision and recall. 135K organizations were used for training, and the rest for testing.
  • Production Dataset: A large-scale dataset of 68 million organization names was used to demonstrate the framework's viability and scalability.

Key Insights and Ideas

  • Graph-based blocking is crucial for scalability: Directly comparing all record pairs is infeasible. Graph structures and recursive subdivision in MapReduce provide an efficient way to manage the search space.
  • Soft clustering with conflict sets is essential for accuracy: Hard clustering (transitive closure) can lead to errors by merging entities that shouldn't be together. sClust's ability to manage conflicting relationships and allow soft assignments significantly improves recall.
  • Handling "black hole" entities: The paper acknowledges the danger of transitive closure creating overly large, inaccurate components and proposes a mechanism to mitigate this by iteratively increasing the match threshold for oversized components.
  • MapReduce as a foundational framework: The entire pipeline is built on MapReduce, demonstrating how complex ER tasks can be distributed and scaled across commodity hardware.

Key Results

  • Pairwise Classifier Performance: Achieved 97% precision and 63% recall with a match threshold of 0.65.
  • Transitive Closure Performance: Showed very high recall (98%) but significantly lower precision (64%) at the same threshold.
  • sClust Performance: Outperformed both the pairwise classifier and transitive closure with a match threshold of 0.65 and a no-match threshold of 0.3, achieving 95% precision, 76% recall, and an f-measure of 84%.
  • Scalability Demonstration: On a 50-node Hadoop cluster, the framework processed 68M organization names, generating 14M unique blocks and 842M comparisons, with blocking completing in 42 minutes, pairwise classification in 220 minutes, and clustering in 3 hours.

Limitations and Future Work

  • Limitations: The paper notes that the "black hole" phenomenon can still be a challenge, and their mitigation strategy involves iterative threshold adjustments. The performance of the transitive closure step can be sensitive to the graph diameter.
  • Future Work: The authors suggest that the sClust algorithm's soft clustering nature and conflict set management are promising directions for future research in entity resolution. The paper also implies that further optimization of the MapReduce jobs for even greater efficiency is always a possibility.

Summary updated

BibTeX
@inproceedings{kardes2013graph,
  author = {Hakan Kardes and Deepak Konidena and Siddharth Agrawal and Micah Huff and Ang Sun},
  title = {{Graph-based Approaches for Organization Entity Resolution in MapReduce}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2013},
}
Figure