Source-linked AI summary
GRAG: Graph Retrieval-Augmented Generation
Yuntong Hu, Zhihan Lei, Zheng Zhang, Bo Pan, Chen Ling, Liang Zhao
TL;DR
Naive RAG retrieves individual documents and therefore does not address networked textual graphs whose structure can matter for retrieval and generation. GRAG retrieves query-relevant textual subgraphs and presents their graph and text views to LLMs, significantly outperforming RAG-based retrievers and LLM baselines on multi-hop graph reasoning tasks.
Problem
Naive RAG focuses on individual documents, whereas networked documents require retrieval and generation that account for joint textual and topological information.
Method
GRAG uses divide-and-conquer retrieval with ego-graphs and soft pruning, then supplies textual graphs to LLMs through complementary graph and text views.
Results
GRAG significantly outperforms RAG-based retrievers and LLM baselines on multi-hop graph reasoning tasks.
Takeaways & Limitations
Graph-aware retrieval and generation improve LLM performance in scenarios requiring detailed multi-hop reasoning over textual graphs.
Takeaways & Limitations
GRAG’s retrieval efficiency depends on initial node ranking and pruning quality, which can produce suboptimal retrieval when graph structure or node importance is difficult to estimate.
Abstract
from arXiv · showhide
Naive Retrieval-Augmented Generation (RAG) focuses on individual documents during retrieval and, as a result, falls short in handling networked documents which are very popular in many applications such as citation graphs, social media, and knowledge graphs. To overcome this limitation, we introduce Graph Retrieval-Augmented Generation (GRAG), which tackles the fundamental challenges in retrieving textual subgraphs and integrating the joint textual and topological information into Large Language Models (LLMs) to enhance its generation. To enable efficient textual subgraph retrieval, we propose a novel divide-and-conquer strategy that retrieves the optimal subgraph structure in linear time. To achieve graph context-aware generation, incorporate textual graphs into LLMs through two complementary views-the text view and the graph view-enabling LLMs to more effectively comprehend and utilize the graph context. Extensive experiments on graph reasoning benchmarks demonstrate that in scenarios requiring multi-hop reasoning on textual graphs, our GRAG approach significantly outperforms current state-of-the-art RAG methods. Our datasets as well as codes of GRAG are available at https://github.com/HuieL/GRAG.
1 Introduction
GRAG extends RAG to networked textual graphs by retrieving relevant subgraphs and preserving their textual and topological context for generation. Experiments show strong gains on multi-hop graph reasoning tasks.
- Motivation: GRAG addresses naive RAG’s focus on individual documents by incorporating document-network information during retrieval and generation.Network structure is important for retrieving relevant documents and prompting LLMs.
- Motivation: GRAG is motivated by the need to pass textual subgraphs’ joint textual and topological information to LLMs while preserving their interdependencies.This is identified as a central generation challenge for networked documents.
- Method: A divide-and-conquer strategy retrieves relevant ego-graphs, then refines and unions them with soft pruning to approximate the optimal textual subgraph.The strategy avoids exhaustive NP-hard subgraph search.
- Results: GRAG significantly outperforms RAG-based retrievers and LLM baselines on multi-hop graph reasoning tasks.Frozen LLM with GRAG also outperforms a fine-tuned LLM on all tasks.
- Contributions: The framework formulates graph retrieval-augmented generation and introduces hierarchical text descriptions intended to preserve topological information.The contribution list identifies both GRAG formulation and topology-preserving prompting as core contributions.
2 Related Work
Related work uses LLMs for textual graph understanding, graph reasoning, and retrieval of structurally meaningful graph elements. These approaches range from relevant nodes and triples to paths and joint graphs that combine question context with retrieved information.
- Prompt tuning: Prompt-tuning approaches modify model inputs rather than model parameters, including learned soft prompts and automated prompt construction.These methods support task-specific adaptation while preserving the original model parameters.
- LLMs for graphs: LLMs support graph applications through text embedding for node and edge attributes and contextual reasoning for graph answering and reasoning.The cited applications include classification, knowledge-graph creation, graph reasoning, and zero-shot graph answering.
- Graph retrieval: Prior methods retrieve relevant nodes, triples, paths, or joint graphs rather than restricting retrieval to isolated documents.Some methods simplify retrieval to finding a path between the question and target entity.
- Graph retrieval: Retrieval methods increasingly incorporate textual and topological information to capture structural relationships in graph-structured data.This line of work moves beyond retrieving individual graph elements.
3 Problem Formalization
GRAG formalizes generation over a textual graph by retrieving an optimal textual subgraph for a query and supplying it to an LLM. Textual graphs and subgraphs explicitly include both graph structure and natural-language node and edge attributes.
- Textual graphs: A textual graph is defined as nodes and edges together with natural-language attributes for each node and edge.This representation combines topology with textual content.
- Textual subgraphs: A textual subgraph selects subsets of the graph’s nodes and edges while retaining their associated textual attributes.The subgraph set is expressed using the power sets of the node and edge sets.
- GRAG objective: GRAG seeks an optimal textual subgraph for query q and incorporates it into an LLM to improve generation relevance to the graph’s embedded knowledge.The objective is defined over the set of all subgraphs of the textual graph.
- Generation formulation: The generation formulation conditions each output token on its preceding tokens, the query, and the retrieved optimal subgraph.The query and subgraph information are concatenated as the model input context.
4 Methodology
GRAG retrieves query-relevant textual subgraphs efficiently and supplies them to LLMs through complementary textual and graph representations. Its methodology combines ego-graph retrieval, soft pruning, hierarchical text conversion, and graph-based soft prompts.
- Textual Subgraph Retrieval: GRAG uses a divide-and-conquer strategy that retrieves relevant ego-graphs, merges them, and softly prunes redundant nodes and edges.The approach approximates optimal subgraph retrieval while avoiding exhaustive search over all subgraphs.
- Textual Subgraph Retrieval: The retrieval space is reduced from 2^|V|+|E| possible subgraphs to |V| ego-graphs, giving the retrieval-then-pruning approach linear-time complexity.Ego-graphs can be indexed offline, then ranked and refined during retrieval.
- Textual Subgraph Retrieval: Soft pruning learns query-dependent scaling factors that mask distant or irrelevant nodes and edges before merging the selected subgraphs.Entities farther from the query receive scalar values closer to 0, reducing their influence on the resulting subgraph.
- Textual Graph Augmented Generation: GRAG represents retrieved textual graphs through a text view that converts ego-graphs into hierarchical descriptions while preserving additional non-tree edges.BFS constructs a rooted tree, preorder traversal serializes node and edge text, and remaining edges are inserted into the description.
- Textual Graph Augmented Generation: Its graph view uses a GNN with relevance-scaled message passing and an MLP to align graph embeddings with the LLM token space.The graph representation supplies topological information as a soft prompt, while the query and hierarchical description form the text-based prompt.
5 Experiments
Experiments evaluate GRAG on graph reasoning benchmarks against retrieval-based and LLM baselines, including transfer, scale, retrieval-size, hallucination, and ablation analyses. GRAG outperforms the compared baselines, while the studies identify the roles of pruning, graph encoding, textual attributes, and subgraph size.
- 5.2 Main Results: GRAG significantly outperforms RAG-based retrievers and LLM baselines across graph reasoning tasks and datasets.It outperforms the fine-tuned LLM on all reported tasks without fine-tuning the LLM.
- 5.2 Main Results: Fine-tuning adds only marginal gains when GRAG is used, with WebQSP Hit@1 increasing from 0.7236 to 0.7275.The authors suggest GRAG can reduce training costs for graph-related tasks.
- 5.2 Main Results: GRAG transfers across datasets: training on WebQSP improves ExplaGraphs accuracy over the naive LLM by 33.77%.The transfer result is reported in the cross-dataset evaluation.
- 5.3 Discussion: Using 2-hop ego-graphs consistently outperforms 1-hop ego-graphs at the same retrieval count, but adding more subgraphs can introduce irrelevant information and reduce performance.Performance drops when the number of ego-graphs increases from 15 to 20, while larger numbers produce smaller standard deviations.
- 5.4 Ablation Study: Ablations show that graph encoding, soft pruning, and textual node and edge attributes are important for generation quality.Without graph encoding, WebQSP Hit@1 falls from 0.7275 to 0.5835; excluding text attributes yields 0.4496, a 38.2% decrease.
6 Conclusion
GRAG extends RAG to graph-based scenarios by retrieving query-relevant textual subgraphs and giving LLMs complementary graph and text views. It significantly outperforms LLM and RAG-based baselines on detailed multi-hop reasoning while allowing a frozen LLM to outperform fine-tuned LLMs at lower training cost.
- GRAG significantly outperforms LLM baselines and RAG-based LLMs on detailed multi-hop reasoning over textual graphs.
- GRAG retrieves query-relevant textual subgraphs using K-hop ego-graphs and soft pruning to approximate the optimal subgraph.
- GRAG provides LLMs with complementary graph and text views of textual graphs to support graph-context understanding.
- A frozen LLM enhanced by GRAG can outperform fine-tuned LLMs at reduced training cost.
7 Limitations
GRAG’s textual subgraph retrieval depends on the quality of its initial node ranking and pruning mechanism. When graph structure or node importance is difficult to estimate, retrieval may become suboptimal.
- GRAG’s retrieval efficiency depends on the quality of initial node ranking and pruning.
- Difficult estimation of graph structure or node importance can lead to suboptimal retrieval performance.
A.1 Hierarchical Description
A 2-hop ego-graph is represented as a nested, indented list whose hierarchy mirrors graph connectivity. Node descriptions preserve textual content while indentation preserves topological relationships.
- A 2-hop ego-graph is transformed into a nested, indented list reflecting connections between nodes.
- Node descriptions or titles preserve textual information such as cited-paper titles or key phrases.
- Indentation and nested levels preserve parent-child connectivity and the graph’s branching structure.
A.2 Comparison Retrievers
The comparison includes statistical, sentence-embedding, multilingual, contrastive, and graph-aware retrievers. These methods use different representations or retrieval objectives to identify relevant graph content.
- The comparison covers BM25, MiniLM-L12-v2, LaBSE, mContriever, E5, and G-Retriever.
- BM25 estimates document relevance from term frequency, inverse document frequency, and document length.
- MiniLM-L12-v2, LaBSE, mContriever, and E5 retrieve using sentence embeddings or bi-encoder architectures with semantic or contrastive objectives.
- G-Retriever retrieves relevant nodes and edges before constructing a subgraph with a Prize-Collecting Steiner Tree method.
A.3 Implementation
The experiments use specified data splits, retrieval metrics, and graph-retrieval settings to evaluate performance across datasets. WebQSP performance generally improves as more entities are retrieved.
- Implementation: The ExplaGraphs and WebQSP datasets use 60%/20%/20% and 60%/5%/35% training, validation, and test splits, respectively.
- Evaluation Metrics: Hit@1 measures whether the top retrieved result is correct, while F1 balances precision and recall.
- Evaluation Metrics: Recall measures the proportion of relevant entities retrieved, while Accuracy measures the proportion of correctly answered questions.
- Effects of the Number of Retrieved Entities: Increasing the number of retrieved entities generally improves performance on WebQSP and ExplaGraphs.Top-k denotes retrieving k nodes and k edges; Figure 5 reports the effect on WebQSP.