# GRAG: Graph Retrieval-Augmented Generation

Yuntong Hu, Zhihan Lei, Zheng Zhang, Bo Pan, Chen Ling, Liang Zhao Department
of Computer Science Emory University Atlanta, GA 30322, USA
<EMAIL_ADDRESS>
###### Abstract

While Retrieval-Augmented Generation (RAG) enhances the accuracy and relevance
of responses by generative language models, it falls short in graph-based
contexts where both textual and topological information are important. Naive
RAG approaches inherently neglect the structural intricacies of textual
graphs, resulting in a critical gap in the generation process. To address this
challenge, we introduce Graph Retrieval-Augmented Generation (GRAG), which
significantly enhances both the retrieval and generation processes by
emphasizing the importance of subgraph structures. Unlike RAG approaches that
focus solely on text-based entity retrieval, GRAG maintains an acute awareness
of graph topology, which is crucial for generating contextually and factually
coherent responses. Our GRAG approach consists of four main stages: indexing
of $k$-hop ego-graphs, graph retrieval, soft pruning to mitigate the impact of
irrelevant entities, and generation with pruned textual subgraphs. GRAG’s core
workflow—retrieving textual subgraphs followed by soft pruning—efficiently
identifies relevant subgraph structures while avoiding the computational
infeasibility typical of exhaustive subgraph searches, which are NP-hard.
Moreover, we propose a novel prompting strategy that achieves lossless
conversion from textual subgraphs to hierarchical text descriptions. Extensive
experiments on graph multi-hop 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 while
effectively mitigating hallucinations.

##  1 Introduction

Large Language Models (LLMs) have demonstrated remarkable capabilities in a
variety of reasoning tasks, including on graph-based data (Hu et al., 2023a;
Chen et al., 2024; Fatemi et al., 2023). However, LLMs themselves struggle
with factual errors due to limitations in their training data and a lack of
real-time knowledge (Mallen et al., 2023; Min et al., 2023). Retrieval-
Augmented Generation (RAG) (Lewis et al., 2020; Guu et al., 2020), which
integrates external data retrieval into the generative process, has been
widely used for its ability to help LLMs generate more relevant answers and
reduce factual errors (Tang and Yang, 2024). However, RAG-based retrievers
focus solely on individual documents and retrieve relevant candidates based on
text similarity. In many situations, we do have important correlations among
documents, which are started to be heavily researched in recent years, called
textual graphs such as scientific article networks, recommender systems, and
knowledge graphs (He et al., 2023; Jin et al., 2023; Li et al., 2023). For
more complex and larger-scale reasoning tasks, we need to leverage the
semantics inside and across documents (Yang et al., 2024; Tang and Yang,
2024). For example, in Figure 1, we raise a question-answering (QA) task where
the question is: How can AI’s recent progress advance solar flare prediction?
To answer this question, we need to locate the subgraph centering on the
papers on existing AI techniques and their applications in solar flare
prediction, then further traverse the citation graph through newer AI papers
while considering their new advantages that can better tackle the hurdles in
solar flare prediction. Such consideration of the rich semantic information
correlating the documents cannot be handled by traditional RAG methods.

Figure 1: GRAG retrieves subgraphs relevant to the query rather than discrete
documents like RAG to reduce the negative impact of semantically similar but
irrelevant documents (in red) on the generation.

To tackle this issue, this work formulates a new problem called Graph
Retrieval-Augmented Generation (GRAG), which requires to first retrieve query-
relevant subgraphs in textual graphs, and perform the LLM generation with
joint text and topological information. Both of these two are nontrivial to be
addressed. Specifically, first, the retrieval of relevant textual subgraphs on
large-scale textual graphs is challenging due to the NP-hard nature of the
problem (Johnson and Garey, 1979) and the need to balance efficiency and
accuracy. Additionally, integrating both textual and topological information
in the retrieved textual subgraphs into a coherent generative framework
presents significant challenges.

This paper proposes a computational framework for GRAG. To address the
challenge of efficient textual subgraph retrieval, we propose a divide-and-
conquer strategy that indexes $k$-hop ego-graphs and employs a soft pruning
mechanism to reduce the influence of irrelevant entities. To handle the
challenge of integrating textual and topological information, we introduce a
novel dual prompting method that divides prompts into two parts: hard prompts
and soft prompts. Retrieved textual subgraphs are converted into hierarchical
text descriptions and combined with the query to form the hard prompts,
effectively preserving both semantic nuances and graph topology. Meanwhile,
soft prompts retain the graph’s topological information by encoding the graph
into embeddings via graph encoders. More specifically, our GRAG approach
involves four main stages. First, $k$-hop ego-graphs within the main textual
graph are indexed and converted into graph embeddings using a pre-trained
language model (PLM). Next, the system retrieves the top$N$ textual subgraphs
most relevant to the query. Third, a novel soft pruning approach reduces the
influence of irrelevant entities within the retrieved textual subgraphs by
learning scaling factors based on their relevance to the query. This provides
an approximate solution to the most relevant textual subgraph structures,
avoiding the NP-hard problem of exhaustively searching all subgraphs. Finally,
the generation stage integrates both the pruned textual subgraphs and the
original query, utilizing GNNs to aggregate information and then align the
graph embedding with the LLM’s text vectors.The generation by LLMs is
controlled by both hard prompts and soft prompts.

Empirical results on multi-hop graph reasoning tasks demonstrate that our GRAG
approach significantly outperforms RAG-based retrievers and LLM baselines in
graph reasoning scenarios. In particular, Frozen LLM with GRAG outperforms
fine-tuned LLM on all tasks with much lower training cost.

The main contributions of this article are summarized below:

  * •

We formulate the problem of Graph Retrieval-Augmented Generation (GRAG) and
propose an efficient computational framework for GRAG, addressing the
limitations of RAG methods in handling graph-based contexts.

  * •

We provide an approximate solution for retrieving the most relevant textual
subgraphs, efficiently avoiding the NP-hard problem of exhaustive subgraph
searches. Furthermore, we introduce a novel prompting method to convert
textual subgraphs into hierarchical text descriptions without losing both
textual and topological information.

  * •

Extensive experiments on graph multi-hop reasoning benchmarks demonstrate that
GRAG significantly outperforms current state-of-the-art RAG methods in graph-
related scenarios.

##  2 Related Work

###  2.1 LLMs in Graph Related Tasks

