Almost Surely Asymptotically Constant Graph Neural Networks
Authors: Sam Adam-Day
Michael Benedikt
Ismail Ilkan Ceylan
Ben Finkelshtein
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks; convergence laws
Primary area: graph_neural_networks
TL;DR: We investigate a very strong convergence property applicable to GNN probabilistic classifiers -- asymptotic almost sure convergence -- and show that it applies to a broad range of GNN architectures and random graph models.

Abstract: We present a new angle on the expressive power of graph neural networks (GNNs) by studying how the predictions of real-valued GNN classifiers, such as those classifying graphs probabilistically, evolve as we apply them on larger graphs drawn from some random graph model. We show that the output converges to a constant function, which upper-bounds what these classifiers can uniformly express. This strong convergence phenomenon applies to a very wide class of GNNs, including state of the art models, with aggregates including mean and the attention-based mechanism of graph transformers. Our results apply to a broad class of random graph models, including sparse and dense variants of the Erdős-Rényi model, the stochastic block model, and the Barabási-Albert model. We empirically validate these findings, observing that the convergence phenomenon appears not only on random graphs but also on some real-world graphs.

Almost Surely Asymptotically Constant Graph Neural Networks
Sam Adam-Day"
Michael Benedikt
ismail ilkan Ceylan Department of Computer Science University of Oxford Oxford, UK
Ben Finkelshtein
Abstract
We present new angle on the expressive power of graph neural networks (GNNs) by studying how the predictions of real-valued GNN classifiers, such as those classifying graphs probabiliisticall, evolve drawn from some random graph model. We show that the output converges to constant function, which upper-bounds what these classifiers express. This strong convergence phenomenon applies to a very wide class GNNs, including state of the art models, with aggregates including mean and the attention-base mechanism of graph transformers. Our results apply to broad class of random graph models, including sparse and dense variants of the Erdös-Rényi model, the stochastic block model, and the Barabási-Ales model. We empirically validate these findings, observing that the convergence phenomenon appears not only on random graphs but also on some real-world graphs.
apply them larger graphs
uniformly
1 Introduction
Graph neural networks (GNNs) 21 have become prominent for graph machine learn- ing with applications in domains such as life sciences [47 25
= 3
n n= 10 a x/
n = 30
7
8 x
(55). Their empirical suc- cess motivated work investigating their theoret- ical properties, pertaining to their expressive
4
power [52] 39 g
I
43 23
19 54], gener-
GNN
alization capabilities [8 33 38 45 40) and
convergence properties [28 27
38
32 2).
We consider GNNs outputting real-valued vec- tors, such as those which classify graphs prob- abilistically, and ask: how do the outputs of these GNNs evolve as we apply them on larger graphs drawn from random graph model?
Class
Class 2
Class 2
Class
Class
Class 1
Figure 1: The output of the considered GNNs even- tually become constant as the graph sizes increase.
Our study provides a surprising answer to this question: the output of many GNNs eventually become independent of their inputs each model eventually outputs the same values on all graphs as graph sizes increase (Figure D This "almost sure convergence" to constant distribution is much stronger than convergence to some limit object [28] 27 32]. The immediate consequence of this strong convergence phenomenon is upper bound the uniform expressiveness of the considered model architectures: these architectures can uniformly express only the classifiers that are almost
Cooresppnniigg author. Email: me@samadanday..cmm com
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

