Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning
Authors: LINHAO LUO
Yuan-Fang Li
Gholamreza Haffari
Shirui Pan
Venue: ICLR 2024 poster (2024)
Keywords: large language models
knowledge graphs
reasoning
Primary area: general machine learning (i.e., none of the above)
TL;DR: we propose a novel method called Reasoning on Graphs (RoG) that synergizes LLMs with KGs to enable faithful and interpretable reasoning.

Abstract: Large language models (LLMs) have demonstrated impressive reasoning abilities in complex tasks. However, they lack up-to-date knowledge and experience hallucinations during reasoning, which can lead to incorrect reasoning processes and diminish their performance and trustworthiness. Knowledge graphs (KGs), which capture vast amounts of facts in a structured format, offer a reliable source of knowledge for reasoning. Nevertheless, existing KG-based LLM reasoning methods only treat KGs as factual knowledge bases and overlook the importance of their structural information for reasoning. In this paper, we propose a novel method called reasoning on graphs (RoG) that synergizes LLMs with KGs to enable faithful and interpretable reasoning. Specifically, we present a planning-retrieval-reasoning framework, where RoG first generates relation paths grounded by KGs as faithful plans. These plans are then used to retrieve valid reasoning paths from the KGs for LLMs to conduct faithful reasoning. Furthermore, RoG not only distills knowledge from KGs to improve the reasoning ability of LLMs through training but also allows seamless integration with any arbitrary LLMs during inference. Extensive experiments on two benchmark KGQA datasets demonstrate that RoG achieves state-of-the-art performance on KG reasoning tasks and generates faithful and interpretable reasoning results.

Published as a conference paper at ICLR 2024
REASONING ON GRAPHS: FAITHFUL AND INTER- PRETABLE LARGE LANGUAGE MODEL REASONING
Linhao Luo, Yuan-Fang Li, Gholamreza Haffari
Monash University
Australia
(linhao. luo, fuanfang.. 1,, Gholamreza Haffari Setfarri@mmoasshc.o hat.arreeeaaaaaffaeemmmaaaaaaaa
edu
Shirui Pan"
Griffith University
Australia
s. s..pangrrifithh.ee
ABSTRACT
Large language models (LLMs) have demonstrated impressive reasoning abili- ties in complex tasks. However, they lack up-to-date knowledge and experience hallucinations during reasoning, which can lead to incorrect reasoning processes and diminish their performance and trustworthiness. Knowledge graphs (KGs), which capture vast amounts of facts in a structured format, offer a reliable source of knowledge for reasoning. Nevertheless, existing KG-based LLM reasoning methods only treat KGs as factual knowledge bases and overlook the importance of their structural information for reasoning. In this paper, we propose novel method called reasoning graphs (RoG) that synergizes LLMs with KGs to enable faithful and interpretable reasoning. Specifically, we present a planning- retrieval-reasee reasoning framework, where RoG first generates relation paths grounded by KGs as faithful plans. These plans are then used to retrieve valid reasoning paths from the KGs for LLMs to conduct faithful reasoning. Furthermore, RoG not only distills knowledge from KGs to improve the reasoning ability LLMs through training but also allows seamless integration with any arbitrary LLMs dur- ing inference. Extensive experiments on two benchmark KGQA datasets demon- strate that RoG achieves state-of-the performance KG reasoning tasks and generates faithful and interpretable reasoning results
INTRODUCTION
Large language models (LLMs) have shown great performance in many NLP tasks (Brown al.
2020 [Bagg et al.) 2023). What's 's especially striking is their ability to handle complex tasks through
reasoning (Wei al. 2022 Huang & Chang, 2023). To further unleash L.LMs' reasoning ability, the plan-and-solve paradigm Wang et al.] [023c) has been proposed, in which LLMs are prompted to
generate a plan and execute each reasoning step. In this way, LLMs decompose complex reasoning tasks into a series of sub-tasks and solve them step by step (Khot et al. 2022).
Despite their success, LLMs still limited by the lack of knowledge and prone to hallucinations during reasoning, which can lead to errors in reasoning processes (Hong et al. 2023 Wang et al.) 2023b). For example, as shown in Figure [] LLMs do not have the latest knowledge and hallucinate an incorrect reasoning step: "has daughter". These issues largely diminish the performance and trustworthiness of I.LMs high-stakes scenarios, such as legal judgment and medical diagnosis.
To tackle the issues, knowledge graphs (KGs) have been incorporated to improve the reasoning ability of LLMs (Pan et al., 2024: Luo et al. (202a)). KGs capture abundant factual knowledge in structured format, which provides faithful knowledge source for reasoning. As typical reasoning
"Corresponding author.
"ooe and data available http:///gttttbb./////a/aa//////e

---

Published as a conference paper at ICLR 2024
Question
Question
What product did Apple release in 2023?
Who is the brother Justin Bieber
Output
Output
Justin Bieber is the child of Jenemy Bieber, who has a daughter named Allie Bieber. Thus, the brother of Justin Bieber is Bieber.
Sorry, have knowledge after Sept. 2021. Could you provide some additional inf information?
Lack of Knowledge
Hallucination
Factual Knowledge f
Reasoning Guidance 1
Triple:
(Iphone 15, released__a at, 2023)
Relation path: child_of has_son
Figure 1:
The issues of lack of knowledge and hallucination in LLMS reasoning and how they can be addressed by triples and relation paths from KGs.
task, knowledge graph question answering (KGQA) aims to obtain answers based on knowledge from KGs (Sun al. 2019). Previous works that jointly use KGs and LLMs for KGQA reasoning
can be broadly divided into two categories: 1) semantic parsing methods (Lan & Jiang 2020; Ye
jet al. 2022), which use LLMs to convert questions into logical queries that are executed on KGs to obtain answers; and 2) retrieval-augmented methods (Li et al. 2023 Jiang et al.) (2023), which retrieve triples from KGs as knowledge context and uses LLMs to obtain the final answers.
Although semantic parsing methods generate more accurate and interpretable results by lever- aging reasoning on KGs, the generated logical queries can often be non-executable and yield no answers, due syntax and semantic limitations (Yu et al. 2022a). Retrieval-augmentté methods are more flexible and exploit the ability of LLMS for reasoning. However, they only treat KGs as factual knowledge bases and overlook the importance of their structural information for reasoning Jiang et al. 2022). For instance, as shown in Figure | a relation path, which is a sequence of rela- tions, "chi fdof-hhassse of Justin Bieber?". Therefore, it is essential to enable LLMs to directly reason on KGs to achieve faithful and interpretable reasoning.
can be used to obtain answers to the question "Who is the brother
In this paper, we propose a novel method called reasoning on graphs (RoG) that synergizes LLMs with KGs to conduct faithful and interpretable reasoning. To alleviate the issues of hallucinations and lack of knowledge, we present planning- retrieval-reasonn erates relation paths grounded by KGs as faithful plans via the planning module. These plans are then used to retrieve valid reasoning paths from KGs to conduct faithful reasoning by the retrieval- reasoning module. this way, we not only retrieve the latest. knowledge from KGs but also consider the guidance of KG structure for reasoning and explanations. Moreover, the planning module of RoG can be plug-and-pn aong-and-lay with different LLMs during inference to improve their performance. Based on this framework, RoG is optimized by two tasks: 1) planning optimization, where distill knowl- edge from KGs into LLMs to generate faithful relation paths as plans; and 2) strieval-reasonie optimization, where enable LLMs to conduct faithful reasoning based on retrieved paths and gen- erate interpretable results. We conduct extensive experiments on two benchmark KGQA datasets, and the results demonstrate that RoG achieves state-of-the-ar performance on KG reasoning tasks and generates faithful and interpretable reasoning results.
framework, where RoG first gen-
RELATED WORK
LLM Reasoning Prompt. Many studies have been proposed to harness the reasoning ability of
LLMs to handle complex tasks through prompting (Wei et al. 2022 Wang et al. 2022 Yao al.
2023 Besta et al. 2023). Plan-and-solve /Wang et al. (023c) prompts LLMs to generate a plan and conduct reasoning based on DecomP eHe al. 202 prompts LLMs to decompose the reasoning task into a series of sub-tasks and solve them step by step. However, the problem of hallucinations and lack of knowledge affect the faithfulness of I.L.ss reasoning. ReACT (Yao et al. 2022) treats LLMs as agents, which interact with the environment to get the latest knowledge for reasoning. To explore faithful reasoning. FAME (Hong et al. 2023) introduces the Monte-Carie planning to
generate faithful reasoning steps. RR (He et al. 2022) and KD-CoT Wang et al. (2023b) further retrieve relevant knowledge from KGs to produce faithful reasoning plans for LLMS.
Knowledge Graph Question Answering (KGQA). Conventional embedding baasddddnn---dddddd methods rep- resent the entities and relations in embedding space and design special model architectures (c.g., Key- memory networks, sequential models, and graph neural networks) to reason answers
2

---

