GraphRAG

GraphRAG (Edge et al., Microsoft, 2024) has an LLM extract an entity graph from the corpus, clusters it into Leiden communities and pre-summarises each; global questions map-reduce over the summaries, local ones fan out from matched entities.

8 min read831 wordsadvanced0 viewsupdated 2026-10-21

Definition

GraphRAG is retrieval-augmented generation over a knowledge graph that an LLM builds from the corpus itself. The reference design is Edge et al., "From Local to Global: A Graph RAG Approach to Query-Focused Summarization" (Microsoft Research, 2024). An LLM extracts entities, relationships and claims from every chunk. The resulting graph is partitioned into a hierarchy of communities with the Leiden algorithm (Traag, Waltman and van Eck, 2019), and the LLM writes a report for each community. Queries are answered from those reports (global search) or from the neighbourhood of matched entities (local search).

Vector RAG answers questions whose answer sits in a few chunks (see RAG architecture). It fails on sensemaking questions over a whole corpus, such as "What are the main themes in these 2,000 news articles?". No top-kk set of chunks contains that answer: it is spread thinly across everything, and the chunks most similar to the question are not the most representative. The paper frames this as query-focused summarisation, and GraphRAG does the summarising in advance, at indexing time.

The second gain is multi-hop structure. An edge such as "Water Board orders rationing" joins facts that appear in different chunks, so a question about an entity can follow relationships instead of hoping each hop is in the top kk. Graph-learning methods for such graphs are covered in Knowledge graph embeddings; GraphRAG uses the graph for retrieval and summarisation, with no trained graph model.

Indexing

From documents to community reports

  1. 1Text units. Split documents into chunks; the paper used 600-token chunks with 100-token overlap.
  2. 2Extraction. For each chunk an LLM lists entities (name, type, description), relationships (source, target, description, strength) and optionally claims. Extra "gleaning" rounds ask the model whether it missed any, which recovers more entities from long chunks.
  3. 3Graph. Entities with the same name are merged and their descriptions summarised; relationship counts become edge weights.
  4. 4Communities. Leiden is run recursively, giving levels C0 (root, few large communities) down to leaf communities.
  5. 5Reports. For each community an LLM writes a report (title, summary, key findings, an impact rating) from its entities, edges and claims; higher levels can summarise their sub-communities' reports.
INDEXING (offline, LLM calls per chunk and per community)text units600-tokenchunks with100 overlape.g. 87 chunksLLM extraction"Water Board ordersrationing as theReservoir falls"→ WaterBrd (org)→ Rationing (event)→ orders, w = 2entity graphWaterBrdRationingReservoirOrtiz30 entities, 47 edgesLeiden hierarchyC0 (root): 5C1: 9 nestedhigh modularity:dense inside,sparse betweencommunity reportsLLM summary each:title: Water crisissummary: drought cutthe Reservoir; Boardordered rationingfindings + ratingQUERY TIMEglobal search (map-reduce over C0 reports)Q: "What are the main issues in the city?"map: report → partial answer, score 0–100water85transit70schools60election40health0reduce: drop 0s, sort by score, fill the context→ one answer covering water, transit,schools and the electionlocal search (entity fan-out)Q: "What did the Water Board decide?"1. match entities by embedding: WaterBrd2. neighbours: Rationing, Pipes, Reservoir, Dam, Ortiz3. their relationships + claims4. reports of WaterBrd's communities5. source text units that mention it→ ranked, packed into one promptreports answer corpus-wide questions that no single top-k chunk set contains; local search keeps chunk-level detail
fig.Top: indexing. A 600-token chunk such as "Water Board orders rationing as the Reservoir falls" yields entities WaterBrd and Rationing and an "orders" edge; all chunks together give a graph of 30 entities and 47 weighted edges in the toy corpus. Leiden splits it into 5 root communities (C0) with 9 nested ones below, and each gets an LLM-written report. Bottom: a global question maps over the C0 reports, each answer scored 0–100, then the non-zero answers are reduced into one. A local question starts from the matched entity WaterBrd and gathers its neighbours, relationships, reports and source chunks.

Communities and modularity

Qγ=∑c[Lcm−γ(dc2m)2],Δi→c=wi,c−γ Σc ki2mQ_\gamma=\sum_{c}\left[\frac{L_c}{m}-\gamma\left(\frac{d_c}{2m}\right)^{2}\right],\qquad \Delta_{i\to c}=w_{i,c}-\gamma\,\frac{\Sigma_c\,k_i}{2m}
Lc,  dcL_c,\;d_c
total edge weight inside community cc, and the sum of its nodes' weighted degrees
mm
total edge weight of the graph (here, co-mention counts)
γ\gamma
resolution: larger γ penalises big communities and gives more, smaller ones
Δi→c\Delta_{i\to c}
gain (up to the factor 1/m1/m) of moving node ii with degree kik_i into cc; wi,cw_{i,c} is its edge weight to cc, Σc\Sigma_c the degree sum of cc

Louvain (Blondel et al., 2008) moves each node to the neighbouring community with the largest Δ\Delta, then merges each community into one node and repeats; every pass is one level of the hierarchy. Leiden adds a refinement step that guarantees every community is internally connected, which Louvain does not. The figure below runs Louvain, which shows the same mechanics on a small graph.

Querying

Global search takes the reports at one level, shuffles them into batches that fit the context window and runs a map step in parallel: each batch yields a partial answer and a helpfulness score from 0 to 100. Answers scored 0 are dropped; the rest are sorted by score and packed into a final reduce prompt. Cost scales with the number of reports read, not with the question. Root-level C0 reports are the cheapest; leaf levels are more detailed and more expensive.

Local search, added in the open-source graphrag library, embeds the question, matches entity descriptions, and gathers the entities' neighbours, relationships, claims, community reports and the raw chunks that mention them into one ranked context. It is closer to ordinary RAG, with the graph deciding which chunks are related.

From the paper (Edge et al., 2024)

Datasets
two corpora of about 1M tokens each: podcast transcripts and news articles; 600-token chunks, 100-token overlap
Questions
global sensemaking questions generated by an LLM from descriptions of likely users and tasks, 125 per dataset
Judging
head-to-head comparisons by an LLM judge on comprehensiveness, diversity, empowerment and directness
Result
all global GraphRAG variants beat vector RAG on comprehensiveness and diversity; vector RAG was more direct. Root-level (C0) reports needed far fewer tokens per query than summarising the source text
Follow-ups
LightRAG (Guo et al., 2024) retrieves over entity and relation keys at two levels; HippoRAG (Gutiérrez et al., NeurIPS 2024) runs Personalized PageRank from query entities over an extracted graph
entity graph (edge = co-mentions in chunks), coloured by detected communityReservoirDamDroughtWaterBrdPipesRationingRiverLeeMetroBus 9FaresTransitCoTramStrikeSchool 12TeachersUnionExamsBudgetCurriculaOrtizCouncilBallotCampaignRiveraPollsHospitalClinicFluVaccinesNursesglobal search: one report per communitycommunities5 (Louvain levels: 2)modularity Q (γ = 1)0.6793purity vs hidden themes0.9333themes with own community5 of 5global search reads1,700 tokenssource text52,200 tokensratio30.7×local search: Strike (transit theme)community 3 (6 entities):Strike, School 12, Teachers, Union, Exams,Curriculaneighbours (co-mentions), 5 chunks:TransitCo 2, Union 2, Nurses 1assumed: 600-token chunk per co-mention; report = 100 + 40 tokens per entity; 30 entities
level
click a node to select it
fig.Louvain on a 30-entity graph from a toy city-news corpus with 5 hidden themes (edge weight = co-mentions, 87 in all). Default (γ = 1, top level): 5 communities, Q = 0.6793, purity 0.9333: only Strike (filed under transit, but linked to the teachers' Union) and Budget (schools, but tied to the Council) sit outside their theme. Global search reads 1,700 tokens of reports against 52,200 of source text, 30.7× fewer, under the stated assumptions. The first level has 9 communities (Q = 0.5461, 2,100 tokens). Drop γ to 0.3 and transit merges with schools: 4 communities, Q = 0.6348, purity 0.80. Raise γ to 2.5 and Strike–Union and Budget–Council split off as pairs: 7 communities, 1,900 report tokens.

Worked example: why Strike joins the schools

At γ=1\gamma=1 the graph has m=87m=87, so 2m=1742m=174. Strike has degree k=5k=5: weight 2 to TransitCo, 2 to Union and 1 to Nurses. With the other nodes in their final communities:

Communityw (Strike → c)Σ_c (degree sum)γΣ_c k / 2mΔ
schools (Union, Teachers, …)22828 · 5 / 174 = 0.80461.1954
transit (TransitCo, Metro, …)23131 · 5 / 174 = 0.89081.1092
health (Nurses, …)12727 · 5 / 174 = 0.77590.2241
Louvain gain of moving Strike into each neighbouring community, Δ = w − γΣk/2m

The edge weights tie at 2, so the smaller community wins: the null model expects fewer edges into it by chance. Moving Strike to transit would lower QQ from 0.67930.6793 to 0.67840.6784. The bridge entity therefore lands in the schools report, and a question about the transit strike must rely on local search or a lower level. In a real corpus the fix is better extraction: separate entities for a teachers' strike and a transit strike.

CommunityEntitiesL_cd_cL_c/m − (d_c/2m)²
water720430.2299 − 0.0611 = 0.1688
transit514310.1609 − 0.0317 = 0.1292
schools + Strike614330.1609 − 0.0360 = 0.1250
election + Budget717400.1954 − 0.0528 = 0.1426
health512270.1379 − 0.0241 = 0.1139
Modularity of the 5 top-level communities (terms rounded; exact sum 0.6793)
python
1import json
2
3MAP = ("Answer the question using only these community reports. "
4 'Return JSON: {"points": [{"text": str, "score": 0-100}]}. '
5 "Score 0 if the reports are irrelevant.")
6
7def global_search(question, reports, batch_tokens=8000, budget_tokens=12000):
8 batches, cur, size = [], [], 0
9 for rep in reports: # C0 reports, shuffled
10 if size + rep["tokens"] > batch_tokens and cur:
11 batches.append(cur); cur, size = [], 0
12 cur.append(rep); size += rep["tokens"]
13 batches.append(cur)
14
15 points = []
16 for b in batches: # map: run in parallel in practice
17 ctx = "\n\n".join(f"[{r['id']}] {r['title']}\n{r['summary']}" for r in b)
18 out = json.loads(llm(system=MAP, user=f"{ctx}\n\nQ: {question}"))
19 points += [p for p in out["points"] if p["score"] > 0]
20
21 points.sort(key=lambda p: -p["score"]) # reduce: best first, until budget
22 ctx, used = [], 0
23 for p in points:
24 n = len(p["text"]) // 4 # rough token count
25 if used + n > budget_tokens: break
26 ctx.append(p["text"]); used += n
27 return llm(system="Combine these analyst points into one answer.",
28 user="\n".join(ctx) + f"\n\nQ: {question}")
The global map-reduce step over community reports (llm and the report list are placeholders; the open-source graphrag library implements this with more prompt detail; not run here)

Use when

  • +Answers global, sensemaking questions over a whole corpus with a bounded context
  • +Relationships make multi-hop links explicit and inspectable
  • +Community reports are reusable artefacts: browsable summaries of the corpus

Avoid when

  • −Expensive, slow indexing: LLM calls over every chunk and every community
  • −Extraction errors (missed entities, unmerged duplicates, ambiguous names) propagate into communities and reports
  • −Global search costs many map calls per question; less direct than vector RAG for simple lookups

Check yourself

Why does vector top-k retrieval do poorly on "What are the main themes in this corpus?"

Check yourself

In the figure, raising γ from 1 to 2.5 at the top level gives 7 communities instead of 5. What happens to the global search cost under the figure's token model?

Remember

  • ✓Index: chunk, LLM-extract entities and relationships, merge into a graph, cluster with Leiden into a hierarchy, write a report per community.
  • ✓Communities maximise modularity Qγ=∑c[Lc/m−γ(dc/2m)2]Q_\gamma=\sum_c[L_c/m-\gamma(d_c/2m)^2]; γ sets their size.
  • ✓Global search: map over community reports with 0–100 scores, reduce the best into one answer; for corpus-wide questions.
  • ✓Local search: match entities, fan out to neighbours, relationships, reports and source chunks; for entity questions.
  • ✓Costly to build and refresh; route point lookups to plain hybrid RAG.
← back to Generative AI roadmap