Published as a conference paper at ICLR 2018 GO FOR A WALK AND ARRIVE AT THE ANSWER: REASONING OVER PATHS IN KNOWLEDGE BASES USING REINFORCEMENT LEARNING
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 unknown destination and combinatorially many paths 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. On a comprehensive evaluation on seven knowledge base datasets, we found MINERVA to be competitive with many current state-of-the-art methods.
The paper proposes a new approach (Minerva) to perform query answering on knowledge bases via reinforcement learning. The method is intended to answer queries of the form (e,r,?) on knowledge graphs consisting of dyadic relations. Minerva is evaluated on a number of different datasets such as WN18, NELL-995, and WikiMovies.
The paper proposes interesting ideas to attack a challenging problem, i.e., how to perform query answering on incomplete knowledge bases. While RL methods for KG completion have been proposed recently (e.g., DeepPath), Minerva improves over these approaches by not requiring the target entity. This property can be indeed be important to perform query answering efficiently. The proposed model seems technically reasonable and the paper is generally written well and good to understand. However, important parts of the paper seem currently unfinished and would benefit from a more detailed discussion and analysis.
Most importantly, I'm currently missing a better motivation and especially a more thorough evaluation on how Minerva improves over non-RL methods. For instance, the authors mention multi-hop methods such as (Neelakantan, 2015; Guu, 2015) in the introduction. Since these methods are closely related, it would be important to compare to them experimentally (unfortunately, DeepPath doesn't do this comparison either). For instance, eliminating the need to pre-compute paths might be irrelevant when it doesn't improve actual performance. Similarly, the paper mentions improved inference time, which indeed is a nice feature. However, I'm wondering, what is the training time and how does it compare to standard methods like ComplEx. Also, how robust is training using REINFORCE?
With regard to the experimental results: The  improvements over DeepPath on NELL and on WikiMovies are indeed promising. I found the later results the most convincing, as the setting is closest to the actual task of query answering. However, what is worrying is that Minerva doesn't do well on WN18 and FB15k-237 (for which the results are, unfortunately, only reported in the appendix). On FB15k-237 (which is harder than WN18 and arguably more relevant for real-world scenarios since it is a subset of a real-world knowledge graph), it is actually outperformed by the relatively simple DistMult method. From these results, I find it hard to justify that "MINERVA obtains state-of-the-art results on seven KB datasets, significantly outperforming prior methods", as stated in the abstract.
Further comments:
- How are non-existing relations handled, i.e., queries (e,r,x) where there is no valid x? Does Minerva assume there is always a valid answer?
- Comparison to DeepPath: Did you evaluate Minerva with fixed embeddings? Since the experiments in DeepPath used fixed embeddings, it would be important to know how much of the improvements can be attributed to this difference. 
- The experimental section covers quite a lot of different tasks and datasets (Countries, UMLS, Nations, NELL, WN18RR, Gridworld, WikiMovies) all with different combinations of methods. For instance, countries is evaluated against ComplEx,NeuralLP and NTP; NELL against DeepPath; WN18RR against ConvE, ComplEx, and DistMult; WikiMovies against MemoryNetworks, QA and NeuralLP. A more focused evaluation with a consistent set of methods could make the experiments more insightful.