# Geometric Graph Filters and Neural Networks:
Limit Properties and Discriminability Trade-offs

Zhiyang Wang Luana Ruiz Alejandro Ribeiro Supported by NSF-Simons MoDL, NSF AI
Institutes program and NSF HDR TRipods. ZW, AR are with the Department of
Electrical and Systems Engineering, University of Pennsylvania, PA, email:
{zhiyangw<EMAIL_ADDRESS>LR is with the Computer Science &
Artificial Intelligence Laboratory at MIT, MA, and is supported by FODSI and
METEOR, email<EMAIL_ADDRESS>Preliminary results presented in [1] and [2].

###### Abstract

This paper studies the relationship between a graph neural network (GNN) and a
manifold neural network (MNN) when the graph is constructed from a set of
points sampled from the manifold, thus encoding geometric information. We
consider convolutional MNNs and GNNs where the manifold and the graph
convolutions are respectively defined in terms of the Laplace-Beltrami
operator and the graph Laplacian. Using the appropriate kernels, we analyze
both dense and moderately sparse graphs. We prove non-asymptotic error bounds
showing that convolutional filters and neural networks on these graphs
converge to convolutional filters and neural networks on the continuous
manifold. As a byproduct of this analysis, we observe an important trade-off
between the discriminability of graph filters and their ability to approximate
the desired behavior of manifold filters. We then discuss how this trade-off
is ameliorated in neural networks due to the frequency mixing property of
nonlinearities. We further derive a transferability corollary for geometric
graphs sampled from the same manifold. We validate our results numerically on
a navigation control problem and a point cloud classification task.

###### Index Terms:

Graph Neural Networks, Manifold Filters, Manifold Neural Networks, Convergence
Analysis, Discriminability

##  I Introduction

Geometric data, or data supported in non-Euclidean domains, is the object of
much interest in modern information processing. It arises in a number of
applications, including protein function prediction [3, 4], robot path
planning [5, 6], 3D shape analysis [7, 8, 9] and wireless resource allocation
[10, 11]. Graph convolutional filters [12, 13] and graph neural networks
(GNNs) [14, 15], along with manifold convolutional filters [16] and manifold
neural networks (MNNs) [17, 18, 19], are the standard tools for invariant
information processing on these domains when they are discrete and continuous
respectively. The convolution operation is implemented through information
diffusion over the geometric structure, thus enabling invariant and stable
representations [20, 21, 22, 23] and feature sharing. The cascading neural
network architecture interleaves convolutions and nonlinearities, further
expanding the model’s expressiveness.

Although there is a clear parallel between graphs and manifolds—the former can
be seen as discretizations of the latter—, manifolds are infinite-dimensional
continuous latent spaces which can only be accessed by discrete point sampling
[7, 24, 25, 26]. In general, we have access to a set of sampling points from
the manifold, and build a graph model to approximate the underlying continuous
manifold while attempting to retain the local and global geometric structure
[27, 7, 11]. GNNs have been shown to do well at processing information over
the manifold both experimentally and theoretically [25, 16, 28]. Of particular
note, conditions that guarantee asymptotic convergence of graph filters and
GNNs to manifold filters and MNNs are known [16].

Asymptotic convergence is a minimal guarantee that can be enriched with non-
asymptotic approximation error bounds. These bounds are unknown and they are
the focus of this paper. These non-asymptotic approximation error bounds
relating graph filters and GNNs to manifold filters and MNNs are important
because they inform the practical design on graphs of information processing
architectures that we want to deploy on manifolds. In addition, explicit
finite-sample error bounds often reveal details about the convergence regime
(e.g., rates of convergence and discriminability trade-offs) that are not
revealed by their asymptotic counterparts. For example, the non-asymptotic
convergence analysis of GNNs on graphs sampled from a graphon (also referred
to as a transferability analysis) gives a more precise characterization of the
discriminability-convergence tradeoff that arises in these GNNs [29], which is
not elucidated by the corresponding asymptotic convergence result [30].

Contributions. In this paper, we prove and analyze a non-asymptotic
approximation error bound for GNNs on graphs sampled from manifold, thus
closing the gap between GNNs and MNNs with an explicit numerical relationship.
We start by importing the definition of the manifold filter as a convolutional
operation where the diffusions are exponentials of the Laplace-Beltrami (LB)
operator ${\mathcal{L}}$ of the manifold
${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ [16]. Given a set of discrete
sampling points from the manifold, we describe how to construct both dense and
relatively sparse geometric graphs that approximate the underlying manifold in
both the spatial and the spectral domains.

Next, we import the concept of Frequency Difference Threshold (FDT) filters
(Definition 3) [17] to overcome the challenge of dimensionality associated
with the infinite-dimensional spectrum of the LB operator. We show that
manifold filters exhibit a trade-off between their discriminability and their
ability to be approximated by graph filters, which can be observed in the
approximation error bound of geometric graph filters in Theorems 1 and 2.

The same analysis is conducted for GNNs by incorporating nonlinearities
(Theorem 3), but in GNNs we hypothesize that the trade-off is alleviated,
i.e., that we can recover discriminability, through the addition of these
nonlinear operations (Section V). In other words, geometric GNNs can be both
discriminative and approximative of the underlying MNNs, which we verify
empirically through numerical experiments (Section VI). Finally, we show how
our approximation result can be extended, by a triangle inequality argument,
to a transferability result for geometric GNNs transferred across geometric
graphs of different sizes sampled from the same underlying manifold.

Related Works. GNNs have been thoroughly studied and discussed in a number of
previous works [15, 31, 14]. Similarly, the convergence and transferability of
neural networks on graphs have been studied in many works including [32, 21,
33, 29]. These works however see the graphs as samples from a graphon model.
In our paper, we focus on the manifold as the limit model for large-scale
graphs, which is more realistic than graphons as it can incorporate the
underlying geometric information. Moreover, the manifold can also represent
the limit of sparse or relatively sparse graphs. Very relevant to this paper,
the spectral convergence of relatively sparse graphs sampled from manifolds
has been studied at length in [34].

Manifold filters and manifold neural networks have been established and
discussed in [16, 17, 18, 24] using different features and metrics. The
integral of the heat diffusion process is employed in [16, 17] where it is
shown that manifold convolutions are consistent with and can recover both the
graph convolution and the time convolution. In [18], a local geodesic system
capturing local anisotropic structures is used to define the manifold
convolution. Taking a different approach, [24] defines a mixture Gaussian
kernel over the spatial domain using patch operator that is constructed
locally.

Among all these methods, the definition leveraging the heat diffusion process
is the only one to build the connection between graph neural networks and
manifold neural networks when the graphs are sampled from the manifold [16].
However, this paper does not provide an explicit convergence rate or
approximation error bound between GNNs and MNNs. In [35], a convergence rate
is given for GNNs approximating MNNs, but the result is restricted to input
signals with a limited bandwidth. Moreover, the graphs constructed in [16] and
[35] still need to be dense with a well-defined Gaussian kernel. In contrast,
in this paper we extend the analysis of the convergence of GNNs by proving a
non-asymptotic approximation error bound for geometric GNNs sampled from the
MNNs where the geometric graphs are either dense or relatively sparse; and we
eliminate the bandlimited signal assumption by importing frequency-dependent
filters.

Organization. Section II introduces preliminary definitions of graph signal
processing and graph neural networks along with manifold signal processing and
manifold neural networks. Section III introduces the construction of the
geometric graphs from the sampling points of the manifold and the convergence
of the geometric graph Laplacians. We show the spectrum of the geometric
graphs – both dense and relatively sparse – can approximate the spectrum of
the LB operator of the underlying manifold with a bounded error. We then go on
to study the approximation of the filtering on the geometric graphs which is
further extended to the approximation of geometric GNNs to MNNs in Section IV.
Section V discusses the implications of the results derived in Section IV.
Section VI illustrates the results of Sections IV with numerical examples.
Section VII concludes the paper. Proofs are deferred to the appendices and
supplementary materials.

##  II Preliminary Definitions

We start by reviewing the basic architecture of graph neural networks and
manifold neural networks.

###  II-A Graph Signal Processing and Graph Neural Networks

Let ${\mathbf{G}}=({\mathcal{V}},{\mathcal{E}},{\mathcal{W}})$ be an
undirected graph with node set ${\mathcal{V}},|{\mathcal{V}}|=n$, and edge set
${\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$. The edges in
${\mathcal{E}}$ may be weighted, in which case the edge weights are assigned
by a function ${\mathcal{W}}:{\mathcal{E}}\rightarrow{\mathbb{R}}$. In this
paper, we are interested in graph signals ${\mathbf{x}}\in{\mathbb{R}}^{n}$
supported on the nodes. For $1\leq i\leq n$, $[{\mathbf{x}}]_{i}$ represents
the value of the signal at node $i$.

Graph shift. Operating on graph signals ${\mathbf{x}}$, we define the graph
shift operator (GSO) ${\mathbf{S}}\in{\mathbb{R}}^{n\times n}$. The GSO is any
matrix satisfying $[{\mathbf{S}}]_{ij}\neq 0$ if and only if
$(i,j)\in{\mathcal{E}}$ or $i=j$, e.g., the adjacency matrix ${\mathbf{A}}$,
$[{\mathbf{A}}]_{ij}={\mathcal{W}}(i,j)$, or the graph Laplacian
${\mathbf{L}}=\mbox{diag}({\mathbf{A}}\boldsymbol{1})-{\mathbf{A}}$ [13, 36].
The GSO is so called because, at each node $i$, it has the effect of shifting
or diffusing the signal values at $i$’s neighbors to $i$, where signal values
are aggregated. Explicitly,
$[{\mathbf{S}}{\mathbf{x}}]_{i}=\sum_{j,(i,j)\in{\mathcal{E}}}[{\mathbf{S}}]_{ij}[{\mathbf{x}}]_{j}$.
In the case of an undirected graph, the GSO is symmetric and can therefore be
decomposed as ${\mathbf{S}}={\mathbf{V}}\bm{\Lambda}{\mathbf{V}}^{H}$. The
eigenvalues in the diagonal matrix $\bm{\Lambda}$ are seen as graph
frequencies, and the eigenvectors in ${\mathbf{V}}$ are the corresponding
graph oscillation modes.

Graph convolution. A graph convolution is defined based on the graph diffusion
process with $K_{t}-1$ consecutive shifts. More formally, the graph
convolutional filter [15, 13, 37] with coefficients
$\\{h_{k}\\}_{k=0}^{K_{t}-1}$ is given by

${\mathbf{h}}_{\mathbf{G}}({\mathbf{S}}){\mathbf{x}}=\sum_{k=0}^{K_{t}-1}h_{k}{\mathbf{S}}^{k}{\mathbf{x}}.$
(1)

Plugging the spectral decomposition of ${\mathbf{S}}$ into (1), we see that in
the spectral domain this filter can be represented as

${\mathbf{V}}^{H}{\mathbf{h}}_{\mathbf{G}}({\mathbf{S}}){\mathbf{x}}=\sum_{k=1}^{K_{t}-1}h_{k}\bm{\Lambda}^{k}{\mathbf{V}}^{H}{\mathbf{x}}=h(\bm{\Lambda}){\mathbf{V}}^{H}{\mathbf{x}}.$
(2)

Hence, the graph frequency response of the graph convolution is given by
$h(\lambda)=\sum_{k=0}^{K_{t}-1}h_{k}\lambda^{k}$, which only depends on the
weights $h_{k}$ and on the eigenvalues of ${\mathbf{S}}$.

Graph neural network. A graph neural network (GNN) is built by cascading
layers that each consists of a bank of filters followed by a point-wise
nonlinearity $\sigma:{\mathbb{R}}\to{\mathbb{R}}$,
$[\sigma({\mathbf{x}})]_{i}=\sigma([{\mathbf{x}}]_{i})$. The $l$th layer of a
GNN produces $F_{l}$ signals ${\mathbf{x}}_{l}^{p}$, each called a feature,
given by

${\mathbf{x}}_{l}^{p}=\sigma\left(\sum_{q=1}^{F_{l-1}}{\mathbf{h}}_{\mathbf{G}}^{lpq}({\mathbf{S}}){\mathbf{x}}^{q}_{l-1}\right),$
(3)

for $1\leq p\leq F_{l}$. At each layer $l=1,2\ldots,L$, the number of input
and output features are $F_{l-1}$ and $F_{l}$ respectively. The filter
${\mathbf{h}}_{\mathbf{G}}^{lpq}({\mathbf{S}})$ is as in (1) and maps the
$q$-th feature of layer $l-1$ to the $p$-th feature of layer $l$. For
simplicity, we write the GNN consisting of $L$ layers like (3) as the map
$\bm{\Phi}_{\mathbf{G}}({\mathbf{H}},{\mathbf{S}},{\mathbf{x}})$, where
${\mathbf{H}}$ denotes a set of the graph filter coefficients at all layers.

###  II-B Manifold Signal Processing and Manifold Neural Networks

Let ${\mathcal{M}}$ be a $d$-dimensional embedded manifold in
${\mathbb{R}}^{\mathsf{N}}$. For simplicity, in this paper whenever we mention
the manifold ${\mathcal{M}}$, we assume that it is a compact, smooth and
differentiable $d$-dimensional submanifold embedded in
${\mathbb{R}}^{\mathsf{N}}$. Atop ${\mathcal{M}}$, signals are defined as
scalar functions $f:{\mathcal{M}}\rightarrow{\mathbb{R}}$ called manifold
signals [23]. The inner product of signals $f,g\in L^{2}({\mathcal{M}})$ is
defined as

$\langle f,g\rangle_{{\mathcal{M}}}=\int_{\mathcal{M}}f(x)g(x)\text{d}\mu(x),$
(4)

where $\text{d}\mu(x)$ is the volume element with respect to the measure $\mu$
over ${\mathcal{M}}$. Similarly, the norm of the manifold signal $f$ is

$\|f\|^{2}_{{\mathcal{M}}}={\langle f,f\rangle_{{\mathcal{M}}}}.$ (5)

Manifold shift. The manifold ${\mathcal{M}}$ is locally Euclidean, and the
local homeomorphic Euclidean space around each point $x\in{\mathcal{M}}$ is
defined as the tangent space $T_{x}{\mathcal{M}}$. The disjoint union of all
tangent spaces over ${\mathcal{M}}$ is called the tangent bundle and denoted
$T{\mathcal{M}}$. The _intrinsic gradient_
$\nabla:L^{2}({\mathcal{M}})\rightarrow L^{2}(T{\mathcal{M}})$ is the
differentiation operator and maps scalar functions to tangent vector functions
over ${\mathcal{M}}$ [25, 38]. The adjoint of $\nabla$ is the _intrinsic
divergence_ , which is defined as $\text{div}:L^{2}(T{\mathcal{M}})\rightarrow
L^{2}({\mathcal{M}})$. The Laplace-Beltrami (LB) operator
${\mathcal{L}}:L^{2}({\mathcal{M}})\to L^{2}({\mathcal{M}})$ is defined as the
intrinsic divergence of the intrinsic gradient [39]. Formally, the operation
is written as

${\mathcal{L}}f=-\text{div}\circ\nabla f.$ (6)

This operator measures the difference between the signal value at a point and
the average signal value in the point’s neighborhood [25]. This is akin to how
the graph Laplacian matrix can be used to compute the total variation of a
graph signal [40].

On manifolds, the shift operation is defined based on the LB operator and on
the solution to the heat equation (see [23] for a detailed exposition).
Explicitly, for a manifold signal $f$ the manifold shift is written as
$e^{-\text{d}t{\mathcal{L}}}f$. Since the LB operator is self-adjoint and
positive-semidefinite and the manifold ${\mathcal{M}}$ is compact,
${\mathcal{L}}$ has real, positive and discrete eigenvalues
$\\{\lambda_{i}\\}_{i=1}^{\infty}$, which can be written as

${\mathcal{L}}\bm{\phi}_{i}=\lambda_{i}\bm{\phi}_{i},$ (7)

where $\bm{\phi}_{i}$ is the eigenfunction associated with eigenvalue
$\lambda_{i}$. The eigenvalues, or manifold frequencies, are ordered in
increasing order as $0<\lambda_{1}\leq\lambda_{2}\leq\lambda_{3}\leq\ldots$,
and the eigenfunctions, or manifold oscillation modes, are orthonormal and
form an eigenbasis of $L^{2}({\mathcal{M}})$ in the intrinsic sense. The
$\phi_{i}$ are also eigenfunctions of the shift operator
$e^{-\text{d}t{\mathcal{L}}}$, with corresponding eigenvalues
$e^{-\text{d}t\lambda_{i}}$.

Manifold convolution. Integrating $e^{-\text{d}t{\mathcal{L}}}f$ over
$[0,\infty)$ yields the infinite-horizon diffusion process

$g(x)=\int_{0}^{\infty}e^{-t{\mathcal{L}}}f(x)\text{d}t\text{.}$ (8)

Let ${\tilde{h}}:{\mathbb{R}}^{+}\to{\mathbb{R}}$ denote the filter impulse
response. Based on this diffusion process,a manifold filter can be defined via
the manifold convolution [23],

$\displaystyle
g(x)={\mathbf{h}}f(x):=\int_{0}^{\infty}{\tilde{h}}(t)e^{-t{\mathcal{L}}}f(x)\text{d}t={\mathbf{h}}({\mathcal{L}})f(x)\text{.}$
(9)

Note that the map ${\mathbf{h}}:={\mathbf{h}}({\mathcal{L}})$ is parametric on
the LB operator, and is a spatial map acting directly on $x\in{\mathcal{M}}$.

If we write $[\hat{f}]_{i}=\langle
f,\bm{\phi}_{i}\rangle_{L^{2}({\mathcal{M}})}=\int_{{\mathcal{M}}}f(x)\bm{\phi}_{i}(x)\text{d}\mu(x)$,
the manifold convolution can be represented in the manifold frequency domain
as

$\displaystyle[\hat{g}]_{i}=\int_{0}^{\infty}{\tilde{h}}(t)e^{-t\lambda_{i}}\text{d}t[\hat{f}]_{i}\text{.}$
(10)

Hence, the frequency response of the filter ${\mathbf{h}}({\mathcal{L}})$ is
given by
$\hat{h}(\lambda)=\int_{0}^{\infty}{\tilde{h}}(t)e^{-t\lambda}\text{d}t$,
which only depends on the impulse response $\tilde{h}$ and the LB eigenvalues
$\lambda=\lambda_{i}$. Further summing over all $i$ and projecting back onto
the spatial domain, we can alternatively represent
${\mathbf{h}}({\mathcal{L}})$ as

$g={\mathbf{h}}({\mathcal{L}})f=\sum_{i=1}^{\infty}\hat{h}(\lambda_{i})[\hat{f}]_{i}\bm{\phi}_{i}.$
(11)

Manifold neural network. Similarly to the GNN, we can define the manifold
neural network (MNN) as a cascade of layers $l=1,2\ldots,L$ each of which
consists of a bank of manifold filters and a pointwise nonlinearity
$\sigma:{\mathbb{R}}\to{\mathbb{R}}$. Layer $l$ is explicitly written as

$f_{l}^{p}(x)=\sigma\left(\sum_{q=1}^{F_{l-1}}{\mathbf{h}}_{l}^{pq}({\mathcal{L}})f_{l-1}^{q}(x)\right),$
(12)

where each signal $f_{l}^{p}$, $1\leq p\leq F_{l}$ is a different feature.
Each layer $l$ maps $F_{l-1}$ input features to $F_{l}$ output features. For a
more succinct representation, in the following the MNN will be denoted
$\boldsymbol{\Phi}({\mathbf{H}},{\mathcal{L}},f)$, where ${\mathbf{H}}$ is a
function set gathering the impulse responses of the manifold filters
${\mathbf{h}}_{l}^{pq}$ for all features and all layers.

##  III Geometric Graphs and Laplacian Convergence

Given discrete set of points sampled from the manifold ${\mathcal{M}}$, we can
construct a discrete approximation of ${\mathcal{M}}$ by connecting the sample
points by means of a graph. The nodes of the graph are the sample points, and
the edges (more specifically, their weights) are defined as some function of
the Euclidean distance between each node pair to encode geometric information
from the manifold. We henceforth refer to graphs carrying topological manifold
information as _geometric graphs_ , which is slightly different from the graph
theory definition that focuses on the geometric properties of the edges of the
graph [41].

Let $X$ be a set of $n$ points $\smash{\\{x_{1},x_{2},\ldots,x_{n}\\}}$
sampled i.i.d. from the manifold ${\mathcal{M}}$ according to measure $\mu$.
The discrete empirical measure associated with these points is defined as
$p_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}$, where $\delta_{x_{i}}$
represents the Dirac measure at $x_{i}$. For signals $u,v\in
L^{2}({\mathcal{M}})$, the inner product associated with measure $p_{n}$ is
defined as

$\langle u,v\rangle_{L^{2}({\mathbf{G}}_{n})}=\int
u(x)v(x)\text{d}p_{n}=\frac{1}{n}\sum_{i=1}^{n}u(x_{i})v(x_{i})$ (13)

and so the norm in $L^{2}({\mathbf{G}}_{n})$ is

$\|u\|^{2}_{L^{2}({\mathbf{G}}_{n})}=\langle
u,u\rangle_{L^{2}({\mathbf{G}}_{n})}.$

For signals ${\mathbf{u}},{\mathbf{v}}\in L^{2}({\mathbf{G}}_{n})$, the inner
product is

$\langle{\mathbf{u}},{\mathbf{v}}\rangle_{L^{2}({\mathbf{G}}_{n})}=\frac{1}{n}\sum_{i=1}^{n}[{\mathbf{u}}]_{i}[{\mathbf{v}}]_{i}$

and the norm is
$\smash{\|{\mathbf{u}}\|_{L_{2}({\mathbf{G}}_{n})}=\langle{\mathbf{u}},{\mathbf{u}}\rangle_{L^{2}({\mathbf{G}}_{n})}}$.

We construct an undirected geometric graph ${\mathbf{G}}_{n}$ from the sampled
points $X$ by seeing each point as a vertex. Every pair of vertices is
connected by edges with weight values determined by a function $K_{\epsilon}$
of their Euclidean distance. Explicitly, the weight of edge $(i,j)$, denoted
$w_{ij}$, is given by

$w_{ij}=K_{\epsilon}\left(\frac{\|x_{i}-x_{j}\|^{2}}{\epsilon}\right),$ (14)

where $\|x_{i}-x_{j}\|$ is the Euclidean distance between $x_{i}$ and $x_{j}$.
The geometric adjacency matrix ${\mathbf{A}}_{n}^{\epsilon}$ and the geometric
graph Laplacian ${\mathbf{L}}_{n}^{\epsilon}$ can therefore be expressed as
$[{\mathbf{A}}_{n}^{\epsilon}]_{ij}=w_{ij}$ for $1\leq i,j\leq n$ and
${\mathbf{L}}^{\epsilon}_{n}=\mbox{diag}({\mathbf{A}}_{n}^{\epsilon}\boldsymbol{1})-{\mathbf{A}}_{n}^{\epsilon}$
[42].

Since it is constructed from points $x_{i}\in{\mathcal{M}}$, the geometric
graph can be seen as a discrete approximation, or discretization, of the
manifold. To analogously obtain the discretization of a manifold signal $f\in
L^{2}({\mathcal{M}})$ on this graph, as well as the reconstruction from the
graph signal back to the manifold signal, we define a uniform sampling
operator ${\mathbf{P}}_{n}:L^{2}({\mathcal{M}})\rightarrow
L^{2}({\mathbf{G}}_{n})$ and an interpolation operator
${\mathbf{I}}_{n}:L^{2}({\mathbf{G}}_{n})\rightarrow L^{2}({\mathcal{M}})$.
The application of the operator ${\mathbf{P}}_{n}$ to $f$ yields the geometric
graph signal

${\mathbf{f}}={\mathbf{P}}_{n}f\text{ with }{\mathbf{f}}(x_{i})=f(x_{i}),\quad
x_{i}\in X\text{.}$ (15)

I.e., ${\mathbf{f}}$ is a signal on the graph ${\mathbf{G}}_{n}$ sharing the
values of the manifold signal $f$ at the sampled points $X$.

We put certain restrictions on the sampling and interpolation operators as
follows [43].

###### Definition 1

We call the sampling and interpolation operators ${\mathbf{P}}_{n}$ and
${\mathbf{I}}_{n}$ _asymptotically reconstructive_ if for any manifold signal
$f\in L^{2}({\mathcal{M}})$, it holds

$\lim_{n\rightarrow\infty}{\mathbf{I}}_{n}{\mathbf{P}}_{n}f=f.$ (16)

Moreover, the sampling and interpolation operators ${\mathbf{P}}_{n}$ and
${\mathbf{I}}_{n}$ are bounded if there exists a constant $D$ such that

$\limsup_{n\in\mathbb{N}}{\|{\mathbf{P}}_{n}\|\ }\leq
D,\quad\limsup_{n\in\mathbb{N}}{\|{\mathbf{I}}_{n}\|\ }\leq D.$ (17)

Seeing the geometric graph Laplacian ${\mathbf{L}}^{\epsilon}_{n}$ as an
operator acting on ${\mathbf{f}}:X\to{\mathbb{R}}$, we can write the diffusion
operation at each point $x_{i}$ explicitly as

${\mathbf{L}}^{\epsilon}_{n}{\mathbf{f}}(x_{i})=\sum_{j=1}^{n}K_{\epsilon}\left(\frac{\|x_{i}-x_{j}\|^{2}}{\epsilon}\right)\left({\mathbf{f}}(x_{i})-{\mathbf{f}}(x_{j})\right)$
(18)

for $i=1,2,\ldots,n$. This operation can be further lifted to continuous
manifold signals $f$ as

${\mathbf{L}}^{\epsilon}_{n}f(x)=\sum_{j=1}^{n}K_{\epsilon}\left(\frac{\|x-x_{j}\|^{2}}{\epsilon}\right)\left(f(x)-f(x_{j})\right)$
(19)

where $x\in{\mathcal{M}}$. If we additionally extend the set of sampled points
from $X$ to all of the manifold ${\mathcal{M}}$, we obtain the functional
approximation of the geometric graph Laplacian

${\mathbf{L}}^{\epsilon}f(x)=\int_{\mathcal{M}}K_{\epsilon}\left(\frac{\|x-y\|^{2}}{\epsilon}\right)\left(f(x)-f(y)\right)\text{d}\mu(y)\text{.}$
(20)

The definition of the weight function $K_{\epsilon}$ allows the construction
of geometric graphs with different levels of sparsity. With different choices
of $K_{\epsilon}$ (i.e., whether $K_{\epsilon}$ has a bounded support, the
relationship between $\epsilon$ and the number of sampling nodes $n$, etc.),
the graphs can be sparse (average node degree $\Theta(1)$), relatively sparse
(average node degree $\Theta(\log n)$) or dense (average node degree
$\Theta(n)$). In the following, we will focus on two kernel definitions that
allow constructing dense and relatively sparse geometric graphs.

###  III-A Laplacian Convergence: Dense Graphs

Dense geometric graphs can be constructed when pairs of points $x_{i}$ and
$x_{j}$ are connected with a weight function $K_{\epsilon}$ defined on an
unbounded support (i.e. $[0,\infty)$), which connects $x_{i}$ and $x_{j}$
regardless of the distance between them, but often with the edge weight
inversely proportional to this distance. This results in a dense geometric
graph with $n^{2}$ edges. In particular, the Gaussian kernel has been widely
used to define the weight value function due to the good approximation
properties of the corrresponding graph Laplacians vis-à-vis the Laplace-
Beltrami operator [44, 45]. In the Gaussian case, the weight function
$K_{\epsilon}$ is computed explicitly as

$K_{\epsilon}\left(\frac{\|x-y\|^{2}}{\epsilon}\right)=\frac{1}{n}\frac{1}{\epsilon^{d/2+1}(4\pi)^{d/2}}e^{-\frac{\|x-y\|^{2}}{4\epsilon}},$
(21)

with $d$ representing the dimension of the manifold. The consistency of the
geometric graph Laplacian constructed with this Gaussian kernel is ensured by
a non-asymptotic error bound. Explicitly, the following result quantifies the
approximation of the dense geometric graph Laplacian in the weak sense.

###### Proposition 1

Let ${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ be equipped with LB
operator ${\mathcal{L}}$, whose eigendecomposition is given by (7). Let
${\mathbf{G}}_{n}$ be a dense geometric graph constructed from $n$ points
sampled u.i.d. from ${\mathcal{M}}$ with the edge weights defined as (14) and
(21), $\epsilon=\epsilon(n)>n^{-1/(d+4)}$. Then, with probability at least
$1-\delta$, the following holds

$|{\mathbf{L}}_{n}^{\epsilon}\bm{\phi}_{i}(x)-{\mathcal{L}}\bm{\phi}_{i}(x)|\leq\left(C_{1}\sqrt{\frac{\ln(1/\delta)}{2n\epsilon^{d+2}}}+C_{2}\sqrt{\epsilon}\right)\lambda_{i}^{\frac{d+2}{4}}\text{.}$
(22)

The constants $C_{1}$, $C_{2}$ depend on the volume of the manifold and are
defined in Appendix B-A.

###### Proof.

See Section B-A in supplemental materials. ∎

We can see that the quality of the approximation of ${\mathcal{L}}$ by
${\mathbf{L}}^{\epsilon}_{n}$ relates not only to the number of sampling
points $n$ but also grows with the corresponding eigenvalue $\lambda_{i}$.
This can be interpreted to mean that eigenfunctions associated with
eigenvalues oscillates faster [46].

Based on this approximation result and using the Davis-Kahan theorem [47], we
can further derive a non-asymptotic approximation bound relating the spectra
of the dense geometric graph Laplacian and of the LB operator.

###### Proposition 2

Let ${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ be equipped with LB
operator ${\mathcal{L}}$, whose eigendecomposition is given by (7). Let
${\mathbf{L}}_{n}^{\epsilon}$ be the discrete graph Laplacian of the dense
geometric graph ${\mathbf{G}}_{n}$ defined as in (19) and (21), with spectrum
given by
$\\{\lambda_{i,n}^{\epsilon},\bm{\phi}_{i,n}^{\epsilon}\\}_{i=1}^{n}$. Fix
$K\in\mathbb{N}^{+}$ and $\epsilon=\epsilon(n)>n^{-1/(d+4)}$. Then, with
probability at least $1-e^{-2n\epsilon^{d+3}}$, we have

$|\lambda_{i}-\lambda_{i,n}^{\epsilon}|\leq\Omega_{1,K}\sqrt{\epsilon},\quad\|a_{i}\bm{\phi}_{i,n}^{\epsilon}-\bm{\phi}_{i}\|\leq\Omega_{2,K}\sqrt{\epsilon}/\theta,$
(23)

with $a_{i}\in\\{-1,1\\}$ for all $i<K$ and $\theta$ the eigengap of
${\mathcal{L}}$, i.e., $\theta=\min_{1\leq i\leq
K}\\{\lambda_{i}-\lambda_{i-1},\lambda_{i+1}-\lambda_{i}\\}$. The constants
$\Omega_{1,K}$, $\Omega_{2,K}$ depend on $\lambda_{K}$, $d$ and the volume of
${\mathcal{M}}$.

###### Proof.

See Section B-B in supplemental materials. ∎

Looking at Proposition 2, we can see that the element-wise non-asymptotic
convergence of the eigenvalues and eigenfunctions is only guaranteed in a
limited part of the spectrum ($i<K$), and that the upper bound is related to
the upper limit $\lambda_{K}$. This can be interpreted to mean that as
eigenfunctions in the high frequency domain oscillate faster, they are harder
to approximate. Therefore, when designing filters, we need to be especially
careful when trying to discriminate components in the high frequency domain.

###  III-B Laplacian Convergence: Relatively Sparse Graphs

We can construct relatively sparse graphs by setting the weight function
$K_{\epsilon}$ with a bounded support, i.e., only nodes that are within a
certain distance of one another can be connected by an edge. We consider the
following weight function from [34], which has been shown to provide a good
approximation of the LB operator,

$K_{\epsilon}\left(\frac{\|x-y\|^{2}}{\epsilon}\right)=\frac{1}{n}\frac{d+2}{\epsilon^{d/2+1}\alpha_{d}}\mathbbm{1}_{[0,1]}\left(\frac{\|x-y\|^{2}}{\epsilon}\right),$
(24)

where $\alpha_{d}$ is the volume of the unit ball in ${\mathbb{R}}^{d}$. As
shown by the indicator function, edges only connect points whose distance is
within the radius $\sqrt{\epsilon}$. From the theory of random geometric
graphs [48], the order of the radius $\epsilon$ decides the order of the
average node degree. I.e., if $\epsilon$ is in the order of $\Theta(1)$, the
expected node degree is in the order of $\Theta(n)$, which is a dense regime.
If $\epsilon$ is in the order of $\Theta((\log(n)/n)^{2/d})$, the expected
node degree is in the order of $\Theta(\log(n))$, which is a relatively sparse
regime. When setting $\epsilon$ in the order of $\Theta(n^{-2/d})$, the graph
is sparse with average node degree $\Theta(1)$.

The following proposition provides a non-asymptotic error bound (in the weak
sense) for the approximation of the LB operator by the relatively sparse graph
Laplacian.

###### Proposition 3

[34, Theorem 3.3] Let ${\mathcal{M}}\in{\mathbb{R}}^{\mathsf{N}}$ be equipped
with LB operator ${\mathcal{L}}$, whose eigendecompostion is given by (7). Let
${\mathbf{G}}_{n}$ be a sparse geometric graph constructed from $n$ points
sampled u.i.d. from ${\mathcal{M}}$ with the edge weights defined as (14) and
(24), $\epsilon>(\log(n)/2n)^{2/(d+2)}$. Then, with probability at least
$1-\delta$, the following holds

$|{\mathbf{L}}_{n}^{\epsilon}\bm{\phi}_{i}(x)-{\mathcal{L}}\bm{\phi}_{i}(x)|\leq\left(C_{3}\sqrt{\frac{\ln{(2n/\delta)}}{cn\epsilon^{d+2}}}+C_{4}\sqrt{\epsilon}\right)\lambda_{i}^{\frac{d+2}{4}}\text{.}$
(25)

The constants $C_{3}$, $C_{4}$ depend on the volume of the manifold.

Comparing Proposition 1 with Proposition 3, we see that for large enough
$\epsilon$ the difference between the graph Laplacian and the Laplace-Beltrami
operator is in the order of
$\smash[b]{O(\sqrt{{\ln(2n/\delta)}/{(n\epsilon^{d+2})}},\sqrt{\epsilon})}$ in
the sparse graph setting, which is slightly larger than the order
$\smash[b]{O(\sqrt{{\ln(1/\delta)}/{(n\epsilon^{d+2})}},\sqrt{\epsilon})}$ we
observe in the dense graph case (22). This agrees with the intuition that as
dense graphs include more information about the manifold—by taking into
account all the connections between each pair of sampling points—, their
Laplacian provides a better approximation to the Laplace-Beltrami operator of
the underlying manifold than those of relatively sparse graphs.

The differences between the eigenvalues and eigenfunctions can be bounded
similarly, based on the Davis-Kahan theorem.

###### Proposition 4

[34, Theorem 2.4, Theorem 2.6] Let
${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ be equipped with LB operator
${\mathcal{L}}$, whose eigendecomposition is given by (7). Let
${\mathbf{L}}_{n}^{\epsilon}$ be the discrete graph Laplacian of graph
${\mathbf{G}}_{n}$ defined as (19) and (24), with spectrum
$\\{\lambda_{i,n}^{\epsilon},\bm{\phi}_{i,n}^{\epsilon}\\}_{i=1}^{n}$. Fix
$K\in\mathbb{N}^{+}$ and assume that
$\epsilon=\epsilon(n)\geq\left({\log(n)}/{2n}\right)^{2/(d+2)}$ Then, with
probability at least $1-2ne^{-cn\epsilon^{d/2+2}}$, we have

$|\lambda_{i}-\lambda_{i,n}^{\epsilon}|\leq
C_{K,1}\sqrt{\epsilon},\quad\|a_{i}\bm{\phi}_{i,n}^{\epsilon}-\bm{\phi}_{i}\|\leq
C_{K,2}\sqrt{\epsilon}/\theta,$ (26)

with $a_{i}\in\\{-1,1\\}$ for all $i<K$ and $\theta$ the eigengap of
${\mathcal{L}}$, i.e., $\theta=\min_{1\leq i\leq
K}\\{\lambda_{i}-\lambda_{i-1},\lambda_{i+1}-\lambda_{i}\\}$. The constants
$C_{K,1}$, $C_{K,2}$ depend on $\lambda_{K}$, $d$ and the volume of
${\mathcal{M}}$.

Akin to the result described in Proposition 2, the approximation errors of the
eigenvalues and eigenfunctions can only be bounded within a certain range of
the spectrum ($<\lambda_{K}$). Comparing with the bounds given in Proposition
2, the orders of the errors both depend on variable $\epsilon$ in the weight
function. Meanwhile, for the convergence probability there is a higher
probability in the dense geometric graph setting compared with the relatively
sparse geometric graph setting, which also supports the observation that dense
geometric graphs can provide a better approximation of the underlying manifold
than their sparse counterparts.

Remark 1. We note that $\epsilon$ in (24) controls the connectivity radius of
each node to its neighboring nodes, and that the average vertex degree is
given by $\alpha_{d}n\epsilon^{d/2}$ according to the random geometric graph
theory [49]. In the case of Proposition 4, where $\epsilon$ is fixed in the
order of $(\log(n)/2n)^{2/(d+2)}$, the average degree scales with an order
between $O((\log(n))^{2}/n)$ and $O(\log(n))$. Hence, the graphs in
Propositions 3 and 4 are relatively sparse.

##  IV Geometric GNN Convergence

Equipped with Propositions 2 and 4, which related the eigenvalues and
eigenfunctions of the manifold and graph Laplacian operators, we will next
show that convolutional filters operating on dense or sparse geometric graphs
constructed by sampling the underlying manifold give good approximations of
manifold filters. As neural networks are cascading structures composing
convolutional filters, GNNs inherit this approximation property from graph
filters, and thus provide good approximations of MNNs. We begin this section
by discussing how the definitions of manifold filters and MNNs can be
generalized to the sampled geometric graphs.

###  IV-A Geometric Graph Convolution

If we fix the impulse response function $\tilde{h}(t)$, the definition of
manifold filtering in (9) indicates that the convolution operation on the
manifold is parametric with respect to the LB operator. Therefore, we can
replace the LB operator, acting on the continuous manifold signal, by the
discrete graph Laplacian ${\mathbf{L}}_{n}^{\epsilon}$ acting on a geometric
graph signal as defined in (18). Explicitly,

${\mathbf{g}}=\int_{0}^{\infty}\tilde{h}(t)e^{-t{\mathbf{L}}_{n}^{\epsilon}}{\mathbf{f}}\text{d}t:={\mathbf{h}}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{f}},\quad{\mathbf{g}},{\mathbf{f}}\in{\mathbb{R}}^{n}.$
(27)

This can be interpreted as a discrete geometric graph filtering process in
continuous-time, where the exponential term $e^{-{\mathbf{L}}_{n}^{\epsilon}}$
should be seen as the GSO. This is slightly different than the graph
convolutional filtering ${\mathbf{h}}_{\mathbf{G}}$ defined in (1), where we
assumed a discrete-time frame.

Leveraging (11), the spectral representation of the above continuous time
geometric graph filter can be written as

${\mathbf{g}}=\sum_{i=1}^{n}\hat{h}(\lambda_{i,n}^{\epsilon})\langle{\mathbf{f}},\bm{\phi}_{i,n}^{\epsilon}\rangle_{L^{2}({\mathbf{G}}_{n})}\bm{\phi}_{i,n}^{\epsilon},$
(28)

where $\\{\lambda_{i,n}^{\epsilon},\bm{\phi}_{i,n}^{\epsilon}\\}_{i=1}^{n}$ is
the spectrum of ${\mathbf{L}}_{n}^{\epsilon}$. The spectral representation
exposes the total dependency of the filter frequency representation on the
eigenspectrum of the Laplacian operator This indicates that the relationship
between geometric graph filters and manifold filters can be established in the
spectral domain using Propositions 2 and 4.

###  IV-B Geometric Graph Convolution Convergence

Recall that the pointwise convergence of the eigenspectrum in Proposition 2
and 4 is restricted to a certain spectral range. Yet, the frequency
representation of the graph filter has a dependency on all spectral
components. Hence, the infinite spectrum of the LB operator inevitably
presents a challenge in the convergence analysis of geometric graph filters.

To address this issue, we exploit Weyl’s law [50]. This classical result
states that the eigenvalues $\\{\lambda_{i}\\}_{i=1}^{\infty}$ of
${\mathcal{L}}$ grow proportionally to $i^{2/d}$. This indicates that large
eigenvalues, in the high frequency domain, tend to accumulate; and that the
differences between neighboring eigenvalues tend to become smaller as the
eigenvalues grow larger. This phenomenon is formally described in the
following lemma.

###### Lemma 1

[17, Proposition 3] Consider a $d$-dimensional manifold
${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ and let ${\mathcal{L}}$ be its
LB operator with eigenvalues $\\{\lambda_{k}\\}_{k=1}^{\infty}$. Let $C_{1}$
be an arbitrary constant and $\alpha_{d}$ the volume of the $d$-dimensional
unit ball. Let $\text{Vol}({\mathcal{M}})$ denote the volume of manifold
${\mathcal{M}}$. For any $\alpha>0$ and $d>2$, there exists $N_{1}$,

$N_{1}=\lceil(\alpha
d/C_{1})^{d/(2-d)}(C_{d}\text{Vol}({\mathcal{M}}))^{2/(2-d)}\rceil$ (29)

such that, for all $k>N_{1}$, $\lambda_{k+1}-\lambda_{k}\leq\alpha$.

Equipped with this fact, we can employ a partitioning strategy to separate the
infinite spectrum into finite intervals as shown in Definition 2.

###### Definition 2

[17, Definition 4] ($\alpha$-separated spectrum) The $\alpha$-separated
spectrum of the LB operator ${\mathcal{L}}$ is defined as a partition
$\Lambda_{1}(\alpha)\cup\ldots\cup\Lambda_{N}(\alpha)$ satisfying
$|\lambda_{i}-\lambda_{j}|>\alpha$ for $\lambda_{i}\in\Lambda_{k}(\alpha)$ and
$\lambda_{j}\in\Lambda_{l}(\alpha)$, $k\neq l$.

The $\alpha$-separated spectrum as defined above can be achieved by means of a
$\alpha$-FDT filter, which is defined as follows.

###### Definition 3

[17, Definition 5] ($\alpha$-FDT filter) The $\alpha$-frequency difference
threshold ($\alpha$-FDT) filter is defined as a filter
${\mathbf{h}}({\mathcal{L}})$ whose frequency response satisfies

$|{\hat{h}}(\lambda_{i})-{\hat{h}}(\lambda_{j})|\leq\gamma_{k}\mbox{ for all
}\lambda_{i},\lambda_{j}\in\Lambda_{k}(\alpha)$ (30)

with $\gamma_{k}\leq\gamma$ for some $\gamma>0$ and $k=1,\ldots,N$.

To prove convergence, we will also an assumption on the continuity of the
manifold filter, which needs to be a Lipschitz filter as defined below.

###### Definition 4

(Lipschitz filter) A filter is $A_{h}$-Lispchitz if its frequency response is
Lipschitz continuous with Lipschitz constant $A_{h}$,

$|{\hat{h}}(a)-{\hat{h}}(b)|\leq A_{h}|a-b|\text{ for all
}a,b\in(0,\infty)\text{.}$ (31)

Letting the geometric graph filter (27) be a Lipschitz continuous $\alpha$-FDT
filter, we are ready to prove an approximation error bound on the difference
between the outputs of a manifold filter and a geometric graph filter
operating on a dense geometric graph.

###### Theorem 1

(Convergence of filters on dense geometric graphs) Let
${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ be equipped with LB operator
${\mathcal{L}}$, whose eigendecomposition is given by (7). Let
${\mathbf{L}}_{n}^{\epsilon}$ be the discrete graph Laplacian of the dense
graph ${\mathbf{G}}_{n}$ defined as in (19) and (21), with spectrum given by
$\\{\lambda_{i,n}^{\epsilon},\bm{\phi}_{i,n}^{\epsilon}\\}_{i=1}^{n}$. Fix
$K\in\mathbb{N}^{+}$ and assume that $\epsilon=\epsilon(n)>n^{-1/(d+4)}$ Let
${\mathbf{h}}(\cdot)$ be the convolutional filter. Under the assumption that
the frequency response of filter ${\mathbf{h}}$ is Lipschitz continuous and
$\alpha$-FDT with $\alpha^{2}\gg\epsilon$,
$\alpha>C_{{\mathcal{M}},d}K^{2/d-1}$ and
$\gamma=\Omega_{2,K}\sqrt{\epsilon}/\alpha$, with probability at least
$1-2n^{-2}$ it holds that

$\displaystyle\|{\mathbf{h}}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f-{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f\|_{L^{2}({\mathbf{G}}_{n})}$
$\displaystyle\qquad\quad\qquad\leq\left(\frac{N\Omega_{2,K}}{\alpha}+A_{h}\Omega_{1,K}\right)\sqrt{\epsilon}+C_{gc}\sqrt{\frac{\log
n}{{n}}}$ (32)

where $N$ is the partition size of the $\alpha$-FDT filter and $C_{gc}$
depends on both $d$ and the volume of ${\mathcal{M}}$.

###### Proof.

See Appendix A-A. ∎

From this theorem, we can see that, if we take $\epsilon=n^{-1/(d+4)}$, the
difference between filtering on the constructed graph and on the manifold
scales with $O(n^{-1/(2d+8)})$. Therefore, given enough sampling points, one
can guarantee good approximation accuracy with high probability. Also note
that a higher dimension leads to a larger $\epsilon$, which results in a
larger approximation error. This indicates that it is more difficult to
approximate manifolds with higher dimension.

Observe that the partition of the spectrum by the $\alpha$-FDT filter lifts
the limitation on the spectrum required in Propositions 2 and 4. This is
achieved by setting $\alpha$ large enough that eigenvalues larger than
$\lambda_{K}$ are grouped. A smaller $K$ leads to a larger $\alpha$, to ensure
that more eigenvalues in the high frequency domain are grouped. Therefore, we
can alleviate the divergence of spectral components associated with large
eigenvalues by giving them similar frequency responses, which subsequently
leads to similar filter outputs. When $K$ gets larger, the constants
$\Omega_{1,K}$ and $\Omega_{2,K}^{\prime}$ scale with $\lambda_{K}$ as
Propositions 2 and 4 show. Meanwhile, $\alpha$ can be set smaller, and the
approximation error becomes larger.

Another observation we can make from this non-asymptotic error bound is that,
for a fixed number of sampling points $n$, an interesting trade-off arises
between the approximative and discriminative capabilities of the filter. A
larger $\alpha$ (i.e., a smaller $K$) means a less discriminative filter as
more eigenvalues tend to be grouped and treated similarly with an almost
constant frequency response. A larger $\alpha$ leads to a smaller number of
partitions, as the number of singletons decreases, which results in the
decrease of the error bound in (2). This implies that the error bound becomes
smaller, as the errors brought by the approximation of the eigenvalues are
alleviated by treating different eigenvalues with similar frequency responses.

For relatively sparse graphs, we can also establish an approximation error
bound between the outputs of manifold filters and geometric graph filters
(27).

###### Theorem 2

(Convergence of filters on relatively sparse geometric graphs) Let
${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ be equipped with LB operator
${\mathcal{L}}$, whose eigendecomposition is given by (7). Let
${\mathbf{L}}_{n}^{\epsilon}$ be the discrete graph Laplacian of
${\mathbf{G}}_{n}$ defined as in (19) and (24). Fix $K\in\mathbb{N}^{+}$ and
assume that $\epsilon=\epsilon(n)>({\log(n)}/{n})^{1/d}$ Let
${\mathbf{h}}(\cdot)$ be the convolutional filter. Under the assumption that
the frequency response of the filter ${\mathbf{h}}$ is Lipschitz continuous
and $\alpha$-FDT with $\alpha^{2}\gg\epsilon$,
$\alpha>C_{{\mathcal{M}},d}K^{1-2/d}$ and $\gamma=C_{K,2}{\epsilon}/\alpha$,
with probability at least $1-2n\exp(-Cn\epsilon^{d+4})$ it holds that

$\displaystyle\|{\mathbf{h}}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f-{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f\|_{L^{2}({\mathbf{G}}_{n})}$
$\displaystyle\qquad\qquad\leq\left(\frac{NC_{K,2}}{\alpha}+A_{h}C_{K,1}\right)\sqrt{\epsilon}+C_{gc}\sqrt{\frac{\log
n}{{n}}}$ (33)

where $N$ is the partition size ofthe $\alpha$-FDT filter and $C_{gc}$ depends
on both $d$ and the volume of ${\mathcal{M}}$.

###### Proof.

See Appendix A-A. ∎

Since the convergence constants in this theorem are related with the
convergence rates presented in Proposition 4, the convergence of geometric
graph filters on sparse graphs is accordant with the convergence of the
Laplacian operator on sparse graphs, and so similar comments apply. Namely,
when compared with sparse geometric graph filters, dense geometric graph
filters provide a better approximation of the underlying manifold filters
because dense graphs carry more information about the geometry of the
manifold.

###  IV-C Geometric Graph Neural Network

As filtering on the constructed geometric graph can successfully approximate
filtering on the manifold, we can cascade geometric graph filters and
nonlinearities to construct a geometric graph neural network that we expect to
provide a good approximation of the manifold neural network. Given the
geometric graph filter defined in (27), the geometric GNN on
${\mathbf{G}}_{n}$ can be written as

${\mathbf{x}}_{l}^{p}=\sigma\left(\sum_{q=1}^{F_{l-1}}{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{x}}^{q}_{l-1}\right),$
(34)

where ${\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon})$ is the filter at
the $l$-th layer of this GNN mapping the $q$-th feature in the $l-1$-th layer
to the $p$-th feature in the $l$-th layer, with $1\leq q\leq F_{l-1}$ and
$1\leq p\leq F_{l}$. We denote the number of features in the $l$-th layer
$F_{l}$ (we have dropped the subscript $n$ in ${\mathbf{x}}_{l}^{p}$ and
${\mathbf{x}}_{l-1}^{q}$ for simplicity). Gathering the filter functions in
the set ${\mathbf{H}}$, this geometric GNN on ${\mathbf{G}}_{n}$ can be
represented more concisely as the map
$\bm{\Phi}({\mathbf{H}},{\mathbf{L}}_{n},{\mathbf{x}})$.

###  IV-D Geometric GNN Convergence

Imposing a continuity assumption on the nonlinearity function, we can prove
the following approximation error bound for geometric GNNs and MNNs.

###### Assumption 1

(Normalized Lipschitz nonlinearity) The nonlinearity $\sigma$ is normalized
Lipschitz continuous, i.e., $|\sigma(a)-\sigma(b)|\leq|a-b|$, with
$\sigma(0)=0$.

We note that this assumption is reasonable, since most common nonlinearity
functions (e.g., the ReLU, the modulus and the sigmoid) are normalized
Lipschitz.

###### Theorem 3

With the same hypotheses and definitions as in Theorem 1 and 2 respectively,
let $\bm{\Phi}({\mathbf{H}},{\mathcal{L}},\cdot)$ be an $L$-layer MNN on
${\mathcal{M}}$ (12) with $F_{0}=F_{L}=1$ input and output features and
$F_{l}=F,l=1,2,\ldots,L-1$ features per layer. Let
$\bm{\Phi}({\mathbf{H}},{\mathbf{L}}_{n},\cdot)$ be the GNN with the same
architecture applied to the geometric graph ${\mathbf{G}}_{n}$. If the
nonlinearities satisfy Assumption 1 and the manifold filters satisfy
$\|{\mathbf{h}}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f-{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f\|_{L^{2}({\mathbf{G}}_{n})}\leq\Delta_{fil,n}$,
it holds that

$\displaystyle\|\bm{\Phi}({\mathbf{H}},{\mathbf{L}}_{n}^{\epsilon},{\mathbf{P}}_{n}f)-{\mathbf{P}}_{n}\bm{\Phi}({\mathbf{H}},{\mathcal{L}},f)\|_{L^{2}({\mathbf{G}}_{n})}\leq
LF^{L-1}\Delta_{fil,n}$

with high probability.

###### Proof.

See Section B-C in supplemental materials. ∎

We conclude that the geometric GNN converges to the MNN as long as the
geometric graph filter components give good approximations of the
corresponding manifold filters when restricted to the sampled geometric
graphs. Further, we see that this error consists of two terms. The first term,
$LF^{L-1}$, depends on the number of filters and layers in the MNN
architecture. More specifically, the approximation bound grows linearly with
the number of layers $L$ and exponentially with the number of features $F$
where the rate is determined by $L$. This term appears because the
approximation errors propagate across all the manifold filters in all layers
of the MNN. The second term is the approximation error constant of the
geometric graph filters $\Delta_{fil,n}$, which should be replaced with the
error bounds from Theorem 1 and Theorem 2 for dense and sparse graphs
respectively.

We note that the approximation error constant $\Delta_{fil,n}$ emphasizes that
the trade-off between approximation and discriminability is inherited from the
convolutional filters. However, since neural networks also have nonlinearities
in their layers, the geometric GNN has a better ability to both discriminate
high frequency components and approximate the MNN with satisfying accuracy.
This is due to the fact that nonlinearities have a spectral mixing effect. In
the neural network architecture, the frequency components in the high
frequency domain can be shifted to low frequency domain, where they can then
be discriminated by the filters in the following layer. This role of
nonlinearities has also been discussed in the stability analysis of GNNs [20]
as well as of MNNs [17].

###  IV-E From convergence to transferability

Leveraging the non-asymptotic convergence results derived in Theorem 3, we can
immediately prove a transferability corollary for geometric GNNs constructed
from a common underlying MNN. Explicitly, consider two geometric graphs
${\mathbf{G}}_{n_{1}}$ and ${\mathbf{G}}_{n_{2}}$ that are either dense (21)
or realtively sparse graphs (24). The difference between the outputs of the
same neural network (i.e., with the same weights) on these two graphs is
bounded by the following corollary.

###### Corollary 1

Let ${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ be equipped with LB
operator ${\mathcal{L}}$. Let ${\mathbf{L}}_{n_{1}}^{\epsilon}$ be the
discrete graph Laplacian of the graph ${\mathbf{G}}_{n_{1}}$ defined as in
(19) and (21) or (24). Let ${\mathbf{L}}_{n_{2}}^{\epsilon}$ be the discrete
graph Laplacian of the graph ${\mathbf{G}}_{n_{2}}$ constructed in the same
manner as ${\mathbf{G}}_{n_{1}}$. Let $\bm{\Phi}({\mathbf{H}},\cdot,\cdot)$ be
an $L$-layer GNN with $F_{0}=F_{L}=1$ input and output features and
$F_{l}=F,l=1,2,\ldots,L-1$ features per layer. Assume that the filters and
nonlinearity functions are as in Definitions 3, 4 and satisfy Assumption 1
respectively. Then, it holds in high probability that

$\displaystyle\|{\mathbf{I}}_{n_{1}}\bm{\Phi}({\mathbf{H}},{\mathbf{L}}_{n_{1}}^{\epsilon},{\mathbf{P}}_{n_{1}}f)-{\mathbf{I}}_{n_{2}}\bm{\Phi}({\mathbf{H}},{\mathbf{L}}_{n_{2}}^{\epsilon},{\mathbf{P}}_{n_{2}}f)\|$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\leq
LF^{L-1}(\Delta_{fil,n_{1}}+\Delta_{fil,n_{2}})\text{.}$ (35)

From this corollary, we can observe that the geometric GNN trained on one
geometric graph can be directly transferred to another geometric graph if they
are constructed in the same way from the same underlying manifold. The
difference between the outputs of the GNNs depends on the size of the neural
network architecture as well as on the approximation capability of the filter
functions. Larger numbers of sample points $n_{1}$ and $n_{2}$ lead to smaller
approximation errors $\Delta_{fil,n_{1}}$ and $\Delta_{fil,n_{2}}$, that is,
better approximation leads to better transferability in geometric GNNs.

The main implication of this corollary is that if we have trained a geometric
GNN on a relatively small geometric graph, this GNN can be transferred to
another, larger geometric graph with performance guarantees, which is helpful
because it is costly to train GNNs on large graphs. Using the bound in
Corollary 1, we can determine the minimum number of sampled points needed for
training a geometric GNN to meet a given approximation error tolerance.
Therefore, the geometric GNN is a suitable model to approximate both
continuous MNNs and large geometric GNNs.

##  V Discussions

Approximation vs. discriminability tradeoff. In the convergence results for
geometric graph filters on both dense graphs (Theorem 1) and sparse graphs
(Theorem 2), the approximation error bounds depend on the size of the
partition ($N$), the frequency partition threshold ($\alpha$), the Lipschitz
continuity constant ($A_{h}$) and the weight function parameter ($\epsilon$),
and the number of nodes in the geometric graph ($n$). The size of the
partition and the frequency partition threshold have a concerted effect in the
approximation, as a larger frequency partition threshold leads to a larger
number of intervals containing more than one eigenvalue and a smaller number
of intervals containing only one eigenvalue. The size of the partition however
tends to stay the same or decrease because the number of intervals cannot
exceed the number of eigenvalues. Therefore, a larger frequency partition
threshold results in a smaller partition size. Combined, these lead to a
smaller approximation error bound. Meanwhile, a larger frequency threshold
also means that a larger number of eigenvalues are grouped and treated with
similar frequency responses. This makes the $\alpha$-FDT filters less
discriminative. A similar story holds for the Lipschitz constant $A_{h}$, with
smaller Lipschitz constant increasing the approximation error bound but
decreasing discriminability. A larger $\epsilon$ leads to a larger
approximation error bound, but at the same time the variation range $\gamma$
in the $\alpha$-FDT filter becomes larger which results in better
discriminability. In conclusion, there is a trade-off between the
approximation and discriminability properties of both geometric graph filters
and geometric GNNs, but in GNNs this trade-off is alleviated thanks to the
nonlinearities, as we discuss next.

Graph filters vs. GNNs. Due to the aforementioned trade-off between
approximation and discriminability arising from the spectrum partition,
geometric graph filters cannot simultaneously discriminate high-frequency
components and provide good approximations of manifold filters. In geometric
GNNs, this trade-off is however alleviated by the use of nonlinearities. When
processing the outputs of the filters in the previous layer, the
nonlinearities in a given layer have the ability to shift some high frequency
components to the low frequency domain, where they can then be discriminated
by the filters in the following layer. As a consequence of this frequency
scattering behavior, geometric GNNs can be simultaneously approximative and
discriminative.

Dense graphs vs. sparse graphs. Depending on whether the graphs are dense or
sparse, different weight functions are chosen to construct the geometric
graph, leading to different convergence regimes. From the results presented in
Proposition 1 and Proposition 2 for dense geometric graphs and Proposition 3
and Proposition 2 for sparse geometric graphs, we can see that, given the same
number of sample points $n$ and the same weight function parameter $\epsilon$,
dense graphs have a slightly smaller approximation error bound when compared
with sparse graphs—thus implying that geometric graph filters and geometric
GNNs provide better approximations of manifold filters and MNNs when operating
on dense graphs. This can be explained by the fact that dense graphs include
more information; for one, they are complete. However, the sparse graph
setting is a more realistic model in practice, and in particular it has been
employed in many areas such as wireless communication networks and sensor
networks. The approximation guarantees derived in this paper apply in either
sparsity regime.

Discretization over time. Theoretically, we employ the definitions of
geometric graph convolution and manifold convolution in a continuous-time
domain as (27) and (9) show. However, in practice we need to operate the
filters and neural networks in digital systems, which requires the time
horizon is discrete. In the following section, we carry out numerical
experiments with geometric graph filters defined in a discrete-time domain.
Specifically, we discretize the impulse response function with an interval
$T_{s}$ and replace the function with a series of filter coefficients
$h_{k}=\tilde{h}(kT_{s})$ [16]. By fixing the time horizon with finite $K_{t}$
samples, we can write the practical geometric filter as

${\mathbf{g}}=\sum_{k=0}^{K_{t}-1}h_{k}e^{-k{\mathbf{L}}_{n}^{\epsilon}}{\mathbf{f}},\quad{\mathbf{f}},{\mathbf{g}}\in{\mathbb{R}}^{n},$
(36)

which recovers the graph convolution definition in (1) with
$e^{-{\mathbf{L}}_{n}^{\epsilon}}$ seen as the graph shift operator.

##  VI Numerical Experiments

###  VI-A Navigation control

(a) Testing on $n=435$

(b) Testing on $n=630$

(c) Testing on $n=780$

(d) Testing on $n=1225$

Figure 1: Lipschitz GNN trained on geometric graph with $n=435$ and tested on
geometric graphs with $n=435,630,780,1225$. The red arrows in the figures show
the predicted directions for all sampled points over the space.

We consider a problem of automatic navigation of an agent [51]. We intend to
navigate an agent starting from a given point to find a path to the goal
without colliding into the obstacles. We sample grid points uniformly over the
free space while avoiding the obstacle areas to construct a geometric graph
structure involving the topological information. We first generate several
trajectories with Dijkstra’s shortest path algorithm that leads the agent from
a randomly selected starting point to the goal. Every point along the
generated trajectories is labeled with a 2-d direction vector of the velocity.
The geometric adjacency matrix is calculated based on the weight function
defined in (14) with (21). Specifically, the underlying topology information
is captured by setting the Euclidean distance between two points as infinity
(i.e. weight value as zero) if there is no direct path connecting these two
points without colliding into the obstacles. The input graph signal is the
position coordinates of some point over the space and the final output is the
direction that can lead to the goal point. The learned architectures are
tested via randomly generating $100$ starting points and computing the
trajectory by predicting directions of the points along the trajectory. If the
trajectory can reach the goal point without colliding into the obstacles, the
trajectory is marked as “success". The performances are measured by
calculating the successful rates of all the learned architectures.

Learning architectures and experiment settings. We build dense geometric
graphs as the approximations to the models as the regular grid graph structure
brings little difference between the dense and sparse graph setting. We set
the position of each point as input signals on the graphs. The weights of the
edges are calculated based on the Euclidean distance between the nodes and the
weight function is determined as (21) with $\epsilon=0.2$. We calculate the
Laplacian matrix for the graph as the input graph shift operator. We train and
test three architectures, including 2-layer Graph Filters (GF), 2-layer Graph
Neural Network (GNN) and 2-layer Lipschitz Graph Neural Network (Lipschitz
GNN) which all contain $F_{0}=2$ input features, $F_{1}=128$ and $F_{2}=64$
features with $K_{t}=10$ filters in each layer. ReLU is used as the
nonlinearity function in GNN and Lipschitz GNN. In Lipschitz GNN architecture,
we put the Lipschitz continuity restriction to the graph filter function by
importing a penalty term which is the scaled derivative of the filter function
$C_{L}h^{\prime}(\lambda)$ to the loss function. A larger Lipschitz constant
$C_{L}$ indicates a smoother filter function. All architectures also include a
linear readout layer to map the 2-d direction vector outputs. The loss
function is MSE loss and the optimizer is SGD with the learning rate set as
$0.0002$. The architectures are trained over $30,000$ epochs.

Convergence analysis. The convergence is tested by calculating the difference
of the outputs of the graph filters in the last layer for each architecture.
By training the graph filters and GNNs on geometric graphs with
$n=190,276,435,630,780$, and plotting the differences between the output of
the trained graph filters or GNNs on geometric graphs with size $n$ and on the
relatively large enough geometric graphs with size $n=1225$. From Figure 5 we
can see that the output differences decrease and converge as the trained
geometric graph size grows, which is accordant with Corollary 1. This also
verifies the convergence of geoemtric GNNs as presented in 3 if we see the
large geometric graph as an approximation of the underlying manifold. We can
conclude that Lipschitz GNNs have better approximations while GNNs outperform
Graph Filters.

Figure 2: Differences of the outputs of 2-layer graph filters, 2-layer GNN and
2-layer Lipschitz GNN.

We further study the effect of Lipschitz continuity of the graph filter
functions by changing the penalty constant $C_{L}$. From Figure 3 we can see
as the constant grows, the output differences become smaller, which attests
our claim that smoother filter functions provide better approximations.

Figure 3: Differences of the outputs of Lipshitz GNN with penalty terms.

Transferability verification. We verify the transferability result presented
in Corollary 1 by training the architectures on a sampled geometric graph with
size $n=435,630,780,1225$ and testing these architectures on the large
geometric graphs with $n=1225$. Note that due to the non-scability of the
linear readout layer, we keep the graph filter functions unchanged and only
retrain the final linear layer to map the outputs to a 2-d direction vector.
The successful rates are shown in Table I. We can observe that the
architectures trained on smaller sampled geometric graphs can still perform
well when implemented on larger graphs. Moreover, Lipschitz GNN performs
slightly better than GNN which outperforms Graph Filters. This can be
understood as the Lipschitz continuity of the filter functions and the
nonlinearity functions help with the transferability as we have discussed in
Section 3.

| Graph Filter | GNN | Lipschitz GNN
---|---|---|---
$n=435$ | 0.74 | 0.74 | 0.76
$n=630$ | 0.79 | 0.8 | 0.78
$n=780$ | 0.81 | 0.82 | 0.83
$n=1225$ | 0.82 | 0.83 | 0.84
Table I: Successful rates when testing the architectures trained on geometric
graphs with $n=435,630,780,1225$ on the geometric graph with $n=1225$.

To make the results more explicit, we show the predicted directions for each
point over the space tested with a Lipschitz GNN trained on graph with $n=435$
in Figure 1. The red arrows point to the learned directions starting from each
unlabeled points while the blue arrows are the learned directions for labeled
points. We can see that Lipschitz GNN can efficiently learn the successful
directions for unlabeled points based on these geometric graphs and can
transfer to larger graphs.

###  VI-B Point Cloud Model Classification

We further evaluate the convergence results on the ModelNet10 [52]
classification problem. The dataset includes 3,991 meshed CAD models from 10
categories for training and 908 models for testing. In each model, $n$ points
are uniformly randomly selected to construct geometric graphs to approximate
the underlying model, such as chairs, tables. Figure 4 shows the point cloud
model with different sampling points. Our goal is to identify the models for
chairs from other models.

Figure 4: Point cloud models with 50 and 300 sampling points in each model.
Our goal is to identify chair models from other models such as toilet and
table.

Learning architectures and experiment settings. We build both dense and sparse
geometric graphs as the approximations to the models. We set the coordinates
of each point as input signals on the graphs. The weights of the edges are
calculated based on the Euclidean distance between the nodes. For the dense
geometric graphs, the weight function is determined as (21) with
$\epsilon=0.1$. Similarly, the weight function of a sparse geometric graph is
calculated as (24) with $\epsilon=0.001$ as the threshold. We calculate the
Laplacian matrix for each graph as the input graph shift operator. In this
experiment, we implement and compare three different architectures, including
2-layer Graph Filters (GF), 2-layer Graph Neural Network (GNN) and 2-layer
Lipschitz Graph Neural Network (Lipschitz GNN). The architectures contain
$F_{0}=3$ input features which are the 3-d coordinates of each point,
$F_{1}=64$ and $F_{2}=32$ features with $K_{t}=5$ filters in each layer. In
GNN and Lipschitz GNN, ReLU is used as the nonlinearity function. The filters
in Lipschitz GNN is regularized as Lipschitz continuous by imposing a penalty
term $C_{L}h^{\prime}(\lambda)$ to the loss function with $C_{L}$ set as 0.3.
All architectures include a linear readout layer to map the final
classification outputs.

All the architectures are trained by minimizing the cross-entropy loss. We
implement an ADAM optimizer with the learning rate set as 0.005 along with the
forgetting factors 0.9 and 0.999. We carry out the training for 40 epochs with
the size of batches set as 10. We run 5 random dataset partitions and show the
average estimation error rates and the standard deviation across these
partitions.

Convergence Verification. We verify our convergence results by training the
graph filters and GNNs on geometric graphs with
$n=300,400,500,600,700,800,900$ sampling points, and plotting the differences
between the output of the trained graph filters or GNNs on geometric graphs
with size $n$ and on the relatively large enough geometric graphs with size
$1000$. Figure 5 shows the convergence results for dense graphs and figure 6
shows the results for sparse graphs.

Figure 5: Differences of the outputs of Lipschitz GNN, GNN and graph filter
trained on dense geometric graphs. Figure 6: Differences of the outputs of
Lipschitz GNN, GNN and graph filter trained on sparse geometric graphs.

From the figures we can see that the differences between the outputs on the
trained smaller geometric graphs and the relatively large geometric graphs
decrease and converge as the trained graph size grows, which verifies
Corollary 1. This also proves what we state in Theorem 3 that the
approximation errors of geometric GNNs to the MNNs decrease as the number of
nodes grows if we see the large enough graph with $n=1000$ nodes as the
manifold. We can also observe that Lipschitz GNNs have better approximations
than GNNs because of the continuous filter function while GNNs outperform
graph filters due to the nonlinearity function.

Transferability verification. We train the architectures on both dense and
sparse geometric graphs with $n=300,500,700,900$ sampled points from each CAD
model. To justify the theoretical results that we have stated in Section IV,
we test these trained architectures on a relatively large graph containing
$n=1000$ sampled points to verify that geometric GNNs have the transferability
to large graphs, i.e. the trained geometric graph filters and GNNs can be
directly implemented on larger geometric graphs as long as the geometric
graphs are constructed in the same manner. The classification error rates are
shown in Table II for the dense graph setting and in Table III for the sparse
graph setting.

| Graph Filters | GNN | Lipschitz GNN
---|---|---|---
$n=300$ | $21.15\%\pm 3.48\%$ | $9.35\%\pm 2.46\%$ | $7.63\%\pm 3.36\%$
$n=500$ | $18.09\%\pm 6.28\%$ | $7.80\%\pm 3.50\%$ | $7.54\%\pm 4.01\%$
$n=700$ | $17.31\%\pm 6.59\%$ | $8.16\%\pm 2.95\%$ | $7.97\%\pm 2.45\%$
$n=900$ | $15.58\%\pm 4.54\%$ | $7.20\%\pm 3.77\%$ | $6.68\%\pm 3.94\%$
Table II: Classification error rates for model ’chair’ when testing the architectures trained on dense geometric graphs with $n=300,500,700,900$ to dense geometric graphs with $n=1000$. Average over 5 data realizations. | Graph Filters | GNN | Lipschitz GNN
---|---|---|---
$n=300$ | $19.83\%\pm 5.94\%$ | $7.74\%\pm 4.05\%$ | $7.68\%\pm 3.75\%$
$n=500$ | $21.97\%\pm 4.17\%$ | $10.10\%\pm 1.40\%$ | $8.60\%\pm 2.95\%$
$n=700$ | $13.85\%\pm 3.81\%$ | $7.45\%\pm 4.03\%$ | $8.02\%\pm 2.77\%$
$n=900$ | $16.62\%\pm 2.38\%$ | $7.92\%\pm 3.14\%$ | $7.44\%\pm 3.30\%$
Table III: Classification error rates for model ’chair’ when testing the
architectures trained on sparse geometric graphs with $n=300,500,700,900$ to
sparse geometric graphs with $n=1000$. Average over 5 data realizations.

We can see from the results shown in the tables that the trained architectures
can still perform well on the relatively large geometric graphs, both for
dense and sparse graph settings. We can see that Lipschitz GNNs outperform
GNNs, which perform better than graph filters. This attests the effects of the
filter function continuity and nonlinearity that we have discussed in Section
IV, which is continuous filter function and nonlinearity function both help
with improving transferability. We can also observe that architectures trained
on geometric graphs with more number of nodes can achieve better performances
on the relatively large graphs. This can be understood when we see this large
enough geometric graph with $n=1000$ approximately as the underlying manifold
and as Theorem 3 shows the geometric GNNs can give better approximations to
the MNNs as the number of nodes grow. This can also be understood as the
transferability property presented in Corollary 1, which also indicates that
graph filters and GNNs trained on larger geometric graphs have better
performance approximations. Furthermore, the results also show that
architectures trained on dense geometric graphs transfer better than the ones
trained on sparse geometric graphs, which is also accordant with what we have
claimed in Section IV.

##  VII Conclusions

In this paper, we import the definition of manifold convolutional filters with
an exponential Laplace-Beltrami operator to process manifold signals. The
manifold model is accessible with a set of i.i.d. uniformly sampled points
over the manifold. We construct both dense and sparse graph models to
approximate the underlying manifold. We first prove the approximation error
bounds of discrete graph Laplacians to the LB operator in the spectral domain.
We transfer the definition of manifold filter to the constructed graph and
prove the graph filter can approximate the manifold filter with a non-
asymptotic error bound. The constructed graph filters need to trade-off
between the discrimative and approximative powers while GNNs composed with
graph filters and nonlinearities can alleviate the trade-off with the
frequency mixing by nonlinearities. We conclude that the GNNs are thus both
good approximations of MNNs and discriminative. We finally verified our
results numerically with a navigation control problem over a manifold.

## References

  * [1] Z. Wang, L. Ruiz, and A. Ribeiro, “Convolutional filtering on sampled manifolds,” in _ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2023, pp. 1–5.
  * [2] ——, “Convergence of graph neural networks on relatively sparse graphs,” 2023\. [Online]. Available: https://zhiyangw.com/Papers/Asilomar2023.pdf
  * [3] V. N. Ioannidis, A. G. Marques, and G. B. Giannakis, “Graph neural networks for predicting protein functions,” in _2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)_. IEEE, 2019, pp. 221–225.
  * [4] V. Gligorijević, P. D. Renfrew, T. Kosciolek, J. K. Leman, D. Berenberg, T. Vatanen, C. Chandler, B. C. Taylor, I. M. Fisk, H. Vlamakis _et al._ , “Structure-based protein function prediction using graph convolutional networks,” _Nature communications_ , vol. 12, no. 1, pp. 1–14, 2021.
  * [5] Q. Li, F. Gama, A. Ribeiro, and A. Prorok, “Graph neural networks for decentralized multi-robot path planning,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 11 785–11 792.
  * [6] E. Tolstaya, J. Paulos, V. Kumar, and A. Ribeiro, “Multi-robot coverage and exploration using spatial graph neural networks,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 8944–8950.
  * [7] J. Zeng, G. Cheung, M. Ng, J. Pang, and C. Yang, “3d point cloud denoising using graph laplacian regularization of a low dimensional manifold model,” _IEEE Transactions on Image Processing_ , vol. 29, pp. 3474–3489, 2019.
  * [8] M. Devanne, H. Wannous, S. Berretti, P. Pala, M. Daoudi, and A. Del Bimbo, “3-d human action recognition by shape analysis of motion trajectories on riemannian manifold,” _IEEE transactions on cybernetics_ , vol. 45, no. 7, pp. 1340–1352, 2014.
  * [9] Y. Wang, Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon, “Dynamic graph cnn for learning on point clouds,” _Acm Transactions On Graphics (tog)_ , vol. 38, no. 5, pp. 1–12, 2019.
  * [10] Z. He, L. Wang, H. Ye, G. Y. Li, and B.-H. F. Juang, “Resource allocation based on graph neural networks in vehicular communications,” in _GLOBECOM 2020-2020 IEEE Global Communications Conference_. IEEE, 2020, pp. 1–5.
  * [11] Z. Wang, L. Ruiz, M. Eisen, and A. Ribeiro, “Stable and transferable wireless resource allocation policies via manifold neural networks,” in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 8912–8916.
  * [12] F. Gama, E. Isufi, G. Leus, and A. Ribeiro, “Graphs, convolutions, and neural networks: From graph filters to graph neural networks,” _IEEE Signal Processing Magazine_ , vol. 37, no. 6, pp. 128–138, 2020.
  * [13] A. Ortega, P. Frossard, J. Kovačević, J. M. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” _Proceedings of the IEEE_ , vol. 106, no. 5, pp. 808–828, 2018.
  * [14] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” _IEEE transactions on neural networks_ , vol. 20, no. 1, pp. 61–80, 2008.
  * [15] F. Gama, A. G. Marques, G. Leus, and A. Ribeiro, “Convolutional neural network architectures for signals supported on graphs,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 4, pp. 1034–1049, 2019.
  * [16] Z. Wang, L. Ruiz, and A. Ribeiro, “Convolutional neural networks on manifolds: From graphs and back,” _arXiv preprint arXiv:2210.00376_ , 2022.
  * [17] ——, “Stability of neural networks on manifolds to relative perturbations,” in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 5473–5477.
  * [18] J. Masci, D. Boscaini, M. Bronstein, and P. Vandergheynst, “Geodesic convolutional neural networks on riemannian manifolds,” in _Proceedings of the IEEE international conference on computer vision workshops_ , 2015, pp. 37–45.
  * [19] R. Chakraborty, J. Bouza, J. H. Manton, and B. C. Vemuri, “Manifoldnet: A deep neural network for manifold-valued data with applications,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 44, no. 2, pp. 799–810, 2020.
  * [20] F. Gama, J. Bruna, and A. Ribeiro, “Stability properties of graph neural networks,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 5680–5695, 2020.
  * [21] N. Keriven, A. Bietti, and S. Vaiter, “Convergence and stability of graph convolutional networks on large random graphs,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 21 512–21 523, 2020.
  * [22] D. Zou and G. Lerman, “Graph convolutional neural networks via scattering,” _Applied and Computational Harmonic Analysis_ , vol. 49, no. 3, pp. 1046–1074, 2020.
  * [23] Z. Wang, L. Ruiz, and A. Ribeiro, “Stability to deformations of manifold filters and manifold neural networks,” _arXiv preprint arXiv:2106.03725_ , 2021.
  * [24] F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein, “Geometric deep learning on graphs and manifolds using mixture model cnns,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 5115–5124.
  * [25] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst, “Geometric deep learning: going beyond euclidean data,” _IEEE Signal Processing Magazine_ , vol. 34, no. 4, pp. 18–42, 2017.
  * [26] M. Eliasof, E. Haber, and E. Treister, “Pde-gcn: novel architectures for graph neural networks motivated by partial differential equations,” _Advances in neural information processing systems_ , vol. 34, pp. 3836–3849, 2021.
  * [27] W. Shi and R. Rajkumar, “Point-gnn: Graph neural network for 3d object detection in a point cloud,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 1711–1719.
  * [28] M. T. Kejani, F. Dornaika, and H. Talebi, “Graph convolution networks with manifold regularization for semi-supervised learning,” _Neural Networks_ , vol. 127, pp. 160–167, 2020.
  * [29] L. Ruiz, L. F. Chamon, and A. Ribeiro, “Transferability Properties of Graph Neural Networks,” _arXiv preprint arXiv:2112.04629_ , 2021.
  * [30] ——, “Graphon signal processing,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 4961–4976, 2021.
  * [31] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, “Graph neural networks: A review of methods and applications,” _AI Open_ , vol. 1, pp. 57–81, 2020.
  * [32] L. Ruiz, L. Chamon, and A. Ribeiro, “Graphon neural networks and the transferability of graph neural networks,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 1702–1712, 2020.
  * [33] S. Maskey, R. Levie, and G. Kutyniok, “Transferability of graph neural networks: an extended graphon approach,” _arXiv preprint arXiv:2109.10096_ , 2021.
  * [34] J. Calder and N. G. Trillos, “Improved spectral convergence rates for graph laplacians on epsilon-graphs and k-nn graphs,” _arXiv preprint arXiv:1910.13476_ , 2019.
  * [35] J. Chew, D. Needell, and M. Perlmutter, “A convergence rate for manifold neural networks,” _arXiv preprint arXiv:2212.12606_ , 2022.
  * [36] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” _IEEE signal processing magazine_ , vol. 30, no. 3, pp. 83–98, 2013.
  * [37] A. Sandryhaila and J. M. Moura, “Discrete signal processing on graphs,” _IEEE transactions on signal processing_ , vol. 61, no. 7, pp. 1644–1656, 2013.
  * [38] N. Boumal, _An introduction to optimization on smooth manifolds_. Cambridge University Press, 2023.
  * [39] S. Rosenberg and R. Steven, _The Laplacian on a Riemannian manifold: an introduction to analysis on manifolds_. Cambridge University Press, 1997, no. 31.
  * [40] F. R. Chung, _Spectral graph theory_. American Mathematical Soc., 1997, vol. 92.
  * [41] J. Pach, “The beginnings of geometric graph theory,” _Erdős Centennial_ , pp. 465–484, 2013.
  * [42] R. Merris, “A survey of graph laplacians,” _Linear and Multilinear Algebra_ , vol. 39, no. 1-2, pp. 19–31, 1995.
  * [43] R. Levie, W. Huang, L. Bucci, M. Bronstein, and G. Kutyniok, “Transferability of spectral graph convolutional neural networks,” _Journal of Machine Learning Research_ , vol. 22, no. 272, pp. 1–59, 2021.
  * [44] D. B. Dunson, H.-T. Wu, and N. Wu, “Spectral convergence of graph laplacian and heat kernel reconstruction in $l^{\infty}$ from random samples,” _Applied and Computational Harmonic Analysis_ , vol. 55, pp. 282–336, 2021\.
  * [45] M. Belkin and P. Niyogi, “Towards a theoretical foundation for laplacian-based manifold methods,” _Journal of Computer and System Sciences_ , vol. 74, no. 8, pp. 1289–1308, 2008.
  * [46] Y. Shi and B. Xu, “Gradient estimate of an eigenfunction on a compact riemannian manifold without boundary,” _Annals of Global Analysis and Geometry_ , vol. 38, no. 1, pp. 21–26, 2010.
  * [47] A. Seelmann, “Notes on the $sin2\theta$ theorem,” _Integral Equations and Operator Theory_ , vol. 79, no. 4, pp. 579–597, 2014.
  * [48] M. Penrose, _Random geometric graphs_. OUP Oxford, 2003, vol. 5.
  * [49] M. Hamidouche, “Spectral analysis of random geometric graphs,” Ph.D. dissertation, Université Côte d’Azur, 2020.
  * [50] W. Arendt and W. P. Schleich, _Mathematical analysis of evolution, information, and complexity_. John Wiley & Sons, 2009.
  * [51] J. Cervino, L. Chamon, B. D. Haeffele, R. Vidal, and A. Ribeiro, “Learning globally smooth functions on manifolds,” _arXiv preprint arXiv:2210.00301_ , 2022.
  * [52] Z. Wu, S. Song, A. Khosla, F. Yu, L. Zhang, X. Tang, and J. Xiao, “3d shapenets: A deep representation for volumetric shapes,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 1912–1920.
  * [53] U. Von Luxburg, M. Belkin, and O. Bousquet, “Consistency of spectral clustering,” _The Annals of Statistics_ , pp. 555–586, 2008.
  * [54] M. Belkin and P. Niyogi, “Convergence of laplacian eigenmaps,” _Advances in neural information processing systems_ , vol. 19, 2006.

##  Appendix A Appendix

###  A-A Proof of Theorem 1 and Theorem 2

We first write out the filter representation as

$\displaystyle\|{\mathbf{h}}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f-{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f\|$
$\displaystyle\leq\left\|\sum_{i=1}^{\infty}\hat{h}(\lambda_{i,n}^{\epsilon})\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i,n}^{\epsilon}-\sum_{i=1}^{\infty}\hat{h}(\lambda_{i})\langle
f,\bm{\phi}_{i}\rangle_{{\mathcal{M}}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right\|$
(37)

We denote the index of partitions that contain a single eigenvalue as a set
${\mathcal{K}}_{s}$ ($|{\mathcal{K}}_{s}|=N_{s}$) and the rest as a set
${\mathcal{K}}_{m}$ ($|{\mathcal{K}}_{m}|=N_{m}$). We decompose the
$\alpha$-FDT filter function as
$\hat{h}(\lambda)=h^{(0)}(\lambda)+\sum_{l\in{\mathcal{K}}_{m}}h^{(l)}(\lambda)$
as

$\displaystyle
h^{(0)}(\lambda)=\left\\{\begin{array}[]{cc}\hat{h}(\lambda)-\sum\limits_{l\in{\mathcal{K}}_{m}}\hat{h}(C_{l})&\lambda\in[\Lambda_{k}(\alpha)]_{k\in{\mathcal{K}}_{s}}\\\
0&\text{otherwise}\\\ \end{array}\right.$ (40) $\displaystyle
h^{(l)}(\lambda)=\left\\{\begin{array}[]{cc}\hat{h}(C_{l})&\lambda\in[\Lambda_{k}(\alpha)]_{k\in{\mathcal{K}}_{s}}\\\
\hat{h}(\lambda)&\lambda\in\Lambda_{l}(\alpha)\\\ 0&\text{otherwise}\\\
\end{array}\right.$ (44)

with $C_{l}$ some constant in $\Lambda_{l}(\alpha)$. With the triangle
inequality, we start by analyzing the output difference of $h^{(0)}(\lambda)$
as

$\displaystyle\|\sum_{i=1}^{\infty}{h}^{(0)}(\lambda_{i,n}^{\epsilon})\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i,n}^{\epsilon}-\sum_{i=1}^{\infty}{h}^{(0)}(\lambda_{i})\langle
f,\bm{\phi}_{i}\rangle_{{\mathcal{M}}}{\mathbf{P}}_{n}\bm{\phi}_{i}\|$
$\displaystyle\leq\left\|\sum_{i=1}^{\infty}\left({h}^{(0)}(\lambda_{i,n}^{\epsilon})-{h}^{(0)}(\lambda_{i})\right)\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i,n}^{\epsilon}\right\|$
$\displaystyle+\left\|\sum_{i=1}^{\infty}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i,n}^{\epsilon}-\langle
f,\bm{\phi}_{i}\rangle_{{\mathcal{M}}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right)\right\|.$
(45)

The first term in (45) can be bounded by leveraging the $A_{h}$-Lipschitz
continuity of the frequency response. From the eigenvalue difference in
Proposition 4, we can claim that for each eigenvalue
$\lambda_{i}\leq\lambda_{K}$, we have

$\displaystyle|\lambda_{i,n}^{\epsilon}-\lambda_{i}|\leq\Omega_{1,K}\sqrt{\epsilon}.$
(46)

The square of the first term is bounded as

$\displaystyle\left\|\sum_{i=1}^{\infty}({h}^{(0)}(\lambda_{i,n}^{\epsilon})-{h}^{(0)}(\lambda_{i}))\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i,n}^{\epsilon}\right\|^{2}$
$\displaystyle\leq\sum_{i=1}^{\infty}|{h}^{(0)}(\lambda_{i,n}^{\epsilon})-{h}^{(0)}(\lambda_{i})|^{2}|\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}|^{2}$
(47)
$\displaystyle\leq\sum_{i=1}^{\infty}A_{h}^{2}|\lambda_{i,n}^{\epsilon}-\lambda_{i}|^{2}\|{\mathbf{P}}_{n}f\|^{2}\leq
A_{h}^{2}\Omega_{1,K}^{2}\epsilon.$ (48)

The second term in (45) can be bounded combined with the convergence of
eigenfunctions in (50) as

$\displaystyle\Bigg{\|}\sum_{i=1}^{\infty}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i,n}^{\epsilon}-\langle
f,\bm{\phi}_{i}\rangle_{{\mathcal{M}}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right)\Bigg{\|}$
$\displaystyle\leq\Bigg{\|}\sum_{i=1}^{\infty}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i,n}^{\epsilon}-\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right)\Bigg{\|}$
$\displaystyle+\left\|\sum_{i=1}^{\infty}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}{\mathbf{P}}_{n}\bm{\phi}_{i}-\langle
f,\bm{\phi}_{i}\rangle_{\mathcal{M}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right)\right\|$
(49)

From the convergence stated in Theorem 4, we have

$\displaystyle\|a_{i}\bm{\phi}_{i,n}^{\epsilon}-\bm{\phi}_{i}\|\leq\Omega_{2,K}\sqrt{\epsilon}/\theta,$
(50)

with the eigengap $\theta\geq\alpha$ under the $\alpha$-FDT filter. Therefore,
the first term in (49) can be bounded as

$\displaystyle\left\|\sum_{i=1}^{\infty}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i,n}^{\epsilon}-\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathcal{M}}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right)\right\|$
$\displaystyle\qquad\qquad\leq\sum_{i=1}^{N_{s}}\|{\mathbf{P}}_{n}f\|\|\bm{\phi}_{i,n}^{\epsilon}-{\mathbf{P}}_{n}\bm{\phi}_{i}\|\leq\frac{N_{s}\Omega_{2,K}}{\alpha}\sqrt{\epsilon}.$
(51)

