Skip to content

Graph RAG

Vector similarity search treats every chunk as isolated text — good at "find text similar to this text," bad at questions whose answer depends on how two things are connected rather than how similar they are to the query. Graph RAG builds an explicit knowledge graph — entities as nodes, relationships as edges — so a query can traverse connections a similarity score alone can't represent.

Hands-on

The full pipeline below is runnable, against real data: Graph RAG → in the code repo. Needs an LLM key; graph construction and community summarization are genuinely expensive, so the built graph is cached after the first run.

TL;DR — quick revision
  • Building the graph is real work, measured honestly: on a 92-chunk sample paper, extraction alone took 92 LLM calls (one per chunk) and produced 605 entities and 819 relationships — that's before community detection or summarization even start
  • Two query modes answer genuinely different question types: local search (entity-link the query, traverse the graph, generate from what's connected) for specific relational questions; global search (map-reduce over community summaries) for broad synthesis questions no single top-k retrieval can cover
  • Both verified as real wins over naive retrieval, not asserted: local search found a connection naive retrieval missed at k=1 and k=3 (only surfacing at k=5); global search's answer to a broad architecture question covered components naive top-5 completely missed
  • A real, honest limitation, caught and reported: entity deduplication by embedding similarity failed to merge "Encoder" and "the Encoder stack" — their actual similarity (0.833) fell just under the 0.88 threshold used
  • Global search costs one LLM call per community, every single query — genuinely expensive; a newer approach (LazyGraphRAG) exists specifically to avoid this recurring cost

Building the graph

1. Extract entities and relationships — one LLM call per chunk

Each chunk gets read by an LLM and turned into (entity, relationship, entity) triples — the raw material the graph is built from.

import re

import llm

EXTRACTION_PROMPT = """Extract entities and relationships from the \
passage below, for building a knowledge graph. Use short, canonical \
entity names (e.g. "Multi-Head Attention", not "the multi-head \
attention mechanism described here").

Passage:
{chunk}

For each relationship found, output one line as:
EntityA | relationship | EntityB

If no clear entity relationships exist in this passage, output NONE.
Wrap your output in <triples></triples> tags."""


def extract_triples(chunk: str, provider: str | None = None) -> list[tuple[str, str, str]]:
    response = llm.generate(EXTRACTION_PROMPT.format(chunk=chunk), provider=provider)
    match = re.search(r"<triples>(.*?)</triples>", response, re.S)
    if not match or match.group(1).strip().upper() == "NONE":
        return []

    triples = []
    for line in match.group(1).strip().splitlines():
        parts = [p.strip() for p in line.split("|")]
        if len(parts) == 3 and all(parts):
            triples.append((parts[0], parts[1], parts[2]))
    return triples

Real output, from an actual chunk in the sample paper:

Chunk: "We used the Adam optimizer with beta1=0.9. The model has h=8
attention heads."

Extracted triples:
  (Adam Optimizer, has_parameter, beta1=0.9)
  (Model, has_component, Attention Heads)
  (Model, has_parameter, h=8)
  (Attention Heads, number, 8)

Run across all 92 chunks of the real sample paper, this produced 605 entities and 819 relationships — genuinely substantial structure, but also 92 separate LLM calls before anything else happens. Naive RAG's entire indexing cost, by comparison, is zero LLM calls (just local embeddings).

2. Deduplicate entities — and a real limitation this surfaced

Different chunks describe the same real entity with different surface forms — "Encoder," "the Encoder stack," "encoder" all refer to the same thing. Left unmerged, these fragment the graph into disconnected near-duplicate nodes that should be one.

import numpy as np
from sentence_transformers import SentenceTransformer

DEDUP_SIMILARITY_THRESHOLD = 0.88


def deduplicate_entities(entity_names: list[str], embed_model: SentenceTransformer) -> dict[str, str]:
    """Different chunks refer to the same real entity with different
    surface forms ("Encoder" vs "the Encoder stack" vs "encoder").
    Exact-string matching alone misses these — this embeds every
    distinct name and greedily merges anything similar enough to an
    already-seen canonical name, keeping the first-seen form as
    canonical. Returns {raw_name: canonical_name}."""
    unique_names = sorted(set(entity_names))
    if not unique_names:
        return {}

    embeddings = embed_model.encode(unique_names, convert_to_numpy=True, show_progress_bar=False)
    canonical_names: list[str] = []
    canonical_embeddings: list[np.ndarray] = []
    mapping: dict[str, str] = {}

    for name, emb in zip(unique_names, embeddings):
        best_sim, best_idx = -1.0, -1
        for i, cand_emb in enumerate(canonical_embeddings):
            sim = float(np.dot(emb, cand_emb) / (np.linalg.norm(emb) * np.linalg.norm(cand_emb) + 1e-8))
            if sim > best_sim:
                best_sim, best_idx = sim, i

        if best_sim >= DEDUP_SIMILARITY_THRESHOLD:
            mapping[name] = canonical_names[best_idx]
        else:
            canonical_names.append(name)
            canonical_embeddings.append(emb)
            mapping[name] = name

    return mapping

A real, honest limitation, not a hypothetical one

This uses embedding similarity with a 0.88 cosine-similarity threshold to merge near-duplicate names. Checked directly: "Encoder" vs "the Encoder stack" scores 0.833 — just under the threshold — so these do not get merged, even though they're genuinely the same entity. Meanwhile "Multi-Head Attention" vs "multi-head attention mechanism" scores 0.927 and merges correctly. Similarity-based deduplication is a real, imperfect heuristic, not a solved problem — worth knowing before trusting a graph's entity count at face value.

3. Detect communities — a real graph algorithm, not an LLM call

Once the graph exists, clustering related entities together is purely structural — no LLM involved at this step.

import networkx as nx


def detect_communities(graph: nx.MultiDiGraph) -> list[set[str]]:
    """Louvain community detection — a real, established graph
    clustering algorithm (networkx's built-in implementation), run
    purely on graph structure. No LLM call here; the LLM only
    summarizes the communities this algorithm finds."""
    undirected = nx.Graph(graph)  # collapses parallel/directed edges into a weighted simple graph
    if undirected.number_of_edges() == 0:
        return [{n} for n in undirected.nodes()]
    return list(nx.algorithms.community.louvain_communities(undirected, seed=42))

Louvain community detection on the real 605-entity graph found 70 communities — a large one centered on the Transformer model itself and its evaluation, down to many small, tightly-related clusters. Each community then gets one LLM call to produce a short summary of what it collectively represents — 70 more calls, on top of the 92 extraction calls above.

Querying the graph

The graph built above supports two genuinely different ways of answering a question, and picking the right one matters — they're built for different question shapes, not interchangeable options.

Local search — anchor on specific entities, then look at what's connected to them

Local search is for questions that are really about one or two specific things and how they relate — "what connects X to Y," "what does X depend on." Instead of hoping a single query embedding happens to rank the one right chunk highly among the whole corpus, it does something more direct: figure out which graph entities the question is actually about, then look at exactly what's connected to them.

Concretely, that means two steps: entity-linking the query to graph nodes by embedding similarity (the query says "label smoothing," the graph node might be canonicalized as "Label Smoothing" — close enough in embedding space to match, without needing an exact string match), and then traversal — walking outward from those matched nodes along graph edges, collecting every relationship (and the original source chunk it came from) encountered along the way.

import numpy as np
from sentence_transformers import SentenceTransformer

import llm


def local_search(
    question: str,
    graph,
    chunks: list[str],
    embed_model: SentenceTransformer,
    provider: str | None = None,
    top_entities: int = 3,
    hops: int = 1,
) -> dict:
    """Entity-link the query to graph nodes by embedding similarity
    (not exact string match — the query rarely uses the graph's exact
    canonical entity names), walk `hops` steps out from the matched
    entities, and gather every triple touched along the way, plus the
    original source chunks those triples came from."""
    nodes = list(graph.nodes())
    if not nodes:
        return {"matched_entities": [], "triples": [], "source_chunks": [], "answer": "(empty graph)"}

    node_embeddings = embed_model.encode(nodes, convert_to_numpy=True, show_progress_bar=False)
    query_vec = embed_model.encode(question, convert_to_numpy=True)
    sims = [float(np.dot(query_vec, v) / (np.linalg.norm(query_vec) * np.linalg.norm(v) + 1e-8)) for v in node_embeddings]
    matched = [nodes[i] for i in np.argsort(sims)[::-1][:top_entities]]

    frontier = set(matched)
    visited_edges = set()
    for _ in range(hops):
        next_frontier = set()
        for node in frontier:
            for u, v, d in list(graph.out_edges(node, data=True)) + list(graph.in_edges(node, data=True)):
                visited_edges.add((u, v, d["relationship"], d["source_chunk"]))
                next_frontier.update([u, v])
        frontier |= next_frontier

    triples = [(u, rel, v) for (u, v, rel, _) in visited_edges]
    source_chunk_ids = sorted({sc for (_, _, _, sc) in visited_edges})
    source_chunks = [chunks[i] for i in source_chunk_ids]

    facts_text = "\n".join(f"{u} -> {rel} -> {v}" for u, rel, v in triples)
    context = f"Graph facts:\n{facts_text}\n\nSource passages:\n" + "\n---\n".join(source_chunks)
    answer = llm.generate(f"Answer the question using the context below.\n\nContext:\n{context}\n\nQuestion: {question}", provider=provider)

    return {"matched_entities": matched, "triples": triples, "source_chunks": source_chunks, "answer": answer}

Measured: a real win naive retrieval didn't have

Asked "What connects label smoothing to the BLEU score improvements?" — naive bi-encoder retrieval misses the connecting chunk at both k=1 and k=3, only surfacing it at k=5. Local search finds it directly: matched entities ['BLEU Score', 'Label Smoothing', 'Learning rate'], traversed 11 triples across 4 source chunks, and generated: "label smoothing... hurts perplexity... but improves accuracy and BLEU score" — grounded in the exact sentence naive retrieval was slow to find. The entity-linking step found the right anchor points directly, instead of hoping a single query embedding would rank the connecting chunk highly enough.

Global search — for questions no single entity or chunk can fully answer

Local search assumes the answer lives near a handful of specific entities. That assumption breaks for a genuinely broad question like "what are the main components of this system and how do they work together" — there's no single entity to anchor on, because the honest answer requires synthesizing across large parts of the whole corpus. This is where the community summaries built earlier get used: instead of anchoring on entities, global search asks every community, independently, whether it has something to contribute to this specific question, then combines whatever comes back.

That's a map-reduce pattern: the "map" step asks each community summary in isolation (parallelizable — and a community with nothing relevant just says so and gets filtered out), and the "reduce" step takes whatever partial answers survived and combines them into one final answer.

import llm

MAP_PROMPT = """Using ONLY the community summary below, write a brief \
partial answer to the question — if this summary isn't relevant to \
the question at all, respond with exactly: NOT RELEVANT

Community summary: {summary}

Question: {question}"""

REDUCE_PROMPT = """Combine the partial answers below into one coherent \
final answer to the question. Ignore any partial answer that said \
"NOT RELEVANT".

Question: {question}

Partial answers:
{partial_answers}"""


def global_search(question: str, community_summaries: list[str], provider: str | None = None) -> dict:
    """Map: ask each community summary independently whether it has a
    partial answer (parallelizable, independent calls — irrelevant
    communities self-report and get filtered out). Reduce: combine
    whatever partial answers came back into one final answer. This is
    what lets a broad synthesis question get answered from a
    whole-corpus view instead of whatever a single top-k happened to
    retrieve — at the real cost of one call per community, every query."""
    partial_answers = []
    for summary in community_summaries:
        resp = llm.generate(MAP_PROMPT.format(summary=summary, question=question), provider=provider).strip()
        if "NOT RELEVANT" not in resp.upper():
            partial_answers.append(resp)

    if not partial_answers:
        return {"partial_answers": [], "answer": "No community summary was relevant to this question."}

    combined = "\n---\n".join(partial_answers)
    answer = llm.generate(REDUCE_PROMPT.format(question=question, partial_answers=combined), provider=provider)
    return {"partial_answers": partial_answers, "answer": answer}

Measured: naive top-5 missed most of the architecture

Asked "What are the main components of the Transformer architecture and how do they work together?" — naive top-5 retrieval clustered around a single narrative thread (parallelization, the overall encoder/decoder split) and never surfaced positional encoding, residual connections, or the decoder's causal masking at all. Global search drew from 10 of the 70 communities and produced a genuinely comprehensive answer covering the encoder, the decoder, multi-head attention's actual mechanics, positional encoding, and residual connections together.

This is the same underlying lesson RAPTOR already demonstrated elsewhere on this site — a flat top-k can't synthesize across an entire corpus, no matter how good the embeddings are — but arrived at through a genuinely different clustering basis: RAPTOR clusters chunks by embedding similarity; Graph RAG's communities are clusters of the entity relationship graph itself. Two different structures, same underlying fix for the same failure mode.

The real cost of global search

That answer required 10+ LLM calls just for the map step, one per community, every single time this question is asked — not a one-time cost like the extraction/summarization above, but a recurring per-query cost. LazyGraphRAG (Microsoft Research) is a real, more recent answer to exactly this problem — it skips upfront community summarization and does relevance filtering lazily at query time instead, trading some of global search's completeness for meaningfully lower cost. Not implemented here, but worth knowing as the actual answer to "this is too expensive to run in production as-is."

Missing piece: choosing local vs. global isn't automatic here

In the code for this page, local vs. global is a flag you pass on the command line — the recipe doesn't decide for you. A real system shouldn't make a user choose that by hand: it should look at the query first and route it automatically, the same way Adaptive RAG routes each query to the right pre-retrieval technique before this graph is ever touched. Wiring an equivalent router in front of local/global search — narrow, entity-specific question → local; broad, whole-corpus synthesis question → global — is a natural next extension of this recipe, deliberately left out here to keep this page's scope to the graph mechanics themselves.

Does all data become graph structure?

No, and this matters for what Graph RAG can and can't do:

  • Only text describing clear entities and relationships extracts cleanly. Narrative or qualitative discussion without a clean entity-relationship structure often doesn't map into a triple at all — extraction is inherently lossy, compressing free text into (entity, relationship, entity) form.
  • Original text chunks are kept, not discarded. Every edge in the graph above stores a reference back to the source chunk it came from — local search's answer above pulled in that original text alongside the graph facts, not just bare triples. Graph RAG is an additional structured layer on top of the same text, not a replacement for it.

Practical implication: most production systems run both — the vector index for plain similarity lookups, the graph for relational/multi-hop or broad synthesis questions — routing between them based on what kind of question came in, the same routing idea covered on the pre-retrieval page.

Use it for / skip it for

Use it for: domains where relationships between entities are the actual point of most queries — org structures, supply chains, regulatory dependency mapping, codebases (call/import graphs), citation networks, fraud-ring/network analysis (patterns of connections between accounts, not any single transaction alone). Skip it for: a narrow, well-curated corpus where multi-hop relational questions are rare — you'd be paying real extraction and summarization cost (measured above: ~162 LLM calls just to build the graph on a 92-chunk paper) for a problem that mostly doesn't come up; or any corpus that changes often enough that re-extraction becomes a constant tax rather than a one-time cost.

Scenario Check

Sources & further reading