Home › Enterprise Intelligence Architecture

Entity Resolution & Knowledge Graphs

Blocking as the only escape from O(n²), probabilistic matching versus deterministic rules, schema matching as the precondition, honest quality metrics, and the resolved domain as a graph.

Last reviewed: 2026-09-04 · Українською

In this area

One customer lives in the CRM, in billing, in a call-centre complaint and on a sanctions list — under four different spellings. Until the system knows that, every aggregate 'per customer' is an aggregate per table row, not per person. Entity resolution is a four-stage pipeline: align the schemas, generate candidate pairs, decide whether a pair is one entity, collapse pairs into clusters. Each stage has its own metric and its own way of failing silently. This module walks all four and ends where the resolved domain becomes a graph — entity nodes, relationship edges, and a merge you can still undo.

Blocking: why the naive O(n²) comparison never ships

E4.1

The arithmetic that ends the debate. For 12M records the number of unordered pairs is 12e6² / 2 = 7.2 × 10¹³. Even at a fantasy rate of 1M comparisons per second that is 833 days of continuous work. Scaling the cluster does not save you: doubling the records quadruples the work. So a real pipeline never compares all pairs — it first generates candidates.

Blocking is a function assigning a key to each record; only records sharing a key are compared. Schemes that survive production:

• Standard blocking: a key built as phonetic surname code plus birth year, or the first 4 characters of the postcode plus the first 3 letters of the given name.
• Sorted neighbourhood: sort by a composite key, compare within a sliding window of size w. Cheap, but sensitive to an error in the first character of the key — such a record lands at the far end of the sort order.
• MinHash + LSH: fuzzy blocking over character n-grams. The band/row parameters set the effective Jaccard threshold above which pairs are guaranteed to collide into a shared bucket.
• Multi-pass: 3–5 independent schemes whose outputs are unioned. Each pass catches a different error mode; intersecting them would collapse recall to the weakest pass.

Two metrics, measured separately from the matcher. Pair completeness is the share of true matches that reached the candidate set at all. It is the recall ceiling of the entire pipeline: a pair blocking never emitted cannot be recovered by any matcher downstream. Reduction ratio is the share of pairs discarded. A scheme with RR 0.9999 and PC 0.91 is worse than one with RR 0.9990 and PC 0.985 despite ten times the compute: 9% of lost matches cannot be bought back with CPU money.

Block skew kills the job before volume does. Block-size distributions are always heavy-tailed: the empty postcode, the placeholder 'N/A', the most common surname. A 2M-record block is 2 × 10¹² pairs inside a single Spark task — one task that never finishes while 511 others finished long ago. A block-size ceiling is mandatory, but oversized keys must be routed to a finer pass with an extra field, not dropped: dropping a block means silently losing recall.

Blocking is a stage with its own report. Measure its metrics on their own labelled pair set, never mixed into the matcher's score: otherwise 'why did recall drop' has no answer — did the new key scheme stop emitting pairs, or did the match threshold move? Every pass carries its own measured PC, and a pass that adds compute without adding a single unique pair is removed from the scheme.

# Multi-pass blocking: candidate generation for 41M party records.
# Naive all-pairs = 41e6**2 / 2 = 8.4e14 comparisons -> never finishes, at any cluster size.
from pyspark.sql import functions as F

MAX_BLOCK = 1000  # hard ceiling: block cost is quadratic, so one fat block IS the job

def pass_keys(df, pass_name, key_expr):
    return (df.select(F.col("record_id"), key_expr.alias("bkey"))
              .where(F.col("bkey").isNotNull() & (F.length("bkey") > 3))
              .withColumn("pass", F.lit(pass_name)))

# Three independent passes, each blind to a different error mode.
blocks = (
    pass_keys(parties, "p1", F.concat_ws("|", F.soundex("last_name"), F.col("birth_year")))
    .unionByName(pass_keys(parties, "p2", F.concat_ws("|", F.substring("postcode", 1, 4),
                                                            F.substring("first_name", 1, 3))))
    .unionByName(pass_keys(parties, "p3", F.col("tax_id_normalised")))
)

# Kill the skew BEFORE the self-join. Route oversized keys to a finer pass; never drop them,
# because a dropped block is recall you lose without any log line saying so.
sizes     = blocks.groupBy("pass", "bkey").agg(F.count("*").alias("n"))
oversized = sizes.where(F.col("n") > MAX_BLOCK)      # -> refine_queue, reviewed every run
safe      = blocks.join(sizes.where(F.col("n") <= MAX_BLOCK), ["pass", "bkey"], "left_semi")