The last equation comes from the definition of norm in
$L^{2}({\mathbf{G}}_{n})$. The second term in (49) can be written as

$\displaystyle\Bigg{\|}\sum_{i=1}^{\infty}{h}^{(0)}(\lambda_{i,n}^{\epsilon})(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}{\mathbf{P}}_{n}\bm{\phi}_{i}-\langle
f,\bm{\phi}_{i}\rangle_{\mathcal{M}}{\mathbf{P}}_{n}\bm{\phi}_{i})\Bigg{\|}$
$\displaystyle\leq\sum_{i=1}^{\infty}|{h}^{(0)}(\lambda_{i,n}^{\epsilon})|\left|\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}-\langle
f,\bm{\phi}_{i}\rangle_{\mathcal{M}}\right|\|{\mathbf{P}}_{n}\bm{\phi}_{i}\|.$
(52)

Because $\\{x_{1},x_{2},\cdots,x_{n}\\}$ is a set of uniform sampled points
from ${\mathcal{M}}$, based on Theorem 19 in [53] we can claim that

$\left|\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}-\langle
f,\bm{\phi}_{i}\rangle_{\mathcal{M}}\right|=O\left(\sqrt{\frac{\log
n}{n}}\right).$ (53)

Taking into consider the boundedness of frequency response
$|{h}^{(0)}(\lambda)|\leq 1$ and the bounded energy
$\|{\mathbf{P}}_{n}\bm{\phi}_{i}\|$. Therefore, we have

