Transferability of Graph Neural Networks using Graphon and Sampling
  Theories
Graph neural networks (GNNs) have become powerful tools for processing
graph-based information in various domains. A desirable property of GNNs is
transferability, where a trained network can swap in information from a
different graph without retraining and retain its accuracy. A recent method of
capturing transferability of GNNs is through the use of graphons, which are
symmetric, measurable functions representing the limit of large dense graphs.
In this work, we contribute to the application of graphons to GNNs by
presenting an explicit two-layer graphon neural network (WNN) architecture. We
prove its ability to approximate bandlimited graphon signals within a specified
error tolerance using a minimal number of network weights. We then leverage
this result, to establish the transferability of an explicit two-layer GNN over
all sufficiently large graphs in a convergent sequence. Our work addresses
transferability between both deterministic weighted graphs and simple random
graphs and overcomes issues related to the curse of dimensionality that arise
in other GNN results. The proposed WNN and GNN architectures offer practical
solutions for handling graph data of varying sizes while maintaining
performance guarantees without extensive retraining.
A. Martina Neuman, Jason J. Bramburger
# Transferability of Graph Neural Networks using Graphon and Sampling Theories

###### Abstract

Graph neural networks (GNNs) have become powerful tools for processing graph-based information in various domains. A desirable property of GNNs is transferability, where a trained network can swap in information from a different graph without retraining and retain its accuracy. A recent method of capturing transferability of GNNs is through the use of graphons, which are symmetric, measurable functions representing the limit of large dense graphs. In this work, we contribute to the application of graphons to GNNs by presenting an explicit two-layer graphon neural network (WNN) architecture. We prove its ability to approximate bandlimited signals within a specified error tolerance using a minimal number of network weights. We then leverage this result, to establish the transferability of an explicit two-layer GNN over all sufficiently large graphs in a sequence converging to a graphon. Our work addresses transferability between both deterministic weighted graphs and simple random graphs and overcomes issues related to the curse of dimensionality that arise in other GNN results. The proposed WNN and GNN architectures offer practical solutions for handling graph data of varying sizes while maintaining performance guarantees without extensive retraining.

**Key words:** graphon, regularized sampling, graph neural network, transferability, random graph, curse of dimensionality

###### Contents

* 1 Introduction
* 2 Preliminaries
	* 2.1 Graph Neural Networks
	* 2.2 Graphons
	* 2.3 Graphon neural networks
	* 2.4 Bandlimited graphon signals and sampling
	* 2.5 WNN and GNN architectures enabled by the sampling theory
* 3
Main Results
	* 3.1 A uniform sampling theorem
	* 3.2 Generalization using WNNs
	* 3.3 Generalization on graphs and GNN-transferability
	* 3.4 Ramifications of the results
* 4 Proof of Theorem 3.1
	* 4.1 A regularized sampling result
	* 4.2 Sampling with \(\mathcal{G}_{r,\sigma}\)
* 5 Proof of Theorem 3.2
	* 5.1 Proof of Lemma 5.1
	* 5.2 Proof of Lemma 5.2
* 6 Proof of Theorem 3.3
	* 6.1 Proof of Lemma 6.1
* 7 Proof of Theorem 3.4
* 8 Discussion
* A Proofs of Proposition 2.1 and Lemma 2.1

## 1 Introduction

Falling under the category of geometric deep learning models [10], graph neural networks (GNNs) have become a powerful tool for processing information that can be represented on graphs [40, 53, 60]. GNNs are a class of neural networks that incorporate an underlying graph topology to facilitate information exchange among neighboring vertices; they have been applied to a variety of different domains including natural language processing [59], chemistry [21, 24, 30], citation networks [5, 15, 26], and recommender systems [22, 23, 28, 46, 47, 48, 60]. GNNs have been shown to outperform the predictive power of traditional neural networks [2, 38] and can generalize bandlimited functions using far fewer network weights than the best-known results for deep neural networks [43]. For a more complete introduction to the theory and application of GNNs see the review [61].

When it comes to GNNs, one of the most desirable properties is that of _transferability_. In this context transferability means that a GNN can be transported between different graphs without re-training, with performance guarantees. A simple example of transferability would be providing robustness guarantees on a GNN when there are alterations in the underlying edge or weight structure, measured by a suitable metric. Beyond just manipulating the edge structure of a graph, one can similarly ask for transferability between graphs of different sizes. An important example of when one would desire such transferability comes from recommender systems. In this case the vertices of the network represent
users/subscribers, while edge weights could represent a similarity measure between them. The goal is to leverage the knowledge of one user's taste or interests to curate recommendations for users deemed similar. In this situation one should expect the number of users to vary frequently as new ones sign up for the platform and others end their subscriptions. Certainly, one does not want to re-train a recommender neural network each time a user is added or lost, especially since all of the structure in the graph remains the same between users who continue on the platform. Thus, one seeks to identify a single GNN architecture that exhibits transferability between these similar user networks with varying numbers of vertices.

To achieve transferability of GNNs over similar networks of different sizes, [48] introduced the concept of a _graphon neural network_ (WNN). The key ingredient is a graphon - a symmetric, measurable function \(W:[0,1]^{2}\rightarrow[0,1]\) that can be used to represent the limit of large dense graphs as the number of vertices tends to infinity [6, 25, 29, 36]. Members of a sequence of graphs converging to a graphon \(W\) can be seen as sharing structural characteristics, despite not being of the same size, much along the line of our motivating example of recommender systems. The ability for graphons to capture similarity of graphs of different sizes was employed in [48] to prove transferability of GNNs for sufficiently large graphs coming from the same sequence that converges to a graphon.

Graphons continue to be employed to capture transferability and other desirable properties of GNNs. The work [39] uses graphons to prove transferability of spectral graph neural networks, while GNN stability with respect to graphon and graph perturbations has also been investigated [31, 52]. Transferability results are examined experimentally in [51] where GNNs are trained on moderately sized graphs and then transferred to large graphs to evaluate theoretical performance guarantees. Graphons have also been estimated from data to train GNNs [27], and used to perform pooling and sampling in GNNs, with the latter application demonstrating that graphon pooling GNNs are less prone to overfitting [45]. While the concept of a WNN primarily exists in theory to describe transferability, [13] proposes a technique for learning a WNN by training GNNs on growing networks sampled from the graphon. Finally, there is also an emerging literature of signal processing using graphons [42, 49, 50, 52] that is particularly useful in describing structurally-similar graph signals over varying network sizes that are used to train GNNs.

In this work we contribute to the emerging application of graphons to data science by providing an explicit two layer WNN architecture and proving that it can approximate a bandlimited signal within an \(\varepsilon>0\) error tolerance using \(\mathcal{O}(\varepsilon^{-10/9})\) network weights. This result is then leveraged to prove transferability of an explicit two layer GNN among all sufficiently large graphs in a sequence converging to a graphon. In particular, transferability is accounted for between both simple deterministic weighted graphs and simple random graphs that belong to the same graphon family, of which the latter is often overlooked in the WNN literature. Importantly, graphons allow us to circumvent any issues related to the curse of dimensionality, and in particular, keep the number of layers bounded independently of \(\varepsilon\). This is because graphons embed data into the one-dimensional interval \([0,1]\). The reader should compare with similar results on approximating bandlimited functions on
high-dimensional domains [14, 41], where one requires the numbers of weights and layers to become unbounded as \(\varepsilon\to 0^{+}\).

Our restriction to bandlimited functions enables a sampling result that motivates the WNN architecture we present herein, and builds upon a growing literature on the ability of neural networks to approximate bandlimited functions [14, 17, 41, 43, 44, 57, 58]. Further, we consider bandlimited functions in the traditional sense that they are a linear combination of only finitely many Fourier modes. This is different from some emerging related literature where bandlimited signals replace the Fourier modes with eigenfunctions of the underlying graphon or manifold [50, 58]. In practice one rarely has access to the graphon and graphon signals beyond finitely-many samples of them and so we view working with Fourier bandlimited functions as potentially more practical. Nonetheless, we note that in the case of graphons that only depend on the distance \(|x-y|\) (so-called ring graphons) the eigenfunctions are exactly the Fourier modes [9], causing the bandlimited definitions to coincide.

We summarize our results in this paper as follows:

1. We prove a sampling theorem that gives an explicit reconstruction of bandlimited functions on \([0,1]\), with a subgeometric convergence rate, and provides a foundation for our WNN and GNN architectures.
2. Informed by our sampling theorem, we provide an explicit shallow WNN architecture comprised of only two layers. We prove a generalization theorem that shows that this architecture can reproduce bandlimited graphon signals with an \(L^{2}\) error \(\varepsilon>0\) using only \(2N=\mathcal{O}(\varepsilon^{-10/9})\) evenly spaced samples from \([0,1]\).
3. Through a discretization of the interval \([0,1]\), the WNN architecture leads to a transferable GNN architecture for which graph adjacency matrices are simply swapped into the filter computational unit. We show performance guarantees on the transferability of these GNNs for all sufficiently large simple deterministic weighted graphs and simple random graphs belonging to the same graphon family.

This paper is organized as follows. We begin in SS2 with a review of all of the important concepts, definitions, and auxiliary results that we will use throughout the remainder of the paper. Precisely, SS2.1 reviews GNNs, SS2.2 introduces graphons and SS2.3 defines WNNs as a generalization of GNNs, bandlimited functions are discussed in SS2.4, and finally SS2.5 introduces our specific WNN and GNN architectures. Our main results are presented in SS3, organized into subsections according to the summarized contributions above, followed by a concluding discussion in SS3.4 on their ramifications. The proof of our sampling result is left to SS4, the proof of WNN generalization is in SS5, and GNN proofs can be found in Sections 6 and 7. We conclude in SS8 with a discussion of our results and some important avenues for future investigation.
Preliminaries

We introduce here the symbols, notations, and conventions that will be used consistently throughout this paper. The symbol \(\mathbb{N}\) will denote the set of natural numbers. We preserve the letters \(j,k,l,n\) to represent integers, while \(\mathfrak{m},L,M,N,d,m\) specifically represent natural numbers, and the latter two indicating dimensions. For \(N\in\mathbb{N}\), we define an integer interval \(B_{N}\) by

\[B_{N}:=\{-N,-N+1,\cdots,0,\cdots,N-2,N-1\}.\]

Given a set \(X\) of objects, we denote its cardinality by the notation \(\hash X\).

We employ a conventional abuse of notation for the symbol \(|\cdot|\). When \(I\) is an interval, then \(|I|\) means the length of \(I\). When \(x\) is an element in a Euclidean space, \(|x|\) denotes its Euclidean norm.

For \(p=1,2\), we will consider the Banach spaces \(L^{p}(X;\mathbb{C}^{d})\) consisting of all functions \(f:X\to\mathbb{C}^{d}\) for which

\[\|f\|_{L^{p}(X;\mathbb{C}^{d})}:=\bigg{(}\int_{X}|f(x)|^{p}\,\mathrm{d}x\bigg{)} ^{1/p}\]

is finite. Here, the integral is interpreted in the Bochner sense. When \(X\) is discrete the integral reduces to a summation over the individual elements of \(X\), i.e.

\[\|f\|_{L^{p}(X;\mathbb{C}^{d})}=\bigg{(}\sum_{x\in X}|f(x)|^{p}\bigg{)}^{1/p}.\]

We preserve the symbols \(\ell^{1}\) and \(\ell^{2}\) for when \(X=\mathbb{Z}\), giving

\[\|f\|_{\ell^{p}(\mathbb{Z};\mathbb{C}^{d})}:=\bigg{(}\sum_{j\in\mathbb{Z}}|f(j )|^{p}\bigg{)}^{1/p},\quad p=1,2.\]

We will futher consider the case of \(p=\infty\), which leads to the \(L^{\infty}\)-norm of a function \(f\):

\[\|f\|_{L^{\infty}(X;\mathbb{C}^{d})}:=\sup_{x\in X}|f(x)|.\]

For convenience, when \(d=1\) we simply write \(L^{p}(X)\) and \(\ell^{p}(\mathbb{Z})\).

We also employ another abuse of notation when referring to the congruence symbol \(\cong\). When \(X\), \(Y\) are two sets, then \(X\cong Y\) means \(X,Y\) are isomorphic as sets. For example, the torus \(\mathbb{T}\cong[0,1)\) or \(\mathbb{T}\cong[-1/2,1/2)\) as sets. When \(X,Y\) are two Lebesgue measure sets, then \(X\cong Y\) means that the set difference \(X\Delta Y\) has Lebesgue measure zero. For example, \([0,1]\cong[0,1)\). Lastly, when \(X,Y\) are both groups, then \(X\cong Y\) signifies that they are isomorphic as groups, however this usage only appears in Appendix A.
### Graph Neural Networks

