Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: There is a lot of recent work on link-prediction in knowledge graphs. One approach is based on embedding entities and relations in a knowledge graph into vector spaces, and the other is based on finding rules that imply relations, and then using these rules to find new links or facts. This paper takes the latter approach. Within the area of rule-based methods, a number of recent papers have used neural network methods to simultaneously generate rules and to find rule-weights or other related parameters (indicating how important individual rules are). Simultaneously solving for rules and rule-weights is a difficult task. In this paper, the authors propose a method where they separate the rule generation process from the weight/parameter calculation process. More importantly, they add a feedback loop from the weight calculation routine ("reasoning predictor") to the rule generation routine ("rule generator"), which in my opinion is novel, even though there have been a few recent attempts (Xiong et. al. 2017) to use reinforcement learning to search for rules. The rule generator in this paper uses a recurrent neural network (RNN) and the parameters of this RNN are modified by the reasoning predictor. In other words, the iterative process has the feature that new rule generation is influenced by the calculated weights of previously generated rules. The authors perform numerical experiments on 4 standard knowledge graphs to demonstrate the performance of their method

Strong points

1. Clean probabilistic framework to jointly solve for rule generation and rule weight calculation via an iterative process where rule weight calculation (of existing rules) influences subsequent rule generation.

2. Good results

3. The authors take into account recent concerns on the quality of knowledge graph link prediction methods voiced in Sun et. al. (2020). Many papers use a ranking approach that yields excessively good scores to low-quality results (if many entities including the correct one receive equal scores as potential solutions to the query (h,r,?) during testing , where h is an entity and r is a relation, then the correct entity is given a high score), and the authors fix one of the issues in such ranking approaches.

Weak points

1. In many rule based methods (such as Neural LP), the goal is to find a set of (weighted) rules that imply a single relation.
In this paper, it seems that the authors generate a set of weighted rules for each "query" of the form (h,r, ?) derived from a fact/triplet of the form (h,r,t) where h,t are entities and r is a relation. My issues with this are: 

 a) computation time, given that the number of relations maybe in the few hundreds (e.g. FB15k-237), whereas the number of facts/triplets is significantly larger. The authors do not say anything about computation time (this seems standard in the area).

 b) In the test-phase, it is not clear how one deals with entities which were not present in the training set? If one had a rule for a relation, then one would still be  able to use the rule.

3. Though the authors fix some issues with over-optimistic ranking approaches during testing, they do not clarify what happens when many entities receive equal non-zero scores. In other words, they do not explain what rank they give to the correct entity for the query (h,r,?) if it receives an equal probability score to a number of other entities. 

4. The authors focus on the theoretical aspects of the paper. However, replicating the experiments in this paper seems to be difficult. The high-level ideas are easy to follow, but the precise way the algorithm is put together is hard to follow.
    
Recommendation

I recommend accepting this paper.
My acceptance recommendation is based on the "Strong Points" 1 and 3. The paper gives a well-founded approach to improving rule-generation based on previously calculated rule weights, and uses an improved scoring method, so that high scores are more meaningful than in some prior papers.

Questions

1. Is my understanding correct that you build rules for each query q = (h,r,?) and not for each relation? This seems to be implied in Figure 2. Please explain how you will deal with head/tail entities in the test set that are missing from the training set?

2. You use "reverse arcs" in training set, but you do not make clear if you use inverse relations in the rules you generate. Do you?

3. In the Sun et. al. paper, they talk about doing a "fair comparison" when an algorithm gives a certain probability/score to the correct answer (and to many incorrect answers) of a query. You only use their suggested fix for the case correct answers are given zero probabilities. What happens when multiplies entities are given identical nonzero probabilities?

4. Can you clarify what RNNLogic with embedding is? I am guessing it is related to assigning path scores via embedding? Please make this explicit.

5. Will your method be computationally more expensive than methods which generate rules for individual relations?

