Transitive Clustering

Transitive clustering is the mother of all clustering algorithms for entity resolution. Its logic is appealing, super fast to compute, and beneficial for recall. However, it is typically paid with a significant reduction in precision. Let’s begin by examining how the algorithm works on a small dataset.

Connected components

Clustering follows pairwise prediction. Let $r_1,\ldots,r_n$​ denote the original records, where $c_{ij}=1$ if the pairwise model predicts a match between $r_i$​ and $r_j$​, and $c_{ij}=0$ otherwise. The following graph illustrates a toy example with $n=9$, nodes representing records, and the presence/absence of edges representing a predicted match/no-match.