Differentiable Learning of Graph-like Logical Rules from Knowledge Graphs
Authors: Hongzhi Shi
quanming yao
Yong Li
Venue:  (2021)
Keywords: knowledge graph
logical rules
logical query

Abstract: Logical rules inside a knowledge graph (KG) are essential for reasoning, logical inference, and rule mining. However, existing works can only handle simple, i.e., chain-like and tree-like, rules and cannot capture KG's complex semantics, which can be better captured by graph-like rules. Besides, learning graph-like rules is very difficult because the graph structure exhibits a huge discrete search space. To address these issues, observing that the plausibility of logical rules can be explained by how frequently it appears in a KG, we propose a score function that represents graph-like rules with learnable parameters. The score also helps relax the discrete space into a continuous one and can be uniformly transformed into matrix form by the Einstein summation convention. Thus, it allows us to learn graph-like rules in an efficient, differentiable, and end-to-end training manner by optimizing the normalized score. We conduct extensive experiments on real-world datasets to show that our method outperforms previous works due to logical rules' better expressive ability. Furthermore, we demonstrate that our method can learn high-quality and interpretable graph-like logical rules.

Under review as a conference paper at ICLR 2021
DIFFERENTIABLE LEARNING OF GRAPH-LIKE LOGI- CAL RULES FROM KNOWLEDGE GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Logical rules inside a knowledge graph (KG) are essential for reasoning, logical inference, and rule mining. However, existing works can only handle simple, i.e., chain-like and tree-like, rules and cannot capture KG's complex semantics, which can be better captured by graph-like rules. Besides, learning graph-like rules is very difficult because the graph structure exhibits a huge discrete search space. To address these issues, observing that the plausibility of logical rules can be explained by how frequently it appears in a KG, we propose score function that represents graph-like rules with learnable parameters. The score also helps relax the discrete space into a continuous one and can be uniformly transformed into matrix form by the Einstein summation convention. Thus, allows us to learn graph-like rules in an efficient, differentiable, and end-to-end training manner by optimizing the normalized score. We conduct extensive experiments on real-world datasets to show that method outperforms previous works due to logical rules' better expressive ability. Furthermore, we demonstrate that our method can learn high-quality and interpretable graph-like logical rules.
INTRODUCTION
Knowledge graph (KG) refers to special type of directed graphs including various entities as nodes and relations as directed edges representing large number of facts (Auer al., 2007: Bollacker et al., 2008). In KG, logical rules are set of compositional logical relations within a specific struc- ture, which are important for reasoning (Cohen et al., 2019; Zhang et al., 2019a; Qu & Tang, 2019), logical inference (Dhingra et al., 2020; Das et al., 2018; Xiong et al., 2017), rule mining (Sadeghian et al., 2019; Yang et al., 2017: Yang & Song, 2020), theorem proving (Rocktäschel & Riedel, 2017; Minervini et al., 2018: 2020), etc.
Learning logical rules (Galárraga et al., 2015; Chen et al., 2016), as an important task, aims to infer structural logical rule for logical query relation, which can support logical query or link prediction while providing interpretable logical rules. The structure of logical queries can be various with very different semantics, shown in Figure 1, including chain-like, tree-like and graph-like rules. Learning the logical rules, especially the graph-like rules, are very difficult because both the logical structure and the relations assigned on each edge are unknown requiring to be inferred from input-output pairs, which compose a huge discrete searching space.
In this paper, dive into the problem of learning graph-like logical rules, including both the logical structure representing how logic connects and the relations assigned on different edges. Recently, series of works on learning logical rule (Yang et al., 2017: Sadeghian et al., 2019; Yang & Song, 2020) has been proposed, which not only can support tasks including logical query and link pre- diction, but as side effect, can also provide the mined logical rules with high interpretability. As shown in Figure 1, all these works are limited to learning chain-like rules (the left case) (Yang et al., 2017: Sadeghian et al., 2019) or tree-like rules (the middle case) (Hamilton et al., 2018; Ren et al., 2020; Yang& & Song, 2020). However, there are widely-existed graph-like logical rules, which the existing works cannot handle due to their limited expressive ability about logical rules. Learn- ing graph-like logical rules is very important in many scenarios such recommendation systems, ceeestion-nnswerii system and KG completion, while learning such complex rules is still an open and challenging problem.

---

Under review as a conference paper at ICLR 2021
Chain-like rule
Tree like rule
Graph like rule
Questions
Who is X's friend's supervisor?
What the address the university that both the students X, and X study
Which book readers with the book while the readers friends?
Input Entity
Target Entity
Variable Entity
Logical
G= (e. (V).).)).
X
V. HIA,,,
Structural Logical Rules
friend
Supervisor
study at
address
read
read(inv)
M- R4 ())
X
study at
read
read[inv]
friend
supervisor
study.at
address of
Knowledge Graphs and Scores
5,13
friend
s,:2
read
5,14
read(inv)
sy (=([),,)))
5:2
5,1
5
Figure 1: Three examples of chain-like, tree-like, graph-like rules (three columns) and their corre- sponding semantic questions, logical structures, structural logical rules, KGs and scores (four rows).
We propose novel method that can explicitly learn the structural logical rules, including a logical structure and the relations assigned on each edge, and we can use the inferred logical rules for conducting inductive logical query with unseen entities and graphs. All the structural logical rules construct discrete search space to explore, and searching for that is an NP-hard problem. To tackle with this problem, our method constructs continuous space including both the structural information and the relational information to learn, which allows us to train our model in an end- to-end differentiable manner. Specifically, as shown in Figure we take the frequency of a logical rule in KG its score estimate how likely logical rule stands. After optimizing w.r.t. the normalized score, our model yields interpretable logical rules of high quality, and support inductive logical query and link prediction, which has been demonstrated by our extensive experiments real-world datasets.
Our contributions can be summarized as following three aspects,
We first propose the problem of learning graph-like rules and design an end-to-end differentiable model that can learn graph-like logical rules instead of only chain-like or tree-like like rules, modeling both the logical structure describing how the logic connects and relations assigned on edges.
We provide uniform expression by Einsum to represent the score of all graph-like logical rules, including the ones that cannot be represented by a combination matrix/element-wis addi- tion/product, which is elegant for expression and convenient for implementation.
We conduct extensive experiments demonstrate that our model has better expressive ability for graph-like logical rules and show our model can mine high-quality logical rules with high interpretability.
2 PROBLEM FORMULATION
Here, formally introduce the definition of logical score, and based on that, further introduce our model's main focus, relation inference (Yang et al., 2017: Sadeghian et al., 2019) and structural rule learning, and our evaluation task, logical query (Hamilton al., 2018 Ren al., 2020).
2