Published as a conference paper at ICLR 2024
Knowledge Graphs (K6s)
USA
Presike
Relation Paths 2
Q 6)
Retrieval
Reasoning Patis W3
gradaatte frem located 13 preseesioo verkiin city.ot
Planning Optimization
Didsa
Didea
lors.is
gradoste. frem
Sccanton
Universty of Delawage
civy.af USA
lccated
USA
Please generats helpful relation paths for ondwering the question.
Prompt:
Pa(ala)
Prompt: Please onswer the question based on the reasoning paths and exploin why.
Planning
Reasoning
Question: What the nationality
Large Language Models (LLMs)
Answer: drswer
USA, becoude
Pelala, 2,0)
Inference
Instraction Finctuning
Reasoring Optimization.
The overall framework of reasoning on graphs (RoG), 1) given a question, we first prompt LLMs to generate several relation paths that are grounded by KGs as plans. 2) Then, we retrieve reasoning paths from KGs using the plans. 3) Finally, we conduct faithful reasoning based on the retrieved reasoning paths and generate answers with interpretable explanations. The orange and red rectangles denote the entities mentioned in the question and answer, respectively.
Figure 2:
Miller al. 2016 He al. 2021 Yasunaga al. 202T). To integrate LLMs for KGQA, retrieval- augmented methods aim to retrieve the relative facts from the KGs to improve the reasoning per- formance (Li al. 2023 Karpukhin al.) 2020). Recently, UniKGQA (hang et al. (022) which unifies the graph retrieval and reasoning process into single model with LLMs, achieves STOA per- formance. Semantic parsing methods convert the question into structural query (e.g.. SPARQL) by LLMs, which can be executed by query engine to reason the answers KGs (Sun al. 2020 Lan Jiang, 2020). However, these methods heavily rely on the quality of generated queries. the query not executable, no answers will be generated. DECAF Yuu et al. 2022a) combines semantic parsing and LLMs reasoning to jointly generate answers, which also reach salient performance on KGQA tasks.
3 PRELIMINARY
Knowledge Graphs (KGs) contain abundant factual knowledge in the form of a set of triples: G = ((e,r, e &,r E R}, where E and R denote the set of entities and relations, respectively.
Relation Paths are sequence of relations: 2 {r1, r,,,,,,.,, where r; E R denotes the i-th relation in the path and / denotes the length of the path.
Reasoning Paths are the instances of a relation path in KGs: w; = ep mi el
et marry to > father of, reasoning path instance could be: Wa Alice marry_Lo Bob father.of, Charlie, which denotes "Alice" is married to "Bob" and "Bob" is the father of "Charlie".
where E & denotes the i-th entity and r; denotes the i-th relation in the relation path z. Example 1. Given relation path:
Knowledge Graph Question Answering (KGQA) is a typical reasoning task based on KGs. Given a natural language question g and a KG G. the task aims to design function f to predict answers E A, based on knowledge from G, i.e., Jiang et al. 2022), we assume the entities e, T mentioned in g and answers a A, are labeled and linked to the corresponding entities in G. i... Ta. Ag E.
f(g. G). Following previous works (Sun et al. 2019
4 APPROACH
In this section, we introduce our method: reasoning on graphs (RoG), which contains two compo- nents: 1) planning module that generates relation paths grounded by KGs faithful plans; 2)
3

---

Published as a conference paper at ICLR 2024
retrieval- module that first retrieves valid reasoning paths from KGs according to the plans, then conducts faithful reasoning based on retrieved reasoning paths and generates answers with interpretable explanations. The overall framework of RoG is illustrated in Figure 2
4.1 REASONING ON GRAPHS: BHANINGGRRETREEVLLRRRBAAEE
Recently, many techniques have been explored to improve the reasoning ability of LLMs by plan- ning, which first prompts LLMs generate reasoning plan and then conduct reasoning based on [Wang et al. 2023c). However, LLMs are known for having hallucination issues, which are prone to generating incorrect plans and leading to wrong answers (Ji et al. 2023). To address this issue, present a novel by KGs and then retrieves faithful reasoning paths for LLM reasoning.
framework, which makes the reasoning plans grounded
Relation paths, which capture semantic relations between entities, have been utilized in many rea- soning tasks on KGs (Wang et al. 202T Xu et al. 2022). Moreover, compared the dynamically updated entities, the relations in KGs are more stable (Wang et al.) (023a). By using relation paths, we can always retrieve the latest knowledge from Gs for reasoning. Therefore, relation paths can serve as faithful plans for reasoning the answer to KGQA task.
Example 2. Given a question "Who the child of Alice", we can generate a relation path as the plan: 2 = marry_te + father_of This relation path expresses the plan: 1) find the person that "Alice" is married to; 2) find the child of that person. We can execute the plan (relation path) by retrieving reasoning path from KGs as: w, Alice mazry-so, Bob father,of, Charlie. Finally, we can answer the question based on the reasoning path, which is "Charlie".
By treating relation paths as plans, we can make sure the plans are grounded by KGs, which enables LLMs to conduct faithful and interpretable reasoning on graphs. In nutshell, we formulate our RoG as an optimization problem that aims to maximize the probability of reasoning the answer from a knowledge graph G w.r.t the question y by generating relation paths z as the plan:
(ala, 9) Σ
(=ll)))
ZEZ
where 0 denotes the parameters of I.LMs, denotes the relation paths (plans) generated by LLMs, and 2 denotes the set of possible relation paths. The latter term Po(=14) is the probability of gen- erating a faithful relation path = grounded by KG, given the question q, which is realized by the planning module. The former term Pa(alg, q, 2, G) is the probability of reasoning answer given the question q, relation path z, and KG G. which is computed by the retrieval-reasooing module.
4.2 OPTIMIZATION FRAMEWORK
Despite the advantage of generating relation paths as plans, the LLMs have zero knowledge of the relations contained in KGs. Therefore, LLMs cannot directly generate relation paths grounded by KGs as faithful plans. Moreover, LLMs might not understand the reasoning paths correctly and conduct reasoning based on them. To address these issues, we design two instruction tuning tasks: 1) planning optimization, which distills the knowledge from KGs into LLMs generate faithful relation paths as plans; 2) retrieval-reasoning optimization, which enables LLMs to reason based on the retrieved reasoning paths.
The objective function in equation D can be optimized by maximizing the evidence lower bound (ELBO) (Jordan al.) [999), which is formulated as
(2) where Q(2) denotes the posterior distribution of faithful relation paths grounded by KGs. The
log P(alg, 9) 2 Re-qqe) Pa(alg, 9) - (Q())]
latter term minimizes the KI. divergence between the posterior and the prior, which encourages LLMs to generate faithful relation paths (planning optimization). The former term maximizes the expectation that
module generates correct answers based on the relation paths and KGs gretrival-reasooiing optimization).
Planning optimization. In planning optimization, we aim to distill the knowledge from KGs into LLMs to generate faithful relation paths plans. This can be achieved by minimizing the KL divergence with the posterior distribution of faithful relation paths Q(2), which can be approximated by the valid relation paths in KGs.
4

---

