LPRULES: RULE INDUCTION IN KNOWLEDGE GRAPHS USING LINEAR PROGRAMMING
Year: 2021

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. Rulebased 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 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 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-art 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.

heading: 1 INTRODUCTION
text: 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 is a triplet of the form (a, r, b) where a and b are nodes, and r is a binary relation labeling a 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_border_with, or part_of. A fact (a, part_of, 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 can 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 Ji et al. (2021) for a recent survey on KGs. KGC involves using known facts in a KG to infer additional (missing) facts. One approach for KGC is to learn first-order logic rules that encode known facts.
In the example above, we could learn a “rule” capital_of(X,Y) → part_of(X,Y) where X, Y are variables that take on entity values. Then if we find a pair of entities P,Q such that (P, capital_of, Q) is a 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_of(X,Y) and part_of(Y,Z) → part_of(X,Z). Again, applying it to entities P and Q, if there exists a third entity R such that capital_of(P,R) is a fact in the graph, and so is part_of(R,Q), then we infer that P is a 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 a 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.
Learning logic rules is a well-studied area. In a 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. (2017)
use neural logic programming to simultaneously obtain sets of rules and the weights of individual rules. Qu 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-based 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, 2019), especially if one obtains compact rule sets (with few rules and few relations per rule). Furthermore, entity-independent rules are more generalizeable (Teru et al., 2020) and can be applied in an inductive setting: they can be applied to entities not considered in the learning process. Embedding-based methods work mostly in a transductive setting.
We propose a novel approach to learning entity-independent, 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 a 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 NeuralLP (Yang et al., 2017), DRUM (Sadeghian et al., 2019), and RNNLogic (Qu et al., 2021) in that we form a linear combination of rule scores (calculated differently from the above papers). As in RNNLogic, 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-art 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-based methods – on YAGO3-10, a 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 a constraint in our LP formulation limiting the complexity of the chosen rule set (and this hyperparameter is tuned per dataset). In some cases, we 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.

heading: 2 RELATED WORK

heading: 2.1 RULE-BASED METHODS
text: There is a rich body of literature on rule-based methods for knowledge graph reasoning. The motivation 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-independent, 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 Cropper & Morel (2020). First-order Logic (FOL) programs in the form of a collection of chain-like Horn clauses are a popular output format. Negative examples are not available in typical knowledge graphs, and some of the positive examples can be mutually inconsistent. Evans & Grefenstette (2018) developed a differential ILP framework to 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 a 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 a set of FOL rules, and rule weights are learned
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 Lao & Cohen (2010), a weighted linear combination of rule-based functions (e.g., the function could return a 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-learning 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 an appropriate RNN. Further improvements in this paradigm can be found in DRUM (Sadeghian et al. (2019)). Another neuro-symbolic approach is implemented in the Neural Theorem Prover (NTP, Rochstätel & Riedel (2017)). More general rules (than the chain-like rules found in NeuralLP) are obtained in NLIL (Yang & Song) along with better scaling behavior. Simultaneously solving for rules and rule-weights is difficult, and a 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 et al., 2021), the rules are generated using an RNN, and rule weights are later calculated via a probabilistic model. Such a 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 to use reinforcement learning (RL) to search for rules can be found in MINERVA (Das et al., 2018), MultiHopKG (Lin et al., 2018), M-Walk (Shen et al., 2018) and DeepPath (Xiong et al., 2017). The first three papers use RL to explore relational paths conditioned on a specific query, and use RNNs to encode and construct a graph-walking agent.
Rule types/Rule combinations. AnyBURL generates rules corresponding to different types of paths (acyclic or cyclic, in their notation) which may be entity-dependent or independent. As mentioned before, NLIL goes beyond simple chain-like rules. Recently Teru et al. (2020) use subgraphs to perform reasoning, and not just paths. We generate weighted, entity-independent, 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 a relational path from a to b 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 b associated with r. Finally, AnyBURL uses maximum confidence scores rather than sums of confidence scores; further, its scoring function returns a vector of sorted scores, and two score vectors are compared lexicographically.
Scalability/Compact 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. NeuralLP, 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).