$\displaystyle\left\|\sum_{i=1}^{\infty}\hat{h}(\lambda_{i,n}^{\epsilon})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i,n}^{\epsilon}\rangle_{{\mathbf{G}}_{n}}-\langle
f,\bm{\phi}_{i}\rangle_{\mathcal{M}}\right){\mathbf{P}}_{n}\bm{\phi}_{i}\right\|=O\left(\sqrt{\frac{\log
n}{n}}\right).$

Combining the above results, we can bound the output difference of $h^{(0)}$.
Then we need to analyze the output difference of $h^{(l)}(\lambda)$ and bound
this as

$\displaystyle\left\|{\mathbf{P}}_{n}{\mathbf{h}}^{(l)}({\mathcal{L}})f-{\mathbf{h}}^{(l)}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f\right\|$
$\displaystyle\leq\left\|(\hat{h}(C_{l})+\gamma){\mathbf{P}}_{n}f-(\hat{h}(C_{l})-\gamma){\mathbf{P}}_{n}f\right\|\leq
2\gamma\|{\mathbf{P}}_{n}f\|,$ (54)

where ${\mathbf{h}}^{(l)}({\mathcal{L}})$ and
${\mathbf{h}}^{(l)}({\mathbf{L}}_{n}^{\epsilon})$ are filters with filter
function $h^{(l)}(\lambda)$ on the LB operator ${\mathcal{L}}$ and graph
Laplacian ${\mathbf{L}}_{n}^{\epsilon}$ respectively. Combining the filter
functions, we can write

