Learning CNF Blocking for Large-scale Author Name Disambiguation (2020)

Abstract: Author name disambiguation (AND) algorithms identify a unique author entity record from all similar or same publication records in scholarly or similar databases. Typically, a clustering method is used that requires calculation of similarities between each possible record pair. However, the total number of pairs grows quadratically with the size of the author database making such clustering difficult for millions of records. One remedy is a blocking function that reduces the number of pairwise similarity calculations. Here, we introduce a new way of learning blocking schemes by using a conjunctive normal form (CNF) in contrast to the disjunctive normal form (DNF). We demonstrate on PubMed author records that CNF blocking reduces more pairs while preserving high pairs completeness compared to the previous methods that use a DNF and that the computation time is significantly reduced. In addition, we also show how to ensure that the method produces disjoint blocks so that much of the AND algorithm can be efficiently paralleled. Our CNF blocking method is tested on the entire PubMed database of 80 million author mentions and efficiently removes 82.17% of all author record pairs in 10 minutes.

## introduction author name disambiguation (and) refers to the problem of identifying each unique author entity record from all publication records in scholarly databases @xcite . it is also an important preprocessing step for a variety of problems. one example is processing author-related queries properly (e.g., identify all of a particular author's * ## related work blocking has been widely studied for record linkage and entity disambiguation. standard blocking is the simplest but most widely used method @xcite . it is done by considering only pairs that meet all blocking predicates. another is the sorted neighborhood approach @xcite which sorts the data by a certain blocking predicate, and forms blocks with pairs of those records within a certain window. @xcite further improved this method to adaptively select the size of the window. @xcite introduced a suffix array-based indexing method, which uses an inverted index of suffixes to generate candidate pairs. canopy clustering @xcite generates blocks by clustering with a simple similarity measure and use loose & tight thresholds to generate overlapping clusters. recent surveys @xcite @xcite imply that there are no clear winners and proper parameter tuning is required for a specific task. much work optimized the blocking function for standard blocking. the blocking function is typically presented with a logical formula with blocking predicates. two studies focused on learning a disjunctive normal form (dnf) blocking @xcite were published in the same year. making use of manually labeled record pairs, they used a sequential covering algorithm to find the optimal blocking predicates in a greedy manner. additional unlabeled data was used to estimate the reduction ratio of their cost function @xcite while an unsupervised algorithm was used to automatically generate labeled pairs with rule-based heuristics used to learn dnf blocking @xcite . all the work above proposed to learn nondisjoint blocking because of the logical or terms in the dnf. however, other work learns the blocking function with a pure conjunction, to ensure the generation of disjoint blocks. @xcite learns a conjunctive blocking tree, which has different blocking predicates for each branch of the tree. @xcite produces blocks with respect to a size restriction, by generating candidate blocks with a list of predefined blocking predicates and then performs a merge and split to generate the block with the desired size. our work proposes a method for learning a nondisjoint blocking function in a conjunctive normal form (cnf). our method is based on a previous cnf learner @xcite , which uses the fact that a cnf can be a logical dual of a dnf. ## problem definition our work tackles the same problem with baseline dnf blocking @xcite , but in a different way to get the optimized blocking function. let @xmath0, r 2 , • • • , r n } be the set of records in the database, where n is the number of records. each record r has k attributes, and a be the attribute set @xmath1.a 2 , • • • , a k }. a blocking predicate p is a combination of an attribute a and a similarity function s defined to a. an example of s is exact string match of a. a blocking predicate can be seen as a logical binary function applied to each pair of records, so p(r x , r y ) = {0, 1}, where r x , r @xmath2. a blocking function f is a boolean logic formula consisting with blocking predicates p 1 , p 2 , • • • , p n , and each predicate is connected with either conjunction ∧ or disjunction ∨. an example is the goal is to find an optimal blocking function f * that covers a minimum number of record pairs while missing up to a fraction ε of total number of matching record pairs. to formalize it, ## learning the blocking function here, we first briefly review dnf blocking and then introduce our cnf blocking function. this section describes the gain functions that select an optimal predicate term for each step in the cnf learner. finally, we discuss an extension that ensures the production of disjunctive blocks. let p os be set of positive samples in l 3: let n eg be set of negative samples in l 4: t erms ← {p} 5: curt erm ← p 6: find p @xmath3, n eg, curt erm ∧ p i ) 9: add curt erm to t erms 11: first, the algorithm selects a set of candidate conjunction terms with at most k predicates. for each predicate p, it generates k candidate conjunction terms with the highest gain function. using the candidate terms, the algorithm learns the blocking function by using a sequential covering algorithm. it sequentially selects a conjunction term, from the set of candidates, that has the maximum gain value on the remaining samples, and attaches it with logical or to the dnf term. in each step, all samples covered by the selected conjunction term are removed. this process repeats until it covers the desired minimum amount of positive samples, or there is no candidate term that can further be improved. ## conclusion we show how to learn an efficient blocking function with a conjunctive normal form (cnf) of blocking predicates. using cnf as a negation of the corresponding disjunctive normal form (dnf) of predicates (mooney, 1995), our method is a logical dual of existing dnf blocking methods @xcite . we find that our method reduces more pairs for a large number of target pairs completeness and has a faster run time. we devise an extension that ensures that our cnf blocking produces disjoint blocks. thus, the clustering process can be efficiently parallelized. future work could use multiple levels of blocking functions for processing each block @xcite and using linear programming to find an optimal cnf @xcite .