Large Language Models based on the Transformer architecture have shown
promising capabilities in reasoning on graphs. On the one hand, the text
embedding capability of LLMs helps encode textual node & edge attributes,
which directly benefits the classification task (Hu et al., 2023a; Chen et
al., 2023, 2024) and knowledge graph creation (Trajanoska et al., 2023; Yao et
al., 2023). On the other hand, the contextual reasoning capabilities of the
LLM benefits the graph reasoning (Wang et al., 2024; Jiang et al., 2023; Luo
et al., 2023) and graph answering in zero-shot scenarios (Baek et al., 2023;
Hu et al., 2023b). While training on large corpora of text data develops
robust language understanding, it does not inherently equip LLMs to understand
or reason about graph-structured data, as textual data lacks explicit
topological information. Therefore, soft prompts that aggregate information
from other modalities can be a powerful tool to help LLMs process and
understand information in modalities beyond just text (Tian et al., 2024; He
et al., 2024). However, generating graph soft prompts that are suitable for
LLMs remains an open problem. To address this problem, we propose a novel soft
prompting strategy for graphs. Furthermore, we develop a novel hard prompting
method to generate text descriptions of graphs while preserving topological
information.

###  2.2 Retrieval Augmented Generation (RAG)

One limitation of LLMs is their dependence on the currency of their training
data. RAG (Lewis et al., 2020) addresses this by enhancing LLMs with
information retrieval systems, enabling the generation of more accurate and
contextually relevant responses through the incorporation of the most current
documents. Naive RAG approaches (Ram et al., 2023; Gao et al., 2023) achieve
this by splitting text in documents into chunks and mapping these chunks into
a vector space to calculate similarity to the query vector. However, for
augmented generation that requires retrieval on graphs, while RAG can help by
retrieving relevant entities within the graph, it does not account for
critical non-textual elements such as the connectivity and topology of the
graph.

Retrieve on Graphs. To address the challenge of losing topological information
during text retrieval, Yasunaga et al. retrieve relevant nodes and create a
joint graph that includes the QA context and the relevant nodes. Kang et al.
and Kim et al. focus on retrieving triples rather than individual nodes and
edges to capture more complex relational data. Particularly, some retrieval
problems can be solved by reasoning chains, which can be simplified to
retrieve the path between the question and the target entity (Lo and Lim,
2023; Choudhary and Reddy, 2023). He et al. reconstruct the retrieved nodes
and edges into a new graph and subsequently generate answers with the graph
token and text tokens. However, none of these individual entity-based
retrieval approaches could consider the topological information in the
retrieval process. As shown in Figure 1, considering only text relevance
without accounting for the graph topology during the retrieval process can
result in retrieved entities that fail to enhance the generation of LLMs.
Therefore, there is an emerging need to retrieve relevant subgraphs rather
than individual entities. A few works propose new retrieval strategies for
graph-related scenarios. For instance, Edge et al. leverage community
detection algorithms to partition the graph into communities, then retrieve
and aggregate relevant communities to generate the final answer to the query.
Unlike our GRAG approach, none of these models directly retrieve at the graph
level and prune irrelevant components to find the precise subgraph structure.

##  3 Problem Formalization

Textual Graphs are graphs consisting of text-attributed nodes and edges, which
can be formally defined as $G(V,E,\\{T_{n}\\}_{n\in V},\\{T_{e}\\}_{e\in E})$.
$V$ and $E$ represent the node set and edge set. $T_{n}$ and $T_{e}$ represent
the natural language attributes of the corresponding nodes and edges in the
graph.

Textual Subgraphs are subgraph structures in a textual graph, e.g., $G$ with
finite node set $V$ and edge set $E$, we have its subgraph set
$\mathcal{S}(G)=\\{g=(V^{\prime},E^{\prime},\\{T_{n}\\}_{n\in
V^{\prime}},\\{T_{e}\\}_{e\in
E^{\prime}})|V^{\prime}\in\mathcal{P}(V),E^{\prime}\in\mathcal{P}(E)\\}$,
where $\mathcal{P}(V)$ and $\mathcal{P}(E)$ represent the power set of $V$ and
$E$, respectively.

Graph Retrieval Augmented Generation (GRAG) aims to enhance the
trustworthiness and explainability of LLMs’ generation in GraphQA. Given a
specific question $q$ over $G$, there must exist an optimal subgraph
structure, i.e., $g\subseteq\mathcal{S}(G)$, leads the LLM to generate answers
that meet expectations. The goal of GRAG is to find the subgraph $g$ and
integrate their information as tokens into LLM to enhance the generation.
Formally, the probability distribution of the final output sequence is as:

$\displaystyle
p_{\theta}(Y|[X_{q};X_{g}])=\prod\nolimits_{i=1}\nolimits^{n}p_{\theta}(y_{i}|y_{<i},[X_{q};X_{g}])$
(1)

where $y_{<i}$ represents the prefix tokens, $X_{q}$ and $X_{g}$ indicate the
token sequence of the question and integrated graph information. $[~{};~{}]$
represents the concatenation operator following a specified order.

In this paper, we investigate the following challenges of GRAG.

Challenge 1. Efficiency of retrieving relevant subgraph structures in large-
scale textual graph scenarios. This problem is particularly difficult due to:
(1) the high dimensionality of textual data within nodes and edges, which
increases the complexity of the retrieval process; (2) the exponential growth
of potential subgraphs with the size of the graph, necessitating efficient
approximation methods; (3) and the need to ensure semantic relevance between
the query and graph structures, which requires sophisticated algorithms to
interpret and align both textual and structural information. These factors
make exhaustive search methods impractical for large-scale textual graphs,
highlighting the necessity for advanced techniques to manage the retrieval and
generation processes effectively.

Challenge 2. Joint preservation of text and topological information in the
retrieved textual subgraphs. Another critical challenge is the need to jointly
preserve and leverage both textual and topological information in the
retrieval and generation process. RAG methods primarily focus on text
embeddings, often neglecting the structural aspects of graphs, which are
crucial for accurate reasoning and context understanding in textual graph-
related scenarios. Additionally, textual graphs often contain a vast amount of
information, making it challenging to filter out irrelevant data while
retaining useful graph context. Efficiently pruning irrelevant nodes and edges
without losing critical information is essential for effective graph retrieval
and generation.

Figure 2: Illustration of our GRAG approach. Given a query and a related
textual graph: (a) all $k$-hop ego-graphs (e.g., 1-hop here) are embedded into
graph embeddings and compared with the query vector to retrieve the topN
similar subgraphs. Irrelevant entities in the graph are partially masked using
a soft pruning module. (b) For the final generation, pruned ego-graphs are
encoded into a soft graph token, and textual information is encoded into text
tokens. (c) Soft pruning module. (d) Generating text descriptions of ego-
graphs preserving both textual and topological information.