We represent a graph by the triple \(G=(V,E,w)\). Here \(V\) denotes the set of graph vertices and \(E\subset V\times V\) the set of graph edges. Suppose \(\#V=n\), for some \(n\in\mathbb{N}\). By adopting a predetermined labeling for the vertices, we simply express \(V\) as \(V=\{v_{1},v_{2},\ldots,v_{n}\}\). The edge weight function \(w:V\times V\to[0,1]\) describes the connections among the vertices. That is, \(w(v_{k},v_{l})>0\) if and only if there exists an edge connecting \(v_{k},v_{l}\), i.e. \((v_{k},v_{l})\in E\). In this paper, we restrict ourselves to the case of simple, undirected graphs, meaning that \(w\) meets two conditions: symmetry, \(w(v_{k},v_{l})=w(v_{l},v_{k})\) and absence of self-loops, \(w(v_{k},v_{k})=0\). Associated with the edge weight function is the \(n\times n\) graph adjacency matrix, symbolized by \(\mathbf{A}\), whose \(kl\)-entry satisfies \([\mathbf{A}]_{kl}=w(v_{k},v_{l})\).

A _graph signal_ is a function \(f\in L^{2}(V;\mathbb{C}^{m})\), for some \(m\in\mathbb{N}\), giving each vertex \(v_{k}\in V\), a set of features \(f(v_{k})\). Often in many applications of GNNs, vertices are assigned coordinate vectors that depict their locations in space, say \(v_{k}\) is given as \(X_{k}\in\mathbb{R}^{d}\). In this case, the graph signal \(f\) can be interpreted as a function in \(L^{2}(\mathbb{R}^{d};\mathbb{C}^{m})\). From an analytical standpoint, a GNN \(\Psi_{G}\) on \(G\) operates as a graph signal, which means, in this context, \(\Psi_{G}\in L^{2}(\mathbb{R}^{d};\mathbb{C}^{m})\). The input of the GNN is the collection of all of the feature vectors \(X_{k}\), called the (input) _feature matrix_ and denoted by

\[\mathbf{X}:=\begin{bmatrix}X_{1}&X_{2}&\cdots&X_{n}\end{bmatrix}\in\mathbb{R} ^{d\times n}. \tag{2.1}\]

The output feature of \(\Psi_{G}\) at each vertex is a vector in \(\mathbb{C}^{m}\); the collection of such vectors is the (output) feature matrix

\[\mathbf{Y}:=\begin{bmatrix}\Psi_{G}(X_{1})&\Psi_{G}(X_{2})&\cdots&\Psi_{G}(X_ {n})\end{bmatrix}\in\mathbb{C}^{m\times n}.\]

The input and output dimensions, respectively, \(d,m\), are problem dependent. In terms of structure, the defining characteristic of a GNN as a neural network lies in its architecture. Specifically, GNNs are built by combining multiple iterations of two distinct computational units, given as follows:

* **Multilayer Perceptron (MLP)**: An MLP is a two-step process of first applying an affine transformation and then a nonlinear activation function. For example, for a weight matrix \(\mathbf{W}\in\mathbb{C}^{m\times d}\), a _bias vector_\(\mathbf{b}\in\mathbb{C}^{m}\), and a nonlinear activation function \(\rho\), an MLP unit acts symbolically on \(\mathbf{Z}\in\mathbb{C}^{d\times n}\) as \[\mathbf{Z}\mapsto\rho(\mathbf{WZ}+\mathbf{b}),\] where \(\rho\) is applied componentwise. These units are the fundamental building blocks of feedforward neural networks. Throughout this work we consider ReLU (rectified linear unit) activation functions, \(ReLU(x)=\max\{x,0\}\), for which the resulting GNN will be called a _ReLU GNN_.
* **Filter**: A graph filter unit \(\mathfrak{F}\) is what distinguishes a GNN from a standard feedforward NN architecture. Generally, a graph filtering process is any process that takes in nodal
features (e.g. \(\mathbf{X}\) in (2.1)) _and_ graphical structure \((V,E,w)\) and outputs a new set of nodal features. There are two types of graph filters: spatial-based and spectral-based. The spatial filters explicitly leverage the graph connections to perform a feature refining process, whereas the spectral ones utilize spectral graph theory to design filtering in the spectral domain. Moreover, some well-known spectral filters can be considered spatial filters [38].

With the above, the operation of a GNN can be expanded as:

\[\mathbf{Y}\equiv\rho_{L}(\mathbf{W}^{(L)}\psi_{L-1}\circ\psi_{L-2}\circ\cdots \circ\psi_{1}(\mathbf{X})+\mathbf{b}^{(L)}). \tag{2.2}\]

Here, \(L\in\mathbb{N}\), and each \(\psi_{j}\) in (2.2) is a (intermediate) _network layer_, which is one composition of an MLP and a filter units, e.g.

\[\mathbf{H}_{j} =\psi_{j}(\mathbf{H}_{j-1})=\mathfrak{F}(\rho(\mathbf{W}^{(j)} \mathbf{H}_{j-1}+\mathbf{b}^{(j)})),\quad j=1,\cdots,L-1, \tag{2.3}\] \[\mathbf{H}_{0} \equiv\mathbf{X}.\]

This says that at the \(j\)th layer, the output of the previous layer \(\mathbf{H}_{j-1}\), is fed to an MLP (with weight matrix \(\mathbf{W}^{(j)}\), bias vector \(\mathbf{b}^{(j)}\) and activation \(\rho\)) and then to a graph filter \(\mathfrak{F}\). A common alternative to (2.3) is

\[\mathbf{H}_{j}=\psi_{j}(\mathbf{H}_{j-1})=\rho(\mathfrak{F}(\mathbf{W}^{(j)} \mathbf{H}_{j-1}+\mathbf{b}^{(j)})),\]

where there is a switch between the filter and activation applications. In this work, we will specifically employ the configuration (2.3). Note from (2.2) that \(\mathfrak{F}\) is not performed at the last \(L\)th layer and that the last activation \(\rho_{L}\) is optional - for example, one can take \(\rho_{L}\) to be a softmax function to ensure that the output is bounded. Furthermore, \(\mathfrak{F}\) should be enabled at a minimum of one - but not necessarily all - intermediate layers. The GNN _network parameter_, often denoted by \(\theta\), is the set of all entries of all the weight matrices, all the bias vectors, and the number of layers, i.e.

\[\theta=\{\{\mathbf{W}^{(j)}\}_{kl},\mathbf{b}^{(j)},j=1,\cdots,L\}.\]

Throughout this work we will focus on (linear) spatial-based graph filters. Such filtering exchanges information between vertices of the graph. This is achieved by a _graph filter kernel_ (sometimes referred to as a _graph shift operator_[48]) \(\mathbf{K}\in\mathbb{C}^{n\times n}\) which encodes the topology of the graph \(G\). Namely, if \(\mathbf{Z}\in\mathbb{C}^{d\times n}\), then the filter layer takes the form

\[\mathfrak{F}:\quad\mathbf{X}\mapsto\mathbf{K}\mathbf{Z}^{T}. \tag{2.4}\]

The choice of \(\mathbf{K}\) can be determined by the user and is often problem dependent. As will become apparent in the forthcoming subsections, we explore graph filters of the form

\[\mathbf{K}=\mathbf{G}\circ\mathbf{A}, \tag{2.5}\]

where \(\circ\) is the Hadamard product, and \(\mathbf{A}\) is again the adjacency matrix of \(G\). The matrix \(\mathbf{G}\in\mathbb{C}^{n\times n}\) in (2.5) is used to localize information spread by introducing a near-sparsity pattern to \(\mathbf{K}\). This sparsification effect is particularly helpful when \(G\) is a dense graph, since then \(\mathbf{A}\) is a dense matrix, and so information \(\mathbf{Z}\) in (2.4) would be spread globally over \(G\) simply through matrix multiplication by \(\mathbf{K}\).
### Graphons

A _graphon_ is a symmetric, Lebesgue-measurable function \(W:[0,1]^{2}\to[0,1]\). The terminology graphon is a combining graph and function and is a continuum generalization of a graph adjacency matrix. This interpretation comes from envisioning \([0,1]\) as a graph of an uncountable number of vertices, where the values \(W(x,y)\in[0,1]\) represents the weight of an edge between vertices \(x,y\in[0,1]\) - as is common with weighted graphs, one interprets \(W(x,y)=0\) as no edge being present.

Graphons as limit objects.Graphons arise as limits of sequences of graphs on increasing numbers of vertices. To give a meaningful interpretation of graph convergence, we introduce the concept of "homomorphism density" from a graph \(G\) into another graph \(H\) as follows:

\[t(G,H):=\frac{\#\mathrm{Hom}(G,H)}{(\#V_{H})^{\#V_{G}}},\]

where \(V_{H}\), \(V_{G}\) denote the number of vertices in graphs \(G\), \(H\), respectively, and \(\#\mathrm{Hom}(G,H)\) is the number of adjacency preserving maps (_graph homomorphisms_) from \(G\) to \(H\). Thus, the ratio that defines \(t(G,H)\) can be interpreted as the probability that a map from the vertices in \(G\) to those in \(H\) will be a homomorphism, with \((\#V_{H})^{\#V_{G}}\) being the total number of all possible maps. A sequence of graphs \(\{G_{n}\}_{n=1}^{\infty}\) is said to converge if for all finite simple graphs \(F\) the limit of the real-valued sequences \(\{t(F,G_{n})\}_{n=1}^{\infty}\) exist. On the other hand, the homomorphism density of a graph \(F\) into a graphon \(W\) can be defined in an analogous manner [35, Chapter 7.2], resulting in a ratio denoted as \(t(F,W)\). Then, as is shown in [35, Chapter 11], for every convergent sequence of graphs \(\{G_{n}\}_{n=1}^{\infty}\) there exists a graphon \(W\) so that

\[\lim_{n\to\infty}t(F,G_{n})=t(F,W), \tag{2.6}\]

for every finite simple graph \(F\). We observe that (2.6) resembles the conventional notion of pointwise convergence in analysis. Therefore, through (2.6) we may think of the graphs \(\{G_{n}\}_{n=1}^{\infty}\) as belonging to the same graphon family. Next, we present two important sequences of graphs from the same family that are particularly relevant to our discussion.

Generating graphs from graphons.A major application of graphons is to generate graphs on finitely many vertices. Typically this is done by discretizing the unit interval \([0,1]\) into \(n\in\mathbb{N}\) points as

\[x_{k}:=\frac{k-1}{n},\quad k=1,\cdots,n, \tag{2.7}\]

which represent graph vertices. Denote \(\mathcal{X}_{n}:=\{x_{1},\cdots,x_{n}\}\), and the resulting intervals of length \(1/n\) by \(I_{k}:=[(k-1)/n,k/n)\), \(k=1,\cdots,n\).

One can use \(W\) to prescribe a simple _deterministic weighted graph_\(G_{n}^{\mathrm{det}}\) on \(n\) vertices \(v_{1},\cdots,v_{n}\), identified with \(x_{1},\cdots,x_{n}\), respectively. To do so, associate with \(G_{n}^{\mathrm{det}}\) the sym
metric adjacency matrix \(\mathbf{A}_{n}^{\det}\), defined by

\[[\mathbf{A}_{n}^{\det}]_{k,l}:=\begin{cases}W(x_{k},x_{l})&k\neq l\\ 0&k=l\end{cases},\]

for \(k,l=1,\cdots,n\). Hence the edge weight \([\mathbf{A}_{n}^{\det}]_{k,l}\) between \(v_{k}\), \(v_{l}\) is given by the value of \(W\) in the bottom left corner of the square \(I_{k}\times I_{l}=[x_{k},x_{k+1})\times[x_{l},x_{l+1})\). Furthermore, we assert that an edge exists between \(v_{k}\), \(v_{l}\) if and only if \([\mathbf{A}_{n}^{\det}]_{k,l}>0\).

Likewise, one can also use \(W\) to generate a simple _random graph_\(G_{n}^{\mathrm{ran}}\), denoted in analogy with the deterministic graph presentation, on \(n\) vertices \(v_{1},\cdots,v_{n}\). In this case, the associated (random) adjacency matrix \(\mathbf{A}_{n}^{\mathrm{ran}}\) is given by

\[[\mathbf{A}_{n}^{\mathrm{ran}}]_{k,l}:=\begin{cases}\xi_{k,l}&k\neq l\\ 0&k=l\end{cases},\]

for \(k,l=1,\cdots,n\). Here, \(\xi_{k,l}=\xi_{l,k}\) are independent Bernoulli random variables whose probability distribution is given by

\[\mathbb{P}(\xi_{k,l}=1)=1-\mathbb{P}(\xi_{k,l}=0)=W(x_{k},x_{l}),\qquad\forall k >l.\]

Again, all relevant graph information is captured by the adjacency matrix \(\mathbf{A}_{n}^{\mathrm{ran}}\): an edge appears between \(v_{k},v_{l}\) if \(\xi_{k,l}=\xi_{l,k}=1\).

The graphs in both sequences \(\{G_{n}^{\det}\}_{n=1}^{\infty}\) and \(\{G_{n}^{\mathrm{ran}}\}_{n=1}^{\infty}\) belong to the graphon family of \(W\). Indeed, for all finite simple graphs \(F\), one has

\[\lim_{n\to\infty}t(F,G_{n}^{\det})=t(F,W), \tag{2.8}\]

and

\[\lim_{n\to\infty}t(F,G_{n}^{\mathrm{ran}})=t(F,W), \tag{2.9}\]

with probability 1 [35, Chapter 11].

Embedding graphs into the graphon space.Graphs can be lifted into the space of graphons. Let \(G=(V,E,w)\) be a finite simple graph on \(\#V=n\) vertices \(v_{1},\cdots,v_{n}\). We define the step graphon \(W_{n}:[0,1]^{2}\to[0,1]\) by

\[\overline{W}_{n}(x,y):=\sum_{k,l=1}^{n}w(v_{k},v_{l})\chi_{I_{k}\times I_{l}} (x,y). \tag{2.10}\]

That is, the vertices \(v_{k}\) of \(G\) are identified with the points \(x_{k}\in[0,1]\) as in (2.7), while \(\overline{W}_{n}\) is a simple function taking on the \(n^{2}\) edge weight values of \(w\) on each of the squares \(I_{k}\times I_{l}\).
In particular, when \(G\) is a simple deterministic graph generated from a graphon \(W\), the formula (2.10) becomes

\[\overline{W}_{n}(x,y)=\sum_{k,l=1}^{n}w(v_{k},v_{l})\chi_{I_{k}\times I_{l}}(x,y )=\sum_{\begin{subarray}{c}k,l=1\\ k\neq l\end{subarray}}^{n}W(x_{k},x_{l})\chi_{I_{k}\times I_{l}}(x,y).\]

Note that \(\overline{W}_{n}(x_{k},x_{l})=w(v_{k},v_{l})=W(x_{k},x_{l})\), \(k\neq l\).

As a point of completion, we mention that the space of graphons is typically endowed with the so-called _cut norm_, a metric given by

\[\|W\|_{\square}:=\sup_{S,T}\bigg{|}\int_{S\times T}W(x,y)\mathrm{d}x\mathrm{d} y\bigg{|}. \tag{2.11}\]

Importantly, the convergence (2.8) and (2.9) in the homomorphism density is equivalent to the convergence of the respective step graphons to \(W\) in the cut norm [35, Theorem 11.3].

Graph and graphon signals.Similar to the representation of graph signals, a _graphon signal_ is a vector-valued function assumed to belong to \(L^{2}([0,1];\mathbb{C}^{m})\). An \(m\)-dimensional graph signal \(g\) on a graph \(G\) of \(n\) vertices has a corresponding graphon signal representative, defined as follows. As usual, identify the vertices \(v_{k}\) of \(G\) with \(x_{k}\in\mathcal{X}_{n}\) as in (2.7). In this context, \(g\) can be viewed as a function defined on \(\mathcal{X}_{n}\): \(g(v_{k})=g(x_{k})\). We then embed \(g\) into \(L^{2}([0,1];\mathbb{C}^{m})\) as the step function

\[\overline{g}(x):=\sum_{k=1}^{n}g(x_{k})\chi_{I_{k}}(x)=\sum_{k=1}^{n}g(v_{k}) \chi_{I_{k}}(x),\quad\forall x\in[0,1]. \tag{2.12}\]

### Graphon neural networks

Drawing upon the analogy between graphs and graphons, we can define a WNN as an extension of the GNN framework. Specifically, a WNN can be expressed as a function \(\Psi:[0,1]\to\mathbb{C}^{m}\), and just like a GNN, is constructed through a finite number of iterated compositions involving two distinct computational units:

* **MLP**: An MLP layer for a WNN is again a two-step process. Let \(b\in\mathbb{C}^{m}\) be the bias vector, \(\mathbf{W}\in\mathbb{C}^{m\times d}\) a weight matrix, and \(\rho\) be a nonlinear activation function. Then, for \(g\in L^{2}([0,1];\mathbb{C}^{d})\), an MLP in a WNN takes the form \[g(x)\mapsto\rho(\mathbf{W}g(x)+b),\quad\forall x\in[0,1],\] where \(\rho\) is applied componentwise. We will again consider \(\rho=ReLU\) and refer to such WNN as a _ReLU WNN_.
* **Graphon filter**: A graphon filter is a generalization of a graph filter. Namely, let \(\mathcal{K}:[0,1]^{2}\to\mathbb{C}\) such that \(\mathcal{K}\in L^{\infty}([0,1]^{2})\). Then the graphon filter is an operator \(T_{\mathcal{K}}\) acting on \(g=(g_{1},\cdots,g_{m})\in L^{2}([0,1];\mathbb{C}^{m})\) as \[\begin{split} T_{\mathcal{K}}g(x)&=(T_{\mathcal{K }}g_{1}(x),\cdots,T_{\mathcal{K}}g_{m}(x))\\ &:=\bigg{(}\int_{0}^{1}\mathcal{K}(x,y)g_{1}(y)\,\mathrm{d}y, \cdots,\int_{0}^{1}\mathcal{K}(x,y)g_{m}(y)\,\mathrm{d}y\bigg{)},\quad\forall x \in[0,1].\end{split}\] (2.13)

The choice of \(\mathcal{K}\) can be either user or problem determined. For example, by taking \(\mathcal{K}\) to be a graphon \(W\), we obtain the operator \(T_{W}\) which is well-studied in the literature [29, 35, 49]. For arbitrary \(\mathcal{K}\), the action of a WNN closely mirrors that of a GNN, which if we adopt the configuration (2.3), can be expressed symbolically as follows:

\[\Psi(g_{0})(x)\equiv\rho_{L}(\mathbf{W}^{(L)}\psi_{L-1}\circ\psi_{L-2}\circ \cdots\circ\psi_{1}(g_{0})(x)+b^{(L)}),\quad\forall x\in[0,1].\]

Here, \(L\in\mathbb{N}\), with the input graphon signal \(g_{0}\in L^{2}([0,1];\mathbb{C}^{d})\), and each intermediate layer \(\psi_{j}\) is presented as

\[g_{j}(x)=\psi_{j}(g_{j-1})(x)=T_{\mathcal{K}}(\rho(\mathbf{W}^{(j)}g_{j-1}(x) +b^{(j)})),\quad j=1,\cdots,L-1.\]

The last activation \(\rho_{L}\) is optional, and filtering is performed at a minimum of one - but not necessarily all - intermediate layer.

### Bandlimited graphon signals and sampling

Let \(f=(f_{1},\cdots,f_{m}):[0,1]\to\mathbb{C}^{m}\) be a graphon signal. We assume \(f\in L^{2}([0,1];\mathbb{C}^{m})\), and therefore \(f\) can be expressed as a Fourier series,

\[f(x)=\sum_{k\in\mathbb{Z}}\hat{f}(k)e^{i2\pi nx},\]

where \(\hat{f}(k)=(\hat{f}_{1}(k),\cdots,\hat{f}_{m}(k))\), and the equal sign equates two members of \(L^{2}([0,1];\mathbb{C}^{m})\). We are interested in profiles \(f\) whose Fourier coefficients

\[\hat{f}(k)=(\hat{f}_{1}(k),\cdots,\hat{f}_{m}(k)):=\int_{0}^{1}f(x)e^{-i2\pi kx }\,\mathrm{d}x \tag{2.14}\]

are zero for all but a finite number of modes \(k\in\mathbb{Z}\). To avoid confusion with another notion of bandlimitedness circulated in the current graphon literature [48], we call such \(f\)_Fourier bandlimited_.

**Definition 2.1**.: Let \(\mathfrak{m}\in\mathbb{N}\) and \(f=(f_{1},\cdots,f_{m})\in L^{2}([0,1];\mathbb{C}^{m})\). Then \(f\) is said to be \(\mathfrak{m}\)-Fourier bandlimited, or \(f\in\mathcal{B}_{\mathfrak{m}}\), if

\[\hat{f}(k)=0,\quad\forall k\not\in B_{\mathfrak{m}}=\{-\mathfrak{m},\cdots,0, \cdots,\mathfrak{m}-1\}.\]

or equivalently,

\[\hat{f}_{j}(k)=0,\quad\forall k\not\in B_{\mathfrak{m}}=\{-\mathfrak{m},\cdots, 0,\cdots,\mathfrak{m}-1\}\]

for every \(j=1,\cdots,m\).
It is well-known that a Fourier bandlimited \(f\) is almost everywhere equal to a continuous function \(f_{c}\) on \([0,1]\) where \(f_{c}(0)=f_{c}(1)\) and

\[f_{c}(x)=\sum_{k=-\mathfrak{m}}^{\mathfrak{m}-1}\hat{f}(k)e^{i2\pi kx}. \tag{2.15}\]

Therefore, we can and will identify \(f\) with this continuous version on \([0,1]\) and on \(\mathbb{T}\cong[0,1)\). A function that is Fourier bandlimited is significant in the sense that all its information is stored in its spatial sampling, as encapsulated by the following proposition.

**Proposition 2.1**.: _Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\) and \(N\geq\mathfrak{m}\). Then,_

\[f(x)=\sum_{j=0}^{2N-1}f(j/2N)s_{N}(x-j/2N),\quad\forall x\in[0,1], \tag{2.16}\]

_where_

\[s_{N}(x):=\frac{1}{2N}\sum_{k=-N}^{N-1}e^{i2\pi kx},\quad\forall x\in[0,1]. \tag{2.17}\]

Proposition 2.1 is a straightforward consequence of the Kluvanek's sampling theorem [33], with the proof left to Appendix A. The function \(s_{N}\) is referred to as a _sampling function_. The reasoning behind the choice of \(s_{N}\), as well as a derivation of (2.16), is fully detailed in Appendix A - see in particular (A.7) and (A.8). One notable observation from the requirement \(N\geq\mathfrak{m}\) is that, when \(N=\mathfrak{m}\), the sampled values (2.20) are said to be sampled at the Nyquist rate [4].

In terms of information, (2.16) represents a remarkable trade-off, in that, to acquire the values of the signal \(f\) at every point on the interval \([0,1]\), one only needs to know its values on a discrete lattice of \([0,1]\). Therefore, the gains achieved substantially outweigh the supply cost. In the following subsection, we will develop a systematic approach to implement the sampling series on the right-hand-side of (2.16) (but more specifically, its regularized variants) into a WNN architecture, which then will be used to generate GNNs capable of generalizing effectively on both deterministic and random graphs.

We conclude this subsection with the following useful lemma that serves as a fundamental connection between sampling theory and Fourier theory on the torus group \(\mathbb{T}\). The second conclusion of the lemma, in particular, provides a practical means for accessing the total graphon signal energy through its spatial samples. This crucial point will be a recurring element in our analysis. The proof is again left to Appendix A.

**Lemma 2.1**.: _Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\) and let \(N\geq\mathfrak{m}\). Then, for \(\hat{f}\) be as in (2.14), we have_

\[\hat{f}(k)=\begin{cases}\frac{1}{2N}\sum_{j=0}^{2N-1}f(j/2N)e^{-i2\pi kj/2N}& k\in B_{\mathfrak{m}}\\ 0&\text{otherwise}\end{cases}, \tag{2.18}\]
_and_

\[\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}^{2}=\|f\|_{L^{2}(\mathbb{T}; \mathbb{C}^{m})}^{2} =\|\hat{f}\|_{\ell^{2}(\mathbb{Z};\mathbb{C}^{m})}^{2}\] \[=\sum_{k=-\mathfrak{m}}^{\mathfrak{m}-1}|\hat{f}(k)|^{2}=\sum_{k=- N}^{N-1}|\hat{f}(k)|^{2}=\sum_{j=0}^{2N-1}|f(j/2N)|^{2}. \tag{2.19}\]

### WNN and GNN architectures enabled by the sampling theory

With the groundwork laid in the previous subsections, we are now in a position to describe the specific network architectures that are used to achieve our main results.

WNN architecture.Let \(f:[0,1]\to\mathbb{C}^{m}\) and suppose that for some \(N\geq 1\) we have access to the vector of values

\[f_{\mathrm{samp}}=\begin{bmatrix}f(0)&f(1/2N)&\cdots&f((2N-1)/2N)\end{bmatrix} \in\mathbb{C}^{m\times 2N}. \tag{2.20}\]

The objective is to design a WNN that can predict the value of \(f\) at some \(x\in[0,1]\) using only the knowledge of \(f_{\mathrm{samp}}\). Our WNN architecture, using ReLU activations and a graphon filter

\[T_{\mathcal{K}}g(x)=\int_{0}^{1}\mathcal{K}(x,y)g(y)\,\mathrm{d}y, \tag{2.21}\]

will be comprised of two hidden layers: a filter layer and an NN layer. Precisely, it is built according to the following steps:

1. **Input:** The input for our WNN is the function \(g_{0}(x)=x\) for all \(x\in[0,1]\).
2. **First hidden layer:** Given the input \(g_{0}\), the output function \(g_{1}\) of the first layer is given by an application of componentwise activation followed by a graphon filtering, \[g_{0}(x)=x\stackrel{{\rho}}{{\mapsto}}\begin{bmatrix}ReLU(x)\\ ReLU(x-\frac{1}{2N})\\ \vdots\\ ReLU(x-\frac{2N-1}{2N})\end{bmatrix}\stackrel{{ T_{\mathcal{K}}}}{{\mapsto}} \begin{bmatrix}T_{\mathcal{K}}ReLU(x)\\ T_{\mathcal{K}}ReLU(x-\frac{1}{2N})\\ \vdots\\ T_{\mathcal{K}}ReLU(x-\frac{2N-1}{2N})\end{bmatrix}=g_{1}(x),\quad\forall x\in[ 0,1].\]
3. **Second hidden layer:** Taking \(g_{1}\) as the input for the second layer, the output \(g_{2}\) is given by \[g_{1}(x)\mapsto f_{\mathrm{samp}}\cdot g_{1}(x)=\sum_{j=0}^{2N-1}f(j/2N)T_{ \mathcal{K}}ReLU(x-j/2N)=g_{2}(x),\quad\forall x\in[0,1]\] where '\(\cdot\)' denotes matrix multiplication between the matrix \(f_{\mathrm{samp}}\) and the vector-valued function \(g_{1}\).
4. **Output:** The output of our WNN is the function \(g_{2}(x)\), for each \(x\in[0,1]\).

The formula for the output WNN,

\[\sum_{j=0}^{2N-1}f(j/2N)T_{\mathcal{K}}ReLU(x-j/2N), \tag{2.22}\]

resembles the sampling form (2.16) on \([0,1]\). As we progress further in this paper, it will become apparent that (2.22) nearly approximates (2.16) (hence in turn, \(f\)). This realization is a compelling testament to the fact that networks can effectively harness sampling principles. Precisely, this will be achieved by taking the graphon kernel \(\mathcal{K}\) of the form

\[\mathcal{K}(x,y)=\mathcal{G}^{*}(x,y)W(x,y), \tag{2.23}\]

for a "Gaussian-like" function \(\mathcal{G}^{*}\) whose specifics will be presented along with our main results. For now, we note the similarity of (2.23) with (2.5). The function \(\mathcal{G}^{*}\) is used to localize the integration in (2.21) to put more preference on "vertices" close to each \(x\in[0,1]\). We therefore assume that \(W\) possesses the following "local" regularity, for (2.23) to be useful in our work.

**Assumption 2.1**.: There exist \(\kappa,\eta\in(0,1)\), \(K>0\), such that for every \(x\in[0,1]\) and almost every pair \((x,y)\) and \((x,z)\) in the diagonal region

\[\mathcal{D}_{\kappa}:=\{(x,y)\in[0,1]^{2}:|x-y|\leq\kappa\} \tag{2.24}\]

we have

\[W(x,y)\geq\eta\quad\text{ and }\quad|W(x,y)-W(x,z)|\leq K|y-z|. \tag{2.25}\]

We emphasize that we do not believe this assumption to be overly restrictive in practice. The second condition in (2.25) is a (one-dimensional) _local Lipschitz_ condition, while the first, the _nonvanishing_ condition \(W(x,y)\geq\eta\), simply guarantees that "vertices" \(x,y\) that are sufficiently close together have some minimal level of influence upon each other in the network. On the other hand, if the contrary holds true, i.e., \(W(x,y)=0\) for almost every \(y\in[-\kappa+x,x+\kappa]\), then any WNN using \(W\) will fail to predict the value \(f(x)\) for all graphon signals \(f\) that are essentially supported in a neighborhood of \(x\). For a simple demonstration of this, note that an application of \(T_{W}\) to such an \(f\) would lead to

\[\bigg{|}\int_{0}^{1}W(x,y)f(y)\,\mathrm{d}y\bigg{|}=\text{ small }\neq|f(x)|,\]

which indicates that the filtering loses information regarding \(f\) at \(x\).
GNN architecture.Running parallel to the presented WNN architecture is our GNN architecture. Let \(G_{n}\) be a graph on \(n\) vertices generated from a graphon \(W\), in the sense presented in SS2.2. We identify a vertex \(v_{k}\) of \(G_{n}\) with \(x_{k}=\frac{k-1}{n}\), where \(k=1,\cdots,n\). Let \(f_{n}\) be an associated graph signal, identified as a function on \(\mathcal{X}_{n}=\{x_{1},\cdots,x_{n}\}\) via \(f_{n}(x_{k})=f_{n}(v_{k})\). Suppose further that \(f_{n}(x_{k})=f(x_{k})\) for all \(k\), for some graphon signal \(f\), and that, for a fixed \(N\geq 1\), we have sampled

\[f_{\mathrm{samp}}=\begin{bmatrix}f(0)&f(1/2N)&\cdots&f((2N-1)/2N)\end{bmatrix} \in\mathbb{C}^{m\times 2N}.\]

We design a GNN that uses only the knowledge of \(f_{\mathrm{samp}}\) to predict the value of the graph signal \(f_{n}\) at some \(x_{k}\). Our GNN architecture uses ReLU activations and a graph filter

\[\mathfrak{F}(g)(x_{k})=\frac{1}{n}\sum_{l\neq k,l=1}^{n}\mathcal{K}(x_{k},x_{ l})g(x_{l}), \tag{2.26}\]

where \(\mathcal{K}\) is the graphon kernel (2.23) above. Notably, (2.26) is a discretization of (2.21) to the "vertices" \(\{x_{k}=(k-1)/n\}_{k=1}^{n}\). The architecture is comprised of two hidden layers: a filter layer and an NN layer, described as follows.

1. **Input:** The input for our GNN is the function \(g_{0}(x_{k})=x_{k}=\frac{k-1}{n}\) for each \(k=1,\ldots,n\).
2. **First hidden layer:** Given the input \(g_{0}\), the output function \(g_{1}\) of the first layer is given by an application of component-wise activation followed by a graph filtering: \[g_{0}(x_{k})=x_{k}\stackrel{{\rho}}{{\mapsto}}\begin{bmatrix}ReLU (x_{k})\\ ReLU(x_{k}-\frac{1}{2N})\\ \vdots\\ ReLU(x_{k}-\frac{2N-1}{2N})\end{bmatrix}\stackrel{{\mathfrak{F}}}{ {\mapsto}}\begin{bmatrix}\mathfrak{F}(ReLU)(x_{k})\\ \mathfrak{F}(ReLU)(x_{k}-\frac{1}{2N})\\ \vdots\\ \mathfrak{F}(ReLU)(x_{k}-\frac{2N-1}{2N})\end{bmatrix}\equiv g_{1}(x_{k}),\] for all \(k=1,\ldots,n\).
3. **Second hidden layer:** Taking \(g_{1}\) as the input for the second layer, the output \(g_{2}\) is given by \[g_{1}(x_{k})\mapsto f_{\mathrm{samp}}\cdot g_{1}(x_{k})=\sum_{j=0}^{2N-1}f(j/2 N)\mathfrak{F}(ReLU)(x_{k}-j/2N)\equiv g_{2}(x_{k}),\] for all \(k=1,\ldots,n\).
4. **Output:** The output of our GNN is the function \(g_{2}(x_{k})\) for each \(k=1,\ldots,n\).

We make three observations. Firstly, as our GNN only requires two hidden layers, the parameter of the network consists of the nonunital linear weights that are the \(2N\) entries of \(f_{\mathrm{samp}}\). Secondly, the formula for the GNN output

\[\sum_{j=0}^{2N-1}f(j/2N)\mathfrak{F}(ReLU)(x_{k}-j/2N), \tag{2.27}\]
like the one in (2.22), carries the form of a sampling principle. Thirdly, it's evident from (2.26) that our choice for graph filter kernel assumes the form

\[\mathcal{K}(x_{k},x_{l})=\mathcal{G}^{*}(x_{k},x_{l})W(x_{k},x_{l}),\quad\forall k \neq l.\]

We again note the similarity with (2.5).

**Remark 2.1**.: _(\(d\)-dimensional input features versus one-dimensional input features)_

Our GNN construction exclusively operates on the input features \(x_{k}\in[0,1]\) assigned to the vertices \(v_{k}\) during the embedding of \(G_{n}\) into the graphon space. While the graph vertices may have initially been associated with Euclidean feature vectors in \(\mathbb{R}^{d}\), we disregard them and instead adopt the vertex locations on the interval \([0,1]\) as the input for our GNN. This distinguishes our approach from the conventional GNN framework, which typically relies on vectors in \(\mathbb{R}^{d}\). By simplifying the input to single scalar values, we enable the construction of our GNN with two hidden layers and \(2N\) nonunital linear weights corresponding to the entries of \(f_{\text{samp}}\). The network output value \(g_{2}(x_{k})\) represents an estimate of the target function \(f_{n}\) at the vertex \(v_{k}\).

**Remark 2.2**.: _(embedded sampling principle)_ As demonstrated, we explicitly employ the order (2.3) for both of our networks. This deliberate choice serves a purpose that is to allow a seamless integration of sampling theory into the network architectures. The emerging sampling principle will provide all the required network parameters for achieving effective generalization, thereby removing the need for a learning processes. A demonstration of this link in a similar context can be found in [43].

## 3 Main Results

In this section we present the main contributions of this paper. We present four theorems. First, in SS3.1 we provide a uniform sampling theorem on \([0,1]\). Then, in SS3.2 we provide a theorem that establishes WNNs' capacity to generalize graphon signals from evenly spaced samples. We leverage these two theoretical results to derive transferability results for GNNs in SS3.3, applying to both deterministic and random graph sequences generated from a single graphon. We conclude this section with a discussion of the ramifications of our results to practical applications in SS3.4. All proofs are left to the sections that follow this one.

As an aside, through the remainder of this paper we adhere to the analysis practice where universal constants denoted by \(C\) may vary in value from one instance to another.

### A uniform sampling theorem

To begin, let \(r\in(0,1/2)\) and define the \(1\)-periodic function \(\mathcal{G}_{r,\sigma}\) on \(\mathbb{R}\) to be

\[\mathcal{G}_{r,\sigma}(x):=\begin{cases}\mathcal{G}_{\sigma}(x):=c(\sigma)\sum _{n\in\mathbb{Z}}e^{-n^{2}\sigma^{-2}/2}e^{i2\pi nx},&-r\leq x\leq r\\ 0,&\text{otherwise}\end{cases} \tag{3.1}\]
where \(r\) is a truncation parameter, \(\sigma\) a variance parameter, and \(c(\sigma)>0\) is a normalization constant such that \(\mathcal{G}_{r,\sigma}(0)=\mathcal{G}_{\sigma}(0)=1\). Due to its periodicity, \(\mathcal{G}_{r,\sigma}\) can equivalently be viewed as a function on \(\mathbb{T}\). Now supposing \(N>\mathfrak{m}\), for \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\) and \(\mathcal{G}_{r,\sigma}\), we consider the reconstruction scheme of \(f\) from its uniform samples \(f_{\rm samp}=\begin{bmatrix}f(0)&f(1/2N)&\cdots&f((2N-1)/2N)\end{bmatrix}\) given by

\[\mathcal{R}_{r,\sigma}f(x):=\sum_{j=0}^{2N-1}f(j/2N)s_{N}(y-j/2N)\mathcal{G}_{ r,\sigma}(x-j/2N), \tag{3.2}\]

where \(s_{N}\) is as in (2.17). The following theorem is our first result of this section, an interesting sampling theorem in its own right. It shows that, with the right choice of \(r,\sigma\) and \(N\), the reconstruction scheme in (3.2) produces a subgeometric convergence rate in \(L^{2}\) norm. It will enable our results on WNNs and GNNs that follow. The proof is left to SS4.

**Theorem 3.1**.: _Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\) and \(\mathcal{R}_{r,\sigma}f\) be as in (4.18). Let \(0<\alpha<\beta<1\), \(N>\mathfrak{m}\), and set_