heading: 2.2 EMBEDDING-BASED METHODS
text: 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 va ∈ Rk for each node a in the knowledge graph and a function Tr : Rk → Rk for each relation r such that Tr(va) ≈ vb
whenever (a, r, b) is a fact in the graph. Then, for a pair of entities a and b, one could assert that (a, r′, b) is a fact (assuming it is not present in the graph) if Tr′(va) ≈ vb. Well known papers in this area are Sun et al. (2019), Bordes et al. (2013), Dettmers et al. (2018), Lacroix et al. (2018), Trouillon et al. (2016), Balažević et al. (2019), Nayyeri et al. (2021), and Chami et al. (2020).
There are a 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., 2019), and ComplExNEE-AER (Ding et al., 2018), the goal is to 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, r, ?). In others (Lin et al., 2018), information from embeddings is used to obtain better rules.
Though embedding-based 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).

heading: 3 MODEL
text: We propose a linear programming model inspired by LP boosting methods for classification using classical column generation techniques (Demiriz et al., 2002; Golderg, 2012; 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).
Knowledge graphs: Let V be a set of entities, and let R be a set of n binary relations defined over the domain V . A knowledge graph represents a collection of facts F ⊆ V ×R× V as a labeled, directed multigraph G. Let F = {(ti, ri, hi) : i = 1, . . . |F|} where ti ̸= hi ∈ V , and ri ∈ R. The nodes of G correspond to entities in F and the edges to facts in F : if (t, r, h) is a fact in F , then G has a directed edge (t, h) labeled by the relation r, depicted as t r→ h. Here t is the tail of the directed edge, and h 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, t) 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 (t, r, ?) asks for a head entity h such that (t, r, h) is a fact, given a tail entity t and a relation r. A collection of facts F is divided into a training set Ftr, a validation set Fv , and a test set Fte, the KG G corresponding to Ftr is constructed and a scoring function (for link prediction) is learnt from G and evaluated on the test set. Goal: For each relation r in G, find a set of closed, chain-like rules R1, . . . , Rp and positive weights w1, . . . wp where each rule Ri has the form
r1(X,X1) ∧ r2(X1, X2) ∧ · · · ∧ rl(Xl−1, Y ) → r(X,Y ). (1) Here r1, . . . , rl 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,Y of G there exist entities X1, . . . Xl of G such that r1(X,X1), rl(Xl−1, Y ) and rj(Xj−1, Xj) are true for j = 2, . . . l − 1, then r(X,Y ) is true. We refer to the conjunction of relations in (1) as the clause associated with the rule Ri. Thus each clause Ci is a function from V × V to {0, 1}, and we define |Ci| to be the number of relations in Ci. Clearly, Ci(X,Y ) = 1 for entities X,Y in G if and only if there is a relational path of the form
X r1→ X1 · · ·Xl−1 rl→ Y. Our learned scoring function for relation r is simply
fr(X,Y ) = p∑ i=1 wiCi(X,Y ) for all X,Y ∈ V. (2)
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 use of LP to learn
the function. Given a query (t, r, ?) constructed from a fact (t, r, h) from the test set, we use the approach from Bordes et al. (2013) where the score fr(t, v) is calculated for every entity v ∈ V , and the rank of the correct entity h is calculated from the scores of all entities in the filtered setting. We similarly calculate the rank of t for the query (?, r, h). We then compute standard metrics such as MRR (mean reciprocal rank), Hits@1, Hits@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 K denote the set of clauses of possible rules of the form (1) with maximum rule length L. Clearly, |K| = nL, where n is the number of relations. Let Er be the set of edges in G labeled by relation r, and assume that |Er| = m. Let the ith edge in Er be (Xi, Yi). We compute aik as aik = Ck(Xi, Yi): aik is 1 if and only if there is a relational path associated with the clause Ck from Xi to Yi.
Furthermore, let negk be a number associated with the number of “nonedges” (X ′, Y ′) from (V × V ) \Er for which Ck(X ′, Y ′) = 1. We calculate negk for the kth rule as follows. We consider the tail node t and head node h for each edge in Er. 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 no edge from t to a node v in S labeled by r, we say that v is an invalid end-point. Let rightk be the set of such invalid points. We similarly calculate the set leftk of invalid start-points based on paths ending at h induced by the kth rule. The total number of invalid start and end points for all tail and head nodes associated with edges in Er is negk = |rightk|+ |leftk |. For a query of the form (t, r, ?) where t is a tail node of an edge in Er, the scoring function defined by the kth rule alone gives a positive and equal score to all nodes in rightk.
Our model for rule-learning is given below.
(LPR)
zmin = min m∑ i=1 ηi + τ ∑ k∈K negkwk (3)
s.t. ∑ k∈K
aikwk + ηi ≥ 1 for all i ∈ Er (4)∑ k∈K (1 + |Ck|)wk ≤ κ (5)
wk ∈ [0, 1] for all k ∈ K. (6)
The continuous variable wk is restricted to lie in [0, 1] and is positive if and only if clause k ∈ K is a part of the scoring function (2). The parameter κ is an upper bound on the complexity of the scoring function (defined as the number of clauses plus the number of relations across all clauses). The variable ηi is a penalty variable which is positive if the scoring function defined by positive wks gives a value less than 1 to the ith edge in Er. Therefore, the ∑m i=1 ηi portion of the objective
function attempts to maximize ∑m
i=1 min{fr(Xi, Yi), 1}, i.e., it attempts to approximately maximize the number of facts in Er that are given a “high-score" of 1 by fr. In addition, we have the parameter τ > 0 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-the-art prediction rules using LPR. Theorem 1. Let IPR be the integer programming problem created from LPR by replacing equation (6) by wk ∈ {0, 1} for all k ∈ K, and letting τ = 0. Given an optimal solution with objective function value γ, one can construct a scoring function such that 1− γ/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 a 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.
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 τ > 0 in LPR. We will now give an interpretation of ∑ k negkwk. To compute the MRR of the scoring function fr in (2) applied to the training set, for each edge (t, r, h) ∈ Er we need to compute the rank of the answer h to the query (t, r, ?) – by comparing fr(t, r, v) with fr(t, r, h) for all nodes v in G – and the rank of answer t to the query (?, r, h) – by comparing fr(v, r, h) with fr(t, r, h) for all nodes v. But ∑ k negkwk is exactly the sum of scores given by fr to all nodes in rightk and leftk and therefore we have the following proposition. Proposition 2. Let (t, r, h) be an edge in Er, and let U(?, r, h) be the set of invalid answers for (?, r, h) and let U(t, r, ?) be the set of invalid answers to (t, r, ?) in the filtered setting. Then
∑ (t,r,h)∈Er  ∑ v∈U(?,r,h) fr(v, r, h) + ∑ v∈U(t,r,?) fr(t, r, v)  = ∑ k∈K negkwk.
In other words, rather than keeping individual scores of the form fr(v, r, h) and fr(t, r, v) small, we minimize the sum of these scores in LPR.
It is impractical to solve LPR given the exponentially many variables wk, except when n and L are both small. For WN18RR (Dettmers et al., 2018), n is only 22 (WN18RR has 11 relations, but we introduce a reverse relation r−1 for each r ∈ R, and create rules that include reverse relations) and thus setting l to 3 does not lead to too many variables. An effective way to solve such large LPs is to use column generation where only a small subset of all possible wk variables is generated explicitly and the optimality of 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 K0 ⊂ K (and implicitly set all rule variables from K \ K0 to 0). Let LPR0 be the associated LP. We solve LPR0, and then dynamically augment the set of candidate rules to create sets Ki such that K0 ⊂ K1 ⊂ · · · ⊂ K. If LPRi is the LP associated with Ki with optimal solution value zimin, then it is clear that a solution of LPRi is a solution of LPRi+1, and therefore zi+1min ≤ zimin. We attempt to have z i+1 min < z i min by taking the dual solution associated with an optimal solution of LPi, and then trying to find a negative reduced cost rule, which we discuss shortly.
Setting up the initial LP. To set up K0 and the associated LP0, 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 it labels a large number of edges from tail nodes to head nodes of edges in Er. Similarly, to create rules of length two, we take each edge (X,Y ) in Er and select the relations from edges (X,Z) in E \ Er and (Z, Y ) in E to create a rule, again taking into account how frequently a length two rule creates paths from the tail nodes to head nodes of edges in Er.
In Rule Heuristic 2, we take each edge (X,Y ) in Er and find a shortest path from X to Y contained in the edge set E \ {(X,Y )} where the path length is bounded by a pre-determined maximum length. We then use the sequence of relations associated with the shortest path to generate a rule. We also use a 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 K0. Adding new rules. Each set Ki for i > 0, is constructed by adding new rules to the set Ki−1. 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 LPRi−1. Let δi ≥ 0 for all i ∈ Er be dual variables corresponding to constraints (4). Let λ ≤ 0 be the dual variable associated with the constraint (5). Given a variable wk which is zero in a solution of LPRi and associated dual solution values δ̄ and λ̄, the reduced cost redk for this variable is given by
redk = τ negk − ∑ i∈Er aik δ̄i − (1 + |Ck|)λ̄
If redk < 0, then increasing wk from zero may reduce the LP solution value.
To try make the reduced cost negative, we sort the dual values δ̄j in decreasing order, and then go through the associated indices j, and create rules k such that ajk = 1 via a shortest path calculation. That is, we take the corresponding edge (X,Y ) in Er, 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 Ki is only slightly larger than Ki−1. More precisely, we set |Ki| − |Ki−1| ≤ 10. We use the
dual values to indicate which facts are not currently implied by the existing set of chosen rules. If the reduced cost of a new rule is nonnegative, then we do not add that rule to Ki−1.