Published as a conference paper at ICLR 2024
Given question q and answer a, could find the path instances wz(Cg, Ca) Cq 3 Ea connecting Eg and ea in KGs. The corresponding relation path z {ri, r2..... ri} can be considered valid and serve a faithful plan for answering the question The posterior distribution (=) can be formally approximated as
e1
"3,
Aw Ca) Eg,
Q(2) ~ Q22a,
3 0lels,
(3)
where assume uniform distribution over all valid relation paths 2, and Bw2 Ca) E 9 denote the existence of path instance connecting the question en and answer entities in G. Therefore, the KL divergence can be calculated
1
Cplan = (Q
DKL
log Po(lg)) (4)
Z+
ZEZ
where we use the shortest paths z" C Z between eq and Ea in KGs supervision signals ZZang
et al. 2022). The detailed derivation can be found in Appendix [..] By optimizing the equa-
tion 4 maximize the probability of LLMs generating faithful relation paths through distilling the knowledge from KGs.
Retrieval-reasoning optimization. In retrieval-reusoning optimization, we aim to enable LLMs to conduct reasoning based on the retrieved reasoning paths. For the retrieval-reasooing module, we follow the FiD framework (Izacard & Grave [202 (iighh al. 2021). which allows reasoning multiple retrieved reasoning path:" formulated as Po(alg, 2,9)
II (ala,, 2,
sEZ
By approximating the expectation with sampled plans Z S Z', the objective function of rea- soning optimization can be written
Creason = E. ((eeo(el... log Po(alg, 2, -
Σ z
log Po , 9) = log Po Zi. G).
(6)
This maximizes the probability of LLMs generating correct answers based on the retrieved reasoning paths.
The final objective function of RoG is the combination of the planning optimization and retrieval- reasoning optimization, which be formulated
L = log (a 2 9)
+
log Po(2lg)
Z
ZEZ
Retrieval reasoning
Planning
that adopt the same LLM for both planning and reasoning, which are jointly trained on two instruction-tunit -unning tasks, i.e., (planning and retrieval-reassonnng) We will discuss the implementation details of these two tasks in the following subsections.
From equation 7
4.3 PLANNING MODULE
The planning module aims generate faithful relation paths as plans for answering the question. To utilize the cerruction-flllwwini ability of L.MMs (Wei al. (202T) we design simple instruction template that prompts LLMs to generate relation paths:
Please generate a valid relation path that can he helpful for answering the following question: <Question>
where <Questi on> indicates the question q. The question together with the instruction template is fed into LLMs to generate the relation paths, which are structurally formatted as a sentence:
Thh FiD framework assumes each Z contributes independently, where the probability Po(alg, 2.9) he approximated the product of each (o 2, g).
5

---

be found in Published as a conference paper at ICLR 2024
2 == <PATH> T1 <SEP> T2 <SEP> <SEP> 7, </PATH>
where <PATH>, <SEP>, </P </PATH> are special tokens indicating the start, separator, and end of the relation path, respectively
Therefore, the optimization of Eplan can be achieved as
arg max
Σ log Po(zlg)
Σ log II Po(r./ren.))
(8)
Z+
Z+
ZEZ-
ZEZ
where Pa(z1g) denotes the prior distribution of generating faithful relation path 2, and Po(rs/rei,g) denotes the probability of each token in 2 generated by LLMs.
4.4
MODULE
Retrieval. Given a question and relation path plan the retrieval module aims to retrieve the reasoning paths w, from KG The retrieval process can conducted by finding paths in that start from the question entities eq and follow the relation paths z, formulated as
(9) We adopt a constrained breadth-fire search to retrieve the reasoning paths w, from KGs. In exper- iments, all retrieved paths are used for reasoning. The detailed retrieval algorithm Appendix A.3
W3 = (eg e.) (ex,),
eq _1 -3 I Eas: W, (eq, e.) ) E g}.
utilize the retrieved reasoning paths and directly get the answers with majority voting. The retrieved reasoning paths could be noisy and irrelevant to the questions, which leads to incorrect answers (He et 2021 Zhang al. 2022). Therefore, we propose reasoning module to explore the ability of LLMs to identily the important reasoning paths and answer the questions based on them.
Despite
The reasoning module takes the question and set of reasoning paths W, to generate answers a. Similarly, we design reasoning instruction prompt to guide LLMs to conduct reasoning based on the retrieved reasoning paths W.. The W, are also formatted as a series of structural sentences. The detailed prompt can be found in Appendix
Reasoning.
The optimization of Lremon can be written as
|al II Po (ett,,ten w2),
arg max Polalq
= log Σ Σ
(10)
=EZ W,EW, ==1
where (alg, Zx, 9) denotes probability of reasoning the correct answer a based on K relation paths Zk, and to denote the tokens of answers
EXPERIMENT
Can RoG achieve state-of-the-aar performance on the KGQA tasks? RQ2: Can the planning module of RoG be inte- grated with other LLMs to improve their performance? RQ3: and generate interpretable reasoning results?
In experiments, aim to answer the following research questions: RQ1:
Can RoG conduct faithful reasoning
5.1 EXPERIMENT SETTINGS
Datasets. We evaluate the reasoning ability of RoG benchmark KGQA datasets: WebQues- tionSP (WebQSP) (Yih et al. 2016) and Complex WebQuestions (CWQ) (Talmor & Berant 2018), which contain up 4-hop questions. Freebase (Bollacker al. 2008 is the background knowledge graph for both datasets, which contains around 88 million entities, 20 thousand relations, and 126 million triples. The details of the datasets are described in Appendix A.4
'The relation name could be split into multiple tokens. For example, "born_in" could be split into "born" and "_i "_in" by tokenizer. In this way, we could fully utilize the semantic information in relation names and generalize to different KGs.

---

Published as a conference paper at ICLR 2024
Table 1: Performance comparison with different baselines on the two KGQA datasets.
Type
Methods
WebQSP
CWQ
Hits@
F1
Hits@ I
FI
KV-Mem MMileer et al
2016
46.7
34.5
18.4
15.7
EmbedKGQAA NSM (He et all 2022
2020
66.6
45.9
Embedding
68.7
62.8
47.6
42.4
Transfo
2021
71.4
48.6
KGT5 KGT5SSaeni
Saxeni et m
56.
36.5
GraftNet
60.4
36.8
Retrieval
PullNet Sumrer mi 2019
68.1
45.9
SR+NSM Zhhing
2022
68.9
64.1
50.2
47.1
SR+NSM-EZE (Zhann ot al. 2022
69.5
64.1
49,3
46.3
SPAROL Sun
2020
31.6
Semantic Parsing
Q3G (Lah & Janee k01u
73.0
73.8
36.9
37.4
ArcaneiA (GU 2072
75.3
RnG-KRQA (YA.RRAAAATTTee... of mi +0.22
76.2
Flan-T5-xl Chune
2022
14.7
Alpaca-7B Taorr ot mi A024
51.8
27.4
LLMs
LLaMA2-
Touvroa
2023
34.6
CharGPT
66.8
39.9
ChatGPT+CaT
75.6
48.9
KD-CoT (Wane et al. 20236
68.6
52.5
53.7
LLMs+KGs
UniKGQA tning DECAF (DPR4FID-3B) cu al. 2022a
77.2
72.2
51.2
49.1
82.1
78.8
RoG
85.7
70.8
62.6
56.2
Baselines. We compare RoG with 21 baselines grouping into 5 categories: 1) Embedding- based methods, 2) Retrieval-augmented methods, 3) Semantic parsing methods, 4) LLMs, and 5)
LLMs+KGs methods. The details of each baseline are described in Appendix
Evaluation Metries. Following previous works, we use Hits@ I and Fl as the evaluation metries. Hits@ measures the proportion of questions whose top-1 predicted answer is correct. Since question may correspond to multiple answers, FI considers the coverage of all answers, which balances the precision and recall of the predicted answers.
Implementations. For RoG, we use C.LMAA--hht-7BB (Touvron al., 2023) as the LLM backbone, which is instruction finetuned on the training split of WebQSP and CWQ well as Freehase for 3 epochs. We generate the top-3 relation paths using beam-search for each question. Since UniKGQA Jiang et al., 2022) and DECAF (Yu et al. 2022a) are state-of-the-an methods, we directly refer their results and those of the other baselines reported in their papers for comparisons. For LLMs, we use zero-shot prompting to conduct KGQA. The detailed settings are described in Appendix A.6
5.2 RQI: KGQA PERFORMANCE COMPARISON
Main Results. In this section, we compare RoG with other baselines on KGQA tasks. The results are shown in Table [ Our method achieves the best performance on both datasets across most metrics. Specifically, compared to the SOTA method DECAF (Yu al.] (202aa) WebQSP, our method improves Hits@ I by 4.4%. On the CWQ dataset, which is more challenging due to multi- hop questions, method improves both Hits @ and F1 by 22.3% and 14.4% against the SOTA model UniKGQA (Jiang et al. 2022). These results demonstrate the superior reasoning ability of our method in KGQA.
Among other methods, retrieval-augmenner approaches outperform conventional embedding-based methods by retrieving relevant subgraphs from KGs, which reduces reasoning complexity. Fur- thermore, SR+NSM and SR+NSM+E2E adopt relation paths- paths-based retrieval which achieves better performance, highlighting the importance of relation paths. Semantic parsing methods perform bet- ter than retrieval methods on WebQSP but worse on CWQ due to the complexity of generating logical queries for complex questions in CWQ. Although L..Ms-based methods achieve comparable performance, they limited by hallucinations and lack of knowledge as shown in Section 5.4 The LLMs+KGs methods achieve the second-bes performance, which demonstrates the effectiveness of unifying KGs and LLMs for reasoning.
Ablation Study. We conduct an ablation study to analyze the effectiveness of the planning module and reasoning module in method (RoG). We compare four variants: 1) w/o planning, where we remove the planning module and perform reasoning without retrieved reasoning paths; 2) w/o reasoning, where we remove the reasoning module and use all answers from retrieved reasoning
7

---

Published as a conference paper at ICLR 2024
# Retrieved Reasoning Puths Retrieval-Precisoon
Retrieval-Roeall
Reasoning-F1
Retrivell Reusning Paths
WebQSP
Retriveed Rasoning Paths
CwQ
40
125
30
00
Coverig
100
60
Coverage
75
20
60
50-
10-
40
25
Top-K relation paths
Top-K relation paths
Figure 3: Faithfulness of top-K generated relation paths. Green bars denote the average number of retrieved reasoning paths, solid lines denote the answer coverage of the retrieved paths, and dashed line denote the answer coverage of the reasoning module based on the retrieved reasoning paths.
paths as results; 3) w/ random plans, where we randomly retrieve reasoning paths from KGs and feed them into the reasoning module; 4) w/ vote reasoning, where we adopt the majority voting to select t answers from retrieved reasoning paths. The results are shown in Table 2
From the results, is evident that without planning module, our method degenerates to conventional LLMs that solely rely on questions as input, suffering from the lack of knowledge issue. Although removing the reasoning module leads to high recall due increased number of answers, precision drops significantly because of noise in retrieved paths. This demonstrates the ef- fectiveness of the reasoning module in identifying important reasoning paths and filtering out noise. Furthermore, using random plans achieves worse performance than removing the planning module, highlighting the importance of planning module who generates faithful reasoning plans. Using a simple majority vote reasoning can improve the results which also demonstrate the necessity of reasoning module.
Table 2: Ablation studies of RoG.
WehQSP
CWQ
Method
Precision
Recall
F1
Precision
Recall
F1
RoG
74.77
75.84
70.81
57.69
58.19
56.17
RoG w/o planning
57.26
49.69
35.35
33.76
RoG w/o reasoning
46.90
79.85
49.56
18.88
67.89
22.26
RoG random plans
38.66
38.31
35,24
38.99
39.29
37.64
RoC vote reasening 54,80
60.44
47.96
22.92
47.98
26.52
5.3 RQ2: PLUG-AND- PLAY RoG PLANNING MODULE
In this section, we evaluate the effectiveness of integrating the planning module of RoG with different LLMs during inference to improve their performance. Specifically, we first adopt the planning module of RoG to generate re- lation paths and feed the retrieved reasoning paths as context into different LLMs for rea- soning. The results are presented in Table To account for the fact that it is difficult to extract the number of answers from LLM's output. We only report the Hits and Recall metrics.
Table 3: Effects of integrating the planning mod-
ule RoG with different LLMs for reasoning.
Merhods
WesQSP
CWQ
Hito@
Recall
Hits
Recall
ChaiGPT
66.77
49.27
39.90)
35.07
ChaGGPT RoG Planning
81.51
71.60
52.68
48.51
Alpaca 7B Alpaca-7B RoG Planning
51.78
33.65
27.44
23.62
56.16
44.04
LLaMA2-Chat-7B
64.37
14.61
34.60
29.91
LLaMA2-Chat 7 RoG Planning
74.20
$6.16
56.41
$1.99
Flan-13xx
30.95
17.08
14.69
12.25
Flan-T5-xl + BoG Planning
67,87
44.93
37.81
32,57
From the results, we can notice that the performance of all LLMs is substantially improved by integrating the planning module of RoG. Specifically, the Hits@ 1 of ChatGPT, Alpaca, LLaMA2, and Flan-T5 are improved by 8.5%, 15.3%, and 119.3%, respectively. This demonstrates that the planning module of RoG can be seamlessly integrated with other LLMs to improve their performance without retraining.
5.4 RQ3: FAITHFUL REASONING AND INTERPRETABLE RESULTS
Quantitative Results. To evaluate the faithfulness of the relation paths, we illustrate the quantita- tive results in Figure 3 In experiments,
sweep the number of top-K relation paths generated by RoG. From results, we can see that the number of retrieved reasoning paths increases with K, which also leads to more answers be covered (recall). This demonstrates the faithfulness of the
8

---

