ING ON KNOWLEDGE GRAPHS
Year: 2021

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 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.

heading: 1 INTRODUCTION
text: Knowledge graphs are collections of real-world facts, which are useful in various applications. Each fact is typically specified as a triplet (h,r, t) or equivalently r(h, t), meaning entity h has relation r with entity t. 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 ∀X,Y, Z hobby(X,Y )← friend(X,Z) ∧ hobby(Z, Y ), meaning that if Z is a 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 on 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 (Richardson & Domingos, 2006) enumerate relational paths on graphs as candidate logic rules, and then learn a weight for each rule as an assessment of rule qualities. There are also some recent methods based on neural logic programming (Yang et al., 2017) and neural theorem provers (Rocktä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 to identify high-quality logic rules. Besides, some recent efforts (Xiong et al., 2017) 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.
In this paper, we propose a principled probabilistic approach called RNNLogic which overcomes the above limitations. Our approach consists of a rule generator as well as a reasoning predictor with logic rules, which are simultaneously trained to enhance each other. The rule generator provides logic 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, r, ?) and a = t, we model the probability of the answer conditioned on the query and existing knowledge graph G, i.e., p(a|G, q), where a set of logic rules z 1 is treated as a latent variable. The rule generator defines a prior distribution over logic rules for each query, i.e., p(z|q), which is parameterized by a 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, z). 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 state-of-the-art methods for knowledge graph reasoning 2. Besides, RNNLogic is able to generate high-quality logic rules.

heading: 2 RELATED WORK
text: 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., 2010), rule mining algorithms (Galárraga et al., 2013; Meilicke et al., 2019), path ranking (Lao & Cohen, 2010; 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 a differentiable way, and most of them are based on neural logic programming (Rocktäschel & Riedel, 2017; Yang et al., 2017; Cohen et al., 2018; Sadeghian et al., 2019; Yang & Song, 2020) or neural theorem provers (Rocktäschel & Riedel, 2017; 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 to 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 a 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 in knowledge graphs to answer questions, and then extract logic rules from reasoning paths (Xiong et al., 2017; Chen et al., 2018; Das et al., 2018; Lin et al., 2018; Shen et al., 2018). However, training effective pathfinding agents is highly challenging, as the reward signal (i.e., whether a path ends at 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-based 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 reasoning 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 al., 2019). With proper architectures, these methods are able to learn
1More precisely, z is a multiset. In this paper, we use “set” to refer to “multiset” for conciseness. 2The codes of RNNLogic are available: https://github.com/DeepGraphLearning/RNNLogic

heading: High-quality Logic Rules
text: some simple logic rules. For example, TransE (Bordes et al., 2013) can 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 an 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 al., 2017), 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 a different task, i.e., reasoning on knowledge graphs.

heading: 3 MODEL
text: 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 a training data distribution, where G is a background knowledge graph characterized by a set of (h,r, t)-triplets which we may also write as r(h, t), q = (h,r, ?) is a query, and a = t is the answer. Given G and the query q, the goal is to predict the correct answer a. 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 ∀{Xi}li=0 r(X0, Xl)← r1(X0, X1) ∧ · · · ∧ rl(Xl−1, Xl) with l 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 ∀{X,Y } r(X,Y )← r−1(X,Y ). In RNNLogic, we treat a set of logic rules which could explain a query as a 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 to generate a set of logic rules, which are 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-quality rules from all generated 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.

heading: 3.1 PROBABILISTIC FORMALIZATION
text: We start by formalizing knowledge graph reasoning in a probabilistic way, where a set of logic rules z is treated as a latent variable. The target distribution p(a|G, q) is jointly modeled by a rule generator and a reasoning predictor. The rule generator pθ defines a prior over a 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 q, and the knowledge graph G. Thus p(a|G, q) can be computed as below:
pw,θ(a|G, q) = ∑ z pw(a|G, q, z)pθ(z|q) = Epθ(z|q)[pw(a|G, q, z)]. (1)
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 θ,w O(θ, w) = E(G,q,a)∼pdata [log pw,θ(a|G, q)] = E(G,q,a)∼pdata [logEpθ(z|q)[pw(a|G, q, z)]]. (2)

heading: 3.2 PARAMETERIZATION
text: Rule Generator. The rule generator defines the distribution pθ(z|q). For a query q, the rule generator aims at generating a set of latent logic rules z for answering the query.
Formally, given a query q = (h,r, ?), we 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← r1∧· · ·∧rl, it can be viewed as a sequence of relations [r,r1,r2 · · ·rl,rEND], where r is the query relation or the rule head, {ri}li=1 are the body of the rule, and rEND is a special relation indicating the end of the relation sequence.
Such relation sequences can be effectively modeled by recurrent neural networks (Hochreiter & Schmidhuber, 1997), 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 rEND. In this process, the probabilities of generated rules are simultaneously computed. With such rule probabilities, we define the distribution over a set of rules z as a multinomial distribution:
pθ(z|q) = Mu(z|N,RNNθ(·|r)), (3) where Mu stands for multinomial distributions, N is a hyperparameter for the size of the set z, and RNNθ(·|r) defines a distribution over compositional rules with rule head being r. The generative process of a rule set z is quite intuitive, where we simply generate N rules with RNNθ to form z.
Reasoning Predictor with Logic Rules. The reasoning predictor defines pw(a|G, q, z). For a query q, the predictor uses a set of rules z to reason on a knowledge graph G and predict the answer a. Following stochastic logic programming (Cussens, 2000), a principled reasoning framework, we use a log-linear model for reasoning. For each query q = (h,r, ?), a compositional rule is able to find different grounding paths on graph G, leading to different candidate answers. For example, given query (Alice, hobby, ?), a rule hobby ← friend ∧ hobby can have two groundings, hobby(Alice,Sing)← friend(Alice,Bob)∧hobby(Bob,Sing) and hobby(Alice,Ski)← friend(Alice,Charlie) ∧ 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 rule in the set z. For each candidate answer e ∈ A, we compute the following scalar scorew(e) for that candidate:
scorew(e) = ∑
rule∈z
scorew(e|rule) = ∑
rule∈z ∑ path∈P(h,rule,e) ψw(rule) · φw(path), (4)
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). ψw(rule) and φw(path) are scalar weights of each rule and path. Intuitively, the score of each candidate answer e is the sum of scores contributed by each rule, i.e., scorew(e|rule). To get scorew(e|rule), we sum over every grounding path found in the graph G. For the scalar weight ψw(rule) of each rule, it is a learnable parameter to optimize. For the score φw(path) of each specific path, we explore two methods for parameterization. One method always sets φw(path) = 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 as a rotation operator on entity embeddings. Then for each grounding path of rule starting from h to e, if we rotate the embedding of h according to 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 e as φw(path), which can be viewed as a measure of the soundness and consistency of each path. For example, given a path Alice friend−−−−→ Bob hobby−−−−→ Sing, we rotate Alice’s embedding with the operators defined by friend and hobby. Afterwards we compute the similarity of the derived embedding and embedding of Sing as φw(path). Such a method allows us to compute a specific φw(path) for each path, which further leads to more precise scores for different candidate answers. See App. C for more details of the parameterization method.
Once we have the score for every candidate answer, we can further define the probability that the answer a of the query q is entity e by using a softmax function as follows:
pw(a = e|G, q, z) = exp(scorew(e))∑
e′∈A exp(scorew(e ′)) . (5)

