OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs
Authors: Yangze Zhou
Gitta Kutyniok
Bruno Ribeiro
Venue: NeurIPS 2022 Accept (2022)
Keywords: OOD
GNNs
link prediction
Message Passing GNNs
random graphs
graphon

Abstract: This work provides the first theoretical study on the ability of graph Message Passing Neural Networks (gMPNNs) ---such as Graph Neural Networks (GNNs)--- to perform inductive out-of-distribution (OOD) link prediction tasks, where deployment (test) graph sizes are larger than training graphs. We first prove non-asymptotic bounds showing that link predictors based on permutation-equivariant (structural) node embeddings obtained by gMPNNs can converge to a random guess as test graphs get larger. We then propose a theoretically-sound gMPNN that outputs structural pairwise (2-node) embeddings and prove non-asymptotic bounds showing that, as test graphs grow, these embeddings converge to embeddings of a continuous function that retains its ability to predict links OOD. Empirical results on random graphs show agreement with our theoretical results.

OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs
Yangze Zhou Department of Statistics Purdue University West Lafayette, IN 47903
Gitta Kutyniok
Department of Mathematics
Ludwig- Mwwimilians-niieeeeeeeee München
Munich, Germany kutyniok@math. lmu.de
zhou950@purdue.cmm
Bruno Ribeiro
Department of Computer Science
Purdue University
West Lafayette, IN 47903
ribeiroêcs purdue. edu
Abstract
This work provides the first theoretical study on the ability of graph Message Passing Neural Networks (gMPNNs) such as Graph Neural Networks (GNNs)- perform inductive out-o--distribution (OOD) link prediction tasks, where de- ployment (test) graph sizes are larger than training graphs. We first prove non- asymptotic bounds showing that link predictors based on permutation-cquivariann (structural) node embeddings obtained by gMPNNs can converge to a random guess as test graphs get larger. then propose a theoretically-sound gMPNN that outputs structural pairwise (2-node) embeddings and prove non-asymptotic bounds showing that, as test graphs grow, these embeddings converge to embeddings of a continuous function that retains its ability predict links OOD. Empirical results on random graphs show agreement with our thcoretical results.
1 Introduction
Link prediction is the task of predicting whether two nodes likely have a missing link [1, 12, 30, 37, 66). Link prediction tasks arise in many settings, ranging from predicting edges on bipartite graphs between users and products or content in recommender systems [6, 11, 31, 32, 39, 62), knowledge graph reconstruction [4. 14, 20, 54, 66, 67], predicting protein-protein interactions [57].
In recent years, there has been growing interest in applying neural network models inductive link prediction tasks. Inductive link prediction considers methods trained on a graph G" and deployed test time on another graph G It also encompasses the task of training the method on smaller induced subgraph G of larger graph G"e then deploying it on the entire graph. In particular, our work focuses on graph message -asssingggnngggg Neural Networks (gMPNNss [21, 60] or, more precisely, the widely used Graph Neural Network (GNN) framework [8, 9, 13, 22, 24, 28, 61, 64, 69].
Our work asks the following questions: Are link prediction methods able to cope with the task of inductive -itoo--distribution (OOD) link prediction, where (unseen) test graphs are significantly larger than training graphs? How can these OOD link prediction tasks be theoretically defined? Can we obtain non-asymptotic bounds on the generalization capabilities of these methods?
The majority of today's link prediction methods based on similar principle. Consider attributed graph = (V, E), with node set V = [1,...N), edge set E S V x V, and node features
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

FER FERNX 2 1. Then, given a pair of nodes i,j E V. after T 2 1 iterations over G, these methods produce associated node embeddings (representation vectors) ,7 0 E R Fr 2 1. which are then used in a link function 77' :R Fr x F + [0, 1] such that 17 ( : 67) predicts the probability that and j have a missing link in G. In our notation we will denote all node embeddings and associated functions with the superscript " "*". Henceforth we denote gMPNNs that output structural node embeddings as gMPNNs*
Node embeddings. The first part of our work considers a subset of these methods, where the output node embeddings are permutation equivariant (a.k.a. structural node embeddings [65]). Informally, a sequence of node embeddings @* E T xPr given by an embedding method is permutation- equivariant if for any arbitrary graph G and any permutation
Sy of the node indices, where Sy is the symmetric group, the resulting isomorphic graph G' = (πr o V, π o E, π F) gets permuted node embeddings O*' a @³, where π o M defines the action of on M (we will provide formal definition in Section 2). We leave the study of OOD link prediction with positional node embeddings (a.k.a. settiutttttoonnnsntiiiii node embeddings [65]) future work.
The application of GNNs to link prediction tasks is made difficult by the fact that, by construction, GNNs give the same embeddings 0 6; to any isomorphic nodes j. in G, as noted by You et al. [82] and Srinivasan and Ribeiro [65]. Isomorphic nodes are nodes that are structurally indistinguishable in G' (even when considering node features) except by their (assumed arbitrary) node indices j E V. That is, if a graph has isomorphic pairs, permutation- equivariant GNN link prediction can fail. The recent link prediction literature has significantly relied on isomorphic nodes for theoretical results (e.g., Zhang et al. [86, Theorem 2] uses isomorphic nodes to prove that, uniformly. graphs are likely have many isomorphic nodes and hence are not amenable to accurate link prediction). However, isomorphic nodes are rare in both real-world graphs (see Figure in the Appendix) and in large random graphs (Proposition 1).
An important open question is whether equivariant GNN would be able to predict links in asymmetric graphs. That is, the concerns of [65, 82] may not be of practical importance. Our work also answers this question: We see that for in-distribution link prediction tasks (where graph test sizes are the same as training sizes), asymmetries. However, we show theoretically and empirically that tapping into asymmetries can fail OOD even when it works in in-distribution.
GNNs are able to predict links by tapping into the graph
Puirwise embedlings. Taking a different route, Srinivasan and Ribeiro [65] provides an existence proof that the link prediction task between and j can always be performed by pairwise embedding Off (G), i.e., for any pair of nodes i.j in a graph G, there exists a pairwise embedding (G) and a link function 17 Er + [0, such that (O!") approximates the probability that i and j have a hidden link. In our notation we will denote all pairwise (joint 2-node) embeddings and associated functions with the superscript "..". Unfortunately, as the test graph grows, we were unable to prove existing pairwise embedding methods [50, 72, 84, 86, 87] are able to perform OOD link prediction tasks. Hence, we propose a novel family of gMPNNs for pairwise embeddings, denoted gMPNNs* ** henceforth. The second part of our work considers the OOD generalization capability of these gMPNNs
Contributions. In this work we study inductive OOD link prediction tasks for larger test graphs using permutation-eqquiariinn node and pairwise embeddings, O* and O* respectively. Our work makes the following contributions:
1. We provide a theoretical framework defining OOD inductive link prediction tasks, where test graphs are significantly larger than training graphs.
2. We show that structural node embeddings from message-passing GNNs can fail in OOD link prediction tasks if the test graph (from the same graph family) is significantly larger than the training graph. Our work fills an important gap in the literature, where Bevilacqua et al. [7] studied the OOD capabilities of GNNs for graph classification using random graph models. Our work studies the OOD capabilities of GNNs for inductive link prediction in a similar setting.
3. We propose a new family of structural pairwise embeddings, denoted gMPNNs that can provably perform the above OOD task.
4. We provide non-asymptotic bounds on the convergence of pairwise gMPNNs embeddings. Exten- sive empirical experiments using stochastic block models (SBMs [63]) validate theoretical

---

results. Our work focuses on providing a theoretical understanding of the challenges of OOD link prediction tasks rather than propose real-world link prediction tasks and compare baselines. However, we believe that our work lays the theoretical foundation (and challenges) for future application-foeused works.
Preliminaries
Given an attributed graph G (V, E), with node set V (1,..,, edge set E C V adjacency matrix A E {0, (0.1)%5 NNN, where A., 1 ((LJ)) F),, and node features F Fx Fo 0. Let Px E By be a permutation matrix associated with permutation π E Sy (where Sy is the symmetric group), where N denotes the Birkhoff polytope of N x N doubly-stochastie matrices. Doubly- sctochastic matrices are non-negative square matrices whose rows and columns sum to one. The matrix Pr, defines the action of permutation и on these matrices, e.g.,
A P,APT We denote a pair of nodes j E V as isomorphic in G if exists π E Sy such that TΙ = j. A P, AP and F F. Node features can be defined by the graph signal f V + 1 _ node to an Po-dimensional feature in IR Po Then the signal of the graph F can be represented by matrix F [f]....,fx] fN]" E RNNx. where f. R are the features of node i V.
function that maps
Random graph model for G. Denote the metric-measure space by (X, d. j). where X is a set, d is metric, and μ is probability Borel measure. A graphon is defined as map- ping W X x X + [0,1] [15, 75]. In what follows we define how the graph G is sampled from the graphon models. The signal definition follows Maskey et al. [46, Def- inition 2.3] and the edge samples follow Airoldi et al. [3], Lawrence and Hyvärinen [34].
Definition 1 (Random graph model). We define f) a random graph model for G on (X, d. p)) with the graphon W :
Graph Model
Graph Size
N
w
f
X' x X + [0, 1] and the metric-space signal X Fo f (X) is an essentially bounded measurable function with the essential supremum norm. We obtain (G, F) by first sampling N
u. [1,
[L...., A.)
Xr,
f.
i..d random points X1...., XN from X' with probability density μ. as the nodes of G. Then the edge (i.j) between nodes i and j is sampled with probability W(X, Xj). ie., the adjacency matrix A -Aig))s of G is defined Aij 1(7g. WWX,, W2)) sampled i..dd from for i,j 1, I,.... N, where {Zx,] A fij==1 (i.....x]] fx]T E Fx Uniform(O,1 1). The graph signal F [f....,
G
Aua
X
f,
Figure 1: Templated causal DAG of G. Hidden and observed vari- ables are shaded white and gray. respectively.
is defined as f, = f(X.). We say (G, F) ~ (W, Further, we restrict our attention to graphons W such that there exists a constant dmin satisfying the graphon degree dw (x) == fx W (z, v)dply) 2 dmmin > 0, Vx E X.
In abuse of notation we identify node i E V with the sampled value X; u, Vi E {I,...N}, since generally i is such that P(X; = X,) = almost everywhere for + (e.g., μ is uniform). The causal DAG of the data generation process of G is given in Figure 1. Our goal is to produce predictors that survive the distribution shift implied by a change in the distribution of graph sizes N during test time. We note that all proofs relegated to the Appendix due to space constraints.
2.1 Inductive structural node representations with graph message- paasssg neural networks
Henceforth use the terms node embeddings and node representations interchangeably. Graph message- passing Neural Network (gMPNN*) ) is defined by realizing a message-passinng Neural Network (MPNN) on graph. We now restate the Maskey et al. [46, Definition 2. of MPNN.
Definition 2 (MPNN [46]). Lei T N denote the number of layers. For L = l...., T, let ((t)) R2F--1 + RBB-1 and vi()), -R---+ - R. be fanctions, where F. E N is called the feature dimension of layer I. The corresponding MPNN θ is define by the sequence of message functions ( and update functions (1)(0)² i.e. θ = ((b(0){=1) ( (-))
We now introduce the gMPNN* with T' message-passing layers. For each node E V. (, at layer
t E (1.... T} is defined recursively using (a) its own representation at layer t - (f, (t-1) 1) and
(b) an aggregated representation of its neighbors (t) Unlike Maskey et al. [46, Definition 2.2] considering mean aggregation, consider here the (N-normalized)sum representation as follows:
3

---

Definition 3 (gMPNN*), (Adaptation of [46. Definition 2.2] to N-normalized GNNs) Let (G, F) be a graph with graph signals as Definition and è be a MPNN as in Definition For layer t t= t= T, define θ A as maps from the input graph G and graph signals F = F E RNFo to the features in the 1-th neural layer by
(t)
0% R NxFo + RNNK,
F-FO (L,t0) )
where F(1) is defined by the (N (Nnormalized) sum aggregation procedure, vi E V. for 0%
(2) m = N A th (1 (2 (0)) = (1 . (11).
,m?
Given a gMPPN' (T), with T layers as in Definition 3, their outputs are (F) e RNX for the (N-normalized) sum aggregation, and are henceforth denoted as node embedding outputs of the gMPNN". We denote (((F)) as the node embedding for node E V.
2.2 Node embeddings with continuous message passing neural networks
Here we adapt the degree- degree-normalize normalized definition of Maskey et al. [46] on continuous message passing for structural node embeddings to our continuous integral aggregation (N-normalized GNNs).
Definition& 4 (Continuous message- pasaaggg...sig............) Given a MPNN θ as in Definition 2, the node continuous message passing neural network (cMPNN*) on graphons is defined by using the metric-space signals f + Fo and continuous aggregation to replace the graph node features and the aggregation scheme Definition
Using a message signal : X x X -> RR... the continuous integral aggregation is defined as MW (U)(x) = Ix W(r, (x. v)dp(y), where W is a graphon.
As defined in Maskey et al. [46, Definition 2.4], the same MPNN θ can process metric-space signals instead of graph signals with the continuous aggregations. Instead of using continuous mean aggregation as [46, Definition 2.4], we are using continuous integral aggregation.
Definition 5 (cMPNN*). (Adaptation of [46, Definition 2.4] to N-normalized GNNs) Let (W; f) be a random graph model as in Definition I and θ be a MPNN as in Definition For = I,... T, define @w) as maps from input metric-space signal f (0) = f X + R to the features in the t-th layer by
1 10())
where f (0 are defined sequentially aggregation for @
g (x) = / W (I,z)) (fott)))))) (ot (w))d (2))
3 Size-stability of node representation and its drawbacks
We now present our results about convergence of gMPNN* to cMPNN* for test graphs G sampled from the graphon random graph model (see Definition 1), and how it leads to size-stability of gMPNN* for nodes that have the same representation under cMPNNs*. Theoretical proofs and common definitions (e.g., Lipschitz continuous functions) are relegated to the Appendix to save space.
3.1 Convergence of gMPNNs towards cMPNNs as test graph size increase
We now prove that, with high probability, the maximum infinity difference between the gMPNN and cMPNN* node representations decreases with N's the size of Ge The proof of Theorem I closely follows the pointwise convergence proof in Maskey et al. [45], adapted to our OOD setting and can be found in the Appendix.
Theorem 1 (OOD convergence without in-distribution convergence). For a random graph model (W, satisfying Definition let N" be random variable defining the distribution of graph sizes in training. Define the test distribution (G't F²) (W, f) through the causal graph in Figure I as an interventional change to obtain larger test graph sizes where min(supp(N') )) (N") (which means any test graph is much larger than the largest possible training graph). Let θ (190)) pE ( be MPNN in Definition 2 with T layers such that

---

Φ11) RRF 1 - RR and T -R. 1 + Bi are learned from the training distribution
and are Lipschitz continuous with Lipschitz constants LE (Mr) and L (Mr) that depend on M Let gMPNN 6AAT) and cMPNN o% be as in Definitions 3 and 5. Let X1. : .... X and A be as in Definition 1. Let p E (0, Eis 2(1++1)) Then, if
VN
4V2
(I)
Vlog (2N
dnmin
we have with probability at least 1 1 Et=1 2(H 1)p.
Vlog(2NVe /p) VNT
0%. =
max 1 A"
10 (F*), - 6, (W) (f)(;))ll +C1 C2llflloo)
i= No
where the constants Cj and C2 are defined in the Appendix and depend on L (Mr), 1 (Ma) and the distribution of (G", F
Theorem I above shows that as the test graph size N grows, the node representations from the discrete gMPNNs learned in the training data converge to the continuous cMPNNs* Theorem 1 I's OOD statement has profound consequences when it comes to predicting links using the node repre- sentations obtained by gMPNN". Next, Corollary shows that for any nodes i, E V that are indistinguishable in the cMPNN (defined as (T) (f)( = " (F)(X))) they will get increasingly similar representations in the discrete gMPNN as N grows.
Corollary 1. Let θ (( ( (1))), (T)
@w PP. (W, f). (G", F").
(G". F"),N",
A",, and Xf,... X2 be as in Theorem 1. If there exists i,j E V i + j. s.t. (
(X,) and Equation (1) is satisfied, then, with C1 and C2 as in Theorem 1, we have that with probability at least Ei= 2HH + 1)p,
A (FF)) OAA0 (F )1lo (CI C2llf 2 log(22N'/p)
VN
Implications of Corollary on Stochastic Block Models (SBMs). In what follows, we will discuss circumstances where two nodes i,j E V get the same cMPNN* representations (i.e.. 0 (7( (Xx,)) (T (f)) We will restrict our results to an important family of graphon models: Stochastic Block Models (SBMs) [63], where we also model node attributes. SBMs were chosen because they can consistently model large graphs generated by any piecewise Lipschitz graphon model [3]. SBMs are also intuitive models, which makes them useful to illustrate our results.
Definition 6 (Stochastic Block Model (SBM)). An SBM (W, f) is a random graph model (Def- inition 1) with cluster structures in W and f. Partition the node set into Z 2 disjoint subsets S1. S2.... S, S. V (known as blocks or communities) with an associated r X r symmetric ma- trix S. where the probability of an edge (i.j). i E Sa and E Sb Sas. for a, b E (1....,r). 1], and be the uniform distribution on [0, 1]. By dividing X' = [0. into dis- and I, = 1, node belongs to block S. is X; Uniform((, 1) satisfies X; E [ta-1, la). The graphon function W is defined E [1o-1,16)). We take the liberty to also define node signals in our SBM model, where for B = [B,,.., "2t...,,,.. BT E Fr the metric-space signal f X + I Fo is defined as f(x) = E.e(t....r) 1(x E (ta-1,ta))
Let X
joint convex seis [Lo, 11), (4,, 12)...., ......,,--1.. (.--,,1)))) where to
as WX;,, X,) = Ea,bE(,.... Sab (X, E (a))1,
We define the action of permutation æ on B of Definition 6 as π B, where (I o B) = Ba- Definition 7 (Isomorphic SBM blocks). For the SBM model (W, f) in Definition 6, we say two blocks
a, E (1....,r) .r are isomorphic if the SBM satisfies the following two conditions: (a) la la-1 1 lB 16-11 1, and (b) for E Sr, such that na b. a and c, Ve E {1,..., T).,, } c. + a, b. S = π S, and = π B.
A similar definition can be obtained for the general graphons in Definition 1 using the isomorphic graphon definition of Lovász and Szegedy [40].
Now that we have the definition for isomorphic blocks in SBM models, we can prove that all nodes in these isomorphic blocks will obtain the same representations under integral aggregation cMPNNs".
5

