Graph Rag

Graph RAG is a sophisticated retrieval-augmented generation system that moves beyond simple vector similarity by leveraging knowledge graphs and community detection to understand complex relationships within documents. This guide covers the complete technical architecture under the hood, from document ingestion through query resolution.

Building the Knowledge Graph

Stage 1: Document Chunking Strategy

The first challenge with large documents is deciding how to split them. Graph RAG doesn’t use fixed-size chunks uniformly:

• Page-level chunking achieves the best average accuracy for most datasets
• Token-based chunking (512-1024 tokens) works well for finance-specific documents
• Document structure-based chunking leverages headings and sections to maintain semantic boundaries
• Overlap is maintained between consecutive chunks to preserve context continuity

For 2,000 articles in real-world deployments, systems typically extract around 13,000 entities and 16,000 relationships with costs around $30 using GPT-4o.

Stage 2: Entity and Relationship Extraction Using LLM Prompts

This is where the real complexity begins. The system uses carefully engineered prompts to extract structured information from unstructured text.

The core prompt structure follows this pattern:

-Goal-
Given a text document and a list of entity types, identify all entities 
of those types from the text and all relationships among identified entities.

-Steps-
1. Identify all entities with:
   - entity_name: Name of the entity, capitalized
   - entity_type: One of predefined types
   - entity_description: Comprehensive description of attributes and activities

2. From identified entities, identify all pairs (source_entity, target_entity) 
   that are clearly related with:
   - relationship_description: Why they're related
   - relationship_strength: Numeric score (1-10) indicating relationship strength

3. Return output as single list using delimiters

4. Output completion signal when done

Critical insight: For large documents that exceed context windows, GraphRAG uses an iterative extraction strategy. The system makes multiple LLM calls with continuation prompts like:

• First pass: Extract all entities and relationships
• Continuation prompt: “MANY entities were missed in the last extraction. Add them below using the same format”
• Validation loop: “Are there still entities that need to be added? YES | NO”

This ensures comprehensive extraction without hallucination from overcrowded context windows.

Auto-Tuning of Prompts

Microsoft’s GraphRAG includes an innovative auto-tuning feature that customizes extraction prompts to your domain. Instead of using generic prompts, the system:

1. Samples documents from your corpus
2. Generates domain-specific entity examples from sample content
3. Creates domain-specific relationship examples
4. Produces 2-3x better extraction (from 6 relationships to 8, from 7 entities to 9 in benchmarks)

This auto-tuning increased extraction depth without manual prompt engineering.

Stage 3: Graph Construction in Neo4j

Once entities and relationships are extracted, they’re inserted into Neo4j as nodes and edges. The structure is:

Nodes: (:Entity {name: entity_name, description: description, embedding: vector})
Relationships: (entity1)-->(entity2)

Each node also gets embedded using the same embedding model as chunks, enabling semantic search across the graph.

Stage 4: Community Detection Using Leiden Algorithm

This is where GraphRAG becomes powerful. Instead of treating the entire graph uniformly, it uses the Leiden algorithm to detect hierarchical communities within the graph. Communities are groups of nodes that are densely connected to each other compared to the rest of the network.

Why Leiden specifically?

• Discovers hierarchical community structures efficiently on large-scale graphs
• Provides multiple levels of communities (like organizing a library by section, then subsection)
• Creates mutually-exclusive, collectively-exhaustive partitions at each level

For a typical corpus, this might produce:

• Level 1: 50 broad communities
• Level 2: 200 medium communities
• Level 3: 500 fine-grained communities

Stage 5: Community Summarization

For each detected community, the system generates a community report using a structured LLM prompt. These reports include:

• Title: Community name representing key entities
• Summary: Executive overview of community structure and relationships
• Impact severity rating: 0-10 score indicating importance
• Rating explanation: Single sentence explaining the rating
• Detailed findings: 5-10 key insights about the community with evidence citations

The prompt ensures outputs are grounded in actual data: “Do not include information where supporting evidence for it is not provided”.

Query Processing Phase: How Answers Are Generated

Stage 1: Query Embedding and Processing

When a user asks a question, the system first converts it to a vector embedding using the same embedding model. Simultaneously, the query is analyzed for entity mentions and intent.

Stage 2: Community Retrieval Strategy

Here’s where retrieval differs significantly from traditional RAG. Graph RAG doesn’t just do semantic search on chunks it intelligently selects which communities to query:

• Option 1: Vector search on community summary embeddings to find semantically similar communities
• Option 2: Direct entity lookup if query mentions specific entities
• Option 3: Entity linking followed by graph traversal to find connected communities
• Option 4 (DRIFT Search): Generic community search followed by local searches to achieve global effects more efficiently

