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

1 Introduction

• Relation-chain methods face nearly infinite relation combinations and exponentially growing candidate paths, so they restrict paths to one, two, or three hops and may miss indirect or complicated questions.KBQA separates topic-entity linking from relation extraction, which finds the path to answer nodes.Source: §1 · p. 1
• Large hop limits are difficult to set in advance for real-world questions, and they require lengthy training instances that are especially difficult.Even exhaustive search cannot reach an answer that lies outside its search space.Source: §1 · p. 1
• UHop decomposes relation extraction into single-hop relation extraction and a decision about when to halt, requiring no predefined maximum hop number.The framework reduces search-space complexity from exponential to polynomial while maintaining comparable results and facilitating use of different models.Source: §1 · pp. 1–2

2 Related Work

• Semantic-parsing systems provide deep question interpretation but require expensive annotation or reinforcement-learning training, while embedding methods may predict answers directly or extract paths for later answer selection.Semantic parsing turns questions into logical forms used to query the knowledge graph.Source: §2 · p. 2
• Relation-chain approaches focus on predicting relation paths but assume a maximum hop count, which UHop seeks to eliminate.UHop follows methods that predict paths rather than answers directly.Source: §2 · p. 2
• Multi-hop reasoning methods such as DeepPath and MINERVA use reinforcement learning, whereas UHop uses annotated relations to train a comparative termination decision directly.The cited methods do not use annotated relations and require REINFORCE optimization.Source: §2 · p. 2
• UHop is contrasted with IRN, which uses memory linearly in knowledge-graph size and still imposes a maximum-hop constraint in its experiments.UHop is reported to process large-scale Freebase experiments, while IRN experiments use a subset of Freebase.Source: §2 · p. 2

3 UHop Relation Extraction

• UHop breaks unrestricted-hop relation extraction into single-hop relation extraction and comparative termination decision.The framework is intended to work with existing relation-extraction models.Source: §3 · p. 2
• Starting from a linked topic entity, UHop scores outbound relations, transitions along a selected relation, and decides whether to continue searching or terminate.If it continues, it searches outbound relations from the new entity and repeats the process; termination returns the extracted relation path.Source: §3 · pp. 2–3

12 end Result: P

• The iterative search concatenates each selected relation with the prior path, repeats from the new entity when termination is false, and returns the extracted relations when it stops.Termination determines how many hops are needed to reach the target entity.Source: §12 · p. 3

3.1 Single Hop Relation Extraction

• Single-hop relation extraction is trained as pairwise classification that favors the gold relation over incorrect outbound relations, using hinge loss to maximize their score margin.This process is compatible with related relation-extraction models, facilitating installation of state-of-the-art models in UHop.Source: §3.1 · p. 3

3.2 Comparative Termination Decision

• The same model makes termination decisions by stopping when the previously extracted relation scores higher than every outbound relation at the new entity.When search should continue, training compares the selected relation against the gold relation for the next hop.Source: §3.2 · pp. 3–4

3.3 Dynamic Question Representation

• Dynamic question representations reduce the importance of question information related to the already selected path when extracting the next relation.For non-attentive models, UHop applies a linear transformation to the concatenated selected relation and question representation.Source: §3.3 · pp. 4–5

3.4 Jointly Trained Subtasks

• UHop jointly optimizes the relation-extraction and termination-decision subtasks across the hops in the gold relation path.The combined loss includes both subtasks’ losses at each hop.Source: §3.4 · p. 5

4.1 Datasets

• WebQSP contains questions with 1- or 2-hop answers, and about 40% require two hops.It is based on Freebase and annotates each question with its relation chain, topic entity, and answer entity.Source: §4.1 · p. 5
• PathQuestion and PathQuestion-Large include 2- and 3-hop questions; the latter uses a larger Freebase subset and fewer training instances.Both datasets generate questions from templates, paraphrasing, and synonyms.Source: §4.1 · p. 5
• Grid World tests navigation questions requiring relation paths of up to 10 hops, with samples grouped into four path-length buckets.Its 16-by-16 fully connected grid uses relative-direction relations; each question supplies a starting node and navigation instructions.Source: §4.1 · p. 5
• MetaQA and Complex Sequential QA are outside the paper’s scope because they use a movie graph with only six relations or sequences of single-hop questions, respectively.The authors characterize MetaQA as too simple for discussion and distinguish sequential questions from multi-hop relation paths.Source: §4.1 · p. 6

4.2.1 Baseline and Settings

