#  Gnn-Rag: Graph Neural Retrieval for Large Language Model Reasoning

Costas Mavromatis
University of Minnesota
<EMAIL_ADDRESS>
&George Karypis
University of Minnesota
<EMAIL_ADDRESS>

###### Abstract

Knowledge Graphs (KGs) represent human-crafted factual knowledge in the form
of triplets (head, relation, tail), which collectively form a graph. Question
Answering over KGs (KGQA) is the task of answering natural questions grounding
the reasoning to the information provided by the KG. Large Language Models
(LLMs) are the state-of-the-art models for QA tasks due to their remarkable
ability to understand natural language. On the other hand, Graph Neural
Networks (GNNs) have been widely used for KGQA as they can handle the complex
graph information stored in the KG. In this work, we introduce Gnn-Rag, a
novel method for combining language understanding abilities of LLMs with the
reasoning abilities of GNNs in a retrieval-augmented generation (RAG) style.
First, a GNN reasons over a dense KG subgraph to retrieve answer candidates
for a given question. Second, the shortest paths in the KG that connect
question entities and answer candidates are extracted to represent KG
reasoning paths. The extracted paths are verbalized and given as input for LLM
reasoning with RAG. In our Gnn-Rag framework, the GNN acts as a dense subgraph
reasoner to extract useful graph information, while the LLM leverages its
natural language processing ability for ultimate KGQA. Furthermore, we develop
a retrieval augmentation (RA) technique to further boost KGQA performance with
Gnn-Rag. Experimental results show that Gnn-Rag achieves state-of-the-art
performance in two widely used KGQA benchmarks (WebQSP and CWQ), outperforming
or matching GPT-4 performance with a 7B tuned LLM. In addition, Gnn-Rag excels
on multi-hop and multi-entity questions outperforming competing approaches by
8.9–15.5% points at answer F1. We provide the code and KGQA results at
https://github.com/cmavro/GNN-RAG.

##  1 Introduction

Large Language Models (LLMs) (Brown et al., 2020; Bommasani et al., 2021;
Chowdhery et al., 2023) are the state-of-the-art models in many NLP tasks due
to their remarkable ability to understand natural language. LLM’s power stems
from pretraining on large corpora of textual data to obtain general human
knowledge (Kaplan et al., 2020; Hoffmann et al., 2022). However, because
pretraining is costly and time-consuming (Gururangan et al., 2020), LLMs
cannot easily adapt to new or in-domain knowledge and are prone to
hallucinations (Zhang et al., 2023).

Knowledge Graphs (KGs) (Vrandečić and Krötzsch, 2014) are databases that store
information in structured form that can be easily updated. KGs represent
human-crafted factual knowledge in the form of triplets (head, relation,
tail), e.g., <Jamaica $\rightarrow$ language_spoken $\rightarrow$ English>,
which collectively form a graph. In the case of KGs, the stored knowledge is
updated by fact addition or removal. As KGs capture complex interactions
between the stored entities, e.g., multi-hop relations, they are widely used
for knowledge-intensive task, such as Question Answering (QA) (Pan et al.,
2024).

Multi-HopMulti-Entity$40$$60$$80$$41.1$$46.9$$61.3$$61.7$$70.2$$77.2$Answer F1
(%)No RAG+KG-RAG+Gnn-Rag Figure 1: Retrieval effect on multi-hop/entity KGQA.
Our Gnn-Rag outperforms existing KG-RAG methods by 8.9–15.5% points.

Retrieval-augmented generation (RAG) is a framework that alleviates LLM
hallucinations by enriching the input context with up-to-date and accurate
information (Lewis et al., 2020), e.g., obtained from the KG. In the KGQA
task, the goal is to answer natural questions grounding the reasoning to the
information provided by the KG. For instance, the input for RAG becomes
“Knowledge: Jamaica $\rightarrow$ language_spoken $\rightarrow$ English \n
Question: Which language do Jamaican people speak?”, where the LLM has access
to KG information for answering the question.

RAG’s performance highly depends on the KG facts that are retrieved (Wu et
al., 2023). The challenge is that KGs store complex graph information (they
usually consist of millions of facts) and retrieving the right information
requires effective graph processing, while retrieving irrelevant information
may confuse the LLM during its KGQA reasoning (He et al., 2024). Existing
retrieval methods that rely on LLMs to retrieve relevant KG information (LLM-
based retrieval) underperform on multi-hop KGQA as they cannot handle complex
graph information (Baek et al., 2023; Luo et al., 2024) or they need the
internal knowledge of very large LMs, e.g., GPT-4, to compensate for missing
information during KG retrieval (Sun et al., 2024).

In this work, we introduce Gnn-Rag, a novel method for improving RAG for KGQA.
Gnn-Rag relies on Graph Neural Networks (GNNs) (Mavromatis and Karypis, 2022),
which are powerful graph representation learners, to handle the complex graph
information stored in the KG. Although GNNs cannot understand natural language
the same way LLMs do, Gnn-Rag repurposes their graph processing power for
retrieval. First, a GNN reasons over a dense KG subgraph to retrieve answer
candidates for a given question. Second, the shortest paths in the KG that
connect question entities and GNN-based answers are extracted to represent
useful KG reasoning paths. The extracted paths are verbalized and given as
input for LLM reasoning with RAG. Furthermore, we show that Gnn-Rag can be
augmented with LLM-based retrievers to further boost KGQA performance.
Experimental results show Gnn-Rag’s superiority over competing RAG-based
systems for KGQA by outperforming them by up to 15.5% points at complex KGQA
performance (Figure 1). Our contributions are summarized below:

  * •

Framework: Gnn-Rag repurposes GNNs for KGQA retrieval to enhance the reasoning
abilities of LLMs. In our Gnn-Rag framework, the GNN acts as a dense subgraph
reasoner to extract useful graph information, while the LLM leverages its
natural language processing ability for ultimate KGQA. Moreover, our retrieval
analysis (Section 4.3) guides the design of a retrieval augmentation (RA)
technique to boost Gnn-Rag’s performance (Section 4.4).

  * •

Effectiveness & Faithfulness: Gnn-Rag achieves state-of-the-art performance in
two widely used KGQA benchmarks (WebQSP and CWQ). Gnn-Rag retrieves multi-hop
information that is necessary for faithful LLM reasoning on complex questions
(8.9–15.5% improvement; see Figure 1).

  * •

Efficiency: Gnn-Rag improves vanilla LLMs on KGQA performance without
incurring additional LLM calls as existing RAG systems for KGQA require. In
addition, Gnn-Rag outperforms or matches GPT-4 performance with a 7B tuned
LLM.

##  2 Related Work

KGQA Methods. KGQA methods fall into two categories (Lan et al., 2022): (A)
Semantic Parsing (SP) methods and (B) Information Retrieval (IR) methods. SP
methods (Sun et al., 2020; Lan and Jiang, 2020; Ye et al., 2022) learn to
transform the given question into a query of logical form, e.g., SPARQL query.
The transformed query is then executed over the KG to obtain the answers.
However, SP methods require ground-truth logical queries for training, which
are time-consuming to annotate in practice, and may lead non-executable
queries due to syntactical or semantic errors (Das et al., 2021; Yu et al.,
2022). IR methods (Sun et al., 2018, 2019) focus on the weakly-supervised KGQA
setting, where only question-answer pairs are given for training. IR methods
retrieve KG information, e.g., a KG subgraph (Zhang et al., 2022a), which is
used as input during KGQA reasoning. In Appendix A, we analyze the reasoning
abilities of the prevailing models (GNNs & LLMs) for KGQA, and in Section 4,
we propose Gnn-Rag which leverages the strengths of both of these models.

Graph-augmented LMs. Combining LMs with graphs that store information in
natural language is an emerging research area (Jin et al., 2023). There are
two main directions, (i) methods that enhance LMs with _latent_ graph
information (Zhang et al., 2022b; Tian et al., 2024; Huang et al., 2024),
e.g., obtained by GNNs, and (ii) methods that insert _verbalized_ graph
information at the input (Xie et al., 2022; Jiang et al., 2023a; Jin et al.,
2024), similar to RAG. The methods of the first direction are limited because
of the modality mismatch between language and graph, which can lead to
inferior performance for knowledge-intensive tasks (Mavromatis et al., 2024).
On the other hand, methods of the second direction may fetch noisy information
when the underlying graph is large and such information can decrease the LM’s
reasoning ability (Wu et al., 2023; He et al., 2024). Gnn-Rag employs GNNs for
information retrieval and RAG for KGQA reasoning, achieving superior
performance over existing approaches.

Figure 2: The landscape of existing KGQA methods. GNN-based methods reason on
dense subgraphs as they can handle complex and multi-hop graph information.
LLM-based methods employ the same LLM for both retrieval and reasoning due to
its ability to understand natural language.

##  3 Problem Statement & Background

KGQA. We are given a KG ${\mathcal{G}}$ that contains facts represented as
$(v,r,v^{\prime})$, where $v$ denotes the head entity, $v^{\prime}$ denotes
the tail entity, and $r$ is the corresponding relation between the two
entities. Given ${\mathcal{G}}$ and a natural language question $q$, the task
of KGQA is to extract a set of entities $\\{a\\}\in{\mathcal{G}}$ that
correctly answer $q$. Following previous works (Lan et al., 2022), question-
answer pairs are given for training, but not the ground-truth paths that lead
to the answers.

Retrieval & Reasoning. As KGs usually contain millions of facts and nodes, a
smaller question-specific subgraph ${\mathcal{G}}_{q}$ is retrieved for a
question $q$, e.g., via entity linking and neighbor extraction (Yih et al.,
2015). Ideally, all correct answers for the question are contained in the
retrieved subgraph, $\\{a\\}\in{\mathcal{G}}_{q}$. The retrieved subgraph
${\mathcal{G}}_{q}$ along with the question $q$ are used as input to a
reasoning model, which outputs the correct answer(s). The prevailing reasoning
models for the KGQA setting studied are GNNs and LLMs.

