Reasoning of Large Language Models over Knowledge Graphs with Super-Relations
Authors: Song Wang
Junhong Lin
Xiaojie Guo
Julian Shun
Jundong Li
Yada Zhu
Venue: ICLR 2025 Poster (2025)
Keywords: Knowledge Graphs
Large Language Models
Question Answering
Primary area: foundation or frontier models, including LLMs

Abstract: While large language models (LLMs) have made significant progress in processing and reasoning over knowledge graphs, current methods suffer from a high non-retrieval rate. This limitation reduces the accuracy of answering questions based on these graphs. Our analysis reveals that the combination of greedy search and forward reasoning is a major contributor to this issue. To overcome these challenges, we introduce the concept of super-relations, which enables both forward and backward reasoning by summarizing and connecting various relational paths within the graph. This holistic approach not only expands the search space, but also significantly improves retrieval efficiency. In this paper, we propose the ReKnoS framework, which aims to Reason over Knowledge Graphs with Super-Relations. Our framework’s key advantages include the inclusion of multiple relation paths through super-relations, enhanced forward and backward reasoning capabilities, and increased efficiency in querying LLMs. These enhancements collectively lead to a substantial improvement in the successful retrieval rate and overall reasoning performance. We conduct extensive experiments on a variety of datasets to evaluate ReKnoS, and the results demonstrate the superior performance of ReKnoS over existing state-of-the-art baselines, with an average accuracy gain of 2.92% across nine real-world datasets.

