FINDING NEEDLES · CHAPTER 16

Graphs and structured retrieval

Some answers live in two pages that never mention each other. Search finds pages. A graph finds the link between them.

~13 min read5 town pagesTested Python

What you'll learn

  • Why a question that spans two pages beats ranked search, even with a wider top-k
  • How a page becomes (subject, relation, object) triples, each tagged with its page
  • How walking two edges joins two pages and keeps the citations
  • What community summaries add for questions that name no entity at all
  • When a graph is worth building, and when it is not

Before you start

The answer is a join

A small river town keeps five pages of notes on its bakeries, mills, and suppliers. A visitor asks: “Who grinds the flour for the rye bread?”

No page says it. The bakeries page says rye bread is baked at Hollow Bakery. The suppliers page says Hollow Bakery gets its flour from Weir Mill. You only get “Weir Mill” by reading both pages and noticing that “Hollow Bakery” appears in each.

That shared name is the bridge. The question never says it. So a search that scores pages by the question’s words has no reason to fetch the second page.

Ranked search treats each page alone. Some questions need two facts from two pages, joined on a name. A graph stores those names as nodes and the facts as edges, so the join is already made before anyone asks.

The answer page shares no word with the question

Drop the stop words and the question is four words: grinds, flour, rye, bread. Score each page by how many times those words occur in it. This is cruder than BM25, but BM25 fails here for the same reason.

join · entities · filters · multi-hop

MANIM GraphRAG: joins over entities/relations for multi-hop facts.
PageTextScore
1Bakeries. Rye bread is baked at Hollow Bakery. Seed rolls are baked at Quay Bakery.2
2Suppliers. Hollow Bakery: Weir Mill. Quay Bakery: Bridge Mill. Barge oil: Tolley.0
3Rye bread care. Rye bread keeps for a week. Slice rye bread thin.6
4Market. Tolley grinds spices and sells flour at the Saturday market.2
5Barges. Grain sacks arrive by barge. The barge docks on Monday.0

The ranking is pages 3, 1, 4, 2, 5. A top-3 retriever hands the model pages 3, 1, 4. Page 1 names Hollow Bakery. Nothing it was given says where Hollow Bakery’s flour comes from. The model either says “I don’t know” or, worse, guesses Tolley, because page 4 says Tolley grinds and sells flour.

Dense retrieval does not rescue this. The suppliers page is a list of bakeries and mills. In meaning, it is nowhere near a question about rye bread. The page that answers the question is about something else.

There are two fixes. One is to search again at question time: read page 1, see “Hollow Bakery”, and run a second search for it. That works, at the cost of an extra round trip for every question. This chapter’s fix is to find the bridges once, when you build the index.

Turn each page into small facts

A triple is one fact with three parts: a subject, a relation, and an object. “Rye bread is baked at Hollow Bakery” becomes (rye bread, baked_at, Hollow Bakery). Each triple also remembers the page it came from, so you can cite it later.

SubjectRelationObjectPage
rye breadbaked_atHollow Bakery1
seed rollsbaked_atQuay Bakery1
Hollow Bakeryflour_fromWeir Mill2
Quay Bakeryflour_fromBridge Mill2
barge oilsold_byTolley2
Tolleytrades_atSaturday market4
grain sacksarrive_bybarge5
bargedocks_onMonday5

These eight triples were written by hand for this chapter. A real pipeline asks a language model, or an entity tagger plus a relation classifier, to propose them for every chunk. That step is the expensive one, and the noisy one.

Every distinct subject or object becomes a node. Every triple becomes a directed edge. Eight triples give 12 nodes and 8 edges. Page 3 adds none: “Rye bread keeps for a week” has no second entity here worth linking.

Notice what made the bridge: “Hollow Bakery” is spelled the same way on pages 1 and 2, so both triples land on one node. If page 2 had said “the bakery on Hollow Lane”, you would get two nodes and no path. Merging names that mean the same thing is called entity resolution. It is most of the real work.

Two hops, two pages, one answer

Answering now means turning the question into a path: start at the node the question names, then follow named relations.

rye breadHollow BakeryWeir Mill seed rollsQuay BakeryBridge Mill barge oilTolleySaturday market grain sacksbargeMonday baked_at · p1flour_from · p2 baked_at · p1flour_from · p2 sold_by · p2trades_at · p4 arrive_by · p5docks_on · p5
The town notes as a graph: 12 nodes, 8 edges. The question walks the top row.

start at the thing the question names, follow one named edge per hop, and stop where the path ends. Each arrow carries the page it was read from.

  1. Plan the path. “Who grinds the flour for the rye bread?” names one entity, rye bread, and asks for whoever supplies its flour. The path is baked_at, then flour_from. In a real system a language model writes this plan, or writes a graph query in a language such as Cypher.
  2. Hop 1. From rye bread, follow baked_at. You land on Hollow Bakery. The edge came from page 1.
  3. Hop 2. From Hollow Bakery, follow flour_from. You land on Weir Mill. The edge came from page 2.
  4. Generate. Hand pages 1 and 2 to the model as numbered sources. It can now write “Weir Mill grinds the flour for the rye bread [1][2]”, and both citations are real.

Compare the two contexts. Keyword top-3 gave pages 3, 1, 4. The walk gave pages 1 and 2. The walk used fewer pages and got the one the ranking left out.

The same path from seed rolls lands on Bridge Mill, again using pages 1 and 2. The plan, not the data, is what changed.

Rank, build, walk, group

Standard library only. The ranking, the graph, the two-hop walk, and the groups used in the next section are all in one file.

graph.pywalk → Weir Mill via pages 1, 2
"""Graph retrieval on five pages about a river town's bakeries and mills.

Keyword search ranks pages by the question's words. The answer page
shares none of them. A small graph of hand-extracted triples joins the
two pages by walking edges instead.
"""

# Five town pages. Ids match the table on the page.
DOCS = {
    1: "Bakeries. Rye bread is baked at Hollow Bakery. Seed rolls are baked at Quay Bakery.",
    2: "Suppliers. Hollow Bakery: Weir Mill. Quay Bakery: Bridge Mill. Barge oil: Tolley.",
    3: "Rye bread care. Rye bread keeps for a week. Slice rye bread thin.",
    4: "Market. Tolley grinds spices and sells flour at the Saturday market.",
    5: "Barges. Grain sacks arrive by barge. The barge docks on Monday.",
}

QUESTION = "Who grinds the flour for the rye bread?"

STOP = {"who", "the", "for", "a", "at", "and", "is", "are", "on", "by"}


def words(text):
    """Lowercase words, punctuation dropped, stop words removed."""
    cleaned = "".join(ch if ch.isalnum() else " " for ch in text.lower())
    return [w for w in cleaned.split() if w not in STOP]


def keyword_rank(question=QUESTION):
    """Score = how many times the question's words occur in the page."""
    terms = set(words(question))
    scores = {d: sum(w in terms for w in words(t)) for d, t in DOCS.items()}
    return sorted(scores.items(), key=lambda item: (-item[1], item[0]))


# (subject, relation, object, page it came from). Written by hand here;
# a real pipeline asks an LLM or an entity tagger to propose these.
TRIPLES = [
    ("rye bread", "baked_at", "Hollow Bakery", 1),
    ("seed rolls", "baked_at", "Quay Bakery", 1),
    ("Hollow Bakery", "flour_from", "Weir Mill", 2),
    ("Quay Bakery", "flour_from", "Bridge Mill", 2),
    ("barge oil", "sold_by", "Tolley", 2),
    ("Tolley", "trades_at", "Saturday market", 4),
    ("grain sacks", "arrive_by", "barge", 5),
    ("barge", "docks_on", "Monday", 5),
]


def build_graph(triples=TRIPLES):
    """Adjacency list: node -> [(relation, neighbour, page), ...]."""
    graph = {}
    for subj, rel, obj, page in triples:
        graph.setdefault(subj, []).append((rel, obj, page))
        graph.setdefault(obj, [])
    return graph


def walk(start, relations, graph=None):
    """Follow one named edge per hop. Return the end node and the pages used."""
    graph = graph or build_graph()
    node, path, pages = start, [start], []
    for rel in relations:
        hop = [(obj, page) for r, obj, page in graph[node] if r == rel]
        if not hop:
            return None, path, pages
        node, page = hop[0]
        path.append(node)
        pages.append(page)
    return node, path, pages


def communities(graph=None):
    """Connected groups of nodes, ignoring edge direction."""
    graph = graph or build_graph()
    links = {n: set() for n in graph}
    for subj, edges in graph.items():
        for _, obj, _ in edges:
            links[subj].add(obj)
            links[obj].add(subj)
    seen, groups = set(), []
    for start in graph:
        if start in seen:
            continue
        group, stack = [], [start]
        seen.add(start)
        while stack:
            node = stack.pop()
            group.append(node)
            for nxt in links[node] - seen:
                seen.add(nxt)
                stack.append(nxt)
        groups.append(sorted(group))
    return groups


if __name__ == "__main__":
    print(keyword_rank())  # [(3, 6), (1, 2), (4, 2), (2, 0), (5, 0)]
    print(walk("rye bread", ["baked_at", "flour_from"]))  # Weir Mill, pages [1, 2]
    print(communities())  # four groups of three

A missing edge stops the walk and returns None. That is a feature. If flour_from is missing for a bakery, the system can say “no supplier is listed” instead of guessing.

