Differentiable learning of numerical rules in knowledge graphs
Authors: Po-Wei Wang
Daria Stepanova
Csaba Domokos
J. Zico Kolter
Venue:  (2020)
Keywords: knowledge graphs
rule learning
differentiable neural logic

Abstract: Rules over a knowledge graph (KG) capture interpretable patterns in data and can be used for KG cleaning and completion. Inspired by the TensorLog differentiable logic framework, which compiles rule inference into a sequence of differentiable operations, recently a method called Neural LP has been proposed for learning the parameters as well as the structure of rules. However, it is limited with respect to the treatment of numerical features like age, weight or scientific measurements. We address this limitation by extending Neural LP to learn rules with numerical values, e.g., ”People younger than 18 typically live with their parents“. We demonstrate how dynamic programming and cumulative sum operations can be exploited to ensure efficiency of such extension. Our novel approach allows us to extract more expressive rules with aggregates, which are of higher quality and yield more accurate predictions compared to rules learned by the state-of-the-art methods, as shown by our experiments on synthetic and real-world datasets.

Published as a conference paper at ICLR 2020
DIFFERENTIABLE LEARNING OF NUMERICAL RULES IN
KNOWLEDGE GRAPHS
Po- Wei Wang
Machine Learning Department Camegie Mellon University and Bosch Center for AI powe seveiwccs. cmu.
Daria Stepanova
Bosch Center for Al
stl.aaattepno.edde..... bosch. com
Csaba Domokos
Bosch Center for Al
esaba. dcmokos@de, bosch. com
Zico Kolter
Department of Computer Science
Carnegie Mellon University and Bosch Center for AI zkolterêcs, cmu edu
ABSTRACT
Rules over knowledge graph (KG) capture interpretable patterns in data and can be used for KG cleaning and completion. Inspired by the TensorLog differ- entiable logic framework, which compiles rule inference into a sequence of dif- ferentiable operations, recently method called Neural LP has been proposed for learning the parameters as well as the structure of rules. However, it limited with respect to the treatment of numerical features like age, weight scientific mea- surements. We address this limitation by extending Neural LP learn rules with numerical values, e.g., "People younger than 18 rypically live with their parents". We demonstrate how dynamic programming and cumulative sum operations can be exploited to ensure efficiency of such extension. Our novel approach allows to extract more expressive rules with aggregates, which are of higher quality and yield more accurate predictions compared to rules learned by the state-of-the-art methods, as shown by our experiments on synthetic and real-world datasets.
INTRODUCTION
Due the availability of amounts of knowledge on the web, advances in information extraction have led to large graph-structured knowledge bases, also known as knowledge graphs (KGs), which are widely used web search, question answering, and data analytics. Such KGs represent data as graph of entities (e.g.. john, articlel) connected via relations (e.g., citedIn), or more formally as a set of binary grounded atoms (e.g., citedTn (john, article )). A common task such settings is that of link prediction, determining whether relation exists between two entities in the graph even the relation not included explicitly in the graph. Although most work on this topic has focused statistical rule-extraction techniques (Meilicke al. (2019); Galárraga et al. (2015); Ortona et al. (2018 8a)), recent methods have shown the benefit using deep learning approaches for this link prediction task (see Wang al. (2017) for overview). And while most deep approaches (for example, those based upon graph embedding methods) are inherently difficult to interpret, the Neural LP method of Yang et al. (2017) is particularly appealing in that it allows for interpretable

---

Published as a conference paper at ICLR 2020
resulting rules for the link prediction task while still preserving the flexibility of a learning approach. Unfortunately, Neural LP is also quite limited in the types of rules is capable of representing, and notably rules that depend on numerical features can be efficiently learned within this framework.
In this paper, we propose an extension to Neural LP that allows for fast learning of numerical rules. Specifically, although numerical rules would result in dense matrix operations in the generic Neural LP framework, we show that using dynamic programming and cumulative sum operations, we can efficiently express the operators for numerical comparators within the Neural LP framework. By defining the relevant operators implicitly in this manner, we show that we can extend Neural LP to efficiently learn rules that make use of numerical features, while retaining the interpretability of the Neural LP framework. More generally. this is an instance of integrating so-called "aggregates" (i.e. external oracle queries, in this case binary queries that reflect numerical comparison) within a rule-learning framework. Learning such rules with aggregates is very much an open problem in the KG community (Galárraga & Suchanek (2014), and our approach the first work to learn rules with these numerical aggregates.
We apply our approach to several knowledge graph datasets, and show that we are able to answer queries more accurately than the previous Neural LP approach, as well as more accurately than state-of-the-art rule extraction method, the AnyBurl package proposed by Meilicke et al. (2019). Specifically, show on two synthetic and two real-world datasets that extension to Neural LP is able to more accurately recover rules that depend on numerical information, and thus make much more accurate link predictions in the knowledge graph. Further, the extracted rules still interpretable as in the original Neural LP framework, and unlike the pure graph embedding strategies (Bordes al. (2013)).
RELATED WORK
Relational Data Mining. The problem of learning rules from the data has been traditionally addressed in the area of relational data mining Raedt (2017) and inductive logic programming (ILP) Muggleton (1995). Works most related to ours concern learning decision trees with aggre- gates Vens et al. (0066) from relational data. However, these methods typically do not scale well, and modern knowledge graphs are far beyond what they can handle.
In the context of KGs, the problem of rule learning has recently gained lot of attention. In Ortona et al. (2018b) rules with negation, which also support numerical comparison we do have been considered. Contrary to our approach, however, Ortona et al. (2018b) is designed to find a small set of rules that cover the majority of positive and as few negative examples possible, which differs from our goal of learning rules in an unsupervised fashion.
Neural-based Rule Learning. Several works Yang et al. (2017); Manhaeve et al. (011):
Rocktäschel & Riedel ()017); Evans & Grefenstette (2018); Zhang et al. (2019); Ho et al. (001))
Weber et al. (2019) utilize embedding models and neural architectures for rule learning. The closest to ours is the work Yang et al. (017)) which reduces the rule learning problem to algebraic oper- ations on neural-ent serrral-mmeddiig-bbe based representations of given KG. However, Yang et al. (2017) is restricted non-numerical rules in contrast to our work.
Embedding Models with Numericals. The problem of KG incompleteness has been tackled by methods that predict missing relational edges between existing entities. Several approaches rely on statistics and include tensor factorization (e.g., Nickel et al. (2011)). Other models are based on neural embeddings (e.g., Bordes et al. )2013). For overview see Wang et al. (2017).
The most relevant for us is the work García--urái & Nieperi (0018), which presents novel ap- proach to combining relational, latent (learned) and numerical features, i.e. features taking large or infinite number of real values for the KG completion task. While Gareía-Dures & Niepert (2018) operates on KGs with numerical values, it's results like in the case of most knowledge graph em- bedding models not interpretable.
2