\[\sigma=\frac{(N-\mathfrak{m})^{\beta}}{\sqrt{6}\pi}\quad\text{ and }\quad r= \frac{3\pi}{(N-\mathfrak{m})^{\alpha}}. \tag{3.3}\]

_Then there exists \(C>0\) such that the followings hold:_

\[\|f-\mathcal{R}_{r,\sigma}f\|_{L^{2}([0,1];\mathbb{C}^{m})}\leq C\widetilde{ \mathcal{E}}(N,\mathfrak{m},\alpha,\beta)\|f\|_{L^{2}([0,1];\mathbb{C}^{m})} \tag{3.4}\]

_for sufficiently large \(N\), where_

\[\widetilde{\mathcal{E}}(N,\mathfrak{m},\alpha,\beta):=e^{-3\pi^{2}(N- \mathfrak{m})^{2(1-\beta)}}\max\left\{1,(N-\mathfrak{m})^{2\beta-1}\right\}+ (N-\mathfrak{m})^{\alpha+\beta}e^{-3\pi^{2}(N-\mathfrak{m})^{2(\beta-\alpha)}}. \tag{3.5}\]

### Generalization using WNNs

The sampling result in Theorem 3.1 will play a crucial role in enabling us to define the kernel (2.23) used in constructing the filter layer of our WNN architecture in SS2.5. We begin by considering a graphon \(W:[0,1]^{2}\to[0,1]\), the function \(\mathcal{G}_{r,\sigma}\) as given in (3.1), and, for some \(N\geq 1\), \(s_{N}\) as given in (2.17). Then, suppressing the dependence on \((r,\sigma,N)\) for the ease of presentation, we define an (asymmetric) kernel \(\mathcal{K}\) (see (2.21)) by

\[\mathcal{K}(x,y)=\bigg{(}\frac{\mathrm{d}^{2}}{\mathrm{d}y^{2}}\,(s_{N}\, \mathcal{G}_{r,\sigma})(x-y)\bigg{)}\bigg{(}\frac{W(x,y)}{\mathcal{W}_{x}} \bigg{)}, \tag{3.6}\]

where, for each \(x\in[0,1]\) we set

\[\mathcal{W}_{x}:=\frac{1}{|\mathfrak{I}_{x}|}\int_{\mathfrak{I}_{x}}W(x,y) \,\mathrm{d}y\quad\text{ and }\quad\mathfrak{I}_{x}:=[0,1]\cap[-r+x,x+r], \tag{3.7}\]
and for every \(j\in\mathbb{N}\),

\[\frac{\mathrm{d}^{j}}{\mathrm{d}x^{j}}\mathcal{G}_{r,\sigma}(x)=\mathcal{G}_{r, \sigma}^{(j)}(x):=\begin{cases}\mathcal{G}_{\sigma}^{(j)}(x)&-r\leq x\leq r\\ 0&\text{otherwise}\end{cases}. \tag{3.8}\]

We now state our result on the generalization capabilities of WNNs for Fourier bandlimited graphon signals. The proof can be found in SS5.

**Theorem 3.2**.: _Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\) and \(W\) a graphon satisfying Assumption 2.1. Let \(\alpha=0.96\), \(\beta=0.98\), and \(\varepsilon\in(0,1)\). Then there exist \(C>0\) and a ReLU WNN \(\Psi_{f}\), using the graphon kernel \(\mathcal{K}\) in (3.6), with \(r,\sigma\) specified by_

\[r=\frac{3\pi}{(N-\mathfrak{m})^{\alpha}}\quad\text{ and }\quad\sigma=\frac{(N- \mathfrak{m})^{\beta}}{\sqrt{6}\pi},\]

_where \(N=\lceil\varepsilon^{-10/9}\rceil\gg\mathfrak{m}\), such that_

\[\|\Psi_{f}-f\|_{L^{2}([r,1-r];\mathbb{C}^{m})}\leq C\eta^{-1}K\,\varepsilon \,\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}. \tag{3.9}\]

_More precisely, \(\Psi_{f}\) assumes the structure described in SS2.5, with two layers, including one filter layer, and \(2N=2\lceil\varepsilon^{-10/9}\rceil\) linear weights that are supplied by the sampled functional values of \(f\)._

**Remark 3.1**.: The specific choices of \(\alpha,\beta\) are made for the sake of concreteness. In fact, it is possible to choose \(\alpha\) in such a way that we obtain \(N=\lceil\varepsilon^{-\delta}\rceil\), where \(\delta\) can be as close to \(1\) as possible. The choices we make are motivated by the following considerations:

\[1-\beta=\beta-\alpha\leq 1/4\quad\text{ and }\quad\alpha>3/5.\]

The last condition will become evident during the proof of the theorem (see (5.21)), while the first condition arises from our effort to equate the two geometric rates in (3.5).

The foundation of Theorem 3.2 relies on the result established in Theorem 3.1. However, the two differ in the scope of their predictions. While our sampling result guarantees predictions on the entire interval \([0,1]\), Theorem 3.2 provides guarantees for the specific _predictable_ zone \([r,1-r]\), which, since \(r=C(N-\mathfrak{m})^{-\alpha}\) and \(N=\lceil\varepsilon^{-10/9}\rceil\), widens to \([0,1]\) as \(\varepsilon\to 0^{+}\). This distinction arises from a crucial implementation of an integration-by-parts result in Theorem 3.2 (see Proposition 5.1), which secures its conclusion but in the process, inherently restricts the prediction range.

### Generalization on graphs and GNN-transferability

Now, consider a graphon \(W:[0,1]^{2}\to[0,1]\) and let \(\{G_{n}\}_{n=1}^{\infty}\) be a sequence of simple graphs on \(n\) vertices, generated from \(W\) as in SS2.2. Further, we denote \(\mathbf{A}_{n}\in\mathbb{R}^{n\times n}\) as the
adjacency matrix associated to each \(G_{n}\). Taking \(\mathcal{G}_{r,\sigma}\) to be as in (3.1) and \(s_{N}\) as in (2.17) for some fixed \(N\geq 1\), for each \(n\geq 1\) we define the graph filter kernel (see (2.26))

\[\mathcal{K}_{n}(x_{k},x_{l})=\frac{1}{n}\bigg{(}\frac{\mathrm{d}^{2}}{\mathrm{d }x^{2}}\,(s_{N}\,\mathcal{G}_{r,\sigma})(x_{k}-x_{l})\bigg{)}\bigg{(}\frac{[ \mathbf{A}_{n}]_{k,l}}{\mathcal{W}_{x_{k}}}\bigg{)}. \tag{3.10}\]

Here \(\mathcal{W}_{x_{k}}\) is defined from the graphon \(W\) as in (3.7) for \(x=x_{k}\).

The sequence \(\{G_{n}\}_{n=1}^{\infty}\) can be comprised of either deterministic or random graphs. When we need to differentiate between the two cases, we adopt specific notations. When \(G_{n}\) is deterministic, we denote it as \(G_{n}^{\mathrm{det}}\), and in this scenario, \([\mathbf{A}_{n}]_{k,l}=W(x_{k},x_{l})\), for \(k\neq l\). When \(G_{n}\) is random, we represent it as \(G_{n}^{\mathrm{ran}}\). In this case, \(\mathbf{A}_{n}\) becomes a random matrix, and each \(\mathcal{K}_{n}(x_{k},x_{l})\) is a random variable for \(k\neq l\). A realization of \(G_{n}^{\mathrm{ran}}\) yields a graph with a binary adjacency matrix \(\mathbf{A}_{n}\) whose entries \([\mathbf{A}_{n}]_{k,l}\in\{0,1\}\). In short, regardless of whether \(G_{n}\) is deterministic or random or realized, we only need to substitute the corresponding adjacency matrix into (3.10).

We now state our results on the generalization capabilities of GNNs for graphs belonging to the same graphon family. Their proofs can be found in SS6, SS7, with respect to the order in which the theorems are presented.

**Theorem 3.3**.: _(Deterministic GNNs) Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\) and \(W\) a graphon satisfying Assumption 2.1. Let \(\varepsilon\in(0,1)\), \(n\geq 1\), \(G_{n}^{\mathrm{det}}\) be a deterministic graph generated from \(W\), and \(f_{n}\) an associated graph signal such that \(f_{n}(x_{k})=f(x_{k})\) for all \(x_{k}\). Then there exist \(C>0\) and a ReLU GNN \(\Psi_{n,f}\), using the graph kernel \(\mathcal{K}_{n}\) in (3.10) with \(r,\sigma\) specified by_

\[r=\frac{3\pi}{(N-\mathfrak{m})^{\alpha}}\quad\text{ and }\quad\sigma=\frac{(N- \mathfrak{m})^{\beta}}{\sqrt{6}\pi},\]

\(\alpha=0.96\)_, \(\beta=0.98\), \(N=\lceil\varepsilon^{-10/9}\rceil\gg\mathfrak{m}\), such that for all \(n\geq\varepsilon^{-13/3}\), it holds that_

\[\|\overline{\Psi}_{n,f}-f\|_{L^{2}([r,1-r];\mathbb{C}^{m})}\leq C\eta^{-2}(1+K )\,\varepsilon\,\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}, \tag{3.11}\]

_where_

\[\overline{\Psi}_{n,f}(x):=\sum_{k=1}^{n}\Psi_{n,f}(x_{k})\chi_{I_{k}}(x), \quad\forall x\in[0,1]. \tag{3.12}\]

_More precisely, \(\Psi_{n,f}\) assumes the structure described in SS2.5, with two layers, including one filter layer, and \(2N=2\lceil\varepsilon^{-10/9}\rceil\) linear weights that are supplied by the sampled functional values of the graphon signal \(f\)._

**Theorem 3.4**.: _(Random GNNs) Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\) and \(W\) a graphon satisfying Assumption 2.1. Let \(\varepsilon\in(0,1)\), \(n\geq 1\), \(G_{n}^{\mathrm{ran}}\) be a simple random graph generated from \(W\), and \(f_{n}\) an associated graph signal such that \(f_{n}(x_{k})=f(x_{k})\) for all \(x_{k}\). Then there exist \(C>0\) and a ReLU GNN \(\Psi_{n,f}\), using the graph kernel \(\mathcal{K}_{n}\) in (3.10) with \(r,\sigma\) specified by_

\[r=\frac{3\pi}{(N-\mathfrak{m})^{\alpha}}\quad\text{ and }\quad\sigma=\frac{(N- \mathfrak{m})^{\beta}}{\sqrt{6}\pi},\]
\(\alpha=0.96\), \(\beta=0.98\), \(N=\lceil\varepsilon^{-10/9}\rceil\gg\mathfrak{m}\), such that for all \(n\geq\varepsilon^{-13/3}\), it holds that_

\[\|\overline{\Psi}_{n,f}-f\|_{L^{2}([r,1-r];\mathbb{C}^{m})}\leq C\eta^{-2}(1+K) \,\varepsilon\,\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}, \tag{3.13}\]

_where \(\overline{\Psi}_{n,f}\) is defined in (3.12), with a probability at least_

\[1-2n\varepsilon^{10(1-\alpha)/9}\exp\bigg{(}-\frac{C\eta^{2}n}{\varepsilon^{4 (15\beta-5\alpha-2)/9}}\bigg{)}. \tag{3.14}\]

_More precisely, \(\Psi_{n,f}\) assumes the structure described in SS2.5, with two layers, including one filter layer, and \(2N=2\lceil\varepsilon^{-10/9}\rceil\) linear weights that are supplied by the sampled functional values of the graphon signal \(f\)._

It should be apparent in (3.14) that as the number of graph vertices \(n\) increases, the likelihood of (3.13) holding also increases. We make a brief remark that the lower bound of \(\varepsilon^{-13/3}\) for \(n\) can be improved to be as near \(\varepsilon^{-4}\) as possible (see also Remark 6.1). The lower bound we obtain for \(n\) in both theorems is a direct consequence of the choices we make for \(\alpha,\beta\).

**Remark 3.2**.: We would like to highlight an alternative generation of simple random graphs using a specific graphon \(W\), as follows. Given \(n\geq 1\) vertices, labeled as \(v_{1},\cdots,v_{n}\), one can independently sample them as random variables \(\xi_{1},\cdots,\xi_{n}\) from the uniform distribution on the interval \([0,1]\). The vertices \(v_{k}\) and \(v_{l}\), \(k>l\), are connected by an edge with an edge-weight of \(W(\xi_{k},\xi_{l})\). This results in a distinct type of random graph, different from the primary ones considered in this paper. Nevertheless, a variant of Theorem 3.4 can be adapted to analyze these types of random graphs and provide similar estimations. To derive this version, we anticipate utilizing the Bernstein inequality [7]. For a practical demonstration of how this inequality is applied in this context, interested readers are referred to [11, Lemma 1].

### Ramifications of the results

Having now presented our main results, we now highlight their most important ramifications.