Questions that name no entity

Now ask: “What are the main trades in this town?” There is no start node. No single page answers it. Retrieving the top few pages gives a sample, not a summary.

GraphRAG handles this kind of question ahead of time. It splits the graph into communities: groups of nodes linked more to each other than to the rest. It asks a language model to write a short summary of each community. A broad question is then answered from those summaries: one partial answer per community, then one combined answer.

The town graph is small enough that its communities are simply its connected pieces. Ignore edge direction and you get 4 groups of 3 nodes.

GroupNodesA summary a model might write
1rye bread, Hollow Bakery, Weir MillHollow Bakery bakes the rye bread with flour from Weir Mill.
2seed rolls, Quay Bakery, Bridge MillQuay Bakery bakes the seed rolls with flour from Bridge Mill.
3barge oil, Tolley, Saturday marketTolley sells barge oil and trades at the Saturday market.
4grain sacks, barge, MondayGrain arrives by barge, which docks on Mondays.

Four lines now cover the whole town. The summaries above are written by hand. On a real corpus with thousands of nodes, connected pieces are useless, because almost everything ends up linked to everything. GraphRAG uses the Leiden algorithm instead, which finds tightly knit groups inside one big connected graph, at several levels of detail.

A graph is an index you pay for up front

Worth it

Questions that join facts across pages: who, which, supplied by, part of, depends on. Corpora full of named things that repeat across documents. Broad “what are the themes” questions over a large collection.

Not worth it

Answers that sit in one passage. Corpora that change every hour, because extraction must re-run. Prose where the meaning is in the explanation, not in who-relates-to-what. Start with hybrid search and add the graph when questions keep failing on joins.

Most systems that use a graph also keep the ordinary text index. The graph finds the pages and the bridges. The text gives the model the full sentences to quote.

Deep dive · When the facts are already a table

If the town kept its supplier list in a spreadsheet, you would not need to extract anything. The rows are the triples. A question like “how many bakeries does each mill supply?” is a group-by and a count, and an exact query beats any retrieval.

Text-to-SQL is that route: give a language model the table schema, have it write a query, run the query with a read-only account, and let the model phrase the rows as an answer. The hard parts are naming (which of three date columns did the user mean?) and safety (treat the generated query as untrusted input, with timeouts and row limits).

Mistakes learners make

Fixing a join problem with a bigger top-k. Raising k from 3 to 4 fetches page 2 here only by luck of the ties. On a real corpus the bridge page can sit at rank 400. Wider is not the same as connected.

Skipping entity resolution. “Hollow Bakery”, “hollow bakery”, and “the bakery on Hollow Lane” must be one node. Without that merge, the edge from page 1 and the edge from page 2 never meet, and the walk stops after one hop.

Dropping the page on each triple. A graph that only stores (Hollow Bakery, flour_from, Weir Mill) can answer, but cannot cite. Keep the source page on every edge so the answer can point back to text a person can check.

Trusting extracted edges as facts. A model that extracts triples will sometimes invent one, or flip its direction. A wrong edge gives a confident, wrong, well-cited answer. Spot-check extraction like you would grade retrieval.

What to remember

  • “Who grinds the flour for the rye bread?” needs pages 1 and 2. Keyword ranking gives 3, 1, 4, 2, 5, and the answer page scores 0.
  • A triple is (subject, relation, object) plus its source page. Eight triples make 12 nodes and 8 edges.
  • The walk rye bread → Hollow Bakery → Weir Mill uses pages 1 and 2, and both become citations.
  • Communities plus summaries answer broad questions. Here: 4 groups of 3 nodes.
  • Build a graph when questions fail on joins, not by default.

Check yourself

1. Why does page 2 score 0 for the question?

It contains none of grinds, flour, rye, or bread. It only lists bakeries and mills. The link to rye bread is on page 1.

2. Page 4 contains “grinds” and “flour”. Why is it a dangerous page to hand the model?

It says Tolley grinds and sells flour. A model with pages 3, 1, 4 and no supplier list may stitch that into “Tolley grinds the flour for the rye bread”, which is wrong.

3. Page 2 said “the bakery on Hollow Lane: Weir Mill” instead. What breaks?

Without entity resolution, “the bakery on Hollow Lane” becomes its own node. The walk reaches Hollow Bakery, finds no flour_from edge, and stops with no answer.

4. How is a two-hop walk different from searching again at question time?

Both join two pages. Searching again finds the bridge while the user waits, with a second search. The graph found it at index time, so the walk is a lookup.

5. Why can’t you start a walk for “What are the main trades in this town?”

It names no entity, so there is no start node. Pre-written community summaries answer it instead.

Go to the source

Keep going