---

Published as a conference paper at ICLR 2020
articlel,
article2
T
ciedii
ciredli
citealn
pele
collengueyf
John
supernisory
lnghuences
hasCimation
bob
124
havCitation
33
Figure 1: An exemplar KG about publications, their authors and relations among them. Relations are presented in italics, entities in bold black and numerical values in circes, true facts as solid black lines and the missing ones as dashed lines in red.
3 PRELIMINARIES
Knowledge Graphs. We assume countable sets C of constants (ak.a. entities), C I of numerical values and R of binary relations (a..a. predicates). A KG G is defined by a finite set of ground atoms (a.k.a. facts), of the form p(z, y), where p E R. x E C and y CUN (e.g., citedIn(john, articlel) )). The set R, S R stores all numerical predicates such that p(z, y) E G, where E C and E N. The set of numerical facts, ie. facts over numerical predicates, denoted by 9n. S G. We use lower-case letters for constants and upper-case letters for variables.
As KGs are incomplete, one can assume that missing facts, i.e. facts that are not in G, are either unknown or false. Typically the open world assumption (OWA) is employed, which means that missing facts are considered to be unknown rather than false. Alternatively, the local closed world assumption (LCWA) can be considered to generate negative facts by assuming that the KG is locally complete as data is usually added to KGs in batches. More precisely, it means that for any x E C we conclude that p(æ, y) is false if E C CUW exists such that p(x, G and p(x, & g.
Numerical Rules. rule an expression of the form
Y) + qi (1, A A 4o Y),
where p, .1....... 9n E R, left-hand side of the rule is referred to as the rule head, and right-hand side as the rule body, and every conjunct in the rule head or body is referred to as an atom. The rule influences(X X, Y) s- colleague X, Z) A supervisorOf (Z, Y) intuitively states that typi- cally students are influenced by colleagues of their supervisors. Aside from conventional rules, we can also have numerical rules, i.e. rules that contain numerical comparison among variables (e.g.. number of citations of two people), or a variable and a numerical constant.
To simplify presentation, numerical values in A linked an entity from C are sometimes treated as its "features", and numerical relations in R2 as functions that depend on those features. In this case, For instance, john.hasCiiati
for p(X, Y) we also use shortcut notation X.P stands for Citationnjooii 124), and for compactness, rpg (X, Y) stands for X.p Y.g, where E {s, }}. The second subscript in py is omitted if it is clear from the context that = Example 1. For example, consider a KG in Figure I and the following rule
124
influences( X, Y) +- collengue (X, Z) A supervisorOf (7,Y) Y) r ThasCitation (X, 7) This rule states that students are influenced by colleagues of their supervisors with higher number of citations
We can also define classification relation mapping the feature to the probability of a logistic clas- sification, a (w X. features + b), where w and are parameters and the sigmoid function. As demonstrate later such rules can be integrated and learnt naturally in the Neural LP framework.
Rule Learning. Given a KG G the goal of rule learning is to extract rules from G. such that their application to 9 results in an approximation of the ideal KG, which stores all correct facts.
Le influences(X, Y) + Of X, 2) A OupervisorOf(2. Y) A has Citation X, V1) A KasCitation V2)
Vi > V22
3

---

