# GraphRAG

Retrieval over a knowledge graph of entities and relationships, so answers can follow connections rather than only match text.

**Rests on:** Graph Traversal BFS and DFS

*LLMs and Generative AI · Retrieval-Augmented Generation*


## Why learn this

This technique allows a system to answer questions where the truth lies in how different facts relate to one another, not just in finding documents that contain the same words as your question. It prepares you for systems that can reason through complex information chains, combine keyword matching with deep meaning analysis, and build personal assistants for companies that truly understand their own records. By relying on these structured connections, the system avoids inventing plausible-sounding lies—a problem known as hallucination—because it follows verified links between facts rather than guessing based on probability.


## The intuition

Imagine you have a box of recipe cards. Each card has a title and a list of ingredients. If someone asks, 'What can I make with paneer and spinach?', you can flip through the cards and find the ones that mention both. That is like finding similar documents: it looks for matches in meaning. But now suppose someone asks, 'Which of my friends would enjoy a dinner party with both a vegetarian and a strict vegan guest?' The answer is not on any single card. You need to know that Priya is vegetarian, that Rohan is vegan, that both of them like Italian food, and that the restaurant you have in mind serves both. That knowledge is spread across multiple cards, and the answer comes from connecting them: Priya likes vegetarian meals, which connects to the restaurant's menu, which connects to Rohan's preference. That is the problem GraphRAG solves.

To solve this, we build a map. On this map, individual items like people or places are dots. The facts linking them are lines. When you ask a question that requires linking these items together, GraphRAG does not just look for matching words. It starts at one dot (for example, Priya), follows the line to the next dot (the restaurant), and follows another line to Rohan. It walks the path. The key insight is that the answer is not in any single document; it is in the connections between facts scattered across many documents.


## An analogy

Think of a city's road network. A map is a graph: intersections are entities like 'Chai Point' or 'Metro Station', and roads are relationships like 'is next to' or 'is 200 metres from'. If someone asks, 'How do I get from the station to the bookshop?', you look at the map and follow the roads. Now imagine you have a stack of photo albums, each with pictures of a different part of the city. If you only had the photos, you would have to flip through every album to find a picture of the station and a picture of the bookshop, then try to guess if they are connected—but they might not even be in the same album. That is like traditional search: you have the pieces, but not the connections. GraphRAG is the map. It is built by looking at all the photos (documents), extracting the landmarks (entities) and the roads between them (relationships), and drawing them on a single map. When someone asks a question that spans multiple landmarks, you trace the route on the map instead of searching through photos. Where the analogy stops: a map is static, but a knowledge graph can be updated as new documents arrive, and it can show any kind of relationship, not just physical distance, such as 'works for' or 'is allergic to'.


## Definition

GraphRAG is a method that converts a collection of documents into a structured map of facts (entities) and the links between them (relationships), then answers questions by following those links to find connected information rather than relying solely on word matching.


## How it connects

This concept builds on Embeddings, which is how text is converted into numerical representations for search, and Vector Databases, which are systems that store and retrieve those numbers efficiently. It also connects closely with Reranking and Retrieval Quality, because even with a map, you must still judge how well the retrieved information matches your intent. Most importantly, it complements Hybrid and Semantic Search, as you will often combine simple word matching with this deeper connection tracking. It serves as the foundation for Agentic Retrieval, where an AI actively chooses which paths to walk on the map, and Enterprise Knowledge Assistants, where the map is built from a company's private documents.


## The mathematics

GraphRAG uses two main ideas from graph theory: how to move through a network of connections, and how to measure how similar two things are. Graph theory is the study of points (called **nodes** or **vertices**) and the lines connecting them (called **edges**). This is different from calculus, which studies change over time. Here, we care about structure.

**1. Building the Graph**
First, we turn text into a graph. We identify key items in the text, such as people or places, and call them **nodes**. We identify how they relate to each other, such as "works for" or "located in," and call these **edges**. Each edge gets a number called a **weight** between 0 and 1. A weight of 1 means a very strong connection; a weight of 0.1 means a weak one.

