Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The author investigates the rule learning problem and  proposes R5, a reinforcement learning  based framework to reason over relational graph data and explicitly mines underlying compositional logical rules from observations. It mainly contains two components: RL agent to model rule learning as a sequential decision-making problem and a dynamic rule memory module to maintain and score candidate rules during the training of the reasoning agent.

main_review: 
Strengths  

S1 The dynamic rule memory module is interesting.

S2 Detailed ablation study and case study.

S2 The paper is well written and well organized.

Weaknesses

W1 RL agent aims to seek long-term and maximum overall reward to achieve an optimal solution. However, this paper aims to divide the long-term decision into independent short-term decision. Therefore, I don’t see why RL should be used in this scenario.

W2 Too much reliance on heuristics. For example, it utilizes statistical features, such as the number of occurrences to represent relation pairs. 

W3 How to recover the logical rule is unclear to me. Should we enumerate over the whole rule space to select the rules with the highest score?

W4 How do the authors handle uncertainty during the deduction is unclear. It is possible for a two relation sequence to have multi heads. For example, given two relation sequences hasAunt and hasSister, both hasMother and HasAunt can be the head. How can the proposed solution solve the multi head scenario?

W5 The author should discuss more about how to choose the value of n (number of unknown relations). Intuitively, a small n may reduce the expressiveness of the model while a big n may cause computational inefficiency. Choosing the value of n could be a tricky problem.

W6 Lack of some representative baselines. For example, NeuralLP, RNNLogic are missing.

W7 Datasets include too few relations.To show the scalability of the proposed model, it will be better to conduct experiments on datasets with more relations e.g., FB15k.
summary_of_the_review: The author investigates an interesting problem, logical rule learning. It also proposes an interesting idea to decompose the long path into small pieces to recurrently learn rules. Although the idea is interesting, the model and the experiments are less convincing as pointed out in the weaknesses. It will be better for the author to clearly illustrate the reasoning why they choose the  RL model to learn rules and how they handle uncertainty during the deduction. They also need to include more baselines and larger datasets to make the experiments more convincing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work explores a rule learning approach (R5) for 2 relation prediction tasks (CLUTRR and GraphLog). The proposed approach starts by finding connecting paths between the two query entities. Then it recursively merge relation pairs until it consists of a single relation output. The merging process is controlled by a policy/value network trained with episodic rewards. The rules are induced whenever the output relation matches the gold relation -- in a fashion similar to that of curriculum learning. 

Experiments show that R5 generalizes better than previous approaches such as Graph Attention Networks (GAN) and Conditional Theorem Provers (CTPs) especially when generalizing to paths longer than those from the training set.

main_review: In general the proposed approach is reasonable and effective for the targeted 2 tasks. The introduction of new relations, and application of RL are interesting. However, the task and model design seem to be very specific to a type of task where the relevant part of a graph (to the prediction) is restricted to a path, which can be recursively derived from the target relation. The separation of path finding and reasoning also seems to be an artifact from the specific task assumption.


Clarity related questions: 
It would be helpful to formally define the relation prediction task.

It would be helpful to describe the path sampling procedure.

How is the model updated given the loss function l?

The state representation has one entry per relation pair. Will that lead to information loss when a relation pair appears multiple times in the path?

"recurrent reasoning agent enables us to predict ... efficiently" -- it is more efficient than what approach? and why?

Table 4 and 5: given that the rule recalls of R5 are almost 100% why the accuracy much lower than 100%?


summary_of_the_review: An interesting approach with good results for a limited task setup.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a novel method for rule induction. The main idea is to apply
reinforcement learning in the task of relational pathfinding within a finite
Herbrand base. The reinforcement learner uses MCTS to find the best routes to
establish the path in between the two arguments of training examples, while the
useful actions (which are length-two relational paths) are maintained in a hash
table as the induced ruleset. Experimental results has shown the effectiveness
of the proposed method.
main_review: Program induction is a hard problem, especially for large-scale tasks in noisy
domains. This problem can be formulated as a Relational Pathfinding task [1], which
has been studied for many years in the area of Inductive Logic Programming. In
Statistical Relational Learning there is also a missing related work that
searches for grounded relational paths first and then applies machine learning
to extract first-order logical rules [2].

