Four Acme nodes give every traversal a quarter of the edges

A knowledge graph stores each thing a corpus mentions as a node, stores each relationship some document states between two of those things as an edge, and answers a question by binding it to the nodes it names and walking edges outward from them. That walk is a traversal. Everything the design promises rests on one assumption no step in the ingestion enforces: that one real-world thing is one node. Prose does not supply it. A company appears in a document as whatever its author typed, and four years of support agents typing produce four spellings of one customer.

What follows from four spellings is not a cosmetic defect. It changes the answer, it changes it silently, and it changes it in a direction every review procedure built for a graph is blind to. The corpus-level pass that fixes it is entity resolution, and the argument here is about where that pass belongs in a system rather than whether it is worth running.

Where three thousand edges went#

An extraction run over a corpus of 200,000 support tickets finished overnight and produced 418,000 nodes and 1.1 million edges, which is roughly what the team estimated. Somebody poking at the result before the demo ran a sanity query against a customer they knew well.

MATCH (c:Company) WHERE toLower(c.name) CONTAINS 'acme'
RETURN c.name, size((c)--()) AS degree ORDER BY degree DESC

"Acme Corporation"   1,847
"Acme Corp"            622
"ACME"                 410
"Acme Inc."            190

Four nodes, one company, 3,069 edges distributed across them in no pattern anybody chose. The distribution reflects how support agents happened to type the customer's name in the ticket subject line over four years, plus the email signature block on forwarded threads, plus a run of tickets from an integration that shouted the account name in caps.

Those four degrees add to 3,069 exactly, and an exact sum licenses two claims and refuses a third. A column of counts only reproduces a total with no residual when the counts partition what is being counted, and the case to rule out here is double counting: size((c)--()) counts edges at both ends, so an edge running between two Acme nodes would appear in two rows and push the sum past the true count. A clean sum says there are no such edges, and that the four rows exhaust what the query found. What it cannot establish is that the query found everything. The filter is CONTAINS 'acme', so a fifth spelling that lost a letter to a typo, an abbreviation used in a hurry, or the name in a script sharing no characters with the Latin one all sit outside the sum. The total is a lower bound on this company's real degree, and the residual it hides is exactly the population string matching is worst at finding.

What a traversal sees from each of them#

The demo question was "which of Acme's open escalations involve the payments integration, and which engineers own them". Bind the question to a company node, expand two hops through raised and owned_by, and return the escalations. The answer depends entirely on which of the four nodes the binding step picked, and binding picks by string and vector similarity against the question, which said "Acme".

Read that table down its columns rather than across its rows, because the two middle columns behave differently and the difference is the teaching. The escalation counts on the four fragments add to 23, the figure the resolved row gives, and that closure licenses a strong statement: the four escalation sets are disjoint. Had any single escalation been reachable from two spellings — a ticket naming the customer one way in its body and another in its subject line — the parts would have summed above the whole. Each escalation attaches to exactly one surface form, so merging the nodes loses nothing on this column and recovers everything.

The engineer counts overshoot. Six, three, two and one add to twelve against a resolved nine, so three of the twelve are duplicate namings: an engineer owning escalations raised under two spellings is counted once per spelling on the left and once in total on the right. A column that closes and one that overshoots describe the shape of the underlying data without anybody stating it. Escalations are per-ticket objects and partition cleanly; engineers are shared across tickets and overlap. Whatever a fragmented graph reports about a one-to-many relationship can be summed back, and whatever it reports about a many-to-many one cannot.

Four different confident answers to the same question, each internally consistent, each with a clean traversal trace and real citations behind every edge. This is the practical consequence to give when someone asks what four duplicate nodes cost you: a traversal starting from any one of them sees roughly its share of the relationships, which here is somewhere between 4% and 60% depending on which node the binding step lands on, and the trace contains no signal at all that the rest exist.

Which node it lands on is fixed rather than random. Binding scores one fixed question against fixed node names, so the same wording returns the same seed and the same answer every time, and re-running a query cannot detect any of this. Rephrasing can: a user who writes "ACME" and one who writes "Acme Corp" bind to different nodes and are told 3 and 5, neither response acknowledging the other.

