# Limits, approximation and size transferability for GNNs on sparse graphs via
graphops

Thien Le
CSAIL
MIT
Cambridge, MA
<EMAIL_ADDRESS>
&Stefanie Jegelka
CSAIL
MIT
Cambridge, MA
<EMAIL_ADDRESS>
###### Abstract

Can graph neural networks generalize to graphs that are different from the
graphs they were trained on, e.g., in size? In this work, we study this
question from a theoretical perspective. While recent work established such
transferability and approximation results via graph limits, e.g., via
graphons, these only apply nontrivially to dense graphs. To include frequently
encountered sparse graphs such as bounded-degree or power law graphs, we take
a perspective of taking limits of operators derived from graphs, such as the
aggregation operation that makes up GNNs. This leads to the recently
introduced limit notion of graphops (Backhausz and Szegedy, 2022). We
demonstrate how the operator perspective allows us to develop quantitative
bounds on the distance between a finite GNN and its limit on an infinite
graph, as well as the distance between the GNN on graphs of different sizes
that share structural properties, under a regularity assumption verified for
various graph sequences. Our results hold for dense and sparse graphs, and
various notions of graph limits.

##  1 Introduction

Since the advent of graph neural networks (GNNs), deep learning has become one
of the most promising tools to address graph-based learning tasks (Gilmer et
al., 2017; Scarselli et al., 2009; Kipf and Welling, 2017; Bronstein et al.,
2017). Following the mounting success of applied GNN research, theoretical
analyses have been following. For instance, many works study GNNs’
representational power (Azizian and Lelarge, 2021; Morris et al., 2019; Xu et
al., 2019, 2020; Garg et al., 2020; Chen et al., 2020; Maron et al., 2019;
Loukas, 2020a, b; Abboud et al., 2021).

A hitherto less addressed question of practical importance is the possibility
of size generalization, i.e., transferring a learned GNN to graphs of
different sizes (Ruiz et al., 2020; Levie et al., 2022; Xu et al., 2021;
Yehudai et al., 2021; Chuang and Jegelka, 2022; Roddenberry et al., 2022),
especially for sparse graphs. For instance, it would be computationally
desirable to train a GNN on small graphs and apply it to large graphs. This
question is also important to judge the reliability of the learned model on
different test graphs. To answer the size generalization question, we need to
understand under which conditions such transferability is possible – since it
may not always be possible (Xu et al., 2021; Yehudai et al., 2021; Jegelka,
2022) – and what output perturbations we may expect. For a formal analysis of
perturbations and conditions, we need a suitable graph representation that
captures inductive biases and allows us to compare models for graphs of
different sizes. _Graph limits_ can help to formalize this, as they help
understand biases as the graph size tends to infinity.

Formally, _approximation theory_ asks for bounds between a GNN on a finite
graph and its infinite counterpart, while _transferability_ compares model
outputs on graphs of different sizes. The quality of the bounds depends on how
the two GNNs (and corresponding graphs) are intrinsically linked, in
particular, to what extent the graphs share relevant structure. This yields
conditions for size generalization. For example, the graphs could be sampled
from the same graph limit (Ruiz et al., 2020) or from the same random graph
model (Keriven et al., 2020).

In particular, Ruiz et al. (2020) study approximation and transferability via
the lens of _graphons_ (Lovász, 2012; Lovász and Szegedy, 2006), which
characterize the limits of _dense_ graphs. Yet, many real-world graphs are not
dense, for instance, planar traffic networks, power law graphs, Hamming graphs
(including hypercubes for error-correcting code), or grid-like graphs e.g.,
for images. For _sparser_ graphs, the correct notion of limit suitable for
deep learning is still an open problem, as typical bounded-degree graph limits
such as the Benjamini-Schramm limit of random rooted graphs (Benjamini and
Schramm, 2001), or graphings (Lovász, 2012) are less well understood and often
exhibit pathological behaviors (see Section 2.1). Limits of intermediate
graphs, such as the hypercubes, are even more obscure. Hence, understanding
limits, inductive biases and transferability of GNNs for sparse graphs remains
an open problem in understanding graph representation learning.

This question is the focus of this work. To obtain suitable graph limits for
sparse graphs and to be able to compare GNNs on graphs of different sizes
while circumventing challenges of sparse graph limits, we view a graph as an
_operator_ derived from it. This viewpoint is naturally compatible with GNNs,
as they are built from convolution/aggregation operations. We show how the
operator perspective allows us to define limits of GNNs for infinite graphs.
We achieve this by exploiting the recently defined notion of _graphop_ , which
generalizes graph shift operators, and the _action convergence_ defined in the
space of graphops (Backhausz and Szegedy, 2022). Our definition of GNN limits
enables us to prove rigorous bounds for approximation and transferability of
GNNs for sparse graphs. Since graphops encompass both graphons and graphings,
we generalize similar bounds for graphon neural networks (Ruiz et al., 2020)
to a much wider set of graphs.

Yet, using graphops requires technical work. For instance, we need to
introduce an appropriate discretization of a graphop to obtain its
corresponding finite graph shift operators. We use these operators to define a
generalized graphop neural network that acts as a limit object, with
discretizations that become finite GNNs. Then we prove approximation and
transferability results for both the operators (graphops and their
discretizations) and GNNs.

Contributions. To the best of our knowledge, this is the first paper to
provide approximation and transferability theorems specifically for sparse
graph limits. Our main tool, graphops, has not been used to study GNNs before,
although viewing graphs as operators is a classic theme in the literature. Our
specific contributions are as follows:

  1. 1.

We define a _graphop convolution_ , i.e., an operator that includes both
finite graph convolutions and a limit version that allows us to define a limit
object for GNNs applied to graphs of size $n\to\infty$.

  2. 2.

We rigorously prove an approximation theorem (Theorem 2) that bounds a
distance between a graphop $A$ (acting on infinite-dimensional $\Omega$) and
its discretization $A_{n}$ (acting on $\mathbb{R}^{n}$), in the $d_{M}$ metric
introduced by Backhausz and Szegedy (2022). To do so, we introduce an
appropriate discretization. Our result applies to a more general set of
nonlinear operators, and implies a transferability bound between finite graphs
(discretizations) of different sizes.

  3. 3.

For neural networks, we present a quantitative approximation and
transferability bound that guarantees outputs of graphop neural networks are
close to those of the corresponding GNNs (obtained from discretization).

###  1.1 Related work

The closest related work is (Ruiz et al., 2020), which derives approximation
and transferability theorems for _graphon_ neural networks, i.e., _dense_
graphs. For graphons, the convolution kernel has a nice spectral
decomposition, which is exploited by Ruiz et al. (2020). In contrast, _sparse_
graph limits are not known to enjoy nice convergence of the spectrum
(Backhausz and Szegedy, 2022; Aldous and Lyons, 2007), so we need to use
different techniques. Since the notion of graphop generalizes both dense graph
limits and certain sparse graph limits, our results apply to dense graphs as
well. Our assumptions and settings are slightly different from Ruiz et al.
(2020). For instance, they allow the convolution degree $K\to\infty$ and
perform the analysis in the spectral domain, whereas our $K$ is assumed to be
a fixed finite constant. As a result, their bound has better dependence of
$O(1/n)$ on $n$–the resolution of discretization, but does not go to $0$ as
$n\to\infty$. Ours have extra dependence on $K$ and a slower rate of
$O(n^{-1/2}$ but our bounds go to $0$ as $n\to\infty$.

Other works use other notions than graph limits to obtain structural
coherence. Levie et al. (2022) obtain a transferability result for spectral
graph convolution networks via analysis in frequency domains. They sample
finite graphs from general topologies as opposed to a graph limit. Their graph
signals are _assumed_ to have finite bandwidth while ours is only assumed to
be in $L^{2}$. Their signal discretization scheme is assumed to be close to
the continuous signals, while ours is proven to be so. Roddenberry et al.
(2022) address sparse graphs and give a transferability bound between the loss
functions of two random rooted graphs. However, the metric under which they
derive their result is rather simple: if the two graphs are not isomorphic
then their distance is constant, otherwise, they use the Euclidean metric
between the two graph signals. This metric hence does not capture
combinatorial, structural differences of functions on non-isomorphic graphs.
To study transferability, Keriven et al. (2020) sample from standard random
graph models, as opposed to a graph limit, resulting in a bound of order
$O(n^{-1/2})$, which is similar to ours. They also need an assumption on the
closeness of the graph signal.

##  2 Background

#### Notation

Let $\mathbb{N}$ be $\\{1,2,\ldots\\}$ and write $[n]=\\{1,\ldots,n\\}$ for
any $n\in\mathbb{N}$. For a scalar $\alpha\in\mathbb{R}$ and a set
$S\subset\mathbb{R}$, let $\alpha S=\\{\alpha s:s\in S\\}$. The abbreviation
a.e. stands for ‘almost everywhere’.

For a measure space $(\Omega,\mathcal{B},\mu)$ and $p\in[1,\infty]$, denote by
$L^{p}(\Omega)$ the corresponding $L^{p}$ function spaces with norm
$\|\cdot\|_{p}:f\mapsto(\int_{\Omega}|f|^{p}d\mu)^{1/p}$. For any
$p,q\in[1,\infty]$, define the operator norms $\|\cdot\|_{p\to
q}:A\mapsto\sup_{v\in L^{\infty}}\|vA\|_{q}/\|v\|_{p}$.

For function spaces, we use $\mathcal{F}=L^{2}([0,1])$ and
$\mathcal{F}_{n}=L^{2}([n]/n)$, for any $n\in\mathbb{N}$. For any $L^{p}$
space $\mathcal{H}$, denote by $\mathcal{H}_{[-1,1]}$ the restriction to
functions with range in $[-1,1]$ a.e. and $\mathcal{H}_{\text{Lip}(L)}$ the
restriction to functions that are $L$-Lipschitz a.e. and
$\mathcal{H}_{\text{reg}(L)}=\mathcal{H}_{[-1,1]}\cap\mathcal{H}_{\text{Lip}(L)}$.

#### Graph neural networks (GNNs)

GNNs are functions that use graph convolutions to incorporate graph structure
into neural network architectures. Given a finite graph $G=(V,E)$ and a
function $X:V\to\mathbb{R}$ (called _graph signal_ or _node features_), a GNN
$\Phi_{F}$ ($F$ for ‘finite’) with $L$ layers, $n_{i}$ neurons at the $i$-th
layer, nonlinearity $\rho$ and learnable parameters $h$, is:

$\displaystyle\Phi_{F}(h,G,X)$ $\displaystyle=X_{L}(h,G,X),$ (1)
$\displaystyle\left[X_{l}(h,G,X)\right]_{f}$
$\displaystyle=\rho\bigg{(}\sum_{g=1}^{n_{l-1}}A_{l,f,g}(h,G)[X_{l-1}]_{g}\bigg{)},\qquad
l\in[L],f\in[n_{l}]$ (2) $\displaystyle X_{0}(h,G,X)$ $\displaystyle=X,$ (3)

where $[X_{l}]_{f}$ is the output of the $f$-th neuron in the $l$-th layer,
which is another graph signal. The input graph information is captured through
order $K$ _graph convolutions_
$A_{l,f,g}(h,G):=\sum_{k=0}^{K}h_{l,f,g,k}GSO(G)^{k}$, where $GSO(G)$ is a
_graph shift operator_ corresponding to $G$ — popular examples include the
adjacency matrix or the Laplacian (Kipf and Welling, 2017; Levie et al.,
2022). The power notation is the usual matrix power, while the notation
$h_{l,f,g,k}$ highlights that there is a learnable parameter for each
convolution order $k$, between each neuron $f$ and $g$ from layer $l-1$ to
layer $l$ of the neural network. Thus, the number of learnable parameters in a
GNN does not depend on the number of vertices of the graph used to form the
GSO.

###  2.1 Graph limits

Graph limit theory involves embedding discrete graphs into spaces with rich
underlying topological and/or geometric structures and studying the behavior
of convergent (e.g. in size) graph sequences.

#### Dense graphs

A popular example of graph limits are graphons - symmetric $L^{1}([0,1]^{2})$
(Lebesgue-measurable) functions whose value at $(x,y)$ can be thought of
(intuitively) as the weight of the $xy$-edge in a graph with vertices in
$[0,1]$. When equipped with the _cut metric_ (see Appendix A for the exact
definition), it contains limits of convergent sequences of dense graphs.
Convergence in this space is dubbed _dense graph convergence_ because for any
$W\in L^{1}([0,1]^{2}),\|W\|_{\square}=0$ iff $W=0$ outside a set of Lebesgue
measure $0$. This implies that graphs with a subquadratic number of edges,
such as grids or hypercubes, are identified with the empty graph in the cut
norm. Dense graph convergence is very well understood theoretically and is the
basis for recent work on GNN limits (Ruiz et al., 2020).

#### Sparse graphs

There are two notions of limits that are deemed suitable for bounded-degree
graph convergence in the literature. The first, _graphing_ (Lovász, 2012), is
a direct counterpart of a graphon. Recall that graphons are not suitable for
sparse graphs because the Lebesgue measure on $L^{2}([0,1]^{2})$ is not fine
enough to detect edges of bounded-degree graphs. Therefore, one solution is to
consider other measure spaces. Graphings are quadruples
$(V,\mathcal{A},\lambda,E)$ where $V$ and $E$ are interpreted as the usual
vertex and edge sets and $(V,\mathcal{A},\lambda)$ together form a Borel
measure such that $E$ is in $\mathcal{A}\times\mathcal{A}$ satisfying a
symmetry condition. While Lebesgue measures are constructed from a specific
topology of open sets on $\mathbb{R}$, for graphings, we are allowed the
freedom to choose a different topological structure (for instance a _local
topology_) on $V$. The definition of graphings is theoretically elegant but
harder to work with since the topological structures are stored in the
$\sigma$-algebra. A second way to embed bounded-degree graphs, Benjamini-
Schramm limits (Benjamini and Schramm, 2001), uses distributions over random
rooted graphs. Roughly speaking, for each $k\in\mathbb{N}$, one selects a root
uniformly at random from the vertex set in the graph and considers the induced
subgraph of vertices that are at distance at most $k$ from the root. The
randomness of the root induces a distribution over the set of rooted graphs of
radius $k$ from the root.

Graphings and distributions of random rooted graphs are intimately connected,
but their connection to convergent bounded-degree graph sequences is not well-
understood. For example, a famous open conjecture by Aldous and Lyons (2007)
asks whether all graphings are weak local limits of some sequence of bounded-
degree graphs. The unresolved conjecture of Aldous and Lyons means that one
cannot simply take an arbitrary graphing and be guaranteed a finite bounded-
degree graph sequence converging to said graphing, which is the main approach
in Ruiz et al. (2020) for dense graphs. A self-contained summary of graphings
within the scope of this paper is provided in Appendix C. Infinite paths and
cycles also have nice descriptions in terms of graphings (also in Appendix C),
which we will use in our constructions for Lemma 2.

###  2.2 Graphops and comparing across graph sizes

More recently, Backhausz and Szegedy (2022) approach graph limits from the
viewpoint of limits of operators, called _graphops_. This viewpoint is
straightforward for finite graphs: both the adjacency matrix and Laplacian,
each defining a unique graph, are linear operators on
$\mathbb{R}^{\\#\text{vertices}}$. Moreover, viewing graphs as operators is
exactly what we do with GSOs and graph convolutions. Hence, graphop seems to
be an appropriate tool to study GNN approximation and transferability. On the
other hand, there are challenges with this approach: being related to
graphings, they inherit some of graphings’ limitations, such as the conjecture
of Aldous and Lyons (2007). Moreover, to understand GNN transferability from
size $m$ to $n$, one needs to compare an $m\times m$ matrix with an $n\times
n$ matrix, which is nontrivial. This is done by comparing their actions on
$\mathbb{R}^{m}$ versus $\mathbb{R}^{n}$. It turns out that these actions,
under an appropriate metric, define a special mode of operator convergence
called _action convergence_. The resulting limit objects are well-defined and
nontrivial for sparse graphs and intermediate graphs, while also generalizing
dense graphs limits. We will describe this mode of convergence, the
corresponding metric, and our own relaxation of it later in this section.

We now describe how graphs of different sizes can be compared through the
actions of their corresponding operators on some function spaces.

#### Nonlinear $P$-operators

For an $n$-vertex graph, its adjacency matrix, Laplacian, or Markov kernel of
random walks are examples of linear operators on $L^{p}([n]/n)$. To formally
generalize to the infinite-vertex case, Backhausz and Szegedy (2022) use _$P$
-operators_, which are linear operators from $L^{\infty}(\Omega)$ to
$L^{1}(\Omega)$ with finite $\|A\|_{\infty\to 1}$. In this paper, we further
assume they have finite $\|\cdot\|_{2\to 2}$ norm but are not necessarily
linear. We address these deviations in Section 4.4.

#### Graphops

$P$-operators lead to a notion of graph limit that applies to both dense and
sparse graphs. _Graphops_ (Backhausz and Szegedy, 2022) are positivity-
preserving (action on positive functions results in positive functions), self-
adjoint $P$-operators. Adjacency matrices of finite graphs, graphons (Lovász
and Szegedy, 2006), and graphings (Lovász, 2012) are all examples of graphops.
Changing the positivity-preserving requirement to positiveness allows one to
consider Laplacian operators.

####  $(k,L)$-profile of a $P$-operator

Actions of graphops are formally captured through their $(k,L)$-profiles, and
these will be useful to compare different graphops. Pick $k\in\mathbb{N}$,
$L\in[0,\infty]$ and $A$ a $P$-operator on $(\Omega,\mathcal{B},\mu)$.
Intuitively, we will take $k$ samples from the space our operators act on,
apply our operator to get $k$ images, and concatenate samples and images into
a joint distribution on $\mathbb{R}^{2k}$, which gives us one element of the
profile. For instance, for $n$-vertex graphs, the concatenation results in a
matrix $M\in\mathbb{R}^{n\times 2k}$, so each joint distribution is a sum
(over rows of $M$) of $n$ Dirac distributions. In the limit, the number of
atoms in each element of the profile increases, and the measure converges
(weakly) to one with density. More formally, denote by
$\mathcal{D}(v_{1},\ldots,v_{k})$ the pushforward of $\mu$ via
$x\mapsto(v_{1}(x),\ldots,v_{k}(x))$ for any tuple $(v_{i})_{i\in[k]}\in
L^{2}(\Omega)$. The _$(k,L)$ -profile_ of $A$ is:

$\displaystyle\mathcal{S}_{k,L}(A):=\\{\mathcal{D}(v_{1},\ldots,v_{k},Av_{1},\ldots,Av_{k}):v_{i}\in
L^{\infty}_{\text{reg}(L)}(\Omega),i=1\ldots k\\}.$ (4)

Formally, denote by $\mathcal{P}(\mathbb{R}^{k})$ the set of Borel probability
distributions over $\mathbb{R}^{2k}$. Regardless of the initial graph size, or
the space on which the operators act, $(k,L)$-profiles of $A$ are always some
subsets of $\mathcal{P}(\mathbb{R}^{2k})$ which allow us to compare operators
acting on different spaces.

#### Convergence of $P$-operators

We compare two profiles (closed subsets
$X,Y\subset\mathcal{P}(\mathbb{R}^{2k})$) via a Hausdorff metric
$d_{H}(X,Y):=\max(\sup_{x\in X}\inf_{y\in Y}d_{LP}(x,y),\sup_{y\in
Y}\inf_{x\in X}d_{LP}(x,y)).$ Here, $d_{LP}$ is the Lévy-Prokhorov metric on
$\mathcal{P}(\mathbb{R}^{2k})$ (see exact definition in Appendix A), which
metrizes weak convergence of Borel probability measures, and translates action
convergence to weak convergence of measures. Finally, given any two
$P$-operators $A,B$, we can compare their profiles across all different $k$ at
the same time as

$d_{M}(A,B):=\sum_{k=1}^{\infty}2^{-k}d_{H}(\mathcal{S}_{k,L}(A),\mathcal{S}_{k,L}(B)).$
(5)

Intuitively, we allow $d_{H}$ to grow subexponentially in $k$ by the scaling
$2^{-k}$. Our definition of profile slightly differs from that of Backhausz
and Szegedy (2022), using $L^{\infty}_{\text{reg}(L)}$ instead of their
$L^{\infty}_{[-1,1]}$. However, we will justify this deviation in Section 4.4,
Theorem 4: by letting $L$ grow slowly in $n$, we recover the original limits
in Backhausz and Szegedy (2022).

This _action convergence_ turns out to be one of the ‘right’ notions of
convergence that capture both sparse and dense graph limits, as well as some
intermediate density graphs:

######  Theorem 1 (Theorem 1.1 Backhausz and Szegedy (2022)).

Convergence under $d_{M}$ is equivalent (results in the same limit) to dense
graph convergence when restricted to graphons and equivalent to local-global
convergence when restricted to graphings.

##  3 Graphop neural networks

Graph limits allow us to lift finite graphs onto the richer space of graphops
to discuss convergent graph sequences $G_{i}\to G$. For finite GNNs (Eqn (2)),
fixing the graph input $G_{i}$ and learnable parameter $h$ results in a
function $\Phi_{F}(h,G_{i},\cdot)$ that transforms the input graph signal
(node features) into an output graph signal. The transferability question asks
how similar $\Phi_{F}(h,G_{i},\cdot)$ is to $\Phi_{F}(h,G_{j},\cdot)$ for some
$i\neq j$. In our approach using approximation theory, we will compare both
functions to the limiting function on $G$. This is done by an appropriate lift
of the GNN onto a larger space that we call _graphop neural networks_.

We then introduce a discretization scheme of graphop neural networks to obtain
finite GNNs, similar to graphon sampling (Ruiz et al., 2020) and sampling from
topological spaces (Levie et al., 2022). Finally, Lemma 1 asserts that,
restricted to self-adjoint $P$-operators, discretizations of graphops are
indeed graph shift operators (GSOs).

###  3.1 Convolution and graphop neural networks

Similar to how GSOs in a GNN act on graph signals, graphops act on some
$L^{2}$ signals (called _graphop signals_). The generalization is
straightforward: replacing GSOs in the construction of the GNN in Eqn. (2)
with graphops results in _graphop convolution_ and replacing graph convolution
with graphop convolution gives _graphop neural networks_.

Formally, fix a maximum order $K\in\mathbb{N}$. For some measure space
$(\Omega,\mathcal{B},\mu)$, select a graphop $A:L^{2}(\Omega)\to
L^{2}(\Omega)$ and a graphop signal $X\in L^{2}(\Omega)$. We define a _graphop
convolution_ operator as a weighted sum of at most $K-1$ applications of $A$:

$H(h,A)[X]:=\sum_{k=0}^{K-1}(h_{k}A^{k})[X],$ (6)

where $h\in\mathbb{R}^{K}$ are (learnable) filter parameters and $A^{k}$ is
the composition of $k$ duplicates of $A$. The square bracket $[v]_{i}$
indicates the $i$-th entry of a tuple $v$.

For some number of layers
$L\in\mathbb{N},\\{n_{i}\\}_{i\in[L]}\in\mathbb{N},n_{0}:=1$, define a
_graphop neural network_ $\Phi$ with $L$ layers and $n_{i}$ features in layer
$i$ as:

$\displaystyle\Phi(h,A,X)$ $\displaystyle=X_{L}(h,A,X),$ (7) $\displaystyle
X_{l}(h,A,X)$
$\displaystyle=\left[\rho\bigg{(}\sum_{g=1}^{n_{l-1}}H(h^{l}_{f,g},A)[X_{l-1}]_{g}\bigg{)}\right]_{f\in[n_{l}]},\qquad
l\in[L],$ (8) $\displaystyle X_{0}(h,A,X)$ $\displaystyle=X$ (9)

with filter parameter tuple $h=(h^{1},\ldots,h^{L})$,
$h^{l}\in(\mathbb{R}^{K})^{n_{l}\times n_{l-1}}$ for any $l\in[L]$, and
graphop signal tuple $X_{l}\in(L^{2}(\Omega))^{n_{l}}$ for any
$l\in[L]\cup\\{0\\}$. Eqn (8) and Eqn (2) are almost identical, with the only
difference being the input/output space: graphops replacing finite graphs, and
graphop signals replacing graph signals.

###  3.2 From graphop neural networks to finite graph neural networks

We are specifically interested in finite GNNs that are discretizations of a
graphop (for instance finite grids as discretizations of infinite grids), so
as to obtain a quantitative bound that depends on the resolution of
discretization. To sample a GNN from a given graphop
$A:\mathcal{F}\to\mathcal{F}$, we first sample a GSO and plug it into Eqn (2).
Choose a resolution $m\in\mathbb{N}$ and define the GSO $A_{m}$, for any graph
signal $X\in\mathcal{F}_{m}$ as:

$\displaystyle A_{m}X(v)$
$\displaystyle:=m\int_{v-\frac{1}{m}}^{v}(A\widetilde{X})\textup{d}\lambda,\qquad
v\in[m]/m,$ (10) $\displaystyle\Phi_{m}(h,A,X)$
$\displaystyle:=\Phi(h,A_{m},X),$ (11)

where graphop signal $\widetilde{X}\in\mathcal{F}$ is an extension of graph
signal $X\in\mathcal{F}_{m}$ defined as

$\displaystyle\widetilde{X}(u):=X\left(\frac{\left\lceil
um\right\rceil}{m}\right),\qquad u\in[0,1].$ (12)

Intuitively, to find the image of the sampled GSO $A_{m}$ when applied to a
graph signal $X$, we transform the graph signal into a graphop signal
$\tilde{X}$ by using its piecewise constant extension. We then apply the given
$A$ to $\tilde{X}$ to get an output graphop signal on $L^{2}([0,1])$.
Discretizing this graphop signal by dividing the domain $[0,1]$ into $m$
partitions of equal size and integrating over each partition, one gets a graph
signal on $\mathcal{F}_{m}$ \- the image of $A_{m}X$. Note that if $A$ is
linear then $A_{m}$ is necessarily linear, but our definition of graphop does
not require linearity. Therefore, $A_{m}$ is strictly more general than the
matrix representation of graph shift operators. We have the following well-
definedness result:

######  Lemma 1.

If a graphop $A:\mathcal{F}\to\mathcal{F}$ is self-adjoint, then for each
resolution $m\in\mathbb{N}$, the discretization
$A_{m}:\mathcal{F}_{m}\to\mathcal{F}_{m}$ defined above is also self-adjoint.

The proof can be found in Appendix B. Compared to previous works, our
discretization scheme in Eqn (10) looks slightly different. In Ruiz et al.
(2020), given a graphon $W:[0,1]^{2}\to\mathbb{R}$, the discretization at
resolution $n$ was defined by forming the matrix $S\in\mathbb{R}^{n\times
n}:S_{i,j}=W(i/n,j/n)$. A related discretization scheme involving picking the
interval endpoints at random was also used, but the resulting matrix still
takes values at discrete points in $W$. These two sampling schemes rely
crucially on their everywhere continuous assumptions for the graphon $W$.
Indeed, but for continuity requirements, two functions that differ only at
finite discrete points $(i/n,j/n),i,j\in[n]$ are in the same $L^{2}$ class of
functions, but will give rise to completely different samples. Furthermore,
not every $L^{2}$ class of functions has a continuous representative. This
means that our discretization scheme is strictly more general than that used
by Ruiz et al. (2020) even when restricted to graphons. This difference comes
from the fact that we are discretizing an operator and not the graph itself.
For our purpose, taking values at discrete points for some limiting object of
sparse graphs will likely not work, since sparsity ensures that most discrete
points are trivial. The integral form of the discretization (as opposed to
setting $A_{m}X(v)=(A\widetilde{X})(v)$ for all $v\in[m]/m$, for example) is
crucial for Lemma 1.

##  4 Main result: Approximation and transferability

###  4.1 Results for $P$-operators

Our first set of theorems address approximation and transferability of
$P$-operators: under certain regularity assumptions to be discussed later,
$P$-operators are well approximated by their discretizations:

######  Theorem 2 (Approximation theorem).

Let $A:\mathcal{F}\to\mathcal{F}$ be a $P$-operator satisfying Assumption 2
with constant $C_{A}$; Assumption 3.A or 3.B with resolutions in
$\mathcal{N}$. Fix $n\in\mathcal{N}$ and consider $(k,C_{v})$-profiles. Let
$A_{n}:\mathcal{F}_{n}\to\mathcal{F}_{n}$ be a discretization of $A$ as
defined in Equation (10). Then:

$d_{M}\left(A,A_{n}\right)\leq
2\sqrt{\frac{C_{A}C_{v}}{n}}+\frac{C_{v}+1}{n}.$ (13)

Compared to theorems in Ruiz et al. (2020), our explicit dependence on $n$ has
an extra $n^{-1/2}$ term that stems from techniques used to bound the Lévy-
Prokhorov distance between two entry distributions obtained from functions
that differ by at most $O(n^{-1})$ in $L^{2}$ norm.

As an immediate corollary, invoking the triangle inequality yields a
transferability bound.

######  Corollary 1 (Transferability).

Let $A:\mathcal{F}\to\mathcal{F}$ be a $P$-operator satisfying assumptions of
Theorem 2 with constant $C_{A}$ and resolutions $\mathcal{N}$. For any
$n,m\in\mathcal{N}$, let $A_{n}:\mathcal{F}_{n}\to\mathcal{F}_{n}$ and
$A_{m}:\mathcal{F}_{m}\to\mathcal{F}_{m}$ be discretizations as defined in
Equation (10). Then:

$\displaystyle
d_{M}\left(A_{m},A_{n}\right)\leq\left(m^{-\frac{1}{2}}+n^{-\frac{1}{2}}\right)2\sqrt{C_{A}C_{v}}+(m^{-1}+n^{-1})(C_{v}+1).$
(14)

We emphasize that these theorems work for general nonlinear $P$-operators and
not only the linear graphops defined in (Backhausz and Szegedy, 2022).

#### Proof sketch

The full proof of Theorem 2 is in Appendix D. To bound the distance in $d_{M}$
between two operators, for each sample size $k\in\mathbb{N}$, we give a bound
on the Hausdorff metric $d_{H}$ between the two $(k,C_{v})$-profiles. As long
as the dependence on $k$ of these bounds is polynomial, the infinite sum in
the definition of $d_{M}$ converges. We do this by picking an arbitrary
distribution $\overline{\eta}$ from $\mathcal{S}_{k,C_{v}}(A)$, which by
definition is given by a $k$-tuple $F$ of functions in
$L^{\infty}_{\text{reg}(C_{v})}$. Discretize each element of $F$ and consider
its entry distribution results in
$\overline{\eta}_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})$. We show that we can give
an upper bound of $d_{LP}(\overline{\eta},\overline{\eta}_{n})$ that is
independent of the choice of $\overline{\eta}$ and thus same upper bound holds
for
$\sup_{\eta\in\mathcal{S}_{k,C_{v}}(A)}\inf_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}d_{LP}(\eta,\eta_{n})$.
By also selecting an arbitrary element of $\mathcal{S}_{k,C_{v}}(A_{n})$ and
extending it to an element of $\mathcal{S}_{k,C_{v}}(A)$, we obtain another
upper bound for
$\sup_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}\inf_{\eta\in\mathcal{S}_{k,C_{v}}(A)}d_{LP}(\eta,\eta_{n})$
and thus for $d_{H}$. The different assumptions come in via different
techniques used to bound $d_{LP}$ by a high probability bound on the $L^{2}$
norm of the functions in $F$ and their discretization/extension.

