Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a novel differentiable model for the ILP problem, i.e., mining logic from KGs. To do this, the authors introduce a compositional view of the chain-like rules and design a learning schema where the model learns to reduce a path into a single edge. The proposed model, namely NCRL, is an RNN-transformer hybrid model that parameterizes this schema with sequences of soft attention. In the experiments, NCRL demonstrates better systematic generalization in several benchmarks.
strength_and_weaknesses: Strength 
- Proposes an interesting perspective of viewing chain-like rules in KGs via hierarchical compositions, which is different from the classical multi-hop pathfinding view.


Weaknesses
- Some design choices (see below) need more justification

clarity,_quality,_novelty_and_reproducibility: ### Novelty


I find the proposed compositional view of the chain-like rule very interesting and inspiring. I particularly like the example shown in the introduction and Fig 1. The proposed model is technically sound, although there might be some aspects needing further justification. The experiments are well-designed and support the claims. A solid contribution to the ILP community.


### Quality


Section 3.2 suggests that for every pair of entities with a sampled path, one sets the head to "null" if there is no direct connection. And with Eq 7, this effectively makes the model predict "null" for every pair of entities with missing direct edges. I'm not sure if this is correct: this essentially leads to a closed-world setting, where every possible missing edge is assigned with a specific label (i.e., null). This can be problematic with many real-world KGs that have many missing edges: for example, there might be two pairs of $(x_0,x_n)_1$ and $(x_0,x_n)_2$ with the same path $p_1 = p_2$, but $(x_0,x_n)_1$ is connected with $r_h=hasMother$ while $(x_0,x_n)_2$ is not. In this proposed setting, the model is told to predict hasMother for $(x_0,x_n)_1$ and null for $(x_0,x_n)_2$ even though they have the same path.

I find the scalability argument not very convincing. The proposed model should have similar asymptotic complexity as other backward-chaining methods such as NeuralLP, as all of them are based on the same personalized random walk mechanism. The difference is just that NeuralLP computes the state probability directly with matrix multiplication, whereas NCLR samples from it. The difference in 4.2 seems to be more of a consequence of implementational optimization. For example, by default NeuralLP multiplies the entire matrix for every query, one can readily optimize it by storing the local adjacency matrices up to the max search step.

With that being said, the path sampling phase may need more elaboration. Right now, it is unclear how the max search step is set, how many samples are collected per pair, and how the duplicates are handled. Also, it is also important to discuss how sensitive the model is w.r.t these hyperparameters.

The authors set the window size to {2,3} throughout the experiments. It would be nice to have an experiment to show how model performance changes w.r.t the window size.


### Clarity


The paper is well-written and generally easy to follow. Below are some minor issues.


In Fig 3 and section 3.1.1, what is $r_i$? Is it an embedding vector of a unique relation? 


Minor issues
	- "infer the relation between nodel pair query"
	- Conjunctions missing in some rules in Table 5

summary_of_the_review: In summary, this paper introduces an interesting view of the chain-like rule and proposes a technically sound model that takes advantage of this observation. I do have some concerns about the methodology and technical details and hope the authors could address them, but in general, I really enjoy reading the paper. That said, I recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes to learn logic rules by recursively encoding subsets of paths into head relations. The paths are samples from the KG. The method to do this is using an RNN to encode each element of the sliding window on the path, selecting one window with a softmax, and using an attention mechanism to predict the summarising head entity.

The authors demonstrate the scalability advantage and the competitive performance of their method against strong rule-learning based methods on a variety of standard benchmarks.

strength_and_weaknesses: Strengths:
 - Good technical novelty
 - Good empirical evaluation: demonstrating good performance and good scalability
 
 Weaknesses:
 - The clarity of the paper could be improved, in particular variable names are re-used and mean different things in different sections of the paper, which is an unnecessary hurdle for the reader.
 - Some questions about the implementation remain that would be necessary for reproducibility:
	- What are the hyperparameters there is no table in the appendix for this as far as I can see (for the results in Table 1 & 3)?
	- Will you publish code upon acceptance?
	
 - Certain design decisions are unexplained and not studied in the ablation studies:
	- Why use an RNN for the encoding of sliding windows (due to the fixed length of window) a standard neural network would do? Did you compare against this?
	
Questions:
 - How is semantic consistency defined in the intro of section 3?
 - Why is an RNN architecture needed for a fixed size sliding window (eq 2.) did you try a standard Neural Network? Would it be possible to do an ablation on this?
 - How the length of sampled paths determined? Is there a maximum cut-off? Are loops automatically removed? In general the section on path sampling was difficult to understand.
 - Why did you choose to project the key and values to the same space (i.e. W_V = W_K eq5)? 

Minor:
 - Please use a different variable name for w_i after the RNN stage, it's unnecessarily confusing. Similarly, please rename the hyperparameter theta as theta is already used in eq4.
 - There is a typo in 4.3, 3rd line at the very end.
 - When defining H in 3.1.2 there are missing brackets in the power as multiplication binds more tightly than addition i.e. it should be (|R|+1) x d.
clarity,_quality,_novelty_and_reproducibility: The paper's clarity and reproducibility needs improving. The quality and novelty of the work is good.
summary_of_the_review: The paper makes a solid technical contribution and validates it well empirically. Some questions remain (see above).