Published as a conference paper at ICLR 2025
REASONING OF LARGE LANGUAGE MODELS OVER KNOWLEDGE GRAPHS WITH SUPER-RELATIONS
Song Wang't Junhong Lin", Xiaojie Guo Julian Shun?, Jundong Li', Yada Zhu
University of Virginia, 2MTT CSAIL, 3IBM
(sw3wv, jundw...jundoggeiiiiiiiii. {junhong, jshun)@mi edu (xiaojie.guo guo, slaajjie.guo.yhhueetb..ccom
ABSTRACT
While large language models (LLMs) have made significant progress in processing and reasoning over knowledge graphs, current methods suffer from a high non- retrieval rate. This limitation reduces the accuracy of answering questions based on these graphs. Our analysis reveals that the combination of greedy search and forward reasoning is a major contributor to this issue. To overcome these challenges, we introduce the concept of super-relations, which enables both forward and backward reasoning by summarizing and connecting various relational paths within the graph. This holistic approach not only expands the search space, but also significantly improves retrieval efficiency. In this paper, we propose the ReKnoS framework, which aims to Reason over Know weoweedge Graphs with Super-Relations Our framework's key advantages include the inclusion of multiple relation paths through super-relations, enhanced forward and backward reasoning capabilities, and increased efficiency in querying LLMs. These enhancements collectively lead to a substantial improvement in the successful retrieval rate and overall reasoning performance. We conduct extensive experiments on nine real-world datasets evaluate ReKnoS, and the results demonstrate the superior performance of ReKnoS over existing state-of-the-art baselines, with an average accuracy gain of 2.92%.
INTRODUCTION
Recent advances in large language models (LLMs) have greatly improved their ability to perform reasoning in various natural language processing tasks (Brown et al. 2020; Wei et al., 2022). How- ever, for more complex and knowledge-intensivee reasoning tasks, such open-domain question answering (Gu et al., 2021), the knowledge stored in LLM parameters alone can be insufficient for effectively performing these tasks (Li et al., 2024). To address this limitation, recent research has explored the integration of knowledge graphs (KGs), which represent structured information as entities and relationships, to provide external knowledge that can assist LLMs in answering such questions (Sun et al., 2023; Ma et al., 2024; Xu et al., 2024; Zhang et al., 2022).
Despite this progress, effectively leveraging knowledge graphs for question answering remains challenging due to the vast amount of information in KGs and their complex structures. Existing approaches typically resort to two retrieval strategies: (1) subgraph-based reasoning (Zhang et al., 2022; Jiang et al., 2023d), which retrieves subgraphs containing task-relevant triples from the KG and uses them as input for LLMs; and (2) LLM-based reasoning (Jiang et al., 2023b; Sun et al., 2023), which involves iteratively querying LLMs to select relevant paths within KGs. While subgraph- based reasoning can efficiently retrieve structured knowledge, LLM- based reasoning benefits from the comprehension capabilities of LLMs precisely select relevant triples, resulting in superior performance compared to subgraph-
methods (Jiang et al., 2024; Pan et al., 2024).
However, even with the advances in LLM-based reasoning methods, there remains a significant performance gap that is often overlooked by existing research. Specifically, current approaches exhibit substantial non-retrieval rate, indicating that in certain cases, the LLMs fail to find satisfactory reasoning path within the maximum allowable reasoning length. As demonstrated in Figure 1, for the recent method ToG (Sun al., 2023) on the prevalent dataset GrailQA (Gu et al., 2021), the accuracy reduces by around 10% when the information is not retrieved from the KG.
"t Work done when Song Wang was visiting MIT CSAIL and the MIT-IBM AI Watson Lab.

---

Published as a conference paper at ICLR 2025
In this paper, investigate the reasons be-
GPT-4
GPT-4o-mini
GPT-3.5
hind retrieval failures when searching the knowledge graph, identifying two relation patterns that are often overlooked by exist-
Retrieved or Not
Yes (54.3%)
ing works. As illustrated in Figure 2, the primary causes of non-retrieval can be clas- sified into three categories: (1) Misdirec-
No (45.7%)
tion, where the correct path runs parallel to the retrieved path; (2) Depth Limitation, indicating that the correct path is longer than the retrieved one due to the maximum allowable length being exceeded; and (3) Path Absence, where the correct path does not exist in the knowledge graph. Notably, the first two cases account for the majority of non-retrieval instances. Existing methods struggle with the first case because they may initially select relations that appear promising but are ultimately incorrect. In such cases, once the first step is wrong, subsequent retrieval attempts unlikely capture the correct path.
50
55
60
65
70
75
80
Accuracy
The accuracy (%) of retrieved and non- retrieved samples on the GrailQA dataset.
Figure
To address the issue of misdirection, we propose novel frame- work ReKnoS, which aims to Reason over Knowledge Graphs with Super-Relations. Super-relations are defined as a group of relations within specific field. For example, the relation "de- veloper of"" and "designer of"" are both under the super-relation "video game". as they are in the same field of video games (shown at the bottom of Figure 3). Using super-relations allows for a more holistic approach by enhancing both width (the number of relations covered at each step) and depth (the total length of the reasoning path). By integrating super-relations, framework introduce additional relational paths that were previously inaccessible, thus expanding the search space and improving retrieval rates. These super-relations effectively summarize and connect disparate parts of the graph, facilitating more comprehensive exploration of the data. Moreover, with the summarized information within super-relations, we pro- pose leverage it to achieve forward reasoning and backward reasoning, which aim at exploring future paths and previous al- ternative paths, respectively. With the design of super-relations, framework represent multiple relation paths with super-relation during reasoning. As such, we do not need to abandon a large number paths during reasoning, thus significantly increasing the search space and improving the retrieval rate.
Path Absence 6.0%
Depth Limit 25.2%
Misdirection 68.8%
Figure 2: The non-retrieval cases on the GrailQA dataset with base- line ToG (Sun al., 2023) (maxi- mum length of 3).
The contributions of this paper are as follows:
The use of super-relations, defined as groups of relations within specific field, enables the inclusion of large number of relations for efficient reasoning over knowledge graphs. Moreover, super-relations can both enhance the depth and width of various reasoning paths to deal with non-retrieval.
Design:
We propose novel reasoning framework ReKnoS that integrates super-relations, enabling the representation of multiple relation paths simultaneously. This approach allows for significant expansion of the scarch space by incorporating diverse relational paths with- out discarding potentially valuable connections during reasoning. Our code is provided at https///gitubb.co/SSngg http://onnwS//EEKK/OO/..
Framework:
We perform experiments nine real-world datasets and show that our approach significantly outperforms traditional reasoning methods in both retrieval success rate and search space size, improving them by average of 25% and 87%, respectively. These results highlight the effectiveness of our design choices in addressing complex knowledge graph reasoning tasks.
Experiments and Results:
2

---

Published as a conference paper at ICLR 2025
2
RELATED WORK
Although LLMs have exhibited expressive capabilities in various natural language process tasks, such as question answering tasks (Wei et al., 2022; Wang et al., 2023), they can lack up-to-date or domain- specific knowledge (Wang al., 2023; Jiang et al., 2023b). Recently, researchers have proposed using knowledge graphs (KGs), which provide up-to-date and structured domain-specific information, enhance the performance of LLMS (Pan al., 2024). As classic example, retrieval-uugmented generation (RAG) methods have been widely used to incorporate external knowledge sources as additional input to LLMs (Jiang et al., 2023c). Nevertheless, the complex structures KGs render such retrieval more difficult and may involve unnecessary noise (Petroni et al., 2021).
Knowledge graph question answering (KGQA) focuses on answering natural language questions using structured facts from knowledge graphs (Pan et al., 2024). A central challenge lies in efficiently retrieving relevant knowledge and applying it derive accurate answers. Recent approaches to KGQA can be divided into two main categories: (1) subgraph- based reasoning and (2) LLM-based reasoning. Subgraph-base based methods, such as (Zhang et al., 2022), UniKGQA (Jiang et al., 2023d), and ReasoningLM (Jiang et al., 2023c), perform reasoning task-related fact triples from the KG. However, these methods are highly dependent on the quality of the retrieved subgraphs, which may contain irrelevant information and struggle to generalize to other structures within the KG. More recently, researchers have turned to LLMs to enhance reasoning on KGs. As an early effort, StructGPT (Jiang et al., 2023b) leverages LLMs to generate executable SQL queries to reason on structured data, including databases and KGs. Think-on-Graph (ToG) (Sun et al., 2023) extends this by using LLMs select relevant relations and entities for retrieving target answers. KG-Agent (Jiang et al., 2024) further advances this line of work by incorporating a multifunctioal toolbox that dynamically selects tools to explore and reason over KGs.
retrieved subgraphs that contain
3 PRELIMINARIES
3.1 KNOWLEDGE GRAPH (KG)
knowledge graph composed of large set of fact triples, represented as G r(e, e,,e' F.r E R). where and R denote the sets of entities and relations, respectively. Each triple (e, e') captures a factual relationship. indicating that a relation r' exists between a head entity e and tail entity e'. For the KGQA task studied in this work, we assume the availability of a KG that contains the entities relevant to answering the given natural language question. Our goal is design an framework capable of performing reasoning on the KG to retrieve the answer to the question.
3.2 SUPER-RELATION RELATIONS
In this paper, we introduce the concept of a super-relation to efficiently gather information from a set of more granu- lar, detailed relations. For instance, consider super-relation "music.featured artist which encompasses a variety of specific relations, such "music.featured artist.recordings. Iterating over each of these detailed relations can be computationally intensive. By using higher-level super-relation like imusic.featuree artist," we abstract and group these related relations together, allowing us to query LLMs using a single, more general relation. This abstraction reduces the complexity of handling numerous fine-graid grained relations while preserving the relevant information needed for reasoning. the prevalent knowledge graph Wikidata (Vrandečić & Krötzsch, 2014) that we use in this paper, relations are typically organized into a three-level hierarchy, such as "music," "'eetture_artti"" and "recordings." We treat the second-leve relations as super-relations, which serve representative for related third-level relations. How- ever, it is important to note that not all KGs are structured with such clear hierarchical levels. In cases where KG lacks this inherent structure, alternative approach
Super-Relation Set S,
Ti music featured artiet
music must-fecturee fectured recoriier
Fg- musk.Jostured artist.ibums
50 computer_ videogame
Ti commuder sishogemm.daaaaa
Typ computer addogome.deveigge
Figure 3: An example of vari- ous super-relations R included in a super-relation set S.
3

---

Published as a conference paper at ICLR 2025
Step contribute question and score them fiom to
Integrrator
Question
Answer Museum.
Which
Retriowe encty
contribute question and score theme from 0 to
Summarize the onswer bosed on the avntinbie information
Timathy
Legend
patter following Ressoning Paths
Example Super-Relations
Super-tatation
0,85
Anthitettur
Fiteree Saper-
Gitty Mexsir
Parvili
Peoplk,
Holetion
Hausey
Archtsetirs.mssun
Enttyy
Ad
Lakeed
Buninessemplooee
Fitered Entry
Funilluu
Nause
klepiee
Figure 4: Overall ReKnoS framework. The LLM first extracts the query entity from the input question and then performs up L steps of reasoning. In each step, the LLM retrieves several super-relations and scores them. Only the selected candidates will be used for further reasoning. Finally, the LLM gathers the reasoning paths and final entities generate the final answer.
involves clustering relations based on their semantic similarity and using the cluster centers as super-relations. These cluster centers must be textually coherent and meaningful ensure they can effectively summarize the detailed relations within each cluster. In our experiments, we directly utilize the bierarchical levels.
We formally define a super-relation R as a group of more granular, detailed relations R (ri, 12.....3 .,, where each a specific relation the knowledge graph. Examples are shown Fig- ure 3. For example, if R is the super-relation music,.eeturee artist," it might include set of relations such R feature artist rrciistrecordinggs" mmsscc.feature aartst.albums" .....
3.3
RELATIN SEARCH PATHS
We first define super-relation connection between two super-relations.
Definition 1. Super-Relation Connection. Let Rı and R₂ be two super-relations, each consisting of multiple relations. We define R₁ > R2 (i.e., R₁ connects to R2) if and only if there exist entities e1. e2 and eg such that E1
e2 22 E3, where V1 Rg and T2 E R2-
In this manner, based on connections between super-relations, define a super-relation path and then define a super-relation search path, where each position in the path consists of multiple super-relations. Definition 2.
Path. A super-relation path p= (R4 - R2 + .... - R2) of length I consist of super-relations that consecutively connected.
Definition 3. Super-Relation Search Path. A super-relation search path Qi of length consists Si). Here S, (R("), R(2), ...., R(IS. '1 is super-
of super-relation sets, i.e., (== relation set at the i-th position in Q, Moreover, in each super-relation set S, there exists at least one super-relation that is connected to super-relation the subsequent set Si+ i.e.
VR E St, 3R' E SS41 such that R + R', i= 1.2.....4 1
4
REASONING
Our ReKnoS framework consists of at most L reasoning steps, which is also the maximum length of search paths considered. During each reasoning step, we aim to retrieve set of N important super- relations that are the most semantically related to the query based on the selected super-relations from previous reasoning steps. In other words, at the beginning of the (-th reasoning step, the search path 2 {Si, S2, ... St } is of length / 1, i.e., containing / 1 sets of important super-relations. These super-relation sets are consecutively connected according to Definition 3, i.e., VR E S,, 3R' S1+1 such that R + R'. Our goal in this reasoning step is to select an important set of N super-relations in S,, while satisfying the condition that VR e S,, ER' E S such that R R'. Moreover, |S| = N for 1.2,..., At the end of each reasoning step, the LLM will be
4

---

Published as a conference paper at ICLR 2025
asked to decide whether to extract the answer from the entities to proceed to the next reasoning step. The overall framework is illustrated Figure 4.
4.1 CANDIDATE SELECTION
To select the current St, we first need extract any candidate super-relation R' that satisfies the connection requirement: vR E St-1; 3R' Si such that R - It.. This means that It' is connected by any super-relation in the last super-relation set Si-1. Therefore, we can represent the set of candidate super-relations C
C = {R ER'S Si-1 such that R' + R),
(1)
where S is the previous super-relation set in the search path Q This approach obtains all generally becoming
super-relations directly connected to the search path. As the connections larger as the search proceeds, it is likely that [C₁] > S = N for > 2. Therefore, we need to perform reasoning to filter out irrelevant super-relations in to obtain S C C..
4.2 SCORING
In the scoring step, are denoted as {s/, Based on these scores, aim to select N super-relations with the largest scores. The scores obtained as follows:
LLM assign score for each of the super-relations in C.. The scores where M = -Cil-- Note that this step is only needed if M > N.
{st st. .f....,,." sMM }
LLM RC. RL. RM }),
RM.
where RS E C₁2 = 1......... M.
(2)
The prompt the LLM is as follows, setting N 3 as an example:
You need select three relations from the following candidate relations, which are the most helpful for answering the question.
Question:
Topic Entity:
Candidate Relations:
Reply with the relations you selected from these candidate relations:
Note that in the prompt, we do not explicitly inform the LLM about the super-relations in order to reduce unnecessary complexity. Following ToG, use human human-crafted example additional input to LLMs to guide the scoring process. Based on these scores, we select the N super-relations from C with the highest scores. We first sort the scores in descending order:
(M)
(M)
2 81
(3)
where (2) is the i-th largest score, and the corresponding super-relation is denoted as R,(
The N selected super-relations are denoted as follows:
S [ Rz(2) ..... R N
(4)
Then, we normalize the scores of the selected super-relations so that they sum to 1:
for k = 1,2,.....4
(5)
j=
In this way, we ensure that only the most relevant super-relations with the highest scores are considered the next iteration, and their influence is appropriately scaled through normalization. The normalized
scores {s) ...,,,,(f N( will be later used for relevant path selection in the reasoning process.
4.3 SCORE-BASED ENTITY EXTRACTION SELECTION
Now we have obtained the selected super-relation search path of length 1, i.e., Q1 = {S1, S2, ..). Here, each super-relation set S, consists of N super-relations, i.e., S; {R(12) n!,2) R [N) ).
5

---

Published as a conference paper at ICLR 2025
Moreover, each super-relation R is associated with score assigned during the scoring step, denoted as 5 At this point, we need to either use the retrieved super-relations to answer the question or proceed to further increase the length of the super-relation search path.
To find the potential answers and also provide sufficient information for the LLM to decide whether continue retrieving the super-relation search path, we propose to extract the entities the end of Qi. i.e., entities connected by super-relations at the last step of that path. These entities will be used to prompt the LLM to decide whether the retrieved entities are sufficient for answering the query. If the LLM responds that these entities are sufficient for answering the query, we will further prompt for the answer. On the other hand, if the LLM suggests further exploring the reasoning, we will repeat the steps described above retrieve a longer super-relation search path Q441. When / L, we will always ask the LLM for the answer.
Reper-Relation Path Selection. Due to the large number of entities connected by super-relations in Q1 we first identify K most relevant super-relation paths from 2, Particularly, we represent a super-relation path P. derived from Q follows:
P. (H( (R(( (1,222) +...- R2 R......).. where R. ( j j 1-L (6)
1-1.
Here, Ki,j [1. |S,l] represents the index of the specific super-relation in the j-th position of the i-th path, such that 1ef E Sy. The set of all possible super-relation paths is denoted as P= Pg... Prpii. }. Notably, the number of possible super-relation paths, i.e., IP], may vary depending on the connectivity across different super-relation sets in Pt. However, P contains least one super-relation path, i.e., [P] 2 according to the following theorem.
Theorem 4.1. A super-relation search path leads to al least one super-relation path. Given a selected super-relation search path of length 2 = (S1, (S1,,2,..... , there exists at least one super-relation path of length i.e., P == [R] (ki) (ks)
Rb R((a)). where R((e) E Sy and ky represents
for a fixed i.
Intuitively, this theorem holds because consecutive super-relation sets, i.e., S; and S are connected, and thus at least one super-relation in each of them is connected to each other according to Definition 3. Therefore, the consecutively connected super-relations form super-relation path. The proof is provided in Appendix A. To select the super-rclation paths that are more relevant to the input query, we propose to sum the scores of the 1 super-relations in each super-relation path. Specifically, for the i-th super-relation path P.
(R( R ((ke)) ....- - R R(fA.)) the total score is computed
Score P,) Σ (k,,)) j=1
(k.z) (kra) + 82
(b..) + + 8|
8)
With the summed scores for these super-relatee relation paths, we select the K super-relation paths with the largest scores. The final selected super-relation paths are as follows:
P
arg max SyEP:PPyls PEP,
Σ Score P).
Final Entity Selection. With the relevant super-relation paths, our final goal is to extract the entities at the end of each reasoning path in Pt, We first introduce the following theorem for selecting specific relation paths from super-relation paths.
(R(-1) 1=
- R +...+ R(( there exists at
Theorem 4.2. For any super-relation path P =
least one corresponding KG reasoning path of length I, represented as e1 E4 e2 13 m, et where r; R (kk) is a relation chosen from the super-relation R( and e1, ..,..., et+1 are entities in the knowledge graph.
This theorem holds because in super-relation path, according Definition 2, two consecutive super- relations are connected, which leads to the connection of two relations. Therefore, the consecutively connected relations will form relation path. The proof is provided in Appendix B. According the

---

Published as a conference paper at ICLR 2025
0.36
0:32
0.6
0.12
0.5
0,05
0:2
0.1
0,3
0.04
0.3
0.09
0.09
0.3
0.12
(a) N relations evaluated after step
(b) At most N ssuper-relations are evaluated on each step
Figure 5: Number of relations need to score by the LLM in (a) the baseline ToG (Sun et al., 2023) and (b) our framework ReKnoS. The numbers on the arrows represent LLM evaluated scores and correspond to LLM computations. For clarity, omit some of the blue nodes.
theorem, know that the selected super-relation path P consists of at least one valid relation path in the knowledge graph. Therefore, this relation path can be used to extract entities that contribute to answering the query.
In Figure 5, we show that for the baseline ToG, the number of LLM calls grows exponentially as / increases. However, for framework ReKnoS, the required LLM calls each step remain constant, indicating the efficiency of our framework. However, one challenge remains- thereethereeee is large number of entities covered by these super-relations, which can make it difficult to find the relevant ones. We describe how to address this issue below.
With these super-relation paths in P we aim to extract the entities that satisfy the con- nection property of these relations. The entity set for the entire super-relation path P (k()) + R( +... + +R(()) R((1)) can be expressed as
Ex(h) {el 3r (k:) 72 (k2) ......7 R((x), such that e1 -) e2
ej.
(9)
This E(4a) contains all of the final entities that satisfy the super-relation path Note that although each super-relation in P can contain multiple relations, the size of E( should be much smaller than P as requires entities on super-relation path to be consecutively connected, which is stricter requirement than having / super-relationn consecutively connected (see Definition 1).
We use the obtained entity set E/ along with the super-relations in to query the LLM regarding the next step. The LLM will either output inferred answer from (kr) decide to continue the process by proceeding to the subsequent super-relations, i.e., repeating the process starting from
Section 4. and increasing the super-relation path length by 1. Notably, when I L, will always ask the LLM for the answer.
EXPERIMENTS
Baselines. For baselines, we compare ReKnoS with several methods, including standard prompting (IO prompt) (Brown et al., 2020), Chain-of-Thouggh prompting (CoT prompt) (Wei et al., 2022), and Self-Consistency (Wang et al., 2023). Additionally, we include previous state-of-the-art (SOTA) approaches tailored for reasoning on knowledge graphs: StructGPT (Jiang et al., 2023b), Think-on- Graph (ToG) (Sun et al., 2023), and KG-Agent (Jiang et al., 2024).
Datasets. To evaluate the performance of our framework on multi-hop knowledge-intensivee reasoning tasks, we conduct tests using four KBQA datasets: CWQ (Talmor & Berant, 2018), WebQSP (Yih al., 2016), GrailQA (Gu et al., 2021), and SimpleQA (Bordes et al., 2015). Among these, three multi-hop reasoning datasets with reasoning path lengths generally larger than one, and one is single- hop reasoning (i.e., SimpleQA) with reasoning paths of length one. Additionally, include one
7

---

Published as a conference paper at ICLR 2025
Table 1: The results (Hits @ in %) of different methods on various Datasets, using GPT-3.5 and Go--io-mini as the LLM. The best results are highlighted in bold.
Dataset
WebQSP GrailQa
CWQ
SimpleQA WebQ
T-REx
zsRE Creak
Hotpot QA
L.M
GPT-3.5
10
63.3
29.4
37.6
20.0
48.7
33.6
27.7
89.7
28,9
Chain-of-Thougle
62.2
28.1
38.8
20.3
48.5
32.0
28.8
90.1
34.4
Self-Consistency
61.1
29.6
45.4
18.9
50.3
41.8
45.4
90.8
35.4
ToG
76.2
68.7
57.1
53.6
54.5
76.4
88.0
91.2
35.3
KG-Agent
79.2
68.9
56.1
50.7
55.9
79.8
85.3
90.3
36.5
StructGPT
75.2
53.9
75.8
86.2
89.5
34.9
ReKnoS (Ours)
81.1
71.9
58.5
$2.9
56.7
78.9
88.7
91.7
37.2
LLM
GPT HPP-44o-inn
ToG
80.7
79.7
65.4
66.1
57.0
77.2
87.9
95.6
38.9
KG-Agent
81.2
77.5
67.0
67.9
56.2
80.6
86.5
96.1
40.1
StruetGPT
79.5
78.2
64.7
63.0
54.5
76.6
88.1
94.9
38.5
ReKnoS (Ours)
83.8
80.5
66.8
67.2
57.6
78.5
88.4
96.7
40.8
open-domain QA dataset, WebQ (Berant al., 2013), slot-filling datasets, T-REx (Elsahar et al., 2018) and Zero-Shot RE (Petroni et al., 2021), one multi-hop complex QA dataset, HotporQA (Yang al., 2018) 8). and one fact-checking dataset, Creak (Onoe et al., 2021). For the larger datasets, GrailQA and SimpleQA, 1,000 samples were randomly selected for testing to reduce computational overhead. For all of the datasets, we use exact match accuracy (Hits as our evaluation metric, consistent with prior studies (Li et al., 2024; Jiang et al., 2023b). We use Freebase (Bollacker et al., 2008) as the KG for CWQ, WebQSP, GrailQA, SimpleQA, and WebQ. We use Wikidata (Vrandečić & Krötzsch, 2014) the KG for T-REx, Zero-Shot RE, HotpotQA, and Creak. The implementation details are provided in Appendix C.
Due to space constraints, some experimental results and discussions deferred to Appendix D.
5.1 COMPARATIVE RESULTS
The Hits@ 1 performance of our ReKnoS framework is evaluated on both GPT-3.5 and GPT-4o-mini across multiple datasets, as shown Table 1. The results highlight several key insights. First, our framework consistently outperforms the basclines across most datasets, particularly in more complex datasets like GrailQA and CWQ. On GrailQA, for example, our framework achieves an accuracy of 71.9% GPT-3.5 and 80.5% on GPT-4o-mini, compared to the best baseline (KG-Agent) with 68.9% and 77.5% accuracy, respectively. This improvement can be attributed to our model's 's more effective integration of reasoning mechanisms and structured knowledge representation, which critical for answering more complex questions.
On simpler datasets, such SimpleQA and WebQ, approach also shows competitive perfor- mance. Although the margin of improvement is smaller compared to other baselines, our framework still surpasses them. For example, on GPT-3.5, our framework achieves 52.9% accuracy on Sim- pleQA, which is higher than KG-Agent's 's 50.7% accuracy, demonstrating the robustness of our framework even on tasks that may not demand intricate reasoning chains.
Furthermore, we observe that the performance gap between our framework and the baselines becomes more pronounced when transitioning from GPT-3.5 5. GoT-io-mini On CWQ, for instance, our framework improves from 58.5% (GPT-3.5) to 66.8% (GPT-4o-mini) accuracy, while the best- performing baseline (KG-Agent) improves from 56.1 % 67.0% accuracy. This suggests that our framework better leverages the increased reasoning and understanding capabilities of GPT-4o-mini, particularly in datasets that require multi-step reasoning, such as CWQ and GrailQA. Morcover, also observe that the baseline KG-Agent performs better on SimpleQA and T-REx using the GPT-4o-mint LLM. This is potentially due to the advanced tool-using capabilities of GPT-4o-mini that can benefit KG-Agent, which performs reasoning
KGs with specialized toolbox.
In conclusion, our results demonstrate the effectiveness and adaptability of our approach across range of datasets, consistently outperforming state-of-the-art baselines. The transition more
8

---

Published as a conference paper at ICLR 2025
Search Space Size
2000
1000
ReKno8
KG-Agent
ToG
Figure 6: The size of the search space (i.e., the number of fact triples encountered during searching) of different methods dataset GrailQA using GPT-3.5, The shape denotes the distribution of the search space sizes across all samples.
advanced language models like GPT-4o-min further amplifies our model's strengths, especially in datasets that require deeper reasoning and knowledge inference.
5.2 EFFECT OF BACKBONE MODELS
In this subsection, we conduct experi- ments to compare the performance of Re- KnoS and the recent baseline ToG using different backbone models to study the impact of model parameter sizes. No- tably, we consider the following LLMs in addition to the two LLMS used Sec. 5.1: Llama-2-7B (Touvron 2023), Mistral-7B (Jiang et al., 2023a), Llama-3-8B (Dubey et al., 2024), and GPT- 4 (Anand et al., 2023). As seen in Table 2, the performance of ReKnoS varies depend- ing on the choice of the underlying back- bone model. First, smaller models, like Llama-2-7B. generally achieve worse re- sults than larger models on all datasets. Nevertheless, the performance improve- ment of ReKnoS over ToG is more sig- nificant smaller models, compared to large models like GPT-4. This indicates that framework significantly better for smaller models that could be easily deployed, making our framework more practical. Moreover, sizes, indicating the advantage of our framework helping smaller models solve complex tasks. Finally, GPT-4, as expected, provides the highest performance across all datasets. This further under- scores the potential of more advanced models like GPT-4 to handle complex, multi-step reasoning tasks and diverse queries, outperforming smaller and less sophisticated models. Nevertheless, smaller models with higher efficiency are valuable in simpler tasks when the inference latency is important.
Table 2: Results (Hits@1 in %) of ReKnoS and ToG on various backbone models on four datasets.
Model
WebQSP GrailQA CWQ SimpleQA
Llama-2-7B
ToG ReKnoS
61.2
60.3
49.8
35.7
64.7
62.2
51.2
41.0
al.,
Mistral-2-7B
ToG
61.9
62.6
50.3
39.2
ReKnoS
62.5
64.3
53.1
45.3
Llama-3-8B
ToG
64.4
63.9
53.2
42.7
ReKnoS
67.9
65.8
56.7
46.4
GPT-4
ToG
82.6
81.4
67.6
66.7
ReKnoS
84.9
82.7
68.2
69.3
framework consistently outperforms ToG models of various parameter
5.3
ANALYSIS
In this subsection, we investigate how the incorporation of super-relations contributes to improved accuracy and running time. As an example, we present the size of the search space of different methods on dataset GrailQA in Figure 6. We observe that our method has the largest search space, with nearly 42% and 55% improvements in average size over the state-of-the-r methods KG-Agent and ToG, respectively. This indicates that with super-relations, search space size when we perform reasoning on a KG. As a consequence, our method can encounter more fact triples and is more likely retrieve the correct one for answering the question.
significantly increase the

---

Published as a conference paper at ICLR 2025
5.4 EFFICIENCY ANALYSIS
LLM calls are the dominant part of the computation; we hence separately analyze LLM calls here. The LLM operations typ- ically require the most time and computa- tional resources in such frameworks, espe- cially when compared to other processes like preprocessing or document retrieval.
Table 3: Comparison of the average number of calls, query times (in seconds), and Hits@1 on the WebQSP and GrailQA datasets using GPT-3.5.
WehQSP
GrailQA
Model
# Calls
Time
Hits @
# Calls
Time Hits@
ToG
15.3
4.9
76.2
18.9
6,8
68.7
Let N and L represent the search width and length, respectively. each reasoning step, ReKnoS calls the L.M twice, where the first one is to score the super-relations, and the second one is to determine whether to proceed to the next reasoning step. Therefore, in this manner, ReKnoS calls the LLM (2L* + 1) times per question, where L* is the final number of reasoning steps used and the other one is to answer the final question. Note that the value of L* can be smaller than the value of L.
StructGPT ReKnoS
11.0
2.0
75.2
13.3
3.5
66.4
7.2
3.7
81.1
10.2
5.1
71.9
The significant advantage of ReKnoS lies in the fact that the number of calls is independent of the width N as we utilize the concept of super-relations. In contrast, ToG searches for each path individually, and the resulting total number L.M calls is upper bounded by 2T. + (ToG calls the LLM twice at each reasoning step for each relation, while also requiring final call for the answer). This reliance on N significantly increases the number of LLM calls needed.
We show the number of LLM calls, average query times, and @its@I for the different methods in Table 3. As seen in the table, ReKnoS achieves the lowest average number of LLM calls while maintaining superior performance, underscoring both its efficiency and effectiveness. Although StructGPT is faster in terms of query times, it suffers from lower accuracy. This trade-off between speed and accuracy further highlights the balance ReKnoS achieves, as it maintains high accuracy without excessively increasing the number of LLM calls.
5.5 HYPER- PHIER-PRRMMEER ANALYSIS
Here, we evaluate how hyper-parameters affect the performance of ReKnoS. We present the results of our framework in Ta- ble 4 with different values of L and N. From the results, we see that increasing both L and N leads to better performance. This because, with larger values of L and N, our framework can retrieve and store more information in the super-relation search path Q. which can contain up to NL super-relations. It is noteworthy that decreasing N from to 1 causes a considerable drop in accuracy. The reduction in Hits @ 1 is substantial. For example, when L = 3. Hits@1 drops from 81.1% with N to 76.2% with N = 1. This indicates that plays a crucial role in the framework's 's perfor- mance, as having fewer super-relations reduces the amount of information available for reasoning, leading to less effective answers.
Table 4: Accuracy and the retrieval rate (Ret.) of Re- KnoS with different typer-parametern using GPT-3.5.
Setting
N =
N = 3
N = 5
Hits@
Ret.
Hits@
Ret.
Hits
Ret.
75.3
57.0
79.2
69.2
79.8
71.3
L 3
76.2
64.3
81.1
69.8
81.8
76.6
L 5
77.3
68.6
82.1
72.9
82,2
76.9
6 CONCLUSION
This paper introduces the ReKnoS framework, which leverages super-relations to involve a large number of relations during reasoning in knowledge graphs. By enabling the representation and exploration of multiple relation paths simultaneously, our approach significantly expands the search space of reasoning paths over knowledge graphs without sacrificing potentially valuable information. Extensive experiments demonstrate the effectiveness of our method, showing that ReKnoS achieves substantial improvements over state-of-the -fee------hhrrrr art baselines. These results underscore the potential of super-relations in advancing complex reasoning tasks in knowledge graph applications. In future work, will apply our work knowledge graphs of other domains and types.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work is supported in part by the MIT-IBM AI Watson Lab, National Science Foundation (NSF) under grants CCF-1845763, CCF-2316235, and CCF-2403237, IIS-2006844, IIS-2144209, IIS- 2223769, CNS-2154960 BCS-2228534, and AMMMI-2411248 the Commonwealth Cyber Initiative (CCI) under grant VV-1Q24-011; Google Faculty Research Award; and Google Research Scholar Award.
REFERENCES
Yuvanesh Anand, Zach Nussbaum, Brandon Duderstadt, Benjamin Schmidt, and Andriy Mulyar. GPT4all: Training an assistant-style chathot with large scale data distillation from GPT-3.5-turbo. GitHub, 2023.
Jonathan Berant, Andrew Chou, Roy Frostig, and Perey Liang. Semantic parsing on freebase from question-answer pairs. In Conference on Empirical Methods in Natural Language Processing, pp. 1533-1544, 2013.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collabora- tively created graph database for structuring human knowledge. In ACM SIGMOD International Conference Management of Data, pp. 1247-1250, 2008
Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. Large-scale simple question answering with memory networks. arXiv preprint SKKV:1506.00077 2015,
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, 13:1877-,901, 2020.
Mohammad Dehghan, Mohammad Alomrani, Sunyam Bagga, David Alfonso-Hermeld Khalil Bibi, Abbas Ghaddar, Yingxue Zhang, Xiaoguang Li, Jianye Hao, Qun Liu, Jimmy Lin, Boxing Chen, Prasanna Parthasarathi, Mahdi Biparva, and Mehdi Rezagholizadeh. EWEK-QA Enhanced web and efficient knowledge graph retrieval for citation-based question answering systems. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 14169-14187, Association for Computational Linguisties, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The Llama herd of models. arXiv preprint arXiv:2407.21788. 2024.
Hady Elsahar, Pavlos Vougiouklis, Arslen Remaci, Christophe Gravier, Jonathon Hare, Frederique Laforest, and Elena Simperl. T-REx: A large scale alignment of natural language with knowledge base triples. In Proceedings of the Eleventh International Conference on Language Resources and Evaluation, 2018
Yu Gu, Sue Kase, Michelle Vanni, Brian Sadler, Percy Liang, Xifeng Yan, and Yu Su. Beyond IID: three levels of generalization for question answering on knowledge bases. In Proceedings of the Web Conference, pp. 3477-3488. 2021.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprini arXiv:2310.06823 2023a.
Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji- Wen. StructGPT: A general framework for large language model to reason over structured data. In Conference on Empirical Methods in Natural Language Processing, pp. 9237-9251, 2023b.
Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, Yaliang Li, and Ji- Rong Wen. ReasoningLMM: Enabling structural subgraph reasoning in pre- trained language models for question answering over knowl- edge graph. In Conference on Empirical Methods in Natural Language Processing, pp. 3721-3735, 2023c.
11

---

Published as a conference paper at ICLR 2025
Jinhao Jiang, Kun Zhou, Xin Zhao, and Ji- Ji-Rong Wen. UniKGQA: Unified retrieval and reasoning for solving multi-hop question answering over knowledge graph. In The Eleventh International Conference Learning Representations, 2023d.
Jinhao Jiang. Kun Zhou, Wayne Xin Zhao, Yang Song, Chen Zhu, Hengshu Zhu, and Ji- Ji-Rong Wen. KG-Agent: An efficient autonomous agent framework for complex reasoning over knowledge graph. arXiv preprint arXiv:2402. /133, 2024.
Zhengbao Jiang, Frank Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi- Yu, Yiming Yang. Jamie Callan, and Graham Neubig. Active retrieval augmented generation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp. 7969-7992, 2023e.
Xingxuan Li, Ruochen Zhao, Yew Ken Chia, Bosheng Ding, Shafiq Joty, Soujanya Poria, and Lidong Bing. Mfain-of-kkowweee Grounding large language models via dynamic knowledge adapting over heterogeneous sources. In The Twelfth International Conference on Learning Representations, 2024.
Linhao Luo, Yuan-Fang Li, Reza Haf, and Shirui Pan. Reasoning on graphs: Faithful and inter- pretable large language model reasoning. In The Twelfth International Conference on Learning Representations, 2024.
Shengjie Ma, Chengjin Xu, Xuhui Jiang, Muzhi Li, Huaren Qu, and Jian Guo. on-Graph 2.0:
Deep and interpretable large language model reasoning with knowledge graph-guided retrieval. arXiv preprint ar arXiv:2407. 240.: 2024.
Costas Mavromatis and George Karypis. GNN-RAG: Graph neural retrieval for large language model reasoning. arXiv preprint arXiv:2405.20133 2024.
Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can a suit of armor conduct electricity? new dataset for open book question answering. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp. 2381-2391, 01 2018.
Yasumasa Onoe, Michael J. Q. Zhang, Eunsol Choi, and Greg Durrett. CREAK: A dataset for com- monsense reasoning over entity knowledge. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, 2021.
OpenAI. ChatGPT: Optimizing language models for dialogue., 2022.
Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. Unifying large language models and knowledge graphs: roadmap. IEEE Transactions on Knowledge and Data Engineering. 2024.
Fabio Petroni, Aleksandra Piktus, Angela Fan, Patrick Lewis, Majid Yazdani, Nicola De Cao, James Thorne, Yacine Jernite, Vladimir Karpukhin, Jean Maillard, Vassilis Plachouras, Tim Rocktaschel, and Sebastian Riedel. KILT: a benchmark for knowledge intensive language tasks. In NAACL-HLT, pp. 2523-2544, 2021.
Robyn Speer, Joshua Chin, and Catherine Havasi. ConceptNet 5.5:
An open multilingual graph of general knowledge. Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Jiashuo Sun, Chengjin Xu, Lumingyuan Tang. Sai Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung yeung Shum, and Jian Guo. Think-on- -n-aphh Deep and responsible reasoning of large language model on knowledge graph. In International Conference on Learning Representations, 2023.
Alon Talmor and Jonathan Berant. The Web as knowledge-baid for answering complex questions. In Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long Papers), pp. 641-651, 2018.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprini arXiv:2307.099 092888 2023.
12

---

Published as a conference paper at ICLR 2025
Denny Vrandečié and Markus Krötzsch. Wikidata: free collaborative knowledgebase. Communica- tions of the ACM, 57)))) 85, 2014.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consisteney improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023.
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-though. prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-2444 2022.
Ran Xu, Hejie Cui, Yue Yu, Xuan Kan, Wenqi Shi, Yuchen Zhuang, Wei Jin, Joyce Ho, and Carl Yang. Knowledge-infused prompting: Assessing and advancing clinical text data generation with large language models. In Findings of the Association for Computational Linguistics: ACL 2024,
pp. 15496-15523, 2024.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Conference on Empirical Methods in Natural Language Processing, 2018.
Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming- Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 206-206, 2016.
Jing Zhang, Xiaokang Zhang, Jifan Yu, Jian Tang, 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 I: Long Papers), pp. 5773-5784, 2022.
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.
A PROOF OF THEOREM 4.1
Theorem 4.1. A super-relation search path leads to at least one super-relation path. Given a selected super-relation search path of length 2i S2.,,,....,5 St), there exists least one super-relation
path of length i.e., P [1( (k1) (k2) + R(((t) where 12(²)) E Sj and kj represents ks, for a fixxe i.
Proof. Let Q = S2, ..) represent a super-relation search path consisting of super-relation
sets, per Definition 3. Each super-relation set S; = {R((), n(?) ...., R. R((S.))) contains multiple super-relations.
According to Definition 3, in each super-relation set S,, there exists at least one super-relation R E S; that connects to a super-relation the next set S other words,
VR S, ER' S1+1 such that R - R'.
This ensures that there are connected super-relations between consecutive sets.
We prove the theorem using induction. As the base case, we observe that according Definition there exists a super-relation super-relation R((1) E S, and another super-relation (/x) E S2 such that:
(k)) + k2k
As the inductive hypothesis, suppose that for a super-relation search path of length 1, where 1 > 2, there exists at least one super-relation path of length - 1. We take one such path
(H)) + (22 + .... + 1 where re(())) E Sj. We take the last super-relation on such
13

---

Published as a conference paper at ICLR 2025
path, R E S1-1- By Definition 3, know that there exists connected super-relation R((a)
St such that:
R 1) R(Aa).
(R((a)
R!!raa ... R - R( Thus,
Then, we can form the super-relation path P we have that every super-relation search path leads to at least one super-relation path, as required.
B PROOF OF THEOREM 4.2
Theorem 4.2. For any super-relation path P (R - R +... - R((a) there exists at least one corresponding KG reasoning path of length 1, represented e₁ =4 e2 '3 3 Ct+ where r; E R( is a relation chosen from the super-relation (k. and 61, e2,,e........ e1+1 are entities in the knowledge graph.
R((K)) need show that there exists corresponding reasoning path in the knowledge graph such that
Proof. Given super-relation path P = (R(
R((aa)
12
e1
E1+1+
where each ry is relation from the super-relation R (k) and the entities 61, c.,..., 61+1 are KG entities.
From Definition 1, we know that each super-relation R₂ is composed of multiple relations, i.e., R, fr.,72.... where ry is standard binary relation between two entities in the knowledge graph. The super-relation R2tt (k) connects to (k2) denoted as (2(k) - R2f2), if there exist entities 61 6g, and Eg such that
+ 62 13
where E R and E (12)
consists of consecutive super-relations that are connected. This means that for each consecutive pair of super-relations (x(htt) and R there exist entities e,, 6i41, and e,42 such that
According to Definition 2, super-relation path [R
R
(kka)
R((ki
et " c++1
ri+1 e,42
where r, R((a) and T4t1 R
(()))))
We proceed by induction on the length of the super-relation path.
Base Case (1 1): For super-relation path of length 1, P (R(*:)), have the super-relation r1 E R2(t (11) and two entities é and 62 such that
F 62
6
This forms a valid KG reasoning path of length 1.
Our inductive hypothesis is that for super-relation path of length 1 1, P (R(hi) R (k- 1) (for > 2), there exists a corresponding KG reasoning path
R (ka)
F2
where each ri (kc) is chosen from the respective super-relation.
14

---

Published as a conference paper at ICLR 2025
Table 5: Evaluation results (Part 1) with average accuracy and standard deviations over five runs.
Model
WebQSP
GrailQA
CWQ
SimpleQA
WebQ
ToG
76.4 + 2.0
68.9 + 1.5
56.2 + 1.8
53.7 + 0.9
54.1 2.5
KG-Agent
78.6 + 1.9
69.4 + 2.1
56.4 + 1.2
52.5 2.7
55.1 - 2.0
ReKnoS (Ours)
81.0 + 1.0
71.2 = 1.5
57.7
+ 0.9
54.1 + 1.0
56.5 1.2
Table 6: Evaluation results (Part 2) with average accuracy and standard deviations over five runs.
Model
T-REx
zsRE
Creak
Hotpot QA
ToG
76.0 1.3
87.5 + 1.0
91.3 + 2.8
35.6 + 2.3
KG-Agent
78.9 + 0.8
86.8 + 1.5
90.3 + 2.5
36.5 + 1.1
ReKnoS (Ours)
79,8 + 1.1
88.3 0.7
91.9
0.9
37.1 + 1.4
Now, consider a super-relation path of length 1, P (R) (n)
R (kt))
R + R kt)
+
+...
From Definition 1, the super-relation R e1+1 such that
+ R exists if and only if there exist entities and
et F c4+1
where ri R ((kx)
Thus, the extended path is
2 62 24
T-1y
24 e14b
which forms valid KG reasoning path of length I, as required.
C IMPLEMENTATION DETAILS
Since our framework is flexible and can be applied to any LLMs, in our experiments, we mainly consider two large LLMs: GPT-3.5 (ChatGPT) (OpenAI, 2022) and GPT-4o-mini (Anand et al., 2023). We additionally consider Llama-2-77 2- (Touvron al., 2023), Mistral-7B (Jiang al., 2023a), Llama-3-8B (Dubey et al., 2024), and GPT-4 (Anand et al., 2023) in Sec. 5.2. We run all of our experiments on one NVIDIA A6000 GPU with 48GB of memory. Across all datasets and methods, we set the width N to 3 and the maximum length T. to 3. When prompting the LLM to score super-relations, we use 3 examples as in-context learning demonstrations, following the existing work on ToG (Sun et al., 2023). The starting entities of each query are provided in the datasets.
D ADDITIONAL RESULTS AND DISCUSSIONS
D.1 ADDITIONAL EVALUATION ANALYSIS
Following the settings of ToG and KG-Agent, we initially did not run multiple rounds of evaluation. To strengthen our analysis, we conducted five additional experimental runs and report the average results along with standard deviations. This ensures that our observed improvements are statistically significant. The results are shown in Table and Table 6.
From these results, we observe slight variations across multiple rounds of experiments. However, ReKnoS consistently achieves the best performance compared to the two state-of-the-arr baselines, highlighting its effectiveness and robustness.
D.2 COMPARISON WITH SUBGRAPHI BASED REASONING METHODS
To further evaluate the effectiveness of proposed ReKnoS framework, conduct additional experiments comparing with subgraph-basee reasoning methods SR (Zhang et al., 2022) and UniKGQA (Jiang et al., 2023d).
15

---

Published as a conference paper at ICLR 2025
Table Performance comparison of subgraph-base reasoning methods and ReKnoS on benchmark KGQA datasets.
Model
WebQSP
GrailQA
CWQ
SimpleQA
SR
68.9
65.2
50.2
48.7
UniKGQA
75.1
68.1
50.7
50.5
ReKnoS
81.1
71.9
58.5
52.9
Table 8: Performance comparison of Hits@ and F1 scores on the WebQSP, GrailQA, and CWQ datasets.
Model
WebQSP
GrailQA
CWQ
Hits 1
F1
Hits@1 1
F1
Hits@
F1
ToG
76.2
64.3
68.7
66.6
57.4
54.5
KG-Agent
79.2
77.1
68.9
65.3
56.1
52.6
ReKnoS
81.1
79.5
71.9
70.2
58.5
56.8
Experimental Setup. While our primary focus is on reasoning methods specifically tailored for large language models (LLMs), we recognize the value of including subgraph- seseraph-bssed reasoning baselines to provide more comprchensive evaluation. Unlike ReKnoS, which leverages super- relations to enhance retrieval and reasoning efficiency for LLMs, subgraph-based approaches operate with different objectives. For instance, UniKGQA employs RoBERTa its encoder, whereas LLM-based methods such as ToG utilize powerful models like GPT--355. Despite these fundamental differences, report the performance of these approaches on four benchmark datasets: WebQSP, GrailQA, CWQ, and SimpleQA. For SR and UniKGQA, we follow the experimental settings in the original papers, and we use GPT-3.5 for our framework.
Results and Discussion. Table presents the comparison between ReKnoS and the subgraph-basee reasoning methods. Our method achieves superior performance across all datasets, demonstrating the effectiveness of leveraging super-relations in KGQA. Notably, ReKnoS outperforms UniKGQA by 6.0 % 3.8 %. 7.8 %, and 2.4% on WebQSP, GrailQA, CWQ, and SimpleQA, respectively while outperforming SR by even more. These results reinforce argument that reasoning methods designed for LLMs can effectively enhance knowledge graph-based question answering.
D.3 ANALYSIS OF HrTs@1 1 vs. F1 METRIC
To comprehensively evaluate the effectiveness of our proposed ReKnoS framework, we compare the use of the @its@1 1 and F1 metries in knowledge graph question answering (KGQA) tasks.
Motivation. While @its@] is commonly used in KGQA benchmarks, the Fl metric may provide additional insights, especially when multiple valid answers exist for given question. However, follow the existing work on ToG (Sun et al., 2023) in primarily reporting Hits 1, as certain datasets in our evaluation, such as T-REx and zsRE, do not involve multiple correct answers per question, making the F1 metric less meaningful in these cases. For single-answer tasks, Hits@ remains the most reliable evaluation metric.
Experimental Results.
Despite the above considerations, acknowledge the value of the F1 metric in datasets where multiple answers exist. Thus, we report both Hits @ and Fl scores for the state-of-the-ar models across three datasets: WebQSP, GrailQA, and CWQ. The results are summarized in Table 8. We use GPT-3.5 for this experiment.
Discussion. From the results in Table 8, we observe that a stronger baseline like KG-Agent does not always maintain better Fl scores. Interestingly, the relatively weaker baseline ToG can demonstrate a more complete answer set, which is useful in scenarios where answer coverage more critical than striet correctness. Notably, ReKnoS consistently outperforms both baselines, achieving the best
16

---

Published as a conference paper at ICLR 2025
Table Comparison of ReKnoS with additional baselines.
Model
WebQSP @its@
GrailQA
F1
@its@) I
Fl
RoG
80.0
70.8
57.8
56.2
GNN-RAG
82.8
73.5
62.8
60.4
ReKnoS
81.1
79.5
58.5
56.8
Table 10: Distribution of non-retrieval cases across datasets.
Dataset
Path Absence
Depth Limit
Misdirection
GrailQA 6.0%
25.2%
68.8%
CWQ
9.2%
43.1% %
47.7%
WebQSP 11.6%
15.9%
72.5%
performance across both the Hits@I and F1 metrics, demonstrating its ability to effectively balance precision and completeness.
These findings highlight that while @its@1 is appropriate for single-answer answer tasks, F1 can be an important complementary metric for tasks with multiple correct answers.
D.4 COMPARISON WITH ADDITIONAL BASELINES
In this subsection, we consider additional baselines that are applicable to the task that we focus on. These methods provide interesting perspectives.
RoG (Luo et al., 2024): RoG is reasoning framework that enhances LLMs with knowledge graphs by using planning-retricee vetrieval-reasoningg approach, where relation paths generated from KGs guide the retrieval of valid reasoning paths, enabling faithful, interpretable, and state-of-the-ae KG reasoning. This method uses
as the L.LM backbone, fine-tuned on the training split of WebQSP, CWQ, and Freebase for 3 epochs.
GNN-RAG (Mavromatis & Karypis, 2024): GNN-RAG a novel RAG framework that combines the reasoning capabilities of Graph Neural Networks (GNNs) with the language understanding abilities of LLMs by extracting KG reasoning paths from a dense subgraph and verbalizing them for LLM-basee KGQA. This method uses LLaMA2- 100MA22-hat-77 Chat-7B as the LLM backbone.
We also considered EWEK-QQ -N (Dehghan et al., 2024), which is enhanced sitation-based QA system that improves knowledge extraction by combining an adaptive Web retriever with efficient knowledge graph (KG) integration. However, this method primarily focuses on citation- based question answering, which diverges from the scope of our work. Additionally, its performance has been reported in Jiang al. (2024) be inferior to the baselines that included. Therefore, did not include this method in the experiments.
From the results presented in Table 9, we observe that GNN-RAG generally achieves better results than ReKnoS on both datasets. This demonstrates the importance of exploiting the structural information in knowledge graphs extract useful knowledge. Nevertheless, despite the strong performance of RoG and GNN-RAG, they require fine-tuning on white-box LLMs, which can be infeasible in specific scenarios where computational resources are scarce. On the other hand, the advantage of ReKnoS is that any black-box LLM can be easily plugged in to the framework.
D.5 BREAKDOWN OF NON-RETRIEVAL CASES ON ADDITIONAL DATASETS
In this subsection, we include the breakdown non-retrieval cases across two additional datasets: WebQSP and CWQ. The results shown in Table 10. From the results, observe that the reasons for non-retrieval cases are distributed differently across datasets. However, the majority of cases still fall under Misdirection, which ReKnoS is designed to address.
17

---

Published as a conference paper at ICLR 2025
Table 11: Evaluation results on datasets without using built-in super-relations.
Method
CWQ
WebQSP
OBQA
MetaQA
StructGPT
55.2
75.2
77.2
81.2
ToG
56.2
76.4
81.0
87.2
ReKnoS (without given super-relations)
57.6
76.9
85.3
92.5
Table 12: Comparison of StructGPT implementations with different numbers of selected relations per step. We include the results for ToG and ReKnoS for reference.
Model
WebQSP Time
GrailQA Time
Calls
Hits @
# Calls
Hits
ToG
15.3
4.9
76.2
18.9
6.8
68.7
StructGPT (3 Relations)
11.0
2.0
75.2
13.3
3.5
66.4
StructGPT (1 Relation)
3.8
1.1
72.7
4.2
1.0
61.7
ReKnoS
7.2
3.7
81.1
10.2
5.1
71.9
D.6 APPLICABILITY BEYOND THE WIKIDATA KNOWLEDGE GRAPH
To further demonstrate the robustness of our method, we conducted additional experiments on two datasets with different knowledge graphs:
OBQA (OpenBookQA)) (Mihaylov et al., 2018) is a multiple-choice signed to assess commonsense knowledge. The utilized KG is ConceptNet (Speer et al., 2017). comprehensive knowledge base covering diverse aspects of everyday knowledge, such as < <rrabbit", CapableOf. "move fast">.
task de-
MetaQA (MoviE Text Audio QA) (Zhang et al., 2018) is a dataset focused on the movie domain, featuring questions where the answer entities can be located up to three hops from the topic entities within a movie KG derived from OMDb.
Both OBQA and MetaQA do not have built-in super-relations. In addition, we removed predefined super-relations from CWQ and WebQSP. The results are shown in Table 11.
The results validate that our approach is effective even in scenarios where relations must be derived dynamically via clustering, without reliance on predefined super-relations. This further reinforces the generalizability and robustness of ReKnoS across diverse KG structures.
D.7 ANALYSIS OF LLM CALLS IN STRUCTGPT
In this subsection, we modified the StructGPT implementation by modifying the number of selected relations per step. The original StruetGPT implementation selects only one relation at time, whereas our modified implementation selects three relations per step, aligning with ToG and ReKnoS. This modification allows StructGPT explore a broader set of candidate relations, thereby improving accuracy (Hits@1)) 1). However, it also increases the number of LLM calls and query time compared to its original implementation.
To provide clearer comparison, present analysis of the trade-off's between the original StructGPT implementation (selecting relation) and our modified implementation (selecting relations). The results summarized in Table 12.
The results illustrate the trade-offs in StructGPT. When selecting only one relation per step. the method reduces query time and the number of LLM calls, but at the cost of slightly lower accuracy @Hits@1) 1). Conversely, when selecting three relations, StructGPT achieves higher accuracy but requires more calls and query time.
18

---

Published as a conference paper at ICLR 2025
Table 13: Performance comparison with and without explicit scoring criteria.
Model
WebQSP
GrailQA
CWQ
ReKnoS
81.0
71.2
57.7
ReKnoS (Explicit Scoring Criteria)
81.9
72.5
58.2
D.8 BENEFITS OF EXPLICIT CRITERIA
In this subsection, integrate explicit scoring criteria to enhance the interoperability of our frame- work. We replace the manual example with the following scoring criteria, which serve as a guideline for the LLMs:
[0.8 1.0]: Highly Relevant
-There is strong logical connection between the relation and the query.
[0.6 0.8]: Strongly Related
-hh relation aligns well with the query and provides substantial relevant information, but it may lack some precision.
[0.4- 0.6]:: Moderately Related
The relation is partially relevant and may provide general background information indirect support for the query.
[0.2 0.4]: Weakly Related
Thee relation has a tenuous connection the query, providing limited or peripheral infor- mation.
[0.0 - -0.2]: Irrelevant
-The relation is unrelated or only tangentially related to the query.
By providing this guideline as an additional input to the LLM, we conduct further experiments and obtain the results shown in Table 13. The results indicate that incorporating explicit scoring criteria improves performance across all three datasets. This suggests that a well-defined guideline can enhance the model's ability to distinguish between different levels of relevance, thereby improving both interpretability and accuracy.
D.9 MITIGATING HALLUCINATION
In this subsection, we discuss the mitigation of the risk of hallucination in our framework. Our framework ensures that all selected super-relations exist within the knowledge graph. First, the candidate selection step explicitly filters super-relations to include only those that are directly connected to previously selected relations in the KG. This design ensures that the reasoning process remains grounded the structure of the KG and prevents the hallucination non-existent relations from influencing the retrieval process. Second, during the scoring step, the LLM is tasked with ranking super-relations for their relevance, but these candidates are pre-selected based on their existence and connectivity in the KG. As result, any hallucinated suggestions by the LLM naturally excluded from the retrieval pipeline.
19


Reviews:
[{"review_id": "5XM9WLRfAk", "reviewer": "Reviewer_7WNT", "summary": "This paper introduces a novel framework, ReKnoS, designed for reasoning over knowledge graphs using super-relations—groups of related connections within a particular domain. A super-relation encompasses various specific relations, effectively summarizing and linking different sections of the graph to support a more holistic exploration of the data.\n\nUsing super-relations, the framework represents multiple relation paths under a single super-relation, enhancing reasoning efficiency. This approach eliminates the need to discard numerous paths, thereby expanding the search space and significantly improving retrieval rates.", "questions": "1. For the reasoning component, could a smaller, fine-tuned language model be used to improve efficiency for individual, straightforward tasks? For instance, in a task where only three relations must be selected from a set of candidates to answer a question, would this approach impact performance?\n\n2. Could these methods be applied to scenarios beyond question answering? For example, might they be used in code generation, where large datasets from GitHub could be structured into a knowledge graph format?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written, with clear and visually appealing graphs. The structure is easy to follow, and complex ideas are effectively explained.\n\n2. The concept of super-relation reasoning is both novel and intuitive, making it easy to understand and engaging. The score-based entity extraction and selection approach is clever, and the entire system, built on LLMs, is practical and straightforward to deploy.\n\n3. Extensive experiments demonstrate the performance improvements achieved by incorporating super-relations into the model.\n\n4. Include efficiency analysis to further demonstrate the strength of the method.", "weaknesses": "There are no major issues with the paper. However, it would be helpful to place Figure 4 on the first page to provide an early overview of super-relations right from the beginning.", "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": "M2aMKKL5Jj", "reviewer": "Reviewer_XLwz", "summary": "The paper introduces ReKnoS, a framework for reasoning over knowledge graphs (KGs) using super-relations. In ReKnoS, super-relations are defined as groups of semantically similar relations within a specific field. The framework uses large language model (LLM) reasoning, similar to prior works such as Jiang et al. (2023b) and Sun et al. (2024). However, instead of relying on standard KG triplets, ReKnoS prompts the LLM to generate candidates with super-relations. This adjustment allows the reasoning process to cover a wider range of paths within the KG, potentially reducing misdirection issues. Additionally, the inclusion of super-relations supports flexible forward and backward reasoning, expanding the search space and potentially improving the accuracy of reasoning paths.\n\nThe paper is clearly written, with well-organized assumptions and a helpful discussion of preliminaries in Section 3 that clarifies design choices. I have a few observations and suggestions below:\n\n1. The concept of super-relations as an abstraction over relations is creative and intuitive. However, its application seems limited to the Wikidata KG. The paper would benefit from discussing whether these improvements could apply to other domains and types of KGQA. Additionally, the reliance on the availability of super-relations is a limitation worth addressing.\n\n2. The evaluation results in Table 1 show some improvement in six out of nine datasets. However, in three cases, the ReKnoS results are mistakenly bolded despite not being the highest values. This may indicate that improvements could be result of randomness within the margin of error, which is not reported in the paper. This small performance gains might also be achievable through hyperparameter tuning, a more thorough analysis would clarify the results in Table 1.\n\n3. The scoring mechanism described in Section 4.2 appears somewhat arbitrary and lacks clarity. It is also not clear how scores are calculated and the prompt example in Lines 243–247 does not mention any scoring criteria. Furthermore, the paper does not present any evidence to indicate whether these scores align with human judgments, which would be beneficial for validating the approach.", "questions": "Suggestions for Improvement:\n1. Consider adding qualitative results to illustrate the benefits of super-relations in ReKnoS, such as examples where super-relations enhanced answer accuracy in specific datasets.\n2. The focus on the GrailQA dataset as motivation for super-relations in Figures 1 and 2 limits the argument for the generalizability of ReKnoS. Including results from additional datasets in these figures would strengthen the paper.\n\nQuestions for the Authors:\n1. Given that the use of super-relations could increase the chance of hallucination in LLMs (e.g., by suggesting relations not present in the KG), did the authors observe any instances of this effect?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "For detailed discussion please check the \"Summary\".", "weaknesses": "For detailed discussion please check the \"Summary\".", "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": "TArjBDzuIH", "reviewer": "Reviewer_gYEF", "summary": "This paper proposes the ReKnoS framework that aims to reason over knowledge graphs with super-relations. To be specific, ReKnoS introduces the concept of super-relations by summarizing and connecting various relational paths within the graph, which enhances the forward and backward reasoning capabilities, and increases the efficiency in querying LLMs. Extensive experimental results demonstrate the effectiveness of the proposed method in increasing the retrieval rate and overall reasoning performance.", "questions": "Please see **Weaknesses** above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper introduces the non-retrieval rate, providing a new insight for evaluating the retrieved path.\n2. The idea behind introducing the super-relations is interesting, which not only expands the search space but also improves the retrieval efficiency.", "weaknesses": "1. It would be beneficial to include some subgraph-based reasoning methods (e.g., SR, UniKGQA and so on) introduced in Section 2 to conduct a comprehensive evaluation of the proposed method.\n2. In Table 3, I have some questions regarding the average number of calls for StructGPT. From my understanding, this method may not require such a high number of LLM calls. It would be helpful to verify this to ensure accuracy.\n3. It would be beneficial to conduct experiments for retrieval rate analysis between the proposed method and other baseline methods, which would better demonstrate the superiority of the proposed method.", "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)