heading: 3.3 OPTIMIZATION
text: Next, we introduce how we optimize the reasoning predictor and rule generator to maximize the objective in Eq. (2). At each training iteration, we first update the reasoning predictor pw according to some rules generated by the generator, and then update the rule generator pθ 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 O(θ, w) in Eq. (2) with respect to the reasoning predictor pw. To do that, we notice that there is an expectation operation with respect to pθ(z|q) for each training instance (G, q,a). By drawing a sample ẑ ∼ pθ(z|q) for query q, we can approximate the objective function of w at each training instance (G, q,a) as below:
O(G,q,a)(w) = logEpθ(z|q)[pw(a|G, q, z)] ≈ log pw(a|G, q, ẑ) (6)
Basically, we sample a set of rules ẑ from the generator and feed ẑ into the reasoning predictor. Then the parameter w of the reasoning predictor is updated to maximize the log-likelihood of the answer a.
With the updated reasoning predictor, we then update the rule generator pθ to maximize the objective O(θ, 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 ẑ for each data instance (G, q,a), and let the reasoning predictor use ẑ to predict a. For each data instance, the E-step aims to identify a set of K high-quality rules zI from all generated rules ẑ, i.e., zI ⊂ ẑ, |zI | = K. Formally, this is achieved by considering the posterior probability of each subset of logic rules zI , i.e., pθ,w(zI |G, q,a) ∝ pw(a|G, q, zI)pθ(zI |q), with prior of zI from the rule generator pθ and likelihood from the reasoning predictor pw. 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 to its intractable partition function, so we approximate the posterior using a more tractable form with the proposition below:
Proposition 1 Consider a data instance (G, q,a) with q = (h, r, ?) and a = t. For a set of rules ẑ generated by the rule generator pθ, we can compute the following score H for each rule ∈ ẑ:
H(rule) = { scorew(t|rule)− 1
|A| ∑ e∈A scorew(e|rule)
} + logRNNθ(rule|r), (7)
where A is the set of all candidate answers discovered by rules in ẑ, scorew(e|rule) is the score that each rule contributes to entity e as defined by Eq. (4), RNNθ(rule|r) is the prior probability of rule computed by the generator. Suppose s = maxe∈A |scorew(e)| < 1. Then for a subset of rules zI ⊂ ẑ with |zI | = K, the log-probability log pθ,w(zI |G, q,a) can be approximated as follows:∣∣∣∣∣log pθ,w(zI |G, q,a)− ( ∑ rule∈zI H(rule) + γ(zI) + const
)∣∣∣∣∣ ≤ s2 +O(s4) (8) where const is a constant term that is independent from zI , γ(zI) = log(K!/ ∏ rule∈ẑ nrule!), with K being the given size of set zI and nrule being the number of times each rule appears in zI .
We prove the proposition in App. A.1. In practice, we can apply weight decay to the weight of logic rules in Eq. (4), and thereby reduce s = maxe∈A |scorew(e)| to get a more precise approximation. The above proposition allows us to utilize ( ∑ rule∈zI H(rule)+γ(zI)+const) to approximate the log-
posterior log pθ,w(zI |G, q,a), yielding a distribution q(zI) ∝ exp( ∑
rule∈zI H(rule) + γ(zI)) as a
good approximation of the posterior. It turns out that the derived q(zI) is a multinomial distribution, and thus sampling from q(zI) is more tractable. Specifically, a sample ẑI from q(zI) can be formed with K logic rules which are independently sampled from ẑ, where the probability of sampling each rule is computed as exp(H(rule))/( ∑ rule′∈ẑ exp(H(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 pw, 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 a 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 pθ, where we compute the prior probability for each rule and use the probability for regularization.
Empirically, we find that pickingK rules with highestH(rule) to form ẑI works better than sampling from the posterior. Similar observations have been made on the node classification task (Qu et al., 2019). In fact, ẑI 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, 2009). 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 ẑI for each data instance (G, q,a) in the E-step, we further leverage those rules to update the parameters θ of the rule generator in the M-step.
Specifically, for each data instance (G, q,a), we treat the corresponding rule set ẑI as part of the (now complete) training data, and update the rule generator by maximizing the log-likelihood of ẑI :
O(G,q,a)(θ) = log pθ(ẑI |q) = ∑
rule∈ẑI
logRNNθ(rule|r) + const. (9)
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 O(θ, w), please refer to App. B.
Algorithm 1 Workflow of RNNLogic while not converge do
For each instance, use the rule generator pθ to generate a set of rules ẑ (|ẑ| = N ). For each instance, update the reasoning predictor pw based on generated rules ẑ and Eq. (6). E-step: For each instance, identify K high-quality rules ẑI from ẑ according to H(rule) in Eq. (7). M-step: For each instance, update the rule generator pθ according to the identified rules and Eq. (9).
end while During testing, for each query, use pθ to generate N rules and feed them into pw for prediction.

heading: 4 EXPERIMENT

heading: 4.1 EXPERIMENT SETTINGS
text: Datasets. We choose four datasets for evaluation, including 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 statistics 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

heading: Category Algorithm FB15k-237 WN18RRMR MRR H@1 H@3 H@10 MR MRR H@1 H@3 H@10

heading: Category Algorithm FB15k-237 WN18RRMR MRR H@1 H@3 H@10 MR MRR H@1 H@3 H@10
text: are MINERVA (Das et al., 2018), MultiHopKG (Lin et al., 2018) and M-Walk (Shen et al., 2018). Other methods. We also compare with some embedding methods, including TransE (Bordes et al., 2013), DistMult (Yang et al., 2015), ComplEx (Trouillon et al., 2016), ComplEx-N3 (Lacroix et al., 2018), ConvE (Dettmers et al., 2018), TuckER (Balazevic et al., 2019) and RotatE (Sun et 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., φw(path) = 1 in Eq. (4), and we denote this variant as w/o emb.. The second variant leverages entity embeddings and relation embeddings to compute the path score φw(path), and we denote the variant as with emb..
Evaluation Metrics. During evaluation, for each test triplet (h,r, t), we build two queries (h,r, ?) and (t,r−1, ?) with answers t 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@k (H@k) under the filtered setting (Bordes et al., 2013), which is used by most existing studies. Note that there can be a 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 et al. (2020). For fair comparison, in that case we 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 as 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 in MINERVA (Das et al., 2018) and MultiHopKG (Lin et al., 2018), they only consider queries in the form of (h,r, ?), 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), we add an inverse triplet (t,r−1, h) into the training set, yielding an augmented set of training triplets T . We use a closedworld assumption for model training, which assumes that any triplet outside T 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,r, t)}, q = (h,r, ?),a = t). Basically, we use the sampled triplet (h,r, 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 FB15k-237, 5 for WN18RR, and 3 for the rest, which are selected on validation data. See App. D for the detailed setting.

heading: Category Algorithm Kinship UMLSMR MRR H@1 H@3 H@10 MR MRR H@1 H@3 H@10

heading: 4.2 RESULTS
text: Comparison against Existing Methods. We present the results on the FB15k-237 and WN18RR datasets in Tab. 1 and Tab. 2. The results on the Kinship and UMLS datasets are shown in Tab. 3.
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 is because the rule generator and reasoning predictor of RNNLogic 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 is 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 of 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 use logic rules to enhance reasoning performance. For RNNLogic without embedding (w/o emb.), it achieves comparable results to embedding-based methods, especially on WN18RR, Kinship and UMLS where the training triplets are quite limited.
Quality of Learned Logic Rules. Next, we study the quality of rules learned by different methods for reasoning. For each trained model, we let it generate I 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 quality of each rule is measured by its prior probability from the rule generator, and we use beam search to infer top-I rules. The results at different I are in Fig. 2, where RNNLogic achieves much better results. Even with only 10 rules per relation, RNNLogic still achieves competitive results.
Performance w.r.t. the Number of Training Triplets. To better evaluate different methods under cases where training triplets are very limited, in this section we reduce the amount of 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 is more significant as we reduce training triplets, showing that RNNLogic is more robust to data sparsity.
20 40 60 80 100 # Logic Rules
0.0
0.1
0.2
0.3
0.4
0.5
0.6
M R
R
Kinship
Algorithm Empirical Precision NeuralLP Path Ranking RNNLogic
20 40 60 80 100 # Logic Rules
0.0
0.1
0.2
0.3
0.4
M R
R
WN18RR
Algorithm Empirical Precision NeuralLP Path Ranking RNNLogic
Figure 2: Performance w.r.t. # logic rules. RNNLogic achieves competitive results even with 10 rules per query relation. 100 200 500 1000 2000 # Embedding Dimension
0.1
0.2
0.3
0.4
0.5
0.6
0.7
M R
R
Kinship
Algorithm RotatE RNNLogic with emb.
Figure 3: Performance w.r.t. embedding dimension.
Performance w.r.t. Embedding Dimension. RNNLogic with emb. uses entity and relation embeddings to improve the reasoning predictor. Next, we study its performance with different embedding dimensions. The results are presented in Fig. 3, where we compare against RotatE (Sun et al., 2019). We see that RNNLogic significantly outperforms RotatE at every embedding dimension. The improvement is mainly from the use 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. F for details). We empirically compare the two algorithms in the w/o emb. case. The results on Kinship and UMLS are presented in Tab. 4. We see EM consistently outperforms REINFORCE.
33% 67% 100% Training Triplets
0.1
0.2
0.3
0.4
0.5
0.6
M R
R
Kinship
Algorithm NeuralLP DRUM MINERVA RotatE RNNLogic w/o emb.
33% 67% 100% Training Triplets
0.1
0.2
0.3
0.4
0.5
0.6
0.7
M R
R
UMLS
Algorithm NeuralLP DRUM MINERVA RotatE RNNLogic w/o emb.
Figure 4: Performance w.r.t. # training triplets. RNNLogic is more robust to data sparsity even without using embeddings.
Kinship UMLS MRR MRR
REINFORCE 0.312 0.504
EM 0.639 0.745
Table 4: Comparison between REINFORCE and EM.
Case Study of Generated Logic Rules. Finally, we show some logic rules generated by RNNLogic on the FB15k-237 dataset in Tab. 5. We can see that these logic rules are meaningful and diverse. The first rule is a 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.

