Almost Surely Asymptotically Constant Graph Neural Networks

Authors: sam  adam-day
michael  benedikt i̇smail
i̇lkan  ceylan
ben  finkelshtein
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:59:54

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.

Main paper: 
 introduction: 
 Figure 1 : The output of the considered GNNs eventually become constant as the graph sizes increase.Graph neural networks (GNNs) [44, 21] have become prominent for graph machine learning with applications in domains such as life sciences [47, 11, 25, 55] . Their empirical success motivated work investigating their theoretical properties, pertaining to their expressive power [52, 39, 4, 8, 1, 43, 23, 19, 54] , generalization capabilities [18, 33, 38, 45, 40] , and convergence properties [28, 27, 38, 32, 2] .We consider GNNs outputting real-valued vectors, such as those which classify graphs probabilistically, and ask: how do the outputs of these GNNs evolve as we apply them on larger graphs drawn from a random graph model?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 1 ). This "almost sure convergence" to a constant distribution is much stronger than convergence to some limit object [28, 27, 32] . The immediate consequence of this strong convergence phenomenon is to upper bound the uniform expressiveness of the considered model architectures: these architectures can uniformly express only the classifiers that are almost surely asymptotically constant. In other words, our results provide impossibility results for what tasks are in 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 neighbours [20] . This approach can be extended to global aggregates [5] . Our main result holds for all architectures that use weighted mean as 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 graph attention networks (GATs) [49] , as well as popular (graph) transformers, such as the General, Powerful, Scalable Graph Transformer (GPS) with random walk encodings [41] .The term language can seamlessly 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 Erdős-Rényi models of various sparsity levels, the Barabási-Albert 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.The key contributions of this paper are as follows:• We introduce a 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 a diverse class of architectures acting as real-valued graph classifiers can be expressed in the term language (Section 4). In Section 5 we present "almost sure convergence" results for our 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 a 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.Question: Do 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 a theoretical and experimental point of view, as claimed in the abstract.Guidelines: 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 instantiations 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 to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations 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 on a few datasets or with a 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 is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• 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 reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 et 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.e., the model construction is dependent on the graph size. There are also recent studies that focus on uniform expressiveness [4, 42, 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-uniform setting [1, 43] . They show that for classical Erdős-Rényi graphs, GNN binary classifiers display a zero-one law, assuming certain restrictions on GNN weights and the random graph model. We focus on 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 real-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 [15] , 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. [9] , Keriven et al. [28, 27] , Maskey et al. [38] , Levie [32] 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 [34] . Our approach is 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 a very strong notion of convergence and it does not follow from convergence in the senses above. In 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 
featured random graphs and convergence: 
 Random graphs. We consider simple, undirected graphs G = (V G , E G , H G ) where each node is associated with a vector of node features given by H G : V G → R d . We refer to this as a featured graph. We are interested in random graph models, specifying for each number n a distribution µ n on graphs with n nodes, along with random graph feature models, where we have a distribution µ n on featured graphs with n nodes. Given a random graph model and a distribution ν over R d , we get a random graph feature model by letting the node features be chosen independently of the graph structure via ν.Erdős-Rényi and the stochastic block model. The most basic random graph model we deal with is the Erdős-Rényi distribution ER(n, p(n)), where an edge is included in the graph with n 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(n 1 , . . . , n M , P ), which contains m communities of sizes n 1 , . . . , n M and an edge probability matrix between communities P ∈ R M ×M . A community i is sampled from the Erdős-Rényi distribution ER(n, p(n) = P i,i ) and an edge to a node in another community j is included with probability P i,j .The Barabási-Albert preferential attachment model. Many graphs encountered in the real world obey a power law, in which a few vertices are far more connected than the rest [7] . 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 are added one at a 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 (µ n ) n∈N , we say F converges asymptotically almost surely (converges a.a.s.) to a vector z with respect to μ if for all ϵ, θ > 0 there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ when drawing featured graphs G from µ n , we have that ∥F (G) -z∥ < ϵ.We first briefly introduce message passing neural networks (MPNNs) [20] , which include the vast majority of graph neural networks, as well as (graph) transformers.Message passing neural networks. Given a featured graph G = (V G , E G , H G ), an MPNN sets the initial features h as:(0) v = H G (v)UPD (ℓ) h (ℓ) v , AGG (ℓ) h (ℓ) v , { {h (ℓ) u | u ∈ N (v)} } ,where { {•} } denotes a multiset and UPD (ℓ) and AGG (ℓ) are differentiable update and aggregation functions, respectively. The final node embeddings are pooled to form a graph embedding vector z(L)G to predict properties of entire graphs. A MEANGNN is an MPNN where the aggregate is mean. GATs. One class of MPNNs are graph attention networks (GATs) [49] , where each node is updated with a weighted average of its neighbours' representations, letting h (ℓ+1) v be:u∈N (v) exp score h (ℓ) v , h (ℓ) u w∈N (v) exp score h (ℓ) v , h (ℓ) w W (ℓ) h (ℓ) u ,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, a single attention head computes a new representation for every (query) node v, in every layer ℓ > 0 as follows:ATT(v) = u∈V G exp scale h (ℓ) v , h (ℓ) u w∈V G exp scale h (ℓ) v , h (ℓ) w W (ℓ) h (ℓ) uwhere 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 v for every node v that encode a node property (e.g., node degree) which are concatenated to the node features h v . The random walk positional encoding (RW) [12] of each node v is given by:rw v = [rw v,1 , rw v,2 , . . . rw v,k ],where rw v,i is the probability of an i-length random walk that starts at v to end at v.The GPS architecture [41] is a representative graph transformer, which applies a parallel computation in every layer: a 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 a standard MPNN in this way, a GPS layer can take advantage of the graph topology even when there is no positional encoding. In the context of this paper, we write GPS to refer to a GPS architecture that uses an MPNN with mean aggregation, and GPS+RW if the architecture additionally uses a random-walk PE.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 a softmax or sigmoid applied to pooled representations.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 if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
model architectures via term languages: 
 We demonstrate the robustness and generality of the convergence phenomenon by defining a term language consisting of compositions of operators on graphs. Terms are formal sequences of symbols which when interpreted in a given graph yield a real-valued function on the graph nodes. Definition 4.1 (Term language). AGG[WMEAN] is a term language which contains node variables x, y, z, . . . and terms defined inductively:2 • The basic terms are of the form H(x), representing the features of the node x, and constants c.• Let h : R d → (0, ∞) d be a function which is Lipschitz continuous on every compact domain.Given terms τ and π, the local h-weighted mean for node variable x is:y∈N (x) τ (y) ⋆ h(π(y))The interpretation of ⋆ will be defined below. The global h-weighted mean is the term:y τ (y) ⋆ h(π(y))• Terms are closed under applying a function symbol for each Lipschitz continuous F : R d×k → R d for any k ∈ N + .The weighted mean operator takes a weighted average of the values returned by τ . It uses π to perform a 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 d 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 as follows. See Figure 2 for a graphical example of evaluating a term on a graph. Definition 4.2. Let G = (V G , E G , H G ) be a featured graph. Let τ be a term with free variables x 1 , . . . , x k and ū = (u 1 , . . . , u k ) a tuple of nodes. The interpretation τ (ū) G of term τ graph G for tuple ū is defined recursively:• c(ū) G = c for any constant c.• H(x i )(ū) G = H G (u i ) for the i th node's features. • F (τ 1 , . . . , τ k )(ū) G = F ( τ 1 (ū) G , . . . , τ k (ū) G )for any function symbol F .• For any term composed using ⋆:y∈N (xi) τ ⋆ h(π)(ū) G =      v∈N (u i ) τ (ū,v) G h( π(ū,v) G ) v∈N (u i ) h( π(ū,v) G ) if N (u i ) ̸ = ∅; 0 if N (u i ) = ∅.The semantics of global weighted mean is defined analogously and omitted for brevity. A closed term has all node variables bound by a weighted mean operator: so the implicit input is just a featured graph. Definition 4.3. We augment the term language to AGG[WMEAN, RW] by adding the random walk operator rw(x). The interpretation of rw(x i ) given a graph G and a tuple of nodes ū, is:rw(x i )(ū) G = [rw ui,1 , . . . , rw ui,d ]4.1 How powerful is the term language?Various architectures can be described using this term language. The core idea is 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 us 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 an L-layer MPNN with mean aggregation, update functions UPD (ℓ) 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:MEAN y π(y) := y π(y) ⋆ 1.For each layer 0 ≤ ℓ < L, we define a term τ (ℓ) (x) which will compute the representation of a node at layer ℓ of the MPNN:• Initialization. Let τ (0) (x) := H(x). Then the value τ (0) (x)(u) G at a node u is the initial node representation H(u).• Layers. For 1 ≤ ℓ < L, define τ (ℓ+1) (x) := UPD (ℓ) x, MEAN y∈N (x) τ (ℓ) (y) .Then the value at node u is the following, which conforms with the inductive construction of the MPNN:τ (ℓ+1) (x)(u) G = UPD (ℓ)   τ (ℓ) (x)(u) G , 1 |N (u)| v∈N (u) τ (ℓ) (x)(v) G   • Final mean pooling. The final graph representation is computed as τ := MEAN x τ (L) (x).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:ATT y π(y) := y π(y) ⋆ exp(scale(π(x), π(y)))The function scale(π(x), π(y)) is a term in the language, since scaled dot product attention is a Lipschitz function. To see how graph transformer architectures such as GPS can be expressed, it 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 to a 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 or residual connection from layer ℓ 1 to layer ℓ 2 can be expressed by including a copy of the term for layer ℓ 1 in the term for the layer ℓ 2 [51] . Global readout can be captured using a 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 [37] .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.In Appendix A we show how to extend the term language to incorporate graph convolutional networks (GCNs) [29] by adding a new aggregator.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to 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 in the paper, and provide a 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or 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 (e.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. (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 it should be possible for other researchers to have some path to reproducing or verifying the results. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
convergence theorems: 
 We start by presenting the convergence theorem.Theorem 5.1. Consider (µ n ) n∈N sampling a graph G from any of the following models and node features independently from i.i.d. bounded distributions on d features.1. The Erdős-Rényi distribution ER(n, p(n)) where p satisfies any of the following properties.• Density. p converges to p > 0.• Root growth. For some K > 0 and 0 < β < 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 -1 .2. The Barabási-Albert model BA(n, m) for any m ≥ 1. Then every AGG[WMEAN, RW] term converges a.a.s. to a constant with respect to (µ n ) n∈N . 3Concretely, 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 a 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.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 a Lipschitz function almost surely. The only caveat is that we may need to distinguish based on the "type" of the node -for example, nodes u 1 , u 2 , u 3 that form a triangle may require a different function from nodes that do not. Formally, for node variables x, an x graph type is a conjunction of expressions E(x i , x j ) and their negations. The graph type of tuple ū in a graph, denoted GrTp(ū) is the set of all edge relations and their negations that hold between elements of ū. A (x, d) feature-type controller is a Lipschitz function taking as input pairs consisting of d-dimensional real vector and an x graph type.The key theorem below shows that to each term π 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 e π (H G (ū), GrTp(ū)) is close to π(ū) . Theorem 5.3 (Aggregate Elimination for Non-Sparse Graphs). For all terms π(x) over featured graphs with d features, there is a (x, d) feature-type controller e π such that for every ϵ, δ, θ > 0, there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ in the space of graphs of size n, out of all the tuples ū at least 1 -δ satisfy that ∥e π (H G (ū), GrTp(ū)) -π(ū) ∥ < ϵ.This can be seen as a kind of "almost sure quantifier elimination" (thinking of aggregates as quantifiers), 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 to use induction on 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 (non-sparse) random graphs, GNNs can only classify based on the features of a node, they cannot make use of any graph structure.In the sparser cases, the analysis is a bit more involved. Instead of graph types over ū, which only specify graph relations among the ū, we require descriptions of local neighbourhoods of ū. Definition 5.4. Let G be a graph, ū a tuple of nodes in G and ℓ ∈ N. The ℓ-neighbourhood of ū in G, denoted N ℓ (ū) is the subgraph of G induced by the nodes of distance at most ℓ from some node in ū.The "types" are now graphs T with k distinguished elements w, which we call k-rooted graphs. Two k-rooted graphs (T, w) and (U, z) are isomorphic is there is a structure-preserving bijection T → U which maps w to z. The combinatorial tool here is 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 ℓ ∈ N. There is q T ∈ [0, 1] such that for all ϵ, θ > 0 there is N ∈ N such that for all n ≥ N with probability at least 1 -θ we have that:|{ū | N ℓ (ū) ∼ = (T, w)}| n -q T < ϵOur "aggregate elimination", analogous to Theorem 5.3, states that every term can be approximated by a Lipschitz function of the features and the neighbourhood type. Theorem 5.6 (Aggregate Elimination for Sparser Graphs). For every π(x), letting ℓ be the maximum aggregator nesting depth in π, for all k-rooted graphs (T, w) there is a Lipschitz function e T π : R |T |•d → R d such that for each ϵ, θ > 0, there is N ∈ N such that for all n ≥ N with probability at least 1 -θ in the space of graphs of size n, for every k-tuple of nodes ū in the graph such that N ℓ (ū) ∼ = (T, w) we have that e T π (H G (N ℓ (ū))) -π(ū) < ϵ.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, it is not true that one gets convergence for Erdős-Rényi with arbitrary growth functions: Theorem 5.7. There are functions p(n) converging to zero and a term τ in 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 1 2 on even n and 1 n on odd n. Consider τ 1 (x) that returns 0 if x has a neighbour and 1 otherwise, and let τ be the global average of τ 1 . So τ is the percentage of isolated nodes in the graph. Then τ clearly goes to zero in the non-sparse case. However the probability that a particular node is not isolated in a random sparse graph of size n is (1 -1 n ) n-1 , which goes to 1 e < 1. Thus τ diverges on ER(n, p(n)). 
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 on the convergence? Q4. Can these phenomena arise within large real-world graphs?All our experiments were run on a single NVidia GTX V100 GPU. We made our codebase available online at https://github.com/benfinkelshtein/GNN-Asymptotically-Constant.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, 3 layers and an output dimension of 5.• We experiment with distributions ER(n, p(n) = 0.1), ER(n, p(n) = log n n ), ER(n, p(n) = 1 50n), 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 is 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 U [0, 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 a model-specific behaviour. Further experimental results are reported in Appendix F.In Figure 3 , a single model initialization of the MeanGNN, GAT and GPS+RW architectures is used with ER(n, p(n) = 0.1), ER(n, p(n) = log n n ) and ER(n, p(n) = 1 50n). Each curve in the plots corresponds to a 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 3 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 to the distinct proof strategy employed in 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 we converge to depends the proportion of these. In all other cases the neighbourhood sizes are 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 are weighted more than others, the attention aggregation has a higher variance than regular mean aggregation. For instance, if half of the nodes have weights close to 0, then the 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. Towards Q4, we investigated a large real-world dataset. Many commonly studied graph datasets (e.g. ZINC [13] , QM9 [6] ) do not exhibit sufficient graph size variance and provide no obvious means to add scaling. We used the TIGER-Alaska dataset [16] of geographic faces. The original dataset has 93366 nodes, while Dimitrov et al. [10] extracted smaller datasets with graphs having 1K, 5K, 10K, 25K and 90K nodes. We chose the modified dataset as it is split by graph size, and consists of graphs differing from our random models (in particular all graphs are planar). Figure 5 shows the results of applying the same five MeanGNNs to graphs of increasing sizes. Strikingly, we again observe a convergence phenomenon, but at a slower pace.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 a 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. 
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 a great variety of random graph models. Rather than having separate proof techniques per GNN model, our paper introduces a broad language where such models can 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 to 0: see Theorem 5.7.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 of the message passing neural network in which the update function is defined as follows.h (ℓ+1) v = u∈N (v) 1 |N (v)||N (u)| W (ℓ) h (ℓ) uTo allow our term language to capture GCNs, we add the new aggregator:GCN y∈N (x) τ (y)The language AGG[WMEAN, GCN, RW] is the result of closing AGG[WMEAN, RW] under this operator.The semantics are extended as follows.GCN y∈N (xi) τ (ū) G = v∈N (ui) 1 |N (u i )||N (v)| τ (ū, v) GWith 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.Throughout the appendix, we make use of a few basic inequalities.Theorem B.1 (Markov's Inequality). Let X be a positive random variable with finite mean. Then for any λ > 0 we have:P(X ≥ λ) ≤ E[X] λProof. See Proposition 1.2.4, p. 8 of [50] .Theorem B.2 (Chebyshev's Inequality). Let X be a random variable with finite mean µ and finite variance σ 2 . Then for any λ > 0 we have:P (|X -µ| ≥ λ) ≤ σ 2 λ 2Proof. See Corollary 1.2.5, p. 8 of [50] .Theorem B.3 (Chernoff's Inequality). Let X i for i ≤ n be i.i.d. Bernoulli random variables with parameter p.(1) For any λ > p we have:P n i=1 X i ≥ λ ≤ e -np enp λ λ(2) For any λ < p we have: P n i=1 X i ≤ λ ≤ e -P n i=1 X i -nµ ≥ λ ≤ 2 exp - 2λ 2 n(b -a) 2Proof. See Theorem 2.2.6, p. 16 of [50] .Corollary B.5 (Hoeffding's Inequality for Bernoulli random variables). Let X i for i ≤ n be i.i.d. Bernoulli random variables with parameter p. Then for any λ > 0 we have:P n i=1 X i -np ≥ λ ≤ 2 exp - 2λ 2 nC Proof for Erdős-Rényi distributions, the non-sparse casesWe new begin with the proof of convergence for the first three cases of the Erdős-Rényi distribution in Theorem 5. • Density. p converges to p > 0.• Root growth. For some K > 0 and 0 < β < 1 we have:p(n) = Kn -β .• Logarithmic growth. For some K > 0 we have:p(n) = K log(n) n .Then for every AGG[WMEAN, RW] term converges a.a.s. with respect to (µ n ) n∈N .Note that throughout the following we use u and v to denote both nodes and node variables.Remark C.2. At various points in the following we will make statements concerning particular nodes of an Erdős-Rényi graph without fixing a graph. For example, we state that for any u we have that its degree d(u) is the sum of n -1 Bernoulli random variables. To make sense of such statements we can fix a canonical enumeration of the nodes of every graph and view our node meta-variables as ranging over indices. So we would translate the previous statement as "for any node index u the degree of the u th node in ER(n, p(n)) is the sum of n -1 Bernoulli random variables."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 a conjunction of atomic statements about the nodes. Definition C.3. A ∧-description ϕ(ū) is a conjunction of statements about the variables ū of the form u i Eu j , which expresses that there exists an edge between u i and u j . A ∧-description u i1 Eu j1 ∧ • • • ∧ u im Eu jm holds if and only if there is an edge between u i ℓ and u j ℓ for each ℓ.The reason for strengthening the results in this way will become clearer when we are proving the local weighted mean induction step v∈N (ui) ρ(ū, v) ⋆ h(η(ū, v)). There we will need our auxiliary results to hold conditioned on vEu i , along with any additional requirements coming from previous induction steps.We will first need a few auxiliary lemmas about the behaviour of random graphs in the different ER models.We will need to know that in the non-sparse case, neighborhoods are fairly big: Lemma C.4 (Log neighbourhood bound). Let p : N → [0, 1] satisfy density, root growth or logarithmic growth. There is R > 0 such that for all δ, θ > 0 there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ when drawing graphs from ER(n, p(n)), we have that the proportion of all nodes u such that|N (u)| ≥ R log(n) is at least 1 -δ.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 ∧-descriptions of Definition C.3. Lemma C.5. Take any ∧-description ϕ on k variables, and choose i ≤ k. We consider k-tuples of nodes ū satisfying ϕ and the degrees of the i th node u i .(1) Let p satisfy the density condition, converging to p. Then for every ϵ, θ > 0 there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ when drawing graphs from ER(n, p(n)), for all tuples ū which satisfy ϕ we have that:n(p -ϵ) < d(u i ) < n(p + ϵ)(2) Let p satisfy the root growth condition, with p = Kn -β . Then for every R 1 ∈ (0, 1) and R 2 > 1 and for every θ > 0 there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ when drawing graphs from ER(n, p(n)), for all tuples ū which satisfy ϕ we have that:R 1 Kn 1-β < d(u i ) < R 2 Kn 1-β(3) Let p satisfy the log growth condition, with p = K log(n) n . Then for every R 1 ∈ (0, 1) and R 2 > 1 and for every δ, θ > 0 there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ when drawing graphs from ER(n, p(n)), for at least 1 -δ of the tuples ū which satisfy ϕ we have that:R 1 K log(n) < d(u i ) < R 2 K log(n)Moreover, there is R 3 > 0 such that for every θ > 0 there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ when drawing graphs from ER(n, p(n)), for all tuples ū which satisfy ϕ we have that:d(u i ) < R 3 K 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 R 3 , while the latter gives a bound for an arbitrary R 2 .We now give the proof of the lemma:Proof.(1) Take ϵ, θ > 0. First, there is N 1 such that for all n ≥ N 1 :|p(n) -p| < ϵNow, any d(u) is the sum of n -1 i.i.d. Bernoulli random variables with parameter p(n): see Remark C.2 for the formalization. Hence by Hoeffding's Inequality (Theorem B.4) and a union bound, there is N 2 such that for all n ≥ N 2 , with probability at least 1 -θ, for every node u we have:d(u) n -p < ϵ Letting N = max(N 1 , N 2 ), the result follows.(2) Take R 1 ∈ (0, 1) and R 2 > 1 and fix θ > 0. Again, any d(u) is the sum of n -1 i.i.d. Bernoulli random variables with parameter p(n). By Chernoff's Inequality (Theorem B.3), for any node u we have that:P d(u) ≤ R 1 Kn 1-β ≤ exp Kn 1-β (R 1 -1 -R 1 log(R 1 )) Since R 1 -1 -R 1 log(R 1 )< 0, by a union bound there is N 1 such that for all n ≥ N 1 , with probability at least 1 -θ, for every node u we have:d(u) > R 1 Kn 1-βSimilarly there is N 2 such that for all n ≥ N 2 , with probability at least 1 -θ, for every node u we have:d(u) < R 2 Kn 1-β Letting N = max(N 1 , N 2 ), the result follows.(3) Take R 1 ∈ (0, 1) and R 2 > 1 and fix δ, θ > 0. By Chernoff's Inequality (Theorem B.3), for any node u we have that:P d(u) ≤ R 1 Kn 1-β ≤ n K(R1-1-R1 log(R1))Since R 1 -1 -R 1 log(R 1 ) < 0 this probability tends to 0 as n tends to infinity. Hence there is N 1 such that for all n ≥ N 1 , for all nodes u:P (d(u) ≤ R 1 log(n))< θδ Let B n be the proportion, our of tuples ū which satisfy ϕ, such that:d(u i ) ≤ R log(n) (the 'bad' tuples). Then for n ≥ N 1 , by linearity of expectation E[B n ] ≤ θδ.By Markov's Inequality (Theorem B.1) we have that:P (B n ≥ δ) ≤ θδ δ = θThat is, with probability at least 1 -θ we have that the proportionout of tuples ū which satisfy ϕ such that:d(u i ) > R 1 log(n) is at least 1 -δ.Similarly, there is N 2 such that for all n ≥ N 2 , with probability at least 1 -θ we have that the proportion out of tuples ū which satisfy ϕ such that:d(u i ) < R 2 log(n) is at least 1 -δ. Letting N = max(N 1 , N 2 ) the first statement follows.To show the 'moreover' part, note that by Chernoff's Inequality (Theorem B.3), for any R 3 > 0 and for any node u we have that:P d(u) ≥ R 3 Kn 1-β ≤ n K(R3-1-R3 log(R3))For R 3 large enough we have that K(R 3 -1 -R 3 log(R 3 )) ≤ -2. Hence taking a union bound for every θ > 0 there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ when drawing graphs from ER(n, p(n)), for all tuples ū which satisfy ϕ we have that:d(u i ) < R 3 K log(n)The basic form of the following "regularity lemma" states that for every k ∈ N + and i ≤ k, whenever we have a large subset S of the (k + 1)-tuples (ū, v) with each u i adjacent to v, there is a large subset of the k-tuples ū such that each u i is adjacent to a large set of v's such that (ū, v) ∈ S. The full regularity lemma states that this is the case also when we restrict the tuples ū to a certain ∧-description. Lemma C.6 (Regularity Lemma). Let p : N → [0, 1] satisfy one of the conditions other than sparsity. Take a ∧-description ϕ on k variables and fix i ≤ k. Then for every γ, θ > 0 there is N ∈ N and δ ′ > 0 such that for all n ≥ N and δ < δ ′ , with probability at least 1 -θ we have that, wheneverS ⊆ {(ū, v) | ϕ(ū) ∧ u i Ev} is such that: |S| |{(ū, v) | ϕ(ū) ∧ u i Ev}| ≥ 1 -δ then there is S ′ ⊆ {ū | ϕ(ū) and d(u i ) > 0} such that: |S ′ | |{ū | ϕ(ū) and d(u i ) > 0}| ≥ 1 -γand for every ū ∈ S ′ we have:|{v | (ū, v) ∈ S}| d(u i ) ≥ 1 -(δ + δ 2 )For this we make use of the following purely combinatorial lemma. Lemma C.7. Take δ, σ > 0. Let (B 1 , . . . , B m ) be a sequence of disjoint finite sets of minimum size a and maximum size b. Take S ⊆ m i=1 B i such that:|S| m i=1 |B i | ≥ 1 -δLet:S ′ := i |S ∩ B i | |B i | ≥ 1 -σ Then: |S ′ | m ≥ 1 - (σ -δ)a (σ -δ)a + δbProof. Let B := (B 1 , . . . , B m ). We look for an upper bound on:γ B,S := 1 - |S ′ | mTo do this, take any ( B, S) with proportion at least 1 -δ which minimises γ B,S . By performing a series of transformations, we show that we can assume that ( B, S) is of a particular form.• First, ensuring that S ∩ B i = B i for each i ∈ S ′ does not increase γ B,S and does not decrease the proportion|S| m i=1 |Bi| . • We can also make sure that |B i | = b for each i ∈ S ′ .• Similarly, we can ensure that:|S ∩ B i | |B i | = ⌊1 -σ⌋ for each i / ∈ S ′ .• Finally, we can make sure that |B i | = a for each i / ∈ S ′ . Now, using this nice form for ( B, S), we can compute:1 -δ ≤ |S| m i=1 |B i | ≤ γ B,S b + (1 -γ B,S )(1 -σ)a γ B,S b + (1 -γ B,S )aRearranging we get:|S ′ | m = 1 -γ B,S ≥ 1 - (σ -δ)a (σ -δ)a + δb as required.Proof of Lemma C.6. We proceed differently depending on which of the non-sparse conditions are satisfied.We begin with the Density condition. Say p converges to some p > 0. Fix γ, θ > 0. Now choose ϵ, δ ′ > 0 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 ≥ N , with probability at least 1 -θ, for all tuples ū which satisfy ϕ(ū) we have that:n(p -ϵ) < d(u i ) < n(p + ϵ)Condition on the event that this holds. Take any δ < δ ′ and S ⊆ {(ū, v) | ϕ(ū) ∧ u i Ev} such that:|S| |{(ū, v) | ϕ(ū) ∧ u i Ev}| ≥ 1 -δ Let: S ′ := ū ϕ(ū) and |{v | (ū, v) ∈ S}| d(u i ) ≥ 1 -(δ + δ 2 )Applying Lemma C.7 with σ = δ + δ 2 , a = n(p -ϵ) and n = n(p + ϵ), we get that:|S ′ | |{ū | ϕ(ū) and d(u i ) > 0}| ≥ 1 - (δ + δ 2 -δ)n(p -ϵ) (δ + δ 2 -δ)n(p -ϵ) + δn(p + ϵ) = 1 - δ(p -ϵ) δ(p -ϵ) + (p + ϵ)By making ϵ and δ ′ small enough, we can make this greater than 1 -γ. This completes the proof for the dense case.We now give the proof for the case of Root growth. Let p(n) = Kn -β . Fix γ, θ > 0. Choose δ ′ > 0 small enough. Also choose R 1 ∈ (0, 1) and R 2 > 1.By Lemma C.5 (2) there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ, for all tuples ū which satisfy ϕ(ū) we have that:R 1 Kn 1-β < d(u i ) < R 2 Kn 1-βProceeding analogously to the dense case, we have that for all δ < δ ′ :|S ′ | |{ū | ϕ(ū) and d(u i ) > 0}| ≥ 1 - δR 1 Kn 1-β δnR 1 Kn 1-β + R 2 Kn 1-β = 1 - δR 1 δR 1 + R 2By making δ ′ and R 2 -R 1 small enough, we can make this greater than 1 -γ. This completes the proof for the root growth case.Finally, we give the argument for the case of Logarithmic growth. Let p(n) = K log(n) n . Fix γ, θ > 0. Choose ζ, δ ′ > 0 small enough. Also choose R 1 ∈ (0, 1) and R 2 > 1.By Lemma C.5 (3), there is R 3 > 0 and N ∈ N such that for all n ≥ N , with probability at least 1 -θ when drawing graphs from ER(n, p(n)), for at least 1 -δ of the tuples ū which satisfy ϕ(ū) we have that:R 1 K log(n) < d(u i ) < R 2 K log(n)and moreover for all tuples ū which satisfy ϕ(ū) we have that:d(u i ) < R 3 K log(n)Now, let:Q := {ū | R 1 K log(n) < d(u i ) < R 2 K log(n)}For n large enough we have both:|Q| |{ū | ϕ(ū) and d(u i ) > 0}| ≥ 1 -ζand (using the fact that outside of Q all nodes u i have degree at mostR 3 K log(n)): |{(ū, v) | ϕ(ū) ∧ u i Ev and ū ∈ Q}| |{(ū, v) | ϕ(ū) ∧ u i Ev}| ≥ 1 -ζSince we have control over ζ, it suffices to restrict attention to:S ⊆ {(ū, v) | ϕ(ū) ∧ u i Ev and ū ∈ Q}Then, analogously to the dense case, we have that for the worst case, for every δ < δ ′ :|S ′ | |{ū | ϕ(ū) and d(u i ) > 0}| ≥ 1 - δR 1 δR 1 + R 2By making δ ′ and R 2 -R 1 small enough, we can make this greater than 1 -γ.This completes the proof of Lemma C.6 for the logarithmic growth case.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-sparse cases. We see that the embeddings are almost surely zero. Lemma C.8. Let p : N → N satisfy density, root growth or logarithmic growth. Then for every k ∈ N and every ϵ, δ, θ > 0 there is N ∈ N such that for all n ≥ N with probability at least 1 -θ, the proportion of nodes v such that:∥rw k (v)∥ < ϵ is at least 1 -δ.Proof. We start with the Dense case. Let p converge to p > 0. Take ϵ, δ, θ > 0. By Hoeffding's Inequality (Theorem B.4) and taking a union bound, there is N such that for all n ≥ N with probability at least 1 -θ we have that:|d(v) -pn| < ϵnCondition on this event.For any node v the number of length-k walks from v is at least:((p -ϵ)n) kBy removing the last node of the walk, the number of length-k walks from v to itself is at most the number of length-(k -1) walks from v.The number of length-(k -1) walks from v is at most:((p + ϵ)n) k-1Thus the proportion of length-k walks from v which return to v is at most:((p + ϵ)n) k-1 ((p -ϵ)n) k = (p + ϵ) k-1 (p -ϵ) k n -1This tends to 0 an n tends to infinity.We now argue this for the Root growth case. Let p = Kn -β .As in the proof of Lemma C.6, by Chernoff's Inequality (Theorem B.3) and taking a union bound, there are 0 < R 1 < 1 < R 2 and N such that for all n ≥ N with probability at least 1 -θ we have that for all v: R 1 Kn1-β < d(v) < R 2 Kn 1-βThen, as in the dense case, the proportion of length-k walks from v which return to v is at most:R 2 Kn 1-β k-1 (R 1 Kn 1-β ) k = R k-1 2 R k 1 K n β-1which tends to 0 as n tends to infinity.Finally, we argue this for the Logarithmic growth case. Let p = K log(n). Take ϵ, δ, θ > 0.As in the proof of Lemma C.6, by Chernoff's Inequality (Theorem B.3), there are 0 < R 1 < 1 < R 2 and N such that for all n ≥ N 1 with probability at least 1 -θ we have that for at least 1 -δ proportion of nodes v:R 1 K log(n) < d(v) < R 2 K log(n) (⋆)Moreover, by Chernoff's Inequality and a union bound, there is R 3 > 0 such that for all n ≥ N 2 with probability at least 1 -θ we have that for all v:d(v) < R 3 K log(n)Let N := max(N 1 , N 2 ). Take n ≥ N . We will condition on the event that the above inequalities hold.Take any node v such that equation (⋆) holds. Then, the number of length-k walks from v is at least:R 1 K log(n)((1 -δ)(R 1 K log(n))) k-1The number of length-k walks from v to itself is at most:(R 3 K log(n)) k-1Thus the proportion of length-k walks from v which return to v is at most:(R 3 K log(n)) k-1 R 1 K log(n)((1 -δ)(R 1 K log(n))) k-1 = R k-1 3 R k 1 (1 -δ) k-1 • 1 log(n)This tends to 0 as n tends to infinity.Finally, we need a simple lemma about division, which has a straightforward proof: Lemma C.9. Let x, y, z, w ∈ R and ζ, ξ, ν, Ω > 0 with ν > ξ be such that |x -y| < ζ and |z -w| < ξ while |x|, |z| < Ω and z > ν. Then:x z - y w < Ω(ζ + ξ) ν(ν -ξ)C.2 Proving the inductive invariant for the non-sparse cases, and proving the convergence theorem for these casesWith the growth lemmas for the non-sparse cases in hand, we return to presenting the main proof of Theorem C.1, the convergence theorem for non-sparse ER distributions.Throughout the following subsection, for notational convenience we allow empty tuples.For a tuple ū in a graph let GrTp(ū) be the graph type of ū. For k ∈ N let GrTp k be the set of such types with k free variables. For any t ∈ GrTp k let:Ext(t) := {t ′ (ū, v) ∈ GrTp k+1 | t ′ (ū, v) ⊨ t(ū)}For any u i free in t let:Ext ui (t) := {t ′ (ū, v) ∈ GrTp k+1 | t ′ (ū, v) ⊨ t(ū) ∧ u i Ev}We now are ready to begin the proof of Theorem 5.1 for the non-sparse cases. This will involve defining controllers and proving that they satisfy the inductive invariant.Let F be the probability distribution of the node features, which, for the sake of convenience, we assume to have domain Note that in each case the probability function p(n) converges to some p (which is 0 in the root growth and logarithmic growth cases).Recall from the body of the paper that a (ū, d) feature-type controller is a Lipschitz function taking as input pairs consisting of a d-dimensional real vector and a ū graph type. Recall from Theorem 5.3 that for each term π, we need to define a controller e π that approximates it. We first give the construction of e π and then recall and verify what it means for e π to approximate π.Take ā ∈ ([0, 1] d ) k and t ∈ GrTp k ,where k is the number of free variables in π.When π = H(u) define: We start with the construction for the global weighted mean. For any t(ū) ∈ GrTp k and t ′ (ū, v) ∈ Ext(t), define α(t, t ′ ) as follows. As an extension type, t ′ specifies some number, say r, of edges between the nodes ū and the new node v. Define: α(t, t ′ ) := pr (1 -p) k-r Note that in both the root growth and logarithmic growth cases, α(t, t ′ ) is non-zero precisely when t ′ specifies no edges between ū and v. These relative atomic type weights will play a key role in the construction.π = v ρ(ū, v) ⋆ h(η(ū, v)).Recall that the semantics are:v∈G ρ(ū, v) G h( η(ū, v) G ) v∈G h( η(ū, v) G )Define:e π (ā, t) := f π (ā, t) g π (ā, t) where: f π (ā, t) := t ′ ∈Ext(t) α(t, t ′ ) E b∼F [e ρ (ā, b, t ′ )h(e η (ā, b, t ′ ))]and:g π (ā, t) := t ′ ∈Ext(t) α(t, t ′ ) E b∼F [h(e η (ā, b, t ′ ))]Note that when p = 0 (as in the root growth and logarithmic growth cases), we have that:α(t, t ′ ) = 1 if t ′ specifies no edges between ū and v 0 otherwise Therefore the controller becomes, letting t ∅ be the type with no edges between ū and v:e π (ā, t) = E b∼F [e ρ (ā, b, t ∅ )h(e η (ā, b, t ∅ ))] E b∼F [h(e η (ā, b, t ∅ ))]For the local weighted mean case, given t(ū) ∈ GrTp k and t ′ (ū, v) ∈ Ext ui (t), we define α ui (t, t ′ ) as follows. Let r be the number of edges specified by t ′ between ū \ u i and v. Define:α ui (t, t ′ ) := pr (1 -p) k-r-1 Consider π = v∈N (ui) ρ(ū, v) ⋆ h(η(ū, v)). Define: e π (ā, t) := f π (ā, t) g π (ā, t) where: f π (ā, t) := t ′ ∈Extu i (t) α ui (t, t ′ ) E b∼F [e ρ (ā, b, t ′ )h(e η (ā, b, t ′ ))]and:g π (ā, t) := t ′ ∈Extu i (t) α ui (t, t ′ ) E b∼F [h(e η (ā, b, t ′ ))]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 ∧-decriptions from Definition C.3:Lemma C.10. For every ϵ, δ, θ > 0 and ∧-description ψ(ū), there is N ∈ N such that for all n ≥ N , with probability at least 1 -θ in the space of graphs of size n, out of all the tuples ū such that ψ(ū), at least 1 -δ satisfy: ∥e π (H(ū), GrTp(ū)) -π(ū) ∥ < ϵProof. Naturally, we prove the lemma by induction.• Base cases H(v) and constant c. These are immediate from the definition.• Base case rw(v). This follows by Lemma C.8.• Induction step for Lipschitz functions f (ρ 1 , . . . , ρ r ).Take ϵ, δ, θ > 0 and ∧-description ψ(ū). By the induction hypothesis there is N ∈ N such that for all n ≥ N and for every i ≤ r, with probability at least 1 -θ, we have that out of all the tuples ū such that ψ(ū), at least 1 -δ satisfy:∥e ρi (H(ū), GrTp(ū)) -ρ i (ū) ∥ < ϵHence, with probability at least 1 -rθ, out of all the tuples ū such that ψ(ū), at least 1 -rδ satisfy this for every i ≤ r. Condition on this event.Take any such tuple ū. Then by Lipschitzness of f we have that the normed distance between:e π (H(ū), GrTp(ū)) = f (e ρ1 (H(ū), GrTp(ū)), . . . , e ρr (H(ū), GrTp(ū)))and:π(ū) = f ( ρ 1 (ū) , . . . , ρ r (ū) )is at most L f ϵ, where L f is the Lipschitz constant of f . Since L f is a constant, this case follows.• Inductive step for v ρ(ū, v) ⋆ h(η(ū, v)).Take ϵ, δ, θ > 0. Take a ∧-description ψ(ū).By the induction hypothesis, there is N 1 such that for all n ≥ N 1 , with probability at least 1 -θ, out of all the tuples (ū, v) which satisfy ψ(ū), at least 1 -δ satisfy:∥e ρ (H(ū, v), GrTp(ū, v)) -ρ(ū, v) ∥ < ϵ ( † ρ )and:∥e η (H(ū, v), GrTp(ū, v)) -η(ū, v) ∥ < ϵ ( † η )Take γ > 0. We will choose how small γ is later.By Lemma C.6 there is N γ > N 1 such that for all n ≥ N γ , with probability at least 1 -θ, out of all the tuples ū such that ψ(ū), at least 1 -γ, at least 1 -(δ + δ 2 ) of the v's satisfy equation ( † ρ ) and equation ( † η ). Now consider t(ū) ∈ GrTp k and take any t ′ (ū, v) ∈ Ext(t). For any tuple ū of nodes such that GrTp(ū) = t, define:t ′ (ū) := {v | t ′ (ū, v)}Since p(n) converges to p and Ext(t) is finite, there is N 3 such that for all n ≥ N 3 with probability at least 1 -θ we have that for every pair (t, t ′ ) and tuple ū of nodes such that t(ū):| t ′ (ū) | n -α(t, t ′ ) < 1 2 k+1 ϵ ( * )Next, for any tuple ū consider the function:f • π (ū, v) := e ρ (H G (ū, v), GrTp(ū, v))h(e η (H G (ū, v), GrTp(ū, v))) Note that the function: (ā, b, t ′ ) → e ρ (ā, b, t ′ )h(e η (ā, b, t ′ ))is bounded. Let Λ be the diameter of its range. This also bounds f • π .We will now apply Hoeffding's Inequality to v|t ′ (ū,v) f • π (ū, v). Note that the number of summands is | t ′ (ū) | and the summands are bounded by Λ. Furthermore, the summands are independent and have expected value:E b∼F [e ρ (H G (ū, b), t ′ )h(e η (H G (ū, b), t ′ ))]Hence, by Hoeffding's Inequality (Theorem B.4) for any ū the probability that:1 n v|t ′ (ū,v) f • π (ū, v) - | t ′ (ū) | n E b∼F [e ρ (H G (ū, b), t ′ )h(e η (H G (ū, b), t ′ ))] ≥ 1 2 k+1 ϵ (♡) is at most: 2d exp - ϵ 2 | t ′ (ū) | 2Λ 2By equation ( * ) there is N 4 such that for all n ≥ N 4 , with probability at least 1 -θ for all t ′ such that α(t, t ′ ) > 0 we have that for every tuple ū:2d exp - ϵ 2 | t ′ (ū) | 2Λ 2 < θδ (♣)Let B n be the proportion, out of all tuples ū for which ψ(ū) holds4 , such that:1 n v|t ′ (ū,v) f • π (ū, v) - | t ′ (ū) | n E b∼F [e ρ (H G (ū, b), t ′ )h(e η (H G (ū, b), t ′ ))] ≥ 1 2 k+1 ϵNote that the property above is exactly the event whose probability is bounded in equation (♡). We can express B n as the mean of a set of indicator variables, one for each tuple ū such that ψ(ū) holds. Each indicator variable has expected value at most θδ by equation (♡) and equation (♣).Then by linearity of expectation, E[B n ] ≤ θδ for all n ≥ N 4 , and hence by Markov's Inequality (Theorem B.1):P (B n ≥ δ) ≤ θδ δ = θTherefore, for all n ≥ max(N 3 , N 4 ), with probability at least 1 -θ for at least 1 -δ of the tuples ū for which ψ(ū) holds we have that:1 n v|t ′ (ū,v) f • π (ū, v) - | t ′ (ū) | n E b∼F [e ρ (H G (ū, b), t ′ )h(e η (H G (ū, b), t ′ ))] < 1 2 k+1 ϵand therefore, by equation ( * ) and the definition of f π :1 n v f • π (ū, v) -f π (H G (ū), GrTp(ū)) < ϵ (△ f )Similarly, for any tuple ū consider the function:g • π (ū, v) := h(e η (H G (ū, v), GrTp(ū, v)))As above there is N 5 ≥ N 3 such that for all n ≥ N 5 with probability at least 1 -θ we have that the proportion out of tuples ū for which ψ(ū) holds such that:1 n v g • π (ū, v) -g π (H G (ū), GrTp(ū)) < ϵ (△ g ) is at least 1 -δ.Take n ≥ max(N 1 , N γ , N 3 , N 4 , N 5 ). For such an n, these events above hold with probability at least 1 -5θ. So from now on we will condition on the event that they hold.Take any such tuple ū. Let t := GrTp(ū). It suffices to show, using the definition of the interpretation of the weighted mean operator, that:v ρ(ū, v) h( η(ū, v) ) v h( η(ū, v) ) - f π (H G (ū), t) g π (H G (ū), t) < ι(ϵ, δ, γ)for ι which we can make arbitrarily small by choosing ϵ, δ, γ small enough.By Lemma C.9 it suffices to find ζ(ϵ, δ, γ), ξ(ϵ, δ, γ) > 0 which we can make arbitrarily small and constants ν, Ω > 0 such that:EQUATIONEQUATIONFor equation ( 3) and equation ( 4) we can use the fact that ρ(ū, v) and η(ū, v) are bounded and that h is Lipschitz on bounded domains. For equation (5) we use the fact that η(ū, v) is bounded and that the codomain of h is (0, ∞) d .The proofs of equation ( 1) and equation ( 2) are very similar. We prove equation ( 2) since it is slightly notationally lighter. Let:g * π (ū) := 1 n v h(e η (H G (ū, v), t))Let κ be a bound on the norms of h(e η (ā, b, t ′ )) and h( η(ū, v) ). By equation ( † η ) we have that:1 n v h( η(ū, v) ) -g * π (ū) < 1 -(δ + δ 2 ) ϵ + (δ + δ 2 )2κ 2We can make the right-hand-side as small as we like by taking ϵ and δ sufficiently small. Now note that:g * π (ū) = 1 n v g • π (ū, v)Hence by equation (△ g ) we have that:∥g * π (ū) -g π (H G (ū), t)∥ < ϵTherefore:g π (H G (ū), t) - 1 n v h( η(ū, v) ) < 1 -(δ + δ 2 ) ϵ + (δ + δ 2 )2κ 2 + ϵwhich we can make as small as we like by taking ϵ and δ small enough.• Inductive step for v∈N (ui) ρ(ū, v) ⋆ h(η(ū, v)).We proceed similarly to the global weighted mean case, this time making use of the conditioning ∧-description in the inductive invariant. Indeed, notice that when we apply the inductive invariant below, we add u i Ev to our condition.Take ϵ, δ, θ > 0. Take a ∧-description ψ(ū).By the induction hypothesis, there is N 1 such that for all n ≥ N 1 , with probability at least 1 -θ, out of all the tuples (ū, v) which satisfy ψ(ū) ∧ u i Ev, at least 1 -δ satisfy:∥e ρ (H G (ū, v), GrTp(ū, v)) -ρ(ū, v) ∥ < ϵ ( † loc ρ ) and: ∥e η (H G (ū, v), GrTp(ū, v)) -η(ū, v) ∥ < ϵ ( † loc η ) Take γ > 0.We will choose how small γ is later. By Lemma C.6 there is N γ > N 1 such that for all n ≥ N γ , with probability at least 1 -θ the following event happens. Out of all the tuples ū such that ψ(ū) ∧ ∃v : u i Ev, a proportion of at least 1 -γ of them satisfy the following. At least 1 -(δ + δ 2 ) of the nodes v for which ψ(ū) ∧ u i Ev holds also satisfy equation ( † loc ρ ) and equation ( † loc η ). Now consider t(ū) ∈ GrTp k and take any t ′ (ū, v) ∈ Ext ui (t). For any tuple ū of nodes such that GrTp(ū) = t, define:t ′ (ū) := {v ∈ N (u i ) | t ′ (ū, v)}By Lemma C.5 we have that in all the non-sparse cases there is R > 0 and N 3 such that for all n ≥ N 3 with probability at least 1 -θ, the proportion of all tuples ū for which ψ(ū) holds such that:d(u i ) ≥ R log(n) is at least 1 -δ.Then, as before, there is N 4 ≥ N 3 such that for all n ≥ N 4 , with probability at least 1 -θ, for all pairs (t, t ′ ) the proportion of all tuples ū for which ψ(ū) and t(ū) hold such that:| t ′ (ū) | d(u i ) -α(t, t ′ ) < 1 2 k+1 ϵFor any tuple ū define the function:f • π (ū, v) := e ρ (H G (ū, v), GrTp(ū, v))h(e η (H G (ū, v), GrTp(ū, v)))Taking Λ as before, by Hoeffding's Inequality for any ū the probability that:1 d(u i ) v∈N (ui)|t ′ (ū,v) f • π (ū, v) - | t ′ (ū) | d(u i ) E b∼F [e ρ (H G (ū, b), t ′ )h(e η (H G (ū, b), t ′ ))] ≥ 1 2 k+1 ϵ is at most: 2d exp - ϵ 2 | t ′ (ū) | 2Λ 2Using a similar argument to the global weighted mean case, there is N 5 such that for all n ≥ N 5 , with probability at least 1 -θ for all t ′ such that α(t, t ′ ) > 0 we have that for at least 1 -δ of the tuples ū such that ψ(ū) and t(ū) hold:2d exp - ϵ 2 | t ′ (ū) | 2Λ 2 < θδWe now proceed as in the global weighted mean case, creating a random variable similar to B n and making using of linearity of expectation. We get that for all n ≥ max(N 3 , N 4 , N 5 ), with probability at least 1 -θ for at least 1 -δ of the tuples ū for which ψ(ū) holds we have that:1 n v f • π (ū, v) -f π (H G (ū), GrTp(ū)) < ϵ (△ loc f )Similarly, with g • π defined as above, there is N 6 such that for all n ≥ N 6 , with probability at least 1 -θ for at least 1 -δ of the tuples ū for which ψ(ū) holds we have that:1 n v g • π (ū, v) -g π (H G (ū), GrTp(ū)) < ϵ (△ loc g )With equations ( † loc ρ ), ( † loc η ), (△ loc f ) and (△ loc g ) established, we can now proceed as before, making use of Lemma C.9.This completes the proof of Theorem 5.3.Applying the lemma to prove the theorem. To prove Theorem C.1, note that e τ is only a function of the GrTp 0 (since τ is a closed term), while GrTp 0 consists of a single type, ⊤, which is satisfied by all graphs. So e τ is a constant.We now give the proof for the sparse Erdős-Rényi and Barabási-Albert cases of Theorem 5.1. In addition, we extend the result to the language AGG[WMEAN, GCN, RW] defined in Appendix A. We state the full result here. Theorem D.1. Consider (µ n ) n∈N sampling a graph G from either of the following models and node features independently from i.i.d. bounded distributions on d features.1. The Erdős-Rényi distribution ER(n, p(n)) where p satisfies Sparsity: for some K > 0 we have:p(n) = Kn -1 .2. The Barabási-Albert model BA(n, m) for any m ≥ 1.Then for every AGG[WMEAN, GCN, RW] term converges a.a.s. with respect to (µ n ) n∈N .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 is a tuple (T, ū). At various points below to lighten the notation we drop the 'ū' and refer simply to a k-rooted graph T .As in the dense case, before we turn to analysis of our term language, we prove some results about the underlying random graph model that we can use as tools.The key combinatorial tool we 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 a k-rooted graph and let (T ′ , w, y) be a (k + 1)-rooted graph. Then T ′ extends T if T is a subgraph of T ′ . Let Ext(T ) be the set of all (k + 1)-rooted graphs extending (T, w). Theorem D.4. Consider sampling a graph G from either the sparse Erdős-Rényi or Barabási-Albert distributions. Let (T, w) be a k-rooted graph and take ℓ ∈ N. Then for every (k + 1)-rooted graph (T ′ , w, y) which extends (T, w) there is q T ′ |T ∈ [0, 1] such that for all ϵ, θ > 0 there is N ∈ N such that for all n ≥ N with probability at least 1 -θ we have that for all k-tuples of nodes ū such thatN G ℓ (ū) ∼ = (T, w): |{v | N G ℓ (ū, v) ∼ = (T ′ , w, y)}| n -q T < ϵMoreover, we have that:T ′ ∈Ext(T ) q T ′ |T = 1We refer to the q T ′ |T as relative neighborhood weights. They will play a role in defining the controllers, analogous to that of the relative atomic type weights α(t, t ′ ) in the non-sparse case.Theorem D. 4 follows from what is known as "weak local convergence" in the literature. It is essentially a non-parametrised version of Theorem D.4. Definition D.5. A sequence (µ n ) n∈N of graph distributions has weak local convergence if for every k-rooted graph (T, w) and ℓ ∈ N there is q T ∈ [0, 1] such that for all ϵ, θ > 0 there is N ∈ N such that for all n ≥ N with probability at least 1 -θ we have that:|{ū | N G ℓ (ū) ∼ = (T, w)}| n -q T < ϵand moreover:T q T = 1Theorem D. Proof of Theorem D.4. Take T ′ ∈ Ext(T ). There are two cases.Case 1. There is a path from y to some node w i of w in T ′ .Set q T ′ |T = 0. Note that in this case, for all tuples ū such that N G ℓ (ū) ∼ = T we have that:{v | N G ℓ (ū, v) ∼ = (T ′ , w, y)} ⊆ N G ℓ (u i )} Since N G ℓ (u i) is determined by T and is thus of fixed size, the proportion:|{v | N G ℓ (ū, v) ∼ = (T ′ , w, y)}| ntends to 0 as n grows. This completes the proof for Case 1.Case 2. There is no path from y to any node of w in T ′ . Then for all tuples ū such that N G ℓ (ū) ∼ = T we have that:{v | N G ℓ (ū, v) ∼ = (T ′ , w, y)} = {v | N G ℓ (v) ∼ = N T ′ ℓ (y)} \ N G ℓ (ū) Hence: |{v | N G ℓ (v) ∼ = N T ′ ℓ (y)}| n - |N G ℓ (ū)| n ≤ |{v | N G ℓ (ū, v) ∼ = (T ′ , w, y)}| n Also: |{v | N G ℓ (ū, v) ∼ = (T ′ , w, y)}| n ≤ |{v | N G ℓ (v) ∼ = N T ′ ℓ (y)}| nBy Lemma 5.5 (with k = 1) we have that:EQUATIONy)}| n converges to some limit q T |T ′ := q N T ′ ℓ (y) asymptotically almost surely, while:|N G ℓ (ū)| n =|T | n converges to 0. This completes the proof for Case 1.Finally, to show that T ′ ∈Ext(T ) q T ′ |T = 1, note the set:{N T ′ ℓ (y) | (T ′ , w, y) ∈ Ext(T ′)} contains all 1-rooted graphs up to isomorphism which can be the ℓ-neighbourhood of a node. Therefore, by the "moreover" part of Definition D.5 we have that:T ′ ∈Ext(T ) q T ′ |T = T ′ ∈Ext(T ) q N T ′ ℓ (y) = 1 D.2Proving the inductive invariant for the sparse cases, and proving the convergence theorem for these casesWe now begin the proof of Theorem D.1. Recall from the body that we will do this via Theorem 5.6, which requires us to define some Lipschitz controllers on neighbourhood types that approximate a given term π relative to a neighbourhood type.Throughout the following, it will be convenient to assume for every k-rooted graph isomorphism type (T, ū) a canonical ordering nodes T = {s 1 , . . . , s |T | } such that:• the first k nodes in the ordering are ū and • for any graph G, tuple of nodes ū and ℓ, ℓ ′ ∈ N with ℓ ′ < ℓ the canonical ordering of N ℓ ′ (ū) is an initial segment of the canonical ordering of N ℓ (ū).Again we will use F for the probability distribution of the node features. For each subterm π of τ , its reach, denoted Reach(π) is a natural number defined as follows:Reach(H(u)) = 0 Reach(c) = 0 Reach(rw(v)) = d Reach(f (ρ 1 , . . . , ρ r )) = max i≤r Reach(ρ i ) Reach   v∈N (u) ρ ⋆ h(η)   = max(Reach(ρ), Reach(η)) + 1 Reach v ρ ⋆ h(η) = 0Take a subterm π of τ . Let k be the number of free variables in π. We now define the controller at π for every k-rooted graph (T, w). The controller will be of the form:e T π : ([0, 1] d ) |T | → R d Note that when |T | = 0 this is a constant.Recall from Theorem 5.6 that our goal is to ensure the following correctness property for our controllers e T π . Property D.7. Let π be any subterm of τ and let ℓ = Reach(π). Consider sampling a graph G from either the sparse Erdős-Rényi or Barabási-Albert distributions. For every k-rooted graph (T, w) and ϵ, θ > 0, there is N ∈ N such that for all n ≥ N with probability at least 1 -θ we have that for every k-tuple of nodes ū in the graph such that N ℓ (ū) ∼ = (T, w), taking the canonical orderingN ℓ (ū) = {s 1 , . . . , s |T | }: e T π (H G (s 1 ), . . . , H G (s |T | )) -π(ū) < ϵFor notational convenience, we allow each e T π to take additional arguments as input, which it 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 i ).Here ℓ = Reach(π) = 0. Let e T π (ā) := a i , the feature value of the i th node in the tuple. Note that for any k-tuple of nodes ū in the graph we have:e T π (H G (s 1 ), . . . , H G (s |T | )) = H G (s i ) = π(ū) • Base case π = c.Let e T π (ā) := c.• Base case π = rw(u i ).Then ℓ = Reach(π) = d. Note that the random walk embeddings up to length d are entirely determined by the d-neighbourhood. Therefore, given rooted graph (T, w), there is r T such that: rw(u i ) = r T for all tuples ū such that N ℓ (ū) = T . So set:e T π (ā) = r T for any ā.• Inductive step for Lipschitz functions π = F (ρ 1 , . . . , ρ r ).Note that ℓ = max j≤r Reach(ρ i ). Take a k-rooted graph (T, w). For each i ≤ r let T j := N T Reach(ρj ) ( w). Define: e T π (ā) := F (e T1 ρ1 (ā), . . . , e Tr ρr (ā))Now take ϵ, θ > 0. By the induction hypothesis, there is N such that for all n ≥ N with probability at least 1-θ we have that for every k-tuple of nodes ū in the graph, letting T = N ℓ (ū), for every j ≤ r: e Tj ρj (H G (s 1 ), . . . , H G (s |Tj | )) -ρ j (ū) < ϵ Hence, by the Lipschitzness of F we have:e T π (H G (s 1 ), . . . , H G (s |T | )) -π(ū) < L F ϵ where L F is the Lipschitz constant of F . • Inductive step for local weighted mean π = v∈N (ui) ρ ⋆ h(η).In this step we use that the value of a local aggregator is determined by the values of the terms it is aggregating in the local neighbourhood. Take a k-rooted graph (T, w), where k is the number of free variables in π. Note that ℓ = max(Reach(ρ), Reach(η)) + 1.When w i has no neighbours in T , define: e T π (ā) := 0 and note that for any k-tuple of nodes ū in the graph such that N ℓ (ū) = T we have:π(ū) = 0 = e T π (H G (s 1 ), . . . , H G (s |T | ))So suppose that w i has some neighbours in T . Enumerate the neighbours as:N T (w i ) = {y 1 , . . . , y r }Define the Lipschitz function:WMean T (a 1 , . . . , a r , b 1 , . . . , b r ) := r j=0 a j h(b j ) r j=0 h(b j )Note that whenever N G ℓ (ū) ∼ = (T, w), letting N G (u i ) = {v 1 , . . . , v r } be the enumeration of the neighbourhood of u i given by the isomorphism, we have that:π(ū) = WMean T ( ρ(ū, v 1 ) , . . . , ρ(ū, v r ) , η(ū, v 1 ) , . . . , η(ū, v r ) ) (□)For any y j ∈ N (w i ), let:T j := N T ℓ-1 ( w, y j ) T ρ j := N T Reach(ρ) ( w, y j ) T η j := N T Reach(η) ( w, y j )Further, for any ā ∈ ([0, 1] d ) |T | let āρ j and āη j be the tuple of elements of ā corresponding to the nodes of T ρ j and T η j respectively. Let:e T π (ā) := WMean T e T ρ 1 ρ (ā ρ 1 ), . . . , e T ρ r ρ (ā ρ r ), e T η 1 η (ā η 1 ), . . . , e T η r η (ā η r ),Take ϵ, θ > 0. Applying the induction hypothesis to the term ρ(ū, v) and to η(ū, v), which have Reach at most ℓ -1, and using the fact that N T (w i ) is finite, there is N such that for all n ≥ N with probability at least 1 -θ, for every y j ∈ N T (w i ) and every (k + 1)-tuple of nodes (ū, v) such that N G ℓ-1 (ū, v) ∼ = (T j , w, y j ) we have that both:e T ρ j ρ (H G (s 1 ), . . . , H G (s |T ρ j | )) -ρ(ū, v) < ϵ and: e T η j η (H G (s 1 ), . . . , H G (s |T η j |)) -η(ū, v) < ϵ Under this event, by equation (□) and the Lipschitzness of WMean T we have:e T π (H G (s 1 ), . . . , H G (s |T | )) -π(ū) < L T ϵ where L T is the Lipschitz constant of WMean T .• Inductive step for the GCN aggregator π = GCN v∈N (ui) ρ.This step is very similar to the previous, where we again use the fact that the value of a local aggregator is determined by the values of the terms it is aggregating in the local neighbourhood. The only difference is that we now have a different Lipschitz function:GCN T (a 1 , . . . , a r ) := r j=1 1 N T (u i ) N T (y j ) a jThe rest of the proof is as before.• Inductive step for global weighted mean π = v ρ ⋆ h(η).Note that ℓ = 0. Let ℓ ′ = max(Reach(ρ), Reach(η)). Take a k-rooted graph (T, w). For any tuple ū and (k + 1)-rooted graph (T ′ , w, y) extending (T, w) let:T ′ (ū) := |{v | N G ℓ ′ (ū, v) ∼ = (T ′ , w, y)}|By the parameterized Weak Local Convergence result, Theorem D.4, for every such T ′ extending there is a relative neighborhood weight q T |T ′ ∈ [0, 1] such that for all ϵ, θ > 0 there is N ∈ N such that for all n ≥ N with probability at least 1 -θ, for every k-tuple ū such that N ℓ (ū) = T we have that:T ′ (ū) n -q T |T ′ < ϵand moreover the relative neighborhood weights sum to one:T ′ ∈Ext(T ) q T |T ′ = 1Consider any (T ′ , w, y) ∈ Ext(T ). In order to define the controller, we need to identify the nodes in the canonical enumeration corresponding to N T ℓ ′ -1 (ū). Let:r T := N T ℓ ′ -1 (ū) Given tuples of R d -vectors ā = (a 1 , . . . , a r T ) and b = (b r T +1 , . . . , b |T ′ | ), let Arrange T ′ (ā, b)be the |T ′ |-tuple of vectors obtained by assigning the a i 's to the nodes in N T ℓ ′ -1 (ū) and the b i 's to the remaining nodes in T ′ , according to the canonical enumeration of T ′ . Define the controller:e T π (ā) := f T π (ā) g T π (ā)where:f T π (ā) := T ′ ∈Ext(T ) E b∼F e T ′ ρ (Arrange T ′ (ā, b)) • h(e T ′ η (Arrange T ′ (ā, b))) • q T |T ′and:g T π (a 1 , . . . , a k ) := T ′ ∈Ext(T ) E b∼F h(e T ′ η (Arrange T ′ (ā, b))) • q T |T ′where in both cases the expectation is taken over b i 's sampled independently from node feature distribution F.Since:e T ′ ρ (a 1 , . . . , a |T ′ | )h(e T ′ η (a 1 , . . . , a |T ′ |)) and:h(e T ′ η (a 1 , . . . , a |T ′ | )) are bounded, and T ′ ∈Ext(T ) q T |T ′ converges, these sums converges absolutely, and hence the controller is well-defined. This completes the definition of the controller. We now present the proof that it is correct. Take ϵ, θ > 0. Take a finite S ⊆ Ext(T ) such that:T ′ ∈S q T |T ′ > 1 -ϵ (⃝)and each q T |T ′ > 0 for T ′ ∈ S.The guarantee given when we applied the parameterized version of Weak Local Convergence, Theorem D.4, is that there is N 1 such that for all n ≥ N 1 with probability at least 1 -θ, for all T ′ ∈ S and every k-tuple ū such that N ℓ (ū) = T we have that:T ′ (ū) n -q T |T ′ < ϵ ( ‡)Define the function:f • π (ā, b) := e T ′ ρ (Arrange T ′ (ā, b)) • h(e T ′ η (Arrange T ′ (ā, b))) and similarly: g • π (ā, b) := h(e T ′ η (Arrange T ′ (ā, b))) Note that these are just the integrands used in f T π (ā) and g T π (ā). Now, for any (k + 1)-tuple of nodes (ū, v) let āū be the tuple of node features of N G ℓ ′ -1 (ū) and b(ū,v) be the tuple of node features of the remaining nodes in N G ℓ ′ (ū, v), ordered as in the canonical enumeration of N G ℓ ′ (ū, v). Note that f • π is bounded, say by Λ. Then for every γ > 0, by Hoeffding's Inequality (Theorem B.4) for any tuple ū such that N ℓ (ū) = T and T ′ ∈ S we have that:P     v N G ℓ ′ (ū,v) ∼ =T ′ f • π (ā ū, b(ū,v) ) -| T ′ (ū) | • E b∼F f • π (ā ū, b) ≥ | T ′ (ū) |γ     ≤ 2 exp - 2 T ′ (ū) γ 2 Λ 2 ≤ 2 exp - 2n(q ′ T -ϵ)γ 2 Λ 2where in the last inequality we use equation ( ‡). Hence, taking a union bound, there is N 2 such that for all n ≥ N 2 with probability at least 1 -θ, for all ū such that N ℓ (ū) = T and T ′ ∈ Ext(T ) we have:v N G ℓ ′ (ū,v) ∼ =T ′ f • π (ā ū, b(ū,v) ) -| T ′ (ū) | • E b∼F f • π (ā ū, b) < | T ′ (ū) |γIf we divide both sides of the inequality through by n, take a γ below 1, and apply equation ( ‡) again, we conclude that there is N 4 such that for all n ≥ N 4 with probability at least 1 -θ, for all ū such that N ℓ (ū) = T and T ′ ∈ Ext(T ) we have:1 n v N G ℓ ′ (ū,v) ∼ =T ′ f • π (ā ū, b(ū,v) ) -q T |T ′ E b∼F f • π (ā ū, b) < ϵ (△ f )Similarly, there is N 5 such that for all n ≥ N 5 with probability at least 1 -θ, for all ū such that N ℓ (ū) = T and T ′ ∈ Ext(T ) we have:1 n v N G ℓ ′ (ū,v) ∼ =T ′ g • π (ā ū, b(ū,v) ) -q T |T ′ E b∼F g • π (ā ū, b) < ϵ (△ g )By the induction hypothesis, there is N 6 such that for all n ≥ N 6 with probability at least 1 -θ, for every T ′ ∈ S and every(k + 1)-tuple of nodes (ū, v) such that N G ℓ ′ (ū, v) ∼ = T ′ we have that both: e T ′ ρ (H G (s 1 ), . . . , H G (s |T ′ | )) -ρ(ū, v) < ϵ ( † ρ )and:e T ′ η (H G (s 1 ), . . . , H G (s |T ′ | )) -η(ū, v) < ϵ ( † η )Let N := max(N 1 , N 2 , N 3 , N 4 , N 5 , N 6 ) and take n ≥ N . Then for such n the probability that these six events happen is at least 1 -6θ. We will condition on this.Take any k-tuple of nodes ū such that N ℓ (ū) = T . It suffices to show, using the definition of the interpretation of the weighted mean operator, that:v ρ(ū, v) h( η(ū, v) ) v h( η(ū, v) ) - f T π (H G (u 1 ), . . . , H G (u k )) g T π (H G (u 1 ), . . . , H G (u k )) < ιfor some ι which we can make arbitrarily small by choosing ϵ small enough.As above it suffices to find ζ, ξ > 0 which we can make arbitrarily small and constants ν, Ω > 0 such that:EQUATIONEquation ( 8), equation ( 9) and equation ( 10) follow as before. We show equation (7) , the proof of equation ( 6) being similar.By equation ( † η ) we have that for every v:h( η(ū, v) ) -g • π (ā ū, b(ū,v) ) < ϵ Hence: 1 n v h( η(ū, v) ) - 1 n v g • π (ā ū, b(ū,v) ) < ϵ Now: 1 n v g • π (ā ū, b(ū,v) ) = 1 n T ′ ∈Ext(T ) v N G ℓ ′ (ū,v) ∼ =T ′ g • π (ā ū, b(ū,v) )Letting Λ be a bound on the norm of g • π (ā ū, b(ū,v) ), by equation (⃝) we have that:1 n v g • π (ā ū, b(ū,v) ) - 1 n T ′ ∈S v N G ℓ ′ (ū,v) ∼ =T ′ g • π (ā ū, b(ū,v) ) < ϵΛBy equation (△ g ) we have that:1 n T ′ ∈S v N G ℓ ′ (ū,v) ∼ =T ′ g • π (ā ū, b(ū,v) ) - 1 n T ′ ∈S q T |T ′ E b∼F g • π (ā ū, b) ≤ ϵFinally, by equation (⃝) again we have that:1 n T ′ ∈S q T |T ′ E b∼F g • π (ā ū, b) -g T π (ā ū) < ϵΛ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 no free variables, and as a subterm of itself has reach 0. The controller e ∅ τ of is a constant z, and hence by the induction hypothesis applied to it, for every ϵ, θ > 0 there is N ∈ N such that for all n ≥ N with probability at least 1 -θ we have that:∥ τ -z∥ < ϵWe now prove the convergence result for the stochastic block model. The proof follows the same structure as the density case in Theorem 5.1, 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(v) ∈ {1, . . . , m} be the community to which v 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 0. Lemma E.1. Let n 1 , . . . , n m : N → N and P be as in Theorem 5.1. Then for every k ∈ N and ϵ, θ > 0 there is N ∈ N such that for all n ≥ N with probability at least 1 -θ, for all nodes v we have that: • We consider 5 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, 3 layers and an output dimension of 5.∥rw k (v)∥ < ϵ• 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, 1] and the initial feature dimension is 128.Further details are available in the experiments repository at https://github.com/ benfinkelshtein/GNN-Asymptotically-Constant.Much like in Section 6, the convergence of class probabilities is apparent across all models and graph distributions, in accordance with our main theorems (Q1). We again observe that attention-based models such as GAT and GPS+RW exhibit delayed convergence and greater standard deviation in comparison to MeanGNN and GCN, which further strengthening our previous conclusions.This research was funded in whole or in part by EPSRC grant EP/T022124/1. For the purpose of Open Access, the authors have applied a CC BY public copyright license to any Author Accepted Manuscript (AAM) version arising from this submission.NeurIPS Paper ChecklistQuestion: 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 3 . 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.• 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 a library function, bootstrap, etc.) • The assumptions made should be given (e.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 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 (e.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. 
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 experiments? 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, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental 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 or 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 https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: we have reviewed the ethics code and are confident that our paper conforms to it. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of 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 of the work performed? Answer: [NA] . Justification: this is a theoretically-oriented paper on convergence properties of graph neural networks. There is no direct path to negative applications. Guidelines:• The answer NA means that there is no 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.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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. • If 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 ML). 
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, or scraped datasets)? Answer: [NA] . Justification: we do not provide new datasets or models in this work. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to usage guidelines or restrictions to access the model or 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 a 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 of the asset is 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 a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators.In the body we reserve x, y, z for free variables and u, v, w for concrete nodes in a graph.The appendix includes additional results for the GCN aggregator.Recall that ψ is the ∧-description on which we condition the tuples ū in the inductive invariant. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

Please find some additional minor remarks below.

* l. 14: ML -> please introduce abbreviation first
* l. 64: what does "import" mean here? (should it be "impact"?)
* l. 127, 132: neighbor vs. neighbour
* l. 137: What is $\mathbf{W}_V$ (in comparison to just $\mathbf{W}$ in GAT)?
* l. 143: dot in sentence (after [12])
* l. 163: What is $k$? The number of nodes?
* l. 165: Consider re-writing this sentence as it is difficult to understand
* Def. 4.3: Missing $G$ subscript?
* l. 233: Sentence seems to be missing something: "Then for every AGG[...] term converges a.a.s. with respect to $(\mu_n)$"
* l. 236: regardless of "the" input graph
* l. 294: "this phenomenon" or "these phenomena"
questions: 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? 
2. 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)?
3. Could you say more about the rate of convergence?
limitations: 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).
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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

- 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

- 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.
questions: 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?

- 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: - *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.


- *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, 
  - What is the difference in the proof techniques between lemma 5.4 in this paper and lemma 4.7 in [a]?
  - If we set the number of classes as 2, then will the convergence results of this paper reduce to the results in [a]?

[a] Adam-Day, S. and Ceylan, I., 2024. Zero-one laws of graph neural networks. Advances in Neural Information Processing Systems, 36.