GNNs. KGQA can be regarded as a node classification problem, where KG entities
are classified as answers vs. non-answers for a given question. GNNs Kipf and
Welling (2016); Veličković et al. (2017); Schlichtkrull et al. (2018) are
powerful graph representation learners suited for tasks such as node
classification. GNNs update the representation ${\bm{h}}_{v}^{(l)}$ of node
$v$ at layer $l$ by aggregating messages ${\bm{m}}^{(l)}_{vv^{\prime}}$ from
each neighbor $v^{\prime}$. During KGQA, the message passing is also
conditioned to the given question $q$ (He et al., 2021). For readability
purposes, we present the following GNN update for KGQA,

${\bm{h}}_{v}^{(l)}=\psi\Big{(}{\bm{h}}_{v}^{(l-1)},\sum_{v^{\prime}\in\mathcal{N}_{v}}\omega(q,r)\cdot{\bm{m}}_{vv^{\prime}}^{(l)}\Big{)},$
(1)

where function $\omega(\cdot)$ measures how relevant relation $r$ of fact
$(v,r,v^{\prime})$ is to question $q$. Neighbor messages
${\bm{m}}_{vv^{\prime}}^{(l)}$ are aggregated by a sum-operator $\sum$, which
is typically employed in GNNs. Function $\psi(\cdot)$ combines representations
from consecutive GNN layers.

LLMs. LLMs for KGQA use KG information to perform retrieval-augmented
generation (RAG) as follows. The retrieved subgraph is first converted into
natural language so that it can be processed by the LLM. The input given to
the LLM contains the KG factual information along with the question and a
prompt. For instance, the input becomes “Knowledge: Jamaica $\rightarrow$
language_spoken $\rightarrow$ English \n Question: Which language do Jamaican
people speak?”, where the LLM has access to KG information for answering the
question.

Landscape of KGQA methods. Figure 2 presents the landscape of existing KGQA
methods with respect to KG retrieval and reasoning. GNN-based methods, such as
GraftNet (Sun et al., 2018), NSM (He et al., 2021), and ReaRev (Mavromatis and
Karypis, 2022), reason over a dense KG subgraph leveraging the GNN’s ability
to handle complex graph information. Recent LLM-based methods leverage the
LLM’s power for both retrieval and reasoning. ToG (Sun et al., 2024) uses the
LLM to retrieve relevant facts hop-by-hop. RoG (Luo et al., 2024) uses the LLM
to generate plausible relation paths which are then mapped on the KG to
retrieve the relevant information.

LLM-based Retriever. We present an example of an LLM-based retriever (RoG;
(Luo et al., 2024)). Given training question-answer pairs, RoG extracts the
shortest paths to the answers starting from question entities for fine-tuning
the retriever. Based on the extracted paths, an LLM (LLaMA2-Chat-7B (Touvron
et al., 2023)) is fine-tuned to generate reasoning paths given a question $q$
as

$\text{LLM}(\text{prompt},q)\Longrightarrow\\{r_{1}\rightarrow\cdots\rightarrow
r_{t}\\}_{k},$ (2)

where the prompt is “Please generate a valid relation path that can be helpful
for answering the following question: {Question}”. Beam-search decoding is
used to generate $k$ diverse sets of reasoning paths for better answer
coverage, e.g., relations {<official_language>, <language_spoken>} for the
question “Which language do Jamaican people speak?”. The generated paths are
mapped on the KG, starting from the question entities, in order to retrieve
the intermediate entities for RAG, e.g., <Jamaica $\rightarrow$
language_spoken $\rightarrow$ English>.

##  4 Gnn-Rag

We introduce Gnn-Rag, a novel method for combining language understanding
abilities of LLMs with the reasoning abilities of GNNs in a retrieval-
augmented generation (RAG) style. We provide the overall framework in Figure
3. First, a GNN reasons over a dense KG subgraph to retrieve answer candidates
for a given question. Second, the shortest paths in the KG that connect
question entities and GNN-based answers are extracted to represent useful KG
reasoning paths. The extracted paths are verbalized and given as input for LLM
reasoning with RAG. In our Gnn-Rag framework, the GNN acts as a dense subgraph
reasoner to extract useful graph information, while the LLM leverages its
natural language processing ability for ultimate KGQA.

Figure 3: Gnn-Rag: The GNN reasons over a dense subgraph to retrieve candidate
answers, along with the corresponding reasoning paths (shortest paths from
question entities to answers). The retrieved reasoning paths –optionally
combined with retrieval augmentation (RA)– are verbalized and given to the LLM
for RAG.

###  4.1 GNN

In order to retrieve high-quality reasoning paths via Gnn-Rag, we leverage
state-of-the-art GNNs for KGQA. We prefer GNNs over other KGQA methods, e.g.,
embedding-based methods (Saxena et al., 2020), due to their ability to handle
complex graph interactions and answer multi-hop questions. GNNs mark
themselves as good candidates for retrieval due to their architectural benefit
of exploring diverse reasoning paths (Mavromatis and Karypis, 2022; Choi et
al., 2024) that result in high answer recall.

When GNN reasoning is completed ($L$ GNN updates via Equation 1), all nodes in
the subgraph are scored as answers vs. non-answers based on their final GNN
representations ${\bm{h}}_{v}^{(L)}$, followed by the
$\mathrm{softmax}(\cdot)$ operation. The GNN parameters are optimized via node
classification (answers vs. non-answers) using the training question-answer
pairs. During inference, the nodes with the highest probability scores, e.g.,
above a probability threshold, are returned as candidate answers, along with
the shortest paths connecting the question entities with the candidate answers
(reasoning paths). The retrieved reasoning paths are used as input for LLM-
based RAG.

Different GNNs may fetch different reasoning paths for RAG. As presented in
Equation 3, GNN reasoning depends on the question-relation matching operation
$\omega(q,r)$. A common implementation of $\omega(q,r)$ is
$\phi({\bm{q}}^{(k)}\odot{\bm{r}})$ (He et al., 2021), where function $\phi$
is a neural network, and $\odot$ is the element-wise multiplication. Question
representations ${\bm{q}}{(k)}$ and KG relation representations ${\bm{r}}$ are
encoded via a shared pretrained LM (Jiang et al., 2023b) as

${\bm{q}}^{(k)}=\gamma_{k}\big{(}\text{LM}(q)\big{)},\;\;{\bm{r}}=\gamma_{c}\big{(}\text{LM}(r)\big{)},$
(3)

where $\gamma_{k}$ are attention-based pooling neural networks so that
different representations ${\bm{q}}^{(k)}$ attend to different question
tokens, and $\gamma_{\text{c}}$ is the [CLS] token pooling.

In Appendix B, we develop a Theorem that shows that the GNN’s output depends
on the question-relation matching operation $\omega(q,r)$ and as result, the
choice of the LM in Equation 3 plays an important role regarding which answer
nodes are retrieved. Instead of trying different GNN architectures, we employ
different LMs in Equation 3 that result into different output node
representations. Specifically, we train two separate GNN models, one using
pretrained LMs, such as SBERT (Reimers and Gurevych, 2019), and one using
$\text{LM}_{\text{SR}}$, a pretrained LM for question-relation matching over
the KG (Zhang et al., 2022a). Our experimental results suggest that, although
these GNNs retrieve different KG information, they both improve RAG-based
KGQA.

###  4.2 LLM

After obtaining the reasoning paths by Gnn-Rag, we verbalize them and give
them as input to a downstream LLM, such as ChatGPT or LLaMA. However, LLMs are
sensitive to the input prompt template and the way that the graph information
is verbalized.

To alleviate this issue, we opt to follow RAG prompt tuning (Lin et al., 2023;
Zhang et al., 2024) for LLMs that have open weights and are feasible to train.
A LLaMA2-Chat-7B model is fine-tuned based on the training question-answer
pairs to generate a list of correct answers, given the prompt:
“Based on the reasoning paths, please answer the given question.\n Reasoning
Paths: {Reasoning Paths} \n Question: {Question}”.
The reasoning paths are verbalised as “{question entity} $\rightarrow$
{relation} $\rightarrow$ {entity} $\rightarrow$ $\cdots$ $\rightarrow$
{relation} $\rightarrow$ {answer entity} \n” (see Figure 3).
During training, the reasoning paths are the shortest paths from question
entities to answer entities. During inference, the reasoning paths are
obtained by Gnn-Rag.

###  4.3 Retrieval Analysis: Why GNNs & Their Limitations

Table 1: Retrieval results for WebQSP.

Retriever | 1-hop questions | 2-hop questions
---|---|---
#Input Tok. | %Ans. Cov. | #Input Tok. | %Ans. Cov.
RoG (Luo et al., 2024) | 150 | 87.1 | 435 | 82.1
GNN ($L=1$) | 112 | 83.6 | 2,582 | 79.8
GNN ($L=3$) | 105 | 82.4 | 357 | 88.5

GNNs leverage the graph structure to retrieve relevant parts of the KG that
contain multi-hop information. We provide experimental evidence on why GNNs
are good retrievers for multi-hop KGQA. We train two different GNNs, a deep
one ($L=3$) and a shallow one ($L=1$), and measure their retrieval
capabilities. We report the ‘Answer Coverage’ metric, which evaluates whether
the retriever is able to fetch at least one correct answer for RAG. Note that
‘Answer Coverage’ does not measure downstream KGQA performance but whether the
retriever fetches relevant KG information. ‘#Input Tokens’ denotes the median
number of the input tokens of the retrieved KG paths. Table 1 shows GNN
retrieval results for single-hop and multi-hop questions of the WebQSP dataset
compared to an LLM-based retriever (RoG; Equation 2). The results indicate
that deep GNNs ($L=3$) can handle the complex graph structure and retrieve
useful _multi-hop_ information more effectively (%Ans. Cov.) and efficiently
(#Input Tok.) than the LLM and the shallow GNN.

On the other hand, the limitation of GNNs is for simple (1-hop) questions,
where accurate question-relation matching is more important than deep graph
search (see our Theorem in Appendix A that states this GNN limitation). In
such cases, the LLM retriever is better at selecting the right KG information
due to its natural language understanding abilities (we provide an example
later in Figure 5).

###  4.4 Retrieval Augmentation (RA)

Retrieval augmentation (RA) combines the retrieved KG information from
different approaches to increase diversity and answer recall. Motivated by the
results in Section 4.3, we present a RA technique (Gnn-Rag+RA), which
complements the GNN retriever with an LLM-based retriever to combine their
strengths on multi-hop and single-hop questions, respectively. Specifically,
we experiment with the RoG retrieval, which is described in Equation 2. During
inference, we take the union of the reasoning paths retrieved by the two
retrievers.

A downside of LLM-based retrieval is that it requires multiple generations
(beam-search decoding) to retrieve diverse paths, which trades efficiency for
effectiveness (we provide a performance analysis in Appendix A). A cheaper
alternative is to perform RA by combining the outputs of different GNNs, which
are equipped with different LMs in Equation 3. Our Gnn-Rag+Ensemble takes the
union of the retrieved paths of the two different GNNs (GNN+SBERT &
GNN+$\text{LM}_{\text{SR}}$) as input for RAG.

##  5 Experimental Setup

KGQA Datasets. We experiment with two widely used KGQA benchmarks:
WebQuestionsSP (WebQSP) (Yih et al., 2015), Complex WebQuestions 1.1 (CWQ)
(Talmor and Berant, 2018). WebQSP contains 4,737 natural language questions
that are answerable using a subset Freebase KG (Bollacker et al., 2008). The
questions require up to 2-hop reasoning within this KG. CWQ contains 34,699
total complex questions that require up to 4-hops of reasoning over the KG. We
provide the detailed dataset statistics in Appendix C.

Implementation & Evaluation. For subgraph retrieval, we use the linked
entities and the pagerank algorithm to extract dense graph information (He et
al., 2021). We employ ReaRev (Mavromatis and Karypis, 2022), which is a GNN
targeting at _deep_ KG reasoning (Section 4.3), for Gnn-Rag. The default
implementation is to combine ReaRev with SBERT as the LM in Equation 3. In
addition, we combine ReaRev with $\text{LM}_{\text{SR}}$, which is obtained by
following the implementation of SR (Zhang et al., 2022a). We employ RoG (Luo
et al., 2024) for RAG-based prompt tuning (Section 4.2). For evaluation, we
adopt Hit, Hits@1 (H@1), and F1 metrics. Hit measures if any of the true
answers is found in the generated response, which is typically employed when
evaluating LLMs. H@1 is the accuracy of the top/first predicted answer. F1
takes into account the recall (number of true answers found) and the precision
(number of false answers found) of the generated answers. Further experimental
setup details are provided in Appendix C.

Table 2: Performance comparison of different methods on the two KGQA
benchmarks. We denote the best and second-best method.

Type | Method | WebQSP | CWQ
---|---|---|---
Hit | H@1 | F1 | Hit | H@1 | F1
Embedding | KV-Mem Miller et al. (2016) | – | 46.7 | 38.6 | – | 21.1 | –
EmbedKGQA Saxena et al. (2020) | – | 66.6 | – | – | – | –
TransferNet Shi et al. (2021) | – | 71.4 | – | – | 48.6 | –
Rigel Sen et al. (2021) | – | 73.3 | – | – | 48.7 | –
GNN | GraftNet Sun et al. (2018) | – | 66.7 | 62.4 | – | 36.8 | 32.7
PullNet Sun et al. (2019) | – | 68.1 | – | – | 45.9 | –
NSM He et al. (2021) | – | 68.7 | 62.8 | – | 47.6 | 42.4
SR+NSM(+E2E) (Zhang et al., 2022a) | – | 69.5 | 64.1 | – | 50.2 | 47.1
NSM+h He et al. (2021) | – | 74.3 | 67.4 | – | 48.8 | 44.0
SQALER Atzeni et al. (2021) | – | 76.1 | – | – | – | –
UniKGQA (Jiang et al., 2023b) | – | 77.2 | 72.2 | – | 51.2 | 49.1
ReaRev (Mavromatis and Karypis, 2022) | – | 76.4 | 70.9 | – | 52.9 | 47.8
| ReaRev + $\text{LM}_{\text{SR}}$ | – | 77.5 | 72.8 | – | 53.3 | 49.7
LLM | Flan-T5-xl (Chung et al., 2024) | 31.0 | – | – | 14.7 | – | –
Alpaca-7B (Taori et al., 2023) | 51.8 | – | – | 27.4 | – | –
LLaMA2-Chat-7B (Touvron et al., 2023) | 64.4 | – | – | 34.6 | – | –
ChatGPT | 66.8 | – | – | 39.9 | – | –
ChatGPT+CoT | 75.6 | – | – | 48.9 | – | –
KG+LLM | KD-CoT (Wang et al., 2023) | 68.6 | – | 52.5 | 55.7 | – | –
StructGPT (Jiang et al., 2023a) | 72.6 | – | – | – | – | –
KB-BINDER (Li et al., 2023) | 74.4 | – | – | – | – | –
ToG+LLaMA2-70B (Sun et al., 2024) | 68.9 | – | – | 57.6 | – | –
ToG+ChatGPT (Sun et al., 2024) | 76.2 | – | – | 58.9 | – | –
ToG+GPT-4 (Sun et al., 2024) | 82.6 | – | – | 69.5 | – | –
RoG (Luo et al., 2024) | 85.7 | 80.0 | 70.8 | 62.6 | 57.8 | 56.2
GNN+LLM | G-Retriever (He et al., 2024) | – | 70.1 | – | – | – | –
Gnn-Rag (Ours) | 85.7 | 80.6 | 71.3 | 66.8 | 61.7 | 59.4
Gnn-Rag+RA (Ours) | 90.7 | 82.8 | 73.5 | 68.7 | 62.8 | 60.4

  * •

Hit is used for LLM evaluation.

  * •

We use the default Gnn-Rag (+RA) implementation. Gnn-Rag, RoG, KD-CoT, and
G-Retriever use 7B fine-tuned LLaMA2 models. KD-CoT employs ChatGPT as well.

Competing Methods. We compare with SOTA GNN and LLM methods for KGQA
(Mavromatis and Karypis, 2022; Li et al., 2023). We also include earlier
embedding-based methods (Saxena et al., 2020) as well as zero-shot/few-shot
LLMs (Taori et al., 2023). We do not compare with semantic parsing methods (Yu
et al., 2022) as they use additional training data (SPARQL annotations), which
are difficult to obtain in practice. Furthermore, we compare Gnn-Rag with LLM-
based retrieval approaches (Luo et al., 2024; Sun et al., 2024) in terms of
efficiency and effectiveness.

##  6 Results

Main Results. Table 2 presents performance results of different KGQA methods.
Gnn-Rag is the method that performs overall the best, achieving state-of-the-
art results on the two KGQA benchmarks in almost all metrics. The results show
that equipping LLMs with GNN-based retrieval boosts their reasoning ability
significantly (GNN+LLM vs. KG+LLM). Specifically, Gnn-Rag+RA outperforms RoG
by 5.0–6.1% points at Hit, while it outperforms or matches ToG+GPT-4
performance, using an LLM with only 7B parameters and much fewer LLM calls –
we estimate ToG+GPT-4 has an overall cost above $800, while Gnn-Rag can be
deployed on a single 24GB GPU. Gnn-Rag+RA outperforms ToG+ChatGPT by up to
14.5% points at Hit and the best performing GNN by 5.3–9.5% points at Hits@1
and by 0.7–10.7% points at F1.

Table 3: Performance analysis (F1) on multi-hop (hops$\geq 2$) and multi-
entity (entities$\geq 2$) questions.

Method | WebQSP | CWQ
---|---|---
multi-hop | multi-entity | multi-hop | multi-entity
LLM (No RAG) | 48.4 | 61.5 | 33.7 | 32.3
RoG | 63.3 | 65.1 | 59.3 | 58.3
Gnn-Rag | 69.8 | 82.3 | 68.2 | 64.8
Gnn-Rag+RA | 71.1 | 88.8 | 69.3 | 65.6

Multi-Hop & Multi-Entity KGQA. Table 3 compares performance results on multi-
hop questions, where answers are more than one hop away from the question
entities, and multi-entity questions, which have more than one question
entities. Gnn-Rag leverages GNNs to handle complex graph information and
outperforms RoG (LLM-based retrieval) by 6.5–17.2% points at F1 on WebQSP and
by 8.5–8.9% points at F1 on CWQ. In addition, Gnn-Rag+RA offers an additional
improvement by up to 6.5% points at F1. The results show that Gnn-Rag is an
effective retrieval method when deep graph search is important for successful
KGQA.

Table 4: Performance comparison (F1 at KGQA) of different retrieval
augmentations (Section 4.4). ‘#LLM Calls’ are controlled by the hyperparameter
$k$ (number of beams) during beam-search decoding for LLM-based retrievers,
‘#Input Tokens’ denotes the median number of tokens.

Retriever | KGQA Model | Input/Graph Statistics | KGQA Performance
---|---|---|---
#LLM Calls | #Input Tokens | F1 (%)
| WebQSP / CWQ | WebQSP / CWQ
a) Dense Subgraph |  (i) GNN + SBERT (Eq. 3) | 0 | – | 70.9 / 47.8
b) Dense Subgraph |  (ii) GNN + $\text{LM}_{\text{SR}}$ (Eq. 3) | 0 | 72.8 / 49.1
c) None | LLaMA2-Chat-7B (tuned) | 0 | 59 / 70 | 49.7 / 33.8
d) (iii) RoG (LLM-based; Eq. 2) | 3 | 202 / 325 | 70.8 / 56.2
e) Gnn-Rag (default): (i) | 0 | 144 / 207 | 71.3 / 59.4
f) Gnn-Rag: (ii) | 0 | 124 / 206 | 71.5 / 58.9
g) Gnn-Rag+Ensemble: (i) \+ (ii) | LLaMA2-Chat-7B (tuned) | 0 | 156 / 281 | 71.7 / 57.5
h) Gnn-Rag+RA (default): (i) \+ (iii) | 3 | 299 / 540 | 73.5 / 60.4
i) Gnn-Rag+RA: (ii) \+ (iii) | 3 | 267 / 532 | 73.4 / 61.0
j) Gnn-Rag+All: (i) \+ (ii) \+ (iii) | 3 | 330 / 668 | 72.3 / 59.1

  * •