heading: 5 CONCLUSION
text: This paper studies learning logic rules for knowledge graph reasoning, and an approach called RNNLogic is proposed. RNNLogic treats a set of logic rules as a latent variable, and a rule generator as well as a 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.

heading: ACKNOWLEDGMENTS
text: 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-Bird Gift Fund and a NRC Collaborative R&D Project (AI4D-CORE-06). This project was also partially funded by IVADO Fundamental Research Project grant PRF-2019-3583139727.

heading: A PROOFS
text: 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, we aim to sample from the posterior distribution over rule sets. However, directly sampling from the posterior distribution is intractable due to the intractable partition function. Therefore, we introduce Proposition 1, which gives an approximation distribution with more tractable form for the posterior distribution. With this approximation, sampling becomes much easier. In Section A.1, we present the proof of Proposition 1. In Section A.2, we show how to perform sampling based on the approximation of the posterior distribution.

heading: A.1 PROOF OF PROPOSITION 1
text: Next, we prove proposition 1, which is used to approximate the true posterior probability in the E-step of optimization. We first restate the proposition as follows:
Proposition Consider a data instance (G, q,a) with q = (h, r, ?) and a = t. For a set of rules ẑ generated by the rule generator pθ, we can compute the following score H for each rule ∈ ẑ:
H(rule) = { scorew(t|rule)− 1
|A| ∑ e∈A scorew(e|rule)
} + logRNNθ(rule|r),
where A is the set of all candidate answers discovered by rules in ẑ, scorew(e|rule) is the score that each rule contributes to entity e as defined by Eq. (4), RNNθ(rule|r) is the prior probability of rule computed by the generator. Suppose s = maxe∈A |scorew(e)| < 1. Then for a subset of rules zI ⊂ ẑ with |zI | = K, the log-probability log pθ,w(zI |G, q,a) could be approximated as follows:∣∣∣∣∣log pθ,w(zI |G, q,a)− ( ∑ rule∈zI H(rule) + γ(zI) + const
)∣∣∣∣∣ ≤ s2 +O(s4) where const is a constant term that is independent from zI , γ(zI) = log(K!/ ∏ rule∈ẑ nrule!), with K being the given size of set zI and nrule being the number of times each rule appears in zI .
Proof: We first rewrite the posterior probability as follows:
log pθ,w(zI |G, q,a) = log pw(a|G, q, zI) + log pθ(zI |q) + const
= log exp(scorew(t))∑ e∈A exp(scorew(e)) + logMu(zI |K,RNNθ(·|r)) + const,
where const is a constant term which does not depend on the choice of zI , and RNNθ(·|r) defines a probability distribution over all the composition-based logic rules. The probability mass function of the above multinomial distribution Mu(zI |K,RNNθ(·|r)) can be written as below:
Mu(zI |K, q) = K!∏
rule∈ẑ nrule! ∏ rule∈ẑ RNNθ(rule|r)nrule ,
where K is the size of set zI and nrule is the number of times a rule appears in zI . Letting γ(zI) = log(K!/ ∏ rule∈ẑ nrule!), then the posterior probability can then be rewritten as:
log pθ,w(zI |G, q,a)
= log exp(scorew(t))∑ e∈A exp(scorew(e)) + log K!∏ rule∈ẑ nrule! + log ∏ rule∈ẑ RNNθ(rule|r)nrule + const = log exp(scorew(t))∑ e∈A exp(scorew(e)) + γ(zI) + ∑
rule∈zI
logRNNθ(rule|r) + const
=scorew(t)− log ∑ e∈A exp(scorew(e)) + γ(zI) + ∑ rule∈zI logRNNθ(rule|r) + const.
The above term log ∑ e∈A exp(scorew(e)) makes the posterior distribution hard to deal with, and thus we approximate it using Lemma 1, which we prove at the end of this section.
Lemma 1 Let e ∈ A be a finite set of entities, let |scorew(e)| ≤ s < 1, and let scorew be a function from entities to real numbers. Then the following inequalities hold:
0 ≤ log (∑ e∈A exp(scorew(e)) ) − (∑ e∈A 1 |A| scorew(e) + log(|A|) ) ≤ s2 +O(s4).
Hence, using the lemma we can get the following upper bound of the posterior probability:
log pθ,w(zI |G, q,a) =scorew(t)− log ∑ e∈A exp(scorew(e)) + γ(zI) + ∑ rule∈zI logRNNθ(rule|r) + const
≤scorew(t)− ∑ e∈A 1 |A| scorew(e) + γ(zI) + ∑ rule∈zI logRNNθ(rule|r) + const
= ∑
rule∈zI
H(rule) + γ(zI) + const,
and also the following lower bound of the posterior probability:
log pθ,w(zI |G, q,a) =scorew(t)− log ∑ e∈A exp(scorew(e)) + γ(zI) + ∑ rule∈zI logRNNθ(rule|r) + const
≥scorew(t)− ∑ e∈A 1 |A| scorew(e) + γ(zI) + ∑ rule∈zI logRNNθ(rule|r) + const− s2 −O(s4)
= ∑
rule∈zI
H(rule) + γ(zI) + const− s2 −O(s4),
where const is a constant term which does not depend on zI .
By combining the lower and the upper bound, we get:∣∣∣∣∣log pθ,w(zI |G, q,a)− ( ∑
rule∈zI
H(rule) + γ(zI) + const )∣∣∣∣∣ ≤ s2 +O(s4) Thus, it only remains to prove Lemma 1 to complete the proof. We use Theorem 1 from (Simic, 2008) as a starting point:
Theorem 1 Suppose that x̃ = {xi}ni=1 represents a finite sequence of real numbers belonging to a fixed closed interval I = [a, b], a < b. If f is a convex function on I , then we have that:
1
n n∑ i=1 f(xi)− f
( 1
n n∑ i=1 xi
) ≤ f(a) + f(b)− 2f ( a+ b
2
) .
As (− log) is convex and exp(scorew(e)) ∈ [exp(−s), exp(s)], Theorem 1 gives us that:
− 1 |A| ∑ e∈A log (exp(scorew(e))) + log
( 1
|A| ∑ e∈A exp(scorew(e))
)
≤ − log(exp(−s))− log(exp(s)) + 2 log ( exp(−s) + exp(s)
2
) .
After some simplification, we get:
log (∑ e∈A exp(scorew(e)) )
≤ ∑ e∈A 1 |A| scorew(e) + log(|A|) + 2 log ( exp(−s) + exp(s) 2 ) = ∑ e∈A 1 |A| scorew(e) + log(|A|) + 2s− 2 log 2 + 2 log(1 + exp(−2s))
≤ ∑ e∈A 1 |A| scorew(e) + log(|A|) + s2 +O(s4),
(10)
where the last inequality is based on Taylor’s series log(1 + ex) = log 2 + 12x+ 1 8x 2 +O(x4) with |x| < 1. On the other hand, according to the well-known Jensen’s inequality, we have:
log
( 1
|A| ∑ e∈A exp(scorew(e)) ) ≥ 1 |A| ∑ e∈A log (exp(scorew(e))) ,
which implies:
log (∑ e∈A exp(scorew(e)) ) ≥ ∑ e∈A 1 |A| scorew(e) + log(|A|). (11)
By combining Eq. (10) and Eq. (11), we obtain:
0 ≤ log (∑ e∈A exp(scorew(e)) ) − (∑ e∈A 1 |A| scorew(e) + log(|A|) ) ≤ s2 +O(s4).
This completes the proof. .