$\displaystyle\|{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f-{\mathbf{h}}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f\|$
$\displaystyle=\Bigg{\|}{\mathbf{P}}_{n}{\mathbf{h}}^{(0)}({\mathcal{L}})f+{\mathbf{P}}_{n}\sum_{l\in{\mathcal{K}}_{m}}{\mathbf{h}}^{(l)}({\mathcal{L}})f-$
$\displaystyle\qquad\qquad\qquad{\mathbf{h}}^{(0)}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f-\sum_{l\in{\mathcal{K}}_{m}}{\mathbf{h}}^{(l)}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}f\Bigg{\|}$
(55)
$\displaystyle\leq\|{\mathbf{P}}_{n}{\mathbf{h}}^{(0)}({\mathcal{L}})f-{\mathbf{h}}^{(0)}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f\|+$
$\displaystyle\qquad\qquad\qquad\sum_{l\in{\mathcal{K}}_{m}}\|{\mathbf{P}}_{n}{\mathbf{h}}^{(l)}({\mathcal{L}})f-{\mathbf{h}}^{(l)}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f\|$
(56) $\displaystyle\leq
A_{h}\Omega_{1,K}\sqrt{\epsilon}+\frac{N_{s}\Omega_{2,K}}{\alpha}\sqrt{\epsilon}+N_{m}\gamma+C_{gc}\sqrt{\frac{\log(n)}{n}}$