- 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. 

- Some minors:

  - 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? 
  - Instead of using randomly initialized weights in the experiments, it would be interesting to use learned weights. 
  - Line 130, what is the meaning of “A MEANGNN is one where…”.
questions: questions: Please see the weakness part.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.  
2. The paper discusses an interesting asymptotic behavior of GNNs as classifiers. However, its impact on GNN real applications is not fully discussed. 
3. I do not find a thorough discussion if features are not i.i.d.
questions: questions: 1. Can the authors give an explicit (rigorous) definition of "probabilistic classifier"? 
2. In the discussion of almost sure convergence (3.1), what is $\bar{\mu}$?
3. 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?  
4. For Theorem 5.1, is the almost sure limit a single (deterministic) vector? 
5. 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?
6. 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: limitations: N.A.

Comments: title: Thank you for the positive evaluation
comment: I thank the authors for taking the time to address my concerns.

I still feel that the construction is much too dense and technical for a conference paper, and would greatly benefit from being more pedagogically explained in a longer journal paper. I keep my score as is.
Thank you for going through our rebuttal and for the positive evaluation.
Thank you for going through our rebuttal and for keeping the positive recommendation.
I thank the authors for their response and keep my current score.
I appreciate the author's response. 

I believe that this paper is above the acceptance bar.
We thank the reviewer for going through our rebuttal and recommending acceptance of our work. We will discuss the limitations and potential future directions in the revised version of the paper. We are also grateful that the reviewer closely monitors the discussion period and considers to further raise their score accordingly.
Sorry, this is indeed a typo. To clarify, both 6-nodes in the right-most graph in Fig 3 should be 4-nodes instead.  Thank you for pointing this out. We will revise this accordingly.
Thank you for providing the graphical example in Fig. 3. Could you briefly explain why the degree 1 node (with initial feature $H(x)=-3$) results in $6$, and not $4$?
I would like to thank the authors for the detailed rebuttal. Most of my concerns are sufficiently addressed. There are issues beyond the scope of the paper, which are important in my opinion. I suggest the authors consider discussing them as limitations and potential future directions in the revision. Otherwise, I recommend the paper be accepted. I think my original score is fair, which I will maintain. However, I may raise the score later depending on the responses of the other reviewers.