Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The paper present a RL based approach to walk on a knowledge graph to answer queries. The idea is novel, the paper is clear in its exposition, and the authors provide a number of experimental comparisons with prior work on a variety of datasets . 

Pros:
1. The approach is simple (no pre-training, no reward shaping, just RL from scratch with terminal reward, uses LSTM for keeping track of past state), computationally efficient (no computation over the full graph), and performs well in most of the experiments reported in the paper. 
2. It scales well to longer path lengths, and also outperforms other methods for partially structured queries.

Cons:
1. You should elaborate more on the negative results on FB15K and why this performance would not transfer to other KB datasets that exist. This seems especially important since it's a large scale dataset, while the datasets a)-c) reported in the paper are small scale. 
2. It would also be good to see if your method also performed well on the Nations dataset where the baselines performed well. That said, if its a small scale dataset, it would be preferable to focus on strengthening the experimental analysis on larger datasets.
3. In Section 4.2, why have you only compared to NeuralLP and not compared with the other methods? 

Suggestions/Questions:
1. In the datatset statistics, can you also add the average degree of the knowledge graphs, to get a rough sense of the difficulty of each task.
2. The explanation of the knowledge graph and notation could be made cleaner. It would be easier to introduce the vertices as the entities, and edges as normal edges with a labelled relation on top. A quick example to explain the action space would also help.
3. Did you try a model where instead of using A_t directly as the weight vector for the softmax, you use it as an extra input? Using it as the weight matrix directly might be over regularizing/constraining your model.  

Revision: I appreciate the effort by the authors to update the paper. All my concerns were adequately addressed, plus improvements were made to better understand the comparison with other work. I update my review to 7: Good paper, accept.
review_title: Simple RL approach for reasoning on Knowledge bases, good performance on variety of datasets but need to be slightly more thorough in their comparisons with prior work

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.
review_title: Review 

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes an approach for query answering/link prediction in KBs that uses RL to navigate the KB graph between a query entity and a potential answer entity. The main originality is that, unlike random walk models, the proposed approach learns to navigate the graph while being conditioned on the query relation type.

I find the method sound and efficient and the proposed experiments are solid and convincing; for what they test for.

Indeed, for each relation type that one wants to be testing on, this type of approach needs many training examples of pairs of entities (say e_1, e_2) connected both by this relation type (e_1 R e_2) and by alternative paths (e_1 R' R'' R''' e_2). Because the model needs to discover and learn that R <=> R ' R'' R''' .

The proposed model seems to be able to do that well when the number of relation types remains low (< 50). But things get interesting in KBs when the number of relation types gets pretty large (hundreds / thousands). Learning the kind of patterns described above gets much trickier then. The results on FB15k are a bit worrying in that respect. Maybe this is a matter of the dataset FB15k itself but then having experiments on another dataset with hundreds of relation types could be important. 

NELL has indeed 200 relations but if I'm not mistaken, the NELL dataset is used for fact prediction and not query answering. And as noted in the paper, fact prediction is much easier.


review_title: Review

Meta-review: Good contribution. There was a (heated) debate over this paper but the authors stayed calm and patiently addressed all comments and supplied additional evaluations, etc.

Decision: Accept (Poster)