A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs
Authors: Xingyue Huang
Miguel Romero Orth
Ismail Ilkan Ceylan
Pablo Barcelo
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
knowledge graphs
expressivity
logical characterization
TL;DR: We provide a characterisation of the expressive power of a wide class of graph neural networks for link prediction.

Abstract: Graph neural networks are prominent models for representation learning over graph-structured data. While the capabilities and limitations of these models are well-understood for simple graphs, our understanding remains incomplete in the context of knowledge graphs. Our goal is to provide a systematic understanding of the landscape of graph neural networks for knowledge graphs pertaining to the prominent task of link prediction. Our analysis entails a unifying perspective on seemingly unrelated models and unlocks a series of other models. The expressive power of various models is characterized via a corresponding relational Weisfeiler-Leman algorithm. 
This analysis is extended to provide a precise logical characterization of the class of functions captured by a class of graph neural networks. The theoretical findings presented in this paper explain the benefits of some widely employed practical design choices, which are validated empirically.

A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs
Xingyue Huang
Miguel Romero
Department of Computer Science University of Oxford Oxford, UK.
Department of Computer Science Universidad Católica de Chile & CENIA Chile mgromero@uc.cm
xingyue.. huw.guus..s.... ox ac
ismail ilkan Ceylan
Pablo Barceló
Department of Computer Science
Inst. for Math. and Comp. Eng. Universidad Católica de Chile & IMFD Chile & CENIA Chile pbarcelo@uc. cl
University of Oxford Oxford, UK.
momaail.cylaneen ox. ac uk
Abstract
Graph neural networks are prominent models for representation learning over graph-structured data. While the capabilities and limitations of these models are well-understood for simple graphs, our understanding remains incomplete in the context of knowledge graphs. Our goal is provide a systematic understanding of the landscape of graph neural networks for knowledge graphs pertaining to the prominent task of link prediction. Our analysis entails a unifying perspec- tive seemingly unrelated models and unlocks a series of other models. The expressive power of various models characterized via corresponding relational Weisseiler-Leean algorithm. This analysis is extended to provide precise logical characterization of the class of functions captured by class of graph neural net- works. The theoretical findings presented in this paper explain the benefits of some widely employed practical design choices, which are validated empirically.
Introduction
Graph neural networks (GNNs) 12] are prominent models for representation learning over graph- structured data, where the idea is to iteratively compute vector representations of nodes of an input graph through series of invariant (resp.. equivariant) transformations. While the landscape of GNNs is overwhelmingly rich, the vast majority of such models are instances of message passing neural networks [II which are well-studied, leading theoretical understanding of their capabilities and limitations 34 21]. In turn, our understanding is rather limited for GNN models dedicated to learning over knowledge graphs, which are applied in a wide range of domains.
To make our context precise, we first consider an extension of message passing neural networks with relation-specific message functions, which call relational message passing neural networks. Two prominent examples this framework are RGCN 288 and CompGCN (32] and their expressive
power has recently been characterized through dedicated relational Weisfeiler-Leman test 4
While offering principled means for learning over knowledge graphs, the standard relational message passing framework is tailored for computing unary node representations and therefore models of this class are better suited for node-level tasks (e.g.. node/entity classification). Actually, it well-known that even good node-level representation might not necessarily induce good edge representation,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