**2. Measuring Similarity with Cosine Similarity**
To find the right starting point for a query, we need to compare the meaning of the question to the meaning of the nodes. We do this using **cosine similarity**. 

Imagine each node (like "Alice") and the query (like "Who does Alice know?") are represented by a list of numbers. These lists have many positions. Cosine similarity asks: Do these two lists point in roughly the same direction? 
- If the lists are very similar, the score is close to 1.
- If they are opposite, the score is close to -1.
- If they are unrelated, the score is near 0.

This gives us a number between -1 and 1 that tells us how well the query matches a specific node based on its text description.

**3. Combining Text Match and Graph Walks**
Once we have the graph, we answer the query by combining two scores:
1. **Text Score**: How similar is the query to the node's name/description? (Calculated via cosine similarity).
2. **Graph Score**: How close is the node to the starting point in the network?

The final relevance score for a node n given a query q is calculated as:

score(q, n) = Text_Score + beta * Graph_Proximity

Here is what each part means:
- **Text_Score**: The cosine similarity between the query and the node.
- **beta** (read "beta"): A small number, like 0.1 or 0.5. It controls how much we trust the graph structure versus the text match. If beta is high, we care more about who is connected to whom. If beta is low, we care more about exact word matches.
- **Graph_Proximity**: This measures closeness in the graph. A common way to calculate this is using the **shortest path**. The shortest path is the route from the starting node to node n that uses the fewest number of steps (edges). We sum the weights of the edges along this path. For example, if the path has two edges with weights 0.8 and 0.9, the proximity might be calculated as their product or sum, depending on the specific algorithm. In simple terms, a shorter path with stronger edges gets a higher proximity score.

**Summary of the Process**
1. Convert text into a graph of nodes and weighted edges.
2. For a new query, find the node most similar to it using cosine similarity (the Text Score).
3. From that starting node, walk through the graph to other nodes.
4. Calculate the final score for each reachable node by adding the Text Score (adjusted for that node) and the Graph Proximity (weighted by beta).
5. Return the nodes with the highest final scores as the retrieved context.


## A worked example

Let us build a tiny graph to see how this works.

**The Setup**
We have three entities (nodes):
- Node A: "Alice"
- Node B: "Bob"
- Node C: "Cat"

We have two relationships (edges) with weights:
1. Alice knows Bob. Weight = 0.8.
2. Bob owns Cat. Weight = 0.9.

So the graph looks like this:
Alice --(0.8)--> Bob --(0.9)--> Cat

**The Query**
Question: "What does Alice know about Cat?"

**Step 1: Find the Starting Node**
We look for the node most similar to the query "Alice". Clearly, Node A ("Alice") is the best match. We start our walk here.
Text_Score for Alice = 1.0 (perfect match).

**Step 2: Walk the Graph**
We want to find information about "Cat". Is Cat connected to Alice?
- From Alice, we follow the edge to Bob. This is 1 step.
- From Bob, we follow the edge to Cat. This is another step.
- Total steps from Alice to Cat = 2 steps.

**Step 3: Calculate Graph Proximity**
Let us assume a simple rule for proximity: multiply the weights of the edges on the shortest path.
Path: Alice -> Bob -> Cat
Edge 1 weight: 0.8
Edge 2 weight: 0.9
Graph_Proximity = 0.8 * 0.9 = 0.72

**Step 4: Calculate Final Score for Node C (Cat)**
We need the Text_Score for Cat relative to the query "What does Alice know about Cat?". Let us say the text description of Cat is just "Cat", and the query contains "Cat", so they are somewhat similar but not identical because the query is about knowledge, not just identity. Let us assign a cosine similarity score of 0.6 for this example.

Let beta = 0.5 (we value graph connections half as much as text match).

Final Score for Cat = Text_Score + (beta * Graph_Proximity)
Final Score for Cat = 0.6 + (0.5 * 0.72)
Final Score for Cat = 0.6 + 0.36
Final Score for Cat = 0.96

