Explainable GNN-Based Models over Knowledge Graphs
Authors: David Jaime Tena Cucala
Bernardo Cuenca Grau
Egor V. Kostylev
Boris Motik
Venue: ICLR 2022 Poster (2022)

Abstract: Graph Neural Networks (GNNs) are often used to learn transformations of graph data. While effective in practice, such approaches make predictions via numeric manipulations 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. In particular, 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 automatically extract rules that completely characterise the transformation. We evaluate our approach by applying it to classification tasks in knowledge graph completion.

Published as a conference paper at ICLR 2022
EXPLAINABLE GNN-BASED MODELS OVER KNOWLEDGE GRAPHS
David Tena Cucala
Bernardo Cuenca Grau
Department of Computer Science University of Oxford, UK
Department of Computer Science University of Oxford, UK
Egor V. Kostylev
Boris Motik
Department of Informatics University of Oslo, Norway
Department of Computer Science University of Oxford, UK
ABSTRACT
Graph Neural Networks (GNNs) are often used to learn transformations of graph data. While effective in practice, such approaches make predictions via numeric manipulations so their output cannot be easily explained symbolically. We pro- pose a new family of GNN-based transformations graph data that can be trained effectively, but where all predictions can be explained symbolically logical in- ferences in Datalog- a how to encode input knowledge graph into graph with numeric feature vec- tors, process this graph using a GNN, and decode the result into an output knowl- edge graph. We use new class of monotonic GNNs (MGNNs) 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 automatically extract rules that com- pletely characterise the transformation. We evaluate our approach by applying it to classification tasks in knowledge graph completion.
rule-based formalism. In particular, we show
INTRODUCTION
Knowledge graphs (KGs) (Hogan et al. 2021) describe application domain as a collection of entities and their relationships, and they are frequently used applications such as Web search, recommendation, fraud detection, and data integration. Many such applications involve realising transformation on knowledge graphs. For example, 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 recommender system then transform this graph into another graph containing recommended user-item interactions. Moreover, a KG completion system (Rossi et al., 2021] Bordes et al. 2013) Teru al., 2020) transforms an input graph into another graph containing relationships missing in the input. Usually, such transformations are not given explicitly, but are 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 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, the transformation can be difficult to understand because GNNs compute predictions through numeric calculations. For example, it would be use- ful to know that a system recommended novel The Idiot because the user liked Crime and Pun- ishment and both novels were written by Dostoevsky. There is growing interest in explaining GNN predictions. Numerous methods focus on identifying relevant subgraphs in the embedding space (Ying et al. 2019; Luo et al. 2020 Lin al., 2021), but such approaches do not explain predictions symbolically that is, by showing how a prediction can be derived from the input KG via logical inferences of knowledge representation formalism. Datalog (Abiteboul et al.

---

Published as a conference paper at ICLR 2022
Ceri al. 1989 is a prominent such formalism. It allows one model application do- main using then' rules, which can be applied to facts to derive new facts. For example, we can represent knowledge about literature using facts Author Dostoevsky, Crime and Punishment) and Author Dosstoessky The Idior), and past interactions using fact Likes (Crime and Punishment). Then, applying rule Author(a: y1) A Author(a: 1/2 A Likes(y)) derives fact Recommend The Idiot). Datalog engines (Motik et al. (014) can generate human- readable proof's explaining why a fact follows from the rules and the data, which can help foster trust in system predictions, ensure norm compliance, and enable verification of fairess standards.
1993
Recommend((2) to these facts
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 stages mentioned earlier, but these were carefully crafted to ensure that the transformation can always be described symbolically. To this end, we introduce a novel class of monotonic GNNs (MGNNs) that ensure an important property: when values in input feature vectors increase, value of an output feature vector decreases. To capture this intuition formally, we show that our transformation is monotonic under homomorphisms well- 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 each MGNN, there exists an equivalent set of rules such that, on each 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 and use it to provide further predictions; however, such predictions can always be explained using rules, For example, we could train an MGNN on graph containing examples of credit applications and then support srcision-making for new applications by applying the model to a different graph. For each MGNN obtained in such a way. there exists set of rules that filly explains each credit recommendation; extracting all such rules can be computationally expensive, but one can typically extract a representative subset of such rules in practice. Thus, we integrate MI. and symbolic Al in a single framework, allowing applications to use the best of both worlds.
We demonstrate the effectiivnnes of our approach by applying it to classification tasks in KG com- pletion. Using well-known benchmarks, we compare our system's s performance with the state-of- the-art KG completion systems DRUM (Sadeghian et al. 2019) and AnyBURL (Meilicke et al.) 2019). We show that, in addition to providing an exact correspondence between the model and the extracted rules, our technique also offers competitive performance.
Our proofs are given in the appendix, and the source code is available as supplementary material.
AN MGNN-BASED TRANSFORMATION OF KNOWLEDGE GRAPHS
We now describe our GNN-based transformation of knowledge graphs. In this paper, we see a KG as dataset, which is a finite set of facts of the form A(a) R(a1, where A is unary predicate, R is a binary predicate, and a, d1, and 02 are constants. Constants represent entities from an application domain, unary predicates typically represent entity types, and binary predicates represent entity relationships. For example, the statements that user likes Crime and Punishment and it is novel written by Fyodor Dostoevsky can be represented as facts Likes( (Crime latnaaannnniimeeeeeeeeee Punishment) and Author Dostoevsky, Crime_ane Lmd__Punishee 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 D.
Our transformation is realised as an operator TM that is parameterised by GNN M and that maps datasets to datasets. dataset 1) is first encoded into a graph GD whose vertices are labelled with numeric feature vectors; graph GD is then processed by M: finally, the result is decoded to the output dataset TM (D). In Section 3 we show that, A is a special kind of GNN that we call monotonic, then T. is equivalent to round of Datalog rule application. and we can automatically extract from TM an equivalent set of rules. The space of encodings of D consists of coloured graphs, which extend standard undirected graphs in two ways. First, each vertex is labelled by numeric feature vector of a fixed dimension, which allows the graph to be processed by M. Second, each edge in the graph is assigned colour, which allows us distinguish different types of connections.
2

---

Published as a conference paper at ICLR 2022
D:
G
Likes
encoding
1i0e
Crime uadddddddPdnnn Punishment
1
61
Author
The Idint
~ decoding
Dostoeusly
Author
63
63
Figure 1: Graphical representation of dataset D {Author( (Dottoovkkst, Crime_ane Punishmen) Auhhor(Dostoessky, The Idiot), LireseCrime Laa.aanddPPPiniaanee )unishment) } and its encoding GD
Figure 1 shows the encoding of the dataset D from the introduction. We introduce vertices Ups Ucp, and By in GD to represent constants Dostoevsky, The Idiot, and Crime and Punishment. To represent relationships between constants, we introduce vertices UD,.P, UCP.s, UD&J, and vr,ssi we do not introduce vertices UCR/ and U1CP because the corresponding constants do not occur together in fact of D. We then encode unary and binary predicates using feature vectors labelling the graph's vertices. To this end, we assign to each predicate a fixed position in the feature vectors; for example, we assign position to predicate Likes and position 3 to predicate Author. Then, we represent fact Likes( Crime and Londd_Pnishumen Punishment) by setting the first element of the feature vector of eer to one, and we represent fact Author Author(Dostoevaa Dostoevsky, Crime _andeaan___aeea Punishment) by setting the third element of the feature vector of UD&CP one. Finally, we connect with coloured edges all pairs of vertices of GD that refer to related constants. For example, we connect vertices up, and UD& by an edge of colour C1 to indicate that Dostoevsky occurs first in the constant pair of UD&CP. We analogously connect UDs CP and UCP by an edge of colour cg. We connect UCP.Ds and UDs.CP by an edge of colour c3 to indicate that the constant pairs of the two vertices are inverses of each other. Finally, we connect eCr and EDs by an edge of colour C4 to indicate that the two constants occur jointly in a fact of D.
Formally, we fix set of four colours Col {ci, c2 C3, C.). We assume that datasets and derived facts will use finitely many predicates, and we fix a list AI,..., Ac. .e+1...., Rs of available unary and binary predicates. We consider vectors and matrices over the reals R and its nonnegative subset Rt. For v a vector, (v); is the i-th element of v. We apply scalar functions to vectors and matrices element-wise for example, for vi...., Vn vectors of equal dimension, max Vi..... Vn the vec- tor whose i-th element is max
(v,))}. Finally, function RR + R is monotonically increasing if x < y implies a (ar) S (v), and function a Boolean if it ranges over {0, 1}. The following definition describes the kind of graph that our encoding produces.
Definition 1. A (Col, graaphh is auple (V, (V.(Ec) {Ec) X) where is a finite set of vertices; for each e E Col, Ec is set of c-coloured undirected edges (possibly including self-loops) over V; and labelling À assigns to each u E V a vector M()) of dimension 8. If is implicitly understood, A(v) is written v. For E Col and v E V, Ne(u) is the set of vertices connected to by edge in Ee-
We are now ready to define our encoding of an arbitrary dataset into a (Col, 8)-graph GD.
Definition 2. The encoding of a dataset is the (Col, 8) -)-rrahh GD that contains a vertex Uo for each constant cn(D), and vertices ba and Ub,a for all (not necessarily distinct) constants a and b that occur together in binary fact in D. For each vertex Ua.b, GD contains an edge of colour Ci connecting Ve.b and Va, an edge of colour e2 connecting Vo.b and Ub, an edge of colour C3 connecting Va.b and Ub,a. and an edge of colour eą connecting and Ub. For each Va. labelling (v.)s is 1 if (a(a) E D and 0 otherwise. For each Va,b, labelling (V.,b); b)s is if R,(a, b) E D and 0 otherwise.
Graph Gn will be processed by GNN. As explain in detail in 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 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, monoooooi graph neural network (MGNN) M with L > layers is tuple (IA') JAsELL [B') bee (b' heeeL, o, cls). For each E (L....,L, L} and each c E Col, A and B', are matrices over R+ of dimension m² x n', and b a vector over IR of dimension nf such that n' m' L 8, and m² monotonically increasing activation function, and cls RR + (0.1) is a monotonically increasing classification function. funticiooiionuuncionn.. The dimension of M is max (n ..........
n' for each E E {2..... .).....). Moreover, o RR + R+ is
L).
3

---

Published as a conference paper at ICLR 2022
Applying M to a (Col, 8) graah G = (V, (Ect X) induces the sequence 2o.... X of vertex labellings where X = X and, for each E (1....,,I L) and v E V. the value of X (u) is given by
= (A -A e-
Σ
B max(w" w E No(o)) +b))
cECol
The result M(G) of applying M to G is the (Col, 8)-graph with the same vertices and edges as G, but where each vertex u E V labelled by cls( (u))
Intuitively, an MGNN consists of L layers. where each layer E {1....,L) L is defined by matrix A a matrix B: for each colour e, 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 explicitly given. An MGNN transforms an arbitrary (Col, 80.g)gp G into another (Col, d)-rrahh M(G) as follows. For each layer & E {0...., L}, each vertex v in G is associated with a labelling vf. Labelling vo is the labelling v of v in G. and, for each layer E, vertex v is labelled by feature vector v computed as specified in equation ( The feature vector of in the resulting graph is computed by applying the classification function cls to the final labelling v". Thus, MGNNs specialise GNNs by (i) taking the maximum of the features of vertex' neighbours (instead of the more commonly used sum or average), (ii) using nonnegative weights in matrices A and B (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 result M(GD) of applying an MGNN to the encoding GD of a dataset can be decoded into the output dataset of the transformation by essentially inverting the encoder (cf. Figure D.. Thus, for each MGNN M, we obtain an operator TM that is specified as follows.
Definition 4. For M (Col, 0MMGNN and D a dataset, (D(D) is the dataset that contains the fact Aa(a) for each i E [1,...,6) {} and each vertex vo such that (v ): = 1 in M(G and the fact [a b) for each i E {e + 1..... 8} and each vertex Va such that (Va,5):
in M(GD).
Note that the dimensions of the matrices of M are independent from the number of constants in dataset; in fact, .M can be trained on one dataset and then applied to another dataset that contains the same predicates but completely different constants. Our transformation thus ideally suited for inductive settings such as KG completion and recommendation (Teru et al. 2020; Hamaguchi et al.,
2017 van den Berg et al. 2017). where training and testing can involve distinct entities.
EXTRACTING AN EQUIVALENT SET OF DATALOG RULES
We now show that, for each MGNN M, we can automatically generate a set of Datalog rules P.M such that T' 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 t, is a constant or variable. A (Datalog) rule is an implication of the form (2). where H is the atom called the rule's 's head, all B, are atoms that together form the rule's body, and each variable H occurs in some B,
H A.A.A.AA Bm
(2)
A (Datalog) program is finite set of rules. A substitution is a mapping of finitely many variables to constants; for a an atom, ov is the result of replacing in a each variable x on which v is defined with v(z). Each rule r of form ( defines the immediate consequence operator T, on datasets: for D a dataset, set T, (D) contains fact Hv for each substitution v satisfying (B,V,.... Bmv} C D. For P a program, operator Tp on datasets is defined by Tp (D) = UrEP (D).
Our objective is to show that, for each MGNN M. operator TM 'behaves analogously' to Datalog rule application. Definition 5 specifies formally what this means in our setting.
Definition S. A homomorphism from dataset D to dataset D' is mapping h of constants to constants that is defined at least on cn( cn(D) and that satisfies h(D) S D', where h(D) is the dataset obtained by replacing each constant in D with h(o) 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 homomorphism from T ((D) to T(D)).
4

---

Published as a conference paper at ICLR 2022
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) A R(z, y)}. so (D) = = b)}. First, op- erator Tp is monotonic: adding facts to D cannot invalidate a consequence of Tp because the body r still matches so r derives S(a, b). Second, operator Tp is resilient to replacement of constants. For example, let D' = (A(c), R(e,c). e)} be obtained from D by replacing and b with Rule "cannot tell' that the constants have been replaced; thus, it derives (D(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 a af - T(D) for each dataset D.
Proposition 7. Let ' be an operator on datasets, let be a constant-free rule form 2 let μ be substitution that maps each variable of to distinct constant, and let D, = [Bi,,.... BmH If T is monotonic under homomorphisms and Hp E T(D,), then T captures r.
Intuitively, if some operator T captures rule T, then T3 provides us with a lower bound for the consequences of T on an arbitrary dataset-that is, T necessarily 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: we replace each variable in with a distinct constant, we collect the resulting body atoms in dataset D,, we apply T to Dr. and we 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 E P. so we can just apply this check to each r e P verify whether T captures P. This provides us with the necessary machinery for rule extraction.
We next show that operator T' is monotonic under homomorphisms, This shows that T' indeed 'behaves like' Datalog reasoning, and it will allow us to use Proposition for rule extraction.
Theorem 8. For each (Col, 6)-MNN M, mapping TM is monotonic under homomorphisms.
For mono- tonicity, note that adding facts to dataset D has the effect of possibly adding new vertices and edges and then flipping some elements of feacture vectors of Go from 0 to I; moreover, the elements of A and B are nonnegative so the arguments of a in equation ① can only increase; finally, functions o and cls are monotonically increasing so the elements of the feature vectors of MMGDD) can only flip from 0 to 1, which is equivalent to deriving more facts in (D). For the resilience of constant merging, replacing, say, constant b with constant a in D is tantamount to merging vertices t6 into Va in Gp: 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 (I) Note that, if aggregated neighbours using sum (as is common in the literature), then elements of the feature vectors in M(GD) could decrease due to merging, which would invalidate Theorem
Theorem 8 a consequence of the restrictions on MGNNs mentioned after Definition 3
Theorem g tells us that can check whether TM captures rule r using Proposition 7 This is key step of our rule extraction algorithm. In particular, we next show that it is sufficient to consider only rules of certain structure, and that the number of such rules is determined by the number of predicates 8, the dimension of M, and the number of layers of M. 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 the rules that pass this check. Such naïve procedure can be optimised in practice. For example, we can reduce the number of considered rules by observing that rules can logically imply other rules; for example, if determine that rule B(x) + A(z) is captured, then we do not need to consider any rule of the form ((x) + A(x) A C where C is an arbitrary conjunction: each such rule is logically implied by (zz) + A(x) and is thus redundant.
Definition@eeerribees the syntactic structure of the rules that can fully characterise TM- To this end, use the well--nown notion of primal graph of a conjunction C' 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 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 connected and acyclic (and, in particular, without self-loops).
Definition 9. Let and d be nonnegative integers. A constant-free conjunction C is (c, dr-tree- like 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., I occurs in C) and, for each vertex in the tree, the distance i of from is at most d and
5

---

Published as a conference paper at ICLR 2022
moreover has at most c(d - i) children. A (c, dre-tee-li rule is rule form A(x) t C2 or R(x,y)= &- C2 A Bz,y A Cy. where C2 and Cy are (c, dl-tree-like conjunctions for x and y. respec- rively. with variables in common, and Bryy is nonempty constant-free conjunction of binary atoms of the form S(x, y) or x(y,x)
For M a (Col, 6)-MGN with L layers and dimension k (see Definition 3 PM is the program that contains, up to variable renaming, each L)k, Ly-tree-liie like rule that is captured by TM-
The primal graph of conjunction A(z) A R(x, v) A Sxx, 2) is tree with root and children y and 2; thus, it is (2,1)-tree like for x, but not (1,1)-tre-likke for (since x is at distance from itself can have at most one child). In contrast, the primal graph of A(x) A R(x, v) A S(x, 2) A T T(y, is a triangle with nodes x. y, and 2, so it is not (c, dd--tre-likke for x for any e and d.
Theorem 10. For each (Col, 8)-MGNN M and each dataset D, we have TM(D) = TPM (D).
To prove Theorem 10 we present construction that, for each (Col, 8)-MGNN M. dataset D, and fact a E (D), constructs a rule r E PM such that a E T, (D) that is, rule r explains symboli- cally how M derives on D. Whether such an explanation is minimal is an open question.
Theorem 10 also describes the expressiveness (i.e., the kind of possible predictions) of TM- For example, MGNN can capture rule R(x, z) +- R(x, y) A R(y.z). To see that this the case, let D = [[(a, b), l(b, c)}. For an arbitrary MGNN M, Theorem ensurrss that all predictions of TM involving binary facts made by rules of the form R(x, y) C2 Be,y A Cy: however, no such rule can derive R(a, c) on D. so we necessarily have R(a, c) 4 TM(D) as well.
4 EVALUATION
We evaluated our approach on KG completion problem of extending a KG seen as dataset D to its complete version D' by adding missing facts. When seen as a classification problem, the aim is to learn Boolean function f(:-)) that takes a dataset D and a fact a over a fixed set of unary and binary predicates such that f(D, a)) returns true if and only if E D'. We consider the inductive variant of this problem, 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 (Meil- icke et al. 2019), two state-of-the-at approaches for knowledge graph completion.
DRUM learns end-to-end differentiable model that, given dataset 1) and a fact a, returns score representing the likelihood of a belonging to the completion of D; predictions are then com- puted by applying a threshold to the score. This is achieved by learning chain rules of the form H ) + B, (Zo, 21) A ... A B, (T ), each associated with a confidence score.
AnyBURL uses path sampling techniques to produce more general variant of chain rules in which variables can be replaced by constants. Each rule is associated with score. To compute a prediction value for dataset 1) and fact a, AnyBURL applies all rules D once, combines the confidence scores of all rules that derive a, and applies a threshold to the result.
Benchmarks and performance metrics. We used the 12 KG completion benchmarks by Teru training, validation, and testing, respectively; dataset statistics are shown in T
et al. (2020), which are based on FB FB15K-237 (Bordes et al. 2013).. NELL-995 (Xiong et al. 2017). and WNI8RR (Dettmers et al. 2018). Each benchmark provides disjoint datasets T, V, and S for
We evaluated our systems as follows. Each benchmark provides a method for randomly splitting its testing dataset S into the incomplete dataset S₁ and the set Sa of missing facts that should be added to Sy. We took (S,, a:) for each fact a E SM as a positive example for testing. Moreover, we randomly sampled SMl facts $1,..., 3n that use the predicates of S but are not contained in SM, and we took each (Sy, B,) as a negative example for testing. Sampling was necessary because the set of possible facts not contained in S is very large; moreover, random sampling of negative examples
Note that C₂ cannot be empty in a rule of form A(x) +- Cz since x is required occur in the hody.

---

Published as a conference paper at ICLR 2022
FBISK SKK2233
NELL
WNI8RR
v1
v2
v4
v1
v2
v3
v4
v1
V2
v3
v4
Train.
4,245
9,739
17,986
27,203
4,687
8,219
16,393
7,546
5,410
15,262
25,901
7,940
Valid.
489
1,166
2,194
3.352
414
922
1,851
876
630
1,838
3,097
934
Test.
2,198
4,623
8,271
13,138
933
5,062
8,857
7,804
1,806
4,452
6,932
13.763
Table 1: Number of facts for each benchmark and phase (Training, Validation, and Testing)
Precision
Recall
Accuracy
FI Score
AUC
Training (s)
A
D>
M
D>
A
D
M
A
M
A
D
M
D>
M
v1
100.0
82.2
98.5
25.6
40,5
32.7
62.9
65.9
66.1
41.1
54.2
49.1
62.0
68.6
65.7
15,540
9,192
100.0
85.3
99.5
47.9
48.5
41.
74.0
70.0
70.5
64.5
61.9
58.3
73.8
76.0
70.4
19,080
23,523
FB] 11
100.0
85.6
99.0
43.6
45.2
34.6
71.2
68.8
67.1
60.7
51.2
71.7
73.3
67.4
37,776
45,104
v4
100.0
88.8
99.4
46.0
41.6
35.1
73.0
68.2
67.5
63.0
56.7
52.0
73.0
73.7
67.3
87,000
42,540
NF1 11.1-.9 1995
v1
97.5
94.7
96.4
77.0
18.0
80.0
87.5
58.5
88.5
86.0
30,3
87.4
85.7
52.6
89.6
402
662
100.0
80.7
100.0
53.1
41.2
48.3
76.6
65.7
74.2
69.4
54.5
65.2
76.3
74.6
74.2
6,354
3,575
100.0
85.8
100.0
47.3
45.6
55.3
73.7
69.0
64.2
59.6
71.2
69.3
75.3
77.6
36,090
13,456
v4
100.0
80.3
99.5
44.3
26.8
57.2
72.2
60.1
78.5
61.4
40.2
72.6
71.6
67.1
78.5
3,990
16,839
v1
99.1
97.9
100,0
58.5
73.4
62.8
79.0
85,9
81.4
73.6
83,4
77.1
78.8
92.5
80.1
312
292
WNI NRR
100.0
96.3
100,0
75.7
69.8
60.8
87.9
83.6
80.4
86.2
80.9
75.6
59.8
87.4
80.3
2,856
856
99.7
91.3
100.0
48.4
59.7
28.3
74.1
77.0
64.1
65.2
72.2
44.1
60.6
85.2
64.0
9,984
2,423
4
99.9
98.3
100.0
71.6
65.6
58.0
85.8
82.2
79.0
83.4
78.7
73.4
59.0
93.9
79.0
1,638
409
Table 2: Results for AnyBURL (A), DRUM (D), and our MGNN- system (M), in percentages
for testing does not favour any particular way of constructing negative examples for training. The number of positive and negative examples was the same to ensure balance between precision and recall. For each system, we classified the positive and negative testing examples and computed the precision, recall, accuracy, and Fl score in the usual way, 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 was split with a 9:1 ratio into an incomplete dataset Ti and a set TM of missing facts that should be added to Ty. We used (T7, a) for each fact TM as a positive example for training, and we obtained negative examples (Tr,3) 3) by sampling 3 analogously to how this was done for testing. We trained MGNNs with two layers and the ReLU activation function;
used cross-entropy loss with a logistic sigmoid on (v) as the output probability; finally, we used the Adam optimisation algorithm with the standard learning rate (0.01) and weight decay (5 x 10-4), and a maximum of 50, 000 epochs. We implemented the procedure in Pytorch Geometric v1.5.0, and we 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 bases and their default config- urations. For each system and benchmark, we computed the accuracy on the validation dataset for range of thresholds; in our tests, we used the threshold that maximised accuracy.
Evaluation results. Table 2 shows the results of our evaluation. As one can see, our system was very competitive, and it outperformed both baselines on most benchmarks based on NELL-995. Table also shows the training times for DRUM and our system, which are are comparable; we cannot show any times for AnyBURL since this system does not train model.
Similarly to AnyBURL, our system attained extremely high precision scores; however, recall values were significantly lower, especially for the benchmarks based on FB 15K. This is because the testing dataset SM was obtained from S by random splitting so it contains many facts of the form R (a, b) where constants and b do not occur together in any fact in Sj. By Theorem 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 fact R(a, b) is placed into Sy only if S contains a fact of the form S(a, b) or Sb, a) for some predicate S. The results for our system obtained in this way are shown in Table 3 As one see, precision scores remain high, whereas recall values increase significantly; thus, accuracy, Fl score, and AUC values improve accordingly. Our system significantly outperformed all baselines in this setting; however,
7

---

Published as a conference paper at ICLR 2022
Benchmark
Precision
Accuracy
Score
v1
95.5
74.0
85.3
83.4
89.5
NELL-99 1995 FB15K-28
V2
90.3
70.0
79.9
76,9
85.8
88.8 8
72.6
81.7
79.9
86.9
v1
92.3
98.8
95.2
95.5
93.3
V2
83.5
57.3
73.0
68.0
79.4
v3
82.3
71.1
77.9
76.3
89.0
72.7
v1
82.1
100.0
89.1
90.2
95.1
WNISRR
V2
91.7
98.0
94.6
94.7
98.7
88.2
98.9
92.9
93.3
89.0
99.0
89,9
90.8
97.7
Table 3: Evaluation of the MGNN transformation with alternative splitting of the testing dataset
Benchmark
Rules with...
Benchmark
Total AnyBURL
Tree-like AnyBURL
Captured by TM
Captured
body
hody atoms
FBBIKK 257
vl
2.102
41,341
2812
252
1371
V2
3,370
27,900
v2
2823
404
102
1048
v3
3,199
42,590
v3
4805
490
118
1749
8,464
82,003
3574
584
134
1046
NELL 995
v1
149
215
NELL .995
891
49
707
V2
1,784
3,087
V2
1123
181
112
650
v3
2,308
5,085
V3
1104
277
181
603
1,308
841
187
108
606
WNI MRR
v1
19
WNTERR
397
V2
22
35
V2
$22
21
35
v3
23
19
v3
424
21
21
48
v4
20
54
Table 4: Rules of PM extracted
Table 5: Comparison of rule extraction with AnyBURL
this way of splitting the data gives our system an unfair advantage comparison, so we refrain from including in Table 3 the results of the baselines on these alternative testing datasets.
computed using Algorithm Tin Appendix the subset P C PM of all nonredundant rules with at most two body atoms. Table 4 shows the size of each such P. Operator Tp thus approximates TM-ttht that is, (D) (D) holds for each dataset D. To determine the quality of the approximation, we computed the precision and recall of Tp on the the complete results. One can see that precision is largely the same for TM. while recall decreases slightly (1.6% on average). Thus, 'short' rules seem to account for almost all predictions on the benchmarks.
Rule Extraction. For each benchmark,
test dataset of each benchmark; Table Appendix[[shoom
We analysed P manually and noticed that transformation rules such as symmetry (e.g.. nibling(z: y) + sibling x)) on FB (3K552377) inverse relations (e.g., CapitalOAArea( y) areaHas y, .)) FB15K-2377 and relationship subsumption (e.g., SthletePlayedii Teaan
able to learn numerous sound
Team(x, y) + athlete Team (z, y) on NELL-995).
In addition, for each benchmark, checked how many of the rules produced by AnyBURL captured by our transformation the results are shown in Table 5 For each benchmark, the first column shows the total number of rules produced by AnyBURL: the second column indicates how many of those are tree-like as per Definition D the third column shows how many rules from the second column captured by our transformation as per Definition and the fourth column shows the number of rules produced by AnyBURL that are captured by T' on the specific dataser- that is, rules r that satisfy T, (Sr) S (ST)... As one can see, significant proportion tree-like rules produced by AnyBURI are captured by TM- Additionally, significant proportion of (not necessarily tree-shaped) rules produced by AnyBURL are captured by TM on each specific dataset, which partially explains why many of the predictions by AnyBURL also obtained by T'-
We could not do this for DRUM since the version of the system available online cannot produce the rules.
8

---

Published as a conference paper at ICLR 2022
5 RELATED WORK
GNN-based approaches to KG completion (Hamaguchi et al., 2017] Schlichtkrull et al., 2018 Xu
ct al.) 2020; Teru et al. 2020 Zhang et al. 2020) are becoming increasingly popular because 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 fully explained symbolicaly.
Rule mining techniques for KGs fall in two categories, Systems in the first category learn model on training data and then extract rules from it. Neural-LP Yang et al.) 2017) an influential such approach, and it has inspired DRUM (Sadeghian et al. 2019) and Neural- Ncural-Num-LA (Wang et al.) 2020). Other approaches use reinforcement learning Xiong et al. 2017 Das al., 2018), dynamic neural module networks (Rocktäschel & Riedel| Camprro et al. 2018), or graph embeddings (Omran et al.) 2018 Zhang et al., 2019). However, the formal relationship between the learned model and the extracted rules is unspecified in these approaches; hence, the model and the rules can make different predictions. Systems in the second category, such as Any use training data to identify path patterss in graphs that are represented as rules (Galárraga et al. 2015 Meilicke et al. 2019 Ahmadi et al. 2020; Gu et al. 2020); hence, they do not train an ML. model.
Inductive Logic Programming (IIPP) generates rules given 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) [991] Cropper & Mug-
gleton 2014 Si et al. 2019; Raghothaman et al. (2020). To improve resilience to noise, recent ILP systems such OILP (Evans & Grefenstette 2018) interpret the ILP task as a binary classification problem and provide differentiable implementation of deduction. These approaches compare to our work analogously to rule mining techniques. Moreover, they focus on learning rules from small datasets and generally struggle with large-scale KGs.
Neuro-symbolic computation aims to integrate logic with neural networks (d Avila Garcez et al, 2002]. To this end, it was shown that the immediate consequence operator of certain classes of logic programs can be approximated by recurrent Hölldobleer et al. (1999), fibring Bader et al. (2005), and feed-forward networks [aderr et al. (2007); however, these techniques do not show how to extract program from a trained network. A method to extract rules captured by feed-forward networks was proposed by d Avila Garcez et al. (2001); however, in contrast to work, the extracted programs do not contain variables, and they are not guaranteed to be equivalent to the network. Recently, Dong let al. 2019) presented network architecture that simulates application of function-free first-order rules to a dataset, but no algorithm for extracting rules from a trained model was provided.
Existing methods for explaining the predictions of GNN focus on identifying parts of the graph in the embedding space that are most relevant to a given prediction (Ying et al. [019 Luo et al. [0200] Lin et al. 2021). These techniques are largely independent from the specifies of the model used. In contrast, we focus on specific type of GNN that can provide logical proof of each prediction.
GNNs can express graph property tests such as isomorphism, existence of cliques, bipartiteness, and planarity (Xu et al. 20199] Morris et al. 2019 Garg et al.) 2020). Moreover, first-order logic queries expressible by GNNs correspond to the description logic ALCQ (Barceló et al. 2020). Our work follows this line of research by relating GNNs and Datalog.
Similarly to our work, techniques for neural learning of monotonic functions on the ordering of real numbers Youu et al. 2017)] Cupta et al. 2016) Wehenkel & Louppe| 2019) also rely on nonnegative matrices and monotonic activation functions. We, however, focus on learning monotonic functions on the ordering induced by the existence of homomorphisms between datasets.
6 CONCLUSION AND FUTURE WORK
In this paper, we presented GNN-based transformation of datasets that mimics a round of applica- tion 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., transi- tivity), well nonmonotonie extensions such negation 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 unified way.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was supported by the AIDA project (Alan Turing Institute, EP/N510129/I) the SIR- IUS Centre for Scalable Data Access (Research Council of Norway, project number 237889), Samsung Research UK, Siemens AG, and the EPSRC projects AnaLOG (EP/P025943/1), OASIS (EP/S032347/1) and UK FIRES (EP/S019111/1).
REFERENCES
Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison Addison-Wesley, Reading, MA, 1995.
Charu Aggarwal. Recommender Systems-The Textbook. Springer, 2016.
Naser Ahmadi, Viet-Phi Huynh, Venkata Vamsikrishna Meduri, Stefano Ortona, and Paolo Papotti. Mining Expressive Rules in Knowledge Graphs. ACM Journal of Data and Information Quality, 12(2):8:1-8277, 2020.
Sebastian Bader, Artur S. d' Avila Garcez, and Pascal Hitzler. Computing First-Order Logic Pro- grams by Fibring Artificial Neural Networks. In Proc. of the 18th Int. Florida Artificial Intelli- gence Research Society Conf. (FLAIRS 2005), pp. 314-319, 2005.
Scbastian Bader, Pascal Hitzler, Steffen Hölldobler, and Andreas Witzel. A Fully Connectionist Model Generator for Covered First-Order Logic Programs. In Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI 2007), pp. 666 671, 2007.
Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The Logical Expressiveness of Graph Neural Networks. In Proc. of the 8th Int. Conf. Learning Representattons (ICLR 2020), 2020.
Antoine Bordes, Nicolas Usumier, Alberto García-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.
Andres Campero, Aldo Pareja, Tim Klinger, Josh Tenenbaum, and Sebastian Riedel. Logical Rule Induction and Theory Learning Using Neural Theorem Proving. CoRR, abs/1 abs/0899,,,,9,,, 2018.
Stefano Ceri, Georg Gottlob, and Letizia Tanca. What you Always Wanted to Know About Datalog (And Never Dared to Ask). FEEE Transactions on Knowledge and Data Engineering, 1(1):146- 166, 1989.
Andrew Cropper and Stephen H. Muggleton. Logical Minimisation of Meta-Rules Within Meta- Interpretive Learning. In Proc. of the 24th Int. Conf. Inductive Logic Programming (ILP 2014), pp. 62-75, 2014.
Rajarshi Das. Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andew McCallum. Go for Walk and Arrive the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning. In Proc. of the 6th Int. Conf. on Learning Representations (ICLR 2018), 2018
Artur S. d' Avila Garcez, Krysia Broda, and Dov M. Gabbay. Symbolic knowledge extraction from trained neural networks: A sound approach. Artificial Intelligence, 125(1-2):155-007 2001.
Artur d' Avila Garcez, Krysia Broda, and Dov M. Gabbay. Neural-symbolic Learning Systems- Foundations and Applications. Springer- Verlag, London, 2002.
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-1818, 2018.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural Logic Machines. In Proc. of the 7th Int. Conf. on Learning Representations (ICLR 2019), 2019.
10