---

Under review as a conference paper at ICLR 2021
Definition 1 (Logical Score) Logical rule is formulated by N Rs - Repe 8, where S, is the score for 1 Rs, and R₂ is a relation R. = (V,, Vi), V. E Y (Z,)) 1....,.. n and Reps is a relation Repe((x)) Y), {X₃} are input nodes, {Zz} are free-variable nodes, Y is output node.
For strict logical query, for any Repe ((x)) Y). there exists (Z1,..., 3x) that make A be true, we can draw the conclusion A R₁ + Repx. However, because KG is usually noisy and incomplete, for learning logical rules, our key insight is to design the score as the number of free- variable tuples (Z1.
Zx) that make A,_ R; be true, which can capture the correlation between logical rules and the input-output pairs of a logical query. For example, for the case in the middle of Figure 1, Raudty at 1 2) A Bandy (X2, Z) A Raddress of (2 Y) - Repx (X1, X2, Y); for the case in the right of Figure 1, we have Reead( (X, Z1) A (X, Zz) A Risend Z1. Zz) A Reeadtimo) (z. Y) A Reeadtiav) Zz, Y) + Repx (X, Note that, Reps can both be relation that exists in the KG and the numan-definee logic rule for a query, which tends to be more complex. The score s, serves as two roles: (i). when input-output pairs are given, it can measure how likely logical rule is, which corresponds to the scenario of Task and Task 2; (ii). when logical rules for query and inputs are given, it can measure how much output node fits the query, which corresponds Task 3.
Task 1 (Relation Inference) Given Repe ((x;). Y) is satisfied and logical structure composed by G (e1 (V), e2 (V2, Vo),...; ...}. we need to infer how to assign relation R3 on each edge e, to form a logical rule AI Re,,, Vi) that will make the score 5n of Reps ((xx((XX): Y) high.
For this task, previous relation inference works (Yang et al., 2017: Sadeghian et al., 2019) can also conduct this task but they limit the G to be a chain-like We model the relation between the input- output pairs behind the query as Repx and infer its graph-like logical rule.
Task (Structural Rule Learning) Given Rope (1X,) ,), Y) is satisfied and the possible max nodes number á 2 Tee where ne is the size of (X,,,8 we need to infer what structure G = (V1, (2),ee(Va "2)....,e"l"" eV, Vi]} where ne S n S â and the relations assigned on edges AB R2 that will make the score 8, high.
For this task, logical structures in previous works (Yang et al., 2017: Sadeghian et al., 2019; Yang & Song, 2020) are limited to chains trees, and the number of input entities are limited to 1. However, we can infer both the logical structure and the relations assigned on edges for graph-like rules.
Task (Logical Query) Given input nodes {X₂} } and the query relation, the target nodes of this query can be represented by = (Y| ( (Xih. Y)}.
Note that, in previous works (Hamilton et al., 2018; Ren et 2020), the logical rule Reps = - R is given, different from those works, we need to infer the A R₁ for logic query. Our model targets at the inference of complex logical rules, and use the inferred logic rules to conduct logical query as evaluation task. For evaluation, we regard Task 3 as the main task and the other two tasks as side products.
3 RELATED WORKS
3.1 LOGICAL QUERY FROM KNOWLEDGE GRAPHS
Logical rules learning (Teru et al., 2020; Evans & Grefenstette, 2018; Manhaeve et al., 2018; Wang et al., 2019; Ho et al., 2018) is learn logical rules (Task 1) for logical query (Task 3) in an inductive setting. Neural-I.P (Yang et al., 2017) design an end-to-end differentiable framework to learn the probability of different logical rules. Furthermore, DRUM (Sadeghian et al., 2019) improve Neural- LP (Yang al., 2017) by introducing the low-rank matrix decomposition. However, these two works can only tackle chain-like logical rules. Different from our model, they mainly focus on relatively simple logical rules such chain-like rike-like rules. To the best of our knowledge, the first one that can learn to infer graph-like complex logical rule including structure and relations assigned on different edges.
model is
Logical queries (Serge et al., 1995) aims to learn how to accurately query an entity (Task 3) ac- cording given input entities and relations representing the logical rules in transductive setting.
3

---

Under review as a conference paper at ICLR 2021
Table I: Comparison between our method and existing methods.
Methods
GQF
Q2B
Grall.
NeuralLP
DRUM
Ours
G's structure
tree
tree
chain
chain
chain
graph
#{+}
multiple multiple single single single
multiple
Variable
Z's position
middle middle middle middle middle
arbitrary
Y's position
end end end end end
arbitrary
Tasks
3
3
3
1,3
1,3
1,2,3
Inductive
x
x
V
V
V
II
V
Interpretable
x x x
V
V
V
According to Task 3, the logic rules representing the semantics of query explicitly given at both training and testing stages in this branch of works, but in paper, the logic rules require to be inferred in the training stage. For most of these works, the main idea is to project entities into the embedding space (Bordes et al., 2013; Trouillon et al., 2016; Sun al., 2018; Balažević et al., 2019) and transform the relations into type of manipulation in embedding space, such as a linear pro- jection. Hamilton al. (2018) first proposes an embedding-based method for conduct query with tree-like logical rules. Ren et al. (2020) further improves Hamilton et al. (2018) by modeling the entities as box embedding rather than vector embedding, which is more natural for the manipulation for the conjunction of sets. Different from our model, these methods require explicit given logical structures with given relations on edges.
3.2 DIFFRENTIABLE INDUCTIVE LOGIC PROGRAMMING
Inductive Logic Programming (ILP) (Shapiro, 1981) aims to conduct inductive logic reasoning or theorem proving based on entities, predicates and formulas. Predicates refer to a type of func- tion projecting
more entities to 0 or 1. For example, isM)le(X) return whether X is a person (1) or not (0), isFatherO X returns whether Y the father of X (1) or not (0), where X and Y are variables which we instantiate them as entities. Then, can de- fine formulas by combining predicates by logic operations including and/or/not. For examples, isMale(XX A is (sFatherOf(Y.X. body formula isM ale(X) X) A is 1aFatherOf(( , X) and a head formula isSonO f(X, Y). The physi- cal meaning of this entailment means if the body formula satisfied (equals to 1), then we can draw the conclusion in the head formula. ILP is an NP-hard problem (Zhang et al.. 2019b) and tradi- tional methods relying on hard matching (Galárraga al., 2015) for ILP are of high computational complexity due to the very large search space.
isSonOf Y) is logic entailment, which composes of
Markov Logic Networks(MLN) (Richardson& Domingos, 2006; Kok & Domingos, 2005) elegantly combine ILP problem and probabilistic models, which define potential functions in Markov random field with formulas as nodes. Different from that, we consider the logical rule as a graph with entities as nodes. In recent years, lot of works on differentiable ILP (Rocktäschel & Riedel, 2017; Minervini et al., 2018: 2020) have been proposed. The most recent work NLIL (Yang & Song. 2020), which targets learning the logic rules based unary and binary predicates efficiently. When we only focus on the binary predicate, then we can naturally conduct ILP based on KG because the relations in KG can be naturally regarded a binary predicate on two entities (exist: 1 not exist: 0). If we only use NLIL (Yang Song, 2020) for binary predicates (relations in KG), then it can only tackle chain-like rules (same as Neural-LP (Yang et al., 2017) and DRUM (Sadeghian al., 2019)) instead of graph-like rules. To the best of our knowledge, differentiable ILP methods cannot handle graph-like rules.
THE PROPOSED METHOD
Logical graph structure and relations assigned on edges construct a huge discrete space, which extremely hard to search (Task 1 and Task 2). The key idea of our method is to design score function modeling both the logical structure and the relation assigned on edges, by optimizing which can obtain complex rules and conduct logical query (Task 3).
4

---

Under review as a conference paper at ICLR 2021
First, we introduce how represent the score s, in when given the logical structure, estimate how likely a logical rule is, by maximizing which we can infer relations (Task 1).
Second, we introduce how to merge the structural information into the score to uniformly obtain the logical structure and relations on edges by optimizing one score (Task 2).
Finally, we provide a uniform and elegant expression of the score s, in matrix form by Einsum for all graph-like logical rules and exploit cross-entropy loss for optimizing our model, which can further support logical query (Task 3).
4.1 RELATION INFERENCE FOR GRAPH-LIKE LOGICAL RULES
Given input node (X,) target node Y and structure G as shown in Figure 1, we use the number of the tuples ({Z+}) that satisfy A R2 as the score to evaluate the plausibility of a logical rule. We denote the adjacency matrix of relation RG as A,, which is soft choice among adjacency matrices As corresponding to all relations R. KG. Then, the score, can be represented as
*(())), Σ
VI 2= Σ IV ZK= II A.V. VD)
where V,, V. E ((X)).Y, (2+)), A, Vi] denotes the (V; V!'diidexed entry in A,, A, is defined as
A, = Σ As exp((:x))
Σ E exp(3:x))
(2)
where Ag represents the k-th relation in the set of relations in KG, by which efficiencts {B(x} on different relations as learnable parameters to learn which relation should be assigned on each edge given the logical structure. For the right case in Figure 1. Eq. (1) becomes
use the
IV] 8r *x((x)), Σ 7. E 72-1 A1|X, 31 A2 Z2) As 2, 22) 71, (722 Y],
M
(3)
Intuitively, in Eq. (3), after assigning an entity for each free variable Z, A, |X, 21 =1 means there is relation R2 between X and Z1, the product of such terms equals to only if all of them equal to 1. which means all free variable 21 and Ze together with and satisfies the logical rule A Rç- We sum w.r.t. Zi...., ZK to caleulate the count of such tuples (Z1...., Zx) in the full KG that satisfied the logical rule to measure its plausibility.
4.2 STRUCTURAL RULE LEARNING
In realistic logical inference scenarios (Yang & Song, 2020; Sadeghian et al., 2019), besides the relations, we also do not know the structure of the logical rule G {er (V1, V7), e2 (V, Vi),,.. ... Thus, need to infer the logical structure well as the relations. To achieve this goal, special auxiliary relations: "removing" relation represented by full-one matrix 1 (all the entries are 1) and "merging" relation represented by identity matrix (the diagonal entries are and the others are 0) into the adjacency matrices. The physical meaning of identity matrix / is merging two connected nodes as one node in the logical rule, because if /[,, V'] = 1, then V; = V/. i.e., they are the same entity in KG; the full-one matrix 1 removes the edge in the logical rule, because for any V; and V/, we have 1[,, Vi]] 1, i.c., there is no relation requirement between V/ and V/". We expand the parameters {. for these two matrices and update the equation of softly selected adjacency matrix A, in Eq. (1) as follows,
add two
IR|+2 A Σ k=
A exp(Bxx)/
Σ
|R|+2 F= exp(3ar).
where At represents the k-th relation in the augmented set of relations including the original rela- tions in KG and two auxiliary relations. By merging nodes and removing edges, which correspond to learning large coefficients one of these two relations, we can obtain any graph structure from the complete graph whose nodes number is no less than the ground truth graph.
Given adjacency matrices consisting of the original adjacency matrices and two aux- iliary adjacency matrices: identity matrix and full-one matrix 1, we assume there are m. I m points constructing the complete graph, then for any logical rule Ap R,,RR, there exists suite of parameters { that make Eq. (1) equal to the number of (Zi...., Zx) that satisfies the logical rule.
Theorem 4.1
5

---

Under review as a conference paper at ICLR 2021
4.3 TRAINING ALGORITHM
For chain-like and tree-like rules, Eq. (1) can be efficiently computed with matrix and element- wise product (see Section 4.4). But for more general graph-like rules, Eq. (1) cannot be directly computed in such a compact way. Here, we introduce Einsum (see Appendix A for more details) make this possible. Einsum is a flexible convention of matrix calculation that unifies matrix multiplication, clement-wise multiplication and some more complex matrix/tensor calculation that cannot expressed by these ordinary operators (e.g., calculating the scores for graph-like rules). Specially, we express Eq. (2) in Einsum format as follows,
sr. s,((X,). Y) einsum (",,, ViVi ...., V2 Vn "x,,, "x,, A An. Uy)
(5)
where *(((()) Y) denotes the score of the pair ((X;), Y), ux and by are the one-hot vectors of the input and output entities.
Such a convention has two advantages: (i). we can uniformly represent all graph-like rules in matrix form; (ii). well-engineered libraries such as Numpy' and Pytorch2 can be exploited for fast computation (Daniel et al., 2018).
Finally, we need loss function that can not only encourage the positive samples but also can provide penalty for negative samples, which allows our model to be learn logical rules accurately. Thus, first calculate 8, (XX,,,, Y) = s, (.((,)))) Ev'ev s, ({X,), Y"),,"), i.c., the normalized score for each entity, then optimize the objective function composed by cross-entropy loss follows,
arg min (3,x} E((X)),) Evey-TTT -T-Y" (ogg(((((())))) Y"),
(6)
where I[-] is an indicator function, which returns if the statement is true and otherwise returns 0.
We optimize this loss, which is back nock-propagated through the calculation of Einsum, learn the parameters {35x} with high interpretability in an end-to-end differentiable manner. The training process is summarized in Algorithm 1.
Algorithm The training process of our model for logical inference.
Require: A set D of training data {{{x)) Repx Y)), KG, max nodes number á 2 fe. max_step; 1: initialize Bik, i = I,....,I,, n,, k = 1...., [R], step = 0;
2: while step max_step do
3: sample a mini-batch Death batch C D;
4: for each ((X,), Repx Y) Spatch do
5: update parameters [3ak] based on the loss function Eq. (6);
6: end for
7: step < step+11
8: end while
9: return logical rules A RG, nh S n S n.
Computational Complexity. Naturally, the search space of structural logical rules is very large and searching them is an NP-hard problem (Galárraga et al., 2015). Our method constructs a continuous space to estimate the logical rules optimize it in differentiable manner, which significantly reduces the complexity to [[D)]K+1) K+)), where | is the number of entities KG, is the number of free-variable nodes.
4.4 CASE STUDY: COMPARISON WITH EXISTING METHODS
We take three real-world cases in Figure to further show how our graph-like rules learning method generalizes previous Chain-/tree-likk one. To the best of our knowledge, our model the first that can infer the graph-like rules.
Chain-like rule. Left in Figure can be represented by s,(f_g),,Y cinsum j. kl. Ux, Attiend; Aupervisso, v.)). This will degenerate to the form of matrix multiplication (Yang et al.,
http:///wwooooooooooooooooooaooa http:///aabbeeeeeeeereeeee/////s generated//orchhhccoooo niuu htm1
httpp:://pptorchh.rr////o/ssss/ e/

---

Under review as a conference paper at ICLR 2021
2017; Sadeghian al., 2019) follows, (1X,), = Aypa where ex and vy are the one-hot vectors of the input entity and output entity.
Tree-like rule. Middle in Figure can be represented by s, () einsum( j.j. jk. kl, I', vx, PX,, Asudy als Asuuyy at, A Audiress of Uy). This will degenerate to the form of a combination of matrix multiplication and element-wise product. For example, the case in the middle of Figure as follows, s, ({Xx), Y uy Aaddress of [Aaudy xx ,,UX, A.Asmdy at ux ), where C denotes the element- wise product, ux, and ux, are one-hot vectors of two inputs, and vy is the one-hot vector of the tail. EQB (Hamilton et al., 2018) and Query 2box (Ren et al., 2020) require Y to be in the end of the logical rules and {2x} into a computational flow. Our method does not have requirements on the number of input nodes and the position of Y and {7x.).
the middle of logical rules, because they transform the logical rules
Graph-like rule. Right in Figure 1 can be represented by s,((X,): Y) = einsum( 'i, ij. ik, jk. jl, kl, ux: Arad- Aread Afrien: Aread (imv): Aread (iv):: vy). This cannot be simplified by only using addition/product. All the graph-like logical
combination of matrix anlliplication/elementtee rules can expressed by Einsum uniformly.
EXPERIMENTS
We conduct extensive experiments on real-world datasets to compare our performance on logical query (Task 3) in Section 5.2. Furthermore, we also demonstrate that our model is able infer the relations (Task 1) and learn the structural logical rules (Task 2) with high quality in Section 5.3 and Section 5.4.
5.1
EXPERIMENT SETUP
We implement our model in Python using Pytorch libraryand optimize all the models by Adam optimizer (Kingma & Ba, 2015).
Datasets. We
the Kinship, Family and Unified Medical Language System (UMLS) datasets (Kok & Domingos, 2007) to evaluate our model's ability to learn some representative log- ical rules for logical queries. Furthermore, we use Douban and Yelp evaluate our model's ability to learn complex graph-like logical rules for logical queries. We report more details in Section C.I.
Query Generation. We care- fully design five representa- tive query structures shown in Figure 2 including the right example in Figure 1, which do exist in real-world datasets.
(2c) 2-chain
(21) 2-intersection
(2iw) 2-intersection without Inout
triangle
(2eb) 2 with bridge
Figure 2: Five representative query structures.
We choose 2-chain (2c) because it is a basic chain rule, a comparison will help understand how our model works the most common cases. We choose 2-intersection (2i) because it is typical tree- like logical rule, while many of the existing works cannot handle it because most of them only allow one input are limited to chain-like rules. Only complex logical query methods (Ren et al., 2020) warreectioo-wihhutt---------
(2iw) because it is special type of tree-like logical rules, the positions of the output and free-variable node are very special. To test more complex graph-like rule, we choose a triangle (tri) structure, which cannot be modeled as chain/tree- rules. At last, we choose structure of chains with bridge (2cb) the same as the right case in Figure 1. All these query structures have corresponding realistic semantics. For query structure 2c, 2i, 2iw, we extract the top frequent query types (A_1) R.) and then follow the logic rules to randomly generate 1000 input-output pairs for each query structure. For query structure tri, we use the query type represented by "Who is X's friend and meanwhile has co-reading book with X?". For query structure 2cb, we use the query semantics "Which book has two common readers with the book X while the two readers are friends" as shown Figure 1. We split the datasets (queries) into training, validation, testing datasets according to the ratio 2 1 1. We use the training dataset for learning the parameters in our model, use the validation set to decide when to conduct early-stopping, and finally use the testing dataset for evaluating our model.
can tackle with this case. We choose

---

Under review as a conference paper at ICLR 2021
Comparing Methods. We compare method on logical query with series of rule mining meth- ods Neural-LP (Yang et al., 2017) and DRUM(Sadeghian et al., 2019) with high interpretability and the state-of-the-art embedding-basee based logical query method (Ren al., 2020) that handle tree-like logical rules. To fairly compare the expressive ability about logical rules, we remove the emhedding information and the corresponding neural network generating coefficients in rule mining baselines (Yang et al., 2017; Sadeghian et al., 2019), instead, we set the coefficients on relations as learnable parameters.
Evaluation Metrics We use Mean Reciprocal Rank (MRR) and Hit Rate at k (k = 1, 3) as evaluation metries (see Section C.2 for more details).
5.2 PERFORMANCE COMPARISON
Table 2: Performance comparison in terms of different query structures between different methods on three real-world datasets. The notation means the method in the row cannot be used for the query structure in the column.
2c Rate
2i
2iw
Dataset
Method
Hit
Hit Rate
Hit Rate
MRR
MRR
MRR
@3
@1
@3
@
@
@
Query2box
.20
.25
.17
.09
Neural-LP
.38
.38
.26
.43
.61
.19
Kinship
DRUM
.55
.59
44
.33
.45
.15
Ours
.63
.69
-52
.63
.81
.42
.53
.77
.24
Query2box
.13
.08
.07
.24
.28
.10
Neural-LP
.74
.82
.61
.28
.38
.06
UMLS
DRUM
.66
.65
.64
.18
.14
.04
Ours
.58
.43
.53
.21
.32
.48
Query2box 2box
.41
.56
.21
.23
.26
.00
Neural-L.P
.73
.86
.60
.67
.84
.45
Family
DRUM
.60
.87
Ours
.72
.85
.58
.67
.86
.47
.69
.88
.48
Table 3: Performance comparison of complex logical query on real- datasets.
tri
2cb
Dataset
Method
Hit
Rate
Hit Rate
MRR
MRR
@3
@
@3
@1
Neural-LP
1.00
.83
.61
.49
Douban
DRUM
1.00
1.00
1.00
.61
.65
.49
Ours
1.00
1.00
1.00
1.00
1.00
1.00
Neural-LP
.79
.90
.70
.74
.82
.92
Yclp
DRUM
.65
.62
.53
.64
.61
.58
Ours
.89
.85
.85
.94
.94
.94
We compare our model with other methods on three real-world datasets in terms of the three rela- tively simple but representative query structures (2c,21,2iw) shown in Table 2. Our method the only one that can tackle all these three query structures. We can observe that, for query structure 2c, Our model achieves better or comparable performance with Neural-LP and DRUM, because these two methods are specifically designed for chain-like rules. However, they cannot handle query structure 2i because they only allow single-input query. Furthermore, they cannot learn the 2iw correctly, because they require the output entity be in the end of chain rule. Their learned chain rules for 2iw are inaccurate or totally wrong, so our model improve the performance of 2iw query type with large margin compared to them. Query2box is designed for handling missing relations in complex queries, which performs poorly on these datasets. Furthermore, Query2box relies on the embeddings of entities it cannot handle unseen entities but ours can.
For more complex logic rules (tbi, we conduct the experiment on two real-world datasets in recommendation system domains, Douban and Yelp, whose information is reported in Table 6. The
8

---

Under review as a conference paper at ICLR 2021
performances of Neural-LP and DRUM are poor because their learned chain rules are far from the the graph-like rules as shown in Figure 3. Here, we do not compare with Query2box because cannot work on such graph-like logical rules.
The results reported in Table 3 show that our model has the best ability on learning such graph- like rules, which cannot be accurately modeled by methods for chain-like rules, such as Neural-LP
Method
Kinship
UMLS
Family
Douban
Yelp
Neural-LP
.76
.91
3.37
.85
.83
DRUM
.23
.43
1.65
.71
.71
or DRUM. As will discuss in Section 5.3, our model learns totally correct logical rules so it can achieve such good performance. The running time results are shown in Table 4, we can observe that our running time is comparable to Neural-L.P and DRUM.
Ours
.99
1.08
6.76
.76
.72
Table 4: Running times (mins) of our model and other models on different datasets.
5.3 CASE STUDY
Furthermore, we check whether the learned rules are the same ground-truth rules. As mentioned, we learn set of weights represented by { for different relations as- signed edges, while the 'merging' relation correspond- ing to matrix 1 means merging two connected nodes and the 'removing' relation corresponding to matrix I means moving the edge (no rule requirement). So we visualize Figure 3: The graph-like logical the weights representing the learned logic rules shown rules learned by our model. We in Figure 3. From that, we can observe that most of the rela- show the learned k-th relation (k tions are learned correctly with very high confidence, and it arg max; Bix) assigned on each i- learns high confidence for removing one edge (the auxiliary th edge with the highest confidence relation represented by full-one matrix), which means our exp(3w)) Σ exp(Bar)). Note that, model has the ability to both infer the relations and learn the full-one matrix, i.c., 1, removes the corresponding edge from the logical rule.
Turh
CastienCsttiteeee nowe)
madjen
2200
logic structures.
5.4 ABLATION STUDY
To demonstrate the effectiveness of auxiliary matrices I and 1, we conduct the experiments that we train the model with both matrices, one of them or none of them, respectively.
As shown in Table 5, we can observe that for case 2c, the Table 5: Performance comparison model with both matrices achieves the best performance, of hit@ 10 among the variants which suggests the effectiveness of these two matrices. For case 2i, the model with the matrix achieves the best perfor- mance because the model with 1 has the expressive ability to model the case 21, more matrices will lead to more parame- ters and difficulty for learning. Due to the same reason, for case 2iw, the model with the matrix and the model with both matrices achieve similar performance. For most complex cases, we need both auxiliary matrices accurately express the complex logical rules.
our method with or without matri-
ces and on Family dataset.
Variants
2i
2iw
none
0.08
0.69
0.20
only 1
0.43
0.94
0.58
only
0.31
0.77
0.50
both
0.89
0.86
0.58
CONCLUSION
We propose uniform to not only unify the existing logical query and inference works but also tackle more complex graph-like logical rules. Furthermore, we exploit Einsum to elegantly express this score function and optimize model in end-to-end differentiable manner, which can learn both the logic structure and the relations assigned on edges. At last, we conduct extensive experiments real-world datasets datasets to demonstrate the effectiveness of our model on logical query and show that our model can yield high-quality complex logical rules with interpretability.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Krister Ahlander. Einstein summation for multidimensional arrays. Computers Mathematics with Applications, 44(8-9): 4408-9):100--1117 2002.
Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives.
Dbpedia: A nucleus for web of open data. In The semanlic web, pp. 722-735. Springer, 2007.
Ivana Balažević, Carl Allen, and Timothy M Hospedales. Tucker: Tensor factorization for knowl- edge graph completion. arXiv preprint 1rXiv::90..0950000 2019.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collab- oratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247-1250, 2008
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems, pp. 2787-2795, 2013.
Yang Chen, Sean Goldberg, Daisy Zhe Wang, and Soumitra Siddharth Johri. Ontological pathfind- ing. In International Conference on Management of Data, pp. 835-846, 2016.
William W Cohen, Haitian Sun, R Alex Hofer, and Matthew Siegler. Scalable neural methods for reasoning with symbolic knowledge base. In International Conference on Learning Represen- tations, 2019.
G Daniel, Johnnie Gray, et al. opt cinsum-a python package for optimizing contraction order for einsum-like expressions. Journal of Open Source Software, 3(26):753, 2018
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. International Conference on Learning Representations, 2018.
Bhuwan Dhingra, Manzil Zaheer, Vidhisha Balachandran, Graham Neubig, Ruslan Salakhutdinov, and William W Cohen. Differentiable reasoning over a virtual knowledge base. In International Conference Learning Representations, 2020.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61: 1-64, 2018.
Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M Suchanek. Fast rule mining in on- tological knowledge bases with AMIE+. International Journal on Very Large Databases, 24(6); 707-730, 2015.
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries knowledge graphs. In Advances in Neural Information Processing Systems, pp. 2026- 2037, 2018.
Vinh Thinh Ho. Daria Stepanova, Mohamed Gad-Elrab, Evgeny Kharlamov, and Gerhard Weikum. Rule learning from knowledge graphs guided by embedding models. In International Semantic Web Conference, pp. 72-90. Springer, 2018.
Diederík Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International
Conference on Learning Representations, 2015.
Stanley Kok and Pedro Domingos. Learning the structure of markov logic networks. In International Conference on Machine Learning, pp. 441-4448 148, 2005.
Stanley Kok and Pedro Domingos. Statistical predicate invention. In International Conference on Machine Learning, pp. 440. 2007.
Robin Manhaeve, Sebastijan Dumancie, Angelika Kimmig, Thomas Demeester, and Lue De Raedt. Deepproblog: Neural probabilistic logic programming. In Advances Neural Information Pro- cessing Systems, pp. 3749-3759, 2018.
10

