# 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.

Source: https://www.mlfoundry.in/learn/graphrag  
Section: Generative AI › Retrieval-Augmented Generation (RAG)  
Level: advanced · 8 min read · updated 2026-10-21

**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-$k$ 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 $k$. 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. **Text units.** Split documents into chunks; the paper used 600-token chunks with 100-token overlap.
2. **Extraction.** 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. **Graph.** Entities with the same name are merged and their descriptions summarised; relationship counts become edge weights.
4. **Communities.** Leiden is run recursively, giving levels C0 (root, few large communities) down to leaf communities.
5. **Reports.** 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.

> Figure: 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_\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}
$$

- $L_c,\;d_c$: total edge weight inside community $c$, and the sum of its nodes' weighted degrees
- $m$: total edge weight of the graph (here, co-mention counts)
- $\gamma$: resolution: larger γ penalises big communities and gives more, smaller ones
- $\Delta_{i\to c}$: gain (up to the factor $1/m$) of moving node $i$ with degree $k_i$ into $c$; $w_{i,c}$ is its edge weight to $c$, $\Sigma_c$ the degree sum of $c$

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

> Figure: 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 $\gamma=1$ the graph has $m=87$, so $2m=174$. Strike has degree $k=5$: weight 2 to TransitCo, 2 to Union and 1 to Nurses. With the other nodes in their final communities:

Louvain gain of moving Strike into each neighbouring community, Δ = w − γΣk/2m

| Community | w (Strike → c) | Σ_c (degree sum) | γΣ_c k / 2m | Δ |
| --- | --- | --- | --- | --- |
| schools (Union, Teachers, …) | 2 | 28 | 28 · 5 / 174 = 0.8046 | 1.1954 |
| transit (TransitCo, Metro, …) | 2 | 31 | 31 · 5 / 174 = 0.8908 | 1.1092 |
| health (Nurses, …) | 1 | 27 | 27 · 5 / 174 = 0.7759 | 0.2241 |

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 $Q$ from $0.6793$ to $0.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.

Modularity of the 5 top-level communities (terms rounded; exact sum 0.6793)

| Community | Entities | L_c | d_c | L_c/m − (d_c/2m)² |
| --- | --- | --- | --- | --- |
| water | 7 | 20 | 43 | 0.2299 − 0.0611 = 0.1688 |
| transit | 5 | 14 | 31 | 0.1609 − 0.0317 = 0.1292 |
| schools + Strike | 6 | 14 | 33 | 0.1609 − 0.0360 = 0.1250 |
| election + Budget | 7 | 17 | 40 | 0.1954 − 0.0528 = 0.1426 |
| health | 5 | 12 | 27 | 0.1379 − 0.0241 = 0.1139 |

```python
import json

MAP = ("Answer the question using only these community reports. "
       'Return JSON: {"points": [{"text": str, "score": 0-100}]}. '
       "Score 0 if the reports are irrelevant.")

def global_search(question, reports, batch_tokens=8000, budget_tokens=12000):
    batches, cur, size = [], [], 0
    for rep in reports:                                  # C0 reports, shuffled
        if size + rep["tokens"] > batch_tokens and cur:
            batches.append(cur); cur, size = [], 0
        cur.append(rep); size += rep["tokens"]
    batches.append(cur)

    points = []
    for b in batches:                                    # map: run in parallel in practice
        ctx = "\n\n".join(f"[{r['id']}] {r['title']}\n{r['summary']}" for r in b)
        out = json.loads(llm(system=MAP, user=f"{ctx}\n\nQ: {question}"))
        points += [p for p in out["points"] if p["score"] > 0]

    points.sort(key=lambda p: -p["score"])               # reduce: best first, until budget
    ctx, used = [], 0
    for p in points:
        n = len(p["text"]) // 4                          # rough token count
        if used + n > budget_tokens: break
        ctx.append(p["text"]); used += n
    return llm(system="Combine these analyst points into one answer.",
               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)

> **Indexing cost and staleness:** Every chunk needs at least one LLM extraction call, plus gleaning rounds, entity summaries and one report per community. That is orders of magnitude more LLM tokens than embedding the same corpus. Adding documents can change communities, so reports must be regenerated. Budget a small pilot first, and use a cheaper model for extraction if its entity recall is acceptable.

> **Use it for the questions vector RAG cannot answer:** GraphRAG pays off for corpus-wide questions ("main themes", "how do these actors relate", "what changed across all reports") and for multi-hop questions about named entities. For point lookups ("what is error E42?") plain hybrid retrieval is cheaper and more direct. Many systems route between the two (see **Agentic RAG**).

**Strengths**

- 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

**Limitations**

- 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

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

- A. The embedding model cannot encode the word "themes"
- B. The answer is spread across the whole corpus, and the k chunks most similar to the question are not a representative sample of it
- C. The question is too short to embed
- D. Vector databases cannot return more than 10 results

**Answer:** B. The answer is spread across the whole corpus, and the k chunks most similar to the question are not a representative sample of it — Similarity search returns chunks that talk about themes, not chunks that together cover every theme. GraphRAG summarises every community in advance, so global search can read a compressed view of the entire corpus.

**Question:** 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?

- A. It falls, because communities are smaller
- B. It rises from 1,700 to 1,900 tokens: two more reports at 100 tokens each, the same 30 entities
- C. It stays the same
- D. It doubles

**Answer:** B. It rises from 1,700 to 1,900 tokens: two more reports at 100 tokens each, the same 30 entities — Report tokens $=100\,C+40\cdot30$. With $C=5$ that is 1,700; with $C=7$ it is 1,900. Finer levels read more, more detailed reports.

**Key points**

- 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_\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