For other experiments, we use the default Gnn-Rag and Gnn-Rag+RA
implementations. The GNN used is ReaRev.

Retrieval Augmentation. Table 4 compares different retrieval augmentations for
Gnn-Rag. The primary metric is F1, while the other metrics assess how well the
methods retrieve relevant information from the KG. Based on the results, we
make the following conclusions:

  1. 1.

GNN-based retrieval is more efficient (#LLM Calls, #Input Tokens) and
effective (F1) than LLM-based retrieval, especially for complex questions
(CWQ); see rows (e-f) vs. row (d).

  2. 2.

Retrieval augmentation works the best (F1) when combining GNN-induced
reasoning paths with LLM-induced reasoning paths as they fetch non-overlapping
KG information (increased #Input Tokens) that improves retrieval for KGQA; see
rows (h) & (i).

  3. 3.

Augmenting all retrieval approaches does not necessarily cause improved
performance (F1) as the long input (#Input Tokens) may confuse the LLM; see
rows (g/j) vs. rows (e/h).

  4. 4.

Although the two GNNs perform differently at KGQA (F1), they both improve RAG
with LLMs; see rows (a-b) vs. rows (e-f). We note though that weak GNNs are
not effective retrievers (see Appendix D.2).

Table 5: Retrieval effect on performance (% Hit) using various LLMs.

Method | WebQSP | CWQ
---|---|---
ChatGPT | 51.8 | 39.9
\+ ToG | 76.2 | 58.9
\+ RoG | 81.5 | 52.7
\+ Gnn-Rag (+RA) | 85.3 (87.9) | 64.1 (65.4)
Alpaca-7B | 51.8 | 27.4
\+ RoG | 73.6 | 44.0
\+ Gnn-Rag (+RA) | 76.2 (76.5) |  54.5 (50.8)
LLaMA2-Chat-7B | 64.4 | 34.6
\+ RoG | 84.8 | 56.4
\+ Gnn-Rag (+RA) | 85.2 (88.5) | 62.7 (62.9)
LLaMA2-Chat-70B | 57.4 | 39.1
\+ ToG | 68.9 | 57.6
Flan-T5-xl | 31.0 | 14.7
\+ RoG | 67.9 | 37.8
\+ Gnn-Rag (+RA) |  74.5 (72.3) |  51.0 (41.5)

In addition, Gnn-Rag improves the vanilla LLM by up to 176% at F1 without
incurring additional LLM calls; see row (c) vs. row (e). Overall, retrieval
augmentation of GNN-induced and LLM-induced paths combines their strengths and
achieves the best KGQA performance.

Retrieval Effect on LLMs. Table 5 presents performance results of various LLMs
using Gnn-Rag or LLM-based retrievers (RoG and ToG). We report the Hit metric
as it is difficult to extract the number of answers from LLM’s output. Gnn-Rag
(+RA) is the retrieval approach that achieves the largest improvements for
RAG. For instance, Gnn-Rag+RA improves ChatGPT by up to 6.5% points at Hit
over RoG and ToG. Moreover, Gnn-Rag substantially improves the KGQA
performance of weaker LLMs, such as Alpaca-7B and Flan-T5-xl. The improvement
over RoG is up to 13.2% points at Hit, while Gnn-Rag outperforms
LLaMA2-Chat-70B+ToG using a lightweight 7B LLaMA2 model. The results
demonstrate that Gnn-Rag can be integrated with other LLMs to improve their
KGQA reasoning without retraining.

Case Studies on Faithfulness. Figure 4 illustrates two case studies from the
CWQ dataset, showing how Gnn-Rag improves LLM’s faithfulness, i.e., how well
the LLM follows the question’s instructions and uses the right information
from the KG. In both cases, Gnn-Rag retrieves multi-hop information, which is
necessary for answering the questions correctly. In the first case, Gnn-Rag
retrieves both crucial facts <Gilfoyle $\rightarrow$
characters_that_have_lived_here $\rightarrow$ Toronto> and <Toronto
$\rightarrow$ province.capital $\rightarrow$ Ontario> that are required to
answer the question, unlike the KG-RAG baseline (RoG) that fetches only the
first fact. In the second case, the KG-RAG baseline incorrectly retrieves
information about <Erin Brockovich $\rightarrow$ person> and not <Erin
Brockovich $\rightarrow$ film_character> that the question refers to. Gnn-Rag
uses GNNs to explore how <Erin Brockovich> and <Michael Renault Mageau>
entities are related in the KG, resulting into retrieving facts about <Erin
Brockovich $\rightarrow$ film_character>. The retrieved facts include
important information <films_with_this_crew_job $\rightarrow$ Consultant>.

Figure 5 illustrates one case study from the WebQSP dataset, showing how RA
(Section 4.4) improves Gnn-Rag. Initially, the GNN does not retrieve helpful
information due to its limitation to understand natural language, i.e., that
<jurisdiction.bodies> usually “make the laws”. Gnn-Rag+RA retrieves the right
information, helping the LLM answer the question correctly.

Further ablation studies are provided in Appendix D. Limitations are discussed
in Appendix E.

Figure 4: Two case studies that illustrate how Gnn-Rag improves the LLM’s
faithfulness. In both cases, Gnn-Rag retrieves _multi-hop_ information that is
necessary for answering the complex questions. Figure 5: One case study that
illustrates the benefit of retrieval augmentation (RA). RA uses LLMs to fetch
semantically relevant KG information, which may have been missed by the GNN.

##  7 Conclusion

We introduce Gnn-Rag, a novel method for combining the reasoning abilities of
LLMs and GNNs for RAG-based KGQA. Our contributions are the following. (1)
Framework: Gnn-Rag repurposes GNNs for KGQA retrieval to enhance the reasoning
abilities of LLMs. Moreover, our retrieval analysis guides the design of a
retrieval augmentation technique to boost Gnn-Rag performance. (2)
Effectiveness & Faithfulness: Gnn-Rag achieves state-of-the-art performance in
two widely used KGQA benchmarks (WebQSP and CWQ). Furthermore, Gnn-Rag is
shown to retrieve multi-hop information that is necessary for faithful LLM
reasoning on complex questions. (3) Efficiency: Gnn-Rag improves vanilla LLMs
on KGQA performance without incurring additional LLM calls as existing RAG
systems for KGQA require. In addition, Gnn-Rag outperforms or matches GPT-4
performance with a 7B tuned LLM.

## References

  * Andersen et al. (2006) Reid Andersen, Fan Chung, and Kevin Lang.  Local graph partitioning using pagerank vectors.  In _2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06)_ , 2006.
  * Atzeni et al. (2021) Mattia Atzeni, Jasmina Bogojeska, and Andreas Loukas.  Sqaler: Scaling question answering by decoupling multi-hop and logical reasoning.  _Advances in Neural Information Processing Systems_ , 2021.
  * Baek et al. (2023) Jinheon Baek, Alham Fikri Aji, and Amir Saffari.  Knowledge-augmented language model prompting for zero-shot knowledge graph question answering.  _arXiv preprint arXiv:2306.04136_ , 2023.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor.  Freebase: a collaboratively created graph database for structuring human knowledge.  In _Proceedings of the 2008 ACM SIGMOD international conference on Management of data_ , pages 1247–1250, 2008.
  * Bommasani et al. (2021) Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Choi et al. (2024) Hyeong Kyu Choi, Seunghun Lee, Jaewon Chu, and Hyunwoo J Kim.  Nutrea: Neural tree search for context-guided multi-hop kgqa.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Chowdhery et al. (2023) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al.  Palm: Scaling language modeling with pathways.  _Journal of Machine Learning Research_ , 24(240):1–113, 2023.
  * Chung et al. (2024) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al.  Scaling instruction-finetuned language models.  _Journal of Machine Learning Research_ , 25(70):1–53, 2024.
  * Das et al. (2021) Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay-Yoon Lee, Lizhen Tan, Lazaros Polymenakos, and Andrew McCallum.  Case-based reasoning for natural language queries over knowledge bases.  _arXiv preprint arXiv:2104.08762_ , 2021.
  * Gururangan et al. (2020) Suchin Gururangan, Ana Marasović, Swabha Swayamdipta, Kyle Lo, Iz Beltagy, Doug Downey, and Noah A Smith.  Don’t stop pretraining: Adapt language models to domains and tasks.  _arXiv preprint arXiv:2004.10964_ , 2020.
  * He et al. (2021) Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen.  Improving multi-hop knowledge base question answering by learning intermediate supervision signals.  In _Proceedings of the 14th ACM international conference on web search and data mining_ , pages 553–561, 2021.
  * 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.
  * Hoffmann et al. (2022) Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al.  Training compute-optimal large language models.  _arXiv preprint arXiv:2203.15556_ , 2022.
  * Huang et al. (2024) Xuanwen Huang, Kaiqiao Han, Yang Yang, Dezheng Bao, Quanjin Tao, Ziwei Chai, and Qi Zhu.  Can gnn be good adapter for llms?  _arXiv preprint arXiv:2402.12984_ , 2024.
  * Jiang et al. (2023a) 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.  _arXiv preprint arXiv:2305.09645_ , 2023a.
  * Jiang et al. (2023b) Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, and Ji-Rong Wen.  Unikgqa: Unified retrieval and reasoning for solving multi-hop question answering over knowledge graph.  In _International Conference on Learning Representations_ , 2023b.
  * 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.
  * Jin et al. (2024) Bowen Jin, Chulin Xie, Jiawei Zhang, Kashob Kumar Roy, Yu Zhang, Suhang Wang, Yu Meng, and Jiawei Han.  Graph chain-of-thought: Augmenting large language models by reasoning on graphs.  _arXiv preprint arXiv:2404.07103_ , 2024.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Lan and Jiang (2020) Yunshi Lan and Jing Jiang.  Query graph generation for answering multi-hop complex questions from knowledge bases.  In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault, editors, _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 969–974. Association for Computational Linguistics, July 2020.
  * Lan et al. (2022) Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen.  Complex knowledge base question answering: A survey.  _IEEE Transactions on Knowledge and Data Engineering_ , 2022.
  * 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.
  * Li et al. (2023) Tianle Li, Xueguang Ma, Alex Zhuang, Yu Gu, Yu Su, and Wenhu Chen.  Few-shot in-context learning on knowledge base question answering.  In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6966–6980. Association for Computational Linguistics, 2023.
  * Lin et al. (2023) Xi Victoria Lin, Xilun Chen, Mingda Chen, Weijia Shi, Maria Lomeli, Rich James, Pedro Rodriguez, Jacob Kahn, Gergely Szilvasy, Mike Lewis, et al.  Ra-dit: Retrieval-augmented dual instruction tuning.  _arXiv preprint arXiv:2310.01352_ , 2023.
  * Luo et al. (2024) Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan.  Reasoning on graphs: Faithful and interpretable large language model reasoning.  In _International Conference on Learning Representations_ , 2024.
  * Mavromatis and Karypis (2022) Costas Mavromatis and George Karypis.  ReaRev: Adaptive reasoning for question answering over knowledge graphs.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 2447–2458, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  URL https://aclanthology.org/2022.findings-emnlp.181.
  * Mavromatis et al. (2024) Costas Mavromatis, Petros Karypis, and George Karypis.  Sempool: Simple, robust, and interpretable kg pooling for enhancing language models.  In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_ , pages 154–166. Springer, 2024.
  * Miller et al. (2016) Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston.  Key-value memory networks for directly reading documents.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , 2016.
  * Pan et al. (2024) Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu.  Unifying large language models and knowledge graphs: A roadmap.  _IEEE Transactions on Knowledge and Data Engineering_ , 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)_ , 2019.
  * Saxena et al. (2020) Apoorv Saxena, Aditay Tripathi, and Partha Talukdar.  Improving multi-hop question answering over knowledge graphs using knowledge base embeddings.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 2020.
  * Schlichtkrull et al. (2018) Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling.  Modeling relational data with graph convolutional networks.  In _The semantic web: 15th international conference, ESWC 2018, Heraklion, Crete, Greece, June 3–7, 2018, proceedings 15_ , pages 593–607. Springer, 2018.
  * Sen et al. (2021) Priyanka Sen, Amir Saffari, and Armin Oliya.  Expanding end-to-end question answering on differentiable knowledge graphs with intersection.  _arXiv preprint arXiv:2109.05808_ , 2021.
  * Shi et al. (2021) Jiaxin Shi, Shulin Cao, Lei Hou, Juanzi Li, and Hanwang Zhang.  Transfernet: An effective and transparent framework for multi-hop question answering over relation graph.  _arXiv preprint arXiv:2104.07302_ , 2021.
  * Sun et al. (2018) Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William Cohen.  Open domain question answering using early fusion of knowledge bases and text.  In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun’ichi Tsujii, editors, _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 4231–4242. Association for Computational Linguistics, 2018.
  * Sun et al. (2019) Haitian Sun, Tania Bedrax-Weiss, and William W Cohen.  Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text.  _arXiv preprint arXiv:1904.09537_ , 2019.
  * Sun et al. (2024) Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Heung-Yeung Shum, and Jian Guo.  Think-on-graph: Deep and responsible reasoning of large language model with knowledge graph.  In _International Conference on Learning Representations_ , 2024.
  * Sun et al. (2020) Yawei Sun, Lingling Zhang, Gong Cheng, and Yuzhong Qu.  Sparqa: skeleton-based semantic parsing for complex questions over knowledge bases.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 8952–8959, 2020.
  * Talmor and Berant (2018) Alon Talmor and Jonathan Berant.  The web as a knowledge-base for answering complex questions.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics_ , 2018.
  * Taori et al. (2023) Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto.  Stanford alpaca: An instruction-following llama model.  https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * 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.
  * 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.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard.  Complex embeddings for simple link prediction.  In _International conference on machine learning_. PMLR, 2016.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Vrandečić and Krötzsch (2014) Denny Vrandečić and Markus Krötzsch.  Wikidata: a free collaborative knowledgebase.  _Communications of the ACM_ , 57(10):78–85, 2014.
  * Wang et al. (2023) Keheng Wang, Feiyu Duan, Sirui Wang, Peiguang Li, Yunsen Xian, Chuantao Yin, Wenge Rong, and Zhang Xiong.  Knowledge-driven cot: Exploring faithful reasoning in llms for knowledge-intensive question answering.  _arXiv preprint arXiv:2308.13259_ , 2023.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837, 2022.
  * Wu et al. (2023) Yike Wu, Nan Hu, Guilin Qi, Sheng Bi, Jie Ren, Anhuan Xie, and Wei Song.  Retrieve-rewrite-answer: A kg-to-text enhanced llms framework for knowledge graph question answering.  _arXiv preprint arXiv:2309.11206_ , 2023.
  * Xie et al. (2022) Tianbao Xie, Chen Henry Wu, Peng Shi, Ruiqi Zhong, Torsten Scholak, Michihiro Yasunaga, Chien-Sheng Wu, Ming Zhong, Pengcheng Yin, Sida I. Wang, Victor Zhong, Bailin Wang, Chengzu Li, Connor Boyle, Ansong Ni, Ziyu Yao, Dragomir Radev, Caiming Xiong, Lingpeng Kong, Rui Zhang, Noah A. Smith, Luke Zettlemoyer, and Tao Yu.  Unifiedskg: Unifying and multi-tasking structured knowledge grounding with text-to-text language models.  _EMNLP_ , 2022.
  * Ye et al. (2022) Xi Ye, Semih Yavuz, Kazuma Hashimoto, Yingbo Zhou, and Caiming Xiong.  RNG-KBQA: Generation augmented iterative ranking for knowledge base question answering.  In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6032–6043. Association for Computational Linguistics, 2022.
  * Yih et al. (2015) Scott Wen-tau Yih, Ming-Wei Chang, Xiaodong He, and Jianfeng Gao.  Semantic parsing via staged query graph generation: Question answering with knowledge base.  In _Proceedings of the Joint Conference of the 53rd Annual Meeting of the ACL and the 7th International Joint Conference on Natural Language Processing of the AFNLP_ , 2015.
  * Yu et al. (2022) Donghan Yu, Sheng Zhang, Patrick Ng, Henghui Zhu, Alexander Hanbo Li, Jun Wang, Yiqun Hu, William Wang, Zhiguo Wang, and Bing Xiang.  Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases.  _arXiv preprint arXiv:2210.00063_ , 2022.
  * Zhang et al. (2022a) Jing Zhang, Xiaokang Zhang, Jifan Yu, Jian Tang, Jie Tang, Cuiping Li, and Hong Chen.  Subgraph retrieval enhanced model for multi-hop knowledge base question answering.  _arXiv preprint arXiv:2202.13296_ , 2022a.
  * Zhang et al. (2024) Tianjun Zhang, Shishir G Patil, Naman Jain, Sheng Shen, Matei Zaharia, Ion Stoica, and Joseph E Gonzalez.  Raft: Adapting language model to domain specific rag.  _arXiv preprint arXiv:2403.10131_ , 2024.
  * Zhang et al. (2022b) Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christopher D Manning, and Jure Leskovec.  Greaselm: Graph reasoning enhanced language models.  In _International Conference on Learning Representations_ , 2022b.
  * Zhang et al. (2023) Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, et al.  Siren’s song in the ai ocean: a survey on hallucination in large language models.  _arXiv preprint arXiv:2309.01219_ , 2023.
  * Zhang et al. (2018) Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J Smola, and Le Song.  Variational reasoning for question answering with knowledge graph.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018.

Appendix / supplemental material

##  Appendix A Analysis

Table 6: Efficiency vs. effectiveness trade-off of LLM-based retrieval.

Retrieval | #LLM Calls | Answer Hit (%)
---|---|---
(efficiency) | (effectiveness)
RoG [Luo et al., 2024] | 3 | 85.7
1 | 77.2
ToG [Sun et al., 2024] | up to 21 | 76.2
3 | 66.3
Gnn-Rag | 0 | 87.2

  * •

#LLM Calls are controlled by the hyperparameter $k$ (number of beams) during
beam-search decoding.

In this section, we analyze the reasoning and retrieval abilities of GNN and
LLMs, respectively.

######  Definition A.1 (Ground-truth Subgraph).

Given a question $q$, we define its ground-truth reasoning subgraph
${\mathcal{G}}_{q}^{\ast}$ as the union of the ground-truth reasoning paths
that lead to the correct answers $\\{a\\}$. Reasoning paths are defined as the
KG paths that reach the answer nodes, starting from the question entities
$\\{e\\}$, e.g., <Jamaica $\rightarrow$ language_spoken $\rightarrow$ English>
for question “Which language do Jamaican people speak?”. In essence,
${\mathcal{G}}_{q}^{\ast}$ contains only the necessary entities and relations
that are needed to answer $q$.

######  Definition A.2 (Effective Reasoning).

We define that a model $M$ _reasons effectively_ if its output is
$\\{a\\}=M({\mathcal{G}}_{q}^{\ast},q)$, i.e., the model returns the correct
answers given the ground-truth subgraph ${\mathcal{G}}_{q}^{\ast}$.

As KGQA methods do not use the ground-truth subgraph
${\mathcal{G}}_{q}^{\ast}$ for reasoning, but the retrieved subgraph
${\mathcal{G}}_{q}$, we identify two cases in which the reasoning model
_cannot_ reason effectively, i.e., $\\{a\\}\neq M({\mathcal{G}}_{q},q)$.

Case 1: ${\mathcal{G}}_{q}\subset{\mathcal{G}}_{q}^{\ast}$, i.e., the
retrieved subgraph ${\mathcal{G}}_{q}$ does not contain all the necessary
information for answering $q$. An application of this case is when we use LLMs
for retrieval. As LLMs are not designed to handle complex graph information,
the retrieved subgraph ${\mathcal{G}}_{q}$ may contain incomplete KG
information. Existing LLM-based methods rely on employing an increased number
of LLM calls (beam search decoding) to fetch diverse reasoning paths that
approximate ${\mathcal{G}}_{q}^{\ast}$. Table 6 provides experimental evidence
that shows how LLM-based retrieval trades computational efficiency for
effectiveness. _In particular, when we switch from beam-search decoding to
greedy decoding for faster LLM retrieval, the KGQA performance drops by
8.3–9.9% points at answer hit_.

Case 2: ${\mathcal{G}}_{q}^{\ast}\subset{\mathcal{G}}_{q}$ and model $M$
cannot “filter-out” irrelevant facts during reasoning. An application of this
case is when we use GNNs for reasoning. GNNs cannot understand the textual
semantics of KGs and natural questions the same way as LLMs do, and they
reason ineffectively if they cannot tell the irrelevant KG information. We
develop the following Theorem that supports this case for GNNs.

######  Theorem A.3 (Simplified).

Under mild assumptions and due to the sum operator of GNNs in Equation 1, a
GNN can reason effectively by selecting question-relevant facts and filtering-
out question-irrelevant facts through $\omega(q,r)$.

We provide the full theorem and its proof in Appendix B. Theorem A.3 suggests
that GNNs need to perform semantic matching via function $\omega(q,r)$ apart
from leveraging the graph information encoded in the KG. Our analysis suggests
that GNNs lack reasoning abilities for KGQA if they cannot perform effective
semantic matching between the KG and the question.

##  Appendix B Full Theorem & Proof

To analyze under which conditions GNN perform well for KGQA, we use the
ground-truth subgraph $\mathcal{G}_{q}^{\ast}$ for a question $q$, as defined
in Definition A.1. We compare the output representations of a GNN over the
ground-truth $\mathcal{G}_{q}^{\ast}$ and another $\mathcal{G}_{q}$ to measure
how close the two outputs are.

We always assume ${\mathcal{G}}_{q}^{\ast}\subseteq{\mathcal{G}}_{q}$ for a
question $q$. 1-hop facts that contain $v$ are denoted as
${\mathcal{N}}_{v}^{\ast}$.

######  Definition B.1.

Let $M$ be a GNN model for answering question $q$ over a KG $\mathcal{G}_{q}$,
where the output is computed by $M(q,{\mathcal{G}}_{q})$. $M$ consists of $L$
reasoning steps (GNN layers). We assume $M$ is an effective reasoner,
according to Definition A.2. Furthermore, we define the reasoning process
${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}$ as the sequence of the derived node
representations at each step $l$, i.e.,

${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}=\Big{\\{}\\{{\bm{h}}_{v}^{(1)}:v\in{\mathcal{G}}_{q}\\},\dots,\\{{\bm{h}}_{v}^{(L)}:v\in{\mathcal{G}}_{q}\\}\Big{\\}}.$
(4)

We also define the optimal reasoning process for answering question $q$ with
GNN $M$ as ${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}^{\ast}}$. We assume that zero
node representations do not contribute in Equation 4.

