Debate on Graph: a Flexible and Reliable Reasoning Framework for Large Language Models
Jie Ma Zhitao Gao Qi Chai Wangchun Sun Pinghui Wang Hongbin Pei Jing Tao Lingyun Song Jun Liu Chen Zhang Lizhen Cui



    The YMDB catalog: Young massive detached binaries for the determination of high-precision absolute stellar parametersFull version of Tables 2, 3 and 4 are only available in electronic form at the CDS via anonymous ftp to cdsarc.u-strasbg.fr (130.79.128.5) or via http://cdsweb.u-strasbg.fr/cgi-bin/qcat?J/A+A/.
    
    
    Pablo Martín-Ravelo 
    1,2
    Roberto Gamen 
    3,4
    Julia I. Arias 
    1
    André-Nicolas Chené 
    2
    Rodolfo H. Barbá In Memoriam (1962–2021)
    1
    
    Received: 20 June 2024 / Accepted: 05 July 2024
================================================================================================================================================================================================================================================================================================================================



§ ABSTRACT 
Large Language Models (LLMs) may suffer from hallucinations in real-world applications due to the lack of relevant knowledge. In contrast, knowledge graphs encompass extensive, multi-relational structures that store a vast array of symbolic facts. Consequently, integrating LLMs with knowledge graphs has been extensively explored, with Knowledge Graph Question Answering (KGQA) serving as a critical touchstone for the integration. This task requires LLMs to answer natural language questions by retrieving relevant triples from knowledge graphs. However, existing methods face two significant challenges: excessively long reasoning paths distracting from the answer generation, and false-positive relations hindering the path refinement. In this paper, we propose an iterative interactive KGQA framework that leverages the interactive learning capabilities of LLMs to perform reasoning and Debating over Graphs (DoG). Specifically, DoG employs a subgraph-focusing mechanism, allowing LLMs to perform answer trying after each reasoning step, thereby mitigating the impact of lengthy reasoning paths. On the other hand, DoG utilizes a multi-role debate team to gradually simplify complex questions, reducing the influence of false-positive relations. This debate mechanism ensures the reliability of the reasoning process. Experimental results on five public datasets demonstrate the effectiveness and superiority of our architecture. Notably, DoG outperforms the state-of-the-art method ToG by 23.7% and 9.1% in accuracy on WebQuestions and GrailQA, respectively. Furthermore, the integration experiments with various LLMs on the mentioned datasets highlight the flexibility of DoG. Code is available at <https://github.com/reml-group/DoG>.




§ INTRODUCTION

Large Language Models (LLMs), characterized by their substantial parameter amount <cit.> and training on extensive, diverse, and unlabeled data <cit.>, exhibit remarkable proficiency in a wide range of natural language understanding and generation tasks <cit.>. For example, GPT-4 <cit.> demonstrates human-level performance across a majority of professional and academic exams originally intended for humans. However, recent studies <cit.> have revealed that they may suffer from hallucinations in real-world applications due to a deficiency in relevant knowledge.

Knowledge graphs <cit.> are large-scale, multi-relational structures housing a plethora of symbolic facts, such as the triple . The incorporation of these structured facts may tackle the aforementioned issue of hallucinations in LLMs <cit.>. One approach to evaluating the integration of knowledge graphs with LLMs is through Knowledge Graph Question Answering (KGQA) <cit.>, which requires machines to answer natural language questions by retrieving relevant facts from knowledge graphs. Recent works <cit.> primarily follow an iterative inference paradigm, consisting of two steps: (1) identifying the initial entity in the question, and (2) retrieving and refining the inference path iteratively until reaching the answer or obtaining sufficient evidence to answer the question. Although they have achieved significant success, they still suffer from excessively long paths and false-positive relations.


Challenge 1: excessively long paths distracting from the answer generation. Existing methods <cit.> usually feed a lengthy evidence path like {, ⋯,  , ⋯} at the top of Fig. <ref> into LLMs to perform answer generation in a single step, which may make it challenging for LLMs to discern the key points in the path. For instance, LLMs may focus on the tail entity  and employ their internal prior knowledge to generate answers. This will result in answers that appear reasonable but are incorrect.

