Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation

• URL: http://arxiv.org/abs/2609.14528v1
• Date: Sun, 13 Sep 2026 14:06:43 GMT
• Title: Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation
• Abstract summary: Multi-Hop Knowledge Graph Question Answering tasks require models to assemble relational evidence along paths in a KG to answer natural-language questions.<n>We re-frame multi-hop KGQA as a question-conditioned graph navigation problem.<n>In this setting, an agent receives a KG, a question, and a topic entity, and traverses a sequence of relations towards the answer, making the reasoning path explicit.
• Score: 11.103813686369685
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-Hop Knowledge Graph Question Answering (KGQA) tasks require models to assemble relational evidence along paths in a KG to answer natural-language questions. However, existing KGQA systems typically focus on predicting the final answer without explicitly modeling or validating the intermediate reasoning steps, obscuring whether the correct answers arise from faithful multi-hop reasoning. To address this limitation, we re-frame multi-hop KGQA as a question-conditioned graph navigation problem. We refer to this formulation as THESEUS - Traceable Hop-wise Evidence SEarch in a Unified Semantics. In this setting, an agent receives a KG, a question, and a topic entity, and traverses a sequence of relations towards the answer, making the reasoning path explicit. To systematically study this formulation, we provide three key contributions. (i) We augment the existing KINSHIP and MQuAKE resources into navigation-ready KGQA datasets with annotated evidence paths and paraphrased questions. (ii) We design evaluation protocols to measure path fidelity, robustness to linguistic variation, and performance across multi-hop and multi-answer questions. (iii) We adapt established path-based KG completion agents - MINERVA, MultiHopKG, and SQUIRE - to operate on full question embeddings rather than symbolic single-relation queries, enabling their trajectories to be guided by natural-language semantics. Together, these contributions advance KGQA research toward systems where traceability is fundamental: answers are accompanied by explicit reasoning paths whose agreement with reference evidence can be systematically evaluated.

Related papers

• PathISE: Learning Informative Path Supervision for Knowledge Graph Question Answering [35.58843209572786]
  We propose PathISE, a novel framework for learning high-quality intermediate supervision from answer-level labels.<n>Extensive experiments on three KGQA benchmarks show that PathISE achieves competitive or state-of-the-art KGQA performance.
  arXiv  Detail & Related papers  (2026-05-11T16:21:47Z)
• Question-Aware Knowledge Graph Prompting for Enhancing Large Language Models [51.47994645529258]
  We propose Question-Aware Knowledge Graph Prompting (QAP), which incorporates question embeddings into GNN aggregation to dynamically assess KG relevance.<n> Experimental results demonstrate that QAP outperforms state-of-the-art methods across multiple datasets, highlighting its effectiveness.
  arXiv  Detail & Related papers  (2025-03-30T17:09:11Z)
• Learning Federated Neural Graph Databases for Answering Complex Queries from Distributed Knowledge Graphs [53.03085605769093]
  We propose to learn Federated Neural Graph DataBase (FedNGDB), a pioneering systematic framework that empowers privacy-preserving reasoning over multi-source graph data.<n>FedNGDB leverages federated learning to collaboratively learn graph representations across multiple sources, enriching relationships between entities, and improving the overall quality of graph data.
  arXiv  Detail & Related papers  (2024-02-22T14:57:44Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  Multi-hop Question Answering over Knowledge Graph(KGQA) aims to find the answer entities that are multiple hops away from the topic entities mentioned in a natural language question. We propose UniKGQA, a novel approach for multi-hop KGQA task, by unifying retrieval and reasoning in both model architecture and parameter learning.
  arXiv  Detail & Related papers  (2022-12-02T04:08:09Z)
• Exploiting Hybrid Semantics of Relation Paths for Multi-hop Question Answering Over Knowledge Graphs [31.088325888508137]
  This paper proposes improving multi-hop KGQA by exploiting relation paths' hybrid semantics. We integrate explicit textual information and implicit KG structural features of relation paths based on a novel rotate-and-scale entity link prediction framework.
  arXiv  Detail & Related papers  (2022-09-02T08:07:37Z)
• Path-Enhanced Multi-Relational Question Answering with Knowledge Graph Embeddings [16.21156041758793]
  We propose a Path and Knowledge Embedding-Enhanced multi-relational Question Answering model (PKEEQA) We show that PKEEQA improves KBQA models' performance for multi-relational question answering with explainability to some extent derived from paths.
  arXiv  Detail & Related papers  (2021-10-29T08:37:46Z)
• Improving Embedded Knowledge Graph Multi-hop Question Answering by introducing Relational Chain Reasoning [8.05076085499457]
  Knowledge Base Question Answer (KBQA) to answer userquestions from a knowledge base (KB) by identifying reasoning between topic entity and answer. As a complex branchtask of KBQA, multi-hop KGQA requires reasoning over multi-hop relational chains preserved in structured KG.
  arXiv  Detail & Related papers  (2021-10-25T06:53:02Z)
• Improving Unsupervised Question Answering via Summarization-Informed Question Generation [47.96911338198302]
  Question Generation (QG) is the task of generating a plausible question for a passage, answer> pair. We make use of freely available news summary data, transforming declarative sentences into appropriate questions using dependency parsing, named entity recognition and semantic role labeling. The resulting questions are then combined with the original news articles to train an end-to-end neural QG model.
  arXiv  Detail & Related papers  (2021-09-16T13:08:43Z)
• Dynamic Semantic Graph Construction and Reasoning for Explainable Multi-hop Science Question Answering [50.546622625151926]
  We propose a new framework to exploit more valid facts while obtaining explainability for multi-hop QA. Our framework contains three new ideas: (a) tt AMR-SG, an AMR-based Semantic Graph, constructed by candidate fact AMRs to uncover any hop relations among question, answer and multiple facts, (b) a novel path-based fact analytics approach exploiting tt AMR-SG to extract active facts from a large fact pool to answer questions, and (c) a fact-level relation modeling leveraging graph convolution network (GCN) to guide the reasoning process.
  arXiv  Detail & Related papers  (2021-05-25T09:14:55Z)
• QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering [122.84513233992422]
  We propose a new model, QA-GNN, which addresses the problem of answering questions using knowledge from pre-trained language models (LMs) and knowledge graphs (KGs) We show its improvement over existing LM and LM+KG models, as well as its capability to perform interpretable and structured reasoning.
  arXiv  Detail & Related papers  (2021-04-13T17:32:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.