Entity Resolution: Deciding Two Records Are One Thing

Entity resolution is deciding that “Acme Robotics GmbH”, “ACME ROBOTICS” and “Acme Rob. GmbH, Dresden” are one company. It is three problems in a trench coat: making the comparison count finite, scoring a pair, and choosing a threshold you can defend. The third is where most implementations quietly go wrong.

The problem, and its size

Start with the arithmetic, because it determines the entire architecture. Comparing every record with every other record is n(n-1)/2 comparisons:

   10,000 records ->  49,995,000 pairs
  100,000 records ->  4,999,950,000 pairs
1,000,000 records ->  499,999,500,000 pairs

At a generous million comparisons per second per core, a hundred thousand records is about 83 minutes and a million records is about five and a half days. The scaling is quadratic, so every doubling of the dataset quadruples the run. Nothing about a faster comparison function fixes this; you have to not do most of the comparisons.

The second piece of arithmetic is about the answer, not the runtime. In a million records with, say, 50,000 true duplicate pairs, the ratio of non-matches to matches is roughly ten million to one. A classifier that is 99.9% accurate on random pairs would still produce five hundred million false positives. Accuracy is a meaningless metric here; precision and recall on the matching class are the only ones that say anything.

Blocking: making the comparison count finite

Blocking partitions the records so that only records sharing a block are compared. A good blocking key is cheap to compute, puts true duplicates in the same block nearly always, and produces blocks small enough to compare exhaustively.

Use several blocking passes and take the union of the candidate pairs. A record only has to be caught by one of them, so passes are additive on recall and roughly additive on cost. Three passes — exact on a strong key, normalised name, and one fuzzy method — is a reasonable default.

Then measure two things about the blocking, before touching the scorer:

• Pair completeness — the share of known true duplicates that land in at least one shared block. This is a ceiling on recall for the whole system. If blocking has a completeness of 0.90, no scorer, however good, gets recall above 0.90.
• Reduction ratio — one minus the candidate pairs divided by all possible pairs. On a million records, going from 5×10¹¹ pairs to 5×10⁷ candidates is a reduction ratio of 0.9999, and a job that finishes.

The largest block is the thing that will actually break the job. One block containing every record whose postcode is missing, or whose name normalises to “holdings”, reintroduces the quadratic term for that block alone. Cap block size, and route oversized blocks to a second, more selective key rather than dropping them.

Scoring a candidate pair

Score per field, then combine. Per-field comparators that earn their place:

Combining them: a weighted sum is easy to explain and easy to tune by hand, which counts for a lot when a stakeholder asks why two records were merged. A trained classifier on labelled pairs does better on recall but has to be explainable to survive contact with a data steward. A workable compromise is a weighted sum with a small number of hard rules layered on top:

def score(a, b) -> float:
    s  = 0.45 * jaro_winkler(clean_name(a.name), clean_name(b.name))
    s += 0.20 * component_address_similarity(a.address, b.address)
    s += 0.15 * (1.0 if a.email_domain and a.email_domain == b.email_domain else 0.0)
    s += 0.10 * (1.0 if a.postcode and a.postcode == b.postcode else 0.0)
    s += 0.10 * date_bucket_similarity(a.founded, b.founded)
    return s


def decide(a, b) -> str:
    # hard rules run first and override the score in both directions
    if a.tax_id and b.tax_id:
        return "match" if a.tax_id == b.tax_id else "no-match"
    if a.country and b.country and a.country != b.country:
        return "no-match"

    s = score(a, b)
    if s >= 0.82:
        return "match"
    if s >= 0.62:
        return "review"
    return "no-match"

Choosing the threshold

A threshold is not a hyperparameter to be tuned by maximising F1. It is a business decision, and the way to make it is to lay out what each threshold does on a labelled sample and choose from the table.

Suppose 1,000 labelled candidate pairs from your blocking output, of which 500 are true matches. The table below is an illustration of the shape this takes, not a result from any real dataset — the point is the arithmetic and how to read it, and you must build the same table from your own labels:

threshold   TP    FP    FN    precision   recall    F1
  0.70     478    91    22      0.840      0.956    0.894
  0.76     455    44    45      0.912      0.910    0.911
  0.82     441    17    59      0.963      0.882    0.921
  0.88     402     5    98      0.988      0.804    0.887
  0.94     341     1   159      0.997      0.682    0.810

precision = TP / (TP + FP)      recall = TP / (TP + FN)
F1        = 2 * precision * recall / (precision + recall)

worked, at 0.82:   441 / (441 + 17) = 0.963
                   441 / (441 + 59) = 0.882
                   2 * 0.963 * 0.882 / (0.963 + 0.882) = 0.921

F1 peaks at 0.82 in that table, and F1 is the wrong objective. It treats a false merge and a missed merge as equally bad, and they are not remotely equally bad — which is the next section.

Merges and un-merges are not symmetric

A missed merge leaves two records where there should be one. The symptom is a duplicate in a list, a customer counted twice, a total that is slightly wrong. It is visible, it is annoying, and it is fixed by merging them later with no further damage.

A false merge collapses two real things into one. Two companies’ orders, credit limits, contacts and contracts are now attached to one node. Downstream systems cache the merged id. Somebody sees the wrong customer’s data. And the un-merge is genuinely hard: you have to decide, for every fact attached since the merge, which of the two originals it belongs to — and for facts created after the merge, the honest answer is sometimes that nobody knows.

So the threshold should be set for precision, and the recall you give up is bought back with a review band rather than with a lower threshold:

• Auto-merge above the high threshold (0.88 in the table, precision 0.988). Roughly one auto-merge in eighty is wrong, which is a rate a stewardship process can absorb.
• Queue for review between the two thresholds (0.62 to 0.88). In the illustrative table this band holds the pairs the system is not sure about, and human review turns them into labels that improve the next model.
• Discard below the low threshold. Accept the missed merges; they surface later as duplicates and get fixed then.

Then size the review band against the people you have. If it contains 4,000 pairs and a reviewer handles 60 an hour, that is 67 hours — one reviewer for a fortnight, or a narrower band. Doing that arithmetic before shipping is the difference between a review queue and a backlog.

The transitivity blow-up

Matching is pairwise; identity is not. If A matches B and B matches C, your system has implicitly claimed A matches C — even if the A-C score is 0.3. Take the transitive closure naively and one bad link can chain a hundred distinct companies into a single node. This is the failure that produces the notorious cluster containing every business in a city.

• Cap cluster size and refuse to auto-merge any connected component above it. A component of 47 records is not a company with 47 spellings; it is a bad blocking key or a generic name, and it belongs in review.
• Check the weakest link. Before merging a component, compute the minimum pairwise score within it. If the weakest pair is below the review threshold, the component is held together by one questionable edge — split it there.
• Prefer correlation clustering over closure. Clustering that considers negative evidence — two records with different tax ids must not be in one cluster — will break the chain where naive closure will not.
• Record the pairwise evidence per merge so an un-merge has something to work from. This is where canonical id design stops being theoretical.

The pipeline end to end

1. Normalise. Case, unicode, whitespace, legal suffixes, phone and address formats. Store the normalised form beside the original; never overwrite the original.
2. Block. Several passes, union the candidate pairs, cap block sizes, and record pair completeness against your labelled set.
3. Score. Per-field comparators, weighted sum, hard rules for decisive identifiers on both sides.
4. Decide. Two thresholds: auto-merge, review, discard.
5. Cluster. Connected components with a size cap and a weakest-link check, not blind transitive closure.
6. Assign canonical ids and write the mapping, keeping every source id resolvable forever.
7. Feed review decisions back as labels. A resolution system without this loop is at its best on day one and degrades from there as the data drifts.