Published as a conference paper at ICLR 2020
The Neural LP method (Yang et al. 2017 Dis among rule learning proposals, which leams dis- tribution over rules of the form in Eq. ( without comparison operators an end-to-end fashion by making of gradient-baser optimization. This approach relies the TensorLog frame- work (Cohen et al. (017)), which connects rule application with sparse matrix multiplications. In TensorLog all entities mapped integers, and each entity i is associated with one-hot coded vector U, {0, 13 1 such that only its i-th entry is 1.
For example, every KG entity c E C in Fig. | encoded as 0/1 vector of length 5, since [C] = 5. For every relation p E R \ R2 and every pair of entities 2, y E a matrix Mp E {0, (0,1)/c1x) 1]10)xia is defined such that its (y.z) entry, denoted by (Mp))ar is 1 iff p(z,, y) E G. For example, by considering the KG in Fig. for the relation citedIn we have
john
pete
bob
articlel
article2
0
0
0
0
john
0
0
pete
Mp =
0
0
0
0
bob
0
0
articlel
1
0
0
0
0
article2
The idea of TensorLog is to imitate application of rules for any entity X x by perform- ing matrix multiplications Mq.... Ma. Mg zero entries in the vector s point the above rule on G. For example, the inference for the following rule (xfluences(X,X))) Of Z), supervisorOf (xnpeporrf (Z, can be translated to
8, where Ua is the indicator of entity Non- entities for which p(1, y) derived by applying
SuupervisorOf M McolleagueOf U2=
By setting Vr 0,0,0.0,0) T as indicator of john and applying the matrix multiplications, we obtain = 0, 0] the indicator of bob. As Ma...., Mg. sparse, the matrix-vector multiplication can be done efficiently, and the inference process is parallelizable on GPUs.
In Neural LP (Yang et al. (217)) above operators are used to learn for every head the formula
f(a) Σ a II M i
JEB,
where i indexes over all possible rules, ag is the confidence associated with the rule and 3; is an ordered list all relations appearing these rules. The rules are read off from the solution of following optimization problem
max log (a.
Σ (x.U)
Σ
a. II
Mar Moz)
jEA;
LEARNING RULES WITH NUMERICAL FEATURES AND NEGATIONS
As the main contribution of the paper we extend the Neural LP framework to allow us to use com- parison operators with numerical values in the rule bodies, and also handle negations of atoms. These extensions are non-trivial as the Neural LP framework does not directly support facts over numerical values: naively treating numerical constants as entities in C is intractable due to the ex- plosion of the number of non-zero elements in the respective matrices. Similarly, naive treatment of negated atoms would introduce dense matrices that would not be practical to operate on. Intuitively, the main idea of our approach is represent the necessary matrix operations implicitly, either using dynamic programming, cumulative sums and permutations (for numerical comparison features) or low rank factorizations (for negated atoms). Exploiting this structure lets us formulate the associated Tenso oossorla Lorg operators efficiently, and effectively integrate them into the Neural LP framework for rule extraction.

---