######  Lemma B.2.

If two subgraphs ${\mathcal{G}}_{1}$ and ${\mathcal{G}}_{2}$ have the same
nodes, and a GNN outputs the same node representations for all nodes
$v\in{\mathcal{G}}_{1}$ and $v\in{\mathcal{G}}_{2}$ at each step $l$, then the
reasoning processes ${\mathcal{R}}_{M,q,{\mathcal{G}}_{1}}$ and
${\mathcal{R}}_{M,q,{\mathcal{G}}_{2}}$ are identical.

This is true as ${\bm{h}}_{v}^{(l)}$ with $l=1,\dots,L$ for both
${\mathcal{G}}_{1}$ and ${\mathcal{G}}_{2}$ and by using Definition B.1 to
show
${\mathcal{R}}_{M,q,{\mathcal{G}}_{1}}={\mathcal{R}}_{M,q,{\mathcal{G}}_{2}}$.
Note that Lemma B.2 does not make any assumptions about the actual edges of
${\mathcal{G}}_{1}$ and ${\mathcal{G}}_{2}$.

To analyze the importance of semantic matching for GNNs, we consider the
following GNN update

${\bm{h}}_{v}^{(l)}=\psi\Big{(}{\bm{h}}_{v}^{(l-1)},\sum_{v^{\prime}\in\mathcal{N}_{v}}\omega(q,r)\cdot{\bm{m}}_{vv^{\prime}}^{(l)}\Big{)}.$
(5)

