Limits, approximation and size transferability for GNNs on sparse graphs via graphops
Authors: Thien Le
Stefanie Jegelka
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
convolution
graph limits
size transferability
TL;DR: We prove rigorously convergence and size transferability theorems of GNNs associated with sparse graphs by introducing a limit notion of GNN using graphops

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.

Limits, approximation and size transferability for GNNs on sparse graphs via graphops
Thien Le MIT thi chienle@mit.ede
Stefanie Jegelka TU Munich and MIT stefje@csail.m mitaaiiiiiii........m.aaa.mie..m edu
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 transforability and approximation results via graph limits, e.g., via graphons, these only apply nontrivially dense graphs. To include frequently en- countered sparse graphs such as bounded-degree or power law graphs, we take perspective of taking limits of operators derived from graphs, such as the iogregalion operation that makes 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 tasks (Gilmer et al., 2017; Scarselli et al., 2009; Kipf and Welling, 2017; Bronstein et al., 2017). Following the mounting success of applied GNN rescarch, thcoretical analyses follow with many works studying GNNs' representational power (Azizian and Lelarge, 2021; Morris et al., 2019; Xu al., 2019, 2020; Garg et al., 2020; Chen et al., 2020; Maron et al., 2019; Loukas, 2020a,b; Abboud et al., 2021).
hitherto less addressed question of practical importance the possibility of size gener- alization, i.e., transferring a learned GNN to graphs of different sizes (Ruiz et al., 2023a; Levie et al., 2022; Xu et al., 2021; Yehudai et al., 2021; Bevilacqua al., 2021; Chuang and Jegelka, 2022; Roddenberry et al., 2022; Maskey et al., 2022, 2023), especially for sparse graphs. For instance, it would be computationally desirable train 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: Ychudai et al., 2021; Jegelka, 2022) and what output perturbations we may expect. For a formal analysis of perturbations and conditions, we need suitable graph representation that captures inductive biases and allows us compare models for graphs of different sizes. Graph limils can help to formalize this, as they help understand biases as the graph size tends infinity.
Formally, approzimation theory asks for bounds between a GNN on a finite graph and its infinite counterpart, while transferabilityy compares model outputs on graphs of different sizes.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