surely asymptotically constant. In other words, our results provide impossibility results for what tasks are principle learnable by GNNs. While our top-level results are for graph classification, in the process we provide strong limitations on what node- and edge-classification can be performed by GNNs on random graphs: see, for example Theorem 5.3
Scope of the result. The core approach in graph machine learning is based on iteratively updating node representations of an input graph by an aggregate of messages flowing from the node's neigh- bours (20). This approach can be extended to global aggregates [5]. Our main result holds for all architectures that use weighted mean an aggregation function and it is extremely robust in the following two dimensions:
1. Model architectures: Our result is very general and abstracts away from low-level architectural design choices. To achieve this, we introduce an aggregate term language using weighted mean aggregation and provide an "almost sure optimization" result for this language: our result states that every term in the language can be simplified to Lipschitz functions for most inputs. Thus, any architecture that can be expressed in this language follows the same convergence law. This includes gruph attention networks (GAT') [49], as well as popular (graph) transformers, such as the General, Powerful, Scalable Graph Trunsformer (GPS) with random walk encodings [41]. The term language can scamlessly capture common design choices, such as skip and jumping knowledge connections [51], or global aggregation schemes (5).
2. Random graph models: All results apply to a wide class of random graph models, including Frdös-Rényi models of various sparsity levels, the Barahási-Alhert preferential attachment model, and the stochastic block model. The sparse models are more realistic than their dense counterparts which makes it typically harder to obtain results for them. This is also reflected in our study, as the results for sparse and dense models require very different proofs.
Contributions. The key contributions of this paper are as follows:
We introduce flexible aggregate term language with attractive closure properties (Section 4 and prove an "almost sure convergence" result for this language relative to a wide class of random graph models (Section [5). This result is of independent interest since it pushes the envelope for convergence results from classical logical languages [15 36 to include aggregation.
We show that diverse class of architectures acting real-valued graph classifiers can be expressed in the term language (Section (4) In Section[]wwe we present "almost sure convergence" results for term language, from which we derive results about GNNs (Corollary 5.2). The results are robust to many practical architectural design choices and even hold for architectures using mixtures of layers from different architectures. We also show strong convergence results for real-valued node classifiers in many graph models.
We validate these results empirically, showing the convergence of these graph classifiers in practice (Section 6) on graphs drawn from the random models studied. In addition, we probe the real-world significance of our results by testing for convergence on dataset with varying size dataset splits. Across all experiments we observe rapid convergence to a constant distribution. Interestingly, we note some distinctions between the convergence of the sparse and non-sparse Erdös-Rényi model, which we can relate to the proof strategies for our convergence laws.
2 Related work
Uniform expressiveness. The expressive power of MPNNs is studied from different angles, including their power in terms of graph distinguishability [52 39 The seminal results of Xu et al. (52). Morris al. 39 show that MPNNs are upper bounded by the 1-dimensional Weisfeiler Leman graph isomorphism test (1-WL) in terms of graph distinguishability. WL-style expressiveness results are inherently non-uniform, i.c., the model construction is dependent on the graph size. There are also recent studies that focus on uniform expressiveness [4, 42,22 2). In particular, Adam-Day et al. 2 investigate the uniform expressive power of GNNs with randomized node features, which are known to be more expressive in the non- non-uniform setting D 43.. They show that for classical Erdōs-Rény Rényi graphs, GNN binary classifiers display a zero-one law, assuming certain restrictions on GNN weights and the random graph model. We focus real-valued classifiers, where their results do not apply, while dealing with a wider class of random graph models, subsuming popular architectures such as graph transformers.

---

Convergence laws for languages. Our work situates GNNs within a rich term language built up from graph and node primitives via veal-valued functions and aggregates. Thus it relates to convergence laws for logic-based languages on random structures, dating back to the zero-one law of Fagin [1S). including [35 46, 31. We are not aware of any prior convergence laws for languages with aggregates: the only work on numerical term languages is by Grädel et al. 22 which deals with a variant of first-order logic in general semi-rings.
Other notions of convergence on random graphs. The works of Cordonnier et al. [.] Keriven et al. 28 27]. Maskey et al. 38 Levie
[2] consider convergence to continuous analogues of GNNs, often working within metrics on a function space. The results often focus on dense random graph models, such as graphons [3]]. Our approach fundamentally different in that we can use the standard notion of asymptotic convergence in Euclidean space, comparable to traditional language- based convergence results outlined above, such as those by Fagin [15] and Lynch [36]. The key point is that a.a.s. constancy is very strong notion of convergence and it does not follow from convergence in the senses above. fact, obtaining such a strong convergence result depends heavily on the details of the term language, as well as the parameters that control the random graph: see Section 7 for further discussion of the line between a.a.s. convergence and divergence. Our study gives particular emphasis to sparse random graph models, like Barabási-Albert, which are closer to graphs arising in practice.
3 Preliminaries
3.1 Featured random graphs and convergence
Random graphs. We consider simple, undirected graphs G (Va, Eg, Ha) where each node is associated with vector of node features given by HG VG - Rd. We refer to this as a featured graph. We are interested in random graph models, specifying for each number n a distribution Jen on graphs with nodes, along with random graph feature models, where have distribution ye, on featured graphs with n nodes. Given a random graph model and a distribution v over RV we get random graph feature model by letting the node features be chosen independently of the graph structure via v.
Réndi and the stochastic block model. The most basic random graph model we deal with is the Erdös-Rény distribution ER(n, p(n)). where an edge is included in the graph with nodes with probability p(n) [14]. The classical case is when p(n) is independent of the graph size n, which we refer as the dense ER distribution. We also consider the stochastic block model SBM(n1,..... nM, P), which contains matrix between communities P E R RMxM X A community i is sampled from the Erdös-Rén distribution (n) Pıç)) and an edge to node in another community j is included with probability P.j.
communities of sizes n1....., R&M and edge probability
The Barabási-Albert preferential attachment model. Many graphs encountered in the real world obey a power law, which a few vertices are far more connected than the rest 77. The Barabási- Albert distribution was developed to model this phenomenon (3]. It is parametrised by a single integer m, and the n-vertex graph BA (n, m) is generated sequentially, beginning with a fully connected m-vertex graph. Nodes added one at time and get connected via m new edges to previous nodes, where the probability of attaching to a node is proportional to its degree.
Almost sure convergence. Given any function F from featured graphs to real vectors and a random featured graph model (Hn)EEN, we say F converges asymptotically almost surely (converges a.a.s.) to a vector with respect to if for all e, > 0 there is N E N such that for all n > N, with probability at least 1 when drawing featured graphs G from pa, we have that [[F(G) - =|| < 6.
3.2 Graph neural networks and graph transformers
We first briefly introduce message passing neural networks (MPNNs)
20 which include the vast
majority of graph neural networks, well as (graph) transformers.
Message passing neural networks. Given a featured graph G = (Vo. Eg, Hc). an MPNN sets
Ho(() and iteratively updates the feature h (8) of each node v, for the initial features h (0)
3

---

0 2 1, based on the node's state and the state of its neighbors ( by defining h (c+1)
(P AGG (n (h (())))
where [.B denotes multiset and (f and AGa differentiable update and aggregation functions, respectively. The final node embeddings are pooled to form a graph embedding vector
(L)
Z to predict properties of entire graphs. A MEANGNN is MPNN where the aggregate is mean.
GATs, One class of MPNNS are graph attention networks (GATs) 49
where each node is updated
with weighted average of its neighbours' representations. letting h (e+1) be:
score hh 12 )
exp
exp score hhe nw W( (0)
Σ (E)
(EN(
where score is a certain learnable Lipschitz function.
Graph transformers. Beyond traditional MPNNs, graph transformers extend the well-known transformer architecture to the graph domain. The key ingredient in transformers is the self-attention mechanism. Given a featured graph, single attention head computes new representation for every (query) node v, in every layer & >> O as follows:
exp scale (2)
h(?)) (ccale ( (1
ArT(U)=
Σ uEVe
Σ Vo
exp
wE
where scale is another learnable Lipschitz function (the scaled dot-product).
The vanilla transformer architecture ignores the graph structure. Graph transformer architectures [53 41 37] address this by explicitly encoding graph inductive biases, most typically in the form of positional encodings (PEs). In their simplest form, these encodings are additional features p. for every node that encode node property (e.g., node degree) which are concatenated to the node features h,,. The random walk positional encoding (RW) [2] of each node given by:
rwo [rw,, IW .................. .Wo.k)
where rw,,i is the probability of an i-length random walk that starts at e to end at v.
The GPS architecture 41 is representative graph transformer, which applies parallel computation every layer: transformer layer (with or without PEs) and an MPNN layer are applied in parallel and their outputs are summed to yield the node representations. By including standard MPNN in this way, a GPS layer can take advantage encoding. In the context of this paper, we write GPS to refer to GPS architecture that uses an MPNN with mean aggregation, and GPS+RW the architecture additionally uses a random sallk PE.
the graph topology even when there is no positional
Probabilistic classifiers. We are looking at models that produce a vector of reals on each graph. All of these models can be used as probabilistic graph classifiers. We only need to ensure that the final layer is softmax sigmoid applied to pooled representations.
4 Model architectures via term languages
We demonstrate the robustness and generality of the convergence phenomenon by defining term language consisting of compositions of operators on graphs. Terms are formal sequences of symbols which when interpreted in given graph yield a real-valued function the graph nodes.
Definition 4.1 (Term language). AGG W MMAN] is term language which contains node variables I, y, 2.... and terms defined inductively
The basic terms of the form H(r),, representing the features of the node ær and constants
II the body reserve æ, y, for free variables and for concrete nodes in graph.

---

Let h: R² - (0, oo) be a function which is Lipschitz continuous every compact domain.
Given terms and x, the local h-weighted mean for node variable æ is:
Σ (E
T(V) x h(T(W))
The interpretation will be defined below. The global h-weighted mean is the term:
Σ +((())(((())
Terms are closed under applying a function symbol for each Lipschitz continuous RRdxk -y IRd for any & E N
The weighted mean operator takes a weighted average the values returned by т. It uses æ to perform weighting, normalizing the values of using h to ensure that we are not dividing by zero (see below for the precise definition).
To avoid notational clutter, we keep the dimension of each term fixed at d. It is possible to simulate terms with different dimensions by letting be the maximum dimension and padding the vectors with zeros, noting that the padding operation is Lipschitz continuous.
We make the interpretation of the terms precise follows. See Figure for graphical example of evaluating a term on a graph.
Definition 4.2. Let
(Vg, EG. HG) be a featured graph. Let be a term with free variables Ti..... and 7 (ui...., 4x) tuple of nodes. The interpretation [r(ū]]c of term graph G for tuple defined recursively:
[e(ü)]c for any constant
[H(x;)(ū]]c = (u, for the hh node's features.
((n,....TT(())))) (T) [Tx(ū]l)) for any function symbol F.
For any term composed using
-{
Σ (M(B.)) ve
-{
if (u;)) # 0: if (f,, = 0. The semantics of global weighted mean is defined analogously and omitted for brevity.
Σ T* (()(
A(<((N)))))
veN(N,)
(E.((.))
0
Input graph
0.
20
2.0
H(x))
211(=)
20
Exemyy (2l((s) +10
18
Figure 2: Evaluation of the term ExeV (2H(x) 2) 1.0 on small graph with scalar features. The term computes the mean of 22 + 2 each of node's neighbours. As each sub-term has one free variable, we can represent the intermediate results as scalar values for each node.
closed term has all node variables bound by weighted mean operator: so the implicit input is just a featured graph.
Definition 4.3. We augment the term language AGG [MEAN, RW] by adding the random walk operator rw(z). The interpretation of rw(z,) given a graph G and tuple of nodes 77, is:
[rw(z))ūi]G [ww.. [Wa.dd

---

4.1 How powerful is the term language?
Various architectures can be described using this term language. The core idea always the same: we show that all basic building blocks of the architecture can be captured in the term language and applying this inductively yields the desired result. Let first note that all linear functions and all commonly used activation functions are Lipschitz continuous, and therefore included in the language.
MPNNS with mean aggregation. Consider I--layer MPNN with functions (PD consisting of an activation function applied to a linear transformation, with mean pooling at the end. First, note that mean aggregation can be expressed as:
aggregation, update
MEANy = Σ (V)) 1
For each layer 0 < f < L, we define term (x) which will compute the representation of node layer of the MPNN:
Initialization. Let (0) H(x). Then the value [+( (z)) node the initial node representation (u).
Layers. For 1 < < L, define (z) = Up (x, MEAN (0)) Then the value at node is the following, which conforms with the inductive construction the MPNN:
[t (x) = (PD( (1
Σ eEN((u)
(x)
W(w)
Final mean pooling. The final graph representation is computed as (EAN)
The idea is similar for the other architectures, where the difference lies in the aggregation functions. Thus below we only present how the term language captures their respective aggregation functions.
Graph transformers. We can express the self-attention mechanism of transformers using the following aggregator:
AT) Σv(1)= exppscale(7(x))
The function scale(m(1)), (v)) is term in the language, since scaled dot product attention is Lipschitz function. see how graph transformer architectures such as GPS can expressed, suffices to note that we can express both self-attention layers and MPNN layers with mean aggregation, since the term language is closed under addition. The random walk positional encoding can also be expressed using the rw operator.
Graph attention networks. The attention mechanism of GAT is local node's neighbours and can be expressed in our term language using similar ideas, except using the local aggregate terms.
Additional architectural features. Because the term language allows the arbitrary combination of graph operations, it can robustly capture many common architectural choices used in graph learning architectures. For example, a skip connection be expressed by including a copy of the term for layer & in the term for the layer &g [51]. Global
residual connection from layer l to layer & can
readout can be captured using global mean aggregation (5). Attention conditioned on computed node or node-pair representations can be captured by including the term which computes these representations in the mean weight 337
Capturing probabilistic classification. Our term language defines bounded vector-valued functions over graphs. Standard normalization functions, like softmax and sigmoid, are easily expressible in our term language, so probabilistic classifiers are subsumed.
Graph convolutional networks. In Appendix A we show how to extend the term language to incorporate graph convolutional networks (GCNs) 29 by adding new aggregator.
Convergence theorems
We start by presenting the convergence theorem.

---

Theorem 5.1. Consider (Pn)neN sampling a graph G from any of the following models and node features independently from i..dd bounded distributions on d features.
1. The Erdös-Rén Kényi distribution ER(n,,(()) where p satisfies any of the following properties.
Density. p converges to p 0.
Root growth. For some K > 0 and 0 < 3 < 1 we have: p(n) = Kn
Logarithmic growth. For some K 0 we have: p(n) K log(n)
n
Sparsity. For some K > 0 we have: p(n) Kn
2. The Sarabasi-Albert model BA(n, m) for any m 2 1.
The stochastic block model (BM(n) (n)), ...., nm (n), P) where Ri..... Rem : R that Tu (n) +... (T) = and each converges, and P is any symmetric m m edge probability matrix.
+ N are such
Then every AGG (MEAN, RW] term converges a.a.s. to a constant with respect to (Jon)
Concretely, this result shows that for any probabilistic classifier, or other real-valued classifier, which can be expressed within the term language, when drawing graphs from any of these distributions, eventually the output of the classifier will be the same regardless of the input graph, asymptotically almost surely. Thus, the only probabilistic classifiers which can be expressed by such models are those which are asymptotically constant.
Corollary 5.2. For any of the random graph featured models above, for any MeanGNN, GAT, or GPS + RW, there is distribution p on the classes such that the class probabilities converge asymptotically almost surely to p.
We now discuss briefly how the results are proven. The cases divide into two groups: the denser cases (the first three ER distributions and the SBM) and the sparser cases (the fourth ER distribution and the BA model). Each is proved with a different strategy.
5.1 Overview of the technical constructions for the denser cases
While the theorem is about closed terms, naturally we need to prove it inductively on the term language, which requires consideration of terms with free variables. We show that each open term in some sense degenerates to Lipschitz function almost surely. The only caveat is that we may need to distinguish based on the "type" of the node for example, nodes U1 U2 Uy that form triangle may require different function from nodes that do not. Formally, for node variables T, an ø graph type is a conjunction of expressions E(x,, 2ÿ) and their negations. The graph type of tuple in graph, denoted GrTp(u) () is the set of all edge relations and their negations that hold between elements of u. A (œ,, d) feature-type controller a Lipschitz function taking as input pairs consisting of d-dimensional real vector and an J graph type.
The key theorem below shows that to each term x we can associate a feature-type controller e, which captures the asymptotic behaviour of æ,, in the sense that with high probability, for most of the tuples the value of cx (Ha(u), GrTp(u)) close to [ī]
Theorem 5.3 (Aggregate Elimination for Non-Sparse Graphs). For all terms (ह) over featured graphs with d features, there is a (ū. d) feature-rype controller e, such that for every c, A > O, there is N N such that for all N, with probability least 1- 0 in the space of graphs of size n, out of all the tuples a at least - 5 satisfy that ||e (H), GrTp(u)) - -T(T(
<
This can be seen as a kind of "almost sure quantifier elimination" (thinking of aggregates as quanti- fiers), in the spirit of Kaila [24] Keisler and Lotfallah [26]. It is proven by induction on term depth, with the log neighbourhood bound playing a critical role in the induction step for weighted mean.
Theorem 5.3 highlights an advantage of working with a term language having nice closure properties, rather than directly with GNNs: it allows us use induction term construction, which may be more natural and more powerful than induction on layers. Theorem 5.3 also gives strong limitations on node and link classification using GNNs: on most nodes in mnn-sspasee) random graphs, GNNs can only classify based on the features of a node, they cannot make use of any graph structure.
The appendix includes additional results for the GCN aggregator.
7

---

5.2 Overview of the technical constructions for the sparser cases
In the sparser cases, the analysis is bit more involved. Instead of graph types over i. which only specify graph relations among the ū. we require descriptions of local neighbourhoods of ū.
Definition 5.4. Let G graph, d a tuple of nodes in and E N. The (-neighbourhood of ū in G. denoted is the subgraph of G induced by the nodes of distance at most É from some node in u.
The "types" are now graphs with k distinguished elements w, which we call k-rooted graphs. Two k-rooted graphs (T, vi) and (U, 2) are isomorphic is there is structure-preserving bijection T + U which maps w to 2. The combinatorial tool here a fact known in the literature as 'weak local convergence': the percentage of local neighbourhoods of any given type converges.
Lemma 5.5 (Weak local convergence). Consider sampling a graph G from either the sparse ER or BA distributions. Let (T, w) be a k-rooted graph and take E N. There qr E [0, 1] such that for all e, 0 > O there is N E N such that for all v 2 N with probability at least - 0 we have that:
H N
④) = (T. w)
QT
<E
7
Our "aggregate climination", analogous to Theorem 5.3 states that every term can be approximated by Lipschitz function of the features and the neighbourhood type.
Theorem 5.6 (Aggregate Elimination for Sparser Graphs), For every T (F), letting & be the max- imum aggregator nesting depth in n. for all k-rooted graphs (T,w) there is a Lipschitz, function ef Tlld - IR such that for each e, >> there N E N such that for all at least 1 - in the space of graphs of size for every k-tuple of nodes u in the graph such that (T) = (T, w) we have that |ee (H))(()())) - [T[ū]]] <.
N with probability
Compared to Theorem 5.3 the result is much less limiting in what node-classifying GNNs can express. Although combining the sparse and non-sparse conditions covers many possible growth rates, is not true that one gets convergence for Erdös-Rént with arbitrary growth functions:
Theorem 5.7. There are functions p(n) converging to zero and term our language such that does not converge even in distribution (and hence does not converge a.a.s.) over ER random graphs with growth rate p.
Proof. Let p alternate between on even n and on odd n. Consider Ty (2) that returns 0 if x has neighbour and 1 otherwise, and let r be the global average of Tı. So r is the percentage of isolated nodes in the graph. Then clearly goes to zero in the non-sparse case. However the probability that particular node is not isolated random sparse graph of size n - n. - which goes to 1. Thus [r] diverges
pn))..
6 Experimental evaluation
We first empirically verify our findings on random graphs and then on a real-world graph to answer the following questions: Q1. Do we empirically observe convergence? Q2. What is the impact of the different weighted mean aggregations on the convergence? Q3. What is the impact of the graph distribution the convergence? Q4. Can these phenomena arise within large real-world graphs?
All our experiments were run on single NVidia GTX V100 GPU. We made our codebase available online at htttp:://gi thub. com/bbetf www.eekeeeetnn http://aaaaaaiiaaaaaaaaaealllal/ www.-llsyyttotiillllll-ooooo
Setup. We report experiments for the architectures MeanGNN, GAT [49 and GPS+RW 41 with random walks of length up to 5. Our setup is carefully designed to eliminate confounding factors:
We consider five models with the same architecture, each having randomly initialized weights, utilizing a ReLU non-linearity, and applying a softmax function to their outputs. Each model uses a hidden dimension of 128, layers and an output dimension 5.
We experiment with distributions ER(n, = 0.1). ER(n, = logm), ER(n, p(n) = s.m BA(n, m 5). We also experiment with an SBM of 10 communities with equal size, where an edge between nodes within the same community included with probability 0.7 and an edge between nodes of different communities is included with probability 0.1.

---

We draw graphs of sizes up to 10,000, where we take 100 samples of each graph size. Node features are independently drawn from UT0 1] and the initial feature dimension is 128.
To understand the behaviour of the respective models, we will draw larger and larger graphs from the graph distributions. We use five different models to ensure this is not model-specific behaviour. Further experimental results are reported in Appendix
6.1 Empirical results random graph models
In Figure g a single model initialization of the MeanGNN, GAT and GPS+RW architectures used +
with ER(n, p(n) = 0.1), [(n),((n) log and ER(n, p(n)
). Each curve the plots
50m
corresponds to different class probability, depicting the average of 100 samples for each graph size along with the standard deviation shown in lower opacity.
The convergence of class probabilities is apparent across all models and graph distributions, as illustrated in Figure 3 in accordance with our main theorems (Q1). The key differences between the plots are the convergence time, the standard deviation and the converged values.
One striking feature of Figure is that the eventual constant output of each model is the same for the dense and logarithmic growth distributions, but not for the sparse distribution (Q3). We can relate this the distinct proof strategy employed the sparse case, which uses convergence of the proportions of local isomorphism types. There are many local isomorphism types, and the experiments show that what converge depends the proportion of these. In all other cases the neighbourhood sizes unbounded, so there is asymptotically almost surely one 'local graph type'.
We observe that attention-based models such as GAT and GPS+RW exhibit delayed convergence and greater standard deviation in comparison to MeanGNN (Q2). A possible explanation is that because some nodes weighted more than others, the attention aggregation has higher variance than regular mean aggregation. For instance, if half of the nodes have weights close to O, then the
0.213
0.219
0.200
0.205
0.205
0,200
0.200
0.200
0.195
0.185
0.199
0.100
0.185
30F
102
10
102
10'
101
101
107
10'
Graph size
Graph size
Graph size
GAT
GAT
GAT
0.200
0.260
0.269
0.260
0.260
0.249
0.240
0.300
0.229
0.200
0.200
0.200
0.389
0.160
0.300
0.160
0.100
0.140
0.140
9:340
Graph size
Graph size
Graph size
GPS+RW
GPS+RW
GPS+RWV
0.800
0.000
0.500
0.400
0.400
2.100
0.300
0.209
0.200
3.100
0.008
0.000
3.000
201
Graph size
Graph size
Graph size
(a) Dense ER
(b) Logarithmic growth ER
(c) Sparse ER
Figure 3: Each plot shows the five mean class probabilities (in different colours) with standard deviations of a single model initialization over ER ER(,,,(n) = 0.1), ER(n,p(n) = logn ), and ER(n, p(n) = 50n as we draw graphs of increasing size.

---

ER(o,p(o) 0.1)
Standard deviation
0.04
0.04
3.64
0.03
0.53
045
0.62
10
10'
10
10
10
10"
10
10
10'
10"
10'
Graph size
Graph size
Graph size
Figure 4: Each plot depicts the standard deviation of Euclidean distances between class probabilities and their respective means across various samples of each graph size for GPS+RW.
attention aggregation effectively takes a mean over half of the available nodes. Eventually, however, the attention weights themselves converge, and thus convergence cannot be postponed indefinitely.
Figure 4 depicts the outcomes of the GPS+RW architecture for various graph distributions. The analysis involves caleulating the Euclidean distance between the class probabilities of the GPS+RW architecture and the mean class probabilities over the different graph samples. The standard deviation across the different graph samples then derived for each of the 5 different model initializations and presented in Figure 4 The decrease of standard deviation across the different model initializations Figure 4 indicates that all class probabilities converge across the different model initializations, empirically verifying the phenomenon for varying model initializations (Q1 and Q3).
6.2 Empirical results large real-world graphs
Towards Q4, we investigated large real-world dataset. Many commonly studied graph datasets (e.g. ZINC [I3,, QM9 (6) do not exhibit sufficient graph size variance and provide no obvious means to add scaling. We used the SIGER-Alaske dataset
TIGER-Alaska
1.000
Standard deviation
0.800
0.600
[16] of geographic faces. The original dataset has 93366 nodes, while Dimitrov et al. [0] extracted smaller datasets with graphs having IK, 5K. 10K,
0.400
25K and 90K nodes. We chose the modified dataset
as it is split by graph size, and consists of graphs
10a
10
differing from random models (in particular all graphs are planar). Figure shows the results of applying the same five MeanGNNs graphs of increasing sizes. Strikingly, we again observe a convergence phenomenon, but slower pace.
Graph size
Figure 5: Standard deviation of distances be- tween class probabilities and their means across TIGER-Alaske graph sizes for MeanGNN.
Discussion and limitations
We have demonstrated a wide convergence phenomenon for real-valued classifiers expressed even in very advanced GNN architectures, and it applies to great variety of random graph models. Rather than having separate proof techniques per GNN model, our paper introduces a broad language where such models be situated, and provides techniques at the level of term languages. Although our top-level theorems deal with graph-level tasks, along the way we provide strong limitative results on what can be achieved on random graphs for node- or edge-level real-valued tasks: see Theorem 5.3
The principal limitations of our work come our assumptions. In particular, we assume that the initial node embeddings are i.i.d. This assumption is used in the application concentration inequalities throughout the proofs, so loosening it would require careful consideration.
Our main results show that many GNN architectures cannot distinguish large graphs. To overcome this limitation, one could consider moving beyond our term language. For example, if we add sum aggregation, the term values clearly diverge, and similarly if we allow non-smooth functions, such as linear inequalities. Further we emphasize that a.a.s. convergence is not universal for our term language, and it does not hold even for ER with arbitrary p(n)) going O: see Theorem 5.7
10

---

References
[1] R. Abboud, Ceylan, M. Grohe, and T. Lukasiewicz. The Surprising Power of Graph Neural Networks with Random Node Initialization. In IJCAI, 2021.
[2] S. Adam-Day M. Iliant, and 1. 1. Ceylan. Zero-one laws of graph neural networks. In NeurlPS, 2023.
[3] A.-L.. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439): 509-512, 1999.
[4] P. Barcelo, E. Kostylev, M. Monet, J. Perez, J. Reutter, and J. P. Silva. The Logical Expressive- ness of Graph Neural Networks. In ICLR, 2020.
[5] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez- Gonbbez-Gozzzzzz, V. F. Zambaldi, M. Malinowski,
A. Tacchetti, D. Raposo, Santoro, R. Faulkner, Ç. Gülçehre, H. Song, A. J. Ballard,
J. Gilmer, G. E. Dahl, A. Vaswani, K. R. Allen, C. Nash, V. Langston, C. Dyer. N. Heess,
D. Wierstra, Kohli, M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1 806.01261, 2018.
[6] M. Brockschmidt. GNN-FiLM: Graph neural networks with feature-wise linear modulation. In ICMI., 2020.
[7] G. Caldarelli. Scale-free networks complex webs in nature and technology. Oxford University Press, Oxford, 2007.
[8] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? In NeurIPS, 2020.
[9] M. Cordonnier, N. Keriven, N. Tremblay, and S. Vaiter, Convergence of message passing graph neural networks with generic aggregation on large random graphs. CoRR, 2304. 1.04.111400 11140, 2023.
[10] R. Dimitrov, Z. Zhao, R. Abboud, and ismail ilkan Ceylan. PlanE: representation learning over planar graphs. In NeurlPS, 2023.
[11] D. Duvenaud, D. Maclaurin, J. Aguilera- Jaanlera-pparraguirre, R. Gómez-Bombarelll, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In NeurIPS, 2015.
[12] V. P. Dwivedi, A. T. Luu, T. Laurent, Y. Bengio, and X. Bresson. Graph neural networks with learnable structural and positional representations. In ICLR, 2021.
[13] V. P. Dwivedi, C. K. Joshi, T. Luu, Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(1), 2024.
[14] Erdös and A. Rényi. On Random Graphs Publicationes Mathematicae Debrecen, 6: 290-297, 1959.
[15] R. Fagin. Probabilities on finite models. Journal of Symbolic Logic, 410):500-5 1976
[16] Fuentes and G. Navarro. Tiger-Alaska dataset, 2021. http://www.inf udec. cl/ Fuentess/datasetta craptss/graas...e. phpp accessed 20 May 2024.
[17] A. Garavaglia. Preferential attachment models for dynamic networks. Phd thesis I (research tu/e graduation tu/e), Mathematics and Computer Science, Jan. 2019. Proefschrift.
[18] V. K. Garg, S. Jegelka, and T. S. Jaakkola. Generalization and representational limits of graph neural networks. In ICLR, 2020.
[19] Geerts and L.. Reutter. Expressiveness and approximation properties of graph neural networks. In ICLR, 2022.
[20] Gilmer, S. S. Schoenholz, Riley, O. Vinyals, and Dahl. Neural message passing for quantum chemistry. In ICML, 2017.

---

[21] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IJCNN, 2005.
[22] E. Grädel, H. Helal, M. Naaf, and R. Wilke. Zero-one laws and almost sure valuations of first-order logic semiring semantics. In LICS, 2022.
[23] M. Grohe. The Deseriptive Complexity of Graph Neural Networks. In LICS, 2023.
[24] R. Kaila. On almost sure elimination of numerical quantifiers. Journal of Logic and Computation, 13(2):273-285, 2003.
[25] S. M. Kearnes, K. McCloskey, M. Berndl, V. S. Pande, and P. Riley, Molecular graph convo- lutions: moving beyond fingerprints. Journal of Computer Aided Molecular Design, 30(8): 595-608, 2016.
[26] H. J. Keisler and W. B. Lotfallah. Almost Everywhere Elimination of Probability Quantifiers. Journal of Symbolic Logic, (4(4):1121-44 2009.
[27] N. Keriven, A. Bietti, and S. Vaiter. Convergence and stability of graph convolutional networks on large random graphs. In NeurIPS, 2020.
[28] N. Keriven, A. Bietti, and S. Vaiter. On the universality of graph neural networks on large random graphs. In NeurlPS, 2021.
[29] T. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[30] N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[31] L. Larrauri, T. Müller, and M. Noy. Limiting probabilities of first order properties of random sparse graphs and hypergraphs. Random Structures and Algorithms, 60(3):506-524 2022.
[32] R. Levie. graphon-signal analysis of graph neural networks. In NeurlPS, 2023.
[33] R. Liao, R. Urtasun, and R. S. Zemel. A PAC-Bayesian approach to generalization bounds for graph neural networks. In ICLR, 2021.
[34] L. Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, 2012.
[35] Lynch. Convergence laws for random words. Australian J. Comb., 7:145-156, 1993.
[36] Lynch. Probabilities sentences about very sparse random graphs. Random Structures and Algorithms, 3(1):33-54, 1992.
[37] L. Ma, Lin, Lim, A. Romero-Soriano, P. K. Dokania, Coates, Torr, and S.-N. Lim. Graph inductive biases in transformers without message passing. In ICMI, 2023.
[38] S. Maskey, R. Levie, Y. Lee, and G. Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In NeurlPS, 2022.
[39] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
[40] C. Morris, F. Geerts, J. Tönshoff, and M. Grohe. WL meet VC. In ICML, 2023.
[41] L. Rampášek, M. Galkin, V. P. Dwivedi, A. T. Luu, Wolf, and Beaini. Recipe for general, powerful, scalable graph transformer. In NeurIPS, 2022.
[42] E. Rosenbluth, J. Tönshoff, and M. Grohe. Some might say all you need is sum. In IJCAI, 2023.
[43] R. Sato, M. Yamada, and H. Kashima, Random features strengthen graph neural networks, In SDM, 2021.
12

---

[44] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Nerworks, 20(1):61-80, 2009.
[45] Scarselli, A. Tsoi, and M. Hagenbuchner. The Vapnik Chenik-Chervoneniis dimension of graph and recursive neural networks. Neural Networks, pages 248-259, 2018.
[46] S. Shelah and J. Spencer. Zero-one laws for sparse random graphs. Journal of the American Mathematical Society, 1(1):97-115, 1988.
[47] J. Shlomi, P. Battaglia, and J.RR. Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2021.
[48] R. van der Hofstad. Random Graphs and Complex Networks. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2024.
[49] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. ICLR, 2018.
[50] R. Vershynin. High-dimensional probability: an introduction with applications in data science. Cambridge University Press, Cambridge, 2018.
[51] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
[52] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[53] C. Ying, Cai, S. Luo, Zheng, G. Ke, D. He, Y. Shen, and T. Liu. Do transformers really perform badly for graph representation? In NeurlPS, 2021.
[54] B. Zhang, S. Luo, L. Wang, and D. He. Rethinking the Expressive Power of GNNs via Graph Biconnectivity. In ICLR, 2023.
[55] M. Zitnik, M. Agrawal, and J. Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13):457-i466, 2018.
13

---

A Graph Convolutional Networks
In the body of the paper, we mentioned that our results can be extended to graph convolutional networks (GCNs) [29]. In this section we show how to extend our term language to capture them. Later in the appendix when providing proof details for our convergence laws, we will utilize the extended language, thus showing the applicability to GCNs.
GCNs are instances the message passing neural network in which the update function is defined as follows.
h(t1)=
Σ
WO
uEN(w) VIN(O)IW(())
To allow our term language to capture GCNs, we add the new aggregator:
GCN (x))
The language AGG|WME:R MEAA,, GCN, RW] the result of closing AGG WMEAN, RW] under this operator. The semantics are extended as follows.
E VEN(U.) (W((s))(No)
[T vil
With this operator it is possible to capture GCNs in the same way as MeanGNNs are captured (Section 4 Moreover, the extended term language permits arbitrary combinations of the GCN aggregator with other language features.
B Concentration Inequalities
Throughout the appendix, make use of a few basic inequalities.
Theorem B.1 (Markov's 's Inequality). Let X be positive random variable with finite mean. Then for any À 0 have:
E E
P(X 2 A)
S
Proof. See Proposition 1.2.4, p. of [50].
Theorem B.2 (Chebyshev's 's Inequality). Let X be random variable with finite mean and finite variance a², Then for any À > 0 we have:
d²
P(X - 1 2 2) S
X2
Proof. See Corollary 1.2.5, p. of (50)
Theorem B.3 (Chernoff's Inequality). Let X; for i S n be i.i.d. Bernoulli random variables with parameter p.
(1) For any X p we have:
P
Σ
X
1
5e nD
Emp
(2) For any X < p we have:
P
Σ
X;
S
se-
emp
Proof. See Theorem 2.3.1, p. 17 of [50) and Exercise 2.3.2, p. 18 of [50)
14

---

Theorem B,4 (Hoeffding's s Inequality for bounded random variables). Let X; for S n be i.i.d. bounded random variables taking values in [a, b) with common mean ps. Then for any X >> 0 we have:
(- (-m(b n(b
2A²
P
X
2 X
S 2xxp
a)²
Proof. See Theorem 2.2.6, p. 16 of 150]
Corollary B.5 (Hoeffding's Inequality for Bernoulli random variables). Let X, for i S n be iidd Bernoulli random variables with parameter Then any À >> 0 we have:
21²
IP
X₁
rpp 2 S 2 exp
n
C Proof for Erdős-Rényi distributions, the non-sparse cases
We new begin with the proof of convergence for the first three cases of the Erdös-Rényi distribution in Theorem 5. which we restate here for convenience:
Theorem C.1. Consider (ne) sampling a graph G from the Erdöö- Frdös-Rényi distribution E.(nn. p(n)) and node features independently from ii.dd bounded distributions on d features, where satisfies any of the following properties.
Density. converges to P > 0.
Root growth. For some K > 0 and 0 < B < 1 have: p(n)) Kn-8
Logarithmic growth. For some > 0 we have: p(n) = K log(n)
Then for every AGG[WMEAN, RW] term converges a.a.s. with respect to (Pn)NEN-
Note that throughout the following we use and denote both nodes and node variables.
C.1 Combinatorial and growth lemmas
Remark C.2. At various points in the following we will make statements concerning particular nodes of Erdös-Rény, graph without fixing graph. For example, we state that for any we have that its degree d((u) is the sum of n - 1 Bernoulli random variables. To make sense of such statements fix canonical enumeration of the nodes of every graph and view our node meta-variable as ranging over indices. So we would translate the previous statement as "for any node index u the Berouuli random variables."
degree of the uth node in ER(n, p(n)) is the sum of
Both the combinatorial and growth lemmas, and the main inductive results themselves require saying that certain events hold with high probability. Inductively, we will need strengthenings of these compared with the statements given in the body. We will need to consider conditional probabilities, where the conditioning is on conjunction atomic statements about the nodes.
Definition C.3. A A-description ((ū) is conjunction of statements about the variables of the form ue Fuj, which expresses that there exists an edge between иı and My- A A-description Wy Fug, A A... W4.,, Fuy,.. holds if and only if there is an edge between u, and Uj, for each f.
The reason for strengthening the results in this way will become clearer when we are proving the local weighted mean induction step EveN(ar) P(ū, v) h(n)(ū, r)). There will need auxiliary results to hold conditioned e'u, along with any additional requirements coming from previous induction steps.
We will first need few auxiliary lemmas about the behaviour of random graphs in the different ER models.
We will need to know that in the non non-sparse case, neighborhoods are fairly big:
Lemma C.4 (Log neighbourhood bound). Let p: + [o, 1) satisfy density, root growth or logarith- mic growth. There is R > 0 such that for all 8, f > 0 there is N E N such that for all n. 2 N, with probability at least 1 when drawing graphs from ER(n,, p(n)), we have that the proportion of all nodes such that [w)) 2 R Rlog(n) is at least 1 8.
15

---

We prove a stronger result, which allows us finer control over the growth in each of the non-sparse cases. The strengthening will involve the A-descriptions of Definition C.3
Lemma C.5. Take any /-description & on k variables, and choose S k. We consider k-tuples of nodes satisfying and the degrees of the ith node u4.
(1) Let p satisfy the density condition, converging that for all n 2 N, with probability at least 0 when drawing graphs from ER(n, ((n)),())..)) for all tuples u which satisfy & we have that:
Then for every e, 9 > 0 there is N N such
n <) < d(u,) n
(2) Let p satisfy the root growth condition, with p Kn- Then for every Rı and for every 8 > there N E N such that for all n 2 N, with probability at least 9 when drawing graphs from ER(n, p( for all tuples which satisfy we have that:
(0, and R₂ 1
R₁ Kn 2- < d(us)) < R2 R2
(3) Let p satisfy the log growth condition, with p = K log(n), Then for every Rí (0, and R2 > 1 and for every 6, 0 >> there is N E N such that for all n 2 N, with probability at least 1 - when drawing graphs from ER(n, p(n)). for least 1- 8 of the tuples à which satisfy we have that:
R1 K log(n) < d(u.)= RyK log(n)
Moreover, there is R3 > such that for every 0 > 0 there is N E N such that for all n 2 N, with probability least 0 when drawing graphs from ER(n, for all tuples ū which satisfy & we have that:
d(u)) RgK log(n)
Note that in the first two cases, we only have claims about all tuples, while in the third case we make an assertion about most tuples, while also asserting an upper bound on all tuples. The upper bound on all tuples does not subsume the upper bound on most tuples, since the former states the existence of an R3, while the latter gives bound for an arbitrary R2.
We now give the proof of the lemma:
Proof.
(1) Take e, 0 O. First, there is N₁ such that for all 2 N1:
(p(n) pl <
Now, any d(u) is the sum of i..dd Bernoulli random variables with parameter p(n): see Remark C.2 for the formalization. Hence by Hoeffding's ' Inequality (Theorem B.4) and union bound, there is N2 such that for all 2 N2. with probability at least 0, for every node have:
d(u))
D <E
n
Letting N max(N1, N2), the result follows.
(2) Take R1 E (0. 1) and R2 > 1 and fix 0 > 0. Again, any d(u) is the sum of n - i.i.d. Berouuli random variables with parameter p(n). By Chernoff's Inequality (Theorem B.3). for any node we have that:
IP (d(u)= S R₁ R2Kn2=P < exp (Kn (R1 1 R3 log R1))
Since R - - Rí log( R1) < O. by union bound there is N₁ such that for all 2 Nr, with probability least 0, for every node u we have:
d(u) Rí 1-1
Similarly there is N₂ such that for all n 2 N2, with probability at least 1 - 0, for every node u we have:
d(u)= < R2Knt-8
Letting N max(NN, N2), the result follows.
16

---

(3) Take R1 E (0, 1) and R2 > and fix 6, 000> > O. By Chernoff's Inequality (Theorem B.3 for any node we have that:
(d(u)= S Rí Knnnn' -) z n (Ra (R--RR11A (og(R:))
tends to infinity. Hence there is Since R1 1- R2 log(Rz) this probability tends N1 such that for all n 2 N1, for all nodes u.
(d((u) & R1 log(n)) A8
Let Bn be the proportion, our of tuples a which satisfy d, such that:
d(u;) S Rlgg(n)
(the 'bad' tuples). Then for n 2 N1, by linearity of expectation E[B,] s 08.
By Markov's Inequality (Theorem B.I have that:
06
P (B,, 2
That is, with probability at least - 0 we have that the proportionout of tuples ū which satisfy Ø such that:
d(u,) > R1 log(n)
least 1- 8.
Similarly, there is N2 such that for all n 2 N2, with probability at least 1 - we have that the proportion out of tuples which satisfy & such that:
d(u.) < R2 log(n)
is at least 1 - 8. Letting N = (1, the first statement follows.
To show the 'moreover' part, note that by Chernoff's Inequality (Theorem B.3 for any R3 > 0 and for any node u we have that:
(d(u) 2 R3Kn²=0) S KRs 11- log(Rs))
For R& large enough we have that (RR3 - 1 R3 log R3)) < 2. Hence taking union bound for every 0 > 0 there N N such that for all 2 N, with probability at least 1 when drawing graphs from (R(n,,(n)) for all tuples ä which satisfy have that:
d(u;)) R R3Klog log(n)
The basic form of the following "regularity lemma" states that for every k E N+ and S k, whenever we have a large subset of the (k: 1)-tuples (ū, v) with each u, adjacent to c, there is a large subset of the k-tuples such that each u; is adjacent to large set of v's such that (ū, v) S. The full regularity lemma states that this the case also when we restrict the tuples ū to a certain A-description.
Lemma C.6 (Regularity Lemma), Let N - [0, 1] satisfy one of the conditions other than sparsity. Take a A-description on variables and fix i k. Then for every 7,0 >> 0 there is N E N and > 0 such that for all n 2 N and ō < 8', with probability at least 0 we have that, whenever
C ((ū,v) v) (u)) u, Eu) is such that:
S
21-6
K(ū, u) ((T) A EEH
then there is S' {ū] (()) and d(w;) 0} such that:
S*
21 21-7
(u ((ū) and d(ui) > O]
fnr every E St we have:
(v U. v) E S)]
> 1 - 1116++8 88+
d(u:)
17

---

For this we make use of the following purely combinatorial lemma.
Lemma C.7. Take 0, > O. Let (Bi..... Bm) be a sequence of disjoint finite sets of minimum size and maximum size b. Take S C U.:11 B, such that:
|
21-5 5
m 1= [B
Let:
S' = {
|S n Bil
Then:
S
( 8)a
m
(a
6) + 5b
Proof. Let B = (Bi...., Bm). We look for upper bound on:
78S = |
m
To do this, take any (B,S) S) with proportion at least 1 - 8 which minimises 7B By performing series of transformations, show that can assume that (B,S) is of a particular form.
First, ensuring that S B; = B; for each E S' does not increase YB,s and does not decrease
the proportion
[8]
We can also make sure that [B|| = b for each E S¹.
Similarly, we can ensure that:
S B,]
[1 [
B.
for each i & S'
Finally, we can make sure that |B,] for each i & S'.
Now, using this nice form for (B, S), compute:
1- |S|
BB.s + (1 (Bss) (1 o)a
Σm Li=l
BB
7B,s + (1 - - -B,s)a
Rearranging we get:
S
(0 8)a
7B. 2 1
( 8)a + ab
as required.
Proof of Lemma C.6 satisfied.
We proceed differently depending which of the non-sparse conditions
We begin with the Density condition. Say converges to some p > 0. Fix 7,0 >> 0. Now choose 8 small enough. We will decide how small later, but we need at least < p.
By Lemma C.5 (1) there is N such that for all n 2 N, with probability at least - 0, for all tuples which satisfy ((u) we have that:
c) d(u)) < n(p + c)
Condition the event that this holds.
Take any 5' and {(ū,v) v) ((ū) Eu) such that:
S
K(ū, v) ((() A E.Jo 2 1
18

---

Let:
Ke (ū, E SH
S' = u ( and
2 1 - (6 + 82)
d(u;)
Applying Lemma C.7 with 6 8",
n(p E) and n(p + E). we get that:
S
(8 2 - 8)n(ū
2
{ū ((ū) and d(u,) > 0H1
(6 + 82 - 8)m - + 6n +
8(p c)
1
8 6) + (++
By making c and 8' small enough, we can make this greater than 1 - ".. This completes the proof for dense case.
We now give the proof for the case of Root growth. Let p(n) = Kn -9 Fix 7,0 0 > 0. Choose 8' > 0 small enough. Also choose Ri E (0, 1) and R2 1.
there is N E N such that for all n 2 N, with probability at least 6, for all tuples ū which satisfy Φ(ū) we have that:
By Lemma C.5 (2)
RnKn' d(u.) < RgKn
Proceeding analogously to the dense case, we have that for all 5 < d':
S
8R 1
(ū ((ū) and d(u,) > 0Hf 2 ÖnR, 1n + Ro K
8R1
8R1 + R
By making 8' and R2 - Ri small enough, proof for the root growth case.
7. This completes the make this greater than
Finally, we give the argument for the case of Logarithmic growth. Let p(n) = K log(n)) Fix 7,0 0. Choose 8. > small enough. Also choose R₁ (0, 1) and R₂ > 1.
By Lemma C there is R& > 0 and N E N such that for all n 2 N, with probability at least 1- when drawing graphs from ER(n,p(n)) for at least 5 of the tuples which satisfy d(ū) we have that:
K log(n) d(u.) < K2 log(n)
and moreover for all tuples ū which satisfy d(ū) have that:
d(u4) < R3K log(n)
Now, let:
Q= {ū] R2 KRKKlggh log(n) < d(ui) < R2K log()))
For large enough we have both:
Q
21 21
Hū ((ū) and d(u;) > 0)
and (using the fact that outside of Q all nodes u, have degree at most R&K log(n)):
((ū v) ((ū) A Ev and E QH
21
K[ū, v) ((ū) A Eu)l
Since we have control over Ç. it suffices to restrict attention to:
S C ((ū, v) ((ū) A uvEv and ū E Q}
Then, analogously to the dense case, we have that for the worst case, for every 8 < 8':
St
5R
H σ(ū) and d(u,) 0}
8R + R
By making and R2 - RS small enough, we can make this greater than -
This completes the proof of Lemma C.6 for the logarithmic growth case.
19

---

The following lemma will be needed only in the analysis of random walk embeddings. It gives the asymptotic behaviour of the random walk embeddings in the non- cases. We see that the embeddings are almost surely zero.
Lemma C.8. Lei p: N + N satisfy density, root growth or logarithmic growth. Then for every k E N and every e, 5, > 0 there is N E M. such that for all 2 N with probability at least the proportion of nodes v such that:
||wx(()]l <e
is at least - 8.
Proof. We start with the Dense case. Let p converge to P > O. Take c, 6, > 0. By Hoeffding's Inequality (Theorem B.4] and taking a union bound, there is N such that for all N with probability at least 1 - we have that:
d((v) - pm en
Condition this event.
For any node e the number length-k ts walks from e is at least:
(Φ - e)m)**
By removing the last node of the walk, the number of length-k walks from v to itself is at most the number of length-(A: (A 1) walks from v.
The number of length- - 1) walks from is at most:
(Φp + c)m)*=1
Thus the proportion of length-k walks from o which return to e is at most:
(( + c))) k-1
( )
(5 (5- n-
( e)m)
This tends an n tends infinity.
We now argue this for the Root growth case. Let = -3
As in the proof of Lemma C.6 by Chernoff's ' Inequality (Theorem B.3) and taking a union bound, there are R1 that for all o:
Rg and N such that for all 2 N with probability at least 9 have
Kn d(v) R2Knt-8
Then, as in the dense case, the proportion of length-k walks from which return to is at most:
(RyKn' R/. n
(R1Kn
R1
which tends to 0 as n tends to infinity.
Finally, we argue this for the Logarithmic growth case. Let p K log(n)) Take e, 6,0 > 0.
As in the proof of Lemma C.6 by Chernoff's Inequality (Theorem B.3), there are R₁ Ra and N such that for all n 2 Ni with probability at least 1 0 we have that for at least 1 - proportion of nodes
R₁ log(n) < d(v) < RgK log(n))
(*)
Moreover, by Chernoff's Inequality and a union bound, there is R3 > such that for n 2 N2 with probability at least 1 - 0 we have that for all w:
d(v) < RaK log(n)
Let N max MNax(N,, N2). Take n 2 N. We will condition on the event that the above inequalities hold.
20

---

Take any node such that equation
+
holds. Then, the number of length-k walks from is at least:
K K (og(n)((1 ( log(n)))*-1
The number of length-k walks from v to itself is at most:
RRa K log(n))$-1
Thus the proportion of length-k walks from e which return to v is at most:
(RyK log(n)) log(n)) R1 (1 - 8) K log(n))){--I This tends to as n tends to infinity.
R
Ri (1 5)k-1 log(n)
Finally, we need a simple lemma about division, which has a straightforward proof:
Lemma C.9. Let x, y, 2, w R and Ç, v, > with v & be such that |x yl < and
I w & while [x), < Ω and z > Then:
y
w
v(v {)
C.2 Proving the inductive invariant for the non-sparse cases, and proving the convergence theorem for these cases
With the growth lemmas for the non-sparse cases in hand, we return to presenting the main proof of Theorem C.I. the convergence theorem for non-sparse ER distributions.
Throughout the following subsection, for notational convenience allow empty tuples.
For tuple à in graph let GrTp(u) be the graph type of ú. For let GrTp; the set of such types with k free variables. For any E GrT Pы let:
Ext(t) = {t' (ū, v) E GrT (t((ū,)) F t(T))
For any free in let:
Extu, (1) = (f((0,)) E GrT ((( F t(T) A u,Eue
We now are ready begin the proof of Theorem 5.T for the non-sparse cases. This will involve defining controllers and proving that they satisfy the inductive invariant.
Let be the probability distribution of the node features, which, for the sake of convenience, we assume to have domain [0, 1jd. The domain [0, 1] can be replaced by the more general domain Ja, 6jd in the results and proofs without further modification. But we note that the domain [0, 1] is already sufficient for the results to hold in the general
which apply to graph distribution D with features in [a, bjd. Modify this distribution to D' by applying the function
Indeed, suppose r(x)
E + (z - (b - a) to the features. This is now distribution with features in [0, 1] Modify r to r' by replacing each H(x) by (H))))) where F' is the function + (b a) + a. Then evaluating T' on D' is equivalent evaluating on D.
Note that in each case the probability function p(n) converges some ş (which is 0 in the root growth and logarithmic growth cases).
Recall from the body of the paper that (ū, d) feature-type controller is Lipschitz function taking as input pairs consisting
d-dimensional real vector and a ū graph type. Recall from Theorem 5.3 that for each term æ, need to define controller e, that approximates it. We first give the construction e and then recall and verify what it means for e, to approximate n.
Take à E (00 1]d)& and L E GrTpg. where & is the number of free variables in
When H(u) define:
ex (a. t) a
21

---

When π = a constant, define:
(ā. ==
When rw(u) define:
ex ( () = 0
When x = f(p....... Pr)) define:
cx(a, [en (ā, .)....,:.. ep. (a,
We start with construction for the global weighted mean. For any ((u) E GrTp, and ((, v) Ext((), define axt,, t') as follows. As an extension type, t' specifies some number, say т, of edges between the nodes ú and the new node v. Define:
a(t,t') p- -))-
Note that in both the root growth and logarithmic growth cases, a(t, t') is non-zero precisely when specifies edges between and These relative atomic rype weights will play a key role in the construction.
Now consider term = En p(ū, v) h(()(ū,
Recall that the semantics are:
Σ
Ip(ū, (ú, c)llch(n(a,e)))o
BEG
Σ h([1(,,))lc
vEG
Define:
ta.
en (a,
Ia (ū,
where:
[+(āt))
Σ all,t) E leplā, b, ())((en(aa
bui
EEEx((A)
and:
9n (a, =
Σ alt,t) EEExt(
E (M(e,(a,,b,t)) buF
Note that when ş = (as in the root growth and logarithmic growth cases), we have that: if t' specifies no edges between and
(11,, (') 0 otherwise
Therefore the controller becomes, letting e be the type with no edges between ūł and et
Eew (ep(a, b, 1 (h(e,, 19))]]
ex ca, t)
Enee ba,
For the local weighted mean case, given ((ū) GrTp, and l' E Exta, (t), define on,, (1, 8') as follows. Let r be the number of edges specified by l' between ā and v. Define:
au, (t,t') = pn(( k-
Consider EveN(u.) ((ū,v) h(n(ū, v)). Define:
en (ā, t) = (ā
9 (a,t)
where:
(a(a))) =
Σ
On, (1,1')
bwF b, ba
r' r'EExt., (t)
and:
gr (a, =
Σ
Oue (1,t') (e,
b
D'EExt., (0)
With the controllers e- defined, we now prove that they satisfy Theorem (Theorem 5.3 We state the strengthened version of this result here using the notation of A-decriptions from Definition C.3
22

---

Lemma C.10. For every e, c, > 0 and A-description (ū)), there is N E N such that for all n 2 N. with probability at least 0 in the space of graphs of size n, out of all the tuples such that (ū). at least ō satisfy:
e (H( GrTp(a)) [+()]] <E
Proof. Naturally, prove the lemma by induction.
Base cases H(v) and constant c. These are immediate from the definition.
Base case rw()). This follows by Lemma C.8
Induction step for Lipschitz functions f(P
Take e, 6,
and A-description (ū)). By the induction hypothesis there is N N such that for all n 2 N and for every i S т, with probability at least 0, we have that out of all the tuples such that (u), at least 8 satisfy:
ee (H(a), GrTp(a))
[I-"|] <e
Hence, with probability least 1 r0, out of all the tuples such that ()) least ró satisfy this for every i & r. Condition on this event.
Take any such tuple ü. Then by Lipschitzness of we have that the normed distance between:
ex (H(H) fle, (H(a), GrTp(u)), ................................ Cp. (H(ū), GrTp(u)))
and:
[π()]] (")) (o)())))))
is Lye, where Ly is the Lipschitz constant of f. Since L is constant, this case follows.
Inductive step for P(ū, v) h(n(ū, v)).
Take c, 8,0 80 O. Take A-description (ū)
By the induction hypothesis, there N1 such that for all n 2 N1, with probability at least out of all the tuples (ū, v) which satisfy (ū), at least 1 - satisfy:
(e v), GrTp(ū, v)) [p(ū, w)]l <6
(tp)
and:
(H(T, v), GrTp(u, v)) [n( <e
(t,)
Take 7 > O. We will choose how small ς is later. By Lemma C.6 there is Nr, > Ni such that for all N,,, with probability at least 1 1 0, out of all the tuples ú such that ((). at least - 7, at least 1 - (8 52) of the v's satisfy equation (ia) and equation (tx)
Now consider t(ū) E GrTPp and take any ('(ū,u) u) E Ext(t). For any tuple ū of nodes such that GrTp(u) define:
[t(x]] = fo t'(ū, b)}
Since pnn) converges to p and Ext(t) finite, there is N₃ such that for all N3 with probability at least 1 - we have that for every pair (t, and tuple ū of nodes such that t(ū):
[t' (z)l a(t,t') t²) < 2k+1
Next, for any tuple ū consider the function:
(), = e, (Ha(U, GrTp(ū u))e(e GGTT
Note that the function:
(a. e, b, (a.
is bounded. Let A be the diameter of its range. This also bounds fo.
23

---

We will now apply Hoeffding's Inequality to Ev ((a,o) (ū, v). Note that the number of summands is [[t'(a) (ū)] and the summands bounded by A. Furthermore, the summands independent and have expected value:
E
eep b), ()) b).
b
Hence, by Hoeffding's Inequality (Theorem B.4 for any a the probability that:
[['(()]] n
1
Σ
oa)
E (H b), (i
2k+1 (V)
is at most:
[['(())
2d exp
2A
By equation there is N4 such that for all n 2 N4, with probability at least - 0 for all l' such that (t,, (') we have that for every tuple w:
2d exp
<
08
2A²
Let Bn be the proportion, out all tuples ú which vi(i) hold such that:
Σ F.( o(F(
[t( n
E b-F
[epp(Ha(u,,)) (MC,
b).
1 26+1
n
Note that the property above is exactly the event whose probability is bounded in equation We can express B, the mean of of indicator variables, one for each tuple such that ( holds. Each indicator variable has expected value at most 65 by equation
and equation
Then by linearity of expectation, B[B,]] < 08 for all 2 Na. and hence by Markov's Inequality (Theorem B.1
08
IP [B, 5)
0
Therefore, for all n 2 max(Ns, N4), with probability at least 0 for at least 1 - of the tuples ū for which (z) holds we have that:
[t((a] n
1
E
(H b), (H b),{()
b-F
26+1
and therefore, by equation
and the definition of fz:
Σ (a, - (H (Ha(W) GrTp(T)))))))))))))))))))))) <E
(A,)
Similarly, for any tuple i consider the function:
( v) = (Ha((, GrTp(a,
As above there is N₂ 2 N₂ such that for all 2 N₂ with probability at least 1 we have that the proportion out of tuples ū for which (ū) holds such that:
Σ -ft (ū, v) 9m (Ho(a), GrTp())))))))))))))))) <E
(4g)
is least 1 8.
RReaal that vi the A-description which condition the tuples a in the inductive invariant.

---

Take n 2 max NN,,N, Ny, Ns, Na, N₃). For such an n. these events above hold with probability at least 56. So from now on we will condition on the event that they hold.
Take any such tuple n. Let = GrTp(ū). suffices to show, using the definition of the interpretation of the weighted mean operator, that:
Loll, ())lk w)I) (H(((()) (=(Ho(u),t)
< ((,
L( v)l)
for which can make arbitrarity small by choosing e, 6, small enough.
By Lemma C.9 suffices to find C(e, o, d,),,,((,, which we can make arbitrarily small and constants Q > 0 such that:
Σ Io(a, -
< <((c,,,)
(1)
h(n(a, w) 9n (H)
< E,),
(2)
Σ Lota, ailia,)lli v)]h([n(( v)I)
< Qn
(3)
Σ 1 M[[n(, w|n
< <nn
(4)
Vi _ d: Σ M(In(a, wiD)
> vn
(5)
For equation 3 and equation 4 we can use the fact that [p(u, v)l and [n)ū, v)] are bounded
and that h is Lipschitz bounded domains. For equation (5) use the fact that [1) v)] is bounded and that the codomain of h is (0, oo)d.
The proofs of equation (T) and equation (2) are very similar. We prove equation since is slightly notationally lighter. Let:
(a) = 1 n
Me, (H)(
Let be bound the norms of (e, b, 1')) and h[[((ū,)]], By equation have that:
M(b(a, of (1)) < (1 (1- (6 +3)) (6 + 52)222
We can make the right-hand-side as small as we like by taking e and sufficiently small.
Now note that:
9 ( (1) = Σ (Z, v)
Hence by equation
we have that:
(I 9x (H)G
Therefore:
Σ M(nn(a w/>|
(HH(
<<1 <11- (8+ 5²) + (8 82)2n +
which make small as we like by taking and small enough.
25

---

Inductive step for (veN(u.) p(ū, v) h(n(a, v)).
We proceed similarly to the global weighted mean case, this time making use the conditioning A-description in the inductive invariant. Indeed, notice that when we apply the inductive invariant below, we add u; Ev to our condition.
Take e, 6, 0 0. Take A-description (()
By the induction hypothesis, there N1 such that for all n 2 N1. with probability at least out of all the tuples (z, 2) which satisfy (T) A E. at least 8 satisfy:
(H u), GrTp(u, u)) Ip(u, x)ll <<
(t/m))
and:
(H, v), GrTp(ū, v)) [v(ū, w)]l <
(th)
Take y > 0. We will choose how small y is later.
By Lemma C.6 there is N. > Ni such that for all n 2 Ny, with probability least 1 the following event happens. Out of all the tuples ū such that ((ū) A 3o: u,Er, proportion of least y of them satisfy the following. At least 1 (6 + 5²) of the nodes for which (ū) A Ev holds also satisfy equation
Floo and equation plocp.
Now consider t(ū) E GrTPp and take any t' v) E Ext,,, (t). For any tuple ū of nodes such that GrTp(u) f, define:
[t(w]] = fo ((4)) (()
By Lemma C.5 we have that all the non-sparse cases there R > 0 and Ng such that for all 2 N3 with probability at least 0, the proportion of all tuples for which (b(ū) holds such that:
d(u,) Rogg(n)
least 8. Then, as before, there is N4 2 N3 such that for all n 2 N4. with probability at least 1 0, for all pairs (1) the proportion of all tuples ū for which (ū) and Mū)) hold such that:
[+)[ d(u,)
att, < 2k+1
For any tuple ū define the function:
fa v) (H v), GrTp(u, o))k(e, v). GrTp(a,)))
Taking A as before, by Hoeffding's Inequality for any ū the probability that:
ea [['(w]] E d(u;)
Σ
(H, ())
d(u))
baz
(EN(M))
2 2
most:
2d exp
2A
Using a similar argument to the global weighted mean case, there is Ns such that for all n 2 Ns- with probability least - 0 for all E' such that axt,, t') > 0 we have that for at least 8 of the tuples ū such that (ū) and t(ū) hold:
edx (- (-=((())) 2A
< A5
We now proceed as in the global weighted mean case, creating a random variable similar to B, and making using of linearity of expectation. We get that for all 2 max(Na, N4, Ns), with probability at least for at least - of the tuples ū for which vi(ū) holds we have that:
n Σ fa(a, (Ha(a), (reo),,rrTTT)))) <e
(A loc
26

---

Similarly, with gf. defined as above, there is No such that for all 2 No. with probability at least 1 for least 8 of the tuples ū for which (ū) holds we have that:
Σ Sū (=H
GrTTe(())GGGTT))) GrTp(T)) <E
(Abo0 log)
(A
With equations Flc
Floc
loc
and
loc g
established, we can now proceed as before, making
use of Lemma
This completes the proof of Theorem 5.3
Applying the lemma to prove the theorem. To prove Theorem C.1 note that e,, only function of the Gr (since is a closed term), while GrTPu Pu consists of single type, T, which is satisfied by all graphs. So e, is constant.
D Sparse Erdős-Rényí and Barabási-Albert
We now give the proof for the sparse Erdös-Rényí and Barabási-Albert cases of Theorem 5.1 In addition, we extend the result the language AGG [MEAN, GCN, RW] defined in Appendix We state the full result here.
Theorem D.1. Consider (Un)neN sampling a graph G from either of the following models and node features independently from ii.d. bounded distributions d features.
The Erdös-Rényi distribution ER(n, p(n)) where p satisfies Sparsity: for some K >>> O we have: p(n) Kn-1
2. The Barabási-Albas model BA(n, m) for any m 2 1.
Then for every AGG(WMMAN, GCN, RW] term converges a.a.s. with respect to (pn)neN-
As discussed in the body, this requires us to analyze neighbourhood isomorphism types, which implicitly quantify over local neighbourhoods, rather than atomic types as in the non-sparse cases. Remark D.2. Formally, a k-rooted graph a tuple (T, ū). At various points below to lighten the notation drop the 'ū' and refer simply to k-rooted graph T.
D.1 Combinatorial tools for the sparse case
As in the dense case, before the underlying random graph model that we can use tools.
analysis of term language, prove some results about
The key combinatorial tool will use is the following, which states that for any tuple of nodes the proportion of nodes v such that (ū, v) has any particular neighbourhood type converges. Definition D.3. Let (T, w) be k-rooted graph and let (T", t7, y) be (k 1)-rotted graph. Then I" extends T if T is subgraph of T'. Let Ext(T") be the set of all (k + (1)+11)--aa 1)-rooted graphs extending (T, w).
Theorem D.4. Consider sampling a graph G from either the sparse Erdōs-Rénye or Barabási-Albes distributions. Let (T, w) be k-rooted graph and take E N. Then for every (k: + 1)-rooted graph (I', y) which extends (T, w) there is qr r E [0, 1] such that for all 9 > 0 there is N N such that for all n 2 N with probability at least NG (u) = (T,w);
we have that for all k-tuples of nodes u such that
He I v) = (T", w.
QT
n
Moreover, we have that:
9T/T
(T)
We refer the GT relative neighborhood weights. They will play role in defining the controllers, analogous to that of the relative atomic type weights a(t, E') in the non-sparse case.
27

---

Theorem D.4 follows from what is known as "weak local convergence" in the literature. It is essentially non- parom-eaeeeteeeeed version of Theorem D.4
Definition D.S. A sequence (Un)neS of graph distributions has weak local convergence if for every k-rooted graph (T,, ti) and E N there gT E [0, 1] such that for all e, > 0 there is N N such that for all n 2 N with probability at least
we have that:
(T, w)}
QT <E
7
and moreover:
Σ
=
RT
Theorem D.6. The sparse Rénōs-Réénii and Barabási-Albes distributions have weak local conver- gence.
Proof. See 44 Theorem 2.18) for the sparse Erdös-Rényí distribution and 17 Theorem 4.2.1] for the Bllert distribution.
Proof of Theorem
D.4
Take E Ext(T). There are two cases.
Case 1. There is path from to some node of ú in T".
Set Gr/r = O. Note that in this case, for all tuples a such that NY (ū) T we have that:
{u 1 (ū, v) = (T", ú. 3)} S W (u:) Since / (u:) is determined by T and is thus of fixed size, the proportion:
Ke W (ū, v) (T" w. y)
tends 0 as n grows. This completes the proof for Case
Case 2. There is no path from y to any node of in T". Then for all tuples such that (T)) = we have that:
E0 No (1, v) = (T' 8. v))
Ev
N = No (v)) (T)
Hence:
KE N (1) N (w)) W2(
H ( (T' 9)
n
n
n (v) ~ (W)
Also:
{u No (ū, (T', ,, v)
n
By Lemma 5.3 (with & = 1) we have that:
(1)))()) = (v)
converges to some limit oryr == (NTT'()) (v) asymptotically almost surely, while:
(
T
converges to 0. This completes the proof for Case 1.
Finally, to show that ETEEE((T) 1r 1, note the set:
(NT (v) (T', w. E Ext(T')
contains all 1-rooted graphs up to isomorphism which can be the t-neighbourhood of a node. There- fore, by the "moreover" part of Definition D.5 we have that:
Σ
GTAT =
9NT' (x)
(Tx)
E'E)((
28

---

D.2 Proving the inductive invariant for the sparse cases, and proving the convergence theorem for these cases
We now begin the proof of Theorem D.1 Recall from the body that we will do this via Theorem 5.6 which requires us define some Lipschitz controllers on neighbourhood types that approximate given term и relative to a neighbourhood type.
Throughout the following, it will be convenient to assume for every k--roote graph isomorphism type (T, ū) canonical ordering nodes T {s1,...., such that:
the first nodes in the ordering are a and for any graph G, tuple of nodes ū and e E with '' < é the canonical ordering of Ne gr is an initial segment of the canonical ordering of (T()).
Again we will use F for the probability distribution of the node features. For each subterm æ of т, its reach, denoted (each(z) is natural number defined as follows:
Reach(H((u))
Reach(c)
Reach(rw(v))
Reach([(P1.... .r))
max Reach(p:) iSr
Reach
Σ
p(n) = max(Reach( Reach(1)) +
(EE((u)
Reach
Σx
p*
0
Take a subterm T. Let the number free variables in m. We now define the controller at m for every k-rooted graph (T', V). The controller will be of the form:
e ((0, 11 + Rd
Note that when [7| = -0 this is a constant.
Recall from Theorem 5.6 that goal is to ensure the following correctness property for
controllers e
Property D.7. Let т be any subterm T and let E Reach(w)). Consider sampling graph G from either the sparse Erdös-Red Réndi--Rééyii or Barabási-Albert distributions. For every k-rooted graph (T, w) and e, A 0, there is N E N such that for all n. 2 N with probability least - 0 have that for every k-tuple of nodes u in the graph such that Ne(u)) (T,w), taking the canonical ordering Ne(u)- {s1,...,
- (Ho(s1)..... Ho(sTT)) ((((s))
[T] <e
For notational convenience, we allow each ef to take additional arguments as input, which will ignore.
Proof of Theorem 5.6 We give the construction of the controllers in parallel with the proof of correctness.
Base case π = H(u:).
Here é = Reach(T) O. Let ef (a) = a, the feature value of the 7h node in the tuple. Note that for any k-tuple nodes ú the graph we have:
(Ho(s))) Ha(s))) = Ho(s:)
= =[<(a]]
Base case π = c.
Let of (a) =
29

---

Base case π = rw(u:).
Then 8 Reach(=) d. Note that the random walk embeddings up length d entirely determined by the d-neighhourhood. Therefore, given rooted graph (7, vi), there is ry such that:
[rw(u,)] rr
for all tuples ū such that Ni(u) =T. So set:
(a) PT
for any a.
Inductive step for Lipschitz functions π F Pr).
Note that = jax Reach(p:).
Take a k-rooted graph (T. For each i S r let T₃ =
N Reach(ps) (1). Define:
(a)
(()((()))))))
(a))
Now take 0 > 0. By the induction hypothesis, there is N such that for all 2 N with probability at least 1 - we have that for every k-tuple of nodes ū in the graph, letting T = (z) for every $
[ (Ha((1),.... .... H...HHH((11)1)) - [0,
(es <e
Hence, by the Lipschitzness of F we have:
||e (H. Ho(s))) [T(U]]| < Lpc
where Lp is the Lipschitz constant of F.
Inductive step for local weighted mean π = Em))( p h(n).
this step we use that the value of a local aggregator is determined by the values of the terms is aggregating in the local neighbourhood.
Take a k-rooted graph (T, w). where is the number of free variables in w. Note that max (ax(Reach(p)) Reach(n)) +
When w; has neighbours in T, define:
(a) =0
and note that for any k-tuple of nodes in the graph such that Ne(ūi) T we have:
[T)) (Hc(s))..... H.((s))
So suppose that wN has some neighbours T. Enumerate the neighbours as:
NT (w:) = -v...... .yrr
Define the Lipschitz function:
b,) = Ej=o azh(b,)
WMeanr(an...... a,, b bi,.b,,,,,,
Σx h(bb)
Note that whenever N (ū) (T, w)) letting N (u.) = fui...., Ar be the enumeration of the neighbourhood of u4 given by the isomorphism, we have that:
T [[]] (Meanr([p(u,, v:), Lo(a, 1. In(a, vi)..... In(a, v+)l)
For any yj E (w:), let:
T, == N 1 (w0 yi)
Tí. NT NT Resach( /) (1, 83)
T = .T /
(e)ch(n) (7, y3)
30

---

Further, for any à E ((0, 119) let ag and aj be the tuple of elements of corresponding to the nodes of Tf and 2 respectively.
Let:
27 a WMeant (af) Th (a.), Enj (a,),
2 (a"),
Take e, 0 > 0. Applying the induction hypothesis to the term p(ū, v) and to n(ū v), which have Reach at most - 1, and using the fact that _ (wx) is finite, there is N such that for all n 2 N with probability least 1 8, for every Vj N (wx) and every (I: + 1) 1t-uue of nodes (ū, v) such that N 1) = (T), 80, y2) we have that both:
|ep Th (Ha(s)),.... ((((rr))..,H(((rg))))) Looo-ooa,,,,, - w|]l <e
and:
@ (Ha(s)), .... Ho((1191))) In(a,, wi] <c
Under this event, by equation and the Lipschitzness of WMeany we have:
(Hc(s)) Hc(sm)) [=]]]]] Lye
where Ly is the Lipschitz constant of WMenny
Inductive step for the GCN aggregator π GCN,EN(u.)
This step is very similar to the previous, where we again use the fact that the value of local aggregator is determined by the values of the terms it aggregating in the local neighbourhood. The only difference is that we now have a different Lipschitz function:
GCN a.) =
W (w:) |N (w)) 4
1=1
The rest of the proof as before.
Inductive step for global weighted mean π Eg p* h(n).
Note that f = Let = max (eaxhhechhp)). Reach(n)) Take a k-rooted graph (T, i). For any tuple and (k 1)-rooted graph (T", w. extending (T, w) let:
[T) = K N v) = (T", w,
By the parameterized Weak Local Convergence result, Theorem D.4 for every such T" extending there is relative neighborhood weight @rirT E [0, 1] such that for all c, 0 > 0 there is N E N such that for all n 2 N with probability least 0, for every k-tuple ù such that Ne(u) = T we have that:
[T (ū)
4ryrr <e
and moreover the relative neighborhood weights sum to one:
ΦTIT" =1
Consider any (T,) Ext(T). In order to define the controller, we need to identify the nodes
in the canonical enumeration corresponding to AT - (z). Let:
Pr N (+)
Given tuples of Red-vcctors (a), (a)..... .d....... apy and b (b (b, b ). let Arrange (ā. b) be the -uple vectors obtained by assigning the a, to the nodes in N/ (+) and the b, the remaining nodes in T', according to the canonical enumeration of T".
Define the controller:
f 9 a
cf (aa))
31

---

where:
(T(a)=
=
E
E b
T (arangerr((abb)) b)) li(e, (Arranger (a, (a,)))) 9ryp"
(T)
and:
- a1
ax)==
E
E b-F
hle, (araaneer((a 9T/T"
(T))
where in both cases the expectation is taken over b,'s sampled independently from node feature distribution F.
Since:
T cp (a apri (r.....,ar(.)
and:
h(e, (ai...., ar)
are bounded, and Ext())( Qr(T" converges, these sums converges absolutely, and hence the controller is well-defined.
This completes the definition of the controller. We present the proof that it is correct.
Take e, 0. Take finite S C Ext(T) such that:
Σ T'ES
ITT >1-6
(O)
and each QrTr for T S.
The guarantee given when we applied the parameterized version of Weak Local Convergence, Theorem D.4 is that there is N₁ such that for all n 2 N1 with probability at least 0, for all T' and every k-tuple such that ( T we have that:
T (ū)
4rpr <E
(+)
Define the function:
( b) = e Th (Arrangerr (ā. b)) (Arranger ())
and similarly:
g (a, = h(e, (Arrange,- b)))
Note that these are just the integrands used in ff (a) and gf (a).
Now, for any (k + 1t-tuple of nodes (ū, u) let a be the tuple of node features of A (π) and ((a,v) be the tuple of node features of the remaining nodes in A canonical enumeration of N (ū, v).
V (ū, v), ordered as in the
Note that f bounded, say by A. Then for every > by Hoeffding's Inequality (Theorem B.4 for any tuple such that N ( = and E S we have that:
P
Σ pa
fi (,,,
[T'
E bwF
[f 6)]
(T)
< 2exp
12
2n(g' - c)72
2exp
1
32

---

where in the last inequality we use equation (1) Hence, taking union bound, there is N2 such
that for all n 2 N2 with probability at least 1 1- for all such that (N T and T" Ext(T)
we have:
Σ
fa (B(.))) (T) b
E [fa(a",
[TT
(S..))TT
we divide both sides of the inequality through by n. take a y below 1, and apply equation again, conclude that there is N4 such that for all n 2 N4 with probability at least 8, for all u such that N (a) T and T E Ext(T) we have:
i
Σ
(a ([(a.,(aae))
QTIT" [F b)]
<C
(4,)
b
(a,
Similarly, there is N3 such that for all Ns with probability least 0, for all a such that (T(1) = and 7 E Ext(T) we have:
Σ
(a (aa,,((a.)))
QTIT"
[o (a 5)] b
<E
(4g)
n
(E,))
By the induction hypothesis, there is No such that for all No with probability at least for every T' E S and every (I: + 1t-uue of nodes (ū, v) such that No (ū, v) = T' we have that both:
T' (Ha(s))...... Ho(srr)) - lo(a, v)] c
<e
(t,)
and:
| (Hocss).......Ha Ha(((T()) In(a, <c
(t,)
Let N = max(N; N2, N3, N4, Ns, No) and take n 2 N. Then for such n the probability that these six events happen is at least 1 60. We will condition on this.
Take any k-tuple of nodes such that We(Ut) T. It suffices show, using the definition of the interpretation of the weighted mean operator, that:
Ie(a, v) ((I((, w)l) (Mc(u))....., Ho((x)) of (Ha(w)), Hu(w))
Σ. M[n(,, +)])
for some 1 which we can make arbitrarily small by choosing small enough.
As above it suffices find Ç, O which we can make arbitrarily small and constants 2 such that:
Ie(ū, v)] Ff (H)c(s))....... (o0g))),,,,,(((rr))) <<
(6)
Σ M([((a,)))) - (Ha(ss)) Ha(smi))
<E
Σ Io(a, (a(a,,))lit w)]l((Ii v)Il)
< S2
(8)
> h([n(a, M/n| < sn
(9)
Vi < d: Σ b(nn( uyD)
> mn
(10)
33

---

Equation 8). equation (9) and equation (T0) follow as before. We show equation 77) the proof of being similar.
equation
By equation
We have that for every w:
([n(a, +)]l g5 ,8(a,))) /lawo)//E
<c
Hence:
E _ot Blaoly
h([n(a, v)]l
<6
n
Now:
Σ 9 a" ((a.))) 1
Σ
Σ
(a bla.v)
T E'EEx((T
N (1,7))77'
Letting A be a bound on the norm of o (a", B(a,v)), by equation
we have that:
Σ 22 (( - 1 Σ Σ
(a B(HD))
<eA
THES (a,
By equation
we have that:
Σ
Σ
((a",,(un)) Sa [(ur))
Σ
E
Se
b
T'ES ((,))))
T'ES
Finally, by equation
again we have that:
ITIT
E [o b)] - g (at)
<ea
b-F
T'ES
This completes the proof of the inductive construction of the controllers, thus proving Theorem 5.6
Application to prove the final theorem, Theorem 5.1 for the sparse Erdós- Rényi and Barabási- Albert cases. To complete the proof, we note that the term has free variables, and as subterm of itself has reach O. The controller e of is constant x, and hence by the induction hypothesis applied it, for every e, there is N E N such that for all 2 N with probability least 1 we have that:
||[>] 2 <c
E Proof for the stochastic block model
We now prove the convergence result for the stochastic block model. The proof follows the same structure as the density case in Theorem 5. except that the notion of graph type is augmented slightly. We therefore only indicate the differences in the proof.
For this is it helpful to be able to remember the community to which each node belongs. Given any graph G generated by the stochastic block model and node v, let C(u) E {1....,m) m) be the community to which belongs.
To prove the result, we first need that the random work positional encodings converge, as in Lemma C.8 In fact they converge to O.
N + N and as in Theorem 5.1 Then for every E and 0 > 0 there is N E N such that for all n 2 N with probability at least 1 for all nodes v we have that:
Lemma E. Let ni,...
||wa(v)]| <e
34

---

Proof. For each j {l....... m.. let "i converge to 9j. Let:
P1, ... + 9m (a.m.) m.j
Note that nry is the expected degree of node in community j. By Hoeffding's Inequality (Theo- rem B.4] and union bound, there N such that for all N with probability least 1 8, for all we have that:
d(r)) ro(w) <c
n
Take 2 N and condition on this event. Take any node v. When rC(e) the node vo has no neighbours, and (w) 0.
So assume TC(e) > Let j = C(v). Then as in the proof of Lemma C.8 we can show that the proportion of random walks of length starting at is at most:
(ī+ e
( c +) n n-
which converges to as n + 0o.
We now follow structure vocabulary for atomic types with predicate Pj for each community j. so that (v) holds if and only if belongs to community j.
proof for the Erdös-Rény. dense cases. This time we augment our
With this we define the community atomic type of tuple of nodes ū in graph, notation Com'T'(W) be the atomic formulas satisfied by in the language augmented with the P3 predicates. For kt E let Com Tp be the set of all complete community atomic types with k free variables.
For each j {1,..., m., let ",
a converge qj- For any type t(ū) and t' (ū. v) E Ext(t), let:
alt, t') == (C(e)
Further, for any type t(ū), free variable us in and t'(ū, u) E Ext,, (t), let:
au (t,t')= = C(o
For any term x with & free variables, the feature-type controller:
e ((0, 1} x ComTpp - [0,
is defined exactly as in the proof of the density case of Theorem 5.1 using the extension proportions (l,, (') and Oua, (1, just defined.
We show by induction that every e, ó, > 0 and A-desc v (t)), there is N N such that for all n > N, with probability at least 0 in the space of graphs of size n, out of all the tuples such that (ū) at least 1 - satisfy:
(Ha(ū), GrTp(a)) [=(a]|| <e
then proceed as the proof of the non-sparse Rénci cases of Theorem 5.1 The only difference is that when showing equation (Ar) f) and equation A we use the fact that the expected proportion of type extensions I' ('ūū, v) of type ((ū) at node U is t').
Additional experiments
In this section we provide additional experiments using MeanGNN, GCN 330,
GAT 49 and
GPS+RW with random walks of length up to 5, over the distributions ER(n, p(n) 0.1), ER(n,p(n) logn Iogn), ER(n,p(m
50n and BA(n, = 5). We also experiment with SBM 10 communities with equal size, where an edge between nodes within the same community included with probability 0.7 and edge between nodes of different communities is included with probability 0.1.
Setup. Our setup is carefully designed to eliminate confounding factors:
35

---

MeanGNN
GCN
0.215
0.210
0.800
0.205
0.200
0.600
0.185
0.200
0.180
0.000
10
10'
10a
10
Graph size
Graph size
GPS+ RW
0.280
0.260
0.500
0.240
0.400
0.220
0.300
0.200
0.200
0.180
0.160
0.140
0.000
10a
10a
10a
10*
10c
10a
10
10
Graph size
Graph size
Figure The class probabilities (in different colours) a MEANGNN, GCN, GAT and GPS+RW model initialization over the ER(n.p(n) = 0.1) graph distributions, we draw increasingly larger graphs.
We consider models with the same architecture, each having randomly initialized weights, utilizing a ReLU non-linearity, and applying softmax function to their outputs. Each model uses hidden dimension of 128, 3 layers and an output dimension of 5.
We draw graphs of sizes up to 10,000, where we take 100 samples of each graph size. Node features are independently drawn from U[0, and the initial feature dimension is 128.
Further details are available in the experiments repository at https: /ttpt:://gitub.... com/ Attp:////AAAAaamatttoaaaallaaaaa
Much like in Section 6 the convergence of class probabilities is apparent across all models and graph distributions, accordance with our main theorems (Q1). We again observe that invention-baseed models such as GAT and GPS+RW exhibit delayed convergence and greater standard deviation in comparison McanGNN and GCN, which further strengthening our previous conclusions.
G Acknowledgements
This research was funded in whole in part by EPSRC grant EP/T022124/1. For the purpose of Open Access, the authors have applied CC BY public copyright license to any Author Accepted Manuscript (AAM) version arising from this submission.
NeurIPS Paper Checklist
Claims
Question: the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We thoroughly investigate the phenomenon of a.a.s. convergence of GNNs, both from theoretical and experimental point of view, claimed in the abstract.
Guidelines:
36

---

MeanGNN
GCN
0.215
1.000
0.210
0.800
0.205
0.200
0.600
0.195
0.400
0.190
0.200
0.000
10
10'
10a
10a
10
10'
10a
10
Graph
Graph size
GAT
GPS+RW RW
0.280
0.900
0.260
0.240
0.400
0.220
0.300
0,200
0.180
0.160
0.100
0.000
10'
10a
10
10'
10
10
Graph size
Graph size
Figure 7: The class probabilities (in different colours) of a MEANGNN, GCN, GAT and GPS+RW
model initialization over the ER(n, p(n) log graph distributions, we draw increasingly larger graphs.
MeanGNN
GCN
1.000
0.800
0.200
0.600
0.195
0.100
0.200
0.185
10
10
10a
101
10'
10a
10*
Graph size
Graph size
GAT
GPS+RW
0.260
0.600
0.240
0.220
0.400
0.200
0.300
0.160
0.140
0.300
10a
10a
10a
10a
10a
10a
10a
10a
Graph size
Graph size
Figure 8: The class probabilities (in different colours) of a MEANGNN, GCN, GAT and GPS+RW model initialization over the ER(n, p(r) 30m graph distributions, as we draw increasingly larger graphs.
37

---

MeanGNN
GCN
0.215
1.000
0.210
0.800
0.200
0.600
0.195
0.100
0.190
0.185
0.200
0.000
10
10'
10a
10a
10
10'
10
10*
Graph
Graph size
GAT
GPS+RW RW
0.280
0.260
0.500
0.240
0.220
0.300
0.200
0.180
0.200
0.160
0.100
0.140
0.000
10
10'
10a
10a
10
10'
10
10
Graph size
Graph size
Figure 9: The class probabilities (in different colours) of a MEANGNN, GCN, GAT and GPS+RW model initialization over the SBM graph distributions, as we draw increasingly larger graphs.
MeanGNN
GCN
1.000
1.000
0.800
0.800
0.600
0.400
0.100
0.200
0.200
0.000
101
10'
10a
10a
101
10'
10a
10*
Graph size
Graph size
GAT
GPS+RW
1.000
1.000
0.800
0.800
0.600
0.400
0.400
0.200
0.700
0.000
0.000
10a
10"
10a
10a
10
10a
10a
10'
Graph size
Graph
Figure 10: The 5 class probabilities (in different colours) of MEANGNN, GCN, GAT and GPS+RW model initialization over the BA(n, m = 5) graph distributions. as we draw increasingly larger graphs.
38

---

GCN trained on ENZYMES
1.000
Class probability
0.800
0.600
0.400
0.200
0.000
10
102
10a
104
Graph size
Figure 11: A three-layer GCN with hidden dimension 128 is trained on the ENZYMES dataset with one class removed so that there are five output classes. This model is then run on graphs drawn from ER(n, p(n) = 0.1) for increasing sizes and the mean output probabilities are recorded, along with standard deviation
The answer NA means that the abstract and introduction do not include the claims made in
the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation long it is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations in the discussion section: in particular we note that a.a.s. convergence does not apply universally to every GNN, and it does not apply for arbitrary in- stantiations of popular random graph models (like Erdos Renyi), regardless of the controlling parameters.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
39

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: full proofs are provided in the appendix to the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results the paper the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: we detail the experimental settings and datasets the paper, and provide link to a github with information about how to reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open-source dataset instructions for how to construct the dataset).
40

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.- to registered users), but should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: all of the necessary information is available in the GitHub repository.
Guidelines:
The answer NA means that paper does include experiments requiring code.
Please see the NeurIPS code and data submission guidelines http:s://niisscc///oee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers canmot rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurIPS code and data submission guidelines (https
to
ssi ssioniiccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Detail.
Question: Does the paper specify all the training and test details (e.g.. data splits. hyperparameters. how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: we provide all the necessary information on the datasets and the models used (our submission does not deal with training).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: we provide envelope error regions for Figure For the figures plotting standard deviations across graph sizes, we judged that it would be clearer to simply plot all datapoints, rather than take the mean (otherwise we would need to plot the standard deviation of standard deviations).
Guidelines:
The answer NA means that the paper does not include experiments.
* The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
41

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates). If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification: we provide information on the resources we used, and for replication these could be utilized.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps:///eur:ii httpp/a/aai/ttttasssuuu.........
Answer: [Yes]
Justification:
we have reviewed the ethics code and are confident that our paper conforms to
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts the work performed?
Answer: [NA].
Justification: this is a theoretically-orienn paper on convergence properties of graph neural networks. There is direct path to negative applications.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
42

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)? Answer: [NA].
Justification: do not provide datasets models in this work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: we cite the public datasets which we use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode com/ con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
43

---

13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: this theoreticall--orieneed paper does not provide new assets. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification: there are no crowdsourcing experiments in our submission.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements your country or institution) were obtained?
Question:
Answer: [NA].
Justification: no human subjects were used.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
44


Reviews:
[{"review_id": "6FVtqJEQB8", "reviewer": "Reviewer_6Ly5", "summary": "This paper introduces a term language to express many common GNN architectures as probabilistic classifiers. Using this term language, the authors provide asymptotically almost sure convergence results for dense and sparse random graph models (Erdos-Renyi variants, Barabasi-Albert, Stochastic Block Model). They perform experiments for these graph models as well as one real-world dataset with several different GNN architectures expressible in their term language. Their empirical results align with the presented theory and they can indeed observe convergence to a class distribution as the size of the graphs increases.", "questions": "1. What happens if we use different (but Lipschitz continuous or smooth) activation functions? E.g., the sine function (while perhaps a peculiar choice) is smooth, but not eventually constant. Is it expressible in your term language? \n2. On a related note, could you state more explicitly or provide some intuition on what assumptions are needed for, e.g., activation functions to be expressible in your term language (beyond the discussion, where it is mentioned that we need mean aggregation and activation functions need to be smooth)?\n3. Could you say more about the rate of convergence?", "limitations": "As briefly mentioned in the **Weaknesses**, the limitations of what can be expressed in the term language are not explicitly stated. While the authors state that the term language is applicable to a wide set of GNN architectures, this is only shown for a subset of them (and for, e.g., GCN, the term language needed to be extended accordingly).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This contribution seems novel, useful and of interest to the broader graph learning community. Overall, the paper is well-written and, despite its technical nature, relatively easy to follow. The introduction of the term language, which allows for proving asymptotic almost sure convergence in a systematic manner, is very elegant, and the results apply to a broad number of random graph models (dense and sparse) and several state-of the art GNNs.", "weaknesses": "The term language is not explained in sufficient detail. E.g., are there any specific assumptions that $\\pi$ and $\\tau$ need to satisfy? Could you clarify what is expressible within your term language and what is not?\n\nPlease find some additional minor remarks below.\n\n* l. 14: ML -> please introduce abbreviation first\n* l. 64: what does \"import\" mean here? (should it be \"impact\"?)\n* l. 127, 132: neighbor vs. neighbour\n* l. 137: What is $\\mathbf{W}_V$ (in comparison to just $\\mathbf{W}$ in GAT)?\n* l. 143: dot in sentence (after [12])\n* l. 163: What is $k$? The number of nodes?\n* l. 165: Consider re-writing this sentence as it is difficult to understand\n* Def. 4.3: Missing $G$ subscript?\n* l. 233: Sentence seems to be missing something: \"Then for every AGG[...] term converges a.a.s. with respect to $(\\mu_n)$\"\n* l. 236: regardless of \"the\" input graph\n* l. 294: \"this phenomenon\" or \"these phenomena\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and for finding our work novel, useful, easy to follow, and elegant. We respond to each of your comments below.\n\n> The term language is not explained in sufficient detail. E.g., are there any specific assumptions that $\\pi$ and $\\tau$ need to satisfy? Could you clarify what is expressible within your term language and what is not?\n\nWe clarify that we make no additional assumptions on the term language beyond those explicitly stated. We allow *any* Lipschitz function and *arbitrary* combinations of the term language components. In other words, the term language is completely specified by Definition 4.1. This is one of the strengths of our approach, in that it means our results are robust to many architectural choices.\n\n> What happens if we use different (but Lipschitz continuous or smooth) activation functions? E.g., the sine function (while perhaps a peculiar choice) is smooth, but not eventually constant. Is it expressible in your term language?\n\n> On a related note, could you state more explicitly or provide some intuition on what assumptions are needed for, e.g., activation functions to be expressible in your term language (beyond the discussion, where it is mentioned that we need mean aggregation and activation functions need to be smooth)?\n\nAll Lipschitz functions are included in the term language, and we do not make any additional assumptions. So in particular the sine function is part of the language (and moreover any Lipschitz continuous activation function you could come up with). Furthermore, any weighted mean whose weights can be computed using terms is part of the language.\n\n> Could you say more about the rate of convergence?\n\nBecause our term language is quite rich (e.g. including arbitrary Lipschitz functions), giving explicit bounds on the rate of convergence would involve chasing through many applications of concentration results and other estimations. We expect that this would be quite a complex expression, in terms of parameters like the Lipschitz bounds. We thus confined our analysis of the convergence rates to the empirical observation that GNNs tend to converge quite quickly.\n\nWe agree that analysis of convergence rates (as well as work to improve bounds on this) is important, and we leave this to future research.\n\n---\n\nWe thank you for your additional minor remarks, and will make corresponding changes. We comment where appropriate below.\n\n> l. 64: what does \"import\" mean here? (should it be \"impact\"?)\n\nWe meant 'import' in the sense of \"importance or significance\". However we recognise that this is somewhat obscure usage, and will change it.\n\n> l. 137: What is $W_V$ (in comparison to just $W$ in GAT)?\n\nThank you for spotting this typo. We will replace it with $W$.\n\n> l. 163: What is $k$? The number of nodes?\n\n$k$ is an arbitrary (but fixed) integer, which allows for Lipschitz functions which take multiple arguments (e.g. binary summation).\n\n> Def. 4.3: Missing $G$ subscript?\n\nYes, thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UVCHgiOSwl", "reviewer": "Reviewer_ETj1", "summary": "In this paper, the authors show that GNNs for graph classification applied to several classes of random graphs (with any node features) converges asymptotically almost surely to a constant. This is similar to several recent results in the literature on graphon-like graphs, but with a potentially stronger notion of asymptotic convergence, and with a seemingly very different proofs based on language terms and associated notions.", "questions": "- the fact that GNNs converge to a limit object on random graphs has been proved several times before (possibly for less general architectures and distribution of graphs), even with strong non-asymptotic results, in which way an asymptotic convergence is \"stronger\" as claimed by the authors?\n\n- the authors mention at the end the treatment of max aggregation which may be different; it is indeed treated specifically in their reference [9], could similar technique be employed?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- a very original approach to GNNs on random graphs compared to the literature\n- the handling of barabasi-albert graphs, which are very different from the results in the literature which treated of graphons, random geometric graphs, and so on.", "weaknesses": "- the presentation of language, terms, and all associated notions is very cryptic for the reader unfamiliar with this specific field (which would be most readers in Neurips). It is very hard to parse the notations and vocabulary, and to relate it to more familiar notions (vectorss, functions, etc.). Some notations seem (?) a bit unconsistent; $x$ sometimes refer to nodes, sometimes to \"free variable\" (?) and nodes become $u$, and so on. Other notions (\"graph-type\", \"edge negation\", \"feature controller\"...) are very hard to digest\n\n- it is not clear how the authors handle the notion of \"class\", the figure 1 seems to suggest that there are several classes and that converging to a constant is a limitation, but surely if all the graphs are drawn from the same distribution they should be all in the same class? Or are the labels related to something else? Other works (eg by Levie) precisely look at the ability of GNNs to distinguish between graphs drawn from different distributions\n\n- this work is not the only one to do so, but it mixes two worlds that do not collide in practice: that of graph classification and of asymptotically large graphs. In practice, graph classification tasks are done on small-ish graphs, while large graphs are almost always for node classification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and for finding our approach original and acknowledging the handling of Barabasi-Albert graphs in our work — an important difference to existing related works. We respond to each of your comments below.\n\n> the presentation of language, terms, and all associated notions is very cryptic for the reader unfamiliar with this specific field (which would be most readers in Neurips). [...] Other notions (\"graph-type\", \"edge negation\", \"feature controller\"...) are very hard to digest\n\nThank you for bringing this up. We understand that some parts of the paper are quite technical in nature, however this technicality is unavoidable given the nature of the theoretical work undertaken. We wish to point out that we took pains to ensure that a reader without the relevant background could still understand the key take-aways. For instance, in Section 4.1 we provide many examples of architectures which are included in the term language, and Corollary 5.2 spells out explicitly how the main result applies to GNNs used in practice. \n\nIn addition, following the suggestion of reviewer xvBN, we have produced a graphical example of evaluating a term on a small graph (Figure 3 in `supplementary-page.pdf`), to provide some additional intuition for the term language. Following your comments, we will also better explain how the example architectures in Section 4.1 can be captured using terms in our language.\n\n> Some notations seem (?) a bit unconsistent; $x$ sometimes refer to nodes, sometimes to \"free variable\" (?) and nodes become $u$, and so on.\n\nThank you for this point; we will add a remark to explain our conventions more explicitly. In the body we reserve $x$ for free variables (which you can think of as similar to letters in algebraic expressions like $y = 3x + 5$) and $u$ for concrete nodes.\n\n> it is not clear how the authors handle the notion of \"class\", the figure 1 seems to suggest that there are several classes and that converging to a constant is a limitation, but surely if all the graphs are drawn from the same distribution they should be all in the same class? Or are the labels related to something else?\n\nIn this work we adopt the common setup used in machine learning, where we have a distribution over labelled inputs, and the goal is to identify the label from the input.\n\nBy “different distributions” we assume that the reviewer is referring to the conditional distributions of input graphs conditioned on each label. Such distributions may well be different from each other in a real-world classification task. However, this fact does not interact with our results, since we show convergence for the full distribution on input graphs. In other words, our results show that asymptotically a GNN will not be able to distinguish graphs *no matter what* the conditional distributions are.\n\n> this work is not the only one to do so, but it mixes two worlds that do not collide in practice: that of graph classification and of asymptotically large graphs. In practice, graph classification tasks are done on small-ish graphs, while large graphs are almost always for node classification.\n\nWe thank the reviewer for pointing this out. Indeed our results have strong implications beyond graph classification. Lemma 5.4 shows that any node-level GNN converges a.a.s. to a function *only of the input node's features*. In other words \"node-level classifiers asymptotically ignore the graph structure\". We will highlight this in the paper and discuss the implications which, in our opinion, improves the presentation of our paper and the framing of our results.\n\nWhile we agree that most current benchmarks contain smaller graphs, we expect that this will likely not always be the case going forward. We therefore consider understanding the asymptotic behaviour of GNNs to be an important theoretical contribution, in that it provides strong bounds on their expressive capacity. Furthermore, we point out that in our experimental evaluation we observed the effect of convergence already for quite small graphs. Such sizes are well within the range of many real-world datasets.\n\n> the fact that GNNs converge to a limit object on random graphs has been proved several times before (possibly for less general architectures and distribution of graphs), even with strong non-asymptotic results, in which way an asymptotic convergence is \"stronger\" as claimed by the authors?\n\nFor example, [9] provides non-asymptotic results, a corollary of which is that under certain conditions the output of a GNN converges *in probability*. Our results show convergence *asymptotically almost surely*, a much stronger notion. Below we provide an example illustrating this. \n\nWe are happy to explain the strength of our notion of convergence with respect to any other references the reviewer may have in mind.\n\n> the authors mention at the end the treatment of max aggregation which may be different; it is indeed treated specifically in their reference [9], could similar technique be employed?\n\nAs mentioned above, [9] shows a convergence in probability for max aggregation. However, showing asymptotically almost sure convergence is not possible in this case. \n\nFor example, using max aggregation one can express the function $F$ that returns $1$ if a graph has a $4$-clique and $0$ otherwise. In some of our typical ER root growth cases, there is a non-trivial proportion of graphs where $F$ returns $0$ and a non-trivial proportion where function $F$ returns $1$ — thus not asymptotically constant. E.g. for edge probability $1/n^{2/3}$, Lynch 1998 showed that asymptotically the frequency of graphs that will have a $4$-clique is around $1-e^{-1/24}$. Shelah and Spencer’s seminal 1988 result shows that for $\\mathrm{ER}(n, n^{-\\alpha})$ with $\\alpha$ rational, first-order logic does not converge in distribution. This implies that there are examples with max aggregation where one does not obtain even convergence in distribution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TtpYIqo5Mj", "reviewer": "Reviewer_JXJp", "summary": "The paper presents a theoretical study on the expressive power of some popular GNNs (MPNNs with the mean aggregator,  GAT, and GPS+RW) as multi-class classifiers with random featured graphs. It shows that their output converges a.a.s. to a constant function from various random graph models, including Erdős-Rényi, stochastic block model, and Barabási-Albert model. The study includes empirical studies on synthetic and real graphs, confirming the theoretical findings.", "questions": "Please see the weakness part.", "limitations": "The authors discuss the limitation that their proposed theory results are only applicable to the examined graph models and GNN structures employing a mean aggregator, which is adequate. I do not see any negative social impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper presents a formal language that is designed to describe compositions of operators and functions applied to graphs. This language captures the operations of GNNs in the architectures. This can be further applied to other theoretical work on GNNs related to their expressiveness and generalization capabilities.\n \n- The paper empirically validates the theoretical results of both synthetic and real graph datasets.", "weaknesses": "- *Unclear Contribution to Expressiveness Analysis.* The expressiveness power is usually used to describe the GNN’s ability to approximate functions, which is essentially to derive generalization bounds or sample complexity. It is not clear how the type of results given in this paper can enable generalization performance analysis.\n\n\n- *Difference between [a] and the current paper.* [a] presents the output of MPNNs and GCNs as binary classifiers on the ER graph model that will converge to a constant as the graph size increases. This paper proposed that the output of some popular GNNs as multiclass classifiers on several graph models will converge to a constant function as the graph size increases. The current paper can be seen as an extension of [a]. It would be better to discuss the differences between them. Specifically, \n  - What is the difference in the proof techniques between lemma 5.4 in this paper and lemma 4.7 in [a]?\n  - If we set the number of classes as 2, then will the convergence results of this paper reduce to the results in [a]?\n\n[a] Adam-Day, S. and Ceylan, I., 2024. Zero-one laws of graph neural networks. Advances in Neural Information Processing Systems, 36.\n\n- The experimental results are supported by std (which is good) but without p-value analysis or confidence interval. The statistical significance is not entirely clear. \n\n- Some minors:\n\n  - The authors assume that the node features are in domain [0, 1]^d, and it would be helpful to explain more about the reason for using this assumption in the proof, e.g., how critical is this assumption for the convergence results? \n  - Instead of using randomly initialized weights in the experiments, it would be interesting to use learned weights. \n  - Line 130, what is the meaning of “A MEANGNN is one where…”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and for pointing out the strength and applicability of our term language. We respond to each point below.\n\n> *Unclear Contribution to Expressiveness Analysis*. The expressiveness power is usually used to describe the GNN’s ability to approximate functions, which is essentially to derive generalization bounds or sample complexity. It is not clear how the type of results given in this paper can enable generalization performance analysis.\n\nThe results in our work provide strong upper bounds on the capacity of any architecture included in the term language to generalise from smaller graphs to larger ones. So rather than providing quantitative bounds on generalisation, our work gives impossibility results for what tasks are *in principle* learnable by GNNs. \n\nWe will add a remark to the introduction clarifying this.\n\n> *Difference between [a] and the current paper*. [...]\n> - What is the difference in the proof techniques between lemma 5.4 in this paper and lemma 4.7 in [a]?\n> - If we set the number of classes as 2, then will the convergence results of this paper reduce to the results in [a]?\n\nIn comparison with [a], we note that our proof techniques are more general along two axes. Firstly, while [a] relies on dense ER graphs where convergence is much easier to show, our work goes well beyond this and provides techniques which apply to a much wider range of graph distributions. In particular the sparse ER and BA cases require quite different proof strategies, and we see nothing similar to this in [a]. Moreover in the logarithmic growth case we see a more subtle convergence phenomenon where only most of the node features converge; this is quite beyond the scope of Lemma 4.7 in [a].\n\nSecondly, while the proof techniques in [a] rely on a fixed architecture, our results apply much more generally, as made precise in the definition of the term language. For example, this includes GAT, graph transformers, GPS architectures, and many architectural variations including skip connections. This is a non-trivial distinction, since we must deal with terms representing higher-order functions of nodes, which requires careful treatment.\n\nTo be clear, if we set the number of classes to 2 as you suggest, and we do not perform probabilistic classification or regression (the focus of our submission) but rather just Boolean classification, then our result would imply a 'zero-one law' similar to that presented in [a]. However, given that this is a special case, and the much greater generality of our assumptions, we consider that our results go much beyond those of [a].\n\n> The experimental results are supported by std (which is good) but without p-value analysis or confidence interval. The statistical significance is not entirely clear.\n\nIn `supplementary-page.pdf` we have regenerated graphs in the original paper using confidence intervals instead of standard deviations (Figure 2). The convergence behaviour of these models remains clear.\n\n> The authors assume that the node features are in domain $[0, 1]^d$, and it would be helpful to explain more about the reason for using this assumption in the proof, e.g., how critical is this assumption for the convergence results?\n\nThis assumption is made purely for notational convenience, to avoid using additional letters for the bounds. The proof works just as well with arbitrary bounds.\n\nBut note that since linear functions are Lipschitz, our result is already completely general and we don't need to allow arbitrary bounds. Indeed, suppose $\\tau(\\bar x)$ is a term which we apply to a graph distribution $\\mathcal D$ with features in $[a, b]^d$. Modify this distribution to $\\mathcal D'$ by applying the function $\\bar z \\mapsto (\\bar z - a) / (b - a)$ to the features. This is now a distribution with features in $[0, 1]$. Modify $\\tau$ to $\\tau'$ by replacing each $\\mathrm H(x)$ by $F(\\mathrm H(x))$, where $F$ is the function $\\bar z \\mapsto (b - a) \\bar z + a$. Then evaluating $\\tau'$ on $\\mathcal D'$ is equivalent to evaluating $\\tau$ on $\\mathcal D$.\n\n> Instead of using randomly initialized weights in the experiments, it would be interesting to use learned weights.\n\nThank you for this suggestion. In `supplementary-page.pdf` we include an experiment in which a GCN is trained on the ENZYMES dataset and then analysed asymptotically in the same way as other experiments (Figure 1). As you can see, we observe very similar convergence behaviour to the randomly initialised case.\n\n> Line 130, what is the meaning of “A MEANGNN is one where…”.\n\nWe will change this to \"A MEANGNN is an MPNN where the aggregate function is the mean.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5UC5bt6RxA", "reviewer": "Reviewer_xvBN", "summary": "This paper theoretically analyze the phenomenon that GNN-based probabilistic classifiers almost surely converge to a constant. A formal approach based on term language is proposed. It provides a unified framework to study different GNN models.", "questions": "1. Can the authors give an explicit (rigorous) definition of \"probabilistic classifier\"? \n2. In the discussion of almost sure convergence (3.1), what is $\\bar{\\mu}$?\n3. From the definition of ``term language'' (Definition 4.1), it seems that it is a high-level summary of components in GNN architectures. I do not see what the essential properties are that lead to key results such as Theorem 5.1. Can authors elaborate on this?  \n4. For Theorem 5.1, is the almost sure limit a single (deterministic) vector? \n5. I interpret the main findings of the paper as: large graphs (from one of the discussed models) are not distinguishable. Is this correct? Is there any way that the GNN architecture can be modified to overcome such a limitation?\n6. Node features are assumed to be i.i.d. (3.1). In applications, this is usually not the case. How will non i.i.d. features affect the results?", "limitations": "N.A.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-organized.\n2. The theoretical study is solid.\n3. The main finding is interesting.", "weaknesses": "1. The use of ``term language'' is abstract and can be difficult to understand. It is preferable the authors can explain more and provide simple (numerical) examples, e.g, on an explicit small graph.  \n2. The paper discusses an interesting asymptotic behavior of GNNs as classifiers. However, its impact on GNN real applications is not fully discussed. \n3. I do not find a thorough discussion if features are not i.i.d.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and for finding our work solid, well-organised, and interesting. We reply to each of your comments below.\n\n> The use of ``term language'' is abstract and can be difficult to understand. It is preferable the authors can explain more and provide simple (numerical) examples, e.g, on an explicit small graph.\n\nThank you for this suggestion, which we like very much. In our `supplementary-page.pdf` we have included a graphical example of computing a term on a small graph, which we will include in the camera-ready paper (Figure 3).\n\n> Can the authors give an explicit (rigorous) definition of \"probabilistic classifier\"?\n\nA probabilistic classifier is a graph-level classifier which outputs a probability distribution over classes. Formally, this is a function which takes as input a graph and outputs a tuple of probabilities which sum to $1$, where the $i$th element of the tuple gives the probability for the $i$th class.\n\n> In the discussion of almost sure convergence (3.1), what is $\\bar\\mu$?\n\nThank you for spotting this typo. It should be $(\\mu_n)_{n \\in \\mathbb N}$.\n\n> From the definition of ``term language'' (Definition 4.1), it seems that it is a high-level summary of components in GNN architectures. I do not see what the essential properties are that lead to key results such as Theorem 5.1. Can authors elaborate on this?\n\nOne way to understand this is to relate the proof structure to the definition of the term language. We focus on the denser cases to illustrate this. Lemma 5.4 is proved by induction on the term structure, showing that if a term is composed of simpler terms which converge, then it also converges. For this we treat each case of Definition 4.1 separately, which provides insight into how each contributes to convergence.\n\nFor example, the Lipschitz function case uses the smoothness of $F$ to show that if its arguments converge, then its application to those arguments must also converge. The heart of the weighted mean case is a concentration bound showing that a weighted mean is with high probability close to its expected value.\n\nAnother way to understand which properties are essential for convergence is to consider extensions of the term language for which it does not hold. For example, if we include a max aggregation operator, we no longer converge a.a.s. to a constant (see the reply to reviewer ETj1).\n\n> For Theorem 5.1, is the almost sure limit a single (deterministic) vector?\n\nIt is indeed. We will add a clarificatory sentence to make this explicit.\n\n> I interpret the main findings of the paper as: large graphs (from one of the discussed models) are not distinguishable. Is this correct? Is there any way that the GNN architecture can be modified to overcome such a limitation?\n\nWe agree with your interpretation: a GNN will output essentially the same value on all large graphs with high probability.\n\nThe question of how to overcome this limitation is intriguing but unfortunately beyond the scope of our current work. One can look towards aggregation functions not included in the term language (such as summation) for potential examples of such non-convergence phenomena. We hope that our work inspires and paves the way for such investigations.\n\n> Node features are assumed to be i.i.d. (3.1). In applications, this is usually not the case. How will non i.i.d. features affect the results?\n\nWe agree that this would be an interesting study. There are several challenges from a theoretical perspective. The first is that 'non-i.i.d.' is underspecified: there are many ways in which variables can be dependent. Second, the independence assumption is used in the application of concentration inequalities throughout the proofs, so these would need careful consideration.\n\nWe believe that many important cases of dependence (e.g. analogous to the SBM model of dependence for graph structure) can be handled by reducing to our framework. But we leave the verification of this for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their time and constructive comments. We are grateful that the reviewers appreciated the novelty of our use of a term language to capture a wide class of GNN architectures, and the fact that our results apply to distributions beyond those typically considered, including  the Barabasi-Albert distribution. 

We summarise our new experiments in the global response PDF (`supplementary-page.pdf`) attached to this post. We also briefly summarise our response to a shared concern raised by the reviewers.

## New experiments and figures

1. Following **reviewer JXJp**’s suggestion, we empirically investigated the asymptotic behaviour of a GNN with trained rather than randomly initialised weights (Figure 1). For this we trained a GCN on the ENZYMES dataset. We observe very similar convergence behaviour to the randomly initialised case.
2. Prompted by **reviewer JXJp**’s comment, we regenerated a number of plots with confidence intervals rather than standard deviations (Figure 2).
3. On the suggestion of **reviewer xvBN**, we produced a graphical example of numerically computing a term on a small graph (Figure 3). This provides intuition for how an inductively built term is evaluated on a graph.

## Term language

We emphasise that term language contains all Lipschitz functions and arbitrary combinations of the components in Definition 4.1. This flexibility means that our results apply to a wide class of architectures, even including potential future innovations.

Following **reviewer ETj1**’s comments, we will explain in more detail how the example architectures in Section 4.1 are captured by our term language, to aid the reader’s comprehension of this language concept. We will also include the graphical example of evaluating a term on a small graph (Figure 3) which provides further intuition for this.

We hope that this helps address the Reviewers' concerns, and we look forward to a collaborative discussion period.

Meta-review: This paper investigates the expressive power of GNN by analyzing how the predictions of a GNN probabilistic classifier evolve when applied to increasingly larger graphs drawn from various random graph models. The authors demonstrate that the output of these GNNs converges to a constant function, which limits what these classifiers can express uniformly across different graph models. This convergence property is shown to apply to a wide range of GNN architectures and is validated both theoretically and empirically.

The reviewers were mostly positive about the paper, and I recommend accepting it to NeurIPS 2025. Nevertheless, I recommend following the recommendation of the reviewers for the camera-ready version, especially :
- improve the clarity of the paper (see for instance the comment of reviewer ETj1)
- improve the flow of the appendix (of more than 20 pages). The authors did their best to pack as most content as possible in 9 pages, but I agree with the referees that some parts are dense for a conference paper.
- include more details on the experiments as started in the rebuttal.
Decision: Accept (poster)