With $\gamma=\Omega_{2,K}\sqrt{\epsilon}/\alpha$, we have

$\displaystyle\|{\mathbf{h}}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f-{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f\|$
$\displaystyle\qquad\leq\left(\frac{N\Omega_{2,K}}{\alpha}+A_{h}\Omega_{1,K}\right)\sqrt{\epsilon}+C_{gc}\sqrt{\frac{\log
n}{n}}$ (57)

We can prove Theorem 2 similarly by importing Proposition 4 into the
eigenvalue and eigenfunction differences.

Supplemental Materials

##  Appendix B Supplementary Materials

###  B-A Proof of Proposition 1

We decompose the operator difference between the graph Laplacian and the LB
operator with an intermediate term ${\mathbf{L}}^{\epsilon}$, which is the
functional approximation defined in (20). We first focus on the operator
difference between ${\mathbf{L}}^{\epsilon}$ and ${\mathcal{L}}$. From [45],
we can get the bound as

$\|{\mathbf{L}}^{\epsilon}\bm{\phi}_{i}-{\mathcal{L}}\bm{\phi}_{i}\|\leq
C\sqrt{\epsilon}\|\bm{\phi}_{i}\|_{H^{d/2+1}},$ (58)

For the Sobolev norm of eigenfunction $\bm{\phi}_{i}$, according to [54, Lemma
4.4] we have

$\|\bm{\phi}_{i}\|_{H^{d/2+1}}\leq C\lambda_{i}^{\frac{d+2}{4}},$ (59)

which leads to

$\|{\mathbf{L}}^{\epsilon}\bm{\phi}_{i}-{\mathcal{L}}\bm{\phi}_{i}\|\leq
C_{1}\sqrt{\epsilon}\lambda_{i}^{\frac{d+2}{4}}.$ (60)

For the operator difference between ${\mathbf{L}}_{n}^{\epsilon}$ and
${\mathbf{L}}^{\epsilon}$ with Hoeffding’s inequality as

$\displaystyle\mathbb{P}\left(|{\mathbf{L}}_{n}^{\epsilon}\bm{\phi}_{i}(x)-{\mathbf{L}}^{\epsilon}\bm{\phi}_{i}(x)|>\epsilon_{1}\right)\leq\exp\left(-\frac{2n\epsilon_{1}^{2}}{\|\bm{\phi}_{i}\|_{H^{d/2+1}}^{2}}\right).$
(61)

Therefore, we can claim that with probability at least $1-\delta$, we have

$\displaystyle|{\mathbf{L}}_{n}^{\epsilon}\bm{\phi}_{i}(x)-{\mathbf{L}}^{\epsilon}\bm{\phi}_{i}(x)|\leq\sqrt{\frac{\ln
1/\delta}{2n}}\|\bm{\phi}_{i}\|_{H^{d/2+1}}.$ (62)

Combining (60) and (62) with triangle inequality, we can get the conclusion in
Theorem 1.

###  B-B Proof of Proposition 2

We first import two lemmas to help prove the spectral properties.

###### Lemma 2

Let ${\mathbf{A}},{\mathbf{B}}$ be self-adjoint operators with
$\\{\lambda_{i}({\mathbf{A}}),{\mathbf{u}}_{i}\\}_{i=1}^{\infty}$ and
$\\{\lambda_{i}({\mathbf{B}}),{\mathbf{w}}_{i}\\}_{i=1}^{\infty}$ as the
corresponding spectrum. Let $Pr_{{\mathbf{w}}_{i}}$ be the orthogonal
projection operation onto the subspace generated by ${\mathbf{w}}_{i}$. Then
we have

$\|a_{i}{\mathbf{u}}_{i}-{\mathbf{w}}_{i}\|\leq
2\|{\mathbf{u}}_{i}-Pr_{{\mathbf{w}}_{i}}{\mathbf{u}}_{i}\|\leq\frac{2\|{\mathbf{B}}{\mathbf{u}}_{i}-{\mathbf{A}}{\mathbf{u}}_{i}\|}{\min_{j\neq
i}|\lambda_{j}({\mathbf{B}})-\lambda_{i}({\mathbf{A}})|}.$ (63)

###### Proof.

The first inequality is directly from [53, Proposition 18]. Let
$Pr^{\perp}_{{\mathbf{w}}_{i}}$ be the orthogonal projection onto the
complement of the subspace generated by ${\mathbf{w}}_{i}$. Then we have

$\displaystyle\|{\mathbf{u}}_{i}-Pr_{{\mathbf{w}}_{i}}{\mathbf{u}}_{i}\|=\|Pr_{{\mathbf{w}}_{i}}^{\perp}{\mathbf{u}}_{i}\|=\Big{\|}\sum_{j\neq
i}\langle{\mathbf{u}}_{i},{\mathbf{w}}_{j}\rangle{\mathbf{w}}_{j}\Big{\|}.$
(64)

Therefore, we have

$\displaystyle\|Pr_{{\mathbf{w}}_{i}}^{\perp}{\mathbf{B}}{\mathbf{u}}_{i}-Pr_{{\mathbf{w}}_{i}}^{\perp}{\mathbf{A}}{\mathbf{u}}_{i}\|$
$\displaystyle=\Big{\|}\sum_{j\neq
i}\langle{\mathbf{B}}{\mathbf{u}}_{i},{\mathbf{w}}_{j}\rangle{\mathbf{w}}_{j}-\sum_{j\neq
i}\langle{\mathbf{A}}{\mathbf{u}}_{i},{\mathbf{w}}_{j}\rangle{\mathbf{w}}_{j}\Big{\|}$
(65)
$\displaystyle=\Big{\|}\langle{\mathbf{u}}_{i},{\mathbf{B}}{\mathbf{w}}_{j}\rangle{\mathbf{w}}_{j}-\sum_{j\neq
i}\lambda_{i}({\mathbf{A}})\langle{\mathbf{u}}_{i},{\mathbf{w}}_{j}\rangle{\mathbf{w}}_{j}\Big{\|}$
(66) $\displaystyle=\Big{\|}\sum_{j\neq
i}(\lambda_{i}({\mathbf{B}})-\lambda_{i}({\mathbf{A}}))\langle{\mathbf{u}}_{i},{\mathbf{w}}_{j}\rangle{\mathbf{w}}_{j}\Big{\|}$
(67) $\displaystyle\geq\min_{j\neq
i}|\lambda_{i}({\mathbf{B}})-\lambda_{i}({\mathbf{A}})|\|\sum_{j\neq
i}\langle{\mathbf{u}}_{i},{\mathbf{w}}_{j}\rangle{\mathbf{w}}_{j}\|$ (68)
$\displaystyle=\min_{j\neq
i}|\lambda_{i}({\mathbf{B}})-\lambda_{i}({\mathbf{A}})|\|{\mathbf{u}}_{i}-Pr_{{\mathbf{w}}_{i}}{\mathbf{u}}_{i}\|,$
(69)

together with
$\|{\mathbf{B}}{\mathbf{u}}_{i}-{\mathbf{A}}{\mathbf{u}}_{i}\|\geq\|Pr_{{\mathbf{w}}_{i}}^{\perp}{\mathbf{B}}{\mathbf{u}}_{i}-Pr_{{\mathbf{w}}_{i}}^{\perp}{\mathbf{A}}{\mathbf{u}}_{i}\|$.
We can conclude the proof. ∎

The following lemma is adapted from [44, Lemma 5c]

###### Lemma 3

Let ${\mathbf{A}},{\mathbf{B}}$ be self-adjoint operators with
$\\{\lambda_{i}({\mathbf{A}}),{\mathbf{u}}_{i}\\}_{i=1}^{\infty}$ and
$\\{\lambda_{i}({\mathbf{B}}),{\mathbf{w}}_{i}\\}_{i=1}^{\infty}$ as the
corresponding spectrum. Then we have

$|\lambda_{i}({\mathbf{A}})-\lambda_{i}({\mathbf{B}})|=\frac{\langle({\mathbf{A}}-{\mathbf{B}}){\mathbf{u}}_{i},{\mathbf{w}}_{i}\rangle}{|\langle{\mathbf{u}}_{i},{\mathbf{w}}_{i}\rangle|}\leq\frac{\|({\mathbf{A}}-{\mathbf{B}}){\mathbf{u}}_{i}\|}{|\langle{\mathbf{u}}_{i},{\mathbf{w}}_{i}\rangle|}$
(70)

With the above lemmas and our proposed Theorem 1, which includes the operator
difference, we can prove Theorem 2. We first fix some $K\in\mathbb{N}$, wich
provides an upper bound for $\lambda_{i}\leq\lambda_{K}$ for all $1\leq i\leq
K$. By taking the probability $1-n^{-2}$ and $\epsilon=n^{-1/(d+4)}$, we can
conclude that the operator difference in Theorem 1 can be bounded with order
$O(\sqrt{\epsilon})$, with the constant scaling with
$\lambda_{K}^{\frac{d+2}{4}}$. Combine with Lemma 2 and $\theta=\min_{1\leq
j\neq i\leq K}|\lambda_{j}-\lambda_{i,n}^{\epsilon}|$, we can get

$\|a_{i}\bm{\phi}_{i,n}^{\epsilon}-\bm{\phi}_{i}\|\leq\frac{C_{k}}{\theta}\sqrt{\epsilon},$
(71)

where we denote the constant as $\Omega_{1}$ to include the effects of $K$,
the eigengap and the volume of ${\mathcal{M}}$.

This upper bound of the eigenfunction difference leads to
$|\langle{\mathbf{u}}_{i},{\mathbf{w}}_{i}\rangle|\geq
1-\Omega_{1}/2\sqrt{\epsilon}\geq 1$. Combining with Lemma 3, the difference
of the eigenvalues can also be bounded in the order of $O(\sqrt{\epsilon})$.

###  B-C Proof of Theorem 3

To bound the output difference of MNNs, we need to write in the form of
features of the final layer

$\displaystyle\|\bm{\Phi}({\mathbf{H}},{\mathbf{L}}_{n}^{\epsilon},{\mathbf{P}}_{n}f)-{\mathbf{P}}_{n}\bm{\Phi}$
$\displaystyle({\mathbf{H}},{\mathcal{L}},f))\|=\left\|\sum_{q=1}^{F_{L}}{\mathbf{x}}_{n,L}^{q}-\sum_{q=1}^{F_{L}}{\mathbf{P}}_{n}f_{L}^{q}\right\|$
$\displaystyle\leq\sum_{q=1}^{F_{L}}\left\|{\mathbf{x}}_{n,L}^{q}-{\mathbf{P}}_{n}f_{L}^{q}\right\|.$
(72)