6. In trying to answer a query (h,r,?), it is clear you may use rules that include the relation 'r'. What is to stop you from using rules of the from 'r(X,Y) and s(Y,Z) and s^-1(Z,Y)'  and other similar rules which implicitly create trivial relational paths? 

7. There are a number of papers in the area of rule-learning for simple binary classification tasks where rule weight calculation influences subsequent rule generation. See papers on boosting classifiers, especially boosting rule-based classifiers e.g. Eckstein and Goldberg (ICML 2010). You should probably give a reference to such work. 

8. In the definition of the probability value in equation (5), you are implicitly assuming that if a rule creates multiple paths from a head entity h to multiple entities other than e (say b, and c), than the rule is not good for e. But what if (h,r,b) and (h,r,c) are facts in the training set in addition to (h,r,e)? Should you be penalizing this rule (or set of rules z)?

9. It seems to me that you are implicitly assuming that if a fact (h,r,e) is missing from the training set, then it is not true; in other words, a closed-world assumption. Is this correct? If so, it would help to mention it explicitly.

Though I like the paper, and I believe it has good results, I am now seriously concerned about the quality of the numbers in Tables 1 and 2. The origin of many of the results in these tables is in doubt. The authors say that the results for TransE, RotatE, ConvE, ComplEx , DistMult, and Minerva are taken from the corresponding papers. But when I look at these papers, I see different (or no) numbers.

The values for Minerva in the current paper match for FB15k-237, but do not match for WN18RR. The values in the Minerva paper for UMLS or Kinship are way better than in the current paper. Now Minerva uses a different evaluation protocol, but I seriously doubt the Minerva numbers for UMLS and Kinship.

RotatE has no numbers for UMLS or Kinship.

ComplEx has none of the numbers reported here.

Distmult has none of the numbers reported here.

The numbers in the current paper for TransE, DistMult, RotatE, ConvE and ComplEx seem to be taken from the RotatE paper. But RotatE has no numbers for UMLS or Kinship.

So overall, the provenance of the numbers in Table 1 and 2 is in serious doubt. I realize that the authors do not have a chance to respond and modify the paper. I hope the PC members can weigh in on what can be done at this stage. Even though I like this paper, my score will go down based on the poor quality of Tables 1 and 2.
review_title: Review of "RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs"

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: In this work, the authors illustrate an approach for learning logical rules starting from knowledge graphs. Learning logic rules is more interesting than simply performing link prediction because rules are human-readable and hence provide explainability.
The approach seems interesting and the tackled problem could interest a wide audience. It does not seem extremely novel, but it seems valid to me.
The paper is well-written and self-contained. Moreover, the experimental results show that the proposed approach has competitive performance comparing to other systems (even compared with systems that do not learn rules but perform only link prediction).

For all these reasons I think the paper should be accepted for publication.
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper focuses on learning logic rules via EM-based algorithm. The idea in the paper is that E-step would try to generate rules while M-step would update the parameters. The empirical comparisons are interesting and show that the paper improves on prior work. 

There are several aspects that make it very hard for me to understand the paper's contributions and evaluation. I am listing below and hoping that other reviewers or authors would be able to clarify:

1. The paper suggests that the performance is owing to reduction of search space due to E-M step. It is hard to understand what MLN tool is being employed here and why MLN-based technique would return a suboptimal answer (the combinatorial solvers may return suboptimal answer due to timeout but that should be clarified in this case). It may perhaps be the case that sampling rules from a good distribution allows us to search only over a small space but that needs to contrasted with weakness of MLN-based methods. 

2. The paper uses mean ranking for measuring. I am failing to understanding how is the ranking computed for rules and why such a metric is a good approach.  Can authors expand on what exactly is being done: i don't understand "for each query, we compute probability for each entity" means? 
review_title: Marginal Gain over existing work

