A graphon-signal analysis of graph neural networks
We present an approach for analyzing message passing graph neural networks
(MPNNs) based on an extension of graphon analysis to a so called graphon-signal
analysis. A MPNN is a function that takes a graph and a signal on the graph (a
graph-signal) and returns some value. Since the input space of MPNNs is
non-Euclidean, i.e., graphs can be of any size and topology, properties such as
generalization are less well understood for MPNNs than for Euclidean neural
networks. We claim that one important missing ingredient in past work is a
meaningful notion of graph-signal similarity measure, that endows the space of
inputs to MPNNs with a regular structure. We present such a similarity measure,
called the graphon-signal cut distance, which makes the space of all
graph-signals a dense subset of a compact metric space -- the graphon-signal
space. Informally, two deterministic graph-signals are close in cut distance if
they ``look like'' they were sampled from the same random graph-signal model.
Hence, our cut distance is a natural notion of graph-signal similarity, which
allows comparing any pair of graph-signals of any size and topology. We prove
that MPNNs are Lipschitz continuous functions over the graphon-signal metric
space. We then give two applications of this result: 1) a generalization bound
for MPNNs, and, 2) the stability of MPNNs to subsampling of graph-signals. Our
results apply to any regular enough MPNN on any distribution of graph-signals,
making the analysis rather universal.
Ron Levie
# A graphon-signal analysis of graph neural networks

###### Abstract

We present an approach for analyzing message passing graph neural networks (MPNNs) based on an extension of graphon analysis to a so called graphon-signal analysis. A MPNN is a function that takes a graph and a signal on the graph (a graph-signal) and returns some value. Since the input space of MPNNs is non-Euclidean, i.e., graphs can be of any size and topology, properties such as generalization are less well understood for MPNNs than for Euclidean neural networks. We claim that one important missing ingredient in past work is a meaningful notion of graph-signal similarity measure, that endows the space of inputs to MPNNs with a regular structure. We present such a similarity measure, called the graphon-signal cut distance, which makes the space of all graph-signals a dense subset of a compact metric space - the graphon-signal space. Informally, two deterministic graph-signals are close in cut distance if they "look like" they were sampled from the same random graph-signal model. Hence, our cut distance is a natural notion of graph-signal similarity, which allows comparing any pair of graph-signals of any size and topology. We prove that MPNNs are Lipschitz continuous functions over the graphon-signal metric space. We then give two applications of this result: 1) a generalization bound for MPNNs, and, 2) the stability of MPNNs to subsampling of graph-signals. Our results apply to any regular enough MPNN on any distribution of graph-signals, making the analysis rather universal.

## 1 Introduction

In recent years, the need to accommodate non-regular structures in data science has brought a boom in machine learning methods on graphs. Graph deep learning (GDL) has already made a significant impact on the applied sciences and industry, with ground-breaking achievements in computational biology [16, 2, 27, 9], and a wide adoption as a general-purpose tool in social media, e-commerce, and online marketing platforms, among others. These achievements pose exciting theoretical challenges: can the success of GDL models be grounded in solid mathematical frameworks? Since the input space of a GDL model is non-Euclidean, i.e., graphs can be of any size and any topology, less is known about GDL than standard neural networks. We claim that contemporary theories of GDL are missing an important ingredient: meaningful notions of metric on the input space, namely, graph similarity measures that are defined for _all graphs of any size_, which respect and describe in some sense the behavior of GDL models. In this paper, we aim at providing an analysis of GDL by introducing such appropriate metrics, using _graphon theory_.