Those two percentages are shares of the answer, not shares of the edges, and the two quantities are close enough to be confused while measuring different things. One escalation out of twenty-three is a little over four per cent of the answer and fourteen out of twenty-three is a shade under sixty-one per cent, whereas the smallest fragment's share of the 3,069 edges is a little over six per cent. Degree share does not predict answer share, because reaching an escalation takes two hops and the second depends on which edges the first landed on — a node can carry many edges of a type the question never traverses.

The quarter in this chapter's title needs the same care. Four nodes holding one company's edges have a mean share of a quarter each, true by arithmetic alone: any four-way division of anything averages a quarter. It is a fact about the number four and carries no information about Acme. The actual shares run from a little over six per cent to a little over sixty, with the middle two near a fifth and near an eighth, so the typical fragment holds well under a quarter. The mean is the right figure for costing the problem across a graph and the wrong one for predicting any single query.

That silence is what makes the failure expensive rather than merely annoying. A missing document in flat retrieval leaves a hole a reader can sometimes feel, because the answer hedges or the citations thin out. A traversal over a fragmented graph produces a chain in which every link is genuine and every citation checks out, and the only thing wrong with it is the set of chains it never enumerated. There is no threshold to tune, no score to inspect, and no "0 results" to trigger a fallback. A reviewer tracing the answer end to end will confirm it, because everything in it is true.

Which names the belief this chapter exists to break. A reader who has followed the argument so far will write, confidently, that they verify graph answers by tracing every hop back to the document that asserts it, so a verified answer is a correct one. That defence is real and it works against fabricated edges, the next chapter's subject. It has no purchase here: the citations per hop, the length of the trace and the fraction of edges whose source document checks out are all identical whether the graph is resolved or shattered. The verification signal stays constant while completeness moves from four per cent to sixty. Every quantity a reviewer inspects is a property of the chains the traversal did produce, and the damage is entirely in the chains it did not.

The same blindness runs one level up, in the check the team actually performed. Matching the estimate of 418,000 nodes and 1.1 million edges was read as a sign of health. Extraction runs per document, so both totals are a per-document yield multiplied by a document count, and a per-document yield counts mentions. Neither total records how many real things those mentions denote, so a resolved corpus and a shattered one agree equally well with an estimate built from the same per-mention arithmetic. The volume check was structurally incapable of seeing the defect it was used to rule out.

Why the extractor produces this and cannot avoid it#

Extraction runs per document, as chapter 2 set out, and a per-document call sees one document. When ticket 84,102 says "ACME reports 500s on the payments webhook", the model has no way to know that ticket 71,338 said "Acme Corporation" about the same account, and asking it to normalise names on its own initiative makes things worse, since it will normalise inconsistently and invent canonical forms that appear in no document. The extractor's job is to report the surface form faithfully along with any aliases stated in the text; deciding which surface forms denote the same thing is a corpus-level question, and it needs a corpus-level pass. That pass is entity resolution: reading all the entity mentions the extraction produced, deciding which of them denote the same real-world thing, and collapsing those onto a single node with a single identity that every edge then attaches to.

This is a limit rather than a shortcoming of a particular model. Judging that two mentions denote one thing requires both mentions in front of whatever makes the judgement, and a per-document call has one. No prompt and no larger model changes that, because the missing input is not knowledge, it is the other document. Which is also why normalisation attempted inside extraction degrades the result: asked to canonicalise from a single document, a model must guess at a form it has not seen, and two documents guessing separately land on two different guesses — the original fragmentation, plus a layer of invented spellings on top.

The size of the comparison, and why it is never a loop#

The scale of that pass on this corpus: 340,000 Company mentions collapse to 41,000 distinct surface strings, which have to be resolved to somewhere around 12,000 real organisations. Comparing every pair of surface strings is 41,000² / 2, about 840 million comparisons, which is the reason resolution is never implemented as a nested loop. It runs as blocking — bucketing the names by some cheap key so that only names sharing a bucket are ever compared — followed by scoring the surviving pairs, followed by adjudication of the ones the score leaves undecided.

The square in that count is the design constraint. Each of n names meets each of the other n minus one, which counts every pair twice, so the number of distinct pairs is n times n minus one, halved — near enough n squared over two once n is large. Doubling the surface strings quadruples the work, which makes the naive version impossible rather than merely slow.