---

11 (Z)) be MPNN in Desinition 2, and @W in Defi- nition 5. For the SBM model (W, () in Definition 6 with N nodes XI....,X, N If there exists i,j V such that XV, X nodes that belong to isomorphic SBM blocks (Definition 7), then
Lemma 1. Let θ
((
(T)
W (f)()) = @ (f))
Note that even though any two nodes in isomorphic SBM blocks get the same cMPNN represen- tations per Lemma 1, these nodes are likely not isomorphic in G (as shown in Proposition 1 in Appendix) and, hence, they get different gMPNN representations. However, Corollary shows that these representations become increasingly similar as the test graph size grows. We use this observation to understand the ability of gMPNNs to perform link prediction tasks next.
3.2
The hardness of OOD inductive link prediction using structural node embeddings
The convergence of g MPNNN' to cMPNNs as the test graph size N grows (Theorem 1) implies through Corollary 1 and Lemma that node representations of distinct SBM blocks can become increasingly similar as the test graph size grows, even though these nodes are not isomorphic in G with high probability (see Proposition I in the Appendix).
Definition 8 (Link prediction function from structural node embeddings). An inductive link prediction function 1f Fr R.Fr - (0, 1] takes the gMPNN* node representations of two nodes i. E Vie and predicts the edge probability P constant Loge (Ma) that depends on max (supp(NN)) In the context of graphon random graph models (Definition 1), we aim to learn 17 (O (F )e ( z Wi.j)). We furthr assume we predict a link if (...) > T, while no link if nf (.)) < T, for some (arbitrary) threshold T E [0 chosen by the user of such system.
3j = 1). We assume 1f is Lipschitz continuous with Lipschitz
The next corollary showeases the difficulty in OOD predicting links using structural node representa- tions as No grows.
Corollary 2. Let θ ((D(1)) (L)))) be the MPNN with T layers and (T))) ( in Theorem 1. Let 17" R R - 1] be in Definition 8. Consider the SBM (W, f) in Definition 6 with isomorphic blocks (Definition 7). Let (G", F") ~ ~W f) and (G F")) ) ~ (W. be the training and test graphs with N and N nodes, respectively as in Theorem 1. Consider any i # j. for which we can make a link prediction decision with vi (T) F"),, (T) (F)))) F T). Let G be large enough to satisfy both Equation (1) and (i.e., 77 (
two test nodes i E {1,.... N*),
VN
2(C1 + C2l1flloc)
vlog(2N'/p)
A (F*),, ( (F"),) - (()))(
where p. C₁, and C2 are as given in Corollary 1. Then, i and j belong isomorphic blocks (i.e.. O (X!") = @ (f) with probability at least 1 1- ---= 2 + 1)p the link prediction method in Definition 8 will make the same link prediction regardless of the SBM probability matrix S (Definition 6) and whether and j are in the same block or distinct isomorphic blocks.
Corollary 2 proves that link prediction with structural node embeddings form MPNNNs is unreliable. That is, for any link prediction method satisfying Definition 8, as the test graph grows, the method will increasingly struggle to give different predictions within and across isomorphic SBM blocks, even when these probabilities are arbitrarily different in the underlying graph model. In what follows we show that pairwise embeddings can address this challenge.
Size-stability of structural pairwise embeddings and its advantages
We have discussed the limitation of gMPNNs on node representation for link prediction. Now we claim that a joint continuous message passing graph neural network is capable of link prediction in graphon random graph models (Definition 1). We define the joint continuous message passing graph neural network inspired by the cMPNNs for node representations (Definition 5). First, we need to define the graphon fraction of common neighbors for graphon nodes and y. cw (z, y) == Ix W(x, x) (y, 2 (d)..). We only consider graphons W such that there exists demin satisfying ew (x, y) 2 demin > 0, Vo. y E X this section. Since we do not have edge feature as in Definition 1, we define the metric-space pair-wis wise signal as f (Ix 3) 1, Vz, y X.

---

Definition 9 (cMPNN*)), ). Let fW. be random graph model as in Definition 1 and @ be a MPNN as in Definition Fort 1,,.., define the continuous (pairwise) cMPNN ( as the mapping that maps input pairwise metric-space signals f==(0) = =j to the features in the t-th layer by
@w (2) + (2), | + f000)
where faol)) are defined recursively by
(0) (1) (I,
] / =();=) T600 (100 (x, v (ea (xr, z))
1
2 x CW (2. y)
W (1,, 2(1)) (fo0(t-1) v), (y,, (3,,2))) (d((())
cw cw y)
( (I, y) = w (f (t) (z. y). 000l (2. (z,y)).
The intuition of the aggregation function is that two edges with one same node is considered neighbors in oederr-ordrrree graph [51], and to go from (æ, y) to (I, 2), we need to transition from to 2, which has probability W (gy, 2). The same holds for going from (z. y) (y,
Lemma 2. 1f y) = y and (z, 3) = z/y. then fre( y) = (xx, v), Vx, y E X is a station- ary point in the cMPNN* i.e. if pell-11(x,, v) = ((,,, y). then (x.1) = W(x, v), Vx,y E X.
We define the corresponding gMPNN as follows. First we define the fraction of common neighbors between nodes and j as CAi.j = NN E A Aj.z- If two nodes do not have common neighbors, then we set CAi.j N to avoid computation error. Further, we define f (.j Vi,j E V for any graph G. and F (f" u.j...fe as the pair-wise graph signals.
Definition 10 (gMPNN**). Let (G, F) be graph with graph signals as in Definittion I and θ be MPNN as in Definition 2. For t L,, ..., T layers we define the gMPNN (x)()) as the mapping that maps input pairwise graph signals F=) F to the features in the I - th layer by
ox N=F. N (=) + >= (f N
1. k-j=1==1
where (()(t) are defined recursively by the following function,
1
Aj.z (1)
(t-1)
poo(t-1)) Ai, (10) (foolt-1) (10(tt-1)),
m
2N
CAL.
1.
1,2
CAL.
ig
p = v (+)
ij
Next, Theorem 2 shows that these discrete joint representations gMPNN" converge to the continuous pairwise representation cMPNN" under the causal DAG of Figure 1.
Theorem 2 (OOD convergence without in-distribution convergence). For a random graph model (W, satisfying Definition 1, let N" be random variable defining the distribution of graph sizes in training. Define the test distribution (G" FF) ~ (W. f) through the causal graph in Figure / as an interventional change to obtain larger test graph sizes where min(supp(NNe) max Mexx(sup(NN')) (which means any test graph is much larger than the largest possible training graph). Let θ = (( "T, (( be a MPNN as in Definition 2 with T layers such that (!!) and w/( that are learned the training data and are Lipschitz continuous with Lipschitz constants (1) (Mz) and 1 (Mr). Let gMPNN" ( and cMPNN" ( be as in Definitions 9 and 10. L
For a random graph model (W, J) as in Definition I with demin >> O. Let "i,,...,%,, and A be as V/="
in Definition I. Let P E (0, ET_ 2(H++1)) Then, if
we have with probability dewin'
4v2
/1og(2(N0)775
at least -ET, 2(H1i 1)p,
(Cs+ V /log(2(Ne))2/p)
000 max N*
No |10 (T) (F - ( (
VNW
where the constants C3 and Cs are defined in the Appendix and depend on (I.00 (M₂), 11 (M.) and the distribution of (G", F
7

---

Hence, as the test graph size N gets larger w.r.t. N" (that is, as we intervene on the causal DAG of Figure
change the support of the distribution of N in order to obtain larger test graphs), the link predictor learned in the training data using gMPNN will converge to a continuous method (cMPNN"*) that can predict links OOD tasks (i.e., ( x)) a stationary solution of cMPNN" per Lemma 2). This convergence is also observed in our empirical results.
5 Further Related Work
In what follows we describe works related to learning transferability in GNNs. The concept of transferability of GNN is introduced by Levie al. [35], Ruiz et al. [58], which state that if two graphs represent same phenomena (e.g., are sampled from the same distribution), then a transferable both graphs. This is closely related
GNN has approximately the same predictive performance to in-distribution generalization capabilities of GNNs to unseen test data, i.e., generalization error when train and test data come from the same distribution. Existing works [26, 44, 58, 59] prove the transferability for spectral-based GCNs under graphon models, and Maskey et al. [46] extends these results to more general message passing GNNs. The GNN smoothness conditions needed to prove uniform convergence of node-embedding equivariant GNNs in Maskey et al. [46] means their GNNs would be unable perform in-distribution link prediction in some tasks (such as the graphs in Definition 7). However, in practice, we observe (Section 6) that GNNs are capable of performing these in-distribution link prediction tasks. Our results are also based on general message passing GNNs. Our goal (OOD link prediction) is, however, significantly different than these prior works, which focus on in-distribution graph and node classification. The link prediction challenge for node-embedding equivariant GNNs is either in symmetric graphs (Srinivasan and Ribeiro [65]) or OOD (this work). Theorem 1 and Corollary say the difference of node representations in isomorphic blocks vanish as the test graphs grow larger, but Theorem 2 says that our pairwise equivariant representation is capable of performing these OOD link prediction task. Related works relating to the representation power, higher order structural and positional link prediction methods (not already covered in our introduction) can be found in Appendix A due to space constraints.
Empirical Evaluation
In what follows we empirically validate our theoretical results in two parts. We implement all our models in Pytorch Geometric [19] and make it available'. Due space constraints we relegate detailed description of our experiments to the Appendix.
Convergence and stability. First we will empirically validate Theorems and 2 and Corollary 1.
Consider an SBM (Definition 6) with three blocks (r = 3) and Sa, = 0.55, a = 1, 2,3, S1.2 S2,1 0.05, S1.3 = S3,1 = 0.02. Note that one and three are isomorphic blocks (see Definition 7). We use a randomly initialized GraphSAGE [24] GNN model for node embedding, and test both the & and V of Lemma 2, and scenario where V a randomly-initializee MLP for pairwise embeddings.
Figures 2(a-c) show log-log plots of the convergence of gMPNNs to their continuous cMPNN counterparts as the test graph size N' increases. The empirical approximation errors ,x, (Theo- rem 1) (Figure 2(a)) and 5%.w (Theorem 2) are shown as a function of the test graph size N 2", n 5, ..., 13. The empirical results show agreement with the theory since 8%. and 5%. are bounded above by OVVlogNV /VNN. which is approximated by the slope -1/2 in a log-log plot. Figures 2(d-e) show histograms of the difference between gMPNN* embeddings of different
nodes in G Let 4 6 (F): - (F); for i,j E V'C, A E Rr and further define A 180 (resp. non-iso);.j := (Ai.)) arg max, (()))))) where & E {1,..., Fr) is the dimension of the embed- ding. We use subscript iso (resp. non-iso) when i, E Vie are in isomorphic (resp. non noniisomorphic) SBM blocks (Definition 7). As N increases, Figure 2(d) shows that embeddings between isomorphic blocks converge, validating Corollary 1, while Figure 2(e) shows that non-isomorphic blocks do not.
Link prediction performance evaluation with SBMs (in-distribution and OOD). In what follows we introduce empirical results using a SBM similar in the previous setting. Details can be found in Appendix B.3. We start by sampling the training graph (G", FF) with N = 10 nodes. We randomly hide 10% of E from the original graph G" for link prediction purpose since the goal of link prediction is to predict possible missing links that is not observed in the original graph. We call
attps:: // //ggthub. waalllccocyyaeeeeee woaa/yaggzee/000-- Link- Prediction www.reeieeeiiia-eeee..
8

---

10g
#kspee110
xtpe-112
skppe-112
25 23 0 0
15 A 0 (ogos/N")
29 28 34 14 46
10gra/i"9)
10ghe
Asan-
Figure 2: Experimental agreement with theory: (a) shows 6% (Theorem 1) of a GraphSAGE GNN as a function of N (b) shows Wx. (Theorem 2) with the gMPNN of Lemma 2 as a function of N (c) replicates (b) with Y/ as a raadomly-initiallll close agreement with Theorems 1 and 2 that predicts slope se -1/2 in log-log scale for large N (d) shows stable node representations between isomorphic SBM blocks, while (e) shows constant difference in node representations between non-isomorphic SBM blocks, which validate Corollary 1.
neural network. Results shows
these edges Ehid-r Then we split Ehid-i into positive train (80%) and validation (10%) edges (we reserve 10% of Ehid-tr for the transductive test scenario), and uniformly sample the same number of across-block non-edges as negative train and validation edges. The embedding method gMPNN (resp. gMPNN**) along with link predictor 17" (resp. 1)**) are trained in an end-to-end manner for predicting positive and negative edges in training using cross-entropy loss. Our experiments consider three scenarios (in all scenarios we use the same number of negative test edges as positive test edges, sampled from non-edges in G with endpoints in different isomorphic blocks): (i) (In-distribution) transductive scenario where G = G where positive test edges are the 10% reserved in thid not used in training or validation; (ii) In-distribution inductive scenario where G is sampled from the same SBM with N = N where we also hide 10% of the edges and sample 0. | F positive test edges from Ehid-te (for fair comparison across all scenarios); (c) OOD inductive scenario where G is sampled from the same SBM with N = 10 x N where we also hide 10% of the edges and sample 0.1 0 Ehid-rr positive test edges from Ehid-te (for fair comparison across all scenarios).
For structural node embeddings we consider GraphSAGE [24], GCN [28] (without positional features), GAT [70] and GIN [78] as the representatives of gMPNN models. The link predictor 17" is as feedfoward network (with 3 hidden layers and 10 neurons each) that receives the two node embeddings as input, and has link prediction threshold
0.5 (see Definition 8 for details).
For structural pairwise embeddings we choose our proposed gMPNN method of Definition 10, since we can prove that our approach is theoretically sound in Lemma 2. We test gMPNN in two versions: The & and V functions in Lemma 2 (denoted fixed v and feedforward neural network for V with 2 hidden layers and 5 neurons each (denoted learn V. The link predictor 1)* is the same as 1)* except it just takes one pairwise embedding as input, rather than two node embeddings.
Table 1 presents our empirical results. The oracle predictor knows the graphon values W )))). Our evaluation metrics include the Matthews correlation coefficient (mcc) [47], balanced accuracy, and Hits @ K for K = 10, 50, 100 that counts the ratio of positive edges ranked at the k-th place or above against all negative edges. Note that gMPNN* structural node representations can very accurately predict links in the transductive tasks, and still performs reasonably well in inductive in-distribution tasks. However, as expected from Corollary 2, this performance suffers significantly as Ne becomes 10x larger than N Now all gMPNN* methods produce predictors that are no better than a random guess over all metrics (e.g.. see OOD mec and accuracy (in red)). In contrast, the gMPNN* is able to consistently offer good performance both in-distribution and OOD tasks.
Link prediction performance evaluation with ogbl-ddi (in-distribution and OOD). In what follows we introduce empirical results using the ogbl-ddi dataset, which represents drug-drug interaction network. For the purpose of performing OOD tasks, we start by sampling 10% of the nodes (427 nodes) and its induced subgraph to be the training graph. Further experimental details can be found in Appendix B.4. The in-distribution inductive scenario has 5 constructed as an induced subgraph with N = Nr nodes from the remaining ogbl-ddi graph. Our OOD inductive scenario has Ge as the induced subgraph without the training nodes (N 3840 nodes). The test edges are obtained by applying the original edge split on the newly induced test subgraph, where we further down-sample to the same amount of test edges as in our in-distribution scenarios for fair comparison across all scenarios. Table 3 in the Appendix presents our empirical results on the ogbl-ddi link prediction task. All MMPNN* methods performs worse inductive settings than transductive settings, and suffer much worse performance in OOD transductive setting except GCNs. In contrast, the

---

Table 1: Test performance over 50 runs of node and pairwise gMPNNS for in-distribution and OOD link prediction over SBM graphs. Methods marked with * indicate best result out of distinct configurations detailed in the Appendix.
Training graph size N -1
Tasks
Model
Hit@ 10(%)
Hit@ 100(%)
mcc.(%)
balanced acc.(%)
GraphSAGE
95.55( 0.52)
95.93( 0.73)
96.14( 0.74)
95.42( 0.37)
97.66( 0.19)
GCN=
93.15(14.57)
93.99(13.08)
94.35(12.72)
92.41(11.72)
95,97( 8.24)
Transductive
GAT
93.77(13.03)
94.01(13.02)
94.14(13.03)
90.94(16.09)
95,26( 8.38)
GIN
95.77( 0.59)
96.09( 0.58)
96,28( 0.59)
95.48( 0.41)
97.69( 0.22)
In-distribution link prediction
gMPNN" (fixed 4)
93.76( 0.55)
94.17( 0.51)
94.51( 0.49)
93.64( 0.53)
96.72( 0.28)
gMPNN" (learn V)
96.71( 0.32)
96.88( 0.31)
97.00( 0.30)
94.23( 0.55)
97.03( 0.29)
Oracle
96.92( 0.36)
96.92( 0.36)
96.92( 0.36)
93.74( 0.42)
96.77( 0.22)
GraphSAGE*
47.38(39.08)
52.13
14,94(37.83)
19.34(43. 19)
61.46(20.17 17)
Inductive N N"'
GCN"
(6.29(37
68.52(35.87)
69.92(35.122 12)
31.76(35. 12)
67.21(22.75)
GAT
40.05(39.05)
41.34(39.39)
41.96(39.54)
19.4 (2)..2())22)
59.52(16.94)
GIN+
39.33(34.622
42.93(33.86)
43,90(33.72)
(8,59(39)43)
59.79(18.24)
gMPNN" (fixed V)
93.85( 0.49)
94.23( 0.51)
94.55( 0.49)
93.74( 0.48)
96.77( 0.25)
gMPNN" (learn V)
96.71( 0.30)
96.91( 0.28)
97.02( 0.27)
94.23( 0.59)
97.03( 0.31)
Oracle
97.01( 0.31)
97.01( 0.31)
97.01( 0.31)
93.87( 0.39)
96.84( 0.20)
OOD link prediction
Inductive N 10+
GCNs
GraphSAGE
9.97(19.47)
(9.29)31.33)
19(3009)))) 42.15(().81)
11.73/21.80 80)
12.98(23.70)
-6.56( 5.12)
4.88(1488)
50.33( 6.72)
49.32( 0.60)
GAT
27.31(26.93)
28.13(26.78)
28.72(226.3)
-2.00( 8.96)
50.20( 3.37)
GIN+
0.00( 0.00)
0.00( 0.00)
0.00( 0.00)
-3.93( 5.12)
49.59( 0.57)
gMPNN" (fixed y)
96.74( 0.07)
96.93( 0.04)
97.01( 0.04)
93.76( 0.05)
96.78( 0.03)
gMPNN" (learn V)
96.97( 0.04)
97.02( 0.04)
97.08( 0.04)
93,94( 0.67)
96.88( 0.35)
Oracle
96.96( 0.03)
96.96( 0.03)
96.96( 0.03) 93.77( 0.04)
96.79( 0.02)
gMNNN* is able to consistently offer good performance both in-distribution and OOD tasks, showing that the theoretical results are not limited to SBM models.
7
Conclusions
This work studied and provided the first theoretical framework for the task of out-of-distribution (OOD) link prediction, where test graphs are larger than training graphs. Using non-asymptotic bounds, this work showed that OOD link prediction methods using structural node embeddings given by message-passing GNNs converge to link predictors that may perform no better than random guesses. The work also proposed theoretically-soot passing algorithm which is able to perform our OOD link prediction task by being approximately invariant to interventions on test graph sizes, as the discrete joint embedding converges to the continuous one. This means that graph sizes grow in test (OOD), it is still possible find neural networks parameters that allows our joint representation to converge to the true link probability. passing GNNs.
structural pairwise embedding with a message-
We show that the same is not guaranteed for mode-embedding equivariant Extensive empirical evaluation showed agreement with these theoretical results. We do not foresee adverse social impacts for this theoretical work, but it does raise awareness of the shorteomings of node-embedding equivariant massagg-passing GNNs for link prediction tasks in applications such as recommender systems.
Acknowledgments
This work was funded in part by the National Science Foundation (NSF) Awards CAREER IIS- 1943364 and CCF-1918483, the Purdue Integrative Data Science Initiative, the Purdue Research Foundation, and the Wabash Heartland Innovation Network. Gitta Kutyniok acknowledges support from the ONE Munich Strategy Forum (LMU Munich, TU Munich, and the Bavarian Ministery for Science and Art), the Konrad Zuse School of Excellence in Reliable AI (DAAD), the Munich Center for Machine Learning (BMBF) as well as the German Research Foundation under Grants DFG-SPP-2298, KU 1446/31- and KU 1446/32-1 and under Grant DFG-SFB/TR 109, Project C09 and the Federal Ministry of Education and Research under Grant MaGriDo. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors.
10

---

References
[1] Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3): 211-230, 2003.
[2] Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexan- der J Smola. Distributed large-scale natural graph factorization. In Proceedings of the 22nd international conference on World Wide Web, pages 37-48, 2013.
[3] Edo M Airoldi, Thiago B Costa, and Stanley H Chan. Stochastic blockmodel approximation of graphon: Theory and consistent estimation. Advances Neural Information Processing Systems, 26, 2013.
[4] Gabor Angeli and Christopher D Manning. Philosophers are mortal: Inferring the truth of unseen facts. In Proceedings of the seventeenth conference on computational natural language learning, pages 132.142,11 2013.
[5] Fabian Ball and Andreas Geyer-Schulz. How symmetric are real-world graphs? a large-scale study, Symmetry, 10(1):29, 2018.
[6] Robert M Bell and Yehuda Koren. Lessons from the netflix prize challenge. Acm Sigkdd Explorations Newsletter, 9(2):75-79, 2007.
[7] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In Marina Mcila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 837-851. PMLR. 2021.
[8] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34 (4):18-42, 2017.
[9] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations, 2014.
[10] Yongqiang Chen, Yonggang Zhang, Han Yang, Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Invariance principle meets out-of-distribution generalization on graphs. CoRR, abs/2202.05441, 2022.
[11] Abhinandan Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Google news per- sonalization: scalable online collaborative filtering. In Proceedings of the 16th international conference on World Wide Web, pages 271-280 2007.
[12] Luc De Raedt. Logical and relational learning. Springer Science
& Business Media, 2008
[13] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[14] Tim Dettmers, Pasquale Minervini. Pontus Stenetorp. and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 32, 2018.
[15] Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs. arXiv preprint 1rX.2:0712..2749, 2007.
[16] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
[17] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. International Conference Learning Representations, 2022.

---

[18] Paul Erdos and Alfréd Rényi. Asymmetric graphs. Acta Math. Acad. Sci. Hungar, 14(295-315):
3, 1963.
[19] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[20] Lise Getoor and Christopher P Dichl. Link mining: a survey, Acm Sigkdd Explorations Newsletter, 7(2):3-12, 2005.
[21] Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272. PMLR, 2017.
[22] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, volume 2, pages 729-734, 2005.
[23] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proc. of KDD, pages 855-864. ACM, 2016.
[24] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[25] Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 2222113-2213, 2020.
[26] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convo- lutional networks on large random graphs. Advances in Neural Information Processing Systems, 33:21512-21523, 2020.
[27] Jeong Han Kim, Benny Sudakov, and Van H Vu. On the asymmetry of random regular graphs and random graphs. Random Structures & Algorithmss, 21(3-4):216-244, 2002.
[28] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[29] Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning, 2016.
[30] Daphne Koller, Nir Friedman, Sašo Džeroski, Charles Sutton, Andrew McCallum, Avi Pfeffer, Pieter Abbeel, Ming-Fai Wong, Chris Meek, Jennifer Neville, et al. Introduction to statistical relational learning. MIT press, 2007.
[31] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, 2009.
[32] Yehuda Koren, Steffen Rendle, and Robert Bell. Advances in collaborative filtering. Recom- mender systems handbook, pages 91-142, 2022.
[33] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34, 2021.
[34] Neil Lawrence and Aapo Hyvärinen. Probabilistic non-linear principal component analysis with gaussian process latent variable models. Journal of machine learning research, 6(11), 2005.
[35] Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22 (272):1-59, 2021.
[36] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances Neural Information Processing Systems, 1144465-4478 2020.
12

---

[37] David Liben-Nowell and Jon Kleinberg. The link pre-diecittion problem for social networks. Journal of the American society for information science and technology, 58(7):1019-100) 1031, 2007.
[38] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.1 13013, 2022.
[39] Greg Linden, Brent Smith, and Jeremy York. Amazon. com recommendations: Item-to-item collaborative filtering. IEEE Internet computing, 7(1):76-88) 80, 2003.
[40] László Lovász and Balázs Szegedy. The automorphism group of graphon. Journal of Algebra, 421:136-166, 2015.
[41] Tomasz Luczak, Abram Magner, and Wojciech Szpankowski. Asymmetry and structural information in preferential attachment graphs. Random Structures & Algorithms, 55(3):696- 718, 2019.
[42] Ben D MacArthur, Rubén Sánchez-Gareia, and James W Anderson. Symmetry in complex networks. Discrete Applied Mathematics, 156(18):35253331, 2008
[43] Haggai Maron, Heli Ben- Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pages 2166-2167, 2019.
[44] Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: an extended graphon approach. arXiv preprint arXiv:2 10096, 2021.
[45] Sohir Maskey, Yunseok Lee, Ron Levie, and Gitta Kutyniok. Convergence and transferability of message passing graph neural networks. (under submission) currently available under the ritle "Stability and Generalization Capabilities of Message Passing Graph Neural Networks" in arXiv:2202.0066 0064455v.. 2022.
[46] Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. Advances in neural information processing systems, 2022.
[47] Brian W Matthews. Comparison of the predicted and observed secondary structure of 14 phage lysozyme. Biochimica Biophysica Acta (BBA)-Protein Structure, 405(2):442-451 1975.
[48] Brendan McKay. Practical graph isomorphism. Dagstuhl Reports, Vol. 5, Issue 12 ISSN 2192-5283, page 11, 2016.
[49] Andriy Mnih and Russ R Salakhutdinov. Probabilistic matrix factorization. Advances in neural information processing systems, 20, 2007.
[50] Federico Monti, Oleksandr Shchur, Aleksandar Bojchevski, Or Litany, Stephan Günnemann, and Michael M Bronstein. Dual-prrmal graph convolutional networks. arXiv preprint arXiv:1806.000 00770, 2018.
[51] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[52] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint arXiv:21 12. 12.09992, 2021.
[53] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In Proceedings of the 36th International Conference on Machine Learning, 2019.
13

---

[54] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33. 2015.
[55] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[56] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pages 701-710, 2014.
[57] Yanjun Qi, Ziv Bar-Joseph, and Judith Jlein-Seetharaman. Evaluation of different biological data and computational classification methods for use in protein interaction prediction. Proteins: Structure, Function, and Bioinformatics, 63(3):490-500) 2006.
[58] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the trans- ferability of graph neural networks. Advances in Neural Information Processing Systems, 33: 1712, 2020.
[59] Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph neural networks: architectures, stability, and transferability. Proceedings of the IEEE, 109(5):660-63) 682, 2021.
[60] Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. Advances in neural information processing systems, 30, 2017.
[61] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-80, 2008.
[62] Brent Smith and Greg Linden. Two decades of recommender systems at amazon. com. leee internet computing, 21(3):12-18, 2017.
[63] Tom AB Snijders and Krzysztof Nowicki. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of classification, 14(1):75-100, 1997.
[64] Alessandro Sperduti and Antonina Starita, Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 8(3):714-733) 1997.
[65] Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. ICLR, 2020.
[66] Ben Taskar, Ming-Fai Wong. Pieter Abbeel, and Daphne Koller. Link prediction in relational data. Advances in neural information processing systems, 16, 2003.
[67] Théo Trouillon, Johannes Welbl, Scbastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International conference machine learning, pages 2071-2080. PMLR, 2016.
[68] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[69] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 17..:/000..00.3....00000003 2017.
[70] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018
14

---

[71] Haorui Wang. Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representations, 2022.
[72] Yanbang Wang, Yen-Yu Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In International Conference Learning Representations, 2021.
[73] Boris Weisfeiler and AA Lehman. A reduction of graph canonical form and algebra arising during this reduction. Nauchno--Tecmnichesskayy Informatsia, 2(9):12-16, 1968.
[74] David S Wishart, Yannick D Feunang, An C. Guo, Elvis Lo, Ana Marcu, Jason R Grant, Tanvir Sajed, Daniel Johnson, Carin Li, Zinat Sayeeda, et al. Drugbank 5.0: a major update to the drugbank database for 2018. Nucleic acids research, (6(D1))D1074-D1022, 2018.
[75] Patrick Wolfe and Soñia C Olhede. Nonparametric graphon estimation. arXiv preprint arXiv:1309.5938 2013.
[76] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In International Conference on Learning Representations, 2022.
[77] Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022.
[78] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[79] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference Learning Representations, 2021.
[80] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward graph neural networks. In International Conference on Learning Representations, 2021.
[81] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11955-1111111 115--1996,, PMLR, 18-24 Jul 2021.
[82] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awazd awaae graph neural networks. In Interna- tional Conference Machine Learning, pages 7134-7143. PMLR, 2019.
[83] Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec. Identity- graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[84] Muhan Zhang and Yixin Chen. Weisfeiler-lehman neural machine for link prediction. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, page 575-583, 2017.
[85] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018
[86] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: theory using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34, 2021.
[87] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-for networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34, 2021.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All theoretical proofs are in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] Included the anonymous code link in Section
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Explain the basic setups in Section 6, and detailed construction in the appendix.
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] included Table
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] All the compute and resources details are in the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] The python packages are cited.
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "ZopqTs1SNdL", "reviewer": "Reviewer_BWxA", "summary": "This work studies the ability of message passing neural network (MPNN) to perform prediction tasks on a test graph larger than the train graph. It first gives a definition of random graph and continuous MPNN (cMPNN) and proves that as the test random graph size approaches infinity, gMPNN converges to cMPNN. Then authors focus on Stochastic Block Model (SBM) and illustrate how the convergence leads to bad generalization on SBM: node representations of distinct SBM blocks can become increasingly similar as the test graph size grows even if they are non-isomorphic with a high probability. Then authors introduce structural pairwise embedding and prove that this method can solve the problem. Empirical results on SBM verify the theoretical analysis.", "questions": "Is there any results for random graphs other than SBM?", "limitations": "Not related.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. Good originality and significance: the first theoretical study on the ability of GNNs to perform inductive out-of-distribution (OOD) link prediction tasks.\n\n2. Novel theoretical analysis.\n\n3. Clear representation.\n\nWeakness:\n\nThe theoretical analysis and experiments are constrained to SBM. However, real-world graphs are different. For example, some graphs have no node features.\n\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Zj1FM_jczSI", "reviewer": "Reviewer_FCSF", "summary": "This paper studies the out-of-distribution (OOD) inductive link prediction capability of graph message passing neural networks (gMPNNs) in terms of graph sizes. While showing gMPNNs predictions can converge to random guesses when test graphs get larger, they also propose to use pairwise embeddings which can provably resolve the issue. The theoretical results are validated with synthetic experiments on random graphs.", "questions": "The authors conduct extensive works on the theoretical analysis which is appreciated. However, the theoretical tools used in the paper are similar to [1], and the solution is not new in the literature [2]. There are several concerns raised regarding the scope and novelty of both the theoretical and empirical results:\n\nThe scope studied in this work seems to be limited:\n- *Task*: This paper studies the OOD inductive link prediction task in terms of graph sizes. However, it seems many of existing link prediction applications, such as knowledge graph and recommender system, focus more on the transductive settings [3,4], or ``inductive’’ settings where the training graph is a subgraph of the test graph, which is different from the setting studied in the paper. It would further strengthen the paper if the authors could provide more concrete examples for the inductive applications studied in the paper, or analysis on other settings.\n\n- *Distribution shifts*: Moreover, the distribution shifts in graphs can be more complicated than graph sizes, as discussed in [5,6,7,8]. It would make the paper more impactful if the authors could also discussed other potential distribution shifts, such as covariate shifts on node features, subgraph appearance frequencies, averaged graph degrees [8].\n\n- *Graph model*: The main results seem to rely largely on a certain graph model, i.e., SBM. And the failure cases seem to be limited to certain nodes in the model. I understood that providing general results for all graph models would be too difficult, however, if authors could provide more results for other graph models or more realistic graphs, it would further strengthen the paper by providing more guide for practitioners as well as future works built on the results of this work.\n\n\nRegarding the novelty:\n- The hardness example seems to rely on the convergence results of gMPNNs to cMPNNs in terms of the node embeddings. Does the similar results can also be developed for graph classification and node classification, too?\n\n- Since the main results of this paper largely rely on the convergence of gMPNNs to cMPNNs on node embeddings, which seems to be similar to Theorem 3.1 from [1]. More discussions on the differences seem to be expected, especially when the convergence can also be applied to other tasks. Otherwise the results for link prediction seem to be a straightforward extension of [1] which may weaken the novelty of the work. \n\n- To mitigate the issue of gMPNNs when generalizing to larger test graphs, the authors propose to use pairwise embeddings [2]. Does it mean using the original pairwise node embeddings [2] can already solve the issue? It would be more helpful for the future works built on the paper if the authors could summarize the implications of the theoretical results to the practitioners. \n\nMinor points:\n- The causal graph seems not to provide further implications.\n- In line 190, i \\in S_A should be I \\in S_a .\n\n== post rebuttal ==\nThe authors adequately resolve my concerns during the rebuttal. Hence I'd like to raise my ratings to 7. \n\nReferences:\n\n[1] Sohir Maskey, Yunseok Lee, Ron Levie, and Gitta Kutyniok. Stability and generalization capabilities of message passing graph neural networks. arXiv 2022.\n\n[2] Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. ICLR 2020.\n\n[3] Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen and Philip S. Yu. A Survey on Knowledge Graphs: Representation, Acquisition, and Applications. TNNLS 2022.\n\n[4] Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. A Survey of Link Prediction in Complex Networks. ACM Computing Survey 2017.\n\n[5] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classiﬁcation extrapolations. ICML 2021.\n\n[6] Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, Tat-Seng Chua. Discovering Invariant Rationales for Graph Neural Networks. ICLR 2022.\n\n[7] Qitian Wu, Hengrui Zhang, Junchi Yan, David Wipf. Handling Distribution Shifts on Graphs: An Invariance Perspective. ICLR 2022.\n\n[8] Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, James Cheng. Invariance Principle Meets Out-of-Distribution Generalization on Graphs. arXiv 2022.\n", "limitations": "Since this is a theoretical work, potential negative social impacts may not be applicable.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Originality & Significance*: Studying the OOD ability of gMPNNs is of great importance to the community, though the theoretical tools used in the paper are similar to Maskey et. al., 2022, and the solution is not new in the literature (Srinivasan and Ribeiro, 2020).\n\n*Quality*: The authors conduct extensive works on the theoretical analysis which is appreciated. However, there are several concerns raised regarding the scope and novelty of both the theoretical and empirical results. See the Questions below for more details.\n\n*Clarity*: The paper is well-written and organized. The authors provide informative explanations for each theoretical result which makes the paper easy to follow despite lots of theories.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LDJ5MaScuk3", "reviewer": "Reviewer_Bs4U", "summary": "This paper theoretically analyze the GNN's capalability for handling link prediction. The main results show that using node embeddings for link prediction could fail to distinguish two nodes even though they are distinct in the graph as node numbers increase, and using pairwise (edge) embeddings for link prediction could successfully learn a correct prediction model and generalize the OOD graphs with larger sizes. Experiments on synthetic datasets verify the theoretical results. ", "questions": "While the main body of the paper seems interesting, there are still some confusing parts which would impact how the contributions are interpreted and need to be clarified before a proper evaluation could be made. I hope the following the questions could be properly addressed during the rebuttal.\n\n1. As far as I understand, the key result of Section 3.2 is Prop 1 (though it is claimed to be contained in the Appendix) which cliams to show that for two nodes which are even distinct in the graph the link prediction model would also map them into the same embedding as the node numbers increase. If this holds true, such a result implies that the models based on node embeddings may fail to generalize to larger graphs. However, I fail to find Prop 1 in the Appendix, so cannot check its soundness and could overally downweigh the significance/contribution of Section 3.2.\n\n2. In Section 4, the results show that the models based on pairwise embeddings would converge to an \"ideal\" model whose stationary solution is the graphon as node numbers increase. Then a conclusion is made that the models would successfully generalize to larger graphs. I am a little confused at this point: 1) what is the implication of the stationary point, does it mean one of the optimums or the unique one? 2) the stationary point is obtained from assumptions for the specific forms of \\Phi and \\Psi, does it mean the conclusion only holds for very specific situation and cannot be applied to the general regime? 3) why such a stationary point implies desirable OOD performance, it seems these two have no clear connection. ", "limitations": "The major limitation lies in the experiments, though most of contents seem reasonable and sound. The experiment datasets only cover synthetic datasets which are simple and limited. I suggest adding more experiments on real-world datasets, especially some common GNN benchmarks for link prediction and comparing with some SOTA approaches (even though they are not designed for OOD regime). Though I understand that the main focus of this paper lies in the theoretical insights and perspecitve, more results on benchmarks and comparison with more strong models (currently used baselines seem too weak and simple) could make this work more complete and convincing, especially that one of the contributions of this work is a new approach for OOD link prediction. \n\nAlso, there are some recent works on out-of-distribution generalization on graphs, e.g., [1, 2, 3], which are missing in the related works and need to be discussed.\n\n[1] Size-Invariant Graph Representations for Graph Classification Extrapolations, ICML 21.\n\n[2] Handling Distribution Shifts on Graphs: An Invariance Perspective, ICLR 22.\n\n[3] From Local Structures to Size Generalization in Graph Neural Networks, ICML 21.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: 1. The insight of this paper is helpful for understanding the capablity and behaviors of GNN models for OOD generalization link prediction tasks, which is an active and open problem in the community. 2. Most of the results are intuitive and see correct though I did not carefully check the proof. 3. The paper is well written and easy to follow with very clear and clean notations.\n\nWeaknesses: 1. Some of the results are confusing and need more illustration (see comments below). 2. Experiments are only conducted on synthetic datasets and more results on real-world datasets especially common GNN benchmarks are expected.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "CF4EU3ZiLmV", "reviewer": "Reviewer_3cpo", "summary": "In this paper, the authors aims to analyze the limitations of existing MPNNs on performing link prediction. Specifically, they identify that existing node-based MPNNs are not able to handle out-of-distribution (OOD) graphs for inductive link prediction, where the ``distribution'' is related to node size. Then, they further propose an edge-based MPNN to overcome this issue.  ", "questions": "1. It is not very clear whether it is really an OOD issue. It seems that node-based MPNNs will experience difficulty to learn distinguishable node representations for nodes from distinct isomorphic blocks when the size of the test graph increases, regardless of the training graph. So, is it an OOD issue or an issue of learning distinguishable representations for isomorphic nodes? It would be better if the authors could provide more detailed explanations on this. For example, is there an OOD issue when the test graph is smaller than the training graph? If the training graph and test graph are both large, will the test performance be good? \n\n2. A large portion of the analyses are based on a specific kind of SBM model, where isomorphic blocks exist. It seems the OOD issue identified in this paper is strongly related to isomorphic blocks. So, does the OOD issue exist in other kinds of graphs (for example, graphs generated from SBM model without isomorphic blocks)? \nAlso, there are some other papers[1] suggesting that MPNNs are not able to deal with graphs with isomorphic patterns.  It would be better if the authors could provide a discussion and comparison with these existing works. \n\n3. In general, it would be better if the authors could provide a more detailed and accurate description on the OOD issue that they try to address. As mentioned in the first two points, the analyses seems to be limited to very specific cases while the title and the introduction is very general. \n\n\n[1] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The authors conduct theoretical analysis to study the OOD issue for inductive link prediction when the test graph is large. \n2. The authors conducted comprehensive results to verify the correctness of their theories. \n3. A new framework is proposed to address the OOD issue for the link prediction task.\n\nWeakness\n1. A large portion of the analyses are based on the SBM model. Also, the features for nodes in the same block are assumed to be the same (Definition 6). Furthermore, the analyses are generally based on SBM models with isomorphic blocks. It is not clear how these analyses can be extended to more general cases.  \n2. It is not very clear whether it is really an OOD issue. It seems that node-based MPNNs will experience difficulty to learn distinguishable node representations for nodes from distinct isomorphic blocks when the size of the test graph increases, regardless of the training graph.    ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept