Seed nodes, a hop budget and community summaries make a graph answerable

The first design decision on a graph build is made in about twenty minutes and is the hardest one to reverse. Someone opens a file and writes down the node types — Company, Part, Facility, ProductLine, Incident — and the relations permitted between them: a Company supplies a Part, a Part used_in a ProductLine, a Company operates a Facility. It looks like a modest piece of data modelling. It is in fact the entire expressive ceiling of the system, because the extraction pass will emit nothing outside it, and every traversal, every summary and every answer for the next six months is built from what that pass emitted.

That claim is worth taking in steps, because "expressive ceiling" is the kind of phrase that gets nodded at rather than believed. Extraction is a model call constrained to emit types from a declared list, and any output naming a type outside the list is rejected, so no edge of an undeclared kind ever reaches the store. A traversal can only follow edges that are in the store. A community summary can only be written from nodes and edges that are in the store. So a distinction the schema cannot express is not merely hard to recover downstream: nothing downstream is ever handed the material it would be recovered from. The one operation that introduces it is re-running extraction over a corpus, which costs the whole ingestion bill a second time.

What the extraction pass actually sends#

Extraction is one model call per document, or per document chunk when documents are long, asking for structured output against the declared schema. The prompt carries the schema, a short type description for each node and relation, and the text; the response is parsed, validated, and rejected if it names a type that does not exist.

EXTRACTION_SCHEMA = {
    "entities": {
        "Company":     "a legal entity: supplier, customer, subsidiary",
        "Part":        "a manufactured component identified by a part number",
        "Facility":    "a physical site: factory, warehouse, data centre",
        "ProductLine": "a product we sell, at line granularity not SKU",
    },
    "relations": {
        "supplies":  ("Company", "Part",        ["valid_from", "valid_to", "sole_source"]),
        "used_in":   ("Part",    "ProductLine", ["revision"]),
        "operates":  ("Company", "Facility",    ["valid_from", "valid_to"]),
        "located_in":("Facility","Facility",    []),
    },
}

def extract(doc_text: str, doc_id: str) -> dict:
    resp = client.messages.create(
        model="claude-sonnet-4-5",
        max_tokens=4096,
        system=build_extraction_system_prompt(EXTRACTION_SCHEMA),
        messages=[{"role": "user", "content": doc_text}],
        tools=[EXTRACTION_TOOL],          # forces a JSON shape
        tool_choice={"type": "tool", "name": "emit_graph"},
    )
    return validate(resp, EXTRACTION_SCHEMA, doc_id)

Two things in that call do different jobs, and running them together is the commonest way to misjudge what a schema controls. EXTRACTION_SCHEMA is a vocabulary: which entity types exist, which relations are permitted, and which qualifiers each relation may carry — supplies is declared as running from a Company to a Part and carrying valid_from, valid_to and sole_source. EXTRACTION_TOOL, forced by tool_choice, is a shape: it makes the response JSON with the fields the tool declares, whatever the vocabulary happens to be. validate then checks the vocabulary against the schema. A response can be correctly shaped and rejected for naming an undeclared type, and — the case that matters later — it can be correctly shaped, correctly typed, and assert something no sentence in the document supports, because neither the shape nor the vocabulary is a claim about truth.

The output for the Hanyu contract looks like this, and the shape is worth reading closely because chapters 3 and 4 are both about fields that are or are not in it.

{
  "entities": [
    {"type": "Company", "name": "Hanyu Precision Manufacturing Co., Ltd",
     "aliases": ["Hanyu Precision", "Hanyu"], "mentions": [{"page": 1, "span": [412, 451]}]},
    {"type": "Part", "name": "CN-4471", "aliases": ["board-to-board connector"],
     "mentions": [{"page": 3, "span": [1180, 1187]}]}
  ],
  "relations": [
    {"type": "supplies", "source": "Hanyu Precision Manufacturing Co., Ltd", "target": "CN-4471",
     "valid_from": "2022-04-01", "valid_to": "2023-06-30", "sole_source": true,
     "evidence": {"doc_id": "contracts/hanyu-precision-2022.pdf", "page": 3,
                  "quote": "Supplier shall be the exclusive source of Part CN-4471"}}
  ]
}

Reading that output back against the schema shows where each field came from. Every qualifier on the relation — valid_from, valid_to, sole_source — is one of the three the schema declares for supplies, and there are no others: the vocabulary closes exactly, which is the expressive ceiling visible as an absence. The entity records carry aliases and mentions, and the relation carries evidence, none of which appears in EXTRACTION_SCHEMA at all. Those come from the tool's shape rather than from the vocabulary, and the distinction is worth holding before a schema review, because reading EXTRACTION_SCHEMA alone tells you what the graph can mean and not what each record will contain.