candidates = (safe.alias("a").join(safe.alias("b"), ["pass", "bkey"])
                  .where(F.col("a.record_id") < F.col("b.record_id"))  # each unordered pair once
                  .select("a.record_id", "b.record_id")
                  .distinct())                                          # union across the 3 passes

# Measure the blocking stage on its own, against a labelled pair set:
#   pair_completeness = |true_matches in candidates| / |true_matches|   <- recall ceiling
#   reduction_ratio   = 1 - |candidates| / (n*(n-1)/2)

Deciding a match: schema matching, deterministic rules and the Fellegi–Sunter model

E4.2

Schemas first, records second. You cannot compare values until you know which fields correspond and in what units they are expressed. Schema matching proposes column correspondences (dob ↔ birth_dt) from names, types, value statistics and, increasingly, language models. Schema mapping is the executable transformation: date formats, units, splitting full_name into two fields, the one-address-versus-three cardinality. Matching without mapping moves nothing, and this seam produces the most expensive class of resolution defects.

The deterministic core. Where a verified identifier exists — a checksummed tax id, an LEI, a policy number — run that rule first and freeze its result. It is fast, fully explainable and needs no labels. The probabilistic model then works on the remainder, where the identifier is absent or disagrees.

Fellegi–Sunter: one weight per field. Each candidate pair yields a comparison vector (agree/disagree/missing per field). Per field you estimate two probabilities: m = P(agree | match) and u = P(agree | non-match). An agreement contributes log₂(m/u), a disagreement log₂((1−m)/(1−u)); weights are summed.

• The ratio sets the weight, not m alone. Gender with m = 0.92 and u = 0.50 yields log₂(1.84) ≈ 0.88 bits — almost nothing. Birth date with m = 0.88 and u = 0.0004 yields ≈ 11 bits. A two-valued field cannot discriminate.
• m and u are estimated without labels — EM over comparison vectors under a two-latent-class model. u is directly checkable: a random pair is almost certainly a non-match.
• Two thresholds, not one. Above the upper one: MATCH. Below the lower: NON_MATCH. Between them lies the band where evidence is insufficient in both directions. Hand it to a human and size it against the team's throughput instead of guessing a single cut point.
• Cost of error sets the thresholds. Sanctions screening pays more for a miss; marketing dedup pays more for wrongly merging two customers. One threshold for both consumers is an implicit decision made on behalf of both.

From pairs to clusters. The matcher emits edges; the consumer needs entities. Naive transitive closure (A~B, B~C ⇒ A~C) has no notion of the cost of a false edge and chains records into giant pseudo-entities. Clustering must account for non-edges too — correlation clustering with a penalty on links resting on a single shared attribute.

# Fellegi-Sunter scoring: one log-likelihood weight per field, summed over the vector.
import math

# m = P(agree | match), u = P(agree | non-match). Both estimated by EM on unlabelled
# comparison vectors; u is sanity-checked against random pairs (almost surely non-matches).
FIELDS = {
    "birth_date": (0.880, 0.00040),   # agree -> +11.1 bits   : the workhorse
    "last_name":  (0.940, 0.00310),   # agree ->  +8.2 bits
    "first_name": (0.910, 0.00900),   # agree ->  +6.7 bits
    "postcode":   (0.790, 0.01200),   # agree ->  +6.0 bits
    "gender":     (0.920, 0.50000),   # agree ->  +0.9 bits   : nearly worthless, keep it honest
}
UPPER, LOWER = 8.0, -2.0   # MATCH / clerical-review band / NON_MATCH

def weight(field, state):
    m, u = FIELDS[field]
    if state == "agree":
        return math.log2(m / u)
    if state == "disagree":
        return math.log2((1.0 - m) / (1.0 - u))
    return 0.0                      # missing on either side contributes no evidence

def decide(comparison_vector):
    """comparison_vector: {'last_name': 'agree', 'birth_date': 'disagree', ...}"""
    w = sum(weight(f, comparison_vector.get(f, "missing")) for f in FIELDS)
    if w >= UPPER:
        return "MATCH", w
    if w <= LOWER:
        return "NON_MATCH", w
    return "REVIEW", w              # size this band against reviewer throughput, then set UPPER

# Deterministic core runs FIRST and wins outright - no probability needed for a checksummed id.
def resolve(pair):
    if pair["tax_id_a"] and pair["tax_id_a"] == pair["tax_id_b"]:
        return "MATCH", float("inf"), "rule:tax_id"
    label, w = decide(pair["cmp"])
    return label, w, "model:fs_v3"

Evaluating resolution quality and the resolved domain as a graph

