wenmin-wu/ds-skills/transitive-match-closure

Transitive Match Closure

Overview

Binary entity matching classifiers predict pairs independently, producing inconsistent match sets: A may match B without B matching A, or A matches B and B matches C but A doesn't match C. Transitive match closure fixes this by first enforcing symmetry (bidirectional links), then propagating matches through connected components. This consistently improves recall in entity deduplication and record linkage tasks.

Quick Start

def symmetric_closure(id2matches):
    """If A matches B, ensure B matches A."""
    for base, matches in list(id2matches.items()):
        for m in matches:
            if base not in id2matches.get(m, []):
                id2matches.setdefault(m, [base]).append(base)
    return id2matches
def transitive_closure(id2matches):
    """If A matches B and B matches C, add C to A's matches."""
    changed = True
    while changed:
        changed = False
        for base, matches in list(id2matches.items()):
            expanded = set(matches)
            for m in matches:
                expanded.update(id2matches.get(m, []))
            expanded.discard(base)
            if len(expanded) > len(set(matches)):
                id2matches[base] = list(expanded)
                changed = True
    return id2matches
# Apply to predictions
id2matches = dict(zip(df["id"], df["matches"].str.split()))
id2matches = symmetric_closure(id2matches)
id2matches = transitive_closure(id2matches)
df["matches"] = df["id"].map(lambda x: " ".join(id2matches[x]))

Workflow

1. Parse raw predictions into an ID → matches dictionary
2. Enforce symmetry: for each A→B link, add B→A
3. Enforce transitivity: propagate matches through connected components
4. Rebuild prediction strings from the closed match sets

Key Decisions

• Symmetry only vs full closure: Symmetry is safe; transitivity can over-merge if classifier has false positives
• Iteration limit: Cap transitive passes to prevent runaway merging on noisy predictions
• Confidence filtering: Only propagate high-confidence matches to limit error cascading
• Union-Find alternative: For large datasets, use disjoint-set (union-find) for O(n) closure

References

• [[Foursquare] LGB + Catboost](https://www.kaggle.com/code/felipefonte99/foursquare-lgb-catboost)
• Foursquare - LightGBM Baseline