final_score: rating: 7: Good paper, accept
review_content: In this paper, the author proposes RNNLogic for learning FOL rules from the knowledge graph. The proposed method assigns embeddings for each relation type and uses RNN module to generate chain-like rule candidates. Candidates are evaluated with a separate evaluation module that computes the scores. The rule scores are then taken to update the generator module using EM.

I think the idea of separating rule generation and evaluation is interesting, and using EM to jointly train the modules is also novel. However, I think the current paper writing is convoluted and prone to notations issues. One needs to constantly refer to appendix to understand the proposed method. For example:

- Why is Eq4 a valid answer score? I think it's related to the commonly-used graph traversal score, but the author should clarify this in the main text.

- Psi_w(rule) is not defined in the main text. And I found its definition in C1 to be problematic too: it's defined over score_w(t|rule) - but isn't that the score_w is defined with psi_w(rule) and psi_w(path) already in Eq4?

- I suggest the author to elaborate more why RotatE can be used to generate psi_w(path), as it's not very intuitive to me why this would help

Some claims are not well addressed:

- In section 2, the author criticizes the current differentiable ILP methods to lack ways "to determine the importance of rules with the learned weights due to the high dimensionality.". However, many methods such as diff-ILP and NeuralLP can indeed learn the rule weights.

- Backward-chaining methods such as NeuralLP are indeed efficient for problems with high dimensionality as well.

- There seems to be no justification or experiments to demonstrate how the proposed method can do better than the previous ones on these properties.

Model details:

- The author claims the psi_w(path) can be fixed to 1, in this case, what's been learned w.r.t parameter w? Is Psi_w(rule) a learnable module as well?

Model efficiency:

- Evaluating Eq 4 and Eq 5 requires to sum over all possible paths and rules. This process can be efficient for methods utilizing matrix multiplication such as NeuralLP. But it's unclear to me if a similar method is used in RNNLogic. If not, how well does the model scale to long paths and KBs with large grounding space?

- Also, the EM algorithm requires to hard sample top-K rules (K=1000) for each data instance at each iteration. I'm concerned about the efficiency of this method. It would be helpful if the author can provide the runtime comparison in the experiment as well.


Experiment:

- Many baseline scores on the FB15K and WN18 are cited from the original paper. But why do NeuralLP and DRUM get rerun in these twos benchmark?

- In appendix D, the author mentions that the entity embeddings are in fact *pre-trained* using RotatE. I find this setting to be unjustified and can lead to unfair comparisons against both ILP and non-ILP methods.

- In the w/o emb. mode, I assume no embeddings are learned in the reasoning module, so the score should be comparable to the vanilla score used in NeuralLP. Given that the RNNLogic also generates only chain-like rules using RNN, it seems that the proposed method should have searched similar rules and got similar rule scores as the NeuralLP. Can author provide intuitions or insights why RNNLogic significantly outperforms the NeuralLP even in w/o emb. mode?

Overall, I think this work indeed has some novelties but it is currently prone to unjustified claims and confusing writing. The experiment is incomplete and the usage of pre-trained embedding for SOTA model is unjustified. With that being said, I would recommend weak rejection at this point, but I'm happy to raise the scores if these concerns are addressed.
review_title: Review

Meta-review: There is a consensus among the reviewers that the work is interesting and the paper should be accepted.  Nevertheless, several reviewers struggled with understanding the details. While the authors  (largely successfully) addressed these concerns, I believe that the paper is still too dense and hard to follow, I would encourage the authors to invest more time into improving its readability.  One important point which came late in the discussion is the provenance of baseline scores in the result tables (see the review by AnonReviewer3, the current manuscript claims that the numbers are taken from the original papers while in some cases, the numbers cannot be located in these papers). Unfortunately, the authors did not have a chance to respond to this criticism, and fortunately we could trace the key numbers and establish that the results are strong enough to warrant accepting the submission. Still, we would ask the reviewers to fix this issue in the final version.
Decision: Accept (Poster)