Chapter 10: GraphRAG on a Vector Store
Time: 40 minutes. Cost: $0. The lab uses a new, smaller collection of 1,000 multi-hop questions, which you build once in about a minute and a half with Ollama. The lab itself runs in under a minute on one CPU core. Part 4 uses the Chapter 7 database in Docker; the rest does not.
- Some questions need two paragraphs, where the first one names the thing the second one is about. Search cannot find the second, because it has almost nothing in common with the question.
- A simple graph fixes much of it: link each paragraph to the paragraphs it mentions by name, then follow those links from the top search results. It fits in an ordinary database table.
- Links only help when the first search was right, and they take room from search results. Measure on your own questions before you build anything bigger.
Here is a question from the lab:
The director of the romantic comedy "Big Stone Gap" is based in what New York city?
Vector search does the first part well. Out of 9,769 Wikipedia paragraphs, the one about the film Big Stone Gap comes back first. It says the film was written and directed by Adriana Trigiani. It does not say where she lives.
That fact is in a different paragraph, the one about Adriana Trigiani: an author and director "based in Greenwich Village, New York City." Vector search ranked that paragraph 238th. A language model handed the top 5 would see the film, two other romantic comedies, and nothing about Trigiani. It would either guess or say it does not know.
Nothing went wrong with the search. It did exactly what it was built to do: find paragraphs that are about what the question is about. The question is about a film. The answer is in a paragraph about a person the question never names. You cannot get there by measuring distance from the question. You have to read the first paragraph, notice the name, and look that up. That is a two-hop question, and this chapter is about the second hop.
Why one search cannot do it​
Every search in this track compares the question with each paragraph, one at a time. Embeddings, BM25, and the reranker from Chapter 9 all work that way. The Trigiani paragraph has almost nothing in common with the question. It never mentions Big Stone Gap, film, or romance. The one thing that connects them, the name "Adriana Trigiani," is in the other paragraph.
Chapter 9 already showed why a reranker cannot rescue this. A reranker only reorders what the first stage found, and the first stage did not find it. Hybrid search does a little better, because "New York" is a keyword the Trigiani paragraph shares with the question, but it still ranked her 10th.
What is missing is a connection between the two paragraphs, not between the question and either one of them. That connection has a name: a link in a graph.
A graph is a list of links​
A graph is two lists. One list is the things, called nodes. The other is the connections between them, called edges or links. A road map is a graph: towns are nodes, roads are links. So is Wikipedia: pages are nodes, and every link from one page to another is an edge.
HotpotQA, the dataset this lab uses, was built from that second graph. For its two-hop questions, its authors took pairs of Wikipedia articles where the first article's opening paragraph links to the second, showed crowd workers both paragraphs, and asked them to write a question that needs both. The full dataset has about 113,000 questions. The lab uses the first 1,000 from its development set: 807 two-hop questions, and 193 comparison questions such as "Were Scott Derrickson and Ed Wood of the same nationality?", which name two things and need a paragraph about each.
The lab does not use Wikipedia's real links. It builds its own graph from the text, the way you would for your own documents. Every paragraph opens a Wikipedia page, so its title is the name of what it is about: a person, a film, a band. If one paragraph mentions another paragraph's name, it gets a link to that paragraph.
PART 1: a graph over 9,769 paragraphs, built in 0.4 s
9,569 names, 10,798 links
5,785 paragraphs mention at least one other paragraph's name
For example, 'Big Stone Gap (film)' links to: Adriana Trigiani, Donna Gigliotti
Most linked to:
1,003 United States (disambiguation)
1,003 United States
188 1989 (Taylor Swift album)
142 Army (Ellie Goulding song)
87 Life (1999 film)
The graph is noisy, and I left that in the output on purpose. Every paragraph that mentions 1989 now links to a Taylor Swift album. Every paragraph that says "Army" links to a song. Plain string matching does not know what a name means. It is still useful: for 85% of the two-hop questions, one of the two paragraphs they need mentions the other by name.
Do not expect that number on your own documents. HotpotQA built every two-hop question from a link between its two paragraphs, so a mention was there by design. In the other 15%, the first paragraph refers to the second in words that the lab's plain string matching does not catch.
Following the links​
The idea is simple. Search as usual. Take the top few results, call them seeds, and add the paragraphs they link to.
Here is the lab's version, keeping the top 3 search results as seeds and filling the other two places with linked paragraphs, best search score first:
Vector search, then the links from its top 3:
1. Big Stone Gap (film) <- needed
2. I Love NY (2015 film)
3. Chalet Girl
4. Donna Gigliotti (link)
5. Adriana Trigiani (link) <- needed
Answer in the top 5: without links False, with links True
Trigiani moved from 238th to 5th. The language model now has both halves of the answer.
What the links buy, on 1,000 questions​
One good example proves nothing, so the lab runs every question five ways and keeps the top 5 each time. Both found is how often both paragraphs a question needs made the top 5. Answer in is a rougher check: does the answer's exact text appear anywhere in those 5 paragraphs?
PART 3: 1,000 questions, top 5 paragraphs kept
two-hop (807) comparison (193)
method both found answer in both found
vector 0.18 0.51 0.05
vector + links 0.29 0.55 0.05
hybrid (Chapter 8) 0.55 0.73 0.70
hybrid + links 0.77 0.88 0.67
hybrid + names + links 0.83 0.89 0.99
I see four things in that table.
Links help two-hop questions a lot, once the first hop is right. On hybrid search, both paragraphs made the top 5 for 77% of two-hop questions with links, against 55% without. The answer text was there 88% of the time instead of 73%.
Links cannot fix a bad first hop. On plain vector search, they only moved both-found from 0.18 to 0.29. You can only follow links from paragraphs you found. This is Chapter 9's ceiling again, one hop earlier. Vector search is especially weak on this dataset because so many questions turn on names, and Chapter 8 showed that names are exactly where embeddings struggle. Fix the first stage before you add a graph.
Links do not help comparison questions. They went from 0.70 to 0.67. "Were Scott Derrickson and Ed Wood of the same nationality?" names both people already. There is no hidden second hop to follow, and the linked paragraphs just take places away from search results.
Looking up names in the question does help them. The last row checks the question itself for paragraph names, and starts from those paragraphs before the search results. Comparison questions went to 0.99, and two-hop questions to 0.83. That is not really search. It is a lookup in a list of names, the cheapest part of the whole graph. It is also close to how Microsoft's GraphRAG does what it calls local search: start from the entities most related to the question.
Before you expect numbers like these on your own documents, know three things that make this dataset easy for a graph. Every two-hop question was built from a link, as you saw above. Every paragraph has a clean title, the same name people write in questions, so looking names up rarely misses. And the collection is small and friendly. It pools the 10 paragraphs HotpotQA supplied with each question, 2 that it needs and 8 look-alikes, so the right paragraphs are always somewhere in it. HotpotQA's harder setting searches the opening paragraphs of all of Wikipedia, about 5 million of them. Real documents have messier names and fewer links, so treat 0.83 and 0.99 as a best case, not a forecast.
Links compete for space​
The top 5 is a fixed budget, and every place you give a link is a place you take from search. In the lab's Try this section, following links from all five search results instead of three leaves no room for any link at all, and every number goes back to the row without links. Keeping 10 paragraphs instead of 5 gives search more room too: plain hybrid search then finds both paragraphs 74% of the time, and links raise that to 87%. The gap shrinks, but it does not close.
So the graph is not free even when it is cheap to build. It earns its place on questions that hide a second hop. On questions that do not, it costs you a few slots of context. If I knew most of my users' questions were simple lookups, I would follow links from fewer seeds or only when the first search looks weak.
The graph is just another table​
You do not need a graph database to store this. A link is two numbers, the paragraph it starts from and the one it points to. Lab Part 4 puts them in a PostgreSQL table next to the vectors from Chapter 7:
CREATE TABLE hotpot_links (
source_id integer REFERENCES hotpot_paragraphs,
target_id integer REFERENCES hotpot_paragraphs,
PRIMARY KEY (source_id, target_id)
);
Following the links from the seeds is one join:
WITH seeds AS (
SELECT id, embedding <=> %(vector)s AS distance
FROM hotpot_paragraphs
ORDER BY embedding <=> %(vector)s
LIMIT 3
),
linked AS (
SELECT DISTINCT target.id, target.embedding <=> %(vector)s AS distance
FROM seeds
JOIN hotpot_links link ON link.source_id = seeds.id
JOIN hotpot_paragraphs target ON target.id = link.target_id
WHERE target.id NOT IN (SELECT id FROM seeds)
)
SELECT id, found_by FROM (
SELECT id, distance, 1 AS step, 'vector' AS found_by FROM seeds
UNION ALL
SELECT id, distance, 2, 'link' FROM linked
) results
ORDER BY step, distance
LIMIT %(top)s
Same top 5 as Part 3's 'vector + links' for 1,000 of 1,000 questions
Vector search alone: 10.7 ms per question. With the links: 11.0 ms.
The SQL returned the same top 5 as the Python version for every question. Following the links cost so
little that it disappears in the noise: on my next run, the two numbers swapped places. PostgreSQL's
EXPLAIN ANALYZE put the join at under a tenth of a millisecond. Almost all the time is the vector
search, which here scans every row, because a table this small does not need an index. The join uses
the links table's primary key, so it stays fast as the table grows.
For more than one hop, PostgreSQL has long supported WITH RECURSIVE queries. The lab's
README has one that walks two links out from a paragraph. If you want a real graph query language
inside PostgreSQL, the Apache AGE extension adds Cypher, the graph query language that came from
Neo4j.
I would keep the graph in the database I already run, as long as the job is a hop or two from a handful of seeds. I would look at a dedicated graph database when the graph itself is the product: traversals many links deep, graph algorithms such as shortest paths or community detection, or a team that thinks and queries in graphs every day. Graph databases have moved toward vectors from the other side, too. Neo4j, the best-known graph database, added a vector index in 2023.
Index graph or knowledge graph​
People use "knowledge graph" for two quite different things, and it helps to keep them apart.
The graph in this lab is an index graph. It was built automatically, to help retrieval, from the documents themselves. Its links have no meaning beyond "mentions." It is noisy, and that is acceptable, because it only decides what to look at. The paragraphs are still the source of truth, and you can throw the graph away and rebuild it whenever the documents change.
A knowledge graph is a curated model of the world. Its links have types, such as "directed by" or "born in," and people or careful pipelines maintain them. The graph itself is the source of truth. Google introduced its Knowledge Graph in May 2012 under the phrase "things, not strings," and it powers the fact panels beside search results. If your company already has something like that, a product catalog with parts and suppliers or an org chart, it can supply the names and links for retrieval directly.
Most GraphRAG systems build the first kind and describe it in the language of the second. That is fine, as long as nobody starts treating automatically extracted links as facts.
Where the names come from​
The lab got its names for free, because every Wikipedia paragraph has a title. Your documents may not have that, so here is how I would think about it.
Start with the names you already have. Most companies keep lists of the things their documents talk about: product names, customer names, employee names, ticket numbers, part numbers, error codes. String matching against those lists is what the lab did, and it costs nothing to run.
If you have no list, extract one. An entity extraction model can find people, places, and organizations in text cheaply. A language model can do more: read each chunk and write down the entities and how they relate. That is much more flexible, and it costs one language model call for every chunk, every time you re-index.
Microsoft GraphRAG​
That last approach is what made "GraphRAG" a common term. Microsoft Research published it in 2024 and released the code.
It uses a language model to extract entities, relationships, and claims from every chunk of text. It then groups closely connected entities into communities, and has the language model write a summary of each community. Think of a town: group the residents into neighborhoods, then write one page about what is going on in each neighborhood.
Those summaries are aimed at a different kind of question from the lab's. The paper's target is a global question about a whole collection, such as "What are the main themes in the dataset?" That is like asking what people in the town are worried about. No single resident's diary answers it, so similarity search has nothing good to return. GraphRAG answers it by asking the language model about every community summary and combining the partial answers.
The paper tested this on two collections of about 1 million tokens each, podcast transcripts and news articles, with GPT-4. A language model judged the answers. Against plain vector RAG, the global approach was preferred for comprehensiveness 72% to 83% of the time, and for diversity 62% to 82% of the time, depending on the collection and settings. That is a real result, with two qualifiers worth keeping: the judge was a language model, and the questions had no single correct answer.
The catch is the indexing cost: language model calls over every chunk, plus summaries. Microsoft's own follow-up, LazyGraphRAG, defers that work until query time and reported indexing costs identical to vector RAG and 0.1% of full GraphRAG's.
Graphs are not the only way to the second hop. HippoRAG builds a graph with a language model and spreads a score outward from the question's entities through the links, a cousin of the PageRank method Google used to rank web pages. IRCoT skips the graph entirely and lets the model search again based on what it has reasoned so far. Search once, read "Adriana Trigiani," search for her. That works with no index at all, and it costs a language model call per hop, at query time, for every question. Advanced Chapter 2 builds a simple version of it.
My recommendation follows the evidence in this chapter. If your questions have a hidden second hop and you have names, build the cheap graph: a links table next to your vectors. If you have no names, extract entities, and measure whether the gain pays for the extraction. Reach for community summaries only if your users really ask whole-collection questions. And measure on your own questions first, because on one-hop questions a graph mostly takes space.
Where this came from: HotpotQA, GraphRAG, and the alternatives
HotpotQA was published by Zhilin Yang, Peng Qi, Saizheng Zhang, and colleagues at EMNLP in 2018.
Microsoft Research described GraphRAG in a blog post in February 2024 and in a paper by Darren Edge and colleagues in April 2024, "From Local to Global: A Graph RAG Approach to Query-Focused Summarization." They released the code that July. It finds communities with a community detection algorithm such as Leiden. LazyGraphRAG was announced in November 2024.
HippoRAG was presented at NeurIPS 2024 and uses Personalized PageRank. IRCoT is from ACL 2023.
PostgreSQL has supported WITH RECURSIVE since version 8.4 in 2009. Neo4j added a vector index as a
beta in version 5.11 in 2023 and made it generally available in 5.13 later that year.
Hands-on lab: follow the links​
You will build the name graph, follow links for the Big Stone Gap question, measure all five methods on 1,000 questions, and run the same search as one SQL query with the graph as a table.
Full instructions: download the
Vector Databases labs ZIP. First build the
multi-hop dataset by following the "Multi-hop dataset" section of labs/vector-databases/dataset/README.md.
Then open labs/vector-databases/10-graphrag and follow its README.
The output is the tables in this chapter. Parts 1 to 3 should match exactly if you built the dataset with Ollama. Part 4's timings depend on your machine.
Checkpoint​
Vector search ranked the Adriana Trigiani paragraph 238th. Why would a better embedding model probably not fix that?
The paragraph is about a different subject from the question. It never mentions Big Stone Gap, and the question never mentions Trigiani. Any search that compares the question with one paragraph at a time has nothing to match. The connection is inside the film's paragraph, and only following that mention finds it.
Links raised "both found" from 0.55 to 0.77 on hybrid search, but only from 0.18 to 0.29 on vector search. Why the difference?
Links can only be followed from the seeds. Hybrid search put the first paragraph among its top 3 far more often than vector search did. When the first hop is wrong, the links point to the wrong places.
What is the difference between the graph in this lab and a knowledge graph?
The lab's graph is an index graph: built automatically from the documents to help retrieval, with untyped "mentions" links and some noise. A knowledge graph is curated, its links have types such as "directed by," and it is itself the source of truth.
Check Your Knowledge​
Click to start the quiz
What's next​
You now have every piece: vector search, keyword search, fusion, a reranker, and a graph, each measured on its own. Chapter 11 puts them into one retrieval stack, measures what each stage adds on the same questions, and gives you a browser page to inspect every stage for any question you type.