1. The two major contributions of this work are the GNN results presented in Theorems 3.3 and 3.4. What they provide is the production of a shallow GNN structure that uses a small number of generated samples from the graphon signal and gives a reliable prediction on any large graph within the graphon family. As the GNNs are constructed with predetermined network parameters, our approach does not involve any learning process.
2. Our approach yields a dimensionless result for the network structure, which is the consequence of our taking in of one-dimensional input features. This lack of dimensional-dependence, as explained in Remark 2.1, is made possible by the graphon presence. The existence of a macroscopic graphon structure is crucial since it enables
us to leverage the transition from a multi-dimensional generalization process to a one-dimensional one, hence circumventing the curse of dimensionality. As a simple demonstration of this efficacy, note that the generalization depicted in Theorem 3.3 provides accurate predictions within, after some appropriate scaling by universal and intrinsic constants, an error of approximately \(0.1\), for at least 19700 vertices in a graph containing at least 21500 vertices, while using a low-cost network with only 26 linear weights, therefore resulting in a cost ratio of approximately \(0.0006\).
3. Additionally, our approach offers a seamless transferability of the network architecture across graphs of different sizes. This transferability, which is of paramount importance, involves a straightforward substititon of the relevant adjacency matrix into the kernel (3.10) while ensuring comparable signal generalization estimates. The subsequent corollary, which we give without proof, serves as a validation of this notable outcome. **Corollary 3.1**.: _(GNN transferability) Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{m}\) and \(W\) be a graphon satisfying Assumption 2.1. Let \(\varepsilon\in(0,1)\) and let \(G_{n_{1}}\), \(G_{n_{2}}\) be two graphs generated from \(W\) (random or deterministic) where \(n_{1}\leq n_{2}\). Denote \(\Psi_{n_{1},f}\) as the ReLU GNN associated with \(G_{n_{1}}\), assuming the structure described in SS3.3, and \(\Psi_{n_{2},f}\) the similar ReLU GNN associated with \(G_{n_{2}}\). Suppose that (3.11) holds for \(\Psi_{n_{1},f}\), in the case that \(G_{n_{1}}\) is deterministic, or with a probability at least_ \[1-2n_{1}\varepsilon^{10(1-\alpha)/9}\exp\bigg{(}-\frac{C\eta^{2}n_{1}}{ \varepsilon^{4(15\beta-5\alpha-2)/9}}\bigg{)}.\] _in the case that \(G_{n_{1}}\) is random. Then (_3.11_) also holds for \(\Psi_{n_{2},f}\), in the case that \(G_{n_{2}}\) is deterministic, or with a probability at least_ \[1-2n_{2}\varepsilon^{10(1-\alpha)/9}\exp\bigg{(}-\frac{C\eta^{2}n_{2}}{ \varepsilon^{4(15\beta-5\alpha-2)/9}}\bigg{)}.\] _in the case that \(G_{n_{2}}\) is random._ As an expository application, take the recommender systems that were used as motivation in the introduction and provided the first application of WNNs in [48]. An \(m\)-dimensional graph signal encodes the ratings given by an individual user, represented as a vertex, for each of the \(m\) products that the service recommends. Our approach permits a GNN to be constructed from the ratings obtained from \(2N\) users, which can then predict the ratings that \(n\gg 2N\) users would assign to each product based on the sampled information. This avoids having to retrain the GNN structure as users are added or subtracted from the service, allowing for a more efficient and scalable recommender system that can adapt to changes in the user base without the burden of frequent model updates. Furthermore, our approach extends the methodology of [48], which constructs deterministic graphs based on pairwise correlations of user rankings, by interpreting these correlations as the likelihood of two users having
overlapping tastes, therefore enabling the construction of random graphs. Our GNNs then provide the same level of prediction accuracy with high probability on these random graphs. This probabilistic framework enhances the robustness and reliability of the predictions generated by the GNN-based recommender system.
4. Our results to some degree strengthen the findings presented in [43], where a similar strategy of incorporating the sampling principle into a GNN structure was employed. A limitation of said work is the unavoidable growth in the number of layers with respect to the input feature dimension, attributed to its use of one-dimensional numerical integration methods. In contrast, as our approach utilizes input features in \([0,1]\), it eliminates the dependency on the input dimension and results in a streamlined GNN consisting of only two layers. In the graphon context, the grid lattice employed in [43] falls within the family of the graphons that are almost everywhere constant in a neighborhood of the diagonal. Consequently, with our approach, as detailed in Remark 5.2, the number of weights would only accumulate to \(N=C\lceil(\log(1/\varepsilon))^{1/(2(\beta-\alpha))}\rceil\). This further serves as a testament to the potential and the unique advantage that graphons offer in GNN applications.

## 4 Proof of Theorem 3.1

In this section, we make the necessary steps toward establishing the validity of Theorem 3.1 in SS4.2 below. The main idea for the proof centers around the use of a truncated and regularized variant of Kluvanek's sampling formulation [33]. More precisely, let \(\mathfrak{m},N\in\mathbb{N}\) and suppose \(N\geq\mathfrak{m}\). For any \(f\in\mathcal{B}_{\mathfrak{m}}\), by Proposition 2.1 we have

\[f(x)=\sum_{j=0}^{2N-1}f(j/2N)s_{N}(x-j/2N),\quad\forall x\in[0,1], \tag{4.1}\]

where \(s_{N}\) is as in (2.17). Our goal is to replace the series on the right-hand-side of (4.1) with

\[\sum_{j=0}^{2N-1}f(j/2N)\mathcal{G}(x-j/2N)\]

where \(\mathcal{G}\) is some function exhibiting a "Gaussian-like" behavior, but only supported in a vicinity of \(x\) of some appropriate radius \(r\). To begin, we need to establish a general result for regularized sampling. In this section as well as others that follow, we will make repeated use of the McLaurin-Cauchy integral test [34, SS3.3, Theorem 3] and the Mills' ratio formula [8], which we cite here for the reader's convenience:

\[\int_{x}^{\infty}e^{-t^{2}/2}\,\mathrm{d}t\leq\frac{\pi e^{-x^{2}/2}}{\sqrt{( \pi-2)^{2}x^{2}+2\pi}+2x}, \tag{4.2}\]

for every \(x>0\).
### A regularized sampling result

Let \(\phi:[0,1]\to\mathbb{C}\) be a continuous function such that \(\phi(0)=\phi(1)=1\) and its Fourier coefficients are absolutely summable, i.e. \(\hat{\phi}\in\ell^{1}(\mathbb{Z})\). Then \(\hat{\phi}\in\ell^{2}(\mathbb{Z})\) as well, and from the Fourier inversion theorem [20] we have \(\phi\in L^{2}([0,1])\) with

\[\sum_{l\in\mathbb{Z}}\hat{\phi}(l)=\phi(0)=1. \tag{4.3}\]

For any \(N\in\mathbb{N}\), let \(\chi_{B_{N}}\) denote a function that is one on \(B_{N}=\{-N,\ldots,N-1\}\subset\mathbb{Z}\) and zero on \(\mathbb{Z}\setminus B_{N}\). For each \(k\in\mathbb{Z}\) we define

\[\mu(k):=\chi_{B_{N}}*\hat{\phi}(k)=\sum_{l\in\mathbb{Z}}\chi_{B_{N}}(k-l)\hat{ \phi}(l)=\sum_{l\in k-B_{N}}\hat{\phi}(l), \tag{4.4}\]

and

\[\nu(k):=\sum_{l\not\in k-B_{N}}\hat{\phi}(l). \tag{4.5}\]

We gather from (4.3), (4.4), (4.5) that

\[\sum_{l\in\mathbb{Z}}\mu(k+l2N)=\sum_{l\in\mathbb{Z}}\hat{\phi}(l)=1=\nu(k)+ \mu(k),\quad\forall k\in\mathbb{Z}, \tag{4.6}\]

and so we deduce

\[\nu(k)=\sum_{l\in\mathbb{Z}\setminus\{0\}}\mu(k+l2N),\quad\forall k\in \mathbb{Z}. \tag{4.7}\]

Now, let \(f\in\mathcal{B}_{\mathfrak{m}}\) and take \(N\geq\mathfrak{m}\). We define

\[\mathcal{R}_{\phi}f(x):=\sum_{j=0}^{2N-1}f(j/2N)s_{N}(x-j/2N)\phi(x-j/2N),\quad \forall x\in[0,1], \tag{4.8}\]

where, from the definition (2.17) of \(s_{N}\), we can write

\[\hat{s}(k)=\frac{1}{2N}\chi_{B_{N}}(k),\quad\forall k\in\mathbb{Z}.\]

Since all the functions involved in (4.8) are continuous on \(\mathbb{T}\cong[0,1)\), we treat the argument addition in (4.8) as a group addition on \(\mathbb{T}\), i.e. it is taken modulo \(1\). (Alternatively, we can consider treating them as \(1\)-periodic functions on \(\mathbb{R}\). This perspective will be used in SS5.) Reasonably, we can no longer expect \(f=\mathcal{R}_{\phi}f\). However, we claim that the regularized sampling error, i.e. \(f-\mathcal{R}_{\phi}f\), can be understood in terms of \(\mu,\nu\) in (4.4) and (4.5), respectively.

**Lemma 4.1**.: _Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\) and \(N\geq\mathfrak{m}\). Then_

\[\hat{f}(k)-\widehat{\mathcal{R}_{\phi}f}(k)=\begin{cases}\hat{f}(k)\nu(k),&k \in B_{\mathfrak{m}}\\ -\hat{f}(k-2lN)\mu(k),&\exists l\neq 0\text{ s.t }k-2lN\in B_{\mathfrak{m}}\\ 0,&\text{otherwise}\end{cases}.\]
Proof.: Recall from Lemma 2.1 that

\[\hat{f}(k)=\begin{cases}\frac{1}{2N}\sum_{j=0}^{2N-1}f(j/2N)e^{-i2\pi kj/2N}&k\in B _{\mathfrak{m}}\\ 0&\text{otherwise}\end{cases}. \tag{4.9}\]

Let \(k\in B_{N}\). By combining (4.9) with (4.4), (4.8), and the definition of \(s_{N}\), we further obtain

\[\widehat{\mathcal{R}_{\phi}f}(k)=\frac{1}{2N}\sum_{j=0}^{2N-1}f(j/N)e^{-i2\pi kj /2N}\mu(k)=\hat{f}(k)\mu(k).\]

Therefore, from (4.6)

\[\hat{f}(k)-\widehat{\mathcal{R}_{\phi}f}(k)=\hat{f}(k)\nu(k), \tag{4.10}\]

which from (4.9), in turn implies \(\hat{f}(k)-\widehat{\mathcal{R}_{\phi}f}(k)=0\), if \(k\in B_{N}\setminus B_{\mathfrak{m}}\).

Now suppose \(k\not\in B_{N}\) but \(k-2lN\in B_{N}\) for some \(l\neq 0\). Then

\[\begin{split}\hat{f}(k)-\widehat{\mathcal{R}_{\phi}f}(k)& =-\widehat{\mathcal{R}_{\phi}f}(k)\\ &=-\frac{1}{2N}\sum_{j=0}^{2N-1}f(j/N)e^{-i2\pi(k-2lN)j/2N}\mu(k )=-\hat{f}(k-2lN)\mu(k),\end{split} \tag{4.11}\]

where we have again used (4.9). In this case, if \(k-l2N\in B_{N}\setminus B_{\mathfrak{m}}\) then it follows from (4.9) and (4.11) that

\[\hat{f}(k)-\widehat{\mathcal{R}_{\phi}f}(k)=0. \tag{4.12}\]

Combining (4.10), (4.11), (4.12), we conclude the lemma. 

We now provide the bounds on the difference between \(f\) and \(\mathcal{R}_{\phi}f\) in both the \(L^{2}\) and \(L^{\infty}\) norms, which will eventually be employed to prove Theorem 3.1 in the following subsection SS4.2.

**Lemma 4.2**.: _Let \(f\in L^{2}([0,1];\mathbb{C}^{m})\cap\mathcal{B}_{\mathfrak{m}}\). Then_

\[\overline{\varepsilon}_{1}\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}\leq\|f-\mathcal{ R}_{\phi}f\|_{L^{2}([0,1];\mathbb{C}^{m})}\leq\,\overline{\varepsilon}_{2}\|f\|_{ L^{2}([0,1];\mathbb{C}^{m})}, \tag{4.13}\]

_where_

\[\overline{\varepsilon}_{1} :=\min_{k\in B_{\mathfrak{m}}}\bigg{\{}|\nu(k)|^{2}+\sum_{l\in \mathbb{Z}\setminus\{0\}}|\mu(k+l2N)|^{2}\bigg{\}}^{1/2}\] \[\overline{\varepsilon}_{2} :=\max_{k\in B_{\mathfrak{m}}}\bigg{\{}|\nu(k)|^{2}+\sum_{l\in \mathbb{Z}\setminus\{0\}}|\mu(k+l2N)|^{2}\bigg{\}}^{1/2}.\]

Proof.: By applying Lemma 4.1 and utilizing Plancherel's theorem, we obtain

\[\|f-\mathcal{R}_{\phi}f\|_{L^{2}([0,1];\mathbb{C}^{m})}^{2}=\sum_{k\in B_{ \mathfrak{m}}}|\hat{f}(k)\nu(k)|^{2}+\sum_{l\in\mathbb{Z}\setminus\{0\}}\sum_ {k\in B_{\mathfrak{m}}}|\hat{f}(k)\mu(k+2l\pi)|^{2}, \tag{4.14}\]

from which (4.13) automatically follows. We note that the \(L^{2}\)-bounds cannot be improved, due to the equality (4.14).
### Sampling with \(\mathcal{G}_{r,\sigma}\)

In this subsection we will apply Lemma 4.2 to specific regularizers \(\phi\), resulting in the proof of Theorem 3.1.

Let \(\sigma>0\) and recall the regularizer

\[\mathcal{G}_{\sigma}(x)=c(\sigma)\sum_{k\in\mathbb{Z}}e^{-k^{2}\sigma^{-2}/2}e ^{i2\pi kx}=2c(\sigma)\sum_{k=0}^{\infty}e^{-k^{2}\sigma^{-2}/2}\cos(2\pi kx),\quad\forall x\in[0,1]. \tag{4.15}\]

presented previously in (3.1). Since \(\mathcal{G}_{\sigma}(0)=\mathcal{G}_{\sigma}(1)\), we consider \(\mathcal{G}_{\sigma}\) as a function on \(\mathbb{T}\cong[0,1)\cong[-1/2,1/2)\). The parameter \(\sigma\) is a variance parameter, and \(c(\sigma)\) is a normalization constant guaranteeing that

\[\mathcal{G}_{\sigma}(0)=\|\hat{\mathcal{G}}_{\sigma}\|_{\ell^{1}(\mathbb{Z}) }=c(\sigma)\sum_{k\in\mathbb{Z}}e^{-k^{2}\sigma^{-2}/2}=1,\]

where \(\hat{\mathcal{G}}_{\sigma}(k)=c(\sigma)e^{-k^{2}\sigma^{-2}/2}\) according to (4.15). Note that \(c(\sigma)\leq 1\).

The motivation for the definition (4.15) stems from the fact that \(\mathcal{G}_{\sigma}\) mimics "Gaussian"-like behavior. We highlight this with the following lemma.

**Lemma 4.3**.: _The function \(\mathcal{G}_{\sigma}\), as defined in (4.15), satisfies_

\[\mathcal{G}_{\sigma}(x)>0,\quad\forall x\in\mathbb{T}, \tag{4.16}\]

_is even, and_

\[\mathcal{G}_{\sigma}(x)=\sum_{l\in\mathbb{Z}}\mathfrak{g}(x+l),\quad\forall x \in\mathbb{T}. \tag{4.17}\]

_where \(\mathfrak{g}(\xi):=d(\sigma)e^{-2\xi^{2}\pi^{2}\sigma^{2}}\), with \(d(\sigma):=\sigma c(\sigma)\sqrt{2\pi}\)._

Proof.: For any \(g\in L^{2}(\mathbb{R})\) we denote the Fourier transform and its inverse by

\[\mathcal{F}_{\mathbb{R}}g(\xi):=\int_{\mathbb{R}}g(u)e^{-i2\pi u\xi}\,\mathrm{ d}u\quad\text{ and }\quad\mathcal{F}_{\mathbb{R}}^{-1}g(\xi):=\int_{\mathbb{R}}g(u)e^{i2\pi u\xi}\, \mathrm{d}u.\]

Precisely, it is known that \(\mathcal{F}_{\mathbb{R}}\circ\mathcal{F}_{\mathbb{R}}^{-1}=Id_{L^{2}(\mathbb{ R})}=\mathcal{F}_{\mathbb{R}}^{-1}\circ\mathcal{F}_{\mathbb{R}}\)[20]. Now, the function \(\mathfrak{g}^{*}(\xi):=c(\sigma)e^{-\xi^{2}\sigma^{-2}/2}\) is such that \(\mathfrak{g}^{*}(l)=\hat{\mathcal{G}}_{\sigma}(l)\) for all \(l\in\mathbb{Z}\), and it's the Fourier transform of the function

\[\mathcal{F}_{\mathbb{R}}^{-1}\mathfrak{g}^{*}(\xi)=\mathfrak{g}(\xi)=d( \sigma)e^{-2\xi^{2}\pi^{2}\sigma^{2}},\quad\forall\xi\in\mathbb{R},\]

where \(d(\sigma)=\sigma c(\sigma)\sqrt{2\pi}\). Hence, by invoking the Poisson summation formula [20], for each \(x\in\mathbb{T}\) we obtain

\[\mathcal{G}_{\sigma}(x)=\sum_{l\in\mathbb{Z}}\mathcal{G}_{\sigma}(l)e^{i2\pi l x }=\sum_{l\in\mathbb{Z}}\mathfrak{g}^{*}(l)e^{i2\pi lx}=\sum_{l\in\mathbb{Z}} \mathfrak{g}(x+l)>0,\]

which proves both (4.16) and (4.17). Finally, that \(\mathcal{G}_{\sigma}\) is even can be seen from definition (4.15).
Next, we introduce a truncated version of \(\mathcal{G}_{\sigma}\), also presented earlier in (3.1). Let \(r\in(0,1/2)\) and define, for \(x\in[-1/2,1/2)\cong\mathbb{T}\), the function

\[\mathcal{G}_{r,\sigma}(x)=\begin{cases}\mathcal{G}_{\sigma}(x)=c(\sigma)\sum_{k \in\mathbb{Z}}e^{-k^{2}\sigma^{-2}/2}e^{i2\pi kx},&-r\leq x\leq r\\ 0,&\text{otherwise}\end{cases}.\]

Note that \(\mathcal{G}_{r,\sigma}=\mathcal{G}_{\sigma}\chi_{I_{r}}\), where \(\chi_{I_{r}}\) is the indicator function on the interval \(I_{r}=[-r,r]\). Since \(\mathcal{G}_{\sigma}\) is even and real, so is \(\hat{\mathcal{G}}_{r,\sigma}\) on \(\mathbb{Z}\). Recall the following truncated regularized sampling series of \(f\) introduced in (3.2):

\[\mathcal{R}_{r,\sigma}f(x)=\sum_{j=0}^{2N-1}f(j/2N)s(x-j/2N)\mathcal{G}_{r, \sigma}(x-j/2N). \tag{4.18}\]

We compute that

\[\widehat{\mathcal{R}_{r,\sigma}f}(k)=\frac{1}{2N}\sum_{j=0}^{2N-1}f(j/2N)e^{- i2\pi kj/2N}\mu_{r,\sigma}(k)\]

where, we have defined

\[\mu_{r,\sigma}(k):=\chi_{B_{N}}*\hat{\mathcal{G}}_{r,\sigma}(k)=\sum_{l\in k- B_{N}}\hat{\mathcal{G}}_{r,\sigma}(l). \tag{4.19}\]

If we let

\[\nu_{r,\sigma}(k):=\sum_{l\not\in k-B_{N}}\hat{\mathcal{G}}_{r,\sigma}(l), \tag{4.20}\]

then we gather that

\[\nu_{r,\sigma}(k)+\mu_{r,\sigma}(k)=\sum_{l\in\mathbb{Z}}\hat{\mathcal{G}}_{r,\sigma}(l)=1\quad\text{ and }\quad\nu_{r,\sigma}(k)=\sum_{l\in\mathbb{Z}\setminus\{0\}}\mu_{r, \sigma}(k+l2N),\quad\forall k\in\mathbb{Z}. \tag{4.21}\]

Both \(\nu_{r,\sigma},\mu_{r,\sigma}\) are even on \(\mathbb{Z}\). It should be clear from the past analysis that \(\mu_{r,\sigma}\) will play the role of \(\mu\) in (4.4). Therefore, to access the upper bound in (4.13), Lemma 4.2, we would need an estimate for

\[\max_{k\in B_{\text{\rm m}}}\bigg{\{}|\nu_{r,\sigma}(k)|^{2}+\sum_{l\in \mathbb{Z}\setminus\{0\}}|\mu_{r,\sigma}(k+l2N)|^{2}\bigg{\}}^{1/2}.\]

For ease of computation, we will replace this quantity with

\[\max_{k\in B_{\text{\rm m}}}|\nu_{r,\sigma}(k)|+\max_{k\in B_{\text{\rm m}}} \bigg{(}\sum_{l\in\mathbb{Z}\setminus\{0\}}|\mu_{r,\sigma}(k+l2N)|^{2}\bigg{)} ^{1/2}. \tag{4.22}\]
We first handle \(\max_{k\in B_{\mathfrak{m}}}|\nu_{r,\sigma}(k)|\). Referring to definition (4.20), observe that for any \(k\in\mathbb{Z}\),

