Learn to Explain Efficiently via Neural Logic Inductive Learning
Authors: Yuan Yang
Le Song
Venue:  (2020)
Keywords: inductive logic programming
interpretability
attention

Abstract: The capability of making interpretable and self-explanatory decisions is essential for developing responsible machine learning systems. In this work, we study the learning to explain the problem in the scope of inductive logic programming (ILP). We propose Neural Logic Inductive Learning (NLIL), an efficient differentiable ILP framework that learns first-order logic rules that can explain the patterns in the data. In experiments, compared with the state-of-the-art models, we find NLIL is able to search for rules that are x10 times longer while remaining x3 times faster. We also show that NLIL can scale to large image datasets, i.e. Visual Genome, with 1M entities.

Published as a conference paper at ICLR 2020
LEARN TO EXPLAIN EFFICIENTLY VIA NEURAL LOGIC INDUCTIVE LEARNING
Yuan Yang & Le Song
Georgia Institute of Technology
yyang75 gatech. edu, 1songlec. gatech. edu
ABSTRACT
The capability of making interpretable and self-explanatory decisions is essential for developing responsible machine learning systems. In this work, we study the learning to explain problem in the scope of inductive logic programming (II.P). We propose Neural Logic Inductive Learning (NLIL), an efficient differentiable ILP framework that learns first-order logic rules that can explain the patterns in the data. In experiments, compared with the fate-of-the--e methods, we find NLIL can search for rules that x x10 times longer while remaining x3 times faster. We also show that NLIL can scale to large image datasets, i.e. Visual Genome, with 1M entities.
INTRODUCTION
"An object that has wheels and windows is car"
Car
Off
Windowl
Wheel
Off
A Wheel
Wineel
Liround
"An object that inside the with clothing a person"
Person
Car
Insided
Toy
Or
On
Inside
Onl
A Clothing
Ground
Person
Clothing
Figure 1: A scene-graph can describe the relations of objects in an image. The NLIL can utilize this graph and explain the presence of objects Car and Person by learning the first-order logic rules that characterize the common sub-patterns in the graph. The explanation is globally consistent and can be interpreted as commonsense knowledge.
The recent years have witnessed the growing success of deep learning models wide range of applications. However, these models are also criticized for the lack of interpretability its behav- ior and decision making process (Lipton 2016 Mittelstadt et al. 2019), and for being data-hungry. The ability explain its decision essential for developing a responsible and robust decision sys- tem (Guidotti logic (FOL), are capable of discovering and representing knowledge explicit symbolic structure that can be understood and examined by human (Evans & Grefenstette 2018).
et al.) 2019). On the other hand, logic programming methods, in the form of first- frrst-order
In this paper, we investigate the learning to explain problem in the scope of inductive logic pro- gramming (ILP) which seeks to learn first-order logic rules that explain the data. Traditional ILP methods (Galárraga et al. 2015) rely on hard matching and discrete logic for rule search which is not tolerant for ambiguous and noisy data (Evans & Grefenstette 2018). A number of works are proposed for developing differentiable ILP models that combine the strength of neural and logic- based computation (Evans & Grefenstette 2018 Campero et al. 2018: Rocktäschel & Riedel 2017 Payani & Fekri 2019 Dong et al.] 2019). Methods such as ØILP (Evans Grefenstette (018) are referred as forward-chaining methods. It constructs rules using set of pre-detined templates and

---

Published as a conference paper at ICLR 2020
evaluates them by applying the rule on background data multiple times to deduce new facts that lie in the held-out set (related works available at Appendix (A). However, general ILP problem involves several steps that are NP-hard: (i) the rule search space grows exponentially in the length of the rule; (ii) assigning the logic variables to be shared by predicates grows exponentially in the number of ar- guments, which refer variable binding problem; (iii) the number of rule instantiations needed for formula evaluation grows exponentially in the size of data. To alleviate these complexities, most works have limited the search length to within 3 and resort to template-based variable assignments, limiting the expressiveness of the learned rules (detailed discussion available at Appendix BB. Still, most of the works are limited in small scale problems with less than 10 relations and 1K entities.
On the other hand, multi-ho hop reasoning methods (Guu et al. 2015 Lao & Cohen 2010; Lin et al.,
2013 Gardner & Mitchell| 2015; Das et al. 2016) are proposed for the knowledge base (KB) com- pletion task. Methods such as P Yang et al. (017) can answer the KB queries by searching for a relational path that leads from the subject to the object. These methods can interpreted in the ILP domain where the learned relational path is equivalent to chain-like first-order rule. Compared to the template-based counterparts, methods such as NeuralLP is highly efficient in variable binding and rule evaluation. However, they are limited in two aspects: (i) the chain-like like rules represent subset of the Horn clauses, and are limited in expressing complex rules such as those shown in Fig- ure [ (ii) the relational path is generated while conditioning learned rule is only valid for the current query. This makes it difficult to learn rules that are globally consistent in the KB, which is an important aspect of a good explanation.
the specific query, meaning that the
In this work, we propose Neural Logic Inductive Learning (NLIL), a differentiable ILP method that extends the multi-hop reasoning framework for general ILP problem. NLIL is highly efficient and expressive. We propose a divide-and-conquer strategy and decompose the search space into 3 subspaces in hierarchy, where each of them can be searched efficiently using attentions. This enables us to search for x 110 times longer rules while remaining x3 times faster than the state-of-the- art methods. We maintain the global consistency of rules by splitting the training into rule generation and rule evaluation phase, where the former is only conditioned on the predicate type that is shared globally.
And more importantly, we show that a scalable ILP method is widely applicable for model expla- nations in supervised learning scenario. We apply NLIL on Visual Genome (Krishna et al., 2016) dataset for learning explanations for 150 object classes over IM entities. We demonstrate that the learned rules, while maintaining the interpretability, have comparable predictive power as densely supervised models, and generalize well with less than 1 1% of the data.
PRELIMINARIES
Supervised learning typically involves learning classifiers that map an object from its input space to score between 0 and 1. How can one explain the outcome of classifier? Recent works on interpretability focus on generating heatmaps or attention that self-explains a classifier (Ribeiro)
al. 2016 Chen et al. 2018 Olah et al., 2018). We argue that more effective and human- intelligent explanation is through the description of the connection with other classifiers.
For example, consider an object detector with classifiers Person(X). Car(X), clcthing(X) and Ins (x XX') that detects if certain region contains person, car, clothing or is inside another region, respectively. To explain why a person is present, one can leverage its connection with other attributes, such as "X" is a person if it's inside car and wearing clothing", as shown in Figure [ This intuition draws a close connection to a longstanding problem of first-order logic literature, i.c. Inductive Logic Programming (ILP).
2.1 INDUCTIVE LOGIC PROGRAMMING
A typical first-order logic system consists of 3 components: entity, predicate and formula. En- tities are objects x E X. For example, for given image, a certain region is an entity x, and the set of all possible regions is X. Predicates are functions that map entities to 0 or 1, for example Person : x + 10, x E X. Classifiers can be seen as saft predicates. Predicates can take multiple arguments, e.g. Inside is a predicate with inputs. The number of arguments is ferred to as the arity. Atom is a predicate symbol applied to logic variable, e.g. Person(X) and inside( (X, X'). A logic variable such as X can be instantiated into any object in X.
2

---

Published as a conference paper at ICLR 2020
A first-order logic (FOL) formula is combination of atoms using logical operations {A, }} which correspond to logic and, or and not respectively. Given a set predicates P (PI..... Pk) ) we define the explanation of predicate Pk first-order logic entailment
X', S., Y2... Px(X,X) A(X, X', Y1, Y2...,
where (x(,,X)) is the head of the entailment, and it will become (X) it is a unary predicate. A is defined the rule body and is general formula, e.g. conjunction normal form (CNF), that made of atoms with predicate symbols from P and logic variables that are either head variables X, X' or one of the body variables y (Yr Yg....-
By using the logic variables, the explanation becomes transferrable as it represents the "lifted" knowledge that does not depend on the specific data. It can be easily interpreted. For example,
Person X) + Inside(X, Yi) A Car(Yi) A on X) A cl clothing(Y))
(2)
represents the knowledge that "if an object is inside the with clothing on it, then it's a person". To evaluate a formula on the actual data, one grounds the formula by instantiating all the variables into objects. For example, in Figure Eq is applied to the specific regions of image.
Given a relational knowledge base (KB) that consists a set of facts (x,, Pa, P(,x)) where P. E P and x,, x E X. The task of learning FOL rules in the form of [ that entail target predicate P E P is called inductive logic programming. For simplicity, we consider unary and binary predicates for the following contents, but this definition can be extended predicates with higher arity as well.
2.2 MUTLI-HOP REASONING
The ILP problem is closely related the multi-hop reasoning task on the knowledge graph (Guu
iet al., [015 Lao & Cohen 2010; Lin et al. 2015 Gardner & Mitchell 2015] Das et al. 2016). Similar to ILP, the task operates on KB that consists of set of predicates P. Here the facts are stored with respect the predicate Ps which is represented
binary matrix M, in (0, 1) ||
This is an adjacency matrix, meaning that (x,, PR. ) is in the KB if and only if the (i,j) entry of Mg is
p(3)
P(T)
Given a query q = (x, P", x'). The task find relational path the two query entities are connected. Formally, let vx be the one-hot encoding of object with dimension of ( Then, the (t)th hop of the reasoning along the path is represented as
x", such that
v()) = (t--()
Vx.
where (()) is the adjacency matrix of the predicate used in (t) hop. The v(1) is the path features vector, where the jth element vj counts the number of unique paths from x (Guu et al. 2015 After 7 steps of reasoning, the score of the query is computed
scorc(x, x') V II M
Vx-
t=1
For each g. the goal is to (i) find an appropriate T and (ii) for each E 11, find the appro- priate (d)) to multiply, such that (3. is maximized. These two discrete picks can he relaxed as learning the weighted sum of scores from all possible paths, and weighted of matrices each step. Let
K(S Sp)
II
c.k M
(4)
be the soft path selection function parameterized by (i) the path attention vector sy
(a( ...., 1 that softly picks the best path with length between to T that answers the query, and
(ii) the operator attention vectors S = (1) sp (TT,. where (t) softly picks the M at (t)th
step. Here omit the dependence on Mj for notation clarity. These two attentions are generated
with a model
S S. T(x:
(5)
3

---

Published as a conference paper at ICLR 2020
with learnable parameters w. For methods such as (Guu al. 2015 Lao & Cohen 2010), T(x; w)
a random walk sampler which generates one-hot vectors that simulate the random walk on the graph starting from And in NeuralLP (Yang et al., 2017). T(x; w) is RNN controller that generates sequence of normalized attention vectors with Vx as the initial input. Therefore, the objective is defined
arg max
Σ v S
(6)
Learning the relational path in the multi-hop reasoning can be interpreted as solving an ILP problem with chain-like FOL rules (Yang et al. 2017)
PM (x, X') + p (X, K)) A piz) Y2) A... pCD (Yn
Compared to the template-based ILP methods such as ØILP, this class of methods is efficient in rule exploration and evaluation. However, (P1) generating explanations for supervised models puts high demand on the rule expressiveness. The chain-like rule space is limited in its expressive power because it represents constrained subspace of the Horn clauses rule space. For example, Eq.(2) a Horn clause and is not chain-like. And the ability to efficiently search beyond the chain-like rule space is still lacking in these methods. On the other hand, (P2) the attention generator T(x; w) is dependent on x, the subject of a specific query g, meaning that the explanation generated for target P can vary from query to query. This makes difficult to learn FOL rules that are globally consistent in the KB.
3 NEURAL LOGIC INDUCTIVE LEARNING
In this section, we show the connection between the multi-hop reasoning methods with the general logic entailment defined in Eq. [.. Then we propose a hierarchical rule space to solve (PI), i.c. we extend the chain-like space for efficient learning of more expressive rules.
3.1 THE OPERATOR VIEW
In L. variables that only appear in the body are under existential quantifier. We can turn Eq.(T into Skolem normal form by replacing all variables under existential quantifier with functions with respect to X and X',
AX, X' P'(X.X' + A(X, ;1 (x (X')
the functions are known, Eq. will be much easier to evaluate than [q. Because grounding this formula only requires to instantiate the head variables, and the rest of the body variables are then determined by the deterministic functions.
Functions in Eq. 7 adopt the notions in section and treat each predicate as an operator, such that we have subspace of the functions T = {4p1, -.. fx where
be arbitrary. But what are the functions that one utilize? We propose to
(xx0= = M (v()))) = MAVx
if E U4 if E B,
where U and B are the sets of unary and binary predicates respectively. The operator of the unary predicate takes input and is parameterized with diagonal matrix. Intuitively, given subject entity x, PP returns the set embedding (Guu et al. 2015) that represents the object entities that, together with the subject, satisfy the predicate Pt. For example, let Vx be the one-hot encoding of an object in the image, then densside (Vxx) returns the objects that spatially contain the input box. For unary predicate such as Car(X), its operator spar M takes no input and returns the set of all objects labelled as car.
Since we only use 4, a subspace of the functions, the existential variables that can be represented by the operator calls, denoted as Di also form the subset 5 C y. This is slightly constrained from Eq. For example, in Person(X) from X. However, we argue that such rules are generally trivial. For example, it's not likely to infer "an image contains person" by simply checking if "there any car in the image".
Car(Y), Y can not be interpreted the operator call
4

---

Published as a conference paper at ICLR 2020
Therefore, any FOL formula that complies with Eq.77 now be converted into the operator form and vice versa. For example, 2) can be written as
Ferson(X) Car((Ptattdee A On(Fciothing)) X):
(8)
where the variable Y1 and Y2 are eliminated. Note that this conversion is not unique. For example, Car(( (X)) can be also written as Ins ie(,,, (Pao ()). The variable binding problem now
becomes equivalent to the path-finding problem in section 2.2 where one searches for the appropri-
ate chain of operator calls that can represent the variable in )
3.2
PRIMITIVE STATEMENTS
As discussed above, the Eq. is equivalent to a chain-like rule. We want to extend this notion and be able to represent more expressive rules. To do this, we introduce the notion of primitive statement v. Note that an atom is defined as a predicate sym- bol applied to specific logic variables. Similarly, define a predicate symbol applied to the head vari- ables or those in y as a primitive statement. For example, Eq. U1 Car(Finsiae and 1 = On(Fecothing 0. X)) are two primitive state- ments.
Even(X] Even(Yi) A (Yi, Y*) Succ (Y2, X)
Chain-llke
Ear(X] - Eye(Yi) A Of(Yi, Y-J A Of(X, Ys)
Tree-like
Of
Person[X)
CarlY:) A InsidelX, Yı) A OnlYs, Clothing(Ys)
Conjunctions
On
Ciothing
Similar to atom, each primitive statement is mapping from the input space to scalar confi- dence score, i.c. sb : R x R + s [0, 1]. Formally, for a unary primitive statement Pa( (0()) (x') and binary one (x( (000)) (T)) x (x')), their mappings
Inside
Factor graphs of example chain- like. tree-like and conjunctions of rules. Each rule type is the subset of the latter. Succ stands for successor.
Figure 2:
defined as
((MM 1)T DTIIE= M(())))
if E EU,
Uh (x,
(9)
((M2 Ie= M( TTT M('vz))
if E B,
where o(-) is the sigmoid function. Note that we give unary ei a dummy input x for notation convenience. For example, in
Ear(X) < Eye A of(Y,, Af
the body is single statement vp Of((pyy (), (oe Its value computed as war (Peye (Pr (Pr (Vx)))) (vx)) ((M Maye 1 vx Compared Eq. 1q. replaces the target Vx' into another relational path. This makes it possible to represent "correlations" between two variables, and the path that starts from the unary operator, e.g. (Dyy ). To see this, one can view a FOL rule as a factor graph with logic variables as the nodes and predicates as the potentials (Cohen al. 2017). And running the operator call essentially conducting the belief propagation over the graph in a fixed direction. As shown in Figure 2 primitive statement is capable of representing the tree-like factor graphs, which significantly improves the expressive power of the learned rules.
Similarly, (9. can be relaxed into weighted sums. In (6. all relational paths are summed with a single path attention vector Sg. We extend this notion by assigning separate vectors for each argument of the statement db. Let S.,. S E KxT be the path attention matrices for the first and second argument of statements V, i.e. Sp,s and s/g e are the path attention vectors of the first and second argument of the kth statement. Then we have
(M& 1)T (s((5), Spp) vze)) (M& K(S vx) (n(ss vsr)
if U,
4/a (x,x'''))=
(10)
if B.
3.3 LOGIC COMBINATION SPACE
By introducing the primitive statements, we are now one step away from representing the running example rule (8. which is the logic conjunction of two statements ti and 1/2- Specifically,
5

---

Published as a conference paper at ICLR 2020
M
MM
4
E9:30
22
Juman
2
Neg
Par
M
2
v/x
$y.tc Syae
S
Sp S
Sy S
$y.e S.p
Figure 3: A hierarchical rule space where the operator calls, statement evaluations and logic com- binations are all relaxed into the weight sums with respect to attentions S.p S.. S Sy, and s.- W/sm denotes the weighted sum, Matmul denotes the matrix product, Neg denotes soft logic not, and XEnt denotes the cross-entrope loss.
we want to further extend the rule search space by exploring the logic combinations of primitive statements, via (A, V, V,-}, shown in Figure 2 logic and operations
To do this, utilize the soft logic not and soft
1-1-22
p pAq-p*1
where p.g E [0.1]. Here we do not include the logic V operation because it can be implicitly represented as PV = -(-pA =q). Let v/ = (x,xxx)))) L be the set of primitive statements with all possible predicate symbols. We define the formula set at lth level
=
ド = F F== (XXx x)x fx(x, Sr. E F.
Fi-1)
(11)
where each element in the formula set ( E is called formula such that f A1 IR X1 ب define the logic combination space in similar way that in path-
[0, 1]. Intuitively, finding: the initial formula set contains only primitive statements V, because they are formulas by themselves. For the / 1th formula Fi-1, we concatenate with its logic negation, which yields Fi-1. Then each formula in the next level the logic and of two formulas from Fi Enumerating all possible combinations at each level is expensive, so we set up a memory limitation C' to indicate the maximum number of combinations each level can keep track of In other words, each level Fi to search for C logic and combinations on formulas from the previous level fi such that the cth formula at the Ith level fie. is
fie(x, x') = f1-1, x') # (x,1,, As an example, for
f-L, E Fi
(12)
(V1, and C = 2, one possible level sequence Fo (11, v2). Fi {t/1 * 2/2, (1 (-2) * 211). F2 {(r) th2) ((1 xh2) th 1/),... and etc. To collect the rules from all levels, the final level L is the union of previous sets, i.c. FL = Fo U... ....U. FL-1- Note that (1) does not explicitly forbid trivial rules such 1/1 (1 v/1) that is always true regardless of the input. This is alleviated by introducing nonexistent queries during the training (detailed discussion at section
Again, the rule selection can be parameterized into the weighted-sum form with respect to the at- tentions. We define the formula attention tensors Sy E R--1xCx2C such that fie is the product of two summations over the previous outputs weighted by attention vectors Sy.e and s'y respectively Formally, we have
fic(x,x)= -),o))x(_(((xxxxx// f
(13)
where (x, x') ) E R2C is the stacked outputs of all formulas f E Fi with arguments (x, x'). Finally, we want to select the best explanation and compute the score for each query. Let s, be the
IC' can vary from level to level, and keep it the same for notation simplicity
Formula set at (0)th level Fo actually contains 2K formulas. Here assume C K for notation simplicity.

---

Published as a conference paper at ICLR 2020
Sp Sp
Sy S
So
Transformer
xT
XL-1
"rransformar
0
foedforward
Seodforward
Transtormer
Spa
x2
Concat
4a
Qu
Transformer
Transformer
p(t-1)
Qg
Qy
Itarata
Concat
f
Concat
Maar
Persan
Hoor
Person
e,
Figure 4: The hierarchical Transformer networks for attention generation without conditioning on the query.
attention vector over FL. so the output score is defined score(x, x') s. fx,
(14)
An overview of the relaxed hierarchical rule space is illustrated in Figure 3
HIERARCHICAL TRANSFORMER NETWORKS FOR RULE GENERATION
We have defined hierarchical rule space as shown in Figure where the discrete selections on the operators, statements and logic combinations are all relaxed into the weight sums with respect to series of attention parameters S.,. S. . S Sy, S'y and s.. In this section, we solve (P2), i.c. we propose differentiable model that generates these attentions without conditioning on the specific query.
The goal of NLIL is to generate data-independent FOL rules. In other words, for each target pred- icate p* its rule set Fr. and the final output rule should remain unchanged for all the queries To do this, we define the learnable em- hh..., hx] E IR xd and the embeddings for the "dummy" arguments X and X' as ex, ex Rdd. We define the attention generation model as
q = Px, x') (which different from that in Eq. beddings of all predicates
H
S.. s Sy S,, S'y, s. T(ex, exx;
(15)
where h" is the embedding of P*, such that attentions only vary with respect to P*
As shown in Figure 4 we propose a stack of three Transformer (Vaswani al. 2017) networks for attention generator T. Each module is designed mimic the actual evaluation that could hap- pen during the operator call, primitive statement evaluation and formula computation respectively with neural networks and "dummy" embeddings. And the attention matrices generated during this simulated evaluation process are kept for evaluating Eq. (4). MultiHead is a standard Trans- former module such that MultiHeadAAtn Qexd Fudd
Ogxd Sax0 where d the latent dimension and v are the query and value dimensions respectively. It takes the query Q and input value (which will be internally transformed into keys and values), and returns the output value O and attention matrix S. Intuitively, S encodes the "compatibility" between query and the value, and O represents the "outcome" of query given its compatibility with the input.
Operator search: For target predicate P", we alter the embedding matrix H with h
h²)),
A [6,,.., hg]T.
such that the rule generation is predicate-speciffc. Let q be the learnable ith step operator query embedding. The operator transformer module is parameterized as
(t)
9 (0) = [exx ex
Q A C.p
(() ((() MultileedAAtt((.... V(--),,
(0)
MultilesdAAta(ql" ((D)..
& is the dummy input embedding representing the starting points of the paths. Cp is learnalle operator encoding such that Q, represents the embeddings of all operators क. Therefore,
Here, (0)

---

Published as a conference paper at ICLR 2020
Table MRR, Hits 10 and time (mins) KB comple- tion tasks.
Table 2: Statistics of benchmark KBs and Visual Genome scene-gee sene-graphs.
FB15K-237
WN18
KB
# facts
# entities
predicates
Model
MRR
Hits@ 10
Time
MRR
@its@ 10
Time
ES-10
17
10
ES-50
Neurall.F PP
0.24
36.2
250
0.94
94.5
54
ES-IK
1.5K
IK
TransF:
0.28
44.5
35
0.57
93.3
53
RotatE
0.34
52.6
342
0.94
95.5
254
WN18
106K
40K
18
FB1SK
272K
ISK
237
NLIL
0.25
32.4
82
0.95
94.6
12
VG
1.9M
1.4M
2100
we consider that ( encodes the outputs of the operator calls of predicates. And we aggregate (t)
the outputs with another MultiHeadAAttn with respect to single query q: which in turn yields the operator path attention vector 5 and aggregated output v
Primitive statement search: Let V d0 path attention is generated as
[vee Vo I be the output embedding of T paths. The
Q₂ = H + ev, Q -H+ V S MullHHeadAAunn( Vo,,
My S = MultiHHeadAAtn(( Qy Vi),
V FeedlForvard(Concll (V V.))
Here, Cÿ and cy are the first and second argument encodings, such that Q₂ and Q encode the arguments of each statement in V. The compatibility between paths and the arguments are computed with two MultiHeadAAtuus Finally, a FeedForward is used to aggregate the selections. Its output V E RK represents the results of all statement evaluations in V
Formula search: Let Qy,,; Y/, Rxdd be the learnable queries of the first and second argument of formulas Ith level, and let f.0 Vg. The formula attention is generated
fu1 = f4-1 + Ve-l V f.t: S
V J... Sya = MultiHeadAAttm Qy1 V fJ-1),, f.s Vz,)).
MantiHHeedAtt(((/.a f
V
Here, e.,, e- are the learnable embeddings, such that V f//- represents the positive and negative states of the formulas at (- 1th level. Similar the statement search, the compatibility between the logic and arguments and the previous formulas are computed with two MultiHHeadAttns. And the embeddings of formulas at Ith level 5. are aggregated by FoedForward. Finally, let qo be the leamable final output query and let V. [V Vy.--i). The output attention is computed as
Vo, S MultiHeadAAtt(qg Vo)-
STOCHASTIC TRAINING AND RULE VISUALIZATIONS
The training of NLIL consists of two phases: rule generation and rule evaluation. During gen- eration, we run (5) to obtain the attentions S,, S', S, and s, for all P's. For the evaluation phase, we sample mini-batch of queries {(x, P "x', y)x J and evaluate the formulas using Fq. 14). Here, is the query label indicating if the triplet exists in the KB or not. We sample nonexistent queries to prevent the model from learning trivial rules that always output In the experiments, these negative queries are sampled uniformly from the target query matrix M where the entry O. Then the objective becomes
1 Σ arg min 1
CrossEntropy s, (x)x))).
Since the attentions are generated from 15) differentiably, the loss is pack-propagated through the attentions into the Transformer networks for end-to-end training.
5.1 EXTRACTING EXPLICIT RULES
During training. the results from operator calls and logic combinations are averaged via attentions. For validation and testing, evaluate the model with the explicit FOL. rules extracted from the
8

---

Published as a conference paper at ICLR 2020
Time Per Eppchh Mins
NeuraILP
NLIL
0.5
RCNN
MLP
Model
ES-10
BS-50
ES-IK
200
Froq
NLIL
aIL
5.6
240
0.2
NeuralLP
0.1
0.1
0.2
100
NLIL
<0.1
<0.1
0.1
8 10
20
Longth
Data Portion %
(b)
(c)
Figure 5: (a) Time (mins) for solving Exen-and-SSccessee tasks. (-) indicates method runs out of time limit; (b) Running time for different rule lengths; (c) R @ for object classification with different training set size.
attentions. To do this, can view attention vector categorical distribution. For example, sp is such a distribution over random variables E [1, K]. And the weighted sum is the expectation over Mg. Therefore, 2018 Yang et al. 2017).
extract the explicit rules by sampling from the distributions (Kool et al.
However, since trated on one entity after convergence. We replace the sampling with the arg max, where we get the one-hot encoding of the entity with the largest probability mass.
interested in the best rules and the attentions usually become highly concen-
6 EXPERIMENTS
We first evaluate NLIL on classical ILP benchmarks and compare with state-of-the-ar KB completion methods in terms of their accuracy and efficiency. Then show NLIL is capable of learning FOL explanations for object classifiers on a large image dataset when scene- scene-graphs are present. Though each scene-graph corresponds to small KB, the total amount of the graphs makes it infeasible for all classical ILP methods. We show that NLII can overcome it via efficient stochastic training. Our implementation is available http:://ggthbb..om//bbacc//////u
6.1 CLASSICAL ILP BENCHMARKS
We evaluate NLIL together with two state-of-the-art differentiable ILP methods, i.e. Neu- ralLP (Yang et al. 2017) and OILP Evans & Grefenstette 2018). and two structure embedding methods, TransE (Bordes al. 2013) and RotatE (Sun et al. 2019). Detailed experiments setup available at Appendix
Benchmark datasets: (i) Even-and- -Sccanssssssoorrrrr (ES) benchmark is introduced in (Evans & Grefen- stette 2018) which involves two unary predicates Even(X), Zero and one binary predicate Succ X, ). The goal is to learn FOL rules over of integers. The benchmark is evaluated with 10, 50 and 1K consecutive integers starting at O; (ii) FB15K-237 is subset of the Freebase knowledge base (Toutanova & Chen 2013) containing general knowledge facts; (iii) WN18 (Bordes) et al. 2013) is the subset of WordNet containing relations between words. Statistics of datasets are provided in Table
Knowledge base completion: All models are evaluated on the KB completion task. The benchmark datasets are split into train/valid/test sets. The model tasked to predict the probability of a fact triplet (query) being present in the KB. We use Mean Reciprocal Ranks (MRR) and Hits @ 10 for evaluation metries (see Appendix C for details).
Results on free, we only show the wall clock time for completely solving the task. As we have previously mentioned, the forward-chaining method, i.c. ôILP scales exponentially in the number of facts and quickly becomes infeasible for IK entities. Thus, we skip its evaluation for other benchmarks.
benchmark are shown in Table 5a Since the benchmark is noise-
Compared to NeuralLP, NLIL yields Results FB 151332237 and WN18 are shown in Table. I
slightly higher scores. This is due to the benchmarks favor symmetriccasymmmetti positions of few relations (Sun et al.) 2219), such that most valuable rules will already lie within the chain-like search space Neural Thus the improvements gained from a larger search space with NIII limited. On the other hand, with the Transformer block and smaller model created
relations or com-

---

Published as a conference paper at ICLR 2020
for each target predicate, NLIL can achieve similar score at least 3 times faster. Compared to the structure embedding methods, NLIL is significantly outperformed by the current state-of-the-arm Le. RotatE, on FB15K. This is expected because NLIL searches over the symbolic space that is highly constrained. However, the learned rules are still reasonably predictive, as its performance is comparable that of TransE.
we demonstrate that NLIL can explore longer rules efficiently. We compare the wall clock time of NeuralLP and NLIL for performing one epoch of training against different maximum rule lengths. As shown in Figure 5b) NeuralLP searches over a chain-like rule space thus scales linearly with the length, while NLIL searches over a hierarchical space thus grows in log scale. The search time for length 32 in NLIL is similar to that for length 3 in NerualLP.
Scalability for long rules:
6.2 ILP ON VISUAL GENOME DATASET
The ability to perform ILP efficiently extends the applications of NLIL beyond canonical KB completion. For example in visual object detection and relation learning, supervised models can learn to generate a scene-graph (As shown in Figure [ for each image. It consists of nodes each labeled as an object class. And each pair of objects are connected with one type of relation. The scene-graph can then be represented FOL rules on such an output of supervised model is beneficial. As it provides an alternative way of interpreting model behaviors terms of its relations with other classifiers that are consistent across the dataset.
relational KB where one can perform ILP. Learning the
To show this, we conduct experiments on Visual Genome dataset (Krishna et al., 2016). The original dataset is highly noisy (Zellers et al. 2018), we use a pre-processed version available as the GQA dataset (Hudson & Manning. 2019). The gene-graphs are converted
collection KBs, and its statistics are shown in Table 2 We filter out the predicates with less than 1500 occurrences. The processed KBs contain 213 predicates. Then we perform ILP on learning the explanations for the top 150 objects in the dataset.
Quantitatively, we evaluate the learned rules on predicting the ob- ject class labels a held-out set in terms of their R@) and R@5. As none of the ILP works scale to this benchmark, we compare NLII with two supervised baselines: (i) MLP-RCNN: MLP clas- sifier with RCNN features of the object (available GQA dataset) input; and (ii) Freq: a frequency-
Table 3: R@I I and R@5 for 150 objects classification on VG.
Visual Genome
Model
baseline that predicts object label by looking at the mostly occurred object class in the re- lation that contains the target. This method is nontrivial. As noted in (Zellers et al., 2018), a large number of triples in Visual Genome are highly predictive by knowing only the relation type and either one of the objects or subjects.
R@
R@5
MLP+RCNN
0.53
0.81
Freq
0.40
0.44
NLIL
0.51
0.52
Explaining objects with rules: Results are shown in Table We see that the supervised method achieves the best scores, as it relies on highly informative visual features. On the other hand, NLIL achieves a comparable score on R@ solely relying on KBs with sparse binary labels. We note that NLIL outperforms Freq significantly. This means the FOL rules learned by NLIL are beyond the superficial correlations exhibited by the dataset. We verify this finding by showing the rules for top objects in Table 4
Induction for few-shot learning: Logic inductive learning is data-efficient and the learned rules are highly transferrable. To see this, we vary the size of the training set and compare the R@) scores for 3 methods. As shown in Figure 5c the NLIL maintains a similar @@ score with less than 1 1% of the training set.
7 CONCLUSION
In this work, we propose Neural Logic Inductive Learning, differentiable ILP framework that learss explanatory rules from data. We demonstrate that NLIL can scale to very large datasets while being able to search over complex and expressive rules. More importantly, show that scalable ILP method effective in explaining decisions of supervised models, which provides an alternative perspective for inspecting the decision process of machine learning systems.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
This project is partially supported by DARPA ASED program under FA8650-18-2-7882. We thank Ramesh Arvind and Hoon Na for implementing the MLP baseline.
REFERENCES
Ivana Balažević, Carl Allen, and Timothy M Hospedales. Tucker: Tensor factorization for knowl- 2019.
edge graph completion. arXiv preprint
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances neural information processing systems, pp. 2787-2795, 2013.
Andres Campero, Aldo Pareja, Tim Klinger, Josh Tenenbaum, and Sebastian Riedel. Logical rule induction and theory learning using neural theorem proving. arXiv preprint arXiv: Skii:/809.0299900 2018.
Xinlei Chen, Li-Jia Li, Li Fei-Fei, and Abhinav Gupta. Iterative visual reasoning beyond convolu- tions. Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp- 7239-7248, 2018.
William W Cohen, Fan Yang, and Kathryn Rivard Mazaitis. probabilistic DBs. July 2017.
TensorLog: Deep learning meets
Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. Chains of rea- soning over entities, relations, and text using recurrent neural networks. arXiv:1607.011266 2016.
arXiv preprint
Rajarshi Das. Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andrew McCallum. Go for walk and anrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. arXiv preprint 1rXiv:1711.05851, 2017.
Honghua Dong, Jiayuan Mao. Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In International Conference on Learning Representations, 2019. URL https::///// // openreview net. detorrmmid=BB11 xy-heetxxtttt
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61: 11:1-64,22 2018.
Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M Suchanek. Fast rule mining in onto- logical knowledge bases with amie+. The VLDB JournalThe International Journal on Very Large Data Bases, 2406))707-730, 2015. 2015.
Matt Gardner and Tom Mitchell. Efficient and expressive knowledge base completion using sub- graph feature extraction. In Proceedings of the 2015 Conference Empirical Methods in Natural Language Processing, pp. 1488-1498, 2015.
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. survey of methods for explaining black box models. ACM computing surveys (CSUR), 51(5))93, 2019.
Kelvin Guu, John Miller, and Percy Liang. Traversing knowledge graphs in vector space. arXiv preprint 1eX.vv1506.0100 2015.
Vinh Thinh Ho, Daria Stepanova, Mohamed Н Gad-EIrab, Evgeny Kharlamov, and Gerhard Weikum. Rule learning from knowledge graphs guided by embedding models. In International Semantic Web Conference, pp. 72-90. Springer, 2018.
'ramesharvind@ gatech.edteccu "hna30 "hna30@gatecc.cddn
11

---

Published as a conference paper at ICLR 2020
Drew A Hudson and Christopher D Manning. Gqa: A new dataset for real-world visual reasoning and compositional question answering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6700-6709, 2019.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv
preprint arXiv: 1803.0845, 2018.
Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, Michael Bernstein, and Li Fei-Fei. Visual Connecting language and vision using crowdsourced dense image annotations. 2016.
genome:
URL https:
org/ abs 160.. 07332
Ni Lao and William W Cohen. Relational retrieval using a combination of path-constrained random
walks. Machine learning, 81(1):53-67, 2010.
Nada Lavrac and Saso Dzeroski. Inductive logic programming. In WLP, pp. 146-160. Springer, 1994.
Yankai Lin, Zhiyuan Liu, Huanbo Luan, Maosong Sun, Siwei Rao, and Song Liu. Modeling relation paths for representation learning of knowledge bases. arXiv preprint 100.079500.00339, 2015.
Zachary C Lipton. The mythos of model interpretability. arXiv preprint arXiv: 2016.
Pasquale Minervini, Matko Bosnjak, Tim Rocktäschel, and Sebastian Riedel. Towards neural theo- rem proving at scale. arXiv preprint arXiv: 082044 2018.
Brent Mittelstadt, Chris Russell, and Sandra Wachter. Explaining explanations in ai. In Proceedings of the conference on fairness, accountability, and transparency, pp. 279-288. ACM, 2019.
Chris Olah, Arvind Satyanarayan. Ian Johnson, Shan Carter, Ludwig Schubert, Katherine Ye, and Alexander Mordvintsev. The building blocks of interpretability. Distill, 3(3) 2018.
Pouya Ghiasnezhad Omran, Kewen Wang, and Zhe Wang. Scalable rule learning via learning rep- resentation. In IJCAI, pp. 2149-2155, 2018.
Ali Payani and Faramarz Fekri. Inductive logic programming via differentiable deep neural logic networks. arXiv preprint 1906.0099033333333 2019,
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp.
ACM, 2016.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. Advances in Neural Information Processing Systems, pp. 3788-3800, 2017.
Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. Reasoning with neural tensor networks for knowledge base completion. In Advances in neural information processing systems, pp. 926-934, 2013.
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint
2019.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, pp. 57-66, 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances Neural Infor- mation Processing Systems, pp. 5998-6008, 2017.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances Neural Information Processing Systems, pp. 2319-2328, 2017.
Rowan Zellers, Mark Yatskar, Sam Thomson, and Yejin Choi. Neural motifs: Scene graph parsing with global context. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5831-5840, 2018
12

---

Published as a conference paper at ICLR 2020
A RELATED WORK
Inductive Logic Programming (ILP) is the task that seeks to summarize the underlying patterns shared in the data and express it set of logic programs (or rule/formulae) (Lavrac & Dzeroski 1994). Traditional II.P methods such as AMIE+ (Galárraga et al.) 2015) and RLvLR (Omran et al, 2018 relies on explicit search-based method for rule mining with various pruning techniques. These works can scale up to very large knowledge bases. However, the algorithm complexity grows expo- nentially in the size of the variables and predicates involved. The acquired rules are often restricted to Horn clauses with a maximum length of less than 3, limiting the expressiveness of the rules. On the other hand, compared to the differentiable approach, traditional methods make use of hard matching and discrete logic for rule search, which lacks the tolerance for ambiguous and noisy data.
The state-of-the the- differentiable forward-chaining methods focus on rule learning on predefined templates (Evans & Grefenstette] 2018 Campero et al. 22118) et al.) 2018). typically in the form of Horn clause with one head predicate and two body predicates with chain-like variables, i.e.
P" (' ((X,)) P,(XX)
To evaluate the rules, one starts with a background set of facts and repeatedly apply rules for every possible triple until new facts can be deduced. Then the deduced facts are compared with held- out ground-truth set. Rules that are learned in this approach are in first-order, i.e. data-independent and can be readily interpreted. However, the deducing phase can quickly become infeasible with a larger background set. Although ØILP (Evans & Grefenstette] (0188) has proposed to alleviate by performing only a fixed number of steps, works of this type could generally scale to KBs with less than 1K facts and 100 entities. On the other hand, differentiable backward-chaining methods such as NTP (Rocktäschel & Riedel, 2017) are more efficient rule evaluation. (Minervini et al.) 2018), NTP 2.0 can scale to larges KBs such as WordNet. However, FOL rules are searched with templates, so the expressiveness is still limited.
Another differentiable ILP method, i.c. Neural Logic Machine (NLM), is proposed in (Dong al, 2019). which learns to represent logic predicates with tensorized operations. NLM is capable of both deductive and inductive learning predicates with unknown arity. However, method, it also suffers from the scalability issue as ØIL. It involves a permutation operation over the tensors when performing logic deductions, making it difficult to scale to well-woldd KBs. On the other hand, the inductive rules learned by NLM are encoded by the network parameters implicitly, so it does support representing the rules with explicit predicate and logic variable symbols.
aaward--cainiin
Multi-hop reasoning: Multi-hop reasoning methods (Guu et al. 2015 I Lao & Cohen 2010 Lin
al. 2015 Gardner & Mitchell 20155) Das et al., [016]] Yang et al. (017)) such as NeuralLP (Yang
et al. 2017) construct rule on-the-lly when given a specific query. It adopts a flexible ILP setting: instead of pre-defining templates, assumes chain-like Horn clause can be constructed to answer
the query
Pd (X, + (X. A (Y, A.. P(T (Yn-1,
And each step of the reasoning in the chain can be efficiently represented by matrix multiplication. The resulting algorithm is highly scalable compared the forward-chaining counter-parts and can learn rules on large datasets such as FreeBase. However, this approach reasons over a single chain- like path, and the path is sampled by performing random walks that are independent on the task context (Das et al. (017)), limiting the rule expressiveness. On the other hand, the FOL rule is gen- erated while conditioning on the specific query, making difficult extract rules that are globally consistent.
Link prediction with relational embeddings: Besides multi-hop reasoning methods, number of works are proposed for KB completion using learnable embeddings for KB relations. For example, In (Bordes et al. 2013 Sun et al. 2019 Balažević et al.) 2019) it learns to map KB relations into vector space and predict links with scoring functions. NTN (Socher et al., 2013), on the other hand, parameterizes each relation into a neural network. In this approach, embeddings are used for predicting links directly, thus its prediction cannot be interpreted explicit FOL rules. This is different from that in NLIL, where predicate embeddings are used for generating data- indeeeddednn rules.
13

---

Published as a conference paper at ICLR 2020
Table 4: Example rules learned by NLIL
Person(() + Sbtxeettt()/AAaaaaanogoo22222223
Wearing(XX K2)]
Shirt(X) - 3ctpa/00heeeaaaoo////////////aa/
Sky(X)
- (g
+ Buup:(10--uuuuuddeo/ooooooooyya0
Sign(X) - otter:/eeeaaaaaaaaooooaoaaaaaaaa
x + http::/hh-oo..o..o.o.ooo/y/o/oan
didewa httpppeeeee..l.ooooooaaaaaoooo/d
Ear(X) + (1t0000-_BB211//0000000000000000
B CHALLENGES ILP
Standard ILP approaches are difficult and involve several procedures that have been proved to be NP-hard. The complexity comes from 3 levels: first, the search space for formula is vast. The body of the entailment can be arbitrarily long and the same predicate can appear multiple times with different variables, for example, the Inside predicate in Eq. appears twice. Most ILP works constrain the logic entailment to be Horn clause. i.e. the body of the entailment is flat conjunction over literals, and the length limited within 3 for large datasets.
Second, constructing formulas also involves assigning logic variables that are shared across different predicates, which refer to as variable binding. For example, in Eq. to express that person is inside the car, we use X and Y to represent the region of person and that of car, and the same two variables are used in ideide express their relations. Different bindings lead different mean- ings. For formula with n arguments (Eq.(2) (2) has 7), there are O(n²) possible assignments. Existing II.P works either resort to constructing formula from pre-defined templates (Evans Grefenstette 2018 Campero et al. 2018) from chain-like variable reference (Yang et al. 2017). 7, limiting the expressiveness the learned rules.
Finally, evaluating a formula candidate is expensive. A FOL rule is data-independent. To evaluate it, one needs to replace the variables with actual entities and compute its value. This is referred to grounding instantiation. Each variable used in formula can be grounded independently, meaning a formula with n variables can be instantiated into O(C") grounded formulas, where C' is the number of total entities. For example, (2) contains 3 logic variables: X, Y and Z. To evaluate this formula, one needs to instantiate these variables into C possible combinations, and check if the rule holds space is vast (c.g. all possible bounding boxes of an image) making the full evaluation infeasible. Many nawward-chaining methods such as UILP (Evans & Grefenstette 2018) scales exponentially in the size of the grounding space, thus are limited to small scale datasets with less than 10 predicates and IK entities.
in each case. However many domains. such as object detection, such grounding
C EXPERIMENTS
Baselines: For NeuralLP, the official implementation at here For ŌILP, the third- party implementation at here For TransE, we use the implementation at here For RotatE, we use the official implementation at here
14

---

Published as a conference paper at ICLR 2020
Table 5: Example low-accuracy rules learned by NLIL.
Bush(X) < -Iree(X)
<- + - A (ea (e)
B + P (LL
[ + A (it,(XXXX
Dirt(X) + Ground Near(Yi,
Model setting: For NLII,, create separate Transformer blocks for each target predicate. All experiments are conducted on a machine with i7-8700K, 32G RAM and one GTX We use the embedding size d 32. We use layers of multi-head attentions for each Transformer network. The number of attention heads are set to number of heads = 4 for encoder, and the first two layers of the decoder. The last layer of the decoder has one attention head to produce the final attention required for rule evaluation.
For KB completion task, we the number of operator calls T 2 and formula combinations L = 0, as most of the relations in those benchmarks can be recovered by symmerric/asymmerrii relations or compositions preferred. For FB15K-237, binary predicates unnecessary search overhead, we use the most frequent 20 predicates that share the same root domain (e.g. "award", "location") with the head predicate for rule body construction, which is similar treatment as in Yang et al. 2017). For VG dataset, we set T 3, L = 2 and 4.
a few relations (Sun al. 2019). Thus complex formulas are not grouped hierarchically into domains. To avoid
Evaluation metries: Following the conventions in (Yng al. 2017: Bordes et al. 2013)
Mean Reciprocal Ranks (MRR) and @its 10 for evaluation metrics. For each query (x, Px. x'), the model generates a ranking list over all possible groundings of predicate Pg. with other ground- truth triplets filtered out. Then MRR is the average of the reciprocal rank of the queries in their corresponding lists, and Hits@ 10 is the percentage of queries that are ranked within the top 10 in the list.
15


Reviews:
[{"review_id": "rkgAlxfAtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 presents a model for effectively hierarchically ‘searching’ through the space of (continuously relaxed) FOL formulas that explain the underlying dataset. The model presented employs a three-level architecture to produce logic entailment formulas, skolemized with a set of skolem functions, i.e. ‘operators’. The three-level search, which is implemented via a stack of transformers, first searches through a space of variable and predicate embeddings to select operators, after which it searches through the space of predicates to form primitive statements of predicates and operators, and finally it generates a number of formulas from the previously ‘selected’ primitive statements. The model is applied on a toy task to showcase its speed, a knowledge base completion task, and modeling the visual genome dataset, where the model shows the ability to induce meaningful rules that operate on visual inputs. The presented benefit of the model is scalability, ability to induce explainable rules, and the ability to induce full FOL rules.\n\nThe paper is well motivated from the explainability perspective and based on the evaluation does what it claims. The model is fairly elaborate, yet manages to be faster than the competing models. In general, I think the model itself is a welcome addition to the area of neuro-symbolic models, especially logic-inducing models, and that the evaluation done is appropriate (with a few caveats). However, my major critique of the paper is in its clarity.\nIn the current state, the paper is quite difficult to read, partially due to its density, partially due to its confusing presentation, notational issues and missing details. It would be difficult to reimplement the model just by reading the paper, which brings me to ask: will you be releasing the code?\nI would be willing to accept the paper if the authors improve the notation and presentation significantly. I’m enumerating issues that I found most confusing:\n\nResult presentation:\n- The figure captions are uninformative. In figure 1, one needs to understand what the graph is before reading the text at the end of the paper which explains what that is. It is not clear from the figure itself. Figure 2 presents the model, but it does not follow the notation from the main body of the paper.\n- Table 1 is missing SOTA models. TransE is definitely not one of the better models out there: check [2, 3, 4] for SOTA results which are significantly higher than the ones presented. I would not at all say that that invalidates the contribution of the paper, but readers should have a clear idea of how your model ranks against the top performing ones.\n- Please provide solving times for TransE, as it has to be by far the fastest method, given that it is super-simple.\n- Are provided times training or inference times (in each of the table/figure) because one gets mixed statements from the text?\n- In which units is time in Table 1?\n- Can you include partially correct or incorrect learned rules in Table 4? It would be great to get some understanding of what can go wrong, and if it does, what might be the cause.\n\nModel presentation and notation:\n- You mention negative sampling earlier in the text but then don’t mention how you do it\n- Notation below (6) is utterly confusing and lacking: what is s_{l,i}^(t), is there a softmax somewhere, what are numbers below ‘score’\n- What is the meaning of e_+ and e_- given that you omit details of negative sampling?\n- The notation does not differentiate between previous modules well so there’s V^(t-1) across modules, and it is not clear which one is used at the end --- last choice over V^(0) - V^(T) is over the LAST output, not the output from previous steps?\n- The notation in the text does not follow the notation in the figure (V_ps, V_\\phi)\n- Notation gets quite messy at some points, e.g. R^c^(0), is e_X and e_Y in H or not? Is H_b there too?\n- The differentiation of embedding symbols is not done well. H_b is an embedding for binary predicates, or a set of predicates? Does that mean that there is only a single embedding for a binary predicate and a single embedding for its operator (thought I thought that operators have an embedding, each)?\n- The explanation of what a transformer does is not particularly useful, the paper would benefit more from an intuitive explanation, such as that the transformer learns the ‘compatibility’ of predicates (query) and input variables (values), etc.\n- The ‘Formula generation’ subsection lacks the feel of fitting where it is right now, given that the notation in it is useful only in ‘Formula search’ paragraph. The other thing is that that subsection is wholly unclear: where do p and q come from, do they represent probabilities of predicates P and Q? How are they calculated? Does your construction imply that a search over the (p, q, a) space is sufficient to cover all possibilities of and/not combinations? In which case alpha is a vector of multiple values different for each f_s  in (5) or no? It is unclear \n- What is the relationship between alpha_0 and alpha_1, sum(alpha_0, alpha_1) = 1? Are alpha_0, and alpha_1 scalars, and how are they propagated in eq 5? Because if they’re just scalars, the continuous relaxation of formulas represented in (5) cannot cover all combinations of p, q, not and and. What is the shape of the alpha vector?\np and q are probabilities of what, predicates P and Q? How are they produced?\n- are \\phi functions pretrained?\n\nRelated work:\n- I do not condone putting it into the appendix, but I’m not taking it as a make-or-break issue.\n- It is notably missing an overview of symbolic ILP, and a short spiel on link prediction models (given that you compare your model to TransE, as a representative of these models)\n\nThe paper is riddled with typos and consistent grammatical errors. I would suggest re-checking it for errors. Examples include:\n- singular/plural noun-verb mismatches (rules..and does not change -> do, Methods ...achieves -> achieve)\n- Q_r^(t) - choice of left operands -> right\n- An one-hot -> a one-hot\n\n\nMinor issues:\n- The claim that the NeuralLP is the only model able to scale to large datasets is a bit too strong given [1]\n- You say “We could adopt” but you “do adopt”\n\nClarification questions:\n- Are 10 times longer rules of any use? Can you provide an example of such rules, a correct one and an incorrect one?\n- How many parameters does your model use? What are the hyperparameters used in training?\n- How big is T in your experiments, and why?\n- Why are queries only binary predicates?\n- How discrete do these rules get? You sample them during testing and evaluation, but are embeddings which encode them approximately one-hot, so that the (Gumbel-softmax) sampling produces the same rules all over again or are these rules fairly continuous and sampling is just a way to visualise them, but they are internally much more continuous?\n- Just to confirm, \\phi are learned, right? Given that they are parameterised with a predicate matrix, and that matrix is trainable?\n- Do you have a softmax on the output? It seems  f^*(T+1) should be a softmaxed value?\n- The rule generation generates a substantial number of rules, right? What might be the number of these rules? Does the evaluation propagate gradients through all of them or to a top-k of them?\n- Why is the formula in Eq.4 written the way it is. I assume it can be written differently, for example “Inside(\\phi_Identity(X), \\phi_Car())) and Inside(\\phi_Clothing(), \\phi_Identity(X))”. I do not understand why Clothing was treated as an operator and Car as a predicate, while treating Inside both as an operator and a predicate. Sure, nothing in the model forces it to consistently represent a formula in the same way always, but an example such as this one would need a good explanation why you chose it or at least mention that this is but one way to present it.\n- Why is Identity(X) used? Is it because you did not want to mix in variable embeddings during the primitive statement search?\n\n\n[1] Towards Neural Theorem Proving at Scale\n[2] Canonical Tensor Decomposition for Knowledge Base Completion\n[3] RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space\n[4] TuckER: Tensor Factorization for Knowledge Graph Completion", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Skl_EBtrtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 a novel architecture of integrating neural models with logic inference capabilities to achieve the goal of scalable predictions with explanatory decisions, which are of significant importance in the real deployment. In general, the article is well-written and nicely-structured with clear motivations, i.e., make the model predictions interpretable, make the logic rules differentiable, and make the algorithm scalable with longer rules and faster inference time. Both the methodology and experimental results make the idea promising and interesting. The contributions could be summarized in the following which make this piece of work worth of publication to my point of view:\n\n1. I like the idea of introducing the operator concepts to save much time in the variable binding problems in the common logic inference domain. \n\n2. The authors proposes a hierarchical attention mechanism to transform the rule composing problem into 3 stages with 3 different subspaces, namely operator composition, primitive statement composition and formula generation. This hierarchy structure solves the inductive problem efficiently by decomposing it into subproblems, which seems novel to me.\n\n3. The proposal of a general logic operator defined in eq5 is crucial for formula generation in a differentiable way. \n\nDespite the above contributions, there are a few limitations and questions to the author:\n\n1. The paper states that eq(5) is able to represent various logic operators with proper parameters. Can you provide some examples of how this general formula represent simple operators such as \"p \\vee q\"? It also mentions the case to avoid trivial expressions, but it's not clear how this is solved.\n\n2. For operator search, I assume \"e_X\" indicates the representation for the head entity, then what does \"e_Y\" represent? If each operator at most takes the head entity as input, where does \"e_Y\" come from? does the process for operator search repeat for each different operator indicated by \"e_\\phi\"? If this is the case, what's the effect of adding extra predicate embeddings \"H_b\"? Furthermore, the formula search is not clearly illustrated as of how eq(5) is softly picked using the defined process?\n\n3. Section 4.2 introduces a use case for end-to-end evaluation through relational knowledge base.However, it is unclear to me how those score functions and \"f_i^{(t)}\" contribute to the search model, i.e., how those formulas in section 4.2 map back to the search functions introduced earlier? This is crucial to understand the gradient backpropagation. And it could be better to provide an illustrative algorithm on generating the actual rules from the search modules.\n\n4. For the experimental section and related work, another existing work is missing, i.e., \"Neural Logic Machines\". More discussions and comparisons (experimental comparisons if possible) are helpful. A further question to ask is whether the proposed architecture could be used in the case when domain knowledge is not that explicit, e.g., the predicates are unknown or some of them are unknown? ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Bylt5yX0FS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 proposes to determine explanations for predictions using first-order logic (FOL). This requires being able to learn FOL rules. The authors propose to divide the search for FOL rules into 3 parts, each being hierarchical. The first level is a search for operator, followed by primitive statement search, followed by search for the Boolean formula. The authors also propose to implement logical variables that appear only in the body of the rule (and thus are existentially quantified) using skolem functions which reduces to a search operation and is an interesting idea which I haven't seen in recent works combining logic and neural networks. The paper then proposes a parameterized logical operator and describes their architecture for training these using attention and transformers.\n\nI found the paper to be very difficult to read. For instance,  Equation (5) doesn't mention parameters \\alpha on the RHS. I can't make out what the parameterization of the logical operator is. I can't also connect section 4 to the parameterized logical operator in section 3. Then Section 4.2 presents a score formulation (Equation 6) and refers the reader to the NeuralLP paper. This is not my favorite way to write a paper. So many indirections make it very difficult to appreciate the contributions. I hope the authors take this feedback and try re-writing their paper with the reader in mind.\n\nIs there a specific reason why Neural Logic Machines (Dong et al, ICLR 2019) is not referenced? It also claims to be more efficient than \\partial-ILP and to be able to learn rules. This is an important question. From what I can make out, not only should this paper cite Neural Logic Machines but they should in fact be comparing against it via experiments. It would also be helpful if the author present experiments against ILP systems (e.g. AMIE+). While ILP cannot deal with noisy labels, these full fledged systems do have some bells and whistles and it would be interesting to find out exactly what results they return. I couldn't make out exactly what the authors meant with this statement from the Appendix:\n\"The main drawback of NeuralLP is that the rule generation dependents on the specific query, i.e. it’s data-dependent. Thus making it difficult to extract FOL rules ...\"\nNeuralLP does learn FOL rules (of a particular form). I don't understand what the above statement means. I think the authors need to reference NeuralLP more carefully lest their statements come off as being too strong.\n\nTwo questions requiring further clarification:\n\n- Since your logical operator is parameterized, how do you take a learned operator and identify which logical operator it corresponds to? More generally, how do you derive the crisp rules shown in Table 4 in the appendix?\n\n- Since your network is fairly deep (e.g., I don't see a direct edge from the output layer to the operator learning layers in Fig 2), how do you ensure that gradients do not vanish? For instance, Neural Logic Machines use residual connections to (partially) address this. Is this not a problem for you?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a differentiable inductive logic programming method in the vein of recent work on the topic, with efficiency-focussed improvements. Thanks the very detailed comments and discussion with the reviewers, my view is that the paper is acceptable to ICLR. I am mindful of the reasons for reluctance from reviewer #3 — while these are not enough to reject the paper, I would strongly, *STRONGLY* advise the authors to consider adding a short section providing comparison to traditional ILP methods and NLM in their camera ready.
Decision: Accept (Poster)