Faithful Rule Extraction for Differentiable Rule Learning Models
Authors: Xiaxia Wang
David Jaime Tena Cucala
Bernardo Cuenca Grau
Ian Horrocks
Venue: ICLR 2024 poster (2024)
Keywords: Faithful Rule Extraction
Rule Learning
Knowledge Graph
Datalog
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: There is increasing interest in methods for extracting interpretable rules from ML models trained to solve a wide range of tasks over knowledge graphs (KGs), such as KG completion, node classification, question answering and recommendation. Many such approaches, however, lack formal guarantees establishing the precise relationship between the model and the extracted rules, and this lack of assurance becomes especially problematic when the extracted rules are applied in safety-critical contexts or to ensure compliance with legal requirements. Recent research has examined whether the rules derived from the influential Neural-LP model exhibit soundness (or completeness), which means that the results obtained by applying the model to any dataset always contain (or are contained in) the results obtained by applying the rules to the same dataset. In this paper, we extend this analysis to the context of DRUM, an approach that has demonstrated superior practical performance. After observing that the rules currently extracted from a DRUM model can be unsound and/or incomplete, we propose a novel algorithm where the output rules, expressed in an extension of Datalog, ensure both soundness and completeness. This algorithm, however, can be inefficient in practice and hence we propose additional constraints to DRUM models facilitating rule extraction, albeit at the expense of reduced expressive power.

Published as a conference paper at ICLR 2024
FAITHFUL RULE EXTRACTION FOR DIFFERENTIABLE RULE LEARNING MODELS
Xiaxia Wang, David J. Tena Cucala, Bernardo Cuenca Grau, Ian Horrocks Department of Computer Science, University of Oxford, UK {xiaxia, wang, wewriddtenacccall. bernardo grau, ian. horrocks )
ABSTRACT
There increasing interest in methods for extracting interpretable rules from ML models trained to solve wide range of tasks over knowledge graphs (KGs), such as KG completion, node classification, question answering and recommendation. Many such approaches, however, lack formal guarantees establishing the precise relationship between the model and the extracted rules, and this lack of assurance becomes especially problematic when the extracted rules are applied in safety- critical contexts or to ensure compliance with legal requirements. Recent research has examined whether the rules derived from the influential NEURAL-LP model exhibit soundness (or completeness), which means that the results obtained by applying the model to any dataset always contain (or contained in) the re- sults obtained by applying the rules to the same dataset. In this paper, we extend this analysis to the context of DRUM, an approach that has demonstrated superior practical performance. After observing that the rules currently extracted from a DRUM model can be unsound and/or incomplete, we propose novel algorithm where the output rules, expressed in an extension of Datalog, ensure both sound- ness and completeness. This algorithm, however, can be inefficient in practice and hence we propose additional constraints to DRUM models facilitating rule extrac- tion, albeit at the expense of reduced expressive power.
INTRODUCTION
Numerous tasks over knowledge graphs (KGs) such as completion (Wang et al., 2021), 1), node clas- sification (Portisch & Paulheim, 2022). question answering (Lan et al. 2021) and recommenda- tion (Guo et al. 2022 Xian et al. 2019) can be formulated as a transformation from an input to an output dataset (e.g., KG completion transforms incomplete KG to its extension with the missing facts). ML models are widely employed to acquire these transformations from examples, as it is a more cost-effective approach than manual design and does not require domain expertise.
ML-based solutions face a challenge explaining predictions. Recent studies (Yang et al. 2017 Evans & Grefenstette 2018 Sadeghian et al. 2019 Qu et al. 2021 Ferreira al. 2022 Zhang al. 2023 Wang et al. (002) propose techniques to extract interpretable Datalog (Abiteboul et al. 1995) rules from trained models. However, many of these approaches lack formal guarantees establishing the relationship between the model and the extracted rules. Instead, they often rely on informal "explain" the model's behavior (Yang et al. 2017: Evans & Grefenstette/ 2018 Sadeghian et al. 2019 Qu et al. 2021). Such claims may be substantiated by empirical evidence showcasing the similarity between the model's predictions and the outcomes of rule application (Ferreira et al.) 2022). Nonetheless, the need for formal assurances regarding the alignment between model and rules becomes particularly critical when these rules are applied in safety-critical contexts or to ensure compliance with legal requirements for explainability.
claims that the rules "approximate"
Recent studies have explored the formal relationship between models and extracted rules in the context of Feed-Forward Networks (Ayoobi et al., 2023 Wang et al. 2022). Convolutional Neural Networks (Benamira et al.) 2023), and Graph Neural Networks (Tema Cucala et al. 2022a b). These works examine whether the rules exhibit soundness (or completeness), which means that the results obtained by applying the model to any given dataset always contain (or are contained in) the results obtained by applying the rules the same dataset. Faithful (i.e., both sound and complete) rule sets

---

Published as a conference paper at ICLR 2024
can be used explain the model's predictions. For example, assume that a model Mmed trained to suggest potential diagnoses predicts fact diagnose flu) when applied to the dataset
D Pmed= = findicaiieOOiifeeer, flu), indiea,iveOfffeeeer,, www. tuberculosis),
hasSymptom (alice, fever), contact((aiiee,, bob), diagnose(bob, flu)]
A medical professional can examine the extracted rules Rmed to understand model predictions. An incomplete rule set may fail support the predicted fact, leaving the prediction unexplained. An unsound rule, like diagnose(1, 3) < ttasSymptom(z;:) A indicativeO((z, y), may generate facts not predicted by the model, such as diagnose (alice, tuberculosis).
contrast, faithful rule set lacks spurious rules and guarantees an explanatory rule for each predicted fact. For example, the following rule r riing explains alice's flu diagnosis due to her fever and contact with a flu patient:
diagnose(z; y) f- hasSymptom(zzz 21) A indicativeOf( y) A contact(2, 22) A diagnose 22, y)
The analysis in Tena Cucala et al. (002bb) revealed that soundness for NEURAT.-L.P can be en- sured by selecting appropriate hyperparameters, but completeness cannot be guaranteed. Thus, the extracted rules may not be a faithful representation of the model.
In this paper, we study faithfulness guarantees in the context of DRUM (Sadeghian et 2019 an approach inspired by NEURAL-LP that has demonstrated superior empirical performance. DRUM exhibits sigmificant differences with respect NEURAL-LP. which makes the relationship between these approaches unclear. First, each DRUM model comprises multiple sub-models, initially applied independently to the input data, followed by the aggregation of their outputs; each DRUM sub-model resembles a NEUR model, but it contains much fewer parameters as it does not implement "skip connections" between network layers. Second, DRUM sub-models and NEURAL-L.P employ different mechanisms for learning rules of varying lengths. Third, DRUM can generate a broader class of rules, including inverse rules such as parent 3) + child 2) Given these disparities, the results from Tena Cucala et al. (2022b) for NEURAL-LP do not directly apply to DRUM.
In Section 2 we revisit the definitions of Datalog, DRUM, and the concepts of soundness, com- pleteness, and faithfulness introduced in Tena Cucala et al. (202bb). In Section 3 we analyse the faithfulness of rules extracted from a DRUM model. We observe that, much like in NEURAL--LA the behavior of DRUM can be characterised in terms of "counting" the distinct matches of rule's body within the input data. We can thus establish results akin to those in Tena Cucala et al. 2002bb) regarding NEURAL-LP. In Section 4 we present a method for extracting faithful set of rules from a DRUM model expressed in an extension of Datalog with inequalities and disjunctions in the rule body, enabling the necessary counting operations. This represents an advancement compared to prior research because the faithful rule extraction method in Tena Cucala et al. (2022b) applies only to significantly restricted NEURAL-LL models. However, we note that achieving practical imple- mentation of our method may be challenging due to the time complexity associated with the rule extraction algorithm. In Section 5 we propose two solutions to this issuc. Firstly, we introduce a mechanism that, given DRUM model and dataset, extracts rule set that is sound for the model and derives all the model predictions on the given dataset. Secondly, we impose constraints on the DRUM models facilitating the extraction of a faithful rule set, at the expense of reduced expressive power. Specifically, we introduce two variants of the model, MMDRUM and SMDRUM, each striking distinct balance between expressivity of the model and the effectiveness of rule extraction.
In Section 6, we conduct a comprehensive evaluation on KG completion tasks. Amongst other findings, our experiments show that SMDRUM and MMDRUM obtain competitive performance and confirm the practical fcasibility of the rule extraction algorithms proposed in Section 5
2 BACKGROUND
Datalog. A signature consists of disjoint, countable sets of constants and predicates, where each predicate is assigned non-negative arity. A term is a variable constant. An atom is expres- sion of the form R(41.- ... f,,). where R is an n-ary predicate and t., in are terms. A fact is a variable-free atom, and dataset is a finite set of facts. A Datalog rule is expression of the form:
H H Bi A
Br, e 0,
'There is an additional difference concerning the way in which the model's 's parameters are generated; how- ever, is irrelevant our analysis, which does rely on the method used compute the model's parameters.
2

---

Published as a conference paper at ICLR 2024
where H and B, for 1 S i S l are atoms. Typically, H is called the head atom, and each B, is called a body atom. The value & E is the length of the rule. We do not make the usual safery requirement that each variable in H must appear in some B, In fact, the rule body can be empty if f = 0, in which case we write T A Datalog program is a finite set of rules.
For mapping of variables to constants and term conjunction X with variables in the domain of a, Xo is the result of replacing each x in X with (I)) For a rule r of the form ( the immediate consequence operator T, maps dataset D to the smallest dataset T, (D) containing Ho for each mapping a of variables in r to constants in 'D that grounds the body of r in D i.e. that satisfies B, E D for all 1 < i E. For a Datalog program R. TR defined as TR (D) UPER (D).
Vectors, Matrices and Tensors. For each E N, we use the notion of n-dimensional ten- sor (Yang et al. 2017 Sadeghian et al. 2019) over R (e.g.. a matrix is a 2-tensor). For an n-tensor A, If M and N are matrices of dimension m x n. and n x p. respectively, then the max-product of M and N, written M @ N, is a matrix of dimension m p whose element at position and j is equal to max M(i,)) k) N(k.)).
( 82,-.. (n) is the element at position (i1 ".. ,In).
...
The DRUM Model. DRUM (Sadeghian et al. 2019) assumes signature with 8 binary predi- cates R1, R2: ... Rs and is designed to learn rules of the form
RA y) t 1/1, t/ka A A th, with 2 1 and h hn E (1,",.66)
where dkk, is of the form Rs, (z,-1, 24) or (2,, 2111,, with 2u = x and be = y. We will show in Section B] however, that rules of this form are not sufficiently expressive to faithfully characterise DRUM models. For instance, our example rule Taing in Section 1 is not of this form.
A DRUM model M of rank N 2 and depth L 2 1 is a tuple (a'.... "......,,, 3), where each a for 1 < h S a 3-tensor over [0, xxx of (learnable) parameters and E E is a threshold for prediction. The rank determines the number of considered "sub-models", as men- tioned in Section [I, Models with higher rank are more expressive and can simulate a richer set of rules (Sadeghian et al., 2019). The depth L determines the maximum length of rule that can be learned. A DRUM model M induces a transformation TM over datasets as we specify next. Given dataset D, let C .., Ce be the constants in D arranged in fixed but arbitrary order. For each 1 S N 26 + 1, an e x e binary matrix M, is computed by setting to 1 all values Ma(i,.) satisfying one of the following conditions: (1) R2 (c,, cÿ) D and 1 S k S 6, (2) RR-s(cy,c)) c;) E and 6 6 < 1: < 26, or (3) j and i = 25 + 1: all remaining values are set to 0.
Matrices M, for k I 8 are adjacency matrices representing facts in D. DRUM can be concep- tualised as extending the input dataset with new facts over 5 + 1 fresh predicates in the remaining matrices: fact R28+1(c, c) for each constant e in D and fact Rs R& (c3, c. for each Re eÿ) E DD representing its inverse. The adjacency matrices M3+1, ... M26+1 capture the new facts. Next, DRUM represents each constant c, with an one-hot vector V. E { 1] in which vs(s) and elsewhere. Then, for < h < 6, DRUM computes a vector v as Equation (3).
26+1
(v+)T=(V.)) ΣII
Σ
aL(,,,)) MR .MA
(3)
Vector v indicates, for each StS c, whether the fact Rd (Co, ct) is in (D), in the following way: R.(C.. (t) E (D) if and only vt is strictly greater than the prediction threshold B..
Rule Extraction in DRUM. Rules are extracted from trained DRUM model M of depth I. by first computing a confidence score or E R for each rule of the form (2) with length at most T.. We next show how to compute such score. In the simple case where r has length exactly L. the score is a, = En of where each of is simply the product of the model parameters correspond- ing to each body atom of for the i-th sub-model. In particular, for R2 the head predicate of r, parameter ai, kg) (respectively, a ky + 6)) is associated to a body atom Rg, (z/-1, 2,) (re- spectively, Rs, (zj, 1)-1) at position S < L and sub-model < S N. Finally, if the length of r is smaller than L, we first consider all the ways in which can be extended to an equivalent
Rules are applied datasets with finitely many constants, and thus only finitely many facts can be derived.
3