The quality of the bounds depends on how the two GNNs (and corresponding graphs) are intrinsically linked, in particular, to what extent they share relevant structure. This yields conditions for size generalivation. For example, the graphs could be sampled from the same graph limit (Ruiz et al., 2023a) or from the same random graph model (Keriven et al., 2020).
In particular, Ruiz et al. (2023a) 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, polymer graphs, Hamming graphs (including hypercubes for crror-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 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.
Schramm limit of random rooted graphs (Benjamini and Schramm,
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 circunventing 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 Donvolution/aggreaaaioo We show how the operator perspective allows us to define limits of GNNs of infinite sequences of 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., 2023a; Maskey et al., 2023) to a much wider set of graphs.
operations.
Yet, using graphops requires technical work. For instance, we need to introduce an appropriate discretization of 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. We define graphop convolution, i.e., an operator that includes both finite graph convo- lutions and a limit version that allows us to define a limit object for GNNs applied to graphs of size n + co.
2. We rigorously prove an approximation theorem (Theorem 2) that bounds distance between a graphop A (acting on infinite-dimensional space) and and appropriate dis- cretization An (acting on IR"), in the dm metric introduced by Backhausz and Szegedy (2022). Our result applics to a more general set of nonlincar operators, and implics a transferability bound between finite graphs (discretizations) of different sizes.
3. For neural networks, we present 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
A summary of comparisons between our framework and related papers is in Table 1.
In structure, the closest related work (Ruiz et al., 2023a), which derives approximation and transferability theorems for graphon neural networks, i.e., dense graphs. For graphons, the convoluitn kernel has a nice spectral decomposition, which is exploited by Ruiz et al.
Rate of convergence to a small positive constant. For convergence to 0, Ruiz al. (2020) showed the rate of O(n -1/2)
2

---

Sparse
Dense
Bounded-degree (z)
Relatively-sparse
Number of edges
(1 log n)
((x*)
infinite grids,
hypereubes,
Examples covered under our assumptions
graphons
polymer graphi
Hamming graphs
Graphons (Ruiz et al., 2023a)
On "
Unbounded graphons (Maskey et al., 2023)
inexplicit
Random graph model (Keriven et al., 2020)
(((log 1/2)
O(n 1/2)
Spectral methods (1 layer) (Levie et al., 2022)
inexplicit
inexplicit
Graphings (I layer) (Roddenberry et al., 2022)
inexplicit
P-operators and graphops (ours)
O(n-173)
O(n 0(m-1/2) O(n 1/2)
Table 1: Summary of our results compared to related work. Quantitative results (e.g. 0(n-1/3) upper-bound the distance between GNNs on sampled graphs of size n and the limiting object in term of n (in an appropriate metric and limit notion). Empty cells are graph models where the approaches in the corresponding papers do not apply to or give trivial bounds (e.g. bounds that compare to a constant-O graphon). "Tnexplicit" refers to asymptotic results where rates of convergence is not explicit.
(2023a). In contrast, sparse graph limits are not known to enjoy nice convergence of the spectrum (Backhausz and Szegedy, 2022; Aldous and Lyons, 2007), also Appendix C.I, 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. (2023a). For instance, they allow the convolution degree K + o and perform the analysis in the spectral domain, whereas our K is assumed to be fixed finite constant. As result, their bound has better dependence of O(1/n) on n-the resolution of discretization, but does not go to 0 as n + co. Ours have extra dependence on K and a slower rate of O(n but our bounds go to as + xc. Maskey et al. (2023) obtains further results for graphons Ruiz et al. (2023b) studies the spectrum of sparser (but still O(n²) edges) graphons.
unbounded domain.
Other works use other notions than graph limits to obtain structural coherence. Levic et al. (2022) obtain a transferability result for spectral graph convolution networks via analysis in frequency domains. They sample finite graphs from general topologies opposed to graph limit. Their graph signals are assumed to have finite bandwidth while ours only assumed to be in 122. Their signal discretiiattin 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 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, hthrerie,, they use the Euclidean metric between the two graph signals. This metric hence docs not capture combinatorial, structural differences of functions on non-isomorphic graphs. To study transferability, Keriven et al. (2020) sample from standard random graph models, resulting in a bound of order 0(n-1/2) for dense graph and O(logn) -)1/2) for relatively-sparse graphs. They do not cover bounded- degree graphs and their bounds hold with high probability. Tn general, having access to deterministic graph limit is considered a weaker assumption than having access to truly random graphs since large graphs satisfy some notion of 'almost randomness' (e.g. via Szemerédi regularity lemma). There are fascinating, tangile separations between graph limits and random graphs, especially among sparse graphs, that are outside the scope of this paper.
Adjacent to transferability studics, Bevilacqua et al. (2021) (also inspired by Lovász and Szegedy (2006)) uses induced homomorphism density to construct a graph representation that works across graph sizes and demonstrates empirical gains in using this larger representation. Maskey al. (2022) uses graph limits to deduce generalization bounds for GNNs.
2 Background
Notation Let N be (1.2....} and write [n] = {l...., n) for any n e N. For a scalar a E R and set S C R, let aS = {as S}. 'A.e. stands for 'almost everywhere!
3

---

For a measure space (Ω, D0,B.1 p)) and E [0) denote by LP( the corresponding L function spaces with norm I f + (Sa lfl'du) For any p,g E [1, oo], define the operator norms || 11pl-m A + suP
For function spaces, we use F = ([0, 1)) and F, = 1.3 ([[[[/n)) for any n E N. For any LP space H. denote by H4-111 the restriction to functions with range in [-1,1] a.e. and HLip(L) the restriction to functions that are T-Tiisccitz a.e. and Heeg(L) H1-1.1 O HLip(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 - and a function X : V + (called graph signal or node features), a GNN ΦF (F for 'finite" with L layers, neurons at the i-th layer, nonlinearity and learnable parameters h, is:
Or X2 G,X),
(1)
T4-1 G. G,),, = P Egn (h, ()).))))))
IE [L) [mi
(2)
Xo(h, G
(3)
where [Xils is the output of the f-th neuron in the 1-th layer, which is another graph signal. The input graph information is captured through order K graph convolutions Ai,f, (h, G) == Ex G 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 bi.f.g.k highlights that there is a learnable parameter for each convolution order k, between each neuron I and from layer I 1-1 to layer the neural norw Thus, the number of learnable parameters in GNN does not depend the number of vertices of the graph.
2.1 Graph limits
Graph limit theory involves embedding discrete graphs into rich topological or geometric spaces and studying the behavior of convergent (c.g. in sizo) graph sequences.
Dense graphs A popular example of graph limits are graphons symmetric ([0, 1)9) ([abesgue-measurable) functions whose value at (2.,)) can be thought of (intuitively) as the weight of the zy-edge in a graph with vertices in [0, 1]. Convergence in this space, under the cut metric (see Appendix for the exact definition), is dubbed dense graph convergence because for any W E L' ([0, || 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., 2023a).
Graphing (Lovász, 2012), is a direct counterpart of a graphon for sparse graphs. Recall that graphons are not suitable for sparse graphs because the Lebesgue measure on ([0, 1J2) is not fine enough to detect edges of bounded-degres graphs. Therefore, one solution is to consider other measure spaces. Graphings are quadruples (V,A, X, E) where V and E are interpreted as the usual vertex and edge sets and A, together form a Borel measure such that E is in A x A satisfying a symmetry condition. While Lebesgue measures constructed from a specific topology of open sets on 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 o-algebra.
Sparse graphs
Furthermore, famous open conjecture by Aldous and Lyons (2007) asks whether all graphings are weak local limits of some sequence of bounded-degroe 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. (2023a) for dense graphs. As result, expect
The architecture is known graph convolutional networks, but we call them GNNs for brevity.

---

some regularity assumptions on the graph sequence for any work that handles sparse graph limits, unless the authors try to tackle this conjecture itself. A self- self-contained summary of graphings within the scope of this paper is provided in Appendix C. Infinite paths and cycles also have nice descriptions 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 straightforward for finite graphs: both the adjacency matrix and Laplacian, each defining unique graph, are linear operators on ##verticess Moreover, viewing graphs as operators is exactly what we do with GSOs and graph convolutions. Hence, graphop seems to be 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) and discontinuity of eigenvalues at the limit (Appendix C.1). Moreover, to understand GNN transferability from size m to n, one needs compare an m X matrix with an n X n matrix, which is nontrivial. This is done by comparing their actions on Ih versus R". 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 (not necessarily linear) P-operators For an n-vertex graph, its adjacency matrix, Laplacian, or random walks kernels are examples of operators on [?[[nn/)). To formally generalize to the infiniteverrtex case, Backhausz and Szegedy (2022) use P-operators, which are linear operators from L (I2) to L' (12) with finite ||A| In this paper, further assume they have finite || 112-22 norm but are not necessarily linear. This allows us to consider nonlinear GNN layers and the whole GNN itself in the same framework.
Graphops P-operators lead to a notion of graph limit that applics to both dense and sparse graphs. Gruphops (Backhausz and Szegedy, 2022) are positivity-preeevingg" self-adjoint P-operators. Adjacency matrices finite graphs, graphons (Lovász and Szegedy, 2006), and graphings (Lovász, 2012) are all examples of graphops.
(k, L)-rofiile of a nonlinear P-operator Actions of graphops are formally captured through their (k, prooffiees,, and these will be useful to compare different graphops. Pick k E N, L E [0, oo] and A a P-operator on (52, B. Intuitively, we will take k samples from the space our operators act on, apply our operator to get & images, and concatenate samples and images into a joint distribution on 22 which gives us one clement of the profile. For instance, for n-vertex graphs, the concatenation results in matrix M E R so each joint distribution 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 D(u,,..., uk) the pushforward of J via + (vI(x),.... ., vx(x)) for any tuple (v) E (2)). The (k, pproffie of A is: (A) = (D(u1,....
Au AUA)= : &. E Leg(2) (2), i 1...
(4)
Formally, denote by P(R*) the set of Borel probability distributions over 222_ Regardless of the initial graph size, or the space on which the operators act, (k, L)-profiles of A are always some subsets of P ((B22) which allow us to compare operators acting on different spaces.
Convergence of P-operators We compare two profiles (closed subsets X,Y C P(R22) via a Hausdorff metric du (X,Y)= == max(sup infyer drr(r, y), sup,ey infzex dir(z, y)).
3 accton on positive functions results in positive functions. This condition can be swapped out for "positiveness' ((Ar, x) 0, Vr Dom(A))(0)) to allow for Laplacians.
5

---

Here, dLP is the Lévy-Prokhoroe metric on P(R2k) (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 at the same time as
das ( (A, (A, B) = Σ k=1
(S
Intuitively, we allow du to grow subexponentially in k by the scaling 2 Our dcfinition of profile slightly differs from that of Backhausz and Szegedy (2022), using Leg(z) instead of their 11-1.11 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 some intermediate density graphs:
Theorem 1 (Theorem 1.1 Backhausz and Szegedy (2022)). Convergence under dm is equivalent (results in the some 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, + G. For finite GNNs (Equ (2)), fixing the graph input G; and learnable parameter h results in a function @ G., that transforms the input graph signal (node features) into an output graph signal. The transferability question asks how similar y Gi, )) is to (h, G). for some i # j. In our approach using approximation theory, will compare both functions to the limiting function on G. This is done by appropriate lift of the GNN onto a larger space that we call graphop neural networks.
We then introduce discretization scheme of graphop neural networks to obtain finile GNNs, similar to graphon sampling (Ruiz et al., 2023a) and sampling from lopological spaces (Levie et al., 2022). Finally, Lemma 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 GNN act on graph signals, graphops act on some L signals (called graphop signals). The generalization is straightforward: replacing GSOs in the construction of the GNN in Equ. (2) with graphops results in graphop convolution and replacing graph convolution with graphop convolutoo gives graphop neural networks.
Formally, fix a maximum order K e N. For some measure space (Ω, B, p), select a graphop A (22 (22 and graphop signal X E (2)) We define graphop convolution operator as weightod sum of at most K applications of A: A)]] == K (ha where T are (learnable) filter parameters and A is the composition of k duplicates of A. The square bracket [r]: indicates the i-th entry of a tuple
For some number of layers L E N. (mihee N, no == 1, define graphop neural network with L layers and n, features in layer as:
A, = (h,
(6)
A,, = p (ETH g=1
H(h A) SE(nI
LE [4],
(7)
Xo, = X
(8)
with filter parameter tuple = (h .o.....,h" ,h),, k² (R& for any E [L], and graphop signal tuple X₁ E (L)())))* for any E [O). Equ (7) and Eqn (2) are almost identical, with the only difference being the imput/outpur 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 F F. we first sample a GSO and plug it into Equ (2). Choose a resolution m E N and define the GSO Am, for any graph signal X E Fm (defined in Section 2) as:
An) == m '" (AX)dA,
v E [m]/m,
(9)
Pm (h, A, := (h, Am, X),
(10)
where graphop signal X E is an extension of graph signal X E Fm defined as [um]]
((u)== =
u [0,
(11)
m
Shared structural properties of sampled graphs The discretization scheme introduced for graphop can be intuitively understood as partitioning the vertex set into finitely many sets and merging nodes and their connections in these sets, with an appropriate scaling of the edge weights. Imagine blurring an n x n matrix into an n/2 x n/2 matrix by wverage-pooling over each disjoint 2 2 square. As n oo (and even for uncountable [0, 1]), this makes rigorous the notion of making a high-resolution graph on a huge number of vertices more 'blurry' by merging nodes in way that still maintains some smoothness conditions, which is reminiscent of the real-world procedures of training with low-resolution images before fine-tuning with higher-rosolution ones, or sampling from low-frequency graph Fourier transform domain.
Note that if A linear then Am necessarily lincar, but our definition of graphop does not require linearity. Therefore, Am 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 F F is self-adjoint, then for each resolution m E N, the discretization Am Fm -> Fm defined above is also self-adjoint.
The proof can be found in Appendix B. Compared to previous works, our discretization scheme in Eqn (9) looks slightly different. Tn Ruiz et al. (2023a); given a graphon W : [0, 1]2 -, R. the discretization at resolution n was defined by forming the matrix S E R : Si,j = (it/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.jj/n)...j E [n] are in the same L class of functions, but will give rise to completely different samples. Furthermore, not every L class of functions has continuous representative. This means that our discretization scheme is strictly more general than that used by Ruiz et al. (2023a) 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.
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 discretixation
Theorem 2 (Approximation theorem). A: F be P-operator satisfying Assumption 2 with constant Ca: Assumption 3.A or 3.B with resolutions in N. Fir n E N and consider (k: -roofeese Let An : Fn + Fn be a discretization of as defined in Equ (9). Then:
CAC. Cr +1
dm Am) $2
(12)
n
n

---

Compared to theorems in Ruiz et al. (2023a), our explicit dependence on n has an extra n n-1/2 term that stems from techniques used to bound the Lévy-Prokhoror distance between two entry distributions obtained from functions that differ by at most O(n in I norm.
As an immodiate corollary, invoking the triangle incquality yields a transferability bound.
Corollary 1 (Transferabilityy. Let A: + F a Pooperator satisfyinn assumptions of Theorem with constant CA and resolutions N. For any m EN, let An : Fr + Fn and Am Fm + Fm be discrelizations as defined in Equ (9). Then:
dy (Am: An) & (m- + +
(m +n +
(13)
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 dy between two operators, for each sample size & E N, we give a bound on the Hausdorff metric dæ between the two (k, C₂) d.r-fllosess. As long as the dependence on À of these bounds is polynomial, the infinile sum in the definition of dM converges. We do this by picking an arbitrary distribution 77 from Sx,c. (A), which by definition is given by a k-luple F of functions in L C..) Discretize each element of F and consider its entry distribution results in 7h E Se... (An). We show that we can give an upper bound of dLP(1,, mn) that is independent of the choice of 17 and thus same upper bound holds for supnES..c. (4) e.,.,, (A.) dLP(n, mn). By also selecting an arbitrary element of Sk,c, (An) and extending it to an element of Ss.c, (A), we obtaín another upper bound for sup,. c, (A..) inf nnfness.e c. (4) dLr(1, Bm) and thus for dæ- The different assumptions come in via different techniques used to bound dip by a high probability bound on the _ norm of the functions in F and their discretization/ exxtension.
4.2 Results for graphop neural networks
Not only are graphops and their discretizations close in das but, we show next, neural networks built from a graphop are also close to those built from graphop discretizations in da- We iterate that here we are comparing nonlinear operators (graphop neural networks) that are acting on different spaces (m)(n)) for some finite n versus ([0, 1])).
Before stating theoretical guaranlees for graphop neural networks, let us introduce some assumptions on the neural network activation function and parameters:
Assumption Let the activation function p + R in the definition of graphop neural networks be 1-Lipschita and the convolution parameters h be such that |h| S 1 sement-wise
Theorem (Graphop neural network discretization). Let A F F. Assume that A satisfies Assumption 2 with constant CA and Assumption 3.A or 3.B with resolutions in N. Fix n E N and consider (k:, Cv) -profllless. Under Assumplion 1, we have:
CaC. C.+1
dm( A, ((,, )). SPI
(14)
n
where C == mnmxa ΣK Cz Rmmax = maxie[L] ni, and P1 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 NN,
( (l, Ams (h, Ans SPI (m-² (m-+++ +n=+) + (C, + 1) (n-1+m-=- m-). (15)
Compared to the main thcorems of Ruiz et al. (2023a), there are two main differences in our results. First, our rate of O is slower than the rate of O(n-1) in Ruiz et al. (2023a) as a function of n. Yel,, second, their bounds contain a small term that is independent of
and does not go to 0 as goes to infinity. This small term depends on the variability of small eigenvalues in the spectral decomposition of the convolution operator associated with
8

---

Figure 1: Hausdorff metric between samples from 1-profiles of 2-hidden-layer GNN on finite polymer graphs vs on large polymer graphs (see Appendix A for polymer graphs). The GNN uses GSO A3 + An where A, is the normalized adjacency matrix earties at each layer. Different solid lines are different random draws of functions that make up the estimated 1-profile. Sec Appondix A for details.
log d H
2
nodes and ReLU nonlin-
log( 1/resoluttio log( [reesotlll)))
1.0
1.5
2.0
2.5
3.0
log resolution
graphon. The bound in Theorem 3, contrast, goes zero. We tested this bound in Figure for GNNs polymer graphs, which suggest that O(n-1) rate may be possible.
The proof for this theorem is in Appendix D.3 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 P. which would result in bound involving 4(h, A. and its discretiza- tion (#(,, A).)), as a nomlinear operator, as opposed to bound between Φ(h, A, and & A). .).Our proof shares the same structure as that of Theorem 2 while making sure that the mismatch from discretizing/ searretiiingetteddnnnng operators does not blow up with compasition.
4.3 Assumptions
We discuss the main assumptions of our P-operators. Assumption 2 (Lipschitz mapping). An operator A F - F is Ca-Lipschitz if ||ff Aglla S Callf glle for any f.g E 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 bounded operator norm and is thus aulomatically satisfied by linear P-operators.
The next few assumptions are alternatives; only one needs be satisfied by our P-operators. Intuitively, they ensure that the images of our operator are not too discontinuous:
Assumption 3.A (Maps constant pieces to constant pieces). We say that an operator
A : F F maps constant pieces to constant pieces at resolutions in N C N if for any n E N, and for any f Fi that is a.c. constant on each interval (u - 1/n, u] for u E [n]/n, Af also constant on (u-1/n,u u] for each u.
A Assumption 3.B (Maps Lipschitz functions to Lipschitz functions). We say that an operator A: F FF maps Lipschitz functions to Lipschitz functions at resolutions in N C CN if for any n E N, and for any f E Fr.) Af is C.-Lipschilz.
This is the most restrictive assumption. However, the next lemma (proof Appendix D) describes some dense, sparse and intermediate graphs that satisfy these assumptions.
Lemma 2 (Well-behaved operators). The following examples salisy our assumplions:
1. Bounded-degree graphings: Let G be graphing corresponding k-D grids polymer graphs (not necessarily regular graphs) with fized monomers (Appendix A). For each N E N, there erists locally equivalent graphing G'y such that its adjacency operator satisfies Assumption 3.A with some resolution set (see Lemma 5 and Lemma 7).
2. Lipschitz graphons: Let W be a Cu-Lipschitz graphon on Freg(C.). Then the Hilbert- Schmidt operator f + fi W(-y)o(yddy satisfies Assumption 9.B with resolution in N.
3. General graphs: Let G be a (potentially infinite) graph with verter coloring of N colors such that if two vertices have the same color, then the multisets of their neighbors' colors are the same. Then G's adjacency operator satisfies Assumption 3.A with resolution N. An N-d hypercube (more generally, Hamming graphs) which is neither bounded- nor dense, satisfies the above condition with resolutions in {2"). [

---

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 finile || ll2-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, 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 are nonlinear operators. We also assert that our restriction to operators acting on 1,2 spaces does not affect convergence guarantees (Theorem 2.14 in (Backhausz and Szegedy, 2022))-
Next, we show that restriction to Lipschitz profiles, which is necessary for our proof technique, does not affect the original convergence either, if we allow our Lipschitz constant to grow:
Theorem 4 (Growing profiles). Let L : N + R be a strictly increasing sequence such that L(n) " co. Consider sequence of P-operators (An : Fr Fa)NEN that is Cauchy in the sense that d' (An Am) == Σk= 2 (An) (Am)) + 0 m, -> co. If A, + A under action convergence (Backhausz and Szegedy, 2022), then (An)ReN converges to the same limit under d's-
This theorem allows us to replace the C. constant in our bound with a slowly growing function in n and get back 'action convergence' as described in Backhausz and Szegedy (2022) so that we can inherit its useful properties while still be able to draw on Lipschitz assumptions in the profiles, without any realistic slowdown in the bound.
Proof sketch For some & E N, by the completeness of the Hausdorff metric over the closed subsets of the space of probability mcasures supported on R2t the statement is equivalent to showing du (S& Sx, argument to smooth out arbitrary measurable functions fi...., f& that witness a measure in the k-profile of A. By selecting a Lipschitz mollifier o, ensure that convolving ʃ3 with d. : x + (0((==((e))) results in Lipschitz function that converges to f in L2 as e goes to O.
- 0 as n - oc. The proof uses a Lipschitz mollification
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 rifferenttresoolution GSOs discretized from the same graphop, are close an operator metric built from weak convergence of measures.
For future dircction, 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., 2023a; 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).
10

---

Acknowledgments and Disclosure of Funding
This work was supported by Office of Naval Research grant N00014-20-1-2000 (MURI ML-SCOPE), NSF award CCI-2112665 (TILOS Al Institute), NSF award 2134108.
References
R. Abboud, T. Ceylan, M. Grohe, and Lukasiewicz. The surprising power of graph neural networks with random node initialization. In International Joint Conference on Artificial Intelligence (IJCAT), 2021.
David Aldous and Russell Lyons. Processes on Unimodular Random Networks. Electromic Journal of Probability, 12(mone):1454 1508, 2007. doi: 10.1214/EMP.v12-4663 URL
https://dol //oii.///iii org/10. 1214/EJP. v12-463.
W. Azizian and M. Lelarge. Expressive power of invariant and equivariant graph neural networks. In Inl. Conf. Learning Representations (ICLR), 2021.
Ágnes Backhausz and Balázs Szegedy. Action convergence of operators and graphs. Canadian Journal of Mathematics, 74(1):72-12) 2022. doi: 10.4113/50006411420000000
Itai Benjamini and Oded Schramm. Recurrence of Distributional Limits of Finite Planar Graphs. Electronéc Journal of Probability, 6(none):1 - 13, 2001. doi: 20.1214/.JP.v6-- URL attps://dee htt///oiiorggg/////// 1214/1J1 v6-96.
Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Sizc-invariant graph representa- tions for graph classification extrapolations. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 837 851. PMLR, 18 24 Jul 2021. URL attps://proccedding mlr wttp://innnn...pee///////// ppeess/1139/brrreeequuue
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.26993
Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems (NeurIPS), 2020.
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.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021. URL http://jmlr http:////wiiroorgpaaar////////// org/paperrs/v2/2204551 html.
V. K. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In Int. Conference on Machine Learning (ICML), 2020.
Justin Gilmer, Samuel 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, TCML'17, page 1263-1272. JMLR.org, 2017.
S. Jegelka. Theory of graph neural networks: Representation and learning. In Proc. of the International Congress of Mathematicions (ICM), 2022.
Nicolas Keriven, Alberto Bictti, 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 Associales Inc. ISBN 9781713829546
11

---

Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https: //openreview.c wtw.:e//oooomm///SSSu////aa
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.
A. Loukas. What graph neural networks cannot learn: depth width. In Int. Conf. Learning Representations (ICLR), 2020a.
A. Loukas. How hard is to distinguish graphs with graph neural networks? In Advances in Neural Information Processing Systems (NeurIPS), 2020b.
Lásvló Lovász. Large Networks and Graph Limils., volume 60 of Colloquium Publications. American Mathematical Society, 2012. ISBN 978-0-8218-9085-1.
László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combi- natorial Theory, Series B, 96(6):9333995 2006. ISSN 0095-8956. doi: ittps://doi.or (0.1016/)jettb.2006.05 0000 URL https: /ttp://wwwwwaaao www.seeieeeccecccccmmm.m com comm/ciiin///atticclio.cc pii/$00988550000517.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Proceedings the 33rd International Conference Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
Sohir Maskey, Ron Levie, Yunscok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Newral Informalion Processing Systems (NewrIPS), 2022. URL https://openrevierr wwt./eet/oroooee fidummddddpppiiiee -9WeF...
Sohir Maskey, Ron Levie, and Gitta Kutyniok. Transferability of graph neural networks: An extended graphon approach. Applied and Computational Harmonic Analysis, 63: 48 18-83, 2023. ISSN 1063-5203. doi: https://waat https://www.scienceee www.sciencedirect.... com/science wttpaaccl///pp//11011022222222/0
2022.11..000200000 URL
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 (AAAT), 2019.
T. Mitchell Roddenberry, Fernando Gama, Richard G. Baraniuk, and Santiago Sogarra. On local distributions in graph signal processing. IEEE Transactions on Signal Processing, 70:5564-5577, 2022. doi: 1111100/TSPP222223222555
Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transfer- ability 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::/prooeeednngs neurips. pdf.
cc/paper_fiile www.s/llllppaeeee
Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. Transferability propertics of graph neural networks. 2023a.
Luana Ruiz, Ningyuan Huang, and Soledad Villar. A spectral analysis of graph neural networks on dense and sparse graphs, 2023b.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfar- dini. The graph neural network model. IEEE Transactions on Neural Nelworks, 20(1): 61 61-80, 2009. doi:
Balint Virag. Operator limits of random matrices. 2018. doi: 10.48550/ AARII//RRIVI.... 06953. URL attps://anes org//bsg////eeeeooooo... hts//bbs/80000 1111880006655
12

---

K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In Int. Conf. on Learning Representations (ICLR), 2019.
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: / / opperevieeeeeee.eeee
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolci Du, Ken-Ichi Kawarabayashi, and Stefanic Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Represenlations, 2021. URL https: //openeeview.net//eeee..eeeeeeee
cmocL.C..
G. Yehudai, E. Fetaya, Meirom, G. Chechik, and H. Maron. From local structures to size generalization in graph neural networks. In Int. Conference on Machine Learning (ICML), 2021.
13

---

A Additional details
Some highly repetitive parts in the proofs presented informally (e.g. "use the same techniques as...) to highlight the main ideas in the NeurIPS 2023 version of the paper. For the complete formal proof, readers are advised study later version on arXiv.
A.1 Notations
We will use the following extra notations in the proof:
1. For some P-operator A E (2) - (2)))), k E N and (fi...., fx) =: F c (2)), let FA be the ordered 2k-tuple (fi..... fk. Afi...... Afk) and denote
fx) Af (z).................... Afx(z))) R22K. 2. For some P-operator (2()) + (1)), k and (f....., fiet F L2()) let DA(F) be the entry distribution ff. Aft) Af.)
F2(x) =
A.2 Definitions
Cut norm and cut metric Here we define concretely the cut metric over the space of graphons. Recall that graphons are ([0 11, F, Lebesgue-integrabll functions. The space of graphons is equipped with a norm known as the cul norm:
Wo = sup 1/ ((.x)))(()))(())
(16)
STEE SXT
and metric known as the cut metrie:
do W2) = = inf [ W2 @l1o
(17)
where ø taken over all measure- preserigp bijections from [0. to [0, 1]. Intuitively, taking the inf over all measure-preserving bijections allows the cut metric to identily graphons that are just. a rearrangement. away from another. This generalizes symmetries permuting the vertices (and the corresponding edges) do not change the graph itself. Lovász (2012) shows that graphon convergence under the cut metric well-behaved: every graphon is limit of convergent sequence of graphons; and every Cauchy sequences converges to graphon. This mode of convergence is known as dense graph convergence.
graphs, where
Lévy-Prokhorov metric
The definition of Lévy-Prokhorov metric on P(R2)) is:
drp(M m2) == inf 0 (U) S m2() + A (2( S mU') + e, VU B2x).
where Bex is the Borel o-algebra generated from open subsets of 2 and U = {y= : 3x E IR 2 | 2112 < e).
(18)
Specific graphs We will also define different graphs that we mentioned in the main paper. Unless otherwise stated, we consider undirected graphs. A path on n-vertices for some n 2 is the graph G = ([n), i 1) i E [n - -]})). Its high dimensional generalization are k-D grids on n² vertices are the graphs G [[n]*. {(u, u) I|u - -ull- = =1}).
Hamming graph (d, q) with parameters d, d, 2 1 N the graph with vertex set [q] and edge set contains all pairs u, that differs at exactly 1 coordinate (Hamming distance 1). For instance, (11,g) q) is the complete graph on q vertices and (2, q) is the hypercube on 24 vertices.
An polymer graph Pa with on kn vertices that contains & copies MI...., M2 of M. Since M is finite, we can choose a starl 81 and end er vertices in VM. MM's being copies of M also means that there is an isomorphism dy from VM,,, 1 to VM, for each i E -1. Let 8; and be inductively defined as di (8-1)) and (e(e;-1) for i from 2 to k. Beside edges in the copies of M, we also add all edges of the form (c,-1, st) for each i from 2 to k. See Figure 2 for an illustration.
and finite n-vertex monomer M (VM, Eas) the graph
14

---

x mod
x
0
37
mod 1
((x + a))
((x + b))
((x -))
((x a))
(a) Cayley graph of Z
(b) Cayley graph of z²
(0) is computation mod
((x a))
T +2
T +++.
3 4++1
.6
I +.8
(c) Polymer graph whose unit is graph with vertices. The pattern extends ad (d) Graphing of (c). (0) is computation mod 0.2. infinitum on both sides.
Edges drawn are from a single unit the polymer.
Figure 2: Examples of limit objects. The vertex set is the interval [o, 1]. Example edges the ares connecting points on the intervals. a and are distinct irrational numbers. In each graph, edges that miss an endpoint are identified as single edge connecting the two existing endpoints.
A.3 Illustrations
Figure 2 shows examples of graphings for a Cayley graph of 2, 2² and polynomer graph.
A.4 Experimental details
To empirically study the rale of convergence of the das metric, we study an approxination of Hausdorff metric wetneen 1-profiles of GNNs build on small finite polymers that built on large one. The result is in Figure 1 and we now detail the set up.
Architecture The GNN has hidden layers, uses ReLU activation at each layer, including the output layer. We fix particular polynomial GSO A + A where A is the normalized (by edge vertex degree) adjacency matrix of the input graph of the GNN. Monomer for each polymer has size 5 and is the same monomer seen in Figure 2. The small polymers consist of 2, 4, 8, 16, 32 monomers. While the large monomers that take the place of the limit object has 128 monomers.
1-profilc cstimation Recall that the 1-profile of an operator P consists of entry dis- tributions of (f, Pf) where f runs through all measurable functions. It is therefore, not tractable construct the 1-profile exactly. Instcad, we draw random = f2. f1o)'s to ruestruct set of 10 probability distributions. Repetitions of this random drawing make up the different solid lines in Figure We construct each f; [0, 1] - [-1, as piecewise wss linear function with pieces ((u 1)/ 10/1000, u/ /10000] for u from 1 to 1000. We set fx(0) = 0 for each and recursively set [1(110000 1000) = f.((u 1)/1000) + 9/100 where g is a random draw linearly interpolate between two consecutive endpoints.
from {-1, 1} uniformly. Finally, Numpy random seed is set at 1234567.
After getting this set F, for each operator P that are cither GNN built on small polymers or GNN built on the large one, we compute the set (D(f., Pf. f E F} to get the corresponding estimation of the 1-profile.
15

---

Hausdorff metric computation Given a pair of 1-profile estimations to compute dæ over, we use optimal transport code from (Flamary al., 2021) to compute the earth mover distance bet each pairs of distributions. This gives an approximation of dyp bet ween elements of the two profiles. Using the definition of Hausdorff distance, we obtain the result in Figure 1.
A.5 Milder assumptions
As mentioned in the main text, 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: F - F maps constant pieces to constant pieces whp al resolutions in N C. N if there erists a set E C [0, 1] with Lebesgue measure X(E) < infnex 1/n, such that for any n E NN, and for any f E F that is a.c. constant on each interval (u - 1/n, al for [n]/n, Af is constant on (u (u- u/n,, and ||AfEEll < infneM 4.
Assumption 4.B (Maps Lipschitz functions to Lipschitz functions with high probability). We say that an operator F:F + F maps Lipschitz functions to Lipschitz functions whp at resolutions in N C N if there crists set E C [0.1] 1] with X(E) < inf 1/n, such that for any n N,, and for any f E F(-1,)), Af is C, Lipschitz on [0, E] and ||Afigll < inf h.
Assumption 5.A (Maps constant pieces to Lipschitz pieces). We say that an operator F F maps constant pieces to Lipschitz pieces at resolutions in N C N and constant C if for any N,, and for any f E F(-1.11 that is a.e. constant on each interval (u - 1/n, u] for E [m]/n, we have that Af is C-Lipschitz on each (u- u], for all u E [nl/n.
Assumption 5.B (Maps constant pieces to Lipschitz pieces with high probability). We say that an operator A: F F maps constant pieces to Lipschitz pieces whp at resolutions in N C N and constant C if for any n EN, there crists a set E C [0, 1] with A(E) < such that for any f E F(-1.1) that is constant on each interval (u 1/n, u) for u E in/nn, it holds that Af C-Lipschitz on each (u 1/n, E,, for all u E [m]/n and ||Af 1l1 < infnee +.
B Omitted proofs from Section 3
Proof of Lemma 1. Fix m E N and S.g E Fm. Since P-operators are bounded, to show that they are self-adjoint, it suffices to show that (AmJig) (J, Ang) where (,-) is the usual inner product in the Hilbert space Fm. We have:
(Amf.g)=
Σ (Amg))))g())) mEI/m[m]
(19)
Σ
Af'd g(u)
(20)
WE1/m[m]
(Af')g'd dp S/ (A
Σ
(21)
WE1/m(m)
f ('Ag))a
(22)
[ ('AA') (f.Ag)
Σ WE1/m[m]
(23)
where the first line is the definition of the inner product in Fm, the second line is the definition of the discretization An (recall that for I Fm, I' E F is the extension of defined as f'(x) [[[mm] ([=m]/m)), the third line is because g' is constant on fixed [u - 1/m, u
intervals for each u and the fourth line is because is self-adjoint.
16

---

C Theory of graphings
In this subsection, we highlight definitions and key characteristies of graphings so that the paper confanoon. much more in-depth discussion can be found in Lovász (2012). Definition 1 (Borel graphs). Let Q be a lopological space and F2, be the corresponding Borel space, A Borel graph is a graph E) such that E E F.
The following proposition asserts that bounded-degree graphs without automorphisms are always Borel:
Lemma 3 (Proposition 18.6 from Lovász (2012)). G is bounded-degres gruph without automorphisms then there exists a topology T on V(G) (called the local topology) such that G is Borel with respect to the Borel space built from т.
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 quadruple G = (9, B) such that F is a Borel oalgebra that makes (St E) Borel graph, and X is a probability measure on (2, sabisfying: for any A, B E F,
J. degn(t) = J, deg (z)x())d)(x),
(24)
where dega(z) counts the number of neighbors in of
As an example, we now describe paths and cycles in terms of graphings: let V be [0, 1), F the Borel o-algebra generated by open intervals with rational endpoints and for each [0. 1]. put (2, x f a) in E if x + component of the graphing is a finite path. If we consider the edge set (2, 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.
1] for some real number a < For a < 2. each connected mod 1) for
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 G1, G2 be two graphings. A measure- preserving map sp : V(G,) - V(22) is a local isomorphism ils restriction to almost every connected component of G1 foutside of a set of connected component of measure 0) is a graph isomorphism with one of the connect components of G2- More formally,
Pr ((G1)2 = (G) A(11
(25)
where= is rooled graph isomorphism and (G1). is the connected component of G1 rooled al x.
Note that local isomorphism of graphings are not symmetric and the map ip needs not be invertible. A stronger notion of equivalence, which is symmetric and transitive is local equivalence:
Definition 4 (Local equivalence (informal)). G1 and G2 are locally equivalent if they have the same subgraph densities t" (F,GG) = (F, 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ásı (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.
17

---

C.1 Degeneracy of eigenvectors
We give an heuristical argument why directed graphing limits can fail to have eigenvalues and eigenvectors/ cernrcoorr/ggennnciooonsss Consider the sequence of one sided directed path: G, = E = {(i, i 1): :iE -)]),, for n 2 Note that this may not be a Cayley graph in certain authors' definition, which requires Caley graphs to be undirected. However, it a realistic example in machine learning since convolutional layers in CNNs are exactly the adjacency operators of these directed graphs. The limiting adjacency operator for this sequence, for all intents and purposes, is intuitively the shift operator (say, on {²) A: (21, T3....) + (0, 11; 22, .2....). An easy calculation then shows that this shift operator does not have eigenvalues.
For a more formal argument and construction on failure cases of existence of eigenvectors in undirected graphings (which is what we defined in this section), refer to Remark 1.6 of Backhausz and Szegedy (2022).
D Omitted proofs from Section 4
D.1 Proof of Lemma
We prove cach bullet point in Lomma 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 the main results. Similar to how isomorphic graphs represent the same graph, we only need to specily 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 Z (two-way infinite paths) or high- diah--dimesionall generalizations (infinite 2D and 3D grids). For a graphing H, let A(H) be its adjacency operator. If H is regular, let deg(H) H) be the degree of any of its vertices. For each N E N, there crists locally equivalent graphings:
1. Gxx such that A(G')) satisfies Assumption 3.A with resolution set d(N) = 1or E za = N for some E N}.
2. GN such that A(G*)) satisfies Assumption 4.A with resolution set [N].
3. G such that A(G))/ deg((G) satisfies Assumption 4.B with resolution set [N].
Proof of Lemma We will first show the results for two-way infinite paths. Higher dimen- sional versions follow almost verbatim. Fix E RRQQQ irrational. Recall from Lovász (2012) that the graphing = (10, A, E)) where FF the Borel o-algebra generated by open intervals with rational endpoints, À is some probability measure ([0, F) and E E F X defined as:
E { mod 1) [0, 1]}.
(26)
That is a graphing and each its connected components is a copy of the Cayley graph of Z generated by {-1, 1} is asserted in Lovász (2012).
1. Fix N N. the goal is to define a graphing Gyy that locally equivalent to G such that A(G')) satisfies Assumption 3.A with resolution set d(N) the divisor set of N.
Defining Gyy- Let Gyy ((0, 1J, A, Exx) where,
E'y : = (ak2=(((0))) (10)))
1 N + 1 N mod ))) : [NI/N, = ..>)
(27)
Intuitively, G'y consists of N disjoint copies of G shrunk to the space (0, 1/N). Since E C [0, 1] [0, 1], GNy is graphing in the same Borel space as G.
18

---

G'v is locally equivalent to G. From Lemma 4 it suffices to display local isomorphism from third graphing to each of them. Let G2 defined similarly as GN,, be the third graphing. We claim that 99 x + 2x mod 1 is a local isomorphism from G2y to Gyy and 82 : x + 2Nx mod is a local isomorphism from GyNy to G. Intuitively, G2N contains 2N copies of G while G'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' is mapped bijectively to connected component in another copy of G in G2N- We give a rigorous argument below.
For z picked randomly according to X, let j E [2N] be such that I E Ii 1/(2N), By definition of G/NN= the connected component (G2N)) consists of vertices of the form
u(k) = 2N + (o + (k/(2N) mod 1/(2N)),
for some k E E and there is an edge from ukk) to v(k = 1). Consider (ı(x) = 2x mod 1 that sends v(k) to
ak N
mod #) mod 1.
(i(o(H)) 2j N +
2x +
Now consider the connected component of yp (xx 2x mod 1 in G'v- Since [j J), D - 1//N,j") where [NV/N з j' == 2j mod n. Thus, the connected component of (G'v) consists of vertices of the form:
(((k): = j'- N + (x) + akk/N mod 1/N)
(28)
N (12 mod 1) + ak N
2j mod N
mod
(29)
N
With some modulo arithmetic manipulation, it is not hard to see that 9p (u(k)) e' (k) for all & e Z. By definition of G.v, there is an edge (v'(k), e' + 1)). Therefore, there is an edge (PI(v(k)), (p((k( + 1))). If X is the uniform measure then we can ignore vertices at the endpoints of our intervals ( points [N]/N] ) and conclude that (G2N)> (p)()) with probability when ~ X.
Now consider (2((x) = 2N mod that sends u(k) to:
(²(v(())) == (2Nj 1 (2Nx + ak mod 1)) mod
(30)
The connected component of (2(x) in G is in [0, 1] and consists of vertices of the form:
= (2Nj - mod 1) + (2Nx + ak mod 1).
(31)
Thus (kk (v((())) for each & E Z and the definition of G implies that (G2 = Gpa(z) since both are isomorphic the two-way infinite path. If X is the uniform measure then the above hold for a.e. x E 1].
G'y satisfies Assumption 3.A with resolution set d(N). Let D be a divisor of N, then Da N for some N. The intuition is rather straightforward, since D is a divisor of N, the partition into equal intervals of [0. 1] is simply a finer partition into D equal intervals. By construction, vertex of G2y 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²) = f(y') for any (x, y), (x', y²) neighbors such that x and x' come from the same 1/D pieces.
Here is more formal argument. Fix f Fi-1111 that is a.e. constant on each interval (u 1/d, u] for (D]/D. We need to show that A(G))) is a.e. constant on the same pieces where A(H) is the adjacency operator of a regular graphing H. Fix d [D], fix æ, x' E [d 1/D, d). Let j be such that [j - 1/N,j) and be
19

---

such that x' E - 1/N,J'), Since Da = N, we have -i- d 1/D,d). d). Furthermore, by definition of Gy, all neighbors of and x' are in j-1/N.j) and [j' 1/N.j" respectively, and thus in [d 1/D,d). Therefore, A(G))/()) = 2f(x) = 2f(²²) (fz)) for all x, E [d 1/D, d), which means that x() is constant on each of the pieces [d 1/D, d) for each d E (D).
2. Fix N E N. the goal is to define a graphing GN that is locally equivalent to G such that A(G%) satisfies Assumption 4.A with resolution set [N].
Since @ is dense in IR there exists number 8(N) 4N= such that 1 4N2 + 6(N) is an irrational number. Let GN ([0, F,,, where,
EN {( I ( 1 4N2 + +5(N)) mod 1) : E
1 10.11
(32)
That Gyy is locally equivalence to G is casily seen via the ambiguity of selecting a when defining G. Now we show that A(G%) satisfies Assumption 4.A with resolution set [N]. Pick M < N and f E Fi-1.11 that is a.e. constant on each pieces (m - 1/M, m] for each m E [M]/M. Let
E
U MM/M/M
m
4N2
1
5(N), m
1 4N2
+ s(N)
then
M
M
1
A(E) = Σ ((((4N))+(N))) m²=1
I
<
N2
N
Pick x, E (m-1/M m)) m/ EE then x, E (m-11 1/M c, m. - c] where 1/(4N²) + 8(N). Thus we have both x + e and x' te are in - (m-1/Me 1/M, m]. By definition of and x'. Therefore, if
G all neighbors of and x' are in the same 1/M piece f T Fi are constant on these pieces, so is Af.
3. Fix N E N, the goal is define a graphing G that is locally equivalent to G such that A(G satisfics Assumption 4.B with resolution set [N].
Since Q is dense in R, there exists a number 8(N) < <1/(4N) such that (((4)++(N))
+
is an irrational number. Let G ((0, F,, EX) where
E EN
Tr x +
4N + S(N))
mod1) mod 1) x E 10.11
(33)
That GH is locally equivalent to G is casily seen via the ambiguity of selecting when defining G. Now we show that A(G satisfies Assumption 4.B with resolution
set [N]. Pick M S N and f E Freg(C.) that is a.c. C,-Lipschitz on [0, Set
e IN + 8(N) and let:
E (0 c,
(34)
Then A(E) = 26 < 1.
N. Pick x, x' E [0, F, then x + e and x' + do not 'loop over' in the interval [0, 1/ ( y mod 1 = y, for y E (2, + { ). Thus we have:
[f(z + + f(r c) f(x' + f(x'' - e)1
- Af(x)-AA(c}))
(35)
2
[s + - - ((x + +)) + 1f(x -) - -xx'xxx - e)
(36)
2
< C.ll - 2'1,
(37)
where the last line we use Lipschitz property of f. This finishes the proof.
20

---

Lemma 6 (Well-behaved operators- General graphs). Let G be (potentially countably infinite) graph with a coloring C V(G) [N] for some N such that for each verter u, with the same color, the mullisets of their neighbors' colors [C(u'): (u', ,u) E E} are the same. Additionally, assume that the cordinality of vertices of each color the some: that there is a bijection from {v= C(v) = of to {u C(v) c;) for any colors c, 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-measune preserving bijection) vertices of V into equipartition of [0, into N pieces IN. IN 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 be function with finite I,2 norm such that f is constant each I for each j from 1 to N. The goal is to show that Af is also constant on these piecos.
We show this by direct computation. Pick vertex x and another vertex y from the same piece, say Is for some particular k. By our construction, æ and y have the same color since they come from the same piece. By our assumplion, the multisets of their neighbors colors the same. However, since f is constant on each pieces, we have f(z) = f(u) for u, e of the same color. Therefore, the multisets {f(2): (2,z) E E} and {f(2) (2, 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 heither dense nor bounded degree, satisfies the requirements of Lemma 6.
Lemma 7 (Well-behaved operators - Polymer graphs). Let P be a polymer graphing on finite monomer n-vertex graph M = (VM, EM). Let A be then normalized (by each vertez degree) adjacency operator of graphing. For each N E N, there ezists locally equivalent graphings:
1. Pky such that A(P)) satisfies Assumption 3.A with resolution set nd( = (nxr E N: ra N for some E N).
2. PKK such that A(P)) satisfies Assumption 4.A with resolution set n(N].
3. PM such that A(P)) satisfies Assumption 4.B with resolution set nl[]].
Proof. The exact same technique as Lemma (make copies 'shrinked down' graphings to get the result with Assumption 3.A and find small enough 5(N) so that the wrap around has small measure to get the result with Assumption 4.A and Assumption 4.B) works. Intuitively, this is because graph.
replacing each node in the path graphing with monomer
To handle coloring at the monomers details, use Lemma 6 with the coloring that assigns the same color to the same node in each monomers (since each monomer is a copy of each other, there is an isomorphism between the nodes and by 'the same node' we meant under this isomorphism).
be Lipschitz graphon, with Lipschitz constant C. In. other words, W has finâte I.2 norm and is Lipschitz in both variables. Then the Hilbert-Schmide 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 norm 1.
Lemma 8 (Well-behaved operators- Graphons). Let W 10, 10,1 [0,1]
21

---

Proof. The proof follows from definition. Take f (30, 1)) such that Ilfl = 1, then:
W(z, 2f L. (().2)
(38)
(2 - W(y, 2))1 1f(=))dz
(39)
$ / Cl 15 C| vl-
(40)
where the first line is definition the Hilbert-Schmidt operator H, the second line is triangle inequality and the last line due to Lipschitzness of W and L' norm of
Lemma 9 (Well-behaved operators Hypercubes). Let C be hypercube of dimension N. Then the normalized adjacency matriz of C satisfies assumption 3.A with resolutions 2 for each n < N.
Proof. We first display 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 binary string of N numbers. Here, similarly, a hypercube with a number in [o, 1] by adding a 0. front of its binary representation. For example, 0.110101 (as binary number) is vertex correspond to the string 110101 when N =6 We call this representation mapping f: V + [o, 1]. Two vertices u, v are connected by edge iff f(v) and f(v) differs by exactly one digit in their binary representation.
will associate vertex v of
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 mumber x E [0, 1], let A(z) 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, is connected to E [0, 1] iff exactly one digit and x - A(x) = y - A(y). For example, for 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 0.110101.
A(x) and A(y) differs
4,
mind, we verify the conditions of Lemma 6. Tet V. Fix < N and divide [0, 1] into 2" equipartitions and let vertices in the same partition enjoy the same color. We will also number the partition/cnl 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 æ from a partition with label a ...a...a,, ap. Then, by the definition of our hypercube representation, the neighbors of have colors:
With this vertex representation
by the binary representation of their
Exactly neighbor with color (a) mod 1)02 .......00 On.
Exactly neighbor with color az (a2 mod 1)a3 ... On-
Exactly I neighbor with color 0102 ... an-1 1..2...001144,, mod 1).
Remaining N - neighbors all have color 0102 ... an.
Therefore, the multiset of neighbors' colors of only depends on the fact that comes from a partition with label a a, and thus, two vertices of the same color has the same multiset of neighbor's colors. Since the condition of Lemma 6 holds, we have the conclusion for this particular resolution n. Since n was chosen arbitrarily, the result holds for every < N. O
In future work, we formalizes the way in which the above proof holds for limiting object of hypercube.
22

---

D.2 Proof of Theorem 2
In this section, we prove slightly more general version of Theorem 2.
Theorem 5 (General approximation theorem). Let F - F be P- P-operator satisfying Assumption with constant Cai Assumption 5.A with constant C. and resolutions in N. Fix
EN and consider (k, Co)-profiles Let An Fn + Fn be a discrelization of A as defined in Equation (9). Then:
CaCr n
Co
dm (A, 58
(n
(41)
If instead of Assumption 5.A, A satisfies Assumption 5.B with constant Ce and resolution set N, then:
(VCnC,+ C. C.+C++1 +1
dM (n) 8
(42)
n2
n
If instead of Assumption 5.A and 5.B, A satisfies Assumption 4.B with resolution set N then:
(VaCC Co+1
dm (A, An) <8
(43)
n
Proof of Theorem 2. Fix k N. In order to derive an upper bound for dM,, we find an upper bound for the Hausdorff distance dæ between the two k-profiles of A and An.
(A.)) dLr(n, na). To bound the supinf quantity, we first select an arbitrary E SS,cc. (A). From this measure, we will construct measure nh E Sk,c. (An). we can upper bound (1 nh)) < M then we have:
Bounding supneS c. (A)
inf
dLr(1, mm) I drp(U, T.) < M, for all v E Sk,c. (A).
(44)
n.ESk.o, (A,)
If further M does not depend on the choice of 7h then have
sup nES, (A) C.
inf (1, nm) s M.
We now proceed with this plan. Fix an arbitrary T (A()), by definition of k-profiles, there corresponding tuple F= (fi...., with elements in Freg(C.) such that Da(F) f7.
Form:
T"=(Frneee Fr.cee(C.) 3
F :=:=
fg uu Jad jEE J Ju-1/n
Th = DD,
(45)
That f/ Fn,rog(C.)) is asserted in Lemma 10.
Bounding dLP(TT 7.)) For some c > 0 to be we want to show that (m))) S which equivalent showing, for any U B2k,
π(U) < (U') +e and (U) ST(') +e.
(46)
Recall that U was defined in Equ (18).
Fix any E B2e, we have
π(U) .f( lodD ['' 1 Faeedd
(47)
and
n. (U*) = (F'd Σ
1 An els..
(48)
aE(n|/n
23

---

Subtracting both sides yield:
f Fx(())U - LF (w)))
7(U) 7n,(U))
Σ
(49)
"EIn//n u-11/n
Similarly, have:
(V) -(U'))
Σ WE/n//n u-11/n
1 (W)EU - 1 (x(())er
(50)
Let y/+ = [an]] /n. Recall that E C [0, 1] defined Assumption 5.B and 4.B is the set of
where Lipschitzness of the image under A may fail. Let E = 0 if we are using Assumption 5.A alternatively. Define the events:
EE(E {a FA(x) ( (1e) EU3
(51)
(e) {x: (v)
(52)
(e) {x [|Fa(<) - (w=)l22 >{)
(53)
(E( {x (z) f](b=|1 e/v e/V2k).
1..k
(54)
(c) = {a: : (Zf)(z) - Av))( > c/v22),
j = 1..k.
(55)
Using this notation, one also has
7(U) n, (U9) x(E))
and TU) - 7UU)) S X(E)).
(56)
It is straightforward to see {)(() C E'(c), 1,2 for any U by definition of U Furthermore,
* E'(c) S U (
(57)
j=1
since all 2k dimensions are bounded in absolute value by c/v 2k then the Euclidean distance of the vector bounded by
Therefore it suffices bound X(E)(c) + ((E),A(()) for each j [k).
Bounding X(E)(c)). Since fj is C. Co-Lipschitz for all j, we have:
(15(;) ff((m) = [z(x) 1 9h
[)()dd(=)
(58)
1/o 11/0
1=
f5(x) fz(=)dA(z)
(59)
1/n
Uv
n
1fs(z) f)(2)(dA(2)
(60)
1//n
C. n < C C=aX(=)=
(61)
yo 1/-1/n
where the first line is definition of fí; the second line is because A((4 - 1/n, u)) = n the third line by triangle incquality and the last line is bocause of Lipschitzness of fz-
Thus, choosing e V2kCC./n /n means that X(E)(()) 0. (We can tighten this bound by only assuming that Sg is C.-Lipschitz outside a set of small measure.)
Bounding X(E,,)) Let F-1111 3 f be the extension of J' defined as f(x) ['([an] /n) for all [0, 1]. Note that f is not continuous in general and hence not Lipschitz. We have
24

---

for any a E [0, 1]:
l -=
u=
(Af(2)) Anfz(Ua) = Aff(2) - n
Af)(2)((())
(62)
M/ [Af(2)) - (=) da(z),
-
n
(63)
where we used uniformity of À 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:
[Af(()) - + - Uv [Af)(x) (va)( Sn
(64)
$ Af)() Aff(0) +n f-- -
(Af)(=) Aff(3)) a)(=).
(65)
Define the following events:
())(()= = x: |Afs(e) A{((0) >
(66)
2/2k
1==
(c) == x x E :n
Aff(()) Aff(2) dA(2)> >
(67)
V2-1/n
2v2k
Then it is clear that EIAA S E// UEJ,A UE and thus A(E3,A) S ((E) + +(E7,A) + A(E).
Bounding (()) via Assumption 5.A or 5.B. Because of Assumption 2, we have:
||Af, Afylle S Callf, f2l12. By L" norms inequality, we have
(パАî)(=) - A5z(0)l1 < Calli, - Ssll x CaC.
(68)
where the last incquality is due to
11, - f112 L ( (((()){(()))a(()))
(69)
[ (ff(u/m) f))2))
Σ
(70)
We (n) //n u-11/n
pu/n
= Σ
n u-1//n
f)())d{(2) - 55(00) -5((a) dx(x)
(71)
(u-1)/n
uE(n|/n
10 15)(2) - {)(o))((=3) da(x)
n2
(72)
u-11/2 u-1/nn
uEIn|/x
C2
(73)
n²
We have:
CAGo 2 / (Af(()) (fj(x)ldr
(74)
n
{ (Am(()) - Aff(z))dr + So.nees.c (A5(*) - (1)(t)
(75)
2
2/2k (()) +0.
(76)
Thus selecting <>> 2/ - gives X(E), S 26
25

---

Bounding (()) via Assumption 5.A or 5.B. Notice that f, is constant in each (u-1/n, 1/n, u| and thus by Assumption 5.A or 5.B, Af, Ce-Lipschitz in cach (u 1/n, u] E. Therefore we have, for z E [o, 1]} and E (Uz- 1/n, E:
[Af(()) - Afx(2) & C.l - 2 C. n
(77)
When E E, we use the second condition in Assumption 5.B to get ||Af I and thus for any x & E:
n
(78)
Ux 1/m
(2) - -ff))) + n [ (va-1/maa 1/m-MeVE
Aff(2) Af) dx(x) (79)
=n
(122 11-nI//alnE
Co
+n 11
+ dA(=)
IA5()) + |AÍs(=))
(80)
11
C.
+ (Af((E))N(EE) + |LAf, 1F, 1
(81)
C.+1 + ((((t))A((E),
(82)
n
where Fig = (Urz - 1/n, v/ ( E.
For I E 87 (e), we have:
Ce +
+ +AAA(()))\(EE)>>>>>>>)
e 2/2k'
(83)
or equivalently,
C + 1
[Af())) nA(Ez)
(84)
122k
Since 1/n 2 [Ai have:
Co+1)
1
12
d)(x) +0
(85)
2/2k
n
A(Ex)
Co+1
Σ A(En)
IdX(x)
(86)
2 2k
n
88,, n(u 1/n,a
"E(n]/n
Cc+1
nx(ET.)).
(87)
2/2k
n
Thus choosing c > 4V2k(Co+ + 1)/n means that:
12
nA(E)
(88)
4v2k
or
4v2k
X(E7,A)
(89)
en
Finally, choosing X(E)
16kv22
2 n
makes X(E7,A) S fE: and choosing makes
n
1
n
26

---

Putting everything together via Assumption 5.A or 5.B.
Thus, we can choose
7= 28th 8h (Veccutt CutC.tl
get:
(() v
E
(90)
==1
which allows us to conclude:
drr (1. mm) Sτ.
(91)
Since lj was chosen arbitrarily, we have for all πe E Ss(A),
inf dLP(T) nn) I dgp 7m) SE. (A..))
(92)
Thus also have:
inf n (A) C..
sup
dLr(N, SE.
(93)
Proof via Assumption 4.B.
Here, we use the other triangle inequality to get for each a:
Uv
[af Anff(ub)) n n
Aff(2) Af)(=)+++++++++ Af)(2) Aff(2)
(94)
-
Ux
(af df2))) +n 1 Aff(2) Aff(2) d2(z).
n
(95)
Define the following events:
I: - (M()) 2/2k
(96)
(4)
x E E: (AG(2) As{())dd(()) 2/2k
(97)
Then it is clear that εj,i S EJ U UE and thus A(E S ((E).) + A(E7,A) + A(E).
Bounding (c) via Assumption 4.B. Because of Assumption 2, we have: ||Af, Afyllz < Callf, - fill2. By L norms incquality, we have
|A - Afsll S Calli, B112 S CAC.
(98)
n
where the last incquality is due to
11i f112 ( - (1(0))(()))
(99)
l (z)(4) f)(())
Σ
(100)
u-1/n
oc ///n /m
Ja-1/m f)(=)d\(2)- -B(O)) 2
Σ
n1
dd(x)
(101)
uE/n|/n
u-1/n
(f" (f((2) - (((o))NN)) ) dA(x)
n2
(102)
Ju-1/n
de [m] /n
C2
(103)
n
27

---

Consider:
X(E),A
e
S
Vv
Afz(2) (A(2)dAA
(104)
2/
JU
uE(ri/n / u-1/nn - - dA(=))
(105)
|Aff Affll1 - CACo
(106)
Thus selecting > C.C. 1kv24 k (C C/Co//)² gives ((E S zσ.
Bounding A(E),A(e) (c)) via Assumption 4.B. Notice that fj is Lipschitz in [0, 1] and thus
by Assumption 4.B, Af; is Co-Lipschitz in (0, E.. Therefore we have, for E [0. E and
z E (y/- 1/n,1// y=], and:
[Af{(>) - Al5(=) S C.l - 2|5 C. n
(107)
When E E, we use the second condition in Assumption 4.B to get ||Af S 1 and thus for any & E:
-
-ole)-AAff3) dd)
(108)
Nv 1/n
(af((z) Af}())|d((3) + (ya-1 11..1//
AA5(2) Af}(2))dA(s)
(ya- 1/m.uiJ7E
(109)
C. +n (
+ (AAG))))
(110)
n
(g0-1/naannE
C. + (Af(()))N(EE)+++ + |Af,1
(111)
n
C. +1 + (AA(())
(112)
n
where Fg = (yr- 1/n, A.FE E.
For E (c), have:
e C.+1 + +AAI())))\(a)>>>>>>)
(113)
2/
equivalently,
AAf(*)
E
C.+1
(114)
nA(E.))
22/2
Since 1/n 2 1Af we have:
1
12
e
Co+1
1
dA(x: +0 +0
(115)
2/ 2k
E3 X(Ez)
Co+1 +1
1dX(x)
(116)
2v 22k
X(Eu)
aE(n|/n
E
C,+1
nA(E?
(117)
2/2
Thus choosing c > 4/2k(CC, + 1)/n means that:
e
(118)
4v2k
28

---

Or
4V2h
x(87,)) &
(119)
en
Finally, choosing c <
16ky2k
2 nZ
makes X(E7,)) S iz and choosing makes
X <
48
Putting everything together via Assumption 4.B. Thus, we can choose ē 8k (Cacutt + Cutl
to get:
((E V Σ E,
(120)
which allows us to conclude:
dlr (7) mm) E.
(121)
Since fj was chosen arbitrarily, we have for all oj E Ss(A),
inf
dr.(l, nn) S dr 7m) SE.
(122)
E. (A,))
Thus we also have:
sup
inf
(m) SE.
(123)
nESt.c, (A) nhe ES, (A,,)
Bounding supg,eS..cu (A,,) inf gnf c, (4) dLp(n, mn). In this direction, we proceed identi- cally, but now choose 7n arbitrarily Sx,c, (An). By definition of (k, C.)-profiles, there exists tuple F (fi,..., fk) each in F..r such that Th DA, (F).
Construct
F' = (Fregtc.) fJ x Van + (y)) (yan xn)f 1/n)].
(124)
7 DA(F").
(125)
where Vs [an]] /n for each j E [k]. That f Fre((C.)) is asserted in Lemina 11. Intuitively, f/ is the continuous piecewise linear function that interpolates fy, created by joining fy
1/n) and (u) with line segment for each [m]/n. Note also that fy(u) f5( for all [n]/n.
Bounding dLp(7.77,)) 7,). As with the previous direction, we start with an arbitrary e B and write down the differences:
St
(U)
Σ
1F (M)EU 1 (X()))
(126)
1-11/n
wEin|/n
π(U) (U') = Σ
1FA())EU L dw))))
(127)
eEIn|/n 1-1//n
Define the events:
E)(E) {x (v.) &U))
(128)
E((c {x (x(x) (UAA) (v.) {U9
(129)
E'(c) {x ||FA (yw) - Fx(x))12> >
(130)
Ec(c) = {x: (fr(U)) - f)(()] c/V2k).
j = 1.kk
(131)
EEA((E) (a (Anf) >
>
j L..k.
(132)
29

---

Using this notation, one also has
n(U) - 7, (,9) - ((E)
and
Tn(U) (-0))) & ((E))
(133)
It is straightforward to see (t(() _ (e((), = 1, for any U by definition of US. Furthermore,
E'(c) S U (,(C)
(134)
since if all 2k dimensions are bounded in absolute value by e/v then the Euclidean distance of the vector is bounded by e.
Therefore it suffices to bound (EE + A(E),A(e)) for each j [k].
Bounding (eE) Since fj is C,-Lipschitz for all j (Lemma 11), we have:
C. n
(f5(U)) fa(1| = (f)(v=) fz(x)] S
(135)
Thus, choosing e V2kC./n means that ((E) O. (We can tighten this bound by only assuming that fy is Co-Lipschitz outside a set of small measure.)
Bounding A(E,,))- Let F(-1.1) 3 f be the extension of f defined as f(x) [[[m]] /n) for all [0, 1]. Note that f is not continuous in general and hence not Lipschitz. We have for any x E [0,1]
(Af((*) Anfs(u=)) = Afz(x) f Af}())d(())
(136)
3/-
n
[Af}(0) Af}())
(137)
where used uniformity of X and triangle inequality. The last thing that need to show is:
11f/ - 1 ( ((1 Unn + f (xn (yn 1/n) f(dx)))dX(())
(138)
1/¹ n² x))(((()=)) f(z 11/)))ddd
(139)
C2
(140)
n²
From here, by a word-for-word argument, we can show that the same choice of does the trick to make ((E) e. This works since we only use the fact that S E Freg(C.) well as assumption conditions in the previous proof.
Bounding dæ. We have:
du (x( = max(
sup inf dLP(N 1),
sup inf dLP(n. S e. (E) EEa((A))
n, E. (A..) (ES)(A) (E)))
(141)
Therefore,
8k
CaCuttl
C.+l
CaC (VVCaC
2C. + C. +
(A <
Σ
<8
(142)
2
n
n
30

---

Lemma 10. E Fix f E Freg(C.) Define the restriction f: [n]] + [-1.1] uu
----// [(=)dX(z). Then f' F Fnree((..)-
Proof. Firstly, we have for any u E [n]/n:
[f((]) S n [ If(z)dd\()) S Sn S", IdA(2) =
(143)
u-1/1
M--1/n
Therefore [ S sn/n = and thus f' is measurable. Finally, for any a < u' E [n]/n:
(f'(1) f'(')) Sn /_- u-11/n
If(=) f(= (u' w)]l s Co(u' - u), (144)
where we use Lipschitz property of f in the last inequality. This shows that f also C,-Lipschitz.
The restriction to Fi-1.1] is necessary for this lemma to work because L (10, 1)) functions can blow up near O. Lemma 11. Fir E N. Fir F n.rgg(C..) Let ya [am]] |n for any [0, 1]. Define the extension f 1 (1 Yon zn)f(ya) + (In f 1/n). Then f E Freg(C.).
Remark 1.
Proof. Firstly, since I' linearly interpolates between points of f. its range cannot exceed that of f. The restricted range immediately implies that the 1,2 norm is bounded by since the support is also in []. Finally, for any < x' E [0, 1], if there is such that linear means that the line segment
I, x' Iu - 1/n, u) then the fact that the interpolation from f'(x) to f'(x') shares the same slope as that from f(u) to f(u - 1/n), which is at most Co since f f FnreR(C... Otherwise, there exists a u < u' E [n]/n such that x E [u - 1/n, u) and x' [u' - 1/n,u'). We have:
-1 C,(a' -x),
(145)
which proves Lipschitzness of f'
D.3 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 wise composition with 1-Lipschitz map:
Lemma 12. Fix k E and a R. Recall that p F.RR -R is L-Lipschitz map. Let A1, A2 : F + F satisfy Assumption 2 with constant C2 and C2 respectively; and Assumption 5.A or 5.B or 4.B with constant Co. and C² respectively with common resolution set N. Then:
1. + Ag satisfy Assumptions 2 and 5.A or 5.B or 4.B with constant (CA + +2) and (C. + C2) respectively.
+
2. aA1 salisfies Assumplion 2 and 5.A or 5.B or 4.B with consland |a]Ca, and |a|Ca respectively.
3. pA (where the composition is done element- wise) satisfies Assumption and 5.A 5.B or 4.B with consland C) and Cj respectively.
4. Furthermore, if Cl =0 then Ag A₁ satisfies Assumption 2 and 5.A 5.B or 4.B with constant C C2 and C² respectively.
Proof of Lemma 12. To recall, A1, A2 : F + F are P-operators that satisfies Assumption 2 with constant C) and C2 respectively and Assumption 5.A or 5.B or 4.B with constant C. and O respectively with common resolution set N. We now show each part of the Lemma.
31

---

1. We have, for any f.g E F: [I(A1 + A2)f (A1 A2)gl2 - ||A1f Aigl2 + 11 A2gl2
(146)
S C - gll2 Call gll2.
(147)
where the first line is triangle incquality and the second line is Assumption 2.
Let f Freg(C.) piccowise constant intervals [n|/n and 2, (u 1/n,, ul for some n E N and [na], we have:
((A1 + Az) - (A1 + f2)f(y)) & [[A]f(())
- + - [A))
(148)
s -c - v-
(149)
where the first line is triangle incquality and the second line is Assumption 5.A.
2. We have, for any f.g F:
[[(AA)) (aA1)all S |a| ||A A1gl2
(150)
S |a| C -912
(151)
where the first line property of norm and the second line is Assumption
Let f E Frgg(C.) piecewise constant on intervals [n]/n, and 2, E (u - 1/n, ul for some n E N and u E [n], we have:
(aAi))(=)) (aA1)f(0)) s [a(A)]((z) alA1f(00)
(152)
S |a| C | vl.
(153)
where the second line is Assumption 5.A.
3. We have, for any f.9 F::
[[(AA)) (pA1)9ll2 ||Aff - A1gl2
(154)
5 CCills gl12,
(155)
where the first line is Lipschitz property of and the second line is Assumption 2.
Let f E Freg(C.) piecewise constant on intervals [n]/n and a, E (u 1/n, u| for some n E N and E [nt], we have:
((AA))(()) - (pAi)((v)) S ([AA/(())--
(156)
S (A C. 1=---- vl.
(157)
where the second line is Lipschitz property of p and Assumption 5.A. 4. We have, for any f.g F:
((A2Ai)) (A2A1)ol2 CaIIAIS- Aigll2
(158)
SC 9l12.
(159)
where the first line is Lipschitz property of A2 and the second line is that of A
Let f Freg(C.) piecewise constant intervals [n]/n. Since A send constant pieces to constant pieces, the final implication follows direction from Assumption 5.A of Ag.
Lemma 13. Fix E N,K (K) satisfies Assumption 2 with constant C'
and Assumption 5.A with constant C. and resolution set N. Let n E N, E Fa, f2 E F. Recall that E F denotes the extension of f Fn to [0,1] f(x) f([an])/n. If [|/1 - f2lla S M for some posilive constant. M then
3 KC
|
A f2
3*C2kM
(160)
32

---

If A satisfies Assumption 5.B with constant Ce instead then the bound becomes:
A - fall gh+1k(C, + C + +
(161)
n²
If A satisfies Assumption 4.B instead then the bound becomes:
A - A f2lB g
+ C)
+ M
(162)
n²
Proof. When O, 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:
A
fal2
(163)
Σ
(A
f22))
(164)
#EI/n/n]
2
12
A[A Allu)dy-A**ah de
(165)
#EI/n|n]
Here we can use Jensen's 's inequality to get:
| A f2ll
(166)
Σ Su (MIA A[1 sa](s)) dyd=
(167)
MEl/n|m]
(168)
We proceed slightly differently based on the exact assumptions that have. If A satisfies Assumption 5.A or 5.B then:
A
A f2ll2
(169)
Σ
<n
WE1/n/un -
[AA fil())
+ - 'Sa(e)i) dyd=
(170)
<n
NE1/nfo
C. +1
+ IA[AR (Ale))NAE))))) + -A[AR- ffl(2)) ALA ALA-- -al(ee)
dydz
(171)
Co +1+1
+ - (I(+))A((E.) + -AIAR- f1((2) A[A (a(=))) 2 dz (172)
3(C. 1)2
+3 (AAAAA- (AIAAA- +3] - [1] 12 (173)
n
Here, we give heuristic argument while the formal argument is exactly similar to that in Theorem 2. The term (A[A"_ (i)()))(()))))) can be made close to 0 possible simply by changing the requirement on X(E) to be smaller and smaller (see the discussion
33

---

after Assumption 4.A). At the same time, assumptions ensure that since A fi is piecewise constant function, the action A on cannot become too wild (Lipschitz outside of E and bounded L norm inside E). This heuristic argument, when made rigorous can help us conchude that:
14 f 3(C++1) 1)2
n + +3
fI - A fall
(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:
| A f2l
(175)
Σ
WEI/n(M)
[A[AR 1-1 fil(e) - A(A fil(w)) + |A[A" (AAA) A[A" fal(ee)) dydz
(176)
22n Σ
AAAA-TAIC Al(()) -100)-(00
A11 A1a--))1(0)) dydz
WEI/n[n]
(C+11
+ 2n
+ +1A[A= (((3))=))(())MM((FF))) dydz
(177)
WE wEI/n[n]
Ju-k
n
3(C, + 1)}
+3 (AIA--)/ + +3||A[AA- 1fl - A11 (178)
n²
Again, we will make of heuristic argument to argue that the middle term can be controlled by controlling X(E) since A sends Lipschitz functions to Lipschitz functions outside of E and has bounded L1 norm inside of E. Therefore:
1 - A 3(C++1) + A3IAAAA fi] - 1[A1-1f211
(179)
n²
Solve the recurrent to get the result in the statement of the Lemma.
Lemma 14. In the same setting Lemma 13, recall that tilde over function in Fr denotes ils extension to F. Tf A satisfies Assumplion 2 with constant CA and Assumption 5.A with conslant Ce and resolution set N. Let ((h, A, (EgEm) ΣK-1 A (t,, for some Ty graphop neural network such that [ f) Bb A, A, M for all g E [m.). Then:
10h - < K² k2 (Kn 2C C M).
(180)
If instead A satisfies Assumption 5.B with constant Ce then the bound becomes:
[b, An. f) (h, A, fil < K²n (Kn=2CC,+1)C + +
M).
(181)
If instead A salisfies Assumplion 4.B then the bound becomes:
2C, + [h, An. @(h A, 1 < k2 (Kn-2(C,
1) + (O2MM).
(182)
34

---

Proof. We have:
|| (h, An, - ((h, f1
(183)
(0 p
( (h, An) (ΣΣ 1 (k,, A, A.1(c)) 2
Σ
d)(x)
Ju-1/n
"c " [g]
9
(184)
2
Σ
ΣΣ
A 2 (h, An, ()) A A0, d)(x)
(185)
1111/n
2
dd(x)
(186)
ME [R]
u-1/n
<km
ΣΣ
At (h, Am, ,h, D(o))) d)(x)
(187)
He a [n]
9
=Km
A An, fx) - A A. (3)
(188)
CC
SKn ΣΣ
C 1 Am. f) F, A, f11
(189)
n
g
Sn nn K. Co. 3 c + K² ny 3 C M
(190)
=K2n (Kn C C
(191)
where in the first line, we use the fact that continuous extension commutes with finite element-wise sum and element-wise application of p, while expanding I,2 norm; the second line uses Lipschitz property of p: the third line uses triangle inequality; the fourth line uses cquivalence of p-norms in finite dimensional vectors; the fifth line is again L norm definition; the sixth line applies Lemma 13 and the rest is algebra.
To get the rest of the cases, applies different versions of Lemma 13.
Lemma 15. Let & be an L-layer graphop neurel network in the same setting as Lemma 13. If A satisfies Assumption 5.A with constant Co then:
(h, An. f) (h, A. f) S n (3" Krimax CK) max (Co, 3 1² Ce CK).
(192)
If instead A satisfies Assumption 5.B with constant Ce then the bound becomes:
[k, An, (h, A, S 133 XmmaxCX)) max (C,, (C.,3KK?(CC + M) C.
(193)
If instead A satisfies Assumption 4.B then the bound becomes:
[b An, f] (b,, Al12 sn "3 Krmma CK max (C,, 3K K² + 1) Ck
(194)
Proof. Solve the recurrent in Lemma 14.
We now prove a more general version of Theorem 3
Theorem 6. Let A E F salisfying Assumplion 2 with consland CA and Assumplion 5.A with constant Ce and resolution set N C. Let n E N and form the discretization A,, as per Theorem 2. Let h be normalized such that [/a| < 1 dlement-wise and form the graphop newral network (h, A, F and (h, Ans F, + F,,. We have the following approzimation bound:
das (h, A, ), (h, Ang S p/ CACo + C. CK P2 + Cyn (195)
where = LKL and P2 = 3k K2,
35

---

If instead A satisfies Assumption 5.B with constant Ce then the bound becomes:
(M, A, (h, An. -) S 1 CAC. + (Ce 1) P2 + (Co + 1)n= (196)
If instead A satisfies Assumption 4.B then the bound becomes:
dM A, (h, )) S 1/2 CAC, + (C.+ 1)m
(197)
Proof. The proof structure is similar the proof of Theorem 2. For brevity of expo- sition, we will write h as the (shared) set of parameters in the graphop neural net- works and shorten @ == $(h, A, and 4, == Apr, Fix k E N, we will bound suP inf ES..c. dLP(TT Tn.)
Fix arbitrary ") E Sk.c, ($). By definition of a (k, -or-flll,,,, there exists f1, Jx T ((, 1)) such that Do(Ji,...ffz) For all j [k], let Fn 3 fj |n|/n D Jw- 1/n [s())d\(z). That fj E (egtc.)(mn//) is shown in Lemma 10. Set Vn
Da. (f%....,,())
Bounding d.p(1) mm)) Fix some > 0 to be specified later, by definition of drp,, we need to bound, for each E Bg:
((U) - n/, (U9)
Σ
n 1 Lurr
(198)
WE/n//n
Notice that since the Lebesgue measure, one can denote ye = [zn] //n and write:
T(U) - TT, (U9) - =f² l((ro).....t.tt)))e - (.
(199)
Since the integrand is only positive when ((.))...,,,((())) E U and (f1 (Ma).....
P (yz)) & U and this conjuction only happens when (1( (x)())) (fa)., Pn (y2))]l2 )ll2 e, we have:
muU) (U9) & A(E(C)) S Σ +
(200)
where
E()) = (x:
- (V(()... Frf((D)))ll > c)
(201)
(c) = {z: : | (x) 3 (v.l > V2k" ). for 2 E (0. 1).1 E [k].
(202)
where B is the identity operator for any operator B the appropriate space.
Bounding (e). Fix j E [k], we have:
S." (ff(2) - (nf((=))de S V. (Df/(o)) (,.5((u))) dr
(203)
=1 &nlille=
(204)
-n Kn K CK) max (C,,3k Co
(205)
where the last line uses Lemma 15 under Assumption 5.A with constant Cc. Similar results are obtained for the other assumptions.
We also have:
[ ('ee)(0) - 2nf(( -
((E)
+ 0.
(206)
V2k
Thus selecting
<> V 2kv2k n 1333 K Kr CK) max (C., 3K BIKK2CC C CK)
(207)
makes (e)) < zt.
36

---

Bounding (e)) This step simply uses Lipschitzness of the graph signal to bound its discretization and is thus identical to that in Theorem 2. short, choosing e v2kC,,/n gives -
Bounding sup e&, c, (b,) inf inf (2) der(n nique as in Theorem 2.
Ba).
This direction uses the same tech-
Putting everything together
Defining CA
(Mmax KC )C gives choice of:
é = 1 CAC. CoNmax CK P2 Con
(208)
where Pi = 3 and P: = 3* K? K2
For other choices of assumptions, obtain similar bounds.
E
Additional results
E.1 Proof of Theorem
Because of completeness of du in the space of closed subsets of P(R22) for every & E N, the statement in Theorem is equivalent to showing that for each & E N, we have Sk,L(m) converges (A) dæ- We do this via a mollification argument.
Definition (Tipschitz mollifier). A Lipschitz mollifier in RR is smooth (infinitely differ- entiable) function & R + IR satisfying:
JR ((x)d\(z)
2. lim,-0 (x(x) = lim, E (1x(E))) = 6(x) the Dirac function.
3. Although not standard, we require & to be 1-Lipschitz and symmetric around 0 (ő(x) d(-x)).
Given measureable function f 1F-1,1 defines the convolution operation:
/ / x))d(v))
J (x0:0-
(209)
The next result shows the existence of such function: Lemma 16. Let Φ + IR be:
e (1
(1-
12
if $ 1
<(x)=
(210)
0
otherwise,
where Z is a normalization constant to make sure that Sq Φdl = 1. Then & is a Lipschitz mollifier.
Proof. The first property is built into the definition. The second property is obvious since the support of <(x/t) [- and thus it converges the Dirac function as goes to Lipschitz-ness can be seen by computing the first derivative (since the function is smooth) over 1) and see that bounded in [-1, 1]. Symmetry also obvious since the function depends only on the absolute value of its argument.
Consequences of a Lipschitz mollifier include: Lemma 17. Let be a Lipschitz mollifier and 0, then for any measurable f F f * ó. is max(1,e -2) and lim |l - f dell2 0.
37

---

Proof. For the first part of the statement, consider:
If * @x(x)
f(z) z) f(=)((z -())(((=)))))(())
(211)
[(=)
2 (-=3))
1/ )) dx(=)
(212)
c
1
r
y
d)(z)
(213)
R
r
yl
(214)
22
For the second part, we have:
( / 2))==) - [())dd(())
(215)
(z+)) - f(z))d\(2), R
(216)
where use two changes of variables. Square both sides and take integral over I and use Jensen inequality to get:
If * oe - f112 [(LLE)))((
((=))))())))((z)
(217)
Apply Fubini- -onelli theorem to factorize the mollifier, we gel:
Il Φ. f113 / ((M-=a)))(())MMMMllooe))))))))
(218)
JR
= - (ó(ze
(219)
Apply final change of variable:
Ilf th - 512 S [ ( (o(=))
(220)
Therefore, as goes to 0, the inner integrand goes to O. Since f and f * de are all bounded (as f E 1)) for small enough we can apply dominated convergence to conclude that the intogral itself goes to and thus the 2-norm on the left hand side also goes to 0. L
We are now ready to proceed with the proof of Theorem 4. Given an element
(A),
there exists a set of functions F i.f...... ........f. fx} C - (l). 1)). Each of these functions can be extended to R by setting f(x) = f(0) if x < 0 and f(x) f(1) if x > 1. Call the extended function f'. Now we can apply mollification convolution to each of them to get family of functions (fz,e == f2+ * de bejee, Recall that we have shown fj. == //.//L(()) to be L(ns-Lipschitz for each n E N. Let fi,n be the restriction of Jj.m to Fa. Then fy is still ((m)- LLischiic (in the metric on 1 1/m[n] induced by metric on [0. 1)) and thus we can find a profile for F" := f',... in (A,)
Furthermore, by property of mollifier and the fact that L(n) do goes to infinity, we have [|fr. - fjll2 + with n - co. Since f is constant outside [0, 1/, we also have [|fmm.10.11 - f51ر - 0 with n. Using the same proof technique as Theorem 2, we can conclude that:
dLp(DA., DA(F)) 2-00, 0,
(221)
and thus Sa(A) C lim,, (A)) For the other direction, recall that Se(A) lim,, (A,A,)) and that (An)) C Sk(An). Together with completeness of du, conclude that lim (Se ()), Sx, =
Conjecture 1 (Action convergence of graphop neural networks). Let (An)nEN be an action convergent sequence of graphops. Then (0 An MneN is an action convergent sequence of P-operators.
38


Reviews:
[{"review_id": "0s2kOUuZ9F", "reviewer": "Reviewer_QqZq", "summary": "This work is essentially extending the existing theoretical study of GNNs through graphons by replacing them with graphops, an operator view on graphs that allows for results of sparse graphs. Then, standard results on size generalization for instance, are presented.", "questions": "Could the authors give the readers more intuitions on how P-operators can generate real-world graphs? \nhow can  (k,L)-profiles be interpreted in real-world? ", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is technically sound as far as I could check. The theoretical contributions are non-trivial and present enough mathematical rigor for this venue. It is a first step towards moving being graphon-restricted analysis of GNNs.", "weaknesses": "The issue I have with this paper is its usefulness for machine learning applications. We understand the space L^1([0,1]^2) pretty well for graphons, but the newly introduced operator view from Backhausz and Szegedy isn't clear to me yet. Could the authors give the readers more intuitions on how P-operators can generate real-world graphs? Remember that in the end of the day the GNN is applied to real-world graphs. Graphons can be seen as latent factor models, which is somehow interpretable as a graph generating process. How can P-operators be seen by the readers? This might be a flaw in my understanding that the authors can help me with, so I'm willing to raise my score. In particular how can  (k,L)-profiles be interpreted in real-world? Graphs as operators make sense in a lot of fields, but I'm a little concerned that graph data isn't fit to this view. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Regarding the questions and concerns:\n1. On the view of graphs as P-operators: We first want to note that P-operators are very general operators satisfying a bounded (operator) norm condition. Viewing graphs as operators is not unfamiliar to finite graph analysis: the adjacency matrix of an n-vertex graph is a matrix and thus, a linear operator $A$ from $\\mathbb{R}^n$ to $\\mathbb{R}^n$, whose image describes a single layer of message passing algorithm: if $f \\in \\mathbb{R}^n$ is a vector of node features then $Af$ is the output of a single layer of message passing. The analysis of graphons W (dense graph limits) also makes use of properties of the Hilbert-Schmidt operator $H$ defined as $Hf(y) = \\int_0^1 W(x,y)f(x) dx$. Similarly, the image of this operator is the pre-activation of a single layer of graphon neural networks. In this view, one can even bypass the use of a generation model (kernels/graphons) and directly model graphs by the images (actions) of their adjacency matrices or their transformations. \n\n2. P-operators in real-world graphs: While dense graph limits such as graphons are amenable to more analysis tools, we would argue that P-operators as graph limits are more realistic for real-world graphs, albeit with a more difficult analysis - as you have seen in this paper. This is because real-world graphs are very rarely dense (at least quadratic order of edges) or even relatively sparse ($n\\log n$ order of edges). Molecule graphs, evolutionary trees, grammar trees, social networks, for example, are usually sparse, bounded-degree even, because of real-world physical constraints. Thus, P-operators capture more realistic graphs in real-world datasets. Furthermore, graphon limit model is not enough: by definition, under the graphon model, the limit of these sparse graphs vanishes and cannot be distinguished from the constant 0 graphon, making their bounds trivial. It is also worth pointing out that both finite graphs and graphons are examples of graphops (which in turn are P-operators), so we have a larger graph limit model altogether. \n\n3. $(k,L)$-profiles real-world interpretation: It is easier to gain intuition in real-world examples by considering $k$-profiles. After all, in Section 4.4 we show that with minimal overhead, $(k,L)$-profiles yield the same convergence as $k$-profiles. When $k = 1$, an element of a $1$-profile of a finite $n$-vertex graph is a joint probability distribution of the form $(X, Y)$ where $X$ is drawn from an empirical distribution supported on some node features $f$ and $Y$ is drawn from an empirical distribution supported on the image of $f$ after $1$ round of message passing on the graph. The $1$-profile is then the set of such distributions when $f$ is taken over a set of reasonably regular (measurable, bounded, Lipschitz) node features. Therefore, the $1$-profile couples the input and output of a message passing layer and captures their dependence structure across all reasonable node feature vectors. Please refer to Backhausz and Szegedy’s original paper for some illustrations of $k$-profiles. We will provide our own illustrations in the next revision of the paper.\n\n4. Graph generation via P-operators: Please refer to the reply to all reviewers section. \n"}, {"review_id": "W2ILsb0rEO", "reviewer": "Reviewer_E8cZ", "summary": "This paper explores the theoretical perspective of whether graph neural networks (GNNs) can generalize to graphs that are different from the ones they were trained on. The authors study the transferability and approximation results via graph limits, including sparse graphs such as bounded-degree or power law graphs. The paper presents various notions of graph limits and develops quantitative bounds on the distance between a finite GNN and its limit on an infinite graph. The authors also verify the regularity assumption for various graph sequences in this study. Overall, the paper's contributions include a theoretical framework for studying the generalization of GNNs to different graphs, as well as insights into the regularity of graph sequences and the use of graph limits for approximation and transferability analysis.", "questions": "Q1. Could you expand the experimental evaluation by including experiments on a wider range of datasets and graph structures? This would provide a more comprehensive understanding of the effectiveness and generalizability of your proposed approach. Additionally, providing a detailed analysis of the experimental results, including statistical significance tests and comparisons with baseline methods, would strengthen the empirical findings.  \nQ2. Can you provide real-world application examples where your proposed approach can be applied? Demonstrating the practical utility of your approach in real-world scenarios would further highlight the significance and relevance of your work.\nCould you discuss the limitations of your proposed approach in more detail? Specifically, addressing the scalability of the approach to larger graphs, considering different types of GNN architectures, and exploring the impact of different graph properties on generalization performance would be interesting.   \nQ3. Have you considered the computational complexity of your proposed approach? It would be helpful to discuss the computational requirements and scalability of your method, especially when applied to larger graphs.  \nQ4. Can you provide more insights into the regularity assumption verified for various graph sequences? How does the regularity assumption impact the generalization performance of GNNs, and are there any specific conditions or properties that need to be satisfied for effective generalization?  \nQ5. Can you discuss potential future directions for your research? Specifically, addressing the scalability of the approach, exploring different types of graph structures, and considering the impact of different graph properties on generalization performance would be valuable areas for further investigation.  ", "limitations": "The paper does not explicitly address the potential negative social impact of the proposed approach. While the paper focuses primarily on the theoretical aspects of graph limits and their implications for GNN generalization, it would be beneficial to include a discussion on the potential ethical implications of the proposed approach. Specifically, the authors could consider the potential impact of their work on issues such as privacy, fairness, and bias in machine learning.\n\nAdditionally, the paper could benefit from a more comprehensive discussion of the limitations of the proposed approach. While the authors acknowledge some limitations, such as the need for regularity assumptions and the limited experimental evaluation, a more detailed discussion on the potential limitations and their impact on the generalization performance of GNNs would be valuable. ", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. The paper takes a unique perspective of studying the transferability and approximation results of GNNs via graph limits. The proposed approach is novel and provides a theoretical framework for studying the generalization of GNNs to different graphs.  \nS2. The authors provide rigorous mathematical proofs and analysis to support their claims, which potentially have important implications for the practical use of GNNs in real-world applications.  \nS3. The paper's results hold for both dense and sparse graphs, and various notions of graph limits, which makes the paper's contributions applicable to a wide range of graph-based learning tasks. ", "weaknesses": "W1. Lack of real-world application examples: The paper focuses primarily on the theoretical aspects of graph limits and their implications for GNN generalization. However, it would be valuable to include real-world application examples where the proposed approach can be applied and demonstrate its practical utility. This would provide concrete evidence of the significance and relevance of the work in real-world scenarios.  \nW2. Limited experimental evaluation: While the paper includes some experimental results, the evaluation could be more extensive and diverse. It would be beneficial to include experiments on a wider range of datasets and graph structures to demonstrate the effectiveness and generalizability of the proposed approach. Additionally, providing a detailed analysis of the experimental results, including statistical significance tests and comparisons with baseline methods, would further strengthen the empirical findings.  \nW3. Lack of comparison with existing methods: The paper could benefit from a more comprehensive comparison with existing methods that address the generalization of GNNs to different graphs. This would provide a clearer understanding of the novelty and effectiveness of the proposed approach. Including a comparison with state-of-the-art methods and discussing the advantages and limitations of the proposed method in relation to existing approaches would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and would like to address the individual points. \n- W1. Real-world applications of GNNs on very sparse graphs (bounded degree, linear order of edges, etc.) have been demonstrated in various disciplines elsewhere. Our paper aims to explain the transferability observed widely in practice in a rigorous theoretical framework. Theory for these very sparse graphs is extremely limited in the literature and thus, lots of existing empirical findings for them are not accounted for rigorously. For example, all molecular graphs are bounded-degree, and thus extremely few existing theories can systematically explain transferability between molecule graphs even when they share lots of structural similarities (for example graphs of polymers with different numbers of units). Other realistic graphs, such as road networks, social networks, evolutionary trees, grammar trees are also mostly sparse due to physical constraints. These have also been studied extensively elsewhere and we refer the reviewer to applied publications for these phenomena. \n- W2. We believe the reviewer is mistaken since we do not include any experimental results in this paper, let alone strengthen them. Our main contribution is a theoretical analysis of transferability of GNNs, rather than a proposal of a new method or a new architecture. That being said, we will add proof-of-concept experiments to demonstrate our Theorems. \n- W3. We will extensively add to our related work section. See also more details in the response to all reviewers. However, since so few theoretical works in the literature share the same emphasis as ours (transferability on very sparse graphs, which are notoriously hard to analyze), it is unclear what the ‘state-of-the-art methods’ are.\n- Q1. Please refer to the reply to W2 above.\n- Q2. Relevance of our analysis to real-world applications: please refer to the response to W1. Scalability of our approach to larger graphs: since our bounds are quantitative and non-asymptotic, they apply to graphs of any size, large or small, and even graph limits. In this paper, we only consider spectral GNNs to demonstrate some main takeaways in terms of the metric and the corresponding convergence. However, we believe our approach works for other GNN models, such as graph isomorphism networks (GIN). We also agree that studying how different graph structures impact rate of convergence under the metric d_M is an interesting direction forward, but is outside the scope of this paper.\n- Q3. The main contribution of this paper is a convergence and transferability analysis of existing GNN models, as opposed to introducing new models. That said, we will provide small experiments demonstrating our Theorems in the final version of the paper.\n- Q4. For a discussion of our assumptions, please refer to the general address to all reviewers. \n- Q5. Please refer to the “Implication for future empirical and theoretical work” section in our reply to all reviewers. \nLimitations: we will address some ethical concerns of GNN developments. That said, seeing that our work theoretically verifies observed transferability experiments done elsewhere, we share the same ethical concerns with most papers in the GNN literature without meaningful deviations. \n"}, {"review_id": "WD60j63coY", "reviewer": "Reviewer_jR1r", "summary": "This paper analyzes the transferability of Graph Neural Networks (GNNs) in terms of size. It proposes Graphop Neural Networks that operate on graphop signals and discretization of the network. It proves that the discretization of graphop and the graph are close, and consequently, two discretizations of different resolutions are close. It also shows that the corresponding Graphop Neural Network outputs are close which implies the transferability of GNN in size.", "questions": "- What is the key difference between this work and the graphon neural network which also adopt a graph limit perspective?\n- The bounds require the number of vertices in both graphs to be sufficiently large. Then how to interpret the bound when one graph is large and the other is smaller, which is more important for graph size transferability, and also two small graphs.\n", "limitations": "Review Summary:\nDue to my lack of background knowledge, I could not appropriately relate it to previous research and assess the proof fairly. However, the paper addresses a crucial problem in graph learning and seems to provide a sound theoretical analysis, which leaves it on the borderline.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "My background does not support me in evaluating the paper fairly. However, I believe the tackled problem of GNN size transferability is critical, and the author's analysis using graph limit and its discretization is promising. The assumption seems mild, which could make the theory applicable to most existing GNNs and real-world sparse graphs.", "weaknesses": "The related work session is scarce, which makes it more difficult for me to understand the background. The paper is purely theoretical, which is fine. Still, it will be more sensible for readers like me if the authors can provide some form of experiment on synthetic graphs of variable size to better understand the implication of the theorem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and address individual questions and concerns:\n1. Scarcity of related work: Past works on size generalizability of GNNs rely either on graphons or random graph models induced by a kernel, while we focus on deterministic sparse graphs. In the latter regime, we only are aware of Roddenbury et al., 2021. This is not unexpected as many authors in the literature agree with us that the analysis of sparse and bounded-degree graphs is challenging and intricate (more in our reply to all reviewers). That said, we will include a more detailed comparison with results obtained from random graph models and extended graphon models in the final version of the paper.\n2. Comparison to graphon neural network: Our work shares a lot of structure with Ruiz et al. 2020’s graphon neural network, especially in our use of graph limits. One major distinction (see table in our reply to all reviewers), is that the graphon limit of sparse and bounded degree graphs is the constant 0 graphon. This makes their approximation bound between a finite graph sampled from a graphon to the limiting graphon vacuous.\n3. Requirement of a large number of vertices: our bounds are non-asymptotic, quantitative and have a specific rate of convergence, which is one of the strengths of our results.  This means that our results work for all finite graph sizes. In particular, our transferability bound between a graph of size m and n states that the transferability gap scales with order $(\\min(m,n))^{-1}$.  \n\nWe will work on improving the accessibility of the writing in our revision. We would also love to help you understand more about our line of work, so please do not hesitate to post more questions that you think we can help you answer.\n"}, {"review_id": "YKi5sfngYe", "reviewer": "Reviewer_3WrU", "summary": "This paper analyzes the transferability and approximation qualities of Graph Neural Networks (GNNs) when applied to graphs or Graph Signal Operators (GSOs) sampled from graph limit objects, known as graphops. The authors demonstrate that when a sequence of graphs is sampled from a graphop, the sequence converges according to a well-known metric. The paper also introduces the concept of graphop neural networks, which are utilized as a tool for analysis. It is shown that when a GNN is applied to a sequence of graphs sampled from a graphop, the output converges to the corresponding output from the graphop neural network applied to the graphop itself.", "questions": "- Could you clarify how your convergence definition aligns with the one proposed by Backhaus and Szegedy? In particular, how can we assure that convergence results still hold if we consider a sequence of Lipschitz constant $(C_{v_n})_n$ that grows sublinearly in n? Why does $d_M$ from Backhaus and Szegedy also converge to zero in this setting?\nIf this is sufficient, why do the authors change the notion of convergence?\nWhat motivates the chosen notion of convergence? If not for mathematical convenience, what other reasons justify this choice?\n- What implications do these results have for practitioners? Maybe the authors can provide some (simple) experiments, where Theorem 2 and 3 are verified? This would help for clarification and realizing an example (other than dense graph convergence which was already covered in previous works)\n- What implications may these results have for developing new theories? For example, do you expect to achieve generalization bounds for sparse graphs such as in [4]?\n- On line 73, could you explain why nonlinear operators are significant? My understanding is that all Graph Signal Operators (GSOs) are linear operators.\n- You sample nodes deterministically, can you compare the loss of generality with works that do not assume this? E.g., [2,3,4]\n- You mention that all graphops are self-adjoint. In light of this, why are nonlinear operators brought up? Note that every self-adjoint operator is linear.\n- Regarding Theorem 4, could you clarify its utility? Also, the proof seems peculiar and certain terms such as $A$ and $A_n$ lack clear definitions.\nFor example, why does $S_{k,L(n)} (A_n) \\subset S_k(A)$ hold? These profiles consist of different distributions, right? More details are provided below.\n\n### Minor Issues and Questions:\n- Line 12: Could you clarify why graphs sampled from the same graphop share structural properties? Especially, for graphops that are not induced by graphons.\n- Line 24: Please consider adding [2,3].\n- Line 43: Please refer to Keriven's work on \"relatively sparse\" graphs in the context of random graph models.\n- Line 53: Do you mean \"limits of GNNs of infinite sequences of graphs\"?\n- Line 58: [3] generalized the results to unbounded graphon operators and more diverse GNNs.\n- Line 89: Ruiz's work also indicates a $\\sqrt(n)$ dependence which decays to zero, this statement seems incorrect. Also, there are other works by Ruiz considering sparse graphs.\n- Line 100: Random Graph Models (RGMs) essentially consist of graphons/kernels which are graph limits, and they are not opposed to these.\n- Line 102: Could you define \"closeness\"?\n- Line 119: Please mention that the entire work considers only spectral (polynomial) GNNs.\n- Line 130: The space also contains limits of sparse graphs.\n- Line 185: What does \"positiveness\" mean?\n- Line 235: Do the results generalize to higher dimensional features?\n- Line 246: What is $F_m$? \n- Line 310: How do you define d_M for these non-linear operators that can neither be self-adjoint nor positive?\n- Line 334: What do you mean with \"wild\"?\n- Line 335: Could you elaborate on what \"specifically designed for our discretization scheme\" means?\n- Line 341: Why \"high probability\"?\n- Line 379: Could you clarify what this sentence means: \"Then, A_n converges to the same limit as action convergence\"?\n\n#### Proof of Theorem 2:\n- In bounding d_H, why is the maximum over certain quantities not considered?\n- Line 731: Could you define the conditions for epsilon in the phrase \"for some epsilon\"?\nThere seem to be numerous typos throughout, such as in equation 56 and line 727, $S_k,C_v$.\n- The definition of $U_\\varepsilon$ is difficult to locate and appears incorrect.\nEquality 60 should be an inequality.\n- Line 763: What does $\\bar{\\mathcal{E}}$ denote? \n\n#### Proof of Theorem 4:\n\n- Line 1007: Could you clarify what it means for $f''$ to be Lipschitz in $l^2(n)$?\n- Line 1011: What does the notation $\\lim_\\bar{S_{k,L(n)}(A_n)}$ signify?\n\n[1] Ruiz, L., Chamon, L., & Ribeiro, A. (2020). Graphon neural networks and the transferability of graph neural networks. Advances in Neural Information Processing Systems, 33, 1702-1712.\n\n[2] Keriven, N., Bietti, A., & Vaiter, S. (2020). Convergence and stability of graph convolutional networks on large random graphs. Advances in Neural Information Processing Systems, 33, 21512-21523.\n\n[3] Maskey, S., Levie, R., & Kutyniok, G. (2023). Transferability of graph neural networks: an extended graphon approach. Applied and Computational Harmonic Analysis, 63, 48-83.\n\n[4] Maskey, S., Levie, R., Lee, Y., & Kutyniok, G. (2022). Generalization analysis of message passing neural networks on large random graphs. In Advances in Neural Information Processing Systems.\n", "limitations": "The authors do not address limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Presents a novel integration of known techniques, specifically graphops and Graph Neural Networks (GNNs). The authors notably generalized the results for graphs converging to a graphon, which has been proven in [1,2,3].\n- This research could potentially pave the way for further exploration into the transferability of GNNs in relation to sparse graphs. However, the authors miss to mention some work from Keriven et al. and Ruiz et al. which already consider non-dense graphs. ", "weaknesses": "- The quality of writing and presenting is poor leading to bad comprehensibility. None of the theorems are self-contained. While the proofs seem correct, it is difficult to follow them due to notational issues and gaps in the argumentation (see below for a non-complete list). Note that I did not check all proofs thoroughly. \n- The authors make some, at least, weird assumptions such as graphops being self-adjoint, but allowing them to be non-linear. The set of such operators is empty. Also, the choices of the convergence notion are not clear, even though a subsection is dedicated to it. \n- Some assumptions appear restrictive, e.g.: The graphops are assumed to be sampled from $[0,1]$, in contrast to many other transferability papers (e.g. [2-4]). Assumption 3.A  also appears restrictive.\n- The paper lacks clear organization and writing, with numerous notational errors scattered throughout. The order of presenting assumptions before other information also appears confusing. The appendix also contains many, at least, notational issues.\n- The practical and theoretical implications of the results remain unclear. For instance, it would be beneficial to understand:\na) The potential impact of this work on theorists and practitioners, b) Examples of graphs for which the results are applicable, c) How can the convergence stated in Theorem 2 and 3 be experimentally demonstrated?, and d) The restrictiveness of the assumptions made in the study.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. \n\nWe name the 5 points raised in the Weakness section W1-W5, points raised in Question Q1-Q7, and points raised in Minor Issues M1-M24. We write B-S to abbreviate Backhaus and Szegedy’s original paper.\n1. For comments regarding the assumptions (W3), future implications (W5, Q2, Q3) and M1, M7, see the reply to all reviewers. \n2. Typos, missing references, phrasing and notational errors (W1, W4, Q7, M2-7, M9, M17-18, M20-22, M24): We will correct them and highlight other elusive notations in the revision of the paper. We will also work on improving the clarity of the paper.\n3. Self-adjoint and nonlinear operators (W2, Q4, Q6, M14): Indeed there are no self-adjoint (strictly)-nonlinear operators. However, we defined ‘nonlinear P-operators’ as those that are ‘not necessarily linear’ (line 180), including linear operators. This is important since a GNN layer itself (as opposed to just the GSO, which is linear) is a nonlinear operator and we would like to include it in the definition of P-operators. In fact, the whole (equivariant) GNN is also a nonlinear operator. This allows us to write Theorem 3, which uses $d_M$ - a metric originally derived to compare P-operators, to compare 2 GNNs. We will highlight this in the paper. Moreover, we only used the self-adjoint property of graphops to ensure that discretizing a graphop indeed gives a finite graph (Lemma 1). In Theorem 2 and 3, we no longer assume self-adjoint properties so at no point are there operators that are both (strictly)-nonlinear and self-adjoint.\n4. Restrictive assumptions (W3): While the domain of the signal is [0,1], we can extend our results to any bounded domain, but currently we do not know of a proof for unbounded signal domains.\n5. Comparison of the modified convergence and B-S original convergence (Q1, Q4): The proof of Theorem 3 with a slow-growing function of n mirrors the current proof verbatim. To gain intuition on the equivalence of the two convergence, note that the only difference between the two convergences is our use of $(k, C_v(n))$-profiles, which consider all bounded, $C_v(n)$-Lipschitz signals, instead of just $k$-profiles, which consider all bounded measurable signals. By letting $C_v(n)$ grow to infinity, we approximate all Lipschitz functions, which are dense in $L^2$ functions. The benefit of recovering B-S’s notion of convergence is that we inherit its useful properties, such as completeness of $d_M$ for linear operators. This modification allows us to use Lipschitzness of signals in our proofs of Theorem 2 and 3. This is necessary, following the insight: approximating functions by step functions on intervals of equal size (a discretization) requires a Lipschitz condition (consider extremely spiky functions, otherwise). This smoothness assumption is also ubiquitous in graphons and random graph kernels literature and may even be relaxed using our mollification argument (Theorem 4).\n6. Proof of Theorem 4 (Q7): We will update a self-contained proof of Theorem 4 and correct the missing notations. Here, $A_n$ is the sequence of P-operators introduced in the proposition and A is the B-S original limit of $A_n$. A exists due to Cauchy-ness of $A_n$ in our metric implying Cauchy-ness in B-S’s original metric (as $(k,C_v(n))$-profiles grow to approximate $k$-profiles) and completeness of the space. In line 1011, $S_{k, L(n)}(A_n) \\subset S_k(A)$ should have read $S_{k, L(n)}(A_n) \\subset S_k(A_n)$, which holds since all signals considered in $S_{k, L(n)}$ are also considered in $S_k$, and concludes the other containment direction.\n\nMinor issues:\n- M6: We cited a wrong version of Ruiz et al. 2020: their IEEE TSP submission ‘Transferability properties of GNN’ has this $O(n^{-1})$ bound. It is unclear how sparse the graphs their new ‘sparse’ model ('GNN for Community Detection on Sparse Graphs') generates but personal communications and our current inspection suggests that their model is close to graphons. We will discuss this in the paper.\n- M8: We are referring to their Lipschitz assumption, which directly implies good approximation of a continuous GCN signal by a discrete sampled graph signal.\n- M10: Going by our definition of sparse graphs, graphon’s cut metric cannot distinguish them from the 0 graphon and thus only contains trivial limits (the 0 graphon) of such sparse graph sequence.\n- M11: Positiveness refers to positive-definite operators where $\\langle Ax,x \\rangle > 0$ for all $x$ in Dom(A).\n- M12: We do not see any immediate obstacle to this generalization.\n- M13: See line 109.\n- M14: $d_M$ only relies on $(k,C_v)$-profiles. For nonlinear operators one can still couple each signal with its image under the operator to define the profiles.\n- M15: The **image** of the operator is only required to be measurable and can be very discontinuous.\n- M16: Assumption 3A/B come with a resolution set that contains the possible sizes of our discretization. Outside of this set, the assumptions do not need to hold.\n- M17: ‘with high probability’ should be deleted.\n- M18: This means that 1. The sequence converges in both the B-S notion and our notion; and 2. The limits are the same.\n- M19: See Line 726 and 808. One can prove $\\max_x F(x) \\leq M$ by proving $F(x) < M$ for arbitrary $x$.\n- M20: We are bounding $d_{LP}$ directly via its definition (see line 494), and thus want to find an $\\epsilon > 0$ such that the condition in the definition of $d_{LP}$ is satisfied.\n- M21: See Line 495.\n- M22: ${\\bar{\\mathcal{E}}}_{j,A}$ is a typo for ${{\\mathcal{E}}^1}\\_{j,A}$.\n- M23: $f’’$ is Lipschitz in the induced metric on the subspace $1/n [n] \\subset [0,1]$ equipped with the Euclidean metric.\n- M24: The bar indicates closure of a set (of distributions) in the weak convergence sense and the limit is taken as n goes to infinity (the existence of such limit is due to existence of $\\lim_n S_k(A_n)$ as shown in B-S and the fact that  $S_{k, L(n)}(A_n)$ converges to $S_k(A_n)$ set-wise).\n"}]

Author rebuttal:
We thank the reviewers for their feedback and would like to emphasize: 
1. Our work establishes quantitative, non-asymptotic transferability bounds for a wide range of sparse graphs, which are notoriously hard to analyze. Please refer to Table 1 in the additional rebuttal pdf file for a concise comparison to related works. This will be in the final version of the paper.
2. Sparse graphs are notoriously difficult to analyze:
- Regularity assumptions are likely necessary: Although some of our assumptions (3A and 3B) seem restrictive, only one of them needs to hold for the results to go through. Furthermore, an unconditional proof of our Theorem 2 would solve the Aldous-Lyon conjecture for bounded-degree graph limits. While this does not prove such a result is impossible, we want to point out that graphops convergence is intricate and nontrivial to analyze.
- Pathological behavior of graph spectrum in the limit: It is well known that for many bounded-degree graph sequences, eigengaps do not converge and that eigenvalues and eigenvectors may not even exist for limiting operators.  Therefore, these sequences are not amenable to spectral methods that use eigenvalue/eigengap convergence. (e.g. Levie et. al, 2021)
3. Sparse graphs and bounded-degree graphs are more realistic in real-world models. See Table 1 for examples that satisfy our assumptions. We have recently verified that polymer graphs (refer to Figure 1 in the additional rebuttal pdf for an illustration of this graph), which model the repetitive structure of polymer molecules, satisfy our assumptions. Unlike other example graphs in the paper, polymer graphs are not necessarily regular graphs. 
4. Deterministic vs random graph: at the time of writing, we considered these two distinct approaches to size transferability. While random graph models are more flexible and usually have stronger results and wider tools for analysis, results for random graph models usually only hold with high probability. In comparison, deterministic graph sampling is more suitable if there is already a deterministic sequence of graphs one has in mind (for example, images of certain resolutions) and wants to compute transferability bounds between them. Results for deterministic graph sequences must also hold in the worst case since there is no randomness to downplay the probability of sampling these graphs. However, seeing that the techniques in both approaches are similar in existing literature, in the final version of the paper, we will include a more thorough discussion of random graph models. 
5. Experiments: Comprehensive empirical studies of transferability on sparse graphs have already been done extensively in the literature, especially since sparse graphs are more common in real-world datasets than dense ones. We will add proof-of-concept experiments that verify some of our results in the final version of the paper.  
6. Implication for future empirical and theoretical work: Since our approach to analyzing very sparse graphs is very new, there are lots of exciting avenues to consider in the future, both in practice and in theory. By introducing P-operators, graphops, and the accompanying metric (with our relaxation to $(k, L)$-profiles for easier use), we contribute to the toolbox of techniques used to analyze and compare GNNs of different graph sizes. This may have impacts on other aspects of GNNs, such as expressiveness (universality theorems under this metric) or proving new generalization bounds beyond size transferability. As our results apply to a much wider range of graph sequences than previous ones, they may also serve as a unifying framework for future studies. From an empirical standpoint, our results ensure size transferability under appropriate structural assumptions (they are sampled from the same regular graphop) between two graphs. Testing how robust size transferability is to failure of such structural assumptions will help practitioners predict transferability and non-transferability of sparse graph sequences. Finally, the connection between sparse graph convergence and weak convergence of distributions is yet another rich future direction. These two concepts are tied together since the $d_M$ metric is built on top of Levy-Prokorov distance ($d_{LP}$), which metrizes weak convergence and most of the proofs boil down to bounding $d_{LP}$. This connection may allow techniques used in optimal transport or Wasserstein distance computation to benefit this line of work. More directly related to this work, generalizing our results to higher dimensional node features appears to be straightforward. Further relaxing Assumptions 3A and 3B is also interesting and would greatly improve this approach. 
7. Graph generation via P-operators: The discretization scheme introduced for graphop can be roughly understood as partitioning the vertex set into finitely many sets and merging nodes and their connections in these sets, with an appropriate scaling of the edge weights. Imagine blurring an n by n matrix into an  n/2 x n/2 matrix by doing some form of average pooling over each distinct 2x2 square. This makes rigorous the notion of making a high-resolution graph on a huge number of vertices more ‘blurry’ by merging nodes in a way that still maintains some smoothness conditions of Assumptions 3A/3B, which is reminiscent of the real-world procedures of training with low-resolution images before fine-tuning with higher-resolution ones, or sampling from low-frequency graph Fourier transform domain. We will clarify these intuitions in the final version of the paper.

Finally, we note that all citations that appear in our rebuttals can be found in the reference section of the current version of the paper, except that Ruiz et. al, 2020 now refers to their IEEE TSP submission ‘Transferability properties of GNN’ available on arXiv. 


Meta-review: This paper is a study of transferability of GNN with graphops. It was overall well received by the reviewers except that the lack of real world examples was considered as an important issue of the paper. I believe there is some truth in this comment, but the theoretical contributions are sound, and are worthy of a NeurIPS publication.

Please incorporate the remaining reviewers' feedback for the camera-ready version.
Decision: Accept (poster)