Two things about running this at scale. Malformed or schema-violating output is a steady tax rather than an occasional annoyance: with tool-enforced JSON the rate is low, in the region of 1–3% of documents, and it is higher on documents with tables, footnotes or bad character encoding, which is to say on exactly the documents most likely to matter. Every one of those is a retry, and a retry is a second full-price call over the same input tokens. Second, the extraction call is the dominant line on the ingestion bill, because it is per document and it reads every token of the corpus. A 500,000-document corpus averaging 1,800 tokens per document is 900 million input tokens before a single retry, which is where the cost chapter starts.

That last figure is a product with nothing left over: five hundred thousand documents at eighteen hundred tokens each is nine hundred million tokens. What the exactness licenses is ignoring document count on its own. Halving the number of documents while doubling their length leaves the product where it was, so the extraction bill is set by how much prose you hold and not by how it is divided into files, and the argument for chunking long documents is about a model's window rather than about price. Three things sit outside the product and are paid anyway. The emitted JSON is output, and output is billed. The instructions are re-sent on every call, so a corpus of many short documents pays for the schema description many more times than one of few long documents does. And the retries multiply the whole figure by a few per cent, which makes the retry tax a percentage on the run rate rather than a fixed cost, so it does not thin out as a corpus grows.

The sentence a reader would confidently write after all that is that a validated extraction is a trustworthy one, and it is worth checking against what validation actually compares. It compares emitted type names against the declared list. So the rejection rate moves when a model invents a type name, and it moves for no other reason. Suppose the extractor starts emitting supplies edges from sentences saying that a company quoted for a part. Every one of those edges names a declared type, carries declared qualifiers and parses cleanly, so the rate stays exactly where it was, in the region of 1–3%, while the share of edges that are true falls as far as you like. A number that holds still while the property it is being read as evidence for varies freely is not evidence for it, and that rate is the one number an ingestion dashboard usually puts on the wall.

Communities answer the question no traversal reaches#

Traversal answers questions that name something. "What are the main themes in our supplier risk exposure this year" names nothing you can bind to, has no start node, and no hop budget will produce an answer, because the answer is a property of a whole region of the graph rather than a path through it. The original GraphRAG work — From Local to Global: A Graph RAG Approach to Query-Focused Summarization — handles this with a second ingestion pass that clusters the assembled graph into communities — groups of nodes more densely connected to one another than to the rest of the graph, found here with the Leiden algorithm, which searches for the partition that maximises that density and refines it over successive passes — and then asks a model to write a summary of each community from its nodes, edges and their source snippets. Global questions are answered by mapping over the community summaries at a chosen level of the hierarchy and reducing the partial answers, rather than by touching the graph at all.

Clustering is hierarchical, so a 400,000-node graph might give roughly 30,000 leaf communities, 4,000 at the level above, and a few hundred near the root. Summaries are generated bottom-up, with higher levels summarising their children, and the cost is one model call per community per level. That is a second per-unit bill sitting on top of extraction, of the order of 35,000 calls for the example above, and it is the line most commonly missing from a cost estimate because it does not scale with document count — it scales with how many distinct clusters the graph happens to form.

That call count is the community counts added down the levels, and the column closes: thirty thousand leaves, four thousand above them, a few hundred near the root, landing on thirty-five thousand to within the width of "a few hundred". The counts fall by close to an order of magnitude at each step, so the sum is dominated by its first term, and what that licenses is estimating the whole summarisation bill from the leaf count alone — everything above the leaves adds roughly a seventh on top. The residual is that these are calls rather than tokens. Four hundred thousand nodes spread over thirty thousand leaf clusters is a dozen or so nodes each, and a summary of a dozen nodes is a short call, while a call one level up reads its children's summaries and a call near the root reads a great many of them. Equal call counts are not equal costs, and the money leans further towards the top of the hierarchy than the count does.

The two query paths this creates are usually called local and global search, and they are answering different question shapes rather than being alternatives for the same one. Local search starts from named entities and traverses; it is the path for "which product lines are exposed to the fire". Global search maps a question over community summaries and reduces the partial answers; it is the path for "what are our top three sources of single-supplier risk", where the answer requires having read the whole corpus and no entity in the question tells you where to start. Global search costs one model call per community consulted at the chosen level, so asking a global question over 4,000 mid-level communities is 4,000 calls, which is why implementations expose the level as a parameter and why global questions are a feature you ration rather than a default.

Those two figures are worth setting against each other, because together they decide the policy. One global question at the mid level is 4,000 calls, and building every summary in that hierarchy was of the order of 35,000. So somewhere around the ninth global question at that level, the feature has cost more model calls than the machinery it runs on cost to build. The level parameter is the dial that moves it: consulting a coarser level touches fewer communities and returns a coarser answer, and consulting the leaves is arithmetically close to re-reading the corpus.