E4.3

The pairwise metric lies systematically. The usual way to score ER is precision/recall/F1 over pairs. The trouble is that a cluster of k records contributes k(k−1)/2 pairs: the metric is weighted by the square of cluster size. A handful of giant wrong clusters supply millions of 'correct' pairs and mask exactly the failure the user feels most.

• B-cubed computes precision and recall for each record and averages over records, not pairs. One record, one vote, regardless of cluster size. The gap between pairwise F1 and B-cubed F1 is not noise but a diagnosis: it almost always points at a few bloated clusters.
• Ground truth is not built by random pair sampling. True matches are on the order of 10⁻⁶ of all pairs; a random sample of 10,000 pairs will contain no positives at all. Labelling is stratified by match score, plus a separate set built specifically to measure blocking pair completeness.
• Split the metrics by stage. PC/RR for blocking, precision/recall for the matcher, B-cubed for clustering. A single number for the whole pipeline hides which stage actually regressed.

The graph as the shape of the result. A resolved domain maps naturally onto a property graph: nodes are entities, edges are relationships. Three architectural rules decide whether the graph is liveable:

• Keep the merge reversible. Source records are neither rewritten nor deleted — they remain nodes, and the cluster becomes an additional node joined by RESOLVES_TO edges. A bad merge is undone by deleting edges, not by restoring a backup.
• Survivorship is per attribute. A golden record is not 'taken from the biggest source': each attribute has its own precedence (verified → recency → system priority), and the contributing record is stored alongside the value. Otherwise 'where did this name come from' has no answer.
• Re-anchor relationships onto resolved nodes. Leave payment edges between source records and a three-record cluster multiplies every payment by three. The edge is aggregated at entity level while keeping a reference to the source edge.

This layer — stable object identities over volatile tables — is what Palantir Foundry's ontology layer and comparable platforms exist to provide: the analyst asks about a 'counterparty', not about party_id in the seventh system. The storage model (property graph versus RDF) is a secondary choice driven by the consumer: neighbourhood traversal and aggregation favour Cypher/Gremlin; federation and formal ontologies favour SPARQL. Bridges between the languages exist, so the decision is not irreversible.

// Resolved entity as a node that never destroys its sources.
// The cluster is an EXTRA layer, so an incorrect merge is undone by deleting edges.
MERGE (e:ResolvedParty {cluster_id: $cluster_id})
  ON CREATE SET e.created_at = datetime(),
                e.method     = $method,          // 'rule:tax_id' | 'model:fs_v3'
                e.model_ver  = $model_version
SET e.legal_name     = $survivor_name,           // survivorship, resolved per attribute
    e.legal_name_src = $survivor_name_record_id, // ... and always the record it came from
    e.confidence     = $cluster_confidence;

WITH e
UNWIND $members AS m
  MATCH (r:SourceRecord {record_id: m.record_id})
  MERGE (r)-[l:RESOLVES_TO]->(e)
    SET l.score = m.score, l.decided_by = m.decided_by, l.decided_at = datetime();

// Relationships are asserted between RESOLVED nodes, never between raw records:
// otherwise a 3-record cluster makes the same payment appear three times to the analyst.
MATCH (a:SourceRecord)-[p:PAID]->(b:SourceRecord),
      (a)-[:RESOLVES_TO]->(ra:ResolvedParty),
      (b)-[:RESOLVES_TO]->(rb:ResolvedParty)
MERGE (ra)-[agg:PAID_AGG {source_edge_id: p.edge_id}]->(rb)
  SET agg.amount = p.amount, agg.source_system = p.source_system;

// Undo a bad merge without touching a single source row:
// MATCH (r:SourceRecord {record_id: $bad})-[l:RESOLVES_TO]->(:ResolvedParty {cluster_id: $c})
// DELETE l;

Sources this area derives from

1. HyperBlocker Accelerating Rule based Blocking in Entity Re
2. Scalable Entity Resolution Using Probabilistic Signatures
3. A Robust and Efficient Pipeline for Enterprise Level Large
4. An Overview of End to End Entity Resolut
5. The Role of Schema Matching in Large Enterprises
6. Valentine Evaluating Matching Techniques for Dataset Disco
7. A LINK BASED APPROACH TO ENTITY RESOLUTI
8. Towards Scalable Schema Mapping using Large Language Model
9. A Practioner s Guide to Evaluating Entity Resolution Resul
10. Meta Property Graphs Extending Property Graphs with Metada
11. Expressive Reasoning Graph Store A Unified Framework for M
12. S2CTrans Building a bridge from SPARQL to Cypher

Continue in this track