Published as a conference paper at ICLR 2024
Table 4: Example of lack of knowledge for ChaIGPT-CoT and interpretable predictions of RoG.
Question
What type of govermment used the countr with Northem District?
Answer
Parliamentary system
ChaGGPT CoT
with a Narthem District, we need specific information. The temm "Northern District' does not specify the of any particulaa country or provide enough context idessity government rype. Could you please provide additional details or clarity the specific country you are referring to?
To determine what type of govemmment is used in
Reasoning Paths
Noethern District location. administrarive divieiiiiiiiinnnn first, level ddivision_
Ismall
government form of government.com countries Parliamentary system
The type of govemmment used the country with Northem District Parliumentary system.
Explanations:
1. Northem District location administraive division level..vel...vii... of Isrnel: The Northem District is part of Israel.
RoG
2. Israel government.Gu form soverament.comttn Patliamentaayy system: Israel has Parliameniary system government.
So, by following the reasoning paths provided, we can conclude that the country with the Norther District, which Israel, Parliancnttry system government
Table 5: Example of the hallucination of ChatGPT-CoT and faithful reasoning of RoG.
Question
Where is the home stadium of the teom who won the 1946 World Series championship'
Answer
Busch Stadium
Step Idenrify the that the 1946 World Series championship. The team that wos World Series championship was
ChaGPT + CoT
Louis Cardinals' home stadium during 1946
Step 2:
Determine the home stadium of the St. Louis Cardinals during that time. The St. Sportsman's is Park.
Therefore. the poesible answer to the question "Where is the home stadium of the team who won the 1946 World Series championship"" is: Sportsman's 's Park.
1946 World Series sports.sports
charpionnships St.
Louis Cardinals
Reasoning Putls
sports.ports team,arena 1916 World Series + sports.sport. Jeam, cla..cpooppppppp...... + St. Louis Cardinals
Busch Stadium
sports.ports team.arena stadium - Roger Dean Stadium
Based the reasoning paths provided, the home stadium the team who won the 1946
World Series championship is Busch Stadium. conclusion is poth:
following
1. 1946 World Series sports.porrs team www.ppommsnssipss--- St. Louis Cardinals sports.sports. www..areaaaaaea...m....aaa
RoG
Busch Stadium
The reasening pash leads us the St. Louis Cardinals as the team that wan the 1916 World Series, and Busch Stadium the stadium associated with the St. Louis Cardinals.. Therefore, Busch Stadium championship.
stadiom
1946 World Series
relation paths by retrieving the answers. However, more retrieved reasoning paths also lead to more noise and retrieval time (shown in Appendix (A.7.) which decreases the precision and makes little contribution to the final results treasoning-fl) Therefore, we set K = 3 in experiments.
Case studies. We also illustrate two case studies in Table 4 and Table 5 In Table 4 we can find that ChatGPT+CoT suffers from the lack of knowledge issue and cannot answer the question. On the contrary, RoG can generate faithful relation paths and retrieve valid reasoning paths from KGs for reasoning. Besides, RoG can provide interpretable explanations based on the reasoning paths. In T we can see that CharGPT+CoT suffers from hallucinations and generates incorrect answers. In contrast, although the retrieved reasoning paths contain noises, the reasoning module can identify the correct reasoning paths and conduct faithful reasoning. These results demonstrate the effectiveness of RoG in conducting faithful reasoning and generating interpretable results. More cases can be found in Appendices A.8 and A.9
CONCLUSION
In this paper, we propose a novel method called reasoning on graphs (RoC) that synergizes LLMs with KGs to conduct faithful and interpretable reasoning. To alleviate the issues of hallucinations ceaauingrrerievvll-ressss
and lack of knowledge, we present to access the latest knowledge while reasoning based on faithful plans on graphs. RoG not only en- hances the reasoning capability of L.LMs by distilling knowledge from KGs through training but also enables seamless integration with any LLMs during inference. Extensive experiments on two bench- mark KGQA datasets demonstrate the superiority of RoG in reasoning ability and interpretability.
framework, which allows LLMs

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This material is based on research partially sponsored by the DARPA Assured Neuro Sym- bolic Learning and Reasoning (ANSR) program under award number FA8750-23-2-1016 and the DARPA Knowledge Management at Scale and Speed (KMASS) program under award number HR001 12220047. This research partly supported by the ARC Future Fellowship FT190100039 to G.H. S. Pan was supported in part by the Australian Research Council (ARC) under grants FT210100097 and DP240101547, and the CSIRO National Science Foundation (US) AI Research Collaboration Program.
ETHICS STATEMENT
Our work is solely dedicated to tackling scientific problems and does not involve any human sub- jects, animals, environmentally sensitive materials. Consequently, we do not anticipate any po- tential ethical risks or conflicts of interest in our study. Our research strives to adhere to the highest standards of scientific integrity and ethical conduct throughout the entire process, guaranteeing the validity and reliability of our findings.
REPRODUCIBILITY STATEMENT
Our model has been meticulously formalized within the main body of the text to ensure clarity and facilitate comprehensive understanding. Additionally, we provide detailed discussions of im- plementation in Appendices A.4 to A.6] encompassing dataset information, baselines, experimental settings, and model configurations. The code and pre-trained model weights have been publicized.
REFERENCES
Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, et al. A multitask, multilingual, multimodal evaluation of chatgpt reasoning. hallucination, and interactivity. arXiv preprint arXiv:2302.04023 2023.
Maciej Besta, Nils Blach, Ales Kubicck, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. arXiv preprint arXiv:2308.. 09687, 2023.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freehase: a collab- oratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247-1250, 2008
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.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, al. Scaling instruction-finetune language mod- els. arXiv preprini arXiv: 14416 2022.
Antonia Creswell and Murray Shanahan. Faithful reasoning using large language models. arXiv preprint arXiv:2208. 2e0.22208.27771 14271, 2022.
Yu Gu and Yu Su. Arcaneqa: Dynamic program induction and contextualized encoding for knowl- edge base question answering. In Proceedings of the 29th International Conference on Computa- tional Linguistics, pp. 7718-1731 2022.
Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. Improving multi-hop knowl- edge base question answering by learning intermediate supervision signals. Proceedings of the 14th ACM international conference web search and data mining, pp. 553-561, 2021.
10

---

Published as a conference paper at ICLR 2024
Hangfeng He, Hongming Zhang, and Dan Roth. Rethinking with retrieval: Faithful large language model inference. arXiv preprint arXiv:2301.00303, 2022.
Ruixin Hong, Hongming Zhang, Hong Zhao, Dong Yu, and Changshui Zhang. Faithful question planning ACL2023, 2023.
answering with monte-carlo planning.
Jie Huang and Kevin Chen-Chuan Chang. Towards reasoning in large language models: A survey. ACI. 2023, 2023.
Gautier Izacard and f'douard Grave. Leveraging passage retrieval with generative models for open domain question answering. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pp. 874-880, 2021.
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12):1-38, 2023.
Jinhao Jiang, Kun Zhou, Xin Zhao, and Ji-Rong Wen. Unikgqa: Unified retrieval and reasoning for solving multi-hop question answering over knowledge graph. In The Eleventh International Conference on Learning Representations, 2022.
Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, Yaliang Li, and Ji-Rong Wen. Reasoninglm: Enabling structural subgraph reasoning pre-trained language models for question answering over knowl- edge graph. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 3721-3735 2023.
Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, Yang Song, Chen Zhu, Hengshu Zhu, and Ji-Rong Wen. Kg-agent: An efficient autonomous agent framework for complex reasoning over knowl- edge graph. arXiv preprint arXiv:240.111163, 2024.
Ming Jin, Shiyu Wang. Lintao Ma, Zhixuan Chu, James Y Zhang, Xiaoming Shi, Pin-Yu Chen, Yuxuan Liang, Yuan-Fang Li, Shirui Pan, and Qingsong Wen. Time-llm: Time series forecasting by reprogramming large language models. In International Conference on Learning Representa- tions, 2024a.
Ming Jin, Yifan Zhang. Wei Chen, Kexin Zhang, Yuxuan Liang, Bin Yang, Jindong Wang, Shirui Pan, and Qingsong Wen. Position paper: What can large language models tell us about time series analysis. arXiv preprint arXiv:2402.027713, 2024b.
Michael Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence K Saul. An introduction to variational methods for graphical models. Machine learning, 18:133,, 1999.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 6769-6781, 2020.
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. In The Eleventh International Conference on Learning Representations, 2022.
Yunshi Lan and Jing Jiang. Query graph generation for answering multi-hop complex questions from knowledge bases. Association for Computational Linguistics, 2020.
Shiyang Li, Yifan Gao, Haoming Jiang, Qingyu Yin, Zheng Li, Xifeng Yan, Chao Zhang, and Bing Yin. Graph reasoning for question answering with triplet retrieval. In Findings of the Association for Computational Linguistics: ACL 2023, 2023.
Ke Liang. Lingyuan Meng, Meng Liu, Yue Liu, Wenxuan Tu, Siwei Wang, Sihang Zhou, Xinwang Liu, and Fuchun Sun. Reasoning over different types of knowledge graphs: Static, temporal and multi-modal. arXiv preprint arXiv:2212.057677 2022.

---

Published as a conference paper at ICLR 2024
Ke Liang, Yue Liu, Sihang Zhou, Wenxuan Tu, Yi Wen, Xihong Yang, Xiangjun Dong, and Xin- wang Liu. Knowledge graph contrastive learning based on relation-symmetricn structure. IEEE Transactions on Knowledge and Data Engineering, pp. 1-12, 2023. doi: 10.1109/KDE.2023.. 3282989.
Yixin Liu, Kaize Ding, Qinghua Lu, Fuyi Li, Leo Yu Zhang, and Shirui Pan. Towards self- interpretable graph-level anomaly detection. Advances in Neural Information Processing Systems, 36, 2023a.
Yixin Liu, Kaize Ding, Jianling Wang, Vincent Lee, Huan Liu, and Shirui Pan. Learning strong graph neural networks with weak information. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2023b.
Linhao Luo, Jiaxin Ju, Bo Xiong, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Chatrule: Mining logical rules with large language models for knowledge graph reasoning, arXiv preprint arXiv:2309.011 03588 2023a.
Linhao Luo, Yunn-Fang Li, Gholamreza Haffari, and Shirui Pan. Normalizing flow-based neural process for few-shot knowledge graph completion. In The 46th International ACM SIGIR Con- ference on Research and Development in Information Retrieval, 2023b.
Alexander Miller, Adam Fisch, Jesse Dodge, Amir- 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, pp. 1400-1409, 2016.
Shirui Pan, Yizhen Zheng, and Yixin Liu. Integrating graphs with large language models: Methods and prospects. arXiv preprint arXiv:2310.05499, 2023.
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 (TKDE), 2024.
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, pp. 4498-4507, 2020.
Apoorv Saxena, Adrian Kochsiek, and Rainer Gemulla. Sequence-to-sequenee knowledge graph completion and question answering. In Proceedings of the 60th Annual Meeting the Association for Computational I Linguisties (Volume 1: Long Pupers), pp. 2814-2822. 2022.
Jiaxin Shi, Shulin Cao, Lei Hou, Juanzi Li, and Hanwang Zhang. Transferet: An effective and transparent framework for multi-hop question answering over relation graph. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 4149-4158, 2021.
Devendra Singh, Siva Reddy, Will Hamilton, Chris Dyer, and Dani Yogatama. End-to-end training of molti-dd reader and retriever for open- open-domain question answering. Advances Neural Information Processing Systems, 01225968-25988 2021.
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 Proceedings of the 2018 Conference Empirical Methods in Natural Language Pro- cessing, pp. 4231 -2422, 2018
Haitian Sun, Tania Bedrax- -eiss, and William Cohen. Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (FMNLL--JCNIP)), pp. 2380-2390, 2019.
Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel Ni, Heung- Yeung Shum, and Jian Guo. Think-on-grae -raphh Deep and responsible reasoning of large language model on knowledge graph. In The Twelfth International Conference on Learning Rep- resentations, 2024. URL CRL.ttts:: /tpp//pprreeeee revi net www.nee//oormmmidmniiett p
12

