LPRules: Rule Induction in Knowledge Graphs Using Linear Programming
Authors: Sanjeeb Dash
Joao Goncalves
Venue: ICLR 2022 Submitted (2022)

Abstract: Knowledge graph (KG) completion is a well-studied problem in AI. Rule-based methods and embedding-based methods form two of the solution techniques. Rule-based methods learn first-order logic rules that capture existing facts in an input graph and then use these rules for reasoning about missing facts. A major drawback of such methods is the lack of scalability to large datasets. In this paper, we present a simple linear programming (LP) model to choose rules from a list of candidate rules and assign weights to them. For smaller KGs, we use simple heuristics to create the candidate list. For larger KGs, we start with a small initial candidate list, and then use standard column generation ideas to add more rules in order to improve the LP model objective value. To foster interpretability and generalizability, we limit the complexity of the set of chosen rules via explicit constraints, and tune the complexity hyperparameter for individual datasets. We show that our method can obtain state-of-the-art results for three out of four widely used KG datasets, while taking significantly less computing time than other popular rule learners including some based on neuro-symbolic methods. The improved scalability of our method allows us to tackle large datasets such as YAGO3-10.

LPRULES: RULE INDUCTION IN KNOWLEDGE GRAPHS USING LINEAR PROGRAMMING
Anonymous authors Paper under double-blind review
ABSTRACT
Knowledge graph (KG) completion is a well-studied problem in AL. Rule-based methods and embedding based methods form two of the solution techniques. Rule- based methods learn first-order logic rules that capture existing facts in an input graph and then use these rules to reason about missing facts. A drawback of such methods is the lack of scalability to large datasets. We present a simple linear programming (LP) model to choose rules from list of candidate rules and assign weights to them. For smaller KGs, we use simple heuristics to create the candidate list. For larger KGs, we start with a small initial candidate list, and then use column generation to add more rules in order to improve the LP model objective value. To foster interpretability and generalizability. we limit the complexity of the set of chosen rules via explicit constraints, and tune the complexity hyperparameter for individual datasets. We show that our method can obtain state-of-the-an results for three out of four widely used KG datasets, while generating compact rule sets and taking significantly less computing time than other popular rule learners, including some based on neuro-symbolic methods. The improved scalability of our method allows us to tackle large datasets such as YAGO3-10.
INTRODUCTION
Knowledge graphs (KG) are used to represent a collection of known facts via labeled directed edges. Each node of the graph represents an entity, and a labeled directed edge from one node to another indicates that the pair of nodes satisfies a binary relation given by the edge label. A fact in the knowledge graph a triplet of the form (a, b) where a and b are nodes, and r is binary relation labeling directed edge from a to b indicating that r(a, b) is true. Consider a KG where the nodes correspond to distinct cities, states, and countries and the relations are one of capital of. shares_bar border_withh or part_of. A fact (a, part_ef. b) in such a graph corresponds to a directed edge from a to b labeled by part_ of implying that a is a part of b. Practical knowledge graphs are often incomplete (they do not contain all true representable facts) and noisy (they have inconsistencies or errors). Knowledge graph completion (KGC), triple classification, entity recognition, and relation extraction are common tasks for extracting implied information from KGs. See Di et al. (2021) for recent survey on KGs. KGC involves using known facts in a KG to infer additional (missing) facts. One approach for KGC learn first-order logic rules that encode known facts.
In the example above, we could learn a "rule" capital_ofixi that take on entity values. Then if we find a pair of entities P.Q such that (P, capital of. Q) is fact in the graph, we could infer that (P, part_ of Q) is also true and augment the set of facts with this new fact if not originally present. A more complex rule of length two is capital oft Y) and purt_of( Yo.) + parrt_f((X,] a fact in the graph, and so is part_oftR, R, Q), then we infer that is part of Q. KG link prediction deals with finding answers to queries of the form part_ of(P, ?), and we focus on finding first-order logic rules of the type above for this task. Instead of learning one rule for a relation, it is common to learn set of rules along with rule weights, where larger weights indicate more important or more certain rules. Dealing with uncertainty or noise is essential for KG reasoning.
+ of where X, Yare variables
Again, applying it to entities P and Q, if there exists third entity R
such that capital_oftie
Learning logic rules is well-studied area. In paper (Lao & Cohen 2010) on path ranking algorithms and another (Richardson & Domingos 2006) on Markov logic networks, candidate logic rules are obtained via relational path enumeration, and then rule weights are calculated. Yang et al. (017))

---