**Step 5: Retrieve Context**
The system sees that Cat has a high score (0.96) because it is textually relevant AND graphically close to Alice. It retrieves the path:
Alice knows Bob, and Bob owns Cat.

This tells us that Alice's knowledge about Cat is mediated through Bob. This is more useful than just finding documents that mention "Alice" and "Cat" separately, because it shows the specific link between them.


## From scratch, in Python

```python
class KnowledgeGraph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}

    def add_node(self, name):
        self.nodes.add(name)

    def add_edge(self, from_name, to_name, relation, strength):
        # store edges as (to_name, relation, strength) for a given from_name
        if from_name not in self.edges:
            self.edges[from_name] = []
        self.edges[from_name].append((to_name, relation, strength))

    def get_neighbours(self, node_name):
        return self.edges.get(node_name, [])

    def traverse(self, start_node, steps):
        """Return all nodes reachable within 'steps' hops from start_node."""
        reached = set()
        frontier = [start_node]
        for _ in range(steps):
            next_frontier = []
            for node in frontier:
                for (to, relation, strength) in self.get_neighbours(node):
                    if to not in reached:
                        reached.add(to)
                        next_frontier.append(to)
            frontier = next_frontier
        return reached

graph = KnowledgeGraph()
# add nodes and edges
graph.add_node('Alice')
graph.add_node('Bob')
graph.add_node('Cat')
graph.add_edge('Alice', 'Bob', 'knows', 0.8)
graph.add_edge('Bob', 'Cat', 'owns', 0.9)

# retrieve for query 'what does Alice know about Cat?'
start = 'Alice'
relevant = graph.traverse(start, 2)
print('Relevant entities:', relevant)
```


## The same thing, with a framework

```python
In practice, you'd use a graph database like Neo4j or a Python graph library like NetworkX. For example, with NetworkX:

import networkx as nx
G = nx.Graph()
G.add_edge('Alice', 'Bob', relation='knows', strength=0.8)
G.add_edge('Bob', 'Cat', relation='owns', strength=0.9)
# find all nodes within 2 hops of Alice
nodes = nx.single_source_shortest_path_length(G, 'Alice', cutoff=2)
print(nodes)
```


## What the code does

The from-scratch code creates a simple graph. First, we define a class `KnowledgeGraph` with a `nodes` set (to keep each entity once) and an `edges` dictionary (which maps a node name to a list of tuples, each tuple being the connected node, the relation name, and the strength). The `add_node` and `add_edge` methods let us build the graph. The `traverse` method does a breadth-first search: it keeps a `frontier` list of nodes to explore, and for each step, it gets the neighbours of the nodes in the frontier, adds them to the `reached` set, and puts them in the next frontier. After the specified number of steps, it returns the set of reached nodes — those are the relevant entities. We then create a graph with Alice, Bob, and Cat, connect them, and call `traverse` with start='Alice' and steps=2, which returns {'Bob', 'Cat'} because Bob is one hop away and Cat is two. The framework version shows how a library like NetworkX does the same traversal in a single line — but now you know what it does underneath: it's walking the edges just like your loop.


## Common misconceptions

**GraphRAG replaces vector search** — GraphRAG is strictly better than vector search, so I should always use it.

GraphRAG fails for queries that rely on semantic similarity or paraphrase. If someone asks 'What are the health benefits of green tea?', a vector search will find a document that says 'drinking this herbal infusion may improve cardiovascular health' even if the word 'green tea' never appears. GraphRAG needs the entities to be explicitly in the graph; it can't infer like an embedding can. In fact: GraphRAG complements vector retrieval. Use vector search for semantic similarity and keyword for exact terms; use GraphRAG when the answer depends on relationships between entities.

**GraphRAG is automatic** — I can feed my documents into a tool and get a knowledge graph automatically, with no effort.

