RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs
Authors: Meng Qu
Junkun Chen
Louis-Pascal Xhonneux
Yoshua Bengio
Jian Tang
Venue: ICLR 2021 Poster (2021)
Keywords: Knowledge Graph Reasoning
Logic Rules
EM

Abstract: This paper studies learning logic rules for reasoning on knowledge graphs. Logic rules provide interpretable explanations when used for prediction as well as being able to generalize to other tasks, and hence are critical to learn. Existing methods either suffer from the problem of searching in a large search space (e.g., neural logic programming) or ineffective optimization due to sparse rewards (e.g., techniques based on reinforcement learning). To address these limitations, this paper proposes a probabilistic model called RNNLogic. RNNLogic treats logic rules as a latent variable, and simultaneously trains a rule generator as well as a reasoning predictor with logic rules. We develop an EM-based algorithm for optimization. In each iteration, the reasoning predictor is updated to explore some generated logic rules for reasoning. Then in the E-step, we select a set of high-quality rules from all generated rules with both the rule generator and reasoning predictor via posterior inference; and in the M-step, the rule generator is updated with the rules selected in the E-step. Experiments on four datasets prove the effectiveness of RNNLogic.

Published as a conference paper at ICLR 2021
RNNLOGIC: LEARNING LOGIC RULES FOR REASON- ING ON KNOWLEDGE GRAPHS
Meng Qu Junkun Chen Louis-Pascal Xhonneux!., Yoshua Bengio 12,5, Jian Tang'.45
1 Mila - Québec Al Institute
Université de Montréal
TTinghua University
'HEC Montréal
CCanadian Institute for Advanced Research (CIFAR)
ABSTRACT
This paper studies learning logic rules for reasoning on knowledge graphs. Logic rules provide interpretable explanations when used for prediction as well being able to generalize to other tasks, and hence are critical to learn. Existing methods either suffer from the problem of searching in a large search space (e.g., neural logic programming) or ineffective optimization due sparse rewards (e.g., techniques based on reinforcement learning). To address these limitations, this paper proposes probabilistic model called RNNLogic. RNNLogic treats logic rules as a latent variable, and simultaneously trains a rule generator as well as a reasoning predictor with logic rules. We develop EM-based algorithm for optimization. In each iteration, the reasoning predictor is first updated to explore some generated logic rules for reasoning. Then in the E-step, we select a set of high-quality rules from all generated rules with both the rule generator and reasoning predictor via posterior inference; and in the M-step, the rule generator is updated with the rules selected in the E-step. Experiments on four datasets prove the effectiveness of RNNLogic.
INTRODUCTION
Knowledge graphs are collections of real-world facts, which are useful in various applications. Each fact is typically specified as a triplet (h, x. t) or equivalently z/h, t), meaning entity h has relation with entity For example, Bill Gates is the Co-founder of Microsoft. As it is impossible to collect all facts, knowledge graphs are incomplete. Therefore, a fundamental problem on knowledge graphs is to predict missing facts by reasoning with existing ones, a.k.a. knowledge graph reasoning.
This paper studies learning logic rules for reasoning on knowledge graphs. For example, one may extract a rule VX, Y, Z hobby(X, Y) +- fri friend X, Z) A hobby (2, Y), meaning that if Z is friend of X and Z has hobby Y, then Y is also likely the hobby of X. Then the rule can be applied to infer new hobbies of people. Such logic rules are able to improve interpretability and precision of reasoning (Qu & Tang 2019 Zhang et al. 2020). Moreover, logic rules can also be reused and generalized to other domains and data (Teru & Hamilton 2020). However, due to the large search space, inferring high-quality logic rules for reasoning knowledge graphs is a challenging task.
Indeed, a variety of methods have been proposed for learning logic rules from knowledge graphs. Most traditional methods such as path ranking (Lao & Cohen| 2010) and Markov logic networks (Richard) son & Domingos, 2006) enumerate relational paths on graphs as candidate logic rules, and then learn weight for each rule
assessment of rule qualities. There also some recent methods based on neural logic programming (Yang et al. 2017) and neural theorem provers (Rocktäschel & Riedel 2017). which are able to learn logic rules and their weights simultaneously in a differentiable way. Though empirically effective for prediction, the search space of these methods is exponentially large, making it hard identify high-quality logic rules. Besides, some recent efforts (Xiong al. (017)) formulate the problem as a sequential decision making process, and use reinforcement learning to search for logic rules, which significantly reduces search complexity. However, due to the large action space and sparse reward in training. the performance of these methods is not yet satisfying.
"Equal contribution.

---

Published as a conference paper at ICLR 2021
In this paper, we propose a principled probabilistic approach called RNNLogie which overcomes the a above limitations. Our approach consists of a rule generator as well as a reasoning predictor with logic rules, which are simultancously trained to enhance each other. The rule generator provides logie rules which are used by the reasoning predictor for reasoning, while the reasoning predictor provides effective reward to train the rule generator, which helps significantly reduce the search space. Specifically, for each query-answer pair, e.g., q (h, ?) and a = t, we model the probability of the answer conditioned on the query and existing knowledge graph G. i..., p(alg, q). where a set of logic rules = is treated as a latent variable. The rule generator defines a prior distribution over logic rules for each query, i.e., p( q). which is parameterized by recurrent neural network. The reasoning predictor computes the likelihood of the answer conditioned on the logic rules and the existing knowledge graph G, i.e., p(a g, q; 2). At each training iteration, we first sample a few logic rules from the rule generator, and further update the reasoning predictor to try out these rules for prediction. Then an EM algorithm (Neal& & Hinton 1998) is used to optimize the rule generator. In the E-step, a set of high-quality logic rules are selected from all the generated rules according to their posterior probabilities. In the M-step, the rule generator is updated to imitate the high-quality rules selected in the E-step. Extensive experimental results show that RNNLogic outperforms offte-of-the-art methods for knowledge graph reasoning ?
Besides, RNNLogic is able to generate high-quality logic rules.
RELATED WORK
Our work is related to existing efforts on learning logic rules for knowledge graph reasoning. Most traditional methods enumerate relational paths between query entities and answer entities as candidate logic rules, and further learn a scalar weight for each rule to assess the quality. Representative methods
include Markov logic networks (Kok & Domingos| 2005; Richardson & Domingos 2006 Khot et al.) 2011), relational dependency networks (Neville & Jensen 2007] Natarajan et al. (0010). rule mining algorithms (Galárraga et al. 2013 Meilicke et al. 2019), path ranking (Lao & Cohen (2000 Lao et al.
2011) and probabilistic personalized page rank (ProPPR) algorithms (Wang et al., 2013 2014a b).
Some recent methods extend the idea by simultaneously learning logic rules and the weights in differentiable way, and most of them are based on neural logic programming (Rocktäschel & Riedel 2017; Yang et al. 2017 Cohen et al. 2018 Sadeghian et al., 2019, Yang & Song 2020) or neural theorem provers (Rocktäschel & Riedel 2011 7, Minervini et al. 2020). These methods and our approach are similar in spirit, as they are all able to learn the weights of logic rules efficiently. However, these existing methods try simultaneously learn logic rules and their weights, which is nontrivial in terms of optimization. The main innovation of our approach is to separate rule generation and rule weight learning by introducing a rule generator and reasoning predictor respectively, which can mutually enhance each other. The rule generator generates a few high-quality logic rules, and the reasoning predictor only focuses on learning the weights of such high-quality rules, which significantly reduces the search space and leads to better reasoning results. Meanwhile, the reasoning predictor can in turn help identify some useful logic rules to improve the rule generator.
The other kind of rule learning method is based on reinforcement learning. The general idea is to train pathfinding agents, which search for reasoning paths knowledge graphs to answer questions, and then extract logic rules from reasoning paths (Xiong et al. 2017: Chen et al. [018]] Das et al.) 2018, Lin et al. 2018: [hen et al.) 2018). However, training effective pathfinding agents is highly challenging, the reward signal (i.e.. whether path ends the correct answer) can be extremely sparse. Although some studies (Lin et al. 2018) try to get better reward by using embedding- based methods for reward shaping, the performance is still worse than most embedding- basdd methods. In our approach, the rule generator has a similar role to those pathfinding agents. The major difference is that we simultaneously train the rule generator and a reasoning predictor with logic rules, which mutually enhance each other. The reasoning predictor provides effective reward for training the rule generator, and the rule generator offers high-quality rules to improve the reasoming predictor.
Our work is also related to knowledge graph embedding, which solves knowledge graph reasoning by learning entity and relation embeddings in latent spaces (Bordes et al., 2013) Wang et al. 2014c
Yang et al. 2015 Nickel et al. 2016 Trouillon et al. 2016 Cai & Wang 2018 Dettmers et al. 2018
Balazevic et al. 2019 Sun et | 2019). With proper architectures, these methods are able to learn
Moore precisely, z is a multisct. In this paper, we use "set" to refer to "multisct" for conciseness.
"The codes of RNNLogic are available: https: htt////tttttttt thub. http////eggggggghhheeeennn/////a
2