##  4 Methodology

#### Overview.

In this section, we introduce our GRAG approach for graph retrieval-augmented
generation. As illustrated in Figure 2, GRAG comprises four main stages:
indexing, graph retrieval, soft pruning, and generation. To address the
challenge in textual subgraph retrieval, as shown in Figure 2(a), we search
for the relevant subgraph structure by retrieving all $k$-hop ego-graphs and
then learn and perform a soft pruning operation to reduce the impact of
redundant entities and obtain an approximately optimal subgraph structure.
Compared with entity retrieval on graphs (i.e., searching all entities in the
graph whose total number is $|V|+|E|$), the retrieval efficiency of GRAG is
guaranteed since only $|V|$ $k$-hop ego-graphs need to be retrieved. To
address the challenge of preserving both textual and topological information,
as shown in Figure 2(b) & 2(d), we pursue two complementary views of textual
graphs: 1) graph of text, using graph embedding as a soft prompt to preserve
graph topology, and 2) text of graph, using structured textual documents as
hard prompts to retain semantic nuances. Both methods are designed to preserve
the textual and structural integrity of the graph, leveraging their
complementary strengths: graph embedding excels in maintaining graph topology,
while textual documents capture semantic nuances.

###  4.1 Textual Subgraph Retrieval

To search for the textual subgraph from the whole graph efficiently, we
propose a new divide-and-conquer strategy that exploits the trade-off between
the number of candidates and computational intensity. More concretely, we
first encode the neighborhood surrounding each node in an offline manner.
During textual subgraph retrieval, we can quickly index a pool of promising
candidates (textual subgraph indexing), from which we further rank and retain
the top-ranked ones (textual subgraph ranking). This process is followed by a
learnable pruner that carves the selected neighborhoods into subgraphs that
are relevant to the query and most beneficial to the task (textual subgraph
pruning).

Textual Subgraph Indexing. We index $k$-hop ego-graphs in $G$ and convert them
to graph embeddings. All embeddings are stored for further retrieval process.
Since graph embeddings will calculate similarity with the question embedding
in the retrieval stage from the perspective of semantic meaning, graph
embeddings need to be semantically meaningful. Therefore, we leverage a pre-
trained language model (PLM)111In this work, SentenceBert (Reimers and
Gurevych, 2019) is used to encode the question and text attributes. to convert
text attributes of nodes and edges to embeddings. Then, we perform a mean
pooling operation on these embeddings to obtain a graph embedding, e.g.,
$z_{g}\in\mathbb{R}^{d}$ for each subgraph $g\in\mathcal{S}(G)$, where $d$
represents the dimension of the graph embedding:

$z_{g}=\text{POOL}(\text{PLM}(\\{T_{n}\\}_{n\in V_{g}},\\{T_{e}\\}_{e\in
E_{g}}))$ (2)

where $V_{g}$ and $E_{g}$ represent the node set and edge set of the subgraph
$g$.

Textual Subgraph Ranking. During the retrieval phase, the same PLM as encoder
is used to obtain the question embeddings:

$z_{q}=\text{PLM}(q)\in\mathbb{R}^{d}$ (3)

where $z_{q}$ has the same dimension as graph embeddings. Then, we calculate
the similarity between the question and each $k$-hop ego-graph then find the
top-$N$ relevant subgraphs as:

$\mathcal{S}(G)_{N}=\text{argtop{N}}_{g\in\mathcal{S}(G)}\text{cos}(z_{q},z_{g})$
(4)

where $\text{cos}(\cdot,~{}\cdot)$ represents the cosine similarity function.
$\mathcal{S}(G)_{N}\subseteq\mathcal{S}(G)$ containing $N$ subgraphs with the
highest similarity to the question is retrieved for subsequent generation.

Textual Subgraph Pruning. We use graph embedding to retrieve subgraphs,
resulting in some redundant irrelevant nodes and edges still in the subgraph,
and these irrelevant entities will not contribute to the final generation.
Therefore, we propose a soft pruning approach to reduce the negative impact of
these irrelevant entities. To be specific, we calculate the distance between
the question and node & edge texts, and then use the distance to scale the
node & edge attributes:

$\displaystyle z_{n}$ $\displaystyle=\text{PLM}(T_{n})\in\mathbb{R}^{d},n\in
V_{g},$ $\displaystyle z_{e}$
$\displaystyle=\text{PLM}(T_{e})\in\mathbb{R}^{d},e\in E_{g}$ (5)
$\displaystyle\alpha_{n}$ $\displaystyle=\text{MLP}_{\phi_{1}}~{}(z_{n}\ominus
z_{q}),$ $\displaystyle\alpha_{e}$
$\displaystyle=\text{MLP}_{\phi_{2}}~{}(z_{e}\ominus z_{q})$ (6)

where $\ominus$ represents the operator to measure the element-wise distance,
i.e., euclidean distance where $z_{n}\ominus
z_{q}=\sqrt{\sum^{d}_{i=1}(z_{n}[i]-z_{q}[i])^{2}}$. $\alpha_{n}$ and
$\alpha_{e}$ are scalars measuring the correlation via a same MLP. In this
way, if information provided by some nodes & edges has a negative impact on
the final generation during the training process, they will be given a small
scaling factor to reduce their impact.

###  4.2 Textual Graph Augmented Generation

The generation by LLMs is controlled by both retrieved ego-graphs and the
question. That is, the prompts to LLMs consist of questions and information
about the retrieved textual subgraphs. Prompts are divided into two parts:
soft prompts, which capture the graph’s topological information through graph
embeddings, and hard prompts, which preserve semantic nuances by representing
the graph’s textual data and the query text.

Hard Prompts. Recent advancements demonstrate that LLMs exhibit strong
reasoning capabilities on graphs (Fatemi et al., 2023). In particular, their
proficiency in contextual reasoning allows LLMs to effectively understand
structured textual documents (Saad-Falcon et al., 2023). During training, LLMs
are often exposed to structured documents with inherent or annotated
hierarchical structures, such as Wikipedia pages. This exposure enables LLMs
to learn the rules and patterns of textual graph representations, facilitating
reasoning on hierarchical data. Therefore, representing retrieved textual
subgraphs in a hierarchical structure can preserve topological information for
LLMs.