use neural logic programming to simultaneously obtain sets of rules and the weights of individual rules. Quu et al. (2021). separately find rules and rule weights, but add a feedback loop from the latter learning problem to the former. The use of recursive neural networks (RNN) to learn rules is common nowadays, though traditional rule-mining approaches remain popular (Meilicke et al. 2019).
Embedding- methods for KGC consist of representing nodes by vectors, and relations by vector transformations that are consistent with the facts in the knowledge graph. They exhibit better scaling with KG size, and yield more accurate predictions. See the surveys by Ji et al. (2021) and Wang et al. 2017). On the other hand, rule-based methods can yield more interpretable explanations of associated reasoning steps (Qu & Tang 2 rules and few relations per rule). Furthermore, especially if one obtains compact rule sets (with few setity-ideeeeddmm rules are more generalizeable (Teru al. 2020) and can be applied in an inductive setting: they can be applied to entities not considered in the learning process. Embedding- basee methods work mostly in a transductive setting.
We propose a novel approach to learning entity- inteeedend,, weighted first-order logic rules for knowledge graph reasoning. Our approach combines rule enumeration with linear programming (LP), and completely avoids the solution of difficult nonconvex optimizaton models inherent in training RNNs. We describe linear programming (LP) formulation with exponentially many variables corresponding to first-order rules and associated weights. Nonzero variable values correspond to chosen rules and their weights. We deal with the exponential number of variables/rules by column generation ideas from linear optimization, where we start off with some small initial set of rules and associated variables, find the best subset of these and associated weights via the partial LP defined on the initial set of rules, and then generate new rules which can best augment the existing set of rules. Our final output rule-based scoring functions resemble those in NeuralL (Yang al.) 2017). DRUM (aadeghian et al., 2019), and RNNLogic (Qu et al. 202T) in that we form a linear combination of rule scores (calculated differently from the above papers). As in RNNLogie, our iterative process of adding new rules is influenced by previous rules.
Our algorithm has better scaling with KG size than a many existing rule-based methods. In addition, we obtain state-of-the-an results on three out of four standard KG datasets while taking significantly less running time than some competing codes. Furthermore, we are able to obtain results of reasonable quality- when compared to embedding- -baed methods- on YAGO3-10. 10. large dataset which is difficult for existing rule-based methods. As an important goal of rule-based methods is to obtain interpretable solutions, we promote interpretability by adding constraint in our LP formulation limiting the complexity of the chosen rule set (and this hyperparameter is tuned per dataset). In some cases, obtain more accurate results (higher MRR) for the same level of complexity as other codes, and less complex rules for the same level of accuracy in other cases.
RELATED WORK
2.1 RULE-BASED METHOOSS
There is rich body of literature on rule-based methods for knowledge graph reasoning. The motiva- tion for learning rules is that they form an explicit symbolic representation of existing knowledge and are amenable to inspection and verification. Further, compact rule sets are interpretable, an efficient way to store knowledge, and useful for transfer learning. For KG applications, when rules are entity- indeeeden,, they can be used in an inductive setting (Yang et al. (2017) Teru et al. (2020).
Inductive Logic Programming (ILP). In this approach, one takes as input positive and negative examples and learns logic programs that entail all positive examples and none of the negative examples. See for example Cropper& & Muggleton (2016) and anopprr & Morel ( (2020). First-order Logic (FOL.) programs in the form of a collection of chain-like Horn clauses are popular output format. Negative examples are not available in typical knowledge graphs, and some of the positive examples can be mutually inconsistent. [vvan & Grefenstette (2018) developed a differential ILP framework generate rules for noisy data.
Statistical Relational Learning (SRL). SRL aims to learn FOL formulas from data and to quantify their uncertainty. Markov logic, which is probabilistic extension of FOL, is a popular framework for SRL. In this framework, one learns a set of weighted FOL formulas; see, for example, Kok & Domingos 2005) where beam search is used to find set of FOL rules, and rule weights are learned
2

---

via standard numerical methods. In knowledge graph reasoning, chain-like rules which correspond to relational paths (and to chain-like Horn clauses) are widely studied. In & Cohen (2010). a
weighted linear combination of rule-based functions (e.g., the function could return probability that the rule implies a link between a pair of entities) is used as a scoring function for KG link completion. An initial set of rules is created and the weights are obtained via regression. A recent, bottom-up rule-lcarning algorithm with excellent predictive performance is AnyBURL (Meilicke et al. (2019) We learn FOL rules corresponding to relational paths and rule weights; our scoring function, and learning model/algorithm are different from prior work.
The column generation aspect of our work has similarities to cutting plane inference methods (Riedel 2008 Noessner et al. 2013) for MAP inference in SRL. While we deal with an exponential number of possible rules/Horn clauses via column generation, the above papers use constraint generation/cutting plane ideas to deal with an exponential number of constraints corresponding to ground clauses.
Neuro-symbolic methods. In NeuralLP (Yang et al., 2017). rules and rule weights are learned simultaneously by training appropriate RNN. Further improvements in this paradigm can be found in DRUM (Sadeghian et al. (2019). Another neuro-symbolic approach is implemented the Neural Theorem Prover (NTP, Rochstätel & Riedel
[iedel (2017)) More general rules (than the chain-like rules found NeuralLP) are obtained in NLIL (Yang & Song) along with better scaling behavior. Simultaneously solving for rules and rule- tule-weights is difficult, and natural question is how well the associated optimization problem can be solved, and how scalable such methods are. We use an easier-to-solve LP formulation.
Hybrid methods. In RNNLogic (Qu al. 2021). the rules are generated using an RNN, and rule weights are later calculated via a probabilistic model. Such separation of rule generation and weight calculation can be found in earlier work (e.g.. Kok & Domingos 2005)), but in RNNLogic new rule generation is influenced by the calculated weights of previously generated rules. Our column generation method and AnyBURL have the same property.
Reinforcement Learning, Recent attempts use reinforcement learning (RL) to search for rules can be found in MINERVA (Das et al., (2188), MultiHopKG (Lin et al. 2018). M-Walk (Shen et al. 2018) and DeepPath (Xiong et al. 2017 7). The first three papers use RL to explore relational paths conditioned on a specific query, and use RNNs to encode and construct graph-walken agent.
Rule types/Rule combinations. AnyBURL generates rules corresponding to different types of paths (acyclic or cyclic, in their notation) which may be -epty-de or independent. As mentioned before, NI.II goes beyond simple chain-like rules. Recently Teru et al. (2020) use subgraphs to perform reasoning, and not just paths. We generate weighted, intii--indeeendent, chain-like rules as in NeuralLP. Our scoring function combines rule scores via a linear combination. For a rule r and a pair of entities a, b, the rule score is just 1 if there exists relational path from to following the rule r and 0 otherwise. We use rule weights as a measure of importance but they are not probabilities. For Neural LP, DRUM, RNNLogic and other comparable codes, the scoring functions depend on the set of paths from a to associated with r. Finally, AnyBURL uses maximum confidence scores rather than sums of confidence scores; further, its scoring function returns vector of sorted scores, and two score vectors are compared lexicographically.
Scalability/Compac Rule sets. As noted above, many recent papers use RNNs in the process of finding chain-like rules and this can lead to expensive computation times. On the other hand, bottom-up rule-learners such as AnyBURL are much faster. The main focus of our work is obtaining compact rule sets for the sake of interpretability while maintaining scalability via LP models and column generation. We impose explicit constraints to maintain compactness, and these constraints influence new rule generation. The new rules must perform well with previously generated/selected rules. Neurall., for example, usually returns compact rule sets while AnyBURL returns a very large number of rules (and does not prune discovered rules for interpretability), and RNNLogic is somewhere in between (though the number of output rules can be controlled).
2.2 EMBEDDING-BASED METHODS
An alternative approach to KG reasoning is based on embedding entities and relations in the KG into (possibly different) vector spaces. For example, suppose one finds a vector v, E R for each node in the knowledge graph and function T, R -> RR* for each relation r such that T, (v.v)) tb
3

---

whenever (a, r, b) is fact in the graph. Then, for a pair of entities and b, one could assert that
ra, b) is a fact (assuming it is not present in the graph) if T., (2)) = Db. Well known papers in this
area are Sun et al. (2019), Bordes et al. (2013), Dettmers al. (2018). Lacroix et al. (2018 Trouillon
et al. 2016), Balažević et al. 2019). Nayyeri et al. (2021). and Chami et al. (2020).
There number of papers which combine embeddings and rules in different ways. In rule-injected embedding models such as RUGE (Guo et al. 2018), LogicENN (Nayyeri et al., (211). and ComplEx- NEE-AER (Ding et al. 2018), the goal is obtain embeddings that are consistent with prior rules (known before the training process). On the other hand, RNNLogic combines rules and embeddings to give more precise scores to candidate answers to queries of the form (a, ?). In others (Lin et al. 2018). information from embeddings is used to obtain better rules.
Though embedding- bastn methods are better than most rule-based methods, AnyBURL is a fast rule-based method with comparable predictive performance to embedding based methods. However, AnyBURL resembles embedding- based methods in that the output KG representation has explicit entity dependence (the generated rules have constants which are often entities).
3 MODEL
We propose a linear programming model inspired by LP boosting methods for classification using classical column generation techniques (Demiriz al. 2002] Golderg [012 [Eckstein & Goldberg
2012. Eckstein et al.] 2019 Dash et al. 2018). Our goal is to create a weighted linear combination of first-order logic rules to be used as a scoring function for KG link prediction. In principle, our model has exponentially many variables corresponding to the possible rules, but our solution approach uses column generation to deal with this issue. We start with few initial candidate rules, find important rules and associated weights, and then generate additional rules that have the potential to improve the overall solution. Previously generated rules influence the generation of new rules (as in RNNLogic).
Let V be set of entities, and let R be set of n binary relations defined over the domain V. A knowledge graph represents a collection of facts FF C V R x V as a labeled, directed multigraph G. Let J = {(1' r'", J+f) ; = 1,....FF [F] where 1 + ht E V, and r' E R. The nodes of G correspond to entities in F and the edges to facts in F: if (1, h) is a fact F, then G has a directed edge (f, f)) labeled by the relation r. depicted as t + h. Here is the tail of the directed edge, and is the head. We let E stand for the list of directed edges in G. For each fact (t, r, h). we say that r(h, 1) is true. Practical KGs are assumed to be incomplete: missing facts that can be defined over V and R are not assumed to be incorrect. The knowledge graph link prediction task consists of taking a knowledge graph as input, and then answering a list of queries of the form (t, r, ?) and (?, r, h)), constructed from facts (t, r, h) in a test set. The query (1, r. ?) asks for head entity h such that (f, r, h) is fact, given tail entity i and relation r. A collection of facts F is divided into training set Ftr. a validation set F,,, and a test set Fre, the KG G corresponding to For is constructed and scoring function (for link prediction) is learnt from G and evaluated on the test set.
Knowledge graphs:
Goal: For each relation r in G, find a set of closed, chain-like rules Ri...., Ry and positive weights Wi,... Wp where each rule R, has the form
(X, X1) A (2)
A Y) + +(X,Y).
(1)
Here 71, rI...., T1 are relations from R represented in G. and the length of the rule is l. The interpretation of this rule is that if for some entities (or nodes) X, of there exist entities X1.... X2 of such that Tı X1), 1) (X Y) and -X. X2)) are true for j = 2.... I - 1, then r(X, Y) is true. We refer to the conjunction of relations in ( as the clause associated with the rule R. Thus each clause C; is a function from V x V to (0, 1 and we define |Ca to be the number of relations in C,
Clearly, (X,YY) = 1 for entities X, Y in G if and only if there is relational path of the form
X 4 ... X 3 Y.
Our learned scoring function for relation r is simply
J( = Σ W; w,Ci(X,Y) for all X.Y Y V.
(2)
E
As discussed earlier, there are different ways to construct scoring functions from rules and rule weights. The linear nature of our scoring function is intimately linked to the of I.P learn
4

---

the function. Given query rt.r.?) constructed from fact (t, h) from the test set, we use the approach from Bordes et al. (2013) where the score fr (t, u) is calculated for every entity v E V. and the rank of the correct entity / is calculated from the scores of all entities in the filtered setting. We similarly calculate the rank of / for the query (?, r, h). We then compute standard metrics such as MRR (mean reciprocal rank), Hits @ Hits @its@3, and Hits @ 10. An issue in rank computation is that multiple entities (say e' and e²) can get the same score for a query. Different treatment of equal scores can lead to significantly different MRR values (Sun et al. 2020). See the Appendix. We use random break ranking (an option available in NeuralLP, where the correct entity is compared against all entities and any ties in scores are broken randomly.
New LP model for rule learning for KG Link Prediction. Let ICC denote the set of clauses of possible rules of the form 1 with maximum rule length L. Clearly, |/]] = where a the number of relations. Let E,, be the set of edges in & labeled by relation r. and assume that | = m. Let the ith edge in E, be (X,, Y.). We compute ag as 0g3 = Cx(X,, Y.): ag. is and only if there is a relational path associated with the clause C₁ from X; to Y,
Furthermore, let neg, be a number associated with the number of "nonedges" (X', Y') from (V x V) \ E, for which C (X', Y')= = 1. We calculate neg; for the kth rule as follows. We consider the tail node f and head node for each edge in E,.. We compute the set of nodes S that can be reached by a path induced by the kth rule starting at the tail. If there is edge from t to node in S labeled by r, we say that v is an invalid end-point. Let right, be the set of such invalid points. We similarly calculate the set left, of invalid start-points based on paths ending at h induced by the leth rule. The total number of invalid start and end points for all tail and head nodes associated with edges in Ex is neg,- = Iright,| + [left,l. For query of the form (f,r, r, ?) where is tail node of an edge in E,, the scoring function defined by the kth rule alone gives a positive and equal score to all nodes in right..
Our model for rule-learning is given below.
(LPR)
Zmin = min
The + neg, Wk
(3)
KEK
s.t.
Σ
ask wy + n 2 for all i E Ex
(4)
keK:
(Cal)ux I[++CCaluuR
(1+
SK
(5)
kEk:
W/ E [0, 1] for all E.
(6)
The continuous variable wP is restricted to lie in [0, 1] and is positive if and only if clause k E IC is a part of the scoring function (2). The parameter x is an upper bound on the complexity of the scoring function (defined the number of clauses plus the number of relations across all clauses). The variable τ): is penalty variable which is positive if the scoring function defined by positive w&s gives a value less than 1 to the ith edge in E,., Therefore, the En= Ths portion of the objective function attempts to maximize Σx1 min (X,, Y.), 1}. i..., it attempts to approximately maximize the number of facts in E, that are given a "high-score" of by fr. In addition, we have the parameter which represents a tradeoff between how well our weighted combination of rules performs on the known facts (gives positive scores). and how poorly it performs on some negative samples or "unknown" facts. We make this precise shortly.
Maximizing the MRR is a standard objective for KG link prediction problems and thus the objective function of LPR is only an approximation; see the next Theorem (the proof is given in the Appendix). In spite of this fact, we can obtain state-of- of-the-art prediction rules using LPR.
Theorem 1. Let IPR be the integer programming problem created from LPR by replacing equation T by wk E (0, 1} for all k E K. and letting T = O. Given an optimal solution with objective function value 7, one can construct a scoring function such that 1 2/m is a lower bound on the MRR of the scoring function calculated by the optimistic ranking method, when applied to the training set triples.
Assuming that the training set facts have similar distribution to the test set facts, the theorem above justifies choosing IPR as an optimization formulation to find a high-quality collection of rules for a relation, assuming MRR calculation via optimistic ranking.
5

---

However, we use random break ranking in this paper. It is essential to perform negative sampling and penalize rules that create paths when there are no edges in order to produce good quality results. This is why we use 7 > 0 in LPR. We will now give interpretation of Ee neg,, Wx- To compute the MRR of the scoring function fr in (2) applied to the training set, for each edge (t, h) E Eb we need to compute the rank of the answer for all nodes v in G - and the rank of answer t to the query r?,r, h) - by comparing fo (v,r, with (t, r, for all nodes v. But Ex neg, Wy is exactly the sum of scores given by fr to all nodes in right, and left, and therefore we have the following proposition.
the query (t, ?) by comparing (r,,,r,,) with fr,t,r, r))
Proposition 2. Let (t, h) be an edge in Er,, and let r(?,r,h) be the set of invalid answers for (3, r, bi) and let (t, ?) be the set of invalid answers to (t,r,?) in the filtered setting. Then
Σ
E f,(e,r,h)+ +
E b(b,,,))) (EU(S..:))
Σ KEK
neg, Wk-
(t.,,))EE (EEU(R,))))
In other words, rather than keeping individual scores of the form fr r, h) and fr(t, v) small, we minimize the sum of these scores in LPR.
It is impractical to solve LPR given the exponentially many variables wh, except when n and L are both small. For WNISRR (Dettmers et al. 2018), n is only 22 (WNISRR has 11 relations, but we introduce a reverse relation r- for each E R. and create rules that include reverse relations) and thus setting to 3 does not lead to too many variables. An effective way to solve such large LPs is to use column generation where only small subset of all possible wt variables is generated explicitly and the optimality the LP is guaranteed by iteratively solving a pricing problem. We do not attempt to solve LPR to optimality. We start with an initial set of candidate rules Ko c K. (and implicitly set all rule variables from IC \ KCo to O). Let LPR, be the associated LP. We solve LPRg, and then dynamically augment the set of candidate rules to create sets Kc; such that Ko C C C... C K.. If LPR; is the LP associated with IC; with optimal solution value 2t zin then it is clear that a solution _5-1 2-11 < mii. We attempt to have *min < = by of LPR; is a solution of L 1, and therefore zminn taking the dual solution associated with an optimal solution of LP,,, s, and then trying to find negative reduced cost rule, which we discuss shortly.
Setting up the initial LP. To set up Ko and the associated LPo. we develop two heuristics. In Rule Heuristic 1, we generate rules of lengths one and two. For length one rules, we create a one-relation rule from a relation in R \ {r} if labels large number of edges from tail nodes to head nodes of edges in E,. Similarly, to create rules of length two, we take each edge (X, Y) in E, and select the relations from edges (X, Z) in E E, and (Z,Y) in E to create a rule, again taking into account how frequently length two rule creates paths from the tail nodes to head nodes of edges in E,.
In Rule Heuristic 2, we take each edge (X, Y) F., and find a shortest path from X to Y contained in the edge set F \ {X. Y)} where the path length is bounded by pre-determined maximum length. We then use the sequence of relations associated with the shortest path to generate a rule. We also use path of length at least one more than the shortest path. Rules generated by any method (NeuralLP, DRUM, etc) can be used to set up Ko-
Adding new rules. Each set K₁ for > 0, is constructed by adding new rules to the set KC-11 We use a modified version of Heuristic 2 to generate the additional rules. In this version of the heuristic, we use the dual variable values associated with the optimal solution of LPR,-1- Let 8; 2 0 for all i E F, be dual variables corresponding to constraints (4). Let À < 0 be the dual variable associated with the constraint (5) Given a variable wa which is zero in solution of LPR, and associated dual solution values and X, the reduced cost red, for this variable is given by
redę = neg,
Σ and, (1 + (C&))
E.
If redg- < O, then increasing W/k from zero may reduce the LP solution value.
To try make the reduced cost negative, we sort the dual values 5, in decreasing order, and then go through the associated indices j. and create rules l such that ays: = via shortest path calculation. That is, we take the corresponding edge (X, Y) in E,, find the shortest path between X and Y and generate a new rule with the sequence of relations in that path. We limit the number of rules generated
so that KC; is only slightly larger than KG More precisely, we set [Ka] [K--1| S 10. We use the

---

Kinship
UMLS
Algorithm
MRR
H@@
I1@3
H@@ 10
MRR
H@@
H1@3
H@ 10
ComplEx-N3
0.889
0.824
0.950
0.986
0.962
0.934
0.990
0.996
TuckER
0.891
0.826
0.950
0.987
0.914
0.837
0.991
0.997
ÿ CoovE
0.83
0.74
0.92
0.98
0.94
0,92
0.96
0.99
AnyBURL
0.653
0.523
0.924
0.952
0.931
0.990
PeuralLP
0.652
0.520
0.726
0.925
0.750
0.601
0.876
0.958
DRUM
0.566
0,404
0.663
0.910
0.845
0.722
0.959
0.991
RNNLogic "0.687
0,566
0.756
0.929
*0.748
0.618
0.849
0.928
LPRules
0.746
0.639
0,816
0,959
0.869
0.812
0.917
0.970
Table 1: Comparison of results on Kinship and UMLS. The results from NeuralLP, DRUM, and our
code use the random break metric. *We modified the RNNLogic code to compute the MRR values based on the random break metric and the values obtained were the same as the values of the original MRR computation up to three decimal places. ConvE results are from the original paper.
dual values to indicate which facts are not currently implied by the existing set of chosen rules. If the reduced cost of new rule is nonnegative, then we do not add that rule to K,,-1-
4 EXPERIMENTS
We conduct experiments on knowledge graph completion tasks with six datasets: Kinship (Denham
1973), UMLS (McCray (200). FB 5k-237 (Toutanova & Chen 2015). WN INNIRRRRR (Dettmers et al.
2018 YAGO3-10 (Mahdisoltani et al. 2015) and DBIIIK- 174 (Hao al. 2019). In Table | we give properties of the datasets: the number of entities. relations. and the number of facts in the training, testing and validation data sets. The partition of FB15k-237, WN1&RR, and YAGO3-10 into training. testing, and validation data sets is standard. We chose the partition for UMLS and Kinship used in Dettmers et al. (2018) and the partition for DB11IK-I1 174 given in Cui et al. (202I).
4.1 EXPERIMENTAL SETUP
We denote the reverse relation for each relation r E R r-, For each fact (t, h) in the training set, we implicitly introduce the fact (h, (h,r-1,1) doubling the number of relations and facts. For each original relation in the training set, create a scoring function of the form fx Y) in (2). For each test set fact (t, r, h) we create two queries (t,r,?) and (?, r, h), and use fr to predict answers here is treated as a candidate solution to the queries (t, r) and (?, r, h) and then use the filtered ranking method in Bordes al. (2013) to calculate a ranking for the correct answer (namely (t, r, h)) the above queries. Ranks are computed using the random break method (option in NeuralLP (Yang et al. 2017 and these used to compute MRR and Hits k (for k 1,3, 10) across all test facts.
to these queries. For each entity in G, we calculate the scores fr,tt, e) and f-
We compare our results with the published embedding-based methods ConvE (Dettmers et al. 2018)) ComplEx-N3 [Lacroix al. 2018). TuckER (Balažević et al. 2019). RotatE (Sun al. [0119) B (Nayeer et al. (021), and AITH (Chami et al. We obtained results for ComplEx-N3 and
TuckER by running on our machines using the best published hyperparameters (if available). The results for the other embedding bassdd methods were taken from either the original papers or from Dettmers et al. (2018) or Qu et al. (2021). These codes do not implement random break ranking for equal scores, and some instead use nondeterministic ranking (Berrendorf et al. 2021). i.e., they sort entity scores before ranking. We compare with the rule-based methods Neural LP, DRUM, and RNNLogiC. We also run AnyBURL for 100 seconds. Additional comparisons Appendix. We obtain results for NeuralLP and DRUM using default parameters and random break score ranking. We modify the RNNLogic code to implement random break ranking, and use the
be found in the
7

---

defaults suggested for different datasets. RNNLogic claims to midpoint ranking, but actually implements a harmonic mean of possible reciprocal ranks in the presence of equal scores while calculating the MRR, which yields very slightly larger number than midpoint ranking based MRR.
We ran two variants of our code which we call "LPRules". In the first variant, we create LPR, by generating rules using Rule Heuristic I and Rule Heuristic 2, and then solve LPR, to obtain rules. As the results are satisfactory for smaller datasets, we do not perform column generation. In the second variant, which we use only for the largest instances, we create LPRg with an empty set of rules, and then perform 5 iterations consisting of generating up to 10 rules using the modified version of Rule Heuristic followed by solving the new LP. In other words, we create and solve LPR; for i O.... 5.
We search for the best values of T and k for each relation. We dynamically let R equal the length of the longest rule generated plus one. We then perform 20 iterations where, at the ith iteration, we set to iR. For each combination of T and K, we take the optimal weighted combination of rules and compute the MRR on the validation data set, and select those and i that yield the best MRR. We set the maximum rule length to 6 for WNISRR, and 3 for YAGO3-10 10, and 4 for the other datasets. Thus K S 100 except for WNISRR, We search for the best T from the list of values in Table [1
FB15k-237
WNISRR
Algorithm
MRR
H@1
H@3
H@
10
MRR
H@1
H@3
H@ 10
ComplEx-N3
0.362
0.259
0.397
0.555
0.469
0.434
0.481
0.545
TuckER
0.353
0.259
0.390
0.538
0.464
0.436
0.477
0.517
i ConvE
0.325
0,237
0.356
0.501
0.43
0.40
0.44
0.52
RotadE
0.338
0,241
0.375
0.533
0.476
0.428
0.492
0.571
5'B
0.37
0.28
0.40
0.56
0.50
0.45
0.51
0.59
AnyBURL
0.278
0.212
0.444
0.479
0.448
0.555
NeuralLP
0.222
0.160
0.240
0.349
0,381
0.367
0.386
0.409
DRUM
0.225
0.160
0.245
0.355
0.381
0.367
0.389
0.410
RNNLogie 0.288
0.208
0.315
0.445
*0.451
0.415
0.474
0.524
LPRules
0.255
0.170
0.270
0.402
0.459
0.422
0.477
0.532
Table 2: Comparison of results on FB15k-237 and WN1SRR. *The RNNLogic MRR value for WN18RR is obtained via random break ranking. $ We could not run RNNLogic on FB15k-237, and report numbers from the original paper. t The results for ConvE and RotatE were taken from Qu et al. The results for 5'E were taken from Nayyeri et al. 2021).
(202
4.2 RESULTS
In Tables 1 3 we give values for different metrics obtained with the listed codes, first for embedding methods, then for AnyBURL, then for rule-based methods (if available), and then for our code. We place AnyBURL in separate category as it is rule-based, but is similar to embedding- bebeedddgg- methods in its entity-dependent KG representation. Henceforth, rule-based codes does refer AnyBURL. All our experiments (with rule- based codes) are performed on machine with 128 GBytes of memory, and four 2.8 Intel Xeon E7-4890 processors, each with 15 cores, for total of 60 cores. We use coarse-grained parallelism in our code, and execute rule generation for each relation different thread, and solve L.ss with IBM CPLEX (IBM) 2019p. If one relation dominates the others (w.r.t number of facts, in YAGO3-10), then our implementation becames essentially tingle-threaded.
In [ we present results on Kinship and UMLS. Our method obtains better results than NeuralLP, DRUM, and RNNLogic Kinship across all measures, and better MRR and Hits@ I values than these three codes on UMLS. This is true even though we generate relatively compact rules (see Table 4 and also very simple rule generation heuristies. Therefore, for these datasets, trivial rule generation heuristics suffice when used in conjunction with a nontrivial weight generation algorithm. The embedding methods are much better across all metries. In Table 2 we present
8

---

results FB15k-237 237 and WN18RR. RNNLogic did not successfully terminate for FB15k-237 on our machine, and we take the published result. Our results for FB15k-237 are better than NeuralLP and DRUM but worse than RNNLogic. The best values for embedding saabedding-basedd based methods are much better than for all rule-based methods. For WN18RR, our results are better than the other rule-based methods, even while taking significantly less computing time, Table 6 in the Appendix. This better scaling behaviour allows us to tackle large datasets such as YAGO3-I0, which we give results for in T We use column generation, generating 10 columns each iteration, and iterate only times for total of 50 candidate rules per relation. To compute negg, we sample 20% of the edges from E,,, and compute the number of invalid paths that start the tails of these edges, and end the heads of these edges. For YAGO3-10 and DB IK-174, our column generation approach becomes essential. We are simply unable to process a very large number of rules. The ability to generate small number of rules, and then use the dual values to focus on "uncovered" facts (not implied by previous rules) and generate new rules covering these uncovered facts is very helpful.
YAGO3-10
DB11IK 1-4
Algorithm
MRR
H@1
H@3
H@
10
MRR
H@] 1
H@3
H@ 10
ComplEx-N3
0.574
0.499
0.619
0.705
0.421
0.344
0.459
0.563
TuckER
0.265
0.184
0.290
0.426
0.345
0.247
0.397
0.529
ConvE
0.44
0.35
0.49
0.62
RotatE
0.495
0,402
0.550
0.670
ATTH
0.568
0.493
0.612
0.702
AnyBURI.
0.543
0,486
0.659
0.391
0.339
0.512
LPRules
0.449
0.367
0.501
0.684
0.363
0.312
0.390
0.460
Table 3: Comparison of results on YAGO3- 10 and DB 11111-111 174 using random break metric. i The results for ConvE are taken from Dettmers et al. (2018). & The results for RotatE are from [Snn et al. (2019). The results for ATTH are from Chami et al. (2020).
In Table 4 we confirm that we obtain compact rule sets as measured by the average number of rules in the final solution, given in column '#rules'. These final rules are selected from few hundred to a thousand generated rules, other than in YAGO3-10, 10, where we only generate 50 rules. We get better MRR for similar levels of sparsity compared to NeuralLP and RNNLogic. For WNI and UMLS, we obtain state-of-the-art results with few rules. We could not extract rules from DRUM. RNNLogic chooses top-K K rules for testing (K is an input parameter), and we run with the default = 200 and K 20. AnyBURL generates many rules and does not prune previously generated rules.
Kinship
UMLS
FB 15k-237
WNI8RR
YAGO3-10
Algorithm
MRR
Brules
MRR
#rules
MRR
#rules
MRR
#rules
MRR
#rules
AnyBURL
0.653
13334
0.952
6228
0.278
1360
0.479
4783
0.543
12852
NeuralLP
0.652
10.2
0.750
14.2
0.222
8.3
0.381
14.6
RNNLogic-22
0.600
20
0.706
20
0.416
20
RNNLogic-200 200
0.687
200
0.677
200
0,451
200
LPRules
0.746
21.0
0.848
4.2
0.255
14.2
0.459
15.6
0.449
7.8
Table 4: MRR and average number of rules selected per relation
5 CONCLUSION
Existing methods to obtain logic rules for knowledge graph completion can be fairly time consuming. Our relatively simple linear programming formulation for selecting weighted logical rules and associated solution algorithm can return state-of-ther results for a number of standard KG datasets even with sparse collections of rules, and much faster than existing methods.

---

REFERENCES
Ivana Balažević, Carl Allen, and Timothy M Hospedales. Tucker:
Tensor factorization for knowledge graph completion. In Empirical Methods in Natural Language Processing, 2019.
M. Berrendorf, E. Faerman, L. Vermue, and V. Tresp. On the ambiguity of rank-based evaluation of entity alignment or link prediction methods. arXiv:2002.06914, 2021.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems, 2013.
Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Re. Low- dimensional hyperbolic knowledge graph embeddings. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 6901-6911 Association for Computational Linguistics, July 2020.
Andrew Cropper and Rolf Morel. Learning programs by learning from failures, 2020.
Andrew Cropper and Stephen H. Muggleton. Learning higher-order logic programs through abstrac- tion and invention, 2016.
Zijun Cui, Pavan Kapanipathi, Kartik Talamadupula, Tian Gao, and Qiang Ji. Type-angmented relation prediction in knowledge graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8):7151-7159) May 2021.
Rajarshi Das, Shehzad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishant 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. In ICLR, 2018.
Sanjeeb Dash, Oktay Günlük, and Dennis Wei. Boolean decision rules via column generation. In Advances in Neural Information Processing Systems, pp. 4655-4665, 2018.
Ayhan Demiriz, Kristin P. Bennett, and John Shawe-Taylor. Linear programming boosting via column generation. Machine Learning, 46:225-254, 2002.
W. Denham. The detection of patterns in Alyawarra nonverbal behavior. PhD thesis, University of Washington, 1973.
Tim Dettmers, Minervini Pasquale, Stenetorp Pontus, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. AAAI, 2018
Boyang Ding, Quan Wang, Bin Wang, and Li Guo. Improving knowledge graph embedding using simple constraints. In Proceedings of 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 110-121, Melbourne, Australia, July 2018. Association for Computational Linguistics.
Jonathan Eckstein and Noam Goldberg. An improved branch-and-bound method for maximum monomial agreement. INFORMS Journal on Computing, 24(2):328-341, 2012.
Jonathan Eckstein, Ai Kagawa, and Noam Goldberg, Repr: Rule-enhanced penalized regression. INFORMS Journal on Optimization, 1(2):143-163, 2019.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
Noam Golderg, Optimization for sparse and accurate classifiers. PhD thesis, Rutgers University, New Brunswick, NJ, 2012.
Shu Guo, Quan Wang. Lihong Wang, Bin Wang, and Li Guo. Knowledge graph embedding with iterative guidance from soft rules. In AAAI, 2018.
Junheng Hao, Muhao Chen, Wenchao Yu, Yizhou Sun, and Wei Wang. Universal representation learning of knowledge bases by jointly embedding instances and ontological concepts. In Proceed- ings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 19, pp. 1709-1719, 2019.
10

---

IBM. IBM CPLEX optimizer, version 12.10, 2019.
URL https://wwe ibm. com/
S. Ji, S. Pan, E. Cambria, P. Marttinen, and P. Yu, A survey knowledge graphs: Representation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-21, 2021.
Stanley Kok and Pedro Domingos. Learning the structure of markov logic networks. ICML, 2005.
Timothee Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML, 2018.
Ni Lao and William W. Cohen. Relational retrieval using a combination of path-constrained random walks. Machine Learning, 81:53 00-3-677262 2010.
Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with reward shaping. Empirical Methods Natural Language Processing, 2018.
F. Mahdisoltani, J. Biega, and Fabian M. Suchanek. Yago3: A knowledge base from multilingual wikipedias. In CIDR, 2015.
A. T. McCray, An upper level ontology for the biomedical domain. Comparative and Functional Genomics, 4:80-84, 2003.
Christian Meilicke, Melisachew W. Chekol, Daniel Ruffinelli, and Heiner Stuckenschmidt. Anytime bottom-up rule learning for knowledge graph completion. IJCAI, 2019.
M. Nayyeri, Chengjin Xu, Jens Lehmann, and Hamed Shariat Yazdi. Logicenn: neural based knowledge graphs embedding model with logical rules. ArXiv, abs/1908.07 141, 2019.
Mojtaba Nayyeri, Sahar Vahdati, Can Aykul, and ens Lehmann. 5* knowledge graph embeddings with projective transformations. In AAAI, 2021.
Jan Noessner, Mathias Niepert, and Heiner Stuckenschmidt. Rockit: Exploiting parallelism and symmetry for map inference in statistical relational models. 2013.
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. NeurlPS, 2019.
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogic: Learning logic rules for reasoning on knowledge graphs. ICLR, 2021.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine Learning, 62:107-136. 2006.
Sebastian Riedel. Improving the accuracy and efficiency of map inference for markov logic. In Proceedings of UAI 2008, 2008
Tim Rochstätel and Sebastien Riedel. End-to-end differential proving. In Advances in Neural Information Processing Systems, 2017.
Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You can teach an old dog new tricks! on training knowledge graph embeddings. In International Conference Learning Representations, 2020.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: End-to-end differentiable rule mining on knowledge graphs. In NeurlPS. 2019.
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 Advances in Neural Information Processing Systems, 2018
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.

---

Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re-evaluation of knowledge graph completion methods. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp.
2020.
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. ICML, 2020.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionaliiy (CVSC), pp. 57-66, 2015.
Théo Trouillon, Johannes Welbl, Sehastian Riedel, Eric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In ICML, 2016.
Q. Wang. Z. Mao, B. Wang, and L. Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE TKDE, 29:2724 2017.
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: reinforcement learning method for knowledge graph reasoning, In EMNLP, 2017.
Fan Yang. Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances Neural Information Processing Systems 30. 2017.
Yang Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. ICLR 2020.
A APPENDIX
A.I DATASET DETAILS AND RUNNING TIMES
Datasets
# Relations
# Entities
# Train
# Test
Valid
Kinship
25
104
8544
1074
1068
UMLS
46
135
5216
661
652
WNISRR
40943
86835
3134
3034
FB15k-237
237
14541
272115
20466
17535
YAGO3-10
37
123182
1079040
5000
5000
DB111K-174
298
98336
474123
65851
1 118531
Table 5: Sizes of datasets.
In Table 6 we give run times (in minutes) on the different datasets. The results in the top section of the table were obtained on the 60 core machine described above and the results in the bottom section of the table were obtained on machine with 16 CPUs and 1 GPU. Our times include the time to evaluate the solution on the test set. AURL is run for fixed time of 100 seconds. For WNISRR, DRUM and NeuralLP take 400 minutes more, and RNNLogic takes over 100 minutes, whereas take minutes and less than minutes with LPRules. We note that we use maximum rule length of 6 for WNISRR, but do not know the maximum path lengths used in the other codes. DRUM takes over 8 days for FB FB15K-237 (as does NeuralLP on a different machine), which is why we do not these codes YAGO3-10 10 and DB111K- 174. Our code can be sped up further if fine- ine-ggrieed parallelism were used (see the Appendix A.5
A.2 ADDITIONAL COMPARISONS
It is challenging compare published codes for KGC they differ in important ways.
12

---

Kinship
UMLS
WNI8RR
FB15k-237
YAGO3-10
DB111K-174
AnyBURL
1.7
1.7
1.7
1.7
1.7
1.7
Ne
1.6
1.1
399.9
DRUM
3.2
2.8
505.9
12053.3
RNNLogic
108.8
133,4
104.0
LPRules
0.5
0.2
11.0
234.5
1648.4
152.4
ComplEx-N3
2.6
1.7
195.9
238.6
2024.8
745.2
TuckER
8.9
5.5
266.6
407.5
2894.7
6161.1
LPRules
2.7
0.4
11.7
267.3
1245.9
131.0
Table Wall clock run times minutes when running in parallel on a 60 core machine for the top group of results and machine with 16 CPUs and I GPU for the bottom results.
a. Entity Ranking: There are different ways (Berrendorf et al. 2021 Sun et al. 2020) of ranking entities that form candidate solutions to queries rt, r). and (?, r, h) constructed from a test set fact (t, r, f),, and the choice of the ranking method may have significant
effect on the final MRR, especially for rule-based methods, see Table 7 Assume m entities
receive strictly better score than the true answer h for the query rt.r. ?) and n entities receive the same score. Some ranking methods listed in Berrendorf et al. (2021) are: receives rank of m
entities, or m m++7 n (pessimistic), or where is a random number between m + and m + ri (random (Sun et al. 2020)). It is also observed in [Berrendorf al. (202T) that numerous codes give a nondeterministic rank between m + and m + based on the position of the correct entity sorted order of equal score entities. Other options are rank of + (n m (midppint) (Qu et al. 2021 or random break, where the correct entity is compared against all entities and any ties in scores are broken randomly. We observe that random and random break are not the same: the probability of getting any rank between
(optimistic)) i.e., the best among all equally-score
and + is the same random, whereas m + (n mm/2 is more probable as a rank than m + or m n in random break. The choice of the ranking method also depends on whether one assumes closed or open world hypothesis. The NTP and NTP-> codes referred in Table use an optimistic ranking method, whereas MINERVA uses a nondeterministe ranking method.
b. Query construction: Some codes, such as MINERVA, only remove right entities from a fact (t, h)) in the test set construct the query (t, ?), and do not evaluate performance on the query (?, h)).
c. Hyperparameters and Experimental Sctup: It was shown recently (Ruffinell et al., 2020) that some older, seemingly lower-quality codes could be made to perform better than more recent codes with appropriate choices of hyperparameters.
Random ranking is proposed in Sun al. (2020) NeuralL.P and DRUM provide random- ranking (which is closer to midpoint ranking) instead of random ranking. We earlier compared our code with these codes and with RNNLogic using the random-breal ranking method, and two-sided query construction during testing. In the next table, we show that our code returns very different numbers if we use optimistic ranking, but similar results we use midpoint ranking.
suitable method for KGC, but the codes
In Table 8 we give a comparison with results published in the MINERVA paper (Das et al.) 2018) that are obtained with right-entity removal only, in query construction. We modify our code to construct queries in similar fashion, though we still use random-breat ranking, The grouping of results by embedding based methods, rule based methods, and those obtained by our code is as before. MINERVA and ConvE use nondeterministic before ranking, but NTP does not. The NTP code refers to the ranking method in ComplEx and says that "we calculate the rank from only those corrupted triples that have higher score" i... they optimistic ranking. our opinion, this accounts for the unusually high scores for UMLS obtained with NTP-X. When optimistic ranking for UMLSS, obtain an MRR of 0.967. ComplEE
(Berrendorf et al. 2021 ranking, they sort scores
13

---

WNI8RR
Metric
MRR
H@1
H@3
H@
Optimistic
0.658
0.603
0.678
0.768
Midpoint
0.455
0.415
0.474
0.532
Random Break
0.459
0.422
0.477
0.532
Table Results on WNISRR obtained with different ways of dealing with equal scores.
also optimistic ranking. Though cannot prove it, suspect that some embedding based methods (especially, ConvE, RotatE, and TuckER; see Sun et al. (2020)) do not return much better MRR values when using optimistic ranking instead of random-break ranking. This can happen if few entities get equal scores. We cannot locate the ranking method used DistMult.
Kinship
UMLS
Algorithm
MRR
H@
H@3
H@ 10
MRR
H@1
H@3
H@ 10
ComplEx
0.838
0.754
0.910
0.980
0.894
0.823
0.962
0.995
ConvE
0.797
0.697
0.886
0.974
0.933
0.894
0.964
0.992
DistMult
0.878
0.808
0.942
0.979
0.944
0.916
0.967
0.992
NTP
0.612
0.500
0.700
0.777
0.872
0.817
0.906
0.970
NTP--
0.793
0.759
0.798
0.878
0.912
0.843
0.983
1.000
NeuralLP
0.619
0.475
0.707
0.912
0.778
0.643
0.869
0.962
MINERVA
0.720
0.605
0.812
0.924
0.825
0.728
0.900
0.968
LPRules
0.776
0.682
0.836
0.966
0.887
0.841
0.924
0.971
Table Comparison with results Kinship and UMLS taken from the MINERVA paper. Queries are constructed from test set facts by right entity removal. Our code uses random break ranking. NTP uses optimistic ranking.
FB 137
WN18RR
Algorithm
MRR
H@1 1
H@3
H@ 10
MRR
H@
H@3
H@ 10
ComplEx
0.394
0.303
0.434
0.572
0.415
0.382
0.433
0.480
ConvE
0.410
0.313
0.457
0.600
0.438
0.403
0.452
0.519
DistMult
0.370
0.275
0.417
0.568
0.433
0.410
0.441
0.475
NeuralLP
0.227
0.166
0.248
0.348
0.463
0.376
0.468
0.657
0.227
0.169
0.248
0.357
0.027
0.017
0.025
0.046
MINERVA
0.293
0.217
0.329
0.456
0.448
0.413
0.456
0.513
M--Walk
0.232
0.165
0.243
0.437
0.414
0.445
I.Ruless
0.350
0.261
0.383
0.533
0.486
0.443
0.511
0.571
Table 9: Comparison with results on FB15k-237 and WN18RR taken from the MINERVA paper. Our code uses random break ranking. The M-Walk results are taken from the associated paper.
14

---

In Table 9 copy results for FB1SK- 237 and WN18RR obtained by right-entity removal in query construction from the MINERVA paper. We also copy results obtained with M-Walk (taken from the corresponding paper), as it uses the same query construction approach. We do not know the score ranking method used in M-Walk or in the Neurall.P runs from the MINERVA paper. We note that our code obtains the best value of MRR for WN18RR, and the best MRR value among all rule-based methods for FB F535-. Thus, for the four datasets mentioned in this table and the previous one, our code returns state-of-the-an results among the rule-based methods compared here.
A.3 PROOFS
We next present the proof of Theorem 1
Proof. Let (17, w) be an optimal solution of IPR. By definition, w has |K]] components, and rj has m Er| components, all of which binary, because of the form of the objective function. Let Cs be the clause associated with rule k. By definition, we have Cste = C& (x Yi). Consider the function
f(x, Y) V
Vkex Th Cx
Therefore, f VV {0, 1}. As (7.. w) satisfies equation 4 we have
Σ anwu + il 2 1 for all i E,,
kEK
We can see that Yi) = 1 and only if EkEK ug 2 1, and therefore
f(x,, Y,) + n. 2 for all E E,.
Therefore, either f(X,, Y2) or गJ 1. Furthermore, f(X,Y) is function for which fewest number of values 7i are or the highest number of values 87 are 0, as (7). w) form an optimal solution of IPR. In other words, f(X, () "covers" the largest number of edges of F, (covering means f(X,, Yi) = 1) among all possible functions that can be formed as a disjunction of rule clauses with complexity at most K. For each i such that f): O, we have
f(X,, Yi = and f(X,, Z) S 1 and f(Z,Y, <
for any entities X, V. If we take the facts in the training set test set, and use Y(X,Y) scoring function and use optimistic ranking of scores, then for each i such that f(,,, Y;) =1 f(X,, 2) and f(,,, Y;) 2 f(Z, Yi) for all entities Z, and therefore the rank of Y; is among all entities Z while scoring (X,, Z) (denoted by rr;), and the rank of X; is 1 among all the entities while scoring (Z, Y2) (denoted by In;). On the other hand rr; 2 1 and Ir, 2 1 if f(X,, Y,) = O. Therefore 1/rr,
for 7 as f(X,Y)
17. and 1/1r; 2 nh. The MRR of the prediction
function is
m
Em 1. 1/2m 2 2(m
Σ
/
Di= rr;
i=1
7
m
But Em -im1 7e is the optimal objective function value. Thus lower value of Σm 7)s yields higher lower bound on the MRR computed via optimistic ranking.
A.4 ANALYSIS OF YAGO3-10
We obtained an MRR of 0.449 with LPRules. We next analyze our performance and observe that it is primarily due to the perfomance on two relations, namely IsAffiliated'oo and playsFor, which together account for 64.4% of the facts the training set, and 63.3% of the facts in the test set. In Table [0] provide the rules generated by LPRules for these two relations. Here R_ R_isAffiliattdTo is the reverse of the relation isAffiliatedTo (and denoted by isAffiliatedTo -1 in the main document). The rule and weight columns together give the weighted combination of rules generated for relation. The MRR column gives the MRR value that would be generated the test set consisted only of facts associated with the relation in the "Relation" column, and the weighted combination of rules
15

---

consisted only of the rules in the same line above. Thus two rules for isAffiliatedTo, and the rules for playsFor, then the MRR would be at least 0.56 on the test set facts associated with these two relations. As these two relations account for 63.3% of the test set, just the four rules mentioned above would yield an MRR 2 0.56 x 0.633 Rs 0.354, as opposed to the MRR of 0.449 that obtained.
that if took only the first
The information in the table suggests a direct correlation between the relations isAffiliated and playsFor. Indeed, we verify that for about 75% of the facts (x, isAffiliatedTo, y), also have (x, playsFor, y) as a fact in the training set. Similarly, 87% of the playsFor facts are explained by the isAffiliatedoo relation in the training set.
A natural question is the following: Is the second rule for isAffiliatedTo a "'egenerate" rule and does it simply reduce to isAffiliatedTo because the entity b the same as entity a when we traverse relational path from x to in the training KG. To give an example that this is not the case, consider the following fact in the test set: [Pablo_Bonells, isAffiliatedToo, Club htub_Cllyya). In the training data, the following three facts imply the previous fact by application of the second rule: (Publo Bonells, isAffiliatedTo, León_ (Salvador Luiss Luis__eyes,, isAffiliatedTo, Club (tub_León), and (Salvador-_atee
isAffiiaaedTTo, Club Club_Celaya) The first rule is also applicable the training data contains the fact (Pablo Bonells. playsFor, Club Celaya). We have similarly verified that the second rule for playsFor creates nontrivial relational paths, where the nodes not repeated.
Relation
Weight
Rule
MRR
isAfilliaeefooox..
playsFor(x.))
0.463
isAffiliatedloox..a) A R isAffiliateeTo(aab A isAffiliatedoo(b.))
0.582
graduatedFromixx.a) A. gr_gruddateFFoomma... a, A isAfflliatedTo(b.))
isPoliticianOf((..a) A (_iiPolitiiiannff(.bb isAffliiateTo((b.)
0.5
livesIn(x,a) R_liveshn(a.b) isAffiliateedlolbb.))
0.585
playsFor(x.y)
isAfflliated(l((x.))
0.504
playsFor(x,a) A k_isAffiliated(ll(ab) A playsFor(by)
0.561
Table 10: Rules generated by LPRules for two relations in YAGO3-10. The MRR values for a particular rule were calculated using only the rules in the same line or above.
A.5 ADDITIONAL EXPERIMENTAL DETAILS
Table II contains the list of values of the parameter т given as input for each dataset. For larger datasets, this hyperparameter search is time-consuming, which is why fewer candidate values.
Datasets
Values of T
Kinship
0.02, 0.025, 0.03, 0.035, 0.04, 0.045, 0.05, 0.055, 0.06
UMLS
0.02, 0.03, 0.04, 0.05, 0.0055, 0.06, 0.07, 0.08, 0.09, 0.1
WNI8RR
0.0025, 0.003, 0.0035, 0.004, 0.0045
FB15k-237
0.005, 0.01, 0.025, 0.05, 0.1, 0.25
YAGO3-10
0.005, 0.01, 0.03, 0.05, 0.07
DB111K-174
0.005, 0.01, 0.03, 0.05, 0.07
Table 11: Values of the parameter for each dataset.
Given the lists of values in Table II removing values from this list reduces the MRR. but not too much. But we use entirely different values, the MRR can drop significantly. Indeed, the experiments in Table T2 that the amount of weight given to negative sampling is very important.
16

---

Furthermore, cannot choose the same value for different datasets, and it is best to search through a list, as we do.
Kinship
UMLS
WNI8RR
0.0001
0.640
0.560
0.453
0.001
0.686
0.758
0.461
0.01
0.728
0.799
0.444
0.1
0.667
0.830
0.385
Table 12: MRR obtained with fixed values of T.
We use coarse-grained parallelism in our code. For example, FB15K-237 has 237 relations, and we run the rule learning problem for each relation on a different thread. As we only have 60 cores, multiple threads are assigned to the same core by the operating system.
The run times increase significantly with increasing number of facts, and with increasing edge density in the knowledge graph. Recall that the rule learning linear program (LPR) that we solve for each relation r has a number of constraints equal |E,| + 1, the number of edges labeled by relation in the knowledge graph. Given candidate rule k in LPR, we need to compute a. = C2 (X,, Y;) for each edge in Fy,, where the ith edge in F,, is X, I Y, Computing Ask increases superlinearly with increasing average node degree and increasing path length, and so does neg, (both calculations involve an operation similar to BFS or DFS). See Table [ increasing run times on WNI8RR with increasing path length. The cost of solving a linear program (LP) grows superlinearly with the number of constraints. The larger datasets (WNI8RR, FB15K-237, and YAGO3-10) 10) all have some relation which has many more associated facts/edges than the average number per relation. This leads to significant run times, both in setting up LPR for the relation and solving LPR, in the case of FB 1155-2277 and YAGO3-10, and also to reduced benefits of parallelism. For example, for YAGO3-10, 10, the relations isAffiiiatdTo and playsFor have 373,783 and 321,024 associated facts, respectively, out of total of roughly a million facts. Most relations completed in short amount of time, while these two relations run for long time on a single thread each. natural approach to of these facts while setting up LPR, but do not do
reducing the run time would be to sample this in this work. For YAGO3-10 10, we do not compute neg, exactly and use sampling to obtain an approximation, as described in the main document.
One can easily parallelize the hyperparameter search process in our code. Other operations which be parallelized are the computation of the coefficients ay in LPR, but we have not done We thus believe there is scope for reducing our run times even further. We note that the operations we perform are not well-suited run on GPUs.
In Table 13 we give our results for WNI8RR when we use rules of length 4, 5 and 6, with the results for length copied from Table in the main document. The best MRR is obtained using path length but takes 5 times the amount of time as path length 4. We note that the reported results for RNNLogic were obtained using a maximum rule length of 5 for WNIS8RR.
Rule Length
Algorithm
MRR
H@1
H@3
H@
10
Time (mins)
4
LPRules
0.449
0.414
0.465
0.518
2.3
5
LPRules
0.457
0.421
0.473
0.527
5.0
6
LPRules
0.459
0.422
0.477
0.532
11.0
Table 13: Results on WNISRR with maximum rule length=4,5,6 obtained using random break ranking.
A.6 ADDITIONAL CODE DETAILS
For the experiments in this paper, in Rule Heuristic 1, we simply generate all length one and length two rules that create relational path from the tail to head node for least one edge (X,, Yi)
17

---

associated with relation while creating LPR for relation The number of such rules is usually small (less than 50).
In Rule Heuristic 2, for every edge X + Y in E, (associated with relation r), we find a shortest path, using breadth-first search, from X; to Y, in the knowledge graph & that does not the edge do not find shortest path between X;
X S Y. However, when perform column generation, and Y; for every directed edge in E,. Instead, we only consider edges E E, that are not "implied" by the currently chosen weighted combination of rules. Such edges are indicated by large dual values, as discussed earlier. A natural improvement to this algorithm would be to find rules which create relational paths between multiple pairs of tail and head nodes X; and Y; which have large dual values.
During the search for the best abd values, we first set LPR or LPR; (for some i, when we do column generation) for a fixed value of and R. Subsequently, we do not add any more rules/columns, and instead change the values of 7 and K, and evaluate the resulting IP solution on validation set by computing the MRR, and then choosing the т, A combination which gives the best value of MRR on the validation set. During training, obtain weighted combination of rules for each relation separately, and then evaluate all these relations on the test set after training is complete.
All relational paths that we create (either in shortest-path calculations during evaluation on the test set) are simple, i.e., they do not repeat nodes.
All our code is written in C++. The LP Solver use is IBM CPLEX (IBM 2019), which is commercial MIP solver (though available for free for academic use). Any high-quality LP solver can be used instead of CPLEX, though the interface functions in code which have CPLEX-specific functions calls would need to be changed.
A.7 SOLUTION SPARSITY
One important feature of rule based methods is the interpretability aspect of rules. is clear that link predictors with very large number of rules will be harder to understand than those with few rules. In the main document, we gave the average number of rules per relation in our solutions as compared to the Neural LP solution. In code, we vary the upper bound complexity of chosen rules in relation up to a certain number and use the validation set to choose the best complexity bound within the range of allowed bounds. However, we do not control the final complexity of the solution beyond the upper bound. Varying the upper bound allows us to generate solutions with lower number of rules. RNNLogic has a parameter which allows one select the number of rules per relation used in testing; see also Figure 2a in Qu et al. (202T) where the MRR is plotted against number of selected rules. In Table 14 give the average number of rules selected for Kinship by NeuralLP. RNNLogic and LPRules and corresponding values of MRR. These results show that LPRules is able to provide higher values of MRR for Kinship for the same number of rules selected compared the other two codes.
Kinship
Algorithm
MRR
S
NeuraLLP
0.652
10.2
RNNLogic
0.611
20.0
0.624
100.0
0.687
200.0
LPRules
0.739
11.6
0.742
17.4
0.746
21.0
Table 14: MRR and average number of rules selected (S) for Kinship.
18


Reviews:
[{"review_id": "YNvYruXaBu", "reviewer": "Reviewer_N4fv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Strengths:\nThis manuscript exploits the idea of linear programming into knowledge graph completion tasks and then presents a model to prove the sufficiency of their idea. Some interesting experimental results are well demonstrated. \n\nWeaknesses:\nThere is no in-depth comparison of the algorithm with previously known work.  Section 2 simply listed a bundle of ‘literature review’.  However, it is still hard to judge whether the algorithm is an improvement on previous work.", "summary_of_the_paper": "To solve the problem that rule-based methods in knowledge graph completion tasks are lack of scalability to large datasets, this manuscript presents a simple linear programming model to choose rules from a list of candidate rules and assign weights accordingly. Some experiments are therefore designed and conducted to demonstrate some interesting results. ", "summary_of_the_review": "This is a well-written paper having some interesting results. A few minor revision are list below.\n* The idea of using column generation techniques to add new rules is interesting. However, the methods and theoretical innovations are still not sufficient. The author(s) must dig deeper into the innovation points before the article can be accepted.\n* The literature review is weak. Related work has not been investigated sufficiently before just presenting the author’s model.  ", "strength_and_weaknesses": "", "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": "AEgSbyM1mvm", "reviewer": "Reviewer_wtBS", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "First, the paper does have it's strong points:\n\nS1. Simple, easy to understand approach.\n\nS2. Only requires shortest-path computations, rule evaluation, and an LP solver.\n\nS3. Decent results.\n\nHowever, in the light of the current state-of-the-art, the paper falls short severely (W1). It's also overly limited in the type of rules that can be generated and how they can be combined (W2).\n\nW1. Does not include SOTA approaches and falls behind in all areas where benefits are claimed: [A] (not cited) proposes a rule learner which (1) has a larger language bias, (2) is orders of magnitude faster than the proposed approach on a less powerful machine, and (3) produces higher-quality predictions, and (4) is simple. E.g., on the largest YAGO3 dataset: paper 21h, .45 MRR, 60 cores; [A] 16min, >=.49 MRR, 4 cores. It's not clear what the benefits of the proposed approach really are, if any.\n\n[A] Christian Meilicke, Melisachew Wudage Chekol, Daniel Ruffinelli and Heiner Stuckenschmidt: Anytime Bottom-Up Rule Learning for Knowledge Graph Completion. IJCAI 2019.\n\nW2. The rule generation heuristics are well-known; there is no novelty here (it's also not claimed). It appears that only chain rules that correspond to shortest path can be learned. The language bias is thus quite limited and does not include other types of rules known to be usefule, most notably, rules involving constants (\"X lives in New York\" => \"X speaks English\"). There has been prior research in how rules are combined (e.g., [A] uses the most confident rule); it's not clear whether a linear combination of rules is a good idea in the first place. Here an ablation and comparison to prior approaches is missing. As for pruning negative-weight rules: There isn't much pruning at all: only 50 candidate rules are generated per relation in the first place in the experimental study. These candidates are useful in that they are generated sequentially based on the candidates so far, but this idea is also present in prior work (e.g, RNNLogic, [A]).\n", "summary_of_the_paper": "The paper proposes a simple method to generate logic rules, where rules are generated by a shortest-path heuristic and rule weights by solving a linear program.\n", "summary_of_the_review": "In the light of the current state-of-the-art, the paper falls short severely (W1). It's also overly limited in the type of rules that can be generated and how they can be combined (W2).\n", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6lpn_9qcSpS", "reviewer": "Reviewer_3BGR", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Generally, the paper is well written, proposes a novel approach to obtain a scoring function given a set of rules and a KG, and has convincing experimental results. \n\nThe only criticism I’d have is some missing related work. The authors cite exhaustively from the literature on knowledge graph embedding methods and rule-based approaches. However, there is a large body of work in the statistical relational learning community, focusing precisely on computing a scoring function (here: marginal probability or MAP state; and/or computing rule weights) in large probabilistic models defined through weighted rules. Below are two representative examples who proposed (among other things) column generation techniques and formulating the problem as an ILP. It’s not an LP but one could relax the ILP. I believe this is work that should be cited as related. In fact, I believe a discussion of these related approaches in the context of SRL might be illuminating and bring SRL researcher to pay attention to the idea proposed here in the context of knowledge graph completion. \n\nhttps://arxiv.org/abs/1206.3282\n\nhttps://arxiv.org/abs/1304.4379", "summary_of_the_paper": "The paper presents a method to obtain weights for a knowledge graph scoring model for link prediction. There are numerous good algorithms for mining rules from knowledge graphs (e.g. AnyBURL and AMIE). Less research has focused on the problem of creating scoring functions based on an (implicit) list of rules. This is what the present paper proposes. \n\nThe core idea is to formulate a linear program whose solution corresponds to a scoring method. Instead of incorporating all rules (there are typically many!) into the LP formulation, the authors propose a column generation approach. \n\n", "summary_of_the_review": "Good paper but some discussion of highly related work is missing ", "strength_and_weaknesses": "", "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": "074YsdVi_Xa", "reviewer": "Reviewer_PFXs", "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": "Advantages: \n* The problem of learning logical rules is very crucial. \n* The proposed model is very simple and seems to be effective. \n* The efficiency is better than some previous works. \n\nDisadvantages: \n* The paper is hard to follow, which requires improvements. \n* The motivation of the model is confusing, which seems to have no significant improvement compared to existing works such as Neurallp and DRUM. They reduce the search space by changing the order of summation and multiplication when calculating rules, which can also be regarded as low-rank decomposition of rule-score tensors. \n* In my opinion, the most time-consuming module of Neurallp and DRUM is LSTM. If they directly use the coefficients of relations in the rule as the learnable parameters, it would be much faster and may achieve comparable performance. I am not sure the proposed method is also faster than the simplified version of Neurallp and DRUM. \n* There are several works that the author didn’t compare with, such as [1,2], which can learn more complex rules. \n\nMinor issues:\nI -> i in equation 2.\n\n[1] Yang, Yuan, and Le Song. \"Learn to Explain Efficiently via Neural Logic Inductive Learning.\" International Conference on Learning Representations. 2019.\n\n[2] Teru, Komal, Etienne Denis, and Will Hamilton. \"Inductive relation prediction by subgraph reasoning.\" International Conference on Machine Learning. PMLR, 2020.\n\n", "summary_of_the_paper": "This paper proposed a simple linear programming model for learning logical rules for KG completion. The model selects candidate rules from KG with explicit constraints and then solves a linear programming problem. The authors conduct experiments on several public datasets and the model has better efficiency than baseline models. ", "summary_of_the_review": "In summary, the paper presentation requires improvements and the motivation for designing such a model is not clear. There are several methods that the authors did not use for comparison. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows how to make use of a linear program for extracting logical rules for knowledge graph completion. Overall, the reviewers and I agree that this is an interesting and important direction for research. Moreover, the presented approach shows good performance with rather small sets of rules extracted. However, all reviewers point out that the related work is not well discussed. While the authors have improved the related work sections during the rolling discussion, overall the positioning of the new method has still to be improved, including a better empirical comparison across different datasets. Overall, we would like to encourage the authors to polish their line of research based on the feedback from the reviews.
Decision: Reject