---

Published as a conference paper at ICLR 2021
Query (A.
Kule Generator
Logle Rules
Reasoning Predictor pu(al(i..
Answer
Py (rlv))
Prior
Likelihood
High-qualtty Logle Rules
Knowledge Graph
Pou (..15.9.0)
Figure 1: RNNLogic consists of rule generator pa and a reasoning predictor Pw- Given a query, the rule generator generates logic rules for the reasoning predictor. The reasoning predictor takes the generated rules as input, and reasons on a knowledge graph to predict the answer. RNNLogic is optimized with an EM-based algorithm. In each iteration, the rule generator produces some logic rules, and we update the reasoning predictor to explore these rules for reasoning. Then in the E-step, a set of high-quality rules are identified from all generated rules via posterior inference. Finally in the M-step, the rule generator updated be consistent with the high-quality rules identified in E-step.
some simple logic rules. For example, TransE (Bordes al.. 2013) learn some composition rules. RotatE (Sun et al. 2019) can mine some composition rules, symmetric rules and inverse rules. However, these methods can only find some simple rules in implicit way. In contrast, our approach explicitly trains a rule generator, which is able to generate more complicated logic rules.
There are some works studying boosting rule-based models (Goldberg & Eckstein 2010 Eckstein et where they dynamically add new rules according to the rule weights learned so far. These methods have been proven effective in binary classification and regression. Compared with them, our approach shares similar ideas, as we dynamically update the rule generator with the feedback from the reasoning predictor, but we focus on different task, i.e., reasoning on knowledge graphs.
MODEL
In this section, we introduce the proposed approach RNNLogic which learns logic rules for knowledge graph reasoning. We first formally define knowledge graph reasoning and logic rules.
Knowledge Graph Reasoning. Let Pdata (G, q, a) be training data distribution, where G a background knowledge graph characterized by set of (h, x, f--tripllets which may also write as r(h,t), t). q = (h, r, ?) is a query, and a = is the answer. Given Ç and the query q, the goal is to predict the correct answer More formally, we aim to model the probabilistic distribution p(a (G q).
Logic Rule. We perform knowledge graph reasoning by learning logic rules, where logic rules in this paper have the conjunctive form &(X,Y'n (Xa, X,) ry (Xo, X2) A -.. A (X,-,,, X1) with I being the rule length. This syntactic structure naturally captures composition, and can easily express other common logic rules such as symmetric or inverse rules. For example, let r-1 denote the inverse relation of relation r, then each symmetric rule can be expressed as V(X.Y) r(X,)) <- - (X,Y).
In RNNLogic, we treat set of logic rules which could explain query as latent variable we have to infer. To do this, we introduce a rule generator and a reasoning predictor using logic rules. Given a query, the rule generator employs a recurrent neural network generate set of logic rules, which given to the reasoning predictor for prediction. We optimize RNNLogic with an EM-based algorithm. In each iteration, we start with updating the reasoning predictor to try out some logic rules generated by the rule generator. Then in the E-step, we identify a set of high-qualing rules via posterior inference, with the prior from the rule generator and likelihood from the reasoning predictor. Finally in the M-step, the rule generator is updated with the identified high-quality rules.
rules from all generated
3.1 PROBABILISTIC FORMALIZATION
We start by formalizing knowledge graph reasoning in a probabilistic way, where a set of logic rules z treated as a latent variable. The target distribution p(a(G, (a(G.q) q) is jointly modeled by a rule generator and reasoning predictor. The rule generator Po defines a prior over set of latent rules z conditioned on a query q. while the reasoning predictor Pw gives the likelihood of the answer a conditioned on latent rules z, the query g. and the knowledge graph G. Thus p(alg, q) can be computed as below:
Pw.e(a. G, q) = Σ Pw (alg, q, x))ppp (z|g) = Epo(=ig) IPw (alg, x)).
(1)
3

---

Published as a conference paper at ICLR 2021
The goal is to jointly train the rule generator and reasoning predictor to maximize the likelihood of training data. Formally, the objective function is presented as below:
max OOO, w) = B(g.q.)) q.a))..aammmnnl log P 9, q)] = Egg. (ltg.q.a))pppe ppmm log (pott) =)]]- (2) 8,
3.2 PARAMETERIZATIIN
Rule Generator. The rule generator defines the distribution po (z(2g)) For a query q, the rule generator aims at generating a set of latent logic rules x for answering the query.
Formally, given query q x,, ?), generate compositional logic rules by only considering the query relation r without the query entity h. which allows the generated rules to generalize across entities. For each compositional rule in the abbreviation form rı A ....A rı, can be viewed as sequence of relations [z, I1, I2 ... It, IEND]. where is the query relation or the rule head, {ri are the body of the rule, and FEND is special relation indicating the end of the relation sequence.
x.
Such relation sequences can be effectively modeled by recurrent neural networks (Hochreiter & Schmidhuber [997]. and thus we introduce RNN; to parameterize the rule generator. Given a query relation r, RNN, sequentially generates each relation in the body of a rule, until it reaches the ending relation TEND- this process, the probabilities of generated rules are simultaneously computed. With such rule probabilities, we define the distribution over set of rules z as multinomial distribution:
po(z]g) = Mu(z (N, RNNo(-1=)
where Mu stands for multinomial distributions, N is hyperparameter for the size of the set z, and RNNo(-12) defines a distribution over compositional rules with rule head being r. The generative process of a rule set is quite intuitive, where simply generate N rules with RNN, to form
Reasoning Predictor with Logic Rules. The reasoning predictor defines pu (alg 9 q, z). For a query q, the predictor uses of rules reason on knowledge graph G and predict the answer a.
Following stochastic logic programming (Cussens 2000). a principled reasoning framework, we lig-linear model for reasoning. For each query q (h. r, ?), compositional rule is able to find different grounding paths on graph G, leading to different candidate answers. For exam- ple, given query (Alice, hobby, ?), a rule hobby + friend hobby can have two ground- ings, hobby (Alice, Sing) + fri riiend(Alice Aob)/hobby (BobbbyyyBbb, Sing) and hobby Ski) + griend(Alice Charlie) A hobby (Charlie, Ski), yielding two candidate answers Sing and Ski.
Let A be the set of candidate answers which can be discovered by any logic rulc in the set z. For each candidate answer e E A, we compute the following scalar scorew for that candidate:
scorem = Σ score (e|rule)
Σ Σ
(ro(e oi (path),
(4)
ndee=
rule pathe ((h,nlee.))
where P(h, rule, e) is the set of grounding paths which start at h and end at e following a rule (e.g..
Alice friend, Bob robby, Sing). v (rule) and dwo are scalar weights of each rule and path. Intuitively, the score of each candidate answer is the sum of scores contributed by each rule, i.e., (c)ree To get score, (e|rule), we sum over every grounding path found in the graph G.
For the scalar weight (rule) of each rule, it is learnable parameter optimize. For the score the (path) of each specific path, we explore two methods for parameterization. One method always 1. However, this method cannot distinguish between different relational paths. To address the problem, for the other method, we follow an embedding algorithm RotatE (Sun et al. 2019) to introduce an embedding for each entity and model each relation on entity embeddings. Then for each grounding path of rule starting from h to e, if we rotate the embedding of h according the rotation operators defined by the body relations of rule, we should expect to obtain an embedding close to the embedding of e. Thus we compute the similarity between the derived embedding and the embedding of de (path). which can be viewed measure of the
sets @w (path)
rotation operator
soundness and consistency of each path. For example, given path Alice friand, Bob hobby, Sing, we rotate Alice's 's embedding with the operators defined by friend and hobby. Afterwards we compute the similarity of the derived embedding and embedding of Sing as ow (path). Such method allows us to compute a specific 6n (path) for each path, which further leads to more precise scores for different candidate answers. See C more details of the parameterization method.
4

---

Published as a conference paper at ICLR 2021
Once we have the score for every candidate answer, further define the probability that the answer a of the query is entity e by using a softmax function as follows:
exp(scorew(e)) ( = el9, EeEd exp(scorew(e))
(5)
3.3 OPTIMIZATION
Next, we introduce how we optimize the reasoning predictor and rule generator to maximize the objective in Eq. (2). At each training iteration, first update the reasoning predictor Pw according to some rules generated by the generator, and then update the rule generator Po with an EM algorithm. In the E-step, a set of high-quality rules are identified from all generated rules via posterior inference, with the rule generator as the prior and the reasoning predictor as the likelihood. In the M-step, the rule generator is then updated to be consistent with the high-quality rules selected in the E-step.
Formally, at each training iteration, we start with maximizing the objective ( w) in Eq. 2 with respect to the reasoning predictor Pu. To do that, we notice that there is an expectation operation with respect to pa (=(q)) for each training instance (g. q, a). By drawing a sample & ~ Pa P=(=]q) for query q, we can approximate the objective function of w at each training instance (9, q, a) as below:
(GG.ga)) (w) log [pu(=lq) [Pw G, q, =)] log PogPo (alg, q.
Basically, we sample set of rules from the generator and feed å into the reasoning predictor. Then the parameter of the reasoning predictor is updated to maximize the log- log-likelihood of the answer
With the updated reasoning predictor, we then update the rule generator Pg to maximize the objective O00, w.) In general, this can be achieved by REINFORCE (Williams 1992) or the reparameterization trick (Jang et al. 2017 Maddison et al.) 2017), but they are less effective in our problem due to the large number of logic rules. Therefore, an EM framework is developed to optimize the rule generator.
E-step. Recall that when optimizing the reasoning predictor, we draw a set of rules é for each data instance (G, q, a), and let the reasoning predictor use é to predict a. For each data instance, the E-step aims to identify a set of K high-quality rules ø from all generated rules 2, i..., 21 C é, |2] = K.
Formally, this is achieved by considering the posterior probability of each subset of logic rules ø1. ie., P8, (v [g, q. a) x Pw (al9; q. x1x1))p <1)))(>7(()) with prior of y from the rule generator pa and likelihood from the reasoning predictor Puc- The posterior combines knowledge from both the rule generator and reasoning predictor, so the likely set of high-quality rules can be obtained by sampling from the posterior. However, sampling from the posterior is nontrivial due its intractable partition function, so we approximate the posterior using more tractable form with the proposition below:
Proposition 1 Consider a data instance (G, q, a) with q - r, ?) and t. For a of rules generated by the rule generator pa, we can compute the the following score H for each rule E 2;
(ruule) = { scorew
Σ BEA
scorew
+ log RNNo (rule)r),
LAI
where is the set of all candidate answers discovered by rules in ε, score scorem((erule) is the score that each rule contributes to entity defined by Eq. 4 RNNo(rule)))) is the prior probability of rule computed by the generator. Suppose 8 = max scorew | < 1. Then for subset of rules pa (z1 G. q, a) can be approximated as follows:
21 C. 2 with xz1| K, the log- tog-probability logpa,
log Log (o
Σ H(rule) + (22) + const ndleE:
S + O((5))
(8)
where const is a constant term that is independent from 21, (2,) log( log(K!/ TImtess Dente!), with K being the given size of set 21 and Dyule being the number of times each rule appears in 21-
We prove the proposition in App. A.1 In practice, can apply weight decay to the weight of logic rules in Eq. (4) and thereby reduce & = maxee sccore (e)l I to get a more precise approximation.
The above proposition allows to utilize (Eritezz) H(rue)) +2(21) const) to approximate the log- posterior log a (2) (2/(g, q, a), yielding distribution q(2)) exp(Entees. H(uue) + 7(2))
5