Despite the promise of using structured textual document to represent textual
graph information, how to achieve such transformation automatically is an open
problem. Here we propose a novel algorithm to achieve this based on graph and
tree traversals. The gap between $k$-order ego-graph and tree is that there
are additional edges between nodes in addition to the edges between levels. To
overcome this challenge, we design a prompt template that describes the text
graph as a tree-like structure while retaining textual and topological
information. As shown in Figure 2(d), we split each retrieved $k$-order ego-
graph into two parts, denoted by $g=\mathcal{T}_{g}\cup\mathcal{E}_{g}$ where
$\mathcal{T}_{g}$ indicates a partially ordered set that forms a tree rooted
at the ego node and $\mathcal{E}_{g}$ is an edge set consisting of edges not
included in the tree. We leverage Breadth-First Search (BFS) on each ego-graph
to find its $\mathcal{T}_{g}$, and then $\mathcal{E}_{g}$ can be easily
obtained. Afterwards, we perform pre-order traversal on $\mathcal{T}_{g}$ and
append the texts of visited node & edge with a relation description template
such as {head} is connected to {tail} via {relation}. For edges in
$\mathcal{E}_{g}$, we insert textual descriptions of these edges into their
head nodes, following the same relationship description template. The final
description, denoted by $D_{g}$, retains all textual information and
topological information with a hierarchical structure, enabling lossless
conversion between the $k$-hop ego-graphs and text descriptions. Then, we
generate text embeddings of the hard prompt with LLM’s text embedder, which is
the first layer of a pretrained and frozen LLM:

$\displaystyle\mathbf{h}_{q}=\text{TextEmbedder}(q)\in\mathbb{R}^{L_{q}\times
d_{\text{LLM}}}$ (7)
$\displaystyle\mathbf{h}_{T}=\text{TextEmbedder}(\text{Concat}(\\{D_{g}\\}_{g\in
S(G)_{N}}))\in\mathbb{R}^{L_{T}\times d_{\text{LLM}}}$ (8)

where $L_{q}$ and $L_{T}$ represent the number of tokens converted from the
question and graph descriptions.

Soft Prompts. To aggregate topological information of graphs while minimizing
the impact of irrelevant entities on the generation, we propose a novel soft
prompting strategy that controls the message passing of GNNs via learnable
relevance scaling factors. Subsequently, we use an MLP to align the graph
embeddings and LLM tokens. This approach allows for controlled message passing
in GNNs based on the relevance between nodes, edges, and the query as,

$\displaystyle m^{(l)}_{u}=\text{MSG}^{(l)}\left(\alpha_{u}\cdot
h^{(l-1)}_{u},\alpha_{uv}\cdot e_{uv}\right),u\in\\{\mathcal{N}(v)\cup v\\}$
(9)

where $h^{(0)}_{u}=z_{n}$ and $e_{uv}=z_{uv}$, $\mathcal{N}(v)$ represents the
set of neighboring nodes of $v$, $h^{(l-1)}_{u}$ are the node features from
the previous layer, $e_{uv}$ denotes the attributes of the edge connecting
nodes $u$ and $v$, $\alpha_{u}$ and $\alpha_{uv}$ are coefficients by Eq. (6)
applied to the node & edge features. We leverage Graph Attention Network (GAT)
(Veličković et al., 2018) as the graph encoder to aggregate all information in
subgraphs. Since multiple subgraphs are retrieved and there is still a gap
between graph encoder and LLMs’ text encoder, we average the graph embedding
of the retrieved subgraphs then use an MLP to align its dimension and that of
the LLMs’ text vectors to obtain the graph token as,

$\mathbf{h}_{G}=\text{MLP}_{\phi_{3}}\left(\
\frac{1}{N}\sum_{g\in\mathcal{S}(G)_{N}}\text{POOL}(\text{GNN}_{\Phi}(g))\right)\
\in\mathbb{R}^{d_{\text{LLM}}}$ (10)

where $d_{\text{LLM}}$ indicates the dimension of the LLMs’ text vector.
$\mathbf{h}_{G}$ is used as a soft prompt, aggregating information from the
most relevant subgraph structures and allowing the LLM to be aware of
topological textual information during the generation stage. The final stage
involves generating the answer $Y$ using both the graph tokens and text
tokens. The generation of LLM is controlled by graph soft prompts and text
hard prompts as:

$p_{\theta,\phi_{1},\phi_{2},\phi_{3},\Phi}(Y|G,q)=\prod_{i=1}^{r}p_{\theta,\phi_{1},\phi_{2},\phi_{3},\Phi}(y_{i}|y_{<i},[\mathbf{h}_{G};\mathbf{h}_{T};\mathbf{h}_{q}]),$
(11)

where LLM’s parameters $\theta$ are frozen.
$[\mathbf{h}_{G};\mathbf{h}_{T};\mathbf{h}_{q}]$ concatenates the graph token
and all text tokens.

##  5 Experiments

###  5.1 Experiment Setup

Table 1: Dataset statistics (average). Dataset | WebQSP | ExplaGraphs
---|---|---
# Graphs | 4,700 | 2,766
# Nodes | 1370.89 | 5.17
# Edges | 4252.37 | 4.25
# Tokens | 100,627 | 1,396

Tasks and Datasets. We conduct experiments on the GraphQA benchmark (He et
al., 2024), where each question is asked to explore specific elements or
relationships in a textual graph. Table 1 records the statistics of the
dataset. WebQSP (Yih et al., 2016; Luo et al., 2023) is a large-scale multi-
hop knowledge graph QA dataset consisting of 4,737 questions. ExplaGraphs
(Saha et al., 2021) is a dataset about commonsense reasoning consisting of
2,766 questions focused on predicting positions in debates. Multi-hop
reasoning is required to answer these questions accurately.

Evaluation Metrics. For the large-scale dataset WebQSP, we utilize the $F_{1}$
Score, Hit@1, and Recall metrics to comprehensively evaluate performance of
models. For ExplaGraphs which focuses on common-sense reasoning, we employ
Accuracy (Acc) as the primary metric.

Comparison Methods. To demonstrate the effectiveness of GRAG, we compare its
performance to widely used retrievers on graph multi-hop reasoning tasks. We
compare GRAG with the following models: BM25 (Robertson et al., 2009), which
is a statistical model, scores documents based on term frequency, inverse
document frequency, and document length, using probabilistic principles to
estimate the relevance of documents to a query; MiniLM-L12-v2, which is a
SentenceTransformer model (Reimers and Gurevych, 2019) widely used in
clustering and semantic search; LaBSE (Feng et al., 2022), a BERT-based model
that performs retrieval by using a dual-encoder framework to learn cross-
lingual sentence embeddings; mContriever (Izacard et al., 2021), which
utilizes a contrastive learning approach with a bi-encoder architecture to
independently encode documents and queries; E5 (Wang et al., 2022), that
employs a contrastive pre-training strategy using a bi-encoder architecture,
optimizing similarity between relevant pairs while distinguishing from
irrelevant ones using in-batch negatives; G-Retriever (He et al., 2024), which
retrieves relevant nodes and edges, and then constructs a relevant subgraph
using a Prize-Collecting Steiner Tree method. Additionally, we establish two
LLM baselines: (1) directly utilizing the LLM to answer questions, and (2)
fine-tuning the LLM using LoRA (Hu et al., 2021) for question answering, where
questions and textual graphs without any retrieval operations are used in both
settings. The default LLM in experiments is Llama2-7b model (Touvron et al.,
2023). Detailed experimental settings are provided in Appendix A.1.

###  5.2 Main Results

Table 2 reports the overall results across datasets (i.e., WebQSP and
ExplaGraphs) and compare the performance of GRAG with all the retrievers and
baselines introduced in Section 5.1. More details can be found in Appendix
A.2.

Key Observations. Our GRAG approach surpasses all compared retrievers and LLM
baselines. Notably, GRAG significantly outperforms the fine-tuned LLM in all
metrics across both datasets by generating soft tokens of retrieved textual
subgraphs without fine-tuning the LLM. Fine-tuning offers only marginal
performance gains when GRAG is employed, as evidenced by the limited
improvement on the WebQSP dataset, with the Hit@1 metric increasing from
0.7236 to 0.7275. This suggests that GRAG is a more effective strategy for
enhancing the graph reasoning capabilities of LLMs than mere fine-tuning. This
can further reduce the cost of training LLMs for graph-related tasks.

When all textual information from graphs is integrated into the prompt, LLMs
exhibit suboptimal performance, even on the ExplaGraphs dataset, which
features smaller graph sizes. This underscores the critical need to implement
retrieval operations to mitigate the negative impact of redundant information
in graphs. Notably, fine-tuning yields significant improvements in the
performance of the LLM when reasoning on small graphs, with a notable increase
from 33.94% to 89.27% accuracy on ExplaGraphs. However, the benefits of fine-
tuning diminish with larger graph sizes, with Hit@1 on WebQSP only increasing
from 0.4148 to 0.6186.

GRAG demonstrates the potential to transfer learned textual graph encoding
capabilities across datasets. Table 5.3 reports the performance of GRAG on
cross-dataset evaluations. When trained on a large dataset, GRAG can enhance
generation on a smaller dataset using the trained model. Notably, performance
on ExplaGraphs surpasses that of the naive LLM when the model is trained on
WebQSP, with an accuracy improvement of 33.77%.

Table 2: Performance comparison across WebQSP and ExplaGraphs datasets. Bold numbers indicate the best performance among all models. Highlight numbers demonstrate the performance improvement achieved by our GRAG approach compared to the LLM baselines. Model | $\mathbf{\Phi(g)}$ | Fine-tuning | WebQSP | ExplaGraphs
---|---|---|---|---
$F_{1}$ Score | Hit@1 | Recall | Acc
Baselines
LLM only | ✗ | ✗ | 0.2555 | 0.4148 | 0.2920 | 0.3394
$\text{LLM}_{LoRA}$ | ✗ | ✓ | 0.4295 | 0.6186 | 0.4193 | 0.8927
Compared Retrievers
BM25 | ✗ | ✗ | 0.2999 | 0.4287 | 0.2879 | 0.6011
MiniLM-L12-v2 | ✗ | ✗ | 0.3485 | 0.4730 | 0.3289 | 0.6011
LaBSE | ✗ | ✗ | 0.3280 | 0.4496 | 0.3126 | 0.6011
mContriever-Base | ✗ | ✗ | 0.3172 | 0.4453 | 0.3047 | 0.5866
E5-Base | ✗ | ✗ | 0.3421 | 0.4705 | 0.3254 | 0.6011
G-Retriever | ✓ | ✗ | 0.4674 | 0.6808 | 0.4579 | 0.8825
$\text{G-Retriever}_{LoRA}$ | ✓ | ✓ | 0.5023 | 0.7016 | 0.5002 | 0.9042
Our Retrieval Approach
GRAG | ✓ | ✗ | 0.5022 | 0.7236 | 0.5099 | 0.9223
$\Delta_{LLM}$ |  |  |  $\uparrow$ 96.56% |  $\uparrow$ 74.45% |  $\uparrow$ 74.62% |  $\uparrow$ 171.74%
$\text{GRAG}_{LoRA}$ | ✓ | ✓ | 0.5041 | 0.7275 | 0.5112 | 0.9274
$\Delta_{LoRA}$ |  |  |  $\uparrow$ 17.37% |  $\uparrow$ 17.60% |  $\uparrow$ 21.92% |  $\uparrow$ 3.89%

Larger LLMs may underperform relative to their smaller counterparts in graph-
related tasks, suggesting that merely increasing the number of parameters does
not inherently enhance LLMs’ graph reasoning capabilities. Without leveraging
retrieval approaches, using larger LLMs does not yield better performance in
graph reasoning tasks. This is illustrated by the performance of
llama2-7b-chat-hf and llama2-13b-chat-hf on both datasets. The former achieves
an accuracy of 33.94% on the commonsense reasoning task in the ExplaGraphs
dataset, whereas the latter records a slightly lower accuracy of 33.57%. A
similar pattern is observed on the WebQSP dataset, where the 13B model’s Hit@1
score of 0.4112 falls below the 0.4148 achieved by the smaller 7B model.

Figure 3: Performance on WebQSP.

Efficiency and Accuracy Trade-off. The retrieval efficiency of our method is
ensured because only $|V|$ ego-graphs need to be retrieved. However,
retrieving more $k$-hop ego-graphs with larger sizes requires encoding
additional information during the generation process, leading to longer
training and inference times. Figure 3 shows the performance of GRAG on WebQSP
as the number of $1$-hop and $2$-hop ego-graphs changes. With the same number
of ego-graphs, using $2$-hop ego-graphs consistently outperform using $1$-hop
ego-graphs. However, increasing the number of retrieved subgraphs does not
necessarily improve performance due to the introduction of redundant
information. A drop in the generation quality can be observed when the number
of ego graphs increases from 15 to 20 on WebQSP. Moreover, using a larger
number of subgraphs results in more robust generation, as indicated by a
smaller standard deviation. For scenarios where optimal generation results are
not required, more low-hop ego-graphs can be used to achieve similar effects
to higher-hop ones. Using ten $1$-hop subgraphs achieves the same generation
quality as using fifteen $2$-hop subgraphs on WebQSP, while reducing training
time by three times.

