Graph structure changes challenge multi-hop knowledge graph navigation
How Benchmark Graph Construction Shapes Multi-Hop KG Navigation: A Controlled Audit of PathQuestion and PathQuestion-Large
Computation and Language
Summary
When computers answer complex questions by exploring knowledge graphs step-by-step, the way the graph is built can make a big difference in how well they find answers. The authors looked closely at two common test sets for this kind of question answering and swapped the smaller, filtered graphs with larger original graphs. They found that larger graphs made it harder for navigation methods to reach the right answers and follow the expected paths, even though the questions stayed the same. This means that the graph’s construction is an important part of the testing setup, not just a background detail.
What this means in practice
- •For natural language processing developers: Design more robust multi-hop question answering models by considering how different graph constructions affect navigation and answer retrieval.
- •For knowledge graph engineers: Improve benchmark design and evaluation of navigation tasks by selecting graph constructions that better reflect real-world graph properties.
Authors
Eduin E. Hernandez, Sergio A. Diaz, Luis F. Garcia, Nurassyl Askar, Stefano Rini
Abstract
Multi-hop knowledge-graph question answering (KGQA) benchmarks are often treated as fixed language-and-reasoning tasks, but for navigation-based methods, difficulty also depends on the graph in which those tasks are instantiated. This makes graph construction a consequential but often entangled part of the navigation task. To isolate this effect, we audit PathQuestion (PQ) and PathQuestion-Large (PQL) as graph-navigation benchmarks under a controlled intervention: we hold questions, topic entities, released answers, released path annotations, and family-level splits fixed while replacing each released task-filtered graph with the larger source KG distributed with the benchmark. Source restoration expands the effective navigation search space and graph-consistent answer and path multiplicity while sharply reducing unguided reachability to released answers. We evaluate whether these structural changes persist across navigation policies using structural references, frozen small-language-model navigation policies, and trained MINERVA policies. Across both frozen and trained policies, restoration substantially reduces released-answer accuracy and trajectory fidelity, while graph-consistent evaluation recovers only part of the loss. These results show that benchmark graph construction is part of the navigation task specification rather than merely an implementation detail and can materially shape measured behavior even when the released QA task is held fixed.