\[\nu_{r,\sigma}(k) =1-\sum_{l\in k-B_{N}}\hat{\mathcal{G}}_{r,\sigma}(l)\] \[=1-\sum_{l\in k-B_{N}}\bigg{(}\hat{\mathcal{G}}_{\sigma}(l)-\int_ {u\not\in[-r,r]\cap[-1/2,1/2)}\mathcal{G}_{\sigma}(u)e^{-i2\pi lu}\,\mathrm{d }u\bigg{)}\] \[=\sum_{l\not\in k-B_{N}}\hat{\mathcal{G}}_{\sigma}(l)+\int_{u \not\in[-r,r]\cap[-1/2,1/2)}\mathcal{G}_{\sigma}(u)\sum_{l\in k-B_{N}}e^{-i2 \pi lu}\,\mathrm{d}u\] \[=\sum_{l\not\in k-B_{N}}\hat{\mathcal{G}}_{\sigma}(l)+\int_{u \not\in[-r,r]\cap[-1/2,1/2)}\mathcal{G}_{\sigma}(u)\cos(2\pi(k-N+1)u)\bigg{(} \frac{1-e^{-i4\pi Nu}}{1-e^{-i2\pi u}}\bigg{)}\,\mathrm{d}u. \tag{4.23}\]

Note that the first sum on the right-hand-side above is \(\nu(k)\) in (4.5) with \(\phi=\mathcal{G}_{\sigma}\). This is the _regularization_ error. The integral on the right-hand-side, carrying an \(r\) in its expression, is the _truncation_ error.

A quick calculation from (4.23) gives

\[\max_{k\in B_{\mathfrak{m}}}|\nu_{r,\sigma}(k)|\leq\sum_{l\not\in\mathfrak{m}- 1-B_{N}}\hat{\mathcal{G}}_{\sigma}(l)+\frac{2\mathcal{G}_{\sigma}(r)}{|1-e^{- i2\pi r}|}. \tag{4.24}\]

Therefore, a bound on \(\max_{k\in B_{\mathfrak{m}}}|\nu_{r,\sigma}(k)|\) can be derived from an upper bound for the right-hand-side above.

**Proposition 4.1**.: _Let \(\nu_{r,\sigma}\) be as in (4.20). Let \(r,\sigma\) be as in (3.3). Then_

\[\max_{k\in B_{\mathfrak{m}}}|\nu_{r,\sigma}(k)|\leq C\widetilde{\mathcal{E}}_ {1}(N,\mathfrak{m},\alpha,\beta),\]

_for some \(C>0\), and_

\[\widetilde{\mathcal{E}}_{1}(N,\mathfrak{m},\alpha,\beta):=e^{-3\pi^{2}(N- \mathfrak{m})^{2(1-\beta)}}\max\bigg{\{}1,(N-\mathfrak{m})^{2\beta-1}\bigg{\}} +(N-\mathfrak{m})^{\alpha+\beta}e^{-3\pi^{2}(N-\mathfrak{m})^{2(\beta-\alpha)}}.\]

Proof.: Since \(e^{-x^{2}\sigma^{-2}/2}\) is even on \(\mathbb{R}\) and strictly decreasing on \([0,\infty)\), we have

\[\sum_{l\not\in\mathfrak{m}-1-B_{N}}\hat{\mathcal{G}}_{\sigma}(l)\leq 2\sum_{l \geq N-\mathfrak{m}}\hat{\mathcal{G}}_{\sigma}\leq 2\hat{\mathcal{G}}_{\sigma}(N- \mathfrak{m})+2\int_{N-\mathfrak{m}}^{\infty}e^{-u^{2}\sigma^{-2}/2}\,\mathrm{ d}u, \tag{4.25}\]

and so using Mills' ratio (4.2) we obtain

\[\int_{N-\mathfrak{m}}^{\infty}e^{-u^{2}\sigma^{-2}/2}\,\mathrm{d}u<\frac{\pi \sigma e^{-(N-\mathfrak{m})^{2}\sigma^{-2}/2}}{\sqrt{(\pi-2)^{2}(N-\mathfrak{ m})^{2}\sigma^{-2}+2\pi}+2(N-\mathfrak{m})\sigma^{-1}}. \tag{4.26}\]
By combining (4.25) and (4.26), and performing the necessary simplifications, we arrive at

\[\sum_{l\not\in\mathfrak{m}-1-B_{N}}\hat{\mathcal{G}}_{\sigma}(l)\leq 4e^{-(N- \mathfrak{m})^{2}\sigma^{-2}/2}\max\bigg{\{}1,\frac{\sigma^{2}}{N-\mathfrak{m }}\bigg{\}}.\]

Keeping in mind that \(\sigma=(N-\mathfrak{m})^{\beta}/(\sqrt{6}\pi)\) in (3.3) allows for the estimate

\[\sum_{l\not\in\mathfrak{m}-1-B_{N}}\hat{\mathcal{G}}_{\sigma}(l)\leq 4e^{-3\pi^{2} (N-\mathfrak{m})^{2(1-\beta)}}\max\bigg{\{}1,(N-\mathfrak{m})^{2\beta-1} \bigg{\}}. \tag{4.27}\]

On the other hand, since \(r\in(0,1/2)\), the function \(e^{-2(x+r)^{2}\pi^{2}\sigma^{2}}\) is strictly decreasing on \([0,\infty)\) and increasing on \((-\infty,-1]\). Thus, we deduce from (4.17) and Mills' ratio that

\[\mathcal{G}_{\sigma}(r) =\sum_{l\in\mathbb{Z}}\mathfrak{g}(r+l)\leq 3d(\sigma)e^{-2r^{2} \pi^{2}\sigma^{2}}+2d(\sigma)\int_{1-r}^{\infty}e^{-2\pi^{2}\sigma^{2}u^{2}} \,\mathrm{d}u\] \[\leq 3\sigma\sqrt{2\pi}e^{-2r^{2}\pi^{2}\sigma^{2}}+\frac{\sqrt{ \pi}e^{-2\pi^{2}\sigma^{2}(1-r)^{2}}}{\sqrt{(\pi-2)^{2}\pi^{2}\sigma^{2}(1-r)^ {2}+\pi}+2\pi\sigma(1-r)},\]

which, by the selections of \(r,\sigma\) in (3.3), simplifies to

\[\mathcal{G}_{\sigma}(r)\leq C(N-\mathfrak{m})^{\beta}e^{-3\pi^{2}(N- \mathfrak{m})^{2(\beta-\alpha)}} \tag{4.28}\]

for some \(C>0\). Since \(r=3\pi(N-\mathfrak{m})^{-\alpha}\), when \(N\) is sufficiently large, we can ensure that \(1-2\pi r\geq 1/2\). Hence

\[\frac{\mathcal{G}_{\sigma}(r)}{|1-e^{-i2\pi r}|}\leq\frac{C(N-\mathfrak{m})^{ \beta}}{r(1-2\pi r)}\bigg{(}e^{-3\pi^{2}(N-\mathfrak{m})^{2(\beta-\alpha)}} \bigg{)}\leq C(N-\mathfrak{m})^{\alpha+\beta}e^{-3\pi^{2}(N-\mathfrak{m})^{2( \beta-\alpha)}}. \tag{4.29}\]

By integrating (4.24), (4.27) and (4.29), we acquire the conclusion of the proposition. 

We will now shift our focus to the components involving \(\mu_{r,\sigma}\) in (4.22).

**Proposition 4.2**.: _Let \(\mu_{r,\sigma}\) be as in (4.19). Let \(r,\sigma\) be as in (3.3). Then there exists \(C>0\) such that_

\[\max_{k\in B_{\mathfrak{m}}}\bigg{(}\sum_{l\in\mathbb{Z}\setminus\{0\}}|\mu_{ r,\sigma}(k+l2N)|^{2}\bigg{)}^{1/2}\leq C\widetilde{\mathcal{E}}_{2}(N, \mathfrak{m},\alpha,\beta), \tag{4.30}\]

_where_

\[\widetilde{\mathcal{E}}_{2}(N,\mathfrak{m},\alpha,\beta):=(N-\mathfrak{m})^{ \beta}e^{-3\pi^{2}(N-\mathfrak{m})^{2(\beta-\alpha)}}+(N-\mathfrak{m})^{2 \beta-\alpha-1}e^{-3\pi^{2}(N-\mathfrak{m})^{2(1-\beta)}}.\]

Proof.: Since \(\mu_{r,\sigma}\) is even on \(\mathbb{Z}\) and \(N>\mathfrak{m}\), it is enough to prove the convergences in (4.30) for all integers of the form \(k^{\prime}=k+2l^{\prime}N\geq 0\), where \(l^{\prime}\in\mathbb{N}\), and so \(k^{\prime}-B_{N}\) consists of positive integers. Fix one such \(k^{\prime}\). Then, by definition (4.19)

\[\mu_{r,\sigma}(k+2l^{\prime}N)=\mu_{r,\sigma}(k^{\prime})=\sum_{l\in k^{ \prime}-B_{N}}\hat{\mathcal{G}}_{r,\sigma}(l)=\sum_{l\in k^{\prime}-B_{N}}\int_ {-r}^{r}\mathcal{G}_{\sigma}e^{-i2\pi lu}\,\mathrm{d}u. \tag{4.31}\]
From the Poisson formula (4.17), we obtain for each \(l\in k^{\prime}-B_{N}\) in (4.31) that

\[\begin{split}\int_{-r}^{r}\mathcal{G}_{\sigma}e^{-i2\pi lu}\, \mathrm{d}u&=d(\sigma)\sum_{j\in\mathbb{Z}}\int_{-r}^{r}e^{-2(u+j) ^{2}\pi^{2}\sigma^{2}}e^{-i2\pi lu}\,\mathrm{d}u\\ &=d(\sigma)\sum_{j\in\mathbb{Z}}\int_{j-r}^{j+r}e^{-2u^{2}\pi^{2} \sigma^{2}}e^{-i2\pi lu}\,\mathrm{d}u\\ &=d(\sigma)e^{-l^{2}/(2\sigma^{2})}\sum_{j\in\mathbb{Z}}\int_{j-r }^{j+r}e^{-2\pi^{2}\sigma^{2}(u+il/(2\pi\sigma^{2}))^{2}}\,\mathrm{d}u\\ &=:d(\sigma)\sum_{j\in\mathbb{Z}}\mathcal{I}_{j,l}.\end{split} \tag{4.32}\]

Fix one \(j\in\mathbb{Z}\) and one \(l\in k^{\prime}-B_{N}\). We consider the contour integration of the holomorphic function \(e^{-l^{2}/(2\sigma^{2})}e^{-2\pi^{2}\sigma^{2}z^{2}}\) over a rectangle consisting of the following four lines on the complex plane:

\[\begin{split}\text{vertical:}\quad\{(j+r,y):0\leq y\leq l/(2\pi \sigma^{2})\},&\quad\{(j-r,y):0\leq y\leq l/(2\pi\sigma^{2})\}\\ \text{horizontal:}\quad\{(x,0):j-r\leq x\leq j+r\},& \quad\{(x,l/(2\pi\sigma^{2})):j-r\leq x\leq j+r\}.\end{split} \tag{4.33}\]

Cauchy's integral theorem [55, Theorem 2.2] then gives that

\[\begin{split} 0=&-\mathcal{I}_{j,l}+e^{-l^{2}/(2 \sigma^{2})}\int_{j-r}^{j+r}e^{-2\pi^{2}\sigma^{2}(x+i(l/(2\pi\sigma^{2})-1/( 2\pi\sigma^{2})))^{2}}\,\mathrm{d}x\\ &+e^{-l^{2}/(2\sigma^{2})}\bigg{(}\int_{l/(2\pi\sigma^{2})}^{0}e ^{-2\pi^{2}\sigma^{2}(j-r+iy)^{2}}\,i\mathrm{d}y+\int_{0}^{l/(2\pi\sigma^{2})} e^{-2\pi^{2}\sigma^{2}(j+r+iy)^{2}}\,i\mathrm{d}y\bigg{)}.\end{split} \tag{4.34}\]

The contribution of the first vertical line in (4.33) is

\[\begin{split} e^{-l^{2}/(2\sigma^{2})}\bigg{|}\int_{0}^{l/(2\pi \sigma^{2})}e^{-2\pi^{2}\sigma^{2}(j+r+iy)^{2}}\,i\mathrm{d}y\bigg{|}\leq& \frac{e^{-2\pi^{2}\sigma^{2}(j+r)^{2}}}{\sqrt{2}\pi\sigma}\int_{0}^{l/(\sqrt{ 2}\sigma)}e^{y^{2}-l^{2}/(2\sigma^{2})}\,\mathrm{d}y\\ &=\frac{e^{-2\pi^{2}\sigma^{2}(j+r)^{2}}}{\sqrt{2}\pi\sigma}\int_{ 0}^{l/(\sqrt{2}\sigma)}e^{(y-l/(\sqrt{2}\sigma))(y+l/(\sqrt{2}\sigma))}\, \mathrm{d}y.\end{split} \tag{4.35}\]

We note that the second and third integrals appearing above take the form \(e^{-a^{2}}\int_{0}^{a}e^{-u^{2}}\,\mathrm{d}u\), which is a _Dawson's integral_[12]. To handle it, we make a convenient change of variables as follows. Let \(u\geq 0\) be such that \(-u=y-l/(\sqrt{2}\sigma)\). Then since \(0\leq y\leq l/(\sqrt{2}\sigma)\),

\[-\frac{2l}{\sqrt{2}\sigma}u\leq y^{2}-\frac{l^{2}}{2\sigma^{2}}=-u(y+\frac{l}{ \sqrt{2}\sigma})\leq-\frac{l}{\sqrt{2}\sigma}u.\]
Putting this back into (4.35) gives us

\[e^{-l^{2}/(2\sigma^{2})}\bigg{|}\int_{0}^{l/(2\pi\sigma^{2})}e^{-2 \pi^{2}\sigma^{2}(j+r+iy)^{2}}\,i\mathrm{d}y\bigg{|} \leq\frac{e^{-2\pi^{2}\sigma^{2}(j+r)^{2}}}{\sqrt{2}\pi\sigma}\int _{0}^{l/(\sqrt{2}\sigma)}e^{-ul/(\sqrt{2}\sigma)}\,\mathrm{d}u\] \[\leq\frac{e^{-2\pi^{2}\sigma^{2}(j+r)^{2}}}{l\pi}\int_{0}^{l^{2}/ (2\sigma^{2})}e^{-u}\,\mathrm{d}u\] \[=:\frac{e^{-2\pi^{2}\sigma^{2}(j+r)^{2}}\mathcal{J}_{l}}{l\pi},\]

where, \(\mathcal{J}_{l}\to 1\) as \(l\to\infty\). By the Poisson summation formula (4.17) again,

\[\sum_{l\in k^{\prime}-B_{N}}\frac{\mathcal{J}_{l}}{l\pi}\sum_{j\in\mathbb{Z}} d(\sigma)e^{-2\pi^{2}\sigma^{2}(j+r)^{2}}=\sum_{l\in k+2l^{\prime}N-B_{N}} \frac{\mathcal{G}_{\sigma}(r)\mathcal{J}_{l}}{l\pi}.\]

We square-sum the final term above over \(l^{\prime}\in\mathbb{N}\), acquiring for any \(k\in B_{\mathfrak{m}}\)

\[\sum_{l^{\prime}\in\mathbb{N}}\bigg{|}\sum_{l=k+(2l^{\prime}-1)N+ 1}^{k+(2l^{\prime}+1)N}\frac{\mathcal{G}_{\sigma}(r)\mathcal{J}_{l}}{l\pi} \bigg{|}^{2} \leq\frac{2N\mathcal{G}_{\sigma}(r)^{2}}{\pi^{2}}\sum_{l^{\prime} \in\mathbb{N}}\sum_{l=k+(2l^{\prime}-1)N+1}^{k+(2l^{\prime}+1)N}\frac{1}{l^{2}} \tag{4.36}\] \[=\frac{2N\mathcal{G}_{\sigma}(r)^{2}}{\pi^{2}}\sum_{l=k+N+1}^{ \infty}\frac{1}{l^{2}}\] \[\leq\frac{2N\mathcal{G}_{\sigma}(r)^{2}}{\pi^{2}}\int_{k+N}^{ \infty}\frac{1}{l^{2}}\] \[\leq\frac{2N\mathcal{G}_{\sigma}(r)^{2}}{\pi^{2}(N-\mathfrak{m})}.\]

Employing the same method for the contribution of the second vertical line in (4.33), and keeping in mind that \(\mathcal{G}_{\sigma}(r)=\mathcal{G}_{\sigma}(-r)\), we also arrive at an analogous bound. On the other hand, consideration of the bottom horizontal integral in (4.34) leads to:

\[e^{-l^{2}/(2\sigma^{2})}d(\sigma)\sum_{j\in\mathbb{Z}}\int_{j-r}^{j+r}e^{-2 \pi^{2}\sigma^{2}x^{2}}\,\mathrm{d}x=e^{-l^{2}/(2\sigma^{2})}\int_{-r}^{r} \mathcal{G}_{\sigma}(x)\,\mathrm{d}x\leq\frac{2e^{-l^{2}/(2\sigma^{2})}}{(N- \mathfrak{m})^{\alpha}}.\]

Similarly as before, since \(l\in k^{\prime}-B_{N}\), where \(k^{\prime}=k+2l^{\prime}N\), \(k\in B_{\mathfrak{m}}\) and \(l^{\prime}\in\mathbb{N}\), summing over \(l^{\prime}\in\mathbb{N}\) for an arbitrary \(k\in B_{\mathfrak{m}}\) results in

\[\sum_{l^{\prime}=1}^{\infty}\quad\sum_{l\in k+2l^{\prime}N-B_{N} }e^{-l^{2}/(2\sigma^{2})}=\sum_{l=k+N+1}^{\infty}e^{-l^{2}/(2\sigma^{2})} \leq\int_{N+k}^{\infty}e^{-x^{2}/(2\sigma^{2})}\,\mathrm{d}x\] \[\leq\frac{C\sigma^{2}e^{-(N+k)^{2}/(2\sigma^{2})}}{N+k}\] \[\leq\frac{C\sigma^{2}e^{-(N-\mathfrak{m})^{2}/(2\sigma^{2})}}{N- \mathfrak{m}},\]
where Mills' ratio (4.2) has entered at the second to last inequality. Then an application of the embedding of the \(\ell^{p}\) spaces leads to

\[\begin{split}\frac{1}{(N-\mathfrak{m})^{\alpha}}\bigg{(}\sum_{l^{ \prime}=1}^{\infty}\bigg{|}\sum_{l\in k+2l^{\prime}N-B_{N}}e^{-l^{2}/(2\sigma^{ 2})}\bigg{|}^{2}\bigg{)}^{1/2}&\leq\frac{1}{(N-\mathfrak{m})^{ \alpha}}\sum_{l=k+N+1}^{\infty}e^{-l^{2}/(2\sigma^{2})}\\ &\leq\frac{C\sigma^{2}e^{-(N-\mathfrak{m})^{2}/(2\sigma^{2})}}{(N -\mathfrak{m})^{\alpha+1}}.\end{split} \tag{4.37}\]

Therefore, by combining (4.31), (4.32), (4.34) (4.36), (4.37), along with (4.28), we obtain

\[\begin{split}\bigg{(}\sum_{l^{\prime}\in\mathbb{N}}|\mu_{r, \sigma}(k+2l^{\prime}N)|^{2}\bigg{)}^{1/2}&\leq\frac{C\sigma^{2 }e^{-(N-\mathfrak{m})^{2}/(2\sigma^{2})}}{(N-\mathfrak{m})^{\alpha+1}}+C \mathcal{G}_{\sigma}(r)\\ &\leq C(N-\mathfrak{m})^{2\beta-\alpha-1}e^{-3\pi^{2}(N- \mathfrak{m})^{2(1-\beta)}}+C(N-\mathfrak{m})^{\beta}e^{-3\pi^{2}(N-\mathfrak{ m})^{2(\beta-\alpha)}}\\ &=\widetilde{\mathcal{E}}_{2}(N,\mathfrak{m},\alpha,\beta),\end{split}\]

from which and the symmetry mentioned at the start of the proof, (4.30) follows. 

Proof of Theorem 3.1.: The proof is a combination of the observation made in (4.22), the proof of Lemma 4.2 and Propositions 4.1, 4.2. 

## 5 Proof of Theorem 3.2

We begin by reminding the reader of some important points that will be useful for this section. Firstly, let \(f\in\mathcal{B}_{\mathfrak{m}}\) and assume that \(N>\mathfrak{m}\). We have asserted that

\[\mathcal{R}_{r,\sigma}f(x)=\sum_{j=0}^{2N-1}f(j/2N)(s_{N}\,\mathcal{G}_{r, \sigma})(x-j/2N)\approx f(x), \tag{5.1}\]

in the \(L^{2}\) norm on \([0,1]\), with precise error bounds provided in Theorem 3.1. Importantly, we require in \(\mathcal{G}_{r,\sigma}\),

\[\sigma=\frac{(N-\mathfrak{m})^{\beta}}{\sqrt{6}\pi}\quad\text{ and }\quad r=\frac{3\pi}{(N-\mathfrak{m})^{\alpha}},\]

where \(0<\alpha<\beta<1\). To facilitate convenience in future calculations, we now identify \(s_{N}\), \(\mathcal{G}_{r,\sigma}\) with their 1-periodic counterparts, respectively. Then \(s_{N}\in C^{\infty}(\mathbb{R})\), and for every \(j\in\mathbb{N}\), \(\mathcal{G}_{r,\sigma}^{(j)}=d^{j}\mathcal{G}_{r,\sigma}/dx^{j}\) exists almost everywhere. Recall that we have defined in (3.8)

