THESEUS

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

THESEUS is a framework for studying multi-hop Knowledge Graph Question Answering (KGQA) as question-conditioned graph navigation.

Rather than evaluating only whether a model reaches the correct answer, THESEUS makes the reasoning process explicit: given a natural-language question, a starting entity, and a knowledge graph, an agent must navigate the graph hop by hop to reach a valid answer.

This formulation enables evaluation of both:

• Answer correctness — did the agent reach the correct answer?
• Path fidelity — did it follow the reasoning trajectory supported by the question?

The resulting trajectories expose the sequence of entities and relations used during reasoning, making it possible to distinguish successful navigation from cases where a model arrives at the right answer through an incorrect or unintended path.

Paper: Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation
Eduin E. Hernandez, Luis F. Garcia, Nurassyl Askar, Sergio A. Diaz, Stefano Rini
arXiv: 2609.14528

---

Resources

This repository is the central landing page for the datasets, adapted models, checkpoints, and evaluation resources used in THESEUS.

Datasets

THESEUS Dataset Releases

Dataset	Description	Resource
KINSHIP	Small controlled navigation-ready KGQA benchmark with 1–3 hop questions, annotated reference reasoning paths, and controlled paraphrases	Hugging Face · GCS mirror
MQuAKE-ST	Large static navigation-ready variant of MQuAKE with 1–4 hop questions, a fixed Wikidata-derived graph, verified relation-chain templates, paraphrases, and single- and multi-answer settings	Hugging Face · GCS mirror

The released datasets use explicit topic entities and materialized KGs so that both terminal-answer quality and executed graph trajectories can be evaluated under a reproducible navigation setting.

Additional Navigation-Ready Benchmarks

We also provide navigation-ready versions of established multi-hop KGQA benchmarks used in our experiments and subsequent evaluations. These datasets were not created by the THESEUS authors. The original dataset sources are linked below alongside the corresponding THESEUS-formatted versions.

Dataset	Original source	THESEUS resource
MetaQA	yuyuz/MetaQA	GCS
PathQuestion (PQ/PQL)	zmtkeke/IRN – PathQuestion	Reconstruction Pipeline
WC2014	zmtkeke/IRN – WC2014	Coming soon

Dataset attribution. These benchmarks retain their original authorship. The linked THESEUS resources provide navigation-ready datasets or reproducible reconstruction pipelines, depending on the availability and redistribution permissions of the original datasets. The PathQuestion reconstruction references the original IRN release through a pinned Git submodule rather than redistributing its data. Please cite the original publications and respect their applicable licensing terms.

Quickstarts and Interactive Navigation

The following Hugging Face Spaces provide dataset quickstarts and an interactive KGQA navigation challenge.

Resource	Description
Kinship Quickstart	Browse QA examples, reference paths, and dataset loading instructions
MQuAKE-ST Quickstart	Explore single- and multi-answer QA records, relation chains, and dataset loading instructions
KGQA Navigation Challenge	Navigate Kinship or MQuAKE-ST graphs manually to answer canonical or paraphrased questions

Adapted Navigation Models

Model	Navigation paradigm	THESEUS implementation
MINERVA	Reinforcement-learning graph navigation	HalcyonSolutions/MINERVA
MultiHopKG	Reinforcement-learning graph navigation adapted from MultiHopKG	HalcyonSolutions/MultiHopKG-NLP
SQUIRE	Sequence-to-sequence path generation	HalcyonSolutions/SQUIRE

Pretrained Checkpoints

Pretrained checkpoints corresponding to the experiments reported in the paper are provided below.

Each released checkpoint page provides the model archives, saved run configurations, evaluation artifacts, SHA-256 checksums, and licensing information.

Model	KINSHIP	MQuAKE-ST Single	MQuAKE-ST Multi	MetaQA
MINERVA	Available	Available	Available	Available
MultiHopKG	Coming soon	Coming soon	Coming soon	Coming soon
SQUIRE	Coming soon	Coming soon	Coming soon	Coming soon

The checkpoint archives preserve the trained model together with the effective configuration and evaluation artifacts from the corresponding experimental run. See the individual checkpoint pages for archive contents, loading instructions, checksums, and license information.

For frozen small language model (SLM) graph navigation, including iterative KGQA navigation and path-fidelity evaluation, see the SLM KGQA navigation project.

---

What is THESEUS?

Traditional multi-hop KGQA evaluation primarily asks whether a system predicts the correct answer. THESEUS instead treats reasoning as an explicit navigation problem:

Natural-language question
          +
     Topic entity
          +
    Knowledge graph
          |
          v
 Question-conditioned
   navigation policy
          |
          v
e0 --r1--> e1 --r2--> ... --rn--> answer
          |
          v
Answer correctness + Path traceability

THESEUS evaluates both:

• Answer ranking: MRR and Hits@1
• Path traceability: PED, RED, F1_SG, and F1_Rel

The adapted models replace their original symbolic query interfaces with natural-language question conditioning while preserving their underlying navigation architectures. The reasoning horizon is separated from the underlying question hop length, allowing questions of different depths to be evaluated under a common traversal budget.

---

Dataset Summary

Dataset	Entities	Relations	Triples	QA setting	Hop lengths	Reference paths
KINSHIP	24	12	112	Single-answer	1–3	Yes
MQuAKE-ST	38,516	665	724,141	Single- and multi-answer	1–4	Yes
MetaQA	43,234	9	134,741	Multi-answer	1-3	No

For KINSHIP and MQuAKE-ST, 1-hop questions are reserved for training in the mixed-hop setting. These releases include explicit reference reasoning paths, enabling evaluation of both terminal-answer correctness and executed trajectory fidelity.

MetaQA provides question-answer supervision but does not include reference reasoning paths.

See the individual dataset pages for construction and preprocessing details, split statistics, licensing, checksums, and machine-readable metadata.

---

Citation

If you use THESEUS, the released datasets, or the evaluation protocol, please cite:

@article{hernandez2026theseus,
  author  = {Hernandez, Eduin E. and Garcia, Luis F. and Askar, Nurassyl and Diaz, Sergio A. and Rini, Stefano},
  title   = {Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation},
  journal = {arXiv preprint arXiv:2609.14528},
  year    = {2026}
}

When using Kinship (KGQA), please also cite the original UCI Kinship work listed on the Kinship_dataset_page

When using MQuAKE-ST, please also cite the original MQuAKE and MQuAKE-Remastered works as listed on the MQuAKE-ST dataset page.

When using the adapted model implementations, please also cite the corresponding original MINERVA, MultiHopKG, or SQUIRE paper.