---

Published as a conference paper at ICLR 2024
rule of the form (2) and length exactly L by padding the sequence of predicates in the body with the
identity predicate R28+1. For example, if = 2, a rule R2(x,y) < (2. y) can be extended as R2(2, u) < Rí (2t, =1) A R26+1 (21, and R2(2, y) + R28+1 (2x, =1) A Ri (21, y)- We can compute a value for each of these rules as before and set ar, as the maximum of these values.
For rule r of the form (2) the set S. contains all sequences (K).... .... .k)) that can be obtained from (A1.... ke) by replacing k, by ky + if 4/k, is of the form Rx, (2,, and then padding it (if needed) with the value 25 + 1. Then, the confidence score O, for r is
0r MAX
EII
a (1.1,
(4)
(Rg N EE
1=1 ==1
For each E R, RMy is the set of all rules in the form with & S L. and score higher than Y
Relations between Models & Programs. Program R. is sound for model M if R (D) C (D) for any dataset D. Conversely, 'R is complete for M if (DD C (D) for any dataset D. Finally, we say that R. is faithful for M if it is both sound and complete for M (Tena Cucala et al. (0226).
3 ANALYSING FAITHFULNESS OF RULE EXTRACTION IN DRUM
We begin by describing the behavior of DRUM model M of rank N and depth L. We show that when M is applied to a dataset D, the decision made by M as to whether to return a fact Ra (c, a)) can be characterised by considering each rule of the form (2) with E S L and head predicate R and then counting the distinct matches of the rule body in D where x is mapped to c2 and y to C..
Lemma 1. For a dataset DD with constants C1, C1,'." Ce. vector va computed by M for S 8 S c and 1 S h S 5 is equal to EvERyay
where Rh, is the set of all rules of the form Q
with 1 < é S. L (resp. f = 0) and head atom RA(I, y) (resp. Rn(2, x)), (F(()) is a non-negative function of r that depends only on the parameters of M, and Qr, is a vector of dimension e such that, its t-th element is (resp. 0) if the body of r is T and the number of different mappings that ground the body of r in D and map x to C2 and y to ct.
(resp. t + s), and otherwise it is
1, and all other tensor elements equal to Suppose contact and diagnose are the first and second predicates in the signature, respectively, and alice and flu in positions and of the constant order, po spectively. Equation (3) ensures that the t-th element of v² represents the count of distinct constants where both contact( (alice,, e) and diagnose(c. flu) diagnose(alice,, flu) is derived if and only if alice has been in contact with at least two flu patients, indicating at least two valid paths from olice to flu.
Consider a DRUM model with N = 2. 1.5, a² 11,
1, a²
in the dataset. The value of B ensures that
In (3), the right-hand side computes a product of the one-hot vector v. and L adjacency matrices for an extended dataset D' with inverse and self-reflecivve facts. Each vector element corresponds to a constant C and represents the count of paths within D' of length L from c, to q.. These paths traverse edges labeled with predicates corresponding to the adjacency matrices, following the specified sequence. Each path corresponds uniquely to a subset of 'D grounding of the body of a rule (2) and is associated with a weight derived from products and summations of elements of the tensor a². The aggregation of such weights yields the expression in Lemma [ showing that DRUM shares similarities with NEURAL-LP, where predictions depend also on the counts of rule matches. The approaches used by NEURAL-LP and DRUM to compute rule weights, however, differ significantly and it is unclear whether NEURAL-LP models can be simulated by DRUM models.
The aforementioned similarities allow to derive results analogous those obtained for NEURAL- LP concerning the connection between the model and the rules extracted from it.
Theorem 1. Program RRRR is sound for M = (at.... a² 33) whenever y 2 B. Furthermore, there is a DRUM model M' (a'). (a.)....... a 6, ,,²) such that R M,
DRUM is for M' for any ? < B.
Hence, by selecting suitable value for 7, it is possible to ensure the soundness of the extracted rules, Nevertheless, achieving completeness cannot be guaranteed.
Theorem 2. There exists DRUM model such that no Datalog program is faithful for it.
4

---

Published as a conference paper at ICLR 2024
4 FAITHFUL RULE EXTRACTION FOR DRUM
Theorem shows that DRUM models cannot be fully expressed using Datalog. This unsurprising considering that DRUM models are characterised in terms of the counts of unique matches of rule bodies in datasets deriving relevant predictions. In contrast, Datalog rules derive a fact whenever there exists match of the rule body in the data, regardless of the count of distinct relevant matches. Datalog can, however, be extended with counting (Dantsin et al.) (001) by introducing inequality atoms in rule bodies interpreted under the Unique Name Assumption (UNA), which stipulates that any two distinct constants must refer to separate entities. For instance, consider the following rules:
R2 R2 v)
R1 2)) A R1 (2), v) A RA (z,, 24) R1 (27,
(5)
(2, v) + R1(2, 2 A Ri (2).2)) v) A R1 (z, 2 A R (21 y) A 2 =
(6)
rule (5) derives fact (2 03) through a match assign- ing + C1. y + c3. 2 + C2 and 2 + c2. In contrast, rule (6) does not apply to Dj since variables zi and 2 cannot be mapped to the same constant. On dataset D2 = D2 U Ri (c1, c4), R1 (c1, ca)), however, both rules derive Ry(c1,cs) In particular, rule (6) admits the match + CD y C3+
On dataset Dj = {Ri(C1 02): R1 (e2,
z| H C2 and 2f + C4 given that the inequality c2 # ca holds by the UNA.
In this section, we demonstrate that such extended Datalog programs can faithfully represent DRUM models. Additionally, we introduce disjunction in the rule bodies: this is a convenient extension that can (exponentially) reduce the number of rules required without increasing the expressive power of the language. Indeed, each rule with disjunction in the body is equivalent to multiple disjunction- free rules. For example, the rule R3(1, y) & (R1 (I, 21) V R2(x, 21)) (21. y) V (2 8)) is equivalent to the four rules of the form Ra y) + RR, (I, =1 Reg (Z1, y), with {ki, 42 S (1,
The basic building block in rule bodies is multipath conjunction specified by a cardinality C E N and a core V' with the same structure as the rule body in Equation (2). Intuitively, a multipath conjunction consists of C' copies of its core where variables other than æ, y have been renamed: each such copy represents "path". Mcanwhile, inequalities are incorporated to guarantee that no two paths can be matched to the dataset in an identical manner. Thus, a multipath conjunction is satisfied if it admits at least C' distinct matches of its core agreeing on the assignments of variables and y- Definition 1. Let V be conjunction of length l 2 in the form of the rule body in 2 A multipath conjunction é with core v and cardinality C' E N is of the form
C A
④ =
V
A
V 2 x Vimi
(7)
ISisi's
where V replaces in V each z by =t for sisl-1. Its length is multipath rule of length L has head Ra(x, 3) (resp. (x,xx)) and its body is conjunction of P > 1 (resp. P 2 0 and where x = y) multipath conjunctions of length < L and pairwise disjoint variables other than x and y.
The definition of the immediate consequence operator is standard and given by the well-known semantics of Datalog with inequalities and disjunction (Dantsin et al. 2001) under the UNA.
Counting in multipath rules is limited by the cardinalities of their multipath conjunctions. In con- trast, DRUM models face no such restrictions as the relevant counts are data-dependent and can become arbitrarily large. To address this challenge, we turn to Lemma [] where M assigns a "weight"" (r) to each rule of the form (2). There no need to count the matches of a rule r with weight zero, as the resulting value will be multiplied by zero. Similarly, when there is at most one body atom, a single match is possible. For positive weights and rules with multiple body atoms, there is minimum number of matches ensuring that the corresponding value in vector va exceeds the model's prediction threshold 3. regardless of the other rules. The threshold will be met the number of matches wr) for r reaches [r) + 1. Thus, we can ignore rules featuring multipath conjunctions op with cardinalities exceeding w (Z, y) + Mp). where Up is the core of dp: any such rule would be equivalent to the rule obtained by substituting Cp with wi (Rn (2, y) + Wp). This leads to finite set of relevant multipath rules, and the only remaining challenge lies in constructing the specific subset characterising the model.
Algorithm outlines the procedure for extracting faithful program from DRUM model. It begins by initializing the output program as an empty set (line 1). Additionally, it creates a list Q encom- passing all conjunctions serving as the body of rules in the form of ( with length e < L,, followed
5

---

Published as a conference paper at ICLR 2024
Algorithm 1: Multipath Rule Extraction.
Input: A DRUM model M = -a',...,............. a², 9), and a rule extraction threshold 7y.
Output: A multipath program
R 0:
:= list of all conjunctions in form the body 2 with S L, ending with
foreach h E (1. .) do
foreach [k1, kr] with & E {1, [1..... 28 + 1) do
K1. k3] = remove all 28 +
foreach j {1.... 2
k S then b == Ray (z)- clse b == Ba, 222
i then r: (x, v) - Nラ=1 زر elser =- (2( x)
if pr undefined then yr 0:
fo- :===00 p,, Σ IT k;);
11
foreach i E (1, [2 11 do
Ty:= n.:=Ra(;; (z.
(((1::
( has atom then foreach [Ct, C -1 with C; {0. ....... , do
1; clse wi 0
14
15
if C = 0 then == T; else ar == multip. conj. of care (2(1) and cardinality Cú
if Σ [ C 9r then R = R u f (2, y) + A p.
16
17
if Σ
C Pr. + Prim y then R = R C (R, + A pdl ++}]
18 return R;
by T (line 2). All elements of Ω except the last are possible cores of multipath conjunctions. The subsequent steps of the algorithm involve iterating over all predicates Rg in the signature (line 3). Within each iteration, it adds necessary multipath rules with head atom R, y) and R2 (x, x) to the output program. Specifically, it first computes the function ΩM from Lemma I for each rule as Rg (z, y) + V with V in Ω and (x, + T, with the results stored in s,, (lines 4-10). Follow- ing this, for each rule r, the algorithm computes an upper bound on the cardinality of multipath conjunctions with core V (lines 11-13). Subsequently, it enumerates all rules with head predi- each multipath conjunction does not exceed the computed bound
cate Rr where the cardinality for its core. This enumeration is performed by considering all combinations of cardinalities (line 14) for each core (i.e., each element of Ω except T) and constructing the corresponding rules for each combination (line 15). The algorithm calculates score for each rule by summing the products of each multipath conjunction's 's cardinality with the weight assigned by PM to its core. The score is compared to a threshold y E IR and the rule is added if the threshold is exceeded (lines 16-17).
The following theorem establishes the correctness and complexity of our rule extraction algorithm. Theorem 3. Program RMP M,y extracted by Algorithm D on input M (at,.... a² .), is faithful L+1 to Mo = B. Furthermore, Algorithm terminates in (L (2 (N (N+un w(())) steps, where w is the maximum value of ( for rule of the form with l < T..
In the example from Section 3 the extracted program would consist of the following rule of the form with core contact(2;, 2) diagnose y) and cardinality 2:
diagnose(1, contact(w, 21) diagnose(21 y) contact(2, 22) A Sitggosse(z2.1) A # z2.
PRACTICAL RULE EXTRACTION
The complexity of Algorithm 1
underscores the difficulty of extracting faithful programs from DRUM models. We next propose two approaches for addressing this challenge.
5.1 RULE EXTRACTION FOR A FIXED DATASET
Our first solution involves extracting (usually small) subset Rh of sound rules for M that explain all the model's predictions on a given dataset D. Focusing on a concrete dataset suffices in scenarios where data is not subject frequent updates, and makes rule extraction practically feasible.

---

Published as a conference paper at ICLR 2024
Algorithm 2: Multipath Rule Extraction for a Fixed Dataset.
Input: A DRUM model M = (a',...,
,e",,..,, a², 19, and dataset D.
Output: A multipath program.
R: 0: Paex == {[e.] Ra (es, ca) (M())), Pai == Poexi
3 foreach; j E [1....:1. do
Ponment == Paeui
Puex 0;
while Peurrear not empry
pop I... C2/) from Peunnut ;
foreach R& (Cur, ) E D do Paeu := Pars U ff. Car, crl];
foreach R& Rg(cr, G2)) E D do Prea == Panu U o Cr,, dell
10 Pau == Pan U Prent
foreach RA (c,, 6e) (D) do
12
p: :==11
13
count + 0:
14
foreach [c=, kl,... ... kz; 0o] E Pay do
15
foreach j {1.....
if k; I ā then wh == Rey (z)= else R 25-1)
16
count(A j=1 43 = count (A 4T 1: foreach & count(u)
17
18
append to p multipath conj. of core ab and cardinality min (count(()).) (w)), (Ra y) - +));
19
if o t then R: = R (N, y) + pt: else R. = RU ( x) + ply + xt}:
20 return R;
Algorithm Sattiam@@impp iimplements this idea. Given a model M and a dataset DD the first part of the algorithm applies M to D and computes all "paths" Pan of length at most L in D that start from constant c, featuring in a fact of the form (c,, ca) (D). The set Pall is initialised with paths of length (i.e.. all relevant constants). Subsequently, for each S S L, it iteratively determines the set of all paths of length j (lines 4-) This is achieved by considering all paths with a length of j (line 7) and examining all possible extensions they undergo (lines 8-9). The second part of the algorithm adds a rule r to R for each fact (c, c:) in (D) so that the application of r to D derives this fact. Rule is initialised with an empty body (line 12). Then, the algorithm counts all paths Pall that start in Cs. end in C (line 14), and traverse the same sequence of predicates (line 15 16-16), and adds a corresponding multipath conjunction to the body of (lines 17-19).
Theorem 4. Program R2 extracted by Algorithm 2 for DRUM model M = (a)..... a² 3) and a dataset D satisfies TRE (D) = TM(D). Furthermore, Algorithm terminates with time complexity (((8)) 4. (N L 28 (
The complexity of Algorithm 2 depends on the structure of D and (D). If their adjacency ma- trices are dense, the algorithm will exhibit exponential behaviour. In practice, however, the matrices are usually sparse (see Table As shown in Section program RM can be efficiently computed.
5.2 FAITHFUL RULE EXTRACTION BY LIMITING MODEL EXPRESSIVITY
Our second approach involves simplifying DRUM models so that extracting faithful programs from them becomes practically feasible, at the expense of decreasing the expressive power of the model.
A key source of complexity in Algorithm I is the need to enumerate all relevant multipath rules. In particular, the enumeration of all possible combinations blowup. This can be avoided by sacrificing the model's 's capacity to count distinct rule matches in the data. Instead, it goes back to Datalog, retaining only the capability to check whether the body atoms of rule can be matched not. This simplification can be achieved by pushing the vector (v.)² inside the product and sum operators in Equation which yields an equivalent expression- and then replacing the sum over & with max aggregation, and matrix products with matrix max- products. The resulting expression cannot be written in a compact form as in Equation (3), but we can write it concisely by using an inductive definition. We call the resulting model SMDRUM.
cardinalities causes an exponential
7

---

Published as a conference paper at ICLR 2024
Definition 2. An SMDRUM model is defined as DRUM model, but Equation by (vA)T= Σ Di=1 uf, where u.. (V,)T, and un max1g4526+1 a² (i,j,
3 is replaced
NV
M
for 1 isjs
This restriction limits expressivity: each SMDRUM model is equivalent to a set of multipath rules where each rule has up N multipath conjunctions without inequalities (i.e., of cardinality 1). Such rules, however, are still more expressive than those of form 2 for instance, they include rule Idiag from Section | They can be extracted with simplified version of Algorithm exponential time. Proposition 1. For an SMDRUM model M there exists program RM of inequality-free multipath rules computable in exponential time in M' size such that (D) =TRaM (D) for any dataset D.
Unfortunately, extracting a faithful program from SMDRUM model remains challenging due to the large number of distinct combinations of N multipath conjunctions. To address this issue, we limit model expressivity further by replacing the sum over 1 S S N by another max aggregation.
Definition 3. An MMDRUM model is defined as an SMDRUM model, but where the sum over 1 S i S N is replaced by a max function.
The advantage of MMDRUM is that we can extract faithful program by simply enumerating all rules of the form 2 then computing the score for each rule using a variant of expression (4)
max max II a (t,i,))) O.Mrr (K4 JES ISPSN
(8)
and then outputting those rules with score higher than a threshold y E R. This can be achieved efficiently by taking advantage of structure-sharing between rules (see Appendix [B. The downside the further loss in expressivity, as we no longer can express commonly used rules with multiple atoms involving variables x and y in the body e.g., citizenOf(z,, v) + bornIn v) A livesIn(z, y).
Theorem 5. For an MMDRUM model M of depth L, the program containing each rule r of the form 2 with & S L or R(x, x)) + T such that aMrr > B is faithful for M.
EVALUATION
We evaluated MMDRUM, SMDRUM, DRUM, and NEURAL-LP (as a baseline) on the inductive KG completion task. Besides, also applied and evaluated our rule extraction methods introduced in Section 5 All experiments were conducted on a Linux workstation with a Xeon E5-2670 CPU.
We followed the methodology of Yang al. 2017) evaluate DRUM models KG completion tasks. We considered an inductive setting, where constants seen at test time may not have encoun- tered during training. This is in contrast with the Iransductive setting, where all relevant constants occur already in the train set (Bordes et al. 2013 Sun et al. 2019).
We used the 13 benchmark datasets (Appendix C for inductive KG completion by Teru al. (2020) based on FB 553-237 (Toutanova & Chen 2015). NELL-995 (Xiong et al.) 2017). WNI8RR Dettmers al. (2018). and Family (Kok & Domingos, 2007), preserving the splits for train, validation and test. We selected L = 2 for all models and rank N = 3 for all DRUM-based models. Each model was trained up to 10 epochs. Threshold | E (0, 1) for each model is hyper- parameter. We tried several values and picked the one maximising F1 F1-score on validation sets.
We evaluated each model using precision, recall, accuracy, area under the precision-recat curve (AUPRC), and Fl score as metrics. The results are presented in Table [ Notably, DRUM outperformed both MMDRUM and SMDRUM in terms of overall performance, demonstrating the ability to exploit higher expressive power in practice. For most FB 15k-237 and NELL-995 datasets, the four models exhibited comparable performances, while for WNISRE datasets we see significant disparities. In particular, NEURAL-LP showed lower recall than all DRUM-based models, suggest- ing that the use of multiple "sub-models" (N > 1) can be critical in practice, even for MMDRUM.
We also implemented the rule extraction algorithms in Section 5 and applied them the inductive KG completion benchmarks. In all cases, both Algorithm 2 and the algorithm for MMDRUM (Ap- pendix B) succeeded to compute the corresponding rule sets in less than 3 minutes, which suggest
8

---

Published as a conference paper at ICLR 2024
Table Results (%) of DRUM (D), SMDRUM (S) MMDRUM (M) and NEURAL-LP (N).
Precision
Recall
Accuracy
AUPRC
FI Score
M
D
M
D
M
N
S
D
M
N
V1
47.2
47.2
48.2
81.9
44.9
44,9
43.9
28.8
47.3
47.3
48.3
61.2
49.6
48.4
51.6
50.0
46.0 46.0
45.9
42.6
V2
53.8
53.9
58.9
89.3
56.3
56.3
54.6
33.3
54.0
54.1
58.3
64.6
60.5
60.2
63.3
60.8
55.0
55.1
56.7
48.5
V3
55.7
55.6
61.0
80.6
50.1
$0.4
48.9
41.8
55.1
55.1
58.8
65.9
58.7
58.0
60.6
59.4
52.7
52.9
54.3
55.1
V4
59.5
59.5
72.6
92.7
$5.0
54.1
49.2
40.9
58.7
58.6
65.3
68.9
62.8
62.3
65.1
64.7
57.1
56.6
58.7
56.8
V1
100
97.2
97.4
100
19.0
70.0
76.0
13.0
59.5
84.0
87.0 56.5
66.9 77.5 84.4 65.9
31.9 81.4
85.4 23.0
V2
64.5
75.4
75.0
75.2
71.6
66.5
66.9 67.6
71.6 74.6 70.8
69.1
69.5
68.9
V3
62.2
62.1
62.6 62.5
79,4
79.0
78.5
77.1
65.6
65.4
65.8 65.4
77.2 75.6
82.0
76.0
69.7
69.5
69.6 69.1
V4
66.4
66.4
66.4
81.4
77.6
77.6
77.6
59.9
69.2
69.2
69.2
73.1
74.3 76.3
81.0
71.5
71.6
71.6
71.6
69.0
WNISRR
V1
68.2
79.1 93.6 86.7
68.6
64.4
62.2
20.7
68.4 73.7 79.0
58.8
68.1 72.6 75.0
65.5
68.4 71.0
74.8
33.5
V2
57.3
76.0
100 77.8
67.1
62.4
60.8
15.9
58.5
71.3
80.4 55.7
60.4 67.7
73.4
59.1
61.8
68.5
75.6
26.4
V3
99.4
29,9
29.8
27.8
39.5
63.8 54.0
34.5
40.4
34.7
33.1
37.3
43,4
16.2
V4
68.1
78.0
94,2 87.6
59.3
59.2
59.5 9.38
65.8
71.3
77.9 54.0
62.1 66.7
70.1
61.2
63.4
67.3
72.9
16.9
Family
93.3
92.7
97.0 94.9
92.9
87.7
82.9 92.8
93.1 90.4 90.2 93.9
94.4 94.1 94.3 94.4
93.1 90.1
89.4 93.8
Table 3: Rules extracted from Family dataset.
Table 2: Rule Extraction Com- pleteness (%) with 7 = B.
Top 10 rules extracted by MMDRUM
Top 10 rules of SMDRUM
brother(ar, 0) +- brother(,r, brother(2.
uncle( y) 4- brother(z, a) uncle(a.
8
0.0001
0.001
0.01
0.1
sisten(z, v) <- daughter(zz,)) A mothen(2z
3.07
0.00
daughter[a;; v)
(2))er((,,))))))))))) daughter((..]
V2
6.16
5.84
0.00
0.00
aunt(>; y) t- sister(z,, x) aunt(z.
V3
3,65
6.25
6.25
nephew(ss, y) +- nephew(s: =] A brother(2,
PB1
V4
5.02
5.23
3.92
5.88
nephew(s. v) son(z,,)) brother(2,
NEL -95
6.19
6.13
sister(z. 6- sister(a. sister(
V2
5.93
6.19
6.25
0.00
son(z. v) < brother(z, A daughter((=,)) niece(z.y) daughter((;,)) brother(s.g))
V3
V4
3.65
4,05
5.74
1.70
Top rules w. different head atoms SMDRUM that not captured by MMDRUM
WNI BRR
VI
5.28
5.74
V2
5,81
5.74
4.62
5.88
sister(z. y) <- sister(a, ax] dister((11.0 A (isterfar 22) A brother(y, 22)
V3
4.91
nicce(z, v) <- sister(æ,, 3 nicco (1) sister(a; (z 92) uncle(g.
V4
5.81
5.62
4.51
4.78
brother( y) 6- brother(an, a1] brother(21, 3) brother(ar, 22) sister(2a. son(z. v) < brother(z, =1) father(y. a)) brother(ar, 22) son(=2, y)
nephow(s, y] 4- brother(a,, 3x) A nephew(2), D) brother(z, 22) aunt(y, 2x)
the practical feasibility of our approach. Additionally, we verified empirically the theoretical guar- antees for these algorithms provided in Theorem and Theorem
We implemented the incomplete Datalog rule extraction algorithm for DRUM described in Section 2 We computed the proportion of model predictions covered by the extracted rules for different predic- tion thresholds. The results in Table 2 show that the rules derive less than 7% of the facts predicted by the models, which suggests that they are insufficient to explain the predictions of the models.
Finally, examined the extracted rules the Family dataset for MMDRUM and SMDRUM (the algorithm for SMDRUM run best effort for a fixed length of time). Table 3 depicts the rules ex- tracted from MMDRUM with the highest score. Some of these the rankings obtained for both models are similar. We also show the highest ranked rules extracted by SMDRUM of the form (2). Many of these are in practice irrelevant and suggest overfitting: this makes sense since the performance of MMDRUM in this dataset is close to that of SMDRUM.
also extracted for SMDRUM and
7 LIMITATIONS AND FUTURE WORK
Rules generated by our approach may be challenging to interpret, as they contain many body atoms. Furthermore, obtaining a faithful program with inequalities for a DRUM model using Algorithm can be challenging in practice. Our first priority will be to devise optimisations for Algorithm that can significantly prune the search space of rules. We also aim at enhancing interpretability by devising algorithms that prioritise shorter rules. Finally, will extend analyses to models such as ÖILP (Evans& & Grefenstette 2018), and explore generalisations of DRUM to capture rules with higher-arity predicates.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
The proofs of all the lemmas, theorems, and propositions in this paper are provided in Appendix A The datasets and source codes used in experiments available from the GitHub repository with documentation http:///.....tto.oooo//////////a
ACKNOWLEDGMENTS
This work was supported by the SIRIUS Centre for Scalable Data Access (Research Council of Nor- way, project 237889), Samsung Research UK, the EPSRC projects AnaLOG (EP/P025943/I)) OA- SIS (EP/S032347/1), UKFIRES (EP/S019111/1), ConCur (EP/V050869/1), and the AIDA project (Alan Turing Institute).
REFERENCES
Serge Abiteboul, Richard Hull, and Victor Vianu, Foundations of Dulabases. Addison- Wesley, 1995. ISBN 0-201-53771-0.
Hamed Ayoobi, Nico Poryka, and Francesca Toni. SpArX: Sparse argumentative explanations for neural networks. In Proc. of the 26th European Conf. on Artificial Intelligence (ECAI 2023), pp. 149-156, 2023.
Adrien Benamira, Tristan Guérand, Thomas Peyrin, and Hans Soegeng. Neural network-based rule models with truth tables. In Proc. of the 26th European Conf. on Artificial Intelligence (ECAI 2023), pp. 223-230, 2023.
Antoine Bordes, Nicolas Usumier, Alberto Garefa-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Proc. of the 27th Conf. on Neural Information Processing Systems (NeurIPS 2013), pp. 2787-2795, 2013.
Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374-423 2001.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2D knowledge graph embeddings. In Proc. of the 32nd AAAI Conf. on Artificial Intelligence (AAAI 2018), pp. 1811-1815 2018.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
João Ferreira, Manuel de Sousa Ribeiro, Ricardo Gonçalves, and João Leite. Looking inside the black-box: Lagic-based explanations for neural networks. In Proc. of the 19th Int. Conf. Principles of Knowledge Representation and Reasoning (KR 2022), 2022.
Qingyu Guo, Fuzhen Zhuang, Chuan Qin, Hengshu Zhu, Xing Xie, Hui Xiong, and Qing He. A survey knowledge graph-based recommender systems. IEEE Transactions Knowledge and Data Engineering, 34(8):3549-335 2022.
Stanley Kok and Pedro M. Domingos. Statistical predicate invention. In Proc. of the 24th Int. Conf. Machine Learning (ICML 2007), pp. 433 440, 2007.
Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. A survey complex knowledge base question answering: Methods, challenges and solutions. In Proc. of the 30th Int. Joint Conf. on Artificial Intelligence (IJCAI 202/), pp. 4483 4491, 2021.
Jan Portisch and Heiko Paulheim. The DLCC node classification benchmark for analyzing knowl- edge graph embeddings. In Proc. of the 2 st Int. Semantic Web Conf. (ISWC 2022), pp. 592-609, 2022.
Meng Qu, Junkun Chen, Louis-Pascal A. C. Xhonneux, Yoshua Bengio, and Jian Tang. RNNLogic: Learning logic rules for reasoning on knowledge graphs. In Proc. of the 9th Int. Conf. on Learning Representations (ICLR 202/), 2021.
10

---

Published as a conference paper at ICLR 2024
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: end- to-end differentiable rule mining on knowledge graphs. Proc. of the 33rd Conf. on Neural Information Processing Systems (NeurIPS 2019), pp. 15321-15331, 2019.
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. RotatE: Knowledge graph embedding by relational rotation in complex space. In Proc. of the 7th Int. Conf. on Learning Representations (ICLR 2019), 2019.
David Jaime Tena Cucala, Bernardo Cuenca Grau, Egor V. Kostylev, and Boris Motik. Explain- able GNN-based models over knowledge graphs. In Proc. of the 10th Int. Conf. on Learning Representations (ICLR 2022), 2022a.
David Jaime Tena Cucala, Bernardo Cuenca Grau, and Boris Motik. Faithful approaches to rule learning. In Proc. of the 19th Int. Conf. on Principles Knowledge Representation and Reasoning (KR 2022), 2022b.
Komal K. Teru, Etienne G. Denis, and William L. Hamilton. Inductive relation prediction by sub- graph reasoning. In Proc. of the 37th Int. Conf. on Machine Learning (ICML 2020), pp. 9448- 9457, 2020.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proc. of the 3rd Workshop on Continuous Vector Space Models and their Composi- fionality (CVSC 2015), pp. 57-66, 2015.
Meihong Wang. Linling Qiu, and Xiaoli Wang. A survey on knowledge graph embeddings for link prediction. Symmetry, 13(3):485, 2021.
Zhuo Wang, Wei Zhang, Ning Liu, and Jianyong Wang. Learning interpretable rules for scalable data representation and classification. IEEE Transactions on Pattern Analysis and Machine Intel- ligence, 200), 2022.
Zihao Wang, Yangqiu Song, Ginny Y. Wong, and Simon See. Logical message passing networks with one-hop inference on atomic formulas. In Proc. of the 11th Int. Conf. on Learning Repre- sentations (ICLR 2023), 2023.
Yikun Xian, Zuohui Fu, S. Muthukrishnan, Gerard de Melo, and Yongfeng Zhang. Reinforcement knowledge graph reasoning for explainable recommendation. In Proc. of the 42nd Int. ACM SIGIR Conf. on Research and Development Information Retrieval (SIGIR 2019). pp. 285-294, 2019.
Wenhan Xiong, Thien Hoang, and William Yang Wang. DeepPath: A reinforcement learning method for knowledge graph reasoning. In Proc. of the 2017 Conf. on Empirical Methods in Natural Language Processing (EMNLP 2017), pp. 564-573, 2017.
Fan Yang, Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowl- edge base reasoning. In Proc. of the 31st Conf. on Neural Information Processing Systems (NeurIPS 2017), pp. 2319,2322,,1 2017.
Shichang Zhang, Jiani Zhang, Xiang Song, Soji Adeshina, Da Zheng, Christos Faloutsos, and Yizhou Sun. PaGE-Link: Path-based graph neural network explanation for heterogeneous link prediction. In Proc. of the ACM Web Conf. 2023 (WWW 2023), pp. 3784-3793, 2023.
11

---

Published as a conference paper at ICLR 2024
A PROOFS
Lemma 1. For a dataset 'D with constants C1,' ,C. vector va computed by M for S 8 S and 1 I h 8 is equal to Eeg (MM()))--:)))) -,, where R RLL is the set of all rules of the form (
with 1 S E T. (resp. f = 0) and head atom (a y) (resp. R (2, (P)(r) is a non-negative function of r that depends only on the parameters of M, and Qr, is vector of dimension e such that, its t-th element is (resp. 0) if the body of r is T and = (resp. t + s), and otherwise it is the number of different mappings that ground the body ofr in DD and map x to Cs and y to Ct.
Proof. Let D be an arbitrary dataset with constants CL,-.- C.. The distributive and associative properties of the product and the sum allow us to rewrite Equation (3) as
N L III (...kk)) (vs) Ma M (EIIa
(v-)T=
Σ
MR.
(9)
(41 ALJE(L, 264134
It is straightforward to see that each sequence (ki,,.. kr.) of elements in {1. 28 + 1 cor- responds to a rule of the form (2). namely, the unique rule with head atom R2 (2, y) (R) (x. x) all elements are 25 + 1) and such that (k,,-.. .kz) E S.F. Furthermore. all sequences in S are over {1, ,22 + 1}² and of length L. Hence, we can rewrite Equation ( as
Mcg )) (10)
(v!)T= = Σ
Σ
(EI[a'..b a" ((...k)) (v.)* My, Mag (1=1
PERA (AI JeDES
Let D' be the extension of 'D with all inverse and identity facts over the extended signature, as described in Section 2 A simple inductive argument shows that the vector (v,)T MA, MM,
Mc, describes the number of paths of length L in D' from C. to each constant. In particular, the t-th element of the vector is the number of paths of length L from C, to C. in D'. Furthermore, for each kL) E S. there is a one-to-one correspondence between each substitution that grounds the body of mapping to 6s and y to Gs, and each path of length T, from to a in D' through kn, k2.... .k. therefore, for each (ki,,... kr) E S the vector (v,)T= Ms. Mk,
rule r in PATH with Z and for each (ki,,
Mr, always qr.D.s- Finally, for r = [z x) < T, there is a unique sequence in S,,, namely, that where all elements are 26 + 1. For this sequence, the vector
Ma.- .............................. ..... -M has s-th component equal to 1 and all other components equal to 0, so it also equal to a. Hence, Equation (TO) we can factor out (v,)T-M
MM,- ....... ..M
as it is equal for each (k..... kL) E S for a given r, and replace by its value D.D.s. Then the right side of the equation becomes EnERyy (r((r) -r.D. a. as we wanted to prove, with
(m(()= Σ ΣI a (1,j,ky)
(11)
(kay YESE ==1
Theorem 1. Program 'R M. is sound for M (a .a...... a² 33) whenever Y 2 B. Furthermore, there is a DRUM model M' = (a",,... ... a., 3²) such that R DRUM is unsound M' for any 7 < B². M ay
Proof. For the first claim, we consider an arbitrary fact Rn,,,, E TRiaU (D). and we show that Rs (ca, Ct) E (D). Since Ba(c,, E T TRuea (D), R contains a rule of the form (2) M.
where 0 < l < L, and there is substitution such that rule's body by this substitution in D. Now, by hypothesis, 7 B. Moreover, the value a, from Equation 44) is strictly greater than y because E DRUM. Furthermore, ppM(r) 2 ar, seen from comparing Equation [II and Equation (4) Finally, we have v² 2 (r) from Lemma and the fact that qr (t) due to the existence of a. Combining all these inequalities yields v (t) B,
Ca. yo Cz. and the grounding of the
indicating RA ct) E (D),), as we intended to show.
We prove the second claim with an example. Let D {Ri(CI, R2(e,, c2)} be dataset, and M = (a), ....... a , B) be a DRUM model which = L = 1, and 3 = 0.5. All non- zero elements of a ... a a² (1, (1,11,2 0.5. According to Equation (3) the
12

---

Published as a conference paper at ICLR 2024
model does not predict the fact Ry(c1, 01) since (1) & B. However, for any y 3, the pro- gram RM, contains the rule R2 x. y) +- R1 y), and Tagan (D) contains the fact R2(c1,01).
Therefore, RDRM not sound for M. M,7
Theorem 2. There exists a DRUM model such that no Datalog program is faithful for it.
Proof. Let M (a) ................................ .a,, 3) be the DRUM model in which N = and 0.8. All non-zero elements of a'...... a are a² (1,, = 0.5 and a² (1,2, = 1. We show that there exists no Datalog program that is faithful for M using proof by contradiction.
Assume that R is faithful Datalog program for M, i.e., for any dataset D, TM(D) = (D) Consider two datasets D1 = (C1 (1),
and D2 Dj U (Ri 02), R2), R2,, where constant e2 does not appear in R. According to Equation 3 the model M predicts no fact if it is applied to Dj (i.e., (D)) = 0) while predicts the fact R2(41,
is ap- On the other hand, since R is complete for M. we have R2(C1.02) E Tw (D2). Let a be a mapping from constants to constants with (c2) = ci and (c;) = c for any + 2. Observe that (D2) D1. Since a (R2(c1,
plied to D2 (i.e., (D2)
(R2(c1,
(a), we have R2(c1, 22) E (D2))) It a well-known property of Datalog that for each Datalog pro- gram R' and each substitution f that maps each constant in R' to itself, it holds that ((TR (D)) S TR (n(D)), Since constant C2 does not occur in R and o is an identity mapping for other con- stants, we have (TR (D2)) C TR (D22)
TR (Di), ). indicating R2(ci, 02) (D())). Notice that TR (Dt) & (D)), so R is not sound for M, which contradicts our assumption that R is faithful for M. Thus, no faithful Datalog program exists for M.
Theorem 3. Program RMP, M,y extracted by Algorithm 1 on inpur M = (al,... "...,,a,,, 3) is faithful terminates in (L. (26) ( (N + w(2))=1)) steps,
to M for = B. Furthermore, Algorithm 1 where w is the maximum value of w()) a rule of the form with 8 S L.
Proof. Let M, be the output of the algorithm for M with y B. Let L and N be the depth and rank of M, respectively.
(Auxiliary Claim) We first prove an auxiliary claim: for each rule r E R with head atom RG (z. y), the value yor is defined after line 9 by Algorithm [ during the iteration of in- dex h (line 3). Besides, frr where 1 < k < 8 for each k, and each wh, is of the form Rx, (zi-1, 2;) or Ra, (zi, 21-)). Note that frr is only created and modified within the loop of h (line 3). Moreover, lines 4-10 ensure that pr, = EiR MESEE E
(M))). Let thx, A A like be the body atoms of r,
where S is the set of all sequences (K1 .. .k)) with 1 < K < +1. Therefore, when performing the iteration in lines 6-7 with index [K..... K... rule r is produced in line 8, and so yr is defined. To complete the proof, by Equation (T] we need to show that S = S. This, however, follows straightforwardly from the definitions of S and Stc
(Soundness) We prove the soundness of RM, for M by considering an arbitrary dataset D and showing that TRyy, a (D) C (D).). Let [c, c.) be an arbitrary fact in T TRur M. (D). Then, there exists a multipath rule r in RM such that either (case 1) the body of r is T, or (case 2) the body of r is of the form Φi A A.. A dp for P 2 1, with each o, being a multipath conjunction with a distinct core (note that Algorithm| I never outputs rules containing two multipath conjunctions with the same core (line 15-16)), and there exists a substitution a from the variables in r to constants of D that grounds x c, and y c such that, for each op of the form 7 if its core is VP WE, A ... A Vir, and its cardinality is Cp, then vie a E 'D for each
S lp. and for each
two 1 S j S Cp. there exists 1 S S Ep such that 2/0 + 2
Case 1. If the body of r is T, then r = m|ol- The auxiliary claim shows that (Pri) = (r)).. By Lemma 1 (t) 2 (P)()) since (.M('') and qr,,,,, are non-negative for each r' E R. R Thus, va (t) 2 Prisi Meanwhile, Priii is precisely the value compared with y in line 18, in the iteration starting from line 14 with index [C1, Cpyy]= = [0.-...0) .0. Since r E M, Praji > 3. (D).
Therefore, Rs (C., cx) E TRNE M.
13

---

Published as a conference paper at ICLR 2024
Case 2. For each 1 S p P. Up is of the form 7 we can use a to produce Cp substitu- tions 01...... Cc, defined as oy(2)) = 2,0 for each 0 S i < and 1 S j S Cp. If Cp > 1, then all substitutions are necessarily pairwise different (i.e., they differ in the assignment of at least one variable) because line 13 ensures that Cp can only be greater than 1 if T contains at least two body atoms, and so 8 > 1. Thus, for each pair of j and j' satisfying 1 S j < S Cp. such that z 7 of a. Therefore, Drp. 2 Cp. for rpp as the rule R2 v) + LP. By Lemma (t) = EFERYT (M(()) 9r.D,s(t). By construction, each rule rp is in R Both pm(()) and D,, are non-negative, so v (1) 2 Ep (M(())) Cp if or v. (t) 2 Ep PM((p) Cp + PM 2) - T) otherwise. By the auxiliary claim, this is equal to Ep Pr, Cp or Ep Pr, -G + Prjay respectively, which is precisely the value compared with y in line 17 (if Co + c), or line 18 (if c. = Ct), in the iteration of the loop starting from line 14 with in- dex [C
there exists I I
up and otherwise C₁ = O. This list is well-defined since no two p and p' with < - P correspond to the same elements of f2, as we already ob- served that each multipath conjunction in the body of has a different core. Hence, r E M, and we have Ep Pr, Op + Pra > B. Thus, we have va (t) B, indicating Ra(c,, ci) TRy. (D).
C [1]- where C/ = Cp if
(Completeness) To prove completeness, we again consider an arbitrary dataset DD and show that TD( S TRme (D). Let Ra(c,, a) be an arbitrary fact in (D).). We show that there a multipath rule in TRNe T which derives the same fact from D. By Lemma [ (t) = EveRyy (Pr())- (t),,s(t. Let R be the set of all rules E Let r be an arbitrary such rule. By definition, if the body of r is empty, then (r) = 1. Oth- erwise, (t) is the number of different substitutions that ground the body of r in D mapping x to C2 and y C.. Furthermore, in the latter case, the body of is an element of S and therefore line 13 ensures that some value w, is computed for it. We now consider two possible cases and show that completeness holds in both. In particular, in each case we construct rule r' with head Ra (z. y) and then show that, on the one hand, the body of r' can be grounded in DD by substitution that maps x to Cg and y to ct. On the other hand, we show r' M. and so Rī (Ca, E TRYS M.
R,, such that qt,D,, > 0.
(D). (D).
Case 1. There exists r E R. such that (r.P,,(1) > Wr. This will not happen if the body of r empty (since wi, is not defined for it) has a single atom, since in that case Qr.D.s S 1. but line 13 ensures W,- = 1. Thus, the body of has at least two atoms. Consider a multipath rule r' where the head is Rx,2,)) y) if C2 # o and otherwise is RA (x, and its body is a multipath conjunction of cardinality wi and its core is the body of r, with x = y if the head does not mention y- Since (t) > Wr, there exist at least W,- substitutions grounding the body of r in D mapping x to C, and y to q. Since in multipath conjunction of the form 77. each element V shares no variables with the others other than x and y, we can take the union of those w, substitutions to obtain a new substitution a, and it is clear that this substitution grounds the body of r' in 'D mapping x to es and y to q- Now, note that there exists unique element of Ω equal to the core of r' (i.e., the body of r). Consider the list [Ci.... -R where C. wr for the unique such that 12(1) is the body of r, and C, 0 otherwise. Consider the iteration in line 14 during the execution of the algorithm within the loop of h, with this list as an index. The value compared with y in line 17 is (Pim + W, pp, 2 w, -pr (by the auxiliary claim and the fact that P. is non-negative). Since has at least two body atoms, by line 13 we have W/ 1p, > B, and so r E RP M.8-
Case 2. There exists no r E R such that qr.D,,(1) (1) > wy. Consider the multipath rule r' where the head is Rx, y) if c, A G. and otherwise it is Rx (), and its body has multipath conjunction for each element E R with non-empty body, with core equal to the body of (with x = y y is not mentioned in the head) and cardinality qt) This is well defined by our assumption that (t) > O. Therefore, for each r with non-empty body, there cxist at least (t) different substitutions grounding the body of r in D mapping x c, and y to G.- Since in a multipath conjunction of the form 77 each element Th shares no variables with the others other than x and y. and different multipath conjunctions in the body of r' also share no variables other than x and y. we can take the union of all those substitutions to obtain a new substitution a,, and this substitution clearly grounds the body of r' in D mapping x to e, and y to ez. Let [C1, C2,-.. Ojoi 1] be the list which has C, 0 if R2 (x. y) +- 2(1) is not in R and C; (1) if (2i)) is equal to the
14

---

Published as a conference paper at ICLR 2024
body of r. This list well-defined since each rule in R has different body and hence there exists unique element in S equal to its body. This list will be considered in the loop of line 14 during the exccution of the algorithm, within the loop of h. because qr, S w,. The value compared with y in line 17-18 for this iteration will be E 9r,D,s(t) Pr- By the auxiliary claim, this expression is equal to ΣrER (PM(T)) (t),,,(t). By Lemma ] and the fact that for any r E Rh.,. $ R, have (t, 0 (with our definition of R.), we obtain that (t) Erer 9r,D,s (1) Pr- Hence, since (t) > 3 and our assumption that (c,,, E TD),), we have that line 17-18 ensures E MP M.9. we intended to show.
(Time Complexity) In line 2, each conjunction has size at most L, so the cost of this step is [[ L). We next analyze the time complexity of the main loop of the algorithm, which runs 8 times. The loop in line 4-10 considers (25 + 1) different lists. For each list, line 5 requires O(L) steps, and so does each iteration line 6-7. The operation in line 9-10 requires N. L steps, so the total cost of this part is ((28 + 1) (L + L + 1 N L))) (((2)) N L).
The loop in line 1 11-13 is performed [9t] times, each of which requires a constant number of opera- tions. The overall time cost is ((9)).
For the loop line 14-18, let w = maxigigia wi- The number of possible combinations of cardinalities [C1,.... Clai] with 0 < C; S w; is bounded by (w+ + 1)181, which is a bound on the number of loop iterations. In each iteration, line 15-16 writes a rule with at most [2) multipath conjunctions, where each conjunction has at most L w atoms and (:) L S w² L inequalities. Line 17-18 requires number of operations linear in Q. Finally, the filtration in line 17-18 can be finished in constant time. The overall time cost of this loop is
O ((w
(w (w++ 1)
(12]-
T. [T.w+
(2) 1.) +111))
which can be simplified to
o [1| |0] 1).
Therefore, the overall time complexity of Algorithm
o (122) L + d (20) N L + [ + w |||+2 -(0|-L) L))
(12)
Considering that the number of conjunctions in 9 for each length 0 S <6 L is (28) we have
(25) +1 26 ((25)* L -
|2
(26)
+ - +1=0 ((26)4)
28 -
t=O
t=1
Hence, Expression
12
becomes
O (6(28) N (20) 222)))4)) =0
= 0 (N+ ( (2-66)))
((2))111))
Theorem 4. Program RD extracted by Algorithm 2 for a DRUM model M (al..... aa, and a dataset D satisfies TRO, (D) = TDDD). Furthermore, Algorithm terminates with time complexity (((8)= (N L 26 22))
Proof. To show T (D) C (D),), we simply point out that the rules in RM are in MM by construction, and so TRR, (D) S TRNe (D). Meanwhile, by Theorem R MM is sound for M,
so TUN M (D) 5 TT))
To show (D) S TRR (D), we consider an arbitrary fact R2 (cs; (t) E (D) and then show that the rule produced during the iteration of the algorithm for this fact suffices to derive this fact in D. Let be the rule added to R2, when RA (ca, 6x) is used as index in the iteration of loop 11. For each multipath conjunction in its body with core ei, the existence of count (+) different paths from c, a in D and the fact that count( is greater equal to the cardinality of this multipath conjunction ensure that the body of matches the dataset mapping r to c, and y to e,. Hence the rule fires on D. and so R2 (cs,, (4) TRR (D).
15

---

Published as a conference paper at ICLR 2024
Algorithm 3: SMDRUM Rule Extraction.
:=
0:
== list of all conjunctions in the body of the form variables other than and y: foreach h E {1.-.. 5) do
with 0 I & v L, and with no overlapping
foreach (1,
N
foreach [K1, ... .z) :1: h; x 25 do
[ki -: kg] == remove all 20 +1;
foreach (1..... . do
8
kg then by Rx, (zj-1, else thy == Ray (3)
if 2 then = (z, v) N thy; else r = (T( T;
10
if Pr. is undefined then (r.. : 0:
Pr. max(pr.1, 11 j=1 a [i, ky));
11
12
foreach [er
Pe.] 11se < ... < en I Pc; E do
13
if) 1-1 Pre,
then
if T $ (Pes.... Pen) then R RU Rr (z, + Pa.:
15
else R. URU(RA (R,( A Pes (v (y
16
return R:
(Time Complexity) In the worst case, the number of possible paths in Pall reaches OieL, L, (28)2 and the size of (D) reaches O(c² 26). Consider the iteration in lines 11-19 of Algorithm each loop of specific path [ca, ki,-... ..... c.] costs at most ((L) steps. Besides, to compute all the
values (r) for each possible rule of the form ( requires at most O(N- ((N-L-(26)) steps. Therefore,
the worst case time complexity of Algorithm 2 is
O (20) 2² 25 + N.NN... L. (28)4) (((2)) (N L
For an SMDRUM model M there exists a program RSM of inequality-reee multipath rules computable in exponential time in M's size such that (D) TTRM (D) for any dataset 'D.
Proposition 1.
To prove Proposition we first present the algorithm extracting the relevant program RSM from M and then prove the faithfulness of the program and its complexity. The Proposition is then a trivial corollary from that result.
Algorithm 3 extracts a faithful program from an SMDRUM model. For each possible rule r of the form 2 with head atom R2 (z. y) (line 3), the algorithm first computes score fr. similar to the score f0r from Algorithm | but computed separately for each sub-model (line 5-11) and using max instead of sum to aggregate different products of elements of a², Then, it checks all possible combinations of rules (which are not necessarily different) with head Ra y), and combines their bodies into a single rule (line 15).
The following result states that this algorithm extracts faithful programs from SMDRUM models. Theorem 6. The Datalog progrum R extracted by Algorithm 3 for SMDRUM model M (al ................................ a², (3) is faithful to M for 7 = -3. Furthermore, Algorithm terminates in O (21) steps.
Proof. (Soundness) We consider an arbitrary fact Rn(ce, E TRAM (D) and show that Ma.
Ba (Ca,,)) c.) (D).). Since (t) E Tayy, (D), there exists a rule r RSM and either M,
(1) is Rx(x,x) + T (2) it of the form Ry RM y) A bi or analogously with x y. with each by different element of Ω, and substitution a grounding the body of this rule in D mapping c and y to c. Furthermore. the fact that E R implies that Σ Pr.. B, for r R2 (a. y) b. Simultaneously. we can rewrite the equation from Definition 2 as
N
a ((.().)))))
max
(13)
(k dz (L.... 264134
(v.) 8... MM, =1
5=1
16

---

Published as a conference paper at ICLR 2024
defining the result of max as 0 of no sequence (k1,.... k2) satisfies the relevant conditions. For any (k1. .... k2) E (1, ... 2 1}", the definition of the matrices Mr, implies that Mr, ... if either bn- the body of r' the unique rule such that (K1," ... kr) E S in DD mapping x to C2 and to Ca or otherwise MR, ..... (s, Hence,
(s. MR,
k 26 + L, or there exists substitution which grounds
L Σ [aa((n))))) T=1
(V)) Z
where (kf,...,kk) ,kt) is the element S (with 7; Ra y) < by bç * T, and rs RA (I, x) +- T otherwise) that was used by the algorithm to produce the final value of Pre But then, Prefn = I15=1a' a (ei, kj), and since the value compared with 3 by the algorithm is E Proper we have (v)) > which implies (c (4) E (D).
(Completeness) To show completeness, consider arbitrary RA Ra(es, ai) E (D). Let e1 <..< en be the indices I S N for which the sequence below is defined.
fi
aTa(t.)ik))))
(k4
AL)
arg max (Ki (L. 26+13" Ma, @- -M, (s,1)=1 1=1
(14)
Let be, be the (unique) conjunction such that (Kf),.... ... k()) E S/ap1" with re, = RA t be. be; * T, and otherwise Te; = Consider the rule r Rn v) + Ni= bb: if none of the Te, have a body equal T. and otherwise construction, I7 (ei, kj) = Prec so Equation (3) and the choice of (kf).- .... kf. to- gether ensure that (t) = Ei= Pre,,es and since (v)) > B, then r E RM To see that Rs (c., c.) E (D). note simply that since one of the requirements in the equation above M,, -... 2 MRy (s, 1; thus, for any be, # T, there exists substitution grounding b. in D mapping to C, and to Since, by definition of Ω different be, share no variables other than and y, we can take the union of these substitutions and obtain substitution that grounds the body of and maps x to C2 and to Cr.
(I
Ni=1 be.ty + x}. By
(Time complexity) In Algorithm 3 there are total of head atoms (line 2). In each rank (1, (1.".,, N (line 4), the number of predicate lists of length L. (line 5) is:
[[k ... :k)
k S 25 + 1) = (25 + 1)4
(15)
In each iteration of [k1, [k kr). the computation of fr,,, costs at most O(L) steps. Then in the combination of bodies b,, the overall number of iteration steps is O((26 + N). The insertion of rules in R has a time cost of O(N). Therefore, the overall computational cost is:
8 (N (26 1 + (26 + 1D O(N)) ((22))-N+1).
(16)
Theorem 5. For an MMDRUM model M of depth L, the program containing each rule r of the form 2 with & < L or R(x, x) + T such that aMr B is faithful for M.
Proof. Let RMM. be the program stated the theorem. To show soundness we consider a fact (c,, 0z) E TRNM (D) and show that it is in TM((), We know that there exists a Data- log rule in RM,, in the form of 2 or Rx(x,)) + T and, if the body of this rule is not empty, a substitution a that maps x to cx, to et, and grounds the body of the rule D. Let
[ a (i. (1...K3))
arg max max
MYJJS ISSEN
17

---

Published as a conference paper at ICLR 2024
Algorithm 4: MMDRUM Rule Extraction.
:= 0:
foreach h E (1....,) and E (1,-. N) do
p:= D: P = [(1, D)
foreach j [1.... L do
P = P ==:=0
foreach (p) and E (1..... .0] do
a a' >> then P p' u {(s a (t, k])):
foreach (s, [K1,... .., kz]) P with >>7 do
"i,-.,, k(] == remove all 28 +1;
10
foreach fl.......... do kg S then th == RAg 25); else f = oog- (35))
11
i 2 1 then Ra (2, NE=1 R5 else
Ri (zz, x)
13
R = (U]
14
return R;
Since this rule is in RM we have 11 a kf, > B. Next, analogously the case for MMDRUM, we can rewrite the equation that defines (v-)T in MMDRUM as
(t))
max ISIN
max (Kg.r (L. 13+11 M2, 60.0 (s,1)=1
I aa (i.).
(17)
Now, note that if the body of is not the existence of implies that My @... Mr, (s, 1. If the body T, then c = C. and Ky = 25 + 1, so Mę; @ .... @0 My, (s, 1) holds by definition of the MMDRUM model. This means that our sequence (K k2) is considered the max computations, and so we obtain (t) 2 a ji. Thus, (v)) > 8 and hence RA (c., E (D).
a
To show completeness, we consider a fact (e (+) (D) Let
4, (ki, kk) arg max ISiSN M4 MYJ.s M., @.. Mi, (s.()=1
Clearly, least one such i and sequence must exist for Ru Rn(es, 0r) to be in (D). By Equation we have that (t)) = 11 a² (i,j, ky)) Next, consider the (unique) rule r with (ki,.... .kk) S.F By our choice of and (ki, ................................ kL). we have a.M.r I a (i, kyy. Since Ra ce) (D), we have (v)) > 8 and so aMrr > B. Thus, E R M, as we wanted to show. It remains to see that we can ground the body of r in D mapping x to c, and y to ct, but this follows from the definition of (k,,..., ,k), which has the condition M&, X & MR2 (s,t) =.
17
B EFFICIENT RULE EXTRACTION FOR MMDRUM
We present an optimised procedure to compute the faithful program RMM, for an MMDRUM model M. The procedure is laid out Algorithm 4 relies on two techniques to optimise rule ex- traction. On the one hand, instead of first enumerating all rules and then calculating their scores, we interweave the construction the rules with the computation of the scores, This allows us to take advantage of structure sharing. On the other hand, since the elements of a" are all between and 1, computing the value rules by multiplying different elements will result a monotonically decreasing manner. Therefore, at each step, threshold, thus pruning the search space.
compare the value computed far with the
The following proposition ensures that the output of the algorithm corresponds the target program.
18

---

Published as a conference paper at ICLR 2024
Proposition 2. The Datalog program R extracted by Algorithm for MMDRUM model M
RMM. (a' , 3 is equal to R&M Furthermore, Algorithm terminates in O(N 81++1) steps.
Notice that, although the time complexity given in Proposition contains an exponential term 8 the woaldworld and L would be relatively small. Besides, the pruning in each step by threshold ? further improves the computational efficiency. The algorithm usually terminates in a short time in practice, which is also confirmed by the empirical results in Section
Proof. We show the double inclusion. First, let RMM be the program from Theorem If r M, with head predicate Rh then there exists (.g::..,k))) E S and i E {1,.... N such that a.M.r > 3. Note that any prefix of factors in the expression will also be greater than 3 since elements a ji, are in [0, 1]. But then, the execution of the algorithm ensures that for the iteration with h and the path (s, "i, ,K 12-16 generate the rule r from (K ,,,,), we have that r is in the output of the algorithm.
1 () and all its subpaths are considered, and since lines
Conversely, suppose that is in the output of the algorithm, with head predicate Ra- Then we have that there exist i and (ki,-.. ,LL) E S such that in the iteration of line with index i, the path (s, 11, kL. t) is considered and IT a (2,j,ky) > B. But then, (A maxi SIEN 11 a (i, > B, and so the rule is in M.
To prove the complexity, note that the outer loop iterates 5- N times. For each of these iterations, the number of rules that can be built is (25 + 1). The remaining operations be performed in linear time. Hence the complexity is O68 N (26 + 1)* which can be simplified as O - -24+1). L
C EXPERIMENT DETAILS
This section provides additional details regarding the experimental set-up, including the used bench- marks and the configurations used for training and testing.
C.I DATASETS
We used the benchmark datasets for inductive KG completion from Teru et al. (2020). Each dataset consists of train, validation and test sets, where the test set contains the same predicates but distinct constants w.r.t the train and validation sets. To use them for the KG completion task, we further split each train set and test set into an "incomplete" dataset and ratio on a random basis. To evaluate the models prediction on negative examples, we randomly sampled the same number of negative facts positive examples in the test set, and combined both positive and negative facts in the test process.
of positive examples with a
Table 4 presents the statistics of each dataset used our experiments. Apart from the number of facts and predicates, we also computed the in-degree and out-degree of nodes in each dataset by viewing as graph, where nodes are constants and edges are predicates. Compared with FB15k- 237 and WNISRR, NELL-995 datasets generally have smaller median in-degree and out-degree, indicating that they have relatively simpler graph structure and fewer paths within given length constraint (e.g., L= 3).
Family Kok & Domingos 2007) is a dataset of blood relationship between individuals. It contains predicates such as sister, brother, mother. etc. We reused the split of train, validation and test sets in Sadeghian et al. (2019).
C.2 SETTINGS
Model Implementation. The original implementation of DRUM by Sadeghian et al. (2019) relied on Python 2. and Tensorflow 1.135 which were relatively outdated and did not support most up- to-date operators (e.g., the max-product of matrices). Therefore, re-implemented the models
https//wwwppytoooooo.//om//////a
19

---

Published as a conference paper at ICLR 2024
Table 4: Statistics of datasets.
In- In-Degree
Out-Degree
ITrain Facts
"Validation Facts
i'esst Faets
iPredicates
median
max
median
max
VI
4,245
489
2,198
180
2
388
3
69
V2
9,739
1,166
4,623
200
2
588
3
102
FB15K-237
V3
17,986
2,194
8,271
215
3
1,061
4
139
27.203
3,352
13,138
219
1,289
5
VI
4,687
414
933
14
293
1
188
V2
8,219
922
5,062
2
608
NELL-995
V3
16,393
1,851
8,857
524
875
V4
7,546
876
7,804
76
254
2
545
VI
5,410
630
1,806
17
V2
15,262
1,838
4,452
10
WNI8RR
V3
25,901
3,097
6,932
2
142
2
87
V4
7,940
934
13,763
2
56
2
24
Family
23,483
2,038
20,450
12
5
5
50
with Python 3.8 and Py PoTchh 2.0. For NEURAL-LP, we reused the source codes and settings provided in Tena Cucala et (2022b).
Model Training. We followed Sadeghian et al. (019 for all the default settings in training, such the log-likelihood loss function, Adam optimizer and the use of 10 maximum training epochs. An early stop strategy was adopted for each model based on the prediction loss of the validation set. All experiments were conducted on Linux workstation with a Xeon E5-2670 CPU. Our data and source codes are available at
Rule Extraction. We conducted rule extraction for each model and benchmark. In addition to using threshold 7 = 3 in rule extraction, we further assessed their efficiency by comparing the time cost of rule extraction with different
For MMDRUM, we used the rule extraction threshold = 0.1 and 0.01, respectively. For SMDRUM to avoid redundant body atoms brought by predicates with low scores such as Figure (a), to make rule extraction feasible, and to balance the contribution of each sub-model, we required the score contributed by each sub-model to exceed lower-bound (i.e., 7 in Figure (b)). We evaluated >' 0.1 and 0.01 for SMDRUM in the experiments. Further, combined duplicate chains of predicates learned by different sub-models each SMDRUM rule by adding up their confidence scores and retaining the body atoms only once shown in Figure [ (b)).
R
0.9
0.
R
R
0.9
R
0.9
=.5
R
R
R
X
D
X
0.8
1.0
R
0.0
R
0.9
R
0.9
A((z)))R(G (Z..)) Rg (x)2g) (x
(a) a rule body with redundancy.
(b) filtering and simplifying the rule body of SMDRUM.
Figure I: motivating example of SMDRUM rule extraction. Different colors represent ranks. The yellow dotted path in (a) is redundant as it contributes nothing to the overall confidence score of the rule, thus should be removed. (b) shows the filtering and simplifying process of combining body atoms by the same chain of predicates (the green and blue paths) learned from different ranks.
For rule extraction in DRUM, as discussed in Section 4 the relatively high complexity of Algorithm makes it impractical to extract all multipath rules for a DRUM model. Instead, we used the approach from Section 5.1 extracting rules that explain the predictions on the test dataset.
httpss//pytorrchoorgggeet http:////ee..ataatreerrtrroe-aea
20

---

Published as a conference paper at ICLR 2024
D ADDITIONAL EVALUATION RESULTS
We provide more evaluation results below, including the training and rule extraction time of each model on the datasets, along with analyses the extracted rules.
D.1 TRAINING TIME
Table 5 presents the training time of MMDRUM, SMDRUM and DRUM on the FB15k-237, NELL- 995, and WN1SRR datasets. The three models used similar time for training, which generally increased in accordance with the number of constants and predicates in the dataset. All the models finished a few hours for each dataset. Besides, the training time increased with the model depth L, as the number of learnable parameters (i.e., the elements of a a²) proportionally increased with
Table 5: Training Time (minutes) of each model with N= =
MMDRUM
SMDRUM
DRUM
L
2
L = 3
L = 2
L
3
L = 2
L 3
V1
18.7
28.1
17.9
26.0
16.7
25.4
V2
69.8
119.5
64.6
99.3
62.0
93.4
FB15k-237
V3
189.5
322.4
204.9
332.9
213.2
347.9
V4
389.1
598.7
425.1
653.6
434.9
668.5
VI
1.8
3.0
2.1
3.3
1.8
2.8
V2
24.9
40.3
28.1
27.2
43.6
NELL-995
V3
153.2
250.5
177.9
273.4
176.8
277.4
V4
21.5
35.0
24.7
40.1
23.6
37.1
VI
1.5
2.4
1.7
2.7
1.7
3.0
V2
11.5
14.9
14.1
21.3
13.3
21.1
WNISRR
V3
40.2
61.9
40.1
76.3
46.2
68.4
V4
7.3
12.4
9.3
14.3
9.5
D.2 RULE EXTRACTION TIME
Table 6 shows the rule extraction time of each model for each dataset. Generally, all of them fin- ished extraction in few minutes for all the datasets, thereby demonstrating their practical viability. Besides, a lower threshold y (or 7²) leads to an increase of rule extraction time, which is closely related the increasing number of rules being extracted under 7 (or 7').
Not surprisingly, MMDRUM finished extracting the faithful Datalog program within the shortest time, which accordance its acceptable time complexity O(N 82+1). SMDRUM was run for a similar amount of time in best-effort mode. We in fact attempted to implement our faithful Datalog rule extraction for SMDRUM, Algorithm 3 However, with
and = the extraction process had not finished in 3 hours for dataset FB 15k-237 V1, which suggested that extracting a faithful program for SMDRUM may not be feasible practice.
For DRUM, the time cost of rule extraction (using the dataset-dependent Algorithm was very influenced by the actual structure of the dataset. Observe that even though the numbers of predicted close, the NELL-995-VV dataset required much longer time than the others (about 170 seconds for 7 = 0.01 and 120 seconds for 7 0.1). This was because the dataset contained some central constants with fairly high in-degree out-degree, thus leading large amount of paths with length < L (at most 1, 544, 589 with L = 3 in NELL-995-V1).
facts in different datasets
D.3 COMPARISON OF RULE EXTRACTION UNDER DIFFBRENT RANKS
We extended analysis to assess the impact of rank N and depth L of the model to the derived rules. To facilitate the investigation, we contrasted the extracted rules from MMDRUM across varying configurations of N and I..
21

---

Published as a conference paper at ICLR 2024
Table 6: Rule Extraction Time (seconds) of DRUM, SMDRUM, and MMDRUM.
MMDRUM
SMDRUM
DRUM
0.1
0.01
7' ===01
0.1
Y = 0.01
0.1
0.01
VI
5.048
5.867
7.212
8.629
0.022
0.024
V2
6.824
8,084
6.827
8.593
0.101
0.132
FB15k-237
V3
8.477
9,836
8.021
10.205
0.673
1.002
V4
8,902
9.844
8.626
10.356
3,924
4.923
VI
0.005
0.011
0.005
0.069
118.971
169.851
V2
0.637
0.832
0.621
1.049
0.164
1,212
NELL--995
V3
2.532
2.748
2.724
3.737
11.788
16,803
V4
0.435
0.586
0.412
0.749
12.851
20.683
VI 0.002
0.004
0.002
0.043
0.029
0.035
V2
0.002
0.005
0.002
0.048
0.046
0.049
WN18RR
V3 0.002
0.004
0.003
0.017
0.029
0.140
V4
0.002
0.003
0.002
0.008
0,200
0,233
Table presents the highest ten rules along with their associated confidence scores for N 1,2 and L 2, 3, respectively. For both = and L = 3, the algorithm extracted rules with length explicitly less than T., such hushand(a; y) wife(y, æ)), which was in alignment with the analy- ses in Dection[] Regarding the rank N, the results suggested that a MMDRUM model with a greater rank derive the same rules with higher confidence scores, due to the model acquiring the same rule independently in different sub-models.
Table 7: Rules extracted from Family (Kok & Domingos, 2007) dataset by MMDRUM.
Top 10 mles
Score
Top 10 niles
Score
brothen(z. 3) brother(2r, =) A brother(z. v)
0.999
sister(ar,)) y) <- aistenfar, 2) sister(z..))
0.995
sister(z..)) 1) sister(ar, sister(a,
0.999
brother(ar
brother( brother(
0.994
niece(z. 1) <- -ister((a;; =) niece(=. v)
0.998
uncle(z. p) <- brother(2t 5x) mother Rx) mother(22 (22.
0.985
uncle(.r.)) +- brothen(rr, uncle(#. (x.p)
0.998
daughter(2.
sister((z, daughter(2..)
0.984
son(a.g) <- brother(z,, x) son( 2. y)
0.994
()) <- siister(ar, 21) sister zy) sisten(22..))
0.983
Z. daughter(ss.)) sister((r, sistter(r
daughter(s, v)
0.991
nephew(z.y) -nepphewss,
brother(s,
0.978
sunt(a, v) sistcr(x,, aunt (x.
0.991
husband( v² + wile(fr.
0.972
sister(z,g) daughter(ir,
mother(s, a.
0.991
auni(z. sister((s, sister(si, s2) nephew s2)
0.932
neplaew(r. 2) smnt(re v) 4- sistsiistt,,, a) mother(a..)
(2, ni
0.900
nephew(z. 3) - sssoooo., brother(s,,))
0.922
0.980
niccola, v) sister(ee,
sister( unclo(y)
0.901
sister(z. 5) sister(aa; sister( brothen(
0.998
cister(a, 5) <- sistee((a, 2) sister(z, s/
0.994
brotbbrrtz, () brotber(a,
brotber(a,,) 3) boother(,, brother(s.
0.988
niece(z..) 3) sister[ar; a) nicce(s,
0.989
nephew (2. 1) <- brother(ar, nephew(2, hushund(y;.r)
0.968
son(a. 5) brother(z,, nephew(n, b (2, 2] nephew(a..)
son(2,
0.987
wife(ar,
0.963
0.976
daughter (2
sister(at, A dauughter(a..))
0.943
2 auntar, v) sister(z, auni(
0.974
hushand(s..)) w-ifeey,,.r
0.922
daughter(s..) +- sisster(<,, =) daughter(s, (2, v)
0.970
aunt(z. y) <- (sste((x.22) sister(st. niscefy. (o. m2)
0.865
uncle(ar, v) brothen(s,, son(y.
0.917
niece(s,)) sisten(ar,
sister unclely ma)
0.847
Inther(r, 3] <- husbond(zz. =) daughter(y..)
0.822
son(z. v) brother(z, x) (aaber(p..))
0.747
wife(z, y) husband(y.2)
0.795
uncle(x. 8) brother(z, x1) brother(s1, nephow(y,
0.706
D.4 ADDITIONAL. EXAMPLES EXTRACTED RULES
We also evaluated the rule extraction performance of each model other benchmark datasets from Teru et al. (2020). Table 8 shows example rules extracted by Algorithm from the FB 15k- 8 NELL-995 and WNISRE datasets with N 3 and L 2. Most rules correct and understandable. Many of them have lengths strictly smaller than L, which in accordance with the model design of MMDRUM.
Additionally, we evaluate the rules extracted by Algorithm B on the FB15k-237, NELL-995 and WN18RR datasets with N 3 and I. 2. Similarly to the results in Section 6 the Family
Forr conciseness, represent the predicates in FB15k-237 with their last parts separated by slash. For example, write "location" for "/people/perso//placcs ppoplpppopee lived/location"
22

---

Published as a conference paper at ICLR 2024
Table 8: Rules Extracted by MMDRUM from Teru al. (020).
Datasets
Example Rules
awardNominee(z; v) <- awardWinner(rr, y)
location(z; v) placeOrBirth(r,
FB15k-237
flmprrouuedBB((r, y) + awardWinner(zz,
tvProgram (r, y) + programCreator(y,
langaugeSpokennn(z, y) officiaallanguaeeee..tt A serviceLocation(y. 2)
subpartOf(2, y) + @gcmtBedonggefoppppaiiiiiino.-.-
worksFor(z, v) + orgaaizaioonHiicdeeeroo....22
NELL-995
CemmPlays.Agains<CCamm.... y) tammllyyssggiiiissTTamm//.
head(uuarteredIn(s..))) v) organzzaiinnaaaQQuuurrrrriiiiiir
personBomInCity(:: y) + personBomlnl (ww.://ooomnn.ooiiiiooa......
dervaationallykclaeeoootmzz y) dedrivatioalllyyeeaaaoooo/.// verbGroup x, y) < verbGroup(y.
WN18RR
hasPart( y) + hasPart(2,, 2) A hasPart(2, v) alsoSee(z, v) <- alsoSee(y,z))
SubsetDDmmannTopicCCOt,,,,
derivationallyyeelaeeddfoim y)
dataset Kok Domingos (007). while some rules in the form of 2 can both extracted by
SMDRUM and MMDRUM, Algorithm Bl can also extract rules that not in the form (2) shown Table / Many rules tend to have lengths smaller than and focus on the same sequence of
predicates among multiple sub-models of SMDRUM.
Table 9: Rules Extracted by SMDRUM from Teru al. 2020
Datasets
Example Rules
film(z, y) + fimseetDDssined((z y) A cditedBy(g,.2)
FB15k-237
film y) writtenBy(y,. 2) A editedBy(y, x)
nominatedFor(z:
film(z, y) editedBy(y.
worksFor(2; v) +- personlLeadSrrggaiizaatnnn...
orgamizationtiirrdPrrsssss 2)
NELL-995
worksFor y) + oopMeebberOrOrrganzzttoiitt orgaauzaaiinntiiceeerssggg.
subpartOf(r, y) ciryCapiialO/CCommttyy... proxyFor(z,
subsetDoomaiTTopiiCO((.... + derivationallyeelaaedooomee y) similarTo(y, alsoSce(x, y) < alsoSee(g, 2) verbGroup(zz,)
WN18RR
iimilarTo(s: y) + similar x)) A verbGroup(z;, y)
23


Reviews:
[{"review_id": "KJ0Vg8STib", "reviewer": "Reviewer_dHjy", "summary": "In the abstract, the authors describe the problem that they are solving as  \"methods for extracting interpretable rules from ML\nmodels trained to solve a wide range of tasks over knowledge graphs (KGs), such as KG completion, node classification, question answering and recommendation.\" and talk about how \"Many such approaches, however, lack formal guarantees establishing the precise\nrelationship between the model and the extracted rules, and this lack of assurance becomes especially problematic when the extracted rules are applied in safety critical contexts or to ensure compliance with legal requirements\"\n\nWhile the work described in the paper seems reasonable, this does not quite seem to match the claim in the abstract. As best as I can tell,\nthe techniques in the paper do not deal with classification / question answering / recommendations. Further, it is not obvious (either from the description of the technique or the experimental results) that they provide assurances around the \"precise relationship between the model and the extracted rules\" (while there might be soundness, completeness does not seem to result).", "questions": "It was not obvious how this applies for general ML problems, particularly those around question answering. It was not clear how the algorithm might perform for classification/recommendation systems.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The results seem interesting for knowledge graph completion problems.", "weaknesses": "It was not obvious how this applies for general ML problems, particularly those around question answering. It was not clear how the algorithm might perform for classification/recommendation systems.", "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": "", "extra_scores": {}}, {"review_id": "gjiyO39gFH", "reviewer": "Reviewer_Crqq", "summary": "The paper adapts a study that was previously conducted for extracting rules from the Neural-LP model (which is a neural model for reasoning about knowledge graphs) to DRUM, an alternative architecture for the same task. This adaptation is not entirely trivial, as the authors motivate well, so that this can be considered an original contribution. They also show that, in analogy to the previous work, the extracted rules are not necessarily faithful, and can be unsound or incomplete. An expensive alternative is also proposed as a remedy.", "questions": "I'm not really familiar with this task, but this seems to be quite a heavy machinery for extracting family relations. In Inductive Logic Programming these are only toy examples. Are there no better tasks for showcasing what you can do?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This paper seems to be well formalized and contain sufficiently interesting improvements over the state-of-the-art. The evaluation is on a standard benchmark task. The introduction is quite accessible, but after that I was quickly lost.", "weaknesses": "I am not sufficiently familiar with this area in order to judge whether the contribution of this work is sufficiently deep for publication, whether the shown results are actually correct, or whether the performed evaluation on this set of benchmark sets is a standard procedure in this area.\nWhat I can judge, however, is that the paper is a) very well written in the sense that a stringent formal presentation is chosen, but also b) not written for an audience outside this immediate community, and the authors also do not make any attempt to make their work more accessible. If you do not know any of the prior works, in particular DRUM, you are lost. I could, e.g., easily follow the terse formal description of Datalog, because I am familiar with that. With the similarly formal presentation of DRUM I was completely lost. I now know what parts this system has, but not what they are used for. I know that path-counting is part of the method, but I don't know what paths are counted, and why this has any significance. \nI think the paper is a very nice illustration of the fact that shorter explanations are not necessarily more interpretable. \n\nMinor stuff:\nThe formalization of the paper seems to be very stringent, the references are not (lower case abbreviations such as gnn, all conference names abbreviated (I don't know all of them), weird references to things like ICML volume 227 or ISWC volume 13489, backslashes in URLs, etc.", "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": "", "extra_scores": {}}, {"review_id": "DGozCnByel", "reviewer": "Reviewer_BVyG", "summary": "This paper discusses the growing interest in extracting understandable rules from machine learning models that work with knowledge graphs. These models are used for various tasks like knowledge graph completion, node classification, question answering, and recommendation. However, many of these rule extraction methods lack formal guarantees, which can be a problem when applying these rules in critical or legally required situations. The paper focuses on the DRUM model, a variant of the NEURAL-LP model, which has shown good practical performance. The paper explores whether the rules derived from DRUM are sound and complete, meaning they provide reliable results. The authors propose a new algorithm to ensure both soundness and completeness in the extracted rules. This algorithm, while effective, may be less efficient in practice. They also suggest adding constraints to DRUM models to facilitate rule extraction, even if it reduces their expressive power. The paper points out that DRUM and NEURAL-LP models have technical differences, making it necessary to examine the guarantees separately for DRUM.", "questions": "-", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Good paper interesting, with good ideas and good experiments.", "weaknesses": "it seems that a lot of citations are missing, please add them and discuss them\n\nhttps://arxiv.org/pdf/2301.09559.pdf\nLearning Interpretable Rules for Scalable Data Representation and Classification\nFINRule: Feature Interactive Neural Rule Learning\nhttps://arxiv.org/pdf/2309.09638.pdf", "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": "", "extra_scores": {}}, {"review_id": "fZvPZOINzN", "reviewer": "Reviewer_piEQ", "summary": "In this paper, the authors proposed a solution on how to extract rules from the DRUM model that are faithful, i.e., both complete and sound. The authors provided extensive analysis on the correctness of the proposed algorithm and demonstrate the benefits of their algorithm with some experiments.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "+ The rule learning problem, in particular, the problem of how to obtain a high-quality set of rules, that the authors are exploring is a critical problem. \n+ The authors present a detailed theoretical analysis of how to derive faithful rules from DRUM model, which is quite impressive", "weaknesses": "+ I have some concerns about the motivation of the proposed method. It is not clear to me why faithfulness is an important metric for rule learning. What kind of benefits can we obtain for the rule learning problem if the rules can respect faithfulness, e.g., say better generalizability? The authors may need more effort to justify this. One motivating example might be helpful for readers to understand this.\n+ I also feel that the proposed solution is too specific. It is only applicable to the DRUM model rather than the general rule learning model, which may limit the applicability of the proposed method in general settings. \n+ The overall presentation may need to be improved. I feel that the authors have a lot of technical content to present. However, putting all of them together without appropriate illustrations makes it hard for readers to digest. One suggestion would be using some running examples to intuitively explain the meaning of the notations and equations rather than just leaving them in the paper. Even the prior work such as DRUM paper or Neural ILP paper, there are a lot of visualizations that help users understand the intuitions of the proposed method.\n+ I feel that the experimental evaluations are also concerning. The authors only focus on evaluating the performance of the proposed methods. However, no appropriate evaluations (except some simple case studies) are conducted for the faithfulness part, e.g., how many rules from the vanilla DRUM model violate the faithfulness criterion and what is the bad effect of including those rules?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)