Neural Compositional Rule Learning for Knowledge Graph Reasoning
Authors: Kewei Cheng
Nesreen Ahmed
Yizhou Sun
Venue: ICLR 2023 poster (2023)
Keywords: Logical Rule
Knowledge Graph
Reasoning
Compositionality
Systematicity

Abstract: Learning logical rules is critical to improving reasoning in KGs. This is due to their ability to provide logical and interpretable explanations when used for predictions, as well as their ability to generalize to other tasks, domains, and data. While recent methods have been proposed to learn logical rules, the majority of these methods are either restricted by their computational complexity and can not handle the large search space of large-scale KGs, or show poor generalization when exposed to data outside the training set. In this paper, we propose an end-to-end neural model for learning compositional logical rules called NCRL. NCRL detects the best compositional structure of a rule body, and breaks it into small compositions in order to infer the rule head. By recurrently merging compositions in the rule body with a recurrent attention unit, NCRL finally predicts a single rule head. Experimental results show that NCRL learns high-quality rules, as well as being generalizable. Specifically, we show that NCRL is scalable, efficient, and yields state-of-the-art results for knowledge graph completion on large-scale KGs. Moreover, we test NCRL for systematic generalization by learning to reason on small-scale observed graphs and evaluating on larger unseen ones.

Published as a conference paper at ICLR 2023
NEURAL COMPOSITIONAL RULE LEARNING FOR KNOWLEDGE GRAPH REASONING
Kewei Cheng"
Nesreen K. Ahmed
Department of Computer Science, UCLA viviancheng@cs ucla edu
Intel Labs
nesreen. k. ahmed@ nttl coom
Yizhou Sun
Department of Computer Science, UCLA yzsunêes. ucla. edu
ABSTRACT
Learning logical rules is critical improving reasoning in KGs. This due their ability to provide logical and interpretable explanations when used for pre- dictions, well as their ability to generalize to other tasks, domains, and data. While recent methods have been proposed to learn logical rules, the majority of these methods are either restricted by their computational complexity and can- not handle the large search space of large-scale KGs, or show poor generalization when exposed to data outside the training set. this paper, we propose an end- to-end neural model for learning compositional logical rules called NCRL. NCRL detects the best compositional structure a rule body, and breaks it into small compositions in order to infer the rule head. By recurrently merging compositions in the rule body with a recurrent attention unit, NCRL finally predicts a single rule head. Experimental results show that NCRL learns high-quality rules, well being generalizable. Specifically, we show that NCRL is scalable, efficient, and yields state-of-ther the-trrtttttttii results for knowledge graph completion on kurge-scale KGs. Moreover, we test NCRL for systematic generalization by learning to reason on small-scale observed graphs and evaluating on larger unseen ones.
INTRODUCTION
Knowledge Graphs (KGs) provide a structured representation of real-world facts (Ti et al. 202T) and they remarkably useful in various applications (Graupmann et al. 2005 Lukovnikov et al., 2017 Xiong et al. 2017: Yih et al. 2015). Since KGs are usually incomplete, KG reasoning is crucial problem in KGs, where the goal is infer the missing knowledge using the observed facts.
This paper investigates how to learn logical rules for KG reasoning. Learning logical rules is critical for reasoning tasks in KGs and has received recent attention. This is due to their ability to: (1) pro- vide interpretable explanations when used for prediction. and (2) generalize to new tasks, domains, and data (Qu al. 2020 Lu al. 2022 Cheng al., 2022). For example, in Fig. the learned rules can be used to infer new facts related to objects that are unobserved the training stage.
Moreover, logical rules naturally have interesting property called compositionality: where the meaning of a whole logical expression is a function of the meanings of its parts and of the way they are combined (Hupkes al. 2020). To concretely explain compositionality. let consider the family relationships shown in Fig. 2 In Fig. ala). we show that the rule (hasUncle +- hasMother A hasMother A hasSon) forms composition smaller logical expressions, which can be expressed as a hierarchy, where predicates (i.e., relations) can be combined and replaced by another single predicate. For example, predicates hasMother and hasMother can be combined and replaced by predicate hasGrandma as shown in Fig. aa.. As such, by recursively combining predicates into a composition and reducing the composition into a single predicate, we can finally infer the rule head (i.e., Naslncle) from the rule body. While there are various possible hierarchical trees to represent such rules, not all of them are valid given the observed relations in the KG. For example, in
work done when author was intern Intel Labs

---