\[\mathcal{G}_{r,\sigma}^{(j)}(x)=\begin{cases}\mathcal{G}_{\sigma}^{(j)}(x),& \exists k\in\mathbb{Z}\text{ s.t. }k-r\leq x\leq k+r\\ 0,&\text{otherwise.}\end{cases} \tag{5.2}\]

This extension allows us to interpret the argument addition in

\[\sum_{j=0}^{2N-1}f(j/2N)(s_{N}\,\mathcal{G}_{r,\sigma})(x-j/2N),\]
as taking place on \(\mathbb{R}\).

Secondly, we have established in SS2.5 that the output of our WNN will take the form

\[\sum_{j=0}^{2N-1}f(j/2N)T_{\mathcal{K}}ReLU(x-j/2N),\quad\forall x\in[0,1]. \tag{5.3}\]

Therefore, by juxtaposing (5.1) and (5.3), it becomes evident that we would complete most of the proof if we can demonstrate that:

\[T_{\mathcal{K}}ReLU(x-j/2N)=(s_{N}\,\mathcal{G}_{r,\sigma})(x-j/2N)+\mathcal{ E}, \tag{5.4}\]

for a small \(\mathcal{E}\) error term and \(x\) in an appropriately large subset of \([0,1]\). If \(\mathcal{E}\) can be bounded and shown to vanish as \(N\to\infty\), then the overall, accumulated, discrepancy between the network output and \(\mathcal{R}_{r,\sigma}f\) can be made small uniformly for \(x\) in the same subset. The proof is then completed by recalling (5.1).

We proceed as planned with the task of bounding the error in (5.4) with the following proposition.

**Proposition 5.1**.: _Let \(\mathfrak{m}\in\mathbb{N}\) and \(\varepsilon>0\). Suppose \(W\) satisfies Assumption 2.1 and \(N>\mathfrak{m}\) is large enough so that_

\[r=\frac{3\pi}{(N-\mathfrak{m})^{\alpha}}\leq\kappa \tag{5.5}\]

_where \(\kappa\) is as in (2.24). Fix \(x\in[r,1-r]\) and \(j=0,\cdots,2N-1\). If \(x-j/2N\in[-r,r)\), then there exists \(C>0\) such that the following holds_

\[|T_{\mathcal{K}}ReLU(x-j/2N)-(s_{N}\,\mathcal{G}_{r,\sigma})(x-j/2 N)|\\ \leq C\eta^{-1}\bigg{(}KNr^{2}+(N-\mathfrak{m})^{\beta}e^{-(N- \mathfrak{m})^{2\beta}/24}\bigg{)}. \tag{5.6}\]

The proof of Proposition 5.1 requires the knowledge of two auxiliary lemmas below. One is an integration-by-parts result, and the other gives estimates of \(s_{N}\,\mathcal{G}_{r,\sigma}\) that are not only essential for the present section but also for all others. Their proofs are given in SS5.1 and SS5.2, respectively.

**Lemma 5.1**.: _Fix \(r\in(0,1)\), \(x\in[r,1-r]\) and \(j=0,\cdots,2N-1\). Suppose \(x-j/2N\in[-r,r)\). Then_

\[(s_{N}\,\mathcal{G}_{r,\sigma})(x-j/2N)=(x+r-j/2N)(s_{N}\, \mathcal{G}_{r,\sigma})^{\prime}(-r)+(s_{N}\,\mathcal{G}_{r,\sigma})(-r)\\ +\int_{x-r}^{x+r}ReLU(y-j/2N)(d^{2}/dy^{2})(s_{N}\,\mathcal{G}_{r,\sigma})(x-y)\,\mathrm{d}y. \tag{5.7}\]

**Lemma 5.2**.: _Given a pair of \(r,\sigma\) as in (3.3), with \(0<\alpha<\beta<1\). There exists \(C>0\) such that for all \(N>\mathfrak{m}\) we have_
1. \(|(s_{N}\,\mathcal{G}_{r,\sigma})^{\prime}(r)|\leq C(N-\mathfrak{m})^{\beta}e^{-(N -\mathfrak{m})^{2\beta}/24}\)_,_
2. \(\|(s_{N}\,\mathcal{G}_{r,\sigma})^{\prime}\|_{L^{\infty}([0,1])}\leq CN\)__
3. \(\|(s_{N}\,\mathcal{G}_{r,\sigma})^{\prime\prime}\|_{L^{\infty}([0,1])}\leq C \max\{N^{2},N^{3\beta}\}\)_,_
4. \(\|(s_{N}\,\mathcal{G}_{r,\sigma})^{\prime\prime\prime}\|_{L^{\infty}([0,1])} \leq CN\max\{N^{2},N^{3\beta}\}\)_._

Equipped with these lemmas, we now delve into the proof of Proposition 5.1.

Proof of Proposition 5.1.: We introduce abbreviations that will be used in this proof as well as in the proofs of Theorems 3.3, 3.4 to enhance a compact presentation. Set

\[\mathcal{G}^{*}(x,y):=\frac{\mathrm{d}^{2}}{\mathrm{d}y^{2}}(s_{N}\,\mathcal{ G}_{r,\sigma})(x-y)\]

and

\[\rho_{j}(x):=ReLU(x-j/2N)=ReLU_{j/2N}(x)\]

for each for \(j=0,\cdots,2N-1\). Begin by noting that if \(x\in[r,1-r]\), then from definition (3.7), \(\mathfrak{I}_{x}=[-r+x,x+r]\). Now if \(x-j/2N\in[-r,r)\), then from Lemma 5.1

\[(s_{N}\,\mathcal{G}_{r,\sigma})(x-j/2N) =\int_{x-r}^{x+r}\rho_{j}(y)\mathcal{G}^{*}(x,y)\,\mathrm{d}y \tag{5.8}\] \[\quad+(x+r-j/2N)(s_{N}\,\mathcal{G}_{r,\sigma})^{\prime}(-r)+(s_{ N}\,\mathcal{G}_{r,\sigma})(-r).\]

I.e.,

\[\int_{\mathfrak{I}_{x}}\rho_{j}(y)\mathcal{G}^{*}(x,y)\,\mathrm{d}y=(s_{N}\, \mathcal{G}_{r,\sigma})(x-j/2N)+\mathcal{E}_{1}, \tag{5.9}\]

and

\[\mathcal{E}_{1}:=-(x+r-j/2N)(s_{N}\,\mathcal{G}_{r,\sigma})^{\prime}(-r)-(s_{ N}\,\mathcal{G}_{r,\sigma})(-r).\]

From Lemma 5.2 and (4.28), we obtain

\[|\mathcal{E}_{1}|\leq C(N-\mathfrak{m})^{\beta}e^{-(N-\mathfrak{m})^{2\beta} /24}. \tag{5.10}\]

Next, we compare \(T_{\mathcal{K}}ReLU(x-j/2N)=T_{\mathcal{K}}\rho_{j}(x)\) with \(\int_{\mathfrak{I}_{x}}\rho_{j}(y)\mathcal{G}^{*}(x,y)\,\mathrm{d}y\). Due to (5.5), \(\{(x,y):y\in\mathfrak{I}_{x}\}\subset\mathcal{D}_{\kappa}\). Therefore, it follows from Assumption 2.1 on \(W\) that \(\mathcal{W}_{x}\geq\eta\) and

\[\begin{split}|\mathcal{W}_{x}-W(x,y)|&=\left|\frac{ 1}{|\mathfrak{I}_{x}|}\int_{\mathfrak{I}_{x}}(W(x,u)-W(x,y))\,\mathrm{d}u \right|\\ &\leq\frac{1}{|\mathfrak{I}_{x}|}\int_{\mathfrak{I}_{x}}|W(x,u)-W( x,y)|\,\mathrm{d}u\\ &\leq 2Kr\end{split} \tag{5.11}\]
for almost every \(y\in\mathscr{I}_{x}\). Moreover, by the Lipschitz continuity assumption, \((\mathrm{d}/\mathrm{d}y)W(x,y)\) exists almost everywhere on \(I_{x}\) (Radamacher's theorem) [18, SS5.8.3, Theorem 5] and that

\[\bigg{|}\frac{\mathrm{d}}{\mathrm{d}y}W(x,y)\bigg{|}\leq K; \tag{5.12}\]

therefore

\[\begin{split}&\int_{\mathscr{I}_{x}}\rho_{j}(y)\mathcal{G}^{*}(x,y) \bigg{(}W(x,y)-\mathcal{W}_{x}\bigg{)}\,\mathrm{d}y=\int_{j/2N}^{x+r}\rho_{j}(y )\mathcal{G}^{*}(x,y)\bigg{(}W(x,y)-\mathcal{W}_{x}\bigg{)}\,\mathrm{d}y\\ &=-\int_{j/2N}^{x+r}(\mathrm{d}/\mathrm{d}y)(s_{N}\,\mathcal{G}_ {r,\sigma})(x-y)\bigg{\{}\rho_{j}(y)(\mathrm{d}/\mathrm{d}y)W(x,y)+W(x,y)- \mathcal{W}_{x}\bigg{\}}\,\mathrm{d}y+\mathcal{E}_{2}.\end{split} \tag{5.13}\]

Here

\[\mathcal{E}_{2}:=(\mathrm{d}/\mathrm{d}y)(s_{N}\,\mathcal{G}_{r,\sigma})(x-y) \rho_{j}(y)\bigg{(}W(x,y)-\mathcal{W}_{x}\bigg{)}\bigg{|}_{y=j/2N}^{y=x+r}\]

and so as a result of Lemma 5.2 again

\[|\mathcal{E}_{2}|\leq C(N-\mathfrak{m})^{\beta}e^{-(N-\mathfrak{m})^{2\beta}/ 24}. \tag{5.14}\]

Going back to the third integral in (5.13), we see that

\[\begin{split}&\bigg{|}\int_{j/2N}^{x+r}(\mathrm{d}/\mathrm{d}y)(s_{N }\,\mathcal{G}_{r,\sigma})(x-y)\bigg{\{}\rho_{j}(y)(\mathrm{d}/\mathrm{d}y)W(x,y)+W(x,y)-\mathcal{W}_{x}\bigg{\}}\,\mathrm{d}y\bigg{|}\\ &\leq CN\bigg{(}K\int_{0}^{2r}y\,\mathrm{d}y+Kr^{2}\bigg{)}\leq CK Nr ^{2}\end{split} \tag{5.15}\]

where the first bound comes from the definition of \(\rho_{j}=ReLU_{j/2N}\) for \(j/2N\in[x-r,x+r)\), Lemma 5.2, (5.11) and (5.12). Then, by synthesizing the findings of (5.12), (5.13), (5.14), (5.15), we acquire

\[\begin{split}\bigg{|}T_{\mathcal{K}}\rho_{j}(x)-\int_{\mathscr{I }_{x}}\rho_{j}(y)\mathcal{G}^{*}(x,y)\,\mathrm{d}y\bigg{|}&=\frac {1}{\mathcal{W}_{x}}\bigg{|}\int_{\mathscr{I}_{x}}\rho_{j}(y)\mathcal{G}^{*}(x, y)\bigg{(}W(x,y)-\mathcal{W}_{x}\bigg{)}\,\mathrm{d}y\bigg{|}\\ &\leq C\eta^{-1}\bigg{(}KNr^{2}+(N-\mathfrak{m})^{\beta}e^{-(N- \mathfrak{m})^{2\beta}/24}\bigg{)}.\end{split} \tag{5.16}\]

As the final step, we combine (5.9), (5.10), (5.16) and arrive at the inequality (5.6), proving the proposition. 

Having now successfully established the proof of Proposition 5.1, we proceed to the proof of Theorem 3.2.

Proof of Theorem 3.2.: Without loss of generality, we may assume \(\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}=1\). From Lemma 2.1 we further have

\[\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}^{2}=\sum_{j=0}^{2N-1}|f(j/2N)|^{2}=1. \tag{5.17}\]
At the outset, we will make a temporary assumption that (5.5) holds. Fix \(x\in[r,1-r]\) and suppose that

\[x-j/2N\neq r,\quad\forall j=0,\cdots,2N-1. \tag{5.18}\]

Note that there are only at most \(\lceil rN\rceil\) indices \(j\) such that \(x-j/2N\in[-r,r)\). Define

\[f_{\sharp}(y):=\sum_{j=0}^{2N-1}f(j/2N)\rho_{j}(y),\quad\forall y\in[0,1]. \tag{5.19}\]

Then \(T_{\mathcal{K}}f_{\sharp}(x)=\sum_{j=0}^{2N-1}f(j/2N)T_{\mathcal{K}}\rho_{j}( x)=\Psi_{f}(x)\) (see SS2.5). On the other hand, recall the regularized sampling series

\[\mathcal{R}_{r,\sigma}f(x)=\sum_{j=0}^{2N-1}f(j/2N)(s_{N}\,\mathcal{G}_{r, \sigma})(x-j/2N).\]

Therefore, as a direct consequence of (5.17), Proposition 5.1 and the \(L^{p}\)-embedding property for finite measure spaces,

\[|\Psi_{f}(x)-\mathcal{R}_{r,\sigma}f(x)| =|T_{\mathcal{K}}f_{\sharp}(x)-\mathcal{R}_{r,\sigma}f(x)|\] \[\leq C\eta^{-1}r^{1/2}N^{1/2}\bigg{(}KNr^{2}+(N-\mathfrak{m})^{ \beta}e^{-(N-\mathfrak{m})^{2\beta}/24}\bigg{)}.\]

Combining this and the result of Theorem 3.1 - and ignoring all the exponential error parts - we obtain

\[\|\Psi_{f}-f\|_{L^{2}([r,1-r];\mathbb{C}^{m})}\leq C\eta^{-1}KN^{3/2-\alpha 5 /2}. \tag{5.20}\]

We now set

\[3/2-\alpha 5/2=0.9\quad\text{ and }\quad\beta-\alpha=0.02, \tag{5.21}\]

hence, \(\alpha=0.96\), \(\beta=0.98\). Set

\[N=\lceil\varepsilon^{-10/9}\rceil;\]

then it follows from (5.20), (5.21) that

\[\|\Psi_{f}-f\|_{L^{2}([r,1-r];\mathbb{C}^{m})}\leq C\eta^{-1}K\varepsilon\]

for every \(x\in[r,1-r]\) that satisfies (5.18). We now note that (5.5) can be guaranteed by taking

\[\frac{3\pi}{\kappa}\leq\varepsilon^{-1},\]

which can be accomplished by taking \(\varepsilon\in(0,1)\) to be sufficiently small. The proof is now concluded.
**Remark 5.1**.: It should be noted that the choices made for \(r,\sigma\) in (3.3) are made specifically to ensure that, when \(\alpha=0.96\), \(\beta=0.98\), all exponential error terms that should appear in (5.20) are dominated by the rational term on its right-hand side even for small \((N-\mathfrak{m})\). In general, for given \(0<\alpha<\beta<1\), one can find \(c_{1}(\alpha,\beta),c_{2}(\alpha,\beta)>0\) such that, if

\[r=\frac{c_{1}(\alpha,\beta)}{(N-\mathfrak{m})^{\alpha}}\quad\text{ and }\quad \sigma=\frac{(N-\mathfrak{m})^{\beta}}{c_{2}(\alpha,\beta)},\]

then a similar effect of keeping the exponential terms small, as observed in (5.20), is achieved.

**Remark 5.2**.: It is important to note that the favorable subgeometric sampling convergence rate established Theorem 3.1 has been forfeited in the proof of Theorem 3.2 due to the implementation of the integration by parts given in Lemma 5.1. Let us suppose for a moment that \(W\) is constant over the diagonal neighborhood \(\mathcal{D}_{\kappa}\), in which case, a diligent study of the proof presented would lead to the conclusion that

\[\|\Psi_{f}-f\|_{L^{2}([r,1-r];\mathbb{C}^{m})}=\mathcal{O}(e^{-CN^{2(\beta- \alpha)}}),\]

and it would have been enough to select \(N=C\lceil(\log(1/\varepsilon))^{1/(2(\beta-\alpha))}\rceil\).

### Proof of Lemma 5.1

The lemma is a direct consequence of the following known result which we provide for the reader.