---

Published as a conference paper at ICLR 2021
good approximation of the posterior. It turns out that the derived ((x1) is multinomial distribution, and thus sampling from (x1)) is more tractable. Specifically, a sample & from g(x1) can be formed with K logic rules which are independently sampled from &. where the probability of sampling each rule is computed as exp( (rule)) (Eaiee exp( (rule')), We provide the proof in the App. A.2
Intuitively, we could view H (rule) of each rule as an assessment of the rule quality, which considers two factors. The first factor is based on the reasoning predictor Pws and it is computed as the score that a rule contributes to the correct answer t minus the mean score that this rule contributes to other candidate answers. If rule gives higher score to the true answer and lower score to other candidate answers, then the rule is more likely to be important. The second factor is based on the rule generator po, where we compute the prior probability for each rule and use the probability for regularization.
Empirically, we find that picking K rules with highest ((rule) to form &ع works better than sampling from the posterior. Similar observations have been made on the node classification task (Qu et al.) 2019). In fact, 2, formed by the top-K rules is an MAP estimation of the posterior, and thus the variant of picking top-K rules yields a hard-assignment EM algorithm (Koller & Friedman (209)). Despite the reduced theoretical guarantees, we use this variant in practice for its good performance.
M-step. Once we obtain a set of high-quality logic rules द for each data instance (g, q. a) in the E-step, we further leverage those rules to update the parameters 0 of the rule generator in the M-step.
Specifically, for each data instance (G, q, a), we treat the corresponding rule set 2, as part of the (now complete) training data, and update the rule generator by maximizing the log- oigliiklldood of žy:
(gg.qa) = log po (2)()))) - Σ
log RRNNN + const.
With the above objective, the feedback from the reasoning predictor can be effectively distilled into the rule generator. In this way, the rule generator will learn to only generate high-quality rules for the reasoning predictor to explore, which reduces the search space and yields better empirical results.
For more detailed analysis of the EM algorithm for optimizing (0,, w). please refer to App. B
Algorithm 1 Workflow of RNNLogic
while not converge do
For each instance, use the rule generator pe to generate set of rules 2 (| .N.
For each instance, update the reasoning predictor Pw based on generated rules and Eq. (6).
E E-step:
For each instance, identify K high-quality rules 2, from according to (rule) in Eq.
Fl M-step:
For each instance, update the rule generator po according to the identified rules and Eq. 9
end while
During testing, for each query, use py to generate N rules and feed them into pw for prediction.
EXPERIMENT
4.1 EXPERIMENT SETTINGS
Datasets. We choose four datasets for evaluation, including FB FB15k-237 Toutanova & Chen 2015).
WN18RR (Dettmers et al. 2018), Kinship and UMLS (Kok Domingos 2007). For Kinship and UMLS, there are no standard data splits, so we randomly sample 30% of all the triplets for training, 20% for validation, and the rest 50% for testing. The detailed statisties are summarized in the App. D
Compared Algorithms. We compare the following algorithms in experiment:
Rule learning methods. For traditional statistical relational learning methods, we choose Markov logic networks (Richardson & Domingos] 2006), boosted relational dependency networks (Natarajan)
et al. 2010) and path ranking (Lao Cohen 2010). We also consider neural logic programming
methods, including NeuralLP (Yang et al. 2017). DRUM (Sadeghian et al. 2019) and NLIL (Yang &
Song. 2020). In addition, we compare against CTP (Minervini et al. 2020). a differentiable method
based on neural theorem provers. Besides, we consider three reinforcement learning methods, which

---

