GraphRAG: Knowledge Graphs for Multi-Hop Reasoning Across Interconnected Documents
Standard Retrieval-Augmented Generation (RAG) is founded on a fundamental premise: that the user's information need can be satisfied by locating a small set of top-$k$ text chunks that are semantically similar to the prompt. While this premise holds for point-lookup queries (e.g. "What is the maximum deductible under Policy Section 3?"), it collapses completely when confronted with Corpus-Wide Synthesis Questions (e.g. "What are the top three strategic risks emerging across all subsidiary audit reports?" or "How does Entity A influence Entity D through intermediary shell corporations?").
Because no single paragraph in the corpus contains the complete answer, standard vector search retrieves chunks that contain surface-level keywords ("risk", "audit") while remaining entirely blind to the global topological connections between actors, transactions, and events. GraphRAG (Edge et al., Microsoft Research 2024) solves this failure mode by converting unstructured corpora into structured Knowledge Graphs, executing Leiden Community Detection to cluster interrelated entities into hierarchical themes, and synthesizing bottom-up community reports for both Local (entity-centric) and Global (holistic) queries.
Core Engineering Thesis
By replacing flat vector indexing with hierarchical knowledge graphs partitioned via the Leiden algorithm, GraphRAG achieves an extraordinary +153.5% increase in query comprehensiveness and +89.4% accuracy on multi-hop reasoning chains (3+ hops), enabling true autonomous intelligence analysis over unstructured enterprise corpora.
1. The Graph Construction Pipeline
The transformation of raw unstructured text into an operational GraphRAG knowledge engine proceeds through four deterministic stages:
Stage 1: LLM-Driven Entity & Relationship Extraction
Input documents are segmented into overlapping text units ($L pprox 600 ext{ tokens}$, overlap $pprox 100 ext{ tokens}$). An extraction prompt directs an LLM to identify all named entities (Persons, Organizations, Geo-locations, Legal Instruments, Technologies) and their typed directional relationships:
$$E_{i,j} = \langle ext{Source\_Entity}, ext{Target\_Entity}, ext{Relation\_Type}, ext{Weight}, ext{Description} angle$$
Crucially, GraphRAG also extracts Covariates (Claims/Assertions): time-bounded, verifiable claims made by entities with associated evidentiary excerpts.
Stage 2: Graph Assembly & Deduplication
The extracted tuples are assembled into a global weighted multigraph $G = (V, E, W)$, where nodes $v \in V$ represent canonical entities and edges $e = (u, v) \in E$ represent aggregated relationships. An entity resolution step merges aliases (e.g., "Alphabet Inc.", "Alphabet", "Google's parent company") using vector similarity and topological graph proximity.
Figure 1: End-to-end GraphRAG pipeline from unstructured text extraction to multi-scale Leiden community summaries.
2. Mathematical Mechanics: The Leiden Community Detection Algorithm
To summarize millions of words without exceeding LLM context windows, GraphRAG must partition the global graph into semantically cohesive, non-overlapping clusters at multiple hierarchical scales. Traditional community detection algorithms (like Louvain) suffer from a well-documented mathematical defect: they can generate disconnected communities.
GraphRAG utilizes the Leiden Algorithm (Traag, Waltman, & van Eck, 2019), which guarantees that all detected communities are connected subgraphs while optimizing Constant Potts Model (CPM) or Reichardt and Bornholdt's modularity:
$$\mathcal{H} = \sum_{c \in C} \left[ e_c - \gamma rac{K_c^2}{2m} ight]$$
Where:
- $e_c$ is the total weight of internal edges within community cluster $c$.
- $K_c$ is the sum of node degrees belonging to community $c$.
- $m$ is the total edge weight across the entire graph ($m = rac{1}{2} \sum_{i,j} W_{ij}$).
- $\gamma > 0$ is the resolution parameter. Sweeping $\gamma$ allows the algorithm to discover communities at multiple zoom levels: small $\gamma$ discovers massive global thematic clusters (Level 0), while large $\gamma$ partitions the graph into tight micro-clusters (Level 2).
Hierarchical Community Summarization
Once the hierarchical community tree is constructed:
- Leaf Communities (Level 2): An LLM reads all nodes, edges, and raw text claims in the community, generating an executive summary report with cited entity references.
- Higher-Level Communities (Level 1 & 0): The LLM synthesizes the reports of its child communities into broader macro-thematic reports.
3. Query Execution: Local Search vs. Global Search
GraphRAG routes incoming user queries through two completely distinct architectural paths based on query intent:
| Query Architecture | Target Query Pattern | Retrieval Mechanism | Context Assembly |
|---|---|---|---|
| Local Search | Entity-specific lookups: "What contracts did Dr. Smith authorize in 2024?" | 1. Entity Extraction from query. 2. Vector lookup on Entity Nodes. 3. 1-to-2 Hop Ego-Graph traversal. |
Adjacent Entity Descriptions + Edge Relations + Covariate Claims + Source Chunks. |
| Global Search | Corpus-wide synthesis: "What are the overarching systemic risks in this portfolio?" | 1. Community Report retrieval at designated hierarchy level (e.g. Level 1). 2. Map phase over reports. |
Map: Extract relevant point claims per report. Reduce: Synthesize intermediate outputs into final global answer. |
4. Empirical Performance Evaluation (GraphRAG vs. Vector RAG)
Evaluated on the complex Podcast Transcript Corpus and Corporate Disclosures benchmark datasets (Edge et al., 2024), evaluated by LLM-as-a-judge across four key dimensions:
| Evaluation Dimension | Naive Vector RAG | Reranked Hybrid RAG | GraphRAG (Global Search) | Delta (GraphRAG vs Hybrid) |
|---|---|---|---|---|
| Comprehensiveness (Covers all relevant aspects) | 0.342 | 0.458 | 0.867 | +89.3% |
| Diversity (Breadth of perspectives) | 0.410 | 0.521 | 0.892 | +71.2% |
| Empowerment (Evidence & citations) | 0.584 | 0.690 | 0.854 | +23.8% |
| Multi-Hop Reasoning (3+ Hops) | 0.285 | 0.412 | 0.894 | +117.0% |
5. Production Implementation (Python)
The following module demonstrates a self-contained in-memory GraphRAG pipeline: extracting entity-relation subgraphs, computing modularity-based community detection, and executing multi-hop ego-graph retrieval.
# -*- coding: utf-8 -*-
import json
from collections import defaultdict
from typing import List, Dict, Tuple, Set, Any
import networkx as nx
from community import community_louvain # Modularity clustering fallback
class GraphRAGEngine:
def __init__(self):
# Master Multi-Graph: G = (V, E)
self.graph = nx.Graph()
self.entity_metadata: Dict[str, Dict[str, Any]] = {}
self.community_hierarchy: Dict[int, List[Set[str]]] = {}
self.community_summaries: Dict[int, Dict[int, str]] = defaultdict(dict)
def add_entity(self, name: str, entity_type: str, description: str):
node_id = name.strip().lower()
if not self.graph.has_node(node_id):
self.graph.add_node(node_id, type=entity_type, name=name)
self.entity_metadata[node_id] = {
"name": name,
"type": entity_type,
"description": description,
"claims": []
}
def add_relationship(
self,
source: str,
target: str,
relation: str,
weight: float = 1.0,
description: str = ""
):
src_id = source.strip().lower()
tgt_id = target.strip().lower()
if not self.graph.has_node(src_id):
self.add_entity(source, "UNKNOWN", "")
if not self.graph.has_node(tgt_id):
self.add_entity(target, "UNKNOWN", "")
if self.graph.has_edge(src_id, tgt_id):
self.graph[src_id][tgt_id]["weight"] += weight
self.graph[src_id][tgt_id]["relations"].append(relation)
else:
self.graph.add_edge(
src_id,
tgt_id,
weight=weight,
relations=[relation],
description=description
)
def detect_communities(self, resolution: float = 1.0) -> Dict[str, int]:
# Executes modularity optimization to partition the graph into communities
if len(self.graph.nodes) == 0:
return {}
partition = community_louvain.best_partition(
self.graph,
weight="weight",
resolution=resolution
)
# Group entities by community ID
communities = defaultdict(set)
for node, comm_id in partition.items():
communities[comm_id].add(node)
self.community_hierarchy[1] = list(communities.values())
return partition
def local_search(self, target_entity: str, max_hops: int = 2) -> Dict[str, Any]:
# Traverses ego-graph around target entity up to max_hops
root = target_entity.strip().lower()
if not self.graph.has_node(root):
return {"error": f"Entity [{target_entity}] not found in knowledge graph."}
# Subgraph extraction via breadth-first search
visited_nodes = {root}
frontier = {root}
traversed_edges = []
for hop in range(max_hops):
next_frontier = set()
for current_node in frontier:
for neighbor in self.graph.neighbors(current_node):
edge_data = self.graph.get_edge_data(current_node, neighbor)
traversed_edges.append({
"source": self.entity_metadata[current_node]["name"],
"target": self.entity_metadata[neighbor]["name"],
"relations": edge_data.get("relations", []),
"weight": edge_data.get("weight", 1.0)
})
if neighbor not in visited_nodes:
visited_nodes.add(neighbor)
next_frontier.add(neighbor)
frontier = next_frontier
# Assemble local context bundle
entities_context = [
self.entity_metadata[n] for n in visited_nodes if n in self.entity_metadata
]
return {
"root_entity": target_entity,
"subgraph_nodes_count": len(visited_nodes),
"subgraph_edges_count": len(traversed_edges),
"entities": entities_context,
"edges": traversed_edges
}
def global_search_mock(self, query: str) -> List[Dict[str, Any]]:
# Map-Reduce over Community Summaries
results = []
communities = self.community_hierarchy.get(1, [])
for comm_id, members in enumerate(communities):
results.append({
"community_id": comm_id,
"member_count": len(members),
"sample_entities": [self.entity_metadata[m]["name"] for m in list(members)[:5]],
"relevance_rank": comm_id + 1
})
return results
6. Production Recommendations
- Dual-Track Ingestion: Graph extraction is computationally expensive (requiring 3–5 LLM extraction calls per document). Run offline batch extraction for enterprise knowledge bases and store in production graph databases like Neo4j or Memgraph with Cypher query interfaces.
- Pair with Fast Hybrid Retrieval: Use standard Hybrid RAG (BM25 + Dense) for sub-50ms operational queries; route complex analytical, strategic, or cross-document audit questions to GraphRAG.
- Prune Low-Weight Artifacts: Real-world LLM extraction generates noisy edges. Enforce an edge weight threshold ($W_{ij} \ge 2$) or cosine-similarity claim verification before building the final Leiden community trees.