Those three counts also close against each other, which is the first independent check available on any of them. The measured fragmentation figure introduced further down is a mean of 3.4 nodes per entity, obtained by hand from a sample of 200 entities listed outside the corpus. Three point four nodes each across twelve thousand organisations predicts a shade under forty-one thousand surface strings, and extraction produced forty-one thousand. Two instruments sharing no step land on one number — one reads a small sample against an external list, the other is a whole-corpus aggregate that never consults an external list at all.

What that licenses is a step the audit could not take alone. The 200 entities somebody can enumerate authoritatively are entities somebody knows well, and fragmentation measured on well-known accounts is exactly the kind of figure that fails to generalise; the agreement says it generalises here. Two residuals keep it honest. If the twelve thousand was itself obtained by dividing forty-one thousand by three point four, the agreement is a restatement and licenses nothing. And both quantities count Company mentions only, so parts and facilities may be fragmented far worse.

def block(names: list[str]) -> dict[str, list[str]]:
    """Group candidates so only plausible pairs are ever compared."""
    buckets = defaultdict(list)
    for n in names:
        core = strip_legal_suffixes(n.lower())      # drops inc, ltd, gmbh, corp, co
        buckets[core[:6]].append(n)                 # prefix block
        for tri in trigrams(core):                  # trigram block, catches typos
            buckets[f"t:{tri}"].append(n)
    return buckets

def score(a: str, b: str, emb) -> float:
    return (0.5 * jaro_winkler(normalise(a), normalise(b))
          + 0.3 * cosine(emb[a], emb[b])            # embeds name + context sentences
          + 0.2 * shared_neighbour_ratio(a, b))     # do they touch the same nodes?

Blocking on a six-character prefix of the suffix-stripped name plus trigrams brings 840 million pairs down to about 2.1 million, which is a few minutes of CPU. Those two figures stand in a ratio of exactly four hundred, and the same four hundred arrives along a different route: 2.1 million pairs spread over forty-one thousand names puts each name in about a hundred pairs, since every pair consumes two name slots, and forty-one thousand over a hundred is four hundred again. The pair-count ratio and the per-name ratio share no arithmetic and agree, which is what says the reduction comes from the bucket structure rather than from a filter applied afterwards. The residual is that a hundred is a mean over wildly uneven buckets: a trigram appearing in a common word puts tens of thousands of names in one bucket, contributing a quadratic term the average hides. Implementations cap bucket size for that reason, and a capped bucket silently discards candidate pairs.

Blocking sorts before it compares, the way sorting post by postcode does before anyone hunts for two letters to one house — an analogy that stops at exactness. A postcode is assigned by an authority, so two letters to one house always carry the same key, whereas a six-character prefix is a guess about the front of a string. Take the code at its comment's word, that strip_legal_suffixes removes the tokens listed: Acme Corp reduces to a core of acme, as do ACME and Acme Inc., and all three land in one prefix bucket. Acme Corporation does not, because corporation is not corp, so its core keeps the second word and its prefix differs — the largest fragment falls in a different bucket from the other three, and only the trigram block brings it back. An implementation stripping corp as a prefix of corporation would collapse all four to one key, and the signature does not say which it does. Either way the blocking key decides which pairs are eligible at all, a plausible key can exclude the pair you most need, and a second key with different failure modes is the only cheap defence.

The third term in the score is the one that carries most of the weight and the one teams leave out: two nodes whose neighbourhoods overlap heavily are usually the same entity, and two nodes with identical names and disjoint neighbourhoods usually are not. Acme Corp and Acme Corporation share 71% of their neighbours in this graph — the same three engineers, the same payments integration, the same two escalation labels — and that is far stronger evidence than the string similarity.

An overlap percentage is only interpretable once you know its denominator, and this chapter's own degrees settle which one it can be. Overlap is quoted two ways: shared members over the union of the two sets, or over the smaller of them. Under the union reading, two nodes carrying 622 and 1,847 edges cannot exceed a share equal to the smaller count over the larger, around a third — below 71%, so that reading is unavailable unless the larger node's edges land on far fewer distinct neighbours than its degree suggests. Under the smaller-set reading, 71% is straightforward. The auto-merge band below asks for neighbour overlap of at least 0.4, which under the union reading would be out of reach for this very pair, so the band would never fire on the case it was designed for. When a ratio arrives without its denominator, ask which reading makes the system's own thresholds achievable.

Knowing how fragmented you are#

