A graphon-signal analysis of graph neural networks
Authors: Ron Levie
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural network
graphon
generalization
stability
sampling
Szemerédi regularity lemma
TL;DR: We develop a metric on the input space of message passing neural networks that allows deriving generalization and stability to subsampling theorems

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.

A graphon-signal analysis of graph neural networks
Ron Levie
Faculty of Mathematics
Technion Israel Institute of Technology
levieron@teehhion.cm ac.
Abstract
We present approach for amalyzing message passing graph neural networks (MPNNs) based on an extension of graphon analysis to a so called graphon-signal analysis. MPNN is function that takes a graph and a signal 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 similarity measure, called the graphon-signa cut distance, which makes the space of all graph-signals a dense subset of 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 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 on any distribution of graph-signals, making the analysis rather universal.
Our results apply any regular enough MPNN
Introduction
In recent years, the need accommodate non-regular structures in data science has brought boom in machine learning methods on graphs. Graph deep learning (GDL) has already made significant impact on the applied sciences and industry, with brouud-breaking achievements in computational biology [2, 10, 17, 28], and a wide adoption as 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 GDL model is -ucliied,,,,, 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.
graphon is extension of the notion of graph, where the node set parameterized by 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 metrie. One result from graphon theory (that reformulates Szemerédi's 's regularity lemma from discrete mathematics) states that any sufficiently large graph behaves if was randomly sampled from a stochastic block model with fixed number of classes.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Figure I: Illustration of the graph-signal cut distance. Left: a stochastic block model (SBM) with a signal. The color of the block represents the value of the signal at this block. The thickness of the edges between the blocks (including self-loops) represents the probability/density of edges between the blocks. Middle: a small graph-signal which looks like was sampled from the SMB. The color of the nodes represents the signal values. Right: a large graph-signal which looks like was sampled from the SMB. In graphon-signal cut distance, these two graph-signals are close each other.
This result poses an "upper bound" on the complexity of graphs: while deterministic large graphs may appear to be complex and intricate, they 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), popular GDL model. Since MPNNs take as input graph with signal defined over the nodes (a graph-signal we extend graphon theory from theory of graphs to a theory of graph-signals. We define metric, called the graph-signal cut distance (see Figure 1 for illustration), and formalize regularity statements for MPNNs of the following sort.
(1) Any deterministic graph-signal behaves as it was randomly sampled from a stochastic block model, where the number of blocks only depends on how much want the graph- signal to look random-like, and not on the graph-signal itself.
(2) If two graph-signals behave if they were sampled from the same stochastic block model, then any (regular enough) MPNN attains approximately the same value on both.
Formally, (I) is proven by extending Szemerédi's 's weak regularity lemma to graphon graphon-signals, As result of this new version of the regularity lemma, we show that the space of graph-signal 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-signall to output space, in the graphon-signa cut distance.
We argue that the above regularity result is 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 also perform well on test soph-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-signa produces a graph-signal which close cut distance to the graphon-signal signal, and then using the Lipschitzness of MPNNs.
As opposed 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. We note that past works about generalization in GNNs [14, 23, 26, 30] consider special assumptions on the data distribution, and often on the MPNN model. Our work provides upper bounds under no assumptions on the data distribution, and only mild Lipschitz continuity assumptions on the message passing functions. Hence, our theory bounds the generalization error when all special assumptions (that are often simplistic) from other papers are not met. We show that when all assumptions fail, MPNNs still have generalization and sampling guarantees, albeit much slower ones. See Table This is also true for past sampling theorems, e.g.. [18, 22, 27, 31, 32].
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 adjacency matrices. The graph metric induced by the Euclidean metric on
2

---

adjacency matrices is called edit- diftaniistece. This reduction of the graph problem to the Euclidean case does not describe the full complexity of the problem. Indeed, the edit-distance 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 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 [19], the expressivity of GNNs is analyzed on assumed that graphons are Lipschitz continuous kernels. The metric on the
spaces of graphons. graphon space is taken as the Toe distance hetween graphons as functions. We claim that the Lipschitz continuity of the graphons in [19], the choice of the I. 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 [18, 26, 27, 31J, 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 E N, we denote [n]] = { ,I....,77 n2). We denote the Lebesgue p space over the measure space X' by (x))), in short, LP. We denote by μ the standard Lebesgue measure on [0, 1]. A partition is a sequence PA- = (P....., } of disjoint measurable subsets of [0, 1] such that - P, [0. 1]. The partition is called equipartition if ((P.) = μ(P;) for every i, E [k]. We denote the indicator function of set S by lls. See Appendix A for more details. We summarize our notations in Appendix I.
2.1 Message passing neural networks
Most graph neural networks used in practice are special cases of MPNN (see [15] and [11] of 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 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-wisd 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.
2.2 Szemerédi weak regularity lemma
The following is taken from [13, 25). Let G= (V, be a simple graph with nodes V and edges E. For any two subsets U, S C V, denote the number of edges with one end point at U and the other at by eg (U, S). Let P = [Vi..... Vx be a partition of V. The partition is called equipartition || | < 1 for every i,j [k). Given two node set U, S V, if the edges between each pair of classes Vi2 and V, were random, we would expect the number of edges of G connecting U and S to be close the expected value EP(U,S) == Σ Σj= ec(V.VV)
TWIT \V: n (UVIIV, nS. Hence, the irregularity, that measures how non-random like the edges between (V:) are, is defined to be
irrego (P)
max (ea(U, -CPUUS))) ? U,SCV
Theorem 2.1 (Weak Regularity Lemma [13]). For every > O and every graph G = (V, E), there is an equipartition P = (Vi,... Vi of V into k S 20/²² classes such that (rrega(P) S 6. Here, e is universal constant that does not depend G and e.
3

---

Theorem 2.1 asserts that we can represent any large graph G by smaller, coarse grained version of it: the weighted graph G with node set V (V..... ..... Vi where the edge weight between the nodes Vi and V is eo(V).)) |Val.Vv The "large-scale" structure of G' is given by G", and the number of edges between any two subsets of nodes U2 V; and U3 C V3 is close to the "expected value" (p(U..U)) Hence, the deterministic graph G "behaves" as if it was randomly sampled from G
2.3 Graphon analysis
A graphon [4, 24] 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 measure preserving bijection), we take [0, 1] as the node set. The space of graphons Wo is defined to be the set of all measurable symmetric function W [0, 1] + [0, 1]. W (a, y) W (yy, x). The edge weight W (az, y) of a graphon W E Wo can be seen as the probability of having an edge between the nodes and y.
Graphs can be seen as special graphons. Let Im = (I....., Im] be an interval equipartition: a partition of [0, 1] into intervals of equal length. The graph G = EV with adjacency matrix mm ft induces the graphon We, defined by Wc () a [am]]_fmm] ! Note that We is {as.g
piecewise constant on the partition I, We hence identify graphs with their induced graphons. A graphon can also be seen as a generative model of graphs. Given graphon W, a corresponding random graph is generated by sampling i.i.d. nodes { {Xn) J from he graphon domain, and connecting each pair Xn, Xm in probability W W(X,, Xm) to obtain the edges of the graph.
2.4 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 generative model for graphs, where graphs are randomly sampled from the graphon underlying the SBM, as explained above. Szemerédi weak regularity lemma asserts that for any error tolerance c, there is number of classes such that any deterministic graph (of any size and topology) behaves as if it was randomly sampled from a SBM with & classes, up to error c. Hence, in some sense, every graph is approximately quasi-randon random.
To write the weak regularity lemma in the graphon language, the notion of irregularity (1) is extended to graphons. For any measurable W [0, 1]2 - lR the norm is defined to be
I W(I, 4)drd
| = sup U, Juxs
where S C [0, 1] are measurable. can be verified that the irregularity (1) is equal to the cut norm of difference between graphons induced by adequate graphs. The cut metric between two graphons W. V Wo is defined to be do(W.V) V) I[ Vllo. The cut distance is defined to be
(W V) inf |W - -V
4E8p.1
where Sio.1] is the space of measure preserving bijections [0, + VV((z,, o(y)) (see Section 3.1 and Appendix A.3 for more details). The cut distance is pseudo metric on the space of graphons. By considering equivalence classes of graphons with zero cut distance, we can construct a metric space Wy for which on is a metric. The following version of the weak regularity lemma is from [25, Lemma 7].
[0, and (* v)
Theorem 2.2. For every graphon W E Wo and E > 0 there exists a step graphon W' E Wo with respect to partition of at most [20/+²] sets such that (W, W') S 6, for some universal constant c.
The exact definition of a step graphon given in Definition 3.3. It is possible to show, using Theorem 2.2, that W/ is compact metric space [25, Lemma 8]. Instead of recalling this construction here, we refer to Section 3.4 for the extension of this construction to graphon-signals.
In the definition of We. the convention is that [0] = 1.

---

Graphon-signal analysis
graph-signal (G, is a graph G, that may be weighted or simple, with node set [n], and signal f E ggn* that assigns the value fy E I& for every node j E [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 so called graphon-signal theory. All proofs are given in the appendix.
3.1
The graphon signal space
For any r > 0, define the signal space
1, 1] (f [00 1] Yx [0, If(z)) sr).
(2)
We define the following "norm" on L, [0. 1| (which not a vector space).
Definition 3.1 (Cut norm of a signal), For a signal f f: :0 R. the cut norm [i is defined as
/ [())d((x))
V/
sup sc(o.1]
where the supremum is taken over the measurable subsets S [0, 1].
In Appendix A.2 prove basic properties of signal cut norm. One important property is the equivalence of the signal cut norm to the Ln norm
1]. IIflln S 11fll2 S 2ll
Given bound on the signals, we define the space of graphon- to be the set of pairs WC, == Wo x L [0, 1]. We define the gruphon-signal cut norm, for measurable W, V [0, 112 + R and f.g [0, 1] + R, by
IIW, lla = l|Wl|a + I1/llo-
We define the graphon-signal cut metric by d= ((W,, (V, = [[(W, (V. We next define a pscudo metric that makes the space of graphon- signals a compact space. Let S (0.11] be the set of measurable measure preserving bijections between co-null sets of [o, 1], namely,
S/o11 (Ø A + B A, B co-null in [0, 1], and AS E A, p(S) (()()))}
where / is a measurable bijection and A, B, S are measurable. For / E Soo.1j. we define W*,,, y) = ((((z),(())) and (z) f()(2)) Note that W and f only defined up to null-set, and we arbitrarily set W, W., and I to 0 in their respective null-sets, which does not affect our analysis. Define the cul distance between two graphon-signals (W, (V,9) E WC, by
8
= inf $E8
(V.g)))
Here, (V.g)* : (V). More details on this construction are given in Appendix A.3.
The graphon-signal cut distance &n is pseudo-metric, and can be made into metric by introducing The quotient space WC, WC,/ ~ of equivalence classes [(W []] of graphon-signals (W, is a metric space with the metric ( f)], [(V,g)) f)W, V)))). By abuse of terminology, call elements WC, also graphon-signals. A graphon-signal in WL,, is defined irrespective of a specific "indexing" of the nodes in [0, 1].
the equivalence relation: (W, ~ (V,g) if ( f). g)))
3.2 Induced graphon-signals
Any graph-signt can be identified with a corresponding graphon-signal as follows. Definition 3.2. Let (G, f) be siaph- with node set [n] and adjacency matrix A = {as. hijje Let (Ix 12 with I = [[k 1)/n, k/n) be the equipartition of [0. 1] into n intervals. The graphon- signal (W,f)a,r) (Wa. . fe) induced by (G, f) is defined by
Wc(x,)) v)
Σ an (z) (,),,, and fr(2) Σ fiL
5

---

We denote (G..) = (We.fr) We identify any graph-signal with its induced graphon-signal. This way, we define the cut distance between a graph-signal and graphon-signal. As before, the distance between a graph-signal (G, f) and a graphon-signal (W, g) can be interpreted as how much the deterministic graph-signal (G, f) "looks like" was randomly sampled from (W, g).
3.3 Graphon-signal regularity lemma
(a)
(b)
(c)
Figure 2: Illustration of the graphon-signal regularity lemma. The values of the graphon in gray
scale over [0, 1)², and the signal is plotted in color on the diagonal of [0, 1j2. (a) A graphon-signal.
(b) Representation of the bijection guaranteed by the regularity lemma. (c) The approximating step graphon-signal guaranteed by the regularity lemma.
graphon-signal under the "good" permutation//measure preserving
To formulate our regularity lemma, we first define spaces of step functions.
Definition 3.3. Given partition Pk. and d E N, we define the space Sp. of step functions of dimension d over the partition Pk to be the space of functions F [0, 1] R of the form
F(r1....,
Σ
Cj II 1p, (21).
(5)
1 (
for any choice of {c₂ E R]jeE
We call any element of Wo n S7, a step graphon with respect to Pk. A step graphon is also called a stochastic block model (SBM). We call any element of D [0, 1] n SSp, a step signal. We also call [WC,]p. == (Wo n S P.) x (C,") [0, S the space of SBMs with respect to Pk.
In Appendix B.2 give number of versions of the graphon-signal regularity lemma. Here, 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 > 1, and any sufficiently small e for every 2525 and every (W,f) E WLr, there exists a step graphon-signal (Wn, fn) E [WLrlI, such that (WW, (Wn, fn)) Se where In is the equipartition of [0, into n intervals.
(6)
Figure 2 illustrates the graphon-signal regularity lemma. By identifying graph-signals with their induced graphon-signals, (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.
The lower bound n 2 2 on the number of steps in the graphon-signal regularity lemma is essentially tight in the following sense. There is universal constant C. such that for every e >> there exists a graphon-signal (W, f) such that no step graphon-signal (W', f') with less than 2 S1 steps satisfies Go,, f), (W', f() < To this. [8, Theorem 1.4, Theorem 7.1] shows that the bound in the standard weak regularity lemma (for graphs/graphons) is essentially tight the above sense. For the graphon-signal case,
Remark 3.5.
take the graphon W' from [8, Theorem 7.1] which does not allow regularity partition with less than 2 steps, and consider the gruphon-signe (W', 1), which then also does not allow such regularity partition.

---

3.4 Compactness of the graphon-signal space and its covering number
We prove that WL, is compact using Theorem 3.4, similarly to [25, Lemma 8). Moreover, bound the number of balls radius e required to cover WL,--
Theorem 3.6. The metric space (WLr; é is compact. Moreover, given r >> 0 and e > 1, for every sufficiently small the spuce WL,, can covered by
x(e) = 2*
balls of radius 6, where k [
9c
The Proof of Theorem 3.6 is given in Appendix C. This is powerful result the space of arbitrarily large graph-signals is dense in the "small" space W.,,, We will use this property in Section 4.3 to prove generalization bound for MPNNs.
3.5 Graphon-signal sampling lemmas
In this section we prove that randomly sampling a graphon signal produces 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.I. Let = (Ai,... A&) E [0, 1 be independent uniform random samples from [0, IJ. and (W, f) f) E WC,. We define the random weighted graph W ((A) as the weighted graph with k nodes and edge weight Wig = W (A,,, Aÿ) between node and node j. We similarly define the random sampled signal f(A) with value fi f(A,) at each node i. Note that (A) and fA) share the sample points A. We then define a random simple graph as follows. We treat each W4, = ((A,, Aÿ) as the parameter of Bernoulli variable es,j, where P(ea.j = 1) = way and P(es., = 0) 1 Wii. We define the random simple graph G(W,A) as the simple graph with an edge between each node i and node if and only if ec. = 1.
We note that, given graph signal (G, sampling graph-signal from f) r) 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 graphon-signal, where graph-signal sub-sampling is a special case. We now extend [24, Lemma 10.16], which bounds the cut distance between a graphon and its sampled graph, the case of sampled graphon-sie -sinnal.
Theorem 3.7 (Sampling lemma for craphon-signals, Letr > 1. There exists constant Ky > 0 that depends on such that for every k 2 Ko, every (W, E W.,,, and for A = (AI,... A E [0, 1] independent uniform random samples from [0, 11. we have
E 60
(
15
V Vlog(k)
and
E 6m ((W, f), (G(W.A).
15
Vlog(k)
The proof of Theorem 3.7 is given in Appendix D.2
Graphon-signal analysis of MPNNs
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.
4.1 MPNNs on graphon signals
Next, we define MPNNs on graphon-signals, such a way that the application MPNN on an induced graphon-signal is equivalent to applying the MPNN on the graph-signal and then inducing it. similar construction was presented in [26], for average aggregation, but we use normalized sum aggregation.
7

---

At each layer, we define the message function ( 8) as linear combination of simple tensors as follows. Let K E N. For every [K] let & 5t Rd + TRP be Lipschitz continuous functions that we call the receiver and transmitter message functions respectively. Define the message function Φ : 2dd + R2 by
( b) = Σ (a)
k=1
where the multiplication is elementwise along the feature dimension. Given signal f, define the message kernel , [0, 1]² + R2 by
- =((t)))=(((()..())
Σ +((()))
We see the variable of 2 (z y) the receiver of the message, and y as the transmitter. Define the aggregation of a message kernel Q [0. 112 RP, with respect to the graphon W E Wo. to be the signal Agg(W, Q) E c [0. 1]. defined by
Ag, (W) J. W(x, (I. v)dy.
for an appropriate O. A message passing layer (MPL) takes the form f()) + Agg(W, & foo where f()) is the signal layer t. Each MPL is optionally followed by update layer, which updates the signal pointwise via f(++1) = f(++)) (f (x), Agg(W, (0t (z)), where f((+1)) a learnable mapping called the update function. A MPNN is defined by choosing the number of layers T, and defining message and update functions {e', ((E)) (t ( ( A MPNN only modifies the signal, and keeps the graph/graphon intact. We denote by O.W, the output of the MPNN applied on () E W,, at layer / E [T]. More details on the construction are given in Appendix E.
()tt))
The above construction is rather general. Indeed, it is well known that many classes of functions F Rd x IRd + Rº (e.g., 2 functions) can be approximated by (finite) linear combinations of simple tensors F(a,b) b) ~ >k=1 (f)) Hence, message passing based on general message functions : R22d + RpP can be approximated by our construction. Moreover, many well-known MPNNs can be written using our formulation with small K, e.g., [29, 36] and spectral convolutional networks [9, 20, 21], if we replace the aggregation in these method with normalized sum aggregation.
In Appendix E.1 we show that for any graph-signal fG, have (W, f) (W, fex..))).))) where the MPNN on graphhsignal is defined with normalized sum aggregation
(Agg(G, (r))
Σ (Dr)i
jE(M)
Here, n is the number of nodes, and { ). is the adjacency matrix of G. Hence, we may identify graph-signals with their induced graphon-signals when analyzing MPNNs.
4.2 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 be MPNN with layers. Suppose that there exist constants L, such that for every layer E (T), every E rt, and every k E [K].
[1)( (0)) s B, and Lu:: Lig < L.
where Lu and Logy are the Lipschitz constants of μ¹ and Egk. Then, there exists a constant Le (that depends T, K, B and L) such that for every (W, (V,9) W..,
f) (VV.g)ll < Le [If allo + I|W NWW-Vll -Vlla).
The constant Ta depends exponentially on T, and polynomially on K, B and L. For formulas of Le. under different assumptions the hypothesis class of the MPNN, refer to Appendix F.

---

4.3 A generalization theorem for MPNN
In this section we prove uniform generalization bound for MPNNS. For background on general- ization 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 [14, 23, 26, 30, 33).
When MPNN is used for classification or regression, Or is followed by global pooling. Namely, for the output signal g : [0, + R2, we return Jf g(x)dr E RR. This is then typically followed by a learnable mapping I2 + IC In our analysis, we see this mapping as part of the loss, which can hence be learnable. The combined loss is assumed be Lipschitz continuous
We model the ground truth classifier into C' classes as a piecewise constant function C: WL,, {0, 13 where the sets of different steps in WC, are Borel measurable sets, correspond to different classes. We consider an arbitrary probability Borel measure on WC,, as the data distribution. More details on the construction are given in Appendix G.2.
Let Lip (iC,, L)) be the space of Lipschitz continuous mappings T : WC, - RC with Lipschitz constant L1. By Theorem 4.1, we may assume that our hypothesis class MPNNs a subset of Lip(WC,,, [1) for some given L1. Let X =
be independent random samples from the data distribution (WC,.v). Let Tx be a model that may depend on the sampled data, e.g.. via training. Let & be a Lipschitz continuous loss function' with Lipschitz constant T.2. For every function Y in the hypothesis class Lip(WC., Li) (i.e. Tx). define the statistical risk
R(T) (( CJ) = / (()))))
We define the empirical risk X( EN ((T(X)))) Theorem 4.2 (MPNN generalization theorem). Consider the above classification setting, and let L L2L2 Let XXN be independent random samples from the data distribution (WC,, v).
N
Then, for every > 0, there exists an event UP C W.C"" with probability
C
Sー (UP) 2 1- Cp N
in which
(R(Ix) - RR x)
SE (N/2C)
122 (L+ (1+v/og(22)))) vlog(2/p))
(8)
where E(e) function of
x(c) log(nee))) is the covering number of WCr given in (7), and g-1 is the inverse
The theorem is proved in Appendix G.4. Note that the term (N/2CC) in (8) decreases to zero as the size of the training set N goes to infinity.
In Table 1 we compare the assumptions and dependency on the number of data points of different generalization theorems. All past works consider special assumptions. Our work provides upper bounds under no assumptions on the data distribution, and only mild assumptions on the MPNN (Lipschitz continuity of the message passing and update functions). In Table in Appendix G.5 we present experiments that illustrate the generalization capabilities of MPNNs with normalized sum aggregation.
4.4 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 MPNN to the smaller subsampled graph [5, 16). Here, we show that such approach is justified
We note that loss functions like cross-entropy not Lipschitz continuous. However, the composition of cross-entropy on softmax Lipschitz. which is the standard way using cross-entropy. 'The loss E may have a learnable component (that depends on the dataset X). long as the total Lipschitz bound of is La.

---

Table 1: Comparison of the assumptions made by different GNN generalization analysis papers.
Generalization smalysis paper
Assumption the graphes
No weight
General MPL.
Dependency N
Gemeralization Limis of CNNNs [14]
bounded degnee
X
N N-172
PAC PAC-boyesian MPNN (25)
bounded degree
X
N N-172
PAC-héyessan GCN [25]
bounded degree
/
x
N 1/2
VC moets IWT, [36]
houvled color complexity
/
N-172
Gemeralizasion Amalysi MPNNs (26)
sampled small graphuns non
N-172
Our graphon-iigua theory
theoretically. Namely, any (Lipschitz continuous) MPNN has approximately the same outcome on the large graph and its subsampled version.
Transferability and stability analysis [18, 22, 27, 31, 32] often studies a related setting. Namely, is shown that MPNN applied on 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 M which is the graphon domain, and the graphon W : . x M - [0. 1] is Lipschitz continuous with respect MM, where the dimension of M affects the asymptoties. 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 WC,, and, hence, limits the analysis significantly. In comparison, our analysis applies any graphon-siget signall in WC,. When we only assume that the graphon is measurable, [0. 1] is only treated as a standard (atomless) probability space, which is very general, and equivalent for example to [0, 1] for any E N, and any Polish space. Note that graphon theory allows restricting the graphon domain to (0, 1] since [0, 1). measure space, is very generic.
Theorem 4.3. Consider the setting of Theorem 4.2, and let θ be a MPNN with Lipschitz constant L. Denote
= (W), and Σ(A)
Then
< 15
E ( (X,
L.
Vlog(k)
5 Discussion
We presented an extension of graphon theory to a graphon-signa 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 the Lipschitz continuity of MPNNs with respect 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 similarity, that allows studying the space of all graph-signals, it applies to any graph-signal data distribution, and does impose any restriction on the number of parameters of the MPNNs, only to their regularity through the Lipschitzness of the message functions.
natural notion of graph
The main limitation of the theory is the very slow asymptotics of the generalization and subsampling theorems. This follows the fact that the upper bound on the covering number of the compact space WC, grows faster than the covering number of any finiteddimensional compact space. Yet, we believe that our work can serve as a point of departure for future works, that 1) will model subspaces of WC,, of lower complexity, which approximate the support of the data- data-disttibutton in real-life settings of graph machine learning, and, 2) will lead to improved asymptotics. Another open problem is find an essentially tight estimate of the covering number of WC,, which may be lower than the estimate presented in this paper.
10

---

Acknowledgments
We thank Ningyuan (Teresa) Huang for providing the experiments of Table 2.
Ron Levie is partially funded by ISF (Israel Science Foundation) grant #1937/23: Analysis of graph deep learning using graphon theory.
References
[1] N. Alon, W. de la Vega, R. Kannan, and M. Karpinski. Random sampling and approximation of max-csps. Journal of Computer and System Sciences, 67(2):212-243, 2003. ISSN 0022-0000. doi: https://doi.org/1100 www.o////....////////... 10001000022000000000000000000000
Special Issue on STOC 2002.
[2] K. Atz, F. Grisoni, and G. Schneider. Geometric deep learning on molecular representations. Nature Machine Intelligence, 3:1023-1032, 2021.
[3] W. Azizian and M. Lelarge. Expressive power of invariant and equivariant graph neural networks.
In ICLR, 2021.
[4] C. Borgs, T. Chayes, Lovász, V. T. Sós, and K. Vesztergombi. Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing. Advances in Mathematics, (01-)1180111811, 2008.
[5] J. Chen, T. Ma, and C. Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
[6] Z. Chen, S. Villar, L. Chen, and J. Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In NeurIPS. Curran Associates, Inc., 2019.
[7] W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD
199, page 257-266, New York, NY. USA, 2019. Association for Computing Machinery. ISBN 97814 15503620166. doi: 10.1145/3292500.333000 3333092..
[8] D. Conlon and J. Fox. Bounds for graph regularity and removal lemmas. Geometric and Functional Analysis, 22:1191-1256, 2012.
[9] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurIPS. Curran Associates Inc., 2016. ISBN 9781 9781510838819,
[10] J. M. S. et al. A deep learning approach to antibiotic discovery. Cell, 180(4)6688- 702.e13, 2020. ISSN 0092-8674.
[11] M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometrie. In ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds, 2019.
[12] G. Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
[13] A. M. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19:175-220, 1999.
[14] V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In H. D. III and A. Singh, editors, JCML, volume 119 of Proceedings of Machine Learning Research, pages 3419-3430. PMLR, 13-18 Jul 2020.
[15] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272, 2017.
[16] W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, page 1025-1035. Curran Associates Inc., 2017. ISBN 97815 1781510869964.
[17] M. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool,
R. Bates, A. Zidek, A. Potapenko, A. Bridgland, C. Meyer, S. A. A. Kohl, A. Ballard, A. Cowie, Nikolov, R. Jain, Adler, T. Back, Petersen, D. A. Reiman, E. Clancy, M. Zielinski, M. Steinegger, M. Pacholska, T. Berghammer, S. Bodenstein, D. Silver, O. Vinyals,
B. Romera-Paredes,
11

---

A. W. Senior, K. Kavukcuoglu, P. Kohli, and D. Hassabis. Highly accurate protein structure prediction with alphafold. Nature, 596:583 589, 2021.
[18] N. Keriven, Bietti, and S. Vaiter. Convergence and stability of graph convolutional networks on large random graphs. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2020.
[19] N. Keriven, A. Bietti, and S. Vaiter. On the universality of graph neural networks on large random graphs. In NeurIPS. Curran Associates, Inc., 2021.
[20] N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[21] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):
97-109, 2019. doi: 10.1/09TTPP 1.099TTS.20112289992244
[22] R. Levie, W. Huang. L. Bucci, M. Bronstein, and G. Kutyniok. Transfcrability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22(272):1-59, 2021.
[23] R. Liao, R. Urtasun, and R. Zemel. A PAC-bayesian approach to generalization bounds for graph neural networks. ICIR, 2021.
[24] L. M. Lovász. Large networks and graph limits. In volume 60 of Colloquium Publications, 2012. doi: 10.1090/co1//660
[25] L. M. Lovász and B. Szegedy. Szemerédi's 's lemma for the analyst. GAFA Geometric And Functional Analysis, 17:252-2700 2007.
[26] S. Maskey, R. Levie, Y. Lee, and G. Kutyniok. Generalization analysis of message passing neural networks on large random graphs. NeurlPS. Curran Associates, Inc., 2022.
[27] Maskey, R. Levie, and G. Kutyniok. Transferability graph neural networks: An extended graphon approach. Applied and Computational Harmonic Analysis, 63:48-83, 2023. ISSN 1063-5203. doi: https://doi.org/10.. 101...00....cccaa222......
(28) O. Méndez-Lacio, M. Ahmad, E. A. del Rio-Chanona, and J. K. Wegner. A geometric deep learning approach to predict binding conformations of bioactive molecules. Nature Machine Intelligence, 3:1033-10339 2021.
[29] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference Artificial Intelligence, 33(01):4602-466) Jul. 2019, doi: 10. v33001. 33014602.
[30] C. Morris, Geerts, Tönshoff, and M. Grohe. WI meet ve. In ICML. PMLR, 2023.
[31] I.. Ruiz, L. F. O. Chamon, and A. Ribeiro. Graphon signal processing. IEEE Transactions Signal Processing, 69:4961-49776 2021.
[32] L. Ruiz, Z. Wang. and A. Ribeiro. Graphon and graph neural network stability. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5255-5259, 2021.
[33] Scarselli, A. C. Tsoi, and M. Hagenbuchner. The vapnik-chervonent chervonenkis dimension of graph and recursive neural networks. Neural Networks, 18::2482559 2018.
[34] S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. doi: 10.1017/CB0978110799888
[35] D. Williams. Probability with Martingales. Cambridge University Press, 1991. doi: 10.1017/ FB0978051181333
[36] K. Xu, W. Hu, J. Leskovee, and Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
12

---

A Basic definitions and properties of graphon-signals
In this appendix, we give basic properties of graphon-signals, eut norm, and cut distance.
A.1 Lebesgue spaces and signal spaces
For S p oo, the space [ 1] is the space of (equivalence classes up to null-set) of measurable functions f |0, + IR, with finite L1 norm
Il = L d() 1/P
<c.
The space [0, 1] is the space of (equivalence classes) of measurable functions with finite Loo norm
|| = ess sup =E[o.1]
[f() inf 2 [x() & a for almost every x E 1].
A.2 Properties of cut norm
Every f E C [0, 1] can be written as f = f+ f-, where
(x) = { f(x) [(x)
f(x) 0.. 0.
and f- is defined similarly. It is easy to see that the supremum in (3) is attained for S which is either the support of f+ or f-, and
|/ = (1/
As result, the signal cut norm is equivalent to the L1 norm
|llll S II ll s lifll..
(9)
Moreover, for every r and measurable function W [o,1]² 1J2 + [-r,r].
S |Wllo S [[]] I ||]| S | Sr.. r.
The following lemma is from [24, Lemma 8.10].
Lemma A.1. For every measurable W [0, 1]² + R, the supremum
/ / W (z. w)drdy
sup (.7C(0.1)
attained for some S,
A.3 Properties of cut distance and measure preserving bijections
Recall that we denote the standard Lebesgue measure of [O, 1] by μ. Let Sto. be the space of measurable bijections [0. 1] + [0, 1] with measurable inverse, that are measure preserving, namely, for every measurable C [o, 1]. p(A) p(o(A)). Recall that S),1) the space of measurable bijections between co-null sets of [o, 1].
For é Sio.1] or Ø $/.1j. we define ( 3) (((z)) d(y)). In case So W is only define up to a null-set, and we arbitrarily W in this null-set. This does not affect our analysis, as the cut norm is not affected by changes to the values of functions on null sets. The cut-metric between graphons then defined be
(W, Wo) = inf
|W
W
$E
inf
sup
(W ((o(z). dxdy.
8
SXT
13

---

Remark A.2. Note that Ln can be defined equivalently with respect to & E Soo.j. Indeed. By [24, Equation (8.17) and Theorem 8.13), ån can be defined equivalently with respect to the measure preserving maps that are not necessarily invertible. These include the extensions of mappings from S/u.1 by defining x(z) 0 for every in the co-null set underlying S.
Similarly to the graphon case, the graphon-signal distance 8n is pseudo-metric By introducing an equivalence relation (W ~ (V,g) if (O f), (V, g)) = O, and the quotient space WC, == W ~. WL, is metric space with metric d defined by ( [)], [V,)))) = do(W, V) where (WW f)), ((V. g)], are the equivalence classes of (W; f) and (V,g) respectively. By abuse of terminology, we call elements of WL, also graphon-signals,
Remark A.3. We note that WL, + Wo L (0, 1] (for the natural definition of L.² [0, 11), since WLr we require that the measure preserving bijection shared between the graphon W and the signal f. Sharing the measure preserving bijetion between W and f is an important modelling requirement, as Φ is seen as a "re-indexing" of the node set [0, 1]. When re-indexing node x, both the neighborhood W (2x,)) )) of x and the signal value f(x) at x should change together, otherwise, the graphon and the signal would fall out of alignment.
We identify graphs with their induced graphons and signal with their induced signals
B Graphon-signal regularity lemmas
In this appendix, we prove a number of versions of the graphon sighonn--ignal regularity lemma, where Theorem 3,4 is one version.
B.1 Properties of partitions and step functions
Given partition Ps and d E N. the next lemma shows that there is equiparition E, such that the space Sg uniformly approximates the space S in [o, 1]dh norm (see Definition 3.3).
Lemma B.1 (Equitizing partitions), Let Pk be a partition of [0, 1] into sets (generally not of the same measure). Then, for any k there exists equipartition &n of [0, 1] into sets such that any function F Sp, can be approximated in Li [0, 1] by function from F St. up to small error. Namely, for every St, there exists F" St.. such that
FF-F S Fl
Proof. Let Pk. = (PI....,Pe P& be a partition [0, 1]. For each i, we divide P. into subsets P. = (Pr.,..., Pi.m, of measure 1/n (up to the last set) with residual, as follows. If ((P.) < 1/n. we choose P. (P.. = P.). Otherwise, we take P......,, P.,m, of measure 1/n, and u(P.,m.) < 1/n. We call P. P.,m, the remainder.
We now define the sequence of sets of measure 1/n
2 =
P2,1, P2. Pk,,,
PR.ma 1k,
(10)
where, by abuse of notation, for any such that m, 1, we set (P....... 11. = 0 in the above formula. Note that general UQ * [0, 1]. We morcover define the union of residuals Il := Pi,my U P2,mg U... Pk.my Note that ((ll)= = 1 f(U2) ([U))== k_ h/n, where & is the number of elements in @, and measure 1/n with residual. Thus we have obtain the equipartition of [0 1] to sets of measure 1/n
k. Hence, we can partition II into h parts (II,,... H. of
En = .PI.....,PPII... Pa...... Pe.ma 1.mm--1...,5 -e................. Sk.m 11, I2..... J. (11)
For convenience, we also denote E,- [Z,...., ..... Z.n).
Let
d II 1=1
F(x) = Σ
I,, (ar) E 5t.-
14

---

We can write F with respect to the equipartition &n as
F(x)=
II 1=1
1 (x1) + E(r),
in Ed] w= 2
for some {cy} with the same values as the values of {ez}. Here, E is supported in the set II C
[0, 1] defied by
IT (IT 11-1))=1) u (10, IT (0, 3) u (10, 1| m).
Consider the step function
F'(x)
1 Zz (xt) E S
)= [n]" vi=1....dd Zn 1=1
Since (LlI) = k/m n,, we have ((11(4)) dk/nn, and so
|F F'll - dl Flo
Lemma B.2. Let {Q1, ....... 2m) partition of [0, 1}. Let {1,, ......, .....,,y Im be a partition of [0, 1]
into intervals, such that for every j [m], m(2,) = p(Tz). Then, there exists measure preserving
bijection é [0, + [0, E S (0.11 such that"
<(2,) Ij
Proof. By the definition of standard probability space, the measure space induced by [0, on non-null subset Q, S [0, 1] is a standard probability space. Moreover, each Q, is atomless, since [0, is atomless. Since there is measure- pressrrires bijection (up to null-set) between any two atomless standard probability spaces, we obtain the result.
Lemma B.3, Let S = (S, C [0, 17 be a collection of measurable sets (that are not disjoint in general), and d E N. Let C3 be the space of functions F [0, 1]dh - R of the form
d
F(x)
Σ
Cj II
Iss (m1),
1=1
for some choice of {e; R jEmmja Then, there exists a partition Pk = (P....., Pk) into k n sets, that depends only on S, such that
C3. C
Pk) Proof. The partition Pı = (P,,....
.k is defined as follows. Let
p = c [0, [0, 1), P == n(; E S|x E
We must have [P] < 2 Indeed, there are at most 2m different subsets of S for the intersections.
We endow arbitrarily order to P. and turn it into sequence. If the size of P. is strictly smaller than 2 we add enough copies of {0) to P to make the size of the sequence 2 that we denote by Pk. where & 2
The following simple lemma is proved similarly to Lemma B.3. We give it without proof.
Lemma B.4. Let PA = (P.....,PP Pk). 2m = (Q....., Q+ be two partitions. Then, there exists a partition Zum into km sets such that for every d,
S4 S and
S Szm
NNaeeyy, there is a measure preserving bijection & between two co-null sets Cs and C2 of [0, 1), such that nC)) 1, C2.
15

---

B.2 List of graphon-signal regularity lemmas
The following lemma from [25, Lemma 4.1] a tool in the proof of the weak regularity lemma. Lemma B.5. Let K1, K2.... be arbitrary Ronempty subsets (not necessarily subspaces) of Hilbert space H. Then, for every e > O and v E '.. there is m S [1/e]] and vs E KC and Iv E R, i E [m]. such that for every Km++1
W.
< ||
(12)
The following theorem is an extension of the graphon regularity lemma from [25] to the case of graphon-signals. Much of the proof follows the steps of [25].
Theorem B.6 (Weak regularity lemma for graphon-signals), Let E, > 0. For every (W,f) E WC,
there exists a partition Px of [0, 1] into = (221/22)) sets, a step function graphon W e Sp. n Wo and a step function signal fR E Sp. n c [0, 11. such that
I W&llo Se and ||ʃ - f& lb S p-
(13)
Proof. We first analyze the graphon part. In Lemma B.5, set H (10, 1J²) and for all i e N, set
AC = {1sxr] [,T [0, 1] measurable).
Then, by Lemma B.5, there exists m [1/e²1 two sequences of sets Sn {S:) Tm (Tik a sequence of coefficients {7: E R)m- and
m
W
Σ
% s.
such that for any V K. given by Vzz. v) 5 (T)) we have
(V w((, = = 11.5 (W(z.y) Wa v) drdy
(14)
<e|lsxr |||W|| S.
(15)
We may choose exactly m [1/e²] by adding copies of the empty to Sm and Tim if the constant m guaranteed by Lemma B.5 is strictly less than [1/ea]. Let W.(r, y) = (W"(a (x. y) + W" (y.x))/2
By the symmetry of W, it is easy that (15) is also true when replacing W by W.. Indeed,
/ (W Wa(a, drdy
1/2 / ((z,,))W(rr,)) (x). + +1/2
/ (W),)) W" v))
<.
Consider the concatenation of the two sequences Tm, given by 22 = Tm U Sm. Note that in the notation of Lemma B.3, W. C32m. Hence, by Lemma B.3, there exists partition Q, into 2 = 2 sets, such that W. is a step graphon with respect to On.
To analyze the signal part, we partition the range of the signal |-r, r] into j = [r/p] intervals (J.K-n of length less or equal to 2p, where the left edge point of cach J, is + (i - f).. Consider the partition of [0, 1] based on the preimages V/+ (Y, = {-){( It is easy to see that for the step signal
j fa(x) = Σ (aIly(1))
1=1
where a; the midpoint of the interval Y,, we have
|| follo s |lf - foll S p.
16

---

Lastly, by Lemma B.4, there is a partition Pk of [0, 1] into |r/p] (2r1/e1)) sets such that We E Sb, and Jp E Sp.-
Corollary B.7 (Weak regularity lemma for graphon-signals version 2). Let > and c > 1. For every sufficiently small
(namely, that satisfies (17)), and for every (W, WL, there exists partition Ps of [0, 1] into k (2)cc/e)) sets, step graphon Wa E S2, n Wo and step signal
fü Epp, c [0, 11, such that
(W,, fa)) Se.
Proof. First, evoke Theorem B.6, with errors || WallD v and - S - We now show that there is some eo > such that for every e < ED. there is choice of v such that the number of sets in the partition, guaranteed by Theorem B.6, satisfies
k(V) = (e/(e-//]]p) - (2)(((22/(()) < 2 2/20/6²1
Denote = 1 + t. In case
V V 2(1 + 0.5t)/e² 1¹
(16)
have
20/1/001 < 22(1-0.51)1
On the other hand, for
1/ s - 21/12
we have
[r/(e v)1 s 22
The reconcile these two conditions, we restrict to e such that
(17)
21/e² | 2(1 + 0.5l)/22 2--6)/22-1 -1
There exists Eo that depends on and r (and hence also on t) such that for every < (17) is satisfied. Indeed, for small enough 6,
2 2-1/c²
21/r2 - = 1-2 2-1/122 2-1
{ (1-tt).)
SO
r
21/12 c1+
Moreover, for small enough e,
2(1 + 211+0.0)/2-1 VV (1 0.5l) - 2² < <e/(1
Hence, for every < cp, there is choice of such that
k(v) = [r((= - w) (2) < 22(0.5t) 2 20 < 2(20/²1
Lastly, we add as many copies of ( to Pa(M)) as needed so that we get a sequence of k: = 20/e/=1 sets.
17

---

Theorem B.8 (Regularity lemma for graphon-signals equipartition version), Let c > and r > 0. For any sufficiently small >> and every (W, f) WC, there exists & E Soo. a step function graphon [W E S4 n Wo and step signal [ E S n.t [0. 11, such that
dn( f (W" In, (1%1))) Sc
(18)
where In is the equipartition of (0, [0, 1] into n = 2/20/e21 interval..
Proof. Let c 1+tt,, 0 and 0 < a, 8 < 1. In Corollary B.7, consider the approximation error
du ((W,
S ar.
20-4/22 (ea)
with partition Pk: into lo = 2 accurately, in Lemma B.1, we choose
sets. We next equatize the partition Ps up error cB. More
2(1+0.50) (en)a
+1 /(c3)),
and note that
2(1+0.55)) (za)
T2 2
By Lemma B.1 and by the fact that the cut norm is bounded by L1 norm, there exists an equipartition En into sets, and step functions W,, and fn with respect to En such that
|| W S 2eB3 and - f S reB.
Hence, by the triangle inequality,
do(,, (W,, f.)) & do do f(W, (Wk. fa)) + do ((W,. fi), (Wn, fw)) S c(a + (2 r)))).
In the following, we restrict to choices of a and / which satisfy a + (2 + r) = 1. Consider the function n (0, 1) - N defined by
(a) = 22 (coo)= +1 /(eB)) - 1
9(140.61) 4(co))
+1 /(e(1- a))]
Using a similar technique as in the proof of Corollary B.7, there cu > 0 that depends on c and (and hence also on t) such that for every Eo, , may choose ag (that depends c) which satisfies
n(aa)) [2 + r)
201+0.50) (=mo)²
+1 (c(l-oa))] <2 < 31
(19)
Moreover, there is choice a1 which satisfies
m((n) ) [ + r) (ems)²
201+0.50)
/c(1 m1) > 2 31
(20)
We note that the function n : (0, 1) + N satisfies the following intermediate value property. For every 0 < a1 < 02 < 1 and every E N between n((1) and (a(2), there is a point a E [a1, a2]
+1 /(c(1 -a)) a continuous such that na)) = m. This follows the fact that a +> (2+r)-2 (eos*
20140.51)
function. Hence, by (19) and (20), there is point (and / such that a + (2 + r) 1) such that
naa)= = n = [2
20.40.50)
(ea)a
+1 /(EB)] = 2020/21
By a slight modification of the above proof, we can replace n with the constant n = -1 As result, we can easily prove that for any n' > 2 #1 we have the approximation property (18) with n' instead of n. This is done by choosing an appropriate d' c and using Theorem B.8 on c', giving a constant n' = [2
2f n. This leads to the following corollary.
equipartition version 2). Let > 1 andd > 0. For any sufficiently small every 2 2 #1 and every (W, f) W.,,, there exists & Sp..j. step function graphon [W*], E S7 0 Wa and step function signal [ St n 4. [0 1). such that
Corollary B.9 (Regularity lemma for graphon-signale
do (aWe, (W"),, (1 Se.
where In is the equipartition of [0, 1] into intervals.
18

---

Next, we prove that we can use the average of the graphon and the signal in each part for the approximating graphon-signal For that we define the projection of a graphon signal upon a partition. Definition B.10. Let Pn (P...... Put be partition of [0, 1]. and (W.f) WC,- We define the projection of (W, f) upon (Sp x SPN, to be the step graphon-sighe (W,f)r. f)p. = :Wp.:fp, that attains the value
((x,y)drdy (p, - J f(z)dr
Wp, (z, v)
P:xP3
for every (x, P.PPP
At the cost of replacing the emrrr by 2e, we can replace W with its projection. This was shown in [1]. Since this paper does not use the exact same setting as us, for completeness, we write proof of the claim below.
Corollary B.11 (Regularity lemma for graphon-signals projection version). For any c > 1, and any sufficiently small 0. for every 2 and every (W, E WC,, there exists ó S/o.11 such that such that
(Wwe, ra), (I. 11 Se.
where In is the equipartition of [0, 1] into intervals.
We first prove a simple lemma
Lemma B.12. Let Pn = (PI,... ).) be a partition of (0, 1), and Let V, R E SP. OW- Then, the supremum of
1 / (V(x, R(xx,)) dxdy
sup 0,T JT
(21)
is attained S,T of the form
s == UP, Pi T T= T-UP, P3
iES
jEL
where 1, C. [m). Similarly for any two signals f,g E Sp. n 12 11. the supremum of
| (f(x) g(x)) dr
sup Sc(0.1)
(22)
is fttained S of the form
S = U P
i
where s [n].
Proof. First, by Lemma A. the supremum of (21) is attained for some S,T [0, 1]. Given the maximizers S, without loss generality, suppose that
S (V y) R(x, v)) drdy >
we can improve as follows. Consider the set / C [r]] such that for every t
1 Jmme (V(x,)) R(z, y) drdy 0.
By increasing the set T P, to Pj. we can only increase the size of the above integral. Indeed,
1/// (V(z, R(x, v) drdy m(P,))
[ (V(r,y) R(x,, v) drdy
p(T
1 I (V(a,y) R(x, (er
19

---

Hence, by increasing T to
T' =
U Pst
(1TM;
we get
J (V u) - R(x, dzdy 2 / (V(z,g) R(x, v) dxdy.
We similarly replace each T' P3 such that
Js Lmmm (V(z,)) R(z, v) dxdy S 0
by the empty set. We now repeat this process for S, which concludes the proof for the graphon part. For the signal case, let f = / - f-, and suppose without loss of generality that ||l = 1l/ easy to that the supremum of (22) is attained for the support of f+, which has the required form.
Proof. Proof of Corollary B.1 Let Wn E Sp, nW be the step graphon guaranteed by Corollary B.9, with eгror c/2 and measure preserving bijection Φ %o.1j. Without loss of generality, we suppose that W W. Otherwise, just denote W W and replace the notation W with W' in the W, Il is attained for for some
following. By Lemma B.12, the infimum underlying W\,,
S S iE8
T T T-UP, Pg.
jet
We now have, by definition of the projected graphon,
W P
Σ
(Wp, - (2. dxdd
iEaJEL P.
= =E
Σ iESJjEt P. P.
J (W(x,)) (x, dadd
/
[ (W(x,)) Walar,)))dde = =| Wilo-
Hence, by the triangle incquality,
| WP, Iln & I - Walln IWW - Wo,lln < W Wlln.
A similar argument shows
Ilf - fp.llo < 2l1fa - fllo.
Hence,
da (W ([,"),,, ([. (1)))) < 2d= (Wo,
(W) (o), (IW%),, S
C Compactness and covering number of the graphon-signal space
In this appendix we prove Theorem 3.6.
Given partition Pk, recall that
WC,]p, = (Wi (6,)) x (C (0. (0.1)%))
called the space of SBMs or step graphon-signals signals with respect to Px. Recall that WC, is the space of equivalence classes of graphon-signals with zero ån distance, with the ôn metric (defined on arbitrary representatives). By abuse terminology, we call elements WL, also graphon-signals.
Theorem C.1. The metric space (WCr, 80) is compact.
20

---

The proof is simple extension of [25, Lemma 8] from the case of graphon to the case of graphon- signal. The proof relies on the notion of martingale. A martingale a sequence of random variables for which, for each element in the sequence, the conditional expectation of the next value in the sequence equal the present value, regardless of all prior values. The Martingale convergence theorem states that for any bounded martingale { [M,) In over the probability pace X, the sequence {M, in converges for almost every a E X, and the limit function is bounded (see [12, 35)).
Proof. [Proof of Theorem C.1] Consider a sequence {[W,,, fa)l C WC,, with (Wn, fx) E W.,.. For each k, consider the equipartition into my intervals Imm where my 230((r"+))14= +1)]A> By Corollary B.11, there is a measure preserving bijection Ōn,k (up to nullset) such that
|| (W fn) (Wn, fa)
Ohik Tank
I1,rr < 1/k,
fnn where (Wn, fn) Bn.k k is the projection of (Wn; Jn) upon Imp (Definition B.10). For every fixed k,
each pair of functions (n):s))z., In) is defined via mi mm values in [0, 1]. Hence, since [0, 1]mi+m= compact, there is subsequence {nž hier, such that all of these values converge. Namely, for each k, the sequence
{W n5. Sut Im, 15=1
converges pointwise to some step graphon-signal (Uk, 9*) in [WC,l,, as
oc. Note that Im, is refinement of Imn for every I k. As as a result, by the definition of projection of graphon-signals to partitions, for every 1 > k, the value of (W....)) [Wnn"") at each partition set I x I can be obtained by averaging the values of (WZ"")zz,, at all partition sets ! x Iz"", that are subsets of Th X T A similar property applies also the signal. Moreover, by taking limits, it can be shown that the same property holds also for (UR, 9k) and (U1,9t). We now see {(URs ]k) sequence of random variables over the standard probability space [0, 1J The above discussion shows that ((U,, g&) ] is bounded martingale. By the martingale convergence theorem, the sequence {(Uk, 9h) ] converges almost everywhere pointwise to limit g), which must be in WLr.
Lastly, we show that there exist increasing sequences {kg N) and {ts n JAEN such that (W.,, St. "t2 converges to (U, g) in cut distance. By the dominant convergence theorem, for each E N there exists a l- such that
1
[[UU,] 1 <
32
We choose such an increasing sequence {KeLeEN with k2 > 3z. Similarly, for ever E N, there is ju such that, with the notation t, n
((Uk,99k.) (W,,, St. St.)
Imme 111
32'
and we may choose the sequence (1=)=en zeN increasing. Therefore, by the triangle inequality and by the fact that the T norm bounds the cut norm,
8 g), (W1,, )t))) s (1(U))) - (W.,, )ia ||
< (1(Ug)) - -UUk, gk..)l1 + [1(Ukr Ik.)) - (We, St, )2intt
+ II(W v. fta)
desiks (Wes ft, joesies l|a
1
1
3=
3z
3z
The next theorem bounds the covering number of W.,..
Theorem C.2. Let r 0 and > 1. For every sufficiently small > 0, the space WC,, can be covered by
<(c) = 2k²
(23)
balls of radius in cut distance, where k = /220/2²
21

---

Proof. Let 1 < <c< d' and 0 < a < 1. Given an enror tolerance ae > 0, using Theorem B.8, take the equipartition I, into n -/ intervals, for which any graphon-signal (W, f) WC, can be approximated by some f), nn in [W,,]I,, up to error ac. Consider the rectangle Rn. [0, 1|m² x 1-r;r]". We identify each element of [WLr]T,, with element of Rn, using the coefficients of (5). More accurately, the coefficients Cs of the step graphon are identifies with the first n entries of a point in Rn,,. and the the coefficients b; of the step signals are identifies with the last entries of a point in Ra Now, consider the quantized rectangle Rn,rs defined as
Ra, - a.)eE)" + 2m n RRn...
Note that R., consists of
n <2(-log loog (a-a)))+11) +1) (1) (22
M S (1-o)e
points. Now, every point æ E Rn, can be approximated by quantized version æQ E Rn, up to emror in normalized & norm
1 - xQll
x
x S S a)ee,
M
where we re-index the entries of x and zQ in a ID sequence. Let us denote by (W. f)g the quantized version of (W,, fn). given by the above equivalence mapping between f). and Rn We hence have
IIW, - (W, fella & ((W. - (Wn, fa) + IIW,,. (Wlla e.
We now choose the parameter Note that for any e' > c, there exists >> 0 that depends on c' such that for any < 6g there is a choice of a (close to 1) such that
n² +2m < 2 ((1-a))) + +1) (n?2 2k
M
a)e
where k /226/ This is shown similarly to the proof of Corollary B.7 and Theorem B.8. We now replace the notation c' + c, which concludes the proof.
D Graphon-signal sampling lemmas
In this appendix, we prove Theorem 3.7. We denote by Wi the space of measurable functions U: [0, 1], and call each U E W1 kernel.
D.1 Formal construction of sampled graph-signals
Let Wo be a graphon, and A' (X, ......... X₂) E [0, 1 We denote by W(A') the adjacency matrix
W(A)= (W Xy)aaset
By abuse of notation, also treat W(A) weighted graph with k nodes and the adjacency matrix (A'). We denote by A = (Ai...., AR) (X,,... X₂) + (X,,..X))) the identity random variable
in [o, 1].. We hence call (AI...., >x) random independent samples from [0, 1]. We call the random variable W(A) random sampled weighted graph.
Given f E -.20 [0, 1] and A' = (A, k nodes, and value f(X)) for each node 1,...,k k. We define the sampled signal the random variable (A).
..))
M E [o, 11= we denote by f(A') the discrete signal with
We then define the random sampled simple graph as follows. First, for deterministic A' g [o, 1j we define 2D array of Bernoulli random variables (ei (A')) where (A,) 1 in probability
22

---

X3), and zero otherwise, for 2,j [k]. We define the probability space {0, 13 with normalized counting measure, defined for any C.C. 10, [0, 1 by
PN(8) Σ II Passa(zasss R (.JEMM
where
W(Y,)))
if zf
Pacss(Eig)) = 1 1 (W, Xg)
if z.
We denote the identity random variable by G(W,A') sampled (A').
and call it random simple graph
Next we also allow to "plug" the random variable A into A'. For that, we define the joint probability space f2 [0, 1] x {0, 1 ja with the product r-algebra of the Lebesgue sets [o, 1] with the power set o-algebra of {0, 1] with measure, for any measurable S2
msS) Juar (s(S))))
where
S(A') (0. (2 (aLStRJE(M {0, 10,1) (A', E),
We call the random variable G(W,A) :'' + the random simple graph generated by W. We extend the domains of the random variables (A), f(A) and C(W,A) to Z trivially (e.g.. [(A) 2) ((A)(A)) and G(W, AA'', z) C(W, that all random variables defined over the same space Ω. Note that the random sampled graphs and the random signal share the same sample points.
Given a kernel U E W1. we define the random sampled kernel (AA similarly.
Similarly to the above construction, given a weighted graph H with & nodes and edge weights haj- we define the simple graph sampled from H as the random variable simple graph G(H) with nodes and independent Bernoulli variables Cij {0, 1}, with P(er, = 1) ha,j, as the edge weights. The following lemma taken from [24, Equation (10.9)).
Lemma D.1. Let Hl be a weighted graph of k nodes. Then
11
E(d)(G(H).HH) <
Vi
The following a simple corollary of Lemma D.I, using the law of total probability. Corollary D.2. Let W E Wo and le E N. Then
11
E(d=(G(W.A) S
VI
D.2 Sampling lemmas of graphon-signals
The following lemma, from [24, Lemma 10.6], shows that the cut norm of kernel is approximated by the cut norm of its sample.
Lemma D.3 (First Sampling Lemma for kernels). Let U E W1, and A E [0, 1] be uniform independent samples from [0, 1). Then, with probability least - 4e V5/10
3 < [U[A]ll k
8
11 < 11/4"
We derive a version of Lemma D.3 with expected value using the following lemma.
Lemma D.4. Let Ω + [o, 1] be a random variable over the probability space Ω. Suppose that in an event & C of of probability
we have a. Then
B(2)= < (1 (1= +
23

---

Proof.
[2() / z(0)dxx
-se =(()dd J =(x)de s (1 t)a 46
As result of this lemma, we have a simple corollary of Lemma D.3.
Corollary D.5 (First sampling lemma expected value version). Let U W1 and A [0, 11th be chosen uniformly at random, where & 2 1. Then
14
E || 1 S
11/4
Proof. By Lemma D.4, and since 6/k1/4 > 4e- VV/110
E [|[]]]lo ||U|a|| s (1 de VVE/10))
1:14 + 4e 1e-4evAA
8
-V/110
<
14 41/4
We note that version of the first sampling lemma, Lemma D.3, for signals instead of kernels, is just a classical Monte Carlo approximation, when working with the I, [0, 1] norm, which is equivalent to the signal cut norm.
Lemma D.6 (First sampling lemma for signals). Let f E C [0, 1]. Then
Illf(A))lı 11.lla1 S k1/2"
Proof. By standard Monte Carlo theory, since ,2 bounds the variance of f()), where is a random uniform sample from [0, 1]. we have
V(II(())ll)) = (EII((())] - 11/111 I 22
k
Here, V denotes variance, and we note that B|]f(A)]I E (f(1)((()))) Cauchy Schwarz inequality,
Ilfll1.
Hence, by
[I)) - II S V ( -
S
K1/2
now extend [24, Lemma 10. 16), which bounds the cut distance between graphon and sampled graph, to the case of a sampled graphon-signal.
Theorem D.7 (Second sampling lemma for graphon signals). Leir > 1. Let 2 Ko, where Ko is constant that depends on r, and let (W, E W.,,, Then,
15
E 8m ((W, (W(A).
Vlog(k)
and
E (OL((WV.D
15
/log(k)
The proof follows the steps of [24, Lemma 10.16] and [4]. We note that the main difference in our proof is that we explicitly write the measure preserving bijection that optimizes the cut distance. While this is not necessary in the classical case, where only graphon is sampled, in our case need to show that there is measure preserving bijection that is shared by the graphon and the signal. We hence write the proof for completion.
Proof.
Denote a generic error bound, given by the regularity lemma Theorem B.8 by If we take intervals the Theorem B.8, then the error in the regularity lemma will be, for such that 2c 3,
[3/e²1 log(nz)

---

SO
3/2 2 log(n).
For small enough we increase the enror bound in the regularity lemma to satisfy
4/e² > 3/c² + log(n).
More accurately, for the equipartition intervals In. there o' E 1lo.11 and piecewise constant graphon signal ([W*,, (x) such that
2
|| - [ Inlln S Vlog(n)
and
2
1 1/0 S o)
Vlog(n)
for some S 1. If we choose such that
Vk rlg((k)
1.
then error bound in the regularity lemma is
I [W Inllo S a
2
V log(k) - log (log(A:) log(r)
and
11 - In S a))
2
log(k: - log (log(A)) log(r)
for some S a S 1. Without loss of generality, we suppose that ø' is the identity. This only means that we work with different representative of [) E WLr throughout the proof. We hence have
2/2
dwWW, S a
Vlg(k)) 2og (log({)) 2 log(r)
and
4
|/ - Sull S (1 -x) ())
log((k) 2 log (Iog(A)) 2 log(r) for some step graphon-signal (W,, fn) [WCrl... Now, by the first sampling lemma (Corollary D.5),
14
E d (W()). W,, (A)) dn(W, Wwn) 41/4"
Moreover, by the fact that fn E C3: (0, 1). Lemma D.6 implies that
2r
E ([(())) (A)ll || fallal s 11/2
Therefore,
(W(()), < BldDddWWWAL (n)()) - dd(W, Ww)l doW,,
14
2
1//4 +a
/log(k) log ( (log(I)) log(r)
Similarly, we have
El)s(A) fn(A)ll S E (A) fa(A)l1 - ffllil + +If - fulli
2r
4
<
+ (1 a))
11/2
Vlog(k) 2 log (log(k)) 2 2log(r)
25

---

Now, let TA be a sorting permutation in [k], such that
(A) : ( = (X1....,,a ./22
a sequence in a non-decreasing order. Let (T [i [i=1, be the intervals of the equipartition
Ig. The sorting permutation тA induces a measure preserving bijection & that sorts the intervals Ti. Namely, we define, for every x E [0, 1].
if E Th <(x) = Ji,aat)))
(24)
where Jez: : : + 1g are defined as + i/k + +j/k, for all x E T..
By abuse of notation, we denote by (A) and (A) the induced graphon and signal from (A) and (A) respectively. Hence, (A)* and (A))
well defined. Note that the graphons W,, and (A) are stepfunctions, where the set of values of Wn, (A) is subset of the set of values of W,. Intuitively, since k >> m, we expect the partition {[G, X+1 } to be "close to a refinement" In, in high probability. Also, we expect the two sets of values of W, and W,, to be identical in high probability. Moreover, since A' is sorted, when inducing a graphon from the graph (A(A) and "sorting" it to (A)9, we get a graphon that is roughly "aligned" with Wn. The same philosophy also applied to fn and (A)* We next formalize these observations.
For each i E [n]] let X₁, be the smaller point of A' that is in Ly, set ji = j+t1 if I, = 0, and set jat1 = 1 + 1. For every i 1, .....,................ n, we call
J, lj - 1,,+1 - 1)/k
the i-th step of Wn, (A) (which can be the empty set). Let a; -- be the left edge point of J.- Note that ag |A n [0, /k is distributed binomially (up to the normalization k) with & trials and success probability i/n.
IW,, W. (A) S 1|
W. (A)
ΣΣ JISNU SIANU
W (x)))( x) drdy
ΣΣΣΣS
Wn - W. (A) (xr, v) drdy
k Lik Ignny 1884
ΣΣΣΣ SK iti
(w((z,)) (A) (z. v) drdy
1fk JanJ, JINT
ΣΣ J JA Jaay
[W((z,)) -Wx))) (I, أ) dxdy
S JINA 18
Say. ddxyy $2 >
S Jes 1drdy
5 2 Σ (li/n mt//nnouh ail + (i 1)/n a)+1l).
Hence,
B,WW, - Wn(A)* 2 Σ (Eli// ail + ((: + 1)/n ai+1l)
> /Bliin - -3)) + V E((i + 1)/n act1)²
By properties of the binomial distribution, we have E(ka;) ik/n, so
B(ik/nn ka,)² V(ka,) k(i/n)(1 i/mo)
As result
(i/n) - i/m1)
W,WW,, Wa(A)) S Σ
(i/n) (1 - -i/m) k
2
di.
26

---

and for n >> 10,
S Vk
n
!
V2- d2 S n
V & 10/3(1.1)8/2
3//1 n
<
4 n2 vk
Vk
vk
Now, by n (k)
VI
vk r (kg(k)
+ 1, for large enough k.
1 +4
W, Wn(A))ll 1
vk v
r llg((k)
rlog(k)
Similarly,
5
E (m v
(k)
Note that in the proof of Corollary B.7, in (16), a is chosen close to 1, and especially, for small enough e, > 1/2. Hence, for large enough k,
B(da(W, (A)))) & dw, W.,) B(da W,,(A))) ((dn (())))
2/2
rlog(k) + 14
5
<a
+
k1/4
V log(k)) - 2 log (log(k)) - 2 log(r)
2v2
+
/og(kk)
log (log({:) 2 log(r)
6
/ (lo
Similarly, for each k, 1 a <
then
Vlog(A)
2v2
B(da(I,((A))) s (1 a)
(k)
log(k) log (log(+)) log(r)
2r
4
+ (1 - a)
1:/2
v /lg(()) 2 log (log(k)) log(r)
log(A:)
Moreover, for each & such that 1 a depends on r), we have
if ls large enough (where the lower bound of
v (k
5
2r
5.5
6
6
+
<1 a.)
log(k)
11/2
log(k)
Mlg((k) Vlo((k)
Vlg(k))
80, by 6v < 9,
2v
2
((A)(f $ (1-a)
V /lg(k)) 2 2log (log(A)) log(r)
log(k)
2r
4V2
+ (1 - a))
k1/2
/log(k) 2log (log(k)) 2 log(()
15
< (1 a)
v /lg((k)
Lastly, by Corollary D.2.
E ((d((W.((W.))))
< 18 ((, + IE (dD(W(A)),c(w))))))
6
11
Sa
S
Vlog(k)
Vk
Vlog(k)
27

---

As result, for large enough k,
E ((((
15 Vlog(k)
and
E ((D((V.D).
15
Vlog(k)
E
Graphon-signal MPNNs
In this appendix we give properties and examples of MPNNs.
E.1 Properties of graphon-signal MPNNs
Consider the construction of MPNN from Section 4.1. We first explain how MPNN grpah is equivalent to MPNN on the induced graphon.
Let G be a graph of nodes, with adjacency matrix A = {a:j and signal f E Rn Consider MPL 0, with receiver and transmitter message functions & & R + R' for & E [K], where K N, and update function RR++ - R The application of the MPL on (G, f) is defined as follows. We first define the message kernel 4r [n]] RP, with entries
- (f.
Σ (C))))))))))
We then aggregate the message kernel with normalized sum aggregation
1 Σ ai
(Agg(G, +r)), n jE(n
(r(i,))
Lastly, apply the update function, to obtain the output ((G, f) of the MPL with value each node
i
B(G, f): = (F, (Agg(G, +f)), TR...
Lemma E.1. Consider a MPL 0 as in the above setting. Then, for every graph signal (G, A,),
e @ (WW.)))))) = (W, (W.f)o(G.))
Proof. Let .i....,, 3 be the equipartition to intervals. For each E [n]. let Dj ly be an arbitrary point. Let i E [n] and x E I. We have
Agg(G, Pr);
1
Σ a.. fr(i 1
Σ ;,, (x,
,E[n]
jE[n
Wa(a, v) ( Agg (,) [
Therefore, for every i E [n] and every æ L,,
(x) (((AAes(c (x) Agg 0s).
= =((((z)), ()))))
28

---

E.2 Examples of MPNNS
The GIN convolutional layer [36] defined as follows. First, the message function is
$(a, b) =
and the update function
7722 v) M where M a multi-layer perceptron (MLP) and c a constant. Each layer may have different MLP and different constant The standard GIN is defined with sum aggregation, but we use normalized sum aggregation.
Given a graph-signal (G, f), with E Raxd with adjacency matrix A E R a spectral convo- lutional layer based on polynomial filter p(A) Eo NCJ, where Cj _d is defined to be
p(A)f = Σ Σ A'IC, j=0 m
A'CC,
followed by pointwise non-linearity like ReLU. Such convolutional layer can be as J + MPLs. We first apply J MPLs, where each MPL is of the form
((f) (f. 7
Af).
We then apply an update layer
U(f) rC
for some C' E (JJ1)dd followed by the pointwise non-linearity. The message part of 0 can be written our formulation with ((a, 6) = 6, and the update part of 0 with nie, d) = (c, d). The last update layer U is linear followed by the pointwise non-linearity,
Lipschitz continuity of MPNNS
In this appendix prove Theorem 4.1. For Rd, often denote by |o| ||e|oco We define the La norm of measurable function h [0 - Rd by
||4|1 = f/² [1(x) dx = [( [1(2z)l
Similarly,
|// == sup [h(x)] zERd
sup [|(
zExd
We define Lipschitz continuity with respect to the infinity norm. Namely, 7 Rdd Lipschitz continuous with Lipschitz constant T, if
Re is called
(xx) - (z)) = |Z((x) - Z(y) S L| - =||m = L - z|.
We denote the minimal Lipschitz bound of the function Z by Lz.
We extend L.S [0, 1] to the space of functions f | + Rd with the above L norm.
Define the space Ky of kernels bounded by q > to be the space of measurable functions
K [0, 1 + !-4.4] 4].
The cut norm, cut metric, and cut distance are defined as usual for kernels in Kgg.
F1 Lipschitz continuity of message passing and update layers
In this subsection we prove that message passing layers and update layers are Lipschitz continuous with respect to he graphon-signal cut metric.
29

---

Lemma F.1 (Product rule for message kernels). Let y, Dg be the message kernels corresponding to the signals f.g. Then
K
|0, - $ 11111
Theell + 115 110/ Le: (15
9ll1-
Proof. Suppose p For every v, [0. 1]2
K
K
( v) $5 ((1,,)1= w) =
Σ {((+))
Σ (c()))
K
-
- - oto0 - (o(=))
K
Le: - (1( ((())
(5()) -
Hence,
|| 10,
Σ 1/' / ((0)) 9())) (f(())) + | (x(x)) Let (f(e) ا(v)و drdy
K
1e 111111//1100 + ||5/ |If 91l1)
Lee 115 Ilxe + |15 Too Tuet)
I| - 9/l1.
Lemma F.2. Let Q, V be two message kernels, and W Wy Then
Aggg(, Q) Agx(W, Vill s I|Q - VIl..
Proof.
Agg(W,Q)(z) Ags(W, ()))) S ((2,))(((z,v)) V V(x, w))dy So
|| Aggg(W Q) Agg(W, W. V)I1 (/1 1// ((x,))(((x,1)) - V(x, vy dr
< /.¹ [ (((r,))((z,,)) - V(r, dyde
1'" L. ((((. - Vaz, v)) v)) dydr 11Q - Vll..
As result of Lemma F.2 and the product rule Lemma F.1, we have the following corollary, that computes the error in aggregating two message kernels with the same graphon. Corollary F3.
Agg [. 0,) Agg(W, 11) S
Le 1loo bo )1f gl1--
30

---

Next we fix the message kernel, and bound the difference between the aggregation of the message kernel with respect to two different graphons. Let L [0. 1] be the space of measurable function f: (0, 1] - [0, I|. The following lemma is a trivial extension of [24, Lemma 8. 8.10J from Kr to K,,
Lemma F.4. For any kernel Q E Kr
I f(x) ((=))(z
IQl|a= =
sup f. [0.1] 1o.1p
where the supremum is altained for some f.g E [,+ 1].
The following Lemma is proven as part of the proof of [24, Lemma 8.11].
Lemma F.S. For any kernel Q E Krr
sup 1 L [0.1] 10.13
S 4/]
For completeness, we give here self-contained proof.
Proof. Any function f E [0, 1] can be written as ʃ = S+ - S-, where f+,S- E 1= 1]. Hence, by Lemma F.4,
sup LeE [0.1] 1.11
I
+4.f--+-9--- [0.1] Jo.1 (-(1)))-((()))aa - 9 (v) dxdy
sup
/ Σ sup +E(+,-) fe E [0.1] 10.12
Next we state simple lemma.
Lemma F6. Let f+ f- be a signal, where f-, [0,1] oo) are measurable. Then the supremuam in the cut norm |[f]]- supsc(oo1] [[s fx) is attained the support of either f+ or S_
Lemma F., Let f L. [0, 1], W.V E Wo. and suppose that (f(x)) (+(((())) I S for every x E [0, 1] and k = 1,..., K. Then
[[Agg(W, 2 Agg(V, (m < 4Kp2 Vll.. Moreover, ch and & are non-negatively valued for every 1,..., K, then
(, - Ag f - K IIW Vlla-
Proof. Let W V. Let be the maximizer of the supremum underlying the cut norm of Agg(T, p) Suppose without loss of generality that fS Agg(T, ( > 0. Denote (x) (f()) and (x)) (f(x)). We have
/ (Agg(W; (W, (ggg(W,,,)(r) (x) Agg(V, (ss(V,)))()))d) Agg(T, (T))))
[ &
Σ k=1
Let
<²(x) = { (x)/pp E S
(25)
x $ S.
31

---

Moreover, define of = /f/pp pp, and note that ext of E L0 11. We hence have, by Lemma F.5,
/ Agg(T, ( (x)(
Σ p² L. S. (x) v) (y)dddr
k=1
k=1
- 4k 4K
Hence,
Agg W, xy) - Agg( V. 1 - AKp2lTT|l Lastly, in case et et are nonnegatively valued, q. ot. and hence by Lemma F.4,
(f)) S Kp'lTT
Theorem F.8. Let (V, WL,, and suppose that [<t([())) (<((())) p and Let Let < L for every [0, 1] and k = 1....,K. K. Then,
|Aggg( W, , Agg( V, 2 l S 4KLp allo + 4Kp²|| -VIb.
Proof. By Lemma F.1, Lemma F.2 and Lemma F.7,
Agg W, ,) Ag T)
Agg W. 22)) WW, 22)l + [[Agg(W, 9,) Agg(V, (VV,,))l 9,)IIn
K
Les 1l.l1///1o + |1 Let |l 1l1e + 4Kpp - Vllo
k=1
s 4KLp alla + 4Kpp - Vll..
Lastly, we show that update layers are Lipschitz continuous. Since the update function takes two functions f: [0, 1] -> R.d. (for generally two different output dimensions d1, d2), we "concatenate" these two inputs and treat it as one input f [0, 1] + +ds,
Lemma F.9. Let 17 Rd+p + RR be Lipschitz with Lipschitz constant Ly, and let f.g E [0, with values in Rd++P for some d,y N. Then
Inn()) n())lli S I.,llS gll1-
Proof.
Iln()) m(0)1 L.¹ In([(x)) - -n((x))) da
[ 1,15(x) ((x) dr Lulls g|l1.
F.2 Bounds of signals and MPLs with Lipschitz message and update functions
We will consider three settings for the MPNN Lipschitz bounds. In all settings, the transmitter, receiver, and update functions are Lipschitz. the first setting all message and update functions are assumed to be bounded. In the second setting, there is no additional assumption over Lipschtzness of the transmitter, receiver, and update functions. In the third setting, we assume that the message function & is also Lipschitz with Lipschitz bound Lg, and that all receiver and transmitter functions
32

---

are nen-eeettvveyy bounded (e.g., via an application of ReLU or sigmoid in their implementation). Note that in case K 1 and all functions are differentiable, by the product rule, can be Lipschitz only in two cases: if both çr and ş are bounded and Lipschitz, or if either &r or & is constant, and the other function Lipschitz. When K 1, we can have combinations of these cases.
We next derive bounds for the different settings. A bound for setting is given in Theorem F,8. Moreover, When the receiver and transmitter message functions and the update functions are bounded, so is the signal at each layer.
Bounds for setting 2.
Next we show boundedness when the receiver and transmitter message and update functions are only assumed to be Lipschitz.
Define the formal bias Bg of function ş IRd R to be [(O) [26]. We note that the formal bias of an affine-linear operator is its classical bias.
Lemma F.10. Let (W W.,., and suppose that for every y E fr, t) and h: 1,.... K
|s)( S BB
Log <
Then, and
| fllo S Lr + B [[Ag S K(Lr + B)²
Proof. yet E (r, We have
(f())) (=)) +5)) B < Leg [f(x)] + B s Lr + B,
Σ [ () k=1
Aggg(W, (z)(
S (Lr B)²
Next, we have a direct result of Theorem F.8. Corollary F.11. Suppose that for every y E (I,t) and is I,...,K
[y) s B, Lgg < <.
Then, for every f), WC,,
|[Agg(W, 2 Ag, & 2)) &
+ - I-
Bound for setting 3. Lemma F.12. Let (W, E WC,, and suppose that
(0 0)1 < B, La < L.
Then,
| - Lr + B |Agg((, 11) I Lr + B.
and
Proof. We have
((f( < ((f(2), 4 + B La B B Lr +B
sO,
Agg(W, o,)(x)) / ((.:))((())
Lr +B
33

---

Additional bounds.
Lemma F.13. Let f be signal, W, V E Wo. and suppose that y I for every k = =1,.. .......K and that e and ek are non-negatively valued. Then
[Ag 4)) Agg(V (ug(V, S KpllW Vlla-
Proof. The proof follows the steps of Lemma F.7 until (25), from where we proceed differently. Since all of the functions g,¹ and q², & E [K], and since || S p. the product of each q, (z)g (y) must be also bounded by p for every x E [0, 1] and k E [K]. Hence, we may replace the normalization in (25) with
of (x) (x) =
of (x)//F
x xES
x(())=
- ae (v)/pb yES S
0
x $
0
where for every is [K], P = This guarantees that ox, of L 1]. Hence,
/ (Tg (2)dda
Σ
K
1. L. AottaaTTe u) (y)dydæ
R=1
1 ( of () s Kyl/Tlaa
k=1
Theorem F.14. Let (W, (V.g) WLr,, and suppose that (1,1,,,1155 11// 11 S all message functions & are non-negative valued, and Lugt Let I., for every I,....
... K. Then,
Agg b1) Agg(V, o 9 S 4KLp ollo KplW - Vllo-
The proof follows the steps of Theorem F.8. Corollary F.1.. Suppose that for every y E (r,1) and k I,...,
| 0) 0)1 (0)) s B, Lo, Lez L,
and 5, & are all non-negatively valued. Then, for every (W, (V.g) E WC,.
|Agg( 2 Agg(V, 21)l < 4K(L'r LB) دااb + K(Lr + B)[lW Vllo.
The proof follows the steps of Corollary F.1..
F33
Lipschitz continuity theorems for MPNNs
The following recurrence sequence will govern the propagation of the Lipschitz constant of the MPNN and the bound of signal along the layers.
Lemma F.16. Let (a1,a2, .2....) and b (bi, .2....). .). The solution e a,e, by with
initialization co, is
e Zi b, co)
II ΣI 1=
ajco +
bi-
(26)
where, by convention,
1.
In case there exist a, b E IR such that o; a and by = b for every i,
e: a'éa
a.b.
1=
34

---

Setting 1.
Theorem F.17. Ler θ be MPNN with T layers. Suppose that for every layer and every and k.
loo; lln' P.
Legt Lagz < L.
Let (W,f), (V. E WC,. Then, for MPNN with no update function
[[O,WW,)) f) .. (4KL 9llcc + Σ
A -V Vllo,
5=0
for MPNN with update function
(0.W, .. < (4KT2 allo + E
- Vlla-
==0
Proof. We prove for MPNNs with update function, where the proof without update function is similar. We can write recurrence sequence for bound |W, f) Lemma F.9, as
(V, 9) In S by Theorem F88 and
1 = 4KL2 pep + pK L|| VIlo.
The proof now follows by applying Lemma F.16 with a = 4KK2 and b = 4K
Setting& 2.
Lemma F.18. Let θ be a MPNN with T layers. Suppose that for every layer t and every E {r,t} and k E [K].
|7)( (0)) S B, Lggr Ligz < L
with L, B > 1. Les (W,J) WL,,, Then, for MPNN without update function, for every layer
[0,(W, (2KL3B2)² 11
and MPNN with update function, for every layer I,
(W, (2KL*B2)2* 1f
Proof. We first prove for MPNNs without update functions. Denote by Ct bound on [ and let Co bound on |ol By Lemma F.10, we may choose bounds such that
C441 KLLC, B)² KL2C, 2KLBC, + KB².
We always choose Ct, K, L 1, and therefore,
C+11 S KL2C? 2KLBC, KB <2KL"B'C
Denote 2KLBB2 We have
C++1 = a(C,)² = alaCt_1) 1+2 01 = - 1+ (a(c
=al42+4 ( (C,o)) a² C/'
Now, for MPNNs with update function, we have
Ct+1 LK(LC, B) +B
KT?C? + 2KK KB B < 2 BBC.
and we proceed similarly.
35

---

Theorem F.19. Let Q be a MPNN with T layers. Suppose for every layer t and every E (I,t} and l [
(0), (²) SB Lngt Ingy <L,
with L, > Ler (W,9), (V.9) E W.,. Then, for MPNNs without update functions
[0 (.(V.)) - II
4K (L2r + LB)IIf gllc
1=0
1-1j-1
EI r LB) -VIlo.
where
r. (2K 11f12.
and MPNNs with update functions
[) - ..(V - II
+ L2B]]1 gllo
+
BJ Vlb.
j= =
where
r 32 11.1
Proof. We prove for MPNNs without update functions. The proof for the other case is similar. By Corollary F.11, since the signals layer are bounded by
ft (2KL
we have
(W, 0 91
S 4K (W,)) (VV -M0/://w0...---00000000--------1
Vllo.
We hence derive a recurrence sequence for bound [W., (.(V.))lo cz, as
Et+1 = 4K( + LB)e, 4K(L, B)
We now apply Lemma F.16.
Setting 3. Lemma F.20. Suppose that for every layer and every y E (r,1) and ,,....6 K, (n). (0' 0) I'sx (0) s B, Lyps Loe, Ligz L, and &, t are all non-negatively valued. Then, for MPNNs without update function
1-1 I
< T.11//bb +
J=1
and for MPNNs with update function
(w, f)lo $ 1
Σ L (LB B).
j=1
Proof. We first prove for MPNNs without update functions. By Lemma F.10, there is bound of [We floo that satisfies
e, Le,-1 + B. Solving this recurrence sequence via Lemma F.16 concludes the proof. Lastly, for MPNN with update functions, we have a bound that satisfies
et = L LB B,
and proceed as before.
36

---

Lemma F21. Suppose that for every E (I,t) and k = I.....K K
[n), ((00 1 (0) - B, La Let < L, and &, 2 are all non-negatively valued. Let (W. g) (V.g) WCr. Then, for MPNNs without update functions
[[ +) = BB)) (IW + 1l. -gll))
and for MPNNs with update functions
|0' 4) - (V, O =V
B²) ( Vlla + || -ollo)
Proof. We start with MPNNs without update functions. By Corollary F.15 and Lemma F.20, there is a bound ee on the error ( x) (V, Py) at step that satisfies
e = =K=K((IPr-1) + LBBe--1 + K(Lr B)[ -VIo
1-1 = = <LK(II +
K (LL'II + L'DB B)Il - -Vlo
f=1
f=1
Hence, by Lemma F.16, and Z defined by (26).
e (a, b, ||ʃ oala) WKK' 2 (e PBB ollo I Vlla),
where in the notations of Lemma F.16,
H
at = (I
Σ LBB)+LB)
j=1
and
1 LBB) + BB) - Vlla
b. = = + Σ
Next, for MPNNs with update functions, there is bound that satisfies
e, 4K(L r + + ()2 + + VIl
4K (171)1
Σ LLB B)) + LBB ex-1
K
+ Σ
LL + B)) + LB || - Vlln-
1=1
Hence, by Lemma F.16, and Z defined by (26).
e = 10K*1 31+ 21 B') - + || -Vlc).
G Generalization bound for MPNNs
In this appendix we prove Theorem 4.2.
G.1 Statistical learning and generalization analysis
In the statistical setting of learning, we suppose that the dataset comprises independent random
samples from probability space that describes all possible data P. We suppose that for each P there is a ground truth value yr. E ),, e.g., the ground truth class or value of x, where y is, in general, some measure space. The loss is measurable function L y2 - R_ that defines
37

---

similarity in y. Given a measurable function : - y. that we call the model or network, its accuracy on all potential inputs is defined as the statistical risk Rets(()) = EgEp (()()), yu)) The goal in learning is to find network θ, from some hypothesis space T, that has low statistical risk. In practice, the statistical risk cannot be computed analytically. Instead, we suppose that a dataset X [m JM C P of M E N random independent samples with corresponding values {ym LM C y is given. We estimate the statistical risk via a "Monte Carlo approximation," called the empirical risk (9) optimizing the empirical risk. The goal in generalization analysis is to show that if a learned O attains low empirical risk, then it is also guaranteed to have low statistical risk.
T Em=i& [(O(zm), Bm). The network θ is chosen in practice by
One technique for bounding the statistical risk in terms of the empirical risk to use the bound Retat (+) S (e) + E, where E is the generalization error E supeet RRstee (+) Remp(() (+),, and to find a bound for E. Since the trained network θ = Ox depends on the data X, the network is not a constant when varying the dataset, and hence the empirical risk is not really a Monte Carlo approximation of the statistical risk in the learning set- ting. If the network & was fixed, then Monte Carlo theory would have given bound of E² of order O (x())/M) in an event of probability 1 - p, where, for example, in Hoeffding's 's inequality Theorem G.2, x(p) = 12g(2/p)) Let us call such an event a good sampling event. Since the good sampling event depends on θ, computing naive bound to the generalization error would require intersecting all good sampling events for all O E T. Uniform convergence bounds are approaches for intersecting adequate sampling events that allow bounding the generalization error more efficiently. This intersection of events leads to a term in the generalization bound, called the complexity/capacityy that describes the richness of the hypothesis space T. This is the philosophy behind approaches such as VC-dimension, Rademacher dimension, fat-shattering dimension, pseudo-dimension and uniform covering number (see, e.g., [34]).
G.2 Classification setting
We define ground truth classifier into C classes as follows. Let C WC, - RCC be measur- able piecewise constant function of the following form. There is a partition of W.,, into disjoint measurable sets Bi..... Be C WL, such that U. B, WL,, and for every i [C] and every x E Bi,
C(x) Ci.
where E IRC is the standard basis element with entries (et), = ōe.j. where ōz, is the Kronecker delta.
We define an arbitrary data distribution as follows. Let B be the Borel o-algebra of WC,, and v be any probability measure on the measurable space (WLr,, B). We may assume that we complete B with respect to v, obtaining the o-algebra E. If we do not complete the measure, we just denote Σ == B. Defining (WCr, Σ, 2/) as complete measure space or not will not affect our construction.
Let S be a metric space. Let Lip(S, L) be the space of Lipschitz continuous mappings : RC with Lipschitz constant L. Note that by Theorem 4.1, for every i E [C]. the space of MPNN with Lipschitz continuous input and output message functions and Lipschitz update functions, restricted to B, is a subset of Lip( B,, I2) which is the restriction of Lip(WC,, L1) to B; C WC,, for some L1 > O. Moreover, B; has finite covering k(c) given in (23). Let E be Lipschitz continuous loss function with Lipschitz constant L2. Therefore, since C\P, is in Lip 0), for any T E Lip(WC,, L.), the function (BT),, ()B,)) is in Lip( (Bi L.) with L L Tz.
G.3 Uniform Monte Carlo approximation of Lipschitz continuous functions
The proof of Theorem 4.2 is based on the following Theorem G.3, which studies uniform Monte Carlo approximations of Lipschitz continuous functions over metric spaces with finite covering.
Definition G.1. A metric space M is said to have covering number K : (0, oo) + N, for every é > 0, the space M can be covered by k(E) ball of radius
38

---

Theorem G.2 (Hoeffding's s inequality). Let Yi...., Yv be independent random variables such that Y almost surely. Then, for every k 0,
P Σ IX P(
(x B[x.)) 2 2k) - 2exp
N
(- ( a)3
21 (b
The following theorem is an extended version of [26, Lemma B.3], where the difference is that we use general covering number k((), where in [26, Lemma B.3] the covering number is exponential c. For completion, we repeat here the proof, with the required modification.
Theorem G.3 (Uniform Monte Carlo approximation for Lipschitz continuous functions). Let X' be probability metric space', with probability measure μa, and covering number k(c). Let XI..... X be drawn Li.dd from X. Then, for every > O, there exists an event Eip C CXN (regarding the choice of XN)) with probability
N (
2 1-p;
such that for every (X1...., XN) Lip for every bounded Lipschitz continuous function F X Td with Lipschitz constant LF, we have
V F(z)du(() - N Σ F(X,)
2 22) + -- (N)] vlog(2/p)), (27)
V2
where E(r) r(()) (((r)log(((r)) log(n(r)) and g-1 is the inverse function 5f
Proof. Let > 0. There exists covering of X by a set of balls {By)eeJ of radius r, where J= x()). j ..... J, define is family of measurable sets such that I n 4 0 for all i + j E [J]. Use For each j E [J], let 2j be the
Bj Uie B,, and define I1 = B₁. Hence, {Ti)je(J]
X. and
diam(1,) < 2r for all j [J], where by convention diam( center of the ball Bj.
Next, we compute a concentration of error bound on the difference between the measure of I, and its Monte Carlo approximation, which is uniform in j E [J]. Let [J] and q E (0, 1). By Hoeffding's inequality Theorem G.2, there is event Ej with probability u(E)) 2 1 q, in which
N 1x,)) -u(k))
1
1og(2/9)
(28)
N
V2
VN
00
Consider the event
J
Lip n Eg
with probability N (Er/g) 2 Jq. In this event, (28) holds for all j J. We change the failure cJy
probability variable Jq. and denote EL,, =
Next we bound uniformly the Monte Carlo approximation emror of the integral of bounded Lipschitz continuous functions F x - IRF. Let F x + R² be bounded Lipschitz continuous function with Lipschitz, constant LF. We define the step function
(T())
Σ F(2;)11,1)) JE(J]
'A metric space with probability Borel measure, where we either take the completion of the measure space with respect y (adding all subsets of null-sett the o-algebra) or not.
39

---

Then.
N
N
1 N
F(X,) - 1 F(u)du(v)
F(Xi)
Σ E=1
F" (X,)
N
N
N
i=1
P*(X.) [ F" ('(()du(()
(29)
/ F(y)du(y)
("
(1) + +2)+(())
To bound (1), we define for each X; the unique index j: E [J] s.t. X; E Ii.. We calculate,
1 N
1 N N 1=1
N
F(X:)
Σ FT
(X+)
F(Xi) - E F1
N
N i=1
JEJ
[F(x))
F(2
N
<rLp.
We proceed by bounding (2). In the event of Lap which holds with probability at least equation (28) holds for all E T. In this event, we get
FT (X.))
-1 (T(e)du(e))
Σ
N
(x.)) - - -f F(2))dy)
N 1=1
N
1=1
Σ jE[J]
F DJ
Σ
(X,) m(Iz)
N
Vlog(2J/p)
$ Fl
V2
VN
Recall that J = =(()). Then, with probability at least - p
N
F (X+) - F" ("))dp()))
N
vlog(n(r) + l2g(2/p)
S F(rrl|Fllx
V2
VN
To bound (3), we calculate
-1 Σ 11 1 F(v)duw))
1/ ('(()du(u) - / F(w)dnte)
jE[J]]
Σ / | |F(z;) F(y)llo du(y)
JEM < rLp.
1,
40

---

By plugging the bounds of (1), (2) and (3) into (29), we get
N Σ F(Xi) J F(y)dp(v)
1
log(n(r)) + log(2/p)
2rLF + k(r)]lF7llo
V2
VN
S 2rLF + V2 k(()) log(n(r)) + (2/p)
log(H(()) (1 + 1og(2/p))
S Lr + v2
(rr)|
VN
Lastly, choosing r = (N) for ((r) =(r)²
<og))))g((()) log(n(r))
gives ((r)/log(x(r))
VN
=r, =0,00
N Σ F(X)) - / F(V)du())
25 (N)L V2 (N)) + Vlg((2/p))
Since the event Lip is independent of the choice of F F RR, the proof is finished.
G.4 generalization theorem for MPNNS
The following generalization theorem of MPNN is now direct result of Theorem G.3.
Let Lip(WE,, L1) denote the space of Lipschitz continuous functions θ WC, + R with Lipschitz bound bounded by L1 and ||0|| S Li. We note that the theorems of Appendix F.2 prove that MPNN with Lipschitz continuous message and update functions, and bounded formal biases, are Lip(WE,, Ln).
Theorem G.4 (MPNN generalization theorem). Consider the classification setting of Appendix G.2. Let XI...., X independent random samples from the data distribution (WL,, E, v). Then, for every p > 0, there exists an event E C W.2," regarding the choice of (X1..... N with probability
N
C² N
U (8 ((pp)21-Cp-22
in which for every function Y in the hypothesis class Lip(WL.r: IA), with we have
R((x)) - R(Tx, x) s (N/20))))
1
(L ((0,0)) vlog(2/p))
(30)
/2
where E(r) = k(r) log(n())) k. is the covering number of WC, given in (23), and g-1 is the inverse
function of
Proof. For each i E [C], let S, be the number of samples of X that falls within B, The ran- dom variable (S,.... Sc) multinomial. with expected value (N/C,...,N/C) and variance
N(C-1) MCC-1) C# 0 I (N ....... N) We now use Chebyshev's inequality, which states that for any 0,
N P > o
/ <a
N1/2
We choose a
20, so
201/7: and
N
2C
P([S, N/C1>
20
N
Therefore,
N
2C
P(S. 20
41

---

We intersect these events of E [C], and get an event &milt of probability more than 1 1-2 N for every i [C]. In the following, given set B, we consider realization M S and then use the law of total probability.
6 in which
S 20
From Theorem G.3 we get the following, For every > 0, there exists event & C B regarding the choice of (X1,..., Xar) C Bs, with probability
v (E(ip) 2 1lpp. p.
such that for every function T' in the hypothesis class Lip(WCr: L1), we have
/ ((TT()),
M
((X(())),((x.))
(31)
M
2 (M)L
/
V2 5 (MM)E (1..111+/11//////111 vlog(2/p))
(32)
$ 25-2
// - + (1) + - llo(2/p)),
(33)
where E(r) = x(r)* log(n(r)) k is the covering number of WC, given in (23), and andg- 5-1 is the inverse the bound, for every x WC,,
function of In the last inequality, [=(T(()),C())) $ (T)) - E(O, 0) + [0, 0) - L2 [ - 0| + {0 0)l Since (31) true for any Y' Lip(WC, Li), ), is also true for Tx for any realization X, so we also have
R(Tx) - R(Tx. x)
s 225 + 5 (N/22)
+ Vlog(2/p))
V2
Lastly, denote
- = Emul
(U E i=1
G.5 Experiments
The nontrivial part in our construction of the MPNN architecture the choice of normalized sum aggregation as the aggregation method of the MPNNs. We hence show the accuracy and generalization gap of this aggregation scheme practice in Table 1.
Most MPNNs typically use sum, mean or max aggregation. Intuitively, normalized sum aggregation close to average aggregation, due its "normalized nature." For example, normalized sum and mean aggregations are well behaved for dense graphs with number of nodes going to infinity, while sum aggregation diverges for such graphs. Moreover, sum aggregation cannot be extended to graphons, while normalized sum and mean aggregations can. In Table 2, we first show that MPNNs with normalized sum aggregation perform well and generalize well. We then compare the normalized sum aggregation MPNNs (in rows and 3 of Table 2) to bascline MPNNs with mean aggregation (rows 2 and 4 Table 2). and show that normalized sum aggregation is not worse than mean aggregation.
The source code, courtesy of Ningyuan (Teresa) Huang, is available as part of pettps//githhn com/nhuang37/ / wwwriiinnnnnneeeeeereeeeeee
H Stability of MPNNs to graph subsampling
Lastly, we prove Theorem 4.3.
Theorem H.1. Consider the setting of Theorem 4.2, and let & be a MPNN with Lipschitz constant L. Denote
== (W,OW,,)), and Σ(A) (GGW,N)
Then
E ( ((())))())
15 L.
Vlog(k)
42

---

Table 2: Standard MPNN architectures with normalized aggregation (nsa) and aggregation (ma), 3-layers with 312-hidden-dimensionn and global mean pooling, denoted by "MPNN-nSS and "MPNN-ma." We the MPNNs GIN [34] and GraphCony [28], and report the mean accuracy + std over ten data splits. Nsa has good generalization and better performance than ma.
Accurney
MUTAC
IMDE: BIN-BBN
IMDR-MUL.TI
NC11
PROTEINS
REDOIT-BINARY
GIN--ns (train)
83.94 3.25
70.54 d: 0.79
47.01 0.8
83.12 4: 0.59
74.06 0.44
90.43 1: 0.53
GiN-nsa (test)
79.36 2,93
69.83 +: 0.93
46.01 +: 1.01
78.55 +: 0.3
73.11 0.81
89.38 + 0.57
GIN-ma (trained)
74.63 d: 2.93
49.48 d: 1.56
33,70 d: 1.35
73.74 d: 0.45
71.53 0.93
50.04 d: 0.70
GIN-ma (untrnined)
72,46 2.56
33.03 1.12
77.16 0.39
70.33 0.98
d: 0.83
GraphCom-nit nsa (triin)
$2.48 0.99
59.34 d: 2.34
40.53 4: 1,85
63.14 4: 0.58
71,07 4: 0.5
82.4 0.19
GrphCoom-nsa (test)
82.04 +: 1.05
59.03 +: 2.77
40.25 + 1.59
63.16 + 0.32
70,92 + 0.7
82.38 =: 0.26
GmphCooe-mi (trained)
65.87 3.24
49.32 d: 1.35
33.15 +: 1.19
54,39 d: 1.25
66.76 0.96
49.68 d: 0.82
Graph Comv-ma (untrained)
63.30 3.55
32.51 0.50
55.84 0.53
70.73 0.69
0.48
Proof. By Lipschitz continuity of O
8 (E())((A) - T.o (WW.),
Hence,
(Z, & LIE 8 (W, (G(W,A),,
and the claim of the theorem follows from Theorem 3.7.
As explained Section 3.5, the above theorem of stability of MPNNS to graphon-signal sampling also applies to subsampling graph-signals.
I Notations
[n] -1,..-.- (1......).
(x)) or L": Lebesgue p space over the measure space X.
μ: standard Lebesgue measure on [0, 1].
Ps {Pi. ...... Pa): partition (page 3)
G (V, E): simple graph with nodes V and edges
= (ar.) = graph adjacency matrix (page 4).
(u S): the number of edges with one end point at and the other at S, where U.S C (page 3).
ep(u,s); density of of edges between U' and S (page 3).
irregg (P): irregularity (1).
Wh: space of graphons (page 4).
W: graphon (page 4).
We: induced graphon from the graph G (page 4).
|| cut norm (page 4).
dn(W, V): cut metric (page 4).
(W, V): distance (page 4).
Spo.j: the space measure preserving bijections [0, 1] - [0, 1] (page 4).
S) the set of measurable measure preserving bijections between co-null sets of [0, 1] (page 5).
v²(z,)) y) V (d(z), d(y)) (page 4).
Wh: space of graphons modulo zero cut distance (page 4).
C [0, 1]: signal space (2).
43

---

|l cut norm of a signal Definition 3.1.
WL,: graphon-signal space (page 5).
((W,/)ll= graphon-signal cut distance (page 5).
So((, (V.g)): graphon-signal cut distance (4).
WC,: graphon-signal space modulo zero cut distance (page 5).
(W, (G.r) (Wa, fr): induced graphon-signal Definition 3.2.
S the space of step functions of dimension d over the partition PeDeniittin 3.3.
Wo n Sp. the space of step graphons/ stochastic block models (page 6).
2 1] n Sp. the space of step signals (page 6).
[WC,lp,: the space graphon-sisg signall stochastic block models with respect to the partition Px (page
6).
W(A); random weighted graph (page
f(A): random sampled signal (page 7).
G(W. A): random simple graph (page 7).
(2x, y): message function (page 8).
<* s Rd + RR: receiver and transmitter message functions (page 8).
f (0, 1]2 RR: message kernel (page 8).
Agg W. Q): aggregation of message Q with respect graphon W (page 8).
(0); signal at layer (page 8).
(++1; update function (page 8).
O.(W, f): the output of the MPNN applied (W E W., at layer (T) (page 8).
LiW(, ): ): the space of Lipschitz wwwpshiit..oniinnnaiie continuous mappings Y WL, RCC with Lipschitz constant La (page 9).
44


Reviews:
[{"review_id": "qZl5p1X84G", "reviewer": "Reviewer_3Bfr", "summary": "This paper extends the graphon theory to the graphon-signal theory. Especially, the authors introduce a distance metric \"cut distance\" on graphon-signal and analyze their regularity, and compactness. Furthermore, the authors use Lipschitez properties of MPNN to bound the model generalization.", "questions": "The questions are demonstrated in the weakness part.", "limitations": "The authors have adequately addressed the limitation of the public.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I am not an expert in this field. But I carefully check the sketch of the points of the theoretical analysis is systemic and comprehensive.", "weaknesses": "I am not an expert in this field, but I think there are at least some points to improve the paper.\n\n1. There are a lot of notations in this paper, it is better to summarize all the notations of this work and make a table in the appendix. It will help the review's comments\n\n2. Some references are still missing for the training since adaptation. For example, the generalization gap in non-adversarial attacks should also be briefly discussed such as ( https://www.pnas.org/doi/10.1073/pnas.1907378117)\n\n3. It would be better to have a figure to demonstrate the motivation of the distance metric.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments.\n\n>\n\n***Notations:*** We will add a notation table in the supplementary material of the camera ready version if accepted. \n\n>\n\n***References and discussion:*** We will add a discussion and references on benign overfitting and double descent to the introduction in the camera ready version, if accepted. We will make clear where our theory sits:  our results are in the classical setting of uniform convergence bounds, and we do not try to explain benign interpolation or double descent. We note that uniform bounds (e.g., using VC dimension or Rademacher complexity), while being classical for Euclidean data, are not well understood for graph data. Hence, one goal of this paper is to derive such bounds for GNNs.\n\nWe will extend the discussion in the introduction and generalization sections regarding the motivation of our work, and stress the following point better. All other GNN generalization papers have strong assumptions on the data distribution, and often on the model, which are often simplistic and not guaranteed in real-life. In this work we give generalization bounds that do not depend on any assumption on the data distribution, and only weak assumptions on the model, assuming that the message functions are Lipschitz. This work derives the generalization bounds in case all assumptions from other papers fail. It is in a sense the ``bound on all possible bounds.’’ We moreover conjecture that our bound is optimal (when no assumptions on the data are made), as explained in the common response. In this sense, our work complements past works, by giving guarantees in case their assumptions are not met in practice.\n\n>\n\n***Figures:*** Thank you for this important comment. We composed two new figures (see the rebuttal PDF), that will be added to the camera ready version if accepted. Figure 1 will be in the introduction. The figure illustrates two graph-signals that are close in cut-distance. Figure 2 will be put in the graphon-signal regularity lemma section (Section 3.3). The figure illustrates the measure-preserving bijection and step graphon-signal that approximates a graph-signal, guaranteed by the graphon-signal regularity lemma. "}, {"review_id": "Jgqim6ZKnU", "reviewer": "Reviewer_9vxX", "summary": "This work proposes a new metric to measure the distance between graphon signals (graphon parameters and signals defined over graphon jointly). The metric generalizes the previous metric for graphon only. The work also uses the metric to characterize the approximation error of graphon signals by performing equipartition of the space, and by sampling. The work also uses the metric to characterize the generalization bound of GNNs and stability of GNNs when they are employed to encode graphon signals. ", "questions": "Please check the above weaknesses. \n\nI think the biggest issue behind this work is that discussion and comparison between the new results and previous ones are missing, which loses the chance to collect insights from the paper. Notations should be also improved.", "limitations": "Pure theoretical work, not see negative societal impact ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The work reads solid and investigates a very fundamental problem. The defined metric may be useful for the future study. \n2. The study of the proposed metric is comprehensive, including approximation, generalization and stability. ", "weaknesses": "The extension of the metric from graphon to graphon signal seems incremental to me. The following results on equipartition and sampling approximation, GNN generalization, and stability results seem to be also just extensions. A better explanation of what the technical difficulty behind such an extension should be discussed. Even if there is no substantial technical challenge, what new insights can be collected based on the new extension should be provided and compared with previous observations in a better way. Currently, it is hard for readers to collect insights into these results. What I learned is that the approximation error converges to 0 very slowly ($O(\\sqrt{log k})$). But why do we have such a slow rate? Is it the best we can have? For the stability results, the issue is similar: does the result mean GNNs if used here are super unstable? In previous literature, the rate is about $O(1/k)$ or $O(1/\\sqrt{k})$. Also, the implication behind the generalization results is almost not discussed at all. \n\nSome minors: \n\n1. the notations in this work are complicated and are used in a kind of arbitrary way. It is hard for readers to track the used notations. I suggest to provide a table list of the key notations and think about how to unify them. \n2. Why the output of $\\Phi$ is in $R^p$ in Sec 4.1 if the output of $\\xi^k$ is $R^p$.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive and in-depth comments.\n\n>\n\n***New insights from the theory and comparison to past results:*** Thank you for this comment. We see your point that the motivation is not explained clearly enough in the first submission. There is actually a clear reason to consider our proposed theory, that we will clarify in the camera ready paper if accepted. **All past works consider special assumptions on the data distribution, and often on the model. Our work provides upper bounds under no assumptions on the data distribution, and only mild Lipschitz continuity assumptions on the message passing functions. Hence, our theory shows how the bounds behave when all special assumptions from other papers are not met. We show that when all assumptions fail, MPNNs still have generalization and sampling guarantees, albeit much slower ones.** We see this as an important contribution, since the special assumptions from other papers, that are often simplistic, could fail to be satisfied in real data. We also note that our bounds do not directly depend on the number of parameters of the mode, in contrast to past works.\n\nThis was written very shortly in the abstract and introduction in the submitted version. We will add paragraphs that explain this in detail in the introduction and in the generalization and sampling sections. **We will also add a section to the supplementary material that discusses what special assumptions each past work considers.** To summarize this comparison, see Table 1 in the rebuttal PDF. \n\nRegarding sampling, we already compared our results to past works in Section 4.4, in the paragraph of line 320. Past works assume that the sampled graphon is Lipschitz continuous over some metric space, which is an unnatural assumption in graphon theory – a theory of measurable functions, not continuous functions. Working with Lipschitz continuous graphon-signals with bounded Lipschitz constant does not allow approximating any graph-signal. Observe that when you talk about the Lipschitz continuity of the graphon, you actually treat [0,1] as the 1D metric line, and not the general atomless standard probability space. Hence, any theory that imposes Lipschitz continuity on the graphon actually models only 1D geometric graphs, which is very restrictive. On the other hand, when we only assume that the graphon is measurable, [0,1] is only treated as a standard (atomless) probability space, which is very general, and equivalent for example to [0,1]^d for any d, and to any Polish space. Basically, the reason graphon theory allows restricting the domain to [0,1] is because [0,1] as a measure space is very generic. **We will extend this comparison in the camera ready version if accepted.**\n\n>\n\n***Optimality of results:*** Thank you for this important comment. We will clarify in the camera ready version the reason and meaning of the slow convergence rates. **We conjecture that our generalization bound is essentially tight.** Indeed, [1, Theorem 1.4] shows that the bound in the weak regularity lemma is tight up to the choice of the constant $c$ in $2^{c/\\epsilon^2}$. Since in our graphon-signal theory the bound is also of the form $2^{c/\\epsilon^2}$, and a graphon can be seen as special graphon-signal, where the signal is constant 1, our bound in the regularity lemma is also tight up to the constant $c$. Indeed, the graphon which does not allow a regularity partition with less than $2^{c’/\\epsilon^2}$ intervals in the graphon regularity lemma can also give a lower bound for the graphon-signal regularity lemma. \n\nMoreover, we also conjecture that the error bound in Theorem H.3 is optimal up to dividing $\\epsilon$ by $\\log(1/\\epsilon)$. Let us explain the motivation. Kolmogorov and Tihomirov gave an exponential upper and lower bounds on the covering number of the L-Lipschitz continuous space over a metric space with finite covering [2, Theorem 17]. The lower bound only differs by a log factor from the upper bound. The construction in [2] is similar in nature to our construction of Theorem H.3. We hence believe that we can also prove in future work that Theorem H.3 is essentially optimal, and as a result so is our generalization bound. **We will write this conjecture in the camera ready version, add the required references, and leave the proof to future work.**\n\nTo conclude, our bounds apply to any data distribution and any model, and hence are very pessimistic, but still conjectured to be essentially optimal (when no assumptions on the data are made). Real-life data is distributed in special unknown ways that make MPNNs perform better than our pessimistic bound. While other works try to model special distributions and restrict to special MPNNs to obtain “tighter” bounds, our goal was to give the “bound of all bounds,” that is guaranteed always, and conjectured to be essentially tight when no assumption on the data and only mild assumption on the model are made. Our work hence complements past works, rather than compete with them.\n\n>\n\n***Triviality of results:*** To use graphon analysis for GNNs you must extend it to graphon-signal analysis, as the input to GNNs are graph-signal. Even if this extension is trivial (which is a matter of opinion), the extension was not done before. Since the results are useful and lead to new insights, and were not done before, they are worthy of publication in our opinion, even if easy to prove. Moreover, we do not see the Lipschitz continuity of MPNNs as a trivial result.  \n\n>\n\n***Notations:*** We will provide a notation table in supplementary material in the camera ready paper, and simplify notations when possible.\n\n>\n\n***Multiplication in Sec 4.1:*** The multiplication is elementwise, not a dot product. We will clarify this in the camera ready version.\n\n>\n\n[1] *D. Conlon, J. Fox. Bounds for graph regularity and removal lemmas. 2012.*\n\n[2] *A.N. Kolmogorov, V.M. Tihomirov, ε-Entropy and ε-capacity of sets in functional space. 1961.*\n"}, {"review_id": "1YG9LUXUZn", "reviewer": "Reviewer_Leoh", "summary": "This work focuses on analyzing message passing neural networks (MPNNs) by extending graphon analysis. It casts MPNNs as a function taking a graph-signal input (graph + signal on the graph) and proposing a similarity measure over graph signals, viewed as a dense subset of a compact metric space. This allows the authors to compare graph signals of different sizes and topological structures. More specifically, the authors formalize \"regularity statements\" for MPNNs by extending Szemerédi's weak regularity lemma to graphon signals. Furthermore, the authors demonstrate the power of their framework by using it to prove generalization bounds for MPNNs and establish stability of MPNNs under subsampling.\n\nThe work is a theoretical work that establishes a new framework for analyzing MPNNs and does not include any empirical results.", "questions": "The exponential growth of the covering number seems to be a limitation for practicality of the Generalization Theorem in Thm 4.2. Are there important settings for which the covering number is much smaller? Does the author believe there is any hope for improving the dependence on covering number (e.g., improving ξ(ε)) in Them 4.2, or is the bound somewhat tight in the general setting?", "limitations": "Limitations of this work pertaining to slow asymptotics are referred to in the Discussion section.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work is original and introduces a new framework for analyzing MPNNs via graphon signals. The approach is original and differs from prior graphon-based MPNN works in that it does not assume a generative model of the data.\n\nThe paper is generally well-written and clear.\n\n", "weaknesses": "It is unclear what the practical implications of this result or analysis are. The paper could be strengthened by some experiments that show, for instance, that theoretically established generalization guarantees transfer over to empirical performance.\n\nThe exponential dependence in covering number, etc. render some of the theorems a bit impractical (though still of theoretical value).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their important and insightful comments.\n\n>\n\n***Slow asymptotics and implications:*** The motivation may have been not clear enough in the first submission. We will extend the discussion in the introduction and generalization sections and stress the following point. All other GNN generalization papers have strong assumptions on the data distribution, and often on the model, which are often simplistic and not guaranteed in real-life. In this work we give generalization bounds that do not depend on any assumption on the data distribution, and only weak assumptions on the model, assuming that the message functions are Lipschitz. This work derives the generalization bounds in case all assumptions from other papers fail. It is in a sense the ``bound on all possible bounds.’’ We moreover conjecture that our bound is optimal, as explained next. In this sense, our work complements past works, by giving guarantees in case their assumptions are not met in practice.\n\n>\n\n***Tightness of the bound:*** **We believe that our generalization bound is essentially tight.** Indeed, [1, Theorem 1.4] shows that the bound in the weak regularity lemma is tight up to the choice of the constant $c$ in $2^{c/\\epsilon^2}$. Since in our graphon-signal theory, the bound is also of the form $2^{c/\\epsilon^2}$, and a graphon can be seen as special graphon-signal, where the signal is constant 1, our bound in the regularity lemma is also tight up to the constant $c$. Indeed, the graphon which does not allow a regularity partition with less than $2^{c’/\\epsilon^2}$ intervals in the graphon regularity lemma can also give a lower bound for the graphon-signal regularity lemma. \n\nMoreover, we also conjecture that the error bound in Theorem H.3 is optimal up to dividing $\\epsilon$ by $\\log(1/\\epsilon)$. Let us explain the motivation. Kolmogorov and Tihomirov gave an exponential upper and lower bounds on the covering number of the L-Lipschitz continuous space over a metric space with finite covering [2, Theorem 17]. The lower bound only differs by a log factor from the upper bound. The construction in [2] is similar in nature to our construction of Theorem H.3. We hence believe that we can also prove in future work that Theorem H.3 is essentially optimal, and as a result so is our generalization bound. **We will write this conjecture in the camera ready version, add the required references, and leave the proof to future work.**\n\n>\n\n***Experiments:*** We ran new experiments that we will include in the camera ready version if accepted. The only non trivial assumption in our model is that it uses normalized sum aggregation. To verify that such a model generalizes well in practice, we ran experiments on MPNNs with normalized sum aggregation. The table shows that the model generalizes well. See the rebuttal PDF for the result. In our theory, there are no assumptions on the other aspects of the learning setting (number of parameters, data distribution, message function architecture). This is the point in the paper - to find a bound (conjectured to be essentially tight) on generalization under no assumptions. Hence, there are no other aspects to directly check in experiments, and standard results from other papers, that did assume something about the data and the model, also apply in our case.\n\n>\n\n***Settings in which the covering number is smaller:*** As explained above, other papers consider special assumptions on the data that lead to lower generalization bounds. The goal of our paper is to show what the bounds look like under no assumptions. We do plan to study in future work special data distributions defined via their covering number in the graphon-signal space, or their so-called metric entropy. We see the current paper as laying the groundwork on which future works can formulate criteria on data distributions that allow small generalization bounds.\n\n>\n\n[1] *D. Conlon, J. Fox. Bounds for graph regularity and removal lemmas. 2012.*\n\n[2] *A.N. Kolmogorov, V.M. Tihomirov, ε-Entropy and ε-capacity of sets in functional space. 1961.*\n\n"}, {"review_id": "rUzoUYxQf1", "reviewer": "Reviewer_KJfc", "summary": "The authors introduce an extension of the graphon analysis to a graphon-signal analysis, in order to measure generalization bounds of and stability of MPNNs. Specifically, they propose a variant of cut distance as a new graph-signal similarity measure that transforms the space of graph-signals to a dense subset of a compact metric space. \n\nGiven the definition of the cut distance, the authors are able to show Lipschitz continuity of MPNNs, that can yield results on generalization and stability properties of MPNNs.\n\nThe authors do not show any empirical result on the connection between the graphon-signal analysis and MPNNs. ", "questions": "1. Can the authors provide any empirical result that can show stability or generalization capabilities of MPNNs with respect to the graph-signals?\n\n2. Can the authors provide a further comparison of their analysis with the analysis in [1]? \n\nTypos:\nInconsistencies in title case format\n- '2.3 graphon analysis'\n- '3.3 graphon-signal regularity lemma'\n\n[1] Luana Ruiz, Zhiyang Wang and Alejandro Ribeiro. GRAPHON AND GRAPH NEURAL NETWORK STABILITY. 2021. ", "limitations": "- The authors discuss the limitations of their theory with respect to the slow asymptotics and the subsampling theorems. \n- The authors do not discuss any potential negative impact (although I do not see any negative impact coming out of this theory).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The methodology of analysing MPNNs through the extension of graphon theory is quite interesting and fairly novel. \n2. The proposed approach can derive generalization and stability arguments for the MPNNs.\n3. In contrast to related work, the authors provide a rigorous analysis that is justified for modeling the graph space, even when the Lipschitz continuity of graphons is required.", "weaknesses": "1. There is no empirical evidence that can highlight the connection of the graphon-signal analysis with the MPNNs.\n\n2. There is no discussion about a related work [1], that also related stability arguments of MPNNs with respect to the graphon analysis. \n\n\n[1] Luana Ruiz, Zhiyang Wang and Alejandro Ribeiro. GRAPHON AND GRAPH NEURAL NETWORK STABILITY. 2021. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive and supportive comments.\n\n>\n\n***Experiments:*** We ran new experiments that we will include in the camera ready version if accepted. The only non trivial assumption in our model is that it uses normalized sum aggregation. To verify that such a model generalizes well in practice, we ran experiments on MPNN with normalized sum aggregation. The table shows that the model generalizes well. See the rebuttal PDF for the result. In our theory, there are no assumptions on the other aspects of the learning setting (number of parameters, data distribution, message function architecture). This is the point in the paper - to find a bound (conjectured to be essentially tight – see common response) on generalization under no assumptions. Hence, there are no other aspects to check, and standard results from other papers, that did assume something on the data and the model, also apply in our case.\n\n>\n\n***Comparison to additional sampling results and [1]:*** We will extend the survey of other works that considered stability/transferability/sampling, including the suggested ref [1]. We note that, as explained in the text, such works give smaller lower bounds than our work by considering additional assumptions on the structure of the sampled graphon. Namely there are assumptions on the gap between eigenvalues of the graphon as a kernel operator, and assumptions that the graphon is Lipschitz continuous over a metric space. In our work the graphon is only assumed to be measurable, which leads to more general results with slower asymptotics. We note that mathematical modeling assumptions like Lipschitz continuity of the graphon need to be verified in practice by running experiments. On the other hand, we have no such assumptions, and any graph-signal is a special case of a measurable graphon-signal.\n\nIn general, we may have not explained well enough the motivation of our construction. We will fix this in the camera ready version if accepted. All other GNN generalization (and sampling) papers have strong assumptions on the data distribution, (on the sampled graphons), and often on the model, which are often difficult to guarantee in real-life. In this work, we give bounds that do not depend on any assumption on the data distribution, (on the sampled graphon), and only mild assumptions on the model, assuming that the message functions are Lipschitz. Our work derives the bounds in case all assumptions of other papers fail. It is in a sense the ``bound on all other bounds.’’ We moreover conjecture that our bounds are optimal, as explained in the common response. **In this sense, our work complements rather than competes with past works: our work gives an “insurance card” to special constructions, by giving guarantees for convergence even in case the special assumptions are not met in practice.** \n\n>\n\n***Typos:*** Thank you for spotting the typos. We will correct them.\n"}]

Author rebuttal:
We thank the reviewers for their constructive and in-depth comments. Following the comments, we will edit the paper to clarify the motivation for our theory as explained below, and will add the experiments and figures described below and in the additional rebuttal PDF file.

>

***New insights from the theory:***  The motivation may have been not clear enough in the first submission. There is actually a clear reason to consider our proposed theory, that we will add to the camera ready paper if accepted. **All past works about generalization and sampling in GNNs consider special assumptions on the data distribution, and often on the model. Our work provides upper bounds under no assumptions on the data distribution, and only mild Lipschitz continuity assumptions on the message passing functions. Hence, our theory shows how the bounds behave when all special assumptions from other papers are not met. We show that when all assumptions fail, MPNNs still have generalization and sampling guarantees, albeit much slower ones.** We see this as an important contribution, since the special assumptions from other papers, that are often simplistic, may not be satisfied in real data. 

We will add paragraphs that explain this in detail in the introduction and in the generalization and sampling sections. We will also add a section to the supplementary material that discusses what special assumptions each past work considers. To summarize this comparison, see Table 1 to the rebuttal PDF. 

>

***Tightness of bounds:*** We will clarify in the camera ready version the reason and meaning of the slow convergence rates. **We conjecture that our generalization bound is essentially tight.** Indeed, [1, Theorem 1.4] shows that the bound in the standard weak regularity lemma is tight up to the choice of the constant $c$ in $2^{c/\epsilon^2}$. Since in our graphon-signal theory the bound is also of the form $2^{c/\epsilon^2}$, and a graphon can be seen as special graphon-signal, where the signal is constant 1, our bound in the regularity lemma is also tight up to the constant $c$. Indeed, the graphon which does not allow a regularity partition with less than $2^{c’/\epsilon^2}$ intervals in the standard regularity lemma can also give a lower bound for the graphon-signal regularity lemma. 

Moreover, we also conjecture that the error bound in Theorem H.3 is optimal up to dividing $\epsilon$ by $\log(1/\epsilon)$. Let us explain the motivation. Kolmogorov and Tihomirov gave an exponential upper and lower bounds on the covering number of the L-Lipschitz continuous space over a metric space with finite covering [2, Theorem 17]. The lower bound only differs by a log factor from the upper bound. The construction in [2] is similar in nature to our construction of Theorem H.3. We hence believe that we can also prove in future work that Theorem H.3 is essentially optimal, and as a result so is our generalization bound. **We will write this conjecture in the camera ready version, add the required references and background motivation, and leave the proof to future work.**

>

***To conclude,*** our bounds apply to any data distribution and any model, and hence are very pessimistic, but still conjectured to be essentially optimal (when no assumptions on the data are made). Real-life data is distributed in special unknown ways that make MPNNs perform better than our pessimistic bound. While other works try to model special distributions and restrict to special MPNNs to obtain “tighter” bounds, our goal was to give the “bound of all bounds,” that is guaranteed always, and conjectured to be essentially tight when no assumption on the data and only mild assumption on the model are made. **In this sense, our work complements past works: it gives an “insurance card” to special constructions, by giving guarantees for convergence even in case the special assumptions are not met in practice.**

>

***Experiments:*** We ran new experiments that we will include in the camera ready version if accepted. The only non trivial assumption in our model is that it uses normalized sum aggregation. To verify that such a model generalizes well in practice, we ran experiments on MPNNs with normalized sum aggregation. The table shows that the model generalizes well. See the rebuttal PDF for the result. In our theory, there are no assumptions on the other aspects of the learning setting (number of parameters, data distribution, MPNN architecture). This is the point in the paper - to find a bound (conjectured to be essentially tight) on generalization under no assumptions. Hence, there are no other aspects to directly check by experiments, and standard results from other papers, that did assume something on the data and the model, also apply in our case.

>

***Notations:*** We will provide a notation table in the supplementary material in the camera ready paper, and simplify notations where possible.

>


***Figures:*** We will add new figures that illustrate the cut distance and the regularity lemma. See rebuttal PDF.

>

[1] *D. Conlon, J. Fox. Bounds for graph regularity and removal lemmas. 2012.*

[2] *A.N. Kolmogorov, V.M. Tihomirov, ε-Entropy and ε-capacity of sets in functional space. 1961.*


Meta-review: This paper is concerned with a theoretical analysis of GNNs through the lens of graphons. It was overall well received by the reviewers, and the rebuttal allowed to fix minor concerns.
Please incorporate the remaining reviewers' feedback for the camera-ready version.
Decision: Accept (poster)