---

Published as a conference paper at ICLR 2024
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, pp. 8952-888 02298999,.40 2020.
Oyvind Tafjord. Bhavana Dalvi, and Peter Clark. Entailer: Answering questions with faithful and truthful chains of reasoning. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 2078 2093, 2022.
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: Human Language Technologies, Volume I (Long Papers), pp. 641- 651, 2018.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori В Hashimoto. Stanford alpaca: instruction-followin llama model. st anford alpaca, 2023.
httpp:://ithhei
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.088 00082207, 2023.
Hongwei Wang. Hongyu Ren, and Jure Leskovee. Relational message passing for knowledge graph completion. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1697-1707, 2021.
Jiapu Wang, Boyue Wang, Meikang Qiu, Shirui Pan, Bo Xiong, Heng Liu, Linhao Luo, Tengfei Liu, Yongli Hu, Baocai Yin, et al. A survey temporal knowledge graph completion: Taxonomy, progress, and prospects. arXiv preprint arXiv:2308. 02455, 2023a.
Keheng Wang, Feiyu Duan, Sirui Wang, Peiguang Li, Yunsen Xian, Chuantao Yin, Wenge Rong, and Zhang Xiong. Knowledge-driven cot: Exploring faithful reasoning in Ilms for knowledge- intensive question answering. arXiv preprint arXiv:2308. /3299, 2023b.
Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka- Wei Lee, and Ee-Peng Lim. Plan-and-solve prompting: Improving zero-shot ofain-of-though reasoning by large language models. arXiv preprint arXiv:2305.0 04091, 2023c.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoc V Le. Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2022.
Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, An- drew M Dai, and Quoe V Le. Finetuned language models are zero-shot learners. In International Conference on Learning Representations, 2021.
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.
Xiaohan Xu, Peng Zhang, Yongquan He, Chengpeng Chao, and Chaoyang Yan. Subgraph neigh- boring relations infomax for inductive link prediction on knowledge graphs. In Proceedings of the Thirty-Firss International Joint Conference on Artificial Intelligence, 2022.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305. 10601, 2023.
13

---

Published as a conference paper at ICLR 2024
Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. Qa-gnn: Reasoning with language models and knowledge graphs for question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Techmologies, pp. 535-546, 2021.
Xi Ye, Semih Yavuz, Kazuma Hashimoto, Yingbo Zhou, and Caiming Xiong. Rng-kbqa: Generation augmented iterative ranking for knowledge base question answering. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp- 2022.
Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming- 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 (Volune 2: Short Papers), pp. 201-206, 2016.
Donghan Yu, Sheng Zhang, Patrick Ng. Henghui Zhu, Alexander Hanbo Li, Jun Wang, Yiqun Hu, William Yang Wang. Zhiguo Wang. and Bing Xiang. Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases. In The Eleventh International Conference on Learning Representations, 2022a.
Donghan Yu, Chenguang Zhu, Yuwei Fang, Wenhao Yu, Shuohang Wang, Yichong Xu, Xiang Ren, Yiming Yang, and Michael Zeng. Kg-fid: Infusing knowledge graph in fusion-in-desn -n-dodrr for open-domain question answering. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 4961-4974, 2022b.
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. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5773-5784, 2022.
Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christopher D Manning, and Jure Leskovec. Greaselm: Graph reasoning enhanced language models. In Inter- national conference on learning representattinss 2021.
Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander Smola, and Le Song. Variational reasoning for question answering with knowledge graph. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
Zicheng Zhao, Linhao Luo, Shirui Pan, Quoe Viet Hung Nguyen, and Chen Gong. Towards few- shot inductive link prediction on knowledge graphs: A relational anonymous walk-guided neural process approach. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 515-532, 2023.
Xin Zheng, Miao Zhang, Chunyang Chen, Chaojie Li, Chuan Zhou, and Shirui Pan. Multi-relational graph neural architecture search with fine-grained message passing. In 2022 IEEE International Conference on Data Mining (ICDM). pp. 783-792. IEEE, 2022a.
Xin Zheng, Yixin Liu, Zhifeng Bao, Meng Fang, Xia Hu, Alan Wee-Chung Liew, and Shirui Pan. Towards data-centric graph machine learning: Review and outlook. arXiv preprint arXiv:2309. 10979, 2023a.
Xin Zheng. Miao Zhang, Chunyang Chen, Soheila Molaei, Chuan Zhou, and Shirui Pan. Gnneval- uator: Evaluating gnn performance on unseen graphs without labels. In Advances in Neural Information Processing Systems (NeurIPS), 2023b.
Xin Zheng, Miao Zhang, Chunyang Chen, Quoe Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. In Advances in Neural Information Processing Systems (NeurIPS), 2023c.
Yizhen Zheng, Shirui Pan, Vincent Lee, Yu Zheng, and Philip S Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. Advances in Neural Information Processing Systems, 1118000918220 2022b.
14

---

Published as a conference paper at ICLR 2024
Yizhen Zheng, Huan Yee Koh, Jiaxin Ju, Anh TN Nguyen, Lauren T May, Geoffrey I Webb, and Shirui Pan. Large language models for scientific synthesis, inference and explanation. arXiv preprint ar arXiv:2310.079884 2023d.
Yizhen Zheng, He Zhang, Vincent Lee, Yu Zheng, Xiao Wang, and Shirui Pan. Finding the missing- half: Graph complementary learning for homophily and heterophily- prrnne prone graphs. Inter- national Conference Machine Learning, 2023e.
A APPENDIX
A.I DETAILED DERIVATION OF THE PLANNING MODULE
In this section, provide detailed derivation of the planning module. By approximating the Q(2) with Q(2la, q, 9), the KL. divergence can be calculated as
Cptan DkL(Q())[IP((sl))
DRL (Ql q, (oll)))
_=-Q(()), log Q(=la, 9) log Po(z)a)).
(11)
-Ex=Q(:)a...)) log Pa (=(2)) + CONST.
where the expectations cannot be computed exactly because of the large number of valid relation paths 2, approximate it by using the shortest paths 2 2 between Eg and in KGs (Zhang et al. 2022). This can be formulated as
Cplan
Σ
Q(zla, log Po(z)a) CONST.
(12)
Based on equation 3 by assuming uniform distribution over the of shortest paths Z", we can rewrite the equation as
Cplan
log (zlg) + CONST,
(13)
where the CONST is omitted in the final optimization since it makes no contributions the loss.
A.2
DETAILED RELATED WORK
A.2.1
LLM REASONING PROMPT
Many studies have been proposed to harness the reasoning ability of LLMS to handle complex tasks
through prompting Wei et al. 2022; Wang et al. 2022 Yao et al. [003] Besta et al. 2023 Pan ct al.]
2023
Zheng et al. 2023d Jin al. 2024a b). Chain-of- -fhouught (Wei al. 2022) enables LLMs
to generate a reasoning chain that could be helpful to reasoning. Tree of thoughts Yaao et al. 2023)
expands the reasoning chain to tree structure explore more reasoning paths. Graph of thoughts (Besta et al. 2023) further models the reasoning chain as graph with an aggregation operation to synergize the reasoning paths. Plan-and-solve (Wang et al. 2023c) prompts LLMs generate plan and execute based on it. DecomP (He et al.) 2021) prompts LLMs to decompose the reasoning task into a series of sub-tasks and solve them step by step. However, the problem of hallucinations and lack of knowledge affect the faithfulness of the reasoning. ReACT (Yao et al. (022) treats LLMs as agents, which interact with the environment to get the latest knowledge for reasoning. To explore faithful reasoning, Entailer (Tafjord et al.] 2022) introduces a verifier to validate the reasoning steps generated by LLMs. Creswell & Shanahan (2022) present a framework including two LLMs that are used for selecting and generating reasoning steps, respectively. FAME (Hong al.] (023) introduces the Monte-CCrlle planning to generate faithful reasoning steps. RR (He et al.) (022) and KD-CoT Wang et al. (2023b) aim retrieve relevant knowledge from KGs to produce faithful reasoning plans for LLMs. Think-on- GnaGraph (Sun et al.] (024) and KG-Agent (Jiang et al.) 2024) treat LLMs agents interact with KGs via prompting to get the latest knowledge for reasoning.
15

---