By inserting the definitions, we have

$\displaystyle\left\|{\mathbf{x}}_{n,l}^{p}-{\mathbf{P}}_{n}f_{l}^{p}\right\|$
$\displaystyle=\left\|\sigma\left(\sum_{q=1}^{F_{l-1}}{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{x}}_{n,l-1}^{q}\right)-{\mathbf{P}}_{n}\sigma\left(\sum_{q=1}^{F_{l-1}}{\mathbf{h}}_{l}^{pq}({\mathcal{L}})f_{l-1}^{q}\right)\right\|$
(73)

with ${\mathbf{x}}_{n,0}={\mathbf{P}}_{n}f$ as the input of the first layer.
With a normalized point-wise Lipschitz nonlinearity, we have

$\displaystyle\|{\mathbf{x}}_{n,l}^{p}-{\mathbf{P}}_{n}f_{l}^{p}$
$\displaystyle\|\leq\left\|\sum_{q=1}^{F_{l-1}}{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{x}}_{n,l-1}^{q}-{\mathbf{P}}_{n}\sum_{q=1}^{F_{l-1}}{\mathbf{h}}_{l}^{pq}({\mathcal{L}})f_{l-1}^{q}\right\|$
(74)
$\displaystyle\leq\sum_{q=1}^{F_{l-1}}\left\|{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{x}}_{n,l-1}^{q}-{\mathbf{P}}_{n}{\mathbf{h}}_{l}^{pq}({\mathcal{L}})f_{l-1}^{q}\right\|$
(75)