Challenge 2: false-positive relations hindering the path refinement. Current methods <cit.> typically focus on identifying relations within graphs that closely match or have the same meaning as those in the questions, even if the relations have already been identified in previous reasoning steps. For example, at the top of Fig. <ref>, these methods may select , which was used in the previous reasoning step and is mentioned in the question, to expand paths rather than choosing  when dealing with the entity . This will lead to incomplete evidence paths.

To address these challenges, we propose an iterative interactive KGQA framework that leverages the interactive learning capabilities of LLMs to perform reasoning and Debating over Graphs, dubbed DoG. Unlike existing approaches <cit.> that seek to construct a complete evidence chain before answering questions, our architecture employs a subgraph-focusing mechanism that allows LLMs to perform answer trying after each reasoning step. For each filtered triple, DoG uses LLMs to assess whether sufficient information is available to answer the current question. In this way, the triple in each reasoning step, such as  in the bottom of Fig. <ref>, can be deeply pondered by LLMs. If the triple does not support answering the current question, DoG employs a multi-role LLM team to debate and simplify the question based on the triple. The iterative process allows complex multi-hop questions to be gradually transformed into single-hop questions, which enables LLMs not to be disturbed by the relation that is retrieved in the previous reasoning step. For example, the relation  that is linked with  will not disturb reasoning after the simplification procedure 173. This is inspired by the human brain in tackling complex questions, which guides LLMs to reason on graphs through chain-of-thought <cit.>. The simplification process can also enhance the transparency of the reasoning process. 

To verify the effectiveness and superiority of our architecture, we conduct thorough experiments on five public KGQA datasets: MetaQA <cit.>, WebQSP <cit.>, CWQ <cit.>, WebQuestions <cit.>, and GrailQA <cit.>. Our findings show that DoG achieves state-of-the-art results on all datasets, except for the 2-hop and 3-hop questions within MetaQA. Notably, DoG outperforms the strong baseline ToG <cit.> by 23.7% and 9.1% in accuracy on WebQuestions and GrailQA, respectively. In summary, our contributions are threefold.

    
  * We propose a flexible and reliable reasoning framework, DoG, which enables LLMs to reason and debate over knowledge graphs and answer questions after thorough deliberation.
    
  * We introduce a strategy, which transforms questions from complex to easy through the interactive learning of a multi-role LLM team, for handling complex reasoning on knowledge graphs. This guides LLMs to engage in step-by-step reasoning, thereby enhancing the reliability of the reasoning process.
    
  * Extensive experiments and ablation studies are carried out on five public datasets to demonstrate the effectiveness and superiority of our architecture. Furthermore, we also conduct integration experiments with various LLMs to verify the flexibility of DoG.




§ RELATED WORK


The methods of LLM reasoning over knowledge graphs can be classified into batch triple recalling, and reasoning path refining from the perspective of evidence gathering.

Batch triple recalling. Knowledge graphs typically store an extensive amount of facts <cit.>. For instance, Freebase <cit.> contains over 1.9 billion triples, and even the smaller non-open-domain MetaQA <cit.> includes over 130,000 triples. The number of relevant triples can be substantial even when constrained by the entities in a given question. Injecting all these triples into the context window of LLMs to perform reasoning not only incurs a high encoding cost but also introduces significant noise <cit.>. To address this issue, previous studies <cit.> focus on how to filter suitable facts. For instance, KAPING <cit.> projects questions and triples into the same space to obtain relevant knowledge by semantic similarity. KG-GPT <cit.> further focuses on fine-grained question representations, decomposing multi-hop questions into sub-questions and matching the relations associated with entities in those sub-questions, then selecting the top-k relevant relations to form evidence triples. Similarly, KGR <cit.> splits the retrieved triples into several chunks and utilizes LLM to distinguish the critical triple relevant with questions.

