Differentiable Logic Programming for Probabilistic Reasoning
Authors: Tuo Xu
Lei Zou
Venue: Submitted to ICLR 2023 (2023)
Keywords: Inductive Logic Programming
Differentiable Programming
Logic Rules

Abstract: This paper studies inductive logic programming for probabilistic reasoning. The key problems, i.e. learning rule structures and learning rule weights, have been extensively studied with traditional discrete searching methods as well as recent neural-based approaches. In this paper, we present a new approach called Differentiable Logic Programming (DLP), which provides a flexible framework for learning first-order logical rules for reasoning. We propose a continuous version of optimization problem for learning high-quality rules as a proxy and generalize rule learning and forward chaining algorithms in a differentiable manner, which enables us to efficiently learn rule structures and weights via gradient-based methods. Theoretical analysis and empirical results show effectiveness of our approach.

Under review as a conference paper at ICLR 2023
DIFFERENTIABLE LOGIC PROGRAMMING FOR PROBABILISTIC REASONING
Anonymous authors Paper under double-bling review
ABSTRACT
This paper studies inductive logic programming for probabilistic reasoning. The key problems, i.e. learning rule structures and learning rule weights, have been extensively studied with traditional discrete searching methods as well recent neural-based approaches. In this paper, we present new approach called Dif- ferentiable Logic Programming (DLP), which provides flexible framework for learning first-order logical rules for reasoning. We propose a continuous version of optimization problem for learning high-quality rules alize rule learning and forward chaining algorithms in a differentiable manner, which enables to efficiently learn rule structures and weights via gradient- based methods. Theoretical analysis and empirical results show effectiveness our ap- proach.
proxy and gener-
INTRODUCTION
Learning to reason and predict is a fundamental problem in the fields of machine learning. Repre- sentative efforts on this task include neural networks (NN) and inductive logic programming (ILP). The NNs and ILP methods represent learning strategies of two extremes: the ideas behind NNs to use fully differentiable real-valued parameters to perceive the patterns of data, while in the fields of ILP, we search for determined and discrete structures match the patterns of data. Over the years. the former approaches, i.e. neural- based methods, have achieved state-of-the-ar performance in solving tasks from many different fields, while the latter ones have fallen behind due to their inherited inferior in fitting noisy and probabilistic data.
However, was pointed out that there a debate over the problems of systematicity and explanabil- ity in connectionist models, as they are black-box models that are hard to be explained. To tackle the problem, numerous methods have been proposed combine the advantages of both connectionist and symbolic systems. Most existing efforts focus two different manners: using logic to en- hance neural networks and using neural networks to help logical reasoning. The former approaches (Rocktäschel & Riedel (017), Minervin
al. (2020c), Vedantam et al. (2019). Dong et al. (2019) modify the structures of NNs to capture some features of logic. Some of them, known as neural theorem provers (Rocktäschel & Riedel (007), Minervini et al.) (2020a)), represent entities with embedding vectors that implies the semantics of them. Further more, they absorb symbolic logical structures into the neural reasoning framework enhance the expressiveness of the models. For example, to prove the existence of (grandf ather, Q, Bart) where Q is the target entity we wish to find, these systems use logic rules such grandfathes + father-of, parent.oooo _of translate the original goal (grandf ather, Q, Bart) into subgoals that can be subsequently proved by operating on entity embeddings. Thus, the expressiveness and interpretability of the systems is improved with the help of logic.
The latter approaches (Yang et al. (017), Xiong al. (0117) Sadeghian al. 2019), Qu et al. (202T) enhance traditional inductive logic programming with the help of neural networks. Gen- erally, they use different techniques to solve the key problems of ILP, which is to learn structures of logical rules from exponential large space. Some of them (Yang et al. (2017). Sadeghian et al. 2019), Yang & Songl (2020) approximate the evaluation of all possible chain- logic rules in single model, making learning of the model differentiable. However,
mentioned in (Sadeghian iet al. (2019). these models inevitable give incorrect rules with high confidence values due to the low-rank approximation of evaluating exponential many logic rules the same time, which also

---

Under review as a conference paper at ICLR 2023
makes it hard to identify high- high-quality logic rules and explain the predictions made by these models. The other line of the research (Yang & Song (2020). Qu et al. (202I) propose different methods to generate higu-value rules such reinforce learning and EM algorithms. However, since structure learning of logical rules is a very hard problem, they are limited in only searching chain-like horn clauses, which is less expressive and general.
In this paper, we propose novel differentiable programming framework, called Differentiable Logic Programming (DLP), build a bridge between the ideas of differentiable programming and sym- bolic reasoning. Our approach enjoys the merits of connectionist systems, i.e., high expressiveness and easy to learn, as well as the merits of ILP systems, i.e., explanability and clear structures for decision making. We study the construction of probabilistic reasoming model, and discuss the properties of valuable logic rules. Based on that, we propose novel rule learning framework that approximates the combinatory search problem with continuous relaxation which enables us to learn structures of logic rules via differentiable program. Once valuable rules are learnt, we can further fine-tune the rule weights and perform probabilistic forward chaining to predict the existence of unobserved terms.
RELATED WORK
Our work is related to previous efforts on Inductive Logic Programming (ILP) fields and their exten- sions. Representative methods of ILP includes FOIL QQiinaan (2004)), MDIE (Muggleton) (209 ).
AMIE (Galárraga et al. (2015)), Inspire (Schüller & Kazmi 2018). ), RLvLR (Omran et al. (2018)
and so on. Generally, these methods search for logic rules in exponential large space to obtain valu- able logic rules and make predictions based on them. However, despite the well-designed searching algorithms and pruning techniques, these methods suffer from their inherent limitations of relying on discrete counting and predefined confidence.
More recently, different learning algorithms have been proposed to overcome the drawbacks of ordinary ILP methods. Many of them consider special kind of ILP tasks namely knowledge graph completion, where most of the proposed methods (Yang et al. | (0117). Rocktäschel & Riedel (2017). Sadeghian et al. (2019), MMinevvini al. (2020b), Yang & Song (2020), Qu al. (2021) focus on learning chain- like rules, and these methods use different learning strategies to learn valuable rules. Some of them are based on reinforcement learning (Xiong et al. (2017). Chen et al. (2018), Das al.)
(2018) Lin et al. (2018), Shen et al. (2018)), and they train agents to find the right reasoning paths to answer the questions in knowledge graphs. Qu al. (2021) uses recurrent neural networks as rule generators and train them with EM algorithms. Yang et al. (017)). (Sadeghian et al. (2019) and Yang Songl (2020) propose end-to-end differentiable methods, which can be trained efficiently with gradient-based optimizers. These methods are similar in spirit with our approach, as they claim to be able to learn rule structures in a differentiable manner. However, what they actually do is to find a low-rank tensor approximation for simultaneous execution of all possible rules of exponential space with different confidence scores, and by doing so they suffer from the risk of assigning wrong rules with high scores (Sadeghian et al. (2019)). Also, although Yang & Song (2020) claims that their attentions usually becomes highly concentrate after convergence, there is no theoretical guarantee so extracting logic rules implying these model could be problematic because there might be exponential potential rules that have confidence scores higher than zero. The parameters learnt by these models are dense vectors thus they suffer from the problem of explainability. Compared with them, our method is able to generate sparse solutions that explicitly learns logic rules for reasoning with a more flexible rule search space while keeping the rule learning procedure differentiable.
There are other methods that focus on different types of ILP problems. Lu (2022) treats relation prediction task as a decision making process, and they use reinforcement learning agents to select the right paths between heads and tails. Our approach is more general and is able to deal with different tasks. [Rockääschel & Riedel (2117) and MMinervini et al. (2020b) propose a generalized version of backward chaining with the help of neural embedding methods, and show great performance both relation prediction and knowledge graph completion tasks. Compared to them, our approach doesn't 't require the help of embeddings, thus our predictions more explainable.
There are also interesting methods based on embedding and neural networks (Bordes et al. (2013), Wang et al. (2014), Yang et al. (2015), Nickel et al. (2016), Trouillon et al. (2016), Cai & Wang
2

---

Under review as a conference paper at ICLR 2023
2018
Dettmers et al. 20118), Balazevic et al. (2019). Sun et al. (2019). Teru et al. 20200) Zhu
et al. 2021)). Since they are less relevant to logic reasoning, we do not cover them in details here.
3
PRELIMINARY
3.1
FIRST-ORDER LOGIC
This paper focuses on learning first-order logic (FOL) rules for reasoning. Across this paper, we assume predicates are from countable universe P where we use uppercase P. Q.... E P to repre- sent predicates. We use a, b, c.... E V to represent constants and æ, y. 2 to represent variables. example of grammars of FOL applied in the experiments of this paper are:
( = P(=) ((x, x)) By (v() p(x,y),
(I)
( y) = P(x, y) ((()) ppy)) (f y) 3z (lzz 2) A p(2) A p(z,)).
Grammars are critical for ILP systems, because they not only define the syntax of FOL formulas, but also determine the expressive power and search space of FOL formulas. However, in this paper we will not restrict the specific formulation of the grammar. Instead, we use common formulation represent them and our approach is equivalently applicable any reasonable grammar.
(x() P(x) (x(x) F2(x)) Fx
Also, Eq. [ frequently used to demonstrate the ideas in the following sections. We to represent a tuple variables, v for tuple of constants for notation simplification given it's clear in the context. F; represents possible format that yP could take. For example, in the definition of (x)) in Eq. we have x = x and F1 (x) = sp v), F2(x) = By (v)) A y).
Logic classifiers and logic rules Logic formulas y can be regarded as classifiers (Barceló et al. 20200). For example, consider (xx) := By Red(y) A Edge(æ, y) and Blue(x) + <p(x). &p can be regarded as a classifier, where we have (pxx) = 1 for nodes æ with red neighbors and otherwise. Generally, logic classifiers take (set of) entities (c.g. node 2)) input and compute the output (e.g. ((()) by grounding the logic formula on the background statements (c.g. (Edge(x, y). Red(y) Blue(z) ((x) is logic rule that tells the rule head Blue(z) be concluded if the rule body (xx) is satisfied. In the fields of probabilistic reasoning, each logic rule can be assigned with weight indicating the degree of certainty of the rule.
Forward chaining and backward chaining Forward chaining methods are critical in automated deduction, as they enable us repeatedly deduce new lemmas from known theorems. Forward chaining starts from known conditions and logic rules, and move forward towards conclusion by applying the logic rules. Then, they absorb the deduced conclusions into known conditions and apply the rules again until there are further new conclusions deduced. Backward chaining methods the opposite of forward chaining, as they move backwards from the conclusions to the potential conditions implied by the rules.
3.2 PROBLEM STATEMENT
This paper studies probabilistic inductive logic programming. The input data is tuple (SB, Sp, SN) where Sp, SN are sets ground atoms of the form (Pi(v1). P:(2)) (V(2).....) Sg is a set of back- ground assumptions, Sp is set of positive instances, and SN set of negative instances. The target to construct a model so that when applied to Sg, it produces the positive conclusions in Sp, well rejecting the negative instances in Sy. This naturally leads to the following problems:
Rule Mining. Our model is based logic rules, and one key problem is finding useful rules that produce the results in Sp when grounded on Sg.
Probabilistic Reasoning. It is often infeasible to directly perform forward chaining with logic rules when input data is noisy. A rule-based inference model p(Q(x) E Sp(Ss) is needed to take the uncertainty of logic rules into account.

---

Under review as a conference paper at ICLR 2023
Edge
Blse
Red
(y(oa))
(g(a.ar)
inve
gif4)
Gx)
Edge
M9,
invE
Edle
(4Droy)
Bdge
ioVE
invE
Figure 1: Illustration of logic classifiers (left) and DLP framework (middle, right). The target rule is Blue(z) 6 Jy: Red(y) A Edge(x, y). In the left figure, (1 directly captures the target rule. In the middle figure, the model is constructed by extending the unary node t (æ) with tree structure.
In the right figure, the model is constructed by stacking multiple layers. (see Sec. 4.2 for detailed description). Both these structures constructed with the grammar in Eq. d learns to identify the target logic rule via gradient descent and converges at the correct (colored as blue) reasoning paths.
4 MODEL
In this section, we introduce our proposed Differentiable Logic Programming (DLP) framework. The general idea is use differentiable programs solve the problems of rule mining and learning the prediction model.
As mentioned in Sec. the learning problems require from discrete space and assign feasible weights to them. In this paper, we introduce differentiable module called Logic Perceptron (LP) to help deal with the problem. Given a grammar of logic classifiers we provide a method to construct corresponding LPs 36 that is able to capture any with limited size. The LPs are stacked as a network to capture more complex logic classifiers as well as being end-to-end differentiable. We further propose new optimization problem whose solutions are sparse so that each local optimal of it corresponds to the symbolic structure of logie rule being revealed. Moreover, these learnt LPs are organized into a prediction model that generalizes forward chaining and can be learnt by maximizing the likelihood. Both these optimization problems are continuous and differentiable w.r.t. parameters, which makes them can be solved via gradient-based methods. Figure presents brief illustration general ideas behind our model. Next, we introduce the details of our approach.
identify important logic classifiers
4.1 OVERVIEW
In this section first introduce the general ideas behind approach, well highlighting the key challenges in our learning framework. The details of model implementation are discussed the next sections. We start with an example which illustrates the general ideas of probabilistic reasoning as well as providing the intuitions and motivations behind our approach.
Example 4.1 (Human Reasoning). Consider the query "Are a and friends?". In this case, we may first ask "Do and know each other?" which corresponds to a logical classifier (pr (a, b) = Know (a, b). If u (a, b) 1, our confidence in and y being friends is increased, and we call this 42 proved Q, also Q the target predicate of Pi, denoted as Q + 9p With the answer of 41, one may continue to ask 62: "Do a and live in the same town?" ... where each evaluation of sp serves as an evidence that proves the existence of Q.
have (xx) Friend( (, b). To answer the query,
In the example, we use different logic classifiers to prove the query from different aspects, and all the classifiers used are highly relevant to the target predicate Friend. This makes sense because our belief in x and y being friends is higher when we realize they know each other, which corresponds to relative high value of ((Friend y) [Knowzz (z, 3) 1), but irrelevant facts such "they both drink water" won't 't help. fact, this simple example illustrates the overall ideas our model, formally described as follows.
4

---

Under review as a conference paper at ICLR 2023
Proposition 4.2 (Properties of Φ). Given the input data (Sp. SN), let Q be d-ary target
predicate. ΦQ = (pu. P1.....,...-............... IPL-1} be a set of logic classifiers and Po E (0, 1] a fixed thresh-
old. With the following statements being satisfied: (1) We start from 1 = 0 and let Sp (0) Sp:
ΣxEVd (x( Qc0espp1
(2) For Pt its precision: p(Q(x) Sp Sp =) Exeve vp(xx) aqoeespuus
Poi (3)
We let Sp 1p(1+)) Sp (1((x)) x E VA -x(x = I and increase 1 by 1 and go to (2)
again until I.; (4) Sp (4) 0. Then, there exists prediction model p(Q(xx) Sp(Ss)
(x)), (L-1(x)) such that its error rate satisfies:
(1 (1-Pol (L-oo)No
Err (S: Sx)! S
< Po.
Po
where No = Exevs QQ()SS and N Exeva LQ(xESSUUSX
Prop. 4.2 implies how we learn such logic classifiers for proving Q. Generally our rule learning procedure can be seen variant of boosting method where each rule regarded as a weak clas- sifier, but we focus on the rule precision rather than misclassification rate. This is because (I) in most situations the input data very sparse that one can obtain a small misclassification rate by simply always predicting false, and (2) often a single logic rule is only able to prove relative small portion of the positive instances and large number of logic rules are often needed to make complete predictions of the target predicates. Thus, our learning procedure is formally described as follows.
Rule Learning Framework Given the input data (SB, Sp, SAr), suppose for each target predicate Q E P. We first start with an empty rule set @Q = 0 for each Q, and assign each instance Q(v) in Sp and SN with weight "Q(v)) = (This corresponds the statement (1) in Prop [4.2). Then, we perform the follow steps recursively: we first find a logic classifier yp having high precision on the weighted data, i.e.
learn L rules
ExEre 1Q(x)SS wQ(x) sx(x)
max p(Q(x)= E Splp(x)=pp1) =1) Exeva 1Q(x)ESpUS WQ(x) p(x)
(4)
This generalizes the statement (2) in Prop. 4.2 We add into de. Then, we evaluate on SB.
and for instances v where <fvv = 1, if (v) E Sp, we let WQ(v) + TI WQux); if Q(v) E Sy. we let (iq(v) <- T2 WQ'v), where TI, 72 E [0, +00) are fixed values. Note that this step generalizes statement (3) in Prop. 4.2 and statement (3) is special case of the above step where we let 0,r2_1. This procedure is then repeated for T. times
Now we have introduced the overall learning framework of our approach except two problems: how we identify high-precision logic classifiers (Eq. 4 and how we learn the prediction model pxQ(x) Sp|SB). In this paper, we propose differentiable model to solve these problems. In the next sections we discuss the implementation of our model in details. In Sec. [.2] we introduce logic perceptrons (LP) building blocks of our model well as how stack them together to express more complex logic classifiers. In Sec. 4.3 we introduce how use LPs to perform probabilistic reasoning. Then, we present our methods for learning the model in Sec. 4.4
4.2 LOGIC PERCEPTRONS
A Logic Perceptron (LP) is a differentiable model that generalizes the ordinary logic classifiers into continuous space. Given the grammar logic classifiers:
(xx) = A(x) F (x)
(x Fx(x) ... Fx(x).
(5)
We provide two methods for constructing corresponding LPs given the grammar 5 which are tree- structured LPs (LP-tree) and ltyerrstructured LPs (Ly--ayer). The main difference is that LP-tree strictly satisfies the constraints discussed in Sec. 4.4 while LP-layer is more compressed. As will be shown in Sec. 5 they produce similar results in the experiments.
5

---

Under review as a conference paper at ICLR 2023
LP-tree
We first define the correspondence between LPs v and logic classifiers yp follows.
(xx; a) = [
w",
K w 1, wi 2 0 for i = 1.2...KK
(6)
s.t.
where R is attention vector, of the model. The functionalities of a are discussed in Sec. 4.44, and often in experiments we set 1. w" is element-wiss exponent applied to w. The evaluation of each Fi ax) in Eq. 6 is corresponded to each (x(x) in Eq. 5. where we define
R is a hyperparameter that helps to keep the sparsity
(x)x) (x) A (x
- F((x:a) (((
- a((:a)= = (F)xx)))) (w
(xxx == (x V (x((x)
(x) == FF)())
- -((x;a) = (x(x;),,
(x) By (x,
= F((x:a)= = F(xx.)))))
Fx = (x)
F(x.y;a) = F)(x:
- a(x:a)= = (P((x), P2(x), PIo, [(x]] (w())²
Fx(x) == (xx)
(6) 1 and u 0. T is a pointer to another LP, We exclude where for each (x) we have Ej 3 the universal quantifier's because this can be equivalently expressed by -
To construct more complex and expressive LPs, we can generate arbitrary numbers of LPs within tree structure. Initially, we create a tho as a root node. As shown in Eq. 7 the evaluation of tho requires its pointers J to be explicitly assigned, so we create a new LP for each pointer & of e/o to be a child of thy The same procedure is performed on the leaf nodes of the tree for arbitrary times while expanding the depth of the tree. Once we reached the desired depth, we simply assign empty nodes as vp for the leaf nodes to terminate the construction procedure. These LPs compose a L.P-tree where the serves the output of the tree. Figure illustrates this procedure.
LP-layer Generally layer structured LPs are similar with tree structured LPs except that now we stack multiple LPs linearly as layers. Suppose for LP-layer we have total number of L LPs (15(1, v5(2) ...., v)(1)). The evaluation of each LP is exactly the same in Eq. and 7 except that for each LP 25(() in LP-layer we have
(x p(x)
F((x:) PXx) (x; G (x;a) (1)))
(8)
thus (0() is able access the layers before PI, Pa...., 2b(1), 10-1) and the LPs are organized as layers illustrated in Fig. where (L(z)) serves as the output of the layers. An advantage of LP- layer is that it's very simple to extend the model: we only need to stack more layers. The following
proposition states the expressiveness of these two construction approaches.
Proposition 4.3 (Expressiveness of LP-tree and LP-layer). Given a grammar of logic classifiers of the form in Eq. 5 suppose a logic classifier is construcied by recursively applying the grammar for > 0 times, then we have:
(1) In worst cases LP-tree with O(KN) LPs express yù;
(2) LP-layer with N LPs can express yp
4.3 INFERENCE
We now discuss how infer pxQ(x) E Sp Sp|S)) for every by generalizing forward chaining. In this section, we assume we have learnt set of V = {wi, th...... } for every Q E P, and the goal is infer the (unknown) positive negative instances in Sp, Sy. For each predicate Q P and every x, we let (())(x 1 if (x) E Sz and Q(") (x) 0 otherwise. Then, at iteration we:
(1) Evaluate I.ss: We evaluate every 1 V on ((t-1) at every Vdl This procedure costs

---

Under review as a conference paper at ICLR 2023
R (IP) + N)N) where N is the size of the network, d is the maximum arity of predicates and LPs when evaluating v. Ry is the amount of rules, i.e., the total size of u for each Q. (2) Update inferences: We update inferences about Q(x) for each Q P and This procedure costs O()))R)))
(xx) = sigmoid (Update (f E val)),
(x) max{(((x, Q("
where Update is the function that specifies how we update the predictions based on the groundings of the Vo- The common implementation of the update function used in this paper is
Update (x))( E voo)
Σ voEWo
Weer Nx(x),
(10)
but any differentiable update functions (MLP, etc.) is also applicable. After T rounds of iterations, directly pick the values of ()T((x) approximation of p(Q(x) Sp(SB), while p pxQ(xx Sx((BB) = 1 p(Q(x) E Sp SB).
Also, the time complexities provided here rather loose. In reality, input data is often very sparse, and turns out that the [V]" term in the time complexities can be significantly reduced. See appendix for more discussion.
4.4 LEARNING
In this section, we discuss how we solve the two problems stated in Sec. 3 i.c., mining logic rules and learning the probabilistic prediction model.
Learning Symbolic Structures via Continuous Optimization structures of logic classifiers, i.e., to solve the problem
We now discuss how we learn the
max <p
p(Q(x)= Splp(x) =
(11)
Theorem 4.4 (Sparse attentions). Consider the optimization problem
min ((v) = log E Ex [v(x; a:] + log E (bxx; 3)},
(12)
where (x(;; a) and (xx;; 8) are obtained by iteration of the inference procedure. Here, assume Ex (x; ] > O and Ex-paly (x(;;; 3)] > O. With the following constraints being satisfied: (1) > B 1; (2) vp is the root of a LP-tree; (3) Negations are applied only on leaf nodes. Then, at each local minima of L(v), the attention vectors w. w() used for evaluating eú
oot vectors and 1a explicitly captures logic classifier.
We say db captures a logic classifier &p when evaluated on any background assumption Sg, ex(x) > 0 xxx) = 1 for any x. With the above theorem, we can directly derive the following corollary.
Corollary 4.5 (Proxy problem). Minimization of the optimization problem
min 2
L(1b) = - log ax) E Sp] + log E (xb(x; ()) E Sw),
(13)
yields a near-optimal solution for solving problem 17 with the constraints of theorem 4.4 being
satisfied.
We say the solution is near-optimal because (1) the LPs are only capable capture the logic clas- sifiers within their expressiveness power, and (2) the ranges of yp and t are different: we have xp(x) E 10 and (xx;; a:) E [0, +oc). For example, if we have (xx) = By Neighbor(a, y). then the corresponding vx(x) is equal to the amount of neighbors that æ have. Also, the 3 constraints are sufficient conditions for the optimization problem to guarantee to converge at the points where s captures logic classifier, but they are not always necessary. In most cases we can relax these constraints and set a = B = 1 while keeping the sparsity of the solutions, which is shown in the experiments. The LP-tree constructed from the grammar [ naturally satisfies the constraint (2), while for Laylr the constraint (2) is relaxed. See appendix C for more discussion of how these constraints work.
7

---

Under review as a conference paper at ICLR 2023
Learning the Inference Model To learn the inference model p(Q(x) E Sp(Sg), fix the pa- rameters of each E V. Then, we proceed the inference steps for a fixed number T. Since the Update function is differentiable w.t.t its parameters, the obtained p(Q(x) Sp(Sg) for each Q E P and x is also differentiable, and we can optimize the inference model by simply maximizing the likelihood of p(Q(x)) Sp(Sg) data.
With the proposed approaches, the whole learning procedure of our model described Sec. 4.1 is realized.
5 EXPERIMENT
5.1 DATASETS
We consider datasets from different fields to test the model's ability in solving ILP tasks, systematic reasoning and knowledge graph completion. These datasets include:
IIP tasks We test the model's expressiveness by applying the model solve the 20 IIP tasks proposed in Evans & Grefenstette (2018). These tasks test the expressive power of an ILP model, including learning the concepts of even numbers, family relations, graph coloring, etc.
Systematicity We test the model's systematicity (Lu et al. 2022) on CLUTRR (Sinha et al. (2019) datasets. These tasks test model's ability of generalizing unseen data of different dis- tributions. Models are trained on small scale of data and tested on larger data with longer resolution steps.
Knowledge graph completion We the model's capability of performing probabilistic rea- soning on knowledge graphs including UMLS, Kinship (Kok & Domingos (007)), WN18RR (Dettmers al. (2018) and FB15k-237 (Toutanova & Chen (2015)). These tasks test model's ability of dealing with probabilistic and noisy data. For Kinship and UMLS, since there are no standard data splits, we take the data splits from Qu et al. a (20T))
5.2 MODEL CONFIGURATION
On all experiments, we the grammar presented in Eq. and if the input data does not contain unary predicates, we simply use an invented one (x) = 1. We stack LPs the same way provided Sec. 4.2 where the depth of LP-tree and number of layers of LP-layer are 5 for ILP tasks, 3 for Systematicity tasks and KG completion. For inference model, the number of iterations is 10 for ILP and Systematicity tasks and 1 for KG completion. Due space constraints, we left the detailed model configuration and sketch figure of the constructed network in Appendix D
5.3 COMPARED ALGORITHMS
We observe there are few models capable of solving all the tasks, so we pick different algorithms for comparison for different tasks. For ILP tasks, we choose Evans & Grefenstette (2018). For system-
atic reasoning, we choose Graph Attention Networks (GAT) (Velickovic et al. (2018). ) Graph Con-
volutional Networks (GCN) (Kipf & Welling (2017)). Recurrent Neural Networks (RNN) (Schus-
ter & Paliwal (1997)). Long Short-Term Memory Networks (LSTM) (Hochreiter & Schmidhuber
(1977). Gated Recurrent Units (GRU) (Cho et al. (2014). Convolutional Neural Networks (CNN)
Kim (2014), CNN with Highway Encoders (CNNH) (Kim et al. (2066)), Greedy Neural Theorem
Provers (GNTP) (Minervini et al. (2020a)), Multi-Headed Attention Networks (MHA) VVawwani
al. 2017), Conditional Theorem Provers (CTP) (Minervini et al. (2020b)). R5 (Lu et al. (022
For knowledge graph completion, we choose cule-based methods including Markov Logic Networks
(MLN) (Richardson & Domingos (2006)). PathRank (Lao & Cohen 2, NeuralLP Yang al.
2017
DRUM (Sadeghian et al. (2019)), CTP (Minervini et al. 2020b)). M- Malk (Shen et al.
2018
MINERVA (Das al. (2018). NLII (Yang & Song 2020 RNNLogie (Qu et al. [202
8

---

Under review as a conference paper at ICLR 2023
Table 1: Results on CLUTRR.
Method
4Efupe
626pp
Short Stectes
"Buup
Afllpe
3Errp
100
Stlpps
Long Stories
10fluge
DLP-acc aec
006
.9922.011
1.0:-000
10
2013
.911
984.00
.9P-3,02
96.
97:4.01
96--00
914-00
9M8-00
1M4-00 04
390--03
1/8-..0
-99--82
581
CTT,
052.00
05:1.00 03
07:..03
06:004
94:.05
89:.00
801.00
-990002
06:004
9011.04
08:3.05
.97:
.95: 104
CTPA
994..00
69-3::00 01
M9s 102
Wi:00
941:00
19::000
083 00
591-004
975.00
09:2:00
-93
911 15.00
071.00
03
05:..0
931.00
09.2.04
942..08
06
45::22 21
324.20
.08..28
59H6.32
.576.34
GAT,
912:00
762.06 D6
$4d2.03
.6m.04
546.00
$5a.05
452.06
9922.00
652.04
802..0
71:.08
700..03
.682.62
OCN,
84-:00
66- 007
53-4.00 (13
44--04
47.1.01
48%
994-00
944--05
700 000
61 000
534.04
.55 994
.41 .04
RNN,
66:008
$6:..00
.832.06
73
892.05
-72=.09
.95..04
CNNR,
903:04
81:6:115
6Pst 10
64::00
56:-11
.3sh 12
50s.
577
JM2 00
566 05
B4t 06
CNN.
052.002
903.00 03
.9:2 944
-0:006
76:1.08
.9:2.00
702.08
1.0:000
10::01
985..01
05:2.08
.933:00
.92::00
MHA
81:.00
76: 84
74:8. 08
700.00
06:.00
643.08
0718.02
385
Kic
706 044
7724.04
7788 005
700s.05
5.4 RESULTS
Comparison with other methods. The main results of systematicity tests and KG completion are shown in Tab. [ Tab. [ and Tab. 3 The 20 ILP tasks are pass-or-fail tests and both LP-tree and LP-layer are able to solve all of them, indicating that our model has sufficient expressive power to learn a variety of general ILP problems. In contrast to öILP (Evans & Grefenstette (2088), principle ILP method which uses different program templates to solve the problems, our approach uses the same grammar for all problems. With the same model architecture, our model is able to achieve high accuracy on the CLUTRR datasets. Our model is also able to learn valuable logic rules and make fairly accurate predictions much noisier knowledge graphs
2. Performance w.r.t rule complexity. We conduct experiments to study the model performance under different rule complexity on UMLS dataset in Tab. 4 We can see that if we force the rules to be too simple, it's hard to capture informative patterns of data; On the other hand, if we force the rules to be too complex, the performance is also decreased due to the loss of rule generality.
Performance w.r.. reweighting techniques. We study the effects of reweighting training data in Tab. 5 We train models on UML. dataset with different reweighting methods. We can that without reweighting, capture various logical patterns by merely randomly initializ- ing model parameters. Besides, replacing, i.e., removing data instances that are correctly predicted, achieved worst results. This is because for noisy data it's better learn more differ- ent logical patterns to prove the targets, and removing them prevents the model to learn more information about them.
model is able to
Frequenzy
Density
8
4
0.0
0.2
0.4
0.6
0.8
1.0
Accuracy
Effects of fine-tuning rule weights. We find on most situations the model is able to make fairly precise predictions without training rule weights as in Tab. [6. We set the weights of each rule to be its precision comparison experiments based on that.
Figure 2: Distribution of rules.
training data, and conduct
5. Efffett of hy perpparameters and B. To show that in most situations we can safely set a and 33 to a relative small value, we conduct experiments on UMLS dataset with different settings of a and (,, summarized in Tab. 7 Suprisingly, the performance under different and 3 greater or equal than 1.0 is quite similar. This implies that on most situations we can safely set a and 3 to 1.0 to both simplify computation and stabilize the learning of model.
6. Distribution of rules accuracy. We summarize the distributions of learnt rule accuracy and average rule contributions for UMLS in Fig. 2 The average contribution of rule equals to the average decrement of scores of queries in test data if we remove the rule and hence measures how important rule is on average for predicting the correct answers. We can see that most learnt rule
9

---

Under review as a conference paper at ICLR 2023
Table 2: Results Kinship and UMLSS
Kinship H@!
UMLS
Method
MR
MRR
H@3
H@ 10
MR
MRR
H@1
H@3
H@ 10
MLN
10.0
0.351
0.189
0.408
0.707
7.6
0.688
0.587
0.755
0.869
PathRank
0.369
0.272
0.416
0.673
0.197
0.148
0
0.252
NeuralLP
16.9
0.302
0.167
0.339
0.596
10.3
0.483
0.332
0.563
0.775
DRUM
11.6
0.334
0.183
0.378
0.675
0.548
0.358
0.699
0,854
MINERVA
0.401
0.235
0.467
0.766
0.564
0.426
0.658
0,814
CTP
0.335
0.177
0.376
0.703
0.404
0.288
0.430
0.674
RNNLogiC (w/o emb.)
3.9
0.639
0.495
0.731
0.924
5.3
0.745
0.633
0.833
0.924
DL.P
3.7
0.645
0.504
0.733
0.927
3.1
0.810
0.708
0.896
0.959
Table 3: Results on FB15k-237 and WN18RR.
FB15k-237
WNISRR
Method
MR
MRR
H@1
H@3
H@ 10
MR
MRR
H@1
H@3
H@
PathRank
0.087
0.074
0.092
0.112
0.189
0.171
0.200)
0.225
NeuralI.P
0.237
0.173
0.259
0.361
0.381
0.368
0.386
0.408
DRUM
0,238
0.174
0.261
0.364
0.382
0.369
0.388
0.410
NLIL
0,25
0.324
M-Walk
0.232
0.165
0.243
0.437
0.414
0.445
RNNLogic (w/o emb.)
538
0.288
0.208
0.315
0.445
7527
0.455
0.414
0.475
0.531
RNNI (w/o emb.)
480
0.299
0.215
0.328
0.464
7204
0.489
0.453
0.506
0.563
DLP
432
0.285
0.208
0.310
0.436
7190
0.501
0,472
0.514
0.556
rather inaccurate, there are barely any rules having precision higher than 0.5, but putting them together, rules of accuracy 0 - 0.4 contribute the most for proving the target queries.
Table 4: Study of rule complexity.
Table 5:
Study of reweighting.
Rule Length
2
3
4
Methods
Reweight
Replace
None
MRR
0.682
0.810
0.786
MRR
0.810
0.584
0.733
Table 6: Study of fine-tuning.
Table Study a and 3.
Fine-tune
Y
N
and 8
0.5
1.0
2.0
3.0
MRR 0.810
0.802
MRR 0.687
0.810
0.809
0.802
6 CONCLUSION
This paper studies inductive logic programming, and we propose Differentiable Logic Programming framework solve the problems of structure learning and weights learning. We generalize the dis- crete rule search problem and forward chaining algorithm in a continuous and probabilistic manner and use differentiable program with proxy problem to solve the learning problem. Both theoret- ical and empirical evidences are present to prove the efficiency of our algorithm. In the future, we plan to explore the possibility combining neural network architecture help the model discovery more complex and accurate logical patterns.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Tucker: Tensor factorization for knowl- edge graph completion. ArXiv, abs/1901.09599 2019.
Pablo Barceló, Egor Kostylev, Mikaël Monet, Jorge Pérez, Juan L.. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In ICLR, 2020.
Antoine Bordes, Nicolas Usumier, Alberto Garefa- Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, 2013.
Liwei Cai and William Yang Wang. Kbgan: Adversarial learning for knowledge graph embeddings. ArXiv, 0bs/1711104477 2018.
Wenhu Chen, Wenhan Xiong, Xifeng Yan, and William Yang Wang. Variational knowledge graph reasoning. In NAACL, 2018.
Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülgehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In EMNLP. 2014.
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. ArXiv, abs/171 1. 1.05851, 2018.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In AAAI, 2018.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. ArXiv, abs/ Abs/1994.1 1694, 2019.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. ArXiv, abs/1711.04574, 2018
Luis Galárraga, Christina Teffioudi, Katja Hose, and Fabian M. Suchanek. Fast rule mining in ontological knowledge bases with amie+. The VLDB Journal, 24:707-730, 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9:1735- 1780, 1997.
Yoon Kim. Convolutional neural networks for sentence classification. In EMNLP, 2014.
Yoon Kim, Yacine Jernite, David A. Sontag, and Alexander M. Rush. Character-aware neural lan- guage models. AAAI, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. abs/1412.6980, 2015.
CoRR,
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ArXiv, abbs/1609.025 (669702907, 2017.
Stanley Kok and Pedro M. Domingos. Statistical predicate invention. In ICML 2007.
N. Lao and William W. Cohen. Relational retrieval using combination of path-constrained random walks. Machine Learning, 81:53-61 2010.
Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with reward shaping. EMNLP, 2018
Shengyao Lu, Bang Liu, Keith Mills, Shangling Jui, and Di Niu. R5: Rule discovery with reinforced and recurrent relational reasoning. ArXiv, abs/2205.06454 2022.
Pasquale Minervini, Matko Bovsnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefenstette. Differentiable reasoning on large knowledge bases and natural language. ArXiv, abs/19 1912 2020a.
11

---

Under review as a conference paper at ICLR 2023
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies end-to-end differentiable proving. In JCML, 2020b.
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies end-to-end differentiable proving. JCML, volume 119 of Pro- ceedings of Machine Learning Research, pp.
PMLR, 2020c.
Stephen Muggleton. Inverse entailment and progol. New Generation Computing, 13:245-2860 2009.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso A. Poggio. Holographic embeddings of knowl- edge graphs. ArXiv, abs/15100.499. 2016.
Pouya Ghiasnezhad Omran, Kewen Wang, and Zhe Wang. Scalable rule learning via learning rep- resentation. In IJCAI, 2018.
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogie: Learn- ing logic rules for reasoning on knowledge graphs. ArXiv, 0bss2210000022/ 2021.
J. Ross Quinlan. Learning logical definitions from relations. Machine Learning, 5:239-266, 266, 2004.
Matthew Richardson and Pedro M. Domingos. Markov logic networks. Machine Learning, 62: 107-136, 2006.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In Advances in Neu- ral Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. -7803, 2017. URL http:
//papers nips. wwtppppppppppppttettttttc 6969 end to end different able -ele-proving
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to- end differentiable rule mining knowledge graphs. In NeurIPS, 2019.
Peter Schüller and Mishal Kazmi. Best-effort inductive logic programming via fine-grained cost- based hypothesis generation. Machine Learning, 107:1 141-1169, 2018.
Mike Schuster and Kuldip K. Paliwal. Bidirectional recurrent neural networks. IEEE Trans. Signal Process., 45:2673-2683 2681, 1997.
Yelong Shen, Jianshu Chen, Po-Sen Huang, Yuqing Guo, and Jianfeng Gao. M-walk: Learning to walk over graphs using monte carlo tree search. In NeurlPS, 2018.
Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. Clutrr: A diagnostic benchmark for inductive reasoning from text. In EMNLP, 2019.
Zhiqing Sun, Zhihong Deng, Jian- Yun Nie. and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. ArXiv, 192199002119,, 2019.
Komal K. Teru, E. Denis, and William L. Hamilton. Inductive relation prediction by subgraph reasoning. ICML, 2020.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Com- positionality, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. In ICML, 2016.
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, 2017.
Ramakrishna Vedantam, Karan Desai, Stefan Lee, Marcus Rohrbach, Dhruv Batra, and Devi Parikh. Probabilistic neural-symbolie models for interpretable visual question answering. In ICML., 2019.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio', and Yoshua Bengio. Graph attention networks. ArXiv, abs/1710. 10900, 2018.
12

---

Under review as a conference paper at ICLR 2023
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by trans- lating on hyperplanes. In AAAI, 2014.
Wenhan Xiong, Thi-Lan-Giao Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, 2017.
Bishan Yang. Wen tau Yih, Xiaodong He, Jianfeng Gao, and Deng. Embedding entities and relations for learning and inference in knowledge bases. CoRR, abs/1412.6575, 2015.
Fan Yang, Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowl- edge base completion. ArXiv, abs/1702.08867, 2017.
Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. In Interna- fional Conference Learning Representations, 2020. URL http:::://ceeeeeeiiee..nt net/
Forum?2d--S1h8CEYDD
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-fooe net- works: general graph neural network framework for link prediction. NeurIPS, 2021.
13

---

Under review as a conference paper at ICLR 2023
A PROOF OF PROPOSITION 4.2
We now prove Prop.
Proposition A.1 (Properties of Φ). Given the input data (Sp. Sp,SN) SN), let Q be a d-ary target
predicate, 2Q = {spo: (P.....PI--1. be set of logic classifiers and po E (0, 1] fixed thresh-
old. With the following statements being satisfied: (1) We start from I and let Sp (0) Sp:
Exevd (((x) Q002sp!)) 2 Poi (3) (2) For Pti its precision: p(Q(x) Sp Sp (oi(x) = 1) = Excoe pi(x) QuNeS)))us
1} and increase by and go to (2) again until = L; (4) Sp (1) 0. Then, there exists a prediction model p(Q(x) E Sp(Ss) =
let Sp (11)) Sp (Q(x) x E Vd (x((x)
f((o((x) (x)(x, Pr. (x)) such that its error rate satisfies:
Err [f: (SB, Sp,Sx)]= (L-oo)NQ 51-Po.
(14)
Po.N
where = Exevn Q(x)sS> and N = =xxEV' IQ(xESSUUX.
= min {1, [1, Epeo p0(x) }. and let Nyp be the number of Q(x)s that true and also predicted true by Ps, with those Qxx)s related to iP, P.., PP-- removed first. It's easy to observe that the number of (x))s predicted true by but are actually false We I 1-2 N For simplification here we let Q(x) = 1 if Q(x) E Sp
Proof:
The proof is constructive. We let
and 0 otherwise. Thus, we have:
Σx 1 (Q(x))
Err (SB, Sp, Sx))
N
Σ ((x))
min Σ plxx)
Ng
pe
N Σ Wr.
(15)
N Σ 1 L- No:
P
(1 N)NQ
< -
pN
B PROOF OF THEOREM 4.4 AND COROLLARY 4.5
We now prove Prop. 4.5 and Corollary 4.5
Theorem B.1 Consider the optimization problem
min
((v) = log Ex~p, [v(x; a)] + log Ex~pp (x(xx; 3)},
(16)
where vxx; a)) and (x(x;; 3) are obtained by one iteration of the inference procedure. Here, we assume Expo, (x)(x; a:] > O and Excos (x:x; 3)] > O. With the following constraints being satisfied: (1) > 3 1; (2) vp is the root of a LP-tree; (3) Negations are applied only on leaf nodes. Then, al each local minima of L(w), the attention vectors w used for evaluating sb are one-hot vectors and up explicitly captures a logic classifier.
Proof:
Before we proceed to prove the proposition, we need to first study in what situations does LP z capture logic classifier y. Across this section assume composed of {d)1, 2/2, V1, } where is the output node built upon t2,..., v/r.) (i.,. we care
given inference network
about. The following lemma explains the properties of when it captures logic classifier.
14

---

Under review as a conference paper at ICLR 2023
Lemma B.2 Given G and {+/1. ...) stated above. If we perform restricted breadth first search
across the inference network where:
We start with the ouiput node v);
For each node we go through, the parameters of the node defined Eq. 6 are one-hot vector where one of its dimensions equals to 1;
From the current node, the next paths we go are a subset of the inverse edges of the where we only consider the ones corresponding to the nonzero dimensions of w discussed above defined in Eq.
6
Then, &b captures a logic classifier for all x, +(x) > 0 > (x(x > 0.
The lemma is quite straightforward: by restricting a LP with the above constraints, its evaluation procedure naturally simulates the grounding of logic classifier. We can construct logic classifier y captured by & as follows: for each node we went through in the procedure of lemma B.2 we replace the LP & with an actual logic classifier &p which is constructed with the correspondence defined in Eq. 7 Moreover, for each one-hot vectors w, we pick the predicates or sub-formulas corresponding the nonzero dimension
these vectors. By doing so, we observe that the evaluation results of y for any x are the same v does because every computational steps of both yp and v stay the same. Thus, to prove that a va captures a ip, we need to show that the parameters of &b satisfy the constraints in lemma B,2
We now proceed to prove Theorem 4.4 recursively: we first prove that the parameters ur of th must satisfies the proposition, i.c. is one-hot, no matter whether w()), w(2), ... of F1, F2.... of sb are or not; Then, we prove that the parameters ((1), (x(2), w.r.t. the nonzero dimension w of w must
also be one-hot; After that, we show that if ab satisfies the proposition, the next nodes of ab in the restricted BFS path must also satisfies the proposition; Hence the theorem proved.
To study w. we fix all other parameters in the inference network G except w for uh, and the evaluation of (x; a:) becomes a simple polynomial function:
(x a)
Σ Fx)x)
(17)
and the evaluation of L' becomes:
L' ('(+) = log Exxp (x: a+] + log Ex (x;;;
log Σ (xxxa))p(x)) + log Σ (xxx;; (x)
(18)
-oo {
ΣΣ (Ex())FF(xa))
(EEOX))F 3)
wit
log
w
Hence, (b) is a polynomial function w.r.t. w and we need to show that at each local minima of ('(1) there cannot exist two w; and wij that are all larger than O, which will be discussed later in this section. Now, assume we have already know that w of ti satisfies the proposition, i.e., w; 1 for some i. To proceed, we need to prove that all parameters w(fh), (f( ... w.r.t. F, are also one-hot. We do this similarly as before: we fix all other parameters in the inference network except some (ix) emerged in neighbor of d in the inference network. By carefully checking the construction steps of J; in Eq. 7, it's easy to show that ('(1)) is also a polynomial function w.r.t. (it) under the constraints that w is one-hot. The following theorem directly proves that these functions indeed satisfy the constraints.
Theorem B.3 (Sparse Attentions.) The following function
h(w, o., 3) E, A((a)
(19)
E. BBB)w
has no local maxima w.r.t. W; E (0. with the following constraints being satisfied:
(1) Atlention vector: w; 2 0 for each dimension i and E, w; 1;
15

---

Under review as a conference paper at ICLR 2023
(2) Positive coefficients: A,(a) 0 and (, for every and all a, > 0;
(3) Non-empty results: (a))) 0 and E; (B)) 0:
(4) a > B>L 1.
We now prove that hww, a, ()) has local maxima where each wi (0. 1) by contradiction. Assume we are now given some wy where there are at least two dimensions of wo that are nonzero, and the target is to prove that wo is not local maxima of h. To do so, we create new vector Un composed of nonzero dimensions of wo together with function h',v, at B), and
Proof of theorem B33
Ci(i()) f(v,a)
h(w,a,3) 1 a'
(20)
E. D.(e), g(e,
To prove that h(w, a, (8) is not at local maxima, of (', at 3) is not at local maxima. We first consider the situations where the partial derivatives of h' w.r.t. each U, are not all the same, for example, suppose dey lu=o >
instead show that Uo is not local maxima
8h' Dey lo= Directly study all dimensions of is intractable with constraint Σ, U; 1, so we instead fix all parameters v3 04, ... at the corresponding value of vp and only study the two parameters Vi and v/ where we let 01 tol + 12 tu2 and the above constraint is naturally satisfied. Thus, have t'(v,aa a. B) = h² (x) and
8h''
(h) dx
a,,
ah' an'( a,
> 0.
(21)
Oei
Ov2
===
==
e=ve
Since the derivative w.r.t x larger than 0, on not a local maxima.
Shd Next, we discuss the situation where Jey
lo=vo À are the same. We again let 01 = vo1 + x,
U2 = Up2 - x. and all other parameters of v. We have
(x)
g g (A1 + A2u2
dx²
93
===0
-2gaB(A10) a-1 A2 (Bio + B2 B2ug-
(22)
+2/ BBIg + B21522
gf3(3 - ( BBis 2-2 + Bru 122 9-2)
Since we assume
8h' Jv, v=
X, we have
0k'
g2 (ngAaof-1 -B[Ba X,
0o:
ag -BfB.u?) = =id,,
(23)
Σ 1
g² (agAroz - Bf BBBro?) = =Eesh vdd,
{(a B) = =
16

---

Under review as a conference paper at ICLR 2023
Substituting Eq.
23
into Eq.
22
we have
(x)
f
1apn-2-BB_a BB13(3 1)09 1)09-2)
1
Ala(a 1)09-2
dx²
==
g
9
+
f
A2a(a - 1)02
-
B2313 - -1)03 2-2
9
9
f
AAiaro - Bi
9-1
f (AAcans
- -2buuz
(24)
9
902
+
11
U2
f (a B)
0.
g
11
0/2
So no is not a local maxima of N.. Thus, we have proved that h(w, 0, has no local maxima for wy E (0, 1).
End of proof of theorem B.3
Since f and log f share the same minimum points for any we have shown that the output node &b indeed satisfies the conditions in the proposition. It's straightforward to show the nodes along the paths that d is built also satisfy the conditions. Suppose
studying another vf that is used for computing tb. By writing the detailed computation steps for evaluating v and fixing all irrelevant a) and thus
parameters, we can show that v/ a)) Ex A(x', (xx((x;;))
Ex-pl (eb x a)] = Ex ax):
(25)
where p' is an unnormalized distribution. Thus, the same conclusion holds for all eb in the restricted BFS path.
We now have proved that every local minima of the proxy problem corresponds to logic classifier, and it's much easier to prove the rest of the conclusions as collaborations of the first one. For conclusion (2), notice that when z converges,
p(Q(x)lx(x)) 1) p((((x) 110(x) 1)
p(Q(x) = 1)
p(p((x)= = 1)
B ((x)) 1] E(Q(x))
E[(((x)
E[v(x: a)) 11(x))xxx)) 1) No
[x [3]
(xbb(x; [(() =
NQ
(26)
B[x(x: (xx) # E/ (xx) N
E [xxxxx]] = 1)
No
[xp:(x; B) +
Q(xx) N
No
1+ - xxx)+
N
E (x(x))))
Q(x)=1
No
(1 + cxp L()))
which is monotone decreasing w.r.t. L(v) conclusion (2) holds. Here, we assume when z
converges, (1x(x;))) > 0) x Exe (bx (xx
> 0).
C DISCUSSION OF CONSTRAINTS IN PROXY PROBLEM
In this section we discuss the properties and functionalities of the three constraints in the proxy problem well as constructing example to illustrate how they work.
17

---

Under review as a conference paper at ICLR 2023
Proxy Problem Minimization of the optimization problem
min ((v) = - (x Q((x)
E Sp] + [o ()) E Sw],
(27)
yields a near-optimal solution for solving problem satisfied.
11 with the constraints of theorem 4.4 being
Properties of and 3. We first discuss the properties of hyperparameters and B. As show in appendix B a > 8 is necessary to keep the second-order derivative positive. If we remove this constraints by simply setting a 1, then we observe that Eq. 23 actually becomes
Oh'
{(a B) 0.
(28)
Ov:
9
and we have the second-order derivative
) - 81 U2
(a B)(
(29)
dx
This means that while training the model, it is possible that the model's derivatives w.r.. multiple nonzero dimensions w; of some w become 0 and the model might falls into local minima where doesn't 't capture any logic classifier. We now discuss the situations where these risks actually exist.
The first and most simple case is when p= q, i.c.,
[(v) log Ex~p [xxx: + log Exep [x; = 0.
(30)
Apparently in this case, training the model provides nothing because L((b) is a fixed sealar irrele- vant to s. We argue that this is not a big problem since requires p and q, corresponding to the distributions of positive and negative data instances, to be the same.
By extending the above case, we can construct a more general situation. Recall that in theorem B.3 we have
h(w 1, = A,1sssss S max {A((1) Am(1) B.(w,,
BB)
(1)
(31)
where we let m be the dimension corresponding to the global maxima. If there are some dimension l of w such that (1) (1) = O. then for any w satisfying w'y and w/ = who
have hww', 1, Am(1) = (1w, 1)3. To solve this problem, we can add a normalization term to the original proxy problem, i.e.
(1)
(V) = -(() + NNomm (1)
(32)
= = log Exxp [x;; 1)] + log Exx [x(xx1)) - A log Exxp [bb(x; 1)]
Thus, even when Aa(1) B& 0, the normalization term still encourages the model to assign larger value Wm-
Another problematic situation still happens when there exists * j such that A,(1) = (1 0 and (1) (1)
This is not usual because it requires there exists two different logic classifiers 1 and 422 to have Exxppyp (x)] Bxxppl [x2(x)] and Ex (Ps (x)] = (xxx((p((x) Even when it happens, it's easy to deal with the problem, as during training we always reweight or sample different batches of training data, yielding different data distribution p' and g'. We can also set
a = 3 > 1, for example, a = 3 = 2, to avoid such situations from happening.
Tree structured paths constraints. We now discuss the second constraint in the problem. If we remove this constraints and there are circles for some unfixed nodes, we observe that L(1) w.r.t. the corresponding
might more holds the form of Eq. 19 Note that in Eq. 7 we define the conjunction as Fx(x) = Fx(x If the evaluation of F., and F& both contains some w, i.e. F, = a² (w) and Fx = at (w)a where aj and ag are irrelevant quantities with w. then F, = a² (ww" which no more holds the form of Eq. 19 Instead, we have
Σ. A.(a II W
h(w,a, 9)
(33)
Σ. A((a) II, m
18

---

Under review as a conference paper at ICLR 2023
This form of h(w. () no longer keeps the good properties of Eq. 19 as it's second order deriva- tives w.r.t some dimension of w no longer guarantee to be larger or equal than O. We provide an example to illustrate this.
Consider we want to learn logic rules of Q(x) < (x(x) = Pi(x) A Px(x) and Q(x) + (P2(x) Pa(x) P2(x). This expression is redundant because the two terms of the con- junction are the same. Suppose we the model we used here is (x; = ax: a) where vx2(x; a) >, Er Px) is a soft selection over all possible predicates. Unluckily, in the training data the logic rule ((x) < (x) and (xx) f (2((x are never satisfied, i.e.. p(((x)) (o (x)) ((Q()))p2xx))
O, but for the rule Q(x) < Ps((x) := (x(x) P2(x) we
have (p(x))(s(())) > 0. Then, it's easy to observe that the global minima of the proxy problem happens when w1 u2 0.5.
Although this situation disobeys with the conclusions of the proxy problem, both the training data, the target logie rules and construction of LPs are ill-conditioned. as we placed the same thy between the conjunction as well as in the training data we are unable to find any high-precision logic rules. We argue that in reality this can often be avoided because we can increase the expressiveness of the model, and set and / to relative large value so that even the above situation happens, because wf = wz are rather small values, it provides little stimulation to the model, and thus the model is encouraged to choose other rule structures that better explains the data. Also, because during training when the model is not at convergence, dimensions of w are rather small values, and the higher order terms II, ; "3 where Ej nj is large are much smaller than oridinary terms, which means they provide little influence to the overall derivatives of w, this problem is less serious.
Negations. When training completes and model converges, negations do not influence the validity of the model. However, during training, negations might be tricky to deal with, as adding negations to the training LPs might lead to the coefficients of corresponding w; in h(x, a, B) being negative. The following example illustrated how negations might influence the training process.
Consider we want to learn the logic rules Q(x) + (1( (x) and Q(x) + (2 (x),,, and we construct a model of v/ (x: a) = 1 - (2 a) where 22 a) = E, uw (x)).
Suppose (x))(() = 1] ([p2(x)) ((x) = 1) Ei. (lpr(x))((x) # 1]
El(p((x))((x) * 1] = E2 Then, by letting (x2(x; = 0.5 Pi (x) + 0.5% Px(),,
we observe
that
((b) log (xx
= 1] + log (x: B) [()) + 1]
- log (0.5 (F(p)(x))Q(x) 1] + R R2 x [(x) = 1)))
(34)
log (0.5 (x) Q(x) * 1] + (x) # 1))
- + 8 + constant.
Thus, we can see ((bb is monotonic decreasing w.r.t. a B, and such 4/2 can reach a smaller value than foi and 222 once 3 is sufficiently large. We can set a 3 to relative small value and carefully select the target LPs when trying to assign negations to them to avoid the problem from happening.
So far we have discussed the situations when the model might fail to converge if we discard the constraints of the proxy problem. As we can see, most of these invalidate situations can be avoided by setting a = 3 = 1 or 2 as well as providing a reasonable grammar of target logic rules. We argue that even if sometimes the model fails converge capturing a logic classifier, the parameters of the relevant LPs randomly and train the model again so that it converges at other minimum points.
reinitialize
D EXPERIMENT DETAILS
In this section we explain the detailed model configuration for each experiment.
D.1 ILP TASKS
The 20 ILP tasks introduced by Evans & Grefenstette (2018) cover problems from integer recogni- tion, family tree reasoning, general graph algorithms and so on. We briefly summarize them here.
19

---

Under review as a conference paper at ICLR 2023
Task 1-6 In task to task 6 we are provided with natural numbers from 0 to 9, which are defined as follows:
Sş {zero(0), succ(0, .)... (u,c(8,9))
(35)
The target to learn to recognize predecessor, even odd numbers, the less-than than relation and divis- ible by 3 or 5.
Task 7-8 Task 7-8 requires us to learn the relation member and length of a list. Nodes in a list is encoded follows: cons(æ, if the node after is y, and value(x. y) if the value of node is y- Two background statements are given, corresponding to the list [4, 3, 2, 1] and [2, 3, 2, 4,
Task 9-14
In task 9-14 we provided with different facts about family relations, and need to learn the relations including son, grandparent, husband, uncle, relatedness and father. An example of rules would be son(x, y) t father y) A p(z), (xx) brother(x, V father(æ, y) where implies the male property.
Task 15-20 In task 15-20 we are provided with labeled directed graphs, and we are asked to learn general concepts of graph algorithms. These tasks includes to learn whether node is adjacent to node; whether node has at least two children; whether graph well-colored, i.e., to identify if there two adjacent nodes of the same color; whether two nodes connected; and recognize graph cycles.
As principled approach, AILP (vann & Grefenstette 2018) is able to solve all these tasks. How- ever, they need to construct different language templates and program templates for each task, for example, to solve the even numbers problem, they use the following templates:
P. (zero/1, succ/2)
P. (oarge//1,peed
Ttarget,1 (h target, na 0, int False)
(36)
Ttarget,2 (h largel, ni = 1, in. True)
Tpred,1 (h pred, na 1,inl False)
Tpred,2 = null.
In contrast, we use unified model to solve the tasks. Our grammar of logic classifiers are as follows:
p(x)= P(x) (0x, a:) By (u)) A (fx, v), ( = (a,, y) (px) (py) ((x, y) Ee (p(x, z) A (22) p(2, v).
(37)
For some tasks there are no observed predicates of arity 1 or 2, we simply create an invented predicates with all values for every variables On all tasks we set
1. The construction of inference network of the model and how we train the model is the same as described in Sec. 4.] Sec. 4.2 and Sec. 4.4 The correctness of learnt model confirmed by checking whether all positive queries are predicted as true and all negative queries are predicted as false by the model.
D.2 SYSTEMATICITY TESTS
All model configurations are the same in the ILP tasks.
D.3
KNOWLEDGE GRAPH COMPLETION
The statistics of datasets are summarised as follows.
Table Statistics of datasets. #Relations
Dataset
#Entities
#Trains
#Validation
#Test
FB15k-237
14514
237
272115
17535
20466
WN18RR
40943
11
86835
3034
3134
Kinship
104
25
3206
2137
5343
UMLS
135
46
1959
1306
3264
20

---

Under review as a conference paper at ICLR 2023
(a(x,)))
P4(0)
(x
(2
g
(x((x,))
(1(
(b(x,2)
v,(x,y)
(x,),)
po(o,y)
(4(2)
(4(x.y)
(x(2,))
Figure 3: Illustration of two inference networks generated by procedure Sec. 4.3 We remove F; nodes for notation clarity. Output nodes are colored in blue. The left figure corresponds to sp(x, v) : A(x, y) ]z ((x, 2) A A(z, y), which is applicable to the systematicity tests and knowledge graph completion tasks. The right figure corresponds to yp(x)) A(x) By pp v) A (p() and pzz, y) = A(x, y) 32 p( 2) (z)) (22, y). which is used in the ILP tasks.
Generally, knowledge graphs are much noisier than ILP tasks, as shown in Fig. 2 most learnt rules have rather small value of accuracy compared to ILP tasks (correct rule accuracy is 1) and systematicity tests (learnt rule accuracy usually more than 0.8). To handle such uncertainty, we set the number of inference iterations be and learn more rules for each predicate. On all tasks grammar is the same as in ILP tasks. Because there are no unary predicates in KG, the resulted grammar is essentially
((a,,) = 32 p(r, 2) p(2,y);
(38)
which is corresponds chain-like rules. On all KG completion tasks we learn rules of length 3. We create negative statements via negative sampling. Instead of removing the proved queries, we reduce the weights of corresponding queries with the fixed ratio 0.8. We train for 400 times for each relation and remove duplicated rules. When testing. we choose different update functions for inference, including the original
in Eq. 2 modification of the original ones where set the restriction (x) = max (x), } thus the evaluation value provided by y is exactly the same as the corresponding logic classifier, and a multi-layer perceptron based on the validation data.
For evaluation, we use the standard filtered ranking (Bordes et al. (013)) metrics, including Mean Rank (MR), Mean Reciprocal Rank (MRR) and Hit@k (H@k) When there multiple tail nodes assigned with the same score, we compute the expectation of each evaluation metric over all random shuffles of entities (Qu al. (202I).
After all, in all of the experiments, we use Adam (Kingma & Ba 2015) optimizer with (r (0.01, 0.1}. We let softmax function follows:
(1,2). We generate the structural parameters of LPs ur using
=oftmaxx(w')
(39)
where w' E R are real-valued vectors with no constraints. We prepossess the data to add per- mutations for ordinary predicates, for example, for every 2-ary statement P(a, b) in data we create an invented one pd (b(b, a). For randomly initialized parameters, we draw them independently from Gaussian distribution (0, 1), but this not necessary and other distributions (uniform. Xavier, ...) also work well. Illustrations of inference network architecture constructed with the procedure discribed in Sec. are Fig.
E DISCUSSION OF TIME COMPLEXITY
In this section discuss the model complexity. Suppose the inference network is composed of N LPs. Suppose the arities of predicates and LPs are at most n. We now discuss the time complexity of each part of the inference model.
General time complexity We first take a look at a single LP's behaviour, where we assume that all other LPs in the network are already evaluated. From the definitions of LPs Eq. and Eq. 7 can see that evaluating one LP invloves:
* (x: a)) (x))
(40)
21

---

Under review as a conference paper at ICLR 2023
Since the total amount of F, is limited and does not scale as the network or input data grows, this step costs
T()) $ Σ +0(1))
(41)
where we let T(サ) be the time complexity for evaluating vxxx;) for all x, T(F;) be the time complexity for evaluating Fi(x; a) for all x, etc. For each F,, we have:
ax (2(), (P)) (m)(0)) = T()5
a) F,(xx
= T(F)) +T)))
a) = (x), Fr (wo(1))
+ +
a) (x;(a)
T(F) S +
F(x:a) Σ (;) y F((,y;a) = (x;
T(F) +T(5)+ -()1))
T(F) S +
(42)
Thus we can see that for one 1h, we have
T(t) Σ CO(PI)))) O(PI)))))
(43)
To evaluate all nodes in the network, we simple evaluate LPs one by one in topological order, which directly gives total time complexity of
T(V)= = O(PIPP)).
(44)
The update procedure for one x is function with Rs (amount of learnt rules) inputs, and all im- plementations we introduced here all make the evaluation of the function O(Rr)), so the evaluation over all x takes O(V))" Rvy) time.
Time complexity on sparse graphs In reality often the input data sparse, and the | term in time complexities can be reduced significantly. Here, we analyse the time complexity of the model under knowledge graph completion experiments.
Suppose the input graph has [V] nodes, |P] predicates and M edges, and we are learning chain-lite rules of length L. Thus, each output unit, corresponding a rule, is composed of LPs, and can be written as follows:
()) =
Σ Pi Pla.::oo//P(aaeeoo)P.11111..:.
(45)
21 21
where
P((x,ya) = [P, P2 (2. v....
(46)
We can efficiently calculate (xx y: a) for all nodes in the knowledge graph with the same source I. The algorithm is an extension of L-step breadth first search described as follows. S, maps nodes y with nonzero value d6x, a.) (b o.).
22

---

Under review as a conference paper at ICLR 2023
Algorithm Inference in sparse graphs
Input: graph G. predicates P. source node 2, rule length model parameters a, w1, W2, ... WL.
Output: U₁.
function EVALUATE(E, I, a, w1, u2,,..; w1)
2: So M-M((())
3: So[z] + 1.0
4:
for 1 +- to do
5:
S: (MM(())
6:
for P E P, Si-1,t E (s(s) do
7:
if & Si then
8:
S 0.0
9:
end if
S/ < Sr + (wi(Pl) S-1[s]]
11:
end for end for
13: return S2
end function
Here, we denote (s) as the neighbors of in the KG, and (P(s) as the neighbors of connected by edge type P. Thus, one run of the function takes at least
Taingle = E
E PEP (ENr(()
Σ 0(1)
SESI-1
(47)
Σ Σ
((W())))
1=1 8ES
Denoting (k) as the max amount of nodes node's h--hpp subgraph, we have
T saigge
N N(L1)
(48)
1=1
$ (((LL())))
Thus, one-time of evaluating total number of Ry rules for all node pairs in the graph takes
T S Ro ViTsin
(49)
= =0 (
Since in sparse graphs we often have N() << (()) << [V], this estimation of time complexity
(Eq. 49 is much less than the original one (Eq. 44p, which is L/P in this case.
F
CASE STUDIES
In this section we illustrate part of the logic rules we learned on ILP tasks, systematicity tests and knowledge graph completion.
23

---

Under review as a conference paper at ICLR 2023
Table 9: Sparsity of L.P-layer.
Task
Converge Ratio
ILP = 1
0,915
Systematicity a =
0.813
Systematicity a 2
0.956
KG completion a =
1.0
Target DivisibleBy3(z)
Rules
V1 (x)) Zero(x)
22 = By: (y) A Succ(y,
(a(x) By: (v)( Succ(y,
4/4 (4) = Fy: DivisibleBy-(()) A Su
MijaeentooRed(2
4/ (1² Fy: Red(v) A Edge(x,
Connect(x,y)
(1 y) Edge((z, y)
42(2, y) = 3z Connect xz 2) A Edge(z, y)
Grandmother(z, v)
(1 v) 3: Brother(#; =) A Grandmother(z,.)) v)
V2(2, 3) 3= Father(æ, =) Mother(z,
Causes(xx 3/)
(2, v) = 3z1, 22 ( 2)) A LocationO((z1,
AOccursIn(22,1/ w)
(22 v) = 3z #2 Contains (1,, .r) LacationOO(z)
AComplicates/ (y/ 22)
V3(2z y) = 3ø1 22 OngredientOf(211222 A IsA(21,
ACauses( 22, y)
- va( v) = 32g, 22 Ongredient (1, A InteractsWith(22..))
ACauses (22,
G ADDITIONAL ABLATION STUDY
In this section we provide empirical results for additional ablation study.
G.1 SPARSITY OF LP-LAYER
We LP-layer the experiments used in this paper and obtain the sparisity of learnt parameters. For each w used for prediction, if after training max (Wi, W2....) 2 0.99 we simply regard w as being converged. Then, obtain the results in Tab.
G.2 DEPTH OF NETWORKS
We run LP-layer and LP-tree with different depths {3, 5, 10} on ILP and Systematicity tests. Depth of 3 cannot complete some of the ILP tasks which requires more reasoning steps. Depth of 5 and 10 are both able to complete ILP tasks. Results on Systematicity tests are very similar with depth 3, 5, 10, as is shown in Tab.
G.3 CLIPPING ON LP
We now study the effects of whether to restrict the range of of to be [0, 1] by simply setting (x; a:) &- min(w(x; a), 1}. The results are shown in Tab. 11
24

---

Under review as a conference paper at ICLR 2023
Table 10: Depth networks.
4Hops
5Hops
6Hops
7Hops
8Hops
9Hops
10Hops
DLP-tree-3
.990
994
1.0
.955
997
.96
1.0
DLP-layer-3
.991
.99
1.0
.955
.997
.96
1.0
DLP-tree-5
.995
994
1.0
.997
.997
.996
1.0
DLP-layer-5
.995
994
1.0
.997
.997
.996
1.0
DLP-tree-10
.995
994
1.0
.993
.997
.966
1.0
DLP-layer-10 10
.955
.994
1.0
.997
.997
.966
1.0
Table 11: Setting (xx; ())
min (xx a), 1}.
Kinship H@
UMLS
Method
MR
MRR
H@3
H@10 10
MR
MRR
H@1
H@3
H@ 10
With clipping
3.7
0.639
0.498
0.725
0.926
3.2
0.800
0.689
0.892
0.957
Without clipping
3.7
0.645
0.504
0.733
0.927
3.1
0.810
0.708
0.896
0.959
25


Reviews:
[{"review_id": "vSAgU003x03", "reviewer": "Reviewer_kdMZ", "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": "This paper proposes a differentiable logic programming (DLP) framework, which relaxes logical operations (e.g., AND, OR) in a rule with numerical operations (e.g., multiplication, addition). DLP can learn logical rules and weights. The key idea is to (recursively) generate logical rules by following a chain-like pattern (specified in Equation 1) with conjunction, disjunction, and negation. Candidate logical rules are associated with weights, which are learned through minimized a proxy loss. The empirical evaluation shows that DLP achieves similar or slightly better performance compared to a number of baselines. ", "summary_of_the_review": "This paper studies an important and interesting challenge in AI -- learning logical rules and weights. The approach of using numerical relaxation and simple template (or so-called generative definition in the paper) to facilitate rule learning is well-known. It's difficult to see the actual novelty besides an obscure way of formalization. And, the practical significance is unclear given the current evaluations.", "strength_and_weaknesses": "Strengths: \n- this paper uses many recent baselines and three different kinds of datasets in the empirical evaluations\n- many performance ablation studies have been presented\n\nWeaknesses:\n- the writing is not easy to follow, particularly, heavy use of (undefined/unexplained) notations makes the reading quite challenging. For instance, proposition 4.2 is especially hard to understand. \n- the idea of relaxing logical operations as numerical operations and attaching logical rules with weights is well-known\n- using differentiable learning to discover useful logical rules is also not new (see the survey paper R1)\n- the so-called generative definition (Equation 1) is essentially a simple template, which may be more generally viewed as grammar. Then the construction of networks (or rule generation process) is a simple instance of the well-known Syntax-guided synthesis (SyGuS) in the programming language community (see R2). \n- the empirical evaluation shows very little improvement. Particularly, around 1% or less improvement on three knowledge graph completion datasets (i.e., Kinship, FB15k-237, WN18RR). \n\n[R1] Luc De Raedt, Sebastijan Dumancic, Robin Manhaeve, Giuseppe Marra: From Statistical Relational to Neuro-Symbolic Artificial Intelligence. IJCAI 2020: 4943-4950\n\n[R2] \tRajeev Alur, Rastislav Bodík, Eric Dallal, Dana Fisman, Pranav Garg, Garvit Juniwal, Hadas Kress-Gazit, P. Madhusudan, Milo M. K. Martin, Mukund Raghothaman, Shambwaditya Saha, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, Abhishek Udupa: Syntax-Guided Synthesis. Dependable Software Systems Engineering 2015: 1-25\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "erGdU5i1ZFY", "reviewer": "Reviewer_mi4W", "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": "This paper presents a  derivcate construction mechanims for logical formulae. Results are very good.", "summary_of_the_review": "\nMaybe my fault: thereś a lot of good suff here, but it didn;t entirely convince me, esoecially when comparing  to related work.", "strength_and_weaknesses": "This paper presents a theory for obtaining derivatves of logic programs Several researches worked on this, Domingo s and colleagues had a relatively simple model for mlns, Problog used Derivatives from BDDS, Last we have graph Rule construction: iit is kind of reminiscent of Tensorlog\n\nResults look good (including variance).\n\nIsues: What is novel here? \n\nAre you constructing a probabilistic system or just a NN?\nPlease explain more in detail how this work evolves over previous packages/", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LcUeEGJkpw", "reviewer": "Reviewer_qPBm", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper proposes a method for an ILP-style rule-learning problem by using gradient descent over differentiable approximations to the various connectives in the language under consideration. The method is empirically tested on a suite of ILP tasks, the CLUTRR benchmark, and some knowledge graph completion tasks.", "summary_of_the_review": "The presentation of the proposed method is too vague to be useful. At times, the presentation seems to deliberately avoid committing to details of the method. This also raises questions about the validity of the experiments, specifically whether or not a single, common algorithm is being evaluated.", "strength_and_weaknesses": "The main strength is that the proposed method seems to do well on CLUTRR and relatively well on the knowledge graph completion tasks, compared to the handful of chosen baselines for each task.\n\nThere are some significant weaknesses, however. The main weakness is that the presentation of the method is essentially unreadable and disturbingly vague at places. \n\nTo begin with, the problem statement is unclear: the input data is described as both a set of FOL statements and as a set of triples. It is not clear to me if the FOL statements are supposed to be ground atoms (as they are in the example) or contain free variables as the notation suggests, or if they can be arbitrary FOL formulas. The tasks \"Recognition of Logical Patterns\" and \"Probabilistic Reasoning\" are only described in rather vague terms: what does it mean to \"explain how the answers are deduced?\" What does it mean to \"make decisions [some expression] based on the groundings of classifiers\"? \n\nIn Proposition 4.2, what is the \"precision on B\"? In the formulas there, for the sums indexed by x, what does x range over? What does it mean to \"remove all queries Q(x) = 1 and also proved true\"? What is the \"prediction model\" being constructed -- what does this notation with p_w mean? Apparently after learning such models, we \"remove or reduce the weights of data instances where Q(x) = phi_i(x) = 1\" -- what are these weights and which is it, remove or reduce them, and by how much?\n\nIn Equations 6 & 7, it seems like some strange vector notation is being used, but the dimensions don't seem to work and I'm not certain I know what is meant by raising the vector to the power alpha.\n\nIn the section on inference, I still don't know what x ranges over; are we looking at all possible groundings? The function \"sigma\" is not defined. Q_0 is also not defined. \n\nThe description of constructing the networks is vague. Equation 7 gives a correspondence between connectives and the differentiable approximations; how do we obtain \"output LPs\" from these definitions? What does it mean for \"another LP\" to be \"needed\"? We repeat the procedure \"a couple of times\" -- meaning two? or just some arbitrary constant number?\n\nIn the learning section, Proposition 4.3, how do you decide when a node should be fixed? What does it mean for the solution to be \"near-optimal\"?  Needless to say, I don't see why the vague construction procedure satisfies these constraints, in particular the constraint of having a tree topology on the unfixed nodes. Note that the network in Figure 1 definitely does not have a tree topology. Actually, this raises a concern, that to satisfy this requirement, the method might need to explicitly represent the tree of possible logical expressions. Needless to say, this would not seem to offer any computational advantage over traditional ILP methods.\n\nMoving on, in the experiments, there are a few fishy features. For one, the authors chose to write their numbers in boldface when there are other methods that seem to have essentially equivalent performance as far as I can tell. For some reason the authors give their method's numbers to three decimal places when the stated accuracy clearly only warrants two. Also, for some reason the knowledge graph completion tasks are only examined on subsets of the baselines for unknown reasons. \n\nUltimately, my main concern with the experiments is that the vagueness of the description of the method may be covering some kind of handcrafting of solutions for the various benchmark problems. At several points, e.g., the definition of the \"update\" function, the choice of structure, etc., the text suggests that there are many possible choices. If these choices are made by the experimenter individually per benchmark, it calls the validity of the results into question.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "G9pdljPWAJm", "reviewer": "Reviewer_qAry", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This work proposes a differentiable logic programming framework that aims to learn first-order logic structures and weights. This framework further supports probabilistic reasoning by performing probabilistic forward chaining. Some theoretical guarantees on error rate and solution optimality are shown. Empirical evaluations of the proposed framework are carried out in various tasks including inductive logic programming, systematic reasoning and knowledge graph completion.", "summary_of_the_review": "My main concern is the readability of this work.", "strength_and_weaknesses": "This work aims to bridge between differentiable programming and symbolic reasoning which has been an important research topic. However, here are a few concerns/confusions when I go through this work:\n\n- Figure 1 is very helpful for understanding the differentiable logic program. Still, it seems that the structure of the learned is not arbitrary since it depends on how the network is defined. Can the authors further illustrate how expressive are the learned logic rules and what are the limitations?\n- Also, I wonder how are the edges are chosen in the example in Figure 1. For example, why \\phi_2 choose the edge connected to Red but not the edge connected to Blue, is there some threshold for for the weights to decide which edge results in the learned logic rule? It is not clear in Sec. 3 or Sec. 4 how this is achieved.\n- For Prop. 4.2, it is unclear to me what these assumptions mean. Specifically, for the assumption (1), the notation is confusing that on the left hand side the x seems to be a variable while on the left hand side x seems to be taken over all possible assignments to the variables. For assumption (2), it is unclear to me what does \"remove all queries Q(x) = 1\" and \"proved true by previous ...\" mean. The authors might want to provide a formal description here to improve readability.\n- In Equation (7), what are the alpha's? Why do we need alpha and how are alpha chosen? It does not seem that they are learnable parameters.\n- The empirical evaluation is extensive. Still, it is not obvious that the proposed framework is more advantageous over RNNLogic+ in Table 3.\n\nMinor issues:\n- in Preliminary, the same notation \\mathcal{V} is used for bot the set of constants and also the set of variables.\n- at the first line of Equation (1), should it be exist y instead of exist z?\n- \\sigma in Equation (8) is not defined.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject