Entity Resolution at Graph Scale
Why matching records is quadratic and how blocking makes it tractable, the transitivity trap in clustering matches, and why this determines a knowledge graph's quality more than anything downstream.
Deciding which records refer to the same real-world entity is the foundational problem of knowledge graph construction. Get it wrong in one direction and an entity's facts are split across duplicates, so no query about it is complete. Get it wrong in the other and two entities are conflated, so the graph asserts facts about a thing that does not exist. Both failures propagate to everything built on top.
The scale problem
Comparing every pair is quadratic: ten million records is fifty trillion comparisons, which is infeasible regardless of how cheap the comparison is.
Blocking reduces this by partitioning records into blocks and comparing only within them. A block key might be a name prefix, a postcode, or a phonetic encoding of a surname. Recall depends entirely on whether true matches share a block key, so a single key misses matches that differ on it.
Multiple blocking keys run in parallel and union the candidates, which raises recall at the cost of more comparisons and requires the keys to fail independently.
Locality-sensitive hashing gives a principled version: hash records so similar ones collide with high probability, with the collision probability tied to the similarity measure. MinHash for Jaccard similarity over token sets is the standard construction for text records.
The blocking stage sets the ceiling on recall for the whole system, and it is where most of the engineering effort should go, because no matching model recovers a pair that was never compared.
Matching and clustering
Within blocks, a matcher scores pairs: rules, a learned classifier over similarity features, or an embedding model. The comparison is straightforward relative to what follows.
The subtlety is transitivity. If A matches B and B matches C, the pairwise decisions imply A matches C, and the matcher may score that pair as a non-match. Naive transitive closure over pairwise matches produces catastrophic merges: a chain of weak matches collapses thousands of distinct entities into one cluster, and the failure is silent until someone queries a merged entity.
Correlation clustering, which optimises agreement with the pairwise scores rather than taking closure, is the principled response. Practical systems also enforce hard constraints, refusing to merge across incompatible attribute values, and cap cluster sizes as a safety net.
When it breaks
The threshold is a business decision. Precision and recall trade against each other, and which error is worse depends on the domain: merging two patients is a safety incident, while duplicating two products is an inconvenience. Setting it as a technical parameter hides a decision someone else should make.
Incremental resolution is harder than batch. A new record can merge two previously separate clusters, so the operation is not a simple insert, and a system designed only for batch resolution needs redesign to handle streams.
Errors are hard to undo. Once merged and used downstream, splitting requires knowing which facts came from which source, so provenance per assertion is what makes correction possible. Without it, an incorrect merge is permanent.
Evaluation needs labels that are expensive. Ground-truth matches must be produced by people, and the pairs that matter are the ambiguous ones, so a random sample of pairs is almost entirely trivial non-matches. Stratified sampling by match score is what produces an informative labelled set.
12 flashcards for this concept
Click a card to reveal the answer.