Topic 12.4
Retrieval over a Graph
In one line
Some questions need facts that sit in different passages and are connected by who or what they mention. Extract entities and relations into a graph, then follow the links hop by hop to collect the passages a chain of facts needs.
Think of it like this
A family tree. To answer "who is Maria's cousin's boss?" you do not search for a page with those words. You start at Maria and walk along lines: to her aunt, to the aunt's child, to that child's employer. Each step is a fact, and the answer is the end of the walk.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Knowledge graph
- Facts stored as nodes and the relations between them.
- Triple
- One fact as (subject, relation, object), for example (Maria, manages, Harbour shop).
- Entity
- A named thing in the text: a person, a shop, a product.
- Multi-hop question
- A question whose answer needs several facts joined together, not one passage.
- Hop
- One step along an edge from one node to the next.
- Entity resolution
- Deciding that different spellings or mentions refer to the same entity.
- Community summary
- In GraphRAG, a summary of a group of closely connected nodes.
Step by step
01Step 1: a question no passage answers alone
"Does the shop Maria manages have a charging station?" needs three facts from three sentences. Searching for the question returns the sentence about Maria managing the shop, and then the chain stops.
02Step 2: turn sentences into triples
Match a few fixed patterns. Each match gives a triple. Sentences that match nothing are reported, not dropped silently, so you can see what the extractor missed.
RELATIONS = [(" manages the ", "manages"), (" is in ", "is_in"), (" has a ", "has")]
def extract(sentence):
text = sentence.rstrip(".")
for marker, name in RELATIONS:
if marker in text:
left, right = text.split(marker, 1)
return (left, name, right)
return None03Step 3: read what was extracted
Five triples from six sentences. The sentence about Priya was skipped, so the graph has no node for her. That one line of output is the whole case for evaluating extraction.
04Step 4: walk the links
Start at the node named in the question. At each hop, follow every edge out of the nodes reached in the last hop, and remember the nodes you have seen. Stop at a hop limit.
05Step 5: see the effect of the hop limit
With one hop the walk finds only the shop. With three hops it reaches the charging station. Too few hops and the chain is cut. Too many and the walk collects unrelated facts, so choose the smallest limit that your questions need.
06Step 6: go back to the text
The facts are only a map. Collect the chunks the walked edges came from and give those chunks to the model, so it answers from sentences you can cite.
Try it yourself
- 1
Fix the missing link
In the first example add
(" looks after the ", "manages")to the relations list. Run again: how many triples now? What does that say about maintaining extraction rules? - 2
Walk from Dev
In the second example change the start to
"Dev"and the limit to 2. Which facts are found? Which of Maria's facts must stay out? - 3
Make a loop
Add the triple
("Eastgate", "near", "Hilltop shop"), change the start to"Dev"and run with a limit of 5. Eastgate now points back to a shop the walk already visited. Why does the walk still stop, and which line of code makes that true?
Code & diagrams
Fixed phrase patterns stand in for a model extractor. Note the skipped sentence: a missed pattern is a missing link, and nothing fails loudly.
Expected output
(Maria) -manages-> (Harbour shop)
(Harbour shop) -is_in-> (Northside)
(Northside) -has-> (charging station)
(Dev) -manages-> (Hilltop shop)
(Hilltop shop) -is_in-> (Eastgate)
skipped: Priya looks after the Docks shop.
5 triples from 6 sentencesA breadth-first walk with a seen-set and a hop limit. Change the start to Dev and the limit to 2.
Expected output
start at Maria, up to 1 hop(s)
hop 1: Maria -manages-> Harbour shop
start at Maria, up to 3 hop(s)
hop 1: Maria -manages-> Harbour shop
hop 2: Harbour shop -is_in-> Northside
hop 3: Northside -has-> charging stationBreak it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Forget the seen-set
In the Python tab of the second example, change and right not in seen to nothing: replace if left == node and right not in seen: with if left == node:, and add the triple ("Northside", "near", "Harbour shop") at the end of TRIPLES. Run.
Myth vs fact
Myth
A knowledge graph replaces vector search.
Fact
A graph answers relationship questions. Vectors and keywords find passages by meaning and words. Most systems use the graph to add passages to what search found.
Myth
A model can extract a perfect graph.
Fact
Extraction misses facts, merges different entities and invents relations. Measure it on a sample before building on it.
Myth
More hops give more complete answers.
Fact
More hops add unrelated facts and more chances for an extraction error to join the wrong things.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Store with every edge the id of the chunk it came from and, if you can, the sentence. Without provenance you cannot cite or delete (Topic 10.6): when a document is removed, its edges must go too.
- ▸
Evaluate extraction separately: take 50 chunks, list the true triples by hand, and measure how many the extractor found and how many it invented. A graph built on a poor extractor looks authoritative and is wrong.
- ▸
Cap the fan-out. A node such as "the company" connects to thousands of others, and walking all of them floods the prompt. Skip hub nodes or keep only the top few edges by relevance to the question.
Remember this
- 1
Why this exists. Ordinary search compares a question with passages one at a time. A multi-hop question needs two or more facts that are written in different places, joined by a shared name: "Does the shop Maria manages have a charging station?" One passage says Maria manages the Harbour shop, another says the Harbour shop is in Northside, a third says Northside has a charging station. No single passage matches the question, and the first search finds only the first fact.
- 2
Triples. A graph is stored as triples: (subject, relation, object), such as (Harbour shop, is_in, Northside). The things are nodes (also called entities) and the relations are the edges. Getting triples from text is called extraction. The example does it with fixed phrases so it runs anywhere. A real system asks a model to read each chunk and list its triples, which is far more flexible and far less exact.
- 3
Following links. Starting from the entity in the question, take every edge out of it, then every edge out of those nodes, up to a limit of hops. Keep a set of nodes already seen, or a loop in the data makes the walk run for ever. Each edge remembers the chunk it came from, so the answer can cite real passages and not only the graph.
- 4
Where it goes wrong. Extraction is the weak point. The sentence "Priya looks after the Docks shop" meant the same as "manages" but matched no rule, so it was skipped and nothing about Priya can be found. A model extractor may merge two people with the same name, split one entity into two spellings, or invent a relation. Every error silently cuts a link in the chain. Entity resolution (deciding that "Harbour shop" and "the Harbour branch" are one node) is a large part of the real work.
- 5
Named methods. GraphRAG (Edge et al., Microsoft, 2024) builds a graph from the documents, groups related nodes into communities, writes a summary for each community, and answers broad questions by combining those summaries. That is the Topic 12.2 idea of summaries applied to a graph. Treat it as a family of ideas to evaluate, not a setting to switch on.
- 6
When a graph earns its upkeep. A graph needs an extraction pipeline, a place to store it, updates when documents change, and evaluation of the extraction itself. It pays off when your questions are about relationships and chains, over data where the same entities appear in many documents (people, products, parts, accounts). If most questions are answered by one passage, a graph is a cost with no return. Start with better chunks, hybrid search and query rewriting first.
Explain it without notes
What is a multi-hop question, and why does ordinary chunk search handle it badly?
Describe how a graph is built from text and how a question uses it.
What goes wrong with extraction, and how would you notice?
When would you decide a graph is not worth building?
Practice
Write neighbours(node, triples) that returns a list of (relation, other) pairs for every triple whose left side is node, in the order they appear. Print the neighbours of Harbour shop and of Northside.
Write hops_between(start, goal, triples, max_hops) that follows outgoing links breadth first and returns the number of hops needed to reach goal, or None if it takes more than max_hops. Print the result for Maria to "charging station" with limits 2 and 3.
Trade-offs
- ↔
A graph answers chains of facts that chunk search cannot, and adds an extraction pipeline, storage and updates.
- ↔
Rule-based extraction: predictable and incomplete. Model-based extraction: flexible and sometimes wrong.
- ↔
Few hops: precise and may cut the chain. Many hops: complete and noisy.
Done when you can
Done when you can write a triple and say what a node, an edge and a hop are.
Done when you can walk a graph with a seen-set and a hop limit.
Done when you can say what extraction gets wrong and how to measure it.
Done when you can say when not to build a graph.