UHop: An Unrestricted-Hop Relation Extraction Framework for Knowledge-Based Question Answering

Zi-Yuan Chen, Chih-Hung Chang, Yi-Pei Chen, Jijnasa Nayak, Lun-Wei KuNAACL 2019 · DOI

Abstract

Knowledge-Based Question Answering (KBQA) often struggles with multi-hop reasoning due to the exponential growth of the search space, leading most models to impose an arbitrary "maximum hop" limit. We present UHop, a novel framework that reframes relation extraction as a transition-based search with an integrated termination decision. This approach reduces search complexity from exponential to polynomial while enabling "unrestricted" hop counts. Evaluated on standard benchmarks and a 10-hop synthetic dataset, UHop demonstrates superior efficiency and maintains near-perfect accuracy on long-path questions where baseline models collapse.

1. Introduction

In KBQA, systems navigate a Knowledge Graph (KG) from a topic entity to an answer entity. Each link represents a "hop." Traditional relation-chain-based models suffer from two primary issues: the horizon problem, where they cannot answer questions requiring more hops than their hard-coded limit (usually 2 or 3), and computational inefficiency caused by exhaustive searching within those limits. UHop addresses these by allowing the model to dynamically decide the path length and when to stop.

2. The UHop Framework

UHop decomposes the task into iterative subtasks, moving step-by-step through the graph rather than evaluating entire chains at once.

Instead of predicting an entire chain, UHop performs single-hop relation extraction at each step. It selects the most likely next relation based on the current entity and the question context. By moving step-by-step, UHop shifts the search space complexity from $O(n^L)$ to $O(n \times L)$, where $n$ is the number of relations and $L$ is the path length.

2.2 Comparative Termination Decision

A key innovation is the implicit "stop" signal. UHop compares the score of the current relation to the scores of all potential subsequent relations. If the current step's score is higher, the model terminates, assuming the destination is reached. This eliminates the need for a separate termination classifier and extra parameters.

Figure 1: Comparison between standard relation-chain extraction and the UHop transition-based framework. UHop iteratively extracts relations and makes termination decisions based on comparative scoring.

2.3 Dynamic Question Representation (DQ)

To prevent loops and maintain focus during long walks, UHop employs an attention mechanism that "de-focuses" parts of the question already addressed by previous hops. This prevents the model from re-extracting the same information and helps mitigate error propagation.

3. Experimental Evaluation

UHop was tested on WebQSP (1-2 hops), PathQuestion (2-3 hops), and a synthetic Grid World dataset designed as a "stress test" for long-path reasoning (up to 10 hops).

3.1 Efficiency and Accuracy

On WebQSP, UHop reduced the candidate relation search space by approximately 30% compared to exhaustive methods while matching or exceeding the accuracy of state-of-the-art models like HR-BiLSTM and ABWIM.

3.2 Long-Path Robustness

The Grid World experiments highlighted UHop's primary advantage. As path lengths increased toward 10 hops, traditional models like MINERVA and Neural LP saw their accuracy plummet. In contrast, UHop variants maintained near 100% accuracy across all hop counts, demonstrating its capability for deep graph traversal.

Figure 2: Performance comparison on the Grid World dataset across varying path lengths. UHop variants maintain near 100% accuracy, significantly outperforming Neural LP and MINERVA as complexity increases.

4. Conclusion

UHop provides a scalable and robust solution for multi-hop KBQA by reframing the problem as a transition-based search. Future work includes incorporating beam search to improve performance in noisy, real-world Knowledge Graphs and addressing length-based overfitting during training to ensure correct termination across all question types.

Summary updated

BibTeX
@inproceedings{chen2019uhop,
  author = {Zi-Yuan Chen and Chih-Hung Chang and Yi-Pei Chen and Jijnasa Nayak and Lun-Wei Ku},
  title = {{UHop: An Unrestricted-Hop Relation Extraction Framework for Knowledge-Based Question Answering}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/n19-1031},
}
Figure