Published as a conference paper at ICLR 2021
Table 1: Results of reasoning on FB15k-237 and WNISRR. H@ %. [*] means the numbers are
taken from the original papers. [*] means we rerun the methods with the same evaluation process.
FB15K-237
WNI8RR
Category
Algorithm
MR
MRR
H@1 1
H@3
H@10
MR
MRR
H@1
H@3
H@ 10
TransE"
357
0.294
46.5
3384
0.226
50.1
DisiMult"
254
0.241
15.5
26.3
41.9
5110
0.43
39
44
49
Learning
No Rule
ComplEx-N3'
ComplEx"
339
0.247
0.37
13.8
27.5
42.8
56
5261
0.48
0.44
41
46
51
ConvE"
244
0.325
23.7
35.6
50.1
4187
0.43
40
44
52
TuckER
0.358
26.6
54.4
0.470
48.2
RotarE
177
0.338
24.1
37,5
53.3
3340
0,476
42.8
49.2
57.1
PathRank
0.087
7.4
9.2
11.2
0.189
17.1
20X0
22.3
Rule
NeuralLPt
0.237
17.3
25.9
36.1
0.381
38.6
Learning
DRUM
0.238
17.4
26.1
36.4
0.382
36.9
38.8
41.0
NLIL"
0.25
32.4
Walk
0.232
16.5
24.3
0.437
44.5
RNNLoogic
wlo emh.
5338
0.288
20.8
31.5
44.5
7527
0.455
41.4
47.5
53.1
with cmb. 232
0.344
25.2
38.0
53.0
4615
0.483
44.6
49.7
55.8
Table Results knowledge graph reasoning on the FB15k-237 and WNI8RR datasets with only (h, r, -ueeriis H@k is in %. [*] means that the numbers are taken from the original papers.
FBB15-2337
WNI8RR H@1
Category
Algorithm
MR
MRR
H@] 1
H@3
H@P 10
MR
MRR
H@3
H@ 10
Rule
MINERVA
0.293
21.7
32.9
45.6
0.448
41.3
45.6
31.3
Learning
MultiHopKG'
0.407
32.7
56.4
0.472
43.7
54.2
RNNLogic
wio emb.
459.0
0.377
28.9
41.2
54,9
7662.8
0.478
43.8
50.3
55.3
with emb.
146.1
0.443
34.4
48,9
64.0
3767.0
0.506
46.3
52.3
59.2
are MINERVA (Das et al. 2018), MultiHopKG (Lin et al. 2018) and M- Walk (Shen et al. 2018).
A Other methods. We also compare with some embedding methods, including TransE (Bordes et al.
2013
DistMult (Yang et al. 2013), ComplEx (Trouillon et al. 2016), ComplEx-N3 ( (Lacroix et al.
2018).
ConvE (Dettmers al. [2018), TuckER (Balazevic et al. 2019) and RotatE (Sun al. 2019))
RNNLogic. For RNNLogic, we consider two model variants. The first variant assigns a constant score to different grounding paths in the reasoning predictor, i.e., (path)))
1 in Eq. 44. and we denote this variant as w/o emb. The second variant leverages entity embeddings and relation embeddings to compute the path score @n. (path), and we denote the variant as with emb..
Evaluation Metrics. During evaluation, for each test triplet (h, r, 4), we build two queries (h, r,?) and (1, 11,r-,, ?) with answers and h. For each query, we compute a probability for each entity, and compute the rank of the correct answer. Given the ranks from all queries, we report the Mean Rank (MR), Mean Reciprocal Rank (MRR) and Hit & (H@ k) under the filtered setting (Bordes et al.) 2013), which is used by most existing studies. Note that there can be case where an algorithm assigns the same probability to the correct answer and a few other entities. For such a case, many methods compute the rank of the correct answer as (m 1) where m is the number of entities receiving higher probabilities than the correct answer. This setup can be problematic according to Sun al. 2020). For fair comparison, in that case compute the expectation of each evaluation metric over all the random shuffles of entities which receive the same probability as the correct answer. For example, if there are n entities which have the same probability the correct answer in the above case, then we treat the rank of the correct answer as (m + (n 1)/2) when computing Mean Rank.
Besides, we notice that MINERVA (Das al. 2018) and MultiHopKG (Lin et al. 2018), they only consider queries in the form of (h, z. ?), which is different from our default setting. To make fair comparison with these methods, we also apply RNNLogic to this setting and report the performance.
Experimental Setup of RNNLogiC. For each training triplet (h, r,t), t), we add an inverse triplet (t, (t,--1,h) h) into the training set, yielding an augmented set of training triplets T. We use a closed- world assumption for model training, which assumes that any triplet outside ' is incorrect. To build a training instance from Pdata we first randomly sample a triplet (h, r, t) from T, and then form an instance as (g T ((h, f)).e) q (h, r, ?), a t). Basically, we use the sampled triplet (h, t) to construct the query and answer, and use the rest of triplets in T to form the background knowledge graph G. During testing, the background knowledge graph G is formed with all the triplets in T. For the rule generator, the maximum length of generated rules is set to 4 for FB 15k-237, 237,5 5 for WN1SRR, and 3 for the rest, which selected on validation data. See App. D for the detailed setting.
7

---

Published as a conference paper at ICLR 2021
Table 3: Results of reasoning on the Kinship and UMLS datasets. H@ is in %.
Kinship H@1
UMLSS
Category
Algorithm
MR
H@3
MRR
H@1
HØ3
H
DistMult
8.5
0.354
18.9
40.0
75.5
14.6
0.391
25.6
44.5
66.9
Learning
No Rule
ComplEx N3
ComplEx
7.8
0.605
0.418
43.7
24.2
49.9
71.0
92.1
81.2
13.6
0.791
0.411
27.3
68.9
87.3
46.8
95.7
70.0
TuckER
6.2
0.603
46.2
69.8
86.3
5.7
0.732
62.5
81.2
90.9
RotatE
93.2
0.744
82.2
MLN
10.0
0.351
18.9
40.8
70.7
7.6
0.688
58.7
75.5
86.9
Bousted RDN
25.2
0.469
39.5
52.0
56.7
54.8
0.227
14.7
25.6
37.6
PathRank
0.369
27.2
41.6
67.3
0.197
14.8
21.4
25.2
Learning
NeuralLP
16,9
0.302
16.7
33.9
59.6
10.3
0.483
33.2
56.3
77.5
DRUM
11.6
0.334
18.3
67.5
0.548
69.9
MINERVA
0.401
23.5
46.7
76.6
0.564
42.6
65.8
81.4
CTP
0.335
17.7
37.6
70.3
0.404
28.8
43.0
67.4
RNNLogii
wlo emb.
3.9
0.639
49.5
73.1
92.4
0.745
63.0
83.3
with cmb.
3.1
0.722
59.8
81.4
94.9
3.1
0.842
77.2
89.1
96.5
4.2 RESULTS
Comparison against Existing Methods. We present the results the FB15k-237 and WNI8RR The results on the Kinship and UMLS datasets are shown in Tab.
datasets in Tab. and Tab. 2
We first compare RNNLogic with rule learning methods. RNNLogic achieves much better results than statistical relational learning methods (MLN, Boosted RDN, PathRank) and neural differentiable methods (NeuralLP, DRUM, NLIL, CTP). This because the rule generator and reasoning predictor of RNNNogic can collaborate with each other to reduce search space and learn better rules. RNNLogic also outperforms reinforcement learning methods (MINERVA, MultiHopKG, M-Walk). The reason that RNNLogic is optimized with an EM-based framework, in which the reasoning predictor provides more useful feedback to the rule generator, and thus addresses the challenge sparse reward.
We then compare RNNLogic against state-of-the-art embedding-based methods. For RNNLogic with embeddings in the reasoning predictor (with emb.), ), it outperforms most compared methods in most cases, and the reason is that RNNLogic is able to logic rules to enhance reasoning performance. For RNNLogic without embedding (w/o emb.), it achieves comparable results to embedding based methods, especially WN18RR, Kinship and UMLS where the training triplets quite limited.
Quality of Learned Logic Rules. Next, we study the quality of rules learned by different methods for reasoning. For each trained model, let it generate rules with highest qualities per query relation, and use them to train a predictor w/o emb. as in Eq. (5) for reasoning. For RNNLogiC, the beam search to infer top-7 rules. The results at different are in Fig. 2] where RNNLogio achieves much better results. Even with only 10 rules per relation, RNNLogic still achieves competitive results.
quality of each rule is measured by its prior probability from the rule generator, and
Performance w.r.t. the Number of Training Triplets. To better evaluate different methods under cases where training triplets very limited, this section reduce the amount training data on Kinship and UMLS to see how the performance varies. The results are presented in Fig. 4 We see that RNNLogic w/o emb. achieves the best results. Besides, the improvement over RotatE more significant as we reduce training triplets, showing that RNNLogic is more robust to data sparsity.
Kinship
50
Algarihi Neviol
Algorithm
Neuerl
Aigorthm
Part Ravkking R/00 agic
Part Raminng
Reball
RXN agi:
Lope fum
#Lage Pllrs
#ee Diree
Figure 2: Performance w.r.t. # logic rules. RNNLogic achieves competitive results even with 10 rules per query relation.
Figure 3: Performance w.r.t.
bedding dimension.
8

