Graph navigation enables clear step by step question answering
Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation
Computation and LanguageMachine Learning
Summary
Answering complex questions by connecting information in knowledge graphs can be difficult because current systems often skip showing how they arrive at their answers. The authors present a way to treat this problem like a navigation task, where a path of reasoning steps through the graph is made explicit. They improved datasets, evaluation methods, and models to understand natural language questions and trace their answer paths. This approach helps verify that answers come from correct, understandable reasoning chains.
What this means in practice
- •For knowledge graph engineers: Build QA systems that provide explicit, verifiable reasoning paths supporting their multi-step answers in natural language queries.
- •For language technology developers: Improve robustness of question answering tools to varied phrasing by embedding full question semantics into graph traversal agents.
Authors
Eduin E. Hernandez, Luis F. Garcia, Nurassyl Askar, Sergio A. Diaz, Stefano Rini
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.