Transitive Closure

Transitive closure is the smallest transitive relation containing a given binary relation. In record linkage, the initial pairwise match decisions form a relation R. The transitive closure R⁺ is computed by iteratively adding edges: if (A,B) ∈ R and (B,C) ∈ R, then add (A,C). This process continues until no new edges can be inferred, producing a set of disjoint connected components.

• Computed using Warshall's algorithm (O(n³)) or breadth-first search on adjacency lists (O(n²) for dense graphs)
• Guarantees linkage consistency across the entire dataset
• Prevents the contradictory scenario where A matches B and B matches C, but A does not match C

The output of transitive closure is a set of connected components — maximal subgraphs where every vertex is reachable from every other vertex via a path of match edges. Each component represents a distinct real-world entity.

• A component with 1 vertex: a singleton record with no matches found
• A component with k vertices: k records from potentially different sources that all refer to the same entity
• Components are mutually exclusive and collectively exhaustive
• Used directly to generate golden records by merging all attributes within a component

A critical vulnerability of transitive closure is that a single false positive match can cascade through the graph, merging two otherwise distinct entity clusters into one erroneous super-cluster. This is known as transitive linkage error.

• If record X incorrectly matches Y, and Y correctly matches Z, then X, Y, and Z all collapse into one component
• The error amplifies quadratically: one false link between two clusters of size m and n creates a single erroneous cluster of size m+n
• Mitigation strategies include edge weight thresholding (only closing over high-confidence matches) and cluster-level review of unexpectedly large components
• Some PPRL systems use correlation clustering instead of pure transitive closure to optimize globally for agreement and disagreement costs

Efficient transitive closure computation in large-scale record linkage uses the Union-Find (Disjoint-Set) data structure with path compression and union-by-rank optimizations.

• Find(x): Returns the representative root of the component containing x, with path compression flattening the tree for O(α(n)) amortized time
• Union(x, y): Merges the components containing x and y, attaching the smaller tree under the larger root
• Achieves near-constant amortized time per operation: O(α(n)) where α is the inverse Ackermann function
• Processes millions of pairwise match decisions in seconds on commodity hardware
• Naturally produces the final set of connected components without explicit graph construction

Transitive closure operates across blocking boundaries. If a blocking strategy partitions records into blocks and pairwise comparisons are only performed within blocks, transitive closure can still connect records that were never directly compared.

• Record A in block 1 matches B in block 1; B also appears in block 2 and matches C
• Transitive closure links A and C even though they were never in the same block
• This property enables multi-pass blocking strategies where different blocking keys are used in successive rounds
• Each round's matches feed into a global union-find structure, progressively growing entity clusters
• Critical for achieving high recall without the quadratic cost of all-pairs comparison

Evaluating transitive closure output requires cluster-level evaluation metrics rather than pairwise metrics, since the goal is correct entity grouping.

• Cluster F-measure: Harmonic mean of cluster-level precision and recall, where each predicted cluster is aligned to the ground-truth cluster with maximum overlap
• Homogeneity: Measures whether each predicted cluster contains records from only one true entity
• Completeness: Measures whether all records belonging to a true entity are assigned to the same predicted cluster
• V-Measure: Harmonic mean of homogeneity and completeness, providing a single score independent of the number of clusters
• Adjusted Rand Index: Measures the similarity between predicted and true clusterings, corrected for chance agreement