where
$\omega(\cdot,\cdot):{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\xrightarrow[]{}\\{0,1\\}$
is a binary function that decides if fact $(v,r,v^{\prime})$ is relevant to
question $q$ or not. Neighbor messages ${\bm{m}}_{vv^{\prime}}^{(l)}$ are
aggregated by a sum-operator, which is typically employed in GNNs. Function
$\psi(\cdot)$ combines representations among consecutive GNN layers. We assume
${\bm{h}}_{v}^{(0)}\in{\mathbb{R}}^{d}$ and that
$\psi\Big{(}h_{v}^{(0)},0^{d}\Big{)}=0^{d}$

######  Theorem B.3.

If $\omega(q,r)=0,\forall(v,r,v^{\prime})\notin{\mathcal{G}}_{q}^{\ast}$ and
$\omega(q,r)=1,\forall(v,r,v^{\prime})\in{\mathcal{G}}_{q}^{\ast}$, then
${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}$ is an optimal reasoning process of GNN
$M$ for answering $q$.

###### Proof.

We show that

$\sum_{v^{\prime}\in\mathcal{N}_{v}}\omega(q,r)\cdot{\bm{m}}_{vv^{\prime}}^{(l)}=\sum_{v^{\prime}\in{\mathcal{N}}^{\ast}_{v}}{\bm{m}}_{vv^{\prime}}^{(l)},$
(6)

which gives that
${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}={\mathcal{R}}_{M,q,{\mathcal{G}}_{q}^{\ast}}$
via Lemma B.2. This is true if

$\omega(q,r)=\begin{cases}1&\text{if
$(v,r,v^{\prime})\in{\mathcal{N}}^{\ast}_{v}$,}\\\ 0&\text{if
$(v,r,v^{\prime})\notin{\mathcal{N}}^{\ast}_{v}$,}\end{cases}$ (7)

which means that GNNs need to filter-out question irrelevant facts. We
consider two cases.

Case 1. Let $u$ denote a node that is present in ${\mathcal{G}}_{q}$, but not
in ${\mathcal{G}}^{\ast}_{q}$. Then, all facts that contain $u$ are not
present in ${\mathcal{G}}^{\ast}_{q}$. Condition
$\omega(q,r)=0,\forall(v,r,v^{\prime})\notin{\mathcal{G}}_{q}^{\ast}$ of
Theorem B.3 gives that

$\displaystyle\omega(q,r)$ $\displaystyle=0,\forall(u,r,v^{\prime}),\text{ and
}$ $\displaystyle\omega(q,r)$ $\displaystyle=0,\forall(v,r,u).$ (8)

as node $u\notin{\mathcal{G}}_{q}^{\ast}$. This gives

$\sum_{v^{\prime}\in\mathcal{N}(u)}\omega(q,r)\cdot\;{\bm{m}}_{uv^{\prime}}^{(l)}=0,$
(9)

as no edges will contribute to the GNN update. With
$\psi\Big{(}h_{v}^{(0)},0^{d}\Big{)}=0^{d}$, we have

$h_{u}^{(l)}=0^{d},\forall u\notin{\mathcal{G}}^{\ast}_{q}\text{ with
}l=\\{1,\dots,L\\},$ (10)

which means that nodes $u\notin{\mathcal{G}}^{\ast}_{q}$ do not contribute to
the reasoning process ${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}$; see Definition
B.1.

Case 2. Let $p$ denote a relation between two nodes $v$ and $v^{\prime}$ that
is present in ${\mathcal{G}}_{q}$, but not in ${\mathcal{G}}^{\ast}_{q}$. We
decompose the GNN update to

$\sum_{v^{\prime}\in\mathcal{N}_{r}(v)}\omega(q,r)\cdot\;{\bm{m}}_{vv^{\prime}}^{(l)}+\sum_{v^{\prime}\in\mathcal{N}_{p}(v)}\omega(q,p)\cdot\;{\bm{m}}_{vv^{\prime}}^{(l)},$
(11)

where the first term includes facts $\mathcal{N}_{r}$ that are present in
${\mathcal{G}}_{q}^{\ast}$ and the second term includes facts
$\mathcal{N}_{p}$ that are present in ${\mathcal{G}}_{q}$ only. Using the
condition
$\omega(q,r)=0,\forall(v,r,v^{\prime})\notin{\mathcal{G}}_{q}^{\ast}$ of
Theorem B.3, we have

$\sum_{v^{\prime}\in\mathcal{N}_{p}(v)}\omega(q,p)\cdot\;{\bm{m}}_{vv^{\prime}}^{(l)}=0.$
(12)

Using condition
$\omega(q,r)=1,\forall(v,r,v^{\prime})\in{\mathcal{G}}_{q}^{\ast}$, we have

$\sum_{v^{\prime}\in\mathcal{N}_{r}(v)}\omega(q,r)\cdot\;{\bm{m}}_{vv^{\prime}}^{(l)}=\sum_{v^{\prime}\in\mathcal{N}_{r}(v)}{\bm{m}}_{vv^{\prime}}^{(l)}.$
(13)

Combining the two above expression gives

$\sum_{v^{\prime}\in\mathcal{N}_{v}}\omega(q,r)\cdot{\bm{m}}_{vv^{\prime}}^{(l)}=\sum_{v^{\prime}\in\mathcal{N}_{r}(v)}{\bm{m}}_{vv^{\prime}}^{(l)}=\sum_{v^{\prime}\in{\mathcal{N}}^{\ast}_{v}}{\bm{m}}_{vv^{\prime}}^{(l)}.$
(14)

It is straightforward to obtain
${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}={\mathcal{R}}_{M,q,{\mathcal{G}}_{q}^{\ast}}$
via Lemma B.2 in this case.

Putting it altogether. Combining Case 1 and Case 2,nodes
$u\notin{\mathcal{G}}_{q}^{\ast}$ do not contribute to
${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}$, while for other nodes we have
${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}={\mathcal{R}}_{M,q,{\mathcal{G}}_{q}^{\ast}}$.
Thus, overall we have
${\mathcal{R}}_{M,q,{\mathcal{G}}_{q}}={\mathcal{R}}_{M,q,{\mathcal{G}}_{q}^{\ast}}$.
∎

##  Appendix C Experimental Setup

KGQA Datasets. We experiment with two widely used KGQA benchmarks:
WebQuestionsSP (WebQSP) Yih et al. [2015], Complex WebQuestions 1.1 (CWQ)
Talmor and Berant [2018]. We also experiment with MetaQA-3 Zhang et al. [2018]
dataset. We provide the dataset statistics Table 7. WebQSP contains 4,737
natural language questions that are answerable using a subset Freebase KG
[Bollacker et al., 2008]. This KG contains 164.6 million facts and 24.9
million entities. The questions require up to 2-hop reasoning within this KG.
Specifically, the model needs to aggregate over two KG facts for 30% of the
questions, to reason over constraints for 7% of the questions, and to use a
single KG fact for the rest of the questions. CWQ is generated from WebQSP by
extending the question entities or adding constraints to answers, in order to
construct more complex multi-hop questions (34,689 in total). There are four
types of questions: composition (45%), conjunction (45%), comparative (5%),
and superlative (5%). The questions require up to 4-hops of reasoning over the
KG, which is the same KG as in WebQSP. MetaQA-3 consists of more than 100k
3-hop questions in the domain of movies. The questions were constructed using
the KG provided by the WikiMovies Miller et al. [2016] dataset, with about 43k
entities and 135k triples. For MetaQA-3, we use 1,000 (1%) of the training
questions.

Table 7: Datasets statistics. “avg.$|{\mathcal{V}}_{q}|$” denotes average
number of entities in subgraph, and “coverage” denotes the ratio of at least
one answer in subgraph.

Datasets | Train | Dev | Test | avg. $|{\mathcal{V}}_{q}|$ | coverage (%)
---|---|---|---|---|---
WebQSP | 2,848 | 250 | 1,639 | 1,429.8 | 94.9
CWQ | 27,639 | 3,519 | 3,531 | 1,305.8 | 79.3
MetaQA-3 | 114,196 | 14,274 | 14,274 | 497.9 | 99.0

Implementation. For subgraph retrieval, we use the linked entities to the KG
provided by Yih et al. [2015] for WebQSP, by Talmor and Berant [2018] for CWQ.
We obtain dense subgraphs by He et al. [2021]. It runs the PageRank Nibble
Andersen et al. [2006] (PRN) method starting from the linked entities to
select the top-$m$ ($m=2,000$) entities to be included in the subgraph.

We employ ReaRev111https://github.com/cmavro/ReaRev_KGQA [Mavromatis and
Karypis, 2022] for GNN reasoning (Section 4.1) and
RoG222https://github.com/RManLuo/reasoning-on-graphs [Luo et al., 2024] for
RAG-based prompt tuning (Section 4.2), following their official implementation
codes. In addition, we empower ReaRev with $\text{LM}_{\text{SR}}$ (Section
4.1), which is obtained by following the implementation of
SR333https://github.com/RUCKBReasoning/SubgraphRetrievalKBQA [Zhang et al.,
2022a]. For both training and inference of these methods, we use their
suggested hyperparameters, without performing further hyperparameter search.
Model selection is performed based on the validation data. Experiments with
GNNs were performed on a Nvidia Geforce RTX-3090 GPU over 128GB RAM machine.
Experiments with LLMs were performed on 4 A100 GPUs connected via NVLink and
512 GB of memory. The experiments are implemented with PyTorch.