• HR-BiLSTM and ABWIM are evaluated within and outside UHop, with BiCNN selected as a baseline.MVM is omitted because its additional tail-entity-type information and further relation queries would make UHop revert to relation-chain-based search.Source: §4.2.1 · p. 6
• The experiments use 300-dimensional pretrained GloVe embeddings and RMSprop, with best parameters selected empirically.WQ uses a randomly selected 10% of training data for validation because it has no predefined validation set.Source: §4.2.1 · p. 6

4.2.2 Results and Discussion

• UHop models achieve performance comparable to standalone versions while allowing unrestricted relation hops and greatly reducing search space.Table 2 reports results for state-of-the-art models in the UHop framework versus standalone versions.Source: Table 2 · p. 6, §4.2.2 · p. 6
• 30%: UHop reduces the WQ search space, translating to lower processing time and memory consumption, and sometimes slightly improved performance.The approximate search spaces are n(n −1)(L−1) without UHop and n(L + 1) with UHop, where n is the average number of relations per entity and L the predefined maximum hop number.Source: §4.2.2 · p. 6, Table 3 · p. 6

4.3.1 Baseline and Settings

• PQ and PQL use 8:1:1 training, validation, and test splits, while PQ+ and PQL+ mix two- and three-hop sets to test termination beyond the majority training length.The experiments also apply dynamic question representations to these long-path datasets.Source: §4.3.1 · pp. 6–7
• The authors report their reproduced performance because they could not reproduce the original paper’s reported 85.32.They state that the reported reproduced performance is from the same model adapted in UHop.Source: §4.3.1 · p. 6

4.3.2 Results and Discussion

• HR-BiLSTM and ABWIM outperform IRN and perform nearly perfectly across the PQ/PQL datasets, while search-space reduction is not obvious on their smaller, simpler knowledge graph.The results also indicate that UHop works well on small and simple knowledge bases.Source: §4.3.2 · p. 7
• Updating the question representation dynamically in each iteration benefits relation extraction in most cases.The PQ/PQL questions are all multi-hop, motivating representations that reflect transitions during relation extraction.Source: §4.3.2 · p. 7

4.4.1 Baseline and Settings

• The Grid World experiments use MINERVA and Neural LP as baselines, with randomly initialized, optimized word embeddings and RMSprop training.The authors state that the search space is too large to run HR-BiLSTM and ABWIM without UHop.Source: §4.4.1 · p. 7

4.4.2 Results and Discussion

• UHop with a relation extraction model perfectly solves Grid World, performing well across all four question buckets while Neural LP and MINERVA suffer from long-path error propagation.The figure presents Grid World results for state-of-the-art knowledge-based relation extraction models.Source: Figure 2 · p. 7, §4.4.2 · pp. 7–8
• For path length k, independent models face an approximate search space of 8k, compared with 8 × k within UHop, making even the shortest-path experiments infeasible without UHop.Grid World has eight directions, allows movement back and forth, and includes paths up to 10 hops.Source: §4.4.2 · p. 8

5.1 Dataset Characteristics

• Grid World tests long sequential decisions rather than question understanding; WQ uses natural-language 1- or 2-hop questions, while PQ/PQL use smaller, repetitive KBs and templated 2- to 3-hop questions.Figure 3 visualizes dataset KB relations, with bubble size proportional to relation frequency.Source: §5.1 · p. 8, Figure 3 · p. 8

5.2 Trained on 3-hop, Tested on 2-hop

• Both UHop models outperform their original versions by more than 7%, but accuracy remains below 50% when training contains no 2-hop samples.Source: Table 6 · p. 8, §5.2 · p. 8

5.3 Error Analysis

• UHop’s hop-level interpretability supports error analysis by hop, and Table 7 reports HR-BiLSTM and ABWIM error-type distributions for relation extraction and termination.Source: §5.3 · p. 8, Table 7 · p. 9
• Across WQ and PQ/PQL, first-hop relation extraction dominates errors; second-hop and termination errors are fewer, with only a few PQL3 ABWIM termination errors.Source: §5.3 · p. 9
• Training on both 2- and 3-hop data improves 2-hop predictions mainly through first-hop extraction, but 3-hop performance suffers when trained on 2-hop data.Source: §5.3 · p. 9
• Dynamic question representations significantly benefit first-hop relation extraction; UHop’s shared selection and termination model is linked to reduced ambiguity during testing.Source: §5.3 · p. 9
• In 3-hop-trained PQL2 tests, termination fails on more than 40% of cases despite correct relation extraction; absent target-length samples and differing templates may limit transfer.Source: §5.3 · p. 9

• UHop allows unrestricted relation hops and reduces the search space; the same model achieves comparable results in the reduced space and works on lengthy relation extraction.The transition-based design supports dynamic question representations, and the framework can use most state-of-the-art models; the current search is greedy at each hop.Source: §6 · p. 9