**Theorem 5.1**.: _(Abel's identity) [3, Theorem 4.2] Let \(\{a_{n}\}_{n\geq 0}\) be a real-valued sequence. Define, for \(t\geq 0\)_

\[A(t):=\sum_{n\leq t}a_{n}, \tag{5.22}\]

_and \(A(t)=0\) if \(t<0\). Then for every \(g\in C^{1}[u,v]\), one has,_

\[\sum_{u<n\leq v}a_{n}g(n)=A(v)g(v)-A(u)g(u)-\int_{u}^{v}A(y)g^{\prime}(y)\, \mathrm{d}y. \tag{5.23}\]

To apply Theorem 5.1, we define \(\{a_{n}\}_{n\geq 0}\) be such that \(a_{0}=1\) and \(a_{n}=0\) if \(n\neq 0\). Let \(A\) be as in (5.22), so

\[A(t)=\chi_{\{t\geq 0\}}(t). \tag{5.24}\]

For \(x\) and \(j\) as stated in the lemma, we define

\[\tilde{\mathcal{G}}(y):=(s_{N}\,\mathcal{G}_{r,\sigma})(x-j/2N-y).\]
Observe that \(\tilde{\mathcal{G}}\in C^{1}([x-r-j/2N,x+r-j/2N])\). Therefore it follows from (5.23) and (5.24) that

\[\sum_{x-r-j/2N<n\leq x+r-j/2N}a_{n}\tilde{\mathcal{G}}(n) =A(x+r-j/2N)\tilde{\mathcal{G}}(x+r-j/2N)-\int_{0}^{x+r-j/2N}( \mathrm{d}/\mathrm{d}y)\tilde{\mathcal{G}}(y)\,\mathrm{d}y\] \[\Rightarrow(s_{N}\,\mathcal{G}_{r,\sigma})(x-j/2N) =(s_{N}\,\mathcal{G}_{r,\sigma})(-r)+\int_{-r}^{x-j/2N}(\mathrm{ d}/\mathrm{d}y)(s_{N}\,\mathcal{G}_{r,\sigma})(y)\,\mathrm{d}y. \tag{5.25}\]

On the other hand,

\[\int_{x-r}^{x+r}ReLU(y-j/2N)(d^{2}/dy^{2})(s_{N}\,\mathcal{G}_{r, \sigma})(x-y)\,\mathrm{d}y\] \[\qquad=\int_{-r}^{x-j/2N}(x-y-j/2N)(d^{2}/dy^{2})(s_{N}\, \mathcal{G}_{r,\sigma})(y)\,\mathrm{d}y\] \[\qquad=-(x+r-j/2N)(s_{N}\,\mathcal{G}_{r,\sigma})^{\prime}(-r)+ \int_{-r}^{x-j/2N}(\mathrm{d}/\mathrm{d}y)(s_{N}\,\mathcal{G}_{r,\sigma})(y) \,\mathrm{d}y, \tag{5.26}\]

and so combining (5.25) and (5.26) yields

\[\int_{x-r}^{x+r}ReLU(y-j/2N)(d^{2}/dy^{2})(s_{N}\,\mathcal{G}_{r, \sigma})(x-y)\,\mathrm{d}y\\ =-(x+r-j/2N)(s_{N}\,\mathcal{G}_{r,\sigma})^{\prime}(-r)-s_{N}\, \mathcal{G}_{r,\sigma}(-r)+(s_{N}\,\mathcal{G}_{r,\sigma})(x-j/2N),\]

which is what we want. 

### Proof of Lemma 5.2

For \(k=1,2,3\) we have, from (5.2), that

\[(s_{N}\,\mathcal{G}_{r,\sigma})^{(k)}(x)=\sum_{l=0}^{k}\binom{k}{l}(s^{(l)}\, \mathcal{G}_{\sigma}^{(k-l)})(x),\quad\forall x\in[-r,r]. \tag{5.27}\]

We first prove (a), so we take \(k=1\). We utilize the Poisson formulation (4.17), which states

\[\mathcal{G}_{\sigma}(x)=\sum_{l\in\mathbb{Z}}\mathfrak{g}(x+l),\quad\forall x \in[0,1].\]

where \(\mathfrak{g}(x)=d(\sigma)e^{-2x^{2}\pi^{2}\sigma^{2}}\) on \(\mathbb{R}\) and \(d(\sigma)=\sigma c(\sigma)\sqrt{2\pi}\). Therefore,

\[\mathcal{G}_{\sigma}^{\prime}(r)=\sum_{l\in\mathbb{Z}}\mathfrak{g}^{\prime}(r +l)=-4\pi^{2}\sigma^{2}d(\sigma)\sum_{l\in\mathbb{Z}}(r+l)e^{-2(r+l)^{2}\pi^{2} \sigma^{2}}.\]
Since \(r\in(0,1/2)\), simple dominations and an application of Mills' ratio yield

\[\begin{split}|\mathcal{G}^{\prime}_{\sigma}(r)|&\leq C \sigma^{2}d(\sigma)\bigg{(}e^{-2\pi^{2}\sigma^{2}(1-r)^{2}}+\int_{1-r}^{\infty} e^{-\pi^{2}y^{2}\sigma^{2}}\,\mathrm{d}y\bigg{)}\\ &\leq C\sigma^{3}e^{-2\pi^{2}\sigma^{2}(1-r)^{2}}+C\sigma e^{- \pi^{2}\sigma^{2}(1-r)^{2}}\\ &\leq C(N-\mathfrak{m})^{\beta}e^{-(N-\mathfrak{m})^{2\beta}/24}. \end{split} \tag{5.28}\]

Now, it's evident that

\[\|s^{\prime}\|_{L^{\infty}([0,1])}\leq CN,\quad\|s^{\prime\prime}\|_{L^{\infty }([0,1])}\leq CN^{2},\quad\|s^{\prime\prime\prime}\|_{L^{\infty},([0,1])}\leq CN ^{3}, \tag{5.29}\]

and that

\[|\mathcal{G}_{\sigma}(r)|\leq C(N-\mathfrak{m})^{\beta}e^{-3\pi^{2}(N- \mathfrak{m})^{2(\beta-\alpha)}} \tag{5.30}\]

was demonstrated in (4.28). Thus, combining (5.27), (5.28), (5.29), (5.30) with that \(|\mathcal{G}_{\sigma}(r)|=|\mathcal{G}_{r,\sigma}(r)|\), \(|\mathcal{G}^{\prime}_{\sigma}(r)|=|\mathcal{G}^{\prime}_{r,\sigma}(r)|\), we have the proof of statement (a).

We will now prove statements (b), (c), (d) simultaneously. If \(x\in[-r,r]\), then similar to the calculation done in (5.28), we can obtain

\[|\mathcal{G}^{\prime}_{r,\sigma}(x)|=|\mathcal{G}^{\prime}_{\sigma}(x)|\leq C (N-\mathfrak{m})^{\beta}e^{-(N-\mathfrak{m})^{2\beta}/24}, \tag{5.31}\]

which is of order \(\mathcal{O}(1)\) whenever \(N\) is sufficiently large. Moreover, by definition (4.15)

\[\mathcal{G}^{(k)}_{r,\sigma}(x)=\mathcal{G}^{(k)}_{\sigma}(x)=(i2\pi)^{k}c( \sigma)\sum_{l\in\mathbb{Z}}l^{k}e^{-l^{2}\sigma^{-2}/2}e^{i2\pi lx}\]

for \(k=1,2,3\). Hence,

\[|\mathcal{G}^{(k)}_{r,\sigma}(x)|=|\mathcal{G}^{(k)}_{\sigma}(x)|\leq C \sigma^{k+1}\sum_{l\in\mathbb{N}}\bigg{(}\frac{l^{k}}{\sigma^{k}}e^{-l^{2} \sigma^{-2}/2}\bigg{)}\frac{1}{\sigma}\leq C\sigma^{k+1}\bigg{(}1+\int_{0}^{ \infty}x^{k}e^{-x^{2}}\,\mathrm{d}x\bigg{)}\]

which, together with (5.29), (5.31), yields (b), (c), (d), as desired. 

## 6 Proof of Theorem 3.3

We start out with some preparation. We continue to assume (5.5) holds with \(\alpha=0.96\). Let the graph \(G_{n}^{\mathrm{det}}\) and its graph signal \(f_{n}\) be as in the premise of Theorem 3.3. As illustrated by SS2.3, SS2.5, we can identify the graph signal \(f_{n}\) with a function on \(\mathcal{X}_{n}=\{x_{1},\cdots,x_{n}\}\), where

\[x_{k}=\frac{k-1}{n}\in[0,1].\]

Recall that \(f_{n}(x_{k})=f(x_{k})\), for every \(x_{k}\), and the following abbreviations set in the proof of Theorem 3.2:

\[\mathcal{G}^{*}(x,y)=\frac{\mathrm{d}^{2}}{\mathrm{d}y^{2}}(s_{N}\,\mathcal{G }_{r,\sigma})(x-y)\quad\text{ and }\quad\rho_{j}(x)=ReLU_{j/2N}(x).\]
Then, from SS2.5, the GNN instantiated by \(\Psi_{n,f}\) is expressed as

\[\Psi_{n,f}(x_{k})=\sum_{j=0}^{2N-1}f(j/2N)\mathfrak{F}(\rho_{j})(x_{k}).\]

Since \(f\in\mathcal{B}_{\mathfrak{m}}\), we infer from Theorem 3.2 that the WNN machinery described therein yields the following outcome

\[\Psi_{f}(x)=\sum_{j=0}^{2N-1}f(j/2N)T_{\mathcal{K}}\rho_{j}(x)\approx f(x)\]

in the \(L^{2}\) sense on the predictable zone \([r,1-r]\). Therefore, by establishing that

\[\mathfrak{F}(\rho_{j})(x)\approx T_{\mathcal{K}}(\rho_{j})(x) \tag{6.1}\]

in some appropriate sense, we would complete a substantial portion of our proof. However, as \(\mathfrak{F}(\rho_{j})\) is a graph signal and \(T_{\mathcal{K}}(\rho_{j})\) a graphon signal, to make sense of (6.1), we must extend the former to a graphon signal. We proceed with the necessary steps below.

We write our graph filter (see (2.26), (3.10)) as

\[\mathfrak{F}(g_{n})(x_{k}) =\frac{1}{n\mathcal{W}_{x_{k}}}\sum_{l=1}^{n}\mathcal{G}^{*}(x_{ k},x_{l})[\mathbf{A}_{n}]_{k,l}g_{n}(x_{l})\] \[=\frac{1}{n\mathcal{W}_{x_{k}}}\sum_{l\neq k,l=1}^{n}\mathcal{G}^ {*}(x_{k},x_{l})W(x_{k},x_{l})g_{n}(x_{l}),\]

for a graph signal \(g_{n}\). For each \(j=0,\cdots,N-1\), we define a step graphon signal

\[\overline{\mathfrak{F}(\rho_{j})}(x):=\sum_{k=1}^{n}\mathfrak{F}(\rho_{j})(x_ {k})\chi_{I_{k}}(x)\quad\forall x\in[0,1], \tag{6.2}\]

where, recall that \(I_{k}=[(k-1)/n,k/n)\). Note that, \(\overline{\mathfrak{F}(\rho_{j})}(x_{k^{\prime}})=\mathfrak{F}(\rho_{j})(x_{ k^{\prime}})\) for any \(k^{\prime}=1,\cdots,n\), and

\[\begin{split}\overline{\Psi}_{n,f}(x)&=\sum_{k=1}^{ n}\Psi_{n,f}(x_{k})\chi_{I_{k}}(x)=\sum_{k=1}^{n}\bigg{(}\sum_{j=0}^{2N-1}f(j/2N) \mathfrak{F}(\rho_{j})(x_{k})\bigg{)}\chi_{I_{k}}(x)\\ &=\sum_{j=0}^{2N-1}f(j/2N)\overline{\mathfrak{F}(\rho_{j})}(x) \end{split} \tag{6.3}\]

by definition (3.12). With that, we can now formalize (6.1) as follows.

**Lemma 6.1**.: _Let \(\alpha,\beta\) be as prescribed by Theorem 3.3. Then there exists \(C>0\) such that, for each \(k=1,\cdots,n\) and \(j=0,\cdots,2N-1\), we have_

\[|T_{\mathcal{K}}\rho_{j}(x_{k})-\overline{\mathfrak{F}(\rho_{j})}(x_{k})|\leq C \eta^{-1}(1+K)\bigg{(}\frac{N^{3\beta+1}}{n^{2}}+\frac{N^{3\beta-\alpha+1}}{n} \bigg{)}. \tag{6.4}\]
The proof of Lemma 6.1 is given in SS6.1, at the end of this section, so as for us to proceed with the proof of Theorem 3.3.

Proof of Theorem 3.3.: Without loss of generality, we assume \(\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}=1\). Recall the following function (5.19) from SS5:

\[f_{\sharp}(x)=\sum_{j=0}^{2N-1}f(j/2N)\rho_{j}(x),\quad\forall x\in[0,1].\]

As previously demonstrated, \(T_{\mathcal{K}}f_{\sharp}(x)=\sum_{j=0}^{2N-1}f(j/2N)T_{\mathcal{K}}\rho_{j}(x )=\Psi_{f}(x)\). Define

\[\overline{\mathfrak{F}(f_{\sharp})}(x):=\sum_{j=0}^{2N-1}f(j/2N)\overline{ \mathfrak{F}(\rho_{j})}(x),\quad\forall x\in[0,1]. \tag{6.5}\]

Then it's ready from (6.3) that \(\overline{\mathfrak{F}(f_{\sharp})}=\overline{\Psi}_{n,f}\) and \(\overline{\mathfrak{F}(f_{\sharp})}(x_{k})=\overline{\Psi}_{n,f}(x_{k})=\Psi _{n,f}(x_{k})\), for every \(k=1,\cdots,n\).

Let us examine the difference \(|T_{\mathcal{K}}f_{\sharp}(x_{k})-\overline{\mathfrak{F}(f_{\sharp})}(x_{k}) |=|\Psi_{f}(x_{k})-\Psi_{n,f}(x_{k})|\). By definition, \(T_{\mathcal{K}}\rho_{j}(x_{k})=0=\mathfrak{F}(\rho_{j})(x_{k})\) if \(|x_{k}-j/2N|>r\). Therefore,

\[\begin{split}|\Psi_{f}(x_{k})-\Psi_{n,f}(x_{k})|& =|T_{\mathcal{K}}f_{\sharp}(x_{k})-\overline{\mathfrak{F}(f_{\sharp})}(x_{k}) |\\ &\leq\sum_{j=0}^{2N-1}|f(j/2N)||T_{\mathcal{K}}\rho_{j}(x_{k})- \overline{\mathfrak{F}(\rho_{j})}(x_{k})|\\ &\leq C\eta^{-1}(1+K)N^{1/2-\alpha/2}\bigg{(}\frac{N^{3\beta+1}} {n^{2}}+\frac{N^{3\beta-\alpha+1}}{n}\bigg{)},\end{split} \tag{6.6}\]

where the last line follows from Lemmas 2.1 and 6.1 and from the fact that there are only \(\lceil rN\rceil\) indices \(j\) partaking in (6.6).

On the other hand, it can be readily assumed that

\[n>2N>N^{\alpha}. \tag{6.7}\]

Recall that \(\alpha=0.96\) and we have selected \(N\geq\lceil\varepsilon^{-10/9}\rceil\), this condition implies \(n\geq\varepsilon^{-1}\). It also follows that, if \(x\in[(k-1)/n,k/n)=I_{k}\) then \(x\in\mathfrak{I}_{x_{k}}\), and moreover, there can only be one \(j/2N\) in \((\mathfrak{J}_{x_{k}}\setminus\mathfrak{J}_{x})\cup(\mathfrak{J}_{x}\setminus \mathfrak{J}_{x_{k}})\). Let \(j=0,\cdots,2N-1\) be such that \(T_{\mathcal{K}}\rho_{j}(x_{k})\neq 0\) and \(T_{\mathcal{K}}\rho_{j}(x)\neq 0\), i.e., \(j/2N\in\mathfrak{I}_{x_{k}}\cap\mathfrak{I}_{x}\). Then for almost every \(x\in I_{k}\)

\[|T_{\mathcal{K}}\rho_{j}(x_{k})-T_{\mathcal{K}}\rho_{j}(x)| =\bigg{|}\int_{0}^{1}\bigg{(}\frac{\mathcal{G}^{*}(x_{k},y)W(x_{k },y)}{\mathcal{W}_{x_{k}}}-\frac{\mathcal{G}^{*}(x,y)W(x,y)}{\mathcal{W}_{x}} \bigg{)}\rho_{j}(y)\,\mathrm{d}y\bigg{|}\] \[=\bigg{|}\int_{\mathfrak{J}_{x_{k}}\cap\mathfrak{J}_{x}}\bigg{(} \frac{\mathcal{G}^{*}(x_{k},y)W(x_{k},y)}{\mathcal{W}_{x_{k}}}-\frac{ \mathcal{G}^{*}(x,y)W(x,y)}{\mathcal{W}_{x}}\bigg{)}\rho_{j}(y)\,\mathrm{d}y \bigg{|}\] \[\leq\frac{C\eta^{-2KN^{3\beta-\alpha}}}{n}+\frac{C\eta^{-1}N^{3 \beta-\alpha+1}}{n}+\frac{C\eta^{-1}KN^{3\beta-\alpha}}{n}, \tag{6.8}\]
since, by Assumption 2.1, \(|W(x_{k},y)-W(x,y)|\leq K/n\) for every \(y\in\mathfrak{I}_{x_{k}}\cap\mathfrak{I}_{x}\), and since

\[|\mathcal{G}^{*}(x_{k},y)-\mathcal{G}^{*}(x,y)|\leq\frac{CN^{3\beta+1}}{n},\]

by Lemma 5.2, and lastly, similar to what was done in (5.11)

\[\bigg{|}\frac{1}{\mathcal{W}_{x_{k}}}-\frac{1}{\mathcal{W}_{x_{k}}}\bigg{|} \leq\eta^{-2}\bigg{(}|\mathcal{W}_{x_{k}}-W(x_{k},x)|+|W(x_{k},x)-\mathcal{W}_ {x}|\bigg{)}\leq\frac{2K\eta^{-2}}{n}.\]

If \(j=0,\cdots,2N-1\) is such that \(T_{\mathcal{K}}\rho_{j}(x_{k})=0\) and \(T_{\mathcal{K}}\rho_{j}(x)\neq 0\) or \(T_{\mathcal{K}}\rho_{j}(x_{k})\neq 0\) and \(T_{\mathcal{K}}\rho_{j}(x)=0\), then \(j/2N\in[x_{k}+r,x+r]\cap[0,1]\) or \(j/2N\in[x_{k}-r,x-r]\cap[0,1]\), respectively. In either scenario, we obtain

\[|T_{\mathcal{K}}\rho_{j}(x_{k})-T_{\mathcal{K}}\rho_{j}(x)|\leq C\eta^{-1}N^{ 3\beta}\int_{0}^{1/n}y\,\mathrm{d}y\leq\frac{C\eta^{-1}N^{3\beta}}{n^{2}}. \tag{6.9}\]

With (6.6), (6.8), (6.9) at hand, we can now estimate \(|T_{\mathcal{K}}f_{\sharp}-\overline{\mathfrak{F}(f_{\sharp})}|=|\Psi_{f}- \overline{\Psi}_{n,f}|\) on \([r,1-r]\). Let \(x_{k^{*}}\) denote the first \(x_{k}\in[r,1-r]\). Then

\[[r,x_{k^{*}})\subset[x_{k^{*}-1},x_{k^{*}})=\mathfrak{I}_{x_{k^{*}-1}}\quad \text{ and }\quad[x_{k^{*}},1-r]\subset\bigcup_{x_{k}\in[r,1-r]}[x_{k},x_{k+1}).\]

Keeping this in mind, and combining (6.6), (6.8), (6.9), we deduce that for almost every \(x\in[(k-1)/n,k/n)\), where either \(x_{k}=x_{k^{*}-1}\) or \(x_{k}\in[r,1-r]\)

\[|T_{\mathcal{K}}f_{\sharp}(x)-\overline{\mathfrak{F}(f_{\sharp}) }(x)| \leq\sum_{j=0}^{2N-1}|f(j/2N)|\bigg{(}|T_{\mathcal{K}}\rho_{j}(x)- T_{\mathcal{K}}\rho_{j}(x_{k})|+|T_{\mathcal{K}}\rho_{j}(x_{k})-\overline{ \mathfrak{F}(\rho_{j})}(x_{k})|\bigg{)}\] \[\leq C\sum_{j=0}^{2N-1}|f(j/2N)|\bigg{(}\frac{\eta^{-2}(1+K)N^{3 \beta-\alpha+1}}{n}+\frac{\eta^{-1}N^{3\beta}}{n^{2}}\bigg{)}\] \[\leq C\eta^{-2}N^{1/2-\alpha/2}\bigg{(}\frac{(1+K)N^{3\beta-\alpha +1}}{n}+\frac{N^{3\beta}}{n^{2}}\bigg{)},\]

since, by the arguments presented above, there are at most \(\lceil rN\rceil+1\) indices \(j\) participating in the sum. Therefore,

\[\|T_{\mathcal{K}}f_{\sharp}-\overline{\mathfrak{F}(f_{\sharp})}\|_{L^{2}([r,1 -r];\mathbb{C}^{m})}\leq C\eta^{-2}N^{1/2-\alpha/2}\bigg{(}\frac{(1+K)N^{3 \beta-\alpha+1}}{n}+\frac{N^{3\beta}}{n^{2}}\bigg{)},\]

which together with Theorem 3.2, yields

\[\|\overline{\Psi}_{n,f}-f\|_{L^{2}([r,1-r];\mathbb{C}^{m})} \leq\|\overline{\mathfrak{F}(f_{\sharp})}-T_{\mathcal{K}}f_{\sharp }\|_{L^{2}([r,1-r];\mathbb{C}^{m})}+\|T_{\mathcal{K}}f_{\sharp}-f\|_{L^{2}([r,1 -r];\mathbb{C}^{m})} \tag{6.10}\] \[\leq C\eta^{-2}N^{1/2-\alpha/2}\bigg{(}\frac{(1+K)N^{3\beta-\alpha +1}}{n}+\frac{N^{3\beta}}{n^{2}}\bigg{)}+C\eta^{-1}K\varepsilon.\]
Since \(\beta=0.98\), we only need to impose

\[n\geq\frac{N^{3\beta-3\alpha/2+3/2}}{\varepsilon}\geq\varepsilon^{-13/3}. \tag{6.11}\]

Note that (6.11) implies (6.7). Putting (6.11) back in (6.10), we obtain

\[\|\overline{\Psi}_{n,f}-f\|_{L^{2}([r,1-r];\mathbb{C}^{m})}\leq C\eta^{-2}(1+K)\varepsilon\]

thereby concluding the proof. 

**Remark 6.1**.: A quick calculation shows that the smallest possible power of \(\varepsilon\) in (6.11) that could be achieved for \(n\) is \(4\). Indeed, let \(\Delta=\beta-\alpha\). Then \(3\beta-3\alpha/2+3/2=3\alpha/2+3\Delta+3/2\). Getting the power \(\delta\) in \(N^{-\delta}\sim\varepsilon\) as close to \(1\) as possible requires \(\alpha\) to be also close to \(1\), and \(\Delta\) close to \(0\), giving the smallest possible value of \((3\beta-3\alpha/2+3/2)/\delta\) to be \(3\).

### Proof of Lemma 6.1

Fix one \(x_{k}\), and let \(j=0,\cdots N-1\). Since \(|x_{k}-j/2N|>r\) implies \(T_{\mathcal{K}}\rho_{j}(x_{k})=0=\mathfrak{F}\rho_{j}(x_{k})\). Therefore, we only consider those \(j\) where \(|x_{k}-j/2N|\leq r\). Take one such \(j\). Write

\[T_{\mathcal{K}}\rho_{j}-\overline{\mathfrak{F}(\rho_{j})}=T_{\mathcal{K}} \rho_{j}-T_{\mathcal{K}}\overline{\rho}_{j}+T_{\mathcal{K}}\overline{\rho}_{ j}-\overline{\mathfrak{F}(\rho_{j})} \tag{6.12}\]

where

\[\overline{\rho}_{j}(x):=\sum_{l=1}^{n}\rho_{j}(x_{l})\chi_{I_{l}}(x),\quad \forall x\in[0,1].\]

The difference \(T_{\mathcal{K}}\rho_{j}-T_{\mathcal{K}}\overline{\rho}_{j}\) is straightforward to address. In fact, from Lemma 5.2 we can manage

\[\|T_{\mathcal{K}}(\rho_{j}-\overline{\rho}_{j})\|_{L^{\infty}([0,1])} \leq\eta^{-1}\|\mathcal{G}^{*}\|_{L^{\infty}([0,1])}\|\rho_{j}- \overline{\rho}_{j}\|_{L^{1}([0,1])} \tag{6.13}\] \[\leq\frac{C\eta^{-1}\max\{N^{2},N^{3\beta}\}}{n}\] \[\leq\frac{C\eta^{-1}N^{3\beta}}{n},\]

since \(\beta=0.98\). The second to last bound above is due to

\[\|\rho_{j}-\overline{\rho}_{j}\|_{L^{1}([0,1])}\leq\sum_{k=1}^{n}\frac{1}{n^{ 2}}=\frac{1}{n},\]

as the functions \(\rho_{j}\) are ReLU functions, the maximum difference \(|\rho_{j}(x)-\rho_{j}(x_{k})|\leq 1/n\) for every \(x\) belonging to the interval \(I_{k}\) of length \(1/n\).
The second difference \(T_{\mathcal{K}}\overline{\rho}_{j}-\overline{\mathfrak{F}}(\rho_{j})\) on the right-hand-side of (6.12) requires a more delicate treatment. Using the definition (6.2) introduced at the beginning of this section, we get

\[|T_{\mathcal{K}}\overline{\rho}_{j}(x_{k})-\overline{\mathfrak{F} (\rho_{j})}(x_{k})|\\ \leq\frac{1}{\mathcal{W}_{x_{k}}}\sum_{l=1}^{n}\bigg{|}\int_{(l-1 )/n}^{l/n}\{\mathcal{G}^{*}(x_{k},y)W(x_{k},y)-\mathcal{G}^{*}(x_{k},x_{l})[ \mathbf{A}_{n}]_{k,l}\}\rho_{j}(x_{l})\,\mathrm{d}y\bigg{|}. \tag{6.14}\]

Observe that at most \(\lceil 2rn\rceil\) indices \(l\) participate in the sum above; namely those that satisfy