Published as a conference paper at ICLR 2024
A.2.2 KNOWLEDGE GRAPH QUESTION ANSWERING
Knowledge graphs contain abundant factual knowledge in structured format, which has attracted
great attention from researchers (Zheng al. 2022a 2023a Pan et al. 2023 Liang et al.) )023).
Knowledge graph reasoning aims to derive new insights based on the existing graph structure and
facts (Liang al. 2022 Wang al. 2023a; Luo et al. 2023b Zhao et al.) 2023). Graph neural networks that effectively capture the structure information have also been widely used in KG rea- soning Zheng et al./ 2022b) 2023ebbec Liu et al. (2023b a). As typical reasoning task, knowledge graph question answering (KGQA) aims to obtain answers based on knowledge from KGs, which can be generally divided into three categories: 1) embedding- -based methods, 2) retrieval -augeettd methods, and 3) semantic parsing methods.
Embeedding-basee based methods model the entities and relations in embedding space and design special model architectures to reason answers. KV-Mem (Miller et al.] 2016) adopts Key- Vaaya memory network to store triples for reasoning. EmbedK (Saxena et al. 2020) and NSM (He et al.) 2021) utilize the sequential model to mimic the multi-hop reasoning process. QA-GNN (Yasunaga) ct al. 2021) and Greaselm (Zhang et al. 2021) further adopt the graph neural network to capture the graph structure for reasoning. However, these methods need to design different model architectures, which are not flexible and generalizable.
Reureeee methods aims to retrieve the relative facts from the KGs to improve the reasoning performance. Early works adopt the page rank or random walk algorithm to retrieve subgraphs from KGs for reasoning (Sun et al., 2018 2019). However, they ignore the semantic information in questions and lead to noisy retrieval results. Zhang et al.] (2022) proposes a relation paths-based subgraph retrieval, resulting a better retrieval and QA performance. Other lines of studies retrieving triples from KGs via BM25 (Li et al. 2023) or DPR (Karpukhin et al. 2020 Yu al. 2022b) improve the performance of LLMs. They discard the structure information in KGs which leads to suboptimal results. Recently, UniKGQA (Jiang et al.) (002) unifies the graph retrieval and reasoning process into a single model with LLMs, which achieves state-of-the-a performance on KGQA tasks.
Semantic parsing methods parse the question into a structural query (e.g.. SPARQL) which can be
executed by query engine get answers (Sun et al.) 2020 Lan & Jiang 2020). ArcaneQA (Gu & Sui, 2022) dynamically generates the query based on results from previous steps. RuG-KBQA (Ye al. (022) first enumerate all possible queries and then rank them to get the final output. These methods heavily rely on the quality of generated queries. If the query is not executable, no answers will be generated. DECAF (Yu et al.] (2022a) combines semantic parsing and LLMs reasoning to jointly generate answers, which also reach salient performance on KGQA tasks.
A.3 RETRIEVAL ALGORITHM
Given a question q and a relation path as plan 2, we adopt a constrained breadth-first search to retrieve the reasoning paths. The pseudocode code is presented in Algorithm [
We first initialize a queue of current reasoning paths Q with the entities in the question T, (line 3-5). Then, we iteratively expand each reasoning path in by adding the triples that are connected to the entities in the queue following the relation in relation path (line 11-1). The reasoning path is expanded until the length is equal to the length of the relation path. The expanded reasoning path is added to the set We as the final results (line 8-10).
A.4 DATASETS
We adopt two benchmark KGQA datasets: WebQuestionSP ( Yih et al. 2016) and Com- plex WebQuestions (CWQF) Talmor& & Berant, 2018) in this work. We follow previous works (Sun) et al. 2018 Jiang et al., 2022) ) to use the same train and test splits for fair comparison. The statistic of the datasets are given Table 6 The statistics of the answer numbers and reasoning hops are presented in Table 7 and Table g respectively.
https://ww.tau-nni/
16

---

Published as a conference paper at ICLR 2024
Algorithm 1: Retrieve reasoning paths based on relation paths
Input: Question 9, relation path fri, ......,,. .r).. KG g.
Output: Reasoning paths W..
W= 0:
Q
Queue(:
foreach ey E Tg do Qaappend((e,: I)); Initialize queue with question entities.
end
while
Q + 9 do (s, wz) + p.pop)) if len((w:) len(=) then W app
10
end
11
if' (en(w>)) len(2) then
12
r +- 2 <len(ws w- + 1]: // Get relation for next step.
foreach (s, r t) E 9 do
14
r' then
w append ()); Expand the reasoning path. O Lappend((t,)) w());
16
17
end
18
end
end
end
21 return Wg.;
Table 6: Statistics of datasets.
Datasets
#Train
#Test
Max #hop
WebQSP
2,826 CWQ 27,639
1,628
2
3,531
4
Table 7: Statistics of the number of answers for questions in WebQSP and CWQ.
Dataset
#Ans
2 #Ans 4
52 #Ans
#Ans 2
10
WebQSP
51.2%
27.4%
8.3%
12.1%
CWQ 70.6%
19.4%
6%
4%
Table Statistics the question hops in WebQSP and CWQ.
Dataset
hop
hop
2: 3 hop
WebQSP
65.49 %
34.51%
0.00%
CWQ 40.91 %
38.34%
20.75%
Table Statisties of MetaQA-3hop datasets.
Datasets
#Train
#Test
#hop
MetaQA-3hop
1,000
1,4274
17

---

