Learning CNF Blocking for Large-scale Author Name Disambiguation

Kunho Kim, Athar Sefid, C. Lee GilesSDP @ EMNLP 2020 · DOI

Introduction

Author Name Disambiguation (AND) is a critical task in scholarly database management, aimed at determining whether multiple mentions of a name (e.g., "J. Smith" and "John Smith") refer to the same individual. In massive datasets like PubMed, which contains over 80 million author mentions, a naive $O(n^2)$ comparison approach is computationally infeasible. To address this, researchers employ blocking, a technique that filters out unlikely candidate pairs to reduce the search space. This paper proposes a novel blocking method using Conjunctive Normal Form (CNF) to achieve high efficiency and scalability without sacrificing accuracy.

Methodology

The core of the proposed approach is learning blocking schemes expressed in CNF—a series of "AND" requirements where each requirement is a set of "OR" options. For example, a rule might require a [Last Name Match] AND [First Initial Match OR Co-author Match].

Logical Duality and Early Rejection

The authors leverage the logical duality between CNF and the more common Disjunctive Normal Form (DNF). While DNF focuses on covering all positive matches, CNF is optimized for filtering out negative matches. Because a CNF formula is a sequence of conjunctions, the system can implement "early rejection": as soon as a single clause fails, the pair is discarded, significantly reducing processing time.

Disjoint Blocking for Parallelization

To handle the scale of 80 million records, the authors developed a disjoint blocking strategy. This ensures that each record is assigned to exactly one block, making the subsequent clustering steps "embarrassingly parallel." This allows the workload to be distributed across multiple CPU threads without inter-process communication overhead.

Experimental Setup

The method was evaluated using two datasets:

  1. PubMed Benchmark: A manually verified subset of 214 unique authors and 3,964 mentions, used for training and cross-validation.
  2. Full PubMed Database: A 2016 snapshot containing 80 million author mentions across 24 million publications.

Results and Discussion

The CNF blocking approach demonstrated superior performance compared to traditional methods. On the benchmark dataset, CNF achieved a Reduction Ratio (RR) of 0.882 at a Pairs Completeness (PC) of 0.99, significantly outperforming DNF-based blocking.

Performance comparison of CNF Blocking against DNF and Canopy Clustering.

The system's scalability was proven by processing the entire PubMed database in just 10.5 minutes using 24 threads. During this run, it successfully filtered out 82.17% of all possible author pairs.

The authors also compared the performance of disjoint versus nondisjoint CNF variants. While disjoint blocking is necessary for optimal parallelization, the results indicate it is slightly more restrictive than nondisjoint blocking, which offers a higher reduction ratio at high completeness levels.

Comparison of Disjoint and Nondisjoint CNF blocking variants alongside other baselines.

Conclusion

By focusing on efficient rejection through CNF and enabling massive parallelization via disjoint blocks, this work provides a scalable solution for author name disambiguation at the scale of tens of millions of records. Future work will explore multi-level blocking strategies and mathematical optimization of CNF formulas using linear programming.

Summary updated

BibTeX
@inproceedings{kim2020learning,
  author = {Kunho Kim and Athar Sefid and C. Lee Giles},
  title = {{Learning CNF Blocking for Large-scale Author Name Disambiguation}},
  booktitle = {SDP @ EMNLP},
  year = {2020},
  doi = {10.18653/v1/2020.sdp-1.8},
}
Figure