---

Published as a conference paper at ICLR 2022
Richard Evans and Edward Grefenstette. Learning Explanatory Rules from Noisy Data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M. Suchanek. Fast Rule Mining in Ontological Knowledge Bases with AMIE+. VLDB Journal, 24(6):707-730, 2015.
V. K. Garg, S. Jegelka, and T. S. Jaakkola. Generalization and Representational Limits of Graph Neural Networks. Proc. of the 37th Int. Conf. on Machine Learning (ICML 2020), pp. 3419- 3430, 2020.
Yulong Gu, Yu Guan, and Paolo Missier. Efficient Rule Learning with Template Saturation for Knowledge Graph Completion. CoRR, abs/2003.06071. 2020.
Maya R. Gupta, Andrew Cotter, Jan Pfeifer, Konstantin Voevodski, Kevin Robert Canini, Alexander Mangylov, Wojtek Moczydlowski, and Alexander Van Esbroeck. Monotonic calibrated interpo- lated look-up tables. Journal of Machine Learning Research, 17:109:1-109:47, 2016.
Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto. Knowledge Transfer for Seweoff-nolledgeBBaaae Entities: A Graph Neural Network Approach. In Proc. of the 26th Int. Joint Conf. on Artificial Intelligence (IJCAI 2017), pp. 1802-1808, 2017.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation I Learning on Graphs: Methods and Applications. IEEE Data Engineering Bulletin, 40(3):52-74. 2017.
Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d' A'mat, Gerard de Melo, Claudio Gutiérrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel- Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan F. Sequeda, Steffen Staab, and Antoine Zimmermann. Knowledge Graphs. ACM Computing Surveys, 54(4):71:1-71:37 2021.
Steffen Hölldobler, Yvonne Kalinke, and Hans-Peter Störr Approximating the Semantics of Logic Programs by Recurrent Neural Networks. Applied Intelligence, 1 11(1):45-58 1999.
Wanyu Lin, Hao Lan, and Baochun Li. Generative Causal Explanations for Graph Neural Networks. In Proc. of the 38th Int. Conf. on Machine Learning (ICML 2021), volume 139, pp. 6666-6677 2021.
Zhiyuan Liu and Jie Zhou. Introduction to Graph Neural Networks. Morgan and Claypool Publish- ers, 2020.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized Explainer for Graph Neural Network. Proc. of the 34th Conf. on Neural Information Processing Systems (NeurIPS 2020), 2020.
Christian Meilicke, Melisachew Wudage Chekol, Daniel Ruffinelli, and Heiner Stuckenshmmidt. Anytime Bottom-Up Rule Learning for Knowledge Graph Completion. In Proc. of the 28th Int. Joint Conf. on Artificial Intelligence (IJCAI 2018), pp. 3137-3143, 2019.
C. Morris, M. Ritzert, M. Fey, W/L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. Proc. of the 33rd AAAI Conf. on Artificial Intelligence (AAAI 2019), pp.
2019.
Boris Motik, Yavor Nenov, Robert Piro, Ian Horrocks, and Dan Olteanu. Parallel Materialisation of Datalog Programs in Centralised, Main-Memor, RDF Systems. In Proc. of the 28th AAAI Conf. on Artificial Intelligence (AAAI 2014), pp. 129-137, 2014.
Stephen Muggleton. Inductive Logic Programming. New Generation Computing, 8(4):295-318, 1991.
Pouya G. Omran, Kewen Wang, and Zhe Wang. Scalable Rule Learning via Learning Representa- tion. In Proc. of the 27th Int. Joint Conf. on Artificial Intelligence (IJCAI 2018), pp. 2149-2155, 2018.
11

---

Published as a conference paper at ICLR 2022
Mukund Raghothaman, Jonathan Mendelson, David Zhao, Mayur Naik, and Bernhard Scholz. Provenance-Guiee Synthesis of Datalog Programs. Proceedings of the ACM on Programming Languages, 4(62):1-27, 2020.
Tim Rocktäschel and Sebastian Riedel. End-to-End Differentiable Proving. In Proc. of the 31st Conf. on Neural Information Processing Systems (NeurIPS 2017), pp. 3788-3800, 2017.
Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo. Knowledge Graph Embedding for Link Prediction: Comparative Analysis, ACM Transactions on Knowledge Discovery from Data, 15(2):14:11444 2021.
Ali Sadeghian, Mohammadrezz Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: End-To- End Differentiable Rule Mining On Knowledge Graphs. In Proc. of the 33rd Conf. on Neural Information Processing Systems (NeurIPS 20/9), pp. 15321-15331, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks and Learning Sys- tems, 20(1):61-80, 2009.
Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. Proc. of the 15th Euro- pean Semantic Web Conf. (ESWC 2018), pp. 593-607, 2018.
Xujie Si, Mukund Raghothaman, Kihong Heo, and Mayur Naik. Synthesizing Datalog Programs using Numerical Relaxation. In Proc. of the 28th Int. Joint Conf. on Artificial Intelligence (IJCAI 2019), pp. 61 6117-6124, 2019.
Komal K. Teru, Etienne Denis, and Will Hamilton. Inductive Relation Prediction by Subgraph Reasoning. In Proc. of the 37th Int. Conf. on Machine Learning (ICML 2020), volume 119 of Proceedings of Machine Learning Research, pp. 1448-9457 2020.
Rianne van den Berg, Thomas N. Kipf, and Max Welling. Graph Convolutional Matrix Completion, 2017.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and Léon Bottou. Stacked Denoising Autoencoders: Learning Useful Representations in Deep Network with a Local Denoising Criterion. Journal Machine Learning Research, 11(12), 2010.
Hongwei Wang, Fuzheng Zhang, Jialin Wang. Miao Zhao, Wenjie Li, Xing Xie, and Minyi Guo. RippleNet: Propagating User Preferences on the Knowledge Graph for Recommender Systems. In Proc. of the 27th ACM Int. Conf. Information and Knowledge Management (CIKM 2018), pp. 417 2018.
Hongwei Wang, Miao Zhao, Xing Xie, Wenjie Li, and Minyi Guo. Knowledge graph convolutional networks for recommender systems. In Proc. of the 30th Web Conf. (WWW 2019), pp. 3307-3313, 2019a
Peifeng Wang, Jialong Han, Chenliang Li, and Rong Pan. Logic Attention Based Neighborhood Aggregation for Inductive Knowledge Graph Embedding. In Proc. of the 33rd AAAI Conf. on Artificial Intelligence (AAAI 2019), pp. 7152-7159, 2019b..
Po-Wei Wang, Daria Stepanova, Csaba Domokos, and J. Zico Kolter. Differentiable learning of numerical rules in knowledge graphs. In Proc. of the 8th Int. Conf. on Learning Representations (ICLR 2020), 2020.
Antoine Wehenkel and Gilles Louppe. Unconstrained Monotonic Neural Networks. CoRR, abs/1908.055 164, 2019.
Wenhan Xiong. Thien Hoang, and William Yang Wang. DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning, In Proc. of the 2017 Conf. Empirical Methods in Natural Language Processing (EMNLP 2017), pp. 573, 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In Proc. of the 7th Int. Conf. on Learning Representations (ICLR 2019), 2019.
12

---