Reasoning path refining. The paradigm of this kind of method <cit.> is first to identify the initial entity in the question, then to iteratively retrieve and refine the reasoning path until reaching the answer or obtaining sufficient evidence to answer the question, and finally to employ LLMs to generate answers based on the refined path. For example, <cit.> proposed an iterative reading-reasoning approach, which iterates an invoking-linearization-generation procedure. It utilizes LLMs to perform reasoning on the interface that is specifically designed for reading structured data until deriving the final answer. Similarly, <cit.> introduced a deep and responsible reasoning framework, which first conducts a beam search on a graph from the entity within questions and then acquires multiple reasoning paths as evidence for answer generation. It is noteworthy that these methods all treat the LLM as a tool for accomplishing specific tasks, conceptualizing it as function executors, and relying on in-context learning <cit.> or fine-tuning to refine its outputs <cit.>. However, some studies <cit.> have demonstrated that LLMs can be induced to exhibit human personality traits and role distinctions to undertake complex reasoning tasks.

Communicative Agents. The primary objective of agents is to collaboratively address complex tasks in a productive and efficient manner through autonomous communication and negotiation <cit.>. LLMs such as ChatGPT and Vicuna <cit.> are frequently employed as these communicative agents. Recently, numerous studies have investigated the application of these agents in various domains, including AI societies <cit.>, software development <cit.>, translation <cit.>, arithmetic problem-solving <cit.>, dialogue response generation <cit.>, and strategic planning among robots <cit.>. Specifically, <cit.> guided ChatGPT to emulate expert system reviewers, thereby improving the quality of its literature retrieval queries. <cit.> introduced a strategically designed role-playing prompt method to enhance reasoning abilities by assigning appropriate expert roles for tasks. Additionally, <cit.> assessed the changes in decision-making abilities when LLM assumes different personality traits. Inspired by these studies, we explore the benefit of multi-agent role differentiation and debates for complex reasoning on knowledge graphs.



§ METHOD




 §.§ Task Formulation

Given a knowledge graph 𝒢 consisting of N triples, represented as { (e_i^l, r_l, e_i+1^l) | e_i ∈ℰ, r_l ∈ℛ, i ∈ [1, I], l ∈ [1, L] }, where e_i^l and e_i+1^l denote the head and tail entity, respectively, I is the number of entities, L denotes the number of relations, and r_l is the relation between entities, KGQA requires machines to answer natural language questions q based on retrieved evidence paths P = {p_j}_j=1^m with p_j representing a triple and m denoting the number of triples. In this paper, we leverage LLMs to reason over P and generate answers â word by word.



 §.§ Overview

As depicted in Fig. <ref>, given a K-hop question q and the initial topic entity e_i^l within q, our framework first invokes knowledge graphs to retrieve the set of candidate relations R linked to e_i^l. Then, it enables LLMs to filter out the most relevant relation r̂_l from R based on in-context learning. Subsequently, the knowledge graph is invoked again to complete the triple information from (e_i^l, r̂_l, ?) to (e_i^l, r̂_l, e_i+1^l). Fourthly, DoG focuses on the current reasoning state and employs LLMs to decide on the subsequent action based on the completed triple: providing a direct answer to the question or performing deep thinking with further iterations. In the latter scenario, a multi-role LLM team leverages the mentioned triple to transform the K-hop question to a K-1 hop (slightly easier) one through debate, with the tail entity e_i+1^l being the subsequent topic entity for the simplified question in the next iteration. All of these debate steps are autonomously executed by the LLM team. The iteration will be ended until LLMs generate answers in the fourth step.




 §.§ Knowledge Graph Invoking