Published as a conference paper at ICLR 2024
Table 10: Statistics of constructed knowledge graphs
KG
#Entities
#Relations
#Triples
Freehase Wiki-Movie
2,566,291
7,058
8,309,195
43,234
9
133,582
Table 11: The statistics of the instances in the instruction-tuning datasets.
Planing Data
Retrieval-reasoning Data
Interpretability Data
216,006
30,465
2,000
To evaluate the transferability of RoG other KGs. We further select the MetaQA --hhop dataset
ZZhang et al. 2018) which is based on Wiki-Movies KG fo
We select 1000 samples from the training
split. The statistic of the dataset is presented Table
Both WebQSP and CWQ can be reasoned based on Freebase KGs (Bollacker et al. 2008). To reduce the size of KGs, following previous works (He et al. 2021 Jiang et al. 2022), construct a subgraph of Freebase by extracting all triples that contain within the max reasoning hops of ques- tion entities in WebQSP and CWQ. Similarly, construct a subgraph of Wiki-Movies KGs for MetaQA-3hop. The statistics of constructed KGs are presented in Table I0
We construct the instruction-tumie For planning optimization, we generate data by extracting the shortest paths that connect the ques- tions and answers, which serve as supervisory signals. In the vetrieval-reasooing optimization phase, we feed both extracted shortest paths together with the questions to predict the answers. To enhance interpretability, we randomly select 1000 samples from each dataset along with their reasoning paths and answers. These are then input into ChatGPT to produce interpretive responses, which help em- power our method in generating results with good explainability. The statistics of final training datasets are shown in Table
dataset using the training split of WebQSP and CWQ datasets.
A.5 BASELINES
We compare RoG with 21 baselines grouping into 5 categories: 1) Embedding- methods, 2) Retrieval- methods, 3) Semantic parsing methods, LLMs, and LLMs+KGr methods. The details of each baseline are described as follows.
Embedding- methods.
KV-Mem Miller et al. 2016) adopts a Value memory network to store triples and perform multi-hop reasoning by iterative operating on the memory.
EmbedKGQA (Saxena al. 2020) models the reasoning KGs as sequential link pre- diction problem by using the embedding of entities and questions.
NSM (He al. 2021
utilizes the sequential model mimic the multi-hop reasoning
process.
2021 adopts a graph neural network to capture the relevance be- tween entities and questions for reasoning.
TransferNet Shh et al.
KGT5 (Saxena et al. 2022 finetunes sequence- to to-sequence framework on KGs and gen- erates answers based on the input question.
Retrieval-augmented methods.
GraftNet (Sun et al. 2018 retrieves relevant subgraphs from KGs with entity linking.
PullNet (Sun al. 2019 trains retrieval model composed of LSTM and graph neural
network to retrieve a s subgraph.
18

---

Published as a conference paper at ICLR 2024
SR+NSM (Zang et al. 2022 proposes relation-pant -attionn-aathhho retrieval to retrieve subgraphs for multi-hop hop reasoning.
SR+NSM+E2E (Zhang et al. 2022) further adopts end-to-end training strategy to jointly train the retrieval and reasoning modules of SR+NSM.
Semantic parsing methods.
SPARQL (Sun et al. 2020) presents novel skeleton grammar represent the high-level structure of complex question with language modes.
QGG (Lan & Jiang 2020)
generates a query graph for question by simultancously adding constraints and extending relation paths.
ArcaneQA (Gu & Su ous steps.
2022) dynamically generates the query based on results from previ-
RnG-KBQA (Ye et al. 2022) first enumerates all possible queries and then ranks them to get the final output.
Large language models (LLMs).
Flan-T5 (Chung ct al. 2022) is an enhanced version of T5 models that is instruction fine- tuned mixture of tasks.
2023 based on LLaMA and finetuned on an instruction instruction-followingg Alpaca (Taori et al. dataset.
1.LaM2-Chat (Touvron et al. 2023 is large language model that is optimized for dia- logue purposes.
* ChatGP is powerful clored-source source LLM that could follow instructions to conduct com- plex tasks
ChatGPT+CoT (Wei et al. 2022) uses the Chain-of-thought prompt to improve the reason
ability ChatGPT.
LLMs+KGs methods.
KD-CoT Wang et al. (023b) retrieves relevant knowledge from KGs to generate faithful reasoning plans for LLMs.
UniKGQA (Jiang al. 2022 unifies the graph retrieval and reasoning process into single
model with LLMs, which achieves state-of-the-an performance on KGQA tasks.
DECAF (Yu al. 2022a) combines semantic parsing and L.MMs reasoning jointly gen- erate answers, which also reach salient performance on KGQA tasks.
A.6 IMPLEMENTATION SETTINGS
For RoG,
LLMM2-CCht-775 (Touvron et al. 2023) the LLM backbone, which is instruc- tion finetuned on the training split of WebQSP and CWQ as well as Freebase for 3 epochs. The batch size is set to 4 and the learning rate is policy with the warmup ratio set to 0.03. The training is conducted on 2 A100-80G GPUs for 38 hours. During inference, we first adopt the LLM to generate top-K relation paths with the highest probability as the plans. Then, we adopt the Algorithm | to retrieve reasoning paths, which are fed into the LLM to reason the final answers.
2e-5. We the cosine learning rate scheduler
For LLM beelines, we use zero-shot prompting to conduct KGQA, which directly asks LLMs to answer the question. For other baselines, we directly copy their results reported UniKGQA (Jiang et al. 2022 and DECAF Yu et al. 2022a) for comparisons.
For combining the planning module of RoG with different LLMs,, we use the planning module to generate plans (relation paths), which are executed on KGs to retrieve the reasoning paths. The retrieved paths are fed into different LLMs during inference by utilizing the reasoning prompts template shown in Appendix A.10
httpp:: /tppaai.ppaa/pp//////e//.i com /bl og/ hagg/chee chatgpt "Experiments are conducted with the ChatGPT model released between July. Scpt., 2023.
19

---

Published as a conference paper at ICLR 2024
Table 12: Performance of RoG on MetaQA-3hop.
MetaQA-3hop
Strategies
Hits@ I
Fl
RoG (train from scratch) RoG (transfer from Freebase)
84.81
41.32
88.98
50.68
Table 13: Training time comparison.
Method
Training on Freehase
Transferring to Wiki-Movies
RoG
38 hours
hours
A.7 ADDITIONAL. EXPERIMENT RESULTS
A.7.1 TRANSFERABILITY TO OTHER KGS
We evaluate the transferability of RoG to other KGs. We select the MetaQA-3hop dataset (Zhang et al. 2018) which is based on Wiki-Movies KGs. We select 1000 samples from the training split and utilize two training strategies to finetune RoG: 1) training from scratch, where we directly train RoG from LLaMA2-Chat with 1000 samples; 2) transfer from Freebase, where we conduct further finetuning based on RoG trained for Freebase. The results are shown Table 12 From results, we see that transfer from Freebase achieves better performance than training from scratch, which demonstrates the transferability of RoG to other KGs.
We also compare the training time Freebase and transferring Wiki-Movies KGs. From results shown in Table 13] we can see that the training time on Freebase is 38 hours, while the transferring time is only 2 hours. This demonstrates the efficiency of transferring RoG to other KGs.
A.7.2 PERFORMANCE WITH DIFFERENT TRAINING DATA
In our experiment, we finetune RoG jointly on the training set of both WebQSP and CWQ datasets to maximize the ability of RoG for reasoning on Freebase. To fairly compare with other methods (e.g., UniKGQA (Jiang et al. 2022)) that are only trained on single dataset, we provide additional results of the performance of RoG trained on single dataset. From the results shown in Tables 14 and 15 we can see that RoG trained on single dataset still outperforms the STOA baselines (UniKGQA). Besides, can also find that jointly training RoG on multiple datasets further improve the performance. In the future, we will try to generate more QA datasets from Freebase to further improved the reasoning ability of RoG.
A.7.3 PERFORMANCE COMPARISON WITH DIFFERENT FINETUNED LLMS
In Table we report the zero-shot performance of different LLMs. However, RoG is finetuned on the training split of the QA dataset. To make fair comparison, we further report the performance of the LLMs finetuned on the training split of the QA dataset Table T6 From the results, we can that RoG still outperforms the finetuned LLMs.
Table 14: Performance WebQSP with different training data.
Method
Training Data
Hits @
F1
UniKGQA
WebQSP
77.2
72,2
RoG
WebQSP
81.5
61.8
RoG
WebQSP+CWQ
85.7
70.8
20

---

Published as a conference paper at ICLR 2024
Table 15: Performance on CWQ with different training data.
Method
Training Data
Hits@1
F1
UniKGQA
CWQ
51.2
49.1
RoG
CWQ
59.1
52.9
RoG
WebQSP+CWQ
62.6
56.2
Table 16: Performance comparison with different finetumed LLMs @Hits@ 1).
Method
WebQSP
CWQ
Alpaca-7B (Zero Shot)
51.78
27.44
LLaMA2-Chat-7B (Zero Shot)
64.37
34.60
Alpaca-7B (Finetuned)
74.57
55.98
-LaMA2-Chat-7B (Finetuned)
73.89
53,49
RoG
85.75
62.65
A.7.4 RETRIEVAL COSTS
We present the retrieval time and number retrieved reasoning paths in Figure 4 From results, can that the retrieval time increases with the number of top-K relation paths. Therefore, should select a proper K to balance the retrieval time and the number of retrieved reasoning paths. In experiments, set K 3.
A.7.5 PERFORMANCE ON DIFFERENT HOPS
We present the performance of RoG and its variants on different hops of questions in Table 17 From results, we can see that RoG achieves better performance than its variants on different hops of questions, especially questions with more than hops. This demonstrates the importance relation paths for improving the reasoning performance of LLMss on complex questions.
A.7.6 PERFORMANCE ON DIFFERENT ANSWER NUMBERS
We also present the performance of RoG and its variants questions with different numbers of answers in Table 18 From results, we can see that RoG achieves better performance than its variants on questions with different numbers of answers. Specifically, with the number of answer increasing, the performance of RoG w/o planning decreases significantly due to the lack of knowledge from
Retrieved Reasoning Paths
Retrieval Time
Retrieved Reasoning Paths
WebQSP le-3
# Retrieved Reasoning Paths Paths
CWQ
le-3
40
125
2.5
100
30
1.5
2.0
1.0
Retrieval
1.5
Retrieval
10
25
1.0
Top-K relation paths
Top-K relation paths
Figure 4: Average retrieval time and average number of retrieved reasoning paths w.r.t. the number of top-K relation paths.
21

---

Published as a conference paper at ICLR 2024
Table 17: Fl scores of RoG and its variants for different hops of questions.
WebQSP
CWQ
Methods
hop
hop
2 hop
hop
hop
2 hop
RoG
77.03
64.86
62.88
58,46
37.82
RoG w/o reasoning
57.06
25.49
17.06
34,25
17.07
RoG w/o planning
50.33
51.66
31.04
33.93
23.29
Table 18: Fl scores of RoG and its variants for questions with varying numbers of answers.
Methods
WebQSP
CWQ
#Ams
#Ams X 4
2 #Ans
AAns 2
8Ans
2 4Ams X 4
5 2 BAns S
AAns 2
79.39
53.73
43.62
RoG w/o reasoning
33.49
52.80
58.05
66.01
16.61
27.06
40.10
34.45
planning
KGs. Although, RoG w/o reasoning can retrieve more answers to improve the performance. still inferior to RoG due to the lack of reasoning ability to remove the noise.
A.8
CASE STUDIES: RELATION PATHS
We illustrate several examples of relation paths generated by RoG in Table
A.9
CASE STUDIES: INTERPRETABLE RESULTS
We illustrate several examples of interpretable reasoning results generated by RoG in Table 20
A.10
PROMPTS
Planning module aims generate faithful relation paths plans for answering the question. The instruction template is presented as follows:
Planning Prompt Template
Please generate valid relation path that can be helpful for answering the following question: <Question>>
where <Questicn> indicates the question.
The reasoning module takes the question y and a set reasoning paths W, to generate answers a. The instruction template is presented as follows:
Reasoning Prompt Template
Based on reasoning paths, please answer given question. Please keep answer as simple as possible and return all the possible answers as a list.
Reasoning Paths:
<Reasoning Faths>
Question:
<Question>
where <Reasoning Paths> denotes the retrieved reasoning paths W, which are formatted as series of structural sentences:
60 +1 +6
ri
+ E
6u 41 +1
+ +
22

---

Published as a conference paper at ICLR 2024
To exploit the explanation ability of RoG, design instruction template for the reasoning
module to generate interpretable results. The instruction template presented as follows:
Explanation Prompt Template
Based on the reasoning paths, please answer the given question and explain why.
Here are some examples: <Examples>
Reasoning Paths:
<Reasoning Paths>
Question: <Questions
where the Examples es denotes a few-shot human- humaan-nnotated examples demonstrate the explana- tion process.
Table 19: Examples of the generated relation paths.
Question
Top-3
excstio.country Singuagss.ppolees
What does jamaican people speak?
2: language human languge spokem..i
locaiim.cooutry.. oflicial Janguge
location Incation people hora here
russell from?
people pensoe. of birth
spoets.pport Jequue.rrrrrrrr www.ar/.pccppppppppprppppp player sports.pons.eegsee.ttlll
people deceased person.place
where did edgar allan poe died?
23 people couse death people
people penson plave bithh
people perpiceerroos.oo pessoo.cducation education educttion student edlcction educativnal Lintitution studentx graditttegg education instititioo
education educational institution stadents, graduntes
highschooll did harper go
people pensos education
music recondicccodin anist
what are the songs that justin bicber wrose?
22: music composition composer music composer composittoss
people pensce nationality
the religions
indonesia?
locaion Mumisticallrrgioen religions location www.gii.pwneemaagge..omoooo peweemaag religgon
religion languages
sports.masoo..ccmm
sports championship event.champion
Lou Seal is the muscot the teum that last won the World Series when?
22 sports mascot Acum sports Jeam chumpiossips.
sports. www../aommpppipppp..... boottsspett_ettmmionniii
pvent championship
locatlon.administtinn administrativee division first Jevel division, of forermment.ooon...o of, www.ggmmeentowaaaeeee countries
location
government used the
location www.aammmiiiiiiiiee...... Jivisio lind Jevel
location country form.ol governmen
with Distriee?
administaiive
first jllvision gowemment cemmmmmnt.oommot.... www.://wm...oooommmeee countries
location administaaiive
level
language human language countries spoken
The people from the country that contains Nord-Ouest Department speak what lan- guagos today?
2o: location aoaaiin.admiiistaalii division first level division -t location.coureryy.. country languages spoken
buse atreas achema alministtative..o une administiiii parent aection.ccunttyy www.laaggggssssrrrrrr.
sports sports facilityteams
team mascot
22 sports.sports
maseot sports sperts facility.coams
named Hank pla at?
Rg masors teom sports Jesr Jeam arena,
sports sports Jeam cesm.championship... -> sports sports Jenm, www.://nnttinnnneee
Which popular sports team in Spain, that wvnn 2014 Eurocup Finals championship?
sports.sortt sports team locarion sports.sports.oo sers-ppottstnnnn Jeam. www.maaaaaaaaaaaaee Jocatio teams
Jeam location sportt.sporss..uu Jeam Jocation Jecattiionnn.......ooooooo teams sports..ports Jewn:eeeen_naaaacoeoccee Jocationseom
educationn educational Institution
What educational inctitution with the mascol named Wishington University Bear did Tun- nessce Williams to?
22 people penson nationality - location locatooo ceculirrkkcatimmmmmtnelllly
cducation..dacation studeet education.duucaioo institution
professionll Jearttteemmmmmooooe...mmo owner_s americun, footbull Louccl current hww.hhhhellcchhchccc fow..aolllll.oollllllloooo Jendjenneedd_oce
current squd owned by the Rooney fumily?
sports.rofessionnl www.:lpppppsea..o..oooooo
23 american
cumeat seom
21 wwppppot.artt mascor leam sports facilityteomss
What is the home lield of the spoets teom whene moscot named Fredhidd?
sports sporss www../eammmmmm.................a team masspo spotts.poris sports scoms
masoot Acom
team arens stadiom
23

---

Published as a conference paper at ICLR 2024
Table 20: Examples of faithful and interpretable reasoning of RoG.
Question
Lou Seal the mascot for the team that last the World Series when?
Answer
2014
Reasoning Paths
Lou
Scal + woa.tss.mccot.camm - San Francisco
Giants
sports.sports. championship event. chent.champion - 2014 World Series
Based on the provided reasoning paths, we can determine when the team for which Lou Seal is the mascot last won the World Series:
1. Lou Seal is associated with the San Francisco Giants,
RoG
2. The San Francisco Giants associated with winning the 2014 World Series.
Therefore, the San Francisco Giants, the team for which Lou Seal the mascot, last won the World Series in 2014.
Question
what my timezone louisiana?
Answer
Central Time Zone
Louisiana - location.locatonn partiall containedby - Tangipahoa River -
geogra-
phy.river.origin + Osyka + location. location. timeeeooeeessssss zones + Central Time Zone
Reasoning Paths
Louisiana
Alexandria lon.location.commmmmmmmmmmm ceaiiiinncotaiinddlyy.. -> United States of America Docatin.locaaton.tiin zones
loca-
Central Time Zone
Based the reasoning paths provided, it he determined that Louisiana is in the Central Time Zone.
Here's the explanation:
The first reasoning path tells us that Louisiana partially contained by the Tangipahoa River, which a geographical feature. However, doesn' 't directly mention the time zone.
RoG
2. The second reasoning path establishes that Louisiana is contained by Alexandria, which is in turn contained by the United States of America. The United States of America is in the Central Time Zone.
Therefore, based on these reasoning paths, the time zone in Louisiana is the Central Time Zone.
Question
Which child Walt Disney died from lung cancer?
Answer
Sharon Mae Disney
Lung cancer - people.deccased person. person.cause cause of death + Sharon Mac Disney
Lung cancer
pecpleedeceased.pprsoo..com of deett Walt Disney
Walt Disney +
+ Lung cancer
Walt Disney -> people.person.childeen -+ Diane Disney Miller
Reasoning Paths
Walt Disney - weople.cause.of oft.lleccuue.o.ddathp.ppp peopee Circulatory collapse
Walt Disney - people..erronn.aree parents + Flora Call Disney
Walt Disney people.person. parents Elias Disney
Walt Disney +
wwoppe.persseeeeee www.ppprrsonn.eeeecee. +
Sharon Mac Disncy
Based the reasoning paths provided, appears that Sharon Mae Disney is the child of Walt Disney who died from lung cancer.
The reasoning path "Walt Disney + people.deceased, www.leecaseddppsss.ccae wpw.spo.ccuuee.ccc of deathh - I Lung can- cer" directly connects Walt Disney to lung cancer cause of death, and since Sharon of death through the path "Lung can-
RoG
Mae Disney is also linked to lung cancer cer + people.deeeased..ers.... pew.odd.eessccaeeeeee cassoonccuee.ooo ofeetthhhhhhhho - Sharon Disney," it can concluded that Sharon Mac Disney is the child of Walt Disney who died from lung cancer.
24


Reviews:
[{"review_id": "940sfv6miJ", "reviewer": "Reviewer_ZzpQ", "summary": "The paper proposes a new approach for questions answering over knowledge graphs. The idea is to use LLMs for QA while exploiting the information in the KG and reasoning over that to alleviate the issues of lack of knowledge and hallucination of LLMs. The main idea is to tune the LLM to generate the relation path needed for finding the final answer, and then instantiate the paths to the answer by searching in the KG. Then feed the instantiated paths that use the actual entities back to the LLM to find the answers that are more faithful to the path of reasoning and less pruned to the hallucination. The experiments are done over two KGQA benchmarks with up to 4 hops of reasoning.  Multiple LLMs (GPT, T5, LLAma, Alpaca) are used and tested. The results show significant improvements compared to a variety of baselines and existing SOTA.", "questions": "--If I understood correctly when you refer to retrieval and reasoning/planning modules of ROG, those are the outcome of instruction-tuning of a specific large language model. When you discussed the ROG model, it was not clear to me what was the base LLM; Which language model was used and tuned for those results of ROG?  when you combine ROG with other language models in Table 4, which one has been used again in the planning module?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The approach is novel and interesting. \nThe experiments show strong results and improvements over SOTA. \nThe paper is well written though the organization of the approach description can be improved.", "weaknesses": "--The approach section was hard to read.\n    --- More specifically, the order of explanation was a bit hard to follow. Before explaining the optimization, I think explaining the flow of information step-by-step will be helpful when you point to Figure 3 in the beginning. In the optimization part, explaining what kind of ground-truth supervision is used was not very explicit. Using the retrieved paths from the KG as a source of supervision could be made clear earlier in the approach.  \n\n--The training approach seems to be very costly.  It needs training and instruction-tuning for the LLMs to generate the relation and KG-specific paths. If we train with a specific KG the results will improve in answering questions from that specific KG --which of course is the scope of this work. However, I am not sure if this helps LLM's QA capability in general and the issues set in front including hallucination and lack of knowledge in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8LRgPcxYV2", "reviewer": "Reviewer_qFDd", "summary": "This paper addresses the increasingly important problem of integrating Large Language Models (LLMs) into a more general support framework that can overcome their shortcomings and limitations using axillary techniques.  A compelling 'Reasoning on Graphs' (RoG) approach is introduced to enhance the reasoning capabilities of LLMs by leveraging the structural information of Knowledge Graphs (KGs).  The RoG concept emphasizes the importance of KGs' relational structures in the reasoning processes. The proposed method consists of a planning-retrieval-reasoning framework that generates relation paths grounded by KGs, which serve as reliable plans for subsequent reasoning tasks. These plans guide the retrieval of valid reasoning paths that facilitate faithful and interpretable reasoning by LLMs. The paper addresses two main issues prevalent in previous methods: the tendency of LLMs to produce hallucinated content and the underutilization of KGs' structural data. RoG is optimized through planning optimization, which distills KG structure into LLMs, and retrieval-reasoning optimization, which enables LLMs to produce accurate, KG-supported conclusions. The paper also situates RoG in the context of existing research, identifying its methodological advancements over semantic parsing and retrieval-augmented reasoning approaches.", "questions": "1. Can you clarify which version of ChatGPT was used?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Originality: This paper presents a solid concept for addressing weaknesses in pure LLM model-driven inference by coupling the LLM with a reasoning system.\n\nQuality:  The concept is sensible, compelling, well described, and thoroughly evaluated.  The breadth of comparison techniques is appreciated.\n\nClarity:  All aspects of the concept, relationship to existing literature, and experimental evaluation are well described.\n\nSignificance:  The application community needs actionable approaches to addressing shortcomings to LLMs, and this paper provides one such compelling example.  This result will likely be impactful to future research and implementations.", "weaknesses": "Clarity:  The evaluation against ChatGPT appears to use 3.5-turbo.  Please clarify, including the dates of the evaluations -- the implementation of ChatGPT changes over time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KR9Wg6qpDn", "reviewer": "Reviewer_1bmQ", "summary": "The authors propose a new knowledge graph retrieval-based fine-tuning algorithm of LLM, RoG, which shows significant improvement over many baselines, including chatGPT, on two KGQA datasets. The method has two training objectives, one retrieval objective, and one planning objective. The LLM is trained to first generate several reasoning paths and then verify and select the best paths based on a KG. The ablation study shows that both objectives are crucial. The fine-tuned LLM can be regarded as a stand-alone planning module for other LLMs, like ChatGPT, and improve their performance.", "questions": "1. Is RoG trained on both WebQSP and CWQ at the same time or is it trained separately on these two datasets? I'm not super familiar with the KGQA baselines, but I wonder if all baselines are trained on the same data as RoG. If the baselines are only trained on one of the datasets each time, then it's not fair to compare RoG with them, if RoG is trained on both of them at the same time. \n\nI'm willing to raise my score if my concerns are properly addressed.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The empirical performance of the proposed method seems to be pretty strong on the two KGQA datasets, compared to many baselines.\n\n2. The proposed method seems to be able to better combine the reasoning power of both LLM and KG.", "weaknesses": "1. There is some nonrigorous math in the paper. e.g. in equation 4, the expectation and Q should not coexist. It's either $\\mathbb{E}_Q \\log P$ or $\\sum_z Q \\log P$. In the next line, $z \\in Q$ does not make sense as $Q$ is a probability distribution. Also, the equality does not make sense as there is a CONST in equation 4. Also, I don't think it's a good idea to use equality for an approximation. Similar nonregorousness happens in equation 6. The marginalization in equation 10 does not make sense, as the authors are marginalizing over the conditions. The correctness of the final training objective needs to be double-checked.\n\n2. More datasets to showcase the effectiveness of the proposed method would be great, as there are currently only two in the paper. Would the fine-tuned LLM generalize to other QA datasets, in addition to the datasets that it is fine-tuned on?\n\n3. About RoG as a planning module for other LLMs: I understand that the fine-tuned LLM can also be combined with other LLMs, and improve the performance of these not fine-tuned LLMs. However, according to Table 4, even combining with a stronger LLM (e.g. ChatGPT) cannot improve upon the original fine-tuned LLM. I don't see the usefulness of having this sort of integrability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AUL0HqYBw6", "reviewer": "Reviewer_cFys", "summary": "This paper proposes a new framework using external KG to enhance the reasoning ability of LM. The authors finetune LMs (e.g., LLaMA) as the planning and retrieval modules for performing reasoning tasks.", "questions": "1. For the KG, is that constructed by yourself and used for all tasks, or is it provided in the dataset?\n\n2. In equation 4, the final equality, the constant term is missing.\n\n3. In Table 2, RoG is finetuned LM, but it's compared with LLMs under the zero/few-shot setting. Is that a fair comparison?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Generally, this paper explores an interesting topic with a reasonable method design. Experiment results also look good.\n\n1. Framework design. This reasoning framework design is reasonable: the explicit KG usage makes the reasoning process interpretable and controllable. \n\n2. The two modules (planning and retrieval) finetuning works well. Experimental results show that indeed using the RoG framework with the two tuned modules, better reasoning performance can be achieved.", "weaknesses": "However, I have several concerns about this work.\n\n1. From equation 1, I understand the authors want to decompose the prediction task into two parts: getting hidden variable z and then predicting the answer with the hidden variable. However, it's not clear whether equations 2-6 are necessary. Could you provide more intuition behind for explanation? \n\n      Even if motivation exists, I'm not sure why equation 3 holds. Why is there only one path / relation path and it's faithful? For example, there could be multiple solutions/paths; if so, equation 3 might not hold. The authors should provide more justification for the equation 3.\n\n2. One of the key points in the framework is the finetuned LLM (i.e., \\theta). However, in the main paper, it's not clear how the LLM is finetuned. It seems the objective functions follow the equation 7. However, these two modules are not evaluated individually and there is no validation loss provided. Only the final framework performance can prove that these modules work as expected, which is not sufficient for readers to know why they can work.\n\n3. Over-claim sentences. The authors claim that their RoG framework can address the hallucination issue and lack of knowledge issue. However, studies with several cases are definitely not sufficient to prove them. I would suggest adding more comprehensive results or changing the claim.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)