###  4.2 Results for graphop neural networks

Not only are graphops and their discretizations close in $d_{M}$, but, as we
show next, neural networks built from a graphop are also close to those built
from graphop discretizations in $d_{M}$. We iterate that here we are comparing
nonlinear operators (graphop neural networks) that are acting on different
spaces ($L^{2}([n]/n)$ for some finite $n$ versus $L^{2}([0,1])$).

Before stating theoretical guarantees for graphop neural networks, let us
introduce some assumptions on the neural network activation function and
parameters:

######  Assumption 1.

Let the activation function $\rho:\mathbb{R}\to\mathbb{R}$ in the definition
of graphop neural networks be $1$-Lipschitz. Let the convolution parameters
$h$ be normalized such that $|h|\leq 1$ element-wise.

######  Theorem 3 (Graphop neural network discretization).

Let $A:\mathcal{F}\to\mathcal{F}$. Assume that $A$ satisfies Assumption 2 with
constant $C_{A}$ and Assumption 3.A or 3.B with resolutions in $\mathcal{N}$.
Fix $n\in\mathcal{N}$ and consider $(k,C_{v})$-profiles. Under Assumption 1,
we have:

$\displaystyle d_{M}(\Phi(h,A,\cdot),\Phi(h,A_{n},\cdot))\leq$ $\displaystyle
P_{1}\sqrt{\frac{\overline{C}_{A}C_{v}}{n}}+\frac{C_{v}+1}{n},$ (15)

where $\overline{C}_{A}:=(n_{\max}\sum_{i=1}^{K}C^{i}_{A})^{L},$
$n_{\max}=\max_{l\in[L]}n_{l}$, and $P_{1}$ is a constant depending on $K,L$.

Furthermore, we can invoke the triangle inequality to compare outputs of
graphop neural networks built from two different discretizations of $A$. For
any $m,n\in\mathcal{N}$,

$\displaystyle d_{M}(\Phi(h,A_{m},\cdot),\Phi(h,A_{n},\cdot))\leq$
$\displaystyle
P_{1}\sqrt{\overline{C}_{A}C_{v}}\left(m^{-\frac{1}{2}}+n^{-\frac{1}{2}}\right)+(C_{v}+1)\left(n^{-1}+m^{-1}\right).$
(16)

Compared to the main theorems of Ruiz et al. (2020), there are two main
differences in our results. First, our rate of $O(n^{-1/2})$ is slower than
the rate of $O(n^{-1})$ in Ruiz et al. (2020) as a function of $n$. Yet,
second, their bounds contain a small term that is independent of $n$ and does
not go to $0$ as $n$ goes to infinity. This small term depends on the
variability of small eigenvalues in the spectral decomposition of the
convolution operator associated with a graphon. The bound in Theorem 3, in
contrast, goes to zero.

The proof for this theorem is in Appendix E for a more general Theorem 6. Note
that it does not suffice to simply use the fact that the assumptions play well
with composition with Lipschitz function $\rho$, which would result in a bound
involving $\Phi(h,A,\cdot)$ and its discretization $(\Phi(h,A,\cdot))_{n}$ as
a nonlinear operator, as opposed to a bound between $\Phi(h,A,\cdot)$ and
$\Phi(h,A_{n},\cdot)$.Our proof shares the same structure as that of Theorem 2
while making sure that the mismatch from discretizing/extending operators does
not blow up with composition.

###  4.3 Assumptions

We state and discuss the main assumptions of our $P$-operators, which are not
necessarily linear.

######  Assumption 2 (Lipschitz mapping).

An operator $A:\mathcal{F}\to\mathcal{F}$ is _$C_{A}$ -Lipschitz_ if $\|Af-
Ag\|_{2}\leq C_{A}\|f-g\|_{2}$ for any $f,g\in\mathcal{F}$.

We have already had a finite bound on the operator norm in the definition of
$P$-operators. For linear operators, Assumption 2 is equivalent to a bounded
operator norm and is thus automatically satisfied by linear $P$-operators.

The next few assumptions are alternatives; only one needs be satisfied by our
$P$-operators. Intuitively, they are regularity assumptions that ensure the
images of our operator are not too wild and are specifically designed for our
discretizations scheme:

######  Assumption 3.A (Maps constant pieces to constant pieces).

We say that an operator $A:\mathcal{F}\to\mathcal{F}$ _maps constant pieces to
constant pieces_ at resolutions in $\mathcal{N}\subset\mathbb{N}$ if for any
$n\in\mathcal{N}$, and for any $f\in\mathcal{F}_{[-1,1]}$ that is a.e.
constant on each interval $(u-1/n,u]$ for $u\in[n]/n$, $Af$ is also constant
on $(u-1/n,u]$ for each $u$.

######  Assumption 3.B (Maps Lipschitz functions to Lipschitz functions).

We say that an operator $A:\mathcal{F}\to\mathcal{F}$ _maps Lipschitz
functions to Lipschitz functions with high probability_ at resolutions in
$\mathcal{N}\subset\mathbb{N}$ if for any $n\in\mathcal{N}$, and for any
$f\in\mathcal{F}_{\text{reg}(C_{v})}$, $Af$ is $C_{v}$-Lipschitz.

This is so far the most restrictive assumption. However, the next lemma
describes some dense, sparse and intermediate graphs that satisfy these
assumptions.

######  Lemma 2 (Well-behaved operators).

The following examples satisy our assumptions:

  1. 1.

_Bounded-degree graphings:_ Let $G$ be a graphing corresponding to the Cayley
graph of $\mathbb{Z}$ (two-way infinite paths) or high-dimensional
generalizations (infinite 2D and 3D grids). For each $N\in\mathbb{N}$, there
exists a locally equivalent graphing $G^{\prime}_{N}$ such that its adjacency
operator satisfies Assumption 3.A with resolution set $\\{x\in\mathbb{N}:x\mid
N\\}$.

  2. 2.

_Lipschitz graphons:_ Let $W$ be a $C_{v}$-Lipschitz graphon on
$\mathcal{F}_{\text{reg}(C_{v})}$. Then the Hilbert-Schmidt operator
$f\mapsto\int_{0}^{1}W(\cdot,y)g(y)\textup{d}y$ satisfies Assumption 3.B with
resolution set $\mathbb{N}$.

  3. 3.

_Intermediate graphs:_ Let $G$ be a (potentially infinite) graph with a
coloring $C:V(G)\to[N]$ for some $N$ such that for each vertex $u,v$ with the
same color, the multisets of their neighbors’ colors
$\\{C(u^{\prime}):(u^{\prime},u)\in E\\}$ are the same. Then its adjacency
operator satisfies Assumption 3.A with resolution $N$. An $N$-d hypercube
(more generally, Hamming graphs) which is neither bounded-degree nor dense,
satisfies the above condition with resolutions in $\\{2^{n}\\}_{n\in[N]}$.

All our results also hold with a less restrictive assumption that allows for a
failure of Assumption 3.A and 3.B in a small set (see Assumption 4.A and 4.B
in the Appendix). The most general results are proven in Appendix D and hold
in even slightly more relaxed conditions which require the operators to map
constant pieces to _Lipschitz_ pieces (Assumption 5.A, 5.B in Appendix D).

###  4.4 Deviations and Justifications

All our theorems hold in slightly modified settings than those by Backhausz
and Szegedy (2022). Namely, we allowed for nonlinear $P$-operators, assumed
that they have finite $\|\cdot\|_{2\to 2}$ norm, and used $(k,L)$-profiles
where we focus on Lipschitz functions (while Backhausz and Szegedy (2022)
consider all measurable functions in their profiles). Therefore, we need to
ensure that our changes still give us a useful mode of convergence that
generalizes dense and sparse graph convergences.

First, without the linearity assumption, the convergence proof by Backhausz
and Szegedy (2022) does not hold: we do not know if all limits of nonlinear
graphops are still graphops. However, our approximation results (Theorem 2)
show special convergent sequences of nonlinear operators, which go beyond the
settings in (Backhausz and Szegedy, 2022). Studying special nonlinear operator
sequences is interesting since graphop NNs themselves can be viewed as
nonlinear operators. We also assert that our restriction to operators acting
on $L^{2}$ spaces does not affect convergence guarantees (Theorem 2.14 in
(Backhausz and Szegedy, 2022)).

Next, we show that our restriction to Lipschitz profiles, which is necessary
for our proof technique, does not affect convergence either, if we allow our
Lipschitz constant to grow with the sequence:

######  Theorem 4 (Growing profiles).

Let $L:\mathbb{N}\to\mathbb{R}$ be a strictly increasing sequence such that
$L(n)\xrightarrow{n\to\infty}\infty$. Consider a sequence of $P$-operators
$(A_{n}:\mathcal{F}_{n}\to\mathcal{F}_{n})_{n\in\mathbb{N}}$ that is Cauchy in
the sense that
$d_{M}(A_{n},A_{m})=\sum_{k=1}^{\infty}2^{-k}d_{H}(\mathcal{S}_{k,L(n)}(A_{n}),\mathcal{S}_{k,L(m)}(A_{m}))$
becomes arbitrarily small as $m,n\to\infty$. Then $(A_{n})_{n\in\mathbb{N}}$
converges to the same limit as action convergence.

This theorem allows us to replace the $C_{v}$ constant in our bound with an
extremely slowly growing function in $n$ and get back action convergence as
described in Backhausz and Szegedy (2022) without any realistic slowdown in
the bound.

#### Proof sketch