Community summarisation is also the part that goes stale fastest. A community summary is a paragraph of English asserting things about a set of nodes and edges; move the edges and the paragraph is quietly wrong, with nothing in it to indicate that. Re-running Leiden on a changed graph does not merely update the affected cluster either, because community boundaries shift, so a node that moves brings its neighbours' summaries into question. The reason the shift is not local is in the algorithm: Leiden picks the partition that maximises density across the whole graph, so a single added edge changes the quantity being maximised, and the partition that wins afterwards need not agree with the previous one anywhere in particular. Chapter 6 turns this into money.

Binding a question to a starting point#

At query time the first job is finding where in the graph to stand, which means choosing the seed nodes a traversal will start from. The question arrives as English and the graph is keyed by entity, so binding runs a mix of exact and fuzzy matching over node names and aliases, plus a vector search over node descriptions for the cases where the question names something obliquely. A question mentioning "the Shenzhen factory fire" binds to the Incident node for the Longhua fire and, through the incident's own edges, to the Facility node for Building C.

Binding is a real failure surface and it fails quietly. A question that names an entity the corpus never mentions binds to the nearest thing by vector similarity, which might be a different company with a similar name, and the traversal that follows is impeccable and about the wrong entity. A question that names nothing bindable — "what changed in our exposure this quarter" — binds to whatever scores highest against a node description, usually something generic. Both cases are worth detecting explicitly: if the best binding score is below a threshold, or if the top two candidates are within a few points of each other, the right behaviour is to ask which one the user meant or to fall back to flat retrieval, rather than to traverse confidently from a guess.

The quietness has a cause worth stating, because it is the same one every time. Nearest-neighbour search returns a nearest neighbour whenever the store is not empty, and "nearest" is defined even when nothing is close. So an unbindable question and a perfectly bindable one produce the same kind of result — a node, with a score — and the interface downstream cannot tell them apart from the shape of the answer. The threshold and the margin check above are not refinements; they are the only place in the design where the difference becomes visible at all.

Then the traversal runs, bounded. A hop budget, meaning the maximum number of edges a traversal is allowed to follow away from its seeds, is not a nicety; without it a two-hop expansion from a well-connected node in a real corpus returns tens of thousands of nodes, which is a context-window problem and a latency problem at once. A node's degree is the number of edges attached to it, and degree distributions in extracted graphs are heavy-tailed, meaning a small minority of nodes carry a large share of all the edges, so a seed with 40 neighbours and an average neighbour degree of 30 reaches 1,200 nodes at two hops and 36,000 at three, and the nodes with the highest degree are usually the least informative ones — a country, a year, the company itself. Practical systems cap depth at two or three, cap fan-out per node, and prune by edge type so that traversal follows only relations relevant to the question, which is a second place the schema's expressiveness pays off.

Both of those counts are one product with a factor per hop: forty neighbours, each with thirty of their own, is twelve hundred at the second hop, and multiplying by thirty once more is thirty-six thousand at the third. So a hop budget is an exponent and not a limit. Each extra hop multiplies rather than adds, which is why capping depth buys more than any other knob and why the gap between a budget of two and a budget of three is thirty-fold rather than incremental. Two residuals sit under that product. It counts paths and not distinct nodes, so a graph whose neighbourhoods overlap returns fewer nodes than the arithmetic says. And thirty is an average over a heavy-tailed distribution, which means most nodes fall well below it and a few sit far above; the moment a traversal touches one of those hubs the average stops describing what happens, and it stops in the expensive direction.

Written against a property-graph store in Cypher, the pattern-matching query language those stores use, the bounded traversal for the Shenzhen question reads like this.

MATCH path = (f:Facility {id: $seed})<-[:operates]-(c:Company)
             -[s:supplies]->(p:Part)-[:used_in]->(pl:ProductLine)
WHERE s.valid_to IS NULL OR s.valid_to > date($as_of)
RETURN pl.name AS product_line,
       [n IN nodes(path) | n.name] AS via,
       [r IN relationships(path) | {edge: type(r), doc: r.doc_id, quote: r.quote}] AS evidence
LIMIT 200

Two details there repay a second look. The first arrow points backwards — the pattern reads (f:Facility {id: $seed})<-[:operates]-(c:Company) — because the schema declares operates as running from a Company to a Facility, while this traversal starts at the facility and wants the companies operating it. A traversal reads an edge in whichever direction the question needs, and the schema only fixes the direction it was written down in. The second is LIMIT 200, which is the fan-out cap made concrete: the frontier arithmetic above is what arrives if it is left off.

What comes back is the material for the answer, and it is worth noticing what is in the projection. The via list is the chain of intermediate nodes, and the evidence list is, for each edge, the document that asserted it and the sentence it was asserted by. That pair is what a citation over a traversal means. A citation in flat retrieval is straightforward, because the chunk you cite is the chunk the model read. A traversal's answer is not supported by any single document; it is supported by three documents each of which supports one link, and the honest citation is the whole chain.