---

Under review as a conference paper at ICLR 2021
Pasquale Minervini, Matko Bosnjak. Tim Rocktäschel, and Sebastian Riedel. Towards neural theo- rem proving at scale. arXiv preprint Nakv::1807.082044 2018.
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktschel. Learning reasoning strategies end-to-end differentiable proving, 2020.
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. Advances Neural Information Processing Systems, pp. 7712-7722, 2019.
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2020.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 62(1-2): 107-136, 2006.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving, In Advances in Neural Information Processing Systems, pp. 3788-3800, 2017.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to- end differentiable rule mining knowledge graphs. In Advances in Neural Information Process- ing Systems, pp. 15321-15331, 2019.
Abiteboul Serge, Hull Richard, and Vianu Victor. Foundations of databases: the logical level, 1995.
Ehud Y Shapiro. Inductive inference of theories from facts. Yale University, Department of Com- puter Science, 1981.
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference Learning Representations, 2018.
Komal K. Teru, Etienne Denis, and William L. Hamilton. Inductive relation prediction by subgraph reasoning. arXiv: Learning, 2020.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. International Conference Machine Learning. 2016.
Po- Ro-Wei Wang, Daria Stepanova, Csaba Domokos, and Zico Kolter. Differentiable learning of numerical rules knowledge graphs. International Conference on Learning Representations, 2019.
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 564-573, 2017.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning, In Advances in Neural Information Processing Systems, pp. 2319-2328, 2017.
Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. In Interna- tional Conference on Learning Representations, 2020.
Wen Zhang. Bibek Paudel, Liang Wang, Jiaoyan Chen, Hai Zhu, Wei Zhang, Abraham Bernstein, and Huajun Chen. Iteratively learning embeddings and rules for knowledge graph reasoning. In The World Wide Web Conference, pp. 2366-2377, 2019a.
Yuyu Zhang, Xinshi Chen, Yuan Yang. Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Effi- cient probabilistic logic reasoning with graph neural networks. In International Conference on Learning Representations, 2019b.
11