Human Evaluation on Hallucinations. We conduct small human evaluations on GRAG
outputs to evaluate hallucinations. In particular, we randomly select and
manually review 100 samples from WebQSP and ExplaGraphs results. Following
Menick et al. and He et al., human annotators evaluate whether the model
output is reasonable and supported, i.e., in graph-related scenarios,
verifying whether nodes and edges referenced in the output exist in the actual
graph. To be specific, we count the valid entities, i.e., the fraction of
total valid nodes & edges. The output of GRAG references 79% of the valid
entities in the graph compared to MiniLM-L12-v2 and G-Retriever, where the
output of MiniLM-L12-v2 and G-Retriever reference 62% and 71% of the valid
entities.

Thorough Comparisons with Different Retrievers and Baselines. Overall, the LLM
can generate better responses with retrieved entities by all tested
retrievers. However, even if advanced retrievers use more data for training
and increase the embedding dimension to obtain better embeddings, their focus
remains exclusively on the text domain, creating a performance bottleneck as
no topological information is retrieved. As shown in Table 2, when graph
tokens are not considered, there is only a slight difference in the
enhancement generated by various retrievers. This phenomenon is further
discussed in Appendix A.2. G-Retriever, which aggregates topological
information as soft prompts, outperforms other retrievers, but it also fails
to consider topology during the retrieval process. Our GRAG approach addresses
this limitation by directly retrieving subgraphs instead of discrete entities
within graphs, thereby achieving optimal performance on both datasets.

###  5.3 Ablation Study

We conducted a series of ablations to our GRAG framework to identify which
components play a key role. We evaluate four model variants trained
differently, where fine-tuning is used and 2-hop ego-graphs are retrieved in
all settings: No Retrieval trains the LLM with question-answer pairs with
fine-tuning; No Graph Encoder trains the LLM using the text on the retrieved
textual subgraphs, but does not generate graph tokens; No Soft Pruning
indicates that irrelevant entities are not pruned when retrieved subgraphs are
encoded to the graph tokens; No Graph Description trains the LLM without the
hierarchical text descriptions of retrieved textual subgraphs. As shown in
Table 5.3, GRAG’s performance drops when any of these components are removed.
Our main findings are as follows:

Setting | Hit@1 | $\Delta_{GRAG}$
---|---|---
w/o Retrieval | 0.6093 |  $\downarrow$ 16.25%
w/o Graph Encoder | 0.5835 |  $\downarrow$ 19.79%
w/o Soft Pruning | 0.5671 |  $\downarrow$ 22.05%
w/o Graph Descriptions | 0.4496 |  $\downarrow$ 38.20%
Table 3: Ablation study on WebQSP.  Dataset | Acc | $\Delta_{LLM}$
---|---|---
WebQSP $\rightarrow$ ExplaGraphs | 0.4540 |  $\uparrow$ 33.77%
ExplaGraphs $\rightarrow$WebQSP | 0.4237 |  $\uparrow$ 2.15%
Table 4: Transfer learning performance.

Importance of Soft Prompting. When no graph token is concentrated to the
prompt, LLM’s generation quality is not improved (even worse than the No
Retrieval variant) even texts on the retrieved subgraph are used. This
suggests that the soft pruning also affects the hard prompts.

Impact of Pruning. When irrelevant entities in retrieved textual subgraphs are
not pruned (No Soft Pruning), the performance on WebQSP is worse compared to
the No Retrieval and No Graph Encoder variant. This suggests that pruning is
crucial, especially in dense graphs, to improve the quality of graph tokens
and avoid negative impacts from irrelevant entities.

Importance of Text Attributes. When text attributes of retrieved textual
subgraphs are not used, the graph token does not benefit the generation
process. The performance of this variant is worse than the No Retrieval
variant, with a Hit@1 score dropping to 0.4496, a 38.2% decrease. This
indicates that the textual attributes of nodes and edges are essential for
generation. Although GNNs aggregate attributes, the inclusion of text
attributes is still important for the generation of the LLM.

##  6 Conclusion

In this paper, we introduced Graph Retrieval-Augmented Generation (GRAG), a
novel approach addressing the limitations of traditional Retrieval-Augmented
Generation (RAG) methods in graph-based contexts. GRAG enhances the generation
capabilities of Large Language Models (LLMs) by retrieving query-relevant
textual subgraphs, preserving both textual and topological information
essential for accurate reasoning. Our framework employs a divide-and-conquer
strategy for efficient subgraph retrieval, using $k$-hop ego-graphs and a soft
pruning mechanism to mitigate irrelevant entities, and introduces dual
prompting with hard and soft prompts to maintain semantic nuances and graph
topology. Empirical results on multi-hop graph reasoning tasks demonstrate
that GRAG significantly outperforms state-of-the-art RAG methods and LLM
baselines, particularly in scenarios requiring detailed, multi-hop reasoning
on textual graphs. This approach not only addresses the NP-hard problem of
exhaustive subgraph searches but also shows that a frozen LLM with GRAG can
outperform fine-tuned LLMs with lower training costs, representing a
significant advancement in integrating graph-based information retrieval and
generation.

