Zero-One Laws of Graph Neural Networks
Authors: Sam Adam-Day
Theodor-Mihai Iliant
Ismail Ilkan Ceylan
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
graph convolutional networks
zero-one law
expressivity
asymptotic behavior
TL;DR: We prove ‘zero-one laws’ for various classes of graph neural networks as the number of nodes tends to infinity.

Abstract: Graph neural networks (GNNs) are the de facto standard deep learning architectures for machine learning on graphs.  This has led to a large body of work analyzing the capabilities and limitations of these models,  particularly pertaining to their representation and extrapolation capacity.  We offer a novel theoretical perspective on the representation and extrapolation capacity of GNNs, by answering the question: how do GNNs behave as the number of graph nodes become very large? Under mild assumptions, we show that when we draw graphs of increasing size from the Erdős–Rényi model, the probability that such graphs are mapped to a particular output by a class of GNN classifiers tends to either zero or one. This class includes the popular graph convolutional network architecture. The result establishes `zero-one laws' for these GNNs, and analogously to other convergence laws,  entails theoretical limitations on their capacity.  We empirically verify our results, observing that the theoretical asymptotic limits are evident already on relatively small graphs.

Zero-One Laws of Graph Neural Networks
Sam Adam-Day" Department of Mathematics University of Oxford Oxford, UK
Theodor-Mihal Iliant Department Computer Science University of Oxford Oxford, UK
sam wwwaaadaaaaaaaaa ac uk
theodor -istorr-mhhiii.. www.annellll.......... ox ac
Ismail īlkaan Ceylan
Department of Computer Science
University of Oxford Oxford, UK
ismail cewpliiccyylaccccc ox ac.
Abstract
Graph neural networks (GNNs) are the de facto standard deep learning architectures for machine learning on graphs. This has led large body of work analyzing the capabilities and limitations of these models, particularly pertaining to their representation and extrapolation capacity. We offer novel theoretical perspec- tive on the representation and extrapolation capacity of GNNs, by answering the question: how GNNs behave as the number of graph nodes become very large? Under mild assumptions, we show that when we draw graphs of increasing size from the Erdös-Rény model, the probability that such graphs are mapped to a particular output by a class of GNN classifiers tends to either zero or to one. This class includes the popular graph convolutional network architecture. The result establishes zzero-one laws' for these GNNs, and analogously to other convergence laws, entails theoretical limitations on their capacity. We empirically verify our results, observing that the thcoretical asymptotic limits are evident already on relatively small graphs.
Introduction
Graphs are common structures for representing relational data in a wide range of domains, including physical (35), chemical [8). and biological [42 [0] systems, which sparked interest in machine learning over graphs. Graph neural networks (GNNs) 331 [4] have become prominent models for graph machine learning for wide range of tasks, owing to their capacity to explicitly encode desirable relational inductive biases [ One important virtue of these architectures is that every GNN model can be applied arbitrarily large graphs, since in principle the model parameters are independent of the graph size. This raises the question: how do GNNs behave as the number of nodes becomes very large? When acting as binary classifiers, GNNs can be thought as parametrizing Boolean properties of (labelled) graphs. A classical method of specifying such properties is through first-order formulas, which allow for precise definitions using formal language
g The celebrated 'zero-one law' for first-order logic [13 8 provides crisp answer to the question of the asymptotic behaviour of such properties: as graphs of increasing size are drawn from the Erdös- Rényi distribution, the probability that first-order property holds either tends to zero to one.
Alternative email address: me@samadanday.com com
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper. we show an analogous result for binary classification GNNs: under mild assumptions on the model architecture, several GNN architectures including graph convolutional networks [2T] satisfy zero-one law over Erdös-Rényí graphs with random node features. The principal import of this result is that establishes novel upper-bound on the expressive power of GNNs: any property of graphs which can be uniformly expressed by a GNN must obey a zero-one law. An example of simple property which does not asymptotically tend to zero or one is that of having an even number of nodes, Note however that our result, combined with the manifest success of GNNs in practice, suggests that zero-one laws must be abundant in nature: if a property we cared about did not satisfy a zero-one law, none of the GNN architectures we consider would be able to express it.
Our main results flexibly apply both to the case where we consider the GNN as a classifier applied to randomly sampled graphs and node features, and where we consider the random node features as part of the model. For the latter, it known that incorporating randomized features into the model significantly increases its expressive power on graphs with bounded number of nodes 32 1]. Our results yield the first upper bound on the expressive power of these architectures which is uniform in the number of nodes. We complement this with corresponding lower bound, showing that these architectures can universally approximate any property which satisfies a certain zero-one law.
A key strength of the results is that they apply equally well to randomly initialized networks, trained networks. and anything in between. In this sense, our asymptotic analysis is orthogonal to the question of optimization, and holds regardless of the choice of training method. Another interesting aspect of these results is that they unite analysis of expressive power with extrapolation capacity. Our zero-one laws simultaneously provide limits on the ability of GNNs to extrapolate from smaller Erdös-Rényí graphs to larger ones: eventually any GNN must classify all large graphs the same way.
To validate our theoretical findings, we conduct series of experiments; since zero-one laws are of asymptotic nature, we may need to consider very large graphs observe clear empirical evidence for the phenomenon. Surprisingly however, GNNs already exhibit clear evidence of a zero-one law even on small graphs. Importantly, this is true for networks with very few layers (even a single-layer), which is reassuring, as it precludes confounding factors, such as the effect of over-smoothing due to increased number of layers [23]. We provide further experimental results in the appendix of this paper, where all proofs of technical statements can also be found. We make the code for our experiments available on- line at /ttpps::/gttiieii cww Sommmmaaaaaaaay//////aaaaaaaaaaa Zero One-Lawe of Graph- Neural- Weural-Networks
2 Preliminaries
Random graphs and matrices. The focus of our study is on classes of random graphs with random features, for which we introduce some notation. We write E Rd to represent vector, and X E Rdx=" to represent a matrix. Analogously, we write x to denote a random vector, and X to denote a random matrix, whose entries are (real) random variables. We write G(n,r) r) to denote the class of simple, undirected Erdös-Réng Rényi (ER) graphs with n nodes and edge probability r and let (d) denote some distribution of feature vectors over Edd We define an Erdös-Rény Rényi graph equipped with random node features as a pair G = (A, X). where A ~ G(n, r) is the random graph adjacency matrix of the graph G = (V, E) and X E Rdxn is a corresponding random feature matrix, independent of G, which contains, for each node V, an initial random node feature x, ~ (dd) as the corresponding columns of X
Message passing neural networks. The focus of this work is on message-pussing neural networks (MPNNs) [7] which encapsulate the vast majority of GNNs. The fundamental idea in MPNNs is of each node for T E N iterations, based on its own state and the state of its neighbors N(r)) as:
to update the initial (random) state vector x, (0)
(++1) = (0()) (x(0) (1) (x.0) ( (xx1) ((IIIEN(())))
where J denotes a multiset, and (5(() and v6(()) are differentiable combination, and aggregation functions, respectively. Each layer's node representations can have different dimensions: we denote by d(t) the dimension of the node embeddings at iteration and typically write d in place of d0).
We define d X [V| dimensional (random) feature matrix as opposed to the more common [V| x d. This is for ease of presentation, since aim to work on the (random) column vectors of such matrices.

---

The final node representations can then be used for node-level predictions. For graph predictions, the final node embeddings are pooled form a graph embedding vector to predict properties of entire graphs. The pooling often takes the form of simple averaging, summing or component- wise maximum. For Boolean node (resp., graph) classification, we further assume a classifier C : [Rd(T") + IB which acts on the final node representations (resp., on the final graph representation).
There exist more general message passing paradigms [3] such as MPNNs with global readout which additionally aggregate over all node features at every layer, and are known to be more expressive [4] Some model architectures considered in this paper include a global readout component and we consider different choices for the combine (6(*) and aggregate (1)(9) functions, as we introduce next.
GCN. The primary GNN architecture we consider is graph convolutional networks (GCN) [21]
These are instances of MPNNs with self-loops, which aggregate over the extended neighborhood of node (u) (v) U {r}. GCNs iteratively update the node representations as x. (y (t)
where the preactivations are given by:
(
Σ
((-1) + +B(()
( VIN(W))
We apply the linear transformation W!! (dd())x((-1)) to normalized sum of the activations for the previous layers of the neighbors of the node under consideration, together with its own activation. Adding bias term (t) yields the preactivation y!" to which we apply the non-linearity a.
MEANGNN.
We also consider the MEANGNN" architecture which is a self-loop GNN with mean aggregation and global readout 17 and updates the node representation x! a (y! where:
W
Σ
it-1)
+
W
(t)
x (t-1) + (()
(N+(
(E)
WEV
MEANGNN* models additionally apply linear transformation W E (((())x((=1))) the mean of all previous node representations. We refer to MEANGNN the special case of this architecture which does not include global readout term (obtained by dropping the second term the equation).
SUMGNN. Finally, we consider the SUMGNN" architecture which a GNN with sum aggregation and global readout 12 and updates the node representations as x!9 = a y where:
W xx((((1))))) (t-1) W(O
Σ x((-1)
Σ x (t-1) ((9)
(E)(M)
This time, we separate out the contribution from the preactivation of the previous activation for the node itself. This yields three linear transformations W w!(") w(() E (()))x((=-)) The corresponding architecture without the global readout term is called SUMGNN.
Related work
Graph neural networks are flexible models which can be applied to graphs of any size following training. This makes an asymptotic analysis in the size of the input graphs very appealing, since such study could lead to better understanding of the extrapolation capabilities of GNNs, which is widely studied the literature [4]40]]
[0]. Previous studies of the asymptotic behaviour of GNNs have focused convergence to theoretical limit networks 220 and their stability under the perturbation of
large graphs [
Zero-one laws have rich history in first-order logic and random graph theory 13 Being the first of its kind in the graph machine learning literature, our study establishes new links between graph representation learning, probability theory, and logic, while also presenting new and interesting way to analyze the expressive power of GNNs. is well-known that the expressive power of MPNNs is upper bounded by the !ddimensional Weisfeiler Leman graph isomorphism test (I-WI) (39 29 and architectures such as SUMGNN [29] can match this. Barceló al. [ further gives logical characterization for class of MPNNs showing SUMGNN* can capture any

---

function which can be expressed in the logic C², which is an extension of the two-variable fragment of first-order logic with counting quantifiers. Several works study the expressive power of these models under the assummption that there are unique node ideniifiers (26.. or define higher-order GNN models
229 27
28
[9] to obtain more expressive architectures.
Our work has direct implications on GNNs using random node features 12 D. which are universal in the bounded graph domain. Specifically, we derive a zero-one law for GNNs using random node features which puts an upper bound on the expressive power of such models in a uniform sense: what class of functions on graphs can be captured by a single GNN with random node features? Abboud et al. [I] prove universality result for these models, but it is not uniform, since the construction depends on the graph sizes, and yields different model parametrization depending on the choice of the graph sizes. Moreover, the construction of Abboud et al. [I] is of size exponential in the worst case. Grohe 15 recently improved upon this result, by proving that the functions that can be computed by a polynomial-size bounded-depth family of GNNs using random node features are exactly the functions computed by bounded depth Boolean circuits with threshold gates. This establishes upper bound on the power of GNNs with random node features, by requiring the class of models to be of bounded depth (fixed layers) and of size polynomial. However, this result is still not uniform, since it allows the target function to be captured by different model parametrizations. There is no known upper bound for the expressive power of GNNs with random node features in the uniform setting, and our result establishes this.
Other limitations of MPNNs include over-smoothing related to information propagation, and are linked to using more message passing layers. The problem of over-smoothing has also been studied from an asymptotic perspective (23 30], where the idea is to see how the node features evolve as we increase the number of layers in the network. Our study can be seen as orthogonal to this work: we conduct an asymptotic analysis in the size of the graphs rather than in the number of layers.
30 and over-squashing which are
4 Zero-one laws of graph neural networks
4.1 Problem statement
We first define graph invariants following Grohe [16..
Definition 4.1. A graph invariant & is a function over graphs, such that for any pair of graphs G1, G2 and, for any isomorphism f from G1 to G2 holds that ((G) = (G)() Graph invariants for graphs with node features are defined analogously.
Consider any GNN model M used for binary graph classification. It immediate from the definition that M is invariant under isomorphisms of the graphs on which it acts. Hence M,, considered as function from graphs to B = {0, 1}. is a graph invariant. In this paper, we study the asymptotic behavior of M as the number of nodes increases.
One remarkable and influential result from finite model theory is the 'zero-one law' for first-order logic. A (Boolcan) graph invariant & satisfies a zero-ona one law if when we draw graphs G from the ER distribution G(n, r). as n tends to infinity the probability that {(G) = 1 either tends 0 or tends to 1. The result, due to Glebskii et al. [13 and Fagin [), states that any graph invariant which can be expressed by a first-order formula satisfies a zero-one law. Inspired by this asymptotic analysis of first-order properties, we ask whether GNNs satisfy a zero-one law. As the input of a GNN is graph with node features, we need to reformulate the statement of the law to incorporate these features.
Definition 4.2. Let adjacency matrix and, independently, X is matrix of node embeddings, where x. ~ (dd)) for every node v. A graph invariant & for graphs with node features satisfies zero-one law with respect to G(n, r) and (d)) if, as n tends to infinity, the probability that ((G) = 1 tends to either 0 or 1.
(A, be a graph with node features, where A G(n, r) is a graph
Studying the asymptotic behavior of GNNs helps to shed light on their capabilities and limitations. zero-one law establishes limit on the ability of such models to extrapolate to larger graphs: any GNN fitted to a finite set of datapoints will tend towards outputting a constant value on larger and larger graphs drawn from the distribution described above. A zero-one law in this setting also transfers to corresponding zero-one law for GNNs with random features. This establishes an upper-bound on the uniform expressive power of such models.

---

4.2 Graph convolutional networks obey zero-one law
Our main result this subsection is that (Boolean) GCN classifiers obey a zero-one law. To achieve our result, we place some mild conditions on the model and initial node embeddings.
Finst, our study covers sub- Sab-Gaussian random vectors, which in particular include all bounded random vectors, and all multivariate normal random vectors. We note that in every practical setup all node features have bounded values (determined by the bit length of the storage medium), and are thus sub-Gaussian.
random vector x E IRd is sub- Gaussiann if there is > 0 such that for every unit vector y E IR the random variable x y satisfies the sab-Gaussian property; that is, for every > 0:
Definition 4.3.
12
P(xx y t) exxp
(-C=
C2
Second, we require that the non-linearity a be Lipschitz continuous. This is again mild assumption, because all non-linearities used in practice Lipschitz continuous, including ReLUU, clipped ReLU, sigmoid, linearized sigmoid and tanh.
Definition 4.4. A function f: R + R is Lipschitz continuous if there is C such that for any y R it holds that fx() f(v)1 Cl yl.
Third, place condition the GCN weights with respect to the classifier function e: pd(T) B. which intuitively excludes a specific weight configuration.
Definition 4.5. Consider a distribution (d) with mean μ.. Let M be GCN used for binary graph classification. Define the sequence p Hr of vectors inductively by po == l and Hr o "W M + b(t)). The classifier classifier C (Rd(T) B is non-splitting for M the vector μr does not lie on a decision boundary for C.
For reasonable choices of C, the decision boundary has dimension lower than the d(T)) and therefore set of zero-measure. This means that in practice essentially all classifiers are non-splitting.
Given these conditions, we are ready to state our main theorem:
Theorem 4.6. Let M be GCN used for binary graph classification and take [0, 1]. Then, M satisfies a zero-one law with respect to graph distribution ((n, r) and feature distribution ((d)
assuming the following conditions hold: (i) the distribution D(d) is aub-Gaussian, (ii) the linearity a is Lipschitz continuous, (iii) the graph-level representation uses average pooling, and (iv) the classifier C is non-splitting.
The proof hinges on a probabilistic analysis of the preactivations in each layer. We use a sub-Gaussian concentration incquality show that the deviation of each of the first-layer preactivations y!" from its expected value becomes less and less as the number of node n tends to infinity. Using this and the fact that is Lipschitz continuous we show then that each activation x!! tends towards fixed value. Iterating this analysis through all the layers of the network yields the following key lemma, which is the heart of the argument.
Lemma 4.7. Let M and (d) satisfy the conditions in Theorem 4.6 Then, for every layer t, there is zt dRt)(t) such that when sampling graph with node features from G(n,r) and D(d), for every i .l.))..((t)) and for every > O we have that:
Vv:
x
21 ]
<E +1
as nt 00
With the lemma established, the proof of Theorem 4.6 follows straightforwardly from the last two assumptions. Since the final node embeddings (") tend to a fixed value 2r, the average- average-pooled graph-level representations also tend to this. Since assume that the classifier is non-splitting. this value cannot lie on a decision boundary, and thus the final output is asymptotically stable at ((2r).
We expect that the rate of converge will depend in a complex way on the number of layers, the embedding dimensionality, and the choice of non-linearity, which makes a rigorous analysis very challenging. However, considering the manner in which Lemma 4.7 is proved, we can arrive the
5

---

following intuitive argument for why the rate of convergence should decrease as the embedding dimensionality increases: if we fix node v and a layer t then each of the components of its preactivation can be viewed as the weighted sum of d(t - 1) random variables, each of which is the aggregation of activations in the previous layer. Intuitively, as d(t - 1) increases, the variance of this sum also increases. This increased variance propagates through the network, resulting in higher variance for the final node representations and thus a slower convergence.
Using analogous assumptions and techniques to those presented in this section, we also establish a zero-one law for MEANGNN", which we report in detail in Appendix B Abstracting away from technicalities, the overall structure of the proofs for MEANGNN and GCN is very similar, except that for the former case we additionally need to take care of the global readout component.
4.3 Graph neural networks with sum aggregation obey zero-one law
The other variant of GNNs we consider are those with sum aggregation. The proof in the case works rather differently, and we place different conditions on the model.
R + I is eventually constant in both directions if there Jo I such that (yy is constant for y < to and (ty) is constant for y > Zxe. We write -oo denote the minimum and do to denote the maximum value of an eventually constant function d.
Definition 4.8. A function
This means that there is threshold (z_oo) below which sigma is constant, and another threshold (Ioo) above which sigma is constant. Both the linearized sigmoid and clipped ReLU are eventually constant in both directions. Moreover, when working with finite precision any function with vanishing gradient in both directions (such as sigmoid) can be regarded as eventually constant in both directions.
We also place the following condition the weights of the model with respect to the mean of (d) and the adge-probability r.
Definition 4.9. Let M be any SUMGNN* for binary graph classification with a non- non-linearity which is eventually constant in both directions. Let Did) be any distribution with mean μ., and let E [0, 1]. Then, the model M is synchronously saturating for G(n,r) and (dd) if the following conditions hold:
For each 1 isis d(1):
[r n + (
[u]
#0
2. For every layer < t t T, for each 1 sis d(t) and for each = E to- 0o
0o0) ) d((t-));
(r + (( )z), #0
Analysis of our proof of the zero-one law for SUMGNN* models (Theorem 4.10 below) reveals that the asymptotic behaviour is determined by the matrices Q: r + w where the asymptotic final layer embeddings are o ((Qr(a (Qr-1- ( ... or Quft) ... )))) ) To be synchronously saturating is to
avoid the boundary case where one of the intermediate steps in the asymptotic final layer embedding computation has a zero component.
Similarly the case of non-splitting classifier, the class of synchronously saturating models is very wide. Indeed, the space of models which are not synchronously saturating is the union of solution space of each equality (i.e. the negation of an inequality Definition 4.9p. Thus, assuming that μ. a- and doo are non-zero, the space of non-synchronously-sttuuee than the space of all models, and thus has measure zero.
models has lower dimension
With these definitions in place we can now lay out the main result:
Theorem 4.10. Let M be a SUMGNN' model used for binary graph classification and take r E [o. 1]. Then, M satisfies zero-one law with respect to graph distribution G GGn, r) and feature distribution D(d) assuming the following conditions hold: (i) the distribation IDdd) is sub- Gaussian, (ii) the non-linearity is eveniually constant in both directions, (ii) the graph-level representation uses either average or component-wie maximum pooling, and (iv) M is synchronously saturating for G (n, r) and ID (d).

---

The proof works differently than the GCN and MEANGNN" cases, but still rests on probabilistic analysis of the preactivations in each layer. Assuming that M is synchronously saturating for G(,, r) and (d),, we can show that the expected absolute value of each preactivation tends to infinity as the number of nodes increases, and that moreover the probability that it lies below any fixed value tends to O exponentially. Hence, the probability that all node embeddings after the first layer are the same and have components which are all 0-c0 or doo tends to 1. We then extend this analysis to further layers, using the fact that M is synchronously saturating, which yields inductively that all node embeddings are the same with probability lending to 1, resulting in the following key lemma.
Lemma 4.11. Let M, (d) and r be as in Theorem 4.10 Let - and x be the extremal values taken by the non-linearity. Then, for every layer t., there is 2 fo-xx: T )d(t) such that when sample graphs with node features from G(n,r) r) and (dd) the probability that X Zt for every node tends to 1 as n tends to infinity.
The final classification output must therefore be the same asymptotically, since its input consists of node embeddings which always take the same value.
5 Graph neural networks with random node features
Up to this point we have been considering the graph plus node features as the (random) input to GNNs. In this section, we make change in perspective and regard the initial node features as part of the model, so that its input consists solely of the graph without features. We focus in this section on SUMGNN". Adding random initial features to GNNs is known to increase their power 32
Note that Theorem 4.10 immediately yields zero-one law for these models. This places restrictions on what can be expressed by SUMGNN' models with random features subject to the conditions of Theorem 4.10 For example, it not possible express that the number of graph nodes is even, since the property of being even does not satisfy zero-one law with respect to any E [0, 1].
It is natural to wonder how tight these restrictions are: what precisely is the class of functions which can be approximated by these models? Let us first formalize the notion of approximation.
Definition 5.1. Let f be Boolean function on graphs. and let Ç be a random function on graphs. Take 6 > 0. Then & uniformly d-approximates f if:
Vn E N: PP((()) f(G) |G| n) 2 8
when we sample G G(,, 1/2).
The reason for sampling graphs from G(n, 1/2) is that under this distribution all graphs on n nodes are equally likely. Therefore, the requirement is the same as that for every E N the proportion of n-node graphs on which ((G) = f(G) is at least 1- 8.
Building on results due to Abboud et al. [1, we show a partial converse to Theorem 4.10 if graph invariant satisfies a zero-one law for (n,, then it can be universally approximated by a SUMGNN* with random node features.
Theorem 5.2. Let & be any graph invariant which satisfies a zero-one law with respect to G(n, 1/2). Then, for every 8 > 0 there is SUMGNN* with random node features M which uniformly d- approximates g.
The basis of the proof is result due to Abboud et al. [ which states that SUMGNN* with random node features can approximate any graph invariant on graphs of bounded size. When the graph invariant satisfies a zero-one law, we can use the global readout to count the number of nodes. Below a certain threshold, we use the techniques of Abboud et al. ① to approximate the invariant, and above the threshold we follow its asymptotic behavior. We emphasise that the combination of these techniques yields a model which provides an approximation which is uniform across all graph sizes.
Experimental evaluation
We empirically verify our theoretical findings on a carefully designed synthetic experiment using ER graphs with random features. The goal of these experiments is to answer the following questions for each model under consideration:
7

---

Q1. Do we empirically observe zero-one one law?
Q2. What is the rate of convergence like empirically?
Q3. What is the impact of the number of layers on the convergence?
6.1 Experimental setup
We report experiments for GCN, MEANGNN, and SUMGNN. The following setup is carefully designed to eliminate confounding factors:
We consider 10 GNN models of the same architecture each with randomly initialized weights, where each weight is sampled independently from U-),, The non-linearity is eventually constant in both directions: identity between [-1, 1]. and truncated -1 the input is smaller than - and if the input is greater than 1. In the appendix we include additional experiments which test other choices of non-linearity (see Appendix E..)). We apply mean pooling to yield
a final representation Zg E Rd of the input graph.
For every model, we apply final classifier off) Idd + IB where f is a 2-layer MLP with random weights and with tanh activation, which outputs real value, and is the sigmoid function. Graphs are classified as if the output of the sigmoid is greater than 0.5, and 0 otherwise.
The input graphs are drawn from G(n, 1/2) with corresponding node features independently drawn from (0, 1).
We conduct these experiments with three choices of layers: 10 models with T = layer, 10 models with T = layers, and 10 models with T = 3 layers.
The goal of these experiments is to understand the behavior of the respective GNN graph classifiers with mrean-pooinng, we draw larger and larger ER graphs. Specifically, each model classifies graphs of varying sizes, and we are interested in knowing how the proportion of the graphs which are classified 1 evolves, we increase the graph sizes.
We independently sample 10 models to ensure this not a model-specific behavior, aiming to observe the same phenomenon across the models. If there is zero-one law, then for each model, we should only see two types of curves: either tending to or tending to 1, as graph sizes increase. Whether will tend to 0 or 1 depends on the final classifier: since each of these are independent MLPs with random weights the specific outcome is essentially random.
We consider models with up 3 layers to ensure that the node features do not become alike because of the orthogonal over-smoothing issue [24, which surfaces with increasing number of layers. key feature of our theoretical results is that they do not depend on the number of layers, and this is an aspect which we wish validate empirically. Using models with random weights is neutral setup, and random GNNs are widely used in the literature as baseline models [36], as they define valid graph convolutions and tend to perform reasonably well.
6.2 Empirical results
We report all results in Figure for all models considered and discuss them below. Each plot in this figure depicts the curves corresponding to the behavior of independent models with random weights.
GCN. For this experiment, we use an embedding dimensionality of 128 for each GCN model and draw graphs of sizes up 5000, where we take 32 samples of each size. The key insight of Theorem (4.6 is that the final moane embedding vector zg tends to constant vector Applying an MLP followed by sigmoid function will therefore map Zg to either 0 or 1, showing a zero-one law. It is evident from Figure I (top row) that all curves tend to either 0 1, confirming expectation regarding the outcome of these experiments for GCNs. Moreover, this holds regardless of the number of layers considered. Since the convergence occurs quickly, already around graphs of size of 1000, we did not experiment with larger graph sizes in this experiment.
draw larger graphs.
MEANGNN. Given that the key insight behind this result is essentially similar to that of Theorem 4.6 we follow the exact same configuration for these models as for GCNs. The proof structure is the same in both cases: show that the preactivations and activations become closer and closer to
8

---

with 2
GCN with
64
64
Gogg 100s
GUM
2
0.0
6.0
10
107
11
17
10
307
Croff Orohh deakeed 1.00
Orech washh ww
02-
20
120
427
427
127
12
27
Figure 1: Each plot shows the proportion of graphs of certain size which are classified as 1 by a set of GCNs (top row). MEANGNNs (middle), and SUMGNNs (bottom row). Each curve (color-coded) shows the behavior of a model, as we draw increasingly larger graphs. The phenomenon is observed for 1-layer models (left column), 2-layer models (mid column), and 3-layer models (last column). GCNs and MEANGNNs behave very similarly with all models converging quickly to 0 or to 1. SUMGNNs shows slightly slower convergence, but all models perfectly converge in all layers.
some fixed values as the number of nodes increases. Moreover, comparing the summations in the definitions of GCN and MEANGNN, on a typical ER graph drawn from G(n, 1/2) we would expect each corresponding summand have similar value, since (M(u)][((r)) should be close to IW*(() (v)). Figure miid row) illustrates the results for MEANGNN and the trends are reassuringly similar to those of GCNs: all models converge quickly to either 0 and with all choices of layers. Interestingly, the plots for GCN and MEANGNN models are almost identical. We used the same seed when drawing each of the model weights, and the number of parameters is the same between the two. Hence, the GCN models were parameterized with the same values as the MEANGNN models. The fact that each pair of models preforms near identically confirms the expectation that the two architectures work in similar ways on ER graphs.
SUMGNN. Theorem 4.10 shows that, as the number of nodes grow, the embedding vector z, of each node will converge to constant vector with high probability. Hence, when we do mean-pooling at the end, we expect to get the same vector for different graphs of the same size. The mechanism by which zero-one law is arrived at is quite different compared with the GCN and MEANGNN case. In particular, in order for the embedding vectors to begin to converge, there must be sufficiently many nodes so that the preactivations surpass the thresholds use smaller embedding dimensionality of 64 for each SUMGNN model and draw graphs of sizes up to 100000, where we take 32 samples of each size. Figure] T shows the results for SUMGNN, Note that we observe slower convergence than with GCN or MEANGNN.
the non-linearity. For this experiment, we

---

7 Limitations, discussion, and outlook
The principal limitations of our work come from the assumptions placed the main theorems. In our formal analysis, we focus on graphs drawn from the ER distribution. From the perspective of characterizing the expressiveness of GNNs this unproblematic, and accords with the classical analysis of first-order properties of graphs. However, when considering the extrapolation capacity of GNNs, other choices of distributions may be more realistic. In Appendices E.4 and B.3 experiments in which zero-one laws are observed empirically for sparse ER graphs and Barabási- Albert graphs [3), suggesting that formal results may be obtainable. While we empirically observe that GNNs converge to their asymptotic behaviour very quickly, we leave it as future work to rigorously examine the rate at which this convergence occurs.
we report
In this work we show that GNNs with random features can at most capture properties which follow a zero-one law. We complement this with almost matching lower bound: Theorem 5.. currently c.rurenyyy requires a graph invariant & which obeys zero-one law with respect to a specific value of r (i.e., 1/2), and if this assumption could be relaxed, it would yield complete characterization of the expressive power of these models.
8 Acknowledgments
We would like to thank the anonymous reviewers for their feedback, which lead several improve- ments in the presentation of the paper. The first author was supported by an EPSRC studentship with project reference 2271793.
References
[1] Ralph Abboud, ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI, pages 2112-211 22182118, 2021.
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In Proceedings the Ninth International Conference Learning Representations, ICLR, 2021.
[3] Álbert-LászIó Barabási and Réka Albert. Emergence of scaling random networks. Science, 286(5439) 1999.
[4] Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In Proceedings of the Eighth International Conference on Learning Representations, ICLR, 2020.
[5] Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez- Zznzzlzz, Vinicius Zam- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song. Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, 2018.
[6] Béla Bollobás. Random Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, second edition, 2001.
[7] David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguire Rafael Gómez-Bombarelli, Timothy Hirzel, Alán Aspuru- Aspuru-Guzik, and Ryan P. Adams, Convolutional networks on graphs for learning molecular fingerprints. In Proceedings of the Twenty-Eighh Annual Conference on Advances in Neural Information Processing Systems, NIPS, pages
2015.
[8] Ronald Fagin. Probabilities on finite models. The Journal of Symbolic Logic, JSL, 41(1):50-58 1976. ISSN 00224812.
[9] Peter A. Flach. First-order logic. In Claude Sammut and Geoffrey I. Webb, editors, Encyclopedia of Machine Learning, pages 410- Springer US, Boston, MA, 2010. ISBN 978-0338--30164 8. doi: 10. 10.100779788-0-88--011444
10

---

[10] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Proceedings of the Thirtieth Annual Conference on Advances in Neural Information Processing Systems, NIPS, pages 6530-6539, 2017.
[11] Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IRE Transactions on Audio, 68:5680-5695, 2020. ISSN 1053-587X.
[12] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the Thirty-Fourth International Conference on Machine Learning, ICML, pages 1263- 1272, 2017.
[13] Yu V Glebskii, DI Kogan, MI Liogonkii, and VA Talanov. Volume and fraction of satisfiability of formulas of the lower predicate caleulus. Kibernetika, 2:17-27, 1969.
[14] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings of the 2005 IEEE International Joint Conference on Neural Networks, IJCNN, volume pages 729-734, 2005.
[15] M. Grohe. The descriptive complexity of graph neural networks. In 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pages 1-14, Los Alamitos, CA, USA, jun 2023. IEEE Computer Society. doi: 10. (U000ILCC55633622221111113
[16] Martin Grohe. The logic of graph neural networks. Proceedings the 36th Annual ACM/IEEE Symposium Logic in Computer Science, LICS, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781665448956.
[17] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the Thirty- firrt--Fisttti Annual Conference on Advances in Neural Informa- tion Processing Systems, NIPS Curran Associates, Inc., 2017.
[18] Steven M. Kearnes, Kevin McCloskey, Mare Berdll, Vijay S. Pande, and Patrick Riley. Molecu- lar graph convolutions: moving beyond fingerprints. Journal of Computer Aided Molecular Design, 30(8):595-600 2016.
[19] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Proceedings of the Thirty-Second Annual Conference on Advances in Neural Information Processing Systems, NeurIPS, pages 7090-7099, 2019.
[20] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolu- tional networks on large random graphs. In Proceedings of the Thirty-Fourtt Annual Conference on Advances in Neural Information Processing Systems, NeurIPS, pages 21512-21523. Curran Associates, Inc., 2020.
[21] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the Fifth International Conference on Learning Representations, ICLR, 2017.
[22] Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22(1), 2021. ISSN 1532-4435.
[23] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI, pages 3538-3545, 2018
[24] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In Proceedings of the Fourth International Conference on Learning Representations, ICLR, 2016.
[25] Leonid Libkin. Zero-One Laws, pages 235-248. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. ISBN 178-3-662-077003-1
[26] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In Proceedings of the Eighth International Conference Learning Representations, ICLR, 2020.
11

---

[27] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Proceedings the Thirty-Second Annual Conference on Advances in Neural Information Processing Systems, NeurIPS, pages 2153-2164, 2019.
[28] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Proceedings of the Thirty-Sixth International Conference on Machine Learning, ICML, pages 4363-432 4371, 2019.
[29] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the Thirty-Thirl AAAI Conference on Artificial Intelligence, AAAI, pages 4602-4609, 2019.
[30] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In Proceedings of the Eighth International Conference on Learning Representations, ICLR, 2020.
[31] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transfer- ability of graph neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Proceedings of the Thirty-Fourth Annual Conference on Advances in Neural Information Processing Systems, NeurlPS, pages 1702-1712. Curran Associates, Inc., 2020.
[32] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference Data Mining, SDM, pages 333-341, 2021.
[33] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
[34] Saharon Shelah and Joel Spencer. Zero-one laws for sparse random graphs. Journal of the American Mathematical Society, 1(1):97-115, 1988. ISSN 08940347, 10886834.
[35] Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2021.
[36] Rylee Thompson, Boris Knyazev, Elahe Ghalebi, Jungtaek Kim, and Graham W. Taylor. On evaluation metrics for graph generative models. In Proceedings of the Tenth International Conference on Learning Representations, ICLR, 2022.
[37] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of the Sixth International Conference on Learning Representations, ICLR, 2018.
[38] Roman Vershynin. High-dimensional probability. Number 47 in Cambridge series on statis- tical and probabilistic mathematics. Cambridge University Press, Cambridge, 2018 ISBN 9781 1 108415194.
[39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? In Proceedings of the Seventh Annual Conference on Learning Representations, ICLR, 2019.
[40] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In Proceedings of the Ninth International Conference on Learning Representations, ICLR, 2021.
[41] Gilad Yehudai, Ethan Fetaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, ICMI., 2020.
[42] Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13):1457-i46 2018.
12

---

A Proof of the zero-one law for GCN
The proof of Lemma 4.7 and subsequently Theorem 4.6 relies on an asymptotic analysis of the distributions of the node embeddings at each layer. The following famous concentration inequality for sub-Gaussian random variables allows us to put bounds on the deviation of sum of random variables from its expected value.
Theorem A.1 (Hoeffding Inequality for sub-Gaussian random variables). There is a universal constant such that the following holds. Let zi....,. Zn be independent nab-Gaussian scalar random variables with mean Assume that the constants C' from Definition 4.3 for each Z₁ can be bounded by K. Then for all 0:
N
ct
P
Σ 2=1
Zi
2
1
exp
K2N
Proof. See Theorem 2.6.2
38
We also make of the following three basic facts about sub- Gaussian random variables.
Lemma A.2. If is a sub-Ga Gabssiann random vector and is any vector of the same dimension then q is sub-Suussee Gaussian.
Proof. This follows directly from Definition
Lemma A.3. If z is a sub- Sub-Gaussian scalar random variable then so is z - E[zz]
Proof. See Lemma 2.6.8 in
38
Lemma A.4. If is Sahussasi scalar random variable and is an independent Bernoulli random variable then za is sub- Gaussian.
Proof. Let C be the constant given by Definition 4.3 for z. Let take values a and B. Using the Law of Total Probability:
P[[za| 2 = P(|za] 2 t P(a== F(|aa > a P(a 3)
= P[(z 2 t/(aa)) P((= P(z) ((a 3)
12
(
12
< 2exp
- |a|c22
P(a = a) + 2cxp
P(a = B)
t²
< 2
max{[al,
Therefore za nab-Gaussian.
We first prove the key lemma regarding the node embeddings.
Proof of Lemma 4.7 Let C' be the Lipschitz constant for a. Start by considering the first layer
preactivations y and drop superscript (1)'s for notational clarity. We have that:
ye
Σ
W x
(0) +
(EN VIV())IV((
Fix i (I...., d(1)). The deviation from the expected value in the ith component is as follows:
- - (EN+(() VIN(O))IN(u))
W (0)
Wn x (0) 1],
Now every [w(x) is sum of n independent 0-1 Bernoulli random variables with success probability r (since the graph sampled from an Rényi distribution). Since Bernoulli random variables are sub- Gaussian (Lemma A.4) can Hoeffding's Inequality to bound the deviation of [ (w)
13

---

[w) + from its expected value nr + 1. By Theorem A.1 there is constant K such that for every
7 E (0, 1) and node u:
P(IN* S yrr) P(Il nrl 2 (1 7)rr)
s (()) nrl 2 (1 - 7/r 1)
K((1 - 2)mr 1)2
s 2xxp
n
This means that, taking a union bound:
Ko((1 - 7)ur 1)2
P(vu E V: (W) 2 (ar) 2 1- exp
n2
Fix (l,..... d(1)). the case where Vu E V: (W+(u)] 2 your we have that:
lly Eyyolll
W Wn (0)
E
W
00)
v VW(w)) ye
(e)
(0)
Now, by Lemma A.2 and Lemma A.3 each W Xu
is sub-Gaussian. We can thus apply Hoeffding's Inequality (Theorem A.1 to obtain constant K such that for every t 0 have:
nx
P(lx. - EEy 2 SP
Σ
x E W Wix
2 IV (W(()Tr
MEN-(w) (w)
Kt KutWW()))nr
< eexp
W (v)
Kft
< 2exp
Now using the Law of Total Probability, partitioning depending on whether Vu E V: IW+ (w)l 2 ynr, we get bound as follows:
Ktyyn
Ko((1- ( 7)r 1)2
P(ly Elyollal 2 20 2 exp
2n exp
2
From now on fix any 7 E (0,
Let 2 := o (E(y,)) ,) for any v (this is the same for every v). Applying the bound with t = Ce we can bound the deviation of x,, from 2 as follows, using the Lipschitz constant C.
P([|x. 2 2 <) P(((o(y,.) (E(y,))) 2 c)
P(lly. E[y.]ki Cc)
KC222mm
Ko((1 7) 1)) -1)2
2xxp
2n exp
2
21]e < for every node and every i Taking union bound, the probability that [[x, (I...., d(1)} is at least:
1 ri((i) P[[[x, 21|1 2 e)
This tends to tends to infinity, which yields the result for the first layer.
Now consider the preactivations for the second layer:
y(22
Σ
(2)) + (2))
(E) VIN(O))(N(W))
As in the single layer case, we can bound the probability that any [W(u) is less than some ynr. Condition the event that Yu V: [W+(w) 2 ynr.
14

---

By applying the result for the first layer to e' = /VTT/ 1 we have that for each i E (I....,d(2)) d(2)):
P
(Vo:
x 21,,1 <c) +1 00
Condition additionally the event that l(x! (1) 21jil e' for every node and every i (1....,(( d(1)).
Now define:
W " 21 + b(2)
02
VIN(o]IA(()) EEN+ (v)
Then have that for every i E (I....,((1))
liy! azlils
W (2 (x. 21)
((N(w)]W((t)
(ENT(())
Σ
wx (0)0))=11 -21)]
/WW())lm mer
(EN+(()
W
Σ
(1) 21
(w mm
uEN+(u)
el)+(v)
2C /CV/M(0)]
e(n 11)
2Cn
Now let 22 == (a2). As in the single-layer case we can use the bound on I[y! (2) a2]s/ and the fact
that a is Lipschitz to find that, for every node and i E {I,...,,ll d(2)):
||x!?
22]il < 6
Since the probability that the two events on which we conditioned tends to 1, the result follows for the second layer.
Finally, we apply the argument inductively through the layers to obtain the ultimate result.
With the key lemma established we can prove the main result.
Proof of Theorem 4.6 By Lemma 4.7 the final node embeddings xT() deviate less and less from žy as the number of nodes increases. Therefore, the average-poole graph-level representation also deviates less and less from ør. By inspecting the proof, we can see that this zr is exactly the vector prr in the definition of non-splitting (Definition 4.5). This means that cannot lie on decision boundary for the classifier C. Hence, there is e > such that C is constant on:
{o (T) Vi (l,....d(T)} [2] æ) c)
Therefore, the probability that the output of M is ((zr) tends to tends to infinity.
B Proof of the zero-one law for MEANGNN
Let us turn now to establishing a zero-one law for GNNs using mean aggregation. We place the same conditions as with Theorem 4.6 This time the notion of "non-splitting" is as follows.
Definition B.1. Consider a distribution (d) with mean μ. Let M be a MEANGNN* used for binary graph classification. Define the sequence po...., pr of vectors inductively by po == μ and μ4 == ((W!!) + ( 1 + b(9). The classifier C RRT(T) - non-splitting for M the vector fr does not lie decision boundary for C.
15

---

Again, in practice essentially all classifiers are non non-splitting.
Theorem B.2. Let M be MEANGNN"
for used for binary graph classification and take E [o, 11.
Then, M satisfies zero-one law with respect graph distribution G G(,,"" r) and feature distribution D(d) assuming the following conditions hold: (i) the distribution ((d) is sub- Gaussian, (ii) the non-linearity Lipschitz continuous, (iii) the graph-level representation uses average pooling, (iv) the classifier C is non-splitting.
Note that the result immediately applies to the MEANGNN architecture, since it a special case of MEANGNN".
The overall structure of the proof is the same as for GCN, In particular, we prove the following key lemma stating that all node embeddings tend to fixed values.
Lemma B.3. Let M and (D)d) satisfy the conditions in Theorem B.2 Then, for every layer t, there is Z, E (Rd(() such when sampling a graph with node features from G(n, r) and ((d), for every i ((()) and for every >> O we have that:
Vv:
(")
=1
<C) <<)
-1
as 22 - 00
We are ready to present the proof' the statements. The proof of the key lemma works in a similar way to the GCN case.
Let C' be the Lipschitz constant for a. Start by considering the first layer preactivations y and drop superseript (1)'s for notational for clarity. We have that:
Proof of Lemmal B.3
y. [+(v) Wn
E
x +
W. Σ 0 +
(E)+(w)
WEV
Fix i (1,...,, d(1)). We can bound the deviation from the expected value follows:
[y, Ily.-Blyolle5
Σ
W (
W.
Σ
W W.xx!
E
W Wnx (0)
[W)
m
(E)
By Lemma
A.2 and Lemma A.3 both each Ww,x(' (0)
E
W (0)
and each
W. x
W are sub- Gaussian. We can therefore apply Hoeffding's Inequal-
ity to their sums. First, by Theorem A.I there is constant Kg such that for any >
P
W W.x (0) - E W 0
[],
< =
Σ uEV
W.
x (0) - E Wax x [0]]
S In
71
ueV
Kgl2n²
< 2 2exp
n (-Kgtn)
2 exp
Second, applying Theorem A.
aaaain there is constant K,, such that for any >> 0:
P
Σ
W Wax
E
Wn (0) 11, 51
W
[+
uEN+(w)
=P
Σ (EA+(())
W Wn
(0)
E
W W.x(")) [0)]
seN+(1))
K2 KntP(N(())
< 2exp
16

---

Now [w) is the sum of n independent 0-1 Bernoulli random variables with success probability Hence, as in the proof of Lemma 4.7 by Hoeffding's ' Inequality (Theorem A.I there is a constant
Ko such that for every y E (0, 1):
(-
Ko((1 - 7) 1)2
P(I (+) 2 ynr) S 2
n
We can then use the Law of Total Probability, partitioning on whether | (v) 2nn, to get a bound as follows:
P
Σ
(Wix!")
E
W wixx((1))
56
[W+(w)]
(E)++(")
Knt (ntrr)))))
Ko((1- - -2)r 1)²
2eep
2exp
n
71
From now on fix any 7 E (0.
Finally let ž == (Bly))) for any v (this is the same for every v). Applying the two bounds with
1 Cef2 we bound the deviation of x,, from 21 as follows, using the Lipschitz constant C.
P([ 21]1|
(x) oBEy c)
- P(Ily. - Ely.Jld Cc)
P
W (w) EmeN+(o)
W n. (0) -
W
x
Ct 1
(w)
2
+
Σvev W W
W
5
2
Ku(Ceer)Pu
exx
2
Koll Kolll-3)am-11
$ +2exp
(Kg (Ge)3n
+2
Taking union bound, the probability that [[x, - -21ld < for every node v and every i (l....,d(1)) is at least:
1 1 -dn(()) P((xx) - zi1i 2
This tends to as tends to infinity.
Let turn to the second layer. By applying the above result for the first layer to d' loc we have that for each ((2)):
c/(C max w lloo); w
P Ve: [x 21],1
as n + 0o
Condition on the event that
|[x(") (1)
21]i| < é for every node & and every E d(I)).
Fix and consider the second-layer preactivations:
(2)
(2)
Σ
x
+
- W (2)
Σ x
+b(2)
(+
VEN+(() (v)
NEV
Define:
02 [+(1] (
Σ
2( Σ + (())
nEA+(w)
uEV
Fix i E (1...., d()).. Then:
(2 azls =
1
(2
(x(1) 211 + (2)
Σ (x(1)
(1) - =1)
[+(w]l
n
n
wEN-(u) (v)
WEV
1
(2
Σ
x(()
1 +
w
Σ
x( 21
N (v)
72
WEV-(v)
NEV
C
17

---

Let = o(a)). Then we can use the Lipschitz continuity of a to bound the deviation of the activation from 22 as follows.
[x =2|1 loly.") -o())) sc| -azls azls Se
tends to 1, we get that the probability that ![x!?) 22|il < for every node and every (l...., d(2)) also tends to 1.
Since the probability that |[x!
- =11/l < for every node and every i E
Finally apply the above argument inductively through all layers get the desired result.
The proof of the main result now proceeds as in the proof of Theorem 4.6
Proof of Theorem B.2 as the number of nodes n increases. Therefore, the average-pooles graph-level representation also deviates less an less from 2y- By inspecting the proof,
By Lemma B.3 the final node embeddings x," deviate less and less from žr
that this 2r is exactly the vector in the definition of non-splitting (Definition B.I). This means that zT cannot lie on a decision boundary for the classifier C. Hence, there is such that C is constant
{a (R)(T) Vi (.....d(T))= [2T - æ). < c
Therefore, the probability that the output of is ((=T) tends to tends to infinity,
C Proof of the zero-one law for SUMGNN
The proof of the key lemma works rather differently to the GCN and MEANGNN case, but we still make important use of Hoeffding's Inequality.
Consider the first layer preactivations y!)) and drop superscript (1)'s for notational clarity. We rearrange the expression follows:
Proof of Lemma 4.77
Yu (W + Wyxx + (W, + Wg)
Σ
+ W
Σ
x +
uEN(()
uEV W
For u, & define:
Wu, (Auv W. Wg)x uso (W, W x 1
Using this, we can rewrite:
Yo Wa,
By assumption the distribution from which we draw graphs with node features, the Wa,n 's are independent for any fixed v.
Now fix i E {l.....d d(1)}. By Lemma A.2 and Lemma A.4 we have that each [Wa,]]e is sub- Gaussian. We therefore apply Hoeffding's Inequality the sum Note that Wa,v can have one of two Suub-Gaussian) distributions, depending on whether = v. Therefore, by Theorem A. and Lemma A.3 there are constants e and K such that, no matter how many nodes n there are, we have that:
(-
ct2
PP([y=]: Ely.lil f) = Σ ([w...) B[wu,olk) 2 2exp
K2n
Let's now compute Ely,). by first computing [W,.)) When u = vo we have that:
E [ew ([W,, W (0)
(W, W,) E[x (0)
(W, W 1
18

---

When u # v we have, using the independence of Aur and x,:
E [[Wa,u] [E([Au Wn + Wg)x (EE W. + W(x
=(rW, + W
Therefore (separating Wa,0 from Wa.u for u + v):
Bly.] = Σ
+b= -b= W) + W + (W, + w
Since M is synchronously saturating for G and D(d), we know that [r + W g)): + 0. Assume without loss of generality that [(rW, + W, W))pk O. Then the expected value of [yr]: increases tends to infinity; moreover we have bound on how much [y.]s can vary around its expected value.
Recall that the non-linearity a is eventually constant in both directions. In particular, it is constant with value dx above some Teo- When Ey l > Zoo the probability that yyll doesn't surpass this threshold is:
P((yo)s <x)) P([[y]] Elyeldl 1 - Ely okl)
2exp
K2n
There is constant p such that |0:00 - E[yolil 2 pn. Hence for sufficiently large (i.e. such that Elyo]: >> Too): P[y xoo) S exp
cgpn2 K2n (-R²m 2 exp
(- (-cr"
cpp K2
Since the activation [x,]: o.).).)), the probability that [x.]i takes value doo is at least 1 the activation [x,]i is either
2 exp (-cp²n// K Now, for each node and each i Jo with high probability or a-oe with high probability. By taking union bound, for sufficiently large the probability that every [x,]i takes its corresponding value is at least:
cp'n
- 2nd(1) exp
(
K2 --K2
This tends to 1 as n tends to infinity. In other words, there is 21 E oz dd1)) such that x (1) 21 for every asymptotically.
We now proceed to the second layer, and condition on the event that x = 21 for every v. this case, we have that the second layer preactivation for node v is as follows.
(2) (w (2) + (W(z) ( + ml)()) 2z + b
Since we're in the situation where every X 21 the degree [W(v) is simply binomially distributed Bin(n, r). The preactivation y!22) then has expected value:
Eyy n(( w
( 21 + (2)
Fix E [l.....d(()),, Since M is synchronously saturating for G(n, r) and (dd), we have that [r (2) 2114 # Assume without loss of generality that [(rw:[3) w 2=1] Then Ely: (2) tends to infinity as n increases.
view ( (2) + w )21] the sum of n Bernoulli random variables (which take values [(w:?) + 2)))) 121k and [W] (2) 21ke). Since by Lemma A.4 Bernoulli random apply Hoeffding" Inequality to bound the probability that [y less than Txc. We get that, sufficiently large n, there is constant K such that this probability is bounded by 2 eexp (KK)).
Furthermore,
variables are sub- mub-Gaussian, in the first-layer case
19

---

Then, as before, we find 22 E fo- ) such that, for sufficiently large every x 22 with probability at least 2nd exp (-Kn).
Finally, this argument is applied inductively through all layers. As the number of layers remains constant (since M is fixed), we find that the node embeddinggs throughout the model are asymptotically constant.
With the key lemma in place, we can now prove the main theorem.
Proof of Theorem 4.10 Applying Lemma 4.11 the final layer, we find zт E {o-oo: Joo }d(T) such that every X = 2T with probability tending to 1. Since we use either average or component-wise maximum pooling, then means that the final graph-level representation is asymptotically constant, and thus the output of the classifier must be asymptotically constant.
D Proof of the uniform expressive power of SUMGNN" with random features
We make use result due Abboud al. M which shows that SUMGNN* models with random features can approximate any graph invariant on graphs with fixed number of nodes.
Definition D.1. Let be a function on graphs, and let be a random function on graphs. Take d and N E N. Then Ç ò d-approximates up N if:
Vn S N: PP((G) = S(G) |G| = n) 2
For completeness, we state the definition of the linearized sigmoid here. Definition D.2. The lineurized sigmoid is the function - defined as follows:
1 if x (-00- -1), if 11,
otherwise.
Theorem D.3. Let &, be any graph invariant. For every N N and 0 there is a SUMGNN" with random features M which 8-approximates & up to N. Moreover, M uses the linearized sigmoid as the non- con-linearity and the distribution of the initial node embeddings consists of d iid U 1] random variables.
Proof. See 1 Theorem 1].
With this result we can now prove the uniform expressivity result.
Proof of Theorem 5.2 First, & satisfies a zero-one law for G(n, 1/2). Without loss of generality assume that E is asymptotically There is N e N such that for every n > we have:
P(g(G) = 1 G ~ G(n, 1/2)) 2 1
Note that this N depends on both & and 6. Second, by Theorem D.3 there is SUMGNN' with random features M which 5-approximates up to N. Moreover, M' uses the linearized sigmoid the non-linearity and the distribution of the initial node embeddings consists of iid U|0 1] random variables.
Using the global readout and the linearized sigmoid, can condition the model behavior on the number of nodes. We give rough description of the model as follows. Define a SUMGNN* with random features M by extending M' as follows.
Increase the number of layers least three.
Increase each embedding dimension by 1. For convenience call this the Oth component of each embedding.
Use the bias term in the first layer to ensure that the 0th component of the activation x(!) for each node is 1.
20

---

Use the global readout to threshold the number of nodes on N. The Oth row of the matrix w should have a in the Oth position and 0's elsewhere. The Oth component the bias vector ((2) should be 2N 1. This ensures that the Oth component of every activation x is 1 n N and - otherwise.
Propagate this value through the Oth component of each layer embedding.
In the final layer, use this value decide whether to output what M' would output, or simply to output 1.
For any n S N the model M behaves like M' Therefore:
P(E(G) = MMG) |G] - n) 2 1
On the other hand, for n > N the model M simply outputs and so:
P(g(G) = MM() |G] = n) P(E(G) |G| n) 2 - Thus M uniformly 6-approximates ç.
E Further Experiments
In this section, focus on GCNs and provide further experiments regarding our results. In partieular, we pose the following questions:
Our theoretical results entail zero-one law for large class of distributions: do empirically observe zero-one law when node features are instead drawn from a normal distribution (Appendix ?
2. Our theoretical results state zero-one law for a large class of non-linearities: do empirically observe a zero-one law when considering other common non-linearities (Appendix E.2
Does zero-one law also manifest itself empirically for GAT models (Appendix E.3
4. Do we empirically observe zero-one law if we were to consider sparse Erdös Rényi graphs (Appendix E.4)?
())4)
5. Is there empirical evidence for our results apply to other random graph models, such the Cerabási-Alberr model (Appendix E.5
E.1 Experiments with initial node features drawn from normal distribution
Figure 2: Normally distributed random node features with GCN models. Each plot shows the proportion of graphs of certain size which are classified as by a of ten GCN models. Each curve (color-coded) shows the behavior of model, as we draw increasingly larger graphs. The phenomenon observed for l-layer models (left column). 2-layer models (mid column). and 3-layer models (last column). We draw the initial features randomly from normal distribution with mean 0.5 and standard deviation
Here we consider using normal distribution to draw our initial node features, Note that normal distributions are sub-Ga Sabb-aussiin, and hence our theoretical findings (Theorem (.66) confer zero-one law in this case. Figure 2 demonstrates the results for GCN models. We observe the expected asymptotic behavior most cases, however the two and three layer cases a few models have not converged by the end of the experiment.
21

---

E.2 Experiments with other non-linearities
In this subsection we test the effect of using different non-linearities in the layers of our GCN models. Theorem 4.6 applies in all of these cases, so do expect see zero-one law. Figures to present the results for ReLUU, tanh and sigmoid, respectively. We see the expected behavior in all cases. Note however that, in contrast with other non-linearities, when that the rate of convergence actually increases as the number of layers increases. This suggests a complex relationship between the rate of convergence, the non-linearity and the number of layers.
sigmoid observe
17
17
127
Figure 3: GCN models with ReLU non-linearity. Each plot shows the proportion of graphs of certain size which classified by set of ten GCN models. Each curve (color-coded) shows the behavior of model, as we draw increasingly larger graphs. The phenomenon is observed for 1-layer models (left column). 2-layer models (mid column), and 3-layer models (last column). This time choose the ReLUU activation function for the GNN layers. Apart from this, the setup is the same as in the main body of the paper.
503 vot 1
S0N with T
Gch/wes
Figure 4: GCN models with tanh non-linearity. Each plot shows the proportion of graphs of certain size which are classified as by set of ten GCN models. Each curve (color-coded) shows the behavior of model, we draw increasingly larger graphs. The phenomenon is observed for I-layer models (left column), 2-layer models (mid column), and 3-layer models (last column). We use tanh as an activation function for the GNN layers, and keep everything else the same.
53M with T
123 Tw
Figure 5: GCN models with sigmoid non-linearity. Each plot shows the proportion of graphs of certain size which are classified as 1 by set of ten GCN models. Each curve (color-coded) shows the behavior of a model, as we draw increasingly larger graphs. The phenomenon is observed for lllayer models (left column), 2-layer models (mid column), and 3-layer models (last column). We use the sigmoid activation function for the GNN layers, and keep everything else the same.
22

---

E.3 Experiments with GAT
Here we investigate the asymptotic behaviour of GNN architecture considered in the main body: the Graph Attention Network [37]. Cast as an MPNN, this architecture uses attention mechanism as the aggregate function the message passing step. The techniques used in this paper establish zero-one law for other GNN architectures do not easily extend to GAT. However, our experiments demonstrate very quick convergence to
#017
W117
Figure 6: Ten GAT models with number of layers 1, 2 and 3 are run graphs of increasing size, with the proportion of nodes classified as recorded. observe a convergence to zero-one law very quickly.
E.4 Experiments sparse Erdós-Rényi graphs
In these experiments, we consider GCN models on a variation of the Frdös-Rényí distribution in which the edge probability is allowed to vary function of n. Specifically, we set log(n)/ /,, which yields sparser graphs than in the standard distribution. Our experiments provide evidence for zero-one law also in this case (Figure
Sos
Figure 7: Sparse Erdös-Rényi graphs with GCN models. Each plot shows the proportion of graphs of certain size which classified as 1 by the behavior of a model, as we draw increasingly larger graphs. The phenomenon is observed for 1-layer models (left column), 2-layer models (mid column), and 3-layer models (last column). We let the probability r of an edge appearing be log(n) All the other parameters are the same as in the experiments of the main body of the paper.
GCN models. Each curve (color-coded) shows
E.5 Experiments on the Barabási-Albert random graph model
In this subsection, we consider another alternative graph distribution: the Barabási-Albes model [3] This model aims to better capture the degree distributions commonly found in real-world networks. can again observe a zero-one law for GCN models under this distribution (Figure S
23

---

17
Figure 8: Barabási-Albert graphs with GCN models. Each plot shows the proportion of graphs of certain size which classified as 1 by set of ten GCN models. Each curve (color-coded) shows the behavior of a model, as we draw increasingly larger graphs. The phenomenon is observed for l-layer models (left column), 2-layer models (mid column), and 3-layer models (last column). We generate the graphs using the Barabási-A model; apart from this the setup is the main as in the experiments in the main body of the paper.
24


Reviews:
[{"review_id": "OUHMDB6S9s", "reviewer": "Reviewer_BoTS", "summary": "\nThis paper proves that for Erdos-Renyi random graphs, the hidden representations of nodes for GNNs, as well as the graph-level representation, will converge to a constant. In Theorem 4.6, which is the main result for GCN and binary graph classification, they prove that the binary output is always zero or one (the zero-one law). This means that the classifier will eventually become trivial. Its proof is based on Lemma 4.7, which shows the concentration of hidden representations on nodes. They then extend their theory in Theorem 4.10 to SumGNNs and show (in Theorem 5.2) that indeed zero-one laws imply uniform approximation by SumGNNs, which can be thought of as a converse to their zero-one law results. The paper is concluded with supporting experiments.\n\n", "questions": "\n\nI believe this is an interesting result. But unfortunately, it is far from practical models for GNNs. Here I list my comments:\n\n\n\n\nMajor comments:\n\n\n\n(0) One major problem regarding the writing of the paper is that many paragraphs try to deliver the simple concept of the zero-one law for GNNs and its importance/motivation, which was too long for me. The paper is not concise. \n\n(1) In the paper, it is mentioned that this is a well-known result: \"any graph invariant which can be expressed by a first-order formula satisfies a zero-one law\" How does this relate to your result? Are you claiming that non-first-order formulas are satisfying the zero-one law? Otherwise, it falls in that category and it's not a new result. If not, an extensive explanation is required for how your proof is different and how those results are connected in each other. \n\n(2) line 209: \"we expect..\" This is indeed an important problem that is left unanswered. The rate of convergence shows when GNNs are not useful, so it may be exponentially slow in the number of nodes. \n\n(3) Many results in the paper are conditional on excluding an unknown zero-measure set of parameters. However, optimization algorithms (like SGD) trajectory is also a set of measure zero. The local minima of the objective may fall in those sets. \n\n (4) In Lemma 4.11, it is proved that the hidden representations of nodes, for any iteration, will converge to a fixed value. This is highly restricted by the assumption that the non-linearity saturates. As a result, it will not directly apply to ReLU networks. \n\n\n\n\n(5) The results are highly restricted. Random initial features are drawn based on the same distribution across different nodes. They cannot depend on the graph. The ER model is itself not realistic because we hope GNNs can extract hidden features from the graph data, while random ER graphs don't have any meaningful \"feature.\" ER graphs are dense, while in practice, sparse graphs (like grids) also appear. Besides that, the paper proofs apply after using the concentration inequalities for a large number of nodes. It thus looks reasonable to expect those zero-one laws to happen. \n\n\n\nMinor comments:\n\n\n (0) line 67 - are the initial features and the random graph independently drawn? Or they can depend on each other?  (it is later mentioned in Definition 4.2) Also, it is unclear whether the random initial features of different nodes are independent. \n \n (1) line 73 - can the functions $\\psi$ and $\\phi$ depend on the iteration index $t$? This is not clearly mentioned there. \n\n(2) line 263: typo: \"every node $u$\" -> \"every node $v$\"\n\n\n", "limitations": "N/A", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- nice theoretical results \n- citing previous works\n", "weaknesses": "- the results are restricted to ER graphs, which are not what we have in practice. Also, their model is restricted to dense graphs.\n- the paper is generally well-written, but some parts are long and could be more concise (like the meaning of the zero-one law and its motivation); they could've used the space better\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and your comments on our paper. We address each below.\n\n> (0) One major problem regarding the writing of the paper is that many paragraphs try to deliver the simple concept of the zero-one law for GNNs and its importance/motivation, which was too long for me.\n\nTo the best of our knowledge, using a zero-one law to give an upper bound on uniform expressivity is a new technique in (graph) ML, though well studied in mathematical logic. While the concept of a zero-one law is not too complex, the perspective of using it to characterise the class of properties which GNNs can capture is new, and thus requires more careful explanation. This motivation is also essential to understand why the choice of ER model is a reasonable one, because it establishes a result on uniform expressivity in line with similar results for first-order logic. We are happy to make all these explanations more concise in line with your request. Could you please let us know which parts/sections could be improved in this respect?\n\n> (1) In the paper, it is mentioned that this is a well-known result: \"any graph invariant which can be expressed by a first-order formula satisfies a zero-one law [...]\n\nGNNs can express logical formulas in certain two-variable fragments of first-order logic (Barcelo et al 2020), but the upper bound remains open: there is *no* result which states that every GNN expresses a first-order formula; conversely, it is known that GNNs cannot express every first-order formula. Hence, even though related, there is no implication between Fagin’s result and ours. Our result further helps with the quest of identifying the precise logical fragment the studied GNNs can capture: the logic that can be captured by these GNNs must follow a zero-one law. We note that Fagin’s proof for first-order formulas works in a completely different way, relying on logical techniques, whereas our techniques are more probabilistic. \n\n> (2) line 209: \"we expect..\" This is indeed an important problem that is left unanswered. [...]\n\nWe agree that the study on the rate of convergence is important, but given its complexity, it deserves a separate study. The natural way to approach this would be to keep track of the variance of the node representations throughout the network. However, there are a number of dependencies between these, which would necessitate computing the covariance matrices, which complicates the analysis. \n\nThat being said, we do not think this presents a weakness for our main question: what class of properties can GNNs (uniformly) express? What we have shown is that if a GNN expresses a property $P$, then $P$ must satisfy a zero-one law on ER graphs. This limits the expressivity of these models to this class of properties. For example, as far as we are aware this is the *first result* showing that GNNs cannot express node-number parity. Please note that, for the expressiveness study, we don’t need any bounds on convergence, as it holds regardless. We nonetheless conjecture a fast convergence, as indicated in the experimental results.\n\n> (3) Many results in the paper are conditional on excluding an unknown zero-measure set of parameters. [...]\n\nCould you explain why the fact that the trajectory is of zero measure makes it plausible that a local minimum falls in any other particular set of zero-measure? The excluded set is a fixed zero-measure (in fact lower dimensional) subset of the parameter space. The optimization trajectory is one-dimensional, so is unlikely to even intersect any set of zero-measure, let alone finish there.\n\n> (4) In Lemma 4.11, it is proved that the hidden representations of nodes, for any iteration, will converge to a fixed value. This is highly restricted by the assumption that the non-linearity saturates.\n\nWe acknowledge this as a limitation for our result on SumGNN models, but note that the result still applies to some common non-linearities, such as the sigmoid function (under fixed precision), and that this limitation does not apply to the GCN and MeanGNN results.\n\nWe include in our global response PDF an experiment on the asymptotic behaviour of ReLU SumGNN models. This suggests that a zero-one law holds in practice. However, our techniques do not straightforwardly extend to the ReLU case, and this would require further study.\n\n> (5) The results are highly restricted. Random initial features are drawn based on the same distribution across different nodes. [...]\n\nIn most theoretical studies we are aware of, it is standard to assume node features from the same distribution, and we align with these studies. It is true that graph topology and node features can be dependent, but the degree of this dependence is hard to determine and could be very different depending on the domain, and on other factors, e.g., whether graphs are homophilic or heterophilic. Hence, we think assuming independence is a reasonable choice for theoretical investigations. \n\nBut let us emphasise that the realisticness of ER graphs has no bearing on the validity of the result establishing a uniform bound on expressivity. In fact an analogous result with respect to *any* graph distribution would provide a new bound (i.e. that properties captured by GNNs must satisfy a zero-one law with respect to that distribution). The choice of ER graphs is common in similar studies on zero-one laws and also in related works in the graph ML community; see, e.g., Oono et al (2020) which analyses the over-smoothing phenomenon of GNNs with respect to ER graphs. We therefore consider it an appropriate choice for our analysis.\n\n> (0) line 67 - are the initial features and the random graph independently drawn? [...]\n\nWe will add a sentence clarifying this part: random initial features are independent both from each other and the graph adjacency matrix.\n\n> (1) line 73 - can the functions ψ and φ depend on the iteration index ?\n\nThe functions can indeed vary between iterations. We will add an index to make this explicit.\n"}, {"review_id": "QEjKgX0hIK", "reviewer": "Reviewer_ye6a", "summary": "This paper introduces the zero-one laws pertaining to graph neural networks. More specifically, the authors utilize concentration analysis on Erdos-Renyi graphs to demonstrate that the likelihood of GNN classifiers producing either zero or one as output approaches 1. These findings are further expanded to encompass three different methods of aggregation and normalization in GNNs. Additionally, the authors present uniform approximation results for graph invariants that adhere to the zero-one law.", "questions": "1. I still lack access to the specific paper mentioned, so I can offer only general suggestions for rephrasing the paragraph based on the information provided:\nI find it challenging to fully comprehend the correct interpretation of Definition 4.9, \"synchronously saturating.\" In addition to presenting reasonable concentration results in the proof, it would be beneficial if the authors could provide a more straightforward explanation. Furthermore, I would appreciate further justification for the claim made: (Ln 242-243) In fact, assuming that µ, σ−∞ and σ∞ are non-zero, the the set of weights which yield a non-synchronously-saturating model has measure zero?\n\n2. If I understand correctly, Section 5 primarily argues that the zero-one law is not always disadvantageous, as it enables uniform approximation. However, I'm curious why approximating a function with a fixed output (either 0 or 1) is considered desirable?\n\n3. The paper uncovers an intriguing zero-one law emerging in GNNs. However, I would like to inquire whether the ER graph and sub-gaussian feature assumptions are the primary factors contributing to this phenomenon. It seems that the concentration is not a result of any specific components within GNNs, but rather an outcome of the assumed input.\n\n4. Could the authors shed light on how the asymptotics correspond to the number of layers? Do additional layers lead to faster or slower concentration?\n", "limitations": "The paper addresses certain limitations, and in addition to those already discussed, I recommend that the authors include a discussion on the strict assumptions made. Examining the impact of removing either the ER graph assumption or the sub-gaussian condition could potentially yield more substantial results.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "+ The primary assertion is intriguing and offers a fresh perspective for evaluating the expressive capabilities of graphs.\n\n+ This paper presents valid theoretical contributions, establishing the first asymptotic analysis of GNN behavior as the number of nodes approaches infinity. This analysis yields negative outcomes regarding GNN expressiveness, which may prompt reconsideration of new GNN architecture designs. \n\n+ Despite its theoretical soundness, the paper also conducts well-designed experiments to substantiate its claims.\n", "weaknesses": "- Certain theoretical definitions and arguments lack intuitive explanations, making it challenging to justify the assumptions. (See Questions)\n\n- To the best of my knowledge, global readout typically occurs only in the last layer. However, it appears that both MeanGNN and SumGNN incorporate it in each layer. Although this may not necessarily complicate the analysis, it may deviate from practical usage.\n\n- Are the arguments limited to ER graphs and sub-gaussian features? Does the concentration primarily stem from the assumptions regarding ER graphs and sub-gaussian features, rather than establishing a unique zero-one law specific to GNNs? (See Questions)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for your comments. We address your concerns below.\n\n> I still lack access to the specific paper mentioned, so I can offer only general suggestions for rephrasing the paragraph based on the information provided: I find it challenging to fully comprehend the correct interpretation of Definition 4.9, \"synchronously saturating.\" In addition to presenting reasonable concentration results in the proof, it would be beneficial if the authors could provide a more straightforward explanation. Furthermore, I would appreciate further justification for the claim made: (Ln 242-243) In fact, assuming that µ, σ−∞ and σ∞ are non-zero, the the set of weights which yield a non-synchronously-saturating model has measure zero?\n\nAnalysis of the proof of the main result reveals that the asymptotic behaviour is determined by the matrices $Q_t = rW_n^{(t)} + W_g^{(t)}$, where asymptotic final layer embeddings are $\\sigma(Q_T(\\sigma(Q_{T-1} \\cdots \\sigma(Q_0 \\mu) \\cdots ))))$. To be synchronously saturating is to avoid the boundary case where one of the intermediate steps in the asymptotic final layer embedding computation has a zero component.\n\nThis is expressed by finitely many linear non-equalities. The space of models which is not synchronously saturating is the union of solution space of each equality, each of which space has dimension lower than the whole space. The space of such models is thus of lower dimension, and therefore of zero measure.\n\nWe will add this explanation to the paper.\n\n> If I understand correctly, Section 5 primarily argues that the zero-one law is not always disadvantageous, as it enables uniform approximation. However, I'm curious why approximating a function with a fixed output (either 0 or 1) is considered desirable?\n\nIn Section 5 we aim for a more complete characterisation of the expressive power of our GNNs, by establishing a partial matching lower bound for the uniform expressivity upper bound established in the previous section. Informally, this corresponds to answering the following complementary question: knowing that we can ‘at best’ capture properties which follow a zero-one law, is it possible to capture all such properties with GNNs? For this theoretical result, given any property which satisfies a certain zero-one law we need to find some GNN model which uniformly approximates it.\n\n> The paper uncovers an intriguing zero-one law emerging in GNNs. However, I would like to inquire whether the ER graph and sub-gaussian feature assumptions are the primary factors contributing to this phenomenon. It seems that the concentration is not a result of any specific components within GNNs, but rather an outcome of the assumed input.\n\nFundamentally, zero-one laws are properties of languages (or classes of models) not the respective inputs. Indeed, the fact that the sum-aggregation and mean-aggregation models require different techniques to establish a zero-one law suggests the choice of aggregation component is an important factor contributing to the law. We would like to draw a comparison with analogous zero-one laws established for first-order formulas by Glebskii et al., (1969) and Fagin (1976). These classical findings are generally regarded as establishing a surprising property of first-order logic, rather than of ER graphs. Our work is in exactly the same spirit: we use ER graphs as a distribution to examine the class of properties expressible by GNN models, just as they have been used to investigate the class of first-order properties.\n\nWe note also that in practice all node features will have bounded values (determined by the bit length of the storage medium), and are thus sub-Gaussian. Therefore this assumption is a very mild one.\n\n> Could the authors shed light on how the asymptotics correspond to the number of layers? Do additional layers lead to faster or slower concentration?\n\nA formal analysis of the rate of convergence would be quite non-trivial. The natural way to approach this would be to keep track of the variance of the node representations throughout the network. However, there are a number of dependencies between these, which would necessitate computing the covariance matrices, which complicates the analysis.\n\nIn the appendix we include experiments investigating the effect of using different nonlinearities. We have found that while for some choices of nonlinearity convergence is slower for a greater number of layers, for other choices the opposite phenomenon occurs (see Appendix E.2). We therefore expect a complex picture, in which the rate of convergence depends on the choice of nonlinearity, the number of layers and (likely) the width of those layers.\n\n> To the best of my knowledge, global readout typically occurs only in the last layer. However, it appears that both MeanGNN and SumGNN incorporate it in each layer. Although this may not necessarily complicate the analysis, it may deviate from practical usage.\n\nWe note that our results apply equally to the case where the global readout occurs in the last layer, or indeed not at all, by setting the global readout weights to 0. We allow a global readout in all layers to make our results more general.\n"}, {"review_id": "isZkcMe5Bu", "reviewer": "Reviewer_Mx1j", "summary": "This paper is primarily a theory paper - proposing a proof that, as the number of nodes in a graph drawn from the ER graph distribution increases, a class of GNNs binary classifiers converges to either 1 or 0.\n\nThis observation is backed up with a small set of empirical experiments of GCNs and variants, but no additional experiments on more advanced GNNs.\n\n", "questions": "How would an attention aggregation change the analysis? For me, that would hugely improve the impact of the paper because you're heading towards transformers at that point and so a far wider audience.", "limitations": "Limitations have been expressed above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I thought the paper was well written, and the mathematics was clearly presented.\n\nThe observations in the text were illuminating and intution was added at appropriate points. I felt that the exposition was not overly confusing, as can be the case with a number of theory papers, and the results put in context. Overall, I really enjoyed reading this, which is a rarity for theory heavy papers.", "weaknesses": "I don't think it can be argued that it is a weakness that the paper's experimental results are for a class of models that isn't very commonly used any more - GCNs as they are presented in this work have been superseded by any number of architectural innovations. There are not, for example, experiments or proofs on the impact of residual layers or skip connections, or GNNs with edge MLPs. As such, I think while it's a very nice result, the impact of the paper is likely to be low.\n\nIt wasn't clear to me - and I think this is because the math would be impossible to do for every architecture - how this result depends upon the scale seen in a number of graph neural networks, or how it changes if you add an attention mechanism. It could be that, in practice, this effect is only relevant if you have a very underpowered network, or you have a very very large graph. Both of which are not hugely practical examples.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review, and your comments on the clarity of the exposition.\n\n> How would an attention aggregation change the analysis? For me, that would hugely improve the impact of the paper because you're heading towards transformers at that point and so a far wider audience.\n\nThe study of attention in its full generality is very interesting, particularly in connection to transformers, but also very challenging, because it can capture wildly different behaviours. On the one hand, we have found that if we restrict the attention to follow a distribution which closely follows a Dirichlet distribution (or, deviates from mean-aggregation with some bounded epsilon), then our techniques for MeanGNNs will apply with minor modifications. On the other hand, in practice attention is conditioned on the feature of the source node and so it can act non-uniformly depending on the source node, effectively emulating different aggregations for different nodes.\n\nUnder the light of these considerations, we view a fine-grained analysis of attention models under different assumptions as a challenging future work. We have, however, conducted experimental analysis on GATs, which do appear to display a zero-one law quite strongly; we conjecture this is due to the static attention of GATs, which is shown to be a restricted form of attention (Brody et al, 2022). We include this experimental result in our 'global' response PDF."}, {"review_id": "kThF3e3hfk", "reviewer": "Reviewer_P48L", "summary": "The authors analyze standard GNN binary classifiers on Erdos-Renyi graphs, and conclude that the output satisfies a zero-one law. To be more precise, this means that an Erdos-Renyi graph with the number of nodes tending to infinity and random node features will be classified as 1 with probability tending towards either 0 or 1. Of course, this comes with some assumptions, which the authors claim are mild and reasonable to assume. The authors also provide empirical data that suggests n does not need to be incredibly large (on the order of 1,000 or 10,000) for this effect to take hold. ", "questions": "1. Do the proofs extend easily to different random graph structures and/or wider families of distributions?\n2. Why was it not possible to run the Figure 1 plot for larger graphs? SUMGNN T=3 seems like it may converge, but it would be nice to see it visually.\n", "limitations": "Limitations address key points, although could be elaborated upon more. The current version may be toning down the limitations as addressed above in the weakness section.\n\nNo potential negative societal impact.\n\n", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The strengths of this paper lie in the novelty of the authors' result. The result is interesting and significant to the field of investigating the theoretical upper and lower bound of expressivity in GNNs, which will inspire other readers to expand upon the investigation, particularly in zero-one laws. Experiments done are also convincing in supporting the practicality of their argument and to give readers a visual indication of the authors' result.", "weaknesses": "The paper's main weakness lies in their dismissal of assumptions. Although the result is interesting, its overall current practicality may be somewhat overstated. For example, in line 173 authors claim sub-Gaussian random vectors \"encompass all practical setups.\" This may be quite a bold statement, as many real-world examples are known to follow common distributions such as the exponential or Pareto distributions, and are fitting for further investigation. In addition, the same can be said about the ER random graph model; it is useful as an analytical tool, but fits to real graph topologies rather poorly. Perhaps more theoretical work or empirical investigation can be done on both fronts. (I acknowledge that there are empirical results on the Barabási-Albert model, which is helpful.)\n\nIf treated as a purely theoretical result/paper though, these addressed weaknesses may be taken lightly. \n\nAlso, would it be possible to add confidence bounds for the graphs in this case?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments on our paper, which we address below.\n\n> Do the proofs extend easily to different random graph structures and/or wider families of distributions?\n\nWe haven’t found an easy extension to different distributions of graphs with node features. Once edges and features become dependent, it becomes harder to apply classical concentration inequalities, and so new techniques would be needed in this case. We note however that in the classical literature on first-order logic, to obey a zero-one law means to do so with respect to ER graphs.\n\n> Why was it not possible to run the Figure 1 plot for larger graphs? SUMGNN T=3 seems like it may converge, but it would be nice to see it visually.\n\nThe principal reason for not continuing the graph was a limitation of our infrastructure setup. We have now rerun the experiment up to larger graphs, which indeed show convergence around $10^5$ nodes. We include the figure in our global response PDF and will replace the corresponding figure in the paper.\n\n> Also, would it be possible to add confidence bounds for the graphs in this case?\n\nThank you for your suggestion. We would like to incorporate it into our paper, but we noticed it may hinder the clarity of the presentation, because of the following reason. Because the asymptotic behaviour goes one of two ways, to add confidence bounds we need need to either separate the data into ‘asymptotically 0’ and ‘asymptotically 1’ by inspection, or else perform some transformation on the data (such as $x \\mapsto 2 |x - 0.5|$), which would reduce the demonstrative force of the figures. If you think the confidence bounds could be nonetheless helpful, we will do our best to integrate these into our presentation.\n\n> Although the result is interesting, its overall current practicality may be somewhat overstated. For example, in line 173 authors claim sub-Gaussian random vectors \"encompass all practical setups.\" This may be quite a bold statement, as many real-world examples are known to follow common distributions such as the exponential or Pareto distributions, and are fitting for further investigation.\n\nWe wish to note that, while real world examples may have distributions which are not sub-Gaussian, as you mention, in practice all node features will have bounded values (determined by the bit length of the storage medium), and are thus sub-Gaussian. We’ll add a sentence to explain this.\n"}]

Author rebuttal:
We wish to thank the reviewers for their comments. We have responded to each concern in detail in our individual responses. In addition, we include a PDF containing the results of additional experiments as suggested by reviewer comments.

Here is a summary of the changes to be made to the paper in light of the reviews received.
- We will include the extended SumGNN experiment (Figure 1 in the PDF) in place of the original. We will also include the additional experiments in the appendix.
- We will add a number of clarifying sentences, as suggested by reviewer comments.
- A few typos and minor errors will be corrected.

We look forward to continuing the discussion with the reviewers in the coming days.


Meta-review: This paper analyzes standard GNN binary classifiers on Erdos-Renyi graphs, and identifies that the output satisfies a zero-one law: an Erdos-Renyi graph with the number of nodes tending to infinity and random node features will be classified as 1 with probability tending towards either 0 or 1. 

Although reviewers have concerns about the assumptions, the results presented in this paper is interesting and significant to the community investigating the theoretical upper and lower bound of expressivity in GNNs, which may prompt new GNN architecture designs. Experiments presented in this paper are convincing as well.
Decision: Accept (poster)