Fragmentation is invisible from the outside, so it needs a measurement rather than an impression, and there are two that cost almost nothing. The first is a gold set: take 200 entities you can enumerate authoritatively from somewhere outside the corpus — the CRM account list, the parts master, the service registry — and check how many nodes each one has in the graph. A mean of 1.0 is a resolved graph; the support corpus above scored 3.4 for companies before resolution and 1.08 after, and the residual 0.08 is the acquisitions and rebrands that no similarity function was going to catch.

The excess over one is the whole content of that measurement. A resolved graph scores exactly 1.0, so subtracting one leaves the average number of spare nodes per entity: 2.4 spare each before resolution, 0.08 after. If the surviving damage takes the simplest shape — each affected entity having one spare node and the rest none — that excess is also the fraction of entities still fragmented, about eight in a hundred. The alert threshold of 1.15 is an excess of fifteen hundredths, near enough double the post-resolution residual, so the alarm fires when refragmentation has roughly doubled the damage rather than at any absolute standard. That is a design decision about tolerable drift, and a different kind of statement from the requirement that a resolved graph score 1.0.

The second is a degree histogram over each entity type. A resolved graph of companies has a smooth heavy tail; a fragmented one has a characteristic bulge of low-degree nodes whose names are near-duplicates of high-degree ones, and a query that groups nodes by their suffix-stripped name and counts groups with more than one member finds it in seconds. Running both after every ingestion batch, and alerting when the gold-set mean drifts above 1.15, is the difference between noticing refragmentation in a week and noticing it when a customer does.

Low-degree there means low relative to its twin, which matters if anyone is tempted to replace the grouping query with a plain degree threshold. This graph averages a little over five edges per node, since 1.1 million edges each touch two of 418,000 nodes, and Acme Inc. — the smallest fragment — carries 190. It sits far out in the tail by any absolute measure and survives any usable threshold. The bulge only appears once nodes are grouped by name.

Multilingual corpora make the gold-set number worse in a way string metrics cannot fix. 华为 and Huawei share no characters, transliterations vary by document, and a Japanese subsidiary's name in kanji has no lexical relationship to its English filing name. The neighbour-overlap term carries these cases, since the two nodes touch the same parts and the same contracts, and an alias table seeded from any structured source you have — a company registry export, a customer list with localised names — carries the rest.

That is the same population the substring query at the top of the chapter could not reach. A name sharing no characters with the one you searched for sits outside a CONTAINS filter, a prefix bucket and a trigram bucket alike, because every cheap instrument here is lexical and they fail together rather than independently.

The merge you should refuse to make#

Pushing recall on resolution is not free, and over-merging causes a worse class of error than fragmentation. Acme Corp and Acme Corp GmbH differ by a legal suffix and score 0.94 on any string metric, and they may be a US parent and a German subsidiary with separate contracts, separate support entitlements and separate data-residency obligations. Merge them and the graph now asserts, with a clean citation chain, that a contract signed by one applies to the other. Fragmentation gives you an answer that is incomplete; over-merging gives you an answer that is wrong in a way no amount of tracing reveals, because the fabricated link is inside the node rather than on an edge.

The workable arrangement is three bands rather than one threshold.

Adjudicating five thousand pairs at roughly 1,200 tokens each is small change next to the extraction bill, and it is where the legal-suffix cases, the abbreviations (IBM / International Business Machines), and the genuinely ambiguous pairs land. Give the adjudicator the neighbourhoods, not just the names, because a model asked whether "Acme Corp" and "Acme Corp GmbH" are the same company can only guess, and a model shown that one touches a Frankfurt facility and a euro-denominated contract while the other touches a Delaware entity and a USD contract will keep them apart.

The cost cell rebuilds itself from the two figures beside it, which fixes what it covers. Four thousand nine hundred pairs at about 1,200 tokens each is just under six million tokens, and at the input price the earlier chapters of this topic use — three dollars for a million tokens — that is a shade under eighteen dollars. The figure is the whole of the adjudication input and nothing else: output tokens, retries and the embedding pass producing the cosine term all sit outside it.

The band volumes stand in a checkable relationship to the job. Collapsing forty-one thousand surface strings into twelve thousand organisations requires twenty-nine thousand merges, since each merge removes exactly one node and the difference between the counts is what has to disappear. The two upper bands offer thirty-six thousand pairs, clearing that with room to spare — and the surplus is redundancy inside groups rather than extra merges, which is a thing to worry about. Merging is transitive: if A merges with B and B with C, then A and C end in one node whether or not that pair was ever scored. A single incorrect pair inside a densely connected group drags the whole group together, so the precision an auto-merge band needs is stricter than its pairwise precision suggests. The 0.4 neighbour-overlap condition alongside the 0.92 score does exactly that work, demanding two independent kinds of evidence before a merge propagates.