First, by the completeness of the Hausdorff metric over the closed subsets of
$\mathcal{P}(\mathbb{R}^{2k})$ \- set of probability measures supported on
$\mathbb{R}^{2k}$, for any $k$, the statement is equivalent to showing
$d_{H}(\mathcal{S}_{k}(A),\mathcal{S}_{k,L(n)}(A_{n}))\to 0$ as $n\to\infty$.
The proof uses a Lipschitz mollification argument to smooth out an arbitrary
measurable functions $f_{1},\ldots,f_{k}$ that witness a measure in the
$k$-profile of $A$ for some $k\in\mathbb{N}$. By selecting a Lipschitz
mollifier $\phi$, we ensure that convolving $f_{j}$ with
$\phi_{\epsilon}:x\mapsto\epsilon^{-1}\phi(x\epsilon^{-1})$ results in a
Lipschitz function that converges to $f$ in $L^{2}$ as $\epsilon$ goes to $0$.

##  5 Discussion and Future directions

In this paper, we study size transferability of finite GNNs on graphs that are
discretizations of graphop, a recent notion of graph limit introduced by
Backhausz and Szegedy (2022). We achieve this by viewing GNNs as operators
that transform one graph signal into another. Under regularity assumptions, we
proved that two GNNs, using two different-resolution GSOs discretized from the
same graphop, are close in an operator metric built from weak convergence of
measures.

For future direction, a principled study of spectral properties of graphops
and graphop neural networks would open doors for techniques from Fourier
analysis as used in (Ruiz et al., 2020; Levie et al., 2022). This leads to
distinct challenges, e.g., the spectral gap is not continuous with respect to
local-global limits and thus action convergence, but many more properties of
spectral measures of bounded-degree graphs are recently studied (Virag, 2018).

## References

  * Abboud et al. (2021) R. Abboud, I. I. Ceylan, M. Grohe, and T. Lukasiewicz.  The surprising power of graph neural networks with random node initialization.  In _International Joint Conference on Artificial Intelligence (IJCAI)_ , 2021.
  * Albert and Barabási (2002) Réka Albert and Albert-László Barabási.  Statistical mechanics of complex networks.  _Rev. Mod. Phys._ , 74:47–97, Jan 2002.  doi: 10.1103/RevModPhys.74.47.  URL https://link.aps.org/doi/10.1103/RevModPhys.74.47.
  * Aldous and Lyons (2007) David Aldous and Russell Lyons.  Processes on Unimodular Random Networks.  _Electronic Journal of Probability_ , 12(none):1454 – 1508, 2007.  doi: 10.1214/EJP.v12-463.  URL https://doi.org/10.1214/EJP.v12-463.
  * Azizian and Lelarge (2021) W. Azizian and M. Lelarge.  Expressive power of invariant and equivariant graph neural networks.  In _Int. Conf. on Learning Representations (ICLR)_ , 2021.
  * Backhausz and Szegedy (2022) Ágnes Backhausz and Balázs Szegedy.  Action convergence of operators and graphs.  _Canadian Journal of Mathematics_ , 74(1):72–121, 2022.  doi: 10.4153/S0008414X2000070X.
  * Benjamini and Schramm (2001) Itai Benjamini and Oded Schramm.  Recurrence of Distributional Limits of Finite Planar Graphs.  _Electronic Journal of Probability_ , 6(none):1 – 13, 2001.  doi: 10.1214/EJP.v6-96.  URL https://doi.org/10.1214/EJP.v6-96.
  * Bronstein et al. (2017) Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: Going beyond euclidean data.  _IEEE Signal Processing Magazine_ , 34(4):18–42, 2017.  doi: 10.1109/MSP.2017.2693418.
  * Chen et al. (2020) Z. Chen, L. Chen, S. Villar, and J. Bruna.  Can graph neural networks count substructures?  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Chuang and Jegelka (2022) C. Chuang and S. Jegelka.  Tree mover’s distance: Bridging graph metrics and stability of graph neural networks.  In _Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Garg et al. (2020) V. K. Garg, S. Jegelka, and T. Jaakkola.  Generalization and representational limits of graph neural networks.  In _Int. Conference on Machine Learning (ICML)_ , 2020.
  * Gilmer et al. (2017) Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl.  Neural message passing for quantum chemistry.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, page 1263–1272. JMLR.org, 2017.
  * Jegelka (2022) S. Jegelka.  Theory of graph neural networks: Representation and learning.  In _Proc. of the International Congress of Mathematicians (ICM)_ , 2022.
  * Keriven et al. (2020) Nicolas Keriven, Alberto Bietti, and Samuel Vaiter.  Convergence and stability of graph convolutional networks on large random graphs.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc.  ISBN 9781713829546.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/forum?id=SJU4ayYgl.
  * Levie et al. (2022) Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok.  Transferability of spectral graph convolutional neural networks.  _J. Mach. Learn. Res._ , 22(1), jul 2022.  ISSN 1532-4435.
  * Loukas (2020a) A. Loukas.  What graph neural networks cannot learn: depth vs width.  In _Int. Conf. on Learning Representations (ICLR)_ , 2020a.
  * Loukas (2020b) A. Loukas.  How hard is to distinguish graphs with graph neural networks?  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020b.
  * Lovász (2012) László Lovász.  _Large Networks and Graph Limits._ , volume 60 of _Colloquium Publications_.  American Mathematical Society, 2012.  ISBN 978-0-8218-9085-1.
  * Lovász and Szegedy (2006) László Lovász and Balázs Szegedy.  Limits of dense graph sequences.  _Journal of Combinatorial Theory, Series B_ , 96(6):933–957, 2006.  ISSN 0095-8956.  doi: https://doi.org/10.1016/j.jctb.2006.05.002.  URL https://www.sciencedirect.com/science/article/pii/S0095895606000517.
  * Maron et al. (2019) Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman.  Provably powerful graph networks.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , Red Hook, NY, USA, 2019. Curran Associates Inc.
  * Morris et al. (2019) C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proc. AAAI Conference on Artificial Intelligence (AAAI)_ , 2019\.
  * Roddenberry et al. (2022) T. Mitchell Roddenberry, Fernando Gama, Richard G. Baraniuk, and Santiago Segarra.  On local distributions in graph signal processing.  _IEEE Transactions on Signal Processing_ , 70:5564–5577, 2022.  doi: 10.1109/TSP.2022.3223217.
  * Ruiz et al. (2020) Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro.  Graphon neural networks and the transferability of graph neural networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 33, pages 1702–1712. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/12bcd658ef0a540cabc36cdf2b1046fd-Paper.pdf.
  * Scarselli et al. (2009) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  _IEEE Transactions on Neural Networks_ , 20(1):61–80, 2009.  doi: 10.1109/TNN.2008.2005605.
  * Virag (2018) Balint Virag.  Operator limits of random matrices.  2018\.  doi: 10.48550/ARXIV.1804.06953.  URL https://arxiv.org/abs/1804.06953.
  * Xu et al. (2019) K. Xu, W. Hu, J. Leskovec, and S. Jegelka.  How powerful are graph neural networks?  In _Int. Conf. on Learning Representations (ICLR)_ , 2019.
  * Xu et al. (2020) Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka.  What can neural networks reason about?  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=rJxbJeHFPS.
  * Xu et al. (2021) Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka.  How neural networks extrapolate: From feedforward to graph neural networks.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=UH-cmocLJC.
  * Yehudai et al. (2021) G. Yehudai, E. Fetaya, E. Meirom, G. Chechik, and H. Maron.  From local structures to size generalization in graph neural networks.  In _Int. Conference on Machine Learning (ICML)_ , 2021.

##  Appendix A Additional notation and assumptions

###  A.1 Notation

We will use the following extra notations in the proof:

  1. 1.

For some $P$-operator $A\in L^{2}(\Omega)\to L^{2}(\Omega)$, $k\in\mathbb{N}$
and $\\{f_{1},\ldots,f_{k}\\}=:F\subset L^{2}(\Omega)$, let $F_{A}$ be the
ordered $2k$-tuple $(f_{1},\ldots,f_{k},Af_{1},\ldots,Af_{k})$ and denote

$F_{A}(x):=(f_{1}(x),\ldots,f_{k}(x),Af_{1}(x),\ldots,Af_{k}(x))\in\mathbb{R}^{2k.}$

  2. 2.

For some $P$-operator $A\in L^{2}(\Omega)\to L^{2}(\Omega)$, $k\in\mathbb{N}$
and $\\{f_{1},\ldots,f_{k}\\}=:F\subset L^{2}(\Omega)$, let
$\mathcal{D}_{A}(F)$ be the entry distribution
$\mathcal{D}(f_{1},\ldots,f_{k},Af_{1},\ldots,Af_{k})$ .

#### Cut norm and cut metric

Here we define concretely the cut metric over the space of graphons. Recall
that graphons are $L^{1}([0,1],\mathcal{F},\lambda)$ Lebesgue-integrable
functions. The space of graphons is equipped with a norm known as the _cut
norm_ :

$\|W\|_{\square}:=\sup_{S,T\in\mathcal{F}}\left|\int_{S\times
T}W(x,y)\textup{d}\lambda(x)\textup{d}\lambda(y)\right|,$ (17)

and a metric known as the _cut metric_ :

$d_{\square}(W_{1},W_{2}):=\inf_{\phi}\|W_{1}-W_{2}\circ\phi\|_{\square},$
(18)

where $\phi$ is taken over all measure-preserving bijections from $[0,1]$ to
$[0,1]$. Intuitively, taking the $\inf$ over all measure-preserving bijections
allows the cut metric to identify graphons that are just a rearrangement away
from another. This generalizes symmetries in graphs, where permuting the
vertices (and the corresponding edges) do not change the graph itself. Lovász
(2012) shows that graphon convergence under the cut metric is well-behaved:
every graphon is a limit of a convergent sequence of graphons; and every
Cauchy sequences converges to a graphon. This mode of convergence is known as
dense graph convergence.

#### Lévy-Prokhorov metric

The definition of Lévy-Prokhorov metric on $\mathcal{P}(\mathbb{R}^{2k})$ is:

$\displaystyle
d_{LP}(\eta_{1},\eta_{2}):=\inf\\{\epsilon>0:\eta_{1}(U)\leq\eta_{2}(U^{\epsilon})+\epsilon\wedge\eta_{2}(U)\leq\eta_{1}(U^{\epsilon})+\epsilon,\forall
U\in\mathcal{B}_{2k}\\},$

where $\mathcal{B}_{2k}$ is the Borel $\sigma$-algebra generated from open
subsets of $\mathbb{R}^{2k}$ and $U^{\epsilon}:=\\{y:\exists
x\in\mathbb{R}^{2k}\|x-y\|_{2}<\epsilon\\}$.

###  A.2 Assumptions

As mentioned in the main text, we will work with the following slightly less
restrictive set of Assumptions.

######  Assumption 4.A (Maps constant pieces to constant pieces with high
probability).

We say that an operator $A:\mathcal{F}\to\mathcal{F}$ _maps constant pieces to
constant pieces whp_ at resolutions in $\mathcal{N}\subset\mathbb{N}$ if there
exists a set $E\subset[0,1]$ with Lebesgue measure
$\lambda(E)<\inf_{n\in\mathcal{N}}1/n$, such that for any $n\in\mathcal{N}$,
and for any $f\in\mathcal{F}_{[-1,1]}$ that is a.e. constant on each interval
$(u-1/n,u]$ for $u\in[n]/n$, $Af$ is constant on $(u-1/n,u]\backslash E$ and
$\|Af\mathbbm{1}_{E}\|_{1}<\inf_{n\in\mathcal{N}}\frac{1}{n}$.

######  Assumption 4.B (Maps Lipschitz functions to Lipschitz functions with
high probability).

We say that an operator $A:\mathcal{F}\to\mathcal{F}$ _maps Lipschitz
functions to Lipschitz functions whp_ at resolutions in
$\mathcal{N}\subset\mathbb{N}$ if there exists a set $E\subset[0,1]$ with
$\lambda(E)<\inf_{n\in\mathcal{N}}1/n$, such that for any $n\in\mathcal{N}$,
and for any $f\in\mathcal{F}_{[-1,1]}$, $Af$ is $C_{v}$ Lipschitz on
$[0,1]\backslash E$ and
$\|Af\mathbbm{1}_{E}\|_{1}<\inf_{n\in\mathcal{N}}\frac{1}{n}$.

######  Assumption 5.A (Maps constant pieces to Lipschitz pieces).

We say that an operator $A:\mathcal{F}\to\mathcal{F}$ _maps constant pieces to
Lipschitz pieces_ at resolutions in $\mathcal{N}\subset\mathbb{N}$ and
constant $C$ if for any $n\in\mathcal{N}$, and for any
$f\in\mathcal{F}_{[-1,1]}$ that is a.e. constant on each interval $(u-1/n,u]$
for $u\in[n]/n$, we have that $Af$ is $C$-Lipschitz on each $(u-1/n,u]$, for
all $u\in[n]/n$.

######  Assumption 5.B (Maps constant pieces to Lipschitz pieces with high
probability).

We say that an operator $A:\mathcal{F}\to\mathcal{F}$ _maps constant pieces to
Lipschitz pieces whp_ at resolutions in $\mathcal{N}\subset\mathbb{N}$ and
constant $C$ if for any $n\in\mathcal{N}$, there exists a set $E\subset[0,1]$
with $\lambda(E)<\frac{1}{n}$ such that for any $f\in\mathcal{F}_{[-1,1]}$
that is a.e. constant on each interval $(u-1/n,u]$ for $u\in[n]/n$, it holds
that $Af$ is $C$-Lipschitz on each $(u-1/n,u]\backslash E$, for all
$u\in[n]/n$ and $\|Af\mathbbm{1}_{E}\|_{1}<\inf_{n\in\mathcal{N}}\frac{1}{n}$.

##  Appendix B Omitted proofs from Section 3

###### Proof of Lemma 1.

Fix $m\in\mathbb{N}$ and $f,g\in\mathcal{F}_{m}$. Since $P$-operators are
bounded, to show that they are self-adjoint, it suffices to show that
$\left\langle A_{m}f,g\right\rangle=\left\langle f,A_{m}g\right\rangle$ where
$\left\langle\cdot,\cdot\right\rangle$ is the usual inner product in the
Hilbert space $\mathcal{F}_{m}$. We have:

$\displaystyle\left\langle A_{m}f,g\right\rangle$ $\displaystyle=\sum_{u\in
1/m[m]}(A_{m}f)(u)g(u)$ (19) $\displaystyle=\sum_{u\in
1/m[m]}\int_{u-\frac{1}{m}}^{u}Af^{\prime}\textup{d}\lambda\cdot g(u)$ (20)
$\displaystyle=\sum_{u\in
1/m[m]}\int_{u-\frac{1}{m}}^{u}(Af^{\prime})g^{\prime}\textup{d}\lambda=\int_{0}^{1}(Af^{\prime})g^{\prime}\textup{d}\lambda$
(21) $\displaystyle=\int_{0}^{1}f^{\prime}(Ag^{\prime})\textup{d}\lambda$ (22)
$\displaystyle=\sum_{u\in
1/m[m]}\int_{u-\frac{1}{m}}^{u}f^{\prime}(Ag^{\prime})\textup{d}\lambda=\left\langle
f,Ag\right\rangle,$ (23)

where the first line is the definition of the inner product in
$\mathcal{F}_{m}$, the second line is the definition of the discretization
$A_{m}$ (recall that for $f\in\mathcal{F}_{m}$, $f^{\prime}\in\mathcal{F}$ is
the extension of $f$ defined as $f^{\prime}(x)=f(\left\lceil
xm\right\rceil/m)$), the third line is because $g^{\prime}$ is constant on
fixed $[u-1/m,u]$ intervals for each $u$ and the fourth line is because $A$ is
self-adjoint. ∎

##  Appendix C Theory of graphings

In this subsection, we highlight definitions and key characteristics of
graphings so that the paper is self-contained. A much more in-depth discussion
can be found in Lovász (2012).

######  Definition 1 (Borel graphs).

Let $\Omega$ be a topological space and $(\Omega,\mathcal{F})$ be the
corresponding Borel space. A _Borel graph_ is a graph $(\Omega,E)$ such that
$E\in\mathcal{F}\times\mathcal{F}$.

The following proposition asserts that bounded-degree graphs without
automorphisms are always Borel:

######  Lemma 3 (Proposition 18.6 from Lovász (2012)).

If $G$ is a bounded-degree graph without automorphisms then there exists a
topology $\tau$ on $V(G)$ (called the _local topology_) such that $G$ is Borel
with respect to the Borel space built from $\tau$.

When the graph does have automorphisms, one can break the symmetries by
coloring the nodes with some set of colors (the fact that the graph has
bounded degree means that one only needs finitely many colors).

We next introduce the main object of interest:

######  Definition 2 (Graphings).

A _graphing_ is a quadruple $G=(\Omega,\mathcal{F},\lambda,E)$ such that
$\mathcal{F}$ is a Borel $\sigma$-algebra that makes $(\Omega,E)$ a Borel
graph, and $\lambda$ is a probability measure on $(\Omega,\mathcal{F})$
satisfying: for any $A,B\in\mathcal{F}$,

$\int_{A}\text{deg}_{B}(x)\textup{d}\lambda(x)=\int_{B}\text{deg}_{A}(x)\textup{d}\lambda(x),$
(24)

where $\text{deg}_{A}(x)$ counts the number of neighbors in $A$ of $x$.

As an example, we now describe paths and cycles in terms of graphings: let $V$
be $[0,1]$, $\mathcal{F}$ the Borel $\sigma$-algebra generated by open
intervals with rational endpoints and for each $x\in[0,1]$, put $(x,x\pm a)$
in $E$ if $x\pm a\in[0,1]$ for some real number $a<1$. For $a<\frac{1}{2}$,
each connected component of the graphing is a finite path. If we consider the
edge set $(x,x\pm a\mod 1)$ for rational $a$, then it is not hard to see that
connected components of the graphing are finite cycles. If $a$ is irrational,
then the resulting graphing is a two-way infinite path, i.e., a path with no
“beginning” and no “end”. A formal argument, with an appropriate metric on the
space of graphings, can be made to show that the limit of cycles and paths
coincides to be the two-way infinite path.

Graphings are not unique in representing certain graphs. There are weak
equivalences between pairs of graphings that are formalized through the notion
of local isomorphisms.

######  Definition 3 (Local isomorphisms of graphings).

Let $G_{1}$, $G_{2}$ be two graphings. A measure-preserving map
$\varphi:V(G_{1})\to V(G_{2})$ is a _local isomorphism_ if its restriction to
almost every connected component of $G_{1}$ (outside of a set of connected
component of measure $0$) is a graph isomorphism with one of the connect
components of $G_{2}$. More formally,

$\Pr_{\lambda(G_{1})}((G_{1})_{x}\equiv(G_{2})_{\varphi(x)})=1,$ (25)

where $\equiv$ is rooted graph isomorphism and $(G_{1})_{x}$ is the connected
component of $G_{1}$ rooted at $x$.

Note that local isomorphism of graphings are not symmetric and the map
$\varphi$ needs not be invertible. A stronger notion of equivalence, which is
symmetric and transitive is local equivalence:

######  Definition 4 (Local equivalence (informal)).

$G_{1}$ and $G_{2}$ are locally equivalent if they have the same subgraph
densities $t^{*}(F,G_{1})=t^{*}(F,G_{2})$ for every connected simple graph
$F$.

The above definition is informal since we have not defined subgraph densities
(which is done via the Benjamini-Schramm interpretation of graphings). We
state Definition 4 for readers who are familiar with dense graph convergence
of graphons since this is how such convergences are defined. In fact, we can
conveniently bypass formally defining local equivalence by the following
characterization:

######  Lemma 4 (Bi-local isomorphism (Theorem 18.59 in Lovász (2012))).

Two graphings are locally equivalent iff there is a third graphing with a
local isomorphism to each of them - a property called _bi-local isomorphism_.

##  Appendix D Omitted proofs from Section 4

###  D.1 Proof of Lemma 2

We prove each bullet point in Lemma 2 separately, in the next three lemmas.

In the following lemma, we show that graphings corresponding to infinite paths
and high dimensional grids satisfy the assumptions in the main results.
Similar to how isomorphic graphs represent the same graph, we only need to
specify a locally isomorphic graphing that represent the equivalence class of
graphings containing the infinite path and high dimensional grids.

######  Lemma 5 (Well-behaved GSOs - Graphings).