A graphon is an extension of the notion of a graph, where the node set is parameterized by a probability space instead of a finite set. Graphons can be seen as limit objects of graphs, as the number of nodes increases to infinity, under an appropriate metric. One result from graphon theory (that reformulates Szemeredi's regularity lemma from discrete mathematics) states that any sufficiently large graph behaves as if it was randomly sampled from a stochastic block model with a fixed number of classes. This result poses an "upper bound" on the complexity of graphs: while deterministic large graphs may appear to be complex and intricate, they are actually approximately regular and behave random-like.
In this paper we extend this regularity result to an appropriate setting for message passing neural networks (MPNNs), a popular GDL model. Since MPNNs take as input a graph with a signal defined over the nodes (a graph-signal), we extend graphon theory from a theory of graphs to a theory of graph-signals. We define a metric, called the _graph-signal cut distance_, and formalize regularity statements for MPNNs of the following sort.

(1) Any deterministic graph-signal behaves as if it was randomly sampled from a stochastic block model, where the number of blocks only depends on how much we want the graph-signal to look random-like, and not on the graph-signal itself.

(2) If two graph-signals behave as if they were sampled from the same stochastic block model, then any (regular enough) MPNN attains approximately the same value on both.

Formally, (1) is proven by extending Szemeredi's weak regularity lemma to graphon-signals. As a result of this new version of the regularity lemma, we show that the space of graph-signals is a dense subset of the space of graphon-signals, which is shown to be compact. Point (2) is formalized by proving that MPNNs with Lipschitz continuous message functions are Lipschitz continuous mappings from the space of graph-signals to an output space, in the graphon-signal cut distance.

We argue that the above regularity result is a powerful property of MPNNs. To illustrate this, we use the new regularity result to prove two corollaries. First, a generalization bound of MPNNs, showing that if the learned MPNN performs well on the training graph-signals, it is guaranteed to also perform well on test graph-signals. This is shown by first bounding the covering number of the graphon-signal space, and then using the Lipschitzness of MPNNs. Second, we prove that MPNNs are stable to graph-signal subsampling. This is done by first showing that randomly subsampling a graphon-signal produces a graph-signal which is close in cut distance to the graphon-signal, and then using the Lipschitzness of MPNNs.

As opposed to past works that analyze MPNNs using graphon analysis, we do not assume any generative model on the data. Our results apply to any regular enough MPNN on any distribution of graph-signals, making the analysis rather universal.

The problem with graph-signal domains.Since the input space of MPNNs is non-Euclidean, results like universal approximation theorems and generalization bounds are less well developed for MPNNs than Euclidean deep learning models. For example, analysis like in [6] is limited to graphs of fixed sizes, seen as adjacency matrices. The graph metric induced by the Euclidean metric on adjacency matrices is called _edit-distance_. This reduction of the graph problem to the Euclidean case does not describe the full complexity of the problem. Indeed, the edit-distance is defined for weighted graphs, and non-isomorphic simple graphs are always far apart in this metric. This is an unnatural description of the reality of machine learning on graphs, where different large non-isomorphic simple graphs can describe the same large-scale phenomenon and have similar outputs for the same MPNN.

Other papers that consider graphs of arbitrary but bounded size are based on taking the union of the Euclidean edit-distance spaces up to a certain graph size [3]. If one omits the assumption that all graphs are limited by a predefined size, the edit-metric becomes non-compact - a topology too fine to explain the behavior of real MPNNs. For example, two graphs with different number of nodes are always far apart in edit-distance, while most MPNN architectures in practice are not sensitive to the addition of one node to a large graph. In [18], the expressivity of GNNs is analyzed on spaces of graphons. It is assumed that graphons are Lipschitz continuous kernels. The metric on the graphon space is taken as the \(L_{\infty}\) distance between graphons as functions. We claim that the Lipschitz continuity of the graphons in [18], the choice of the \(L_{\infty}\) metric, and the choice of an arbitrary compact subset therein, are not justified as natural models for graphs, and are not grounded in theory. Note that graphon analysis is measure theoretic, and results like the regularity lemma are no longer true when requiring Lipschitz continuity for the graphons. Lastly, in papers like [30, 17, 25, 26], the data is assumed to be generated by one, or a few graphons,
which limits the data distribution significantly. We claim that this discrepancy between theory and practice is an artifact of the inappropriate choices of the metric on the space of graphs, and the choice of a limiting generative model for graphs.

## 2 Background

For \(n\in\mathbb{N}\), we denote \([n]=\{1,\ldots,n\}\). We denote the Lebesgue \(p\) space over the measure space \(\mathcal{X}\) by \(\mathcal{L}^{p}(\mathcal{X})\), or, in short, \(\mathcal{L}^{p}\). We denote by \(\mu\) the standard Lebesgue measure on \([0,1]\). A _partition_ is a sequence \(\mathcal{P}_{k}=\{P_{1},\ldots,P_{k}\}\) of disjoint measurable subsets of \([0,1]\) such that \(\bigcup_{j=1}^{k}P_{j}=[0,1]\). The partition is called _equipartition_ if \(\mu(P_{i})=\mu(P_{j})\) for every \(i,j\in[k]\). We denote the indicator function of a set \(S\) by \(\mathds{1}_{S}\). See Appendix A for more details.

### Message passing neural networks

Most graph neural networks used in practice are special cases of MPNN (see [14] and [10] of a list of methods). MPNNs process graphs with node features, by repeatedly updating the feature at each node using the information from its neighbors. The information is sent between the different nodes along the edges of the graph, and hence, this process is called _message passing_. Each node merges all messages sent from its neighbors using an _aggregation scheme_, where typical choices is to sum, average or to take the coordinate-wise maximum of the messages. In this paper we focus on normalized sum aggregation (see Section 4.1). For more details on MPNNs we refer the reader to Appendix E.

### Szemeredi weak regularity lemma

The following is taken from [12, 24]. Let \(G=\{V,E\}\) be a simple graph with nodes \(V\) and edges \(E\). For any two subsets \(U,S\subset V\), denote the number of edges with one end point at \(U\) and the other at \(S\) by \(e_{G}(U,S)\). Let \(\mathcal{P}=\{V_{1},\ldots,V_{k}\}\) be a partition of \(V\). The partition is called _equipartition_ if \(||V_{i}|-|V_{j}||\leq 1\) for every \(i,j\in[k]\). Given two node set \(U,S\subset V\), if the edges between each pair of classes \(V_{i}\) and \(V_{j}\) were random, we would expect the number of edges of \(G\) connecting \(U\) and \(S\) to be close to the expected value \(e_{\mathcal{P}(U,S)}:=\sum_{i=1}^{k}\sum_{j=1}^{k}\frac{e_{G}(V_{i},V_{j})}{| V_{i}||V_{j}|}\,|V_{i}\cap U|\,|V_{j}\cap S|\). Hence, the _irregularity_, that measures how non-random like the edges between \(\{V_{j}\}_{j=1}^{k}\) are, is defined to be

\[\operatorname{irreg}_{G}(\mathcal{P})=\max_{U,S\subset V}|e_{G}(U,S)-e_{ \mathcal{P}}(U,S)|\,/\,|V|^{2}\,. \tag{1}\]

**Theorem 2.1** (Weak Regularity Lemma [12]).: _For every \(\epsilon>0\) and every graph \(G=(V,E)\), there is an equipartition \(\mathcal{P}=\{V_{1},\ldots,V_{k}\}\) of \(V\) into \(k\leq 2^{c/\epsilon^{2}}\) classes such that \(\operatorname{irreg}_{G}(\mathcal{P})\leq\epsilon\). Here, \(c\) is a universal constant that does not depend on \(G\) and \(\epsilon\)._

Theorem 2.1 asserts that we can represent any large graph \(G\) by a smaller, coarse-grained version of it: the weighted graph \(G^{\epsilon}\) with node set \(V^{\epsilon}=\{V_{1},\ldots,V_{k}\}\), where the edge weight between the nodes \(V_{i}\) and \(V_{j}\) is \(\frac{e_{G}(V_{i},V_{j})}{|V_{i}|,|V_{j}|}\). The "large-scale" structure of \(G\) is given by \(G^{\epsilon}\), and the number of edges between any two subsets of nodes \(U_{i}\subset V_{i}\) and \(U_{j}\subset V_{j}\) is close to the "expected value" \(e_{\mathcal{P}(U_{i},U_{j})}\). Hence, the deterministic graph \(G\) "behaves" as if it was randomly sampled from \(G^{\epsilon}\).

### graphon analysis

A graphon [4, 23] can be seen as a weighted graph with a "continuous" node set, or more accurately, the nodes are parameterized by an atomless standard probability space called the _graphon domain_. Since all such graphon domains are equivalent to \([0,1]\) with the standard Lebesgue measure (up to a measure preserving bijection), we take \([0,1]\) as the node set. The space of graphons \(\mathcal{W}_{0}\) is defined to be the set of all measurable symmetric function \(W:[0,1]^{2}\to[0,1]\), \(W(x,y)=W(y,x)\)
The edge weight \(W(x,y)\) of a graphon \(W\in\mathcal{W}_{0}\) can be seen as the probability of having an edge between the nodes \(x\) and \(y\).

Graphs can be seen as special graphons. Let \(\mathcal{I}_{m}=\{I_{1},\ldots,I_{m}\}\) be an _interval equipartition_: a partition of \([0,1]\) into intervals of equal length. The graph \(G=\{V,E\}\) with adjacency matrix \(A=\{a_{i,j}\}_{i,j=1}^{m}\)_induces_ the graphon \(W_{G}\), defined by \(W_{G}(x,y)=a_{\lceil xm\rceil,\lceil ym\rceil}\)1. Note that \(W_{G}\) is piecewise constant on the partition \(\mathcal{I}_{m}\). We hence identify graphs with their induced graphons. A graphon can also be seen as a generative model of graphs. Given a graphon \(W\), a corresponding random graph is generated by sampling i.i.d. nodes \(\{X_{n}\}\) from he graphon domain, and connecting each pair \(X_{n},X_{m}\) in probability \(W(X_{n},X_{m})\) to obtain the edges of the graph.

Footnote 1: In the definition of \(W_{G}\), the convention is that \(\lceil 0\rceil=1\).

### Regularity lemma for graphons

A simple way to formulate the regularity lemma in the graphon language is via stochastic block models (SBM). A SBM is a piecewise constant graphon, defined on a partition of the graphon domain \([0,1]\). The _number of classes_ of the SBM is defined to be the number of sets in the partition. A SBM is seen as a generative model for graphs, where graphs are randomly sampled from the graphon underlying the SBM, as explained above. Szemeredi weak regularity lemma asserts that for any error tolerance \(\epsilon\), there is a number of classes \(k\), such that any deterministic graph (of any size and topology) behaves as if it was randomly sampled from a SBM with \(k\) classes, up to error \(\epsilon\). Hence, in some sense, every graph is approximately _quasi-random_.

To write the weak regularity lemma in the graphon language, the notion of irregularity (Equation (1)) is extended to graphons. For any measurable \(W:[0,1]^{2}\to\mathbb{R}\) the _cut norm_ is defined to be

\[\|W\|_{\square}=\sup_{U,S\subset[0,1]}\left|\int_{U\times S}W(x,y)dxdy\right|,\]

where \(U,S\subset[0,1]\) are measurable. It can be verified that the irregularity (Equation (1)) is equal to the cut norm of a difference between graphons induced by adequate graphs. The cut metric between two graphons \(W,V\in\mathcal{W}_{0}\) is defined to be \(d_{\square}(W,V)=\|W-V\|_{\square}\). The _cut distance_ is defined to be

\[\delta_{\square}(W,V)=\inf_{\phi\in S_{[0,1]}}\|W-V^{\phi}\|_{\square},\]

where \(S_{[0,1]}\) is the space of measure preserving bijections \([0,1]\to[0,1]\), and \(V^{\phi}(x,y)=V(\phi(x),\phi(y))\) (see Section 3.1 and Appendix A.3 for more details). The cut distance is a pseudo metric on the space of graphons. By considering equivalence classes of graphons with zero cut distance, we can construct a metric space \(\widetilde{\mathcal{W}}_{0}\) for which \(\delta_{\square}\) is a metric. The following version of the weak regularity lemma is from [24, Lemma 7].

**Theorem 2.2**.: _For every graphon \(W\in\mathcal{W}_{0}\) and \(\epsilon>0\) there exists a step graphon \(W^{\prime}\in\mathcal{W}_{0}\) with respect to a partition of at most \(\lceil 2^{\epsilon/\epsilon^{2}}\rceil\) sets such that \(\delta_{\square}(W,W^{\prime})\leq\epsilon\), for some universal constant \(c\)._

The exact definition of a step graphon is given in Definition 3.3. It is possible to show, using Theorem 2.2, that \(\widetilde{\mathcal{W}}_{0}\) is a compact metric space [24, Lemma 8]. Instead of recalling this construction here, we refer to Section 3.4 for the extension of this construction to graphon-signals.

## 3 Graphon-signal analysis

A graph-signal \((G,\mathbf{f})\) is a graph \(G\), that may be weighted or simple, with node set \([n]\), and a signal \(\mathbf{f}\in\mathbb{R}^{n\times k}\) that assigns the value \(f_{j}\in\mathbb{R}^{k}\) for every node \(j\in[n]\). A graphon-signal will be defined in Section 3.1 similarly to a graph-signal, but over the node set \([0,1]\). In this section, we show how to extend classical results in graphon theory to a so called graphon-signal theory. All proofs are given in the appendix.
### The graphon signal space

For any \(r>0\), define the _signal space_

\[\mathcal{L}_{r}^{\infty}[0,1]:=\{f\in\mathcal{L}^{\infty}[0,1]\ |\ \forall x\in[0,1],\ \ |f(x)|\leq r\}. \tag{2}\]

We define the following "norm" on \(\mathcal{L}_{r}^{\infty}[0,1]\) (which is not a vector space).

**Definition 3.1** (Cut norm of a signal).: _For a signal \(f:[0,1]\to\mathbb{R}\), the cut norm \(\|f\|_{\square}\) is defined as_

\[\|f\|_{\square}:=\sup_{S\subseteq[0,1]}\bigg{|}\int_{S}f(x)d\mu(x)\bigg{|}, \tag{3}\]

_where the supremum is taken over the measurable subsets \(S\subset[0,1]\)._

In Appendix A.2 we prove basic properties of signal cut norm. One important property is the equivalence of the signal cut norm to the \(L_{1}\) norm

\[\forall f\in\mathcal{L}_{r}^{\infty}[0,1],\quad\|f\|_{\square}\leq\|f\|_{1} \leq 2\|f\|_{\square}.\]

Given a bound \(r\) on the signals, we define the space of _graphon-signals_ to be the set of pairs \(\mathcal{WL}_{r}:=\mathcal{W}_{0}\times\mathcal{L}_{r}^{\infty}[0,1]\). We define the _graphon-signal cut norm_, for measurable \(W,V:[0,1]^{2}\to\mathbb{R}\) and \(f,g:[0,1]\to\mathbb{R}\), by

\[\|(W,f)\|_{\square}=\|W\|_{\square}+\|f\|_{\square}.\]

We define the _graphon-signal cut metric_ by \(d_{\square}\big{(}(W,f),(V,g)\big{)}=\|(W,f)-(V,g)\|_{\square}\).

We next define a pseudo metric that makes the space of graphon-signals a compact space. Let \(S^{\prime}_{[0,1]}\) be the set of measurable measure preserving bijections between co-null sets of \([0,1]\), namely,

\[S^{\prime}_{[0,1]}=\{\phi:A\to B\ |\ A,B\ \text{co-null in}\ [0,1],\ \text{ and }\ \forall S\in A,\ \mu(S)=\mu(\phi(S))\},\]

where \(\phi\) is a measurable bijection and \(A,B,S\) are measurable. For \(\phi\in S^{\prime}_{[0,1]}\), we define \(W^{\phi}(x,y):=W(\phi(x),\phi(y))\), and \(f^{\phi}(z)=f(\phi(z))\). Note that \(W^{\phi}\) and \(f^{\phi}\) are only define up to a null-set, and we arbitrarily set \(W,W^{\phi},f\) and \(f^{\phi}\) to \(0\) in their respective null-sets, which does not affect our analysis. Define the _cut distance_ between two graphon-signals \((W,f),(V,g)\in\mathcal{WL}_{r}\) by

\[\delta_{\square}\big{(}(W,f),(V,g)\big{)}=\inf_{\phi\in S^{\prime}_{[0,1]}}d _{\square}\big{(}(W,f),(V,g)^{\phi}\big{)}. \tag{4}\]

Here, \((V,g)^{\phi}:=(V^{\phi},g^{\phi})\). More details on this construction are given in Appendix A.3.

The graphon-signal cut distance \(\delta_{\square}\) is a pseudo-metric, and can be made into a metric by introducing the equivalence relation: \((W,f)\sim(V,g)\) if \(\delta_{\square}((W,f),(V,g))=0\). The quotient space \(\widetilde{\mathcal{WL}_{r}}:=\mathcal{WL}_{r}/\sim\) of equivalence classes \([(W,f)]\) of graphon-signals \((W,f)\) is a metric space with the metric \(\delta_{\square}([(W,f)],[(V,g)])=\delta_{\square}((W,f),(V,g))\). By abuse of terminology, we call elements of \(\widetilde{\mathcal{WL}_{r}}\) also graphon-signals. A graphon-signal in \(\widetilde{\mathcal{WL}_{r}}\) is defined irrespective of a specific "indexing" of the nodes in \([0,1]\).

### Induced graphon-signals

Any graph-signal can be identified with a corresponding graphon-signal as follows.

**Definition 3.2**.: _Let \((G,\mathbf{f})\) be a graph-signal with node set \([n]\) and adjacency matrix \(A=\{a_{i,j}\}_{i,j\in[n]}\). Let \(\{I_{k}\}_{k=1}^{n}\) with \(I_{k}=[(k-1)/n,k/n)\) be the equipartition of \([0,1]\) into \(n\) intervals. The graphon-signal \((W,f)_{(G,\mathbf{f})}=(W_{G},f_{\mathbf{f}})\) induced by \((G,\mathbf{f})\) is defined by_

\[W_{G}(x,y)=\sum_{i,j=1}^{n}a_{ij}\mathds{1}_{I_{i}}(x)\mathds{1}_{I_{j}}(y), \quad\text{ and }\quad f_{\mathbf{f}}(z)=\sum_{i}^{n}f_{i}\mathds{1}_{I_{i}}(z).\]
We denote \((W,f)_{(G,\mathbf{f})}=(W_{G},f_{\mathbf{f}})\). We identify any graph-signal with its induced graphon-signal. This way, we define the cut distance between a graph-signal and a graphon-signal. As before, the cut distance between a graph-signal \((G,\mathbf{f})\) and a graphon-signal \((W,g)\) can be interpreted as how much the deterministic graph-signal \((G,\mathbf{f})\) "looks like" it was randomly sampled from \((W,g)\).

### graphon-signal regularity lemma

To formulate our regularity lemma, we first define spaces of step functions.

**Definition 3.3**.: _Given a partition \(\mathcal{P}_{k}\), and \(d\in\mathbb{N}\), we define the space \(\mathcal{S}^{d}_{\mathcal{P}_{k}}\) of step functions of dimension \(d\) over the partition \(\mathcal{P}_{k}\) to be the space of functions \(F:[0,1]^{d}\to\mathbb{R}\) of the form_

\[F(x_{1},\ldots,x_{d})=\sum_{j=(j_{1},\ldots,j_{d})\in[k]^{d}}c_{j}\prod_{l=1}^{ d}\mathds{1}_{P_{j_{l}}}(x_{l}), \tag{5}\]

_for any choice of \(\{c_{j}\in\mathbb{R}\}_{j\in[k]^{d}}\)._

We call any element of \(\mathcal{W}_{0}\cap\mathcal{S}^{2}_{\mathcal{P}_{k}}\) a _step graphon_ with respect to \(\mathcal{P}_{k}\). A step graphon is also called a _stochastic block model (SBM)_. We call any element of \(\mathcal{L}^{\infty}_{r}[0,1]\cap\mathcal{S}^{1}_{\mathcal{P}_{k}}\) a _step signal_. We also call \([\mathcal{WL}_{r}]_{\mathcal{P}_{k}}:=(\mathcal{W}_{0}\cap\mathcal{S}^{2}_{ \mathcal{P}_{k}})\times(\mathcal{L}^{\infty}_{r}[0,1]\cap\mathcal{S}^{1}_{ \mathcal{P}_{k}})\) the space of SBMs with respect to \(\mathcal{P}_{k}\).

In Appendix B.2 we give a number of versions of the graphon-signal regularity lemma. Here, we show one version in which the partition is fixed regardless of the graphon-signal.

**Theorem 3.4** (Regularity lemma for graphon-signals - equipartition).: _For any \(c>1\), and any sufficiently small \(\epsilon>0\), for every \(n\geq 2^{\lceil 2c/\epsilon^{2}\rceil}\) and every \((W,f)\in\mathcal{WL}_{r}\), there exists a step graphon-signal \((W_{n},f_{n})\in[\mathcal{WL}_{r}]_{\mathcal{I}_{n}}\) such that_

\[\delta_{\square}\big{(}(W,f),(W_{n},f_{n})\big{)}\leq\epsilon, \tag{6}\]

_where \(\mathcal{I}_{n}\) is the equipartition of \([0,1]\) into \(n\) intervals._

By identifying graph-signals with their induced graphon-signals, (Equation (6)) shows that the space of graph-signals is dense in the space of graphon-signals with cut distance. Similarly to the classical case, Theorem 3.4 is interpreted as follows. While deterministic graph-signals may seem intricate and complex, they are actually regular, and "look like" random graph-signals that were sampled from SBMs, where the number of blocks of the SBM only depends on the desired approximation error between the SBM and the graph-signal, and not on the graph-signal itself.

### Compactness of the graphon-signal space and its covering number

We prove that \(\widetilde{\mathcal{WL}_{r}}\) is compact using Theorem 3.4, similarly to [24, Lemma 8]. Moreover, we can bound the number of balls of radius \(\epsilon\) required to cover \(\widetilde{\mathcal{WL}_{r}}\).

**Theorem 3.5**.: _The metric space \((\widetilde{\mathcal{WL}_{r}},\delta_{\square})\) is compact. Moreover, given \(r>0\) and \(c>1\), for every sufficiently small \(\epsilon>0\), the space \(\widetilde{\mathcal{WL}_{r}}\) can be covered by_

\[\kappa(\epsilon)=2^{k^{2}} \tag{7}\]

_balls of radius \(\epsilon\), where \(k=\lceil 2^{2c/\epsilon^{2}}\rceil\)._

The Proof of Theorem 3.5 is given in Appendix C. This is a powerful result - the space of arbitrarily large graph-signals is dense in the "small" space \(\widetilde{\mathcal{WL}_{r}}\). We will use this property in Section 4.3 to prove a generalization bound for MPNNs.
### Graphon-signal sampling lemmas

In this section we prove that randomly sampling a graphon signal produces a graph-signal that is close in cut distance to the graphon signal. Let us first describe the sampling setting. More details on the construction are given in Appendix D.1. Let \(\Lambda=(\lambda_{1},\ldots\lambda_{k})\in[0,1]^{k}\) be \(k\) independent uniform random samples from \([0,1]\), and \((W,f)\in\mathcal{WL}_{r}\). We define the _random weighted graph_\(W(\Lambda)\) as the weighted graph with \(k\) nodes and edge weight \(w_{i,j}=W(\lambda_{i},\lambda_{j})\) between node \(i\) and node \(j\). We similarly define the _random sampled signal_\(f(\Lambda)\) with value \(f_{i}=f(\lambda_{i})\) at each node \(i\). Note that \(W(\Lambda)\) and \(f(\Lambda)\) share the sample points \(\Lambda\). We then define a random simple graph as follows. We treat each \(w_{i,j}=W(\lambda_{i},\lambda_{j})\) as the parameter of a Bernoulli variable \(e_{i,j}\), where \(\mathbb{P}(e_{i,j}=1)=w_{i,j}\) and \(\mathbb{P}(e_{i,j}=0)=1-w_{i,j}\). We define the _random simple graph_\(\mathbb{G}(W,\Lambda)\) as the simple graph with an edge between each node \(i\) and node \(j\) if and only if \(e_{i,j}=1\).

We note that, given a graph signal \((G,\mathbf{f})\), sampling a graph-signal from \((W,f)_{(G,\mathbf{f})}\) is equivalent to subsampling the nodes of \(G\) independently and uniformly (with repetitions), and considering the resulting subgraph and subsignal. Hence, we can study the more general case of sampling a graphon-signal, where graph-signal sub-sampling is a special case. We now extend [23, Lemma 10.16], which bounds the cut distance between a graphon and its sampled graph, to the case of a sampled graphon-signal.

**Theorem 3.6** (Sampling lemma for graphon-signals).: _Let \(r>1\). There exists a constant \(K_{0}>0\) that depends on \(r\), such that for every \(k\geq K_{0}\), every \((W,f)\in\mathcal{WL}_{r}\), and for \(\Lambda=(\lambda_{1},\ldots\lambda_{k})\in[0,1]^{k}\) independent uniform random samples from \([0,1]\), we have_

\[\mathbb{E}\bigg{(}\delta_{\square}\Big{(}\big{(}W,f\big{)},\big{(}W(\Lambda),f(\Lambda)\big{)}\Big{)}\bigg{)}<\frac{15}{\sqrt{\log(k)}},\]

_and_

\[\mathbb{E}\bigg{(}\delta_{\square}\Big{(}\big{(}W,f\big{)},\big{(}\mathbb{G}( W,\Lambda),f(\Lambda)\big{)}\Big{)}\bigg{)}<\frac{15}{\sqrt{\log(k)}}.\]

The proof of Theorem 3.6 is given in Appendix D.2

## 4 Graphon-signal analysis of MPNN

In this section, we propose utilizing the compactness of the graphon-signal space under cut distance, and the sampling lemma, to prove regularity results for MPNNs, uniform generalization bounds, and stability to subsampling theorems.

### MPNN on graphon signals

Next, we define MPNNs on graphon-signals, in such a way that the application of a MPNN on an induced graphon-signal is equivalent to applying the MPNN on the graph-signal and then inducing it. A similar construction was presented in [26], for average aggregation, but we use normalized sum aggregation.

At each layer, we define the message function \(\Phi(x,y)\) as a linear combination of simple tensors as follows. Let \(K\in\mathbb{N}\). For every \(k\in[K]\), let \(\xi_{\mathrm{r}}^{k},\xi_{\mathrm{t}}^{k}:\mathbb{R}^{d}\to\mathbb{R}^{p}\) be Lipschitz continuous functions that we call the _receiver_ and _transmitter message functions_ respectively. Define the _message function_\(\Phi:\mathbb{R}^{2d}\to\mathbb{R}^{p}\) by

\[\Phi(a,b)=\sum_{k=1}^{K}\xi_{\mathrm{r}}^{k}(a)\xi_{\mathrm{t}}^{k}(b).\]

Given a signal \(f\), define the _message kernel_\(\Phi_{f}:[0,1]^{2}\to\mathbb{R}^{p}\) by

\[\Phi_{f}(x,y)=\Phi(f(x),f(y))=\sum_{k=1}^{K}\xi_{\mathrm{r}}^{k}(f(x))\xi_{ \mathrm{t}}^{k}(f(y)).\]
We see the \(x\) variable of \(\Phi_{f}(x,y)\) as the receiver of the message, and \(y\) as the transmitter. Define the aggregation of a message kernel \(Q:[0,1]^{2}\to\mathbb{R}^{p}\), with respect to the graphon \(W\in\mathcal{W}_{0}\), to be the signal \(\mathrm{Agg}(W,Q)\in\mathcal{L}_{r}^{\infty}[0,1]\), defined by

\[\mathrm{Agg}(W,Q)(x)=\int_{0}^{1}W(x,y)Q(x,y)dy,\]

for an appropriate \(r>0\). A _message passing layer (MPL)_ takes the form \(f^{(t)}\mapsto\mathrm{Agg}(W,\Phi_{f^{(t)}}^{(t+1)})\), where \(f^{(t)}\) is the signal at layer \(t\). Each MPL is optionally followed by an _update layer_, which updates the signal pointwise via \(f^{(t+1)}=\mu^{(t+1)}\big{(}f^{(t)}(x),\mathrm{Agg}(W,\Phi_{f^{(t)}}^{(t+1)})( x)\big{)}\), where \(\mu^{(t+1)}\) is a learnable mapping called the _update function_. A MPNN is defined by choosing the number of layers \(T\), and defining message and update functions \(\{\mu^{\epsilon},(\xi_{\mathrm{r}}^{k}),(\xi_{\mathrm{t}}^{k})\}_{k\in[K],t \in[T]}\). A MPNN only modifies the signal, and keeps the graph/graphon intact. We denote by \(\Theta_{t}(W,f)\) the output of the MPNN applied on \((W,f)\in\mathcal{WL}_{r}\) at layer \(t\in[T]\). More details on the construction are given in Appendix E.1.

The above construction is rather general. Indeed, it is well known that many classes of functions \(F:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{C}\) (e.g., \(L^{2}\) functions) can be approximated by (finite) linear combinations of simple tensors \(F(a,b)\approx\sum_{k=1}^{K}\xi_{1}^{k}(a)\xi_{2}^{k}(b)\). Hence, message passing based on general message functions \(\Phi:\mathbb{R}^{2d}\to\mathbb{R}^{p}\) can be approximated by our construction. Moreover, many well-known MPNNs can be written using our formulation with a small \(K\), e.g., [29, 34] and spectral convolutional networks [8, 19, 21], if we replace the aggregation in these method with normalized sum aggregation.

In Appendix E.1 we show that for any graph-signal \((G,\mathbf{f})\), we have \(\Theta_{t}(W,f)_{(G,\mathbf{f})}=(W,f)_{\Theta_{t}(G,\mathbf{f})}\), where the MPNN on a graph-signal is defined with normalized sum aggregation

\[\big{(}\mathrm{Agg}(G,\Phi_{\mathbf{f}})\big{)}_{i}=\frac{1}{n}\sum_{j\in[n]} a_{i,j}(\Phi_{\mathbf{f}})_{i,j}.\]

Here, \(n\) is the number of nodes, and \(\{a_{i,j}\}_{i,j\in[n]}\) is the adjacency matrix of \(G\). Hence, we may identify graph-signals with their induced graphon-signals when analyzing MPNNs.

### Lipschitz continuity of MPNNs

We now show that, under the above construction, MPNNs are Lipschitz continuous with respect to cut distance.

**Theorem 4.1**.: _Let \(\Theta\) be a MPNN with \(T\) layers. Suppose that there exist constants \(L,B>0\) such that for every layer \(t\in[T]\), every \(\mathrm{y}\in\{\mathrm{t},\mathrm{r}\}\) and every \(k\in[K]\),_

\[\big{|}\mu^{t}(0)\big{|}\,,\ \big{|}^{t}\xi_{\mathrm{y}}^{k}(0)\big{|}\leq B, \quad\text{and}\quad L_{\mu^{t}},\ L_{\xi_{\mathrm{y}}^{k}}<L,\]

_where \(L_{\mu^{t}}\) and \(L_{\cdot\xi_{\mathrm{y}}^{k}}\) are the Lipschitz constants of \(\mu^{t}\) and \({}^{t}\xi_{\mathrm{y}}^{k}\). Then, there exists a constant \(L_{\Theta}\) (that depends on \(T,K,B\) and \(L\)) such that for every \((W,f),(V,g)\in\mathcal{WL}_{r}\),_

\[\|\Theta(W,f)-\Theta(V,g)\|_{\square}\leq L_{\Theta}\Big{(}\|f-g\|_{\square}+ \|W-V\|_{\square}\Big{)}.\]

The constant \(L_{\Theta}\) depends exponentially on \(T\), and polynomially on \(K,B\) and \(L\). For formulas of \(L_{\Theta}\), under different assumptions on the hypothesis class of the MPNN, we refer to Appendix F.

### A generalization theorem for MPNN

In this section we prove a uniform generalization bound for MPNNs. For background on generalization analysis, we refer the reader to Appendix G.1. While uniform generalization bounds are considered a classical approach in standard neural networks, the approach is less developed in the case of MPNNs. For some works on generalization theorems of MPNNs, see [31, 13, 22, 26, 28].
When a MPNN is used for classification or regression, \(\Theta_{T}\) is followed by global pooling. Namely, for the output signal \(g:[0,1]\to\mathbb{R}^{p}\), we return \(\int g(x)dx\in\mathbb{R}^{p}\). This is then typically followed by a learnable mapping \(\mathbb{R}^{p}\to\mathbb{R}^{C}\). In our analysis, we see this mapping as part of the loss, which can hence be learnable. The combined loss is assumed to be Lipschitz continuous2.

Footnote 2: We note that loss functions like cross-entropy are not Lipschitz continuous. However, the composition of cross-entropy on softmax is Lipschitz, which is the standard way of using cross-entropy.

We model the ground truth classifier into \(C\) classes as a piecewise constant function \(\mathcal{C}:\widetilde{\mathcal{W}\mathcal{L}_{r}}\to\{0,1\}^{C}\), where the sets of different steps in \(\widetilde{\mathcal{W}\mathcal{L}_{r}}\) are Borel measurable sets, correspond to different classes. We consider an arbitrary probability Borel measure \(\nu\) on \(\widetilde{\mathcal{W}\mathcal{L}_{r}}\) as the data distribution. More details on the construction are given in Appendix G.2.

Let \(\operatorname{Lip}(\widetilde{\mathcal{W}\mathcal{L}_{r}},L_{1})\) be the space of Lipschitz continuous mappings \(\Upsilon:\widetilde{\mathcal{W}\mathcal{L}_{r}}\to\mathbb{R}^{C}\) with Lipschitz constant \(L_{1}\). By Theorem 4.1, we may assume that our hypothesis class of MPNNs is a subset of \(\operatorname{Lip}(\widetilde{\mathcal{W}\mathcal{L}_{r}},L_{1})\) for some given \(L_{1}\). Let \(\mathbf{X}=(X_{1},\dots,X_{N})\) be independent random samples from the data distribution \((\widetilde{\mathcal{W}\mathcal{L}_{r}},\nu)\). Let \(\Upsilon_{\mathbf{X}}\) be a model that may depend on the sampled data, e.g., via training. Let \(\mathcal{E}\) be a Lipschitz continuous loss function3 with Lipschitz constant \(L_{2}\). For every function \(\Upsilon\) in the hypothesis class \(\operatorname{Lip}(\widetilde{\mathcal{W}\mathcal{L}_{r}},L_{1})\) (i.e. \(\Upsilon_{\mathbf{X}}\)), define the _statistical risk_

Footnote 3: The loss \(\mathcal{E}\) may have a learnable component (that depends on the dataset \(\mathbf{X}\)), as long as the total Lipschitz bound of \(\mathcal{E}\) is \(L_{2}\).

\[\mathcal{R}(\Upsilon)=\mathbb{E}\big{(}\mathcal{E}(\Upsilon, \mathcal{C})\big{)}=\int\mathcal{E}(\Upsilon(x),\mathcal{C}(x))d\nu(x). \tag{8}\]

We define the empirical risk

\[\hat{\mathcal{R}}(\Upsilon_{\mathbf{X}},\mathbf{X})=\frac{1}{N} \sum_{i=1}^{N}\mathbb{E}\big{(}\Upsilon_{\mathbf{X}}(X_{i}),\mathcal{C}(X_{i} )\big{)}. \tag{9}\]

**Theorem 4.2** (MPNN generalization theorem).: _Consider the above classification setting, and let \(L=L_{1}L_{2}\). Let \(X_{1},\dots,X_{N}\) be independent random samples from the data distribution \((\widetilde{\mathcal{W}\mathcal{L}_{r}},\nu)\). Then, for every \(p>0\), there exists an event \(\mathcal{U}^{p}\subset\widetilde{\mathcal{W}\mathcal{L}_{r}}^{N}\), with probability_

\[\nu^{N}(\mathcal{U}^{p})\geq 1-Cp-2\frac{C^{2}}{N},\]

_in which_

\[\Big{|}\mathcal{R}(\Upsilon_{\mathbf{X}})-\hat{\mathcal{R}}( \Upsilon_{\mathbf{X}},\mathbf{X})\Big{|}\leq\xi^{-1}(N/2C)\Big{(}2L+\frac{1}{ \sqrt{2}}\big{(}L+\mathcal{E}(0,0)\big{)}\big{(}1+\sqrt{\log(2/p)}\big{)} \Big{)}, \tag{10}\]

_where \(\xi(\epsilon)=\frac{\kappa(\epsilon)^{2}\log(\kappa(\epsilon))}{\epsilon^{2}}\), \(\kappa\) is the covering number of \(\widetilde{\mathcal{W}\mathcal{L}_{r}}\) given in (Equation (7)), and \(\xi^{-1}\) is the inverse function of \(\xi\)._

The theorem is proved in Appendix G.4. Note that the term \(\xi^{-1}(N/2C)\) in Equation (10) decreases to zero as the size of the training set \(N\) goes to infinity.

### Stability of MPNNs to graph-signal subsampling

When working with very large graphs, it is often the practice to subsample the large graph, and apply a MPNN to the smaller subsampled graph [15, 5, 7]. Here, we show that such an approach is justified theoretically. Namely, any (Lipschitz continuous) MPNN has approximately the same outcome on the large graph and its subsampled version.

Transferability analysis [20, 30, 17, 25] often studies a related setting. Namely, it is shown that a MPNN applied on a randomly sampled graph \(G\) approximates the MPNN on the graphon \(W\) from which the graph is sampled. However, previous analyses assumed that the generating graphon \(W\) has metric properties. Namely, it is assumed that there is some probability metric space \(\mathcal{M}\) which
is the graphon domain, and the graphon \(W:\mathcal{M}\times\mathcal{M}\to[0,1]\) is Lipschitz continuous with respect to \(\mathcal{M}\), where the dimension of \(\mathcal{M}\) affects the asymptotics. This is an unnatural setting, as general graphons are only assumed to be measurable, not continuous. Constraining the construction to Lipschitz continuous graphons with a uniformly bounded Lipschitz constant only accounts for a small subset of \(\mathcal{W}\mathcal{L}_{r}\), and, hence, limits the analysis significantly. In comparison, our analysis applies to any graphon-signal in \(\mathcal{W}\mathcal{L}_{r}\).

**Theorem 4.3**.: _Consider the setting of Theorem 4.2, and let \(\Theta\) be a MPNN with Lipschitz constant \(L\). Denote_

\[\Sigma=\big{(}W,\Theta(W,f)\big{)},\quad\text{and}\quad\Sigma(\Lambda)=\Big{(} \mathbb{G}(W,\Lambda),\Theta\big{(}\mathbb{G}(W,\Lambda),f(\Lambda)\big{)} \Big{)}.\]

_Then_

\[\mathbb{E}\Big{(}\delta_{\square}\big{(}\Sigma,\Sigma(\Lambda)\big{)}\Big{)}< \frac{15}{\sqrt{\log(k)}}L.\]

## 5 Discussion

We presented an extension of graphon theory to a graphon-signal theory. Especially, we extended well-known regularity, compactness, and sampling lemmas from graphons to graphon-signals. We then showed that the normalized sum aggregation of MPNNs is in some sense compatible with the graphon-signal cut distance, which leads to the Lipschitz continuity of MPNNs with respect to cut distance. This then allowed us to derive generalization and sampling theorems for MPNNs. The strength of our analysis is in its generality and simplicity- it is based on a natural notion of graph similarity, that allows studying the space of _all_ graph-signals, it applies to any graph-signal data distribution, and does not impose any restriction on the number of parameters of the MPNNs, only to their regularity through the Lipschitzness of the message functions. The main limitation of the theory is the very slow asymptotics of the generalization and subsampling theorems. This follows the fact that the covering number of the compact space \(\widetilde{\mathcal{W}\mathcal{L}_{r}}\) grows faster than the covering number of any finite-dimensional compact space. Yet, we believe that our work can serve as a point of departure for future works, that 1) will model subspaces of \(\widetilde{\mathcal{W}\mathcal{L}_{r}}\) of lower complexity, which approximate the support of the data-distribution in real-life settings of graph machine learning, and, 2) will lead to improved asymptotics.

### Acknowledgments

I would like to thank Manish Krishan Lal for many interesting discussions on optimization, geometric deep learning, and graphon analysis, during his internship in my lab.