Published as a conference paper at ICLR 2022
Xiaoran Xu, Wei Feng, Yunsheng Jiang, Xiaohui Xie, Zhiqing Sun, and Zhi-Hong Deng. Dynami- cally Pruned Message Passing Networks for Large-scale Knowledge Graph Reasoning. In Proc. of the 8th Int. Conf. on Learning Representations (ICLR 2020), 2020.
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-2328, 2017.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNNExplainer: Generating Explanations for Graph Neural Networks. In Proc. of the 33rd Conf. on Neural Infor- mation Processing Systems (NeurIPS 2019), pp. 9240-9251, 2019.
Seungil You, David Ding, Kevin Robert Canini, Jan Pfeifer, and Maya R. Gupta. Deep lattice networks and partial monotonic functions. In Proc. of the 31st Conf. on Neural Information Processing Systems (NeurIPS 2017), pp. 2981-2989, 2017.
Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei- Ying Ma. Collaborative Knowl- edge Base Embedding for Recommender Systems. In Proc. of the 22nd ACM SIGKDD Conf. on Knowledge Discovery and Data Mining (KDD 2016), pp. 353-362, 2016.
Wen Zhang. Bibek Paudel, Liang Wang, Jiaoyan Chen, Hai Zhu, Wei Zhang. Abraham Bernstein, and Huajun Chen. Iteratively Learning Embeddings and Rules for Knowledge Graph Reasoning. In Proc. of the 30th Web Conf. (WWW 2019). pp. 2366-266 2366-2377, 2019.
Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient Probabilistic Logic Reasoning with Graph Neural Networks. In Proc. of the 8th Int. Conf. on Learning Representations (ICLR 2020), 2020.
13

---