---

Published as a conference paper at ICLR 2021
Performance w.r.f Embedding Dimension. RNNLogic with emb. uses entity and relation embed- dings to improve the reasoning predictor. Next, we study its performance with different embedding dimensions. The results are presented in Fig. [] where compare against RotatE (Sun al.) 2019). We see that LNNi significantly outperforms RotatE at every embedding dimension. The improvement is mainly from the of logic rules, showing that our learned rules are indeed helpful.
Comparison of Optimization Algorithms. RNNLogic uses an EM algorithm to optimize the rule generator. In practice, the generator can also be optimized with REINFORCE (Williams) 1992) (see App. For details). We empirically compare the two algorithms in the w/o emb. case. The results on Kinship and UMLS are presented in Tab. We see EM consistently outperforms REINFORCE.
Kinship
UMLS
50
07
Kinship MRR
UMLS
MRR
04
REINFORCE
0,312
0.504
Aigorisi
Algorithm
12
MINERU
03
DRUM
INNERW
EM
0.639
0.745
ogt
Table 4: Comparison between REINFORCE and EM.
Theilng Troteb
Trplet
Figure 4: Performance w.r.t. # training triplets. RNNLogic is more robust to data sparsity even without using embeddings.
Case Study of Generated Logic Rules. Finally, show some logic rules generated by RNNLogic on the FB 7B35k-237 dataset in Tab. 5 We can see that these logic rules are meaningful and diverse. The first rule is subrelation rule. The third and fifth rules are two-hop compositional rules. The rest of logic rules have even more complicated forms. This case study shows that RNNLogic can indeed learn useful and diverse rules for reasoning. For more generated logic rules, please refer to App. E
Table 5: Case study of the rules generated by the rule generator.
Appears_in, X.V] Acto-Lof[X.Y
Sopears_.n.TV..hoxdd. + Creatoz.of(X U) Aaa....PP.a.. Pro..er V) Atgpears.in.TV.h...
ORG. in State(X. 08G. City(X. U)) City Locates State(U,
2nG..I..taaee(..Y In.Cityy X') A Add::es_ot_FFRR. (U, (B.V) Dora.in(V W) Town
Person Nationality(X.y)) Born in(X, A in Couatry(U,
Porson.latt:ono::tyyXX.Y. + student.cf suudent_cf.aducatte wwd.caaaiinnllaaeete.... inntiiittioo((.. (X, UJ) ORG, www.dweeett.urreeeeeeeeeeeeeeeee V)A
Curseacy Used in Region(V A in Country(W.
CONCLUSION
This paper studies learning logic rules for knowledge graph reasoning, and approach called RNNLogic is proposed. RNNLogic treats a set of logic rules as a latent variable, and a rule generator as well reasoning predictor with logic rules are jointly learned. We develop an EM-based algorithm for optimization. Extensive expemriments prove the effectiveness of RNNLogiC. In the future, we plan to study generating more complicated logic rules rather than only compositional rules. Besides, we plan to extend RNNLogic to other reasoning problems, such as question answering.
ACKNOWLEDGMENTS
This project is supported by the Natural Sciences and Engineering Research Council (NSERC) Discovery Grant, the Canada CIFAR AI Chair Program, collaboration grants between Microsoft Research and Mila, Samsung Electronics Co., Ldt., Amazon Faculty Research Award, Tencent AI Lab Rhino -Brd Gift Fund and a NRC Collaborative R&D Project -A1DDCCORE-O This project was also partially funded by IVADO Fundamental Research Project grant PRI-2201-33831139777

---

Published as a conference paper at ICLR 2021
REFERENCES
Ivana Balazevic, Carl Allen, and Timothy Hospedales. Tucker: Tensor factorization for knowledge graph completion. EMNLP. 2019.
Antoine Bordes, Nicolas Usunier, Alberto Farcia-Duran Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relations data. In NeurlPS, 2013.
Liwei Cai and William Yang Wang. Kbgan: Adversarial learning for knowledge graph embeddings. In NAACL, 2018.
Wenhu Chen, Wenhan Xiong, Xifeng Yan, and William Wang. Variational knowledge graph reasoning. In NAACL, 2018.
William W Cohen, Fan Yang. and Kathryn Rivard Mazaitis. Tensorlog: Deep learning meets probabilistic databases. Journal of Artificial Intelligence Research, 2018.
James Cussens. Stochastic logic programs: sampling, inference and applications. In UAI, 2000.
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In ICLR, 2018.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. AAAI, 2018.
Jonathan Eckstein, Noam Goldberg, and Ai Kagawa. Rule-enhanced penalized regression by column generation using rectangular maximum agreement. In ICML, 2017.
Luis Antonio Galárraga, Christina Teftioudi, Katja Hose, and Fabian Suchanek. Amie: association rule mining under incomplete evidence in ontological knowledge bases. WWW, 2013.
Noam Goldberg and Jonathan Eckstein. Boosting classifiers with tightened 10-relaxation penalties. In ICML, 2010.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1997.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztion with gumbel-softmax. In ICLR, 2017.
Tushar Khot, Sriraam Natarajan, Kristian Kersting, and Jude Shavlik. Learning markov logic networks via functional gradient boosting. In /CDM, 2011.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2014.
Stanley Kok and Pedro Domingos. Learning the structure of markov logic networks. ICML, 2005.
Stanley Kok and Pedro Domingos. Statistical predicate invention. JCML, 2007.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Timothee Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML, 2018.
Ni Lao and William W Cohen. Relational retrieval using combination of path-constrained random walks. Machine learning, 2010.
Ni Lao, Tom Mitchell, and William W Cohen. Random walk inference and learning large scale knowledge base. In EMNLP, 2011.
Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with reward shaping. EMNLP, 2018.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: continuous relaxation of discrete random variables. In ICLR, 2017.
10

---

Published as a conference paper at ICLR 2021
Christian Meilicke, Melisachew Wudage Chekol, Daniel Ruffinelli, and Heiner Stuckenschmidt. Anytime bottom-up rule learning for knowledge graph completion. In IJCAI, 2019.
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies end-to-end differentiable proving. In ICML, 2020.
Sriraam Natarajan, Tushar Khot, Kristian Kersting, Bernd Gutmann, and Jude Shavlik, Boosting relational dependency networks. In ICILP, 2010.
Radford M Neal and Geoffrey E Hinton. A view of the em algorithm that justifies incremental, sparse, and other variants. In Learning in graphical models. Springer, 1998.
Jennifer Neville and David Jensen. Relational dependency networks. Journal of Machine Learning Research, 2007.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio. Holographic embeddings of knowledge graphs. In AAAI, 2016.
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. In NeurlPS, 2019.
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. In ICMI., 2019.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning. 2006.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. NeurIPS, 2017.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. In Neur/PS, 2019.
Yelong Shen, Jianshu Chen, Po-Sen Huang, Yuqing Guo, and Jianfeng Gao. M-walk: Learning to walk over graphs using monte carlo tree search. In NeurIPS, 2018.
Slavko Simic. On global upper bound for jensen's 's inequality. Journal of mathematical analysis and applications, 2008
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.
Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re-evaluation of knowledge graph completion methods. In ACL, 2020.
Komal K Teru and William L Hamilton. Inductive relation prediction on knowledge graphs. In ICML, 2020.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Workshop Continuous Vector Space Models and their Compositionality, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In /CML, 2016.
William Yang Wang, Kathryn Mazaitis, and William W Cohen. Programming with personalized pagerank: a locally groundable first-order probabilistic logic. In CIKM, 2013.
William Yang Wang, Kathryn Mazaitis, and William W Cohen. Proppr: Efficient first-order proba- bilistic logic programming for structure discovery, parameter learning, and scalable inference. In Workshops AAAI, 2014a.
William Yang Wang, Kathryn Mazaitis, and William W Cohen. Structure learning via parameter learning. In CIKM, 2014b.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In AAAI, 2014c.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 1992.

---

Published as a conference paper at ICLR 2021
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, 2017.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR, 2015.
Fan Yang. Zhilin Yang, and William Cohen. Differentiable learning of logical rules for knowledge base reasoning, In NeurlPS, 2017.
Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. In ICLR, 2020.
Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. In ICLR, 2020.
12

---

Published as a conference paper at ICLR 2021
A
PROOFS
This section presents the proofs of some propositions used in the optimization algorithm of RNNLogic.
Recall that in the E-step of the optimization algorithm, aim sample from the posterior distribu- tion over rule sets. However, directly sampling from the posterior distribution is intractable due to the intractable partition function. Therefore, introduce Proposition which gives approximation distribution with more tractable form for the posterior distribution. With this approximation, sampling becomes much easier. In Section AA.1] present the proof of Proposition [ how to perform sampling based on the approximation of the posterior distribution.
In Section A.2 show
A.1 PROOF OF PROPOSITION 1
Next, we prove proposition I which used to approximate the true posterior probability in the E-step of optimization. We first restate the proposition as follows:
a set of rules generated by the rule generator pa, compute the following score H for each rule E 2:
Proposition Consider a data instance (9, q, a) with q = (h,r,?) and a
((rue)) = score
Σ CEA
scorew(e)rule) log RNNo(rule)r))
[A]
where the set of all candidate answers discovered by rules in ê, score scorew(e)rule) the score that each rule contributes to entity defined by Eq. 4 RNNolrule)r) is the prior probability of 1. Then for subset of rules 21 C 2 with |z| = K, the log-probability log pa w 9, a) could be approximated follows:
rule computed by the generator. Suppose s max,e A score,
log u (0
Σ H(rule) + 7211 + const
S 2 62+0(s*)
nuleE::
where const a constant term that independent from 21, 7(21) = log(K)/ II nente!), ), with K being The given size of set 2ı and Myale being the number of times each rule appears in 21.
Proof:
We first rewrite the posterior probability as follows:
log Pe (zrl9, q, a) log Pw (w =1) lo + const
exp(scorew(t)) log E.EA exp(score.(e)) + log K, RNNo(-Ir) + const,
where const is constant term which does not depend on the choice of 21, and RNN (-Ir) defines probability distribution over all the composition- based logic rules. The probability mass function of the above multinomial distribution Mu(z) K, RNNo(-Ir) can be written as below:
K!
Mu(2r
II RNNo(rul
I Tiude!
where K is the size of set 2 and Myate is the number of times rule appears in zz.
Letting (22) log( / Heeeer nrmte!), then the posterior probability can then be rewritten as: log po (21 a)
exp(score, (1))
K!
llog
log
log II nuleE$
RNNo const
EeEl exp(scorem(e))
Iimdes Ainde!
exp(score,(()
=log
Eeel (xp(scorew(e)) + 7 +
Σ ruleEst
log (NNo(rul))))) const
=scorew log Σ exp(score_(e)) + (2)1) +
Rog + const.
aEA
ruleEz?
The above term log E.EA exp(score,.(e)) makes the posterior distribution hard to deal with, and thus approximate it using Lemma which we prove at the end of this section.
13

---

Published as a conference paper at ICLR 2021
Lemma Let E A be finite set of entities, let (scorew(e) I < and let scorew be function from entities to real numbers. Then the following inequalities hold:
5 log Σ exp(sccore((e))
Σ AEA
1
scorew(e) + log((A1))
s s -
A
AEA
Hence, using the lemma we can get the following upper bound of the posterior probability:
log Pa, (21 a.
=score (1) - log Σ
exp(scoreu(e)) +2(=))+ +
Σ
log RNNo + const
EEA
ruleE#s
<scorew()) - E
score + +
Σ raleEt
log (NNo(r) + const
A
cEA
H(rule) + (z1)
const.
ml
and also the following lower bound of the posterior probability:
log Pe.u (2119, q, a)
=score, i (t) - log Σ
exp(scorew(e)) + (21))+ +
Σ
log (oNollrl)))))) + const
cEA
nuleEz1
2score (f)- E
1
score + 7z1)) +
Σ
log (ogNNN((rlle(r) + const - -² - -(s
A
cEA
ni
H(rule) + 7(z) + const 0(s
where const is constant term which does not depend on 21.
By combining the lower and the upper bound, we get:
log log q.
Σ
(rule) + 721) + const
53²
nneeEzr
Thus, it only remains to prove Lemmal to complete the proof. We use Theorem T from Simic starting point:
2008
Theorem Suppose that ā. = {a, )n represents a finite sequence of real numbers belonging to fixed closed interval I = |a, bi. a < b. If convex function on 1, then we have that:
a a b
[(aa)= -
3z S I(a) + 5(b) - 25
n
72
2
As (- log) is convex and exp(score,,()) (c)) E (exp(=s), exp(s)), Theorem 1 gives us that:
log (exp(scorem (e))) + log
exp(score..(e))
LA
AA
AEA
cEA
exp(-5) + eep(s)
< - lolo(expp -s)) - log(exp(s)) + 2 log
2
14

---

Published as a conference paper at ICLR 2021
After some simplification, get:
log
Σ
exp(scorew(e))
scorew log( 2og <ex((=s) + cxp(s)
A
2
cEA
(10)
Σ
scorew + log((A)) + 2s - 2 2lo 2 + 2 2oog(1 + exp(
A
cEA
$ Σ cEA
scorew + ()) + s² +²
+O*5),
[
where the last inequality is based on Taylor's series log(1 +*)= log x }=² + Ox*)) with On the other hand, according the well-known Jensen's 's inequality, we have:
|x|| <
log
Σ
exp(scorew(e))
Σ cEA
log (es)(ccore(())))
A
A
cEA
which implies:
log Σ expl exp(scorew(e))
Σ
1
score + log(1AA)
(11)
A
By combining Eq.
10 and Eq.
we obtain:
S log Σ
(xp(sccoreu(e))
Σ lEE
scorew(e) + log((41)) s 5 0
A
AEEd
This completes the proof.
A.2 SAMPLING BASED ON THE APPROXIMATION OF THE TRUE POSTERIOR
Based Proposition 1, the log-posterior probability log Pe,. (z)l9, q, a) could be approximated by (Emleez, (rule) +)())))))))))))))))))))))))))))) const), with const being term that does not depend on z₁. This implies that we could construct distribution ((z)) x exp(2 exp(E,uleez: H (rule) + (2r)) to approximate the true posterior, and draw samples from y as approximation to the real samples from posterior.
It turns out that the distribution ((2)) is multinomial distribution. To see that, we rewrite g(2)) as:
((21)= = 2 exp
Σ
(rule) + ((11)
AnleEz1
Z
exp
(7(21)
II exp (Iule)) ni
K!
II raleE
exp (ll (rule))
Indees Trude! Z
1
K!
II (rule)
Ponk
Z'
Immeee Drute! rile
2. MMu(zr|K gr),
where nruke is the number of times a rule appears in the set 21, qr distribution over all the generated logic rules & with qr (rude) exp( H (rule))/ Ematess es cxp (rule")), Z and Z' are normalization terms. By summing over zy on both sides of the above equation, we obtain Z' = 1, and hence:
q(21)
Mu( (K,
15

---

Published as a conference paper at ICLR 2021
To sample from such multinomial distribution, could simply sample K rules independently from the distribution gr, and form a sample & with these rules.
In practice, we observe that the hard-assignment EM algorithm (Koller & Friedman 2009) works better than the standard EM algorithm despite the reduced theoretical guarantees. In the hard- assignment EM algorithm, Based on the above approximation ((z)) of the true posterior distribution pe,w 2 (9, q. a), we could simply construct such a sample Ê, with K rules which have the maximum probability under the distribution gr- By definition, we have qr (rule) & exp( ( H (rule)), and hence drawing K rules with maximum probability under 9, is equivalent choosing K rules with the maximum H values.
need draw sample ž, with the maximum posterior probability.
B MORE ANALYSIS OF THE EM ALGORITHM
In RNNLogiC, this EM algorithm is able to maximize the objective function of the rule generator.
an EM algorithm to optimize the rule generator. In this section, we show why
Recall that for fixed reasoning predictor Pw, we aim to update py to maximize the log-likelihood function log Pu. o (alg 9, q) for each data instance (G, q. a). Directly optimizing log Pu. o G q) is
difficult due to the latent logic rules, and therefore we consider the following evidence lower bound of the log-likelihood function:
Po,Pu,e Pw.e (a/ G, q) 2 By(=,) Pltz))llo@P (a|g, q, 21) + log - log g(>))] ]]] = LF.BO(d. (12)
where ((21) is variational distribution, and the equation holds when g(=1) pe,u (21 q. a).
With this lower bound, we can optimize the log-likelihood function P (a q) with an E-step and an M-step. In the E-step, we optimize ((2)) to maximize LE.BO Po), which is equivalent to minimizing (g(((2)) (22))(lPo,o IlPo, (2r19 q, a)). By doing so, we are able to tighten the lower bound. Then in the M-step, we further optimize 8 to maximize LELBO (g, po). Next, we introduce the details.
E-step. In the E-step, our goal is to update to minimize (L(((22) Po ( q, a)). However, there huge number of possible logic rules, and hence optimizing ((2)) on every possible rule set z, is intractable. To solve the problem, recall that we generate a set of logic rules & when optimizing the reasoning predictor, and here we add a constraint to q based on E. Specifically, we constrain the sample space of ((2)) to be all subsets of & with size being K, i.c.. ž! C. & and | K. In other words, we require ,x,c,, (2z) 1. With such constraint, we can further use proposition to construct the variational distribution q to approximate Pa, (21 |9, q. a), as what is described the model section.
M-step. In the M-step, our goal is to update po to maximize the lower bound LELBO(q.PM Po). To do that, we notice that there is expectation operation with respect to g(21) in LELBO Po). By drawing sample from ((27), LELBO(4, po) can be estimated as follows:
LELBO Po)
= By(=,) [lo Pn (a G, q, z1) + por(())))) logg(zr))
(13)
= Po 9, 21) + (o - log 9(2))
where 2, q(21) ) is sample drawn from the variational distribution. By ignoring the terms which are irrelevant to pe, we obtain the following objective function for 6:
log 2, (g).
(14)
which is the same as the objective function described in the model section.
As result, by performing the E-step and the M-step described in the model section, we are able to update pa to increase the lower bound LElBO (g, po). and thereby push up the log-likelihood function log Pwr (alg, q). Therefore, we see that the EM algorithm can indeed maximize log PogPa..o (a with respect to Po-
C DETAILS ABOUT PARAMETERIZATION AND IMPLEMENTATION
Section 3.2 of the paper introduces the high-level idea of the reasoning predictor with logic rules and the rule generator. Due to the limited space, some details of the models are not covered. In this section, we explain the details of the reasoning predictor and the rule generator.
16

---

Published as a conference paper at ICLR 2021
C.I REASONING PREDICTOR WITH LOGIC RULES
We start with the reasoning predictor with logic rules. Recall that for each query, our reasoning predictor leverages a set of logic rules give each candidate answer a score, which is further used to predict the correct answer from all candidates.
Specifically, let A denote the of all the candidate answers discovered by logic rules in set z, For each candidate answer e E .A, we define the following function scorew to compute a score:
S scorew (c) (e)= Σ
a = Σ Σ
tw (rule) &w (path),
(15)
nule=
ndee patlic (hh,uee)
where P(h, rule, e) is the set of grounding paths which start at h and end at e following a rule (e.g.. Alice friend, Bob hobby,, Sing). tie (rule) and ow (path) are scalar weights of each rule and path. For the scalar weight (rule) of rule, we initialize the (rule) as follows:
(rule) aa [P(h, rule, t)
1
Σ PEA
IP(h, rule, rule,
eill
(16)
[AI
where IP(h, rale, ()] is the number of relational paths starting from head entity h, following the relations in rule and ending tail entity L. The form very similar to the definition of H values for logic rules, and the value can effectively measure the contribution of a rule to the correct answers. We also try randomly initializing rule weights initializing them as which yield similar results.
For the scalar score ow (path) of path, we either fix it to I, or compute it by introducing entity and relation embeddings. In the second case, we introduce an embedding for each entity and relation in the complex space. Formally, the embedding of an entity is denoted as and the embedding of
relation is denoted æ.. For a grounding path path eo _ E1 -2, e2 61-1 - Et, follow
the idea in RotatE (Sun et al. 2019) and compute ow (path) in the following way:
@w (path) = o66 d(xe. x., x.,
22, Te:))
(17)
where (x)) Ite-= is the sigmoid function, d is distance function between two complex vectors, 8 is hyperparameter, and is the Hadmard product in complex spaces, which could be viewed as rotation operator. Intuitively, for the embedding Te, of entity ep, we rotate Zep by using the rotation operators defined by {rx } yielding (Zep Dr, Fr, o .... Z. Then we compute the distance between the new embedding and the embedding Le, of entity et, and further convert the distance to value between 0 and by using the sigmoid function and hyperparameter 5.
C.2 RULE GENERATOR
This paper focuses on compositional rules, which have the abbreviation form <- A ... A ry and thus could be viewed a sequence of relations [r, ,1, 12 ... Σı, LEND], where r the query relation or the head of the rule, {r:}(=r are the body of the rule, and TEND is special relation indicating the end the relation sequence. We introduce a rule generator RNN, parameterized with an LSTM (Hochreiter & Schmidhuber, [997) to model such sequences. Given the current relation sequence [r ri, T2 .. ryj. RNN, aims to generate the next relation ri+1 and meanwhile output the probability of ri+1- The detailed computational process towards the goal is summarized follows:
Initialize the hidden state of the RNNg as follows:
hg f(vr),
where v is a parameter vector associated with the query relation or the head relation r, f is a linear transformation. Sequentially compute the hidden state at different positions by using the LSTM gate:
h = (0TTM(h,,,,0((1, vr,.);
where vr, is parameter vector associated with the relation r,, [vr, Uz,] is the concatenation of u, and V..- & is linear transformation.
17

---

Published as a conference paper at ICLR 2021
Generate re+1 and its probability based on h4+1 and the following vector:
softmax(o(t++41).
Suppose the set relations is denoted as R. We first transform h4+1 to a / -imeensiona vector by using linear transformation o, and then apply softmax function to the (R] -dimensional vector to get the probability of each relation. Finally, we generate r++1 according to the probability vector.
D EXPERIMENTAL SETUP
D.I DATASET STATISTICS
The statistics of datasets are summarised in Table 6
Table 6: Statistics of datasets.
Dataset
#Entities
#Relations
#Train
#Validation
#Test
FB15K-233
14,541
237
272,115
17,535
20,466
WNI8RR
40,943
11
86,835
3,034
3.134
Kinship
104
25
3,206
2,137
5,343
UMLS
135
46
1,959
1,306
3,264
D.2 EXPERIMENTAL SETUP OF RNNLOGIC
Next, we explain the detailed experimental setup of RNNLogic. We try different configurations of hyperparameters on the validation set, and the optimal configuration is then used for testing. We report the optimal hyperparameter configuration as below.
Data Preprocessing. For each training triplet (h, r, add inverse triplet (1, x-,,-) into the training set, yielding an augmented set of training triplets T. To build a training instance from Pdata- first randomly sample triplet (h, r, from T, and then form an instance
(g
(h, r, r,?),a a = t). Basically, we use the sampled triplet (h, r, t) to construct the query and answer, and the rest of triplets in T form the background knowledge graph g.
T ((((,, (,),,,
During testing, the background knowledge graph G is constructed by using all the triplets in T.
Reasoning Predictor. For the reasoning predictor with embedding cases, the embedding dimension is set to 500 for FB15k-231 200 for WN1 1RR, 2000 for Kinship and 1000 for UMLS. We pre-train these embeddings with RotatE (Sun et al. 2019). The hyperparameter d for computing de (path) in Equation (17) is set to 9 for FB 237. 37. 6 for WNISRR, 0.25 for Kinship and 3 for UMLS. We use the Adam (Kingma Ba 2014) optimizer with an initial learning rate being 5 10-5, and decrease the learning rate in cosine shape.
Rule Generator. For the rule generator, the maximum length of generated rules is set for FB FB15k-237,5 5 for WN18RR, and for Kinship and UMLS. These numbers are chosen according to model performace on validation data. The size of input and hidden states in RNN, are set to 512 and 256. The learning rate is set to I 10-3 and monotonically decreased in cosine shape. Beam search is used to generate rules with high probabilities, so that we focus on exploiting these logic rules which the rule generator is confident about. Besides, pre-train the rule generator by using sampled relational paths on the background knowledge graph formed with training triplets, which prevents the rule generator from exploring meaningless logic rules in the beginning of training.
EM Optimization, During optimization, we sample 1000 rules from the rule generator for each data instance. In the E-step, for each data instance, identify 300 rules as high-quality logic rules.
Evaluation. testing, for each query q = (h, ?). we use the rule generator Py to generate 1000 logic rules, and let the reasoning predictor Pae use the generated logic rules to predict the answer
18

---

Published as a conference paper at ICLR 2021
E CASE STUDY
We present more rules learned by RNNLogic on FB15k-237 dataset and UMLS dataset in Table 7 at the last page. In this table, h S t means triplet (h, t) and h é t means triplet (h, r x or equivalently (t,r, h).
F CONNECTION WITH REINFORCE
In terms of optimizing the rule generator, our EM algorithm has some connections with the RE- INFORCE. algorithm (Williams, 1992). Formally, for training instance (G, q. a), REINFORCE computes the derivative with respect the parameters @ of the rule generator as follows:
R V
R V log (=
(18)
where is a sample from the rule generator, i.e., ~ (o q). R is a reward from the reasoning predictor based on the prediction result on the instance. For example, we could treat the probability of the correct answer computed by the reasoning predictor as reward, i.e., R pw pw (GGG,, q ě).
In contrast, our EM optimization algorithm optimizes the rule generator with the objective function defined in Equation (2) yielding the derivative Vo log po (2)lg)) Comparing the derivative to that in that EM only maximizes the log-probability for rules selected in the E-step, while REINFORCE maximizes the log- pog-pobbbbiiiyy for all generated rules weighted by the scalar reward R. Hence the two approaches coincide if R is set to for the selected rules from the approximate posterior and otherwise. In general, finding an effective reward function to provide feedback is nontrivial, and empirically compare these two optimization algorithms in experiments.
REINFORCE (Eq. 18
19

---

Published as a conference paper at ICLR 2021
Table 7: Logic rules learned by RNNLogic.
Relation
Rule (Explanation)
Appears_1n_TV_shog Y
X Has_kctor Y
(Definition. An actor of a show appears in the show, obviously.)
X Createz of, U Eroducer
V Agpeaza.in.IV.Bior Y
(The creator and the producer of another show U are likely appear in the same show Y.)
X Acter.ef AMard NemrstNem Kinner.oi Y
X Keiter.of, U Creater.oi V Acter.ef Y
Student.cg of, U Student.of V Agpears.in.TV.Bbo. Y
X
(Two students X and V in the same school U are likely to appear in the same show Y.)
X ORG..in.lais Y
X oRc.,n U City.in,ttat, Y
(Use the city to indicate the state directly.)
OBG. ins.in, U Lives V Boralin W
Town it
(Use the person living the city induct the state.)
X Sub-ORG. of U 02G. in State y
+ X Sub-ORG..of, U Sub-ORe. V URG. cas..in Y
ORG. ORG.in, JiG.in V ORG..in.state, Y
(Two organizations the same city are the same state.)
Peraon_Mat lonalllly Y
X Bornin, U
Place_in_Count Y
(Definition.)
X Spouse U pexson.Nationality, Y
(By a fact that people are likely marry a person of same nationality.) Student.o
CBG Enndomann
Begien,Currency
W Region Country,
(Use the currency induct the nationality.)
X Hornan, U porn.in
Pesson.aatinalltty Y
t X Politician.of U
Politician.of Person.alionnalit, y
Mart Marifeste for of y
X Treata U
Praventa
V
Precedes
X Complicates U
Precedes
Y
X
Location.of
15.
V
Precedes
Y
f- X Complicates
U
Procedes
iccura_in Y
Location.of
Deaura-in
Donura.in
X Precedes,
U
Occurs.i
V
Degree_ot y
X Affects y
X
Result.of
U Decura.in
V
Prececes Y
+ X Precedes
U
Produces
Occurs Y
< Prevents
U
Disrupts
Co withh Y
X of of U Complicates
V
Precedes Y
X Assesses affect of U Method of V Complicates Y
4 X PrOCeSS_Of U interacts.with, V Causes Y
X Aasesses.DIeect.n Result.ol Precedes, Y
20


Reviews:
[{"review_id": "kOJs5_dKXyW", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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\n\nStrong points\n\n1. 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.\n\n2. Good results\n\n3. 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.\n\nWeak points\n\n1. In many rule based methods (such as Neural LP), the goal is to find a set of (weighted) rules that imply a single relation.\nIn 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: \n\n 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).\n\n 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.\n\n3. 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. \n\n4. 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.\n    \nRecommendation\n\nI recommend accepting this paper.\nMy 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.\n\nQuestions\n\n1. 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?\n\n2. 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?\n\n3. 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?\n\n4. Can you clarify what RNNLogic with embedding is? I am guessing it is related to assigning path scores via embedding? Please make this explicit.\n\n5. Will your method be computationally more expensive than methods which generate rules for individual relations?\n\n6. 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? \n\n7. 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. \n\n8. 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)?\n\n9. 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.\n\nThough 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.\n\nThe 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.\n\nRotatE has no numbers for UMLS or Kinship.\n\nComplEx has none of the numbers reported here.\n\nDistmult has none of the numbers reported here.\n\nThe 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.\n\nSo 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Qchi-HYieL1", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThere 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:\n\n1. 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. \n\n2. 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? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "M8R1WNhAiNK", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI 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:\n\n- 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.\n\n- 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?\n\n- 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\n\nSome claims are not well addressed:\n\n- 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.\n\n- Backward-chaining methods such as NeuralLP are indeed efficient for problems with high dimensionality as well.\n\n- There seems to be no justification or experiments to demonstrate how the proposed method can do better than the previous ones on these properties.\n\nModel details:\n\n- 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?\n\nModel efficiency:\n\n- 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?\n\n- 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.\n\n\nExperiment:\n\n- 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?\n\n- 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.\n\n- 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?\n\nOverall, 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4NfnkJ8xMh5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 1, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\nThe approach seems interesting and the tackled problem could interest a wide audience. It does not seem extremely novel, but it seems valid to me.\nThe 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).\n\nFor all these reasons I think the paper should be accepted for publication.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)