Reasoning on graphs requires LLMs first to identify relevant knowledge triples. To facilitate this, we have designed two interactive interfaces specifically tailored to retrieve these triples from knowledge graphs. The interfaces are invoked as needed, depending on the requirements.

    
  * get_relations(e_i^l): This interface is designed to retrieve the candidate relation set R associated with the entity e_i^l. For example, in Fig. <ref>, it is invoked to retrieve the candidate relation set of .
    
  * triple_filling(e_i^l, r̂_l): This interface is responsible for obtaining the tail entity e_i^l, r̂_l, ? given the head entity and the filtered relation. We will introduce relation filtering in the next subsection.

The underlying mechanisms of these interfaces are implemented through either SPARQL (for Freebase queries) or specific matching (for questions in MetaQA). To facilitate comprehension and generation by LLMs, all entities and relationships above the interfaces are expressed in natural language, with the conversion between a Machine ID (MID) and a corresponding friendly name carried out exclusively within the interfaces. The MID facilitates efficient access to comprehensive details related to the entity. More specifically, in Freebase, the MID is a unique identifier assigned to each entity, allowing for straightforward retrieval of entity-specific information. The friendly name of the MID is a natural language descriptor. For example, the MID of the friendly name  is m.03_r3.








 §.§ Relation Filtering

Through get_relations(e_i^l), we obtain a candidate relation set R associated with the initial entity in the question. Subsequently, DoG selects the optimal relation r̂_l from this set through in-context learning. The prompt and in-context examples are detailed in the In-context Learning subsection of the appendix. Specifically, DoG first utilizes LLMs to identify the first-hop problem to be solved in the given question q. Then, it allows LLMs to choose the optimal relation according to the mentioned sub-question. This serves as a guiding principle for relation selection, avoiding the constant reliance on the complete multi-hop question throughout the entire reasoning stage, as seen in previous studies <cit.>. We believe this short-sighted greedy strategy can guide a correct progression on the graph, alleviating the need to account for future inferential information regarding the multi-hop question. For example, for the question in Fig. <ref> “In what year was the movie Joe Anderson starring in released”, the first-hop question to be addressed is “Which film starred Joe Anderson?”. The linearized relation set is {; ; } (“∼” represents a passive relationship), from which the optimal relation  can be easily selected.




 §.§ Answer Trying

After obtaining the optimal relation, our architecture invokes the triple-filling interface triple_filling(e_i^l, r̂_l) to acquire a complete triple, such as  in Fig. <ref>. Then, DoG utilizes LLMs to determine whether the retrieved triple can sufficiently support answering the question. If the triple is insufficient, DoG prompts LLMs to deeply contemplate the current question based on the provided triple. This allows DoG to generate answers based on a single triple, thus avoiding excessively long and potentially confusing paths composed of multiple triples. The prompt and in-context examples are detailed in the In-context Learning subsection of the appendix. Notably, if the maximum iteration limit is reached without successfully generating an answer, the parameterized knowledge of LLMs is utilized to respond.




 §.§ Question Simplifying

Once LLMs determine that a question is unanswerable with the current retrieved triple, it represents that further exploration is required. Inspired by how humans tackle complex questions, our architecture employs a question-simplifying strategy to transform questions from K hop to K-1 hop based on the retrieved triple. Specifically, DoG utilizes a team of agents with distinct roles to engage in debate, ensuring the reliability of the reasoning process. The debate team consists of three roles.



    
  * Question simplifying expert (R1). This expert provides initial simplifications for questions, which may contain apparent errors. For example, the original question in Fig. <ref> is initially simplified as “What are some notable films in which Joe Anderson has acted?". This is far from the intention of the original question.
    
  * Critic (R2). The critic examines the simplification efforts of the above expert and offers suggestions for modifications. For instance, the above question is modified into “When did High Life which was starred by Joe Anderson release?".
    
  * Linguist (R3). This role ensures that the simplified question is not only semantically correct but also free from redundant information of previously resolved sub-questions. For example, the mentioned question is further refined to “When did [High Life] release?".
    

Due to the interdependency and progressive nature of the roles played by the three agents, DoG employs a one-by-one discussion strategy <cit.>. Each agent, implemented by ChatGPT, takes turns contributing to the ongoing optimization of the simplified question, with the statements made by other agents serving as references for guiding subsequent remarks generation. After simplification, we obtain a slightly easier K-1 hop question, prompting LLMs to undergo iteration once again. In this way, the relation in the first-hop sub-question is removed in the simplified question, effectively avoiding the impact of false positive relations. The iteration process, from knowledge graph invocation to question simplification, continues until LLMs make an answerable decision in the answer-trying module. The prompt and in-context examples are shown in the In-context Learning subsection of the appendix.



§ EXPERIMENTS



 §.§ Dataset and Evaluation

We select five public datasets to evaluate the reasoning ability over knowledge graphs: MetaQA <cit.>, WebQSP <cit.>, CWQ <cit.>, WebQuestions <cit.>, and GrailQA <cit.>. MetaQA comprises a movie ontology derived from the WikiMovies dataset <cit.> and contains three sets of natural language question-answer pairs: 1-hop, 2-hop, and 3-hop. WebQSP contains questions sourced from the WebQuestions dataset, which are answerable using Freebase. CWQ is designed for answering complex questions that require reasoning over multiple web snippets. GraiQA, which tests three-level generalizations including i.i.d., compositional, and zero-shot, covers 3,720 relations and 86 domains from Freebase. Following <cit.>, we uniformly sample 500 instances per type for the mentioned five datasets to reduce computational cost. We use  (Hits@1) to evaluate the reasoning performance of our framework and baselines following previous works <cit.>. For the experiment of integrating DoG with GPT-4, we uniformly sample only 100 instances per type from the mentioned datasets to reduce costs.



 §.§ Implementation Settings

We preprocess the MetaQA dataset to construct a structured knowledge graph, facilitating subsequent query and retrieval operations. A local Virtuoso server is deployed for datasets derived from the Freebase. We utilize the OpenAI API to call ChatGPT (gpt-3.5-turbo-0125) and GPT-4 (gpt-4-0613). Additionally, we employ Qwen-14B and Llama-3-8B, running on 8 V100 GPUs, to verify the flexibility of DoG. The maximum number of debate rounds for the multi-agent team is limited to three, with only the best unique relation being recalled. We implement in-context learning across multiple modules: specifically, 10 exemplars for Relation Filtering and Answer Trying, and one exemplar for Question Simplifying.




 §.§ Baselines

Inspired by <cit.>, we compare DoG with previous state-of-the-art supervised learning and in-context learning-based methods, to verify its effectiveness and superiority. Supervised learning: KV-Mem <cit.>, GraftNet <cit.>, PullNet <cit.>, EmbedKGQA <cit.>, NSM <cit.>, TransferNet <cit.>, UniKGQA <cit.>. In-context learning: StructGPT <cit.>, KG-GPT <cit.>, KB-BINDER <cit.>, ToG <cit.>. The baselines are detailed in the Baseline Introduction subsection of the appendix.



 §.§ Reasoning on Knowledge Graphs



  §.§.§ Main Result
 Table <ref> presents a comparison across five public datasets. Taking GPT-3.5 as an example, we observe that DoG enables it to achieve competitive results on MetaQA and the best results on the other four datasets compared with baselines. Specifically, DoG outperforms the best-supervised method, UniKGQA, by 11.4% on WebQSP. Additionally, it surpasses the best in-context learning method, ToG, by 23.7% and 9.1% on WebQuestions and GrailQA, respectively. These datasets comprise complex and compositional questions. Therefore, these results not only highlight the effectiveness and superiority of DoG but also confirm its capability for complex reasoning.



  §.§.§ Flexibility Verification
 We conduct experiments on the aforementioned datasets to explore whether DoG enables other LLMs, including QWen, Llama, and GPT-4, to achieve complex reasoning on knowledge graphs. Experimental results in Table <ref> show that DoG facilitates improvements in some cases compared to GPT-3.5. Specifically, DoG with Llama achieves a 1.6% improvement on WebQSP. It also allows GPT-4 to achieve the most significant improvement on the mentioned datasets. These results clearly demonstrate the flexibility and effectiveness of our architecture. We observe that the performance of DoG with Qwen is slightly lower than with other LLMs. This could be attributed to its marginally weaker complex reasoning capabilities compared to other LLMs.



 §.§ Ablation Studies