## References

  * Hu et al. [2023a] Yuntong Hu, Zheng Zhang, and Liang Zhao.  Beyond text: A deep dive into large language models’ ability on understanding graph data.  In _NeurIPS 2023 Workshop: New Frontiers in Graph Learning_ , 2023a.
  * Chen et al. [2024] Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al.  Exploring the potential of large language models (llms) in learning on graphs.  _ACM SIGKDD Explorations Newsletter_ , 25(2):42–61, 2024.
  * Fatemi et al. [2023] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi.  Talk like a graph: Encoding graphs for large language models.  In _The Twelfth International Conference on Learning Representations_ , 2023.
  * Mallen et al. [2023] Alex Troy Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Hajishirzi.  When not to trust language models: Investigating effectiveness of parametric and non-parametric memories.  In _The 61st Annual Meeting Of The Association For Computational Linguistics_ , 2023.
  * Min et al. [2023] Sewon Min, Kalpesh Krishna, Xinxi Lyu, Mike Lewis, Wen-tau Yih, Pang Koh, Mohit Iyyer, Luke Zettlemoyer, and Hannaneh Hajishirzi.  Factscore: Fine-grained atomic evaluation of factual precision in long form text generation.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 12076–12100, 2023.
  * Lewis et al. [2020] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _Advances in Neural Information Processing Systems_ , 33:9459–9474, 2020.
  * Guu et al. [2020] Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wei Chang.  Realm: retrieval-augmented language model pre-training.  In _Proceedings of the 37th International Conference on Machine Learning_ , pages 3929–3938, 2020.
  * Tang and Yang [2024] Yixuan Tang and Yi Yang.  Multihop-rag: Benchmarking retrieval-augmented generation for multi-hop queries.  _arXiv preprint arXiv:2401.15391_ , 2024.
  * He et al. [2023] Xiaoxin He, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi.  Harnessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning.  In _The Twelfth International Conference on Learning Representations_ , 2023.
  * Jin et al. [2023] Bowen Jin, Gang Liu, Chi Han, Meng Jiang, Heng Ji, and Jiawei Han.  Large language models on graphs: A comprehensive survey.  _arXiv preprint arXiv:2312.02783_ , 2023.
  * Li et al. [2023] Yuhan Li, Zhixun Li, Peisong Wang, Jia Li, Xiangguo Sun, Hong Cheng, and Jeffrey Xu Yu.  A survey of graph meets large language model: Progress and future directions.  _arXiv preprint arXiv:2311.12399_ , 2023.
  * Yang et al. [2024] Sohee Yang, Elena Gribovskaya, Nora Kassner, Mor Geva, and Sebastian Riedel.  Do large language models latently perform multi-hop reasoning?  _arXiv preprint arXiv:2402.16837_ , 2024.
  * Johnson and Garey [1979] David S Johnson and Michael R Garey.  _Computers and intractability: A guide to the theory of NP-completeness_.  WH Freeman, 1979.
  * Chen et al. [2023] Zhikai Chen, Haitao Mao, Hongzhi Wen, Haoyu Han, Wei Jin, Haiyang Zhang, Hui Liu, and Jiliang Tang.  Label-free node classification on graphs with large language models (llms).  In _The Twelfth International Conference on Learning Representations_ , 2023.
  * Trajanoska et al. [2023] Milena Trajanoska, Riste Stojanov, and Dimitar Trajanov.  Enhancing knowledge graph construction using large language models.  _arXiv preprint arXiv:2305.04676_ , 2023.
  * Yao et al. [2023] Liang Yao, Jiazhen Peng, Chengsheng Mao, and Yuan Luo.  Exploring large language models for knowledge graph completion.  _arXiv preprint arXiv:2308.13916_ , 2023.
  * Wang et al. [2024] Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov.  Can language models solve graph problems in natural language?  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Jiang et al. [2023] Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji-Rong Wen.  Structgpt: A general framework for large language model to reason over structured data.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 9237–9251, 2023.
  * Luo et al. [2023] LinHao Luo, Yuan-Fang Li, Reza Haf, and Shirui Pan.  Reasoning on graphs: Faithful and interpretable large language model reasoning.  In _The Twelfth International Conference on Learning Representations_ , 2023.
  * Baek et al. [2023] Jinheon Baek, Alham Aji, and Amir Saffari.  Knowledge-augmented language model prompting for zero-shot knowledge graph question answering.  In _The 61st Annual Meeting Of The Association For Computational Linguistics_ , 2023.
  * Hu et al. [2023b] Nan Hu, Yike Wu, Guilin Qi, Dehai Min, Jiaoyan Chen, Jeff Z Pan, and Zafar Ali.  An empirical study of pre-trained language models in simple knowledge graph question answering.  _World Wide Web_ , 26(5):2855–2886, 2023b.
  * Tian et al. [2024] Yijun Tian, Huan Song, Zichen Wang, Haozhu Wang, Ziqing Hu, Fang Wang, Nitesh V Chawla, and Panpan Xu.  Graph neural prompting with large language models.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 38, pages 19080–19088, 2024.
  * He et al. [2024] Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh V Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi.  G-retriever: Retrieval-augmented generation for textual graph understanding and question answering.  _arXiv preprint arXiv:2402.07630_ , 2024.
  * Ram et al. [2023] Ori Ram, Yoav Levine, Itay Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin Leyton-Brown, and Yoav Shoham.  In-context retrieval-augmented language models.  _Transactions of the Association for Computational Linguistics_ , 11:1316–1331, 2023.
  * Gao et al. [2023] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang.  Retrieval-augmented generation for large language models: A survey.  _arXiv preprint arXiv:2312.10997_ , 2023.
  * Yasunaga et al. [2021] Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec.  Qa-gnn: Reasoning with language models and knowledge graphs for question answering.  In _North American Chapter of the Association for Computational Linguistics (NAACL)_ , 2021.
  * Kang et al. [2023] Minki Kang, Jin Myung Kwak, Jinheon Baek, and Sung Ju Hwang.  Knowledge graph-augmented language models for knowledge-grounded dialogue generation.  _arXiv preprint arXiv:2305.18846_ , 2023.
  * Kim et al. [2023] Jiho Kim, Sungjin Park, Yeonsu Kwon, Yohan Jo, James Thorne, and Yoonjae Choi.  Factkg: Fact verification via reasoning on knowledge graphs.  In _61st Annual Meeting of the Association for Computational Linguistics, ACL 2023_ , pages 16190–16206. Association for Computational Linguistics (ACL), 2023.
  * Lo and Lim [2023] Pei-Chi Lo and Ee-Peng Lim.  Contextual path retrieval: A contextual entity relation embedding-based approach.  _ACM Transactions on Information Systems_ , 41(1):1–38, 2023.
  * Choudhary and Reddy [2023] Nurendra Choudhary and Chandan K Reddy.  Complex logical reasoning over knowledge graphs using large language models.  _arXiv preprint arXiv:2305.01157_ , 2023.
  * Edge et al. [2024] Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, and Jonathan Larson.  From local to global: A graph rag approach to query-focused summarization.  _arXiv preprint arXiv:2404.16130_ , 2024.
  * Reimers and Gurevych [2019] Nils Reimers and Iryna Gurevych.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3982–3992, 2019.
  * Saad-Falcon et al. [2023] Jon Saad-Falcon, Joe Barrow, Alexa Siu, Ani Nenkova, Ryan A Rossi, and Franck Dernoncourt.  Pdftriage: Question answering over long, structured documents.  _arXiv preprint arXiv:2309.08872_ , 2023.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In _International Conference on Learning Representations_ , 2018.
  * Yih et al. [2016] Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Wei Chang, and Jina Suh.  The value of semantic parse labeling for knowledge base question answering.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 201–206, 2016.
  * Saha et al. [2021] Swarnadeep Saha, Prateek Yadav, Lisa Bauer, and Mohit Bansal.  Explagraphs: An explanation graph generation task for structured commonsense reasoning.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 7716–7740, 2021.
  * Robertson et al. [2009] Stephen Robertson, Hugo Zaragoza, et al.  The probabilistic relevance framework: Bm25 and beyond.  _Foundations and Trends® in Information Retrieval_ , 3(4):333–389, 2009.
  * Feng et al. [2022] Fangxiaoyu Feng, Yinfei Yang, Daniel Cer, Naveen Arivazhagan, and Wei Wang.  Language-agnostic bert sentence embedding.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 878–891, 2022.
  * Izacard et al. [2021] Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave.  Unsupervised dense information retrieval with contrastive learning.  _arXiv preprint arXiv:2112.09118_ , 2021.
  * Wang et al. [2022] Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei.  Text embeddings by weakly-supervised contrastive pre-training.  _arXiv preprint arXiv:2212.03533_ , 2022.
  * Hu et al. [2021] Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al.  Lora: Low-rank adaptation of large language models.  In _International Conference on Learning Representations_ , 2021.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Menick et al. [2022] Jacob Menick, Maja Trebacz, Vladimir Mikulik, John Aslanides, Francis Song, Martin Chadwick, Mia Glaese, Susannah Young, Lucy Campbell-Gillingham, Geoffrey Irving, et al.  Teaching language models to support answers with verified quotes.  _arXiv preprint arXiv:2203.11147_ , 2022.
  * Loshchilov and Hutter [2018] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2018.

