Year: 2021

Abstract:
Graph Neural Networks (GNNs) are often used to learn transformations of graph data. While effective in practice, GNNs make predictions via numeric manipulations in an embedding space, so their output cannot be easily explained symbolically. We propose a new family of GNN-based transformations of graph data that can be trained effectively, but where all predictions can be explained symbolically as logical inferences in Datalog—a well-known rule-based formalism. We show how to encode an input knowledge graph into a graph with numeric feature vectors, process this graph using a GNN, and decode the result into an output knowledge graph. We use a new class of monotonic GNNs (MGNNs) to ensure that this process is equivalent to a round of application of a set of Datalog rules. We also show that, given an arbitrary MGNN, we can extract automatically a set of rules that completely characterises the transformation. We evaluate our approach by applying it to classification tasks in knowledge graph completion.

heading: 1 INTRODUCTION
text: Knowledge graphs (KGs) (Hogan et al., 2021) are graph-structured knowledge bases describing an application domain as a collection of entities and their relationships. They can be captured in formats such as the Resource Description Framework (RDF), and are used in applications such as Web search, recommendation, fraud detection, and data integration. Many of these applications involve realising a graph transformation. For example, in a recommender system we can represent user-item interactions as a graph (Aggarwal, 2016) and extend it with external KGs to improve accuracy, diversity, and interpretability of recommendations (Zhang et al., 2016; Wang et al., 2018; 2019a); the system then realises a transformation of the input graph into another graph containing recommended user-item interactions. Moreover, a KG completion system (Rossi et al., 2021; Bordes et al., 2013; Teru et al., 2020) transforms an input graph into another graph containing relationships missing in the input. Usually, the transformation is not given explicitly, but is learned from examples.
Graph Neural Networks (GNNs) (Scarselli et al., 2009; Liu & Zhou, 2020) are one of the most popular ML models for graph data. They are usually applied to KGs in three stages (Hamilton et al., 2017). First, the input KG is encoded into an embedding space as another graph whose vertices are labelled with numeric feature vectors. Second, this graph is processed by a GNN with several layers; for each layer, the GNN updates the feature vectors based on the learned model parameters and the vectors of the previous layer. Finally, the vectors of the output layer are decoded to the output KG.
While such approaches are effective in practice, GNNs compute predictions through numeric calculations in the embedding space, so the transformation can be difficult to understand. For example, it would be useful to know that a system recommended novel The Idiot because the user liked Crime and Punishment and both novels were written by Dostoevsky. There is growing interest in explaining GNN predictions, and many methods have focused on identifying relevant subgraphs in the embedding space (Ying et al., 2019; Luo et al., 2020; Lin et al., 2021). Such methods, however, do not explain predictions symbolically—that is, by showing how each prediction can be derived from the input KG using rules of inference in a knowledge representation formalism. Datalog (Abiteboul et al., 1995; Ceri et al., 1989) is a prominent formalism based on ‘if–then’ rules. When applied to facts, the rules derive new facts. For example, we can represent knowledge about literature using facts Author(Dostoevsky,Crime and Punishment) and Author(Dostoevsky,The Idiot), and past interactions using fact Likes(Crime and Punishment).
Then, the application of rule Author(x, y1) ∧ Author(x, y2) ∧ Likes(y1)→ Recommend(y2) to these facts derives the target fact Recommend(The Idiot). State-of-the-art Datalog engines (Motik et al., 2014) provide powerful methods for generating human-readable proofs explaining why a target fact follows from the input rules and the data. Such proofs can help fostering trust in system predictions, ensuring compliance with norms, and enabling verification of fairness standards.
The main contribution of this paper is a new family of GNN-based transformations of KGs that can be trained from examples as usual, but whose predictions can be explained symbolically using Datalog rules. Our transformation consists of the three steps mentioned earlier: encoding an input KG, applying a GNN, and decoding the result back into an output KG. These steps, however, were carefully crafted to ensure that the transformation can always be described symbolically. We use a novel class of monotonic GNNs (MGNNs), which we designed to ensure an important property: when values in input feature vectors increase, no value of an output feature vector decreases. To capture this intuition formally, we show that our transformation is monotonic under homomorphisms—a well-known property that captures key aspects of Datalog rule application.
In contrast to the related approaches (Teru et al., 2020; Hamaguchi et al., 2017; Schlichtkrull et al., 2018; Wang et al., 2019b), all predictions of our transformation can be explained using Datalog rules. Specifically, for an arbitrary MGNN, there exists an equivalent set of rules so that, on any KG, the rules and the MGNN-based transformation produce the same facts. This opens the door to new ways of using MGNNs: when developing Datalog rules manually is difficult, we can train an MGNN model and use it to provide further predictions, but such predictions can be explained using rules. For example, we could train an MGNN on a graph containing examples of credit applications and then use it to support decision-making on new applications by applying the model to a different graph. Unlike existing approaches, there exists a set of rules implicitly captured by the model that fully explain each credit recommendation; although computing all such rules can be computationally expensive, we can typically extract a representative subset of them in practice. Thus, we integrate ML and symbolic AI in a single framework, allowing applications to use the best of both worlds.
We demonstrate the effectiveness of our approach by applying it to classification tasks in KG completion. Using well-known benchmarks, we compare our system’s performance with that of DRUM (Sadeghian et al., 2019) and AnyBURL (Meilicke et al., 2019), both state-of-the-art KG completion systems able to also generate rules. We show that, in addition to providing an exact correspondence between the model and the extracted rules, our technique also offers competitive performance.
Proofs are given in the appendix, and the source code is available as supplementary material.