Some pairs should never be decided by similarity at all. Where the corpus contains an identifier — a customer ID in the ticket metadata, a DUNS number, a VAT number, a repository URL — resolution should key on it and stop, because a deterministic join is right and a fuzzy match is only probably right. In practice most corpora have such an identifier for the entity type that matters most and nothing for the rest, so resolution ends up deterministic for accounts and fuzzy for everything else.

Resolution is a stage, not a cleanup#

The tempting shape is a one-off script run after the first extraction, because that is when the problem is visible and the fix is satisfying. It does not survive contact with a corpus that grows. Every ingestion batch introduces new surface forms — a new agent typing the name a new way, a new acquisition, a document in a language the corpus did not previously contain — and if resolution ran once, the graph starts refragmenting the day after it ran, invisibly, at whatever rate new documents arrive.

Running it as a stage means the pipeline carries a canonical entity registry with stable IDs, and ingestion resolves each new mention against the registry before writing edges.

def ingest(doc):
    ext = extract(doc.text, doc.id)
    for e in ext["entities"]:
        canon = registry.resolve(e)          # returns existing canonical id, or mints one
        e["canonical_id"] = canon.id
        canon.add_alias(e["name"], source=doc.id)
    for r in ext["relations"]:
        graph.upsert_edge(
            src=registry.canonical_id(r["source"]),
            dst=registry.canonical_id(r["target"]),
            type=r["type"], props=r, evidence=r["evidence"],
        )

The order of operations in that function is the mechanism. Entities resolve first, and the loop over relations looks up canonical_id for both ends before calling upsert_edge, so an edge is never written against a surface form. No window exists in which a raw mention is a node, and therefore no backlog of edges attached to the wrong place awaits a later pass. A cleanup script has to do that moving over a graph being read at the same time; a stage never creates the situation.

Stable IDs matter more than they look. Edges, provenance records and community summaries all reference nodes; if a re-extraction mints new IDs for the same entities, every reference breaks and the summarisation pass has to run again over a graph that did not meaningfully change. A merge should therefore be a redirect — the losing ID stays resolvable and points at the winner — so that anything holding the old ID keeps working and an incorrect merge can be undone without rebuilding.

Undoing is a requirement, not a nicety, because some merges will be wrong. The registry should record why each merge happened: the score, the band, the adjudicator's output if there was one, and the pair of source documents. Six months later, when somebody reports that the graph is conflating two subsidiaries, that record is the difference between a targeted split and a re-run. Between them the redirect and the record are what make transitive merging survivable at all.

Where a resolved graph is still wrong#

Resolution does not touch relation quality. A graph with perfectly resolved nodes can be full of edges asserting things no document says, and resolution will happily consolidate those edges onto the correct node, which makes the wrong answer more confident rather than less. The two failure modes compound: fragmentation hides edges that exist, and bad extraction manufactures edges that do not, and a graph can be suffering both at once with a node count and edge count that look entirely healthy.

Nor is it coreference resolution, which is a different problem inside a single document — deciding that "the supplier", "they" and "Hanyu" in paragraph four all refer to the entity named in paragraph one. That happens during extraction and affects whether an edge is emitted at all. Entity resolution happens after, across documents, and affects where the edge is attached. Teams that solve one and assume they have solved the other end up with a graph that is clean within each document and fragmented across the corpus, which is the common case.

Separating the two by what each can see keeps them apart. Coreference has one document in front of it and needs nothing else, which is why it runs inside the per-document extraction call; entity resolution needs every document at once, which is why it cannot. That difference in input is a difference in consequence. A coreference failure means the edge is never emitted, so the evidence is absent entirely. An entity-resolution failure leaves something to find in the wrong place, and the wrong place is reachable, correctly cited and confidently reported.

And it does nothing about the question of whether an edge is supported by anything at all. That question — how you tell an edge somebody asserted from one that extraction invented — has no answer in any schema shown so far, because nothing in the pipeline as described requires an edge to remember where it came from once it has been written. The next chapter is about the six months it takes for that to surface.