Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning

TLDR

Knowledge bases are incomplete, and prior path‑based methods have mainly focused on predicting missing relations or evaluating triples using random or learned paths between fixed entity pairs. This work introduces MINERVA, an algorithm that tackles the harder problem of answering queries with a known relation but only one entity. MINERVA employs neural reinforcement learning to guide a walk through the knowledge graph conditioned on the query, learning to select informative paths rather than sampling random walks. Experiments show that MINERVA achieves state‑of‑the‑art performance on multiple datasets, substantially surpassing existing approaches.

Abstract

Knowledge bases (KB), both automatically and manually constructed, are often incomplete --- many valid facts can be inferred from the KB by synthesizing existing information. A popular approach to KB completion is to infer new relations by combinatory reasoning over the information found along other paths connecting a pair of entities. Given the enormous size of KBs and the exponential number of paths, previous path-based models have considered only the problem of predicting a missing relation given two entities or evaluating the truth of a proposed triple. Additionally, these methods have traditionally used random paths between fixed entity pairs or more recently learned to pick paths between them. We propose a new algorithm MINERVA, which addresses the much more difficult and practical task of answering questions where the relation is known, but only one entity. Since random walks are impractical in a setting with combinatorially many destinations from a start node, we present a neural reinforcement learning approach which learns how to navigate the graph conditioned on the input query to find predictive paths. Empirically, this approach obtains state-of-the-art results on several datasets, significantly outperforming prior methods.