Stage 3: Parallel Intermediate Response Generation (Map Phase)

This is where GraphRAG gets sophisticated. Instead of generating one answer, it uses map-reduce parallel processing:

1. Shuffle: Community report summaries are shuffled and divided into chunks of pre-specified token size (ensuring relevant info isn’t concentrated in one context window)

2. Map: For each chunk, a parallel LLM call generates:

   • An intermediate answer addressing the user query
   • An importance score (0-100) indicating how relevant the answer is

The prompt tells the LLM:

You are an expert agent responding to inquiries based on a knowledge graph.
Given one community report extracted from that knowledge graph, craft a response 
addressing the user's query. You must rely solely on the community description 
provided as context. If insufficient information, respond with "The user cannot 
be answered based on given community context."

Score your response 0-100 indicating helpfulness.

3. Filter: Responses with score 0 are discarded

Stage 4: Aggregation and Ranking (Reduce Phase)

All intermediate responses are sorted by importance score in descending order:

• High-scoring responses are prioritized
• Redundant information is eliminated
• Top-k most relevant responses are selected

Stage 5: Final Response Generation

The final responses are combined into a comprehensive answer using another LLM call that synthesizes all selected intermediate answers into a coherent, grounded response.

Handling Large Documents: Practical Implementation Details

Document Size Management

When documents exceed LLM context windows, GraphRAG handles this through:

1. Chunking optimization: Typical chunk size is 512-2048 tokens, with 50-100 token overlap
2. Iterative extraction: Multiple extraction rounds with continuation prompts until completion signal
3. Batch processing: Neo4j insertions happen in batches to manage memory efficiently
4. Asynchronous processing: Concurrent extraction across chunks (with throttling to avoid rate limits)

For a real-world deployment with 2,000 articles:

• Extraction time: ~35±5 minutes
• Cost: ~$30 (GPT-4o pricing)
• Extracted entities: ~13,000
• Extracted relationships: ~16,000

Relationship Strength Scoring

The system extracts numeric relationship strength (typically 1-10) during extraction, indicating:

• 1-3: Weak relationships (mentioned in passing)
• 4-7: Moderate relationships (clear connection)
• 8-10: Strong relationships (central to both entities)

This scoring helps during retrieval to prioritize stronger connections when traversing the graph.

Graph Updates and Incremental Processing

Challenge with Updates

Unlike traditional RAG where adding documents is straightforward, Graph RAG faces unique challenges:

• Entities extracted from new documents might refer to existing entities in the graph
• New relationships might bridge previously disconnected communities
• Community structure might need recalculation
• Entity descriptions might need merging if the same entity appears in new documents

Current Solutions

While GraphRAG doesn’t have built-in incremental update mechanisms, practical approaches include:

1. Entity Resolution/Disambiguation: When processing new documents, the LLM is prompted to map extracted entities to existing ones using semantic similarity and naming conventions

2. Upsert Operations: Neo4j’s merge operations allow insert-update patterns using consistent entity IDs. Newer versions maintain ID consistency across updates

3. Batch Reprocessing: For substantial updates, some implementations re-run the entire pipeline but use change-detection algorithms to minimize unnecessary reprocessing

4. Temporal Edge Versioning: GraphRAG can track relationship evolution using timestamps—useful when relationships change over time (e.g., “contract amendments”)

5. Streaming Graph Algorithms: Advanced deployments use dynamic graph algorithms that incrementally update community structures as new data arrives, avoiding full recomputation

LinkedIn’s Customer Support System

LinkedIn applied Graph RAG to historical customer support tickets, achieving dramatic improvements:

Implementation approach:

• Constructed knowledge graph from 100k+ support tickets
• Parsed tickets into tree representations to preserve internal structure
• Linked tickets based on contextual similarities, dependencies, and references
• Generated embeddings for each KG node for semantic search

Results:

• 77.6% improvement in Mean Reciprocal Rank (MRR)
• 29.6% reduction in median resolution time (from 40 hours to 15 hours)
• System now handles queries requiring multi-hop reasoning across ticket relationships

Linkedin has tried and see the improvement

Resources

• https://graphrag.com/
• Going Meta - Ep 23: Advanced RAG patterns with Knowledge Graphs
• https://www.falkordb.com/
• Revolutionizing Graph Analytics: Next-Gen Architecture with NVIDIA cuGraph Acceleration
• https://www.nvidia.com/en-in/glossary/networkx/