Published as a conference paper at ICLR 2020
4.1 COMPARISON OPERATORS
Pair-wise Comparison. We start by implicitly representing the operators associated with numerical comparators. Let p, q E (R U {NaM))]él be the vector of two specific features, where NaN means missing values. The comparison operator M, is defined as
{
if p. S qy and pt, qj are not NaN,
(M s )os - p4
otherwise.
Intuitively, this matrix includes the binary indicator of the comparison, over all pairs of entities in the knowledge graph that contain p and g. Unlike conventional sparse relations, the matrix M "p is usually dense (i.e. it has O non-zero elements), thus naive materialization would exceed the typical GPU memory limit. However, in reality there no need to explicitly materialize the TensorLog relation matrix. Note that in the Neural LP inference chain described above, all that is needed to efficiently compute the matrix- vector product between a relation matrix and some vector representing the current probabilities in the inference chain.
Consider the special case that both and are sorted an ascending order as p and ğ with operator (<) and call the corresponding comparison matrix < Since q S @++1 and Py S Pj+1, we have the following property (P1)
(M (M, jas Pq
(M (M 111.
(M )====
=
ie., the resulting matrix M x is always effectively lower triangular in form (or more precisely, the transition from 1 to 0 is always monotonic in the matrix, even if the non-zero pattern is not precisely lower triangular in the usual sense).
Now define y arg max, such that (M, "pu ) i..., % is the index of the last element equal to one. The main observation is that we can compute the required matrix-vector product using just this 7 vector, i.e. for any vector v.
vM FF
Σ 1/ cumsum(v)n.
TSSSICI
The respective values of y for M can be precomputed on CPU with linear complexity by dynamic programming since its value is monotonically increasing because of the property (P1). be calculated in O([C)) time, with efficient GPU parallelization
Also, the cumsum operator that in practice is even faster for large vectors.
For the general case when p and y are sorted, can first permute the input v the sorted order, perform the matrix-vector multiplication, then permute the result back to the original order. Since permutation (a.k.a,, index slicing) a simple linear time operation, this does not affect the complex- ity of the overall approach. Specifically, let P, and Pa be the permutation matrices corresponding the argsort of p and g, respectively. Then the matrix-vector multiplication corresponding the comparison operator can be written as
M S pq
(P, (P) PaJ== (MPP)) P.J (P
which can be computed in O(CC)) in parallel given 3, which are precomputed once in O(IC) log [C]). Thus, the comparison operator needed for inference can be computed efficiently a GPU.
Efficient Use of Numerical Comparisons via Multi-atom Symbol Matching. Although the above numerical comparison operator provides an efficient means for implementing such compar- isons within the Neural LP framework, has significant drawbacks as well. Specifically, because the comparison operator is dense, when using it to match potential entities in the graph, it has the
This way, the comparison involving NaNl always yields false and they will be stacked the end.
5

---

Published as a conference paper at ICLR 2020
potential to create huge number of candidate matches. For example, the operator (X.p I Y.p) will link the entity with smallest p to all other entities with attribute p and will decrease the probability of finding the correct target. To make the comparison operator more useful, it is natural to use jointly with some other sparse operator. For example,
(X, Y) (X.p
would search only over neighbors of X in the graph that also obey the respective numerical re- lation. Let the two parallel relations from above correspond to operators M Molleague and M M,s. "pa
respectively. The above conjunction can be implemented in TensorLog via
(M (Menlteguu:Or1) ④ (M Pi
v) diag( ( () v),
where the symbol @ denotes the element- wise multiplication. Unfortunately, the above relation is not learnable in the standard Neural LP framework, since the latter only supports single chain of matrix-vector operations Ma.... M ... Ma Cn. which does not allow for easy computation of this Hadamard product, as it includes two "copies" of the vector v. However, we note that it is trivial to simply cache intermediate values of in the multiplication chain, and this way conveniently compute such Hadamard products; in the knowledge graph setting, this exactly corresponds to the ability to integrate symbol matching at multiple points in the inference chain.
Classification Operators. We may also consider more general rules, where the comparison per- formed not necessarily among two numerical attributes of a certain entity but rather functions over such attributes. Note that such comparison for all entities can readily be expressed by TensorLog operators, that is, the corresponding matrix for given numerical value Z is diagonal matrix. We model the numerical value Z by making use of logistic model. Namely, for each entity we collect the feature vector y, which consists of all the numerical values from N that are in relation with the given entity. The 2 element of the diagonal in M is defined as sigmoid (w" T g + b), where the weight vector and the bias vector b are assumed be learned. These parameters can easily be learnt in the Neural LP framework via backpropagation.
Negated Operators. The negation of relation p E R. obtained by naively flipping all zeros to ones and vice versa in the corresponding (sparse) matrix Mp results in a dense matrix, which is not supported directly in TensorLog. To compute the negated operator Mp E {0, 1011)iixi x|C| we employ the local closed-world assumption. For a given Mp only the elements, that in such rows that contain at least one non-zero element, should be flipped. The matrix-vector multiplication for the negated operator Mp can be written as
1p:==1,1-0 MDU.
where 1 E f0, 13|cI is the indicator vector for such that (1p): = 0 iff p. = NaN. Here, is the vector with all of its elements equal to 1. Note that for any TensorLog operator Mp the products MA and 1 (1(TT) can be computed efficiently, therefore the negated operator M, can be computed efficiently as well.
The trick in Eq. (3) generalizes the comparison operators M,e.- namely,
M, v 1p1, Mrg.
E.g., M 1p1 M G. This way we can learn rules with negated atoms in the body.
Once the rules have been learned by our approach, we rely on the same procedure as in Yang et al. (007) to decode them back the form of E
Connection to Rules with Aggregates over Knowledge Graphs. Note that, importantly, the rules that we extract using the described procedure fall into the language of logic rules with external com- putations in the spirit of Eiter et al. (2012), and are connected to the concept known as aggregates in the knowledge representation community. Indeed, much of the formulation we have presented here can be viewed as instance of learning rules with aggregates from knowledge graphs. This is an active area of current research, and our work here is significant in connection to this area in that we present one of the first methods for learning rules using (a limited form of) such aggregates. However, the discussion requires substantial additional notation in order to be concrete, and so we defer this discussion to Appendix A

---

Published as a conference paper at ICLR 2020
Dataset
[R]
[Km
19n
19
19
FBI5K 237Num
12493
237
116
27899
82992
10359
DBPI5K
12867
278
251
48105
79345
9789
Numericall
1000
2
1
1000
5785
98
Numerical2
1000
3
2
2000
5800
100
Table 1: Dataset statisties, where G. stands for the KG corresponding to the testset.
5 EXPERIMENTAL RESULTS
In this section we report the results of our experimental evaluation, which focuses on the effective- ness of our method against the state-of-art rule learning systems with respect the predictive quality of the learned rules. Specifically. we conduct experiments on a canonical knowledge graph comple- tion task as described in Yang al. (2017). In this task, the query and tail are given the algorithm, and the goal is to retrieve the related head. For example, if supervisorOf (turing, church) is not present in the knowledge graph, then when presented with the relation supervisorOf and the entity church, the goal is to exploit the existing triples in the KG to retrieve turing. In order represent the query as a continuous imput to the neural controller, for each query we learn the embedding of the lookup table. As in Yang et al. (2017), the embedding has dimension 118 and is randomly initialized to unit norm vectors. The only difference between the parameters of the Neural-LP and our system that we set the learning rate 10 while in Yang al. (2017) it is set 10-3, but both systems are run to convergence, and this learning rate does not affect the final performance materially except for making converge faster. all cases, we extracted rules with maximum length of 5.
5.1 EXPERIMENTAL SETUP
Datasets. To evaluate and compare our approach for learning numerical rules, we considered the following datasets containing knowledge graphs:
FB15K-237-num is a variant of Freebase knowledge graph with numerical values, where the reverse relations have been removed (Garcfa-Durán & Niepert (2088).
DBPediaJ5K is fragment of the DBPedia knowledge graph Lehmann al. (0115) stricted to numerical facts Saariia-Duráa & Niepert (2018).
Numericall synthetic dataset with 1000 entities, each containing a single numerical value (generated uniformly from to 1000). Each entity has 50 randomly-chose neigh- bors, and the goal is to find neighbors with the closest value the current entity given the constraint that the neighbor's value must be higher.
Numerical2 is a variant of the Numericall dataset, where each entity has two numerical values, "balance" and "debt"; under the same generation process above, the goal is to find neighbor of each node with the largest delta between balance and debt.
The statistics of the knowledge graphs used in our experiments presented in Table where apart from the number of KG entities (IC)), facts (lG)) and the size of the test set (G,), we also report the number of numerical relations ([R,)) ) and numerical facts (GG,.). We use 80% of the KG as the training set, and 10% for test set and the same for validation. The KG is split randomly with the constraint that only non numeeriallll facts appear in the test set, since we do not learn rules capable of predicting missing facts over numerical entities.
Baselines. We compared our proposed approach, which we refer to as Neural-Num-LL against the following two baselines:
3 (Mellicke et al. (2019) is an anytime bottom-up method for learning Horn rules, i.e. rules with only positive atoms and no comparison operators. To tune the system we use the default parameters as described on the system webpage and set the timeout to 5000 seconds.
Neural-LF Yang et al. 2017 is a differential rule learning system described in Section
7

---

Published as a conference paper at ICLR 2020
Numerical1
Numerica12
HB15K -2mmmmmm
DBPI5K
num
Dataset
@it@ 10
MRR
@it@ 10
MRR
@it@ 10
MRR
Hit@ 10
MRR
AnyBurl 0.031
0.009
0.685
0.509
0.426
0.244
0.522
0.371
Neural-LP
0.240
0.295
0.362
0.240
0.436
Neural-Num-LPP 1.000
0.941
1.000
0.837
0,415
0.259
0.682
0.451
Table 2: Comparing our approach against current state-of- oh------ttttttttt- rule learning methods. annotated entries obtained from Yang al. (2017).
prefer(X X, Y) neighbour (X, Y) ATT ThasOnter (X, YY)J(Y)
p2: prefer(X, Y) + neighbour( X, K Y) A f(Y) hosBalance , 22) A borrowed Y, Z2)
symptom Has Risksooootsr X, Y) + f(x) A symptom OffrstsseODDissse((X 7)A
Rask
Y)
defends(X, (x, Y) < ministerrOfDeeenee(XX Z) A f(Z) A miiterrgrracchO/Connnrzz/
Table 3: Example rules generated by Neural-I.P-N on the DBPedial 5K knowledge graph. See text. for discussion of these rules.
Following the common practice Meilicke et al. (2019); Yang et al. (2017) we compute the standard evaluation metrics used for the link prediction task Bordes et al. ( Hir@ 10, the number of correct head terms predicted out of the top 10 predictions; and mean reciprocal rank (MRR), the mean of one over the rank of the correct answer in the list of predictions. We have implemented our approach for learning numerical rules from knowledge graphs in python using the Py Torch library, and conducted all experiments on machine GTX 1080 TO GPU with 11 GB RAM.
5.2 RESULTS
In Table we report the quality of predictions obtained by our method and the baselines. Since the Neural-LP framework Yang et al. (2017) cannot handle the Freebase with numerical information, we present the results for FB15K-237 without numerical facts instead, which are taken from Yang ct al. (017)) The MRR values missing for Neural-LP in several places, as the implementation provided by the authors does not have the respective function implemented.
As expected, on the synthetic datasets Numericall and Numerica/2, method significantly out- performs the baselines. This is natural, since these datasets are constructed so that reasoning about numerical attributes is required for almost any prediction task presented the algorithms. And notably, the proposed approach is able to achieve 100% Hit@ 10 rates, as it is able to correctly iden- tify these relevant numerical properties. This contrasts to the baseline Neural-LP approach, which is unable to incorporate such information, and thus predicts the heads of each relation more or less ran- domly. The datasets are also particularly challenging for AnyBURL, because AnyBURL treats each numerical value as an independent entity, and thus cannot perform efficient comparative reasoning.
Most compellingly, however, similar observations can be made about the real-world datasets as well. Indeed, since all entities in the KG including numerical ones are treated equally by the avail- able systems, intuitively both AnyBurl and Neural-LP try to find frequent patterns in KGs, and use these to predict the missing facts. The numerical rules mined by our system are much more pressive and substantially improve the performance of the approach in some cases. Specifically, method outperforms the Neural-LP approach in terms of all metrics on both the FB15K-237- num and DBPedial 5K datasets. The AnyBURL dataset is still competitive with our approach on the 1B855-2377-mn dataset (better in terms of @it 10 but worse in terms of MRR), but our ap- proach substantially outperforms it on the DBPedia 15K, where our reasoning involving numerical comparison is able substantially improve upon the existing methods.
Examples of extracted rules. In Figure 3 we present examples of the rules learned by our system. In particular, the rules r², and ,2 have been extracted from the datesets Numericall and Numer- ical2 respectively, the rule 3 from FB15K-237-mun For example, r is the rule with a comparison operator, which states that a person X prefers neigh- bours with the maximal order that is less than X's. The rule r3 reflects that symptoms with certain properties (described by the function f) typically provoke risk factors inherited from diseases which have these symptoms. Here, the function f is the sigmoid over linear combination of numerical
and the rest of the rules from DBPedia 155..
8

---

Published as a conference paper at ICLR 2020
properties of X. Finally, r states that prime ministers of countries with certain numerical properties (described by the function f), are supported by military branches of the given country. Here, the function f is again the sigmoid over linear combination of numerical properties of Y.
6 CONCLUSION
In this paper we have addressed the problem of learning numerical rules from large knowledge graphs. Especially we have considered rules, where in the rule bodies numerical comparison oper- ators and aggregates (i.e. external oracle queries) that enable us to aggregate numerical properties of entities are allowed. The Neural-LP method is a recent appealing learning approach based on TensorLog; however it does not support numerical rules, they would result in dense matrix operations. We have introduced an extension the Neural-LP framework that allows for learning such rules from KGs by efficiently expressing comparison and classification operators, negation as well as multi-atom symbol matching. We have shown that our proposed extension outperforms pre- vious techniques that do support numerical information with respect the quality of predictions that they produce. The future research might focus on a further extension of our current approach by allowing for more general rule forms with complex external computations as well as rules with existential variables in the head.
ACKNOWLEDGMENTS
Authors would like to thank Christian Meilicke for his support with adjusting the parameters of the AnyBurl package as well as anonymous reviewers for their invaluable feedback.
REFERENCES
Sören Auer, Viktor Kovtun, Manuel Prinz, Anna Kasprzik, Markus Stocker, and Maria-Esther Vidal. Towards a knowledge graph for science. In Proceedings of the 8th International Conference on Web Intelligence, Mining and Semantics, WIMS 2018, Novi Sad, Serbia, June 25-27, 2018, pp- 1:1-1:6, 2018.
Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-reaationl data. In NeurlPS, pp. 2787-2795, 2013.
William W. Cohen, Fan Yang, and Kathryn Mazaitis. Tensorlog: Deep learning meets probabilistic 2017.
dbs. CoRR,
Thomas Eiter, Michael Fink, Thomas Krennwallner, and Christoph Redl. Conflict-driven ASP solv- ing with external sources. TPLP, 12(4-5)x699-67, 2012.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. JAIR, 61: 1-64, 2018
Wolfgang Faber, Gerald Pfeifer, and Nicola Leone. gates in answer set programming. Artif. Intell., 175(1):278-298, 2011.
Semanties and complexity of recursive aggre-
Luis Galárraaa and Fabian M. Suchanek. Towards numerical rule mining language. AKBC, 2014.
Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M. Suchanek. Fast rule mining in ontological knowledge bases with AMIE+. VLDB, volume 24, pp. 707-730, 2015.
Alberto Garefa-Durán and Mathias Niepert. Kbirn: End-to-end learning of knowledge base repre- sentations with latent, relational, and numerical features. In UAI, pp. 372-381, 2018.
Vinh Thinh Ho, Daria Stepanova, Mohamed H. Gad-Elrab, Evgeny Kharlamov, and Gerhard Weikum. Rule learning from knowledge graphs guided by embedding models. In ISWC, pp- 72-90, 2018.
Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. Db- pedia large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web, 6: 167-195, 2015.

---

Published as a conference paper at ICLR 2020
Robin Manhaeve, Sebastijan Dumancie, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In NeurIPS, pp. 3753-3763 2018.
Christian
Meilicke, Melisachew Wudage Chekol, Daniel Ruffinelli, and Heiner Stuckenschmidt. Anytime bottom-up rule learning for knowledge graph completion. In Proceedings of the Twenty- Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, Au- gust 10-16, 2019, pp. 3137-3143, 2019.
Stephen Muggleton. Inductive logic programming: Inverse resolution and beyond. IJCAI (I), pp. 997. Morgan Kaufimann 1995.
Maximilian Nickel, Volker Tresp. and Hans Kriegel. A three-way model for collective learning on multi-rclational data. In JCML, pp. 809-816, 2011.
Stefano Ortona, Venkata Vamsikrishna Meduri, and Paolo Papotti. Robust discovery of positive and negative rules in knowledge bases. In ICDE, pp. 1168-1179 IEEE Computer Society, 201 8a.
Stefano Ortona, Venkata Vamsikrishna Meduri, and Paolo Papotti. Rudik: Rule discovery in knowl- edge bases. PVLDB, 11(12)1196-11999 2018b.
Luc De Raedt. Multi-relational data mining. In Encyclopedia of Machine Learning and Data Mining, pp. 892-893, Springer, 2017.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In NeurlPS, pp. 3791- 3803, 2017.
Celine Vens, Jan Ramon, and Hendrik Blockeel. Refining aggregate conditions in relational learning. In PKDD, volume 4213 of Lecture Notes in Computer Science, pp. 383-398-- Springer, 2006.
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE Trans. Knowl. Data Eng., 29(12):2724-217) 2017.
Leon Weber, Pasquale Minervini, Jannes Münchmeyer, Ulf Leser, and Tim Rocktäschel. NIprolog: Reasoning with weak unification for question answering in natural language. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2019, Volume Long Papers, pp. 6151-6161 2019.
Fan Yang, Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowl- edge base reasoning. In NeurlPS, pp. 2316-2325, 2017.
Wen Zhang, Bibek Paudel, and et al. Liang Wang. Iteratively learning embeddings and rules for knowledge graph reasoning. WWW, pp. 2366-2377. ACM, 2019.
A INTERPRETATION AS RULES WITH EXTERNAL COMPUTATIONS
We have presented our approach for learning rules that support numerical comparison among en- tities and classification of entities based on aggregation of their numerical features, and have also highlighted the algorithmic and numerical approaches to handling such rules.
In this Appendix we draw a connection between the rules of our focus and formalisms known in the knowledge representation community.
In the general case the rule features that we consider are inlined with logic rules that allow for exiernal computations, i.e. "oracle programs" that might appear in the body of the rules part of a generic black-box computation (in the spirit of answer set programs with external functions Eiter al. (2012)). In the case of simplest numerical comparisons, for example, the corresponding oracle may check whether some numerical feature of one entity is larger than some numerical feature of another one. In more complex setting oracle may aggregate numerical features of entity by computing their linear combination, and compare the result with a certain value.
Since the rules that be characterized as restricted explainable structures simultaneously supporting symbolic and sub- symbolic representations and inference. Learning such structures is long-standing and important
targeting account both for relational and numerical information, they can
10

---

Published as a conference paper at ICLR 2020
goal of artificial intelligence, which has recently gained special attention (see e.g.. Manhaeve et al. 2018); Weber et al. ; Rocktäschel & Riedel (2017); Evans & Grefenstette (2018).
The challenge of learning such rules with aggregates is also central in much work on KGs Galárraga Suchanek (2014). Indeed, discovering patterns by learning rules from knowl- edge graphs enables obtain concise descriptions of domain well as complete and clean the data. Especially by considering numerical values such as age, weight or experimental measure- ments, which are common, e.g., for scientific knowledge graphs Auer al. (2018), learned rules might reveal interesting correlations in the data or even lead to scientific discoveries.
Our proposed procedure is the first approach that is capable of learning such rules (even though of course do not allow for arbitrary aggregates, the fact that we incorporate such learning at all is substantial contribution the KG literature). Because this a key capability of our approach, in this section we further formally present the exact structure of the rules that we support and illustrate them by examples, motivating their applicability various scenarios. The notation and definitions here are not crucial for understanding the remainder of the paper, but will provide context and clarify the contribution of the current work from the perspective of the knowledge representation community.
A.1 RULES WITH AGGREGATES
We consider aggregate atoms of the form J(Y1, Yn: PI (X,)). P. o Z, where aggregate function symbol, (Y1...., Yn element, o E { and Z is a numerical value. For any aggregate the above form we assume that pl; pı..... . Pn RR,, i.e., Ply.... - Pn numerical features of an entity X.
.... (x, Y)} is called aggregate
Example 2. The aggregate element {Y,, Yg: citedIn(X, Y1). AmgleAuthorArticdle notes the numerical feature vector containing & = (Y, Y2), where Y1 is the number of citations X has, and Y2 is the number of articles with X being single author.
Ye)} de-
The function f can in principle be arbitrarily complex and can be even represented by neural network. In our work, as a starting point we restrict ourselves to linear functions of the following form: sigmoid w T +p + b), where ip is the respective numerical feature vector for the target entity X.
Example 3. Reconsider the knowledge graph in Figure D extended with the facts 6), Artttrrre
singleA Arthcrt has Ciasalaaio X, Yi), single uuthor (X, Y2)) > 0.5, with I being the sigmoid function of the above form, suppose that w = (1, 10) and b = 200. We have = (50, 6) for X = pele and * (124, 8) for X john. Since 50 + 10 200 < 0.5, for pele the respective aggregate atom evaluates to false, while for john it is true, which is easy to verify based on analogous computations.
20). For the aggregate f(Y1, Y2 :
In this work we have described procedures for learning rules that have the following form
p(X, + 2 (X, 2 A A qa (Zn, Y).
44)
where pı (Y, X) is an atom, and every (Y, 2,)..... .... XZ, is either an atom, a negated atom, an aggregate atom of the form f(Y Yn with pI,.. E Rn, and being a sigmoid function or it is comparison concunction of the form
(X,, Y "m)....,Pw..
Yn)} 0.5, {z,>} >}
(2,)) + P(Z,N) A ((Y
M.
where o E [5 and Y, Z are present in some rule body atom elsewhere.
As described in Section above condition that Y, Z must be connected via some relation ensures that the entities that participate in the comparison semantically related to each other, which is needed to avoid irrelevant comparisons.
Example 4. Consider the following rule
(2 +f(Y,, Yg has CisCiiitinn(X, Yr), singeedutttorrrrtrreeeess../ Y2)} > 0.5A Supervisor X, 2) A affiliated With (2, 2').
Intuitively, the aggregate function computes a certain index for a person based on the number of his citations and the number publications, with him being single author. The rule states that people
11

---

Published as a conference paper at ICLR 2020
with index above certain threshold supervise only top students of the university with which they are affilliated.
The following expression demostrates rule with comparison atom:
influences(X, (X, Y) + colleague (X, Z) A supercisorOf (Z, Y)A hasCitation X, N) A hasCitation Z, M), N > M.
This rule states that students rypically influenced by colleagues their supervisors with higher number of citations. The expression r "assCttation" (Y, 7) can be used shortcut for the last three atoms in the body of the above rule.
A.2 EXECUTION OF RULES WITH AGGREGATES
The execution of rules with negation and aggregates that we focus on is defined the standard way Faber et al. (201) 1); Eiter et al. (2012) for details). More precisely, let G be KG, rule over G, and a be a standard atom from G. Then, rule 1 a holds there a variable assignment that maps G such that it does not map any the atoms in
atoms in the positive part of rule body (body the negative part of rule body (bodyruie) in G. For aggregate atoms a we have that rule kg a if the value of the respective aggregate function the KG satisfies the given incquality constraint.
G. = G {al r Fg a} extends with atoms derived from G by applying т. Note that to avoid propagating uncertain predictions, given set of rules R we execute every rule in R on G indepen- dently, i.e. GR = UPER Gy. Given additional syntactic restrictions on rules in R, which disallow eycles through negation consistency is ensured.
12


Reviews:
[{"review_id": "SJx_7NveqH", "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 proposes an extension of NeuralLP that is able to learn a very restricted (in terms of expressiveness) set of logic rules involving numeric properties. The basic idea behind NeuralLP is quite simple: traversing relationships in a knowledge graph can be done by multiplicating adjacency matrices, and which rules hold and which ones don't can be discovered by learning an attention distribution over rules from data.\n\nThe idea is quite clever: relationships between numeric data properties of entities, such as age and heigh, can also be linked by relationships such as \\leq and \\geq, and those relations can be treated in the same way as standard knowledge graph relationship by the NeuralLP framework.\n\nA major drawback in applying this idea is that the corresponding relational matrix is expensive to both materialise, and use within the NeuralLP framework (where matrices are mostly sparse). To this end, authors make this process tractable by using dynamic programming and by defining such a matrix as a dynamic computation graph by means of the cumsum operator.  Furthermore, authors also introduce negated operators, also by defining the corresponding adjacency matrices by means of computation graphs.\n\nAuthors evaluate on several datasets - two real world and two synthetic - often showing more accurate results than the considered baselines.\n\n\nOne thing that puts me off is that, in Table 2, AnyBurl (the single one baseline authors considered other than the original NeuralLP) yields better Hits@10 values than Neural-LP-N, but the corresponding bold in the results is conveniently omitted.\n\nAnother concern I have is that the expressiveness of the learned rules can be somehow limited, but this paper seems like a good star towards learning interpretable rules involving multiple modalities.\n\n\nMissing references - authors may want to consider citing https://arxiv.org/abs/1906.06187 as well in Sec. 2 - it seems very related to this work.\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 thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1eJGUy6Yr", "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": "This paper proposes an interesting extension to the Neural LP framework for learning numerical rules in knowledge graphs. The proposed method can handle predicates involving the comparison of the numerical attribute values. The authors demonstrate its effectiveness on both synthetic knowledge graphs and the parts of existing knowledge graphs which consider numerical values.\n\nI recommend the paper to be rejected in its current form for the following 3 reasons:\n\n(1) Although the idea of making numerical rules differentiable is interesting, the current proposed method can only deal with one form of numerical predicate, which is numerical comparison. The limitation to such a special case makes the paper somewhat incremental. \n\n(2) The paper does not do a great job of convincing the reader that the problem it is trying to solve is an important matter, or the proposed method is indeed effective in some applications. Although the proposed method does a good job in synthetic experiments, outperforming existing methods by a large margin, its performance on the numerical variants of Freebase/DBPedia dataset does not show consistent significant improvement. The authors should try to find a real-world domain which can really demonstrate the effectiveness of the method.\n\n(3) The experiment section lacks more detailed analysis which can intuitively explain how well the proposed method performs on the benchmarks. A good place to start with is to visualize(print out) the learned numerical rules and see if they make any sense. The experiment section needs significant improvement, especially when there is space left.\n\n\nThe authors can consider improving the paper based on the above drawbacks. I encourage the authors to re-submit the paper once it's improved. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJekrJ9atS", "reviewer": "AnonReviewer1", "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 proposed several extensions to the Neural LP work. Specifically, this paper addresses several limitations, including numerical variables, negations, etc. To efficiently compute these in the original Neural LP framework, this paper proposed several computation tricks to accelerate, as well as to save memory. Experiments on benchmark datasets show significant improvements over previous methods, especially in the case where numerical variables are required. \n\nI think overall the paper is written clearly, with good summarization of existing works. Also I like the simple but effective tricks for saving the computation and memory.\n\nOne main concern is, how general this approach would be? As it is a good extension for Neural LP, it is not clear that the framework of Neural LP is flexible or powerful enough in general. For example, if rules contain quantifiers, how would this be extended? \n\nMinor comments:\n\n1) 4.1,  “O(n^2/2)” -- just put O(n^2) or simply write as n^2/2.\n2) How are the rules from in Eq (2)? i.e., how is \\beta_i selected for each i? In the extreme case it would be all the permutations.\n3) I would suggest a different name other than Neural-LP-N, as it is somewhat underselling this work. Also it makes Table 2 not that easy to read.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a number of improvements on existing approaches to neural logic programming. The reviews are generally positive: two weak accepts, one weak reject. Reviewer 2 seems wholly in favour of acceptance at the end of discussion, and did not clarify why they were sticking to their score of weak accept. The main reason Reviewer 
 1 sticks to 6 rather than 8 is that the work extends existing work rather than offering a "fundamental contribution", but otherwise is very positive. I personally feel that
a) most work extends existing work
b) there is room in our conferences for such well executed extensions (standing on the shoulders of giants etc).

Reviewer 3 is somewhat unconvinced by the nature of the evaluation. While I understand their reservations, they state that they would not be offended by the paper being accepted in spite of their reservations.

Overall, I find that the review group leans more in favour of acceptance, and an happy to recommend acceptance for the paper as it makes progress in an interesting area at the intersection of differentiable programming and logic-based programming.
Decision: Accept (Poster)