Advances in computing power and the emergence of large-scale language models have driven dramatic progress in Natural Language Processing.
Now the field faces a different question: how do you improve on an LLM that already exists?
There are the many prompting strategies that followed Chain of Thought,
generation using Retrieval Augmented Generation,
and the LangChain and LangGraph frameworks introduced previously — all of which are ultimately tool chains for using LLMs more effectively.
What I want to introduce today is both an effective knowledge structure and a new technique for enhancing RAG: GraphRAG.
Knowledge Graph
To understand this topic, you first need to know what a graph is.
We won't go too deep, so let's focus specifically on Knowledge Graphs.
What you see above is a graph.
You can think of it as a structure for encoding knowledge, using nodes and edges to express relationships between pieces of information.
In a conventional graph, an edge represents a simple connection.
That connection can carry a variety of meanings, but it can only take one form.
For example, in a citation graph of papers, an edge means only "cites," and in a social graph of people, it means only "has interacted with" — each edge carries exactly one semantic meaning.
Character relationship graph from Les Misérables
Take the Les Misérables character relationship graph as an example.
Here, nodes are characters, and edges represent co-appearances between those characters.
The weight of an edge corresponds to the number of times two characters appear together.
It's quite simple, yet it expresses character relationships remarkably effectively.
Knowledge graphs were designed to overcome the limitation of edges described above.
In other words, the semantic type of an edge is no longer fixed to a single meaning.
Consider the [graph related to the Mona Lisa] below.
Edges no longer carry a single piece of information [https://zilliz.com/learn/what-is-knowledge-graph]
As shown, edges no longer carry a single meaning.
What does a connection between two people mean?
What does a connection between a person and a place mean?
What does a connection between a person and an object mean?
Connections that previously had one fixed meaning are now decomposed into many distinct, labeled relationships.
If the Mona Lisa and da Vinci are simply connected in a plain graph, how would you express what that relationship actually is?
A conventional graph has no way to encode that this is the relationship between a painting and its painter.
Knowledge graphs make this possible by adding knowledge to edges — each edge carries a label describing the relationship it represents.
Graph Retrieval Augmented Generation
Graph RAG is a technique designed to make effective use of this kind of knowledge structure, and it aims to decisively move beyond the limitations of conventional RAG, which is inherently constrained by query embedding.
According to [Microsoft's blog post], conventional RAG has several notable problems:
Conventional RAG struggles to connect the dots — synthesizing holistic insights by identifying shared attributes across diverse pieces of information.
Conventional RAG struggles to holistically understand summarized semantic concepts over large data collections or even singular large documents.
These observations point to two conclusions.
First, LLMs are extremely powerful tools — and here's why that matters: if accurate information is simply "provided" to an LLM, it has little difficulty understanding and generating meaningful responses.
So what's actually the problem? It's the Retrieval component built into RAG. It's reasonable to conclude that the retrieval mechanism itself is the bottleneck.
Conventional RAG fails to supply the LLM with the information it actually needs, and that's where the problem originates.
Wu, J., Zhu, J., Qi, Y., Chen, J., Xu, M., Menolascina, F., & Grau, V. (2024). Medical graph rag: Towards safe medical large language model via graph retrieval-augmented generation. arXiv preprint arXiv:2408.04187.
The medical domain is highly rigid — it deals with life-critical information and demands extremely robust knowledge representation.
[The study referenced above] describes how to build a GraphRAG system for the medical domain.
The key things to note are the Entities Extraction step shown in step 2 of the figure, and the Relationship Linking step shown in step 4.
The paper explains this with dense notation, but the intuition is straightforward:
- First, from a given information chunk H, extract individual information units e.
- Create links so that chunk H serves as a reference for each unit e.
- Examine the relationships between units e within chunk H and create the corresponding links.
This process forms the backbone of the overall knowledge graph.
In practice, the best approach is to conduct the entire process using human experts or authoritative reference sources.
However, this study performs the entire process using prompts and an LLM.
(Convenient, yes — but given that this is the medical domain, that's a bit of a concern...)
This is still quite encouraging, because one of the hardest challenges in working with graphs is building a clean, well-structured graph in the first place.
It has long been understood that knowledge graphs are powerful, but actually constructing one has always been prohibitively expensive.
In some ways, the most significant contribution of this study may be demonstrating that even a knowledge graph built with an LLM is sufficient to improve LLM performance.
Graph Retrieval
We've looked at what a knowledge graph is and how recent LLM-based research builds one.
The final question is: given a knowledge graph, how does an LLM actually retrieve from it?
The study above uses a tag-based approach, which the authors call U-Retrieval.
At graph construction time, tags are assigned appropriately to nodes, as shown above.
When a user query Q arrives, an LLM and prompt are used to first extract T_Q from the query.
The graph is then traversed layer by layer, searching for the tag that maximizes similarity between T_Q and T^i[j].
After the relevant tag is found, the information units e whose embedding similarity to the query is highest are retrieved.
The resulting set of information units acts as the Retrieval input to the LLM.
The neighboring nodes connected to those units are also fetched along with them.
This is arguably one of the most intuitive yet effective retrieval strategies possible.
Exhaustively searching every knowledge node in a graph is both impractical and computationally infeasible.
Tags are used to constrain the search space to a manageable scope.
Several other studies take a similar approach.
[LEGO-GraphRAG] extracts data through three modular steps.
Let's go through them briefly.
The first step is Subgraph-Extraction.
The goal of SE is exactly what was described earlier: construct a small-scale subgraph from the full graph to reduce the search space.
This study performs query-based search to find related subgraphs, then merges them all to form the final search space.
(In practice, this step uses algorithms such as Personalized PageRank (PPR) or Random Walk with Restart.)
Next, Path-Filtering is used to find the optimal reasoning path P from the given subgraph g.
This step searches for paths within the subgraph using entities extracted from the query.
Concretely, the study uses complete path-filtering algorithms such as BFS and DFS, shortest path-filtering algorithms such as Dijkstra's algorithm, and iterative path-filtering algorithms such as Beam Search.
Finally, Path-Refinement takes the set of paths P produced in the previous step and narrows it down to a single best path.
The paper doesn't describe the internals of this step in detail, but from the tables in the paper it appears to use an LLM with a prompt to select the single best path.
[Another study] takes the same approach.
Known as GNN-RAG, it follows the same general strategy:
- Infer a dense subgraph from the user's query to narrow down retrieval candidates.
- Search within those candidates for the path most relevant to the query.
For now, the key takeaway from this post is that GraphRAG approaches the retrieval problem from a similar angle across multiple lines of research.
Next time, we'll build a graph using GraphRAG and benchmark it against conventional RAG to evaluate the performance difference.