Building a useful graph requires deciding what counts as an entity, how to merge 'Dr. Smith' and 'John Smith', and which relations to extract. If the extraction is noisy, the graph is useless. The library notes 'Graph construction and entity resolution are the real cost'. In fact: Expect a significant data engineering effort to build a clean, correct graph. The traversal is the easy part.

**A graph is a database of facts** — A knowledge graph stores all the facts from my documents, so I can query anything.

A knowledge graph stores entities and relations, not every sentence. If a fact isn't extractable as an entity-relation triple, it won't be in the graph. You still need the original documents for citations and details. In fact: A graph gives you a skeleton of connections; the full text is still needed for precise evidence and citations.

**One hop is enough** — If a question asks about 'A and B', I just need to retrieve nodes A and B.

The answer often lies in the path between them. For 'How is Alice related to Cat?', you need the intermediate node Bob. Stopping at the two named nodes misses the connection. In fact: Graph traversal often requires multiple hops to find the connecting path. The number of hops is a design choice.

**Edge strengths are confidence in the fact** — A relationship strength of 0.9 means I am 90% sure the relationship is true.

The strength might represent the frequency of co-occurrence, a similarity score, or a manually assigned importance. It does not necessarily measure factual certainty. A 0.9 edge might be between two entities that just appear often together, not because they are truly connected in the way you think. In fact: Edge weights are model choices. They can encode confidence, but you must know what they mean in your graph before interpreting them.


## In short

GraphRAG (Retrieval over a knowledge graph) means: build a graph of entities and relationships from your documents, then at query time walk that graph to find the connected facts that answer the question. It's not a replacement for vector search — it's a complement. The real work is in building a clean graph (entity resolution). It unlocks agentic retrieval, multi-hop answers, and enterprise assistants.


## Where this is used

GraphRAG is used in real systems when the answer requires connecting facts. In **large language models** (like ChatGPT), you can't just rely on the model's internal memory for specific facts about a company's products or a research area — you need to ground it with retrieved information. If you have a knowledge graph of your company's products, customers, and service issues, you can use GraphRAG to answer questions like 'Which customers are affected by the same bug as this one?' The model generates a query, the GraphRAG system walks the graph, and the retrieved subgraph (entities and relationships) is placed in the prompt to ground the answer. In **small language models** running on phones or laptops, GraphRAG is even more valuable because you can't fit a huge model; you can store a compact knowledge graph of the user's contacts, messages, and calendar, and answer 'What time is my next meeting with Priya?' by traversing the graph on-device — no cloud needed. In **retrieval-augmented generation**, GraphRAG complements vector retrieval. You might first do a vector search to get the top documents, then extract entities and run a graph traversal to expand the context with related facts. Microsoft's GraphRAG paper shows this hybrid approach improves answer coverage for multi-hop questions. In **agentic systems** that plan and call tools, the agent might decide to call a graph query tool multiple times, following links to gather evidence. For example, an agent researching a medical condition might look up a drug, then ask the graph 'which patients are allergic to this drug?' and use that to refine its search. In **everyday applied ML**, GraphRAG is used for recommendation systems (recommending movies by connecting actors, directors, genres), fraud detection (connecting suspicious accounts via shared phone numbers or addresses), and forecasting (connecting weather events to supply chain disruptions). The developer's job is to build the graph: they extract entities from documents, resolve duplicates (e.g., 'Dr. Smith' and 'John Smith' might be the same person), and define relationships. They then write queries like `MATCH (a)-[:KNOWS]->(b) WHERE a.name='Alice' RETURN b.name` (in Cypher, the Neo4j query language). What breaks when it's done badly? If the graph is built on poor entity resolution, you get noise — the traversal goes to irrelevant nodes and the answer is grounded in wrong connections. If the graph is too sparse, you get low recall — the path is missing, so the answer is incomplete. The library's note says 'Graph construction and entity resolution are the real cost', and that matches practice: most of the effort is in cleaning the data, not in running the traversal.


---

Read this on the web: https://basavapurushottam.com/learn-ai/graphrag