Compared to previous works in this direction, the main contribution of this
work is applying reinforcement learning in the relational pathfinding problem. The
proposed approach works surprisingly well in the experiments, and the combination of 
neural-guided heuristic learning for MCTS and the symbolic rewarding method perform good
in the relational pathfinding problem.

The main weakness of relational pathfinding is the grounding problem, i.e., for
each training example, the algorithm needs to search for ground paths before
training. Besides, the pathfinding algorithm may suffer from incompleteness if
the hypothesis has some complex structures, e.g., if there are some useful
relations do not showing in a path (node "z" in p(x,y)<-q(x,y),r(x,z)), or if
there exists higher-order primitive predicates or triadic predicates. Another
possible weakness is that reinforcement learning usually requires large numbers
of training epochs, especially when learning the heuristics for program
induction.

### Some minor issues:
- "unknown relations" should be called "invented predicates/relations", following the
  convention in the area of program induction;
- The algorithm implicitly assumes all rules are using the same template, which
  is a dyadic chain meta-rule [3], which could result in incompleteness [4]
  (i.e., some hypotheses can never be learned), I think this should be made
  clear in this paper.
- Following my last point, the proposed method seems can only learn dyadic chain
  rules in datalog (e.g., every rule in the target hypothesis have the form of
  "p(x,y)<-q(x,z), r(z,y)", and the language is function-free). Is it possible to extend it to complex domains?
- The learned policy can not be transferred to other tasks (e.g., adapt from one
  task to another task, or from one target relation to another one).

### References:
1. Bradley L. Richards and Raymond J. Mooney. Learning relations by pathfinding.
   In Proceedings of the 10th National Conference on Artificial Intelligence,
   pages 50–55, San Jose, CA, July 1992.
2. Wang-Zhou Dai and Zhi-Hua Zhou. Statistical unfolded logic learning. In:
   Proceedings of the 7th Asian Conference on Machine Learning (ACML’15), Hong
   Kong, 2015, JMLR: W&CP 45, pp. 349-361.
3. S.H. Muggleton, D. Lin, N. Pahlavi, and A. Tamaddoni-Nezhad.
   Meta-interpretive learning: application to grammatical inference. Machine
   Learning, 94:25-49, 2014.
4. Andrew Cropper and Stephen H. Muggleton. Logical minimisation of meta-rules
   within meta-interpretive learning. In Proceedings of the 24th International
   Conference on Inductive Logic Programming, pages 65-78.
   Springer-Verlag, 2015. LNAI 9046.

summary_of_the_review: This paper presents a novel algorithm to solve program induction formulated as a
relational pathfinding problem. The proposed approach outperforms existing rule
induction methods in several benchmark datasets. It has missed several important
references and needs further clarification, so I would like to recommend to
accept if the authors can fix those problems.
review_title: null

Meta-review: A novel method is described that uses RL to search for a rule set which predicts multiple relations at once for KBC-like problems.  The rules can include latent predicates, which reduces the complexity of individual rules, similar to Cropper & Muggleton's (2015) meta-interpretive learning framework, which is usual for rule-learning systems.  Another novel aspect is use of a cache memory for rules.

Pros
 - the idea of using RL instead of carefully-designed discrete search for symbolic learning systems is a very nice novel idea
 - the experimental results are strong

Cons
 - the benchmarks are synthetic (although GraphLog does at least include noise)
 - although the Cropper and Muggleton work is cited the relationship between the search spaces of the two systems is not discussed - this should be corrected in the final version.
Decision: Accept (Spotlight)