Abstract
Knowledge bases (KB), both automatically and manually constructed, are oftenincomplete --- many valid facts can be inferred from the KB by synthesizingexisting information. A popular approach to KB completion is to infer newrelations by combinatory reasoning over the information found along other pathsconnecting a pair of entities. Given the enormous size of KBs and theexponential number of paths, previous path-based models have considered onlythe problem of predicting a missing relation given two entities or evaluatingthe truth of a proposed triple. Additionally, these methods have traditionallyused random paths between fixed entity pairs or more recently learned to pickpaths between them. We propose a new algorithm MINERVA, which addresses themuch more difficult and practical task of answering questions where therelation is known, but only one entity. Since random walks are impractical in asetting with combinatorially many destinations from a start node, we present aneural reinforcement learning approach which learns how to navigate the graphconditioned on the input query to find predictive paths. Empirically, thisapproach obtains state-of-the-art results on several datasets, significantlyoutperforming prior methods.