Let $G$ be a graphing corresponding to the Cayley graph of $\mathbb{Z}$ (two-
way infinite paths) or high-dimensional generalizations (infinite 2D and 3D
grids). For a graphing $H$, let $A(H)$ be its adjacency operator. If $H$ is
regular, let $\text{deg}(H)$ be the degree of any of its vertices. For each
$N\in\mathbb{N}$, there exists locally equivalent graphings:

  1. 1.

$G^{\prime}_{N}$ such that $A(G^{\prime}_{N})$ satisfies Assumption 3.A with
resolution set $d(N)=\\{x\in\mathbb{N}:x=\alpha N\text{ for some
}\alpha\in\mathbb{N}\\}$.

  2. 2.

$G^{\prime\prime}_{N}$ such that $A(G^{\prime\prime}_{N})$ satisfies
Assumption 4.A with resolution set $[N]$.

  3. 3.

$G^{\prime\prime\prime}_{N}$ such that
$A(G^{\prime\prime\prime}_{N})/\text{deg}(G)$ satisfies Assumption 4.B with
resolution set $[N]$.

###### Proof of Lemma 5.

We will first show the results for two-way infinite paths. Higher dimensional
versions follow almost verbatim. Fix $a\in\mathbb{R}\backslash\mathbb{Q}$
irrational. Recall from Lovász (2012) that the graphing
$G=([0,1],\mathcal{F},\lambda,E)$ where $\mathcal{F}$ is the Borel
$\sigma$-algebra generated by open intervals with rational endpoints,
$\lambda$ is some probability measure on $([0,1],\mathcal{F})$ and
$E\in\mathcal{F}\times\mathcal{F}$ is defined as:

$E:=\\{(x,x\pm a\mod 1)\mid x\in[0,1]\\}.$ (26)

That $G$ is a graphing and each of its connected components is a copy of the
Cayley graph of $\mathbb{Z}$ generated by $\\{-1,1\\}$ is asserted in Lovász
(2012).

  1. 1.

Fix $N\in\mathbb{N}$, the goal is to define a graphing $G^{\prime}_{N}$ that
is locally equivalent to $G$ such that $A(G^{\prime}_{N})$ satisfies
Assumption 3.A with resolution set $d(N)$ \- the divisor set of $N$.

#### Defining $G^{\prime}_{N}$.

Let $G^{\prime}_{N}:=([0,1],\mathcal{F},\lambda,E^{\prime}_{N})$ where,

$E^{\prime}_{N}:=\left\\{\left(x_{j},j-\frac{1}{N}+\left(x_{j}\pm\frac{a}{N}\mod\frac{1}{N}\right)\right):j\in[N]/N,x_{j}\in\left[j-\frac{1}{N},j\right)\right\\}.$
(27)

Intuitively, $G^{\prime}_{N}$ consists of $N$ disjoint copies of $G$ shrunk to
the space $[0,1/N)$. Since $E\subset[0,1]\times[0,1]$, $G^{\prime}_{N}$ is a
graphing in the same Borel space as $G$.

####  $G^{\prime}_{N}$ is locally equivalent to $G$.

From Lemma 4 it suffices to display a local isomorphism from a third graphing
to each of them. Let $G^{\prime}_{2N}$, defined similarly as $G^{\prime}_{N}$,
be the third graphing. We claim that $\varphi_{1}:x\mapsto 2x\mod 1$ is a
local isomorphism from $G^{\prime}_{2N}$ to $G^{\prime}_{N}$ and
$\varphi_{2}:x\mapsto 2Nx\mod 1$ is a local isomorphism from $G^{\prime}_{2N}$
to $G$. Intuitively, $G^{\prime}_{2N}$ contains $2N$ copies of $G$ while
$G^{\prime}_{N}$ contains $N$ copies of $G$. Thus, our local isomorphisms only
need to make sure that a connected component in one copy of $G$ in
$G^{\prime}_{N}$ is mapped bijectively to a connected component in another
copy of $G$ in $G^{\prime}_{2N}$. We give a rigorous argument below.

For $x$ picked randomly according to $\lambda$, let $j\in[2N]/(2N)$ be such
that $x\in[j-1/(2N),j)$. By definition of $G^{\prime}_{2N}$, the connected
component $(G^{\prime}_{2N})_{x}$ consists of vertices of the form

$v(k)=j-\frac{1}{2N}+\left(x\pm ak/(2N)\mod 1/(2N)\right),$

for some $k\in\mathbb{Z}$ and there is an edge from $v(k)$ to $v(k\pm 1)$.
Consider $\varphi_{1}(x)=2x\mod 1$ that sends $v(k)$ to

$\varphi_{1}(v(k)):=\left(2j-\frac{1}{N}+\left(2x\pm\frac{ak}{N}\mod\frac{1}{N}\right)\right)\mod
1.$

Now consider the connected component of $\varphi_{1}(x)=2x\mod 1$ in
$G^{\prime}_{N}$. Since
$x\in[j-\frac{1}{2N},j),\varphi_{1}(x)\in[j^{\prime}-1/N,j^{\prime})$ where
$[N]/N\ni j^{\prime}:=2j\mod\frac{1}{N}$. Thus, the connected component of
$(G^{\prime}_{N})_{\varphi_{1}(x)}$ consists of vertices of the form:

$\displaystyle v^{\prime}(k)$
$\displaystyle:=j^{\prime}-\frac{1}{N}+\left(\varphi_{1}(x)\pm ak/N\mod
1/N\right)$ (28)
$\displaystyle=\left(2j\mod\frac{1}{N}\right)-\frac{1}{N}+\left((2x\mod
1)\pm\frac{ak}{N}\mod\frac{1}{N}\right).$ (29)

With some modulo arithmetic manipulation, it is not hard to see that
$\varphi_{1}(v(k))=v^{\prime}(k)$ for all $k\in\mathbb{Z}$. By definition of
$G^{\prime}_{N}$, there is an edge $(v^{\prime}(k),v^{\prime}(k\pm 1))$.
Therefore, there is an edge $(\varphi_{1}(v(k)),\varphi_{1}(v(k\pm 1)))$. If
$\lambda$ is the uniform measure then we can ignore vertices at the endpoints
of our intervals ( points in $[N]/N$ ) and conclude that
$(G^{\prime}_{2N})_{x}\equiv(G^{\prime}_{N})_{\varphi_{1}(x)}$ with
probability $1$ when $x\sim\lambda$.

Now consider $\varphi_{2}(x)=2Nx\mod 1$ that sends $v(k)$ to:

$\varphi_{2}(v(k)):=\left(2Nj-1+\left(2Nx\pm ak\mod 1\right)\right)\mod 1.$
(30)

The connected component of $\phi_{2}(x)$ in $G$ is in $[0,1]$ and consists of
vertices of the form:

$\displaystyle v^{\prime\prime}(k)$ $\displaystyle:=(2Nj-1\mod 1)+(2Nx\pm
ak\mod 1).$ (31)

Thus $v^{\prime\prime}(k)=\varphi_{2}(v(k))$ for each $k\in\mathbb{Z}$ and the
definition of $G$ implies that $(G^{\prime}_{2N})_{x}\equiv
G_{\varphi_{2}(x)}$ since both are isomorphic to the two-way infinite path. If
$\lambda$ is the uniform measure then the above hold for a.e. $x\in[0,1]$.

####  $G^{\prime}_{N}$ satisfies Assumption 3.A with resolution set $d(N)$.

Let $D$ be a divisor of $N$, then $D\alpha=N$ for some $\alpha\in\mathbb{N}$.
The intuition is rather straightforward, since $D$ is a divisor of $N$, the
partition into $N$ equal intervals of $[0,1]$ is simply a finer partition into
$D$ equal intervals. By construction, a vertex $x$ of $G^{\prime}_{N}$ only
has neighbors in the $1/N$ interval containing it. Therefore, if $f$ is
constant on each of the $D$ pieces, it is also constant on each of the $N$
pieces and $f(y)=f(x)=f(x^{\prime})=f(y^{\prime})$ for any
$(x,y),(x^{\prime},y^{\prime})$ neighbors such that $x$ and $x^{\prime}$ come
from the same $1/D$ pieces.

Here is a more formal argument. Fix $f\in\mathcal{F}_{[-1,1]}$ that is a.e.
constant on each interval $(u-1/d,u]$ for $u\in[D]/D$. We need to show that
$A(G^{\prime}_{N})f$ is a.e. constant on the same pieces where $A(H)$ is the
adjacency operator of a regular graphing $H$. Fix $d\in[D]$, fix
$x,x^{\prime}\in[d-1/D,d)$. Let $j$ be such that $x\in[j-1/N,j)$ and
$j^{\prime}$ be such that $x^{\prime}\in[j^{\prime}-1/N,j^{\prime})$. Since
$D\alpha=N$, we have
$[j-1/N,j),[j^{\prime}-1/N,j^{\prime})\subseteq[d-1/D,d)$. Furthermore, by
definition of $G^{\prime}_{N}$, all neighbors of $x$ and $x^{\prime}$ are in
$[j-1/N,j)$ and $[j^{\prime}-1/N,j^{\prime})$ respectively, and thus in
$[d-1/D,d)$. Therefore,
$A(G^{\prime}_{N})f(x)=2f(x)=2f(x^{\prime})=A(G^{\prime}_{N})f(x^{\prime})$
for all $x,x^{\prime}\in[d-1/D,d)$, which means that $A(G^{\prime}_{N})f$ is
constant on each of the pieces $[d-1/D,d)$ for each $d\in[D]$.

  2. 2.

Fix $N\in\mathcal{N}$, the goal is to define a graphing $G^{\prime\prime}_{N}$
that is locally equivalent to $G$ such that $A(G^{\prime\prime}_{N})$
satisfies Assumption 4.A with resolution set $[N]$.

Since $\mathbb{Q}$ is dense in $\mathbb{R}$, there exists a number
$\delta(N)<\frac{1}{4N^{2}}$ such that $\frac{1}{4N^{2}}+\delta(N)$ is an
irrational number. Let
$G^{\prime\prime}_{N}=([0,1],\mathcal{F},\lambda,E^{\prime\prime}_{N})$ where,

$\displaystyle
E^{\prime\prime}_{N}:=\left\\{\left(x,x\pm\left(\frac{1}{4N^{2}}+\delta(N)\right)\mod
1\right):x\in[0,1]\right\\}.$ (32)

That $G^{\prime\prime}_{N}$ is locally equivalence to $G$ is easily seen via
the ambiguity of selecting $a$ when defining $G$. Now we show that
$A(G^{\prime\prime}_{N})$ satisfies Assumption 4.A with resolution set $[N]$.
Pick $M\leq N$ and $f\in\mathcal{F}_{[-1,1]}$ that is a.e. constant on each
pieces $(m-1/M,m]$ for each $m\in[M]/M$. Let

$E=\bigcup_{m\in[M]/M}\left(m-\frac{1}{4N^{2}}-\delta(N),m+\frac{1}{4N^{2}}+\delta(N)\right]$

then

$\lambda(E)=\sum_{m^{\prime}=1}^{M}2(1/(4N^{2})+\delta(N))\leq\frac{M}{N^{2}}<\frac{1}{N}.$

Pick $x,x^{\prime}\in(m-1/M,m]\backslash E$ then
$x,x^{\prime}\in(m-1/M+\epsilon,m-\epsilon]$ where
$\epsilon=1/(4N^{2})+\delta(N)$. Thus we have both $x\pm\epsilon$ and
$x^{\prime}\pm\epsilon$ are in $(m-1/M,m]$. By definition of
$G^{\prime\prime}_{N}$, all neighbors of $x$ and $x^{\prime}$ are in the same
$1/M$ piece as $x$ and $x^{\prime}$. Therefore, if $f\in\mathcal{F}_{[-1,1]}$
are constant on these pieces, so is $Af$.

  3. 3.

Fix $N\in\mathcal{N}$, the goal is define a graphing
$G^{\prime\prime\prime}_{N}$ that is locally equivalent to $G$ such that
$A(G^{\prime\prime\prime}_{N})$ satisfies Assumption 4.B with resolution set
$[N]$.

Since $\mathbb{Q}$ is dense in $\mathbb{R}$, there exists a number
$\delta(N)<1/(4N)$ such that $1/(4N)+\delta(N)$ is an irrational number. Let
$G^{\prime\prime\prime}_{N}=([0,1],\mathcal{F},\lambda,E^{\prime\prime\prime}_{N})$
where

$E^{\prime\prime\prime}_{N}:=\left\\{\left(x,x\pm\left(\frac{1}{4N}+\delta(N)\right)\mod
1\right):x\in[0,1]\right\\}$ (33)

That $G^{\prime\prime\prime}_{N}$ is locally equivalent to $G$ is easily seen
via the ambiguity of selecting $a$ when defining $G$. Now we show that
$A(G^{\prime\prime\prime}_{N})$ satisfies Assumption 4.B with resolution set
$[N]$. Pick $M\leq N$ and $f\in\mathcal{F}_{\text{reg}(C_{v})}$ that is a.e.
$C_{v}$-Lipschitz on $[0,1]$. Set $\epsilon=\frac{1}{4N}+\delta(N)$ and let:

$E=[0,\epsilon)\cup[1-\epsilon,1).$ (34)

Then $\lambda(E)=2\epsilon<\frac{1}{N}$. Pick $x,x^{\prime}\in[0,1]\backslash
E$, then $x\pm\epsilon$ and $x^{\prime}\pm\epsilon$ do not ‘loop over’ in the
interval $[0,1]$ ( $y\mod 1=y$, for $y\in\\{x,x^{\prime}\\}+\\{\pm\epsilon\\}$
). Thus we have:

$\displaystyle\left|Af(x)-Af(x^{\prime})\right|$
$\displaystyle=\frac{\left|f(x+\epsilon)+f(x-\epsilon)-f(x^{\prime}+\epsilon)-f(x^{\prime}-\epsilon)\right|}{2}$
(35)
$\displaystyle\leq\frac{|f(x+\epsilon)-f(x^{\prime}+\epsilon)|+|f(x-\epsilon)-f(x^{\prime}-\epsilon)|}{2}$
(36) $\displaystyle\leq C_{v}|x-x^{\prime}|,$ (37)

where in the last line we use Lipschitz property of $f$. This finishes the
proof.

∎

######  Lemma 6 (Well-behaved operators - Graphons).

Let $W:[0,1]^{2}\to[0,1]$ be a Lipschitz graphon, with Lipschitz constant $C$.
In other words, $W$ has finite $L^{2}$ norm and is Lipschitz in both
variables. Then the Hilbert-Schmidt integral operator $H$ that defines the
adjacency operator of $W$ satisfies Assumption 3.B at any resolution when
applied to graph(on) signal $f$ with $L^{1}$ norm $1$.

###### Proof.

The proof follows from definition. Take $f\in L^{2}([0,1])$ such that
$\|f\|_{L^{2}}=1$, then:

$\displaystyle|Hf(x)-Hf(y)|$
$\displaystyle=\left|\int_{0}^{1}W(x,z)f(z)\textup{d}z-\int_{0}^{1}W(y,z)f(z)\textup{d}z\right|$
(38)
$\displaystyle\leq\int_{0}^{1}\left|W(x,z)-W(y,z))\right|\cdot|f(z)|\textup{d}z$
(39) $\displaystyle\leq\int_{0}^{1}C|x-y|\cdot|f(z)|\textup{d}z=C|x-y|,$ (40)

where the first line is definition of the Hilbert-Schmidt operator $H$, the
second line is triangle inequality and the last line is due to Lipschitzness
of $W$ and $L^{1}$ norm of $f$ ∎

######  Lemma 7 (Well-behaved operators - General graphs).

Let $G$ be a (potentially countably infinite) graph with a coloring
$C:V(G)\to[N]$ for some $N$ such that for each vertex $u,v$ with the same
color, the multisets of their neighbors’ colors
$\\{C(u^{\prime}):(u^{\prime},u)\in E\\}$ are the same. Additionally, assume
that the cardinality of vertices of each color is the same: that there is a
bijection from $\\{v:C(v)=c\\}$ to $\\{v:C(v)=c;\\}$ for any colors
$c,c^{\prime}$. Then its adjacency operator satisfies Assumption 3.A with
resolution $N$.

###### Proof.

Given that the cardinality of vertices of each color is the same, it is
straightforward to map (via a Lebsesgue-measure preserving bijection) vertices
of $V$ into equipartition of $[0,1]$ into $N$ pieces $I_{1},...,I_{N}$ such
that each partition contains vertices of the same color and vertices from
different partitions will have different colors. Let $A$ be the normalized
adjacency operator of $G$ and $f$ be a function with finite $L^{2}$ norm such
that $f$ is constant on each $I_{j}$ for each $j$ from $1$ to $N$. The goal is
to show that $Af$ is also constant on these pieces.

We show this by direct computation. Pick a vertex $x$ and another vertex $y$
from the same piece, say $I_{k}$ for some particular $k$. By our construction,
$x$ and $y$ have the same color since they come from the same piece. By our
assumption, the multisets of their neighbors’ colors is the same. However,
since $f$ is constant on each pieces, we have $f(z)=f(u)$ for $u,v$ of the
same color. Therefore, the multisets $\\{f(z):(z,x)\in E\\}$ and
$\\{f(z):(z,y)\in E\\}$ is exactly the same. Taking the appropriate countable
sum over each multiset thus result in the same number, i.e. $Af(x)=Af(y)$,
which finishes the proof. ∎

Note that we can drop the countable requirement of the previous proof by
invoking an appropriate integral definition. Now we show that the hypercubes -
an intermediate graph that is neither dense nor bounded degree, satisfies the
requirements of Lemma 7.

######  Lemma 8 (Well-behaved operators - Hypercubes).

Let $C$ be a hypercube of dimension $N$. Then the normalized adjacency matrix
of $C$ satisfies assumption 3.A with resolutions $2^{[n]}$ for each $n<N$.

###### Proof.

We first display a mapping of the vertices in the hypercube over the interval
$[0,1]$ such that Assumption 3.A will be shown to hold. Recall that a
hypercube vertices can be represented by a binary string of $N$ numbers. Here,
similarly, we will associate a vertex $v$ of a hypercube with a number in
$[0,1]$ by adding a $0.$ in front of its binary representation. For example,
$0.110101$ (as a binary number) is a vertex correspond to the string $110101$
when $N=6$. We call this representation mapping $f:V\to[0,1]$. Two vertices
$u,v$ are connected by an edge iff $f(v)$ and $f(v)$ differs by exactly one
digit in their binary representation.

To get a hypercube representation over the interval $[0,1]$, we simply take
disconnected copies of (uncountably) infinitely many hypercubes described
above. To be more precise, for a number $x\in[0,1]$, let $A(x)$ be the
$N$-letter binary string such that $0.A$ (as a string) is the trunction of $x$
to the $N$-th digit after the binary point. Then, $x$ is connected to
$y\in[0,1]$ iff $A(x)$ and $A(y)$ differs in exactly one digit and
$x-A(x)=y-A(y)$. For example, for $N=4$, we connect $0.110101$ with $0.010101$
, $0.100101$, $0.111101$ and $0.110001$. Notice how the first four digits
after the dots differ from the original number at exactly one letter, and the
last few digits always stay the same. In this example, $A(x)=0.1101$ for
$x=0.110101$.

With this vertex representation in mind, we verify the conditions of Lemma 7.
Let $V$. Fix $n<N$ and divide $[0,1]$ into $2^{n}$ equipartitions and let
vertices in the same partition enjoy the same color. We will also number the
partition/color by the binary representation of their left hand endpoint. For
example, the first interval is labelled $00..0$ ($n$ digits), the second
interval is labelled $00..01$ ($n$ digits). Select a vertex $x$ from a
partition with label $a_{1}a_{2}\ldots a_{n}$. Then, by the definition of our
hypercube representation, the neighbors of $x$ have colors:

  * •

Exactly $1$ neighbor with color $(a_{1}+1\mod 1)a_{2}\ldots a_{n}$.

  * •

Exactly $1$ neighbor with color $a_{1}(a_{2}+1\mod 1)a_{3}\ldots a_{n}$.

  * •

…

  * •

Exactly $1$ neighbor with color $a_{1}a_{2}\ldots a_{n-1}(a_{n}+1\mod 1)$.

  * •

Remaining $N-n$ neighbors all have color $a_{1}a_{2}\ldots a_{n}$.

Therefore, the multiset of neighbors’ colors of $x$ only depends on the fact
that $x$ comes from a partition with label $a_{1}\ldots a_{n}$ and thus, two
vertices of the same color has the same multiset of neighbor’s colors. Since
the condition of Lemma 7 holds, we have the conclusion for this particular
resolution $n$. Since $n$ was chosen arbitrarily, the result holds for every
$n<N$. ∎

In future work, we formalizes the way in which the above proof holds for
limiting object of hypercube.

###  D.2 Proof of Theorem 2

In this section, we prove a slightly more general version of Theorem 2.

######  Theorem 5 (General approximation theorem).

Let $A:\mathcal{F}\to\mathcal{F}$ be a $P$-operator satisfying Assumption 2
with constant $C_{A}$; Assumption 5.A with constant $C_{c}$ and resolutions in
$\mathcal{N}$. Fix $n\in\mathcal{N}$ and consider $(k,C_{v})$-profiles. Let
$A_{n}:\mathcal{F}_{n}\to\mathcal{F}_{n}$ be a discretization of $A$ as
defined in Equation (10). Then:

$d_{M}\left(A,A_{n}\right)\leq
8\left(\sqrt{\frac{C_{A}C_{v}}{n}}+\frac{C_{v}+C_{c}}{n}\right).$ (41)

If instead of Assumption 5.A, $A$ satisfies Assumption 5.B with constant
$C_{c}$ and resolution set $\mathcal{N}$, then:

$d_{M}\left(A,A_{n}\right)\leq
8\left(\sqrt{\frac{C_{A}C_{v}+1}{n}}+\frac{C_{v}+C_{c}+1}{n}\right).$ (42)

If instead of Assumption 5.A and 5.B, $A$ satisfies Assumption 4.B with
resolution set $\mathcal{N}$ then:

$d_{M}\left(A,A_{n}\right)\leq
8\left(\sqrt{\frac{C_{A}C_{v}+1}{n}}+\frac{C_{v}+1}{n}\right).$ (43)

###### Proof of Theorem 2.

Fix $k\in\mathbb{N}$. In order to derive an upper bound for $d_{M}$, we find
an upper bound for the Hausdorff distance $d_{H}$ between the two $k$-profiles
of $A$ and $A_{n}$.

#### Bounding
$\sup_{\eta\in\mathcal{S}_{k,C_{v}}(A)}\inf_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}d_{LP}(\eta,\eta_{n})$.

To bound the $\sup\inf$ quantity, we first select an arbitrary
$\overline{\eta}\in\mathcal{S}_{k,C_{v}}(A)$. From this measure, we will
construct a measure $\overline{\eta}_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})$. If
we can upper bound $d_{LP}(\overline{\eta},\overline{\eta}_{n})<M$ then we
have:

$\inf_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}d_{LP}(\overline{\eta},\eta_{n})\leq
d_{LP}(\overline{\eta},\overline{\eta}_{n})<M,\text{ for all
}\overline{\eta}\in\mathcal{S}_{k,C_{v}}(A).$ (44)

If further $M$ does not depend on the choice of $\overline{\eta}$, then we
have

$\sup_{\eta\in\mathcal{S}_{k,C_{v}}(A)}\inf_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}d_{LP}(\eta,\eta_{n})\leq
M.$

We now proceed with this plan. Fix an arbitrary
$\overline{\eta}\in\mathcal{S}_{k}(A)$, by definition of $k$-profiles, there
is a corresponding tuple $F=(f_{1},\ldots,f_{k})$ with elements in
$\mathcal{F}_{\text{reg}(C_{v})}$ such that
$\mathcal{D}_{A}(F)=\overline{\eta}$.

Form:

$F^{\prime}:=\left\\{\mathcal{F}_{n,\text{reg}(C_{v})}\ni
f^{\prime}_{j}:u\mapsto n\int_{u-1/n}^{u}f_{j}\textup{d}\lambda\mid
j\in[k]\right\\},\qquad\overline{\eta}_{n}:=\mathcal{D}_{A_{n}}(F^{\prime}).$
(45)

That $f^{\prime}_{j}\in\mathcal{F}_{n,\text{reg}(C_{v})}$ is asserted in Lemma
9.

#### Bounding $d_{LP}(\overline{\eta},\overline{\eta}_{n})$

For some $\epsilon$ to be we want to show that
$d_{LP}(\overline{\eta},\overline{\eta}_{n})\leq\epsilon$, which is equivalent
to showing, for any $U\in\mathcal{B}_{2k}$,

$\overline{\eta}(U)\leq\overline{\eta}_{n}(U^{\epsilon})+\epsilon\qquad\text{and}\qquad\overline{\eta}_{n}(U)\leq\overline{\eta}(U^{\epsilon})+\epsilon.$
(46)

Fix any $U\in\mathcal{B}_{2k}$, we have

$\displaystyle\overline{\eta}(U)=\int_{\mathbb{R}^{2k}}\mathbbm{1}_{U}\textup{d}\mathcal{D}_{A}(F)=\int_{0}^{1}\mathbbm{1}_{F_{A}\in
U}\textup{d}\lambda,$ (47)

and

$\displaystyle\overline{\eta}_{n}(U^{\epsilon})=\int_{\mathbb{R}^{2k}}\mathbbm{1}_{U^{\epsilon}}\textup{d}\mathcal{D}_{A_{n}}(F^{\prime})$
$\displaystyle=\sum_{u\in[n]/n}\frac{1}{n}\mathbbm{1}_{F^{\prime}_{A_{n}}\in
U^{\epsilon}}.$ (48)

Subtracting both sides yield:

$\displaystyle\overline{\eta}(U)-\overline{\eta}_{n}(U^{\epsilon})=\sum_{u\in[n]/n}\int_{u-1/n}^{u}\mathbbm{1}_{F_{A}(x)\in
U}-\mathbbm{1}_{F^{\prime}_{A_{n}}(u)\in U^{\epsilon}}\textup{d}\lambda(x).$
(49)

Similarly, we have:

$\displaystyle\overline{\eta}_{n}(U)-\overline{\eta}(U^{\epsilon})=\sum_{u\in[n]/n}\int_{u-1/n}^{u}\mathbbm{1}_{F^{\prime}_{A_{n}}(u)\in
U}-\mathbbm{1}_{F_{A}(x)\in U^{\epsilon}}\textup{d}\lambda(x)$ (50)

Let $y_{x}=\left\lceil xn\right\rceil/n$. Recall that $E\subset[0,1]$ defined
in Assumption 5.B and 4.B is the set of $x$ where Lipschitzness of the image
under $A$ may fail. Let $E=\emptyset$ if we are using Assumption 5.A
alternatively. Define the events:

$\displaystyle\mathcal{E}^{1}_{U}(\epsilon)$ $\displaystyle=\\{x:F_{A}(x)\in
U\wedge F^{\prime}_{A_{n}}(y_{x})\not\in U^{\epsilon}\\}$ (51)
$\displaystyle\mathcal{E}^{2}_{U}(\epsilon)$
$\displaystyle=\\{x:F^{\prime}_{A_{n}}(y_{x})\in U\wedge F_{A}\not\in
U^{\epsilon}\\}$ (52) $\displaystyle\mathcal{E}^{\prime}(\epsilon)$
$\displaystyle=\\{x:\|F_{A}(x)-F^{\prime}_{A_{n}}(y_{x})\|_{2}>\epsilon\\}$
(53) $\displaystyle\mathcal{E}_{j}(\epsilon)$
$\displaystyle=\\{x:|f_{j}(x)-f^{\prime}_{j}(y_{x})|>\epsilon/\sqrt{2k}\\},$
$\displaystyle j=1..k$ (54) $\displaystyle\mathcal{E}_{j,A}(\epsilon)$
$\displaystyle=\\{x:|Af_{j}(x)-A_{n}f^{\prime}_{j}(y_{x})|>\epsilon/\sqrt{2k}\\},$
$\displaystyle j=1..k.$ (55)

Using this notation, one also has

$\displaystyle\overline{\eta}(U)-\overline{\eta}_{n}(U^{\epsilon})\leq\lambda(\mathcal{E}^{1}_{U})\qquad\text{and}\qquad\overline{\eta}_{n}(U)-\overline{\eta}(U^{\epsilon})\leq\lambda(\mathcal{E}^{2}_{U}).$
(56)

It is straightforward to see
$\mathcal{E}^{l}_{U}(\epsilon)\subseteq\mathcal{E}^{\prime}(\epsilon),l=1,2$
for any $U$ by definition of $U^{\epsilon}$. Furthermore,

$\mathcal{E}^{\prime}(\epsilon)\subseteq\bigcup_{j=1}^{k}\mathcal{E}_{j}(\epsilon)\cup\mathcal{E}_{j,A}(\epsilon),$
(57)

since if all $2k$ dimensions are bounded in absolute value by
$\epsilon/\sqrt{2k}$ then the Euclidean distance of the vector is bounded by
$\epsilon$.

Therefore it suffices to bound
$\lambda(\mathcal{E}_{j}(\epsilon))+\lambda(\mathcal{E}_{j,A}(\epsilon))$ for
each $j\in[k]$.

#### Bounding $\lambda(\mathcal{E}_{j}(\epsilon))$.

Since $f_{j}$ is $C_{v}$-Lipschitz for all $j$, we have:

$\displaystyle|f_{j}(x)-f^{\prime}_{j}(y_{x})|$
$\displaystyle=\left|f_{j}(x)-n\int_{y_{x}-1/n}^{y_{x}}f_{j}(z)\textup{d}\lambda(z)\right|$
(58)
$\displaystyle=n\left|\int_{y_{x}-1/n}^{y_{x}}f_{j}(x)-f_{j}(z)\textup{d}\lambda(z)\right|$
(59)
$\displaystyle=n\int_{y_{x}-1/n}^{y_{x}}|f_{j}(x)-f_{j}(z)|\textup{d}\lambda(z)$
(60) $\displaystyle\leq
n\int_{y_{x}-1/n}^{y_{x}}\frac{C_{v}}{n}\textup{d}\lambda(z)=\frac{C_{v}}{n},$
(61)

where the first line is definition of $f^{\prime}_{j}$, the second line is
because $\lambda((u-1/n,u])=\frac{1}{n}$, the third line is by triangle
inequality and the last line is because of Lipschitzness of $f_{j}$.

Thus, choosing $\epsilon>\sqrt{2k}C_{v}/n$ means that
$\lambda(\mathcal{E}_{j}(\epsilon))=0$. (We can tighten this bound by only
assuming that $f_{j}$ is $C_{v}$-Lipschitz outside a set of small measure.)

#### Bounding $\lambda(\mathcal{E}_{j,A})$.

Let $\mathcal{F}_{[-1,1]}\ni\tilde{f}$ be the extension of $f^{\prime}$
defined as $\tilde{f}(x)=f^{\prime}(\left\lceil xn\right\rceil/n)$ for all
$x\in[0,1]$. Note that $\tilde{f}$ is not continuous in general and hence not
Lipschitz. We have for any $x\in[0,1]$:

$\displaystyle|Af_{j}(x)-A_{n}f^{\prime}_{j}(y_{x})|$
$\displaystyle=\left|Af_{j}(x)-n\int_{y_{x}-\frac{1}{n}}^{y_{x}}A\tilde{f}_{j}(z)\textup{d}\lambda(z)\right|$
(62) $\displaystyle\leq
n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af_{j}(x)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z),$
(63)

where we used uniformity of $\lambda$ and triangle inequality. From here, we
proceed slightly differently depending on the specific assumptions.

#### Proof via Assumption 5.A or 5.B.

If $A$ satisfies Assumption 5.A or Assumption 5.B, then we have for each $x$:

$\displaystyle|Af_{j}(x)-A_{n}f^{\prime}_{j}(y_{x})|$ $\displaystyle\leq
n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af_{j}(x)-A\tilde{f}_{j}(x)\right|+\left|A\tilde{f}_{j}(x)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)$
(64)
$\displaystyle\leq\left|Af_{j}(x)-A\tilde{f}_{j}(x)\right|+n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|A\tilde{f}_{j}(x)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z).$
(65)

Define the following events:

$\displaystyle\mathcal{E}_{j,A}^{1}(\epsilon)$
$\displaystyle:=\left\\{x:\left|Af_{j}(x)-A\tilde{f}_{j}(x)\right|>\frac{\epsilon}{2\sqrt{2k}}\right\\}$
(66) $\displaystyle\mathcal{E}_{j,A}^{2}(\epsilon)$
$\displaystyle:=\left\\{x\not\in
E:n\int_{y_{x}-1/n}^{y_{x}}\left|A\tilde{f}_{j}(x)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)>\frac{\epsilon}{2\sqrt{2k}}\right\\}$
(67)

Then it is clear that
$\mathcal{E}_{j,A}\subseteq\mathcal{E}_{j,A}^{1}\cup\mathcal{E}_{j,A}^{2}\cup
E$ and thus
$\lambda(\mathcal{E}_{j,A})\leq\lambda(\mathcal{E}_{j,A}^{1})+\lambda(\mathcal{E}_{j,A}^{2})+\lambda(E)$.

#### Bounding $\lambda(\mathcal{E}^{1}_{j,A}(\epsilon))$ via Assumption 5.A or
5.B.

Because of Assumption 2, we have: $\|A\tilde{f}_{j}-Af_{j}\|_{2}\leq
C_{A}\|\tilde{f}_{j}-f_{j}\|_{2}$. By $L^{p}$ norms inequality, we have

$\|A\tilde{f}_{j}(x)-Af_{j}(x)\|_{1}\leq
C_{A}\|\tilde{f}_{j}-f_{j}\|_{2}\leq\frac{C_{A}C_{v}}{n}.$ (68)

where the last inequality is due to

$\displaystyle\|\tilde{f}_{j}-f_{j}\|^{2}_{2}$
$\displaystyle=\int_{0}^{1}(\tilde{f}_{j}(x)-f_{j}(x))^{2}\textup{d}\lambda(x)$
(69)
$\displaystyle=\sum_{u\in[n]/n}\int_{u-1/n}^{u}(f^{\prime}_{j}(u/n)-f_{j}(x))^{2}\textup{d}\lambda(x)$
(70)
$\displaystyle=\sum_{u\in[n]/n}\int_{u-1/n}^{u}\left(n\int_{(u-1)/n}^{u/n}f_{j}(z)\textup{d}\lambda(z)-f_{j}(x)\right)^{2}\textup{d}\lambda(x)$
(71)
$\displaystyle\leq\sum_{u\in[n]/n}\int_{u-1/n}^{u}n^{2}\left(\int_{u-1/n}^{u}|f_{j}(z)-f_{j}(x)|\textup{d}\lambda(z)\right)^{2}\textup{d}\lambda(x)$
(72) $\displaystyle\leq\frac{C_{v}^{2}}{n^{2}}.$ (73)

We have:

$\displaystyle\frac{C_{A}C_{v}}{n}$
$\displaystyle\geq\int_{0}^{1}|A\tilde{f}_{j}(x)-Af_{j}(x)|dx$ (74)
$\displaystyle=\int_{\mathcal{E}^{1}_{j,A}(\epsilon)}|A\tilde{f}_{j}(x)-Af_{j}(x)|dx+\int_{[0,1]\backslash\mathcal{E}^{1}_{j,A}(\epsilon)}|A\tilde{f}_{j}(x)-Af_{j}(x)|dx$
(75)
$\displaystyle\geq\frac{\epsilon}{2\sqrt{2k}}\lambda(\mathcal{E}^{1}_{j,A}(\epsilon))+0.$
(76)

Thus selecting
$\epsilon>2\sqrt{(\sqrt{2}k\sqrt{k}C_{A}C_{v})/n}=2^{\frac{5}{4}}k^{\frac{3}{4}}(C_{A}C_{v}/n)^{\frac{1}{2}}$
gives
$\lambda(\overline{\mathcal{E}}_{j,A}(\epsilon))\leq\frac{\epsilon}{2k}$.

#### Bounding $\lambda(\mathcal{E}^{2}_{j,A}(\epsilon))$ via Assumption 5.A or
5.B.

Notice that $\tilde{f}_{j}$ is constant in each $(u-1/n,u]$ and thus by
Assumption 5.A or 5.B, $A\tilde{f}_{j}$ is $C_{c}$-Lipschitz in each
$(u-1/n,u]\backslash E$. Therefore we have, for $x\in[0,1]\backslash E$ and
$z\in(y_{x}-1/n,y_{x}]\backslash E$:

$\displaystyle|A\tilde{f}_{j}(x)-A\tilde{f}_{j}(z)|$ $\displaystyle\leq
C_{c}|x-z|\leq\frac{C_{c}}{n}.$ (77)

When $z\in E$, we use the second condition in Assumption 5.B to get
$\|A\tilde{f}_{j}\mathbbm{1}_{E}\|_{1}\leq\frac{1}{n}$ and thus for any
$x\not\in E$:

$\displaystyle
n\int_{y_{x}-1/n}^{y_{x}}\left|A\tilde{f}_{j}(x)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)$
(78) $\displaystyle=$ $\displaystyle n\int_{(y_{x}-1/n,y_{x}]\cap
E}\left|A\tilde{f}_{j}(x)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)+n\int_{(y_{x}-1/n,y_{x}]\backslash
E}\left|A\tilde{f}_{j}(x)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)$ (79)
$\displaystyle\leq$ $\displaystyle\frac{C_{c}}{n}+n\int_{(y_{x}-1/n,y_{x}]\cap
E}\left|A\tilde{f}_{j}(x)\right|+\left|A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)$
(80) $\displaystyle\leq$
$\displaystyle\frac{C_{c}}{n}+|A\tilde{f}_{j}(x)|n\lambda(E_{x})+\|A\tilde{f}_{j}\mathbbm{1}_{E_{x}}\|_{1}$
(81) $\displaystyle\leq$
$\displaystyle\frac{C_{c}+1}{n}+|A\tilde{f}_{j}(x)|n\lambda(E_{x}),$ (82)

where $E_{x}=(y_{x}-1/n,y_{x}]\cap E$.

For $x\in\mathcal{E}_{j,A}^{2}(\epsilon)$, we have:

$\frac{C_{c}+1}{n}+|A\tilde{f}_{j}(x)|n\lambda(E_{x})>\frac{\epsilon}{2\sqrt{2k}},$
(83)

or equivalently,

$|A\tilde{f}_{j}(x)|>\frac{1}{n\lambda(E_{x})}\left(\frac{\epsilon}{2\sqrt{2k}}-\frac{C_{c}+1}{n}\right)$
(84)

Since $1/n\geq\|A\tilde{f}_{j}\mathbbm{1}_{E}\|_{1}$, we have:

$\displaystyle 1$
$\displaystyle\geq\left(\frac{\epsilon}{2\sqrt{2k}}-\frac{C_{c}+1}{n}\right)\int_{\mathcal{E}^{2}_{j,A}}\frac{1}{\lambda(E_{x})}\textup{d}\lambda(x)+0$
(85)
$\displaystyle\geq\left(\frac{\epsilon}{2\sqrt{2k}}-\frac{C_{c}+1}{n}\right)\sum_{u\in[n]/n}\frac{1}{\lambda(E_{u})}\int_{\mathcal{E}_{j,A}^{2}\cap(u-1/n,u]}1\textup{d}\lambda(x)$
(86)
$\displaystyle\geq\left(\frac{\epsilon}{2\sqrt{2k}}-\frac{C_{c}+1}{n}\right)n\lambda(\mathcal{E}_{j,A}^{2}).$
(87)

Thus choosing $\epsilon>4\sqrt{2k}(C_{c}+1)/n$ means that:

$\displaystyle
1\geq\frac{\epsilon}{4\sqrt{2k}}n\lambda(\mathcal{E}_{j,A}^{2}),$ (88)

or

$\displaystyle\lambda(\mathcal{E}_{j,A}^{2})\leq\frac{4\sqrt{2k}}{\epsilon
n}.$ (89)

Finally, choosing
$\epsilon>\sqrt{\frac{16k\sqrt{2k}}{n}}=\frac{2^{\frac{9}{4}}k^{\frac{3}{4}}}{n^{\frac{1}{2}}}$
makes $\lambda(\mathcal{E}_{j,A}^{2})\leq\frac{\epsilon}{4k}$; and choosing
$\epsilon>\frac{4k}{n}$ makes $\lambda(E)<\frac{1}{n}<\frac{\epsilon}{4k}$.

#### Putting everything together via Assumption 5.A or 5.B.

Thus, we can choose
$\overline{\epsilon}=8k\left(\sqrt{\frac{C_{A}C_{v}+1}{n}}+\frac{C_{v}+C_{c}+1}{n}\right)$
to get:

$\lambda(\mathcal{E}^{\prime}(\epsilon))\leq\sum_{j=1}^{k}\frac{\overline{\epsilon}}{k}=\overline{\epsilon},$
(90)

which allows us to conclude:

$d_{LP}(\overline{\eta},\overline{\eta}_{n})\leq\overline{\epsilon}.$ (91)

Since $\overline{\eta}$ was chosen arbitrarily, we have for all
$\overline{\eta}\in\mathcal{S}_{k}(A)$,

$\inf_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}d_{LP}(\overline{\eta},\eta_{n})\leq
d_{LP}(\overline{\eta},\overline{\eta}_{n})\leq\overline{\epsilon}.$ (92)

Thus we also have:

$\sup_{\eta\in\mathcal{S}_{k,C_{v}}(A)}\inf_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}d_{LP}(\eta,\eta_{n})\leq\overline{\epsilon}.$
(93)

#### Proof via Assumption 4.B.

Here, we use the other triangle inequality to get for each $x$:

$\displaystyle|Af_{j}(x)-A_{n}f^{\prime}_{j}(y_{x})|$ $\displaystyle\leq
n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af_{j}(x)-Af_{j}(z)\right|+\left|Af_{j}(z)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)$
(94) $\displaystyle\leq
n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af_{j}(x)-Af_{j}(z)\right|\textup{d}\lambda(z)+n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af_{j}(z)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z).$
(95)

Define the following events:

$\displaystyle\mathcal{E}_{j,A}^{1}(\epsilon)$
$\displaystyle:=\left\\{x:n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af_{j}(z)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)>\frac{\epsilon}{2\sqrt{2k}}\right\\}$
(96) $\displaystyle\mathcal{E}_{j,A}^{2}(\epsilon)$
$\displaystyle:=\left\\{x\not\in
E:n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af_{j}(x)-Af_{j}(z)\right|\textup{d}\lambda(z)>\frac{\epsilon}{2\sqrt{2k}}\right\\}$
(97)

Then it is clear that
$\mathcal{E}_{j,A}\subseteq\mathcal{E}_{j,A}^{1}\cup\mathcal{E}_{j,A}^{2}\cup
E$ and thus
$\lambda(\mathcal{E}_{j,A})\leq\lambda(\mathcal{E}_{j,A}^{1})+\lambda(\mathcal{E}_{j,A}^{2})+\lambda(E)$.

#### Bounding $\lambda(\mathcal{E}^{1}_{j,A}(\epsilon))$ via Assumption 4.B.

Because of Assumption 2, we have: $\|A\tilde{f}_{j}-Af_{j}\|_{2}\leq
C_{A}\|\tilde{f}_{j}-f_{j}\|_{2}$. By $L^{p}$ norms inequality, we have

$\|A\tilde{f}_{j}-Af_{j}\|_{1}\leq
C_{A}\|\tilde{f}_{j}-f_{j}\|_{2}\leq\frac{C_{A}C_{v}}{n}.$ (98)

where the last inequality is due to

$\displaystyle\|\tilde{f}_{j}-f_{j}\|^{2}_{2}$
$\displaystyle=\int_{0}^{1}(\tilde{f}_{j}(x)-f_{j}(x))^{2}\textup{d}\lambda(x)$
(99)
$\displaystyle=\sum_{u\in[n]/n}\int_{u-1/n}^{u}(f^{\prime}_{j}(u)-f_{j}(x))^{2}\textup{d}\lambda(x)$
(100)
$\displaystyle=\sum_{u\in[n]/n}\int_{u-1/n}^{u}\left(n\int_{u-1/n}^{u}f_{j}(z)\textup{d}\lambda(z)-f_{j}(x)\right)^{2}\textup{d}\lambda(x)$
(101)
$\displaystyle\leq\sum_{u\in[n]/n}\int_{u-1/n}^{u}n^{2}\left(\int_{u-1/n}^{u}|f_{j}(z)-f_{j}(x)|\textup{d}\lambda(z)\right)^{2}\textup{d}\lambda(x)$
(102) $\displaystyle\leq\frac{C_{v}^{2}}{n^{2}}.$ (103)

Consider:

$\displaystyle\lambda(\mathcal{E}^{1}_{j,A}(\epsilon))\cdot\frac{\epsilon}{2\sqrt{2k}}$
$\displaystyle\leq\int_{0}^{1}n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af_{j}(z)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)\textup{d}\lambda(x)$
(104)
$\displaystyle=\sum_{u\in[n]/n}\int_{u-1/n}^{u}\left|Af_{j}(z)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z)$
(105) $\displaystyle=\|Af_{j}-A\tilde{f}_{j}\|_{1}\leq\frac{C_{A}C_{v}}{n}.$
(106)

Thus selecting
$\epsilon>\sqrt{\frac{C_{A}C_{v}4k\sqrt{2k}}{n}}=2^{\frac{5}{4}}k^{\frac{3}{4}}(C_{A}C_{v}/n)^{\frac{1}{2}}$
gives
$\lambda(\overline{\mathcal{E}}_{j,A}(\epsilon))\leq\frac{\epsilon}{2k}$.

#### Bounding $\lambda(\mathcal{E}^{2}_{j,A}(\epsilon))$ via Assumption 4.B.

Notice that $f_{j}$ is Lipschitz in $[0,1]$ and thus by Assumption 4.B,
$Af_{j}$ is $C_{v}$-Lipschitz in $[0,1]\backslash E$. Therefore we have, for
$x\in[0,1]\backslash E$ and $z\in(y_{x}-1/n,y_{x}]\backslash E$ and:

$\displaystyle|Af_{j}(x)-Af_{j}(z)|$ $\displaystyle\leq
C_{v}|x-z|\leq\frac{C_{v}}{n}.$ (107)

When $z\in E$, we use the second condition in Assumption 4.B to get
$\|Af_{j}\mathbbm{1}_{E}\|_{1}\leq\frac{1}{n}$ and thus for any $x\not\in E$:

$\displaystyle
n\int_{y_{x}-1/n}^{y_{x}}\left|Af_{j}(x)-Af_{j}(z)\right|\textup{d}\lambda(z)$
(108) $\displaystyle=$ $\displaystyle n\int_{(y_{x}-1/n,y_{x}]\cap
E}\left|Af_{j}(x)-Af_{j}(z)\right|\textup{d}\lambda(z)+n\int_{(y_{x}-1/n,y_{x}]\backslash
E}\left|Af_{j}(x)-Af_{j}(z)\right|\textup{d}\lambda(z)$ (109)
$\displaystyle\leq$ $\displaystyle\frac{C_{v}}{n}+n\int_{(y_{x}-1/n,y_{x}]\cap
E}\left|Af_{j}(x)\right|+\left|Af_{j}(z)\right|\textup{d}\lambda(z)$ (110)
$\displaystyle\leq$
$\displaystyle\frac{C_{v}}{n}+|Af_{j}(x)|n\lambda(E_{x})+\|Af_{j}\mathbbm{1}_{E_{x}}\|_{1}$
(111) $\displaystyle\leq$
$\displaystyle\frac{C_{v}+1}{n}+|Af_{j}(x)|n\lambda(E_{x}),$ (112)

where $E_{x}=(y_{x}-1/n,y_{x}]\cap E$.

For $x\in\mathcal{E}_{j,A}^{2}(\epsilon)$, we have:

$\frac{C_{v}+1}{n}+|Af_{j}(x)|n\lambda(E_{x})>\frac{\epsilon}{2\sqrt{2k}},$
(113)

or equivalently,

$|Af_{j}(x)|>\frac{1}{n\lambda(E_{x})}\left(\frac{\epsilon}{2\sqrt{2k}}-\frac{C_{v}+1}{n}\right)$
(114)

Since $1/n\geq\|Af_{j}\mathbbm{1}_{E}\|_{1}$, we have:

$\displaystyle 1$
$\displaystyle\geq\left(\frac{\epsilon}{2\sqrt{2k}}-\frac{C_{v}+1}{n}\right)\int_{\mathcal{E}^{2}_{j,A}}\frac{1}{\lambda(E_{x})}\textup{d}\lambda(x)+0$
(115)
$\displaystyle\geq\left(\frac{\epsilon}{2\sqrt{2k}}-\frac{C_{v}+1}{n}\right)\sum_{u\in[n]/n}\frac{1}{\lambda(E_{u})}\int_{\mathcal{E}_{j,A}^{2}\cap(u-1/n,u]}1\textup{d}\lambda(x)$
(116)
$\displaystyle\geq\left(\frac{\epsilon}{2\sqrt{2k}}-\frac{C_{v}+1}{n}\right)n\lambda(\mathcal{E}_{j,A}^{2}).$
(117)

Thus choosing $\epsilon>4\sqrt{2k}(C_{v}+1)/n$ means that:

$\displaystyle
1\geq\frac{\epsilon}{4\sqrt{2k}}n\lambda(\mathcal{E}_{j,A}^{2}),$ (118)

or

$\displaystyle\lambda(\mathcal{E}_{j,A}^{2})\leq\frac{4\sqrt{2k}}{\epsilon
n}.$ (119)

Finally, choosing
$\epsilon>\sqrt{\frac{16k\sqrt{2k}}{n}}=\frac{2^{\frac{9}{4}}k^{\frac{3}{4}}}{n^{\frac{1}{2}}}$
makes $\lambda(\mathcal{E}_{j,A}^{2})\leq\frac{\epsilon}{4k}$; and choosing
$\epsilon>\frac{4k}{n}$ makes $\lambda(E)<\frac{1}{n}<\frac{\epsilon}{4k}$.

#### Putting everything together via Assumption 4.B.

Thus, we can choose
$\overline{\epsilon}=8k\left(\sqrt{\frac{C_{A}C_{v}+1}{n}}+\frac{C_{v}+1}{n}\right)$
to get:

$\lambda(\mathcal{E}^{\prime}(\epsilon))\leq\sum_{j=1}^{k}\frac{\overline{\epsilon}}{k}=\overline{\epsilon},$
(120)

which allows us to conclude:

$d_{LP}(\overline{\eta},\overline{\eta}_{n})\leq\overline{\epsilon}.$ (121)

Since $\overline{\eta}$ was chosen arbitrarily, we have for all
$\overline{\eta}\in\mathcal{S}_{k}(A)$,

$\inf_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}d_{LP}(\overline{\eta},\eta_{n})\leq
d_{LP}(\overline{\eta},\overline{\eta}_{n})\leq\overline{\epsilon}.$ (122)

Thus we also have:

$\sup_{\eta\in\mathcal{S}_{k,C_{v}}(A)}\inf_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}d_{LP}(\eta,\eta_{n})\leq\overline{\epsilon}.$
(123)

#### Bounding
$\sup_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(A_{n})}\inf_{\eta\in\mathcal{S}_{k,C_{v}}(A)}d_{LP}(\eta,\eta_{n})$.

In this direction, we proceed identically, but now choose
$\overline{\eta}_{n}$ arbitrarily in $\mathcal{S}_{k,C_{v}}(A_{n})$. By
definition of $(k,C_{v})$-profiles, there exists a tuple
$F=(f_{1},\ldots,f_{k})$ each in $\mathcal{F}_{n,\text{reg}(C_{v})}$ such that
$\overline{\eta}_{n}=\mathcal{D}_{A_{n}}(F)$.

Construct

$\displaystyle F^{\prime}$
$\displaystyle:=\left\\{\mathcal{F}_{\text{reg}(C_{v})}\ni
f^{\prime}_{j}:x\mapsto(1-y_{x}n+xn)f_{j}(y_{x})+(y_{x}n-xn)f_{j}(y_{x}-1/n)\right\\},$
(124) $\displaystyle\overline{\eta}$
$\displaystyle=\mathcal{D}_{A}(F^{\prime}),$ (125)

where $y_{x}=\left\lceil xn\right\rceil/n$ for each $j\in[k]$. That
$f^{\prime}_{j}\in\mathcal{F}_{\text{reg}(C_{v})}$ is asserted in Lemma 10.
Intuitively, $f^{\prime}_{j}$ is the continuous piecewise linear function that
interpolates $f_{j}$, created by joining $f_{j}(u-1/n)$ and $f_{j}(u)$ with a
line segment for each $u\in[n]/n$. Note also that $f^{\prime}_{j}(u)=f_{j}(u)$
for all $u\in[n]/n$.

#### Bounding $d_{LP}(\overline{\eta},\overline{\eta}_{n})$.

As with the previous direction, we start with an arbitrary
$U\in\mathcal{B}_{k}$ and write down the differences:

$\displaystyle\overline{\eta}_{n}(U)-\overline{\eta}(U^{\epsilon})$
$\displaystyle=\sum_{u\in[n]/n}\int_{u-1/n}^{u}\mathbbm{1}_{F_{A_{n}}(u)\in
U}-\mathbbm{1}_{F^{\prime}_{A}(x)\in U^{\epsilon}}\textup{d}\lambda(x),$ (126)
$\displaystyle\overline{\eta}(U)-\overline{\eta}_{n}(U^{\epsilon})$
$\displaystyle=\sum_{u\in[n]/n}\int_{u-1/n}^{u}\mathbbm{1}_{F^{\prime}_{A}(x)\in
U}-\mathbbm{1}_{F_{A_{n}}(u)\in U^{\epsilon}}\textup{d}\lambda(x).$ (127)

Define the events:

$\displaystyle\mathcal{E}^{1}_{U}(\epsilon)$
$\displaystyle=\\{x:F_{A_{n}}(y_{x})\in U\wedge F^{\prime}_{A}(x)\not\in
U^{\epsilon}\\}$ (128) $\displaystyle\mathcal{E}^{2}_{U}(\epsilon)$
$\displaystyle=\\{x:F^{\prime}_{A}(x)\in U\wedge F_{A_{n}}(y_{x})\not\in
U^{\epsilon}\\}$ (129) $\displaystyle\mathcal{E}^{\prime}(\epsilon)$
$\displaystyle=\\{x:\|F_{A_{n}}(y_{x})-F^{\prime}_{A}(x)\|_{2}>\epsilon\\}$
(130) $\displaystyle\mathcal{E}_{j}(\epsilon)$
$\displaystyle=\\{x:|f_{j}(y_{x})-f^{\prime}_{j}(x)|>\epsilon/\sqrt{2k}\\},$
$\displaystyle j=1..k$ (131) $\displaystyle\mathcal{E}_{j,A}(\epsilon)$
$\displaystyle=\\{x:|A_{n}f_{j}(y_{x})-Af^{\prime}_{j}(x)|>\epsilon/\sqrt{2k}\\},$
$\displaystyle j=1..k.$ (132)

Using this notation, one also has

$\displaystyle\overline{\eta}(U)-\overline{\eta}_{n}(U^{\epsilon})\leq\lambda(\mathcal{E}^{1}_{U})\qquad\text{and}\qquad\overline{\eta}_{n}(U)-\overline{\eta}(U^{\epsilon})\leq\lambda(\mathcal{E}^{2}_{U}).$
(133)

It is straightforward to see
$\mathcal{E}^{l}_{U}(\epsilon)\subseteq\mathcal{E}^{\prime}(\epsilon),l=1,2$
for any $U$ by definition of $U^{\epsilon}$. Furthermore,

$\mathcal{E}^{\prime}(\epsilon)\subseteq\bigcup_{j=1}^{k}\mathcal{E}_{j}(\epsilon)\cup\mathcal{E}_{j,A}(\epsilon),$
(134)

since if all $2k$ dimensions are bounded in absolute value by
$\epsilon/\sqrt{2k}$ then the Euclidean distance of the vector is bounded by
$\epsilon$.

Therefore it suffices to bound
$\lambda(\mathcal{E}_{j}(\epsilon))+\lambda(\mathcal{E}_{j,A}(\epsilon))$ for
each $j\in[k]$.

#### Bounding $\lambda(\mathcal{E}_{j}(\epsilon))$.

Since $f^{\prime}_{j}$ is $C_{v}$-Lipschitz for all $j$ (Lemma 10), we have:

$\displaystyle|f_{j}(y_{x})-f^{\prime}_{j}(x)|$
$\displaystyle=|f^{\prime}_{j}(y_{x})-f^{\prime}_{j}(x)|\leq\frac{C_{v}}{n}.$
(135)

Thus, choosing $\epsilon>\sqrt{2k}C_{v}/n$ means that
$\lambda(\mathcal{E}_{j}(\epsilon))=0$. (We can tighten this bound by only
assuming that $f_{j}$ is $C_{v}$-Lipschitz outside a set of small measure.)

#### Bounding $\lambda(\mathcal{E}_{j,A})$.

Let $\mathcal{F}_{[-1,1]}\ni\tilde{f}$ be the extension of $f$ defined as
$\tilde{f}(x)=f(\left\lceil xn\right\rceil/n)$ for all $x\in[0,1]$. Note that
$\tilde{f}$ is not continuous in general and hence not Lipschitz. We have for
any $x\in[0,1]$:

$\displaystyle|Af^{\prime}_{j}(x)-A_{n}f_{j}(y_{x})|$
$\displaystyle=\left|Af^{\prime}_{j}(x)-n\int_{y_{x}-\frac{1}{n}}^{y_{x}}A\tilde{f}_{j}(z)\textup{d}\lambda(z)\right|$
(136) $\displaystyle\leq
n\int_{y_{x}-\frac{1}{n}}^{y_{x}}\left|Af^{\prime}_{j}(x)-A\tilde{f}_{j}(z)\right|\textup{d}\lambda(z),$
(137)

where we used uniformity of $\lambda$ and triangle inequality. The last thing
that we need to show is:

$\displaystyle\|f^{\prime}_{j}-\tilde{f}_{j}\|_{2}^{2}$
$\displaystyle=\int_{0}^{1}((1-y_{x}n+xn)f(y_{x})+(xn-
y_{x}n)f(y_{x}-1/n)-f(y_{x}))^{2}\textup{d}\lambda(x)$ (138)
$\displaystyle=\int_{0}^{1}n^{2}(y_{x}-x)^{2}(f(y_{x})-f(y_{x}-1/n))^{2}\textup{d}\lambda(x)$
(139) $\displaystyle\leq\frac{C_{v}^{2}}{n^{2}}.$ (140)

From here, by a word-for-word argument, we can show that the same choice of
$\overline{\epsilon}$ does the trick to make
$\lambda(\mathcal{E}^{\prime}(\epsilon))\leq\overline{\epsilon}$. This works
since we only use the fact that
$f^{\prime}_{j}\in\mathcal{F}_{\text{reg}(C_{v})}$ as well as assumption
conditions in the previous proof.

#### Bounding $d_{M}$.

We have:

$d_{H}(\mathcal{S}_{k}(A),\mathcal{S}_{k}(A_{n}))=\max(\sup_{\overline{\eta}_{n}\in\mathcal{S}_{k}(A_{n})}\inf_{\eta\in\mathcal{S}_{k}(A)}d_{LP}(\overline{\eta}_{n},\eta),\sup_{\overline{\eta}\in\mathcal{S}_{k}(A)}\inf_{\eta_{n}\in\mathcal{S}_{k}(A_{n})}d_{LP}(\overline{\eta},\eta_{n}))\leq\overline{\epsilon}.$
(141)

Therefore,

$\displaystyle
d_{M}(A,A_{n})\leq\sum_{k=1}^{\infty}\frac{8k\left(\sqrt{\frac{C_{A}C_{v}+1}{n}}+\frac{C_{v}+1}{n}\right)}{2^{k}}\leq
8\left(\sqrt{\frac{C_{A}C_{v}+1}{n}}+\frac{2C_{c}+C_{v}+1}{n}\right).$ (142)

∎

######  Lemma 9.

Fix $n\in\mathbb{N}$. Fix $f\in\mathcal{F}_{\text{reg}(C_{v})}$. Define the
restriction $f^{\prime}:\frac{1}{n}[n]\to[-1,1]:u\mapsto
n\int_{u-1/n}^{u}f(z)\textup{d}\lambda(z)$. Then
$f^{\prime}\in\mathcal{F}_{n,\text{reg}(C_{v})}$.

###### Proof.

Firstly, we have for any $u\in[n]/n$:

$\displaystyle|f^{\prime}(u)|\leq
n\int_{u-1/n}^{u}|f(z)|\textup{d}\lambda(z)\leq
n\int_{u-1/n}^{u}1\textup{d}\lambda(z)=1.$ (143)

Therefore $\|f^{\prime}\|_{L^{2}([n]/n)}\leq n/n=1$ and thus $f^{\prime}$ is
measurable. Finally, for any $u<u^{\prime}\in[n]/n$:

$\displaystyle|f^{\prime}(u)-f^{\prime}(u^{\prime})|\leq
n\int_{u-1/n}^{u}\left|f(z)-f(z+(u^{\prime}-u))\right|\textup{d}\lambda(z)\leq
C_{v}(u^{\prime}-u),$ (144)