heading: 4 EXPERIMENTS
text: We conduct experiments on knowledge graph completion tasks with six datasets: Kinship (Denham, 1973), UMLS (McCray, 2003), FB15k-237 (Toutanova & Chen, 2015), WN18RR (Dettmers et al., 2018), YAGO3-10 (Mahdisoltani et al., 2015) and DB111K-174 (Hao et al., 2019). In Table 5, 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, WN18RR, 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 DB111K-174 given in Cui et al. (2021).

heading: 4.1 EXPERIMENTAL SETUP
text: We denote the reverse relation for each relation r ∈ R by r−1. For each fact (t, r, h) in the training set, we implicitly introduce the fact (h, r−1, t) doubling the number of relations and facts. For each original relation r in the training set, we create a scoring function of the form fr(X,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 to these queries. For each entity e in G, we calculate the scores fr(t, e) and fr(e, h) – here e is treated as a candidate solution to the queries (t, r, ?) and (?, r, h) – and then use the filtered ranking method in Bordes et al. (2013) to calculate a ranking for the correct answer (namely (t, r, h)) to the above queries. Ranks are computed using the random break method (option in NeuralLP (Yang et al., 2017)), and these are used to compute MRR and Hits@k (for k = 1, 3, 10) across all test facts.
We compare our results with the published embedding-based methods ConvE (Dettmers et al., 2018), ComplEx-N3 (Lacroix et al., 2018), TuckER (Balažević et al., 2019), RotatE (Sun et al., 2019), 5∗E (Nayyeri et al., 2021), and ATTH (Chami et al., 2020). 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-based 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 NeuralLP, DRUM, and RNNLogic. We also run AnyBURL for 100 seconds. Additional comparisons can be found in the 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
defaults suggested for different datasets. RNNLogic claims to use midpoint ranking, but actually implements a harmonic mean of possible reciprocal ranks in the presence of equal scores while calculating the MRR, which yields a 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 LPR0 by generating rules using Rule Heuristic 1 and Rule Heuristic 2, and then solve LPR0 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 LPR0 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 2 followed by solving the new LP. In other words, we create and solve LPRi for i = 0, . . . 5.
We search for the best values of τ and κ for each relation. We dynamically let κ̄ equal the length of the longest rule generated plus one. We then perform 20 iterations where, at the ith iteration, we set κ to iκ̄. For each combination of τ and κ, we take the optimal weighted combination of rules and compute the MRR on the validation data set, and select those τ and κ that yield the best MRR. We set the maximum rule length to 6 for WN18RR, and 3 for YAGO3-10, and 4 for the other datasets. Thus κ ≤ 100 except for WN18RR. We search for the best τ from the list of values in Table 11.

heading: 4.2 RESULTS
text: 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 a separate category as it is rule-based, but is similar to embedding-based methods in its entity-dependent KG representation. Henceforth, rule-based codes does not refer to AnyBURL. All our experiments (with rule-based codes) are performed on a machine with 128 GBytes of memory, and four 2.8 Intel Xeon E7-4890 v2 processors, each with 15 cores, for a total of 60 cores. We use coarse-grained parallelism in our code, and execute rule generation for each relation on a different thread, and solve LPs with IBM CPLEX (IBM, 2019). If one relation dominates the others (w.r.t number of facts, as in YAGO3-10), then our implementation becames essentially single-threaded.
In Table 1, we present results on Kinship and UMLS. Our method obtains better results than NeuralLP, DRUM, and RNNLogic on Kinship across all measures, and better MRR and Hits@1 values than these three codes on UMLS. This is true even though we generate relatively compact rules (see Table 4 ) and also use very simple rule generation heuristics. Therefore, for these datasets, even trivial rule generation heuristics suffice when used in conjunction with a nontrivial weight generation algorithm. The embedding methods are much better across all metrics. In Table 2, we present
results on FB15k-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-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, see Table 6 in the Appendix. This better scaling behaviour allows us to tackle large datasets such as YAGO3-10, which we give results for in Table 3. We use column generation, generating 10 columns in each iteration, and iterate only 5 times for a total of 50 candidate rules per relation. To compute negk, we sample 20% of the edges from Er, and compute the number of invalid paths that start at the tails of these edges, and end at the heads of these edges. For YAGO3-10 and DB111K-174, our column generation approach becomes essential. We are simply unable to process a very large number of rules. The ability to generate a 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.
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 a few hundred to a thousand generated rules, other than in YAGO3-10, where we only generate 50 rules. We get better MRR for similar levels of sparsity compared to NeuralLP and RNNLogic. For WN18RR and UMLS, we obtain state-of-the-art results with few rules. We could not extract rules from DRUM. RNNLogic chooses top-K rules for testing (K is an input parameter), and we run with the default K = 200 and K = 20. AnyBURL generates many rules and does not prune previously generated rules.

heading: 5 CONCLUSION
text: 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-the-art results for a number of standard KG datasets even with sparse collections of rules, and much faster than existing methods.

heading: A APPENDIX

heading: A.1 DATASET DETAILS AND RUNNING TIMES
text: 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 a machine with 16 CPUs and 1 GPU. Our times include the time to evaluate the solution on the test set. AnyBURL is run for a fixed time of 100 seconds. For WN18RR, DRUM and NeuralLP take 400 minutes or more, and RNNLogic takes over 100 minutes, whereas we take 11 minutes and less than 2 minutes with LPRules. We note that we use maximum rule length of 6 for WN18RR, but we do not know the maximum path lengths used in the other codes. DRUM takes over 8 days for FB15K-237 (as does NeuralLP on a different machine), which is why we do not run these codes on YAGO3-10 and DB111K-174. Our code can be sped up further if fine-grained parallelism were used (see the Appendix A.5).

heading: A.2 ADDITIONAL COMPARISONS
text: It is challenging to compare published codes for KGC as they differ in important ways.
a. Entity Ranking: There are different ways (Berrendorf et al., 2021; Sun et al., 2020) of ranking entities e that form candidate solutions to queries (t, r, ?) and (?, r, h) constructed from a test set fact (t, r, h), and the choice of the ranking method may have a significant effect on the final MRR, especially for rule-based methods, see Table 7. Assume m entities receive a strictly better score than the true answer h for the query (t, r, ?) and n entities receive the same score. Some ranking methods listed in Berrendorf et al. (2021) are: h receives a rank of m + 1 (optimistic), i.e., the best among all equally-scored entities, or m+ n (pessimistic), or k where k is a random number between m+ 1 and m+ n (random (Sun et al., 2020)). It is also observed in Berrendorf et al. (2021) that numerous codes give a nondeterministic rank between m + 1 and m + n based on the position of the correct entity in a sorted order of equal score entities. Other options are a rank of m+ (n−m)/2 (midpoint) (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 m+ 1 and m+ n is the same in random, whereas m+ (n−m)/2 is more probable as a rank than m+ 1 or m+ n in random break. The choice of the ranking method also depends on whether one assumes a closed or open world hypothesis. The NTP and NTP-λ codes referred to in Table 8 use an optimistic ranking method, whereas MINERVA uses a nondeterministic ranking method.
b. Query construction: Some codes, such as MINERVA, only remove right entities from a fact (t, r, h) in the test set to construct the query (t, r, ?), and do not evaluate performance on the query (?, r, h).
c. Hyperparameters and Experimental Setup: It was shown recently (Ruffinelli 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 et al. (2020) as a suitable method for KGC, but the codes NeuralLP and DRUM provide random-break 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-break 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 if we use midpoint ranking.
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 a similar fashion, though we still use random-break 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 (Berrendorf et al., 2021) ranking, as they sort scores 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 a higher score" - i.e., they use optimistic ranking. In our opinion, this accounts for the unusually high scores for UMLS obtained with NTP-λ. When we use optimistic ranking for UMLS, we obtain an MRR of 0.967. ComplEx
also uses optimistic ranking. Though we cannot prove it, we 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 in DistMult.
In Table 9, we copy results for FB15K-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 NeuralLP 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 FB15K-237. Thus, for the four datasets mentioned in this table and the previous one, our code returns state-of-the-art results among the rule-based methods compared here.

heading: A.3 PROOFS
text: We next present the proof of Theorem 1.
Proof. Let (η̄, w̄) be an optimal solution of IPR. By definition, w̄ has |K| components, and η̄ has m = |Er| components, all of which are binary, because of the form of the objective function. Let Ck be the clause associated with rule k. By definition, we have aik = Ck(Xi, Yi). Consider the function
f(X,Y ) = ∨k:w̄k=1Ck(X,Y ) = ∨k∈Kw̄kCk(X,Y ). (7)
Therefore, f : V × V → {0, 1}. As (η̄, w̄) satisfies equation (4), we have∑ k∈K aikw̄k + η̄i ≥ 1 for all i ∈ Er.
We can see that f(Xi, Yi) = 1 if and only if ∑ k∈K aikw̄k ≥ 1, and therefore
f(Xi, Yi) + η̄i ≥ 1 for all i ∈ Er.
Therefore, either f(Xi, Yi) = 1 or η̄i = 1. Furthermore, f(X,Y ) is a function for which fewest number of values η̄i are 1 or the highest number of values η̄i are 0, as (η̄, w̄) form an optimal solution of IPR. In other words, f(X,Y ) "covers" the largest number of edges of Er (covering means f(Xi, Yi) = 1) among all possible functions that can be formed as a disjunction of rule clauses with complexity at most κ. For each i such that η̄i = 0, we have
f(Xi, Yi) = 1 and f(Xi, Z) ≤ 1 and f(Z, Yi) ≤ 1
for all Z ∈ V as f(X,Y ) = 0 or 1 for any entities X,Y ∈ V . If we take the facts in the training set as a test set, and use f(X,Y ) as a scoring function and use optimistic ranking of scores, then for each i such that f(Xi, Yi) = 1 ≥ f(Xi, Z) and f(Xi, Yi) ≥ f(Z, Yi) for all entities Z, and therefore the rank of Yi is 1 among all entities Z while scoring (Xi, Z) (denoted by rri), and the rank of Xi is 1 among all the entities Z while scoring (Z, Yi) (denoted by lri). On the other hand rri ≥ 1 and lri ≥ 1 if f(Xi, Yi) = 0. Therefore 1/rri ≥ 1− η̄i and 1/lri ≥ 1− η̄i. The MRR of the prediction function is
( ∑m
i=1 1 rri
+ ∑m
i=1 1 lri )/2m ≥ 2(m− m∑ i=1 η̄i)/2m
= 1− 1 m m∑ i=1 η̄i. (8)
But ∑m i=1 η̄i is the optimal objective function value. Thus a lower value of ∑m
i=1 ηi yields a higher lower bound on the MRR computed via optimistic ranking.

heading: A.4 ANALYSIS OF YAGO3-10
text: 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 IsAffiliatedTo and playsFor, which together account for 64.4% of the facts in the training set, and 63.3% of the facts in the test set. In Table 10, we provide the rules generated by LPRules for these two relations. Here R_isAffiliatedTo 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 a relation. The MRR column gives the MRR value that would be generated if the test set consisted only of facts associated with the relation in the "Relation" column, and the weighted combination of rules
consisted only of the rules in the same line or above. Thus we can see that if we took only the first 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 ≥ 0.56× 0.633 ≈ 0.354, as opposed to the MRR of 0.449 that we obtained.
The information in the table suggests a direct correlation between the relations isAffiliatedTo and playsFor. Indeed, we verify that for about 75% of the facts (x, isAffiliatedTo, y), we also have (x, playsFor, y) as a fact in the training set. Similarly, 87% of the playsFor facts are explained by the isAffiliatedTo relation in the training set.
A natural question is the following: Is the second rule for isAffiliatedTo a “degenerate" rule and does it simply reduce to isAffiliatedTo because the entity b is the same as entity a when we traverse a relational path from x to y in the training KG. To give an example that this is not the case, consider the following fact in the test set: (Pablo_Bonells, isAffiliatedTo, Club_Celaya). In the training data, the following three facts imply the previous fact by application of the second rule: (Pablo_Bonells, isAffiliatedTo, Club_León), (Salvador_Luis_Reyes, isAffiliatedTo, Club_León), and (Salvador_Luis_Reyes, isAffiliatedTo, Club_Celaya). The first rule is also applicable as 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 are not repeated.

heading: A.5 ADDITIONAL EXPERIMENTAL DETAILS
text: Table 11 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 we use fewer candidate τ values.
Datasets Values of τ
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
Given the lists of values in Table 11, removing values from this list reduces the MRR, but not too much. But if we use entirely different values, the MRR can drop significantly. Indeed, the experiments in Table 12 show that the amount of weight given to negative sampling is very important.
Furthermore, one cannot choose the same value for different datasets, and it is best to search through a list, as we do.
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 to |Er| + 1, the number of edges labeled by relation r in the knowledge graph. Given candidate rule k in LPR, we need to compute aik = Ck(Xi, Yi) for each edge i in Er, where the ith edge in Er is Xi
r→ Yi. Computing aik increases superlinearly with increasing average node degree and increasing path length, and so does negk (both calculations involve an operation similar to a BFS or DFS). See Table 13 for increasing run times on WN18RR with increasing path length. The cost of solving a linear program (LP) grows superlinearly with the number of constraints. The larger datasets (WN18RR, FB15K-237, and YAGO3-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 in solving LPR, in the case of FB15K-237 and YAGO3-10, and also to reduced benefits of parallelism. For example, for YAGO3-10, the relations isAffiliatedTo and playsFor have 373,783 and 321,024 associated facts, respectively, out of a total of roughly a million facts. Most relations are completed in a short amount of time, while these two relations run for a long time on a single thread each. A natural approach to reducing the run time would be to sample some of these facts while setting up LPR, but we do not do this in this work. For YAGO3-10, we do not compute negk 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 can be parallelized are the computation of the coefficients aik in LPR, but we have not done so. We thus believe there is scope for reducing our run times even further. We note that the operations we perform are not well-suited to run on GPUs.
In Table 13 we give our results for WN18RR when we use rules of length 4, 5 and 6, with the results for length 6 copied from Table 2 in the main document. The best MRR is obtained using path length 6, 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 WN188RR.

heading: A.6 ADDITIONAL CODE DETAILS
text: For the experiments in this paper, in Rule Heuristic 1, we simply generate all length one and length two rules that create a relational path from the tail to head node for at least one edge (Xi, Yi)
associated with relation r, while creating LPR for relation r. The number of such rules is usually small (less than 50).
In Rule Heuristic 2, for every edge X r→ Y in Er (associated with relation r), we find a shortest path, using breadth-first search, from Xi to Yi in the knowledge graph G that does not use the edge X
r→ Y . However, when we perform column generation, we do not find a shortest path between Xi and Yi for every directed edge in Er. Instead, we only consider edges i ∈ Er 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 Xi and Yi which have large dual values.
During the search for the best τ abd κ values, we first set up LPR or LPRi (for some i, when we do column generation) for a fixed value of τ and κ. Subsequently, we do not add any more rules/columns, and instead change the values of τ and κ, and evaluate the resulting LP solution on a validation set by computing the MRR, and then choosing the τ, κ combination which gives the best value of MRR on the validation set. During training, we obtain a 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 or 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 we use is IBM CPLEX (IBM, 2019), which is a 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 our code which have CPLEX-specific functions calls would need to be changed.

heading: A.7 SOLUTION SPARSITY
text: One important feature of rule based methods is the interpretability aspect of rules. It is clear that link predictors with a 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 our code, we vary the upper bound on complexity of chosen rules in a 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 to select the number of rules per relation used in testing; see also Figure 2a in Qu et al. (2021) where the MRR is plotted against number of selected rules. In Table 14 we 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 to the other two codes.

Review summaries:
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.   The 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.   

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.