For LLM prompting during retrieval (Section 4.4), we use the following prompt:

Please generate a valid relation path that can be helpful for answering the
following question:
{Question}

For LLM prompting during reasoning (Section 4.2), we use the following prompt:

Based on the reasoning paths, please answer the given question. Please keep
the answer as simple as possible and return all the possible answers as a
list.\n
Reasoning Paths: {Reasoning Paths} \n
Question: {Question}

During GNN inference, each node in the subgraph is assigned a probability of
being the correct answer, which is normalized via $\mathrm{softmax}$. To
retrieve answer candidates, we sort the nodes based on the their probability
scores, and select the top nodes whose cumulative probability score is below a
threshold. We set the threshold to 0.95. To retrieve the shortest paths
between the question entities and answer candidates for RAG, we use the
NetworkX library444https://networkx.org/.

Competing Approaches.

We evaluate the following categories of methods: 1. Embedding, 2. GNN, 3. LLM,
4. KG+LMM, and 5. GNN+LLM.

  1. 1.

KV-Mem Miller et al. [2016] is a key-value memory network for KGQA. EmbedKGQA
Saxena et al. [2020] utilizes KG pre-trained embeddings Trouillon et al.
[2016] to improve multi-hop reasoning. TransferNet Shi et al. [2021] improves
multi-hop reasoning over the relation set. Rigel Sen et al. [2021] improves
reasoning with questions of multiple entities.

  2. 2.

GraftNet Sun et al. [2018] uses a convolution-based GNN Kipf and Welling
[2016]. PullNet Sun et al. [2019] is built on top of GraftNet, but learns
which nodes to retrieve via selecting shortest paths to the answers. NSM He et
al. [2021] is the adaptation of GNNs for KGQA. NSM+h He et al. [2021] improves
NSM for multi-hop reasoning. SQALER Atzeni et al. [2021] learns which
relations (facts) to retrieve during KGQA for GNN reasoning. Similarly, SR+NSM
[Zhang et al., 2022a] proposes a relation-path retrieval. UniKGQA [Jiang et
al., 2023b] unifies the graph retrieval and reasoning process with a single
LM. ReaRev [Mavromatis and Karypis, 2022] explores diverse reasoning paths in
a multi-stage manner.

  3. 3.

We experiment with instruction-tuned LLMs. Flan-T5 [Chung et al., 2024] is
based on T5, while Aplaca [Taori et al., 2023] and LLaMA2-Chat [Touvron et
al., 2023] are based on LLaMA. ChatGPT555https://openai.com/blog/chatgpt is a
powerful closed-source LLM that excels in many complex tasks. ChatGPT+CoT uses
the chain-of-thought [Wei et al., 2022] prompt to improve the ChatGPT. We
access ChatGPT ‘gpt-3.5-turbo’ through its API (as of May 2024).

  4. 4.

KD-CoT [Wang et al., 2023] enhances CoT prompting for LLMs with relevant
knowledge from KGs. StructGPT [Jiang et al., 2023a] retrieves KG facts for
RAG. KB-BINDER [Li et al., 2023] enhances LLM reasoning by generating logical
forms of the questions. ToG [Sun et al., 2024] uses a powerful LLM to select
relevant facts hop-by-hop. RoG [Luo et al., 2024] uses the LLM to generate
relation paths for better planning.

  5. 5.

G-Retriever [He et al., 2024] augments LLMs with GNN-based prompt tuning.

##  Appendix D Additional Experimental Results

###  D.1 Question Analysis

Table 8: Performance analysis (F1) based on the number of maximum hops that
connect question entities to answer entities.

Method | WebQSP | CWQ
---|---|---
1 hop | 2 hop |  $\geq$3 hop | 1 hop | 2 hop |  $\geq$3 hop
RoG | 73.4 | 63.3 | – | 50.4 | 60.7 | 40.0
Gnn-Rag | 72.0 | 69.8 | – | 47.4 | 69.4 | 51.8
Gnn-Rag +RA | 74.6 | 71.1 | – | 48.2 | 70.9 | 47.7

Following the case studies presented in Figure 4 and Figure 5, we provide
numerical results on how Gnn-Rag improves multi-hop question answering and how
retrieval augmentation (RA) enhances simple hop questions. Table 8 summarizes
these results. Gnn-Rag improves performance on multi-hop questions ($\geq$2
hops) by 6.5–11.8% F1 points over RoG. Furthermore, RA improves performance on
single-hop questions by 0.8–2.6% F1 points over Gnn-Rag.

Table 9: Performance analysis (F1) based on the number of answers (#Ans).

Method | WebQSP | CWQ
---|---|---
#Ans=1 | 2$\leq$#Ans$\leq$4 | 5$\leq$#Ans$\leq$9 | #Ans$\geq$10 | #Ans=1 | 2$\leq$#Ans$\leq$4 | 5$\leq$#Ans$\leq$9 | #Ans$\geq$10
RoG | 67.89 | 79.39 | 75.04 | 58.33 | 56.90 | 53.73 | 58.36 | 43.62
Gnn-Rag | 71.24 | 76.30 | 74.06 | 56.28 | 60.40 | 55.52 | 61.49 | 50.08
Gnn-Rag +RA | 71.16 | 82.31 | 77.78 | 57.71 | 62.09 | 56.47 | 62.87 | 50.33

Table 9 presents results with respect to the number of correct answers. As
shown, RA enhances Gnn-Rag in almost all cases as it can fetch correct answers
that might have been missed by the GNN.

###  D.2 GNN Effect

Table 10: Performance comparison of different GNN models at complex KGQA
(CWQ).

Retriever | KGQA Model | CWQ
---|---|---
Hit∗ | H@1 | F1
Dense Subgraph | GraftNet | – | 45.3 | 35.8
Dense Subgraph | NSM | – | 47.9 | 42.0
Dense Subgraph | ReaRev | – | 52.7 | 49.1
RoG | LLaMA2-Chat-7B (tuned) | 62.6 | 57.8 | 56.2
Gnn-Rag: GraftNet | 58.2 | 51.9 | 49.4
Gnn-Rag: NSM | 58.5 | 52.5 | 50.1
Gnn-Rag: ReaRev | 66.8 | 61.7 | 59.4

Table 11: Results on MetaQA-3 dataset.

Method | MetaQA-3
---|---
| Hit@1
RoG | 84.8
RoG+pretraining | 88.9
Gnn-Rag | 98.6

Gnn-Rag employs ReaRev [Mavromatis and Karypis, 2022] as its GNN retriever,
which is a powerful GNN for deep KG reasoning. In this section, we ablate on
the impact of the GNN used for retrieval, i.e., how strong and weak GNNs
affect KGQA performance. We experiment with GraftNet [Sun et al., 2018] and
NSM [He et al., 2021] GNNs, which are less powerful than ReaRev at KGQA. The
results are presented in Table 10. As shown, strong GNNs (ReaRev) are required
in order to improve RAG at KGQA. Retrieval with weak GNNs (NSM and GraftNet)
underperfoms retrieval with ReaRev by 9.2–9.8% and retrieval with RoG by
5.3–5.9% points at H@1.

###  D.3 MetaQA-3

Table 11 presents results on the MetaQA-3 dataset, which requires 3-hop
reasoning. RoG is a LLM-based retrieval which cannot handle the multi-hop KG
information effectively and as a result, RoG underperforms (even when using
additional pretraining data from WebQSP & CWQ datasets). On the other hand,
Gnn-Rag relies on GNNs that are able to retrieve useful graph information for
multi-hop questions and achieves an almost perfect performance of 98.6% at
Hit@1.

###  D.4 Retrieval Augmentation

Table 12: Performance comparison of retrieval augmentation approaches
(extended).

Retriever | KGQA Model | #LLM Calls | WebQSP | CWQ | Avg.
---|---|---|---|---|---
(total) | Hit∗ | H@1 | F1 | Hit∗ | H@1 | F1
Dense Subgraph |  (i) ReaRev + SBERT | 0 | – | 76.4 | 70.9 | – | 52.9 | 47.8 | –
(ii) ReaRev + $\text{LM}_{\text{SR}}$ | 0 | – | 77.5 | 72.8 | – | 52.7 | 49.1 | –
None | LLaMA2-Chat-7B (tuned) | 1 | 65.6 | 60.4 | 49.7 | 40.1 | 36.2 | 33.8 | 47.63
(iii) LLM-based | 4 | 85.7 | 80.0 | 70.8 | 62.6 | 57.8 | 56.2 | 68.85
Gnn-Rag: (i) | 1 | 85.7 | 80.6 | 71.3 | 66.8 | 61.7 | 59.4 | 70.92
Gnn-Rag: (ii) | 1 | 85.0 | 80.3 | 71.5 | 66.2 | 61.3 | 58.9 | 70.50
Gnn-Rag: (i) \+ (ii) | LLaMA2-Chat-7B (tuned) | 1 | 87.2 | 81.0 | 71.7 | 65.5 | 59.5 | 57.5 | 70.40
Gnn-Rag: (i) \+ (iii) | 4 | 90.7 | 82.8 | 73.5 | 68.7 | 62.8 | 60.4 | 73.15
Gnn-Rag: (ii) \+ (iii) | 4 | 89.9 | 82.4 | 73.4 | 67.9 | 63.0 | 61.0 | 72.93
Gnn-Rag: (i) \+ (ii) \+ (iii) | 4 | 90.1 | 81.7 | 72.3 | 67.3 | 61.5 | 59.1 | 72.00
None | LLaMA2-Chat-7B | 1 | 64.4 | – | – | 34.6 | – | – | –
Gnn-Rag: (i) \+ (ii) | 1 | 86.8 | – | – | 62.9 | – | – | –
Gnn-Rag: (i) \+ (iii) | 4 | 88.5 | – | – | 62.1 | – | – | –

Table 12 has the extended results of Table 4, showing performance results on
all three metrics (Hit / H@1 / F1) with respect to the retrieval method used.
Overall, Gnn-Rag improves the vanilla LLM by 149–182%, when employing the same
number of LLM calls for retrieval.

###  D.5 Prompt Ablation

When using RAG, LLM performance depends on the prompts used. To ablate on the
prompt impact, we experiment with the following prompts:

  * •

Prompt A:

Based on the reasoning paths, please answer the given question. Please keep
the answer as simple as possible and return all the possible answers as a
list.\n
Reasoning Paths: {Reasoning Paths} \n
Question: {Question}

  * •

Prompt B:

Based on the provided knowledge, please answer the given question. Please keep
the answer as simple as possible and return all the possible answers as a
list.\n
Knowledge: {Reasoning Paths} \n
Question: {Question}

  * •

Prompt C:

Your tasks is to use the following facts and answer the question. Make sure
that you use the information from the facts provided. Please keep the answer
as simple as possible and return all the possible answers as a list.\n
The facts are the following: {Reasoning Paths} \n
Question: {Question}

Table 13: Performance comparison (%Hit) based on different input prompts.

|  | WebQSP | CWQ
---|---|---|---
Prompt A | RoG | 84.8 | 56.4
Gnn-Rag | 86.8 | 62.9
Prompt B | RoG | 84.3 | 55.2
Gnn-Rag | 85.2 | 61.7
Prompt C | RoG | 81.6 | 51.8
Gnn-Rag | 84.4 | 59.4

We provide the results based on different input prompts in Table 13. As the
results indicate, Gnn-Rag outperforms RoG in all cases, being robust at the
prompt selection.

###  D.6 Effect of Training Data

Table 14: Performance results based on different training data.

Method | WebQSP | CWQ
---|---|---
Training Data (Retriever) | Training Data (KGQA Model) | Hit | Training Data (Retriever) | Training Data (KGQA Model) | Hit
UniKGQA | WebQSP | WebQSP | 77.2 | CWQ | CWQ | 51.2
RoG | WebQSP | WebQSP | 81.5 | CWQ | CWQ | 59.1
WebQSP+CWQ | None | 84.8 | WebQSP+CWQ | None | 56.4
WebQSP+CWQ | WebQSP+CWQ | 85.7 | WebQSP+CWQ | WebQSP+CWQ | 62.6
Gnn-Rag | WebQSP | None | 86.8 | CWQ | None | 62.9
WebQSP | WebQSP+CWQ | 87.2 | CWQ | WebQSP+CWQ | 66.8

Table 14 compares performance of different methods based on the training data
used for training the retriever and the KGQA model. For example, Gnn-Rag
trains a GNN model for retrieval and uses a LLM for KGQA, which can be fine-
tuned or not. As the results show, Gnn-Rag outperforms the competing methods
(RoG and UniKGQA) by either fine-tuning the KGQA model or not, while it uses
the same or less data for training its retriever.

###  D.7 Graph Effect

GNNs operate on dense subgraphs, which might include noisy information. A
question that arises is whether removing irrelevant information from the
subgraph would improve GNN retrieval. We experiment with SR [Zhang et al.,
2022a], which learns to prune question-irrelevant facts from the KG. As shown
in Table 15, although SR can improve the GNN reasoning results – see row (a)
vs. (b) at CWQ –, the retrieval effectiveness deteriorates; rows (c) and (d).
After examination, we found that the sparse subgraph may contain disconnected
KG parts. In this case, Gnn-Rag’s extraction of the shortest paths fails, and
Gnn-Rag returns empty KG information.

Table 15: Performance comparison on different subgraphs.

Retriever | KGQA Model | WebQSP | CWQ
---|---|---|---
Hit∗ | H@1 | F1 | Hit∗ | H@1 | F1
a) Dense Subgraph |  (A) ReaRev + $\text{LM}_{\text{SR}}$ | – | 77.5 | 72.8 | – | 52.7 | 49.1
b) Sparse Subgraph [Zhang et al., 2022a] |  (B) ReaRev + $\text{LM}_{\text{SR}}$ | – | 74.2 | 69.8 | – | 53.3 | 49.7
c) Gnn-Rag: (A) | LLaMA2-Chat-7B (tuned) | 85.0 | 80.3 | 71.5 | 66.2 | 61.3 | 58.9
d) Gnn-Rag: (B) | 83.4 | 78.9 | 69.8 | 60.6 | 55.6 | 53.3

##  Appendix E Limitations

Gnn-Rag assumes that the KG subgraph, on which the GNN reasons, contains
answer nodes. However, as the subgraph is decided by tools such as entity
linking and neighborhood extraction, errors in these tools, e.g., unlinked
entities, can result to subgraphs that do not include any answers. For
example, Table 7 shows that CWQ subgraphs contain an answer in 79.3% of the
questions. In such cases, Gnn-Rag cannot retrieve the correct answers to help
the LLM answer the questions faithfully. In addition, if the KG has
disconnected parts, the shortest path extraction algorithm of Gnn-Rag may
return empty reasoning paths (see Appendix D.7).

##  Appendix F Broader Impacts

Gnn-Rag is a method that grounds the LLM generations for QA using ground-truth
facts from the KG. As a result, Gnn-Rag can have positive societal impacts by
using KG information to alleviate LLM hallucinations in tasks such as QA.