Splicing Social Circles: High-Precision Name Disambiguation via Bipartite Graphs

TL;DR

Distinguishing between two people with the same name (e.g., "Andrew McCallum") in millions of web pages is a classic IR challenge. This paper moves beyond traditional text clustering by treating document-level social networks as fragments of a larger puzzle. Using a bipartite graph-based splicing method, the authors achieve a record-breaking precision of 0.95 on the WePS-2 benchmark, proving that who you know is a better identifier than what you say.

Background: The Limits of Textual Features

Most name disambiguation systems view web pages as bags of words. They cluster "Andrew the Professor" and "Andrew the Athlete" by looking for keywords like "Machine Learning" vs. "Track and Field." However, textual features are noisy and often overlap.

The authors argue that a person's social circle—the set of entities they appear with—is a much more stable signature. But there's a catch: social data in a single document is sparse. To solve this, we don't just need to compare networks; we need to splice them together.

Methodology: From Fragments to Networks

The core innovation lies in the Candidate-Neighbor Bipartite Graph.

1. Snippet Extraction: For every document $d_i$ mentioning name $n$, the system extracts "neighbors" $s_j$ (other person entities).
2. Graph Construction:
   • Nodes: One set of nodes represents document candidates ($C_n$), and the other represents neighbor entities ($S_n$).
   • Edges: An edge exists if a neighbor co-occurs with the target name in the same paragraph. Weights are based on normalized co-occurrence frequency.

Figure 1: The Bipartite Graph Structure connecting candidates to their social neighbors.

3. Iterative Splicing: The authors use a bottom-up clustering algorithm. Two candidates are merged if they share a significant number of neighbors in the bipartite space. This "splices" individual document snippets into a comprehensive social network for a specific namesake.

To combat the high dimensionality of name entities, the authors utilized a dimension array data structure, significantly reducing the computational complexity of the clustering process.

Experiments & SOTA Performance

The method was tested on the WePS-2 dataset (30 names, 150 pages each). The results highlight a fascinating trade-off:

• Pure Bipartite Method: Achieved a Precision (BEP) of 0.95, significantly higher than the top-performing systems at WePS-2. This confirms that social networks are incredibly "clean" features—if two pages share a social circle, they almost certainly refer to the same person.
• Two-Step Hybrid: By combining the graph method with textual features (URL, tokens, titles), the system achieved an F1-score of 0.83, surpassing the existing SOTA.

Table 1: Comparison with WePS-2 Top Performers. Note the superior Precision of the Bipartite approach.

Deep Insight: Why Splicing Wins

The "Namesake F1" metric (Figure 2 in the paper) reveals that the bipartite method is far more stable (standard deviation of 0.094) than hybrid methods. While textual features help boost Recall (finding all documents), they introduce noise that confuses the identity of the namesake. The social network acts as a "hard" constraint that prevents incorrect merges.

Critical Analysis & Conclusion

The strength of this work is its move away from "flat" feature vectors toward "relational" data structures. By recognizing that social networks are bipartite by nature, the authors effectively bypassed the sparseness problem that plagues traditional co-occurrence models.

Limitations: The method is dependent on the presence of named entities in the text. For "recluses" or individuals mentioned in short snippets without other names, the bipartite graph remains empty, forcing the system to fall back on less reliable textual features.

Takeaway: This paper provides a blueprint for modern Entity Resolution. In an era of Knowledge Graphs, the "splicing" of relational snippets remains a more effective strategy for identity verification than any amount of raw text processing.