The difference can be further decomposed as

$\displaystyle\|{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon})$
$\displaystyle{\mathbf{x}}_{n,l-1}^{q}-{\mathbf{P}}_{n}{\mathbf{h}}_{l}^{pq}({\mathcal{L}})f_{l-1}^{q}\|$
$\displaystyle\leq\|{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{x}}_{n,l-1}^{q}-{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f_{l-1}^{q}$
$\displaystyle\qquad+{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f_{l-1}^{q}-{\mathbf{P}}_{n}{\mathbf{h}}_{l}^{pq}({\mathcal{L}})f_{l-1}^{q}\|$
(76)
$\displaystyle\leq\left\|{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{x}}_{n,l-1}^{q}-{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f_{l-1}^{q}\right\|$
$\displaystyle\qquad+\left\|{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f_{l-1}^{q}-{\mathbf{P}}_{n}{\mathbf{h}}_{l}^{pq}({\mathcal{L}})f_{l-1}^{q}\right\|$
(77)

The second term can be bounded with
$\|{\mathbf{h}}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{P}}_{n}f-{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f\|_{L^{2}({\mathbf{G}}_{n})}\leq\Delta_{fil,n}$.
The first term can be decomposed by Cauchy-Schwartz inequality and non-
amplifying of the filter functions as

$\displaystyle\left\|{\mathbf{x}}_{n,l}^{p}-{\mathbf{P}}_{n}f_{l}^{p}\right\|\leq\sum_{q=1}^{F_{l-1}}\Delta_{fil,n}\|{\mathbf{x}}_{n,l-1}^{q}\|+\sum_{q=1}^{F_{l-1}}\|{\mathbf{x}}_{l-1}^{q}-{\mathbf{P}}_{n}f_{l-1}^{q}\|,$
(78)

where $C_{per}$ representing the constant in the error bound of manifold
filters in (2). To solve this recursion, we need to compute the bound for
$\|{\mathbf{x}}_{l}^{p}\|$. By normalized Lipschitz continuity of $\sigma$ and
the fact that $\sigma(0)=0$, we can get

$\displaystyle\|{\mathbf{x}}_{l}^{p}\|\leq\left\|\sum_{q=1}^{F_{l-1}}{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon}){\mathbf{x}}_{l-1}^{q}\right\|\leq\sum_{q=1}^{F_{l-1}}\left\|{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{n}^{\epsilon})\right\|\|{\mathbf{x}}_{l-1}^{q}\|$
$\displaystyle\qquad\leq\sum_{q=1}^{F_{l-1}}\|{\mathbf{x}}_{l-1}^{q}\|\leq\prod\limits_{l^{\prime}=1}^{l-1}F_{l^{\prime}}\sum_{q=1}^{F_{0}}\|{\mathbf{x}}^{q}\|.$
(79)

Insert this conclusion back to solve the recursion, we can get

$\displaystyle\left\|{\mathbf{x}}_{n,l}^{p}-{\mathbf{P}}_{n}f_{l}^{p}\right\|\leq
l\Delta_{fil,n}\left(\prod\limits_{l^{\prime}=1}^{l-1}F_{l^{\prime}}\right)\sum_{q=1}^{F_{0}}\|{\mathbf{x}}^{q}\|.$
(80)

Replace $l$ with $L$ we can obtain

$\displaystyle\|\bm{\Phi}({\mathbf{H}},{\mathbf{L}}_{n}^{\epsilon},{\mathbf{P}}_{n}f)-{\mathbf{P}}_{n}\bm{\Phi}({\mathbf{H}},{\mathcal{L}},f))\|$
$\displaystyle\qquad\qquad\leq\sum_{q=1}^{F_{L}}\left(L\Delta_{fil,n}\left(\prod\limits_{l^{\prime}=1}^{L-1}F_{l^{\prime}}\right)\sum_{q=1}^{F_{0}}\|{\mathbf{x}}^{q}\|\right).$
(81)

With $F_{0}=F_{L}=1$ and $F_{l}=F$ for $1\leq l\leq L-1$, then we have

$\displaystyle\|\bm{\Phi}({\mathbf{H}},{\mathbf{L}}_{n}^{\epsilon},{\mathbf{P}}_{n}f)-{\mathbf{P}}_{n}\bm{\Phi}({\mathbf{H}},{\mathcal{L}},f))\leq
LF^{L-1}\Delta_{fil,n},$ (82)

which concludes the proof.