Zero-One Laws of Graph Neural Networks
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\H{o}s-R\'enyi 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 '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.
Sam Adam-Day, Theodor Mihai Iliant, İsmail İlkan Ceylan
# Zero-One Laws of Graph Neural Networks

###### Abstract

Graph neural networks (GNNs) are 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 Erdos-Renyi 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 '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.

Machine Learning, Graph Neural Networks, Graph Neural Networks

## 1 Introduction

Graphs are common structures for representing relational data in a wide range of domains, including physical (Shlomi et al., 2021), chemical (Duvenaud et al., 2015; Kearnes et al., 2016), and biological (Zitnik et al., 2018; Fout et al., 2017)) systems, which sparked interest in machine learning over graphs. Graph neural networks (GNNs) (Scarselli et al., 2009; Gori et al., 2005) have become prominent models for graph machine learning for a wide range of tasks, owing to their capacity to explicitly encode desirable relational inductive biases (Battaglia et al., 2018), and to their adaptability to different graphs of different sizes.

One important virtue of these architectures is that every GNN model can be applied to _arbitrarily large_ graphs, since, in principle, the model parameters can be independent of the graph size. This raises the following question: how do GNNs behave as the number of nodes becomes very large? Inspired by the remarkable 'zero-one law' for first-order properties of graphs (Glebskii et al., 1969; Fagin, 1976), we investigate the behavior of GNNs when we draw graphs of increasing size from the Erdos-Renyi distribution on graphs, together with random node features.

The motivation of this work is twofold. First, our study establishes a setting in which to probe the _extrapolation capacity_ of GNNs: to what extent can models trained on smaller graphs capture properties which generalize well to larger graphs? Second, our analysis transfers readily to yield _expressiveness results_ for GNNs with random node features which are known to be very powerful on bounded graph domains (Sato et al., 2021; Abboud et al., 2021). What class of functions over graphs can GNNs with random node features _uniformly_ approximate?

The main result of this paper is given for binary graph classification: under mild assumptions on the model, several GNN architectures including graph convolutional networks (Kipf and Welling, 2017) satisfy a zero-one law over Erdos-Renyi graphs with random node features. This means that as we draw larger and larger graphs, the probability that the GNN maps such graphs to a particular output either tends to _one_ or tends to _zero_. This surprising result establishes important limits on the extrapolation capacity of GNNs as well as the expressivity of GNNs with random node features.

Zero-one laws give a simple and a direct argument for proving that properties for which these convergence laws fail cannot be expressed in the target language. A well-known example is the fact that no sentence of first-order logic can distinguish between finite structures of _even_ and _odd_ cardinality. Our study can thus be seen as an upper bound on the expressive power of the class of models under consideration. We also prove an interesting lower bound on the expressive power of GNNs with random node features: any property which satisfies a certain zero-one law can be universally approximated by a GNN using sum aggregation with random node features. This complementary results allows us to better understand the expressive power of such models.

Our main contributions can be summarized as follows.
* We obtain a zero-one law for the prominent model of graph convolutional networks using mild assumptions. We also prove a zero-one law for models with mean and sum aggregation, subject to certain mild conditions.
* Our result implies a corresponding zero-one law for GNNs with random node features, which establishes an upper bound on their expressivity. We complement this result, by additionally showing that these models can universally approximate any property which satisfies a certain zero-one law.
* We conduct experiments to validate our theoretical findings. Since zero-one laws are of asymptotic nature, we may need to consider very large graphs to observe a clear empirical evidence for the phenomenon. Surprisingly, however, GNNs already exhibit a clear evidence of zero-one law even on small graphs. Importantly, this is true for networks with very few layers (even single-layer), which is reassuring, as it precludes confounding factors, such as the effect of over-smoothing due to increased number of layers (Li et al., 2018).

All proof details are deferred to the appendix of this paper.

## 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 \(\mathbf{x}\in\mathbb{R}^{d}\) to represent a vector, and \(\mathbf{X}\in\mathbb{R}^{d\times n}\) to represent a matrix. Analogously, we write \(\mathbf{x}\) to denote a _random_ vector, and \(\mathbf{X}\) to denote a _random_ matrix, whose entries are (real) random variables.

We write \(\mathbb{G}(n,r)\) to denote a class of simple, undirected Erdos-Renyi (ER) graphs and \(\mathbb{D}(d)\) to denote a distribution of feature vectors over \(\mathbb{R}^{d}\). We define an Erdos-Renyi graph equipped with random node features as a pair \(\mathcal{G}=(\mathbf{A},\mathbf{X})\), where \(\mathbf{A}\sim\mathbb{G}(n,r)\) is the random graph adjacency matrix of a simple graph \(G=(V,E)\) of order \(n\) and \(\mathbf{X}\in\mathbb{R}^{d\times n}\) is a corresponding random feature matrix which contains, for each node \(v\in V\), an initial random node feature \(\mathbf{x}_{v}\sim\mathbb{D}(d)\) as the corresponding columns of \(\mathbf{X}\).1

Footnote 1: We define a \(d\times|V|\) dimensional (random) feature matrix as opposed to the more common \(|V|\times d\). This is for ease of presentation, since we aim to work on the (random) column vectors of such matrices (without the need of transposing each time).

**Message passing neural networks.** Graph neural networks have become prominent in machine learning over graph-structured data. The focus of this work is on _message-passing neural networks (MPNNs)_ (Gilmer et al., 2017) which encapsulate the vast majority of GNNs. The fundamental idea in MPNNs is to update the initial (random) state vector \(\mathbf{x}_{v}^{(0)}=\mathbf{x}_{v}\) of each node \(v\) for \(T\in\mathbb{N}\) iterations, based on its own state and the state of its neighbors \(\mathcal{N}(v)\) as:

\[\mathbf{x}_{v}^{(t+1)}=\phi\Big{(}\mathbf{x}_{v}^{(t)},\psi\big{(}\mathbf{x}_ {v}^{(t)},\{\!\{\!\mathbf{x}_{u}^{(t)}|\;u\in\mathcal{N}(v)\}\!\}\big{)}\Big{)},\]

where \(\{\!\{\!\cdot\!\}\!\}\) denotes a multiset, and \(\phi\) and \(\psi\) are differentiable _combination_, and _aggregation_ functions, respectively. We allow each layer's node representations to have different dimensions, and denote by \(d(t)\) the dimension of each \(\mathbf{x}_{v}^{(t)}\). We also write \(d(0)=d\). The choice for the combine (\(\phi\)) and aggregate (\(\psi\)) functions yields different models.

In other words, when applied on a random graph \(\mathbf{A}\) with random features \(\mathbf{x}_{v}^{(0)}\) for every node \(v\in V\), an MPNN generates a sequence of random node state vectors \(\mathbf{x}_{v}^{(1)},\dots,\mathbf{x}_{v}^{(T)}\). The final node representations can then be used for node-level predictions. For graph-level predictions, the final node embeddings are _pooled_ to form a graph embedding vector to predict properties of entire graphs. The pooling often takes the form of simple averaging, summing or element-wise maximum. For Boolean node (resp., graph) classification, we further assume a classifier \(\mathfrak{C}:\mathbb{R}^{d(T)}\to\mathbb{B}\) which acts on the final node representations (resp., on the final graph representation).

It is important to note that there are more general massage passing paradigms (Battaglia et al., 2018). In particular, _MPNNs with global readout_, which additionally aggregate over all node features at every layer, are known to be more expressive (Barcelo et al., 2020). Some specific model instances considered in this paper include a global readout component.

**GCNs.** The primary GNN architecture we consider is the _graph convolutional network_(Kipf & Welling, 2017), denoted by GCN. These are instances of MPNNs with self-loops, which aggregate over the extended neighborhood of a node \(\mathcal{N}^{+}(v):=\mathcal{N}(v)\cup\{v\}\). GCNs iteratively update the representations as \(\mathbf{x}_{v}^{(t)}=\sigma\left(\mathbf{y}_{v}^{(t)}\right)\), where the preactivations are given by:

\[\mathbf{y}_{v}^{(t)}=\mathbf{V}_{\text{n}}^{(t)}\sum_{u\in\mathcal{N}^{+}(v)} \frac{1}{\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}}\mathbf{x}_{u}^{(t-1)}+\mathbf{b} ^{(t)}\]

We apply the linear transformation \(\mathbf{V}_{\text{n}}^{(t)}\in\mathbb{R}^{d(t)\times d(t-1)}\) to a normalized sum of the activations for the previous layers of the neighbors of the node under consideration, together with its own activation. Adding a bias term \(\mathbf{b}^{(t)}\) yields the preactivation \(\mathbf{y}_{v}^{(t)}\), to which we apply the non-linearity \(\sigma\).

**MeanGNNs.** We also consider _GNN models with self-loops, mean aggregation and global readout_, denoted MeanGNN\({}^{+}\). This is a modification of GCN architecture in which we normalize the previous preactivations by taking the mean. We also include a global readout term. Formally,
these are instances of MPNNs with global readout, given as \(\mathbf{x}_{v}^{(t)}=\sigma\left(\mathbf{y}_{v}^{(t)}\right)\), where:

\[\mathbf{y}_{v}^{(t)}=\left(\begin{array}{c}\frac{1}{|\mathcal{N}^{\frac{1}{ \left(v\right)}}|\boldsymbol{V}_{n}^{(t)}\sum_{u\in\mathcal{N}^{+}\left(v \right)}\mathbf{x}_{u}^{(t-1)}}\\ +\frac{1}{n}\mathbf{V}_{\mathrm{r}}^{(t)}\sum_{u\in V}\mathbf{x}_{u}^{(t-1)} \\ +\boldsymbol{b}^{(t)}\end{array}\right).\]

We sometimes refer to this model _without the global readout_ term, which is simply denoted as MeanGNN.

**SumGNNs.** Finally, we define the _sum GNN models with global readout_, denoted SumGNN\({}^{+}\), which are instances of MPNNs with global readout, given as \(\mathbf{x}_{u}^{(t)}=\sigma\left(\mathbf{y}_{u}^{(t)}\right)\), where:

\[\mathbf{y}_{v}^{(t)}=\left(\begin{array}{c}\boldsymbol{V}_{\mathrm{s}}^{(t) }\mathbf{x}_{\mathrm{v}}^{(t-1)}\\ +\boldsymbol{V}_{\mathrm{n}}^{(t)}\sum_{u\in\mathcal{N}(v)}\mathbf{x}_{u}^{(t- 1)}\\ +\boldsymbol{V}_{\mathrm{r}}^{(t)}\sum_{u\in V}\mathbf{x}_{u}^{(t-1)}\\ +\boldsymbol{b}^{(t)}\end{array}\right).\]

This time, we separate out the contribution from the preactivation of the previous activation for the node itself. This yields three linear transformations \(\boldsymbol{V}_{\mathrm{s}}^{(t)},\boldsymbol{V}_{\mathrm{n}}^{(t)}, \boldsymbol{V}_{\mathrm{r}}^{(t)}\in\mathbb{R}^{d(t)\times d(t-1)}\). The model without the global readout term is denoted SumGNN.

## 3 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 a study could lead to a better understanding of the extrapolation capabilities of MPNNs which is widely studied in the literature (Yehudai et al., 2020; Xu et al., 2021). More broadly, zero-one laws have a rich history in first-order logic and random graph theory (Glebskii et al., 1969; Fagin, 1976; Libkin, 2004; Shelah and Spencer, 1988; Bollobas, 2001). Being the first of its kind in the graph machine learning literature, our study establishes fundamental links between graph representation learning, probability theory and logic, while also presenting an interesting way to analyze the expressive power of GNN models.

It is well-known that the expressive power of MPNNs is upper bounded by the _1-dimensional Weisfeiler Leman graph isomorphism test (1-WL)_(Xu et al., 2019; Morris et al., 2019). This implies that graphs cannot be distinguished by MPNNs if \(1\)-WL does not distinguish them. It has been shown that some architectures can match the power of 1-WL, including SumGNN\({}^{+}\) models (Morris et al., 2019). Barcelo et al. (2020) further gives a logical characterization for a class of MPNNs showing SumGNN\({}^{+}\) models can capture any function which can be expressed in the logic C\({}^{2}\), 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 identifiers_(Loukas, 2020), or define _higher-order_ GNN models (Morris et al., 2019; Maron et al., 2019; Beriven and Peyre, 2019) to obtain more expressive architectures.

Our work has direct implications on GNNs using random node features (Sato et al., 2021; Abboud et al., 2021), which are shown to be 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 can be captured by a _single_ GNN with random node features? Abboud et al. (2021) prove a universality result for these models, but it is not uniform, since the construction depends on the graph sizes, and yields a different model depending on the choice of the graph sizes. There is no known upper bound for the expressive power of GNNs with random node features in the uniform setting. Our results imply such an upper bound assuming ER graphs as inputs, and we complement this result, by giving a lower bound: GNNs with random node features can uniformly approximate any property which satisfies a certain zero-one law.

Other limitations of MPNNs include _over-smoothing_(Li et al., 2018; Oono and Suzuki, 2020) and _over-squashing_(Alon and Yahav, 2021) which are 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 (Li et al., 2018; Oono and Suzuki, 2020), 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 orthogonal to this work: we conduct an asymptotic analysis in the size of the graphs rather than in the number of layers.

## 4 Zero-One Laws of Graph Neural Networks

### Problem statement

We first define graph invariants following Grohe (2021).

**Definition 4.1**.: A _graph invariant_\(\xi\) is a function over graphs, such that for any pair of graphs \(G_{1}\), \(G_{2}\), and, for any isomorphism \(f\) from \(G_{1}\) to \(G_{2}\) it holds that \(\xi(G_{1})=\xi(f(G_{2}))\). Graph invariants for graphs with node features are defined analogously.

Consider any GNN model \(\mathcal{M}\) used for binary graph classification. It is immediate from the definition that \(\mathcal{M}\) is invariant under isomorphisms of the graphs on which it acts. Hence \(\mathcal{M}\), considered as function from graphs to \(\mathbb{B}\), is a graph invariant. In this paper, we study the asymptotic behavior of \(\mathcal{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 (Boolean) graph invariant \(\xi\) satisfies a _zero-one law_ if when we draw graphs \(G\) from the ER distribution \(\mathbb{G}(n,r)\), as \(n\) tends to infinity the probability that \(\xi(G)=1\) either tends to \(0\) or tends to \(1\). The result, due to Glebskii et al. (1969) and Fagin (1976), 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 a graph with node features, we need to reformulate the statement of the law to incorporate these features.

**Definition 4.2**.: Let \(\mathcal{G}=(\mathbf{A},\mathbf{X})\) be a graph with node features, where \(\mathbf{A}\sim\mathbb{G}(n,r)\) is a graph adjacency matrix and, independently, \(\mathbf{X}\) is a matrix of node embeddings, where \(\mathbf{x}_{v}\sim\mathbb{D}(d)\) for every node \(v\). A graph invariant \(\xi\) for graphs with node features satisfies a _zero-one law_ with respect to \(\mathbb{G}(n,r)\) and \(\mathbb{D}(d)\) if as \(n\) tends to infinity, the probability that \(\xi(\mathcal{G})=1\) either tends to \(0\) or tends to \(1\).

Studying the asymptotic behavior of GNNs helps to shed light on their capabilities and limitations. A zero-one law establishes a 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 a corresponding zero-one law for GNNs with random features. This establishes an upper-bound on the uniform expressive power of such models.

### Graph convolutional networks obey a zero-one law

Our main result in 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.

First, our study covers sub-Gaussian random vectors, which is a very wide class.

**Definition 4.3**.: A random vector \(\mathbf{x}\in\mathbb{R}^{d}\) is _sub-Gaussian_ if there is \(C>0\) such that for every unit vector \(\mathbf{y}\in\mathbb{R}^{d}\) the random variable \(\mathbf{x}\cdot\mathbf{y}\) satisfies the sub-Gaussian property: for every \(t>0\):

\[\mathbb{P}(|\mathbf{x}\cdot\mathbf{y}|\geq t)\leq 2\exp\left(-\frac{t^{2}}{C^{2}}\right)\]

Sub-Gaussian random vectors encompass almost all practical machine learning setups, including all bounded random vectors, and every multivariate normal random vector.

Second, we require that the non-linearity \(\sigma\) be Lipschitz continuous.

**Definition 4.4**.: A function \(f\colon\mathbb{R}\to\mathbb{R}\) is _Lipschitz continuous_ if there is \(C>0\) such that for any \(x,y\in\mathbb{R}\):

\[|f(x)-f(y)|\leq C|x-y|\]

Lipschitz continuity is a mild assumption, and in practice all non-linearities used are Lipschitz continuous. For example, each of \(\mathrm{ReLU}\), clipped \(\mathrm{ReLU}\), \(\mathrm{sigmoid}\), linearized \(\mathrm{sigmoid}\) and \(\tanh\) are Lipschitz continuous.

Third, we place a condition on the GCN weights with respect to the classifier function \(\mathfrak{C}\colon\mathbb{R}^{d(T)}\to\mathbb{B}\).

**Definition 4.5**.: Consider a distribution \(\mathbb{D}(d)\) with mean \(\mathbf{\mu}\). Let \(\mathcal{M}\) be a GCN used for binary graph classification. Define the sequence \(\mathbf{\mu}_{0},\dots,\mathbf{\mu}_{T}\) of vectors inductively by \(\mathbf{\mu}_{0}:=\mathbf{\mu}\) and \(\mathbf{\mu}_{t}:=\sigma(\mathbf{V}_{n}^{(t)}\mathbf{\mu}_{t-1}+\mathbf{b}^{(t)})\). The classifier classifier \(\mathfrak{C}:\mathbb{R}^{d(T)}\to\mathbb{B}\) is _non-splitting_ for \(\mathcal{M}\) if the vector \(\mathbf{\mu}_{T}\) does not lie on a decision boundary for \(\mathfrak{C}\).

For all reasonable choices of \(\mathfrak{C}\), the decision boundary has dimension lower than the \(d(T)\), and is therefore a set of zero-measure. This means that in practice essentially all classifiers are non-splitting.

**Theorem 4.6**.: _Let \(\mathcal{M}\) be a GCN used for binary graph classification and take \(r\in[0,1]\). Then, \(\mathcal{M}\) satisfies a zero-one law with respect to \(\mathbb{G}(n,r)\) and \(\mathbb{D}(d)\) assuming the following conditions hold:_

1. \(\mathbb{D}(d)\) _is sub-Gaussian._
2. \(\sigma\) _is Lipschitz continuous._
3. _The graph-level representation uses average pooling._
4. _The classifier is non-splitting._

The proof hinges on a probabilistic analysis of the preactivations in each layer. We use a sub-Gaussian concentration inequality to show that the deviation of each of the first-layer preactivations \(\mathbf{y}_{v}^{(1)}\) from its expected value becomes less and less as the number of node \(n\) tends to infinity. Using this and the fact that \(\sigma\) is Lipschitz continuous we show then that each activation \(\mathbf{x}_{v}^{(1)}\) tends towards a 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 \(\mathcal{M}\) and \(\mathbb{D}(d)\) satisfy the conditions in Theorem 4.6. Then, for every layer \(t\), there is \(\mathbf{z}_{t}\in\mathbb{R}^{d(t)}\) such that when sampling a graph with node features from \(\mathbb{G}(n,r)\) and \(\mathbb{D}(d)\), for every \(i\in\{1,\dots,d(t)\}\) and for every \(\epsilon>0\) we have that:_

\[\mathbb{P}\left(\forall v\colon\left|\left[\mathbf{x}_{v}^{(t)}-\mathbf{z}_{t} \right]_{i}\right|<\epsilon\right)\to 1\quad\text{as }n\to\infty\]
With the lemma established, the proof of Theorem 4.6 follows straightforwardly from the last two assumptions. Since the final node embeddings \(\mathbf{x}_{v}^{(T)}\) tend to a fixed value \(\mathbf{z}_{T}\), the average-pooled graph-level representations also tend to this. Since we assume that the classifier is non-splitting, this value cannot lie on a decision boundary, and thus the final output is asymptotically stable at \(\mathfrak{C}(\mathbf{z}_{T})\).

### Graph neural networks with mean aggregation

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 4.8**.: Consider a distribution \(\mathbb{D}(d)\) with mean \(\mathbf{\mu}\). Let \(\mathcal{M}\) be a MeanGNN\({}^{+}\) used for binary graph classification. Define the sequence \(\mathbf{\mu}_{0},\ldots,\mathbf{\mu}_{T}\) of vectors inductively by \(\mathbf{\mu}_{0}:=\mathbf{\mu}\) and \(\mathbf{\mu}_{t}:=\sigma((\mathbf{V}_{\mathrm{n}}^{(t)}+\mathbf{V}_{\mathrm{r}}^{(t)})\bm {\mu}_{t-1}+\mathbf{b}^{(t)})\). The classifier classifier \(\mathfrak{C}:\mathbb{R}^{d(T)}\to\mathbb{B}\) is _non-splitting_ for \(\mathcal{M}\) if the vector \(\mathbf{\mu}_{T}\) does not lie on a decision boundary for \(\mathfrak{C}\).

Again, in practice essentially all classifiers are non-splitting.

**Theorem 4.9**.: _Let \(\mathcal{M}\) be a MeanGNN\({}^{+}\) used for binary graph classification and take \(r\in[0,1]\). Then, \(\mathcal{M}\) satisfies a zero-one law with respect to \(\mathbb{G}(n,r)\) and \(\mathbb{D}(d)\) assuming the following conditions hold:_

1. \(\mathbb{D}(d)\) _is sub-Gaussian._
2. \(\sigma\) _is Lipschitz continuous._
3. _The graph-level representation uses average pooling._
4. _The classifier is non-splitting._

Note that the result immediately applies to MeanGNN, since it is a special case of MeanGNN\({}^{+}\) where \(\mathbf{V}_{\mathrm{g}}=0\).

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 4.10**.: _Let \(\mathcal{M}\) and \(\mathbb{D}(d)\) satisfy the conditions in Theorem 4.9. Then, for every layer \(t\), there is \(\mathbf{z}_{t}\in\mathbb{R}^{d(t)}\) such when sampling a graph with node features from \(\mathbb{G}(n,r)\) and \(\mathbb{D}(d)\), for every \(i\in\{1,\ldots,d(t)\}\) and for every \(\epsilon>0\) we have that:_

\[\mathbb{P}\left(\forall v\colon\left|\left[\mathbf{x}_{v}^{(t)}-\mathbf{z}_{t} \right]_{i}\right|<\epsilon\right)\to 1\quad\text{as }n\to\infty\]

With the key lemma in place the proof of Theorem 4.9 follows as before.

### Graph neural networks with sum aggregation

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

**Definition 4.11**.: A function \(\sigma\colon\mathbb{R}\to\mathbb{R}\) is _eventually constant in both directions_ if there are \(x_{-\infty},x_{\infty}\in\mathbb{R}\) such that \(\sigma(y)\) is constant for \(y<x_{-\infty}\) and \(\sigma(y)\) is constant for \(y>x_{\infty}\). We write \(\sigma_{-\infty}\) to denote the minimum and \(\sigma_{\infty}\) to denote the maximum value of an eventually constant function \(\sigma\).

Both the linearized \(\mathrm{sigmoid}\) and clipped \(\mathrm{ReLU}\) are eventually constant in both directions. Moreover, when working with finite precision any function with vanishing gradient in both directions can be regarded as eventually constant in both directions.

We also place the following condition on the weights of the model with respect to the mean of \(\mathbb{D}(d)\) and the edge-probability \(r\).

**Definition 4.12**.: Let \(\mathcal{M}\) be any SumGNN\({}^{+}\) for binary graph classification with a non-linearity \(\sigma\) which is eventually constant in both directions. Let \(\mathbb{D}(d)\) be any distribution with mean \(\mathbf{\mu}\), and let \(r\in[0,1]\). Then, the model \(\mathcal{M}\) is _synchronously saturating_ for \(\mathbb{G}(n,r)\) and \(\mathbb{D}(d)\) if the following conditions hold:

1. For each \(1\leq i\leq d(1)\): \[\left[(r\mathbf{V}_{\mathrm{n}}^{(1)}+\mathbf{V}_{\mathrm{g}}^{(1)})\mathbf{\mu}\right]_{ i}\neq 0\]
2. For every layer \(1<t\leq T\), for each \(1\leq i\leq d(t)\) and for each \(\mathbf{z}\in\{\sigma_{-\infty},\sigma_{\infty}\}^{d(t-1)}\) we have that:2 Footnote 2: We use \(\{\sigma_{-\infty},\sigma_{\infty}\}^{d(t-1)}\) to denote the set of \(d(t-1)\)-dimensional vectors whose components are all either \(\sigma_{-\infty}\) or \(\sigma_{\infty}\).

\[\left[(r\mathbf{V}_{\mathrm{n}}^{(t)}+\mathbf{V}_{\mathrm{g}}^{(t)})\mathbf{z}\right]_{i}\neq 0\]

To get a flavor of how wide the class of synchronously saturating models is, the following result shows that under certain assumptions on \(\mathbb{D}(d)\) and \(\sigma\), almost all \(\textsc{SumGNN}^{+}\) models are synchronously saturating. It is a straightforward consequence of the fact that to be non-synchronously-saturating is to satisfy one of a finite set of linear equalities.

**Proposition 4.13**.: _Let \(\mathbb{D}(d)\) be any distribution with mean \(\mathbf{\mu}\), such that \(\mathbf{\mu}_{i}\neq 0\) for each \(i\). Take \(r\in[0,1]\). Fix a non-linearity \(\sigma\) which is eventually constant in both directions, satisfying \(\sigma_{-\infty}\neq 0\) and \(\sigma_{\infty}\neq 0\). The following statements hold:_

1. _The set of values for each_ \(\mathbf{V}_{\mathrm{n}}^{(t)}\) _and_ \(\mathbf{V}_{\mathrm{g}}^{(t)}\) _which yield a_ SumGNN_\({}^{+}\) _model_ \(\mathcal{M}\) _which is not synchronously saturating for_ \(\mathbb{G}(n,r)\) _and_ \(\mathbb{D}(d)\) _has empty interior in the vector space of all weights._
2. _If the weights of a_ \(\textsc{SumGNN}^{+}\) _model_ \(\mathcal{M}\) _are drawn from a distribution whose support has non-empty interior, such as a multivariate normal or uniform distribution, then_ \(\mathcal{M}\) _is simultaneously saturating for_ \(\mathbb{G}(n,r)\) _and_ \(\mathbb{D}(d)\) _with probability_ \(1\)_._

With these definitions in place we can now lay out the main result:

**Theorem 4.14**.: _Let \(\mathcal{M}\) be a \(\textsc{SumGNN}^{+}\) used for binary graph classification and take \(r\in[0,1]\). Then, \(\mathcal{M}\) satisfies a zero-one law with respect to \(\mathbb{G}(n,r)\) and \(\mathbb{D}(d)\) assuming the following conditions hold:_

1. \(\mathbb{D}(d)\) _is sub-Gaussian._
2. \(\sigma\) _is eventually constant in both directions._
3. _The graph-level representation uses either average or element-wise maximum pooling._
4. \(\mathcal{M}\) _is synchronously saturating for_ \(\mathbb{G}(n,r)\) _and_ \(\mathbb{D}(d)\)_._

Note that as with Theorem 4.9, this result also applies to SumGNN, since it is a special cases of \(\textsc{SumGNN}^{+}\).

The proof works in a different way to the GCN and \(\textsc{MeanGNN}^{+}\) cases, but still rests on a probabilistic analysis of the preactivations in each layer. Assuming that \(\mathcal{M}\) is synchronously saturating for \(\mathbb{G}(n,r)\) and \(\mathbb{D}(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 \(0\) exponentially. Therefore, the probability that all node embeddings after the first layer are the same and have components which are all \(\sigma_{-\infty}\) or \(\sigma_{\infty}\) tends to \(1\). We then extend this analysis to further layers, using the fact that \(\mathcal{M}\) is synchronously saturating, which yields inductively that all node embeddings are the same with probability tending to \(1\). We therefore prove the following key lemma.

**Lemma 4.15**.: _Let \(\mathcal{M}\), \(\mathbb{D}(d)\) and \(r\) be as in Theorem 4.14. Let \(\sigma_{-\infty}\) and \(\sigma_{\infty}\) be the extremal values taken by the non-linearity. Then, for every layer \(t\), there is \(\mathbf{z}_{t}\in\{\sigma_{-\infty},\sigma_{\infty}\}^{d(t)}\) such that when we sample graphs with node features from \(\mathbb{G}(n,r)\) and \(\mathbb{D}(d)\) the probability that \(\mathbf{x}_{v}^{(t)}=\mathbf{z}_{t}\) for every node \(u\) 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 GNNs with Random Features

Up to this point we have been considering the graph plus node features as the (random) input to the GNN model. In this section, we make a 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 \(\textsc{SumGNN}^{+}\). Adding random initial features to GNNs is known to increase their power (Sato et al., 2021).

Note that Theorem 4.14 immediately yields a zero-one law for these models. This places restrictions on what can be expressed by \(\textsc{SumGNN}^{+}\) models with random features subject to the conditions of Theorem 4.14. For example, it is not possible to express that the number of graph nodes is even, since the property of being even doesn't satisfy a zero-one law with respect to any \(r\in[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 a Boolean function on graphs, and let \(\zeta\) be a random function on graphs. Take \(\delta>0\). Then \(\zeta\)_uniformly \(\delta\)-approximates_\(f\) if:

\[\forall n\in\mathbb{N}\colon\,\mathbb{P}(\zeta(G)=f(G)\mid|G|=n)\geq 1-\delta\]

when we sample \(G\sim\mathbb{G}(n,1/2)\).

The reason for sampling graphs from \(\mathbb{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 \(n\in\mathbb{N}\) the proportion of \(n\)-node graphs on which \(\zeta(G)=f(G)\) is at least \(1-\delta\).

Building on results due to Abboud et al. (2021), we show a partial converse to Theorem 4.14: if a graph invariant satisfies a zero-one law for \(\mathbb{G}(n,1/2)\) then it can be universally approximated by \(\textsc{SumGNN}^{+}\) with random features.

**Theorem 5.2**.: _Let \(\xi\) be any graph invariant which satisfies a zero-one law with respect to \(\mathbb{G}(n,1/2)\). Then, for every \(\delta>0\) there is a \(\textsc{SumGNN}^{+}\) with random node features \(\mathcal{M}\) which uniformly \(\delta\)-approximates \(\xi\). Moreover, \(\mathcal{M}\) uses the linearized \(\mathrm{sigmoid}\) as the non-linearity and the distribution of the initial node embeddings consists of \(d\) iid \(U[0,1]\) random variables._

The basis of the proof is a result due to Abboud et al. (2021) which states that \(\textsc{SumGNN}^{+}\) models 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. (2021) to approximate the invariant, and above the threshold we follow its asymptotic behavior. We emphasise that the combination of these techniques yeilds a model which provides an approximation which is uniform across all graph sizes.
## 6 Experimental Evaluation

We empirically verify our theoretical findings over ER graphs with random node features. We want to answer the following questions for each model under consideration:

1. [label=**Q0**]
2. Do we empirically observe a zero-one law?
3. What is the rate of convergence like empirically?
4. What is the impact of the number of layers?

**Experimental setup.** We report experiments for GCNs, MeanGNNs, and SumGNNs. The following setup is carefully designed to eliminate confounding factors:

* We consider \(10\) GNN models of the same architecture each with _random weights_, where each weight is sampled independently from \(U(-1,1)\). The non-linearity is eventually constant in both directions: identity between \([-50,50]\), and truncated to \(-50\) if the input is smaller than \(-50\), and \(50\) if the input is greater than \(50\). We apply mean pooling to yield a final representation \(\mathbf{z}_{G}\in\mathbb{R}^{d}\) of the input graph.
* For every model, we apply a final classifier \(\sigma(f):\mathbb{R}^{d}\rightarrow\mathbb{B}\) where \(f\) is a 2-layer MLP with _random weights_ and with \(\tanh\) activation, which outputs a real value, and \(\sigma\) is the sigmoid function. Graphs are classified as \(1\) if the output of the sigmoid is greater than \(0.5\), and \(0\) otherwise.
* The input graphs are drawn from \(\mathbb{G}(n,1/2)\) with corresponding node features independently drawn from \(U(0,1)\).
* We conduct these experiments with three choices of layers: \(10\) models with \(T=1\) layer, \(10\) models with \(T=2\) 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 mean-pooling, as 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 as \(1\) evolves, as we increase the graph sizes_.

We independently sample 10 models to ensure this is not a model-specific behavior, aiming to observe the same phenomenon across the models. If there is a zero-one law, then for each model, we should only see two types of curves: either tending to \(0\) or tending to \(1\), as graph sizes increase. Whether it 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.

**Remark.** We consider models with up to \(3\) layers to ensure that the node features do not become alike because of the orthogonal over-smoothing issue (Li et al., 2016), which surfaces with increasing number of layers. Using models with random weights is a neutral setup, and random GNNs are widely used in the literature as baseline models (Thompson et al., 2022), as they nonetheless define valid graph convolutions and tend to perform reasonably well.

### Empirical results

We report all results in Figure 1 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. Figure 2 in the appendix contains experiments using SumGNN\({}^{+}\) models.

**GCNs.** For this experiment, we use an embedding dimensionality of \(128\) for each GCN model and draw graphs of sizes \(\{10,50,100,500,1000,2000,5000\}\), where we take \(32\) samples of each size. The key insight of Theorem 4.6 is that the final mean-pooled embedding vector \(\mathbf{z}_{G}\) tends to a constant vector as we draw larger graphs. Applying an MLP followed by a sigmoid function will therefore map \(\mathbf{z}_{G}\) to either \(0\) or \(1\), showing a zero-one law. It is evident from Figure 1 (top row) that all curves tend to either \(0\) or \(1\), confirming our 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. In line with the proof of our theorem, the speed of convergence depends on the embedding dimensionality, hence our choice of \(128\). GCN models converge even faster with embedding dimensions \(64\), as expected.

**MeanGNN.** Given that the key insight in Theorem 4.9 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: we show that the preactivations and activations become closer and closer to 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 \(\mathbb{G}(n,1/2)\) we would expect each corresponding summand to have a similar value, since \(\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}\) should be close to \(|\mathcal{N}^{+}(v)|\).

Figure 1(mid row) illustrates the results for MeanGNNs and the trends are reassuringly similar to those of GCNs: all models converge quickly to either \(0\) and \(1\) with all choices of layers. Interestingly, the plots for GCN and MeanGNN 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.14 shows that, as the number of nodes grow, the embedding vector \(\mathbf{z}_{v}\) of each _node_\(v\) will converge to a 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 a 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 of the non-linearity. We therefore expect slower convergence. To accommodate for this, for this experiment, we use a smaller embedding dimensionality of \(64\) for each SumGNN model and draw graphs of sizes \(\{10,50,100,500,1000,2000,5000,10000,15000,20000,\\ 50000,100000,150000,200000,50000\}\), where we take \(32\) samples of each size. Figure 1 shows the results for SumGNNs, which clearly suggest slower convergence, as predicted.

In fact, two models (out of 10) do not converge in the two-layer setup, and three models (out of 10) do not converge in the three-layer setup. While it is highly likely that the randomly sampled model weights yield models which are simultaneously saturating (see the second item in Proposition 4.13), analysis of the proof of Theorem 4.14 suggests that the closer the model weights are to being non-simultaneously-saturating, the slower they will be to converge to a zero-one law. We hypothesize that the slowest converging models are those whose weights are closest to the critical values.

## 7 Discussions and Outlook

Our study has uncovered an intimate connection between graph neural networks and zero-one laws. The relation

Figure 1: Each plot shows the \(\%\) of graphs of certain size which are classified as \(1\) by the respective models: 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 much slower convergence, but all models converge in the case of 1-layer models. When considering 2 layers (resp., 3 layers), there are 2 (resp., 3) models out of 10, which have not yet converged with graphs of size \(50000\).
ship has consequences for the expressive power and extrapolation capacity of these models. In both the empirical evaluation and the technical proofs of our results we discovered two distinct mechanisms by which GNNs arrive at zero-one laws. One of these was at play in the case of GCN and MeanGNN models, while the other in the case of SumGNN models.

We leave as future work to examine the asymptotic behavior of other GNN architectures, such as GAT (Velickovic et al., 2018) and GIN (Xu et al., 2019). We would expect GAT models to follow the pattern of GCN and MeanGNN, since it is a self-loop MPNN in which the attention weights are normalized. In contrast, the architecture of GIN models suggest they may behave similarly to SumGNN.