heading: A.2 SAMPLING BASED ON THE APPROXIMATION OF THE TRUE POSTERIOR
text: Based on Proposition 1, the log-posterior probability log pθ,w(zI |G, q,a) could be approximated by ( ∑
rule∈zI H(rule)+γ(zI)+const), with const being a term that does not depend on zI . This implies that we could construct a distribution q(zI) ∝ exp( ∑ rule∈zI H(rule) + γ(zI)) to approximate the true posterior, and draw samples from q as approximation to the real samples from the posterior.
It turns out that the distribution q(zI) is a multinomial distribution. To see that, we rewrite q(zI) as:
q(zI) = 1
Z exp ( ∑ rule∈zI H(rule) + γ(zI) )
= 1
Z exp (γ(zI)) ∏ rule∈zI exp (H(rule))
= 1
Z K!∏ rule∈ẑ nrule! ∏ rule∈ẑ exp (H(rule))nrule
= 1 Z ′ K!∏
rule∈ẑ nrule! ∏ rule∈ẑ qr(rule)nrule
= 1
Z ′ Mu(zI |K, qr),
where nrule is the number of times a rule appears in the set zI , qr is a distribution over all the generated logic rules ẑ with qr(rule) = exp(H(rule))/ ∑ rule′∈ẑ exp(H(rule
′)), Z and Z ′ are normalization terms. By summing over zI on both sides of the above equation, we obtain Z ′ = 1, and hence:
q(zI) = Mu(zI |K, qr).
To sample from such a multinomial distribution, we could simply sample K rules independently from the distribution qr, and form a sample ẑI with these K 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 hardassignment EM algorithm, we need to draw a sample ẑI with the maximum posterior probability. Based on the above approximation q(zI) of the true posterior distribution pθ,w(zI |G, q,a), we could simply construct such a sample ẑI with K rules which have the maximum probability under the distribution qr. By definition, we have qr(rule) ∝ exp(H(rule)), and hence drawing K rules with maximum probability under qr is equivalent to choosing K rules with the maximum H values.

heading: B MORE ANALYSIS OF THE EM ALGORITHM
text: In RNNLogic, we use an EM algorithm to optimize the rule generator. In this section, we show why this EM algorithm is able to maximize the objective function of the rule generator.
Recall that for a fixed reasoning predictor pw, we aim to update pθ to maximize the log-likelihood function log pw,θ(a|G, q) for each data instance (G, q,a). Directly optimizing log pw,θ(a|G, q) is difficult due to the latent logic rules, and therefore we consider the following evidence lower bound of the log-likelihood function:
log pw,θ(a|G, q) ≥ Eq(zI)[log pw(a|G, q, zI) + log pθ(zI |q)− log q(zI)] = LELBO(q, pθ), (12) where q(zI) is a variational distribution, and the equation holds when q(zI) = pθ,w(zI |G, q,a). With this lower bound, we can optimize the log-likelihood function log pw,θ(a|G, q) with an E-step and an M-step. In the E-step, we optimize q(zI) to maximize LELBO(q, pθ), which is equivalent to minimizing KL(q(zI)||pθ,w(zI |G, q,a)). By doing so, we are able to tighten the lower bound. Then in the M-step, we further optimize θ to maximize LELBO(q, pθ). Next, we introduce the details. E-step. In the E-step, our goal is to update q to minimize KL(q(zI)||pθ,w(zI |G, q,a)). However, there are a huge number of possible logic rules, and hence optimizing q(zI) on every possible rule set zI is intractable. To solve the problem, recall that we generate a set of logic rules ẑ when optimizing the reasoning predictor, and here we add a constraint to q based on ẑ. Specifically, we constrain the sample space of q(zI) to be all subsets of ẑ with size being K, i.e., zI ⊂ ẑ and |zI | = K. In other words, we require ∑ zI⊂ẑ,|zI |=K q(zI) = 1. With such a constraint, we can further use proposition 1 to construct the variational distribution q to approximate pθ,w(zI |G, q,a), as what is described in the model section.
M-step. In the M-step, our goal is to update pθ to maximize the lower bound LELBO(q, pθ). To do that, we notice that there is an expectation operation with respect to q(zI) in LELBO(q, pθ). By drawing a sample from q(zI), LELBO(q, pθ) can be estimated as follows:
LELBO(q, pθ) = Eq(zI)[log pw(a|G, q, zI) + log pθ(zI |q)− log q(zI)] ' log pw(a|G, q, ẑI) + log pθ(ẑI |q)− log q(ẑI),
(13)
where ẑI ∼ q(zI) is a sample drawn from the variational distribution. By ignoring the terms which are irrelevant to pθ, we obtain the following objective function for θ:
log pθ(ẑI |q), (14) which is the same as the objective function described in the model section.
As a result, by performing the E-step and the M-step described in the model section, we are able to update pθ to increase the lower bound LELBO(q, pθ), and thereby push up the log-likelihood function log pw,θ(a|G, q). Therefore, we see that the EM algorithm can indeed maximize log pw,θ(a|G, q) with respect to pθ.

heading: C DETAILS ABOUT PARAMETERIZATION AND IMPLEMENTATION
text: 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.

heading: C.1 REASONING PREDICTOR WITH LOGIC RULES
text: We start with the reasoning predictor with logic rules. Recall that for each query, our reasoning predictor leverages a set of logic rules z to give each candidate answer a score, which is further used to predict the correct answer from all candidates.
Specifically, let A denote the set of all the candidate answers discovered by logic rules in set z. For each candidate answer e ∈ A, we define the following function scorew to compute a score:
scorew(e) = ∑
rule∈z
scorew(e|rule) = ∑
rule∈z ∑ path∈P(h,rule,e) ψw(rule) · φw(path), (15)
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). ψw(rule) and φw(path) are scalar weights of each rule and path. For the scalar weight ψw(rule) of a rule, we initialize ψw(rule) as follows:
ψw(rule) = E(G,q,a)∼pdata
[ |P(h, rule, t)| − 1
|A| ∑ e∈A |P(h, rule, e)|
] , (16)
where |P(h, rule, t)| is the number of relational paths starting from head entity h, following the relations in rule and ending at tail entity t. The form is 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 or initializing them as 0, which yield similar results.
For the scalar score φw(path) of a path, we either fix it to 1, 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 e is denoted as xe, and the embedding of a relation r is denoted as xr. For a grounding path path = e0 r1−→ e1 r2−→ e2 · · · el−1
rl−→ el, we follow the idea in RotatE (Sun et al., 2019) and compute φw(path) in the following way:
φw(path) = σ(δ − d(xe0 ◦ xr1 ◦ xr2 ◦ · · · ◦ xrl ,xel)), (17)
where σ(x) = 11+e−x is the sigmoid function, d is a distance function between two complex vectors, δ is a hyperparameter, and ◦ is the Hadmard product in complex spaces, which could be viewed as a rotation operator. Intuitively, for the embedding xe0 of entity e0, we rotate xe0 by using the rotation operators defined by {rk}lk=1, yielding (xe0 ◦ xr1 ◦ xr2 ◦ · · · ◦ xrl). Then we compute the distance between the new embedding and the embedding xel of entity el, and further convert the distance to a value between 0 and 1 by using the sigmoid function and a hyperparameter δ.