where we use Lipschitz property of $f$ in the last inequality. This shows that
$f^{\prime}$ is also $C_{v}$-Lipschitz. ∎

######  Remark 1.

The restriction to $\mathcal{F}_{[-1,1]}$ is necessary for this lemma to work
because $L^{2}([0,1])$ functions can blow up near $0$.

######  Lemma 10.

Fix $n\in\mathbb{N}$. Fix $f\in\mathcal{F}_{n,\text{reg}(C_{v})}$. Let
$y_{x}:=\left\lceil xn\right\rceil/n$ for any $x\in[0,1]$. Define the
extension $f^{\prime}:x\mapsto(1-y_{x}n+xn)f(y_{x})+(xn-y_{x}n)f(y_{x}-1/n)$.
Then $f^{\prime}\in\mathcal{F}_{\text{reg}(C_{v})}$.

###### Proof.

Firstly, since $f^{\prime}$ linearly interpolates between points of $f$, its
range cannot exceed that of $f$. The restricted range immediately implies that
the $L^{2}$ norm is bounded by $1$ since the support is also in $[0,1]$.
Finally, for any $x<x^{\prime}\in[0,1]$, if there is a $u$ such that
$x,x^{\prime}\in[u-1/n,u)$ then the fact that the interpolation is linear
means that the line segment from $f^{\prime}(x)$ to $f^{\prime}(x^{\prime})$
shares the same slope as that from $f(u)$ to $f(u-1/n)$, which is at most
$C_{v}$ since $f\in\mathcal{F}_{n,\text{reg}(C_{v})}$. Otherwise, there exists
a $u<u^{\prime}\in[n]/n$ such that $x\in[u-1/n,u)$ and
$x^{\prime}\in[u^{\prime}-1/n,u^{\prime})$. We have:

$|f^{\prime}(x)-f^{\prime}(x^{\prime})|\leq|f^{\prime}(x)-f^{\prime}(u)|+|f^{\prime}(u)-f^{\prime}(u^{\prime}-1/n)|+|f^{\prime}(u^{\prime}-1/n)-f^{\prime}(x^{\prime})|\leq
C_{v}(x^{\prime}-x),$ (145)

which proves Lipschitzness of $f^{\prime}$. ∎

##  Appendix E Omitted proofs for Section 4.2

The following result characterizes the behaviors of Assumptions 2, 5.A, 5.B
and 4.B under addition, multiplication by scalars, power, and element-wise
composition with a $1$-Lipschitz map:

######  Lemma 11.

Fix $k\in\mathbb{N}$ and $\alpha\in\mathbb{R}$. Recall that
$\rho:\mathbb{R}\to\mathbb{R}$ is a $1$-Lipschitz map. Let
$A_{1},A_{2}:\mathcal{F}\to\mathcal{F}$ satisfy Assumption 2 with constant
$C_{A}^{1}$ and $C_{A}^{2}$ respectively; and Assumption 5.A or 5.B or 4.B
with constant $C_{c}^{1}$ and $C_{c}^{2}$ respectively with common resolution
set $\mathcal{N}$. Then:

  1. 1.

$A_{1}+A_{2}$ satisfy Assumptions 2 and 5.A or 5.B or 4.B with constant
$(C_{A}^{1}+C_{A}^{2})$ and $(C_{c}^{1}+C_{c}^{2})$ respectively.

  2. 2.

$\alpha A_{1}$ satisfies Assumption 2 and 5.A or 5.B or 4.B with constant
$|\alpha|C_{A}^{1}$ and $|\alpha|C_{c}^{1}$ respectively.

  3. 3.

$\rho A_{1}$ (where the composition is done element-wise) satisfies Assumption
2 and 5.A or 5.B or 4.B with constant $C_{A}^{1}$ and $C_{c}^{1}$
respectively.

  4. 4.

Furthermore, if $C_{c}^{1}=0$ then $A_{2}\circ A_{1}$ satisfies Assumption 2
and 5.A 5.B or 4.B with constant $C_{A}^{1}C_{A}^{2}$ and $C_{c}^{2}$
respectively.

###### Proof of Lemma 11.

To recall, $A_{1},A_{2}:\mathcal{F}\to\mathcal{F}$ are $P$-operators that
satisfies Assumption 2 with constant $C_{A}^{1}$ and $C_{A}^{2}$ respectively
and Assumption 5.A or 5.B or 4.B with constant $C_{c}^{1}$ and $C_{c}^{2}$
respectively with common resolution set $\mathcal{N}$. We now show each part
of the Lemma.

  1. 1.

We have, for any $f,g\in\mathcal{F}$:

$\displaystyle\|(A_{1}+A_{2})f-(A_{1}+A_{2})g\|_{2}$
$\displaystyle\leq\|A_{1}f-A_{1}g\|_{2}+\|A_{2}f-A_{2}g\|_{2}$ (146)
$\displaystyle\leq C_{A}^{1}\|f-g\|_{2}+C_{A}^{2}\|f-g\|_{2},$ (147)

where the first line is triangle inequality and the second line is Assumption
2.

Let $f\in\mathcal{F}_{\text{reg}(C_{v})}$ piecewise constant on intervals
$[n]/n$ and $x,y\in(u-1/n,u]$ for some $n\in\mathcal{N}$ and $u\in[n]$, we
have:

$\displaystyle|(A_{1}+A_{2})f(x)-(A_{1}+A_{2})f(y)|$
$\displaystyle\leq|[A_{1}f](x)-[A_{1}f](y)|+|[A_{2}f](x)-[A_{2}f](y)|$ (148)
$\displaystyle\leq C_{c}^{1}|x-y|+C_{c}^{2}|x-y|,$ (149)

where the first line is triangle inequality and the second line is Assumption
5.A.

  2. 2.

We have, for any $f,g\in\mathcal{F}$:

$\displaystyle\|(\alpha A_{1})f-(\alpha A_{1})g\|_{2}$
$\displaystyle\leq|\alpha|\cdot\|A_{1}f-A_{1}g\|_{2}$ (150)
$\displaystyle\leq|\alpha|C_{A}^{1}\|f-g\|_{2},$ (151)

where the first line is property of norm and the second line is Assumption 2.

Let $f\in\mathcal{F}_{\text{reg}(C_{v})}$ piecewise constant on intervals
$[n]/n$, and $x,y\in(u-1/n,u]$ for some $n\in\mathcal{N}$ and $u\in[n]$, we
have:

$\displaystyle|(\alpha A_{1})f(x)-(\alpha A_{1})f(y)|$
$\displaystyle\leq|\alpha[A_{1}f](x)-\alpha[A_{1}f](y)|$ (152)
$\displaystyle\leq|\alpha|C_{c}^{1}|x-y|,$ (153)

where the second line is Assumption 5.A.

  3. 3.

We have, for any $f,g\in\mathcal{F}$:

$\displaystyle\|(\rho A_{1})f-(\rho A_{1})g\|_{2}$
$\displaystyle\leq\|A_{1}f-A_{1}g\|_{2}$ (154) $\displaystyle\leq
C_{A}^{1}\|f-g\|_{2},$ (155)

where the first line is Lipschitz property of $\rho$ and the second line is
Assumption 2.

Let $f\in\mathcal{F}_{\text{reg}(C_{v})}$ piecewise constant on intervals
$[n]/n$ and $x,y\in(u-1/n,u]$ for some $n\in\mathcal{N}$ and $u\in[n]$, we
have:

$\displaystyle|(\rho A_{1})f(x)-(\rho A_{1})f(y)|$
$\displaystyle\leq|\rho([A_{1}f](x))-\rho([A_{1}f](y))|$ (156)
$\displaystyle\leq|A_{1}f(x)-A_{1}f(y)|\leq C_{c}^{1}|x-y|,$ (157)

where the second line is Lipschitz property of $\rho$ and Assumption 5.A.

  4. 4.

We have, for any $f,g\in\mathcal{F}$:

$\displaystyle\|(A_{2}A_{1})f-(A_{2}A_{1})g\|_{2}$ $\displaystyle\leq
C_{A}^{2}\|A_{1}f-A_{1}g\|_{2}$ (158) $\displaystyle\leq
C_{A}^{1}C_{A}^{2}\|f-g\|_{2},$ (159)

where the first line is Lipschitz property of $A_{2}$ and the second line is
that of $A_{1}$.

Let $f\in\mathcal{F}_{\text{reg}(C_{v})}$ piecewise constant on intervals
$[n]/n$. Since $A_{1}$ send constant pieces to constant pieces, the final
implication follows direction from Assumption 5.A of $A_{2}$.

∎

######  Lemma 12.

Fix $n\in\mathcal{N},k\in[K]\cup\\{0\\},A:\mathcal{F}\to\mathcal{F}$ satisfies
Assumption 2 with constant $C_{A}$ and Assumption 5.A with constant $C_{c}$
and resolution set $\mathcal{N}$. Let
$n\in\mathcal{N},f_{1}\in\mathcal{F}_{n},f_{2}\in\mathcal{F}$. Recall that
$\tilde{f}\in\mathcal{F}$ denotes the extension of $f\in\mathcal{F}_{n}$ to
$[0,1]$ as $\tilde{f}(x)=f(\left\lceil xn\right\rceil)/n$. If
$\|\widetilde{f_{1}}-f_{2}\|_{2}\leq M$ for some positive constant $M$ then

$\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}\leq\frac{3^{k+1}kC_{c}^{2}C_{A}^{2k}}{n^{2}}+3^{k}C_{A}^{2k}M.$
(160)

If $A$ satisfies Assumption 5.B with constant $C_{c}$ instead then the bound
becomes:

$\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}\leq\frac{3^{k+1}k(C_{c}+1)^{2}C_{A}^{2k}}{n^{2}}+3^{k}C_{A}^{2k}M.$
(161)

If $A$ satisfies Assumption 4.B instead then the bound becomes:

$\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}\leq\frac{3^{k+1}k(C_{v}+1)^{2}C_{A}^{2k}}{n^{2}}+3^{k}C_{A}^{2k}M.$
(162)

###### Proof.

When $k=0$, the bound is vacuously true. We will hide the measure in integrals
when it is clear from context in this proof.

Assume that the bound is correct up to some $k-1$. We have:

$\displaystyle\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}$ (163)
$\displaystyle=$ $\displaystyle\sum_{u\in
1/n[n]}\int_{u-\frac{1}{n}}^{u}(A^{k}_{n}f_{1}(u)-A^{k}f_{2}(z))^{2}\textup{d}z$
(164) $\displaystyle=$ $\displaystyle\sum_{u\in
1/n[n]}\int_{u-\frac{1}{n}}^{u}\left(n\int_{u-\frac{1}{n}}^{u}A\widetilde{[A^{k-1}_{n}f_{1}]}(y)\textup{d}y-A^{k}f_{2}(z)\right)^{2}\textup{d}z$
(165)

Here we can use Jensen’s inequality to get:

$\displaystyle\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}$ (166)
$\displaystyle=$ $\displaystyle n\sum_{u\in
1/n[n]}\int_{u-\frac{1}{n}}^{u}\int_{u-\frac{1}{n}}^{u}\left(A\widetilde{[A^{k-1}_{n}f_{1}]}(y)-A[A^{k-1}f_{2}](z)\right)^{2}\textup{d}y\textup{d}z$
(167)

We proceed slightly differently based on the exact assumptions that we have.
If $A$ satisfies Assumption 5.A or 5.B then:

$\displaystyle\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}$ (169)
$\displaystyle\leq$ $\displaystyle n\sum_{u\in
1/n[n]}\int_{u-\frac{1}{n}}^{u}$
$\displaystyle\int_{u-\frac{1}{n}}^{u}\left(|A\widetilde{[A^{k-1}_{n}f_{1}]}(y)-A\widetilde{[A^{k-1}_{n}f_{1}]}(z)|+|A\widetilde{[A^{k-1}_{n}f_{1}]}(z)-A[A^{k-1}f_{2}](z)|\right)^{2}\textup{d}y\textup{d}z$
(170) $\displaystyle\leq$ $\displaystyle n\sum_{u\in
1/n[n]}\int_{u-\frac{1}{n}}^{u}$
$\displaystyle\int_{u-\frac{1}{n}}^{u}\left(\frac{C_{c}+1}{n}+|A\widetilde{[A_{n}^{k-1}f_{1}]}(z)|n\lambda(E_{z})+|A\widetilde{[A^{k-1}_{n}f_{1}]}(z)-A[A^{k-1}f_{2}](z)|\right)^{2}\textup{d}y\textup{d}z$
(171) $\displaystyle\leq$
$\displaystyle\int_{0}^{1}\left(\frac{C_{c}+1}{n}+|A\widetilde{[A_{n}^{k-1}f_{1}]}(z)|n\lambda(E_{z})+|A\widetilde{[A^{k-1}_{n}f_{1}]}(z)-A[A^{k-1}f_{2}](z)|\right)^{2}\textup{d}z$
(172) $\displaystyle\leq$
$\displaystyle\frac{3(C_{c}+1)^{2}}{n^{2}}+3\int_{0}^{1}(A\widetilde{[A_{n}^{k-1}f_{1}]}(z)n\lambda(E_{z}))^{2}\textup{d}z+3\|A\widetilde{[A^{k-1}_{n}f_{1}]}-A[A^{k-1}f_{2}]\|_{2}^{2}\textup{d}z.$
(173)

Here, we give a heuristic argument while the formal argument is exactly
similar to that in Theorem 2. The term
$3\int_{0}^{1}(A\widetilde{[A_{n}^{k-1}f_{1}]}(z)n\lambda(E_{z}))^{2}\textup{d}z$
can be made as close to $0$ as possible simply by changing the requirement on
$\lambda(E)$ to be smaller and smaller (see the discussion after Assumption
4.A). At the same time, our assumptions ensure that since
$\widetilde{A_{n}^{k-1}f_{1}}$ is a piecewise constant function, the action of
$A$ on it cannot become too wild (Lipschitz outside of $E$ and bounded $L^{1}$
norm inside $E$). This heuristic argument, when made rigorous can help us
conclude that:

$\displaystyle\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}\leq\frac{3(C_{c}+1)^{2}}{n^{2}}+3C_{A}^{2}\|\widetilde{A^{k-1}_{n}f_{1}}-A^{k-1}f_{2}\|_{2}^{2}$
(174)

Plug in the inductive hypothesis and solve the recurrent to get the bound.

Similarly, if we are instead using Assumption 4.B then we use the other
triangle inequality to conclude:

$\displaystyle\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}$ (175)
$\displaystyle\leq$ $\displaystyle n\sum_{u\in
1/n[n]}\int_{u-\frac{1}{n}}^{u}$
$\displaystyle\int_{u-\frac{1}{n}}^{u}\left(|A\widetilde{[A^{k-1}_{n}f_{1}]}(y)-A[A^{k-1}f_{1}](y)|+|A[A^{k-1}f_{1}](y)-A[A^{k-1}f_{2}](z)|\right)^{2}\textup{d}y\textup{d}z$
(176) $\displaystyle\leq$ $\displaystyle 2n\sum_{u\in
1/n[n]}\int_{u-\frac{1}{n}}^{u}\int_{u-\frac{1}{n}}^{u}\left(A\widetilde{[A^{k-1}_{n}f_{1}]}(y)-A[A^{k-1}f_{1}](y)\right)^{2}\textup{d}y\textup{d}z$
$\displaystyle+2n\sum_{u\in
1/n[n]}\int_{u-\frac{1}{n}}^{u}\int_{u-\frac{1}{n}}^{u}\left(\frac{C_{v}+1}{n}+|A[A^{k-1}f_{2}](z)|n\lambda(E_{z})\right)^{2}\textup{d}y\textup{d}z$
(177) $\displaystyle\leq$
$\displaystyle\frac{3(C_{v}+1)^{2}}{n^{2}}+3\int_{0}^{1}(A[A^{k-1}f_{1}](z)n\lambda(E_{z}))^{2}\textup{d}z+3\|A\widetilde{[A^{k-1}_{n}f_{1}]}-A[A^{k-1}f_{2}]\|_{2}^{2}.$
(178)

Again, we will make use of a heuristic argument to argue that the middle term
can be controlled by controlling $\lambda(E)$ since $A$ sends Lipschitz
functions to Lipschitz functions outside of $E$ and has bounded $L^{1}$ norm
inside of $E$. Therefore:

$\displaystyle\|\widetilde{A_{n}^{k}f_{1}}-A^{k}f_{2}\|^{2}_{2}\leq$
$\displaystyle\frac{3(C_{v}+1)^{2}}{n^{2}}+3\|A\widetilde{[A^{k-1}_{n}f_{1}]}-A[A^{k-1}f_{2}]\|_{2}^{2}.$
(179)

Solve the recurrent to get the result in the statement of the Lemma. ∎

######  Lemma 13.

In the same setting as Lemma 12, recall that a tilde over a function in
$\mathcal{F}_{n}$ denotes its extension to $\mathcal{F}$. If $A$ satisfies
Assumption 2 with constant $C_{A}$ and Assumption 5.A with constant $C_{c}$
and resolution set $\mathcal{N}$. Let $\Phi(h,A,\cdot)=\rho\left(\sum_{g\in
n_{l}}\sum_{k=0}^{K-1}A^{k}\Phi_{g}(h,A,\cdot)\right)$ for some $\Phi_{g}$
graphop neural network such that
$\|\widetilde{\Phi_{g}}(h,A_{n},f)-\Phi_{g}(h,A,\tilde{f})\|_{2}<M$ for all
$g\in[n_{l}]$. Then:

$\|\widetilde{\Phi}(h,A_{n},f)-\Phi(h,A,\tilde{f})\|_{2}^{2}\leq
K^{2}n_{l}^{2}3^{K}\left(Kn^{-2}C_{c}^{2}C_{A}^{2K}+C_{A}^{2K}M\right).$ (180)

If instead $A$ satisfies Assumption 5.B with constant $C_{c}$ then the bound
becomes:

$\|\widetilde{\Phi}(h,A_{n},f)-\Phi(h,A,\tilde{f})\|_{2}^{2}\leq
K^{2}n_{l}^{2}3^{K}\left(Kn^{-2}(C_{c}+1)^{2}C_{A}^{2K}+C_{A}^{2K}M\right).$
(181)

If instead $A$ satisfies Assumption 4.B then the bound becomes:

$\|\widetilde{\Phi}(h,A_{n},f)-\Phi(h,A,\tilde{f})\|_{2}^{2}\leq
K^{2}n_{l}^{2}3^{K}\left(Kn^{-2}(C_{v}+1)^{2}C_{A}^{2K}+C_{A}^{2K}M\right).$
(182)

###### Proof.

We have:

$\displaystyle\|\widetilde{\Phi}(h,A_{n},f)-\Phi(h,A,\tilde{f})\|_{2}^{2}$
(183) $\displaystyle=$
$\displaystyle\sum_{u\in\frac{1}{n}[n]}\int_{u-1/n}^{u}\left(\rho\left(\sum_{g}\sum_{k}\widetilde{A_{n}^{k}\Phi_{g}}(h,A_{n},f)(x)\right)-\rho\left(\sum_{g}\sum_{k}A^{k}\Phi_{g}(h,A,\tilde{f})(x)\right)\right)^{2}\textup{d}\lambda(x)$
(184) $\displaystyle\leq$
$\displaystyle\sum_{u\in\frac{1}{n}[n]}\int_{u-1/n}^{u}\left(\sum_{g}\sum_{k}\widetilde{A_{n}^{k}\Phi_{g}}(h,A_{n},f)(x)-A^{k}\Phi_{g}(h,A,\tilde{f})(x)\right)^{2}\textup{d}\lambda(x)$
(185) $\displaystyle\leq$
$\displaystyle\sum_{u\in\frac{1}{n}[n]}\int_{u-1/n}^{u}\left(\sum_{g}\sum_{k}\left|\widetilde{A_{n}^{k}\Phi_{g}}(h,A_{n},f)(x)-A^{k}\Phi_{g}(h,A,\tilde{f})(x)\right|\right)^{2}\textup{d}\lambda(x)$
(186) $\displaystyle\leq$ $\displaystyle
Kn_{l}\sum_{u\in\frac{1}{n}[n]}\int_{u-1/n}^{u}\sum_{g}\sum_{k}\left(\left|\widetilde{A_{n}^{k}\Phi_{g}}(h,A_{n},f)(x)-A^{k}\Phi_{g}(h,A,\tilde{f})(x)\right|\right)^{2}\textup{d}\lambda(x)$
(187) $\displaystyle=$ $\displaystyle
Kn_{l}\sum_{g}\sum_{k}\|\widetilde{A_{n}^{k}\Phi_{g}}(h,A_{n},f)(x)-A^{k}\Phi_{g}(h,A,\tilde{f})(x)\|_{2}^{2}$
(188) $\displaystyle\leq$ $\displaystyle
Kn_{l}\sum_{g}\sum_{k}\frac{3^{k+1}kC_{c}^{2}C_{A}^{2k}}{n^{2}}+3^{k}C_{A}^{2k}\|\widetilde{\Phi_{g}}(h,A_{n},f)-\Phi_{g}(h,A,\tilde{f})\|_{2}^{2}$
(189) $\displaystyle\leq$ $\displaystyle n^{-2}n_{L}^{2}\cdot K^{3}\cdot
C_{c}^{2}\cdot 3^{K}C_{A}^{2K}+K^{2}\cdot n_{l}^{2}\cdot 3^{K}C_{A}^{2K}\cdot
M$ (190) $\displaystyle=$ $\displaystyle
K^{2}n_{l}^{2}3^{K}\left(Kn^{-2}C_{c}^{2}C_{A}^{2K}+C_{A}^{2K}M\right),$ (191)