##  Appendix A Appendix

###  A.1 Implementation

All experiments are performed on a Linux-based server with 4 NVIDIA A10G GPUs.
We use SentenceBert [Reimers and Gurevych, 2019] to encode the question and
text attributes to obtain vectors for the retrieval process. The graph
encoder, i.e. GAT [Veličković et al., 2018], has 4 layers with 4 heads per
layer and a hidden dimension size of 1024.

The LLM backbone is Llama-2-7b-hf, while the model used is in the setting of
LLM only is Llama-2-7b-chat-hf. We employ Low-rank Adaptation (LoRA) [Hu et
al., 2021] for fine-tuning, configuring the LoRA parameters as follows: the
dimension of the low-rank matrices is set to 8; the scaling factor is 16; and
the dropout rate is 0.05. For the optimization, AdamW optimizer [Loshchilov
and Hutter, 2018] is used. The initial learning rate is set to 1e-5 and the
weight decay is 0.05. Each experiment runs for up to 10 epochs, and the batch
size is 2. For compared retrievers, each experiment on ExplaGraphs is
replicated three times, utilizing different retrieval settings for each run,
i.e., top-3, top-5 and top-10; Each experiment on WebQSP is replicated five
times, utilizing different retrieval settings for each run, i.e., top-3,
top-5, top-10, top-15 and top-20, where top-k indicates how many relevant
entities are retrieved and used for the generation. In our GRAG approach,
since the graphs in ExplaGraphs are constructed from several triples, each
graph is actually a chain consisting of only a few nodes. Therefore, we feed
the entire graph into the LLM without retrieval.

###  A.2 Experiment

Evaluation Metrics. Hit@1 assesses whether the top retrieved result is
correct. It is particularly useful for understanding the accuracy of the first
retrieval hit in graph-based question answering tasks. $F_{1}$ Score is the
harmonic mean of precision and recall, providing a single metric that balances
both false positives and false negatives. Recall measures the proportion of
relevant entities that are successfully retrieved. High recall indicates that
the retrieval system captures most of the relevant information. Accuracy (Acc)
measures the proportion of correctly answered questions. It is particularly
useful for tasks like ExplaGraphs, where the focus is on commonsense
reasoning.

Table 5: Performance of RAG-based retrievers: Hit@1 on WebQSP and Acc on ExplaGraphs. Model | WebQSP | ExplaGraphs
---|---|---
top-3 | top-5 | top-10 | top-15 | top-20 | top-3 | top-5 | top-10
BM25 | 0.3722 | 0.3821 | 0.4109 | 0.4165 | 0.4287 | 0.5704 | 0.5921 | 0.6011
MiniLM-L12-v2 | 0.4251 | 0.4251 | 0.4539 | 0.4625 | 0.4730 | 0.5848 | 0.5939 | 0.6011
LaBSE | 0.4091 | 0.4171 | 0.4294 | 0.4527 | 0.4496 | 0.6011 | 0.6011 | 0.6011
mContriever-Base | 0.4183 | 0.4158 | 0.4349 | 0.4459 | 0.4453 | 0.5866 | 0.5866 | 0.5866
E5-Base | 0.4404 | 0.4558 | 0.4662 | 0.4650 | 0.4705 | 0.5921 | 0.5939 | 0.6011
Figure 4: Effects of the number of retrieved entities on the WebQSP dataset.

Effects of the Number of Retrieved Entities. Top-$k$ indicates $k$ nodes and
$k$ edges are retrieved. The performance of various RAG retrievers on the
WebQSP and ExplaGraphs datasets, with different numbers of retrieved entities,
is summarized in Table 5. GRAG in Figure 4 indicates that the hard prompts of
the text descriptions are replaced by texts of retrieved entities, while the
soft prompt is the token generated by the retrieved $k$-hop ego-graphs. As
observed, increasing the number of retrieved entities generally improves
performance up to a point. For instance, BM25’s Hit@1 score on WebQSP
increases from 0.3722 with top-3 retrievals to 0.4287 with top-20 retrievals.
Similarly, MiniLM-L12-v2 shows improvement from 0.4251 to 0.4730 over the same
range. However, this trend does not continue indefinitely; for some models,
performance plateaus or even slightly decreases beyond a certain number of
entities. For example, LaBSE’s performance peaks at top-15 and then slightly
drops at top-20 on WebQSP. This indicates that retrieving too many entities
can introduce irrelevant information, which may negatively impact the final
generation. On the ExplaGraphs dataset, the trend is less pronounced due to
the smaller graph sizes, with most models showing minimal performance changes
beyond top-5 retrievals. When the graph size is small, indicating that limited
information is available, all RAG-based retrievers encounter a performance
bottleneck. In contrast, our GRAG approach can leverage topological
information, effectively breaking through this performance limitation.