heading: C.2 RULE GENERATOR
text: This paper focuses on compositional rules, which have the abbreviation form r ← r1 ∧ · · · ∧ rl and thus could be viewed a sequence of relations [r,r1,r2 · · ·rl,rEND], where r is the query relation or the head of the rule, {ri}li=1 are the body of the rule, and rEND is a special relation indicating the end of the relation sequence. We introduce a rule generator RNNθ parameterized with an LSTM (Hochreiter & Schmidhuber, 1997) to model such sequences. Given the current relation sequence [r,r1,r2 · · ·ri], 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 as follows:
• Initialize the hidden state of the RNNθ as follows:
h0 = f(vr),
where vr 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:
ht = LSTM(ht−1, g([vr,vrt ]),
where vrt is a parameter vector associated with the relation rt, [vr,vrt ] is the concatenation of vr and vrt , g is a linear transformation.
• Generate rt+1 and its probability based on ht+1 and the following vector:
softmax(o(ht+1)).
Suppose the set of relations is denoted asR. We first transform ht+1 to a |R|-dimensional vector by using a linear transformation o, and then apply softmax function to the |R|-dimensional vector to get the probability of each relation. Finally, we generate rt+1 according to the probability vector.

heading: D EXPERIMENTAL SETUP

heading: D.1 DATASET STATISTICS
text: The statistics of datasets are summarised in Table 6.

heading: D.2 EXPERIMENTAL SETUP OF RNNLOGIC
text: 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, t), we add an inverse triplet (t,r−1, h) into the training set, yielding an augmented set of training triplets T . 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,r, t)}, q = (h,r, ?),a = t). Basically, we use the sampled triplet (h,r, 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 constructed by using all the triplets in T . Reasoning Predictor. For the reasoning predictor in with embedding cases, the embedding dimension is set to 500 for FB15k-237, 200 for WN18RR, 2000 for Kinship and 1000 for UMLS. We pre-train these embeddings with RotatE (Sun et al., 2019). The hyperparameter δ for computing φw(path) in Equation (17) is set to 9 for FB15k-237, 6 for WN18RR, 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 we decrease the learning rate in a cosine shape.
Rule Generator. For the rule generator, the maximum length of generated rules is set to 4 for FB15k-237, 5 for WN18RR, and 3 for Kinship and UMLS. These numbers are chosen according to model performace on the validation data. The size of input and hidden states in RNNθ are set to 512 and 256. The learning rate is set to 1× 10−3 and monotonically decreased in a 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, we 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, we identify 300 rules as high-quality logic rules.
Evaluation. In testing, for each query q = (h, r, ?), we use the rule generator pθ to generate 1000 logic rules, and let the reasoning predictor pw use the generated logic rules to predict the answer a.

heading: E CASE STUDY
text: 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 r−→ t means triplet (h,r, t) and h r←− t means triplet (h,r−1, t), or equivalently (t,r, h).

heading: F CONNECTION WITH REINFORCE
text: In terms of optimizing the rule generator, our EM algorithm has some connections with the REINFORCE algorithm (Williams, 1992). Formally, for a training instance (G, q,a), REINFORCE computes the derivative with respect to the parameters θ of the rule generator as follows:
Epθ(z|q)[R · ∇θ log pθ(z|q)] ' R · ∇θ log pθ(ẑ|q), (18)
where ẑ is a sample from the rule generator, i.e., ẑ ∼ pθ(z|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(a|G, q, ẑ). In contrast, our EM optimization algorithm optimizes the rule generator with the objective function defined in Equation (2), yielding the derivative ∇θ log pθ(ẑI |q). Comparing the derivative to that in REINFORCE (Eq. (18)), we see that EM only maximizes the log-probability for rules selected in the E-step, while REINFORCE maximizes the log-probability for all generated rules weighted by the scalar reward R. Hence the two approaches coincide if R is set to 1 for the selected rules from the approximate posterior and 0 otherwise. In general, finding an effective reward function to provide feedback is nontrivial, and we empirically compare these two optimization algorithms in experiments.

Review summaries:
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

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.