heading: 2 AN MGNN-BASED TRANSFORMATION OF KNOWLEDGE GRAPHS
text: We now describe our GNN-based transformation of knowledge graphs. In this paper, we see a KG as a dataset, which is a finite set of facts of the form A(a) or R(a1, a2), where A is a unary predicate, R is a binary predicate, and a, a1, a2 are constants. Constants represent entities from an application domain, unary predicates typically represent entity types, and binary predicates represent relationships between entities. For example, the statements that a user likes Crime and Punishment and it is a novel written by Fyodor Dostoevsky are represented as facts Likes(Crime and Punishment) and Author(Dostoevsky,Crime and Punishment). KGs in formats such as RDF can be transformed into such a dataset in the obvious way. For D a dataset, cn(D) is the set of constants occurring in D.
Our transformation is realised by an operator TM on datasets, which is parameterised by a GNNM. A dataset D is first encoded into a graph GD in the embedding space, where vertices are labelled with numeric feature vectors; then,GD is processed byM; finally the result is decoded to the output dataset TM(D). In Section 3, we show that, by restrictingM to be a GNN of a special form, called monotonic, we can ensure that TM is equivalent to a round of Datalog rule application; this, in turn, allows us to automatically extract an equivalent set of rules from TM. The embedding space consists of coloured graphs, which extend the standard notion of undirected graphs in two ways. First, each vertex is labelled by a numeric feature vector of some fixed dimension; this is necessary in order to allow the coloured graph to be processed by M. Second, each edge in the graph is assigned a colour, which allows us to distinguish different types of connections in the graph.
Figure 1 illustrates the encoding of the datasetD in the introduction. First, we introduce vertices vDs, vCP, and vI in GD to represent constants Dostoevsky, The Idiot, and Crime and Punishment. The
feature vector of each vertex va represents all unary and binary facts of the form X(a) and Y (a, a); for example, vCP has 1 as the first element of its vector representing Likes(Crime and Punishment). Second, we introduce vertices vDs,CP, vCP,Ds, vDs,I, and vI,Ds, whose vectors represent all binary facts over the corresponding constants; for example, vDs,CP has 1 as the third vector element, representing Author(Dostoevsky, Crime and Punishment). Since The Idiot and Crime and Punishment do not occur together in a fact in D, the encoding of D contains neither vCP,I nor vI,CP. Here, we rely on an order of predicates to determine the corresponding vector positions; this order is arbitrary, but fixed in advance. Third, we connect all vertices of GD referring to common constants with coloured edges, which allows us to distinguish different types of joins between facts. For example, vDs and vDs,CP refer to Dostoevsky, so we connect them with an edge of colour c1, thus indicating that Dostoevsky occurs first in the constant pair of vDs,CP. Analogously, we connect vDs,CP and vCP with an edge of colour c2. The constant pair of vCP,Ds is the inverse of vDs,CP ’s, so we connect them with an edge of colour c3. Finally, we use edges of colour c4 to connect vertices of GD representing constants occurring together in a fact, such as vCP and vDs.
Formally, we fix a set of four colours Col = {c1, c2, c3, c4}. We assume that datasets and derived facts will use finitely many predicates, and fix a list A1, . . . , A , R +1, . . . , Rδ of available unary and binary predicates. We consider vectors and matrices over the reals R and its nonnegative subset R+. For v a vector, (v)i is the i-th element of v. We apply scalar functions to vectors and matrices element-wise; for example, for v1, . . . ,vn vectors of equal dimension, max{v1, . . . ,vn} is the vector whose i-th element is max{(v1)i, . . . , (vn)i}. Finally, a function σ : R→ R is monotonically increasing if x < y implies σ(x) ≤ σ(y), and function σ is Boolean if it ranges over {0, 1}. The following definition describes the structure of our embedding space.
Definition 1. A (Col, δ)-graph is a tuple 〈V, {Ec}c∈Col, λ〉, where V is a finite set of vertices; for each c ∈ Col, Ec is a set of c-coloured undirected edges (possibly including self-loops) over V ; and labelling λ assigns to each v ∈ V a vector λ(v) of dimension δ. If λ is implicitly understood, λ(v) is written as v. For c ∈ Col and v ∈ V , Nc(v) is the set of vertices connected to v by an edge in Ec.
We are now ready to define our encoding of an arbitrary dataset D into a (Col, δ)-graph GD.
Definition 2. The encoding of a dataset D is the (Col, δ)-graph GD that contains a vertex va for each constant a ∈ cn(D), and vertices va,b and vb,a for all (not necessarily distinct) constants a and b that occur together in a binary fact in D. For each vertex va,b, GD contains an edge of colour c1 connecting va,b and va, an edge of colour c2 connecting va,b and vb, an edge of colour c3 connecting va,b and vb,a, and an edge of colour c4 connecting va and vb. For each va, labelling (va)i is 1 if Ai(a) ∈ D and 0 otherwise. For each va,b, labelling (va,b)i is 1 if Ri(a, b) ∈ D and 0 otherwise.
We process GD by a GNN. As we explain in more detail Section 3, if we are to ensure that our transformation ‘mimics’ Datalog rule application, we cannot use an arbitrary GNN. Instead, we introduce Monotonic Graph Neural Networks (MGNNs), which restrict GNNs in a way that allows us to attain our objective. Definition 3 also specifies how to apply an MGNN to a coloured graph.
Definition 3. A (Col, δ)-monotonic graph neural network (MGNN)M with L ≥ 1 layers is a tuple 〈{A`}1≤`≤L, {B`c}c∈Col,1≤`≤L, {b`}1≤`≤L, σ, cls〉. For each ` ∈ {1, . . . , L} and each c ∈ Col, A` and B`c are matrices over R+ of dimension m` × n`, and b` is a vector over R of dimension n` such that n1 = mL = δ, and m`−1 = n` for each ` ∈ {2, . . . , L}. Moreover, σ : R→ R+ is a monotonically increasing activation function, and cls : R+ → {0, 1} is a monotonically increasing classification function. The dimension ofM is max{n1, . . . , nL}.
ApplyingM to a (Col, δ)-graph G = 〈V, {Ec}c∈Col, λ〉 induces the sequence λ0, . . . , λL of vertex labellings where λ0 = λ, and for each ` ∈ {1, . . . , L} and v ∈ V , the value of λ`(v) is given by
v` = σ ( A`v`−1 + ∑ c∈Col B`cmax{w`−1 | w ∈ Nc(v)}+ b` ) . (1)
The resultM(G) of applyingM to G is the (Col, δ)-graph with the same vertices and edges as G, but where each vertex v ∈ V is labelled by cls(λL(v)).
Intuitively, an MGNN consists of L layers, where each layer ` ∈ {1, . . . , L} is defined by a matrix A`, a matrix B`c for each colour c, and a bias vector b
`; these constitute the learnable parameters of the model. In addition, an MGNN also uses functions σ and cls which are fixed and given explicitly. An MGNN transforms an arbitrary (Col, δ)-graph G into another (Col, δ)-graphM(G) as follows. Each vertex v in G and each ` ∈ {0, . . . , L} is associated with a labelling v`. Labelling v0 is the labelling v of v in G, and, for each layer `, vertex v is labelled by a feature vector v` computed as specified in equation (1). The feature vector of v in the resulting graph is computed by applying the classification function cls to the final labelling vL. Thus, MGNNs instantiate the GNN framework by (i) taking the maximum of the features of a vertex’ neighbours (instead of the more commonly used sum or average), (ii) using nonnegative weights in matrices A` and B`c (but the elements of bias vectors b` can be negative), and (iii) requiring the activation and classification functions to be monotonically increasing. We discuss the reasons for these restrictions in Section 3.
The resultM(GD) of applying an MGNN to the encoding GD of a dataset D can be decoded into the output dataset of the transformation by essentially inverting the encoder (see Figure 1 for an example). Thus, for each MGNNM, we obtain a distinct operator TM that is specified as follows. Definition 4. For M a (Col, δ)-MGNN and D a dataset, TM(D) is the dataset containing the fact Ai(a) for each i ∈ {1, . . . , } and each vertex va such that (va)i = 1 inM(GD), and the fact Ri(a, b) for each i ∈ { + 1, . . . , δ} and each vertex va,b such that (va,b)i = 1 inM(GD).
Note that the dimensions of the matrices in M do not predetermine the kind of dataset to which TM can be applied; in fact, M can be trained on some dataset and then applied to a different dataset over the same predicates. This makes our transformation ideally suited for inductive settings in applications such as KG completion and recommendation (Teru et al., 2020; Hamaguchi et al., 2017; van den Berg et al., 2017), where the datasets to which a trained model is applied may use constants (i.e., entities) not mentioned in the datasets on which the model was trained.

heading: 3 EXTRACTING AN EQUIVALENT SET OF DATALOG RULES
text: We now show that, for each MGNNM, we can automatically generate a set of Datalog rules PM such that TM and PM derive the same facts on any dataset D. To this end, we first recapitulate the basic definitions of Datalog and identify a property that characterises Datalog reasoning.
A (Datalog) atom is of the form A(t1) or R(t1, t2), where A and R are unary and binary predicates, respectively, and each ti is a constant or variable. A (Datalog) rule is an implication of the form (2), where H is the atom called the rule’s head, all Bi are atoms that together form the rule’s body, and each variable in H occurs in some Bi.
H ← B1 ∧ · · · ∧Bm (2) A (Datalog) program is a finite set of rules. A substitution ν is a mapping of finitely many variables to constants; for α an atom, αν is the result of replacing in α each variable x on which ν is defined with ν(x). Each rule r of form (2) defines the immediate consequence operator Tr on datasets: for D a dataset, Tr(D) contains fact Hν for each substitution ν satisfying {B1ν, . . . , Bmν} ⊆ D. For P a program, operator TP on datasets is defined by TP(D) = ⋃ r∈P Tr(D).
Our objective is to show that, for each MGNNM, operator TM ‘behaves analogously’ to Datalog rule application. Definition 5 specifies formally what this means in our setting. Definition 5. A homomorphism from a dataset D to a dataset D′ is a mapping h of constants to constants that is defined at least on cn(D) and that satisfies h(D) ⊆ D′, where h(D) is the dataset obtained by replacing each constant a in D with h(a) and removing all duplicate facts. An operator T from datasets to datasets is monotonic under homomorphisms if, for all datasets D and D′, each homomorphism from D to D′ is also a homomorphism from T (D) to T (D′).
For any constant-free program P , operator TP is monotonic under homomorphisms. For example, let D = {A(a), R(a, b)} and P = {S(x, y)← A(x) ∧R(x, y)}, so TP(D) = {S(a, b)}. First, operator TP is monotonic: adding facts to D cannot invalidate any consequence of TP , since the body of r still matches and the rule derives S(a, b). Second, operator TP is resilient to replacement of constants. For example, let D′ = {A(c), R(c, c)} be obtained from D by replacing a and b with c. Rule r ‘cannot tell’ that the constants have been replaced, deriving TP(D′) = {S(c, c)}, which is obtained from TP(D) by the same replacement. Monotonicity under homomorphisms combines both properties. We next show that rules can be extracted from any operator satisfying this property. Definition 6. An operator T on datasets captures a rule or program α if Tα(D) ⊆ T (D) for each dataset D.
Proposition 7. Let T be an operator on datasets, let r be a constant-free rule of form (2), let µ be a substitution that maps each variable of r to a distinct constant, and let Dr = {B1µ, . . . , Bmµ}. If T is monotonic under homomorphisms and Hµ ∈ T (Dr), then T captures r.
Intuitively, if some operator T captures a rule r, then Tr provides us with a lower bound for the consequences of T on an arbitrary dataset—on any dataset, T derives at least as many facts as r (but T can derive more facts). Moreover, if T is monotonic under homomorphisms, Proposition 7 provides us with an effective way of checking whether T captures r: replace each variable in r with a distinct constant, collect the resulting body atoms in a datasetDr, apply T toDr, and finally check whether the result contains the replaced head atom of r. Clearly, T captures a constant-free program P if T captures each rule r ∈ P , so we can just apply this check to each r ∈ P to verify whether T captures P . This provides us with the necessary machinery for rule extraction. We next show that operator TM is monotonic under homomorphisms. This shows that TM indeed ‘behaves like’ Datalog reasoning, and it will allow us to use Proposition 7 for rule extraction. Theorem 8. For each (Col, δ)-MGNNM, mapping TM is monotonic under homomorphisms.
Theorem 8 is a consequence of the restrictions on MGNNs mentioned after Definition 3. For monotonicity, note that adding facts to a datasetD has the effect of possibly adding new vertices and edges and then flipping from 0 to 1 some vector positions labelling the vertices of GD; moreover, the elements of A` and B`c are nonnegative so the arguments of σ in equation (1) can only increase; finally, functions σ and cls are monotonically increasing so the elements of the feature vectors inM(GD) can only flip from 0 to 1, which is equivalent to deriving more facts in TM(D). For the resilience of constant merging, replacing, say, constant b with constant a in D is tantamount to merging vertices vb into va in GD; this will cause vertex va to have fewer neighbours, but since we aggregate neighbours’ feature vectors by taking the maximum, this cannot change the result of equation (1). Note that, if we aggregated neighbours using a sum (as is common in the literature), then elements of the feature vectors inM(GD) could decrease due to merging, which would invalidate Theorem 8. Theorem 8 tells us that we can check whether TM captures a rule r effectively using Proposition 7. This is a key step of our rule extraction algorithm. In particular, we next show that it is sufficient to consider only rules of a certain structure, and that the number of such rules is bounded and determined by the dimension of M, the number of layers of M, and the number of predicates δ. Thus, to obtain a program PM deriving the same consequences as TM, we can, in principle, enumerate all such rules, apply Proposition 7 to each rule, and keep only the rules that pass this check. To realise such procedure in practice, several optimisations are possible. For example, the relevant space of rules can be significantly reduced by exploiting the fact that rules can be subsumed (i.e., logically implied) by other rules; for instance, if we have determined that a rule B(x)← A(x) has been captured, then rules of the form B(x) ← A(x) ∧ C, with C any conjunction, do not need to be considered since such rules are logically implied by the previous one and are hence redundant.
Definition 9 describes the syntactic structure of the rules that can fully characterise TM. To this end, we use the well-known notion of a primal graph of a conjunctionC of atoms, which is the undirected graph (possibly with self-loops) whose vertices are the variables of C, and where an edge connects each pair of (not necessarily distinct) variables x and y such that R(x, y) is in C for some R. Note that the primal graph of an empty conjunction is also empty. A primal graph is a (possibly empty) tree if it is connected and acyclic (and, in particular, without self-loops). Definition 9. Let c and d be nonnegative integers. A constant-free conjunction C is (c, d)-treelike for a variable x if the primal graph of C is a tree that is either empty or can be rooted at x
(i.e., x occurs in C) and, for each vertex v in the tree, the distance i of v from x is at most d and moreover v has at most c(d − i) children. A (c, d)-tree-like rule is a rule of form A(x)← Cx or R(x, y)← Cx ∧Bx,y ∧ Cy , where Cx and Cy are (c, d)-tree-like conjunctions for x and y, respectively, with no variables in common, and Bx,y is a nonempty constant-free conjunction of binary atoms of the form S(x, y) or S(y, x).1
ForM a (Col, δ)-MGNN with L layers and dimension k (see Definition 3), let PM be the program that contains, up to variable renaming, each (3k, L)-tree-like rule that is captured by TM.
The primal graph of rule A(x) ∧R(x, y) ∧ S(x, z) is a tree with root x and children y and z; thus, it is (2,1)-tree like, but not (1,1)-tree-like (since x is at distance 0 from itself it can have at most one child). Second, the primal graph of A(x) ∧R(x, y) ∧ S(x, z) ∧ T (y, z) is a triangle with nodes x, y, and z, so it is not (c, d)-tree-like for any c and d.
Theorem 10. For each (Col, δ)-MGNNM and each dataset D, we have TM(D) = TPM(D).
Theorem 10 also describes the expressiveness (i.e., the kind of possible predictions) of TM. For example, no MGNN can capture rules such as r = R(x, z)← R(x, y) ∧R(y, z). To see this, let D = {R(a, b), R(b, c)}. For an arbitrary MGNN M, Theorem 10 ensures that all predictions of TM involving binary facts are made by rules of the form R(x, y)← Cx ∧Bx,y ∧ Cy; however, no such rule can derive R(a, c) on D, so we necessarily have R(a, c) 6∈ TM(D) as well.

heading: 4 EVALUATION
text: We have evaluated our approach on KG completion tasks, which involve extending a KG seen as a datasetD to its complete versionD′ by adding missing facts. When seen as a classification problem, the aim is to learn a Boolean function f(·, ·) that takes a dataset D and a fact α over a fixed set of unary and binary predicates such that f(D,α) returns true if and only if α ∈ D′. We consider the more general inductive variant of this task, where the testing dataset may contain constants not occurring in the training or validation datasets (but all predicates in the testing dataset are known before training). Inductive KG completion is more general and challenging than the transductive variant (Bordes et al., 2013), where all constants in the testing data also occur in the training data.
Baselines. We compared our approach with DRUM (Sadeghian et al., 2019) and AnyBURL (Meilicke et al., 2019), two state-of-the-art approaches for knowledge graph completion.
DRUM learns an end-to-end differentiable model that, given a datasetD and a fact α, returns a score representing the likelihood of α belonging to the completion of D; predictions are then computed by applying a threshold to the score. The system also produces a set of chain Datalog rules of the form H(x1, xn)← B1(x1, x2) ∧B2(x2, x3) ∧ · · · ∧Bn−1(xn−1, xn), each associated with a confidence score. These extracted rules approximate the model’s predictions, but, unlike in our work, the exact relationship between the predictions and the result of applying the rules is unspecified.
AnyBURL uses path sampling techniques to generate chain rules of a slightly more general form (variables can be replaced by constants). Each rule is associated with a score. Given dataset D and fact α, AnyBURL makes its prediction by applying a threshold to a score computed by first applying the rules on D once and then combining the probabilities associated to all rules deriving α.
Benchmarks and performance metrics. We used the 12 KG completion benchmarks by Teru et al. (2020), which are based on FB15K-237 (Bordes et al., 2013), NELL-995 (Xiong et al., 2017), and WN18RR (Dettmers et al., 2018). Each benchmark provides disjoint datasets T , V , and S for training, validation, and testing, respectively; statistics are shown in Table 1.
We evaluated performance of our systems as follows. Each benchmark provides a method for randomly splitting its testing dataset S into disjoint subsets SI and SC ; intuitively, SI is the incomplete dataset to be completed with dataset SC . Thus, we took (SI , α) for each fact α ∈ SC as a positive example for testing. Moreover, we randomly sampled |SC | facts β1, . . . , βn over the predicates of SI satisfying βi 6∈ SC , and we took each (SI , βi) as a negative example for testing. Sampling was necessary because the set of possible facts not contained in SC is very large; moreover, random
1Note that Cx cannot be empty in a rule of form A(x)← Cx since x is required to occur in the body.
sampling does not favour a specific way of constructing negative examples during training. The number of positive and negative examples was the same to ensure that metrics are balanced. For each system, we classified the positive and negative testing examples and computed the precision, recall, accuracy, and F1 score in the usual way, as well as the area under the precision-recall curve (AUC) by considering different classification thresholds between 0.01 and 0.99.
Training. Our system is trained as a denoising autoencoder (Vincent et al., 2010). The training dataset T is first split with a 9:1 ratio into an incomplete dataset TI and a set TC of facts that should hold in the completion of TI . To train our model, we used (TI , α) for each fact α ∈ TC as a positive example, and we obtained negative examples (TI , β) by sampling β analogously to how this was done for testing. We consider MGNNs with 2 layers and ReLU as activation function. We used cross-entropy loss with a logistic sigmoid on λL(v) as the output probability, and we trained using Adam optimisation with the standard learning rate (0.01) and weight decay (5× 10−4), and a maximum of 50, 000 epochs. We implemented the procedure in Pytorch Geometric v1.5.0, and ran it on a laptop running macOS 10.15.7 with 8 GB of RAM and an Intel Core i5 2.30 GHz CPU.
We trained the baseline systems using their (publicly available) code with their default configurations. For each system and benchmark, we computed the accuracy on the validation dataset for a range of thresholds, and we used in our tests the threshold that maximises accuracy.
Evaluation results. Table 2 shows the results of our evaluation. As one can see, our system was overall very competitive, and it outperformed both baselines on most benchmarks based on NELL995. Table 2 also shows the training times for DRUM and our system, which are are comparable; no times can be shown for AnyBURL because this system does not train a model.
Similarly to AnyBURL, our system attained extremely high precision scores; however, recall values were significantly lower, especially for the benchmarks based on FB15K. This can be explained by the fact that, after randomly splitting the testing dataset S into subsets SI and SC , numerous facts of the form R(a, b) in SC use pairs of constants a and b that do not occur together in any fact in SI . By Theorem 10 from Section 3, our transformation can never produce such facts in the output. To confirm our hypothesis that this is the main reason for low recall scores, we additionally split the testing dataset S so that a factR(a, b) is placed into SC only if SI contains a fact of the form S(a, b) or S(b, a) for some predicate S. The results for our system obtained in this way are shown in Table 3. As one can see, precision scores remain high, whereas recall values increase significantly; thus, accuracy, F1 score, and AUC values improve accordingly. Our system significantly outperformed all
Benchmark Total Tree-like Captured Captured AnyBURL AnyBURL by TM on SI
FB 15
K -2 37 v1 2812 252 72 1371 v2 2823 404 102 1048 v3 4805 490 118 1749 v4 3574 584 134 1046
N E
L L
-9 95
v1 891 51 49 707 v2 1123 181 112 650 v3 1104 277 181 603 v4 841 187 108 606
W N
18 R R v1 397 15 11 30 v2 522 21 14 35 v3 424 21 21 48 v4 511 16 12 23
Table 5: Comparison of rule extraction with AnyBURL
baselines in this setting; however, this way of splitting the data gives our system an unfair advantage in a comparison, and hence we did not present the results for the baselines in Table 3.
Rule Extraction. For each benchmark, we used the algorithm in Appendix D to extract the set P of all non-redundant rules in program PM (c.f. Definition 9) with at most two body atoms; we give the size of each P in Table 4. Since P is captured by TM, operator TP approximates TM; in particular, TP(D)⊆ TM(D) for any datasetD. To measure the quality of the approximation, we applied TP to the test dataset of each benchmark. We observed that precision remained unchanged, while recall decreased only slightly (1.6% in average). This shows that the generated “short” rules account for almost all predictions on the benchmarks. Full results are shown in Table 6 of Appendix D.
By analysing the rules in P , we noted that our transformation learned many rules describing sound inferences such as symmetry (e.g., sibling(x, y)← sibling(y, x) on FB15K-237), inverse relations (e.g., capitalOfArea(x, y)← areaHasCapital(y, x) on FB15K-237), and relationship subsumption (e.g., athletePlayedForTeam(x, y)← athleteLedSportsTeam(x, y) on NELL-995). In addition, we generated rules using AnyBURL on each benchmark and checked how many of those are captured by our transformation;2 Table 5 summarises our results. The first column provides the total number of rules generated by AnyBURL on each benchmark. The second column indicates how many of those rules were tree-like as per Definition 9. The third column shows how many rules from the second column are captured by our transformation per Definition 6. Finally, the fourth column shows the number of AnyBURL rules r that are captured by TM on the specific dataset—that is, such that Tr(SI) ⊆ TM(SI). As one can see, a significant proportion of tree-like rules generated by AnyBURL are captured by TM. Additionally, a significant proportion of (not necessarily tree-shaped) rules generated by AnyBURL are captured by TM on the specific dataset, which partially explains why many of the predictions by AnyBURL are also obtained by TM.
2We could not do this for DRUM since the version of the system available online cannot produce the rules.

heading: 5 RELATED WORK
text: GNN-based approaches to KG completion (Hamaguchi et al., 2017; Schlichtkrull et al., 2018; Xu et al., 2020; Teru et al., 2020; Zhang et al., 2020) are becoming increasingly popular as they are more generally applicable than earlier solutions based on graph embeddings (Rossi et al., 2021). Typically, the predictions made by these techniques cannot be explained symbolically.
Rule mining techniques for KGs can categorised in two groups. Systems in the first category learn a model on training data and provide ways to extract rules from it: DRUM and similar approaches (Yang et al., 2017; Sadeghian et al., 2019; Wang et al., 2020) use RNNs, while others use reinforcement learning (Xiong et al., 2017; Das et al., 2018), dynamic neural module networks (Rocktäschel & Riedel, 2017; Campero et al., 2018), or graph embeddings (Omran et al., 2018; Zhang et al., 2019). However, the formal relationship between the model and the rules extracted from it is unspecified in these approaches; hence, model predictions can differ from the result of applying the rules. Systems in the second category, such as AnyBURL, use training data to identify patterns of paths in the graph that are represented as rules (Galárraga et al., 2015; Meilicke et al., 2019; Ahmadi et al., 2020; Gu et al., 2020); hence, they do not involve training an ML model.
Inductive Logic Programming (ILP) generates rules given a dataset and examples of positive and negative inferences so that rule application yields all positive and no negative examples (Muggleton, 1991). ILP techniques cannot typically handle noisy examples (Muggleton, 1991; Cropper & Muggleton, 2014; Si et al., 2019; Raghothaman et al., 2020). Other recent ILP systems, such as ∂ILP (Evans & Grefenstette, 2018), achieve robustness to noise by interpreting the ILP task as a binary classification problem and providing a differentiable implementation of deduction. These approaches are similar to rule mining techniques, and they compare to our work analogously. Furthermore, they focus on learning rules from small datasets and struggle with large-scale KGs.
Neuro-symbolic computation focuses on integrating Logic with neural networks (d’Avila Garcez et al., 2002). Rule extraction methods have focused on identifying classes of rules for which the immediate consequence operator can be simulated by recurrent (Hölldobler et al., 1999), fibring (Bader et al., 2005), or feed-forward networks (Bader et al., 2007). Their embedding methods are, however, different from ours, as they encode groups of facts as numeric vector components and they can only extract variable-free rules from trained networks. Recently, Dong et al. (2019) presented a network architecture that simulates application of arbitrary function-free first-order rules to a dataset. This work, however, does not provide an algorithm extracting rules from a trained model.
Existing methods for explaining the predictions of a GNN focus on identifying parts of the graph in the embedding space that are most relevant to a given prediction (Ying et al., 2019; Luo et al., 2020; Lin et al., 2021). These techniques are largely independent from the specifics of the model used. In contrast, we focus on a specific type of GNN and provide a logical proof for each prediction.
GNNs were shown capable of expressing graph property tests such as isomorphism, existence of cliques, bipartiteness, and planarity (Xu et al., 2019; Morris et al., 2019; Garg et al., 2020). Moreover, first-order logic queries expressible by GNNs correspond to the description logicALCQ (Barceló et al., 2020). Our work follows this line of research by relating GNNs and Datalog.
There has been work on neural learning of functions that are monotonic for the ordering on the real numbers You et al. (2017); Gupta et al. (2016); Wehenkel & Louppe (2019), and which rely on the use of non-negative matrices and monotonic activation functions. Our work, however concerns GNNs and the learning of monotonic functions for the ordering induced by the existence of homomorphisms between datasets, which is the notion of monotonicity in Logic and Data Management.

heading: 6 CONCLUSION AND FUTURE WORK
text: We presented a GNN-based transformation of datasets that mimics a round of application of Datalog rules. The predictions made by our transformation can be explained symbolically, and we have shown our approach to be practically feasible. We see many avenues for future work. On the theoretical side, we shall develop extensions that capture more complex rules (e.g., transitivity), as well as nonmonotonic extensions such as negation or aggregation. On the practical side, we shall establish links with the existing approaches to rule mining and ILP, thus allowing us to compare the performance of all of these heterogeneous approaches in a unified way.

heading: A PROOF OF PROPOSITION 7
text: Proposition 7. Let T be an operator on datasets, let r be a constant-free rule of form (2), let µ be a substitution that maps each variable of r to a distinct constant, and let Dr = {B1µ, . . . , Bmµ}. If T is monotonic under homomorphisms and Hµ ∈ T (Dr), then T captures r.
Proof. Consider T , r,Dr, and µ that satisfy the prerequisites of the proposition. Moreover, consider an arbitrary dataset D and an arbitrary fact α ∈ Tr(D); we show that α ∈ T (D). By the definition of operator Tr, there exists a substitution ν such that {B1ν, . . . , Bmν} ⊆ D and Hν = α. Now let h be the mapping of constants to constants such that h(xµ) = xν for each variable x in occurring in r. This definition of h is correct since µ maps each variable in r to a distinct constant. Also, rule r is constant-free, so h(Dr) = h({B1µ, . . . , Bmµ}) = {B1ν, . . . , Bmν} ⊆ D holds; moreover, each constant in Dr is obtained by instantiating a variable of r, so h is defined on all of cn(Dr)). In other words, h is a homomorphism from Dr to D. Since T is monotonic under homomorphisms by the assumption of the proposition, h is also a homomorphism from T (Dr) to T (D). Moreover, Hµ ∈ T (Dr) holds by our assumption, so the definition of homomorphisms ensures h(Hµ) ∈ T (D). Finally, atom H is constant-free, which together with the definition of h ensures h(Hµ) = Hν. Thus, we have Hν ∈ T (D), as required.

heading: B PROOF OF THEOREM 8
text: We prove Theorem 8 in two steps. First, we first introduce in Definition B1 a notion of homomorphisms on (Col, δ)-graphs that is analogous to the notion of homomorphisms on datasets. Then, in Lemma B2 we show that the transformation of (Col, δ)-graphs by an MGNN preserves such homomorphisms. Theorem 8 finally combines this result with our encoding and decoding steps. To formalise these results, we extend the order ≤ on real numbers to a partial order on vectors so that a1 ≤ a2 holds whenever (a1)i ≤ (a2)i holds for each position i. Definition B1. A label-respecting homomorphism from a (Col, δ)-graph 〈V, {Ec}c∈Col, λ〉 to a (Col, δ)-graph 〈V ′, {E′c}c∈Col, λ′〉 is a mapping h : V → V ′ such that λ(v) ≤ λ′(h(v)) for each vertex v ∈ V , and, for each colour c ∈ Col and each edge in Ec between vertices v and w, vertices h(v) and h(w) are connected by an edge in E′c.
Lemma B2. For each (Col, δ)-MGNNM and all (Col, δ)-graphs G and G′, each label-respecting homomorphism h from G to G′ is also a label-respecting homomorphism fromM(G) toM(G′).
Proof. Consider a (Col, δ)-MGNNMwith components as specified in Definition 3, (Col, δ)-graphs G = 〈V, {Ec}c∈Col, λ〉 andG′ = 〈V ′, {E′c}c∈Col, λ′〉, and a label-respecting homomorphism h from G to G′. SinceM(G) andM(G′) have the same edges as G and G′, respectively, h satisfies the first condition of a label-preserving homomorphism fromM(G) toM(G′). We show that h also satisfies the second condition. To this end, let λ0, . . . , λL and λ′0, . . . , λ′L be the sequences of vertex labelling functions used in the computation ofM(G) andM(G′), respectively. We next show by induction on 0 ≤ ` ≤ L that λ`(v) ≤ λ′`(h(v)) holds for each vertex v ∈ V1; since classification function cls is monotonically increasing, this will imply that cls(λL(v)) ≤ cls(λ′L(h(v))) holds for each vertex v ∈ V1 as well, which proves our claim. The base case for ` = 0 holds immediately since λ0 = λ and λ′0 = λ′. For the inductive step, we assume that, for some ` − 1, we have λ`−1(v) ≤ λ′`−1(h(v)) for each v ∈ V1, and we show that λ`(v) ≤ λ′`(h(v)) also holds for each v ∈ V1. To this end, consider arbitrary i between 1 and the dimension of b`. By Definition 3, the i-th components of λ`(v) and λ′`(h(v)) are equal to σ(x1) and σ(x2), where x1 and x2 are as in (3) and (4) for (A`)i and (B`c)i the i-th rows of A
` and B`c, respectively:
x1 = (A `)i λ `−1(v) + ∑ c∈Col (B`c)imax{λ`−1(w) | w ∈ Nc(v)} + (b`)i, (3)
x2 = (A `)i λ ′`−1(h(v)) + ∑ c∈Col (B`c)imax{λ′`−1(u) | u ∈ Nc(h(v))}+ (b`)i. (4)
By the inductive hypothesis, we have λ`−1(v) ≤ λ′`−1(h(v)); moreover, all numbers in A` are nonnegative, so we clearly have (A`)iλ`−1(v) ≤ (A`)iλ′`−1(h(v)). In addition, mapping h
satisfies the first property of label-preserving homomorphisms so, for each colour c ∈ Col and each w ∈ Nc(v), we have h(w) ∈ Nc(h(v)); moreover, by the inductive hypothesis, we have λ`−1(w) ≤ λ′`−1(h(w)). By combining these two observations, we have
max{λ`−1(w) | w ∈ Nc(v)} ≤ max{λ′`−1(u) | u ∈ Nc(h(v))},
which, together with the fact that all numbers in (B`c)i are nonnegative, implies
(B`c)imax{λ`−1(w) | w ∈ Nc(v)} ≤ (B`c)imax{λ′`−1(u) | u ∈ Nc(h(v))}.
Consequently, we have x1 ≤ x2. Finally, activation function σ is monotonically increasing, so σ(x1) ≤ σ(x2) holds, which completes our proof of the inductive step.
Theorem 8. For each (Col, δ)-MGNNM, mapping TM is monotonic under homomorphisms.
Proof. Consider an arbitrary (Col, δ)-MGNN M, arbitrary datasets D and D′, and an arbitrary homomorphism h from D to D′; thus, h(D) ⊆ D′ holds. Now let GD and GD′ be (Col, δ)-graphs obtained by transforming D and D′ as in Definition 2. Moreover, let g be the mapping from the vertices of G1 to the vertices of G2 defined as follows:
• g(va) = vh(a) for each vertex va of G1; and • g(va,b) = vh(a),h(b) for each vertex va,b of G1.
It is straightforward to see that g is a label-respecting homomorphism from GD to GD′ . By Lemma B2, mapping g is also a label-respecting homomorphism fromM(GD) toM(GD′). Thus, however, implies that h is also a homomorphism from T (D) to T (D′), as required.

heading: C PROOF OF THEOREM 10
text: Theorem 10. For each (Col, δ)-MGNNM and each dataset D, we have TM(D) = TPM(D).
Proof. Consider arbitraryM, PM, and D as stated in the claim. Let L be the number of layers of M, and let k be the dimension ofM. Since operator TPM captures each rule in PM by definition, we clearly have TPM(D) ⊆ TM(D). For the converse, consider an arbitrary fact α ∈ TM(D). We next construct a rule r for which we prove r ∈ PM and α ∈ Tr(D). Let GD be the (Col, δ)-graph obtained from D by the transformation in Definition 2, and let VD be the set of vertices of GD. For each ` ∈ {0, . . . , L}, let v` be the vector labelling each v ∈ VD in the computation ofM(GD). Moreover, let µ be a substitution that maps each variable to a distinct constant. We next construct an atom H , a conjunction C, a substitution ν from the variables in C to cn(D), a set U of fresh vertices (i.e., vertices not occurring inGD) of the form ud and ud,e for d and e constants from the image of µ, and mappings ξ : U → VD and Mc : U → 2VD for each c ∈ Col. We also assign each vertex in U to a level between 0 and L, and we identify a single vertex from U as the root vertex. In the rest of this proof, we use letters a and b for the constants in D, letters d and e for the constants in the image of µ, possibly indexed letters v, w, and s for the vertices in VD, and possibly indexed letters u and t for the vertices in U . Our construction is by induction from level L down to level 1, and we prove in parallel the following properties:
P1. for each vertex of the form ud ∈ U , for x the variable such that µ(x) = d, and for a = ν(x), we have ξ(ud) = va;
P2. for each vertex of the form ud,e ∈ U , for x and y variables such that µ(x) = d and µ(y) = e, and for a = ν(x) and b = ν(y), we have ξ(ud,e) = va,b;
P3. conjunction C satisfies ν(C) ⊆ D; and
P4. if H is of the form A(x), conjunction C is (3k, L)-tree-like for x; otherwise it is of the form Cx ∧ Bx,y ∧ Cy , where Cx and Cy are (3k, L)-tree-like conjunctions for x and y, respectively, and Bx,y is a nonempty conjunction of atoms of the form S(x, y) or S(y, x).
We initialise C as the empty conjunction, and we set ν, ξ, and each Mc for c ∈ Col as the empty mappings. For the induction base, we consider the form of the atom α ∈ TM(D) and proceed as follows; the base case also identifies the root vertex. Properties P1–P4 clearly hold after these steps.
• If α is of the form A(a), then VD contains vertex va. We introduce a fresh variable x, and we let d be the constant such that d = µ(x). We define ν(x) = a; we define H = A(x); we introduce vertex ud of level L; we define ξ(ud) = va; and we make ud the root vertex. Finally, we extend C with atom B(x) for each B(a) ∈ D. Note that C can be empty if D does not contain a fact such as B(a). However, va ∈ VD implies that constant a must occur in D in a fact of the form S(a, b) or S(b, a). Thus, Nc(va) 6= ∅ for c ∈ {c1, c2, c4}. Since L ≥ 1, vertex ud is processed in the inductive step below, which will extend C with an atom that contains variable x. • If α is of the form R(a, b), then VD contains vertices va,b and vb,a; due to the latter, D contains at least one fact of the form S(a, b) or S(b, a), and so VD contains vertices va and vb. We introduce fresh variables x and y, and we let d and e be constants such that d = µ(x) and e = µ(y). We define ν(x) = a and ν(y) = b; we define H = R(x, y); we introduce vertices ud, ue, ud,e, and ue,d of level L; we define ξ(ud) = va, ξ(ue) = vb, ξ(ud,e) = va,b, and ξ(ue,d) = vb,a; and we make ud,e the root vertex. Moreover, we extend C with an atom S(x, y) for each S(a, b) ∈ D, an atom S(y, x) for each S(b, a) ∈ D, an atom B(x) for each B(a) ∈ D, and an atom B(y) for each B(b) ∈ D; note that, C cannot empty after this step. Finally, we define Mc(u) = Nc(ξ(u)) for each u ∈ {ud,e, ue,d} and colour c ∈ Col; note thatMc1(u),Mc2(u), andMc3(u) are all singletons, andMc4(u) = ∅.
Next, we consider each level ` with 1 ≤ ` ≤ L that has already been processed, and we consider each vertex of the form ud of level `. Let x be the variable such that µ(x) = d, and let a = ν(x); property P1 ensures ξ(ud) = va. For each colour c ∈ {c1, c2, c4}, we choose a smallest set Mc(ud) ⊆ Nc(va) such that, for each `′ ∈ {0, . . . , `− 1} and each i ∈ {1, . . . , k}, there exists a vertex w ∈Mc(ud) satisfying
(w` ′ )i = max{(s` ′ )i | s ∈ Nc(va)}. (5)
Note that set Mc(ud) may not be unique, but any set satisfying (5) can be selected. There are at most k distinct values of (w` ′ )i for each `′, so set Mc(ud) contains at most k` elements. We also define Mc3(ud) = ∅. We now consider each vertex v ∈Mc1(ud) ∪Mc2(ud) ∪Mc4(ud). By Definition 2, such v is of the form va,b, vb,a, or vb for b ∈ cn(D), depending on the set from which v is drawn. Set VD clearly also contains vertices vb,a and vb if v ∈Mc1(ud), and vertices va,b and vb if v ∈Mc2(ud). Moreover, if v ∈Mc4(ud), then VD clearly contains vb, and Mc4(ud) ⊆ Nc4(va) ensures thatD contains a fact of the form S(a, b) or S(b, a); thus, VD also contains va,b and vb,a. We introduce a fresh variable y, and we let e be the constant such that e = µ(y). We define ν(y) = b; we introduce vertices ue, ud,e, and ue,d of level `− 1; and we define ξ(ue) = vb, ξ(ud,e) = va,b, and ξ(ue,d) = vb,a. Moreover, we extend C with an atom S(x, y) for each S(a, b) ∈ D, an atom S(y, x) for each S(b, a) ∈ D, and an atom B(y) for each B(b) ∈ D. Finally, we define Mc(u) = Nc(ξ(u)) for each u ∈ {ud,e, ue,d} and colour c ∈ Col; note that Mc1(u), Mc2(u), and Mc3(u) are all singletons, and Mc4(u) = ∅. Since each Mc(ud) with c ∈ {c1, c2, c4} contains at most k` vertices and we consider three colours, this step introduces at most 3k` fresh variables. Moreover, note that each fresh variable y occurs in C in an atom of the form S(x, y) or S(y, x). Finally, it should be clear that P1–P4 hold after level ` is processed.
This completes our inductive construction. At this point, either H = A(x) and C is a nonempty (3k, L)-tree-like conjunction for x, or H = R(x, y) and C = Cx ∧Bx,y ∧ Cy where Cx and Cy are (3k, L)-tree-like conjunctions for x and y, respectively, and Bx,y is a nonempty conjunction of atoms of the form S(x, y) or S(y, x). Thus, rule H ← C is of the form A(x)← Cx or R(x, y)← Cx ∧Bx,y ∧ Cy . To complete the proof, we next show this rule is captured by TM. Then, Definition 9 ensures ensures H ← C ∈ PM; together with Hν = α and ν(C) ⊆ D, we have α ∈ TPM(D), which proves our claim. We use Proposition 7 to show thatH ← C is captured by TM. To this end, letDC = {αµ | α ∈ C}, and letGDC be the (Col, δ)-graph constructed using vertices in U obtained by applying the encoding from Definition 2 to dataset DC . Finally, let u` be the labelling associated with each vertex u ∈ U in the computation ofM(GDC ). The construction of C clearly ensures the following two properties for each colour c ∈ Col and each vertex u ∈ U :
R1. for each vertex v ∈Mc(u), there exists a vertex t ∈ Nc(u) such that ξ(t) = v; and
R2. for each vertex t ∈ Nc(u) in graph GDC , we have ξ(t) ∈ Nc(ξ(u)).
We now show by the induction on ` that, for each 0 ≤ ` ≤ L and each vertex u ∈ U whose level is at least `, we have u` = v` for v = ξ(u). For the base case ` = 0, we have the following possibilities.
• Assume u is of the form ud. Let x be the variable such that d = µ(x), and let a = ν(x). Property P1 ensures ξ(ud) = va, and the construction of C ensures B(x) ∈ C if and only if B(a) ∈ D; thus, u0d = v0a holds. • Assume u is of the form ud,e. Let x and y be variables such that µ(x) = d and µ(y) = e, and let a = ν(x) and b = ν(y). Property P2 ensures ξ(ud,e) = va,b, and the construction of C ensures S(x, y) ∈ C if and only if S(a, b) ∈ D; thus, u0d,e = v0a,b holds.
For the induction step, assume that the property holds for some `− 1, and consider an arbitrary vertex u ∈ U whose level is at least `. Let v = ξ(u). The induction assumption ensures u`−1 = v`−1. Also, for each colour c ∈ Col, our construction ensures that each vertex t ∈ Nc(u) is of level at least `− 1, so the induction assumption ensures t`−1 = w`−1 for w = ξ(t). Finally, property R2 ensures that each t`−1 used to compute u` is considered when computing v`, and property R1 ensures that the maximal values of t`−1 are also present in the computation of u`. Thus, u` = v` holds.
To complete the proof, let u be the root vertex, and let v = ξ(u). The above property ensures uL = vL, and so cls(uL) = cls(vL) as well. Thus, we have µ(H) ∈ TM(DC), so Proposition 7 allows us to conclude that rule H ← C is captured by TM.
Please note that given a (Col, δ)-MGNN M, a dataset D, and a fact α ∈ TM(D), the proof of Theorem 10 shows how to identify a rule r ∈ PM such that α ∈ Tr(D). A user interested in understanding why TM derived α from D can apply this procedure to extract a rule r that explains why α was derived. Furthermore, a user can then search for shorter explanations by considering rules that subsume r and checking whether they are still captured by TM (using Proposition 7), and whether they still derive α from D.

heading: D OPTIMISED RULE EXTRACTION ALGORITHM
text: In this section we describe the rule extraction algorithm that we have implemented and used to obtain the results in in Table 4 from Section 4. The pseudocode for the algorithm is shown in Algorithm 1.
Our algorithm takes as input a trained modelM and a number m and generates as output a list of (3k, L)-tree-like rules captured by TM with at mostm atoms in the body, with k andL the dimension and number of layers ofM respectively. The algorithm relies on rule subsumption checks to ensure that redundant rules (i.e., logically implied by another rule) are not included in the output.
The algorithm starts by initialising an empty mapping head to bodies in Line 1. This mapping will store pairs of the form (S(x, y), {C1, C2, . . . , Cn}), where each S(x, y) ← Ci is a (3k, L)tree-like rule captured by TM with no more than m body atoms. In each iteration i of the loop in Lines 2–15, the algorithm will generate rules with exactly i atoms in the body. To this end, the algorithm iterates over all ordered combinations of predicates with repetition of length i, which are generated by the auxiliary function COMBINATIONS(i). Then, in Line 4, given the list of predicates pred list, the algorithm iterates over all conjunctions (up to variable renaming) that can be obtained by transforming each predicate in pred list into an atom, using a number of variables no greater than the size of pred list. For example, if pred list is [A,R], where A is unary and R is binary, then BODIES(pred list) is(
A(x) ∧R(x, x), A(x) ∧R(x, y), A(x) ∧R(y, x), A(x) ∧R(y, y) )
Lines 5 and 6 discard each conjunction that is not (3k, L)-tree-like, to avoid testing rules that do not have such form. Lines 7-9 ground the conjunction body, apply TM to the result, and lift the resulting dataset back into a set of non-ground atoms. In particular, ENCODE(body) grounds body by mapping each variable to a different constant, and then encodes the result into a (Col, δ)-labelledgraph as described in Section 2. Function DECODE(output graph) performs the reverse operation,
Algorithm 1 Rule extraction algorithm Input: m : natural number (max. num. of atoms desired in the body of an extracted rule)
M : MGNN model (from where we extract rules) 1: head to bodies : = ∅ 2: for i ≤ m do 3: for pred list in COMBINATIONS(i) do 4: for body in BODIES(pred list) do 5: if not TREELIKE(body) then 6: next; 7: input graph← ENCODE(body) 8: output graph←M(input graph) 9: heads← DECODE(output graph)
10: for head in heads do 11: new head, new body ← NORMALISE(head, body) 12: for prev body in head to bodies(new head) do 13: if SUBSUMES(prev body, new body) then 14: break; 15: head to bodies(new head).add(new body) 16: extracted rules := [ ] 17: for (head, bodies) in head to bodies do 18: for body in bodies do 19: extracted rules.append(head← body)
return extracted rules
and the result is a set heads of non-ground atoms, where each set element head is such that TM captures head← body. In Line 10, the algorithm iterates over each head in heads. Line 11 rewrites the candidate rule head ← body to ensure that heads of extracted rules always use variables x and y in this order, and it makes the corresponding substitutions in the body of the candidate rule. The result is rule new head ← new body. Lines 12 and 14 check whether new head ← new body is subsumed by any rule previously stored in head to bodies. If it is not, then Line 15 adds rule new head ← new body to head to bodies. Specifically, conjunction new body is added to the set head to bodies(new head). Finally, Lines 16 to 19 process the mapping head to bodies and output all rules encoded in it.
Algorithm 1 satisfies the following property, which ensures its correctness. Proposition D1. Let EXTRACT(M,m) be the set of rules generated by Algorithm 1 for a (Col, δ)-MGNNM, of dimension k and L layers, and a number m ∈ N. Then:
1. For every r ∈ EXTRACT(M,m), r is a (3k, L)-tree-like rule r captured by TM with no more than m atoms in the body.
2. For every (3k, L)-tree-like rule r captured by TM with no more than m atoms in the body, there exists a rule in EXTRACT(M,m) that subsumes r (up to variable renaming).
Proof. Item 1 is a direct consequence of Proposition 7 and the fact that Algorithm 1 only evaluates (3k, L)-tree-like rules with at most m atoms in the body. To see that Item 2 holds, one can straightforwardly verify that if r is a (3k, L)-tree-like rule with at most m atoms in the body, then Lines 2-9 of Algorithm 1 check whether this rule is captured by TM; if so, Lines 10-15 ensure that r is either in the output of the algorithm, or the output contains a rule that subsumes it.
In Section 4, we used Algorithm 1 with m = 2 to extract, for each benchmark, all the rules from the corresponding PM that have at most two atoms in the body and are not subsumed by another rule in the program. Table 6 shows the classification metrics obtained by using the extracted program to classify the positive and negative examples in the testing dataset of each benchmark.

Review summaries:
This paper focuses on graphs representing sets of facts in a knowledge base, and casts knowledge graph completion as a graph labeling problem. The authors propose a particular encoding of facts into graphs, and introduce a particular family of "monotonic graph neural networks" (MGNNs) that share properties with logical inference rules in Datalog: namely, they prove that MGNNs are "monotonic under homomorphisms", which effectively means that renaming objects or introducing new facts never causes the classification to switch from True to False. The authors also prove that for any MGNN (with a fixed classification threshold) there exists a set of rules in Datalog that produce the same conclusions, and treat this as a symbolic explanation for the MGNN's behavior. They evaluate MGNNs on a set of knowledge graph completion tasks, and find that it performs on par with some other methods for knowledge graph completion.

The paper proposes the Monotonic Graph Neural Network (MGNN) model that can be exploited to learn tasks on knowledge graphs. Knowledge graphs are referred to as "datasets", that are based on constants, unary and binary predicates. A method is defined to encode a given dataset (i.e. a KG) as a colored graph, whose nodes correspond to the constants and pairs of constants. Edges of one out of four different "colors" (types) are added to encode the relationships between constants and the occurrences of their pairs in binary predicates. A vector is stored in each node to represent the truth table of each predicate when computed on the corresponding grounding. The MGNN processes such a graph to computed a new KG in which new facts are inferred. A theoretical result shows that an equivalent set of Datalog rules can be derived from the trained MGNN, thus providing a direct explanation of the learned model. The proposed approach is evaluated on KG benchmarks, showing promising results when compared to other 2 state of the art methods.

This paper proposes a new family of GNN-based transformations for knowledge graphs, which is called monotonic GNNs (MGNNs). The key characteristic of MGNNs is that we can produce an equivalent set of rules for an arbitrary MGNN, and the rules and the MGNN-based transformation can produce the same facts. In other words, the rules can be used to explain how MGNNs make predictions. Moreover, the authors provide dedicated proofs for their formal statements. The experimental results on classification tasks for knowledge graph completion demonstrate the effectiveness of the approach.