\[I_{l}=\left[\frac{l-1}{n},\frac{l}{n}\right)\cap\mathfrak{I}_{x_{k}}\neq \emptyset. \tag{6.15}\]

Among all the indices that satisfy (6.15), there will be at most two "boundary" \(l\) such that

\[I_{l}=\left[\frac{l-1}{n},\frac{l}{n}\right)\not\subset\mathfrak{I}_{x_{k}}, \tag{6.16}\]

on at most one of which,

\[\mathcal{G}^{*}(x_{k},x_{l})=0. \tag{6.17}\]

Let \(l^{*}\) denote this index and \(l_{*}\) denote the other index that satisfies (6.16). Let \(S\) be the set of the remaining, "interior", indices, i.e., those \(l\) that satisfy (6.15) but not (6.16). Among these include \(l=k\), in which case it follows directly from definition that

\[[\mathbf{A}_{n}]_{k,l}=[\mathbf{A}_{n}]_{k,k}=0. \tag{6.18}\]

Consider

\[D_{1} :=\frac{1}{\mathcal{W}_{x_{k}}}\bigg{|}\int_{(l^{*}-1)/n}^{l^{*}/ n}(\mathcal{G}^{*}(x_{k},y)W(x_{k},y)-\mathcal{G}^{*}(x_{k},x_{l^{*}})[ \mathbf{A}_{n}]_{k,l^{*}})\rho_{j}(x_{l^{*}})\,\mathrm{d}y\bigg{|}\] \[=\frac{1}{\mathcal{W}_{x_{k}}}\bigg{|}\int_{(l^{*}-1)/n}^{l^{*}/ n}\mathcal{G}^{*}(x_{k},y)W(x_{k},y)\rho_{j}(x_{l^{*}})\,\mathrm{d}y\bigg{|},\]

due to (6.17). We find, as a consequence of Lemma 5.2, that

\[D_{1}\leq\frac{1}{\mathcal{W}_{x_{k}}}\int_{(l^{*}-1)/n}^{l^{*}/ n}|\mathcal{G}^{*}(x_{k},y)W(x_{k},y)||\rho_{j}(x_{l^{*}})|\,\mathrm{d}y \leq\frac{C\eta^{-1}N^{3\beta}}{n}. \tag{6.19}\]

Likewise, by virtue of (6.18),

\[D_{2} :=\frac{1}{\mathcal{W}_{x_{k}}}\bigg{|}\int_{(k-1)/n}^{k/n}( \mathcal{G}^{*}(x_{k},y)W(x_{k},y)-\mathcal{G}^{*}(x_{k},x_{k})[\mathbf{A}_{n }]_{k,k})\rho_{j}(x_{k})\,\mathrm{d}y\bigg{|} \tag{6.20}\] \[=\frac{1}{\mathcal{W}_{x_{k}}}\bigg{|}\int_{(k-1)/n}^{k/n} \mathcal{G}^{*}(x_{k},y)W(x_{k},y)\rho_{j}(x_{k})\,\mathrm{d}y\bigg{|}\] \[\leq\frac{C\eta^{-1}N^{3\beta}}{n}.\]
Next, let

\[D_{3}:=\frac{1}{\mathcal{W}_{x_{k}}}\sum_{l\neq k,l\in S}\bigg{|}\int_{(l-1)/n}^{l /n}(\mathcal{G}^{*}(x_{k},y)W(x_{k},y)-\mathcal{G}^{*}(x_{k},x_{l})[\mathbf{A}_ {n}]_{k,l})\rho_{j}(x_{l})\,\mathrm{d}y\bigg{|}. \tag{6.21}\]

We estimate, on one of these intervals \(I_{l}\), that

\[\begin{split}&|\mathcal{G}^{*}(x_{k},x_{l})[\mathbf{A}_{n}]_{k,l}- \mathcal{G}^{*}(x_{k},y)W(x_{k},y)|\\ &\leq|\mathcal{G}^{*}(x_{k},x_{l})-\mathcal{G}^{*}(x_{k},y)|+|[ \mathbf{A}_{n}]_{k,l}-W(x_{k},y)||\mathcal{G}^{*}(x_{k},y)|\\ &=|\mathcal{G}^{*}(x_{k},x_{l})-\mathcal{G}^{*}(x_{k},y)|+|W(x_{ k},l\,)-W(x_{k},y)||\mathcal{G}^{*}(x_{k},y)|\leq\frac{CN^{3\beta+1}}{n}+\frac{ CKN^{3\beta}}{n}\end{split} \tag{6.22}\]

where the last inequality follows from Lemma 5.2 and Assumption 2.1 on \(W\). By plugging this bound back in (6.21), we gain

\[D_{3}\leq C\eta^{-1}(1+K)\bigg{(}\sum_{l\neq k,l\in S}\frac{1}{n}\bigg{(}\frac {N^{3\beta+1}}{n}\bigg{)}\bigg{)}\leq C\eta^{-1}(1+K)\bigg{(}\frac{N^{3\beta- \alpha+1}}{n}\bigg{)}, \tag{6.23}\]

since \(\hash S\leq\lceil 2rn\rceil\). Finally, let

\[D_{4}:=\frac{1}{\mathcal{W}_{x_{k}}}\bigg{|}\int_{(l_{*}-1)/n}^{l_{*}/n}( \mathcal{G}^{*}(x_{k},y)W(x_{k},y)-\mathcal{G}^{*}(x_{k},x_{l_{*}})[\mathbf{A }_{n}]_{k,l_{*}})\rho_{j}(x_{l_{*}})\,\mathrm{d}y\bigg{|}.\]

Then following a similar calculation as in (6.22), we derive

\[|\mathcal{G}^{*}(x_{k},x_{l_{*}})[\mathbf{A}_{n}]_{k,l_{*}}-\mathcal{G}^{*}(x _{k},y)W(x_{k},y)|\leq\frac{CN^{3\beta+1}}{n}+\frac{CKN^{3\beta}}{n}\]

and so

\[D_{4}\leq C\eta^{-1}(1+K)\bigg{(}\frac{N^{3\beta+1}}{n^{2}}\bigg{)}. \tag{6.24}\]

Taking into account (6.12), (6.13), (6.14), (6.19), (6.20), (6.23), and (6.24), we arrive at (6.4), as desired. 

## 7 Proof of Theorem 3.4

Throughout this section we continue to assume (5.5) holds. We continue to work with the shorthand abbreviations established in the previous sections, which are

\[\mathcal{G}^{*}(x,y)=\frac{\mathrm{d}^{2}}{\mathrm{d}y^{2}}(s_{N}\,\mathcal{G} _{r,\sigma})(x-y)\quad\text{ and }\quad\rho_{j}(x)=ReLU_{j/2N}(x).\]

The proof will be a straightforward application of the bounded-difference inequality and Theorem 3.2. As usual, we begin with some preliminary arrangements.
First, recall that in the case of a simple random graph \(G_{n}^{\text{ran}}\) generated from a graphon \(W\), the event of two vertices \(v_{k},v_{l}\) being connected by an edge is a random variable

\[\xi_{k,l}\sim\text{Bernoulli}(W(x_{k},x_{l})),\quad k>l. \tag{7.1}\]

Since \(W(x_{k},x_{l})=W(x_{l},x_{k})\), we have the undirected symmetry \(\xi_{lk}=\xi_{k,l}\) of the graph; nevertheless, each of the sets

\[\{\xi_{k,l}:k,l=1,\cdots,n\text{ s.t }k>l\}\quad\text{ and }\quad\{\xi_{k,l}:k,l=1, \cdots,n\text{ s.t }k<l\}\]

is an independent set of random variables. A realization of the random graph \(G_{n}^{\text{ran}}\) is then a simple graph whose associated adjacency matrix \(\mathbf{A}_{n}\) satisfies

\[[\mathbf{A}_{n}]_{k,l}\in\{0,1\}.\]

Using this matrix, the graph filter \(\mathfrak{F}\)'s application on a graph signal \(g_{n}\) has the value

\[\mathfrak{F}(g_{n})(x_{k})=\frac{1}{n\mathcal{W}_{x_{k}}}\sum_{l=1}^{n} \mathcal{G}^{*}(x_{k},x_{l})[\mathbf{A}_{n}]_{k,l}g_{n}(x_{l}).\]

Until \(\xi_{k,l}\) are all realized, the quantity

\[\mathfrak{F}^{\text{ran}}(g_{n})(x_{k}):=\frac{1}{n\mathcal{W}_{x_{k}}}\sum_{ l\neq k,l=1}^{n}\mathcal{G}^{*}(x_{k},x_{l})\xi_{k,l}g_{n}(x_{l}) \tag{7.2}\]

is a random variable, for each \(k=1,\cdots,n\), as indicated by the superscript 'ran'. Fix a \(k\) and \(j=0,\cdots,2N-1\). Set \(g_{n}=\rho_{j}\) in (7.2), suppressing the dependence on \(j\) for simplicity. We define the random variables

\[Y_{\mathcal{L}_{k}} :=\frac{1}{n\mathcal{W}_{x_{k}}}\sum_{l\in\mathcal{L}_{k}} \mathcal{G}^{*}(x_{k},x_{l})\xi_{k,l}\rho_{j}(x_{l})\] \[Y_{\mathcal{U}_{k}} :=\frac{1}{n\mathcal{W}_{x_{k}}}\sum_{l\in\mathcal{U}_{k}} \mathcal{G}^{*}(x_{k},x_{l})\xi_{k,l}\rho_{j}(x_{l}),\]

where

\[\mathcal{L}_{k} :=\{l<k:\mathcal{G}^{*}(x_{k},x_{l})>0,\rho_{j}(x_{l})>0\}\] \[\mathcal{U}_{k} :=\{l>k:\mathcal{G}^{*}(x_{k},x_{l})>0,\rho_{j}(x_{l})>0\};\]

note that

\[\text{\#}\mathcal{L}_{k},\text{\#}\mathcal{U}_{k}\leq\lceil nr\rceil. \tag{7.3}\]

We first focus on \(Y_{\mathcal{L}_{k}}\). Observe from (7.1) that

\[\mathbb{E}[Y_{\mathcal{L}_{k}}]=\frac{1}{n\mathcal{W}_{x_{k}}}\sum_{l\in \mathcal{L}_{k}}\mathcal{G}^{*}(x_{k},x_{l})W(x_{k},x_{l})\rho_{j}(x_{l}).\]
Moreover, \(Y_{\mathcal{L}_{k}}\) has the form of a function \(g_{\mathcal{L}_{k}}\) of \(L_{k}:=\#\mathcal{L}_{k}\) one-dimensional variables in \([0,1]\), applied to \(\{\xi_{k,l}:l\in\mathcal{L}_{k}\}\), where

\[g_{\mathcal{L}_{k}}((z_{l})_{l\in\mathcal{L}_{k}}):=\frac{1}{n\mathcal{W}_{x_{ k}}}\sum_{l\in\mathcal{L}_{k}}\mathcal{G}^{*}(x_{k},x_{l})\rho_{j}(x_{l})z_{l}.\]

Such a function \(g_{\mathcal{L}_{k}}\) is of bounded difference. Indeed, let \(z,z^{\prime}\) be two \(L_{k}\)-tuples that differ at only one coordinate entry. It's due to (5.5) that \(\mathcal{W}_{x_{k}}\geq\eta\), and Lemma 5.2 further provides

\[|g_{\mathcal{L}_{k}}(z)-g_{\mathcal{L}_{k}}(z^{\prime})|\leq\frac{C\eta^{-1}N ^{3\beta}}{n}. \tag{7.4}\]

As mentioned earlier, the central element of our proof is a bounded-difference inequality, presented as follows.

**Theorem 7.1**.: _(adapted from [56, Theorem 2.9.1]) Let \(X_{1},\cdots,X_{L}\) be independent random variables. Let \(g:\mathbb{R}^{L}\to\mathbb{R}\). Assume that the value of \(g(x)\) can be changed by at most \(c_{j}>0\) under an arbitrary change of a single coordinate of \(x\in\mathbb{R}^{L}\). Then for any \(\delta>0\), we have_

\[\mathbb{P}(|g(X)-\mathbb{E}[g(X)]|>\delta)\leq 2\exp\bigg{(}-\frac{2\delta^{2}} {\sum_{j=1}^{L}c_{j}^{2}}\bigg{)}\]

_where \(X=(X_{1},\cdots,X_{L})\)._

Proof of Theorem 3.4.: Applying Theorem 7.1 to \(Y_{\mathcal{L}_{k}}\), and using (7.3), (7.4), we acquire

\[\mathbb{P}(|Y_{\mathcal{L}_{k}}-\mathbb{E}[Y_{\mathcal{L}_{k}}]|>\varepsilon) \leq 2\exp\bigg{(}-\frac{C\varepsilon^{2}\eta^{2}n^{2}}{N^{6\beta- \alpha}}\bigg{)}.\]

A similar argument in the case of \(\mathcal{U}_{k}\) would also result in

\[\mathbb{P}(|Y_{\mathcal{U}_{k}}-\mathbb{E}[Y_{\mathcal{U}_{k}}]|>\varepsilon) \leq 2\exp\bigg{(}-\frac{C\varepsilon^{2}\eta^{2}n}{N^{6\beta-\alpha}} \bigg{)}.\]

Since \(Y_{\mathcal{L}_{k}}+Y_{\mathcal{U}_{k}}=\mathfrak{F}^{\mathrm{ran}}(\rho_{j}) (x_{k})\), we conclude that

\[\mathbb{P}(|\mathfrak{F}^{\mathrm{ran}}(\rho_{j})(x_{k})-\mathbb{E}[\mathfrak{ F}^{\mathrm{ran}}(\rho_{j})(x_{k})]|>\varepsilon)\leq 2\exp\bigg{(}-\frac{C \varepsilon^{2}\eta^{2}n}{N^{6\beta-\alpha}}\bigg{)}, \tag{7.5}\]

for every \(x_{k}\in\mathcal{X}_{n}\) and each fixed \(j=0,\dots,2N-1\).
Now, allowing \(j\) to vary gives

\[\mathbb{P}\bigg{(}\bigg{|}\sum_{j=0}^{2N-1}f(j/2N)\mathfrak{F}^{ \text{ran}}(\rho_{j})(x_{k})-\sum_{j=0}^{2N-1}f(j/2N)\mathbb{E}[\mathfrak{F}^{ \text{ran}}(\rho_{j})(x_{k})]\bigg{|}>\varepsilon\|f\|_{L^{2}([0,1];\mathbb{C}^ {m})}\bigg{)}\] \[\leq \mathbb{P}\bigg{(}\sum_{j=0}^{2N-1}|f(j/2N)||\mathfrak{F}^{\text{ ran}}(\rho_{j})(x_{k})-\mathbb{E}[\mathfrak{F}^{\text{ran}}(\rho_{j})(x_{k})]|> \varepsilon\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}\bigg{)}\] \[\leq \mathbb{P}\bigg{(}\bigg{(}\sum_{j=0}^{2N-1}|\mathfrak{F}^{\text{ ran}}(\rho_{j})(x_{k})-\mathbb{E}[\mathfrak{F}^{\text{ran}}(\rho_{j})(x_{k})]|^{2} \bigg{)}^{1/2}>\varepsilon\bigg{)}\] \[\leq 2N^{1-\alpha}\exp\bigg{(}-\frac{C\varepsilon^{2}\eta^{2}n}{N^{6 \beta-2\alpha+1}}\bigg{)}. \tag{7.6}\]

The number of indices \(j\) taking part in these sums above is again at most \(\lceil rN\rceil\). Therefore, the second to last inequality follows from the \(L^{p}\)-embedding for finite measures and the last from (7.5). Note that, by design

\[\sum_{j=0}^{2N-1}f(j/2N)\mathfrak{F}^{\text{ran}}(\rho_{j})(x_{k})\]

is the GNN network \(\Psi_{n,f}\) applying to the random graph \(G_{n}^{\text{ran}}\) (see (2.27)). In this case

\[\overline{\Psi}_{n,f}(x)=\sum_{k=1}^{n}\bigg{(}\sum_{j=0}^{2N-1}f(j/2N) \mathfrak{F}^{\text{ran}}(\rho_{j})(x_{k})\bigg{)}\chi_{I_{k}}(x),\]

and that from (6.2), (6.5)

\[\mathbb{E}[\overline{\Psi}_{n,f}(x)] =\sum_{j=0}^{2N-1}f(j/2N)\bigg{(}\sum_{k=1}^{n}\mathbb{E}[ \mathfrak{F}^{\text{ran}}(\rho_{j})(x_{k})]\chi_{I_{k}}(x)\bigg{)}\] \[=\sum_{j=0}^{2N-1}\frac{f(j/2N)}{n\mathcal{W}_{x_{k}}}\sum_{k=1}^ {n}\bigg{(}\sum_{l\neq k,l=1}^{n}\mathcal{G}^{*}(x_{k},x_{l})W(x_{k},x_{l}) \rho_{j}(x_{l})\bigg{)}\chi_{I_{k}}(x)\] \[=\sum_{j=0}^{2N-1}f(j/2N)\overline{\mathfrak{F}(\rho_{j})}(x)= \overline{\mathfrak{F}(f_{\sharp})}(x).\]

Therefore, based on (7.6), we deduce that for every \(x\in[r,1-r]\),

\[|\overline{\Psi}_{n,f}(x)-\overline{\mathfrak{F}(f_{\sharp})}(x)|\leq \varepsilon\|f\|_{L^{2}([0,1];\mathbb{C}^{m})} \tag{7.7}\]
with probability at least \(1-2nN^{1-\alpha}\exp(-\frac{C\varepsilon^{2}\eta^{2}n}{N^{6\beta-2\alpha+1}})\). On the other hand, we obtain from the proof of Theorem 3.3 that for almost every \(x\in[r,1-r]\)

\[\left|\overline{\mathfrak{F}(f_{\sharp})}(x)-T_{\mathcal{K}}f_{\sharp}(x) \right|\leq C\eta^{-2}(1+K)\,\varepsilon\,\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}, \tag{7.8}\]

whenever \(n\geq\lceil\varepsilon^{-13/3}\rceil\). By combining (7.7), (7.8), and recalling that \(N=\lceil\varepsilon^{-10/9}\rceil\), we infer that

\[|\Psi_{n,f}(x_{k})-f(x_{k})|\leq C\eta^{-2}(1+K)\,\varepsilon\,\|f\|_{L^{2}([0,1];\mathbb{C}^{m})}\]

holds for all \(x_{k}\in[r,1-r]\), with a probability at least

\[1-2n\varepsilon^{10(1-\alpha)/9}\exp\bigg{(}-\frac{C\eta^{2}n}{\varepsilon^{4 (15\beta-5\alpha-2)/9}}\bigg{)},\]

where \(\alpha=0.96\), \(\beta=0.98\), so as long as \(n\geq\varepsilon^{-13/3}\), leading us to the conclusion of the proof. 

## 8 Discussion

In this work we have provided powerful novel results regarding the generalizability of WNNs and the transferability of GNNs. Our results were enabled first through the sampling routine in Theorem 3.1, which was used to inform our network architecture for both WNNs and GNNs. In the case of WNNs we provide bounds on the number of samples required to achieve the approximation of graphon signals to arbitrary accuracy using our proposed WNN architecture. These results were then leveraged to provide transferability results for GNNs across graphs belonging to the same graphon family. This included both deterministic weighted graphs and simple random graphs. Together these results constitute a significant advancement in the budding theory of graphons applied to neural networks and the expressive capabilities of WNNs.

We emphasize that these results mark only an initial step towards a unified theory of graphons and their application to GNNs. Moving forward we wish to expand the class of graphons for which our results apply beyond those that satisfy Assumption 2.1. For example, popular graphs/graphons in application are stochastic block models [1, 54] which do not satisfy our assumption. However, one may subdivide the domain of a stochastic block model according to each of the blocks, in which case our results can be applied piecewise to the distinct blocks. Hence, it is important that a follow-up work generalize our results to as wide a class of graphons as possible to provide the greatest applicability of our results. One direction in which such a generalization could be achieved is by replacing the graphon domain \([0,1]^{2}\) with \(\Omega^{2}\), for an arbitrary compact set \(\Omega\). In the case of a stochastic block model \(\Omega\) would take the form of a union over the finitely-many (compact) blocks. A presentation of graphons with arbitrary \(\Omega\) is done in [29] where much of the theory laid out in SS2.2 can still be applied, but the presentation becomes more delicate
at points. Therefore, such a generalization marks an immediate point for a follow-up investigation of our work herein.

Given that our work describes an explicit network architecture, we have therefore provided a simple GNN/WNN architecture that can be readily applied in experiments. As with all statements in mathematical analysis, our results are given in the worse case scenario and so it remains to benchmark our network's performance on real-world data. In particular, it would be interesting to compare the performance of our network architecture against some of the other architectures for both WNNs and GNNs that have been provided throughout the literature. Such experiments may provide key insights into better architectures and tighter bounds than those which are reported here.

As a final aside, we note that graphons can only describe _dense_ graphs. To fully generalize our results to accommodate a more diverse range of graph structures one should hope to be able to apply our results to _sparse_ graphs as well. There is theory for capturing sparse graph structures using graphons [6, 19, 32, 37] which could form the basis for an extension of our work in this paper. We expect such an extension to be highly nontrivial and leave it for future work.

## Acknowledgements

JJB was supported by an NSERC Discovery grant.
