Tournament on Path: Relation Abstraction and Ranking for Knowledge Graph Reasoning

Abstract

While Knowledge Graph Question Answering (KGQA) leverages Large Language Models (LLMs) toperform complex multi-hop reasoning, existing training-free frame works like Think-on-Graph (ToG) suffer from inherent limitations, including locally scoped pruning, unstable pointwise scoring, and the indiscriminate discarding of valuable candidates through random sampling. To address these challenges, this thesis introduces Tournament on Path (ToP), a novel reasoning framework that enhances relation abstraction and candidate ranking. The proposed framework systematically tackles the baseline’s flaws by implementing an entity-agnostic relation path pruning strategy that captures global path semantics and reduces the search space. To effectively operationalize this, ToP is instantiated into two specific variants. System 1 employs a hybrid lexical-semantic pre-filtering combined with a chunked tournament selection algorithm to stabilize ranking across large candidate pools. System 2 relies on purely semantic pre-filtering and a pairwise tournament selection method, introducing a topic entity masking mechanism to strictly prevent LLMs from answering using unverified internal knowledge. Experimental evaluations across four diverse benchmarks (CWQ, WebQSP, WebQuestions, and GrailQA) demonstrate that both variants consistently outperform the ToG baseline. The results confirm that these strategies not only improve reasoning accuracy but also resolve the "negative scaling" behavior, establishing a computationally efficient and consistently reliable framework for different language models.