---

Under review as a conference paper at ICLR 2021
A EINSUM
Einsum (Ahlander, 2002) is a mathematical notational convention that is elegant and convenient for expressing summation and multiplication vectors, matrices, and tensors. It can represent some calculation of multiple matrices that cannot be represented by matrix product or element-wise product. Specifically, not only makes the expression of complex logic rules very simple and elegant but also make the implementation of this calculation simpler and more efficient. Here, we introduce the implicit mode Einsum because it can tackle more cases than the classical one, and this function has been implemented in many widely-used libraries such as Numpy and Pytorch. It takes string representing the equation and series of tensors as input and provides a tensor as output. The rules of Einsum are as follows,
the input string is comma-separated including a series of labels, where each term separated by commas represent tensor (or matrix, vector) and each letter is corresponding to a dimension;
the terms in the string before "->" means input variables, and the term after " means output variables;
the same label in multiple inputs means element-wiss multiplication on the dimensions of differ- ent input tensors;
the dimensions that occur in the inputs but not in the outputs mean that dimension will be summed, while others will remain in the output. When there is no dimension after "->, it means all dimen- sions should be summed to get a scalar, and in such case " can be omitted.
Here we provide several simple examples to help understand:
einsum ("i, i + ; a. b) or einsum ('i, i", a, 6) represents the inner product of two vectors a bb; einsum ("ú,j + ij", a,, b) represents the outer product of two vectors ab?
einsum ('új, + i A, B) represents the element-wise product of two matrices A O B;
einsum ('ij, -> ik', A, B) represents the matrix product of two matrices AB.
B PROOF OF THEOREM 4.
Proof Here, we provide a strategy to construct the coefficients (3,r} which make Eq. (1) equal to the number of (Zi...., Zx) that satisfies the logical rule. First, without loss of generality, we assume that the ground-truth logical rules is N RV,V,, Vi)) including m free-variable nodes. Our strategy is divided into two stages: merging redundant nodes and removing useless edges.
m. we can set the coefficient of identity matrix of complete graph on all edges between node Zm, Zm+1..... Zin as 1, which means all of these edges are merged. And then for any Zj that j < m and Z that k >> m, we force the coefficient on the edge between Zj and Zg should be the same as the edge between Zj and Zt, i.e., the edge connected to these binding nodes should be the same. After the merging stage, we get a complete graph with nodes.
Stage 1: Merging redundant nodes. If
Stage 2: Removing useless edges. Then for any V and V if there is no edge between these two nodes, set the coefficient 'reooving' relation and others O. which means remove those edges from the logical rules. Finally, for R& RV,,, V/¹) in the ground-truth logical rule, we set the coefficient of the correct relation the corresponding edge 1 and others as 0.
After all these manipulations, we can get that
sy *(Xxiii = Σ
VI
IVI
Eull A&V, VD.
71=1
7K=1
where
A, = Σ ΣIR (xxp(Bit) / ===
exp(3xx)) A
k=1
becomes
,((X,,) Σ VI
Σ
II A.V. Vi.
(8)
7,=1
7x
12

---

Under review as a conference paper at ICLR 2021
where
A, Σ |R|+2
Em
exp((3x)/
/ Exmr exp(3ss)) Ak: k-=
|2|+2
kml
which means the Eq. (7) becomes the number of (Zi,..., Zx) that satisfies the logical rule, Note that, this is the only way construct the parameters to achieve this goal.
C EXPERIMENTS
C.I DATASET
The statistics of five real-world datasets are reported in Table 6.
Table 6: Datasets statistics for learning complex logical rules.
#Tiiplets
#Relations
# Entities |
Kinship
9587
25
104
UMLS
5960
46
135
Family
28356
12
3007
Douban
310
100
Yelp
283
100
C.2 EVALUATION METRICS.
For each query Repx ((X,) Y), we can calculate scores 8, for all entities by our model. We sort the entities in descending order of score and denote the rank of right entity Y as rank(Y). Then, for each entity we calculate MRR as follows,
MRR
Eixxtr rank(Y)
[Deeal
and Hit Rate at follows,
hit@k
E((x,))r)E [rank(YY) I k].
[Dessl
where I[-] is an indicator function, which returns if the statement is true and otherwise returns 0.
C.3 LINK PREDICTION
We conduct the experiment of link prediction on three datasets Kinship, UMLS and Family follow- ing the setting in Sadeghian et al. (2019). To be fair, we remove the embedding information in logical rule mining methods to purely compare the expressive ability about logic rules. We test all the methods for chain-like rules(Neural-LP (Yang et al., 2017), DRUM (Sadeghian et al., 2019) for more complex rule learning with only one input and one output, although they may learn inaccurate wrong rules. We further add GralL (Teru et al., 2020), the state-of-the of-the-an art method designed for inductive link prediction, as a bascline. As shown in Table 7, we can observe that our model achieves comparable performance compared with existing works.
Table Performance comparison of link prediction on three real-world datasets.
Kinship
UMLS
Family
Method
Hit Rate
Hit Rate
Hit Rate
MRR
MRR
MRR
10
@3
@
@
10
@3
@
@ 10
@3
@
DRUM
.52
.83
.60
.37
.80
.92
.83
.73
.71
.90
.84
.58
Grall.
.55
.85
.63
41
.72
.91
.83
.59
.85
.95
.92
.76
Ours
.55
.72
.44
.70
.65
.82
.84
.78
13


Reviews:
[{"review_id": "pHLDv1Et_yo", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper addresses the problem of logic structure learning, AKA, finding rules that generate a noisy knowledge graph. The innovation here is that the learning algorithm can address a much broader spectrum of rules than current methods. The key ingredient of the proposed method is a differentiable scoring function that models the rules.\n\n* I think the authors are making the problem unreasonably complicated formalism to express the scoring function. It would have been much easier to express their algorithm in higher order tensors for equations (1),(2),(3)\n* The A_i matrices they want to learn can be consolidated in a 3-dimensional tensor. Then what they need in order to obtain the s_r scoring function is a sumproduct over this tensor. In reality wha they are trying to learn is this huge but potentially sparse tensor. I would also like to point that from equation (3) it is implied that their algorithm cannot learn arbitrarily long recursive relations. Notice that in equation (3) each relation is used once only. For example, you cannot have A_3[Z1, Z2]A_3[Z2, Z3]....\n* Another limitation which I think is important is that it does not learn the negation. That is probably an easy fix, but I think it is worth mentioning.\n\n* The experiments are a bit limited in scope, but they are convincing. I realize that for the complexity of the algorithm it might be hard to scale to more datasets. I would have preferred if some timing results were reported too.\n\n* What I find odd is that the authors didn’t try to model the 3-dimensional tensor A with a deep network. It would have definitely helped them scale better. I am not sure how they would have implemented the merge and remove operator but this is worth investigating\n\nOverall I think the work is interesting and novel, but it is far from being practical for the moment. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gEVlglgEjUf", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "#### Summary\n\nThis paper proposes a differentiable model to learn \"graph-like\" (ie, more general than tree-like) logical rules over a knowledge base from example instances of the target relation. The key contributions are the generalization beyond tree-like rules, an Einsum expression notation, and an experimental evaluation.\n\n#### Strong and weak points\n\nI found Figure 1 and the associated running examples to be extremely helpful. The decomposition and definition of the three tasks was also very clear. On the other hand, I found the notation and presentation text of Definition 1 and Section 4.1 to be dense and confusing. The auxiliary removing and merging relations could also have benefitted from some more explanation like a diagram or worked example.\n\nThe key innovation (in my reading) is the use of the learnable $\\beta$ softmax parameters to determine which relations should be \"active\" in a given learned rule, as well as the normalized score objective which would penalize rules with many \"spurious\" groundings that satisfy the antecedent of the implication.\n\nThe significance or usefulness of graph-like rules could be established more convincingly. The Figure 1 running example seems a little contrived, and the experimental evaluation for these rules had to rely synthetic data. It would be helpful to identify important applications or research directions that would be unblocked by this work.\n\nExperimental results against strong baselines show comparable performance on simpler (chain and tree-like) rules, and much stronger results (as expected) on graph-like rules.\n\nThe actual mechanics of what gets computed and how are not very clear. The einsum notation is nice, but it is not rigorously shown why or how the operations cannot be expressed as matrix operations, or what actual computational graph PyTorch would generate under the hood to run learning and inference.\n\n#### Recommendation (accept or reject) with one or two key reasons \n\nI would argue to reject primarily on clarity and rigor concerns, and somewhat less so on significance of graph-like rules.\n\n#### Supporting arguments\n\nI think there are some potentially exciting contributions here in terms of the beta-softmax formulation and being able to handle graph-like rules. That said the core technical content could be developed more clearly, and underlying details about complexity and computation should be handled more carefully. Some more specificity around use cases or research directions for graph-like rule learning could also further strengthen the submission.\n\n#### Questions to clarify / additional evidence required\n\nWhy is the target relation called $R_{cpx}$ (ie, what does \"cpx\" mean)? This notation doesn't seem common in the related works.\n\n\"NP-hard problem\" is mentioned a few times but without citation or clarification. The \"Computational complexity\" Big-O term is given without explanation or justification, and furthermore it was not clear what $m$ meant. Also, is the differentiable training approach guaranteed to find global optima, or only local ones? Is there an approximation factor or rounding gap between solutions found by this approach and the ground truth combinatorial optimum solution?\n\nSection 4.1: minor typos \"evaluate the plausibility of a logical _rule_\" and \"_adjacency_ matrix\".\n\n\n#### Additional feedback to improve\n\nIt might be worth reviewing the literature in logical rules learning, eg, [Turning 30: New Ideas in Inductive Logic Programming](https://arxiv.org/pdf/2002.11002.pdf) might be relevant. Relatedly, I think the terminology of \"rule groundings\" and related ideas from [Markov Logic Networks](https://homes.cs.washington.edu/~pedrod/papers/mlj05.pdf) would probably be helpful here. This work also seems particulary related to [Learning the Structure of Markov Logic Networks](https://homes.cs.washington.edu/~pedrod/papers/mlc05a.pdf).\n\nIt would be helpful to at least mention the normalized score earlier in the paper when the intuition for rule scoring is introduced, as I was immediately curious why this wouldn't lead to rules which add \"easily satisfied\" free variables and edges in order to increase the score.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "bt7aBmeLx5q", "reviewer": "AnonReviewer1", "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 proposes techniques that generate logical rules out of knowledge graphs; the idea is to produce more complex rules than usual by exploiting a differentiable formulation of the associated learning process. This is a relevant theme as rule learning from knowledge graphs is important in practice due to its potential interpretability (as compared to black-box schemes based on embeddings). The solution is relatively simple to describe, with a score that leads to differentiable learning, and some needed insights to obtain useful results. The empirical testing seems fine and does indicate that the method is useful in practice.\n\nI must say that I was very interested in the \"Einstein sum notation\" but I could not quite see what it is and, more importantly, I could not see how this notation helps anything. Of course I understand that the authors do not have much space to explain details of this formalism, but some clarification would really help: I doubt that readers of ICLR papers will know this notation in detail. In fact, it would be nice to indicate how important this notation is in the whole system. \n\nOne question: looking at Figure 1 I see some questions on knowledge graphs and their possible answers, I cannot see exactly where are the \"rules\" there. \n\nOverall the text can be followed but it could be revised so as to be made more didactic; also there are some annoying typos that should be fixed. For example:\n- Abstract, line 6: \"observing [that] the\".\n- Introduction, line 8: \"ruleS\".\n- What is \"widely-existed graph-like logical rules\"?", "extra_scores": {}, "extra_text": {}}, {"review_id": "PjoMKkOKQ-N", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper aims to learn graph structured logical rules on knowledge graphs. It proposes three tasks, which I summarize as learning rule structure, instantiating a graph-structured rule (fill in a specific relation on the edge), and answering logical queries. However, many statements are entangled and mixed, the paper has many typos and inconsistency, making it hard to follow. I suggest the authors reformulate the tasks and the order or you can focus on one aspect/task and make it crystal clear.\n\nQuestions:\n- What is the difference between logic rules and logical queries? The paper abuses terms like “logical rules”, “logical queries”, “logical rules for query”, making it extremely hard to follow. Are you learning logical rules or answering logical queries? \n- According to the definition 1, figure 1 is not showing 3 logical rules but rather 3 logical formulas/queries, because there is no $R_{cpx}$.\n- I don't quite follow and agree with the statement “Note that, $R_{comp}$ can both be a relation that exists in the KG and the human-defined logic rule for a query, which tends to be more complex” I think $\\wedge_i^n R_i$ can be complex, no matter it is a chain, tree or graph, but $R_{cpx}$ should always be a concrete relation that exists on KG, otherwise it’s meaningless, because $R_{cpx}$ can simply represent anything. (I assume $R_{comp}$ is a typo and you mean $R_{cpx}$ here)\n- Here is another confusing statement “Note that, in previous works (Hamilton et al., 2018; Ren et al., 2020), the logical rule $R_{cpx} = \\wedge^n_i R_i$ is given”, according to your definition 1, shouldn’t the logical rule be $\\wedge^n_i R_i \\to R_{cpx}$? \n- What is the relationship between $e(v_i, v_i’)$ and $R_i(v_i, v_i’)$?\n- What is $G$ at the start of sec. 4.1, is it $G_e$ in section 2? There is also no $G$ anywhere in figure 1, you need to add some pointers.\n- “We denote the adjacent matrix of relation $R_i$ as $A_i$ , which is a soft choice among adjacent matrices $A_k$ corresponding to all relations in R.” Then which one is the adjacency matrix $A$ or $A$ bar? According to your statement, it is $A$, but according to Eq. 2, it is $A$ bar.\n- $\\beta_{ik}$ comes out of nowhere. Why do you want to have this new parameter and what is the motivation?\n- Why do you want to “by which we can use {$\\beta_{ik}$} as learnable parameters to learn which relation should be assigned on each edge given the logical structure.”? I think you already have instantiated the edges right? E.g., in the right case in Figure 1, you already know that some edges are “read” and some edges are “friend”.\n- The use of $S_r$ is not rigorous, for Eq. 3, it should be $s_r$({$X$},$Y)$ instead of $s_r(X,Y)$.\n- Why do you have $A_1$ to $A_5$ in Eq.3, but in the example, you only have 3 relations: “read”, “read(inv)”, “friend”.\n- In Sec. 4.3, it’s not “(1)”, “(2)”, but rather “Eq. (1)”, “Eq. (2)”\n- Add reference and citations to the statement in the Computation Complexity paragraph.\n- I did not find how the model answers logical queries (task 3) in the inference step, i.e., given a new $(${$X_j$}$,R_{cpx})$, how to find $Y$.\n- In the case study section, it only shows how the model deals with task 1, i.e., when the logical structure is given. Considering there are 3 tasks, it would be better if you can show examples for the other 2 tasks.\n- The datasets in the experiment section are small-scale and synthetic. What is the real-world application of the model? You claim that “For more complex rules, we generate a synthetic dataset because the real-world datasets are usually noisy.”, but isn’t the whole goal of the paper to model the real-world data and robust to noisy links?\n- What is the evaluation setup? Table 2 lists the performance of query answering, (task 3), where are the results for the other 2 tasks? Also, I assume DRUM/Neural-LP can only handle link prediction in the original paper, there lacks details how you improve DRUM to model complex queries.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While all reviewers see a lot of value in the paper, it cannot be accepted in its current form: too many issues with clarity. A more focused paper, with clear task and contributions is recommended.
The revisions and answers to reviewer questions are greatly appreciated and go a long way towards addressing these concerns for a future submission.
Decision: Reject