We conduct ablation experiments on the aforementioned datasets to analyze the contribution of each component of DoG. The ablation results for DoG with GPT-3.5 are presented in Table <ref>. We perform experiments on the 2-hop and 3-hop splits of MetaQA, as the 1-hop questions do not require complex reasoning. Row 1 shows the results without the subgraph-focusing and question-simplifying components. In other words, this configuration allows LLMs to answer complex questions directly after collecting the whole set of evidence triples, rather than reasoning step by step. We observe a significant performance decrease compared to the results in Row 4, strongly demonstrating the effectiveness of the mentioned modules. Rows 2 and 3 aim to verify the contribution of the expert role in the debate team. The results show consistent improvements across five public datasets, suggesting that each agent plays a critical role in simplifying questions. This also highlights the importance of transforming complex questions into simpler ones for LLMs step-by-step reasoning on knowledge graphs. Row 5 aims to verify the necessity of the debating process, where the tasks of the three roles are performed by a single agent. The average result decreases by 10.3% compared to Row 4, strongly supporting the effectiveness of the debating mechanism.





 §.§ Analyses for Debate Rounds

We conduct experiments to explore how the number of debate rounds affects LLM reasoning on knowledge graphs. Fig. <ref> shows the performance trend of DoG with GPT-3.5 as the number of debate rounds increases across the five datasets mentioned. We observe that DoG achieves the best results on the majority of datasets with just a single round of debates. Additionally, increasing the number of debate rounds leads to a performance decrease in some datasets. DoG utilizes a one-by-one discussion strategy, which makes each agent aware of the historical debate record. This makes the agents more susceptible to being influenced by the views of others, potentially leading to inaccurate decisions for question simplifications. We may also conclude that the agent is sufficiently strong to achieve the goal of instructions without needing iterative debates.



 §.§ Exemplar Impacts

DoG leverages in-context learning to guide LLMs in performing relation filtering, question simplification, and answer trying during iterative reasoning. Specifically, DoG provides instructions and exemplars to help LLMs achieve these objectives. We conduct experiments on five public datasets to explore the impact of the number of exemplars on LLM reasoning. Fig. <ref> shows the analyses for the mentioned three modules. In Relation Filtering, we observe that reasoning performance improves as the number of exemplars increases in the majority of datasets. However, reasoning errors caused by relation filtering account for a large proportion, which we will discuss in the next subsection. In Question Simplifying, the performance improvement is not significant with the increase in the number of exemplars, likely due to the complexity of this task. Converting questions from complex to simple step-by-step may be challenging for LLMs, and they may not be able to infer strategies for addressing this issue from exemplars. In Answer Trying, we see that reasoning performance improves with the increase in the number of exemplars in most cases. In summary, the number of exemplars plays a critical role in decision-making, especially for less complex tasks. In contrast, for more complex tasks, detailed instructions may have a greater impact on LLM reasoning.




 §.§ Error Analyses

To analyze the deficiency of DoG, we randomly select 50 failure cases from each dataset, including MetaQA, WebQSP, and GrailQA, for manual inspection. Fig. <ref> shows the proportion of factors contributing to these errors. We observe that relation filtering errors are quite common. This may be caused by too many relations linked to the entities in questions, making it difficult for LLMs to accurately filter the most relevant relation. Iteration stopping errors denote LLMs make inaccurate decisions in the answer-trying module, either terminating the iterative reasoning too early or too late. This type of error is particularly prevalent in GrailQA cases. Answer aliasing errors mean the generated answers do not have the same description or wording as the annotations, even though they are semantically consistent. This error can be mitigated by introducing a rich collection of aliases. Answer generation errors refer to that LLMs provide incorrect answers based on accurately retrieved triples and simplified questions. Question simplifying errors represent that LLMs fail to transform questions from complex to easy. Additionally, other errors account for 4% of the failure cases in each dataset. This type of error often occurs due to API access issues, an excessively long context, or exceeding the token limit per minute. More details can be found in the Failure Cases subsection of the appendix.



§ CONCLUSION AND FUTURE WORK

This paper proposes an iterative interactive framework, DoG, for knowledge graph question answering. It leverages the interactive learning and reasoning capabilities of LLMs to perform debating on knowledge graphs. Specifically, it employs a team of multi-role agents to transform questions from complex to simple, enabling LLMs to perform reliable step-by-step reasoning based on the retrieved knowledge triples. Extensive experiments across five public datasets demonstrate the effectiveness and superiority of DoG in the few-shot setting, outperforming nearly all in-context and supervised learning-based baselines. Additionally, the integration results with different LLMs verify its flexibility. In the future, we will explore enhancing relation filtering performance from knowledge graphs given the entity of questions.





§ APPENDIX



 §.§ In-context Learning

Table <ref> shows the prompt, instruction, and exemplar utilized in the module within DoG.





 §.§ Baseline Introduction

The brief introduction of supervised-based baselines is as follows.

    
  * KV-Mem <cit.> is a key-value memory network that enhances the viability of reading knowledge sources, such as documents or knowledge bases, by utilizing different encodings during the addressing and output stages of the memory read operation. 
    
  * GraftNet <cit.> aims to provide answers based on a question-specific subgraph that includes text, entities, and relations. It employs heterogeneous update rules to handle knowledge base nodes differently from text nodes and utilizes a directed propagation method to constrain the propagation of embeddings within the graphs.
    
  * PullNet <cit.> builds on the early GraftNet system but focuses on learning how to construct the subgraph. Unlike GraftNet, PullNet leverages a limited set of retrieval operations, with each operation expanding a graph node by acquiring new information from knowledge bases or corpora.
    
  * EmbedKGQA <cit.> is the first work that utilizes knowledge graph embeddings to perform multi-hop question answering over sparse knowledge graphs.
    
  * NSM <cit.> is a teacher-student network in which the student network aims to retrieve the correct answer to a question, while the teacher network learns intermediate supervision signals to enhance the reasoning capacity of the student network.
    
  * TransferNet <cit.> is an effective and transparent model for multi-hop question answering that supports both label and text relations within a unified framework. TransferNet traverses entities across multiple steps. During each step, it focuses on different parts of the question, calculates activation scores for relations, and subsequently propagates the prior entity scores along these activated relations in a differentiable manner.
    
  * UniKGQA <cit.> is a unified model designed for multi-hop question answering. It comprises a semantic matching module, leveraging a pre-trained language model for question-relation semantic matching, and a matching information propagation module that propagates this information along directed edges within knowledge graphs.


The brief description of in-context learning-based baselines is as follows.

    
  * StructGPT <cit.> provides a specialized interface for gathering relevant evidence from structured data and utilizes large language models (LLMs) to focus on the reasoning task using the collected information. Specifically, it employs a linearization-generation procedure to enable LLMs to reason effectively on structured data, facilitated through the interface.
    
  * KG-GPT <cit.> is a multi-purpose framework leveraging LLMs for tasks employing KGs. Specifically, it comprises three steps: sentence segmentation, graph retrieval, and inference, each aimed at partitioning sentences, retrieving relevant graph components, and deriving logical conclusions, respectively.
    
  * KB-BINDER <cit.> is a unified, training-free framework that uses LLMs to generate logical forms for specific questions by mimicking a few demonstrations, and then grounds these forms on a knowledge base using BM25 score matching.
    
  * ToG <cit.> treats LLMs as agents that interactively explore relevant entities and relations on knowledge graphs, enabling them to perform reasoning based on the retrieved knowledge.




 §.§ Failure Cases

Fig. <ref> illustrates the error case that has been analyzed in the Error Analysis subsection.