Published as a conference paper at ICLR 2022
A PROOFS
A.1 PROOF OF PROPOSITION 7
Proposition 7. Let T be an operator on datasets, let be a constant-free rule of form 2 let μ be substitution that maps each variable of distinct constant, and let D, (BI,, Bmu}.. If is monotonic under homomorphisms and Hp E T(D)), then T captures T.
Proof. Consider T, r. D,, and j that satisfy the prerequisites of the proposition. Moreover, consider an arbitrary dataset D and an arbitrary fact E T, (D); we show that a E TDD). By the definition of operator Tr, there exists a substitution v such that [Bir,... Bm } C D and Hv = a. Now let h be the mapping of constants to constants such that h(pp)) = 2v for each variable x occurring in r. This definition of h is correct since μe maps each variable in to a distinct constant. Also, {Bir,... Bm S D holds; more- over, each constant in D, is obtained by instantiating variable of r. so h is defined on all of cn(Dr). other words, h is homomorphism from D, to D. Since T is monotonic under homo- morphisms by the assumption of the proposition, h is also a homomorphism from T(D,) to T(D)- Moreover, Hu E TD,)) holds by our assumption, so the definition of homomorphisms ensures k(Hu) E T(D). Finally, atom H is constant-free, which together with the definition of h ensures h(Hu)= ) = Hv. Thus, we have Hv E TDD), as required.
rule constant-free, so h (D,)) h([BIp...... (....,,,,,,p))
A.2 PROOF OF THEOREM g
We prove Theorem g in two steps. First, we first introduce in Definition A1 notion of homomor- phisms on Col, ( 5g-rrah that is analogous to the notion of homomorphisms on datasets. Then, in Lemma A2 we show that the transformation of (Col, 5)-graphs by an MGNN preserves such ho- momorphisms. Theorem [ finally combines this result with our encoding and decoding steps. To formalise these results, we extend the order I on real numbers to a partial order on vectors so that a & a2 holds whenever (a1); S (a2); holds for each position é.
Definition A1. A label-respecting homomorphism from a 8) --gapph (V, (EEteECon A) to (Col, 8)-grahh (V', (EE.hooo X\) is a mapping h : V + V' such that X(u) S (h(v)) for each vertex U V, and, for each colour e Col and each edge in Eg between vertices v and w, vertices h(V) and h(w) are connected by an edge in Ey-
Lemma A2. For each (Col, (Col,8)-MGH 8)-MGNN M and all (Col, -grapss G and G', each label-respecting homomorphism h from G to G' is also label-respecting homomorphism from M(G) to M(G)).
Proof. Consider a (Col, 8) -GGNN M with components as specified in Definition 3, (Col, 8)-graphs G == (V, [Ee)oeCol, X) and G' (V', (V',, X") and a label-respecting homomorphism h from G to G¹. Since M(G) and M(G') have the same edges as G and G', respectively, h satisfies the first condition of a label preserving homomorphism from M(G) to M(G'). We show that h also satisfies the second condition. To this end, let X ....,- and x"....,,X" X be the sequences of vertex labelling functions used in the computation of MGG) and M(G"), respectively. We next show by induction on 0 < & L that X((r) < (k(v)) holds for each vertex u E Vú: since classification function cls is monotonically increasing, this will imply that cls(X* < cls(x"((h(v)) holds for each vertex v E V1 as well, which proves our claim.
The base case for l 0 holds immediately since X = and X X. For the inductive step, we assume that, for some 8- 1, we have X-1 (w) < (hx)) for each E V1, and we show that ((v) S x (h(v)) also holds for each e E Vi. To this end, consider an arbitrary i between and the dimension of by. By Definition 3 the i-th components of (vv) and (((())) are equal to o (211) and a (I2), where Ii and x2 are as in 3 and for (At), and (B)), the i-th rows of A and B respectively:
2 = (A9x--10 (v)
+ Σ (B
J max - (w) | w E No(o)} + +(b)),
(3)
rECal
x2 = =2 x-- +
(Ba) max uE +((h())))+bb)
(4)
eECol
14

---

Published as a conference paper at ICLR 2022
By the inductive hypothesis, have (0) (h(l)h(t)); moreover, all numbers in A' are nonnegative, so we clearly have satisfies the first property of label-presrrving homomorphisms so, for each colour E Col and each w E No(,), we have h(w) E Na(h(v)); moreover, by the inductive hypothesis, we have X (h(w)). By combining these observations, have (w) S (
(h(v)). In addition, mapping (w) & (A (A))
max(X* ((x)))=)(w)) w E N.(o)) & max (u) | u E Nc(h(u))),
which, together with the fact that all numbers in (B are nonnegative, implies
(B:), max (w) w E NN(v)} & (B max[X* | u NN(h(e)))
Consequently, we have 21 I Z2. Finally, activation function is monotonically increasing, so (21) & (22) holds, which completes our proof of the inductive step.
Theorem 8. For each (Col, 6M-GNN M, mapping TM is monotonic under homomorphisms.
Proof. Consider an arbitrary (Col, 8)-MGNN M, arbitrary datasets D and D', and an arbitrary homomorphism h from D to D'; thus, h(D) S D' holds. Now let GD and GD be (Col, 8)-graphs obtained by transforming D and D' as in Definition Moreover, let be the mapping from the vertices of G1 to the vertices of G2 defined as follows:
g(va) Uh(a) for each vertex vo of G and g(a,b)) (h()).A(b) for each vertex Va,6 of G₁.
It is straightforward to see that g is label-respecting homomorphism from GD to Gp. By Lemma A2 mapping 9 also a lespe-regg homomorphism from M(Gp) to M(GD') This, however, implies that h is also a homomorphism from T(D) to T(D'), as required.
A.3 PROOF OF THBBREM 10
Theorem 10. For each (Col, 8)-MGNN M and each dataset D, we have TM(D) = TPM
Proof. Consider arbitrary M, PM. and D as stated in the claim. Let L be the number of layers of M, and let & be the dimension of M. Since operator Tp,, captures each rule in PM by definition, we clearly have T. (D) S (D). For the converse, consider an arbitrary fact a E (D). We next construct a rule r for which we prove E PM and E TD).).
Let GD be the (Col, -graphh obtained from D by the transformation Definition 2 and let VD be the set of vertices of Gp. For each & E {0, ... L). let v be the vector labelling each v E Vn in the computation of (GD).. Moreover, let ys substitution that maps each variable to distinct constant. We next construct atom H, conjunction C, substitution from the variables in C to Dn) a set U of fresh vertices (i.e., vertices not occurring in GD) of the form Ua and ud,e for d and e constants from the image of μ., and mappings E + VD and Ma U + 2 for each c E Col. We also assign each vertex in U to level between 0 and L, and as the root vertex. In the rest of this proof, we use letters a and b for the constants in D, letters d and for the constants in the image of 14, possibly indexed letters v, w, and for the vertices in Vp, and possibly indexed letters u and for the vertices in U. Our construction is by induction from level down level 1, and we prove in parallel the following properties:
identify single vertex from U
PI. for each vertex of the form ua E U, for x: the variable such that p(x) = d, and for a = v(x), we have E(ua)= = Vai
P2. for each vertex of the form Udee U, for and y variables such that u(x) and μ(y) and for vzz) and b v(y), we have {(uae) = Va,b;
P3. conjunction C' satisfies vCC) S D; and
P4. if H is of the form A(z), conjunction C' is (3k, L) -i--ere---ike for otherwise, C' is of the form C2 A Bz,g A Cy. where C₂ and C, are (3k, L)-tree-like conjunctions for x and y, respectively, and Br,y y is a nonempty conjunction of atoms of the form S(x, y) or S(y,
15

---

Published as a conference paper at ICLR 2022
We initialise C' as the empty conjunction, and we set v, E, and each Mc for Col as the empty mappings. For the induction base, we consider the form of the atom a E (D) and proceed as follows; the base case also identifies the root vertex. Properties PI P4 clearly hold after these steps.
If a 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 = j(zz). We define v(x) = a; we define H Az)); we introduce vertex de of level L; we define E(ua) = Vaa and we make de the root vertex. Finally, we extend C' with atom ((x) for each B(a) E D. Note that C can be empty if D does not contain a fact such as B(a). However, Ua E VD implies that constant a must occur in D in a fact of the form S(a, b) or a(b, Thus, Ne(va) F 0 for E {ci, C2 c4): Since L 2 1, vertex Ud is processed in the inductive step below, which will extend C with an atom that contains variable x.
If a is of the form R(a, b). then VD contains vertices da,b and ub,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 vs. We introduce fresh variables and y, and we let d and be constants such that d = p(x)) and e = u(y). We define v(x) = a and v(y) = by we define H = R(x, y); we introduce vertices uda Wee Wd,e. and Ve,a of level L; we define E(ua) = Va E(ue) lbd E(ua,e) and ((ue.a) = Ub.ai and we make Unee the root vertex. Moreover, we extend C' with an atom S(x, 3) for each S(a,b) B(a)) E D. and an atom Bly) for each Bb)) E D; note that C' cannot be empty after this step. Finally, we define (u) Ne(E(u)) for each u E {Ud,es He.d) and colour E Col; note that Mo, (u), Mcs (u), and Mzy (u) are all singletons, and Mc, (u) O.
Va.b.
D, an atom S(y, 2) for each S(b, a) D, an atom (zx) for each
Next, we consider each level É with 1 é < L that has already been processed, and con- sider each vertex of the form ua of level l. Let x be the variable such that μ(z) = d, and let v(z); property PT ensures {(ua)= = Va- For each colour E {ci, C2 Ca), we choose smallest set Mo(ua) S (e(sa) such that, for each f' E ( and each i E {l...., kk. there exists a vertex w E Mo(us) satisfying
(5) Note that set Mc(ua) may not be unique, but any set satisfying (5) can be selected. There are at most l distinct values of (wf';: ); for each f', so set Meaua) contains at most kl elements. We also define Mc, (ua) = 0. We now consider each vertex V E Mc, (uz) U Me, (ua) U Mc, (uz). By Def- inition 2 such v is of the form va,b. 18 or Ub for be cn(D). depending on the set from which is drawn. Set VD clearly also contains vertices Ub.a and v; if v E Ma, (ua), and vertices Wa.s and us o E Mcz (uz). Moreover, if E Me, (ua), then Vp clearly contains ug. and (ua) S Ne, (va) ensures that D contains a fact of the form S(a, b) or S(b, a): thus, VD also contains Pa,b and Vb We introduce a fresh variable y, and we let be the constant such that e = j(w). We define vyy) = b; we introduce vertices Ue. ed and Ued of level e 1; and we define E(ue)
(w = max((s") )e s Ne(va)).
Ub. E(ua,e) = Va and E(ue.d) = Ub,a- Moreover, we extend C with an atom S(x, y) for each S(a, b) E D, an atom Sty. x) for each S(b, a) E D, and an atom Byy) for each ((b) E D. Finally, we define M.(u) = (E)) for each u E (ud,e; J and colour E Col; note that Me, (u), Mea (w). and Mey (u) are all sin- gletons, and Meg (1) = 0. Since each Ma(ua) with E {ci, C2, (2,,c4 contains at most kl vertices and we consider three colours, this step introduces at most 3kl fresh variables. Moreover, note that each fresh variable y occurs in C in an atom of the form S(z, v) or s(y,2). Finally, it should be clear that P1 14 hold after level é is processed.
This completes our inductive construction. At this point, either H A(x) and C is a nonempty (3ke, Li-tree-like conjunction for x, or H = R(z,v/ v) and C= C2 A Bay A Cy where C₂ and C, are (3k, -)-tree-like conjunctions for and y. respectively, and Bay is a nonempty conjunc- tion of atoms of the form S(x,y) y) or S(y,z). 2:). Thus, rule H + C' is of the form A(x) + Cn or R(x, y) +- Cz A Br.y A Cy- To complete the proof, we next show that this rule captured by TM. Then, Definition 9 ensures H +- C E Pmi together with Hv a and v(C) C D, we have a E Tp. (D), which proves our claim.
We use Proposition 7 to show that H + C is captured by TM. To this end, let Dc- = {aw a C), and let GD. be the (Col, -0grrph constructed using vertices in U obtained by applying the encoding from Definition to dataset Dc. Finally, let u' be the labelling associated with each vertex u E U in the computation of (MG ). The construction of C clearly ensures the following two properties for each colour E Col and each vertex u E U:
16

---

Published as a conference paper at ICLR 2022
Algorithm Rule extraction algorithm
Input: 771 natural number (max. num. atoms in the bodies of extracted rules)
.M MGNN
1: head to bodies :=
2: for S
3: for pred_ist E COMBINATIONS(1 do for body E BODIES (pred_itt) do if TREELIKE then input grrat == ENCODE(body)) cutput-graph M (iinntttggrappl heads == DECODE( graph) for head heads do
4:
5:
6:
7:
8:
9:
10:
new new_head, new new_body- == NORMALISE(head, body)
not not_iimleedd- true
12:
for body' E head to bodies[new head] do
if IMPLIES(body' new body) then not implied == false if nol. implied then ADD(head to bodies[new head), new body)
14:
15: extracted 0
16: for (head, bodies) E head to foaddtt.bbodie bodies do for body E bodies do (oD(extrracted.run head &- body) return exctracted_
17:
18:
R1. for each vertex Mc(u), there exists vertex & Ne(u) such that g(t) u; and
R2. for each vertex E Nu)u) in graph GD., we have g(t) Ne(E(u)).
We now show by the induction on that, for each s l < L and each vertex E whose level is at least f, we have uf = vf for {u)). For the base case l 0, we have the following possibilities.
Assume is of the form ug- Let be the variable such that d= μ(x),, and let u(x)). Property Pl ensures E(ua) = and the construction of C' ensures B(x) E C if and only if B(a) D; thus, u v holds.
Assume u is of the form ud,e. Let x and be variables such that u(x)) d and μ(v) and let v(x) and v(y). Property P2 ensures E(ud,e) = da,b, and the construction of C' ensures S(x, v) E C if and only if S(a,b) E thus, u²,-- v holds.
For the induction step. assume that the property holds for some f - 1. and consider an arbitrary ver- u e U whose level least É. Let {u). The induction assumption ensures u f- v Also, for each colour e E Col, our construction ensures that each vertex t E NN) is of level at least f-1, so the induction assumption ensures t- f-1 for = E()). Finally, property R2 ensures that each f used to compute u' is considered when computing v and property R1 ensures that
the maximal values e are also present the computation u Thus, u
holds.
To complete the proof, let be the root vertex, and let ((u). The above property ensures u² vL, and so cls(u²) = cls( ()s as well. Thus, we have μ(H) E TM(Dc), so Proposition allows us conclude that rule H +- C is captured by TM-
B OPTIMISED RULE EXTRACTION ALGORITHM
We now describe the rule extraction algorithm that we used obtain the results shown Table Section 4 Our algorithm takes input positive integer and MGNN M of dimension & and with L layers, and produces a set (3k, -)-tree-like rules with at most m body atoms that are captured by TM. The algorithm ensures that rule that is logically implied by any other individual rule included in the output. The algorithm's 's pseudocode is shown in Algorithm and it uses several auxiliary functions that will be introduced shortly.
17

---

Published as a conference paper at ICLR 2022
The algorithm initialises in line 1 empty mapping head_to_oodies that will be used to store pairs of the form (S(x, y), [C1, C2...., C.)) such that, for each C,. rule S(z, y) + C2 is (3k, L)- tree-like, has most body atoms, and is captured by TM. In each iteration i of the main loop (lines2H14) the algorithm produces rules with exactly body atoms. To this end, the algorithm calls COMBINATIONS()) in line 3 to produce all ordered combinations (with repetition) of predicates of length i. For each list of predicates predJist. the algorithm calls BODIES PODIES(pred. (pred in line to enumerate every possibly body over the predicates of pred list. For example, if pred list is [A, RJ.. where A is unary and R is binary, then RODIES(pred: list) returns
{ Axx) A R(x,)), A(x) A R(r,v), A(x) A R(y,a), A(x) R(y. v) }-
Next, the algorithm filters out bodies that not (3k: L)-ttre--iikk (line 5). calls ENCODE(body) to transform body into a (Col, 50graph by replacing each variable by a distinct constant and then applying the encoding from Definition 2 (line b applies M the resulting graph (line (7). and finally calls DECODE oraah) to reverse the encoding and obtain the set heads of candi- date head atoms (line 8). Thus, for each head heads, operator T'M captures head < body. For each candidate head E heads, the algorithm calls NORMALISE((hadd, body) to rewrite the can- didate rule head + body into new_head
new_body ensure that the head of each extracted rule always uses variables z and in this order (the body is rewritten accordingly). The algo- rithm then checks whether rule new head <- new body is implied by any rule previously stored in head to bodies (lines 13); if not, it records the new rule by adding conjunction new body new hhead) (line 14). Finally, the algorithm transforms the mapping head to bodies of heads to bodies into standard rules (lines 16 18
to the set headd_oo_oole
Algorithm satisfies the following property, which ensures its correctness.
Proposition B1. Let P be the result of applying Algorithm to an integer m N and (Col, 0)- MGNN M of dimension i and L layers.
1. Each rule r E P is (3k, L)-tree-like with at most m body atoms, and it is captured by TM--
2. For each (3k, L.)tree-likee rule r with at most m body atoms that is captured by TM, there exists a rule P that logically implies r.
Proof. The first claim is a direct consequence of Proposition 7 and the fact that Algorithm [ Tonly considers (3k, L)-tree-like rules with at most m atoms in the body. For the second claim, if r is a (3k, L)--tre-lliks rule with at most body atoms, then lines 2 of Algorithm Serritthmmhhee check whether this rule is captured by Ty: if that is the case, then lines 9 14 ensure that r is either in the output of the algorithm, or the algorithm's output contains rule that logically implies r.
C FULL RESULTS FOR THE RULE EXTRACTION EXPERIMENT
As explained in Section 4 for each benchmark, used Algorithm with 2 to extract the subset P S PM of all nonredundant rules with at most two body atoms, and then we applied P to the testing dataset S, and computed the usual classification metrics. Complete results of this experiment are shown in Table
18

---

Published as a conference paper at ICLR 2022
Benchmark
Precision
Recall
Accuracy
Fl Score
FB13K-237
vl
98.5
32.7
66.1
49.1
100.0
38.3
69.1
55.4
66.5
v4
99.6
32.7
66.3
49.3
NELL-999 L995
v1
96.4
80.0
88.5
87.4
v2
100.0
45.2
72.6
62.2
75.5
v4
99.7
53.9
76.9
70.0
vl
100.0
61.7
80.9
76.3
v2 100.0
60.3
80.2
75.2
100.0
64.0
100.0
57.6
78.8
73.1
Table 6: Classification metrics for the programs extracted using Algorithm with 2
19


Reviews:
[{"review_id": "Z4Jwpa2glCC", "reviewer": "Reviewer_Eofg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Clarity and technical correctness\nOverall, the paper is well written. I was able to follow the majority of the main paper, and the authors anticipated many of my technical questions and answered them with helpful examples and discussion (for instance, by walking through the intuitive interpretation of MGNNs, discussing how their method does not allow inferring transitivity relations, and describing how they set thresholds in their experiments).\n\nSome specific comments on clarity:\n- On page 5, it was difficult to follow the connection between the definition of \"monotonic under homomorphisms\" and the description of \"monotonic\" for constant-free programs; the paper simply states \"Monotonicity under homomorphisms combines both of these properties.\" without saying how. (Is it that we can always construct a homomorphism from a smaller dataset to a larger one, and thus properties of the smaller dataset must also hold in the larger one?) It would be nice to have a short discussion of why an operator that is monotonic under homomorphisms is always monotonic.\n- It would be useful to have a figure showing what the graph encoding of a dataset looks like.\n- In section 4, it says the MGNN models were trained with \"cross-entropy loss\". What was used as the output probability for this loss? Was it a logistic sigmoid applied to $\\lambda^L(v)$? This doesn't appear to be stated explicitly.\n\nI believe the theorems are likely to be true, but I found some of the proofs difficult to follow and did not check them in detail. Although the paper does a good job at giving intuition in the main paper, I felt like this intuition was missing in some of the proofs, in particular in Theorem 10. Some things I had trouble following for the proof of Theorem 10:\n- There are a huge number of definitions and new symbols being introduced, and I wasn't sure what those symbols were supposed to represent.\n- The induction argument is very difficult to follow, I think because it omits the dependence of various quantities on the induction variable $\\ell$ (I think), interleaves re-definition of values with proofs about them, and doesn't seem to have a well-stated goal (or at least I couldn't find it). As one point of confusion, after the end of the construction, it is stated that \"C is a nonempty (3k, L)-tree-like conjunction for x\" but I don't think this is ever explicitly proved, or even stated as something that should be proved; it seems like this should have been a property being maintained through the induction process?\n\n### Interpretation of the extracted \"explanations\"\n**(Edit: My original criticisms in this section are partially based on a flawed comparison to an alternative approach that I later realized did not make sense. I have added strikethrough for the parts I no longer believe to be correct.)**\n\nThe authors motivate their approach based on the quality of the explanations it extracts, and one of the stated strengths of their method is that the behavior of the MGNN can be fully characterized by a set of Datalog rules. The authors seem to be working under the assumption that Datalog rules are inherently better explanations than the original GNN. While this is plausible for hand-written Datalog rules, I'm not at all convinced the rules extracted by their method are particularly useful.\n\nFrom what I could understand, it seems like their construction is roughly as follows:\n- Constrain an MGNN such that it is monotonic under homomorphisms.\n- Enumerate *all possible rules* up to a given size (under some constraints), where the size is determined by the receptive field of the MGNN. For each rule, construct a subgraph representing the body of the rule, and see if the MGNN classifies the head of the rule as true or false.\n- ~~Collect *every subgraph* (or, equivalently, every rule) that the MGNN classifies as true and store them in a gigantic list.~~ **Edit: It's not possible to enumerate every possible subgraph of every possible dataset, since the MGNN may have arbitrarily many nodes in its receptive field. The authors describe a particular subset of rules, and concrete (sub)graphs that determine whether the GNN captures those rules. This subset is smaller than the set of all subgraphs (in particular it's finite). Additionally, the revised paper clarifies that they only include rules that are not subsumed by other rules, so every part of the extracted rules is actually relevant to the MGNN output.**\n- ~~Use this list (effectively a lookup table) as an explanation of the MGNN.~~ **Edit: This is an oversimplification on my part; given that they restrict the form of considered subgraphs and do subsumption checks, it's not just a lookup table.**\n\nThe argument of Theorem 10, as far as I could follow it, appears to be that if the MGNN deduces that a particular fact as true in a knowledge graph D, then the subgraph of D that the MGNN looked at could be represented as a rule, and so it would be in the gigantic list of all possible subgraphs that the MGNN classifies as true.\n\n~~While it is technically true that a gigantic list of all possible subgraphs that the MGNN classifies as true \"fully characterizes\" the set of graphs that the MGNN classifies as true, this doesn't really seem like a satisfactory explanation for why it does so. In fact, I think you could do a very similar thing for an ordinary GNN without monotonicity constraints: enumerate all possible subgraphs up to the receptive field of the GNN, and see which ones it classifies as true. But such an explanation seems mostly useless, since it boils down to a sort of tautology: \"the output was true because this is one of the graphs in the list of things classified as true\". Admittedly, it might be possible to simplify the MGNN explanation by only keeping the set of \"minimal subgraphs\" classified as true by the MGNN, and discarding any rule that is implied by another smaller rule (instead of using every extracted rule as their theorem assumes). It's also possible that the constraints on the rules lead to a smaller number of subgraphs (although it still seems like an exponentially large blowup). However, it's not obvious to me that this necessarily leads to set that is small enough to reason about.~~ **Edit: This comparison is flawed; it's not just a subgraph search, because there are infinitely many possible subgraphs (among the set of all datasets) and you can't enumerate all of them. The authors also do subsumption checks to ensure that the extracted rules are as simple as possible.**\n\nPerhaps the authors can provide additional information about how many rules are needed to actually fully characterize their models? On page 8 they say \"To reduce the search space, we considered only rules with at most two body atoms\", which might suggest that it is computationally infeasible to actually fully characterize the performance of MGNNs by extracting rules of this form.\n\nAdditionally, it's possible that I am misunderstanding the rule extraction mechanism; if so, please let me know.\n\n### Novelty and related work\nI am not well versed in the knowledge base completion literature, but as far as I know the idea of constraining a GNN to be monotonic under homomorphisms of knowledge bases, and thus to behave like Datalog rules, is novel. However, there has been a fair amount of related work on neural networks that are monotonic for other purposes (and which use similar techniques of nonnegative matrices and monotonic activation functions, among others). As a few examples:\n\n- You, Seungil, et al. \"Deep lattice networks and partial monotonic functions.\" Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017. https://arxiv.org/abs/1709.06680\n- Gupta, Maya, et al. \"Monotonic calibrated interpolated look-up tables.\" The Journal of Machine Learning Research 17.1 (2016): 3790-3836. https://arxiv.org/abs/1505.06378\n- Wehenkel, Antoine, and Gilles Louppe. \"Unconstrained monotonic neural networks.\" Advances in Neural Information Processing Systems 32 (2019): 1545-1555. https://arxiv.org/abs/1908.05164\n\nThe technical details of the rule extraction mechanism seem novel as well, but as I've stated above, I'm not particularly convinced that the rules it extracts are particularly meaningful, so it's difficult to tell if this is significant.\n\n### Empirical results\nThe authors evaluate their approach compared to two existing knowledge graph completion baselines. From the results, it seems like their method is not strictly better or worse than either of the baselines they present, and the different methods have a wide range of performance across the different datasets. One thing that would be useful would be to report standard deviation measures over different random seeds and training splits (specifically the 9:1 split used to construct the incomplete knowledge base and completion targets).\n\nThe authors note that the expressivity of MGNNs is limited by the power of \"(c,d)-tree-like\" rules, and that consequently they cannot express properties such as transitivity. They point to this as a possible reason for the low recall of their method on many of the datasets. They also include an experiment with an alternative test set where they ensure every output fact is at least structurally possible to be classified using their method, and show that recall improves; however, they don't report baseline performance for this test set so it's possible some of the improvement is just because this new test set is easier.\n\nThe authors also mention that they analyzed some of the rules by hand. I think it would be useful to include additional details of this, for instance by showing some of the extracted rules. I also wonder how close their extracted rules come to capturing the behavior of the MGNN; how many classifications of the MGNN can be explained using the extracted rules, and how many of them are left unexplained due to the truncation on the search method?\n\nI also notice that their method learns orders of magnitude more rules than AnyBURL, e.g. their method learns roughly 90,000 rules on FB15K-237 v4, whereas AnyBURL achieves higher accuracy with only 3,574 rules. It seems like fewer rules should be better for a good explanation, right?\n\n### Updated review (Nov 18)\n\nAfter discussion with the authors, I have raised my score from 5 to 6. I misunderstood a few aspects of the proposed method in my initial review, and also compared it to an alternative approach which I later realized was incorrect. The authors have also addressed many of my concerns regarding clarity and missing experimental details.\n\nI still feel that the paper could be improved by adding more of a discussion in the main paper of how to actually make use of the extracted rules to explain predictions made by a MGNN in practice. For instance, given the extracted set of rules, how do we formally verify properties of interest about the MGNN? Or, given a particular prediction of the MGNN in a particular dataset, how can we identify which facts the MGNN actually used to make its prediction? Can the full set of rules (e.g. those with more than two body atoms) be extracted quickly enough to make either of these practical? These details are especially important because the paper motivates the approach based on the trustworthiness/compliance/verifiability/fairness of the system. After discussion with the authors I believe doing this kind of verification and inspection should be possible in principle (although I have some concerns about runtime), but many of the details are buried in the appendix, and I think they should be given more of a focus.\n\n### Updated review (Nov 22)\n\nI have raised my score again from 6 to 8.\n- The authors have added additional information about how to use Datalog reasoning engines to explain the behavior of the MGNN using the extracted rules.\n- I am still unsure that it is feasible to extract every rule captured by the MGNN, which would make verification difficult. However, the authors have added new results showing that the subset of extracted rules with at most two body atoms still have fairly similar performance to the MGNN on their datasets. If verification is important, a user could then just use the extracted rules instead of the MGNN, allowing them to build a fully-explainable prediction system while trading off accuracy and computational cost (e.g. spending compute to extract more rules in exchange for a better, more-accurate approximation of the MGNN).\n\nA few more suggestions for improvement:\n- I would recommend briefly mentioning the computational constraints on the current rule-extraction algorithm in the introduction, to make it clear that there is a difference between the theoretical and practical ability to extract rules. Specifically, after the sentence \"we can explicate the rules that are implicitly captured by the model and use them to fully explain each credit recommendation\", I'd suggest adding another sentence stating that the existing algorithm for extracting rules may only explain a subset of predictions of the original MGNN (and, optionally, that the extracted rules could just be used directly if it is critical to be able to explain every prediction).\n- In section 4 \"Rule Extraction\" after \"we applied $T_P$ to the test dataset of each benchmark\", it would be useful to explicitly refer to Table 6 in the appendix, so that readers know where to find that information.\n- I think it would be important to include some results for AnyBURL and DRUM in Table 6 as well, by extracting a set of rules from them and then evaluating those rules. I am aware neither AnyBURL or DRUM has any theoretical guarantees about extracted rules, but as far as I understand it each method does produce some rules with thresholds, so it seems fair to take a subset of their rules (with threshold similarly tuned for accuracy). This would help answer the question of how much the MGNN adds over the baselines if you require that every prediction be explainable by rules.", "summary_of_the_paper": "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.", "summary_of_the_review": "The main paper is well written and I think it is technically sound (although I found the proofs difficult to follow and did not fully verify them). ~~However, I'm not convinced that the rules they extract really count as \"explanations\": as far as I can tell the extracted rule sets can be extremely complex and may not have any more explanatory power than a gigantic lookup table~~. Empirical results are also not particularly strong; their system achieves comparable performance to other methods but seems to require orders of magnitude more rules and also has fundamental limits to its expressivity.\n\n**Update (Nov 18):** After discussion with the authors, I have raised my score from 5 to 6; some of my concerns in my initial review were based on a misunderstanding of the proposed method, and the authors have addressed many of my comments regarding clarity and experimental details in the revised paper. I still feel that the paper could be improved by describing in more detail how to use the extracted rules to explain predictions, since this seems to be the main way their approach differs from prior work.\n\n**Update (Nov 22):** I have raised my score again from 6 to 8. The authors have added more discussion of how Datalog engines can use the extracted rules and how accurately the truncated rule-extraction algorithm approximates the MGNN. Since the rule-based approximation performs fairly well (and could be improved by running the extraction algorithm for a longer time), it could be used directly for making predictions in domains where explaining every prediction is critical, and then standard Datalog tools could be used to explain all predictions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IX19cIN9ob", "reviewer": "Reviewer_AzED", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed method is very interesting since it provides a theoretically motivated model that is able to learn tasks on knowledge graphs, having the possibility to extract explanations. The MGNN just requires to apply simple constraints on the original GNN architecture to guarantee monotonicity in the implemented function (positive weights, monotonic activation functions, use of the max as aggregation operator for neighbor nodes). The most valuable property is the possibility to derive the datalog rules that the model implements, as guaranteed by the provided theoretical results.\n\nDespite being generally a good quality contribution, in my own opinion, the paper suffers from some weaknesses.\n\n- Some parts are quite hard to follow. Even if the main ideas can be understood and are explained with sufficient clarity, the more theoretical part is quite hard to follow (in particular, Section 3, that introduces the main theoretical results on the extraction of equivalent datalog rules from a trained MGNN).  Some concepts would need a more detailed description, with examples (figures, algorithms) to provide a mode immediate understanding. For instance, the extraction process is supported by theorem 8 but it requires the enumeration of all rules. In the experimental section it is described that some constraints are imposed on the search strategy to keep the complexity low. A schema of the generic procedure, that can be implemented for the rule extraction, would have given a more compact and clear view of the proposed method and its potential limitation with respect to complexity. Other important concepts are also difficult to grasp without simple practical examples. For instance, primal graphs and in particular (c,d)-tree-like structures for variables are important concepts to undestand the limitations of the proposed architecture (the two provided examples are for instance useful). If you look at defintion 9 and what follows (I guess that the two following paragraphs are not part of the definition and should not be in italics), many imporant concepts are introduced  that involve the rule structure and the representational power of the MGNN model. This is just in few lines... (btw, what is the dimension k? The numer of internal units in the GNN?)\n- The limitations of the representational power of the MGNN model should be discussed more deeply. Theorem 10 is claimed to provide results on the expressiveness of the model, but beside the proof in the appendix and a few  lines after definition 9, this aspect is not detailed to make the reader understand the actual limitations in practice. The evaluation section reports a few rules that are extracted, but they are quite simple and limited to symmetry, inverse relations and subsumption. It would be useful to provide more examples of extracted rules. \n- The extaction process requires to enumerate all rules and to check them on the trained model by applying proposition 7. In the evaluation some restrictions on the considered rules are applied (rules with at most two body atoms). The issues about complexity and the possible solutions should be clearly pointed out.\n- In the evaluation section there are not enough details on the used architecture (f.i. number of layers, activation function, etc). As far as I understand, the results are obtained on only one run for each dataset (dataset split/weight initialization). It would be useful to show how the architecture affects the results and how the training is stable (however this is not a major weakness since the paper contribution may be considered theoretical).\n\nMinor remarks.\n- When describing the MGNN model (definition 3) the notation of the dimension may be confusing because of the stacking of the layers. Is {\\bf b}^{\\ell} of dimesion n^\\ell o m^\\ell? \n- Does the encoding of the KG consider only the pairs of constants found in the binary predicates in KG? In case, may it happen that pairs not present in the graph are needed? \n- As far as I understand, all predicates (binary/unary) are considered in the vector attached to each node being it a single constant or a pair of constants. Is this just a choice to simplify the notation in the theoretical part or is it also used in the implementation? (I did not check the code).", "summary_of_the_paper": "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.\nThe proposed approach is evaluated on KG benchmarks, showing promising results when compared to other 2 state of the art methods.", "summary_of_the_review": "The paper provides an interesting model to learn tasks on knowledge graphs. However, there are some aspects (limitations of the model and of the extraction procedure, settings of the evaluation) that would need more details and/or discussion. Finally the are some parts that are dense in concepts/theory and are hard to follow (more examples/schemes would be useful to improve readability). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9c6T6Mls-P0", "reviewer": "Reviewer_PNwA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n* It first transforms the original knowledge graph into a colored graph where each vertex is labeled by a feature vector and represents the facts of the corresponding entity or entity pairs. It further connects the vertices that refer to the common entities. Such a transformation is a bit inspiring, and it is naturally suitable for inductive settings.\n\n* The authors make it clear that there is an equivalent set of rules for any MGNN, and that both can produce the same facts. Hence, we can use rules to understand the predictions made by MGNNs.\n\nCons:\n\n* The approach appears to be straightforward. I discovered that Equation 1 is sufficient to describe the model. Furthermore, Section 3, which is two pages long, only states that there is a set of rules that can be used to derive the same facts as MGNNs. The authors should simplify this section and add some details to the appendix, in my opinion.\n\n* It appears that rule extraction is a searching procedure that requires a lot of space and time. This could limit its use in larger datasets. Some baselines, such as DRUM and AnyBURL, can also capture rules. Although the exact relationship between the predictions and the results of applying the rules to these methods is unknown, the generated rules can still assist us in understanding their predictions to some extent. Table 2 also shows that these baselines can produce competitive results. Hence, I think the advantage of the proposed approach is not obvious.\n\nQuestions and Suggestions:\n\n* The authors should add some citations regarding the transformation process into a colored graph, as there exists some work that adopts similar transformations.\n\n* Theorem 10 describes the expressiveness limitation of MGNNs, i.e., MGNNs can only capture some rules. I want to know whether some baselines (e.g., DRUM and AnyBURL) also have this limitation, as they can also capture rules.\n\n* The authors split the testing dataset and re-evaluated their approach in Table 3. I think it is better to provide the results of baselines in this setting.\n\n* In Section 3, the authors said that \"we can enumerate all such rules, apply Proposition 7 to each rule, and keep only the rules that pass this check\". It seems that the rule extraction procedure is time-consuming. Can the authors provide the corresponding time cost? I also notice that the last column of Table 2 records the training time. I want to know whether the training time includes the time cost of rule extraction.\n\n* In Section 4, the authors said that \"to reduce the search space, we considered only rules with at most two body atoms\". I think the extracted rules can not exactly describe the predictions made by MGNNs, as the authors only consider a part of the rules.\n\n* From Table 4 and 5, I notice that $T_M$ captures much more rules than AnyBURL on FB15K-237, and fewer rules on WN18RR. Can the authors explain the phenomenon? Moreover, the fourth column in Table 5 shows the number of AnyBURL rules captured by $T_M$ on $S_I$. Can the authors provide the number of rules captured by AnyBURL on $S_I$? It will help readers see the proportions of rules generated by AnyBURL and $T_M$.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The idea of the paper is interesting but the technical contributions are not very significant and the advantage of the proposed approach is not obvious.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1fYgVqubPen", "reviewer": "Reviewer_EWub", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- This paper studies how to improve the interpretability of GNN-based predictions, which is an important research direction.\n- The authors provide a detailed theoretical analysis of the model’s ability to \nexplain the GNN-based predictions by logical rules.\n\nWeaknesses:\n\nIn terms of the experiments, my concerns are as follows.\n- This proposed method is based on GNN. However, the comparison with GNN-based methods is missing. The authors may want to compare their approach with the state-of-the-art GNN-based ones, such as GraIL[1] .\n- MGNN does not outperform some existing models like DRUM and AnyBURL on several benchmarks.\n- The authors may want to provide some case studies to show how MGNN ensures that the predictions can be explained by logical rules, as what DRUM [2] does in Section 5.3.\n\nIn terms of the proposed model, MGNN assigns a feature vector to each link, which significantly increases the computational cost. This makes the model difficult to apply to large-scale knowledge graphs.\n\nIn terms of the writing, my concerns are as follows. \n- The necessary visual illustrations of the idea and the model architecture are missing, making this paper hard to follow. The authors may want to provide figures in Sections 2 and 3.\n- The authors may want to specify some important details.\n    - In Section 2, the authors say that the result of MGNN can be decoded to an output knowledge graph by \"inverting the encoder\". However, the decoding procedure is unclear. \n    - The definitions of $c_3$ and $c_4$ in Paragraph 4 are missing.\n    - Some of the statements are confusing. For example, in Section 2, Definition 3 states that $\\sigma$ is a mapping from $\\mathbb{R}$ to $\\mathbb{R}^+$, while the input of $\\sigma$ in Eq. (1) belongs to $\\mathbb{R}^d, d\\geq 1$. Besides, each vertex of the result $M(G)$ is labelled by a boolean number, while in Definition 4 the label is a vector.\n\n[1] Komal K Teru, Etienne Denis, and William L Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, 2020.\n\n[2] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs. In NeurIPS, 2019. \n", "summary_of_the_paper": "The authors propose a Monotonic Graph Neural Network transformation (MGNN) for inductive knowledge graph completion, which allows the predictions to be explained symbolically by logical rules. ", "summary_of_the_review": "This paper proposes a GNN-based method, named MGNN, which allows the predictions to be explained symbolically as logical reference to improve their interpretability. However, MGNN does not outperform existing approaches on some benchmarks, and it may be difficult to apply to large-scale knowledge graphs. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes monotonic graph neural networks (MGNNs) for the transformation of knowledge graphs. Specifically, MGNNs transform a knowledge graph into a colored graph where each node is represented by a numeric feature vector and each edge encodes the node relationship with different colors. The authors provide theoretical analysis showing that monotonic constraint can enable the model to derive logical inference rules in Datalog, and thus the trained model is explainable. 


The authors addressed most of the concerns raised by the reviewers, such as motivation, runtime, and comparison with existing baselines. Three of the four reviewers are positive (with the scores of 6 or above) towards acceptance after rebuttal discussions, and the remaining reviewer gives a score of 5 (below acceptance threshold) thinks that this work still lacks novelty, but he/she is not against acceptance if other reviewers choose so. Considering this work makes a good exploration on explainable graph neural networks, which is an interesting and important research direction, we recommend for acceptance. We thank the reviewers and the authors for their active discussion.
Decision: Accept (Poster)