I will raise my score if my concerns regarding clarity and reproducibility are addressed.

EDIT: The rebuttal has addressed my concerns, I have adapted my score accordingly.

EDIT EDIT: Due to the concerns regarding the empirical evaluation, I have to lower my score again.

EDIT EDIT EDT: The new results have resolved the concerns surrounding the empirical evaluation.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies compositional rule learning for knowledge graph reasoning, and a model called the NCRL is proposed. NCRL is able to break a rule into small compositions for reasoning, and a recurrent attention unit is proposed to integrate different relational paths. Experimental results on several benchmarks are impressive.
strength_and_weaknesses: Strengths:
1. The problem of learning logic rules is important for knowledge graph reasoning, which could also inspire more advanced models for other reasoning problems.
2. The idea of breaking rules into small compositions is intuitive and effective, as illustrated in Figure 1. The proposed approach is easy to follow.
3. The proposed approach achieves SOTA results on many datasets such as WN18RR.

Weaknesses:
1. Compositional Horn rules have been widely used for knowledge graph reasoning. It is unclear whether the proposed framework can generalize to other more complicated rules.
2. The experiment can be further improved.

Below are some detailed comments:
1. NCRL uses compositional Horn rules for knowledge graph reasoning. Although the results are impressive, such logic rules have been widely explored. In order to develop more advanced models for knowledge graph reasoning and other reasoning tasks, I believe that some more complicated logic rules are needed (e.g., some tree-structured rules). I wonder whether NCRL can also model such logic rules.
2. In Eq. (2), the proposed model uses a RNN for representation learning. Why does NCRL choose to use RNN? Whether some more advanced sequence models such as Transformer can help?
3. On WN18RR, NCRL achieves SOTA results while on FB15K-237 the results are slightly worse. Is there any intuition why NCRL gets better results on WN18RR? Is this because WN18RR is more sparse in terms of the number of triples? This might be important if we would like to develop better models in the future.
4. In the experiment, only some small datasets are considered. Is it possible to apply NCRL to some larger datasets, such as the OGB dataset?
clarity,_quality,_novelty_and_reproducibility: See comments above.
summary_of_the_review: See comments above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new approach to learning chain-like Horn rules by constructing the relation composition hierarchy in rule bodies from sample paths and by extracting the rule bodies from learnt relation embeddings. Experimental results on two tasks, namely link prediction and inductive relational reasoning, demonstrate the advantages of the proposed approach.
strength_and_weaknesses: Strengths:

(1) Learning chain-like rules by composing the body atoms step by step has a lower time complexity than learning rules by generating all body atoms at a time. This efficiency benefit has been confirmed by experiments.

(2) Rather extensive experiments on two different tasks have been conducted to demonstrate that the proposed approach NCRL outperforms the state-of-the-arts. In particular, in the link prediction task NCRL is shown to achieve the best performance among all state-of-the-art rule learning approaches that do not consider entity embeddings.

Weaknesses:

(1) The superiority in performance depends on the sampled results on relation paths in the given knowledge graph. That is, this superiority depends on random sampling, and thus it is not stable and unconvincing. The paper should report the average and std results for different runs of the proposed approach. It would be better if different sampling strategies can also be compared with each other to draw a guideline for selecting an appropriate sampling method.

(2) The learnt rules are more restricted than ordinary chain-like Horn rules since they require that adjacent body atoms appearing in siblings of the composition hierarchy should be able to compose a named relation. It is unclear whether this lower expressivity impacts the performance in link prediction or inductive relational reasoning, and whether this restriction can be removed to increase the expressivity to meet broader application requirements.

clarity,_quality,_novelty_and_reproducibility: The quality of the paper is questionable in terms of technical soundness. The performance of the proposed approach depends on random sampling, and it is unclear how randomness impacts the performance and how the proposed approach guarantees a stable performance in considering tasks. The clarity of the paper is generally good except the aforementioned issues in technical soundness. The main originality lies in learning chain-like rules by composing relational sub-chains within a window of fixed size. A similar idea for hierarchical rule induction has been published in ICML2022 [1]. The authors may add the comparisons with [1] in Related Work to highlight their originality. The source code is provided in the supplemental material but there are no guidelines provided to download the datasets and to reproduce the experimental results.

[1] Claire Glanois, Zhaohui Jiang, Xuening Feng, Paul Weng, Matthieu Zimmer, Dong Li, Wulong Liu, Jianye Hao: Neuro-Symbolic Hierarchical Rule Induction. ICML 2022: 7583-7615

summary_of_the_review: The paper has a major problem in technical soundness by considering that it is based on random sampling and may not yield stable performance. The expressivity of learnt rules is lower than ordinary chain-like Horn rules. This means that the proposed approach is probably inferior to state-of-the-art methods that learn ordinary chain-like Horn rules, in scenarios where the expressivity of ideal rules is higher than the supported expressivity.

AFTER RESPONSE:
I increased the overall score since the authors reasonably addressed my main concerns.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary: authors propose an end-to-end approach for learning compositional rules
Strength: interesting approach with good empirical performance
Weakness: Design of experimental setup
justification_for_why_not_higher_score: Issues with initial experimental setup
justification_for_why_not_lower_score: Nice technical contribution with eventually satisfying experiments.
Decision: Accept: poster