Aurora handset
  via:  Building C → Hanyu Precision → CN-4471 → Aurora handset
  [1] operates   news/2024-03-longhua-fire.md p1
      "tenants of Building C included Hanyu Precision"
  [2] supplies   contracts/hanyu-precision-2022.pdf p3   valid_to=2023-06-30  ⚠ expired
      "Supplier shall be the exclusive source of Part CN-4471"
  [3] used_in    bom/aurora-mainboard-rev-c.csv row 41

None of that citation is assembled at answer time. Set link 2 against the extraction output earlier in this chapter: the document, the page and the quoted sentence are the evidence object the extractor emitted at ingestion, carried through the store and printed. Two artefacts produced at opposite ends of the system, sharing no step in between, agree line for line, and that agreement is what makes the citation checkable rather than decorative. The residual is exactly what the extractor's word is worth. evidence records the sentence a model said supports the relation, and nothing between ingestion and printing has re-read that sentence to confirm that it does — which is where chapter 4 starts.

The two artefacts do disagree about one thing, and the disagreement is a design decision rather than a defect. The Cypher filters expired edges out, so for any as_of after 2023-06-30 the Hanyu path is not in the result set at all. The trace returns the path and marks it expired. Both behaviours are defensible and they answer different questions: filtering answers "what is exposed now", flagging answers "what would have been reported, and on what grounds it was not". A system that only filters hands a reviewer an answer with a path silently missing from it, and a silently missing path looks exactly like an edge that was never extracted — the same ambiguity chapter 1 raised about a traversal that stops without saying why. The expired flag on link 2 is the payoff for having put valid_to in the schema in the first twenty minutes. A reviewer reading that trace can reject the answer in five seconds. A reviewer reading only the sentence "Aurora and Aurora Lite are exposed through Hanyu Precision" cannot.

The generator then receives the traversal — nodes, edges, evidence quotes — usually alongside the full text of a handful of the source chunks, because the extracted triple is a lossy compression of the document and the model writes better answers when it can read some prose. That hybrid is normal and is not a compromise; the graph decides which text to fetch, and the text is what the answer is written from.

The schema is wrong in two directions#

The way to avoid discovering the ceiling late is to write the schema backwards, starting from twenty real questions from the query log rather than from the domain. Take each question and trace, by hand, the chain of relations that would answer it: fire → tenant → part → product line for the Shenzhen question, and something like customer → contract → entitlement → escalation for a support question. The union of the relation types those traces need is your schema, and the qualifiers the traces depend on — validity dates, sole-source flags, quantities — are the edge properties. Anything the twenty questions never traverse is a node type you are paying to extract and never reading.

That guards against the schema being too small. It does nothing about the other direction, in which the schema will be wrong in ways nobody notices for weeks, because the extractor is helpful. Ask it for supplies edges and it will produce them from sentences that say a company quoted for a part, was considered for a part, or previously supplied a part, since all three are close enough to the type description to look like a match. The graph fills with edges that are individually defensible and collectively misleading.

There is nothing in the node count or the edge count to indicate it, and this is where the earlier point about validation lands. Both counts go up when the extractor is being too generous, in exactly the way they go up when it is being accurate. Neither count, nor the rejection rate beside them, has any access to whether an edge is true, so a build that has quietly filled with quoted for edges looks, on every number a team routinely watches, like a build that went well.

A lossy index over prose#

None of this is a knowledge base in the sense a data-modelling team would mean. Nothing in a pipeline built this way enforces that a Part has exactly one supplier at a time, or that valid_from precedes valid_to, and there is no transaction that fails when a document contradicts an earlier one. It is a lossy, probabilistic index over prose, and treating its contents as facts of record — feeding them into a planning system, exporting them to a compliance report — attributes a reliability to it that extraction cannot supply.

It also does not replace the vector index. Every serious implementation keeps the chunks, keeps the embeddings, and uses them both for binding and for the text handed to the generator. A team that deletes the flat pipeline after standing up the graph has removed the thing that answers the majority of its traffic, since single-hop questions do not stop arriving.

Two properties of the assembled graph are true at once and pull against each other. It is the only structure in which the Shenzhen chain exists as a chain, reachable in a bounded traversal with a document behind every link. It is also a compression of prose, written by a model, against a vocabulary somebody typed into a file in twenty minutes. Every part of the machine above inherits both: a traversal can only walk what extraction emitted, a community summary can only summarise what the clustering could see, and the citation on an answer is the extractor's own note about which sentence it was reading at the time.

That is one of two ways the assembled graph can be quietly wrong. The other is worse, because it survives every schema review: the extraction can be perfect, every edge correct and every relation permitted, and the graph can still return a quarter of the truth. That happens when the same real-world thing arrives under four different names, which is where the next chapter starts.