where in the first line, we use the fact that continuous extension commutes
with finite element-wise sum and element-wise application of $\rho$, while
expanding $L^{2}$ norm; the second line uses Lipschitz property of $\rho$; the
third line uses triangle inequality; the fourth line uses equivalence of
$p$-norms in finite dimensional vectors; the fifth line is again $L^{2}$ norm
definition; the sixth line applies Lemma 12 and the rest is algebra.

To get the rest of the cases, applies different versions of Lemma 12. ∎

######  Lemma 14.

Let $\Phi$ be an $L$-layer graphop neural network in the same setting as Lemma
12. If $A$ satisfies Assumption 5.A with constant $C_{c}$ then:

$\|\widetilde{\Phi}(h,A_{n},f)-\Phi(h,A,\tilde{f})\|_{2}\leq
n^{-1}(3^{K}Kn_{\max}C_{A}^{K})^{L}\max\left(C_{v},3^{K}K^{2}C_{c}n_{\max}C_{A}^{K}\right).$
(192)

If instead $A$ satisfies Assumption 5.B with constant $C_{c}$ then the bound
becomes:

$\|\widetilde{\Phi}(h,A_{n},f)-\Phi(h,A,\tilde{f})\|_{2}\leq
n^{-1}(3^{K}Kn_{\max}C_{A}^{K})^{L}\max\left(C_{v},3^{K}K^{2}(C_{c}+1)n_{\max}C_{A}^{K}\right).$
(193)

If instead $A$ satisfies Assumption 4.B then the bound becomes:

$\|\widetilde{\Phi}(h,A_{n},f)-\Phi(h,A,\tilde{f})\|_{2}\leq
n^{-1}(3^{K}Kn_{\max}C_{A}^{K})^{L}\max\left(C_{v},3^{K}K^{2}(C_{v}+1)n_{\max}C_{A}^{K}\right).$
(194)

###### Proof.

Solve the recurrent in Lemma 13. ∎

We now prove a more general version of Theorem 3

######  Theorem 6.

Let $A\in\mathcal{F}$ satisfying Assumption 2 with constant $C_{A}$ and
Assumption 5.A with constant $C_{c}$ and resolution set
$\mathcal{N}\subseteq\mathbb{N}$. Let $n\in\mathcal{N}$ and form the
discretization $A_{n}$ as per Theorem 2. Let $h$ be normalized such that
$|h|\leq 1$ element-wise and form the graphop neural network
$\Phi(h,A,\cdot):\mathcal{F}\to\mathcal{F}$ and
$\Phi(h,A_{n},\cdot):\mathcal{F}_{n}\to\mathcal{F}_{n}$. We have the following
approximation bound:

$d_{M}(\Phi(h,A,\cdot),\Phi(h,A_{n},\cdot))\leq
n^{-1/2}P_{1}\sqrt{\overline{C_{A}}C_{v}+C_{c}n_{\max}C_{A}^{K}\cdot
P_{2}}+C_{v}n^{-1}$ (195)

where $P_{1}=3^{KL}$ and $P_{2}=3^{K}K^{2}$.

If instead $A$ satisfies Assumption 5.B with constant $C_{c}$ then the bound
becomes:

$d_{M}(\Phi(h,A,\cdot),\Phi(h,A_{n},\cdot))\leq
n^{-1/2}P_{1}\sqrt{\overline{C_{A}}C_{v}+(C_{c}+1)n_{\max}C_{A}^{K}\cdot
P_{2}}+(C_{v}+1)n^{-1}$ (196)

If instead $A$ satisfies Assumption 4.B then the bound becomes:

$d_{M}(\Phi(h,A,\cdot),\Phi(h,A_{n},\cdot))\leq
n^{-1/2}P_{1}\sqrt{\overline{C_{A}}C_{v}}+(C_{v}+1)n^{-1}$ (197)

###### Proof.

The proof structure is similar to the proof of Theorem 2. For brevity of
exposition, we will write $h$ as the (shared) set of parameters in the graphop
neural networks and shorten $\Phi:=\Phi(h,A,\cdot)$ and
$\Phi_{n}:=\Phi(h,A_{n},\cdot)$. Fix $k\in\mathbb{N}$, we will bound
$\sup_{\eta\in\mathcal{S}_{k,C_{v}}(\Phi)}\inf_{\overline{\eta}_{n}\in\mathcal{S}_{k,C_{v}}(\Phi_{n})}d_{LP}(\overline{\eta},\overline{\eta}_{n})$.

Fix arbitrary $\overline{\eta}\in\mathcal{S}_{k,C_{v}}(\Phi)$. By definition
of a $(k,C_{v})$-profile, there exists $f_{1},\ldots,f_{k}\in
L^{\infty}_{\text{reg}(C_{v})}([0,1])$ such that
$\overline{\eta}=\mathcal{D}_{\Phi}(f_{1},\ldots,f_{k})$. For all $j\in[k]$,
let $\mathcal{F}_{n}\ni f^{\prime}_{j}:[n]/n\ni
u\mapsto\int_{u-1/n}^{u}f_{j}(z)\textup{d}\lambda(z)$. That $f^{\prime}_{j}\in
L_{\text{reg}(C_{v})}^{\infty}([n]/n)$ is shown in Lemma 9. Set
$\overline{\eta}_{n}=\mathcal{D}_{\Phi_{n}}(f_{1}^{\prime},\ldots,f_{k}^{\prime})$.

#### Bounding $d_{LP}(\overline{\eta},\overline{\eta}_{n})$.

Fix some $\epsilon>0$ to be specified later, by definition of $d_{LP}$, we
need to bound, for each $U\in\mathcal{B}_{k}$:

$\displaystyle\overline{\eta}(U)-\overline{\eta}_{n}(U^{\epsilon})=\int_{0}^{1}\mathbbm{1}_{(f_{1}(x),\ldots,\Phi
f_{k}(x))\in
U}\textup{d}\lambda(x)-\sum_{u\in[n]/n}\frac{1}{n}\mathbbm{1}_{(f^{\prime}_{1}(u),\ldots,\Phi_{n}f^{\prime}_{k}(u))\in
U^{\epsilon}}.$ (198)

Notice that since $\lambda$ is the Lebesgue measure, one can denote
$y_{x}=\left\lceil xn\right\rceil/n$ and write:

$\displaystyle\overline{\eta}(U)-\overline{\eta}_{n}(U^{\epsilon})=\int_{0}^{1}\mathbbm{1}_{(f_{1}(x),\ldots,\Phi
f_{k}(x))\in
U}-\mathbbm{1}_{(f^{\prime}_{1}(y_{x}),\ldots,\Phi_{n}f^{\prime}_{k}(y_{x}))\in
U^{\epsilon}}\textup{d}\lambda(x).$ (199)

Since the integrand is only positive when $(f_{1}(x),\ldots,\Phi f_{k}(x))\in
U$ and $(f^{\prime}_{1}(y_{x}),\ldots,\Phi_{n}f^{\prime}_{k}(y_{x}))\not\in
U^{\epsilon}$ and this conjuction only happens when $\|(f_{1}(x),\ldots,\Phi
f_{k}(x))-(f^{\prime}_{1}(y_{x}),\ldots,\Phi_{n}f^{\prime}_{k}(y_{x}))\|_{2}>\epsilon$,
we have:

$\displaystyle\overline{\eta}(U)-\overline{\eta}_{n}(U^{\epsilon})\leq\lambda(\mathcal{E}(\epsilon))\leq\sum_{j=1}^{k}\lambda(\mathcal{E}_{j}^{0}(\epsilon))+\lambda(\mathcal{E}_{j}^{1}(\epsilon)),$
(200)

where

$\displaystyle\mathcal{E}(\epsilon)$
$\displaystyle:=\\{x:\|(f_{1}(x),\ldots,\Phi
f_{k}(x))-(f^{\prime}_{1}(y_{x}),\ldots,\Phi_{n}f^{\prime}_{k}(y_{x}))\|_{2}>\epsilon\\},$
(201) $\displaystyle\mathcal{E}_{j}^{z}(\epsilon)$
$\displaystyle=\\{x:|\Phi^{z}f_{j}(x)-\Phi^{z}_{n}f^{\prime}_{j}(y_{x})|>\frac{\epsilon}{\sqrt{2k}}\\},\text{
for }z\in\\{0,1\\},j\in[k],$ (202)

where $B^{0}$ is the identity operator for any operator $B$ in the appropriate
space.

#### Bounding $\lambda(\mathcal{E}^{1}_{j}(\epsilon))$.

Fix $j\in[k]$, we have:

$\displaystyle\int_{0}^{1}|\Phi
f_{j}(x)-\Phi_{n}f^{\prime}_{j}(y_{x})|\textup{d}x\leq\sqrt{\int_{0}^{1}\left(\Phi
f_{j}(x)-\Phi_{n}f^{\prime}_{j}(y_{x})\right)^{2}}\textup{d}x$ (203)
$\displaystyle=$ $\displaystyle\|\Phi
f_{j}-\widetilde{\Phi_{n}}f^{\prime}_{j}\|_{L^{2}}$ (204) $\displaystyle\leq$
$\displaystyle
n^{-1}(3^{K}Kn_{\max}C_{A}^{K})^{L}\max\left(C_{v},3^{K}K^{2}C_{c}n_{\max}C_{A}^{K}\right).$
(205)

where the last line uses Lemma 14 under Assumption 5.A with constant $C_{c}$.
Similar results are obtained for the other assumptions.

We also have:

$\int_{0}^{1}|\Phi
f_{j}(x)-\Phi_{n}f^{\prime}_{j}(y_{x})|\textup{d}x\geq\lambda(\mathcal{E}_{j}^{1}(\epsilon))\cdot\frac{\epsilon}{\sqrt{2k}}+0.$
(206)

Thus selecting

$\epsilon>\sqrt{2k\sqrt{2k}\cdot
n^{-1}(3^{K}Kn_{\max}C_{A}^{K})^{L}\max\left(C_{v},3^{K}K^{2}C_{c}n_{\max}C_{A}^{K}\right)}$
(207)

makes $\lambda(\mathcal{E}_{j}^{1}(\epsilon))<\frac{\epsilon}{2k}$. ∎

#### Bounding $\lambda(\mathcal{E}_{j}^{0}(\epsilon))$.

This step simply uses Lipschitzness of the graph signal to bound its
discretization and is thus identical to that in Theorem 2. In short, choosing
$\epsilon>\sqrt{2k}C_{v}/n$ gives $\lambda(\mathcal{E}_{j}^{0}(\epsilon))=0$.

#### Bounding
$\sup_{\eta_{n}\in\mathcal{S}_{k,C_{v}}(\Phi_{n})}\inf_{\eta\in\mathcal{S}_{k,C_{v}}(\Phi)}d_{LP}(\eta,\eta_{n})$.

This direction is almost the same as the previous bounds, just as in Theorem
2. We will provide the complete proof in a later version of the paper but the
same choice of $\epsilon$ works to bound this side of the Hausdorff metric.

#### Putting everything together

Defining $\overline{C_{A}}=(n_{\text{max}}KC_{A}^{K})^{L}$ gives a choice of:

$\overline{\epsilon}=n^{-1/2}P_{1}\sqrt{\overline{C_{A}}C_{v}+C_{c}n_{\max}C_{A}^{K}\cdot
P_{2}}+C_{v}n^{-1}$ (208)

where $P_{1}=3^{KL}$ and $P_{2}=3^{K}K^{2}$.

For other choices of assumptions, we obtain similar bounds.

##  Appendix F Additional results

###  F.1 Proof of Theorem 4

Because of completeness of $d_{H}$ in the space of closed subsets of
$\mathcal{P}(\mathbb{R}^{2k})$ for every $k\in\mathbb{N}$, the statement in
Theorem 4 is equivalent to showing that for each $k\in\mathbb{N}$, we have
$\mathcal{S}_{k,L(n)}(A_{n})$ converges to $\mathcal{S}_{k}(A)$ in $d_{H}$. We
do this via a mollificaition argument.

######  Definition 5 (Lipschitz mollifier).

A _Lipschitz mollifier_ in $\mathbb{R}$ is a smooth (infinitely
differentiable) function $\phi:\mathbb{R}\to\mathbb{R}$ satisfying:

  1. 1.

$\int_{\mathbb{R}}\phi(x)\textup{d}\lambda(x)=1$.

  2. 2.

$\lim_{\epsilon\to
0}\phi_{\epsilon}(x):=\lim_{\epsilon}\epsilon^{-1}\phi(x/\epsilon)=\delta(x)$
\- the Dirac function.

  3. 3.

Although not standard, we require $\phi$ to be $1$-Lipschitz and symmetric
around $0$ ($\phi(x)=\phi(-x)$).

Given a measureable function $f\in L^{\infty}_{[-1,1]}(\mathbb{R})$, defines
the convolution operation:

$f\ast\phi:x\to\int_{\mathbb{R}}f(y)\phi(y-x)\textup{d}\lambda(y).$ (209)

The next result shows the existence of such a function:

######  Lemma 15.

Let $\phi:\mathbb{R}\to\mathbb{R}$ be:

$\phi(x)=\begin{cases}e^{-(1-x^{2})^{2}}/Z&\text{ if }|x|\leq 1\\\ 0&\text{
otherwise,}\end{cases}$ (210)

where $Z$ is a normalization constant to make sure that
$\int_{\mathbb{R}}\phi\textup{d}\lambda=1$. Then $\phi$ is a Lipschitz
mollifier.

###### Proof.

The first property is built into the definition. The second property is
obvious since the support of $\phi(x/\epsilon)$ is $[-\epsilon,\epsilon]$ and
thus it converges to the Dirac function as $\epsilon$ goes to $0$. Lipschitz-
ness can be seen by computing the first derivative (since the function is
smooth) over $(-1,1)$ and see that it is bounded in $[-1,1]$. Symmetry is also
obvious since the function depends only on the absolute value of its argument.
∎

Consequences of a Lipschitz mollifier include:

######  Lemma 16.

Let $\phi$ be a Lipschitz mollifier and $\epsilon>0$, then for any measurable
$f\in\mathcal{F}_{[-1,1]}^{\infty}(\mathbb{R})$, $f\ast\phi_{\epsilon}$ is
$\max(1,\epsilon^{-2})$-Lipschitz and $\lim_{\epsilon\to
0}\|f-f\ast\phi_{\epsilon}\|_{2}=0$.

###### Proof.

For the first part of the statement, consider:

$\displaystyle\left|f\ast\phi_{\epsilon}(x)-f\ast\phi_{\epsilon}(y)\right|$
$\displaystyle=\left|\int_{\mathbb{R}}f(z)\phi_{\epsilon}(z-x)-f(z)\phi(z-y)\textup{d}\lambda(z)\right|$
(211)
$\displaystyle\leq\int_{\mathbb{R}}\left|\frac{f(z)}{\epsilon}\left(\phi\left(\frac{z-x}{\epsilon}\right)-\phi\left(\frac{z-y}{\epsilon}\right)\right)\right|\textup{d}\lambda(z)$
(212)
$\displaystyle\leq\frac{1}{\epsilon}\int_{\mathbb{R}}\left|\frac{z-x}{\epsilon}-\frac{z-y}{\epsilon}\right|\textup{d}\lambda(z)$
(213) $\displaystyle\leq\frac{|x-y|}{\epsilon^{2}}$ (214)

For the second part, we have:

$\displaystyle|f\ast\phi_{\epsilon}(x)-f(x)|$
$\displaystyle\leq\int_{\mathbb{R}}\phi_{\epsilon}(z-x)|f(z)-f(x)|\textup{d}\lambda(z)$
(215)
$\displaystyle\leq\int_{\mathbb{R}}\phi_{\epsilon}(z)|f(z+x)-f(x)|\textup{d}\lambda(z),$
(216)

where we use two changes of variables.

Square both sides and take integral over $x$ and use Jensen inequality to get:

$\displaystyle\|f\ast\phi_{\epsilon}-f\|_{2}^{2}$
$\displaystyle\leq\int_{\mathbb{R}}\int_{\mathbb{R}}(\phi_{\epsilon}(z))^{2}(f(z+x)-f(x))^{2}\textup{d}\lambda(z)\textup{d}\lambda(x).$
(217)

Apply Fubini-Tonelli theorem to factorize the mollifier, we get:

$\displaystyle\|f\ast\phi_{\epsilon}-f\|_{2}^{2}$
$\displaystyle\leq\int_{\mathbb{R}}\int_{\mathbb{R}}(f(z+x)-f(x))^{2}\textup{d}\lambda(x)(\phi_{\epsilon}(z))^{2}\textup{d}\lambda(z)$
(218)
$\displaystyle=\int_{\mathbb{R}}\left(\epsilon^{-1}\int_{\mathbb{R}}(f(z+x)-f(x))^{2}\textup{d}\lambda(x)\right)(\phi(z\epsilon^{-1}))^{2}\textup{d}\lambda(z).$
(219)

Apply a final change of variable:

$\displaystyle\|f\ast\phi_{\epsilon}-f\|_{2}^{2}\leq\int_{\mathbb{R}}\left(\int_{\mathbb{R}}(f(z\epsilon+x)-f(x))^{2}\textup{d}\lambda(x)\right)(\phi(z))^{2}\textup{d}\lambda(z).$
(220)

Therefore, as $\epsilon$ goes to $0$, the inner integrand goes to $0$. Since
$f$ and $f\ast\phi_{\epsilon}$ are all bounded (as $f\in[-1,1]$) for small
enough $\epsilon$, we can apply dominated convergence to conclude that the
integral itself goes to $0$ and thus the $2$-norm on the left hand side also
goes to $0$. ∎

We are now ready to proceed with the proof of Theorem 4. Given an element
$\eta\in\mathcal{S}_{k}(A)$, there exists a set of functions
$F=\\{f_{1},\ldots,f_{k}\\}\subseteq L^{\infty}_{[-1,1]}([0,1])$. Each of
these functions can be extended to $\mathbb{R}$ by setting $f(x)=f(0)$ if
$x\leq 0$ and $f(x)=f(1)$ if $x>1$. Call the extended function $f^{\prime}$.
Now we can apply mollification convolution to each of them to get a family of
functions
$\\{f_{j,\epsilon}:=f^{\prime}_{j}\ast\phi_{\epsilon}\\}_{j\in[k],\epsilon>0}$.
Recall that we have shown $f_{j,n}:=f_{j,1/\sqrt{L(n)}}$ to be
$L(n)$-Lipschitz for each $n\in\mathbb{N}$. Let $f^{\prime\prime}_{j,n}$ be
the restriction of $f_{j,n}$ to $\mathcal{F}_{n}$. Then
$f^{\prime\prime}_{j,n}$ is still $L(n)$-Lipschitz and thus we can find a
profile for
$F^{\prime\prime}_{n}:=\\{f^{\prime\prime}_{1,n},\ldots,f^{\prime\prime}_{k,n}\\}$
in $\mathcal{S}_{k,L(n)}(A_{n})$.

Furthermore, by property of mollifier and the fact that $L(n)\to\infty$ as $n$
goes to infinity, we have $\|f_{j,n}-f^{\prime}_{j}\|_{2}\to 0$ with
$n\to\infty$. Since $f^{\prime}_{j}$ is constant outside $[0,1]$, we also have
$\|f_{j,n,|[0,1]}-f_{j}\|_{\mathcal{F}}\to 0$ with $n$. Using the same proof