hindering the applicability of such models for the crucial task of link prediction [39] This has led to the design of GNN architectures specifically tailored for link prediction over knowledge graphs for which our understanding remains limited.
30
40
33
18
The goal of this paper is to offer theory of the capabilities and limitations of a class of relational GNN architectures which compute pairwise node representations to be utilized for link prediction. Although most such architectures can be seen to be subsumed by higher-order message passing neural networks that compute pairwise representations on nodes, the inherently quadratic behavior of the latter justifies local approximations which align better with models used in practice. Of particular interest to us is Neural Bellman-Food Networks (NBFNets) [40], which define a message passing approach inspired by the Bellman- FFrd algorithm. We argue in salient detail that the crucial insight of this approach is in leveraging the idea of computing conditional pairwise-node representations, which leads to more expressive models at a more reasonable computational cost, given its local nature.
Building on this fundamental aspect, we define conditional message passing neural networks, which extend traditional ones by conditional message passing paradigm: every node representation is conditional on a source node and query relation, which allows for computing pairwise node representations. This framework strictly contains NBFNets and allows for systematic treatment of various other models. Through careful study of this framework, we can explain the conceptual differences between different models along with their respective expressive power.
Our contributions can be summarized as follows:
We introduce conditional message passing neural networks which encode representations of nodes v conditioned on a (source) node u and query relation q. yielding pairwise node representations. We discuss the model design space, including a discussion different initialization regimes and the presence of global readout functions in each layer of the network.
We define relational Weisfeiler-Lemma algorithm (building on similar works such as Barceló et al. 4., and prove that conditional message passing neural networks can match the expressive power of this algorithm. This study reveals interesting insights about NBFNets, suggesting that their strong empirical performance is precisely due to the expressive power, which can be matched by other instances of this framework.
Viewing conditional message passing neural networks (with without global readouts) clas- sifiers over pairs of nodes, we give logical characterizations of their expressive power based on formulas definable in some binary variants of graded modal logic [8] 19]. This provides us with a
declarative and well-studied formal counterpart of C-MPNNs.
We conduct an experimental analysis to verify the impact of various model choices, particularly pertaining to initialization, history, message computation, and global readout functions. We also conduct both inductive and transductive experiments on various real-world datasets, empirically validating our theoretical findings.
2 Related work and motivation
Early GNNs for knowledge graphs are relational variations of message passing neural networks. A prototypical example is the RGCN architecture (28). which extends graph convolutional net- works (GCNs) [77 with -eltiin--peecfii message functions. CompGCN [32 and several other architectures 37 follow this line of work with differences in their aggregate, update, and message functions. These architectures encode unary node representations and typically rely on a pairwise decoder function to predict the likelihood of a link which is known to be suboptimal for link pre- diction 33.. There is a good understanding of the expressive power of these architectures [4] we generalize these results in Section since they form the basis for the rest of our results.
different approach is given for single-relational graphs by SEAL (38, where the idea is to encode (labeled) subgraphs (instead of nodes). GralL [30] extends this idea to knowledge graphs, and one important virtue of these models is that they are inductive even if there are no node features in the input graph. The idea is to use form of labeling trick [39 based on pairwise shortest path distances in sampled subgraphs, but these architectures suffer from scalability issues. More recent inductive architectures integrate ideas from earlier path-based link prediction approaches 24 14
into modern GNN architectures, resulting in proposals such as PathCon [33, Geodesic GNNs 18
and NBFNets 44).. Our study is very closely related to NBFNets which is inspired by the generalized

---

version of the Bellman-Fort algorithm for finding shortest paths. These architectures aggregate over relational paths by keeping track of conditional pairwise-nodk representations. While NBFNets can be intuitively seen as the neural counterpart of the generalized Bellman-Ford algorithm, they do not provably align with this algorithm since the "semiring assumption" invalidated through the use of non-linearities (which is explicit in Zhu et al. 40].. This leaves open many questions regarding the capabilities and limitations of these architectures.
In this paper, we argue that the key insight behind architectures such as NBFNets is in locally computing pairwise representations through conditioning on source node, and this has roots in earlier works, such as ID-GNNs [36]. To formally study this, we introduce conditional message
passing neural networks as strict generalization of NBFNets [40] and related models such as NeuralLP [35.. or DRUM [25] Through this abstraction, we theoretically study the properties of a large class of models in relation local variants of relational Weisfeiler-Leman algorithms.
Broadly, our study can be seen as the relational counterpart of the expressiveness studies conducted for GNNs 34 21 [ particularly related to higher-order GNNs [21], which align with higher-order dimensional variants of the WL test. Our characterization relies on local versions of higher-order WL tests [22], albeit not in a relational context. This can be seen as a continuation and generalization of the results given for relational message passing neural networks 4 to a broader class of models.
3 Background
3.1 Knowledge graphs and invariants
Knowledge graphs. A knowledge graph is tuple G (V, R)., where V is set of nodes, E "C R x V x is a set of labeled edges, or facts, R is the set of relation types and e: V + D is node coloring. When D = IRd, we also say that e is a d-dimensional feature map, and typically use instead of c. We write r(u, r) to denote a labeled edge, or a fact, where r E R and u, v E V. The neighborhood of a node E V relative to relation r E R is defined as NN, := {u r(u, v) E E}.
Graph invariants. We define k-ary graph invariants following the terminology of Grohe [3], for which we first define isomorphism over knowledge graphs. An isomorphism from knowledge graph G = (V. E, R, e) to a knowledge graph G' (V','', R, c') is a bijection f V + ~V' such (f))) for all V, and r(u, v) E E if and only if ((f f())
E', for all r E R and u. v E V. A 0-ary graph invariant is a function & defined on knowledge graphs such that ((G) = {(')) for all isomorphic knowledge graphs G and G'. For k 2 a k-ary graph invariant is a function & that associates with each knowledge graph G = (V, E, R, c) a function E(G) defined on v such that for all knowledge graphs G and G¹, all isomorphisms f from G to G', and all k-tuples If k 1, this defines node invariant, or unary invariant, and if I- = 2, this defines a binary invariant, which is central to our study.
that c(v)
of nodes V² it holds that (v) = {(G')((())
Refinements. A function ((G) Vk + D refines function ('(G) V + D, denoted as = S(G) 3 E'(G). if for all v, v' E V* (v)) = (e)) implies =[ (z)). We call such functions equivalent. denoted as E(G) = (') if { = ('G)) and < E k-ary graph invariant & refines k-ary graph invariant g', if ((G) refines (G) for all knowledge graphs G.
3.2 Relational message passing neural networks
We introduce relational message passing neural networks (R-MPNNs), which encompass several known models such as RGCN (8) and CompGCN (2) The idea is to iteratively update the feature of node based on the different relation types r E R and the features of the corresponding neighbors in (v). In our most general model we also allow readout functions, that allow further updates to the feature of by aggregating over the features of all nodes in the graph.
Let G = (V. F, R, æx) be a knowledge graph, where æ is a feature map. An R-MPNN computes sequence of feature maps (t), V + Rd(()) for 2 0. For simplicity, we write (a instead of (t) (v). For each node v E V, the representations (.) are iteratively computed as:
(0))) Z.
h ((+1) = UPD h (f()), AGG( Of (hG w E (.G()), E RR. READ(Sh!) EVB),
3

---

where UPD, AGG, ReAd, and M are differentiable update, aggregation, global readout, and relation-specific message functions, respectively, and : IN + always non-decreasing and satisfies ((L) S t. An R-MPNN has a fixed number of layers 7 2 0, and then, the final node representations are given by the map (T) V - Rd((T)
history function which is
The use of readout component in message passing is well-known [5] but its effect is not well- explored in a relational context. It is of interest to us since it has been shown that standard GNNs can capture larger class of functions with global readout 3
An R-MPNN can be viewed as an encoder function enc that associates with each knowledge graph G' function enc(G) V - Rd(T), which defines a node invariant corresponding to hT) The final representations can be used for node-level predictions. For link-level tasks, we use a binary decoder dec, Rd(T) x Rd(TT) + R, which produces a score for the likelihood of the fact q(u, v), for q E R.
In Appendix | provide useful characterization of the expressive power of R-MPNNs in terms of a relational variant of the Weisfeiler- Lemmailer-Leman test [4] This characterization is essential for the rest of the results that present in the paper.
4 Conditional message passing neural networks
R-MPNNs have serious limitations for the task of link prediction 33 which has led to several proposals that compute pairwise representations directly. In contrast the case of R-MPNNs, our understanding of these architectures is limited. In this section, we introduce the framework of conditional MPNNs that offers a natural framework for the systematic study of these architectures.
Let G = (V,E, R, x) be a knowledge graph, where æ is a feature map. A conditional message passing neural network (C-MPNN) iteratively computes pairwise representations, relative fixed query E R and fixed node u E V, as follows:
h (0)
INIT(U, v.
r/u.g
(++1) = Up (()) elu.g
vlu.g* AGG @f (MSG, (h) ( z,y1 I w E NN,(),, E RB), READ (1) w/u.q w E VH),
where INIT, UPD, AGG, READ, and MsG, are differentiable initialization, update, aggregation, global readout, and relation-specific message functions, respectively, and f is the history function. We (t) (u, v) h //ju.q' and denote 2y to be learnable denote by fgy V x V + Rd(t) the function hg
vector representing the query q R. A C-MPNN has a fixed number of layers T 2 O, and the final pair representations are given by hg (T), We sometimes write C-MPNNs without global readout to refer the class of models which do not use readout component.
Intuitively, C-MPNNs condition on a source node u in order to compute representations of (u, v) for all target nodes v. To further explain, we show visualization of C-MPNNs and R-MPNNs in Figure to demonstrate the differences the forward pass. Contrary to the R-MPNN model where we carry out relational message passing first and rely on the binary decoder to compute query fact q(u, v), the C-MPNN model first initializes all node representations with the zero vector except the representation of the node which is assigned vector with non-zero entry. Following the initialization, we carry out relational message passing and decode the hidden state of the target node to obtain the output, which yields the representation of u conditioned on u.
Observe that C-MPNNs compute binary invariants, provided that the initialization INIT a binary in- variant. To ensure that the resulting model computes pairwise representations, we require INIT(U, v, q) to be nontrivial function in the sense that it needs to satisfy target node distinguishability: for all q E R and + V. it holds that INIT(U, u, g) + INIT(U, v. q).
This is very closely related the Labeling Trick proposed by Zhang et al. [39] which is initializa- tion method aiming to differentiate a set {u, v} of target nodes from the remaining nodes in a graph. However, the Labeling Trick only applies when both the source u and target nodes u are labeled. Recent state-of- the-ttrrrrt models such as ID-GNN (36) and NBFNet [40] utilize a similar method, but only with the source node u labeled differently in initialization. Our definition captures precisely this, and we offer a theoretical analysis of the capabilities of the aforementioned architectures accordingly.
'The typical choice is f(t) but other options are considered in the literature, as we discuss later.

---

Encoder
Decoder
G
ha
h
dec,
-
Message Passing
R-MPNN
2g
dec
- R
Input Graph
INIT(U, U.
Message Passing
C-MPNN
Figure Visualization of R-MPNN and C-MPNN. The dashed arrow the target query q(u, v). Arrow colors indicate distinct relation types, while node colors indicate varying hidden states. R- MPNN considers a unary encoder and relies on a binary decoder, while C-MPNN first initializes binary representation based on the target query quu, v), and then uses unary decoder.
One alternative to directly learn pairwise representations following similar ideas to those of higher- order GNNs, but these algorithms are not scalable. Architectures such NBFNets represent trade-off' between computational complexity and expressivity. The advantage of learning conditional representations he be able learn such representations in parallel for all V. amortizing the computational overhead; see Zhu et al. 440] for a discussion. We have also carried out a runtime analysis comparison among different classes of models in Appendix B
4.1 Design space and basic model architectures
To specify C-MPNN architecture, we need to specify the functions INIT, AGG, MsG,, f. and READ. In the following, consider three initialization functions {INIT², INIT², INIT"), two aggrega- tion functions {sum, PNAJ, three message functions (Msg). MsG",, MsG two history functions (S(1) = L, f(t) 0}. and either sum global readout or no readout term.
Initialization. We consider the following natural variants for initialization: INIT' (u, v, v) 1u=. * 1, INIT (u, q) 1u=v * Zg. INIT where represents element-wise multiplication, the function (w) is the indicator function which returns the all-ones vector 1 if u = e and the all-zeros vector O otherwise with corresponding size.
(Zg + ew),
Clearly, both INIT' and INIT? satisfy target node distinguishability assumption if we assume 2g has no zero entry, where INIT2, in addition, allows query-specific initialization to be considered. Suppose we further relax the condition to be target node distinguissaaiiity in expectation. Then, INIT can also distinguish between each conditioned node given the same query vector zy by adding an error vector e, sampled from ((0, 1) to the conditioned node's 's initialization.
Aggregation. We consider sum aggregation and Principal Neighborhood Aggregation (PNA)
Message. We consider the following variations of message functions:
(s (h 2n) h"d (t)
((() Zgr
wluug
(1) m/ugg Zy) h mnjun ((9)
(h w/ 2g) w!()) h (1)
(t)
w//ugg
where ( are relation-specific transformations. Msat computes a query-dependent message,
whereas M and MsG; are analogous to message functions of CompGCN and RGCN, respectively.
5

---

History. In addition, we can set f, which intuitively is the function that determines the history of node embeddings to be considered. By setting f(t) we obtain standard message- nessage-passing algorithm where the update function considers the representation of the node in the previous iteration. We can alternatively set ft) 0, in which case we obtain (a generalization of) NBFNets.
Readout. We consider standard readout which sums the representations and applies a linear transformation on the resulting representations. Alternatively, we consider the special case, where we omit this component (we discuss a dedicated readout operation in our empirical analysis later).
A simple architecture. Consider basic C-MPNN architecture with global readout, which, for query relation q E R and a fixed node u, updates the representations as:
(0) "//u,g = uuuv * 2q
h ((+1) σ (/(') (n plu,g + Σ PE (EN
Σ
(s i|l.gg" xn)) + W
Σ h
wEV
where ( w are linear transformations followed by non-linearity a.
5 Characterizing the expressive power
5.1 A relational Weisfeller-Leman characterization
To analyze the expressive power of C-MPNNs, we introduce the relational asymmetric local 2-WI. denoted by rawlz- this case, we work with knowledge graphs of the form = (V, F., R, e, n) where 1) V x V + D is pairwise coloring. We say that 1) satisfies target node distinguishubility ry(u, u) # (u,, v)) for all u & E V. The notions of isomorphism and invariants extend this context in natural way. For each 2 O, update the coloring
!awl (u, v) nu,,)))
rawl
(awl(++)) (++1) (u, = T (rawl,)) (u, v), (rawl)) (u, w),r) w E N,()), R)B),
where injectively maps the above pair to unique color, which has not been used in previous iterations. Observe that rawl,)) defines binary invariant, for all t 2 0.
The test is asymmetric: given pair (u, v), we only look at neighbors of (u, v) obtained by changing the second coordinate of the pair. In contrast, usual versions of (local) k-WL are symmetric as neighbors may change any coordinate. Interestingly, this test characterizes the power of C-MPNNs in terms of distinguishing pairs of nodes.
Theorem 5.1. Let = (V, E, x. 1) be a knowledge graph, where x is a feature map and nj is pairwise coloring satisfying larget node distinguishabiltyy. Let q E R be any query relation. Then:
1. For all C-MPNNs with T layers and initializations INIT with INIT = 1), and 0 t S. we have r 3 h
2. For all T and history function f. there is C-MPNN without global readout with T' layers and history function I such that for all < 1. < T, we have rawll"" (t) = =h4]
The idea of the proof is as follows: we first show a correspondent characterization of the expressive power of R-MPNNs in terms of relational variant of the WL test (Theorem A.I.. This result generalizes results from Barceló et al. 44. We then apply a reduction from C-MPNNs to R-MPNNs, that is, we carefully build auxiliary knowledge graph (encoding the pairs of nodes of the original knowledge graph) to transfer our R-MPNN characterization to our sought C-MPNN characterization.
Note that the lower bound (item (2)) holds even for the basic model of C-MPNNs (without global readout) and the three proposed message functions from Section 4.1, The expressive power of C- MPNNs is independent of the history function as in any case it is matched by rawl2. This suggests that the difference between traditional message passing models using functions (() = and path-based models (such as NBFNets [40)) using f(t) 0 is not relevant from theoretical point of view.

---

5.2 Logical characterization
We now turn to the problem of which binary classifiers can be expressed as C-MPNNs. That is, we look at C-MPNNs that classify each pair of nodes in knowledge graph as true or false. Following Barceló al. [3] study logical binary classifiers, i..., those that can be defined in the formalism of first-order logic (FO). Briefly, a first-order formula Φ(x, y) with two free variables æ, y defines logical binary classifier that assigns value true to the pair (u, v) of nodes in knowledge graph G whenever G = p(u, v), i.e., e holds in G when x is interpreted as u and as v. A logical classifier 6(x y) is captured by C-MPNN A if over every knowledge graph G the pairs (u, v) of nodes that are classified as true by & and A are the same.
A natural problem then is to understand what are the logical classifiers captured by C-MPNNs. Fix a set of relation types R and set of pair colors C. We consider knowledge graphs of the form G = (V, F, R,y)) where 1) is mapping assigning colors from C. to pairs of nodes from V. In this context, FO formulas can refer to the different relation types in It and the different pair colors in Our first characterization is established in terms of simple fragment of FO, which we call rFO ent= and is inductively defined as follows: First, a(x, y) for C, is in rFO Second, y( y) and <b(2, y) are in rFO cnt. N 2 is a positive integer, and r R, then the formulas
px((, v), p(z, A (), M 2 (vp(x, 2) A (22
and 32 (p(u, 2) r(2, 8)) holds in G if e has least N incoming edges labeled r R from nodes w for which ppu, w) holds in G. We use the acronym iFO as this logic corresponds to a restriction of FO with three variables and counting. We can show the following result which is the first of its kind in the context of knowledge graphs:
are also in rFO ent. Intuitively, a(u, v) holds in G = (V) (f,
Theorem 5.2. A logical binary classifier is captured by C-MPNNs without global readout if and only if it can be expressed in rFO ent.
The idea of the proof is show logical characterization for R-MPNNs (without global readout) in terms of a variant of graded modal logic called rFO (Theorem A.11), which generalizes results from Barceló et al. [3] to the case of multiple relations. Then, as in the case of TheoremB.1 we apply reduction from C-MPNNs to R-MPNNs (without global readout) using an auxiliary knowledge graph and a useful translation between the logics rFO
ent and rFO ent-
Interestingly, arbitrary C-MPNNs (with global readout) are strictly more powerful than C-MPNNs without global readout in capturing logical binary classifiers: they can at least capture a strict extension of rFO cat denoted by erFO
Theorem 5.3. Each logical binary classifier expressible in er 3 cnt. can be captured by C-MPNN.
Intuitively speaking, our logic rFO3 ent from Theorem 5.2 only allows us to navigate the graph by moving to neighbors of the "current node". The logic er eut is a simple extension that allows us to move also non-neighbors (Proposition A5 shows that this logic actually gives us more power). Adapting the translation from logic to GNNs (from Theorem A.11 I. we can easily show that
C-MPNNs with global readout can capture this extended logic.
The precise definition of erFO ent together with the proofs of Theorems 5.2 and 5.3 can be found in Appendices A.3 and A.4, respectively. Let us stress that rFOs cat and erFO cut correspond to some
binary variants of graded modal logic g 19 As in Barceló et al. [ these connections are exploited in our proofs.
5.3 Locating rawly in the relational WL landscape
Let us note that rawle strictly contains rwl,, since intuitively, we can degrade the rawl2 test to compute unary invariants such that it coincides with rwl, As a result, this allows us to conclude that R-MPNNs are less powerful than C-MPNNs. The rawlz test itself upper bounded by known relational variant of 2-WL, namely, the relational (symmetric) local 2- WL test, denoted by rwl2. Given knowledge
7

---

graph G = (V,E, m),, this test assigns pairwise colors via the following update rule:
mwl, (u, (u, -- =r(wl (u, v), Ef (rwlly (),r) w E NN) E R)}, M (rwll (w,w), w), w E (G,)), E R))
This test and corresponding neural architecture, for arbitrary order k 2 2, have been recently studied in Barceló et al. under the name of multi-relational local k- S-WI..
This helps us to locate the test rawlz within the broader WL hi- erarchy, but it does not align perfectly with the practical setup: one common practice in link prediction is to extend knowledge 32 which empiri- cally yields stronger results and hence is used in most practical setups. However, the effect of this choice has never been quan- tified formally. We formally explain the benefits of this design choice, showing that it leads to provably more powerful mod- els. The idea is to consider tests (and architectures) which are augmented with the inverse edges: we write rawl; and rwl to denote the corresponding augmented tests and prove that results in more expressive tests (and hence architectures) in each case, respectívely. The precise tests and propositions, along with their proofs can be found in Appendix A..5| We present in Figure 2 the resulting expressiveness hierarchy for all these tests.
rwl
rawl
graphs with inverse relations 40 35
Proposition A.19
Proposition A.17
Propesition A.18
rwl2
rawl2
Figure 2: Expressiveness hierarchy: A B iff A B. By Proposi- tion A.20 rwl2 and rawl." are incom- parable. The case of rwlž N rawl analogous to Proposition A.18
Experimental evaluation
We experiment on knowledge graph benchmarks and aim to answer the following questions: Q1. What is the impact of the history function on the model performance? In particular, do models with f(t t perform comparably to those with f(t) = 0 specific choices for aggregation and message functions affect the performance? Q3. What is the impact of the initialization function the performance? What happens when the target identifiability property does not hold? Q4. Do C-MPNNs outperform R-MPNNs empirically? Q5. Does the use of global readout, a relational version affect the performance?
theory suggests? Q2. How do the
6.1 Experimental setup
Datasets. We use the datasets WN18RR 31 and FB15k-237 99, for inductive relation prediction tasks, following standardized train-test split given in four versions [30]. We augment each fact r(u, v) with an inverse fact ( u). There are no node features for either of the datasets, and the initialization is given by the respective initialization function INIT. This allows all the proposed GNN models to be applied the inductive setup and to better align with the corresponding relational Weisfeiler- algorithms. The statistics of the datasets reported in Ta Appendix C.I The code for experiments is reported in https:::/// /tt/gggtttbbb com crteyyySootuuungg
Implementation. All models use 6 layers, each with 32 hidden dimensions. The decoder function
parameterizes the probability of fact q(u, v) as p(u u, q) off function, and / a 2-layer MLP with 64 hidden dimensions. We adopted layer-normalization 2 and short-cut connection after each aggregation and before applying ReLUU. For the experiments concerning the message function MsG.. we follow the basis decomposition for the FB 15k-237 dataset with 30 basis functions for aggregation, and 15 for PNA aggregation. We ran the experiments for 20 epochs on Tesla T4 GPU. with mild modifications to accommodate all architectures studied in this paper. We discard the edges that directly connect query node pairs to prevent overfitting. The best checkpoint for each model instance is selected based on its performance on the validation set. All hyperparameter details are reported in Table of Appendix C.I
(2') ( (fo((()))) where the sigmoid
Evaluation. We consider filtered ranking protocol 66: for each test fact r(u, v), we construct 50 negative samples r(u', u'), randomly replacing either the head entity or the tail entity, and we report Hits 10, the rate of correctly predicted entities appearing in the top entries for each instance list prediction. We report averaged results of five independent runs for all experiments.
8

---

Table 1:
Inductive relation prediction with C-MPNNs using INIT initialization and no readout. The best results for each category are shown in bold and the second best results are underlined.
Model architectures
WNI8RR
FB15K-237
AGG
MsG,
f(t
v1
v2
v3
v2
v3
v4
sum
MsG
0
0.934
0.896
0.894
0
0.784
0.900
0.940
0.923
sum
MsG
t
0.932
0.896
0.900
0.881
0.794
0.906
0.947
0.933
sum
MsG
2
5
0
0.939
0.906
0.881
0.881
0.734
0.899
0.911
0.941
sum
MsG
t
0.937
0.906
0.865
0.884
0.728
0.883
0.929
0.931
sum
MsG
0
0.943
0.898
0.888
0.877
0.850
0.934
0.919
0.941
3
Sum
MsG.
t
0.934
0.896
0.892
0.880
0.844
0.943
0.926
0.950
PNA
MsG
0
0.943
0.897
0.898
0.886
0.801
0.945
0.934
0.960
PNA
MsG
1
0.941
0.895
0.904
0.886
0.804
0.949
0.945
0.954
PNA MsGa
0
0.946
0.900
0.896
0.887
0.715
0,896
0.887
0.886
5
PNA
MsG
t
0.947
0.902
0.901
0.888
0.709
0.899
0.875
0.894
PNA MsG
0
0.947
0.898
0.899
0.884
0.788
0.908
0.906
0.927
PNA
MsG
t
0.944
0.897
0.894
0.882
0.795
0.916
0.908
0.926
6.2
Results for inductive link prediction with C-MPNN architectures
We report inductive link prediction results for different C-MPNN architectures in Table T all ini- tialized with INIT?. Each row of Table I corresponds compare the model components. Note that while NBFNets [40] use different message functions for different datasets, separately report for each model architecture to specifically pinpoint the impact of each model component.
specific architecture, which allows to
History functions (Q1). First, we note that there is no significant difference between the models with different history functions. Specifically, for any choice of aggregate and message functions, the model which sets ft) t performs comparably to the one which sets f(t) = 0. This supports our theoretical findings, which state that path- message passing and traditional message passing have the same expressive power. This may appear subtle point, but it is important for informing future work: the strength of these architectures is fundamentally due to their ability to compute more expressive binary invariants, which holds regardless of the choice of the history function.
Message functions (Q2). We highlight that there is no significant difference between different message functions WNISRR, which is unsurprising: WN18RR splits contain at most 11 relation types, which undermines the impact of the differences in message functions. In contrast, the results on FB15k-237 are informative in this respect: Msc. clearly leads to worse performance than all the other choices, which can be explained by the fact that Msq? utilizes fewer relation-specific parameters. Importantly, Msa² appears strong and robust across models. This is essentially the message function of RGCN and uses basis decomposition to regularize the parameter matrices. Architectures using MsG with fewer parameters (see the appendix) can match or substantially exceed the performance of the models using Msc,,, where the latter is the primary message function used in NBFNets. This may appear counter- inntter-nttiitve since Msc. does not have a learnable query vector 2g. but this vector is nonetheless part of the model via the initialization function INIT?.
Aggregation functions (Q2). We experimented with aggregation functions sum and PNA. We do not observe significant trends on WNISRR, but PNA tends to result in slightly better-performing ar- chitectures. On FB 15k-377, there seems to be an intricate interplay between aggregation and message functions. For MsG... PNA appears to be a better choice than sum. On the other hand, for both Msc? and Msc sum aggregation is substantially better. This suggests that a sophisticated aggregation, such as PNA, may not always be necessary since it can be matched (and even outperformed) with a sum aggregation. In fact, the model with sum aggregation and Msc; is very closely related to RGCN and appears to be one of the best-performing models across the board. This supports our theory since, intuitively, this model can be seen as an adaptation of RGCN to compute binary invariants while keeping the choices for model components the same as RGCN.

---

Table 2: Results for inductive relation prediction on WNI&RR and FB15k-237 using no readout, global readout and selation-specifi readout, respectively. We use C-MPNN architecture with AGG PNA, MsG = Msa and INIT INIT?.
Model architectures
WN18RR
FB15k-237
READ
v1
v2
v3
v4
v1
v2
v3
v4
no readout
0.941
0.895
0.904
0.886
0.804
0.949
0.945
0.954
global readout
0.946
0.890
0.881
0.872
0.799
0.897
0.942
0.864
relation-specific
0.932
0.885
0.882
0.874
0.835
0.959
0.953
0.960
We conducted further experiments to understand the differences in different initializations at Ap- pendix C.2 confirming that the initializations that do not satisfy the target node distinguishabil- ity criteria perform significantly worse (Q3). We could not include R-MPNNs (e.g., RGCN and CompGCN) in these experiments, since these architectures are not applicable to the fully inductive setup. However, we conducted experiments on transductive link prediction in Appendix D.I and carried out additional experiments on biomedical knowledge in Appendix [.2] In both experiments, we observed that C-MPNNs outperform R-MPNNs by a significant margin (Q4).
6.3 Empirically evaluating the effect of readout
To understand the effect of readout (Q5), we experiment with C-MPNNs using INIT?, PNA, MsG... and ft) = f. We consider three architectures: (i) no readout component, (ii) global readout component (as defined earlier), and finally (iii) relation-specift readout. The idea behind the relation- relation-specifie readout is natural: instead of summing over all node representations, we sum over the features of nodes w which have an incoming q-edge (w Vit ) an outgoing q-edge (w E Vgr), where q is the query relation, as:
(t) READ( (h T
VG 4 B, w |wE wW w
Σ WEV
h w/ugg
W (4)
Σ VVV
h (4)
w|u.g"
We report all results in Table 2 First, we observe that the addition of global readout does not lead to sigmificant differences on WN18RR, but it degrades the model performance on 151--2237 in two splits (v2 and v4). We attribute this to having more relation types in FBI 15-37737, so readout over all nodes does not necessarily inform us about a elation-speeiffe prediction. This is the motivation behind the relation-specific readout: we observe that it leads to significant improvements compared to using no readout (or a global readout) over all splits, leading to state-of-the art results. In contrast, relation-specific readout does not yield improvements findings suggest that the global information can be very useful practice, assuming the graph rich in relation types. We further conduct synthetic experiment to validate the expressive power of using global readout: architectures without global readout cannot exceed random performance, while those using a global readout can solve the synthetic link prediction task (see Appendix EE)
the relationally sparse WNISRR. These
7 Outlook and limitations
We studied a broad general class of GNNs designed for link prediction over knowledge graphs with a focus on formally characterizing their expressive power. Our study shows that recent state-of-the-an models are at 'sweet spot': while they compute binary invariants, they do so through some local variations of higher-dimensional WI. tests. This is precisely characterized within our framework. To capture global properties, we propose readout components and show that their relational variant is useful datasets with many relation types. This study paints more complete picture for our overall understanding of existing models and informs future work on possible directions.
In terms of limitations, it is important to note that the presented approach has certain restrictions. For instance, it limited to binary tasks, such as link prediction. Thus, this approach does not directly extend to higher arity tasks, e.g., link prediction on relational hypergraphs or predicting the existence knowledge graph. When considering local or conditional variations of the k- WI. algorithm, computational demands can become significant challenge. Further research is needed to explore potential optimizations for higher-order MPNNs that can enhance their performance while preserving their expressive power.
of substructures of size
10

---

8 Acknowledgement
The authors would like acknowledge the use of the University of Oxford Advanced Research Computing (ARC) facility in carrying out this work (http://dx. would also like to thank Google Cloud for kindly providing computational resources. Barceló is funded by ANID-Millenaium Science Initiative Program CodelCN Romero is funded by Fondecyt grant 1009556. Barceló and Romero are funded by the National Center for Artificial Intelligence CENIA FB210017, BasalANID.
222////2ooo.222588 We
References
[1] Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In IJCAI, 2021.
[2] Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. In CoRR, 2016.
[3] Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In ICLR, 2020.
[4] Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel Romero. Weisfeiler and leman go relational. In LoG, 2022.
[5] Peter W. Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray Kavukcuoglu. Interaction networks for learning about objects, relations and physics. In NIPS, 2016.
[6] Antoine Bordes, Nicolas Usumier, Alberto Garcia-Duran Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, 2013.
[7] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In NeurIPS, 2020.
[8] Maarten Rijke. A note on Graded Modal Logic. Stud Logica, 2000.
[9] Tim Dettmers, Minervini Pasquale, Stenetorp Pontus, and Sebastian Riedel. Convolutional 2D) knowledge graph embeddings. In AAAI, 2018
[10] Luis Antonio Galárraga, Christina Teflioudi, Katja Hose, and Fabian Suchanek. AMIE: As- sociation rule mining under incomplete evidence in ontological knowledge bases. In WWW, 2013.
[11] Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICMI, 2017.
[12] Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In IJCNN, 2005.
[13] Martin Grohe. The logic of graph neural networks. In LICS, 2021.
[14] Aditya Grover and Jure Leskovec. Node2vee: Scalable feature learning for networks. In KDD, 2016.
[15) Daniel Scott Himmelstein, Antoine Lizee, Christine Hessler, Leo Brueggeman, Sabrina I. Chen, Dexter Hadley, Ari Green, Pouya Khankhanian, and Sergio E Baranzini. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. In eLife, 2017.
[16] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NewrIPS, 2020.
[17] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.

---

[18]
Lecheng Kong, Yixin Chen, and Muhan Zhang. Geodesic graph neural network for efficient graph representation learning. In NeurlPS, 2022.
[19] Carsten Lutz, Ulrike Sattler, and Frank Wolter. Modal logic and the two-variable fragment. In CSL, 2001.
[20] Christian Meilicke, Manuel Fink, Yanjie Wang. Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt. Fine-grained evaluation of rule- and umbedding-basee systems for knowledge graph completion. In /WSW, 2018.
[21] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
[22] Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. NeurIPS, 2020.
[23] Martin Otto. Graded modal logic and counting bisimulation. In arXiv, 2019.
[24] Bryan Perozzi. Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social repre- sentations. KDD, 2014.
[25] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. In NIPS, 2019.
[26] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In SDM, 2021.
[27] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 2009.
[28] Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, 2018.
[29] Zhiqing Sun, Zhi-Hong Deng. Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embed- ding by relational rotation in complex space. In ICLR, 2019.
[30] Komal K. Teru, Etienne G. Denis, and William L.. Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, 2020.
[31] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In CVSC, 2015.
[32] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition-based multi-relational graph convolutional networks. In ICLR, 2020.
[33] Hongwei Wang, Hongyu Ren, and Jure Leskovee. Relational message passing for knowledge graph completion. In KDD, 2021.
[34] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[35] Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In NewrlPS, 2017.
[36] Jiaxuan You, Jonathan M. Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In AAAI, 2021.
[37] Donghan Yu, Yiming Yang, Ruohong Zhang, and Yuexin Wu. Generalized multi-relational graph convolution network. ICML. Workshop on Graph Representation Learning and Beyond, 2020.
[38] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NeurlPS, 2018.
12

---

[39] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. In NeurIPS, 2021.
[40] Zhaocheng Zhu, Zuobai Zhang, Mouis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. In NeurIPS, 2021.
13

---

A Proofs of technical statements
A.1 Expressive power of R-MPNNs
The expressive power of R-MPNNs has been recently characterized in terms of a relational variant of the Weisfeiler-Leman test (4] We define the relational local 1- WL tes which we denote by rwh- Let G (V, E, R, c) be a knowledge graph. For each 2 the test updates the coloring as follows:
rw! = c(v), (w((+t)(()) T ((wwl (rwl)
(v), r)) w e (G()),, RB),
where т injectively maps the above pair to a unique color, which has not been used in previous iterations. Hence, rw/!" defines node invariant for all 0.
The following result generalizes results from Barceló et al. 44. Theorem A.1. Let G (V, E, R. be knowledge graph.
1. For all initial feature maps with all R-MPNNs with T layers, and 0 t T, it holds that rwi( = (t)
2. For all T 2 O and history function f. there is an initial feature map a with c = a and an R- MPNN without global readout with T layers and history function such that for all we have rwl (1).
Intuitively, item (1) states that the relational local 1-WL algorithm upper bounds the power of any R-MPNN A: if the test cannot distinguish two nodes, then A cannot either. On the other hand, item (2) states that R-MPNNs can be as expressive as rwh: for any time limit T, there is an R-MPNN that simulates T iterations of the test. This holds even without global readout component.
Remark A.2. A direct corollary of Theorem A. is that R-MPNNs have the same expressive power as rwh,, independently of their history function.
In order to prove Theorem A. we define a variant of rwl, as follows. For a history function f: IN (recall is non-decreasing and f(t) (), and given knowledge graph G (V, E,, e). we define the rwli,f test via the following update rules:
(,) (v) c(v)
nw/ (++11) (w/( (w) 7 (rwl (1m(( (v), (rm) (w), r)) E ENG()), RB).
where - injectively maps the above pair to unique color, which has not been used in previous iterations. Note that rwl, corresponds to rwl1,id for the identity function id(t)
We have that (") is always a refinement of rw!!"y Note that this is trivial for [(() = /. but not for arbitrary history functions.
(t)
Proposition A.3. Let G = (V, E, R, c) be knowledge graph and f be a history function. Then for all 2 0, we have rwl (++1) 3 rw))))
Proof. We proceed by induction on t. For t = O, note that (wl = nwll ()) implies (w((((()) (u) = rwl (f(0)) (v) and f(() = 0. For the inductive case, suppose rwnl (e+11 (w) = mw (+) fort and u. V. By injectivity of r, we have that:
mwl (5((5 (u) = rmn(((10)
I (w),)) (N), RD = M (. RJ.
"This test over single-me rellte-elltton graphs is often called color refinement called multi relational 1-W WL.
B3 In Barceló et al. 4 it is also
14

---

By inductive hypothesis and the facts that [(1- S [(L) (as f' non-decreasing) and rwl / (1(00) (1)(0)()))
rwllff (e), we obtain (f(t-t 13) (u) r rwl
( 1)) (v). On the other hand, by inductive hypothesis,
we obtain that
[(mll (w),r) (w),)) TewwEN ( E RB = {(ml (w),)) | w EN)( E RR.
We conclude that nwl (wll.y( (u) (v)
As it turms out, (w] defines the same coloring independently of f: Proposition A.4. Let G - (V, E, R,
c) be a knowledge graph and J, I' be history functions. Then for all t 2 O, we have that rw] = 1.
Proof. We apply induction on t. For t 0, we have rwll =c= 1. For the inductive case, suppose (wl (u) ( (v). for t 1 and u, E V. Since f'(t
1) S t and by Proposition A.3 we have that (w if (f((tt))) (u) rwly, ( The inductive hypothesis implies
[ that (
1}] (u) m
(e (v). On the other hand, by injectivity of r we have
1.f
(w), I
E (N), RD = (w), w ENN)))) RD.
The inductive hypothesis implies that
@ (rwl 18 (w),r) (ww) we EN,( E R] = [( (Iw)),))))))))))) w ENN(U))
Summing up, we have that rwlf (u) = ( (v), and hence rwl 3 mwl The case rwl (1) (w] (t) follows by symmetry.
1.f
Now we are ready to prove Theorem A.1
We start with item (1). Take an initial feature map with = x. an R-MPNN with T' layers, and history function f. suffices to show that rwl i, 3 h((), for 0 S l L Indeed, by Proposition A.4 we have rw!!")) = rw] = rwlf)) where id is the identity function id(t) = t,, and hence the result follows. We apply induction on t. The case t = follows directly as rw/ (0) = (u) = mwl (2) 1,f (v) for 2 and u, E V. By c + = (0). For the inductive case, assume nwl (w) injectivity of we have:
rwl 11 (u) rw]l (m1((((-1)(()))
( (nwi ()))))))))))) w E (.) RD (nmil (1) w ENN())) RJ.
By inductive hypothesis we have (recall [(I - 1) 1-51110 1):
(((--1)) = (f((t11))
(h | W (w) (h (N(())
for each r R.
This implies that of (Ms and hence:
(11) E NN(u)) = (1o- | w E (NN(N())).. for each R.
[MSG (b)- | WEN,(u)) RB- (MGG (.N,
We conclude that
h (t)
UpD(h (ag--))))GGG((( (MMG, ((-1)) (N)(w), E RJ), READ w E VB)
= UpD(h!/(t-1) AGG (hs, (t-(1))) w (N), E RW), READ w (EEVE VV))
15

---

For item (2), we refine the proof of Theorem 2 from Barceló et al. 4 which is based on ideas from Morris al. [2T]. In comparison with Barceló et al. [4] in our case, we have arbitrary adjacency matrices for each relation type, not only symmetric ones, and arbitrary history functions, not only the identity. However, the arguments still apply. Moreover, the most important difference that here we aim for a model of R-MPNN without global readout that uses a single parameter matrix, instead of two parameter matrices as in Barceló et al. [4] (one for self-representations and the other for neighbors representations), This makes the simulation of rwl, more challenging.
We use models of R-MPNNs without global readout of the following form:
h (++1) sign (W()) (1(
Σ
Σ
a, ar -bb) b).
where ( is parameter matrix and b is the bias term (we shall use the all-ones vector b = 1). As message function MsG, we use vector scaling, that is, MsG, (h) = a,,h, where a, is parameter of the model. For the non-linearity, we use the sign function sign. We note that the proof also works for the ReLU function, following arguments from Corollary 16 in Morris et al. [21].
For matrix B, we denote by B, its i-th column. Let V nn). We will write features maps h V -> Rd for G = (V, F,, R, c) also as matrices H E [dxx, where the column H. corresponds to the d-dimensional feature vector for v. Then we can also write our R-MPNN model in matrix form:
[V] and without loss of generality assume
H (+++) sign
( H (f0))
+I
A,) H A,) -.))- -))
PER
where A, is the adjacency matrix of G for relation type E R and J is the all-ones matrix of appropriate dimensions.
Let Fts be the following matrix:
1
Ftss
That is, (Fts); = -1 if 2 i, and (Fts) = otherwise. Note that the columns of Fts are linearly independent. We shall use the columns of Fts node features in our simulation.
The following lemma is an adaptation Lemma 9 from Morris et al. (2T]
Lemma A.5. Let E Noxp matrix such that S n, and the columns are pairwise distinct and different from the all-zeros column. Then there is a matrix X E R such that the matrix Sign(BB B- - J) E (-1, 1 is precisely the sub-matrix of Fts given by its first p columns.
Proof. Let (1, m, m² m== Nixn, where m is the largest entry in B, and b xB NIXP, By construction, the entries of are positive and pairwise distinct. Without loss of generality, assume that b- (61, b2..... .a.....bp. .p)) for bi > b2
bp > O. As the b, are ordered, we can choose numbers #1 T1..... Ip E such that 6; Ij < l 2 j. and b; Ty > 1 if < j. for all i (I.......) .p). Let æ = (II...... Tp. 2/bp,.................. 2/bb)² Rax1, Note that (2/bp) by > 1, for all i E (1...., ... Then sign(xb - J) precisely the sub-matri of Fts given by its first columns. We can choose X = x2 E Raxa.
Now ready to show item (2). Let be any history function and T 0. It suffices show that there a feature map x with e = æ and an R-MPNN without global readout with T layers and history function f such that (w](.) = (t), for all 0 < < T. Indeed, by Proposition A.4, we have (w](.) rwi 1,sd rw where id is the identity function id(t) t. and then the result follows. We conclude item (2) by showing the following lemma:
16

---

Lemma A.6. There is a feature map h h() + R", and all 0 S < T, there is feature map ((+1), V R", matrix (( Raxx and scaling factors or RR for each r E R, such that:
h0 = m
The columms of H(t) RR are columns of Fts (recall H ) the matrix representation of ).
. H = sign (W()) ( + EVER
of 19 A.)
J). -J).
Proof. We proceed by induction on f. Suppose that the node coloring rw]].) = uses colors .....PP. for p S n. Then we choose (0) (this is the initial feature map x in the statement of item (2)) such that h = Ft)s.())- that is, h the c(u)-th column of Fts. We have that (0) satisfies the required conditions.
For the inductive case, assume that (t()) (+) and the columns H (() are columns of Fts, for all 0 < t' < < T. We need to find (t++1), ( and (1) satisfying the conditions. Let M E R be the matrix inverse of Ft.s. If H(((), is the i-th column of Fts, say that has color at iteration t'. Observe that for all 0 < t' S f, we have
{}
if has color at iteration t'
(MH
0
otherwise.
In other words, the v-th column of M MH (t') is simply one-hot encoding of the color of v at iteration
l'. For each r E R we have
(MH( A,) = (wr E (v) to has color at iteration #||--
Hence the v-th column of (() A, is an encoding of the multiset of colors for the neighbor- hood Nf at iteration Let Ti...., Tm be enumeration of the relation types in R. Let
D R(m++))xx be the matrix obtained by horizontally concatenating the matrices (H()())
MH ,,....,, (M Ar.. Since H((()) = rw(((()) and (1)) rwl we have that
D rw1((+1) Now note that E, where
E MHU ( A.,.
Indeed, Eiv is simply the (n + 1)-base representation of the vector (Dio, D Platijes (j2n+iju--...... ...y D (mn+s))u) and hence E., E. if and only if D. D₂ (note that the entries of D are in {O.....n)) n)). In particular, E = mll!tt))
Let be the number of distinct columns of E and let É E Na be the matrix whose columns are the distinct columns of E in an arbitrary but fixed order. We can apply Lemma A.5 to E and obtain matrix X E _ such that sign( X E J) is precisely the sub-matrix of Fts given by its first columns. We choose (1+1) sign( J-J) E Raxn, W(() XM E Raxx and ar. (n+1)'. Note that the columns of H (++1) are columns of Fts, and that (++1) = E = mll()))) Finally, we have
H sign( X -
sign(X (MH(/()) + Σ (n 11) (A.,) -
= sign (H)(((HU())) +
(1) H A..) - JJ.
a
i=1
17

---

Note that our result applies to more complex message functions such as MsG, (h) h * b,,, where stands for element-win wise multiplication and b, is a vector parameter, and MSG, W, where W, is matrix parameter, as they can easily express vector scaling. The first case has been used for the model CompGCN 32 while the second case has been used for R-GCN (8
A.2 Proof of Theorem 5.1
We recall the statement of the theorem:
Theorem 5.1 Lei G (V, E, R x.,1) n) be a knowledge graph, where x: is a feature map, and yj is pairwise coloring satisfying target node distinguishability, Let q E R be any query relation. Then:
1. For all C-MPNNs with T layers and initialization INIT satisfying INIT = 1), and all 0 S.ST, we have rawl?"
2. For all T 2 and history function f. there is an C-MPNN without global readout with T layers and history function f such that for all 0 S t S T, we have rawl (t) = h/g
We start by showing item (1) and (2) of the theorem for the case without global readout. As we explain later, extending item (1) to include readouts is straightforward. In order to prove this particular case, we apply a reduction to R-MPNNs and the relational local 1-WL. Before doing so we need some auxiliary results.
Let G= (V, E, R, c, ri) be a knowledge graph where is pairwise coloring. We denote by G the knowledge graph G = (VxV, E' R, CT) where E' = {r((u,, (r)((,),, (u, u)) r(w, u) E,r E R} and C, is the node coloring C,((u, u)) = 17(2, v). Note that the coloring c is irrelevant in the construction. Intuitively, G encodes the adjacency relation between pairs of nodes of G used in C-MPNNs. We stress that G and G2 have the same relation type set R. If A is a C-MPNN and B is R-MPNN, write h (t) (,, v) := h (u, v) and B ((u, o)) == h (2()) ((u, v)) for the features computed by A and B over G and G², respectively. We sometimes write N,H (v) to emphasize that the neighborhood
is taken over the knowledge graph H. Finally, we say that an initial feature map y for G satisfies target node distinguishability if y((,, u)) & y(uu,)) for all + V.
We have the following equivalence between C-MPNNs and R-MPNNs without global readout: Proposition A.7. Let G = (V, , E, R, æ, 1) The a knowledge graph where æ is a feature map, and rj is pairwise coloring. Let q E R be any query relation. Then;
1. For every C-MPNN without global readout A with T layers, there is an initial feature map for G2 an R-MPNN without global readout B with layers such that for all 0 S t < T and
u. U E V, we have h (,, v) = h B. hBg.Ga((u, ((u,))))) v)).
2. For every initial feature map y for G2 satisfying target node distinguishability and every R- MPNN without global readout 13 with T layers, there is C-MPNN without global readout A
(t) with T layers such that for all 0 S < T and u, G E V, we have h A v) = h h ((u, v)).
(1)
Proof. We start with item (1). The sought R-MPNN has the same history function and the same message, aggregation, and update functions as A for all the T layers. The initial feature map is defined as y(uu, v)) INIT(U, v, q). where INIT is the initialization function of A.
We show the equivalence by induction on t. For f = O, we have (0) (u, v) = INIT(U, =
v(uu, v)) hg ((u, r)). For the inductive case, take u, v E V. We have
n (e+1) (u. u) = UPD (h (/(0) (u, v), AGG Mss, (h (u, w)), 2g)1 w Un (f(0) ((u, v)), Aca @f Msc, (h (t) ((u,w)), 21)1 (u. E N ((u,u)),r r E RB))
RD))
hg (1+1) ((u,
For item (2), we take A to have the same history function and the same message, aggregation, and update functions than 23, for all the T layers, and initialization function INIT such that INIT(U, v, =
((u,, v)). The argument for the equivalence is the same as item (1).
The pairwise coloring does not play any role in the proposition.
18

---

Regarding WL algorithms, we have a similar equivalence:
Proposition A.8. Let G (V, E, R, c, 1i) be a knowledge graph where n is a pairwise coloring. For all 2 and computed over G = (V x V, E', R. C.))
V. we have that rawl??
(0) (u,o) v) computed over G coincides with rwl)" ((u,v)
Proof. For i O, we have rawl2 (u, v) u), c,((u, rwl) ((u, u)). For the inductive case, we have
rawl ((+1) vu, = ((rawll") (u, v), & (rawl)") (u, w), A,) )R)) = =T(ml] ((u, u)), { [rml (0) ( ((,,w)),)) (u,w) E N, ((u,u)), R)H)
rwl(tt]) ((,,)))
Now we are ready to prove Theorem 5.1
For G (V, E, R. x. 7)), we consider G = (V x x R. c,). We start with item (1). Let A be a C-MPNN without global readout with 7 layers and initialization INIT satisfying INIT = 1j and let 0 Ostt 1 T. Let y be an initial feature map for G2 and B be R-MPNN without global readout with 7 layers as in Proposition
A.7, item (1). Note that = co as y((u, v)) = INIT(U, U, q). We can
apply Theorem A.l
item (1) G2, y and B and conclude that rw] 3 h (1)
(t)
BB,02 This implies that
rawl() A.G.
(t)
For item (2), Tet and f be a history function. We can apply Theorem A. item (2), to G2 to obtain initial feature map y with y Cg and an R-MPNN without global readout B with T layers and history function f such that for all 0 S t S T, we have rwi(") = h (c)
8.G2- Note that y satisfies larget node distinguishability since does. Let A be the C-MPNN without global readout obtained from Proposition A.7 item (2). We have that rawl? h A.G required.
Remark A.9. Note that item (2) holds for the basic model of C-MPNNs (without global readout), presented in Section 4.1 with the three proposed message functions Msa,, MsG., MsG. they can express vector scaling.
Finally, note that the extension of item (1) in Theorem 5.1 to the case with global readouts is straightforward. Indeed, readout. As for two pairs of the form (w,, v) and (u, v') the global readout vectors are identical (to READ( @ (t) wll
apply exactly the same argument used for the without global
E V)),,, this argument still works.
A.3 Proof of Theorem 5.2
We recall the statement of the theorem:
Theorem 5.2] A logical binary classifier is captured by C-MPNNs without global readout if and only if it can be expressed in rFO
The proof is reduction to the one-dimensional case, that is, R-MPNNS without global readout and a logic denoted by rFO2 ent- So in order show Theorem 5.2 need some definitions and auxiliary results.
Fix set of relation types R and set of node colors C. We consider knowledge graphs of the form G= (V, E, R. c) where e is a node coloring assigning colors from C. In this context, logical formulas refer to relation types from R and node colors from C. Following Barceló al. 3, logical (node) classifier is a unary formula expressible in first-order logic (FO), classifying each node u on a knowledge graph G according whether the formula holds not for over G.
We define a fragment rFO2 ent of FO as follows. A rFO ent formula is either a(x) for E C, or one of the following, where oo and & are rFO ent formulas, N 2 1 is a positive integer and E R:
px(x), p(z)
3 N y (p(()) A r(y,
19

---

We remark that rFO is actually the fragment of FO used in Barceló et al. [ to characterize GNNs, adapted to multiple relations. It is well-known that iFO cut is equivalent to graded modal logic B
The following proposition provides useful translations from rFO cut to rFO cnt and vice versa. Recall from Section A.2 that given knowledge graph G = CV, E, R. n) where 1/ is pairwise coloring, we define the knowledge graph G² = (V x V, E", R, Cg) where E' = [r((u, w), (u, v)) r(w, E F,r E R} and Cy is the node coloring Cn Cr((U, v)) (u,
Proposition A.10. We have the following:
1. For all rFO Fn formula p( y). there is a formula ((x) in rFO ent. such that for all knowledge graph G = (V, R,, n). we have G, u, -= ip if and only if G2 (u, v) } pp.
2. For all formula yp(x) in rFO ene there is a rFO formula ((x,, y) such that for all knowledge graph G = (V, E, R, 1), we huve G, u, F & if and only if G2, (u, v) F 4.
Proof. We start with item (I), We define ((x) by induction on the formula p(x, y):
1. If (oz, y) a(x, v) for color a, then ( - a(z).
2. If (Tlp,, y) (- v). then ((x) -p)).
3. If (fz(2,)) y) (I, 3) (2 y), then p(x) (x) A (2(2))
4. (f y) = 3 (0 2) A ((,,)) v)) then ((x) = 32 N y (v(()) A r(y,
Fix G = EV, R. 7) and G² = (V x V, , R. C,). We show by induction on the formula that G, U.u.e v = p if and only if G? (u, r) = V.
For the base case, that is, case (1) above, we have that p(x, a(x, v) and hence G, u,u, v F= yp iff = a iff G²,
n(,, v) = a iff
Now we consider the inductive case. For case (2) above, we have p(z.v) = -b(2z v). Then G, u. - + iff G, u, + & iff G2, (u,e) + & iff G2, (u, v) F G.
For case (3), we have p0x, y) = si (x, 4) (a y). Then G,u,U F vp iff G, G,u,U F i and G, C.u.o P2 iff G², (u, v) F 51 and G2 (u, v) F 42 iff G2, (w,
Finally, for case (4), we have y(æ, u) N2ト= (1b( 2) A Ar(z,y)) Assume G, u, v F= 9, then there exist at least N nodes w E V such that G, u, w F vp and r(w, 1) E E. By the definition of G2. there exist at least N nodes in G2 of the form (u, w) such that G2, (u, w) } + and r(uu, w). (u, v)) E E'.
It follows that G², (u, v) F c.. On the other hand, suppose G², (u, v) } P. Then there exist at least N nodes (o, of) in G2 such that G, (o, o') } & and r((o, ('), (u, v)) E'. By definition of G2 each (o, o') must be of the form (o, d') = (u, w) for some w E V such that r(w, v). Then there are at least N nodes w E V such that G, u, w F te and r(w,") v) E E. It follows that G, u, v F pp
Item (2) is similar. We define ((x, y) by induction on the formula ((x):
1. If p(z)= = a(x) for color then p(x, y) = a(x, v)-
2. If ((x)= (2), then ((x, v) = - y).
3. If (fx))) yP (z) ^ (x). then f(x, 8) T (1. v) (z.
4. If p(x)) = 3 y (v) r(y, then ((x, y) = N (5(z, 2) A r(),))).
Following the same inductive argument from item (1), we obtain that u,u,v F= vp if and only if (,, F p.
The following theorem is an adaptation of Theorem 4.2 from Barceló et al. B. The main difference with Barceló et al. [3] is that here we need to handle multiple relation types. Theorem A.11. A logical classifier is captured by R-MPNNs without global readout if and only if it can be expressed in r ent-
20

---

Proof. We start with the backward direction. Let p(x)) be a formula in rFO ent for relation types R and node colors C. Let .I...... Pr. an enumeration of the subformulas of ip such that if y; is subformula of jj, then i S j. In particular, 9r. s. We shall define an R-MPNN without global readout B, with layers computing T--dimensional features in each layer. The idea is that at layer E {L..... L), the l-th component of the feature h! is computed correctly and corresponds to 1 if se is satisfied node v, and otherwise. We add an additional final layer that simply outputs the last component of the feature vector.
We use models of R-MPNNs of the following form:
h (++1) a Wh + E E W w,h +b) FER wEN
where W E REx is a parameter matrix and b E R is the bias term. As message function MsG, we use MsG, (h) W.h. where W, E R4x a parameter matrix. For the non-linearity a we use the truncated ReL.U function (xx) (ain(max(0, r), 1). The &-th row of W and W,, and the f-th entry of b are defined as follows (omitted entries are 0):
1. If pe(x)) a(x) for a color C. then Wee
2. If (e(x)) (2) then We 1, and by 1.
3. pe(x) (a) (px(2) (z) then Wej 1. We 1 and by -1.
4. If (e(x)) = 3 y (p)(y) A r(y, x)) then (W, 11 and b -N + 1.
Let G = (V, E, R, c) be a knowledge graph with node colors from C. order to apply B, to G, we choose initial T--dimensional features h such that (h.")) if ye a(x) and is the color of , )
otherwise. In other words, the I--dimensional initial feature h is a one-hot encoding of the color of v. It follows from the same arguments than Proposition 4.1 in Barceló et al.
v, and (ne
3 that for all E (1...., L} we have (R = if G, u += pe and (h = otherwise, for all E V and E {l.... L}. In particular, after L layers, B, calculates !a such that (h! 1 if G, v. == yp and (h( r. otherwise. As layer T. + extracts the I-th component of the feature vector, the result follows.
For the forward direction, we follow the strategy of Theorem 4.2 from Barceló et al. [3] Given a knowledge graph G = (V, E, R, c) and number L IN, we define the unravelling of u E V at depth I., denoted Unr((vv) is the knowledge graph having:
A node (v, 01 UI....,
in G of length S L. uz) for each directed path ui,.... "i,...,,1, 21,
For each r E R, fact r((v, u1...., (here tig := v).
"u.....,,,............. u4), (v, u1. Mi...., ui....,u_... for all facts r(u,, (4-1) E E
Each node (v, ui.... u.) is colored with c(us), that is, the same color as uq-
Note that the notion of directed path is defined in the obvious way, as for directed graphs but ignoring relation types. Note also that (n))(()) (v) is a tree in the sense that the underlying undirected graph is tree.
The following proposition is trivial adaptation of Observation C.3 from Barceló al. 3 We write Unr Unr/y (v') if there exists an isomorphism from Unr(((v) to (n") such that f(v) =
Proposition A.12. Let G and G' be two knowledge graphs and v and be nodes in G and G', respectively, Then, for all L N, we have that rw (v) G coincides with rwif") (e') G' if and only if (v) (n))
As consequence of Theorem A. obtain:
21

---

Proposition A.13. Let G and G' be two knowledge graphs and and v' be nodes in G and G', respectively, such that (nl ~ (nrgg(t') (v') for all L N. Then for any R-MPNN without global readout with T layers, we have that h on G coincides with h h on G'.
Finally, the following theorem follows from Theorem C.5 in Barceló et al. [3], which in turn follows from Theorem 2.2 in Otto [23] The key observation here is that the results from Otto 23 are actually presented for multi-modal logics, that is, multiple relation types.
Theorem A.14. 123) Let a be unary FO formula over knowledge graphs. If a is not equivalent to formula, then there exist two knowledge graphs G and G', and two nodes in G and vf in G' such that (v) = Unrg. for all L E IN and such that G. v }= a but G', of V a.
Now we are ready to obtain the forward direction of the theorem. Suppose that a logical classifier a is captured by an R-MPNN without global readout B with T layers, and assume by contradiction that a is not equivalent to a rFO ent formula. Then we can apply Theorem A. 14 and obtain two knowledge graphs G and G", and two nodes v in G and v' in G' such that (v) = (t') for all L E N and such that G, v }= a but G", if a. Applying Proposition A.13 we have that h
on G coincides with h (2) on G", and hence B classifies either both v and v' as true over G and G', respectively, or both as false. This is a contradiction.
Now Theorem 5.2 follows easily. Let a be a logical binary classifier and suppose it is captured by C-MPNN without global readout A. By Proposition A.7 i.tem (I), know that A can be simulated by R-MPNN without global readout B over G². In turn, we can apply Theorem A. and and obtain a formula &p in rFO? equivalent to B. Finally, we can apply the translation in Proposition A. item (2), and obtain a corresponding formula ; in rFO3 ent We claim that & captures A. Let G be knowledge graph and u, two nodes. We have that G, u, } & iff G2, (u,v) v) } yp iff B classifies (u, v) as true over G2 iff A classifies (u, v) as true over G.
The other direction is obtained analogously following the reverse translations.
A.4 Proof of Theorem
We recall the statement of the theorem:
Theorem 5.3
Each logical binary classifier expressible in erFO can be captured by C-MPNN.
We start by formally defining the logic erFO? ent. which is a simple extension of rFO cut from Sec- tion 5.2 Fix set of relation types R and set of pair colors C. Recall consider knowledge graphs of the form G = (V, E, R, 17) where 1) is a mapping assigning colors from C to pairs of nodes from V. The logic erFO cut contains only binary formulas and it is defined inductively as follows: First, a(æ, y) for a E C, is in erFO cut- Second, if ppx y) and ()x y) are in erFO ont N 2 1 is a positive integer, and r E R, then the formulas
-4(x, v), (lx, v) A V), INM 21pxx, 2) Ar(2,y)), 3ZN 2 (1((1 A - v))
also in erFO3 As expected, v(u,e) holds in G (V, E,E.RRRY R, if n(u,w) = a, and g2N (p(u, 2) A f(2, v)) holds in G. for 8 E R U {or r E R). if there are at least N nodes we E V for which p(u, w) and f(w, v) hold in G.
3 Intuitively, erFO" ent. extends rFO ent. with negated modalities, that is, of node. As turns out, erFO²
check for neighbos
3 ent is strictly more expressive than FFo3 cnt that cannot be expressed by any formula in rFO
Proposition A.15. There is a formula in erFO?
Proof. Consider the following two knowledge graphs G1 and G2 over R = (r) and colors C = (Green). The graph G1 has two nodes u and and one edge r(u, v). The graph G2 has three nodes u, v and w and one edge r(u, v) (hence w is an isolated node). In both graphs, all pairs are colored Green.
We show first that for every formula ylz,, y) in FO ent: is the case that G1, u, n F= sp iff G2, u, n F= sp, for n E {u, v). We proceed by induction on the formula. For (p(z, y) = Green(æ, v), we have
22

---

that GI, n, F and G2, n - ip and hence we are done. Suppose now that qfx, y) = -,, y). Assume G1, u. n F & for n E fu, v}. Then G₁, u, bا v, and by inductive hypothesis. we have G2, U j th and then G2, u F s. The other direction is analogous. Assume now that (((x)) y) = th1 (2, y) A (2(2; y). Suppose G,,u, u, n = yp for a E v). Then G1,u, G1, u, F 2/2, and by inductive hypothesis, G2. u. F 1/1 and G2. U. F th2. Then G2. U, = g. The other direction is analogous. Finally, suppose that gfxx, y) = 32 2(,( Ar(Z, B)). Assume that G1, u, n += & for n E {u, w). Then there exist at least N nodes w E (n) in G1 such that G1, u, w + v. Since (u) = 0. we have ni = s. As (T) = {u}, we have w = u. Since the neighborhood (v) is the same in G1 and G2, and by the inductive hypothesis, we have that there are at least N nodes w E (v) in G2 such that G2, u, w F vb. This implies that G2. u, v - p. The other direction is analogous.
U, n F 1/1 and
Now consider the erFO cut formula cp y) = 3=22222222222 2 2) ^ (r B)). We claim that there is no rFO ent formula equivalent to (0(1, y). By contradiction, suppose we have such an equivalent formula sp. As shown above, we have G1. u, v F s' iff G2, u, + s². On the other hand, by definition, we have that G1, u, V f and G2, v + s. This is a contradiction.
Now we are ready to prove Theorem 5.3 We follow the same strategy as in the proof of the backward direction of Theorem AIII
Let (zz y) be a formula in erFO ent for relation types R and pair colors C. Let (i...... fL be an enumeration of the subformulas of y such that if yo; is subformula of 4,, then i S j. In particular, pr. = yp We will construct C-MPNN A.p with I. layers computing T--dimensional features in each layer. At layer é E (1...., L). the é-th component of the feature h hvlu.g will correspond to 1 if yoe is satisfied on (u, v), and 0 otherwise. The query relation q plays no role the construction, that is, for any possible q E R the output of A,p is the same. Hence, for simplicity, in the remaining of the proof we shall write f/ instead of (t) We add an additional final layer that simply outputs the last component of the feature vector.
"/u.g"
We use models of C-MPNNs of the following form:
h (t+1)
(Woh! (1) + Σ Σ WER
W. (1)
w/u + W1 Σ h (2) ulju + +).
WEV
where Wo, W1 RLXL are parameter matrices and b RL is the bias term. As message function MSG, we use MsG, (h) = W,,h, where W, E RLXL is a parameter matrix. For the non-linearity o we use the truncated ReLU function (Ix) min(max(O, z), 1). The ê-th row of Wo. W1 and W,. and the E-th entry of b are defined as follows (omitted entries are 0):
1. If (ele(, v) = axx, y) for a color a E C, then (Wo)et 1.
2. If (eee,, y) = -pp((,,) y) then (Wo)es 1, and be = L.
3. If (e((z y) (, v) (2, y) then (Wo)s, = 1. (Wo)es
and be -I
4. If (ele,, y) = 3 2 (1, 2) r(2, v)) then (W,) e and by -N + 1.
5. If (e v) 327 > 3 2) -r. then (W, W.)ex 11 (W1) ei)ex and b -N 1.
Let G = EV,E, be knowledge graph with pair colors from C. In order to apply A. to G,
(0) we choose the initialization INIT such that T-dimmensinal initial features h ooju satisfy (h/fu)) =
(0)
if op a(z, y) and nuu, v) = and (h (0 = 0 otherwise. That is, the L-dimensional initial (0)
feature h o/2 is ooe-hot encoding of the color of (u, Using the same arguments as in the proof of Theorem A.11 we have (h (/))) 1 if G, u, v }= po and (h (fu) )r = otherwise, for all u, u E V and t E {l....,.i L}. In particular. after L layers, Ap calculates h (L) such that (A (A < = if
G,u.v Pp and (h (h))), 0 otherwise. As layer L + extracts the L-th component of the feature vector, the result follows.
Remark A. We note that in Barceló et al. 3. it is shown that a more expressive graded modal logic (with more expressive modalities) can be captured by R-MPNNs in the context of single-relation
23

---

graphs. It is by no means obvious that an adaption of this logic to the nulti-relational case is captured by our C-MPNNs. We leave as an open problem find more expressive logics that can be captured by C-MPNNs.
A.5 Proofs of the results from Section 5.3
First, recall the definition of rawlg. Given knowledge graph G EV, R, c, we have
rawll ( (u, 2) - n7(u v), rawl2 ((+1)) (u, - 100--(rras (rawll) (u, v), El (rawll (u, w): w ENG()) E R)B)
Note that rawlz, and hence C-MPNNs, are one-directional: the neighborhood. (G only considers facts in one direction, in this case, from neighbors to v. Hence, a natural extension is to consider bi-directional neighborhoods. Fortunately, we can define this extension by simply applying the same test rawli to knowledge graphs extended with inverse relations. We formalize this below.
For test T, we sometimes write T(G, v), or T(G, v) in case of unary tests, to emphasize that the test is applied over G. and T(G) for the node/pairwise coloring given by the test. Let G' = (V, E, C,T) be knowledge graph. We define its augmented knowledge graph to be G = (V, E R C, 1),, where Rt is the disjoint union of R and fr r E R), and
E EU (r (v,u) | r(u, v) E E, u + v).
We define the augmented relational asymmetric local 2-WL test on G. denoted by rawl,.. as rawl: (1) (G, u, = rawl 2 (G+ u, v),
for all 2 0 and u, v. V. As we show below, rawlž is strictly more powerful than rawl2. Proposition A.17. The following statements hold:
1. For all t 2 0 and all knowledge graphs G, we have rawl (1) (G) 3 rawl, (G).
2. There is a knowledge graph G and nodes u, v. u, such that rawl. (1) (G, + rawl (1) (G,
(Gatt)))G,,,)) vl,, v²) but rawl," (4) (G,u, u,,) rawl, (1) (G, v') all 1 121 1.
Proof. To prove rawl. (G) 3 (G) first, we consider induction on iteration f. The base case for I = 0 trivial by the assumption, so is enough to consider the inductive step. We need to show that for some k.
rawl) (k+1) (u, v) = rawlt (k+1) (k-1)) (u',v))
( = rawl (u, v) = rawl (t (u', v')
By the definition of rawl; (k+11) (u, w), (1tt) (u', o') and the injectivity of r, holds that rawlt (k) (u, r)) = rawl; (k) (u',
(1++1)
(A: (rawt) (A) x)) x E (c)) = (rawl) (k) (u', x ,z),, r') | ENNO)) e E
Because all inverse relations r- are newly introduced, so it impossible to be mixed with r, we can split the second equation into the following equations:
(rawtt (M) (u, x), I (G))),, E RD = (rawl) (K) (ul,z'),,") a E (N) E R} if (rawit (K) (u, v).r y W, (v), r E RD = (rawl) (k) (ul.vv),''") y E ENr (v'), E R}
By the inductive hypothesis and unpacking the first equation, we can further imply that
{ (rawll r) E &NG(u), r E RD = (rawwl (u', 2'),,')) I a' e eNr( e R3
Thus, By definition of raw!!
(I+1)) (*+1)) (u, w), rawl (++1))(((,)
holds that rawl (k+1) (u, v) rawl! (k+1) (u', v²)
(u', (''''') v²)
24

---

For the counterexample, we consider a relational graph with two types of relation G' (V', E", R², c, n) such that V== = [u, fu n'}. E' (ri u), r2(v', u]}. and R' (21, Let the
initial pairwise labeling y for node pairs (u, v) and (u', v) satisfy rawl; (0) (u, u) rawl? (0) and rawll (u, v) rawll (u, o'). For such graph G", we consider node pair (u, and (u, r¹). For rawl,) where t 2 0, we show by induction that rawl?) (u, v) = rawl," (u, v'). The base case is trivial by assumption. The inductive step shows that by the inductive hypothesis,
(u, v')
rawl? (1+1) (u, u) (rawwl) (1) (u, v): (())
Trrawl22 ( (u, 2'), (
= rawl!--//
On the other hand, we have
rawly" (1) (u, 0) = (rawl) (0) u)) ( (rawl) ' r),r() A rawl) (1)
(u, v') = Trawl)) (0) (u, 2'), (rawl) (0) (I, (5)))
We can also extend C-MPNNs with bi-directionality in an obvious way, obtaining augmented C- MPNNs. By applying Theorem 5. to the augmented graph G+, we obtain the equivalence between augmented C-MPNNs and the test rawl." directly. In turn. Proposition A.17 implies that augmented C-MPNNs are strictly more powerful that C-MPNNs in distinguishing nodes in a graph.
Recall the definition of rwlz. Given knowledge graph G = (V, F,, R. n), we have
rw15+ Dw, =r(wll]) (u, v),, If (rwll) (w,, u),r) E (N()), E R)B.
[ (rwll] w)) | w ENG()), R)H)
We define the augmented version nwla in an obvious way, that is,
rwt) (1) (G, u, v) = rwll" (G+ v,,
for all 2 0 and u, V.
We will drop the notation of G during the proof when the context is clear for simplicity.
Proposition A.18. For all 2 0 and all knowledge graph G, let rwl! (G) rawl, (0) (G). The following statements hold:
1. For every t > 0, it holds that rwl (G) I rawl (G).
2. There is knowledge graph G and pair of nodes (u, v) and (u', v²) such that rawl, u, (G, u, o rwnl) (G, o').
rawl (G,u',
(G, u', v') for all t 2 but (wl()GGG (G,
(1) (G) and proceed by induction on f. The base case for t = 0 trivial by assumption. For the inductive step, given that we have rwilkt?) (u, v) r (f++)(((, by the definition of rw1fk++1)( (1,
(t) Proof. First, we show rwl! (G) = rawl
(u', (a'','' v²).
v) and rwnl (1+ (u', v'), and as 7 is injective, it holds that
rw)l") (u, v) rw/l (u',e")
I (rww) (k) (z, v).r) x N.)), R3 (((mll (x', r'),)') 1 e (N)()) e R} I (n x).r) x ENN,(,)) R3 = (((wl (b) (u', x'), r') o (N), e R} (2)
Now, by the inductive hypothesis we have rawll the last equation by applying the inductive hypothesis again after unpacking the multiset. This results
(h) (u, v) = rawl! (u', ,'). We can further transform
{ (rawl) (k) 2). NNC())) RD (1) (
(u', o (N)( RD
25

---

u
Figure 3: Graph G" as the counter-example in Proposition A.18
It is also shown in Proposition A.20
prove rawly (9) (u, v) rawlž" (f) (u', v') for all 2 0 but rwl. (u, v) o r (u',e").
x
u
12
Figure 4: Two counterexamples shown in Proposition A.17 and 1.19
The left graph G' is to show raw12 (1) (u, v) " (u', 2²) for all t 2 but rawl," (2) (u, v) * rawl (1) (u', vf), whereas the right
graph G" is to show rwl. (u, v) = rwl2 (u', e') for all & 2 0 but rwl, (1) (u, v) & rwl (1) (u', v').
Thus, holds that rawl, (+ (u, v) = rawll fa (u', v') by definition of fawl? (u, v) and rawl (8+1)
(w,,"))
For counter-example, we show the case for 2 Consider a relational graph G' C"=(V', E", , R, c, n) such that V = {u, u', v, E' {r(x, u')}, and R {r} with the initial labeling v for node pairs (u,r) and (u', v) satisfies rw! (u, v) = rwl, (ul v) and rawl,, (u, v) rawl, ( v). For such graph G", we consider node pair (u, v) and (w', v). For rawl! where 2 O, we show by induction (t) (u, v) rawl?" (u', .)). The base case is trivial by assumption. The inductive step shows that by the inductive hypothesis:
that rawll")
rawl (6+1) (u, u) = <rawwl? (u, v). (())
-(rawl 110 (u', o),, f
rawll ( (u',u)
On the other hand, we have
nwl!") (u, v) =(rwl))) (u, v), KB. (t)
# rwl2 (1) (u, 2') = T(rw1))) (u, v'), [nwi, (0) r)).
Proposition A.19. For all 2 0 and all knowledge graph G, let rwlj (0) (G) = rw (G). The following statements hold:
1. For every > O, rwt) (1) (G) - rwil (G)
2. There is a knowledge graph G" and pair of nodes (u, v) and (u', such that rwol (G" u,, mw!! (G", w/, v').frr all 2 but rw/ (G" u, v) + rwl, (w) (t)("" wi, v').
Proof. As before, we first prove rwl, (G) I rwlz(G) by induction on iteration The base case for t = 0 is trivial by the assumption. By the inductive hypothesis,
nwl (u,w) rwl,
(u', (
rwlb"((,,)) (u, -rwl(((('' ('',v')
26

---

for some k. Thus, assuming mwl (k+1) (u, v)
mul 1 (u', e'), by the definition of (u, v) and rwt, (k+1) (u', v') and by the injectivity of r, it holds that
rwlz (k+1)
ml) (k) (u, u) mwl (k) (u',
(nwiz (k) v). (E) R [rwnlz (k) (a', (e',)"),))) o' eNTW)) ((rwl) (K) (u, x), N;),
[rwwl ( (1', (u',=)) | ENTW),
By the similar argument in proving rawl 3 rawl2, we can split the multiset into two equations by decomposing (u) = (u) UN (u) and N.. (v) ) (o UN, (v). Thus, we have
[((wl) (1) (z, a Ne), RD E (rwi) (1) (z',0') v'),"") a' E NN E RB
& (rwlz (K) (v. I (w), R] [((wl) (8)
(1/ v'), r' 1 ENp-(())) (w)), E RD
[(rwl2 (1) z)) x E RB [(rw)) (8) (ul ,'), i'' E (o) RB
( E RD (rwl (8) (ul v'),''))))))))))) / E AN (v)), e R By the inductive hypothesis and unpacking the first and the third equations, we can further imply that
{ (rwil (M) (u,
rwlg (w, v) rw!! (u',
If (nmw) (z, v) EN)(u),, R] {(mwl) (x', ('),)) of (N, RD If [rwll]
(K) x).r) ENN())), RD ((wwll (u', a')r" a (N' e R)
This would results in rwl, (wit+tl((u (u, = mwly rw/ttt) (u', e²) by the definition of rwl, rw!! (
ww(++11 ( v) and
For the counter-example we consider a relational graph G" (V", E" R", c. 1) such that V 2²)), and R" = (ri,r2). For such graph G", we set the initial labeling for node pairs (u, v) and (w', v') to satisfy rwtj (0)
{u, u', v, v', 2, 2'}, E" = (ri
(u, u) = rwl. (0) (ul, v') and rw!! (u, v) rw/g (0) (ul, v'), For such graph G", we consider node pair (u, v) and (u', v²).
Consider rw!!" where 2 O, we show by induction that rwl, (u, v) = rwl, (u',v'). The base case is trivial by assumption. The inductive step shows that by inductive hypothesis,
rw((-1)) 1) (u, v) =(rwl,)) (u, v), ( (u/n""((/, (u/, H.B. (.))
T(rwl]?)
rw
On the other hand, we have
rwtj (1)
(u, v) = T(rWl) (0) (u, v), &l (nwl) (0)
(z, (t,,),,T)B: (D)
# rw/t (1) (u', = -(rwlt (0) (u', v'), , &l (rwlt (0)
(z', ('),) )) (T)
Proposition A.20. For all 2 and all knowledge graph G. let rwl, (0) (G) rawl (0) (G), then the following statement holds:
I. There is knowledge graph G and pair of nodes (u, v) and (u', v²) such that rwlp (G, u, =
(1) (w2, v'',"').ooo all I. 2 but rawl, (G, v) & rawl)" (1) (G, w')
2. There is a knowledge graph G' and pair of nodes (u, v) and ('),v') such that (f (G', u, v) = rawlz (G', ul, vf) for all 2 0 but rwfl (G', u, v) # mwll) (G', ul, w').
Proof. To show (wlz(G) does not refine rawl, (G), we consider a relational graph G = (V, F, R, c, such that V = {u, u', o', x'), E [ri(v, T2 x' æ')). and R [ri,72) We let the initial
27

---

u
u
r2
Figure 5: Counterexample shown in Proposition t 2 0 but rawlz (1) (u, v) rawlz" (u', v').
A.20 prove rwly (u, rwl2 rwl2" (u', ("(,',")) for all
labeling ry for node pairs (u, v) and (u/, r²) to satisfy "w, (u,e) v) = rwl (u', v²) and rwl? (u, v)
rwll" (u', w²). For such graph G, we consider node pair (u, v)) and (u', For rwl, where 2 0. we show by induction that rwl? ( (u, v) = rw!! (u', v'). The base case trivial by assumption. The inductive step shows that by the inductive hypothesis,
rw/2 (t (u, T(rwl?" (u, 0.B
-T(wll?)) (m/, o'), H.D. (CB)
(w/,
On the other hand, we have
rawl (1)
(u, u) = T(rawl3 (0) (u, v), (rawl) (0) zu, (u. rT)
* rawl. (1)
(u, v') = T(rawlz (0) (u', v²), &l (rawl, (0) (u', .x') re),rr)
Finally, to show rawl." does not refine rwlg, we demonstrate the case for t 2 0. Consider a relational graph G² -V', E", R², c, 17) such that V {u, u/, v, E" {r(x, w')}, and R' {r]. We let the initial labeling 17 for node pairs (u, and (u', satisfy rwl. (u, v) = rwl, (0) (u', v) and
rawlž (0), ("u v) = rawl; (u', v). For such graph G', we consider node pair (u,, v) and (u', v). For
rawl. (1) where 2 0, and show by induction that rawl;- (u, v) = rawl;" (1) (ul, v). The base case is trivial by assumption. The inductive step shows that by the inductive hypothesis,
rawl (t+1), (u, v) = (raall (1)
(u, v), (
Trraw,," (1) (1l, v), (.)))
rawl, (++1) (1)
On the other hand, we have
nwl 11 (u, v) = T (u, v). KB.
# rwl) (1) (u, v') = =(rw!) (u, 0'), (rwl, (z, r)),))) (
Note that the counter-example graph G' here is identical to the one Proposition A.18
B Runtime analysis
In this section, we present the asymptotic time complexity of R-MPNN, C-MPNN, and labeling- rick-based relation prediction model GraiL [30] in Table 3 taken from Zhu et al. [40]. We also consider 2-RN the neural architecture from Barceló et al. 4 corresponding to rwl2 to showcase an example higher-order GNNs. We present both the complexity
a single forward pass of the model as well the amortized complexity of a single query better reflect the practical use cases and the advantages stemming from parallelizability. To avoid confusion, we take CompGCN B2 as the example of R-MPNN, and basic C-MPNN, since specific architecture choices will impact the asymptotic complexity of the model.
Notation. Given knowledge graph G = (V, F, R, c). we have that [V] [8], [R] represents the size of vertices, edges, and relation types, respectively. d the hidden dimension of the model, and T' the number of layers in the model.
28

---

Table 3: Model asymptotic runtime complexities. Observe that the amortized complexity of 2-RN becomes obselete by the fact that its forward pass being prohibitive in practice (quadratic in (V).
Model
Complexity of a forward pass
Amortized complexity of a query
R-MPNNs
O(T(EE|++ ( [V(2))
O(T
|EId
+ de
[R|lV] + d))
C-MPNNs
[[[[E)d+[][d)) O + [V]))) ( (V)
O V + d)))
Lid
GralL
( d + [V [())))
2-RN
O(T( | + [R] + d))
[E
d²
Runtime of C-MPNNs. Let us note that C-MPNNs subsume NBFNets. Indeed, if we consider C-MPNNs without readout and set the history function as f() = O. we obtain (a slight generalization of) NBFNets, stated in the paper. In terms of the runtime, C-MPNNs and NBFNets are comparable: even though the readout component of C-MPNNs incurs a linear overhead, this is dominated by other factors. Thus, as shown in Lemma 2 of Zhu et al. 40,. the total complexity for a forward pass is O
E d + [V] to compute V queries at the same time, resulting an amortized complexity of
O(T( E + d² See Zhu et al. 40 for detailed discussion and proof.
Comparison with R-MPNNs. As directly carrying out relational message passing in R-MPNN for each triplet costly, a common way to carry out link prediction task is to first compute all node representations and then use a binary decoder to perform link prediction. This would result in O + [V(d)) for a complete forward pass. Consequently, we obtain [V] triplets, and since passing through binary decoder has complexity of Odd) we have that the amortized d
188d + [ejll| + d)). Although the complexity of forward pass for R-MPNN and C-MPNN are the same, we compute R||VV22 queries with R-MPNN but only [V] queries with C-MPNN, resulting difference in amortized complexity of a single query. However, as discussed in Section 4 this comes at the cost of expressivity.
complexity for each query is ((T( [RIIVE
Comparison with the architectures using labeling trick. GralL. is an architecture using labeling trick and we focus on this to make the comparison concrete. In terms of runtime, architectures that rely on the labeling trick are typically slower, since they need to label both the source and the target node, as we state in Section[4 [ This yields worse runtime complexity for these models, and particularly for Grall 9 with an amortized complexity of a query being the same as the one for a forward pass, that is, O E) d2 + [V]d))). In C-MPNNs, we only label the source node which allows parallel comparison for all queries in the form quu, ?): a single forward pass would compute all hidden representations of these queries. With the labeling trick, [V] forward passes need to be carried out as each time, both source u and target v need to be specified. See Zhu et al. [40] for detailed discussion and proof.
Comparison with higher-order GNNs. Regarding higher-order GNNs, we take 2-RN, the neural architecture from Barceló et al. [4] corresponding to rwly. These higher-order models require O([V] + [V(2=2) in each layer (assuming each message function takes (dd) as before) to update all pairwise representations in a single forward pass, which is computationally prohibitive in practice. This makes the study of the amortized complexity obselete, but we provide an analysis for the sake of completeness. Similar to R-MPNN, we need an additional query-specific unary decoder for the task of link prediction on knowledge graphs, resulting in ((d) complexity overhead. The
amortized complexity of single query is thus ( [gld
+ d2
+ d)). [
[
C Experiments on inductive link prediction
C.1 Details of the experiments reported in Section
In this section, we report the details of the experiments reported in the body of this paper. Specif- ically, we report the performance of some baseline models (Table 4. dataset statisties (Table 5) hyperparameters (T), and the number of trainable parameters for each model variation (Table
'Comparing to C-MPNN, the complexity for MsG, is different because GralL utilizes RGCN relational message passing model, which needs (dd) for linear transformation in its MSG,.
29

---

Table 4: Inductive relation prediction results. We basic C-MPNN architecture with AGG sum, MsG = Msc,,, and INIT INIT² with no readout component. All the baselines are taken from the respective works.
Model
WN18RR
FB15k-237
vl
v2
v3
v4
vI
v2
v3
v4
NeuralLP
35
0.744
0.689
0.462
0.671
0.529
0.589
0.529
0.559
DRUM
(25
0.744
0.689
0.462
0.671
0.529
0.587
0.529
0.559
RuleN
200
0.809
0.782
0.534
0.716
0.498
0.778
0.877
0.856
Grall 30
0.825
0.787
0.584
0.734
0.642
0.818
0.828
0.893
C-MPNN
0.932
0.896
0.900
0.881
0.794
0.906
0.947
0.933
Table 5: Dataset statistics for the inductive relation prediction experiments. #Query is the number of queries used in the validation set. In the training set, triplets are used as queries.
Train & Validation
Test #Triplet
Dataset
#Relation
#Nodes
#Triplet
#Query*
#Nodes
#Query
01
2,746
5,410
630
922
1,618
188
10
6,954
15,262
1,838
2,757
4,011
441
WN18RR
03
12,078
25,901
3,097
5,084
6,327
605
9
3,861
7,940
934
7,084
12,334
1,429
01
180
1,594
4,245
489
1,093
1,993
205
FB1 15k2-237
1/2
200
2,608
9,739
1,166
1,660
4,145
478
03
215
3,668
17,986
2,194
2,501
7,406
865
074
219
4,707
27,203
3,352
3,051
11,714
1,424
Table 6: Hyperparameters for inductive experiments with C-MPNN.
Hyperparameter
WN18RR
FB15k-237
(epth(T)
6
6
GNN Layer
Hidden Dimension
32
32
Depth
2
2
Decoder Layer
Hidden Dimension
64
64
Optimizer Learning Rate
Adam 5e-3
Adam
Optimization
5e-3
Batch size
8
8
#Negative Samples Epoch Adversarial Temperature
32
32
Learning
20
20
1
1
Table 7: Number of trainable parameters used in inductive relation prediction experiments for C-MPNN architectures with INIT initialization..
Model architectures
WN18RR
FB15k-237
AGG
MSG,
v1
v2
v3
v4
v1
v2
v3
v4
sum
MsG!
132k
144k
157k
132k
2,310k
2,564k
2,755k
2,806k
MsG
21k
22k
22k
21k
98k
107k
113k
115k
Sum
MSG
128k
141k
153k
128k
2,240k
2,488k
2,673k
2,722k
PNA
MsG.
199k
212k
225k
199k
2,377k
2,632k
2,823k
2,874k
PNA
MSG
89k
89k
90k
89k
165k
174k
181k
183k
PNA
MSG
196k
208k
22.1k
196k
2,308k
2,555k
2,740k
2,790k
30

---

All of the model variations minimize the negative log- likelihhodd of positive and negative facts. We follow the partial completeness assumption [TO] by randomly corrupting the head entity or the tail entity to generate the negative samples. We parameterize the conditional probability of a fact q(u, v) by p(u u. q) (f (lu.g)) )) where is the sigmoid function and f is 2-layer MLP. Following RotatE [2),, we adopt self-adversarice negative sampling by sampling negative triples from the following distribution with as the adversarial temperature:
L(v u. log p(v u, 4)
Σ Wia log(1 plu! u/, 4))
where 1: is the number of negative samples for positive sample and (u/, q, u/) is the i-th negative sample. Finally, w; is the weight for the i-th negative sample, given by
log(1 - p(u u )
Wioo == Sofumax
a
C.2 Experiments for evaluating the effect of initialization functions
Initialization f'unctions (Q3). We argued that the initialization function INIT(U, v, 9) needs to satisfy the property of target node distinguishability to compute binary invariants. To validate the impact of different initialization regimes, we conduct a further experiment which is reported in Table with the same experiment settings as in Section 6 In addition to the initialization functions INIT', 1 INIT?, INIT3 defined in Section 4.1 we also experiment with simple function INIT which assigns to all nodes. As expected, using INIT initialization, results in very sharp decrease in model performance in WNISRR, but less so in FB 53-2377 Intuitively, the model suffers more WN1SRR since there are much fewer relations, and it is harder to distinguish node pairs without an initialization designed to achieve this. Perhaps one of the simplest functions satisfying target node distinguishability criteria is INIT 1 1, which pays strong results, showing that even the simplest function ensuring this property could boost the model performance. Interestingly, the performance of models using INIT' match exceed models using INIT?, even though the latter additionally has a relation-specifee learnable query vector. Note, however, that this shall not undermine the role of the learnable query relation: integrating the learnable query vector either in the initialization function or in the message computation function seems to suffice.
respect to the target query relation. Empirically, INIT' achieves
Table 8: Inductive relation prediction of C-MPNN using AGG sum, MsG,- MsG S(() L and different initialization methods.
Initialization
WN18RR
FB15k-237
[NI v)
vl
v2
v3
v4
v1
v2
v3
v4
INIT (u, v.
0.615
0.715
0.811
0.654
0.777
0.903
0.894
0.910
INIT (u, 2,
0.932
0.894
0.902
0.883
0.809
0.927
0.944
0.911
INIT (u, v.
0.932
0.896
0.900
0.881
0.794
0.906
0.947
0.933
INIT3 (u, 9)
0.934
0.890
0.894
0.877
0.804
0.924
0.941
0.944
Random initialization (Q3). The idea of random node initialization known to lead to more expressive models []. Inspired by this, we incorporate varying degrees of randomization to the initialization, satisfying the target node distinguishability property in expectation. The key advantage is that the resulting models are still inductive and achieve nontrivial expressiveness gain over alternatives. In this case, the models with INIT' perform closer to the models with INIT?, but we do not a particular advantage on these benchmarks.
DD Experiments on transductive link prediction
We further conducted transductive link prediction experiments to empirically validate that C-MPNNs more expressive than R-MPNN via the abstraction given by rawlz and rwl,, respectively (Q4).
31

---

Table 9: Transductive knowledge graph completion task of C-MPNNS and R-MPNNS on WNI8RR and FB15k-237. Here, C-MPNN-basi refers to basic C-MPNN model without readout.
WN18RR
FB15k-237
Model class
Architectures
MR
MRR
Hits@ 10
MR
MRR
Hits @ 10
RGCN
3069
0.367
0.405
210
0.205
0.387
R-MPNNs
CompGCN
3590
0.433
0.519
217
0.334
0.514
PeuralLP
0.435
0,566
0.240
0.362
C-MPNNs
DRUM
0.486
0.586
0.343
0.516
C-MPNN-basic
687
0.534
0.643
121
0.400
0.583
Table 10: Dataset statistics for transductive experiments on WNI8RR and FB15K-237.
#Triplet #Valid
Dataset
#Nodes
#Relation
#Train
#Test
WN18RR 40,943 FB 15k-237
11
86,835
3,034 17,535
3,134
14,541
237
272,115
20,466
Table 11: Hyperparameters for transductive experiments on FB15k-237 and WNISRR with C-MPNN.
Hyperparameter
WN18RR
FB15k-237
(2"th
6
6
GNN Layer
Hidden Dimension
32
32
Depth
2
2
Decoder Layer
Hidden Dimension
64
64
Optimizer Learning Rate
Adam 5e-3
Adam
Optimization
5e-3
Batch size
8
8
#Negative Sample
32
32
Learning
Epoch Adversarial Temperature
20
20
1
1
D.1 Experiments on WN18RR and FB15k-237
Datasets. We use two benchmark datasets for transductive link prediction experiments, namely WNI8RR [3I] and FB15k-237 (9), with the provided standardized train-test split. Similar to the inductive relation prediction experiments, we augment the fact r(u, v) with its inverse fact y (v. u). The detailed data statisties are shown in Table I0
Implementation. For basic C-MPNN without readout (denoted as C-MPNN in Table 9 all pyper-parameters used reported in Table [T] and we adopt nayer-normalization [2] and short-cut connection after each aggregation and before applying ReLU. We also discard the edges that directly connect query node pairs prevent overfitting. For RGCN, we dimension of 100. We consider the same basis-decomposition trick with basis number equal to 30. In addition, we train the model with a learning rate of 0.1 and a dropout rate of 0.2, using Adam optimizer for 10,000 epochs. For CompGCN, we use three layers, each with hidden dimension 200, and adopt distmult scoring function well as element-wise multiplication as composition function. During the training process, we consider a learning rate of 0.001 and a dropout rate of 0.1, using Adam optimizer for 500 epochs. Additionally, since there are node features for both of the datasets, we initialize node representations using learable embeddings with Xavier initialization for RGCN and CompGCN. We take the results of NeuralLP from Yang et (35), and the results DRUM from Sadeghian et al. 255, respectively. The best checkpoint for each model instance is selected based on its performance on the validation set. All experiments are performed on one NVIDIA V100 32GB GPU.
layers, each with hidden
32

---

Evaluation, We consider filtered ranking protocol 6 with negative sample per positive triplet. and report Mean Rank(MR). Mean Reciprocal Mank(M and Hits @ 10 for each model. We also report averaged results of five independent runs for all experiments.
Results. From Table it is evident that models under the class of C-MPNN consistently outperform R-MPNN models across both datasets and all evaluation metrics, with only one exception on FB 15K- 237 with NeuralLP. This aligns with our theoretical understanding, as C-MPNN models are inherently more expressive than R-MPNNs. In particular, the C-MPNN-basic model stands out by achieving the lowest MR and the highest values for both MRR and Hits@@ 10, surpassing all other models by significant margin, underscoring its efficiency and robustness in transductive knowledge graph completion tasks.
D.2 Experiments on biomedical datasets
To compare R-MPNNs and C-MPNNs on large-scale graphs, we carried out additional transductive
knowledge graph completion experiments on biomedical datasets: Hetionet [5] and ogbl-biokg [6].
Datasets. Hetionet [15] is a large biomedical knowledge graph that integrates data from 29 different public databases, representing various biological connections and associations, and ogbl-biokg is large-scale biomedical knowledge graph dataset, developed as a part of the Open Graph Benchmark (OGB) [16] suite. We have used the provided standardized train-test split for both datasets and similarly augmented every fact r(u, v) with its inverse relation r (u, v). We present the detailed dataset statistics in Table
We study the basic C-MPNN without readout, referred to as C-MPNN in the Table 12 the epoch number is set to due to the datasets being larger and denser, leading to longer exccution times for C-MPNN. All byperparameters used for C-MPNN are reported in Table [4 and we adopt noyaalaoomaiiioioonn (2] and short-cut connection after each aggregation and before applying ReLU, We also discard the edges that directly connect query node pairs. For RGCN, we consider batch size of 65536, learning rate of 0.001, and 100 epochs for both datasets. On Hetionet, use a hidden dimension size of 200, and a learning rate of 0.001 across 4 layers. On ogbl-biokg, consider dimension size of 500, and dropout rate of 0.2 across 2 layers. For CompGCN on Hetionet, the parameters include a batch size of 65536, 100 epochs, a dimension size of 200, learning rate of 0.01, and single layer. We adopt distmult scoring function and element-wise multiplication as a composition function. On ogbl-biokg. CompGCN results cannot be reproduced to the best of our effort due an out-of-memory (OOM) error. The best checkpoint for each model instance is selected based on its performance on the validation set. All experiments are performed on one NVIDIA V100 32GB GPU. addition, since there are no node features for both of the datasets, we initialize node representations using learnable embeddings with Xavier initialization for RGCN and CompGCN.
Implementation.
Evaluation. We consider filtered ranking protocol 6 but restrict our ranking to entities of the same type. With each positive triplet, of Mean Reciprocal Rank(MRRR, Hits 1, and Hits@ 10 over five independent runs for each model.
32 number of negative samples and report the averaged results
Results. From Table 12 it is evident that C-MPNN outperforms R-MPNN on both datasets by large margin, despite the challenges posed by the large and dense nature of biomedical knowledge graphs. These results reassuring as they have further consolidated our theory. showing that the expressivity gain of C-MPNNs compared to R-MPNNs has a significant impact on rorl-world biomedical datasets.
Table 12: Transductive experiments on biomedical knowledge graphs. We use basic C-MPNN architecture with AGG = sum, MsG Msa,, and INIT = INIT with no readout component. 00M stands for out of memory.
Hetionet
ogbl-biokg Hits@1
Model
MRR
Hits@1 1
Hits@ 10
MRR
Hits@
RGCN
0.120
0.067
0.228
0.636
0.511
0.884
CompGCN
0.152
0.083
0.292
00M
00M
00M
C-MPNN
0.479
0.394
0.649
0.790
0.718
0.927
33

---

Table 13: Dataset statistics for transductive biomedical knowledge graph completion.
#Triplet #Valid
Dataset
#Nodes
#Node Type
#Relation
#Train
#Test
Hetionet
47 00.31
11
24
1,800,157
225,020 162,886
225.020 162,870
ogbl-biokg
93,773
5
4,762,677
Table 14: Hyperparameters for the transductive experiments on biomedical knowledge graphs with C-MPNN.
Hyperparameter
Hetionet
ogbl-biokg
Depth(T)
GNN Layer
Hidden Dimension
32
32
Depth
2
2
Decoder Layer
Hidden Dimension
32
32
Optimizer
Adam 2e-3
Adam
Optimization
Learning Rate
2e-4
Batch size
64
8
#Negative Sample
32
32
Learning
Epoch
1
1
Adversarial Temperature
0.5
E Evaluating the power of global readout on synthetic dataset
constructed a synthetic experiment to showcase the power of global readout (Q5).
Dataset. We proposed a synthetic dataset TRI-SQR, which consists of multiple pairs of knowledge graphs in form (G1, G2) s.t. G1 (V1, E,, R, c1), G2 (V2, Eg, R, 02) where {ro. r2) For each pair, we constructed as follows:
1. Generate an Erdos-Reny' graph Gui with 5 nodes and random probability p. We randomly select one of the nodes as the source node u.
2. G1 is constructed by disjoint union Ginit with two triangles, one with edges relation of rı, and the other with r2. The target query is r3(u, v) for all triangle with an edge relation of r1-
3. Similarly, G2 is constructed by disjoint union another copy of Gini with two squares, one with edges relation of and the other with r2. The target query is ra(u, v) for all in square with an edge relation of r2-
One example of such a pair can be shown in Figure We generate 100 graph pairs and assign 70 pairs as the training and the remaining 30 pairs as the testing set (140 training graphs and 60 testing graphs). In total, there are 490 training triplets and 210 testing triplets.
Objective. For all node Ginit we want higher score for all the links ro(u, v) if either e is in triangle consists of r1 relation or v For negative sampling, choose counterpart triplets for each graph, that is, take ro(u, v) for all v in a triangle with an edge relation of 72 in G1 and in a square with an edge relation of r1 in Gz-
square consists of 72 relation, and lower score otherwise.
Model architectures. We have considered two model architectures, namely C-MPNNs with INIT INIT2 AGG sum, MsG Msc?, and ft) without sum global readout:
h v/uug 11 1 Zzg:
h. (++1) (W(0) (h
Σ
Σ
(h)) (hof zg)))
PER wE..
34

---

11
G1
11
F2
G2
Figure 6: Construction of graph pair in TRI-SQR for global readout
and the same C-MPNN architecture with sum global readout:
h (0)
1u=v *
Zog
h (++1) v/lug
a (w((((
(h
(e) (hojunq
Σ
Σ
MsG 2 (h wlu.g kn)) W
(0)
Σ
(c) h
(E)
Design, We claim that C-MPNNs with sum readout can correctly predict all testing triplets, whereas C-MPNNs without readout will fail to learn this pattern and achieve 50% random guessing. Theoretically. the TRI-SQR dataset is designed in such a way that any R-MPNN model assigns identi- cal node representations nodes in triangles and squares with the same relation type. Consequently, any C-MPNN model without global readout will be unable to determine which graph between G₁ and G2 in the graph pair is being predicted, making challenging to learn the conditional representation hulv.g. However, we anticipate that a C-MPNN model with sum readout can differentiate between G1 and G2 in each pair, it can access global information like the total number of nodes in the graph. This allows it to accurately identify the graph being predicted in the graph pair, even when the representations of the triangle and square with the same relation are identical. As result, it can learn the target rules and achieve 100% accuracy.
Experiment details. We configure each model variant with four layers and 32 hidden dimensions per layer. We set learning rate of le-4 for both models and train them for 500 epochs. Empirically, find that C-MPNN with global sum readout achieves 100% accuracy, while C-MPNN without global sum readout reaches 50% accuracy as random guesses, which consistent with our theoretical expectations.
35


Reviews:
[{"review_id": "wjArXSJHgj", "reviewer": "Reviewer_cjW9", "summary": "This paper explores the expressive power of several GNNs designed for link prediction in knowledge graphs. The authors propose a conditional message passing framework with various designs for each component, a generalization of NBFNets. They also prove that the proposed framework can match the expressive power of a relational Weisfeiler-Leman algorithm. The experimental results demonstrate the impact of different model choices.", "questions": "Please refer to the weakness.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides a theoretical understanding of some relational GNNs for knowledge graphs, such as NBFNets.\n2. The proposed C-MPNN is reasonable, generalizing GNNs that can compute pairwise representations.\n3. The authors study the effect of different model architectures, adding depth to the exploration of GNNs.", "weaknesses": "1. Using relational asymmetric local 2-WL (rawl2) to measure the expressive power of C-MPNN is a little awkward. The definition of rawl2 is quite similar to C-MPNN, leading to potential confusion.\n2. The experiments do not verify some theoretical findings, focusing mainly on different choices of model design. Certain theoretical discoveries, such as logical characterization, are not confirmed.\n3. The experiments are primarily conducted on two datasets with differing data splits, leading to inconsistencies. More datasets and deeper analysis may be necessary to solidify the findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and your comments on our paper. We address each below.\n\n>“Using relational asymmetric local 2-WL (rawl$_2$) to measure the expressive power of C-MPNN is a little awkward. The definition of rawl$_2$ is quite similar to C-MPNN, leading to potential confusion.”\n\nThe color refinement algorithm rawl$_2$ is introduced to exactly capture the theoretical expressiveness of the corresponding neural architecture C-MPNNs. These algorithms are therefore closely related to each other, which can perhaps be better understood in analogy to the relation between the 1-WL algorithm and standard GNNs. Fundamentally, rawl$_2$ is a non-parameterized color refinement algorithm, whereas C-MPNNs is a class of neural networks with trainable parameters. In this sense, C-MPNNs can be viewed as a learnable, continuous, differentiable version of rawl$_2$. We are happy to elaborate further if this does not address reviewers' concerns.\n\n>“The experiments do not verify some theoretical findings, focusing mainly on different choices of model design. Certain theoretical discoveries, such as logical characterization, are not confirmed.”\n\nThere are two main conclusions which follow from the presented expressiveness study and logical characterization and are empirically validated in the appendix of the paper:\n\n1. It follows that C-MPNNs are more expressive than R-MPNNs via the abstraction given by rawl$_2$ and rwl$_1$, respectively. To empirically validate this, we conducted transductive link prediction experiments which are reported in Appendix B.3 (as part of the supplementary material). The presented results suggest a clear trend that C-MPNN has an overall better performance compared to R-MPNNs. These experiments are transductive, as R-MPNNs (i.e., R-GCN) only apply in this setup. \n1. It follows from the logical characterization that the addition of global readout yields more expressive power in the class of queries that can be captured. We conducted a dedicated synthetic experiment to validate this, which is reported in Appendix B.1.  C-MPNN model without readout achieved random accuracy on this task, whereas the C-MPNN model with readout solved this task almost perfectly. Please note that this is in addition to the experiments on real-world data which is presented in the body of the paper.\n\nWe wish to note that we prioritized inductive experiments in the body of the paper in order to validate the other aspects of the presented theory (i.e., the choice of history should not matter). We are happy to include more details regarding the experiments from the appendix if they need to be better highlighted.  \n\n>“The experiments are primarily conducted on two datasets with differing data splits, leading to inconsistencies.”\n \nWe are using the exact same data splits from the existing literature and our results align with the presented theory. It is therefore unclear to us where the inconsistency lies: could you please be more specific on what inconsistencies are presented in the paper so that we can clarify these?\n\n>“More datasets and deeper analysis may be necessary to solidify the findings.”\n\nWe would like to re-emphasize the experiments reported in the appendix of the paper. Following your feedback, we carried out additional experiments for transductive link prediction on biomedical datasets **Hetionet** and **OGB-Biokg** to further solidify the findings on diverse datasets. These are reported in Table 3 of **rebuttal.pdf** as part of our global response. These results are reassuring, as they show very similar trends to those observed in the other datasets. Please let us know whether these points clarify your concerns."}, {"review_id": "xl9E9W82gR", "reviewer": "Reviewer_kRBD", "summary": "The authors note that while GNNs are understood well in the context of simple graphs, there is a lack of comprehensive understanding when it comes to knowledge graphs. This study aims to systematically explore the use of GNNs in knowledge graphs, specifically in relation to the task of link prediction. The research includes a unifying view on different, seemingly unrelated models, potentially revealing new ones. The study evaluates the expressive power of different models using the relational Weisfeiler-Leman algorithm. The theoretical findings help clarify the advantages of some commonly used practical design choices, and these theories are supported by empirical validation.", "questions": "Can the author add more baselines?\n\nAlthough the authors have already provided two datasets, each with four different versions, I think this is adequate, so I have not listed it as a weakness. However, it would be good if the authors could include one or two additional datasets.\n", "limitations": "As the author mentioned, the method is limited to binary task such as link prediction.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I have read the appendix of the paper. The technical details are clearly articulated, and the proof statements are clear and persuasive.\n\nThe authors introduce conditional message-passing neural networks and define a relational Weisfeiler-Leman algorithm to substantiate that these neural networks can match the expressive power of this algorithm.\n\nThe initialization progress is interesting.\n", "weaknesses": "In the background section, the author first mentioned G = (V, E, R, c) while change it to G = (V, E, R, x) later. I know the author says it usually should be x instead of c. But can we directly use G = (V, E, R, x) at first to prevent confusion?\n\nMore GNN baseline method should be involved in the experiments.\n\nThe proof process is commendable, but could it be possible to draw a conclusion from it and incorporate it into the main text instead of the appendix?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and your comments on our paper. We address each below.\n\n>“In the background section, the author first mentioned $G = (V, E, R, c)$ while change it to $G = (V, E, R, \\mathbf{x})$ later. I know the author says it usually should be $\\mathbf{x}$ instead of $c$. But can we directly use $G = (V, E, R, \\mathbf{x})$ at first to prevent confusion?”\n\nWe understand the source of the confusion, but let us note that $G = (V, E, R, c)$ is indeed a more general definition compared to $G = (V, E, R, \\mathbf{x})$. This is indicated in the background section as follows: *“When $D=\\mathbb{R}^d$, we also say that $c$ is a $d$-dimensional *feature map*, and typically use $\\mathbf{x}$ instead of $c$”*. The differences between $G = (V, E, R, c)$ and $G = (V, E, R, \\mathbf{x})$ may appear rather subtle but they are important. In our context, we use $c$ to denote a discrete set of colors used in the WL test, whereas $\\mathbf{x}$ are the continuous features belonging to $\\mathbb{R}^d$ in the corresponding neural counterpart. We carefully distinguish between these two notations on knowledge graphs for mathematical clarity as the lack of such a notational convention can present problems. We will highlight this point to avoid the confusion of readers.\n\n>“More GNN baseline method should be involved in the experiments.”\n\nWe added more baseline methods from GraIL paper [1] which are reported in Table 1 of the **rebuttal.pdf** as part of our global response. We also provided the transductive link prediction baseline methods from DRUM paper [2], which are reported in Table 2 of the **rebuttal.pdf**.\n\n>“The proof process is commendable, but could it be possible to draw a conclusion from it and incorporate it into the main text instead of the appendix?”\n\nThanks for going through the proofs. We are glad you find the presentation of the technical content commendable. The key theoretical contributions are presented in terms of Theorem 5.1, 5.2, and 5.3 along with brief explanations. Figure 1 serves as a summary of all the lemmas presented in Section 5.3. We can elaborate these details further (with more space allowance): we are happy to add some discussions regarding the high-level ideas behind these proofs in the body of the paper. \n\n>“Although the authors have already provided two datasets, each with four different versions, I think this is adequate, so I have not listed it as a weakness. However, it would be good if the authors could include one or two additional datasets.”\n\nThanks for this suggestion! We agree that diverse datasets are beneficial to strengthen our point. Following your suggestion, we provide transductive link prediction experiments on two additional datasets: **Hetionet** and **OGB-Biokg**. The experiments are reported in Table 3 of **rebuttal.pdf** as part of our global response. The results are reassuring as they show very similar trends to those observed on the other datasets. Please let us know whether these points clarify your concerns. \n\n*[1] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. 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. NeurIPS, 2019.*\n"}, {"review_id": "ESinNqniYZ", "reviewer": "Reviewer_7NY6", "summary": "The paper investigates graph neural networks (GNNs) for link prediction in knowledge graphs. The authors propose a GNN that generalizes several existing techniques based on the labeling trick and NBFNets and investigate its expressive power by relating it to the Weisfeiler-Leman method and giving a logical characterization. Different design choices of the architecture are explored experimentally. ", "questions": "* How does the approach compare to NBFNets, architecture using the labeling trick, and higher-order WL-type GNNs regarding (i) accuracy and (ii) running time?\n", "limitations": "Limitations are addressed sufficiently.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* A highly relevant problem with various applications is addressed and neural architectures for related tasks are thoroughly analyzed, giving new theoretical insights. As the number of papers published in this area grows rapidly, it is of utmost importance to explain the advantage of practical design choices and to work out the benefits of specific architectures. The paper is a solid contribution in this direction.\n* The authors give a good overview of related work, including several recent results, and place their work well in the context of existing approaches. The paper continues recent work and generalizes it, which is a valuable contribution to fostering future work.\n* The paper is well-written and enjoyable to read; the presentation is on a high level.", "weaknesses": "* The experimental comparison focuses on the design choices of the proposed architecture but does not compare to existing works. This would be desirable, in particular, since higher-order GNNs subsume some of the techniques (as stated in the paper). The trade-off between efficiency and expressivity appears to be crucial but is neither investigated theoretically in terms of time complexity nor experimentally in terms of measured runtimes.\n* The presentation of conditional messages passing remains abstract. It would be helpful to come up with an illustrative example, if possible.\n\nMinor comments:\n* l176: $\\epsilon_u$ should be explained\n* l186: $\\mathbf{z}_q$ as argument of MSG should be just $q$ following the notation introduced earlier \n* l370: \"Thus, thus\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and your comments on our paper. We address each below.\n\n>“The experimental comparison focuses on the design choices of the proposed architecture but does not compare to existing works. This would be desirable, in particular, since higher-order GNNs subsume some of the techniques (as stated in the paper). The trade-off between efficiency and expressivity appears to be crucial but is neither investigated theoretically in terms of time complexity nor experimentally in terms of measured runtimes.”\n\nThanks for raising this. Following your suggestion, we present a time-complexity analysis for C-MPNNs and other inductive link prediction models in Table 4 of **rebuttal.pdf**. This also includes the amortized time per query which can better reflect the practical use cases and the advantages stemming from parallelizability. Regarding higher-order GNNs we consider the neural architecture from Barceló et al. [1] corresponding to rwl$_2$ (and mentioned in line 259 of our paper). This higher-order model requires $O(|V||E|d + |V|^2d^2)$ time in each layer to update all pairwise representations, and it cannot be parallelized, hence remains prohibitive in practice.  \n\n>“The presentation of conditional messages passing remains abstract. It would be helpful to come up with an illustrative example, if possible.”\n\nThe main difference from standard message passing stems from the conditioning on the source node, which we make explicit in our approach. We agree this is more intricate than standard message passing, and hence we provide a visualization of C-MPNN and R-MPNN in Figure 1 of **Rebuttal.pdf** with the following explanation: for the basic C-MPNN model, in order to compute a query fact $q(u,v)$, where $u$ is the source node and $v$ is the target node, we first initialize all node representations with the zero vector except the representation of the node $u$ which is assigned a learnable query vector $\\mathbf{z}_q$. Following the initialization, we carry out relational message passing and decode the hidden state of the target node $v$ to obtain the output, which yields the representation of $v$ conditioned on $u$. \n\n\n>“Minor comments: l176: $\\epsilon_u$ should be explained. ”\n\n$\\epsilon_u$ is explained in line 184: *“adding an error vector $\\epsilon_{u}$ sampled from $\\mathcal{N}(0,1)$ to the conditioned node's initialization”*. Here, $\\epsilon_{u}$ is a fixed perturbation given that node $u$ is chosen. \n\n>“Minor comments: …l186: $\\mathbf{z}_q$ as argument of MSG should be just $q$ following the notation introduced earlier. ”\n\nMany thanks for this! Indeed, this is a slight abuse of notation. We will pass $\\mathbf{z}_q$ as an argument to MSG on line 150, where this is first introduced to fix this.\n\n>“Minor comments: …l370: \"Thus, thus\".”\n\nThank you, we have corrected this.\n\n>“How does the approach compare to NBFNets, architecture using the labeling trick, and higher-order WL-type GNNs regarding (i) accuracy and (ii) running time?”\n\nWe answer your questions regarding (i) accuracy and (ii) runtime, separately for each model:\n- **Comparison with NBFNets**: Let us note that C-MPNNs subsume NBFNets. Indeed, if we consider C-MPNNs without readout and set the history function as $f(t) = 0$, we obtain (a slight generalization of) NBFNets, as stated in the paper. In terms of the runtime, C-MPNNs and NBFNets are comparable: even though the readout component of C-MPNNs incurs a linear overhead, this is dominated by other factors. In terms of the accuracy, the picture is more complex: our results show that the choice of history function is not critical, which is empirically confirmed: $f(t) = t$ and $f(t) = 0$ yields similar results (Table 1 of the main paper). On the other hand, the (uniform) logical characterization shows the theoretical benefit of using a global readout component: this is empirically observed on FB15K-237, where the model  using a readout component showed substantial gains (leading to state-of-the-art results) compared to not using a readout component (Table 2 of the main paper).\n- **Comparison with the architectures using labelling trick**: GraIL is an architecture using labeling trick and we focus on this to make the comparison concrete. In terms of runtime, architectures which rely on labeling trick are typically slower, since they need to label both the source and the target node, as we state in the paper *“... the Labeling Trick only applies when both the source $u$ and target nodes $v$ are labeled”*. This yields worse runtime complexity for these models, and particularly for GraIL: we report the runtimes in Table 3 of **rebuttal.pdf**. In C-MPNNs, we only label source $u$, which allows parallel comparison for all queries in form $q(u,?)$: a single forward pass would compute all hidden representations of these queries. With Labeling Trick, $|V|$ forward passes need to be carried out as each time, both source $u$ and target $v$ needs to be specified. In terms of accuracy, we added more baselines in **rebuttal.pdf**, including GraIL, showing C-MPNNs outperform these models. We will integrate these discussions to our paper.\n- **Comparison with higher-order GNNs**: Regarding higher-order GNNs we consider the neural architecture from Barceló et al. [1] corresponding to rwl$_2$, as we stated in a response to a related question. These higher-order models are computationally prohibitive in practice, and hence it is hard for us to conclude anything in terms of the accuracy of these models on knowledge graphs. Theoretically, they can compute stronger binary invariants, and hence we conjecture that they would perform strongly if it would have been possible to scale them up. The trade-off between expressive power and scalability is perhaps the most intriguing aspect of the study of link prediction.\n\n\n*[1] Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel Romero. Weisfeiler and leman go relational. LoG, 2022.*\n"}, {"review_id": "kA3sHCc14h", "reviewer": "Reviewer_1Kyu", "summary": "This paper focuses on graph neural networks (GNNs) for link prediction on knowledge graphs. It introduces the concept of conditional message-passing neural networks, which compute pairwise node representations based on a source node and a query relation. The paper analyzes the expressive power of these networks with a relational Weisfeiler-Leman algorithm and a logical characterization. Experimental analysis is conducted to validate the theoretical findings.\n", "questions": "See in Weakness", "limitations": "The authors have adequately addressed the limitations", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper offers a systematic understanding of conditional message-passing neural networks for link prediction on knowledge graphs. \n\n2. The paper provides insights into the expressive power of conditional message-passing neural networks over the general message-passing neural networks. \n\n3. The paper conducts experimental analysis to empirically validate the theoretical findings. It explores the impact of different model choices, e.g., initialization, global readout functions, providing practical insights into the performance of graph neural networks for link prediction on knowledge graphs.", "weaknesses": "1.  The title and some lines in the introduction seem to be a little bit overclaimed. For instance, the title named a theory of link prediction seems to be claimed on the general link prediction task while the main discussion in the main paper is about the Knowledge Graph link prediction. besides, it is hard for me to understand lines 32-36. I could see from this paragraph that the paper focuses on the NBFNet-based model with conditional message passing. Nonetheless, it seems not so clear to me what higher-order messaging passing neural network computing the pairwise representation on the node. I would like to suggest authors to strengthen the focus of the paper at the beginning and then detail the difference between the RGCN, and CompGCN models with NBFNet. \n2.  The second bullet of the contribution part at line 52 claims that the paper designed a relational Weisfeiler-Lemma algorithm. It leads to the potential misleading that the paper is the first to propose the relational Weisfeiler-Lemma algorithm. Nonetheless, as discussed in line 97 in related work, the relationship is already included in the discussion in 'Weisfeiler and Leman go relational'. I would like to suggest the authors for a clear comparison with the related work on existing relational Weisfeiler-Lemma algorithms. \n3.  The intuition for logical characterization is not so clear. It seems to be hard for me to understand the logical characterization. How it contributes to the expressiveness is not so clear. I would like to suggest the author have more discussion on motivation and why the contribution is significant.\n4.  Lack of explanation on why only focuses on the inductive Link Prediction setting. Despite the NBFNet shows strong ability typically inductive setting. Nonetheless, the algorithm seems not so relevant in the transductive or inductive setting. I still think the experiments on both transductive and inductive settings should be taken into consideration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and your comments on our paper. We address each below.\n\n>“The title and some lines in the introduction seem to be a little bit overclaimed. For instance, the title named a theory of link prediction seems to be claimed on the general link prediction task while the main discussion in the main paper is about the Knowledge Graph link prediction.”\n\nWe do not mean to overclaim our findings: we state link prediction in the title, because link prediction on simple graphs can be seen as a special case of link prediction on KGs, where only one relation type is allowed. In fact, all of the studied models and the presented theory equally applies to link prediction on single-relational graphs. The empirical focus is on KGs, but we make this clear in the paper. If there is an ambiguity regarding this, we will do our best to tone things accordingly to avoid any confusion.\n\n>“Besides, it is hard for me to understand lines 32-36. I could see from this paragraph that the paper focuses on the NBFNet-based model with conditional message passing. Nonetheless, it seems not so clear to me what higher-order messaging passing neural network computing the pairwise representation on the node.”\n\n\nThis statement refers to the following: In principle, one could design a relational variant of  higher-order GNNs, especially those with expressive power matching that of folklore 2-WL. These models compute strong pairwise node invariants, which is crucial for link prediction. However, they are inherently unscalable, which hinders their use in practice. This is precisely what motivates a trade-off between the expressive power and scalability: our paper studies models which are scalable while also being able to compute pairwise node invariants. We can improve this explanation also in the paper.\n\n>“The second bullet of the contribution part at line 52 claims that the paper designed a relational Weisfeiler-Lemma algorithm. It leads to the potential misleading that the paper is the first to propose the relational Weisfeiler-Lemma algorithm. Nonetheless, as discussed in line 97 in related work, the relationship is already included in the discussion in 'Weisfeiler and Leman go relational'.”\n\nWe will rephrase this sentence to avoid any misleading statements as:\n\n*“We define a relational Weisfeiler-Leman algorithm (building on similar works such as Barceló et al [1]), and prove that conditional message passing neural networks can match the expressive power of this algorithm.”*\n\nAs you kindly acknowledge, we give appropriate credit to this work in multiple places in the paper. Specifically, we cover this in the related work section, and separately, on line 484 as *“...generalizes results from Barceló et al [1]”*, and finally, in Appendix A.1 as: *“The expressive power of R-MPNNs has been recently characterized in terms of a relational variant of the Weisfeiler–Leman test [1]”*. \n\n>“The intuition for logical characterization is not so clear.…How it contributes to the expressiveness is not so clear.”\n\nLogical characterizations are by now a well-established topic related to the expressiveness of GNNs (starting from the work of Barceló et al [2]). Unlike the characterization of GNNs based on the WL test, these logical characterizations are *uniform*, in the sense that they hold over the set of all graphs. This means that for any unary formula F(x) in the logical language there is a GNN A such that, *over every graph G*, the set of nodes from G that satisfy F(x) is the same as the set of nodes from G that are classified positively by A. We believe that this logical characterization provides a clear picture of what C-MPNNs can do. On the one hand, the logic is “guarded”, i.e., it is only possible to existentially quantify over nodes that are directly linked to our given node x. This represents the “local” nature of C-MPNNs. On the other hand, the logic has counting quantifiers, which represents the fact that C-MPNNs can distinguish how many neighbors of x satisfy a certain property. \n\nLogical characterizations are also important since they provide a link between the procedural behavior of GNNs and the more declarative and better understood formalisms of logic. For example, and as established by Barcelo et al [2], *“if one proves that two GNN architectures are captured with two logics, then one can immediately transfer all the knowledge about the relationships between those logics, such as equivalence or incomparability of expressiveness, to the GNN setting.”* As an application of this, we have shown in the paper that C-MPNNs with global readout are strictly more powerful than standard C-MPNNs for expressing logical classifiers: we have done so by showing that there is a logical classifier that the former can recognize but the latter cannot.  \n\n>“Lack of explanation on why only focuses on the inductive Link Prediction setting. Despite the NBFNet shows strong ability typically inductive setting. Nonetheless, the algorithm seems not so relevant in the transductive or inductive setting. I still think the experiments on both transductive and inductive settings should be taken into consideration.”\n\nYes, the proposed algorithms are not limited to the inductive setting. As a matter of fact, we did take this into account in our paper, and also reported transductive link prediction experiments in Appendix B.3 of our original submission.\n\nFollowing the suggestions, we further experimented on transductive link prediction on biomedical knowledge graphs, **Hetionet** and **OGB-Biokg** which is reported in Table 3 of **rebuttal.pdf**. These empirical results are very much in line with the presented theory.\n\n*[1] Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel Romero. Weisfeiler and leman go relational. LoG, 2022.*\n\n*[2] 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., ICLR, 2020.*\n"}]

Author rebuttal:
We thank the reviewers for their comments. We have responded to each concern in detail in our individual responses. In addition, we include a **rebuttal.pdf** to this post containing the results of all additional experiments.
Here is a summary of the changes to be made to the paper in light of the reviews received.
- **New experiments on biomedical datasets**: We added additional transductive knowledge graph completion experiments on biomedical datasets: **Hetionet** and **OGB-Biokg** and reported them in Table 3. (Reviewer cjW9, Reviewer kRBD, Reviewer 1Kyu)
- **Visualization of models**: We have provided a visualization of C-MPNN and R-MPNN in Figure 1. (Reviewer 7NY6)
- **Complexity analysis**: We presented the complexity analysis of the models in Table 4. (Reviewer 7NY6) 
- **Baselines**: We added more baselines to inductive relation prediction experiments and reported these in Table 1 (Reviewer kRBD). Similarly, we added more baselines to transductive knowledge graph completion experiments and reported these in Table 2 (Reviewer kRBD).
- **Results from the appendix**: Based on reviewer feedback, we noticed that some of our experiments which are originally reported in the appendix of the paper could be better highlighted in the body of the paper. We have incorporated these changes.

We look forward to hearing your comments and feedback during the discussion period.


Meta-review: The paper examines the application of Graph Neural Networks (GNNs) in predicting links within knowledge graphs. The authors introduce a novel GNN that extends various established approaches utilizing the labeling trick and NBFNets. They assess its capacity for expression by establishing connections with the Weisfeiler-Leman method and providing a logical characterization. Through experimental analysis, the paper explores different architectural options.

Overall, the paper has a solid contribution to graph neural networks. Moreover, the most of concerns raised by reviewers are adequately addressed during the rebuttal, and most of the reviewers agree to accept the paper. Thus, I also vote for acceptance.
Decision: Accept (poster)