Published as a conference paper at ICLR 2023
Training Graph
b. Test Graph
Aetyy
Fass Klathar
lom
①1 hasGrandmabur/ Mastothetttttttt.aooooooo h/wastttttthhthh.......
hastinda
haaSon
2 hasUnclefsyl ha Shassttt
hasSon
hasGrandma
hash RasiHuaabbndde aaama
hechlrther
hasUndieuua
Motther
hasGrandma
hasMotherik, zz sh
Jone
Emnra
hasMother(AAn Sue) www.suuuu///hhMhheeSSSaaa (Sun, Army) AattaanddaaAAnAmmrr
hasUnndejAlice, hastunddAAicc.Bee---saatttteeeed haaaj)--assMoctee/iiiieeeeeeee
(aaUncie(KateeTTmm)--- haaenn/-aanaanndaaaasstaeee Aunj/ hasSon(/vn,.omm
AhasSon(Bess.Bot
Illustration of how the compositionality of logical rules helps improve systematic generalization. (a) logical rule extraction from the observed graph (i.e., training stage) and (b) Inference an unseen graph (i.e., test stage). The train and the test graphs have disjoint sets of entities. By combining logical rules I and ② we can successfully learn rule ( for prediction on unseen graphs.
Figure I:
Fig. 2(b). given a KG which only contains relations (hasMother, hasSon, hasGrandma, hasUncle); }, it possible to combine hasMother and hasSon first. However, there is proper predicate to represent it in the KG. Therefore, learning a high-quality compositional structure for a given logical expression is critical for rule discovery, and it is the focus of our work.
In this work, our objective is to learn rules that generalize large-scale tasks and unseen graphs.
Hierarchical Tree (a) /
Hierarchical Tree (b) X
hasUnole
Unknown
Let us consider the example in Fig. | From the training KG, we can extract two rules rule D: hasGrandma(r: y) + hasMother(x,,2) A hasMother(z; y) and rule 2: hasUncle(1;, y) < hasGrandma(z,, =) A hasSon(z, v). We also ob- serve that the necessary rule to infer the rela- tion between Alice and Bob in the test KG is rule 3: hasUncle 3) + hasMother(z; 21) A hasMother 21, 22) A hasSon(22, y), which is not ob- served in the training KG. However, using compo- sitionality combine rules ! and 2), we can suc- cessfully learn rule 3 which is necessary for inferring the relation between Alice and Bob in the test KG. The successful prediction in the test KG shows the model's ability for systematic general- ization, i.c., learning to reason on smaller graphs and making predictions on unseen graphs (Sinhal et al. 2019).
hasGrandma
Unknows
banMother hasMother hasSon
hootother
hasMetthrr
haoSon
Relations hasbkather, hadton, haGGandma, hastide Query: 2- banMtthhr hasMother hasdon
Learning an accurate hierarchical structure is significant for rule discovery: (a) a good compositional structure; (b) an improper compositional structure.
Figure 2:
Although compositionality is crucial for learning logical rules, most of existing logical rule learn- ing methods fail to exploit it. In traditional AI, inductive Logic Programming (ILP) (Muggleton & De Raedi] 1994] Muggleton et al. 1990) is the most representative symbolic method. Given a col- lection of positive examples and negative examples, an IIP system aims to learn logical rules which are able to entail all the positive examples while excluding any of the negative examples. However, it is difficult for ILP to scale beyond small rule sets due to their restricted computational complexity to handle the large search space of compositional rules. There are also some recent neural-symbolic methods that extend ILP, e.g., neural logic programming methods (Yang et al., 2017 Sadeghian et al. 2019) and principled probabilistic methods (Qu et al. 2020). Neural logic programming si- multaneously learns logical rules and their weights in a differentiable way. Alternatively, principled probabilistic methods separate rule generation and rule weight learning by introducing a rule gen- erator and a reasoning predictor. However, most of these approaches are particularly designed for the KG completion task. Moreover, since they require an enumeration of rules given a maximum rule length T. the complexity of these methods grows exponentially as max rule length increases, which severely limits their systematic generalization capability. To overcome these issues, several works such as conditional theorem provers (CTPs) (Minervini et al., (220)), recurrent relational rea- soning (R5) (Lu et al., 2022) focused on the model's 's systematicity instead. CTPs learn an adaptive strategy for selecting subsets of rules to consider at each step of the reasoning via gradient-based op- timization while R5 performs rule extraction and logical reasoning with deep reinforcement learning equipped with dynamic rule memory. Despite their strong generalizability to larger unseen graphs beyond the training sets (Sinha et al. (2019), they cannot handle KG completion tasks for large-scale KGs due to their high computational complexity.
2

---

Published as a conference paper at ICLR 2023
In this paper, propose end-to-end neural model to learn compositional logical rules for KG reasoning. Our proposed NCRL approach is scalable and yields state-of-the-an (SOTA) results for KG completion
large-scale KGs. NCRL shows strong systematic generalization when tested on larger unseen graphs beyond the training sets. NCRL, views a logical rule as a composition of predicates and learns hierarchical tree to express the rule composition. More specifically, NCRL breaks the rule body into small atomic compositions in order to infer the rule head. By recurrently merging compositions in the rule body with recurrent attention unit, NCRL finally predicts single rule head. The main contributions of this paper are summarized as follows:
We formulate the rule learning problem from new perspective and define the score of a logical rule based on the semantic consistency between rule body and rule head.
NCRL presents an end-to-end neural approach to exploit the compositionality of a logical rule in recursive way improve the models' systematic generalizability.
NCRL is scalable and yields SOTA results for KG completion on large-scale KGs and demon- strates strong systematic generalization to larger unseen graphs beyond training sets.
2 NOTATION & PROBLEM DEFINITION
Knowledge Graph. A KG, denoted by G E R, O}, consists of set of entities E, set of relations R. and a set of observed facts O. Each fact in O is represented by a triple (errk: rk. ex))
special case of first-order logical rules, composed of body of conjunctive predicates (i.c., relations are called also predicates) and a single-head predicate. In this paper, we interested in mining chain-like compositional Horn rules
Horn Rule. Horn rules,
I in the following form.
s rb) (a 3) < rb, (2, A A.. A Tb., (3
where s(Th: rb) E [0, 1J is the confidence score associated with the rule, and rh (I, y) called rule head and rb, (I, 21) A ... A rb., (2n-1.8) y) is called rule body. Combining rule head and rule body, we denote a Horn rule as (r,, where rb [rb, [rb....... ............. .b..
Logical Rule Learning. Logical rule learning aims to learn confidence score s(rn. Ib) for each rule (rh, rb) in rule space to measure its plausibility. During rule extraction, the top rules with the highest scores will be selected as the learned rules.
NEURAL COMPOSITIONAL RULE LEARNING (NCRL)
In this section, we introduce our NCRL to learn compositional logical rules. Instead of using the fre- quency of rule instances to measure the plausibility of logical rules, define the score of a logical rule as the probability that the rule body can be replaced by the rule head based on its semantic con- sistency. The semantic consistency between a rule body and rule head means that the body implies the head with a high probability. An overview of NCRL is shown in Fig. 3 NCRL starts by sampling of paths from given KG, and further splitting each path into short compositions using sliding window. Then, NCRL uses a reasoning agent to reason over all the compositions to select one com- position. NCRL uses a recurrent attention unit transform the selected composition into a single relation represented as weighted combination of existing relations. By recurrently merging compo- sitions in the path, NCRL finally predicts the rule head. Algorithm [uutines the learning procedure of NCRL. Source code is available at htttts:://gtthiii hub. com/ siviann993. 11///n11999/........ git
3.1 LOGICAL RULE LEARNING WITH RECURRENT ATTENTION UNIT
As discussed in Section I while the rule body can be viewed as sequence, it naturally exhibits a rich hierarchical structure. The semantics of the rule body is highly dependent on its hierarchical structure, which cannot be exploited by most of the existing rule learning methods. To explicitly allow our model to capture the hierarchical nature of the rule body, we need to learn how the relations in the rule body are combined as well as the principle to reduce each composition in the hierarchical tree into a single predicate.
An instance of rule hody of chain-like compositional Horn rules corresponding to a path in KG
3

---

Published as a conference paper at ICLR 2023
Recumnet Attertion Usi
Recument Altertion Usi
Recurrnn Altentin
Thanning Crish
Viluo
(Faira)
Vake
Riad Pockidian
BAD
Crint
Crosi Atrection
Yy4 BX0
Crowa Atteetion
Antettonn
ID nb
Pain
Selection
Selecion
Selection
00
Siding Window Encoder
Siding Window Freeder
Steling Window Encoder
Dru 01
5
U17s (k(r))
Tarattrs
An overview of NCRL. It samples paths from KG (e.g-(ri, ra, ra), and predicts the relations that directly connect the sampled paths (e.g..ra) based on the learned rules. NCRL takes the embeddings of predicates in the sampled paths as the input and outputs 0 as the probability of cach relation to be the rule head.
Figure 3:
3.1.1 HIERARCHICAL STRUCTURE LEARNING
The hierarchical structure of logical rules is learned in an iterative way. At each step, NCRL selects only one composition from the rule body and replaces the selected composition with another sin- gle predicate based on the recurrent attention unit to reduce the rule body. Although rule body is hierarchical, when operations are very local (i.e.. leaf-level composition), a composition is strictly sequential. To identify a composition from sampled path, we use sliding window with different lengths to decompose the sampled paths into compositions of different sizes. In our implementation, we vary the size of the sliding window among (2, 3). Given fixed window size sliding windows are generated by size window which slides through the rule body rb = [rb....,,h,.]
Sliding Window Encoder. When operations are over local sliding window (i.e., composition), the relations within a sliding window should strictly follow a chain structure. Sequence models can be utilized to encode a sliding window. Considering the tradeoff between model complexity and performance, we chose RNN (Schuster & Paliwal 1997) over other sequence models to encode the sequence. For example, taking č-th sliding window whose size is 2 (i.e., wi [Tb,, Tb..1) as the input, RNN outputs:
h; h,41] RNN(w;)
(2)
where h, Id is a hidden-state of predicate ro. in wi. Since the final hidden-state h, is usually used to represent the whole sequence, we represent the sliding window as w, = h;+1-
Composition Selection. w; is useful to estimate how likely the relations in i-th window appear together. If these relations always appear together, they have higher probability to form a mean- ingful composition. To incorporate this observation into our model, we select the sliding window by computing:
f softmax([f(w1)) f(22) I (W
where I is fully connected neural network. It learns the prohability of i-th window to be mean- ingful composition from its representation w;- wy with the highest μ4, will be selected as the input to the recurrent attention unit.
3.1.2 RECURRENT ATTENTION UNIT
Note that rule induction following its underlying hierarchical structure is recurrent process. There- fore, we propose novel recurrent attention unit to recurrently reduce the selected composition into single predicate until it outputs a final relation.
Attention-based Induction. The goal of recurrent attention unit is reduce the selected com- position into single predicate, which can be modeled as matching the composition with another single predicate based on its semantic consistency. Since attention mechanisms yield impressive results in Transformer models by capturing the semantic correlation between every pair of tokens in natural language sentence (Vaswani et al., 2017). we propose to utilize attention to reduce the se- lected composition w,. Note that may not always find an existing relation to replace the selected composition. For example, given the composition [hasBrother, has Wife), none of the existing rela- tions can be used represent it. As such, in order accommodate unseen relations, we incorporate
4

---

Published as a conference paper at ICLR 2023
"null" predicate into potential rule heads and denote it as To- The embedding corresponding to ro is set as the representation of the selected composition w,. In this way, when there is no direct link closing sampled path (which means we do not have the ground truth about the rule head), we use the representation of the selected composition to represent itself rather than replace it with an existing relation. Let H E [2([)+))xd be the matrix of the concatenation of all head relations, where Hg w; IR is set as the selected composition. By taking w; as query and H as the content, the scaled dot-product attention a can be computed to estimate the semantic consistency between the selected composition and its potential heads:
w, WWWWHHWK
= softmax
(4)
Vd
where Wo, WK E Rddd are learnable parameters that project the inputs into the space of query and key. E R RR +1 is the learned attention, in which 0, measures p(ry/w;) - the probability that the selected composition can be replaced by the predicate r; based on their semantic consistency. Given O, we are able to compute a new representation for the selected composition as a weighted combination of all head relations (i.e., values) each weighted by its attention weight:
Wi- OHWV
(5)
where W; E IRd is the new representation of the selected composition. We project the key and value
to the same space by requiring Wy WK because the keys and the values are both embeddings of relations in KG. As shown in Fig. we can reduce the long rule body [rb, Tb2 ..... rb, by recursively applying the attention unit to replace its composition (rb. Tb++.) with a single predicate. In the final step of the prediction, the attention O computed following Eq. coollects the probability that the rule body can be replaced by each of the head relations.
3.2 TRAINING AND RULE EXTRACTION
NCRL is trained in an end-to-end fashion. It starts by sampling paths from an input KG and predicts the relation which directly closes the sampled paths based on learned rules.
Path Sampling. We utilize a random walk (Spitzer (013) sampler to sample paths that connect two entities from the KG. Formally, given source entity zi, we simulate a random walk of max length Let 23 denote the i-th node in the walk, which is generated by the following distribution:
if (e), E otherwise
p(z, = -. =e)
Wos O,
(6)
where (N(e))) is the neighhorhood size of entity eg. Different from random walk, each time after we sample the next entity I,, we add all the edges which can directly connect xo and z;. We denote the path connecting two nodes 2n and Vn, as p. where p [ ]b,,, indicating To ". "ny Σn. We also denote the relation that directly connects xo and H,, as тy- If none of the relations directly connects the zn and Fa, we set as "null". We control the ratio of non-closed paths to ensure a majority of sampled paths are associated with an observed head relation.
Objective Function. Our goal is to maximize the likelihood of the observed relation rhe which directly closes the sampled path p. The attention collects the predicted probability for p being closed by each of the head relations. We formulate the objective using the cross-entropy loss as:
Σ (P
Σ
xh log 0º
where P denotes set of sampled paths from given KG, T* vector such that only the rheth entry is 1, and Or E [R| is the learned attention for the sampled path p. In particular, 66 represents the probability that the sampled path cannot be closed by any existing relations in KG.
Th E {0, 1| is the one-hot encoded
00 is specific the query composition w..
5

---

Published as a conference paper at ICLR 2023
Rule Extraction. To recover logical rules, cal- culate the score s(n,, Tb) for each rule (rh, rb) in rule space based on the learned model. Given candidate rule (r,, lb), we reduce the rule body rb into single head ra by recursively merge com- positions in path rb. At the final step of the pre- diction, we learn the attention 0 1..,..., 0mn] where Og is the score of rule (rx; rb). The top k rules with the highest score will be selected as learned rules.
Algorithm 1: Learning Algorithm
Input:
Observed triples in KG O Output: Relation embeddings
(SamplcPatss(O)
2 for (p) E TP do while len(p) >
If Decompose with sliding window; whose size
[....... Wn+1-al -.]== Decompose(p)
6
#f Selectt a composition
[wi..... Wa s|=
RNN([W -e--1-a)
8
w; Select( [W1: .... w..1 >))
9
If Apply recurrent attention unit
w. = =Attn(..)
EXPERIMENTS
If Reduce the sampled path p
[bb
Pbb.
logical rules valuable for various downstream 13
end
tasks, such as (1) KG completion task, which aims infer the missing entity given the query (h, r, 15 w = RNN(p)
Final prodiction
Take the query compute based on
or (?,r. t); (2) A more challenging inductive re- lational reasoning task, which tests the systematic
17
Minimize the loss in Egg
generalization capability of the model by inferring
the missing relation between two entities (i.e., (h, ()) with more hops than the training data. A majority of existing methods can handle only one of these two tasks (e.g.. RNNLogic is designed for the KG completion task while R5 is designed for the inductive relational reasoning task). In this
section, we show that method is superior to existing SOTA algorithms on both tasks. In addition, we also empirically assess the interpretability of the learned rules.
4.1 KNOWLEDGE GRAPH COMPLETION
KG completion is classic task widely used by logical rule learning methods such as Neural- LP (Yang al. 2017). DRUM (Sadeghian et al. 2019) and RNNLogic (Qu al. 2020) to evaluate the quality of learned rules. An existing algorithm called forward chaining (Salvat & Mugnier 1996) can be used predict missing facts from logical rules.
Datasets. We use six widely used benchmark datasets to evaluate our NCRL in comparison to SOTA methods from knowledge graph embedding and rule learning methods. Specifically, we use the Family (Hinton et al.) 1986). UMLS (Kok& & Domingos) 2007). Kinship (Kok & Domingos, (007)) WNISRR (Dettmers et al. 2018), FB 15K-237 (Toutaoova & Chen 2015), YAGO3-10 (Suchanek
al. 2007) datasets. The statistics of the datasets are given in Appendix 1.
Evaluation Metries. We mask the head or tail entity of each test triple and require each method to predict the masked entity. During the evaluation, we use the filtered setting (Bordes et al. 2013) and three evaluation metrics, i.c., Hit@ 1, Hit@ @ 10, and MRR.
Comparing with Other Methods. We evaluate method against SOTA methods, including (1) traditional KG embedding (KGE) methods (c.g.. TransE (Bordes et al.; 2013), DistMult (Yang et al.)
2014). ConvE (Dettmers al. 2018), ComplEx (Trouillon et al. (016) and RotatE (Sun et al.
2019 ); (2) logical rule learning methods (c.g.. Neural-LP (Yang et al. 2017), DRUM (Sadeghian
al. 2019), RNNLogic (Qu et al. 2020) and RLogic (Cheng et al. | (022)) D. The systematic general-
izable methods (e.g., CTPPs and R5) cannot handle KG completion tasks due to their high complexity.
The comparison results presented in Table [ We observe that: (1) Although NCRL is not designed for KG completion task, compared with KGE models, it achieves comparable re- sults on all datasets, especially on Family, UMLS, and WNI8RR datasets; (2) NCRL consistently outperforms all other rule learning methods with significant performance gain in most cases.
Results.
4.1.1 ABLATION STUDY
Performance w.r.t. Data Sparsity. We construct sparse KG by randomly removing triples from the original dataset. Following this approach, we vary the sparsity ratio a among {0.33, 0.66, 1} and report performance
different methods presented in Fig. 4 the performance of NCRL does not vary a lot with different sparsity ratio a, which is appealing in practice. More analysis of other datasets is given in Appendix A.3.2.
the KG completion task on Kinship dataset. As

---

Published as a conference paper at ICLR 2023
Table KG completion. The red numbers represent best performances among methods, while the blue numbers represent the best performances among all rule learning methods.
Methods
Models
Family Hit@:
Kinship Hit@1
UMLS
MRR
Hit 10
MRR
Hit 10
MRR
Hi@@
Hit@
TransE
22.1
0.31
0.9
523
DistMult
0.54
36.0
88.5
0.35
18.9
75.5
0.391
25.6
66.9
KGE
ComplEx
0.81
72.7
94.6
0.42
24.2
81.2
0.41
27.3
70.0
RotatE:
0,86
78.7
93.3
0.65
50.4
93.2
0.74
63.6
93.9
Neural-LP
0.88
80.1
98.5
0.30
16.7
59.6
0.48
33.2
77.5
DRUM
Rule Learning
RNNLogic
0.86
79.2
95.7
0.64
49.5
92.4
0.75
63.0
92.4
RLogic
0.88
81.3
97.2
0.58
43.4
87.2
0.71
56.6
93.2
NCRL
0.91
85.2
99.3
0.64
49.0
92.9
0.78
65.9
95.1
WNI8RR
FB15K-237
YAGO3-10
Methods
Models
H1
TrunsE
0.23
2.2
52.4
0.29
18.9
46.5
0,36
25.1
58.0
DistMult
0.42
38.2
50.7
0.22
13.6
38.8
0.34
24.3
53.3
KGE
ConvE
0.43
40.1
52.5
0.32
21.6
50.1
0.44
35.5
61.6
ComplEx
0.44
41.0
51.2
0.24
15.8
42,8
0.34
24.8
54.9
Rotat::
42.9
Neural LP
0.38
36.8
40.8
0.24
17.3
36.2
DRUM
0.38
36,9
41.0
0.23
17.4
36.4
Leamiing
Rule
RNNLogic
0.46
4144
0.29
20.8
44.5
RLogic 0.47
44.3
53.7
0.31
20.3
50.1
0.36
25.2
50.4
NCRL
N. ogic excoed monory cogucity muchines on YAGO3-10 dutaset
Kup
0.2
335
220
1/7
170
20 50
106
200
Performance KG Figure 6: Performance KG completion vs sparsity ratio on Kin- completion vs # logical rules on completion vs embedding dimen- sion on Kinship.
Figure Performance KG Figure 5:
ship.
Kinship.
KG completion performance w.r.. the Number Learned Rules. We generate rules with the highest qualities per query relation and use them to predict missing links. We vary k among {10, 20, 40, 60, 80, 100}. The results on Kinship are given Fig. 5 We observed that even with only 10 rules per relation, NCRL still givens competitive results. More analysis of other datasets is given in Appendix A.3.2.
Performance w.r.t. Embedding Dimension. We vary the dimension of relation embeddings among {10, 100, 200, 500, 1000, 2000} and present the results on Kinship in Fig. 6 comparing against RLogic (Cheng et al. 2022). We that the embedding dimension has significant impact on KG completion performance. The best performance is achieved at d = 1000.
4.2 TRAINING EFFICIENCY
To demonstrate the scalability of NCRL,, give the training time of NCRL against other logical rule learning methods on three benchmark datasets in Table We ob- serve that: (1) Neural-LP and DRUM do not perform well in terms of efficiency as they apply a sequence of large matrix multiplications for logic reasoning. They cannot handle YAGO3-10 dataset due to the memory issue; (2)
Table Training time (s) rule learning methods
Neurall 1,308
RNNLogie 1.044
WINTERI
1,146
77
1B15K-233
23,708
22,428
410
YAG03-10
190
It is also challenging for RNNLogic to scale to large-scale KGs it relies all ground rules to evaluate the generated rules in each iteration. It is difficult for it to handle KG with hundreds of relations (c.g., FB15K-237) nor KG with million entities (c.g.. YAGO3-10); (3) our NCRL is average 100x faster than state-of-ther ther--art baseline methods.

---

Published as a conference paper at ICLR 2023
Table 3: Results of inductive relational reasoning on CLUTRR dataset. Trained on path samples with hops {2, 3, 4) and evaluated on path samples with hops (5...., ,,...,,0), 10). mances while the brown numbers represent the second best performances.
The red numbers represent the best perfor-
Hops
Model
Hops
Hops
7 Hops
8 Hops
Hops
Hops
RNN
0,931:0.06
0.87:10.07
0.79:10.11
0.731:0112
0.651:0116
0.641:0.16
LSTM
0.98110.33
0,95110004
0.89110.10
0.84.0..7
0.7740.11
0.78:10.11
GRU
0.95:10.04
0.94::0003
0.87::088
0.81::0113
0.741:.115
0.75
Transformer
0.8000.33
0.831.0.55
0.76.10.04
0.72.10.04
0.741.0.05
0.70.10.03
GNTP
0.68
0.6340.34
0.6240.31
0.59:40.32
0.574:0.4
0,52::0,32
GAT
0.99
0.85:00004
0.80:20.03
0.71::0.05
0.70
0.68
GCN
0.94
0.79::002
0.61
0.53::0.04
0.53
0.41::0.04
CTPL
0.902100.02
0.98:10.04
0
0.98:10003
0.97:::004
0.95:10.04
CTP A
0.99 0.99.10.04
0.99.1:003
0.97:1..033
0.95
0.93
0.915
СТP
0.98++0.04
0
0,95+0006
0,94+00088
0,93+0008
0
RLogic
0.99:1:0.02
0.98:+0.02
0.97
0.97=20.05
0.94
0.94
R5
0.99:1:000
0.99:1:0004
0.99-10.03
100:10.02
0.99-10.02
0
NCRL
10:00.01
0.99:40.01
0.98
0.98:20.03
0.98::00033
0.97:0002
Table Results inductive relational reasoning on GraphLog datasets for robustness analysis.
CTP
RLogic
R5
NCRL
ACC
Recall
ACC
Recall
ACC
Recall
ACC
Recall
World
0.685=0.03
0.80::0:00
0.726:0000
0.95
10:00:00
0.774=0.01
10=0.00
World
0.624
0.85:10.000
0.737:10.02
1.0:10.00
0.701
1.0::0000
0.797=0000
1.0:20.00
World
0.533 =0.03
0.85::0000
0.638 #:003
0.00
0.687:00.05
0.9:00000
0.702
0.02
0.93=00000
World
0.545=0.02
0.70:10:00
0.605+10.02
0,90-:00000
0.671::0.05
0.95:00.00
0.687 0.02
0.95-+:0.00
4.3 SYSTEMATIC GENERALIZATION
We test NCRL for systematic generalization to demonstrate the ability of NCRL to perform reason- ing over graphs with more hops than the training data, where the model is trained on smaller graphs and tested on larger unseen ones. The goal of this experiment to infer the relation between node pair queries. We use two benchmark datasets: (1) CLUTRR (Sinha et al.] 2019) which is a dataset for inductive relational reasoning over family relations, and (2) GraphLog (Sinha al., (2020) is benchmark suite for rule induction and it consists of logical worlds and each world contains graphs generated under a different set of rules. Note that most existing rule learning methods lack system- atic generalization. CTPs (Minervini et al., (2020), R5 (Lu et al.) (022), and RLogic (Cheng et al.) 2022) are the only comparable rule learning methods for this task. The detailed statistics and the description of the datasets are summarized in Appendix 1.4.1.
Systematic Generalization on CLUTRR. Table 3 shows the results NCRL against SOTA algo- rithms. Detailed information about the SOTA algorithms is given in Appendix A.4.2. We observe that the performances of sequential models and embedding- path length grows longer while NCRL still prediets successfully longer paths without significant performance degradation. Compared with systematic generalizable rule learning methods, NCRL has better generalization capability than CTPs especially when the paths grow longer. Even though R5 gives invincible results over CLUTRR dataset, NCRL shows comparable performance. Systematic Generalization on GraphLog. Table g shows the results on 4 selected worlds. We observed that NCRL consistently outperforms other rule-learning baselines over all 4 worlds.
models drop severely when the
4.4 CASE STUDY OF GENERATED LOGICAL RULES
Finally, we show case study of logical rules that are generated by NCRL on the YAGO3-10 dataset in [5] We can see that these logical rules are meaningful and diverse. Two rules with different lengths are presented for each head predicate. We highlight the composition and predicate which share the same semantic meaning with boldface.
RELATED WORK
Inductive Logic Programming. Mining Horn clauses have been extensively studied in the Induc-
tive Logic Programming (ILP) (Muggleton & De Raedt 1994 Muggleton al. 1990 Muggleton 1992 Nienhuys-Chaen & De Wolf (199]]Quinlam 1990 Tsunoyama et al. 2008 Zelle & Mooney Given a set of positive examples and set of negative examples, II. system learns logical
1993
8

---

Published as a conference paper at ICLR 2023
Table 5: Top rules learned on YAGO3-10. We highlight the composition and predicate which share the same semantic meaning with boldface.
isL.catedII((2 z. y) + bsLocatedIn(2; =) A isLatctee y)
isLocatedIn| 2, y) + hasAAcademicAddiioori.. 21) isLocatedIn 22) A isLocatedIn( (22,
isAffiliate 8) - isKnownFor(2; 2) A isAffiliated To( M)
isAffiliated (o; 3) < isKnownfor(2;, 21) A IsAffliateeTo(21.....2 (2) isLeaderOf(22 v)
playsFor(a:, (z. y) < isKnownFor(zz, #) IsAffilittee 9)
playsFor(æ, y) < isKnowaFor(a: (xr 21 A playsFor 31, 22) A owns(22.
influcnccs( xx y) - isPoliticiantOf ax 2) A inffuences (2
influences( (z. M) isPoliticianO(((: u #1) A influences(21, 22) A influences(22, v)
rules which are able to entail all the positive examples while excluding any of the negative examples. Scalability is central challenge for IL. methods they involve several steps that NP-hard. Re- cently, several differentiable ILP methods such as Neural Theorem Provers (Rocktäschel & Riedel, 2017 Campero et al.) 2018: Glanois et al., 2022) are proposed to enable continuous relaxation of the logical reasoning process via gradient descent. Different from our method, they require pre- defined dend-designed, and task-specific templates to narrow down the rule space.
Neural-Symbolic Methods. Very recently, several methods extend the idea of ILP by simultane- ously learning logical rules and weights differentiable way. Most of them are based on neural logic programming. For example, Neural-LP (Yang et al., 2017) enables logical reasoning via se- quences of differentiable tensor multiplication. neural controller system based on attention is used to learn the score of specific logic. However, Neural-LP could learn higher score for meaning- less rule because it shares an atom with a useful rule. To address this problem, RNNs are utilized in DRUM (Sadeghian et al. 2019) to prune the potential incorrect rule bodies. In addition, Neural-LP can learn only chain-like Horn rules while NLIL (Yang & Song 2019) extends Neural-LP to learn Horn rules in a more general form. Because neural logie programming approaches involve large matrix multiplication and simultaneously learn logical rules and their weights, which is nontrivial in terms of optimization, they cannot handle large KGs, such as YAGO3-10. To address this issue, RNNLogic (Qu et al. 22200) is proposed to separate rule generation and rule weight learning by introducing a rule generator and a reasoning predictor respectively. Although the introduction of the rule generator reduces the search space, it is still challenging for RNNLogic to scale to KGs with hundreds of relations (e.g., FB15K-237) or millions of entities (e.g.. YAGÓ3-10).
Systematic Generalizable Methods. All the above methods cannot generalize to larger graphs be- yond training sets. To improve models' systematicity, Conditional Theorem Provers (CTPs) is pro- posed to learn an optimal rule selection strategy via gradient-based optimization. For each sub-goal, a select module produces a smaller set of rules, which is then used during the proving mechanism. However, since the length of the learned rules influences the number of parameters of the model, it limits the capability of CTPs to handle the complicated rules whose depth is large. In addition, due to its high computational complexity, CTPs cannot handle KG completion tasks for large-scale KGs. Another reinforcement learning- rent relational reasoning solution learn compositional rules. However, R5 cannot generalize the KG completion task due to the lack of scalability. It requires pre-sampling for the paths that entail the query. Considering that all the triples in a KG share the same training graph, even a relatively small- scale KG contains a huge number of paths. Thus, it is impractical to apply R5 to even small-scale KG for rule learning. In addition, R5 employs hard decision mechanism for merging a relation pair into a single relation, which makes it challenging to handle the widely existing uncertainty in KGs. For example, given the rule body hasAunt(x, =) A hasSisterrz, y), both hasMother(s. y) and hasAunt(z; (z, 3) can be derived as the rule head. The inaccurate merging of relation pair may result in error propagation when generalizing to longer paths. Although RLogic (Cheng et al.) 2022) are generalizable across multiple tasks, including KG completion and inductive relation reasoning, they couldn't systematically handle the compositionality and outperformed by NCRL.
method R5 (Lu et al., 2022) is proposed to provide a recur-
6 CONCLUSION
In this paper, we propose NCRL, an end-to-end neural model for learning compositional logical rules. NCRL treats logical rules as hierarchical tree and breaks the rule body into small atomic compositions in order to infer the head rule. Experimental results show that NCRL is scalable, efficient, and yields SOTA results for KG completion on large-scale KGs.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This work was partially supported by NSF 2211557, NSF 2303037, NSF 1937599, NSF 2119643, NASA, SRC, Okawa Foundation Grant, Amazon Research Awards, Amazon Fellowship, Cisco search grant, Picsart Gifts, and Snapchat Gifts.
REFERENCES
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances neural information processing systems, pp. 2787-2795, 2013.
Andres Campero, Aldo Pareja, Tim Klinger, Josh Tenenbaum, and Sebastian Riedel. Logical rule induction and theory learning using neural theorem proving. arXiv preprint wiXiv:880.00299) 2018.
Kewei Cheng, Jiahao Liu, Wei Wang, and Yizhou Sun. Rlogic: Recursive logical rule learning from knowledge graphs. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 179-189, 2022.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Claire Glamois, Zhaohui Jiang, Xuening Feng, Paul Weng, Matthieu Zimmer, Dong Li, Wulong Liu, and Jianye Hao. Neuro-symbolic hierarchical rule induction. In International Conference on Machine Learning, pp. 7583-7615. PMLR, 2022.
Jens Graupmann, Ralf Schenkel, and Gerhard Weikum. The SphereSearch engine for unified ranked retrieval of heterogeneous XML and web documents. In Proceedings of the 31st international conference on very large data bases, pp. 529-540. VLDB Endowment, 2005.
Geoffrey E Hinton et al. Learning distributed representations of concepts. Proceedings of the eighth annual conference of the cognitive science society, volume pp. 12. Amherst, MA, 1986.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionalliy decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. A survey knowledge graphs: Representation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Systems, 33(2):494-51 514, 2021.
Stanley Kok and Pedro Domingos. Statistical predicate invention. In Proceedings of the 24th inter- national conference on Machine learning, pp. 433-440, 2007.
Shengyao Lu, Bang Liu, Keith G Mills, SHANGLING JUI, and Di Niu. R5: Rule discovery with reinforced and recurrent relational reasoning. In International Conference Learning Represen- tations, 2022. URL http:::::////peeiiiieeeee net/
Denis Lukovnikov, Asja Fischer, Jens Lehmann, and Sören Auer. Neural network- question answering over knowledge graphs on word and character level. In Proceedings of the 26th inter- national conference World Wide Web, pp. 1211-1220. International World Wide Web Confer- ences Steering Committee, 2017.
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies in end-to-end differentiable proving. In International Conference on Machine Learning, pp. 6938-692 PMLR, 2020.
Stephen Muggleton. Inductive logic programming. Number 38. Morgan Kaufmann, 1992.
Stephen Muggleton and Lue De Raedt. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19:629-679, 1994.
10

---

Published as a conference paper at ICLR 2023
Stephen Muggleton, Cao Feng, al. Efficient induction of logic programs. Citeseer, 1990.
Shan-Hwei Nienhuys-Cheng and Ronald De Wolf. Foundations of inductive logic programming. volume 1228. Springer Science & Business Media, 1997.
Meng Qu, Junkun Chen, Louis-Pascas Xhonneux, Yoshua Bengio, and Jian Tang. Runlogic: Learn- ing logic rules for reasoning on knowledge graphs. arXiv preprint arXi::2010.04029 2020.
J. Ross Quinlan. Learning logical definitions from relations. Machine learning, 5(3):239-266, 1990.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. Advances in neural information processing systems, 30, 2017.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to- end differentiable rule mining on knowledge graphs. arXiv preprint arXiv:1911.0005: 2019.
Eric Salvat and Marie-Laure Mugnier. Sound and complete forward and backward chainings of graph rules. In International Conference Conceptual Structures, pp. 248-262. Springer, 1996.
Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE transactions on Signal Processing, 45(1 1)227322668, 1997.
Koustuv Sinha, Shagun Sodhani, Jin Dong. Joelle Pineau, and William L Hamilton. Clutrr: A diagnostic benchmark for inductive reasoning from text. arXiv preprint IrXiv: 06177, 2019.
Koustuv Sinha, Shagun Sodhani. Joelle Pineau, and William L Hamilton. Evaluating logical gener- alization in graph neural networks. arXiv preprint (XXv:20033066600 2020.
Frank Spitzer. Principles of random walk, volume 34. Springer Science & Business Media, 2013.
Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, pp. 697-706, 2007.
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint arXiv:
2019.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionalliy, pp. 57-66, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. International Conference on Machine Learning, pp. 2071-2080, PMLR, 2016.
Kazuhisa Tsunoyama, Ata Amini, Michael JE Sternberg, and Stephen Muggleton. Scaffold hop- ping in drug discovery using inductive logic programming. Journal of chemical information and modeling, 48(5):949 957.999999579900 2008
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Chenyan Xiong, Russell Power, and Jamie Callan. Explicit semantic ranking for academic search via knowledge graph embedding. In Proceedings of the 26th international conference on world wide web, pp. 1271 1279. International World Wide Web Conferences Steering Committee, 2017.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv: /41.65:4//..675,, 2014.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances Neural Information Processing Systems, pp. 2319-2328, 2017.
Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. arXiv preprint arXiv: arXiv:1910.00 19/0.0248. 2019.

---

Published as a conference paper at ICLR 2023
Wentau Yih, Ming-Wor Wei Chang, Xiaodong He, and Jianfeng Gao. Semantic parsing via staged query graph generation: Question answering with knowledge base. In IJCNLP, pp. 1321-1331, Beijing, China, July 2015.
John M Zelle and Raymond J Mooney. Learning semantic grammars with constructive inductive logic programming. In AAAI, pp. 817-822, 1993.
12


Reviews:
[{"review_id": "tJFYSph0z_B", "reviewer": "Reviewer_FLaJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n\nThe authors demonstrate the scalability advantage and the competitive performance of their method against strong rule-learning based methods on a variety of standard benchmarks.\n", "summary_of_the_review": "The paper makes a solid technical contribution and validates it well empirically. Some questions remain (see above).\n\nI will raise my score if my concerns regarding clarity and reproducibility are addressed.\n\nEDIT: The rebuttal has addressed my concerns, I have adapted my score accordingly.\n\nEDIT EDIT: Due to the concerns regarding the empirical evaluation, I have to lower my score again.\n\nEDIT EDIT EDT: The new results have resolved the concerns surrounding the empirical evaluation.", "strength_and_weaknesses": "Strengths:\n - Good technical novelty\n - Good empirical evaluation: demonstrating good performance and good scalability\n \n Weaknesses:\n - 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.\n - Some questions about the implementation remain that would be necessary for reproducibility:\n\t- 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)?\n\t- Will you publish code upon acceptance?\n\t\n - Certain design decisions are unexplained and not studied in the ablation studies:\n\t- 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?\n\t\nQuestions:\n - How is semantic consistency defined in the intro of section 3?\n - 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?\n - 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.\n - Why did you choose to project the key and values to the same space (i.e. W_V = W_K eq5)? \n\nMinor:\n - 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.\n - There is a typo in 4.3, 3rd line at the very end.\n - 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ERWRYhf5FI", "reviewer": "Reviewer_N8Wt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "See comments above.", "strength_and_weaknesses": "Strengths:\n1. The problem of learning logic rules is important for knowledge graph reasoning, which could also inspire more advanced models for other reasoning problems.\n2. The idea of breaking rules into small compositions is intuitive and effective, as illustrated in Figure 1. The proposed approach is easy to follow.\n3. The proposed approach achieves SOTA results on many datasets such as WN18RR.\n\nWeaknesses:\n1. 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.\n2. The experiment can be further improved.\n\nBelow are some detailed comments:\n1. 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.\n2. 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?\n3. 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.\n4. In the experiment, only some small datasets are considered. Is it possible to apply NCRL to some larger datasets, such as the OGB dataset?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9J3XiWU0vT", "reviewer": "Reviewer_XZA5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Strength \n- Proposes an interesting perspective of viewing chain-like rules in KGs via hierarchical compositions, which is different from the classical multi-hop pathfinding view.\n\n\nWeaknesses\n- Some design choices (see below) need more justification\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1Cv4vQMRNJK", "reviewer": "Reviewer_WAeF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.\n\nAFTER RESPONSE:\nI increased the overall score since the authors reasonably addressed my main concerns.", "strength_and_weaknesses": "Strengths:\n\n(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.\n\n(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.\n\nWeaknesses:\n\n(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.\n\n(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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster