# Convolutional Filtering on Sampled Manifolds

###### Abstract

The increasing availability of geometric data has motivated the need for
information processing over non-Euclidean domains modeled as manifolds. The
building block for information processing architectures with desirable
theoretical properties such as invariance and stability is convolutional
filtering. Manifold convolutional filters are defined from the manifold
diffusion sequence, constructed by successive applications of the Laplace-
Beltrami operator to manifold signals. However, the continuous manifold model
can only be accessed by sampling discrete points and building an approximate
graph model from the sampled manifold. Effective linear information processing
on the manifold requires quantifying the error incurred when approximating
manifold convolutions with graph convolutions. In this paper, we derive a non-
asymptotic error bound for this approximation, showing that convolutional
filtering on the sampled manifold converges to continuous manifold filtering.
Our findings are further demonstrated empirically on a problem of navigation
control.

Index Terms—  Manifold filter, manifold signal processing, Laplace-Beltrami
operator, graph Laplacian

##  1 Introduction

Applications involving structured data in non-Euclidean domains are attracting
more and more attention these days, including but not limited to robot
coordination [1, 2], resource allocation over wireless networks [3] and 3D
shape analysis [4, 5]. Graph convolutional filtering [6, 7] and manifold
convolutional filtering [8, 9] have become the top choices to process
information over these non-Euclidean domains. This can be attributed to the
fact that the convolution operation consists of local diffusions over the
geometric structure, which capture features that are shared across the whole
domain. Moreover, convolutional filtering provides the fundamental block for
constructing deep learning architectures, which are powerful models [10] to
solve a wide range of geometric problems.

Unlike graphs, which are discrete objects, manifolds are not directly
accessible in general because they are infinite-dimensional continuous spaces
[4, 8]. Instead, we typically have access to a set of points sampled from the
manifold, or a _sampled manifold_. In many manifold problems, a _graph_
capturing both the local and global connection structure is built from this
sampled manifold to approximate the underlying continuous manifold [11, 3]
(herein, we use the terms _sampled manifold_ and _graph_ interchangeably).
Convolutional filters constructed on graphs have been used to approximately
process information over the manifold, which has been supported both
experimentally and theoretically [10, 12, 8]. However, an explicit non-
asymptotic theoretical result closing the gap between graph convolutional
filtering and manifold convolutional filtering is still lacking.

Contributions. In this paper, we define manifold filtering as a convolutional
operation based on diffusions that are defined as exponentials of the Laplace-
Beltrami (LB) operator ${\mathcal{L}}$ of the embedded manifold
${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ [8]. Graphs are constructed by
sampling a set of points uniformly over the manifold, with edge weights given
by application of a Gaussian kernel. Denoting the graph Laplacian
${\mathbf{L}}_{n}^{\epsilon}$, we derive upper bounds for both the operator
norm difference and the difference between the spectra of the graph Laplacian
${\mathbf{L}}_{n}^{\epsilon}$ and the LB operator ${\mathcal{L}}$. Then, to
deal with the infinite dimensional spectrum and the sharp variations in the
high frequency domain of LB operator ${\mathcal{L}}$, we import the definition
of the Frequency Difference Threshold (FDT) filters (Definition 2) [13] to
separate the spectrum into finite eigenvalue partitions. Finally, we show that
when applying FDT filters to graphs sampled from the manifold, graph filtering
converges to the manifold filtering with a non-asymptotic approximation bound
in the order of $n^{-1/(2d+8)}$ (Theorem 3).

Related Works. Graph convolutional filtering has been thoroughly discussed in
previous works [6, 14, 7]. A large number of works have studied the
convergence of graph filters, such as [15] and [16] which consider graphs that
are dense or relatively sparse, and which are both sampled from a graphon
model. Unlike the graphon, the manifold is more realistic and can be seen as a
limit for graphs that have finite degree [17]. Convolutional filtering in
manifolds has been discussed in [8, 9, 12], with different definitions
depending on how the graphs are sampled from manifolds. The connection between
graph filtering and manifold filtering has been discussed in [8]. In this
paper, it is proved that manifold filtering can recover graph filtering by
discretization in both the space and time domains; and that filtering on
graphs sampled from the manifold converges to manifold filtering. However,
there are no theoretical convergence rates. In the present paper, we extend
upon the results of [8] by proving a non-asymptotic approximation bound for
graph filters sampled from manifold filters.

##  2 Preliminary definitions

In order to relate graph filters and manifold filters, we start by reviewing
the basic setup as well as the graph signal processing and manifold signal
processing frameworks.

###  2.1 Graph signal processing: graph filters

We consider an undirected graph
${\mathbf{G}}=({\mathcal{V}},{\mathcal{E}},{\mathcal{W}})$ with
${\mathcal{V}},|{\mathcal{V}}|=n$, representing the set of nodes and
${\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$ the set of edges. The
weight function ${\mathcal{W}}:{\mathcal{E}}\rightarrow{\mathbb{R}}$ assigns
weights to the edges. Graph signals ${\mathbf{x}}\in{\mathbb{R}}^{n}$ are
defined as data supported on the graph, with the $i$-th element $x_{i}$
representing the datum at node $i$ [6, 14].

The so-called graph shift operator (GSO) ${\mathbf{S}}\in{\mathbb{R}}^{n\times
n}$ is typically selected to be the Laplacian matrix, the normalized Laplacian
or the adjacency matrix, which encodes the graph sparsity pattern. The
application of the GSO to a graph signal leads to a diffusion of the data over
the edges. Specifically, for each node $i$, the GSO diffuses the signals on
the neighboring nodes $x_{j}$ scaled with the proximity measure
$[{\mathbf{S}}]_{ij}$ to this node $i$. I.e.
$[{\mathbf{S}}{\mathbf{x}}]_{i}=\sum_{j,(i,j)\in{\mathcal{E}}}[{\mathbf{S}}]_{ij}x_{j}$.
Based on this notion of diffusion, we can then define graph convolutional
filters as a shift-and-sum operation

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

where $\\{h_{k}\\}_{k=0}^{K-1}$ are the filter coefficients [7, 6].

For an undirected graph ${\mathbf{G}}$, the GSO is symmetric and thus can be
diagonalized as ${\mathbf{S}}={\mathbf{V}}\bm{\Lambda}{\mathbf{V}}^{H}$, with
$\bm{\Lambda}$ containing the graph eigenvalues and ${\mathbf{V}}$ the graph
eigenvectors. By replacing the GSO by its eigendecomposition, we can thus
write the spectral representation of the graph convolution as

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

The frequency response of graph convolution can therefore be written as
$h(\lambda)=\sum_{k=0}^{K-1}h_{k}\lambda^{k}$, which only depends on the
coefficients $h_{k}$ and the eigenvalues of ${\mathbf{S}}$.

###  2.2 Manifold signal processing: manifold filters

We consider a compact smooth differentiable $d$-dimensional submanifold
${\mathcal{M}}$ embedded in some Euclidean space ${\mathbb{R}}^{\mathsf{N}}$,
and a measure $\mu$ over the manifold ${\mathcal{M}}$. Manifold signals are
defined as scalar functions $f:{\mathcal{M}}\rightarrow{\mathbb{R}}$ supported
on ${\mathcal{M}}$. The inner product of functions $f,g\in
L^{2}({\mathcal{M}})$ can be defined as

$\langle
f,g\rangle_{L^{2}({\mathcal{M}})}=\int_{\mathcal{M}}f(x)g(x)\text{d}\mu(x)$
(3)

with $\text{d}\mu(x)$ representing the volume element with respect to measure
$\mu$. Therefore, the energy of manifold signal $f$ is naturally given as
$\|f\|^{2}_{L^{2}({\mathcal{M}})}={\langle
f,f\rangle_{L^{2}({\mathcal{M}})}}$. We consider manifold signals with finite
energy, i.e., $f\in L^{2}({\mathcal{M}})$.

The manifold 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 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}}$ [10]. 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}})$ can be defined as
the intrinsic divergence of the intrinsic gradient [18]. More formally,

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

The LB operator measures the difference between the function value at a point
and the average function value over the point’s neighborhood [10], similar to
graph Laplacian matrix.

The manifold convolution of ${\tilde{h}}:{\mathbb{R}}^{+}\to{\mathbb{R}}$ and
the manifold signal $f\in L^{2}({\mathcal{M}})$ is called a manifold filter
with impulse response ${\tilde{h}}$, and is defined by leveraging the heat
diffusion dynamics [8]. Explicitly, this filter, denoted ${\mathbf{h}}$, is
given by

$\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{.}$
(5)

This is a spatial manifold convolution operator because it is parametrized by
the operator ${\mathcal{L}}$ and directly operates on points
$x\in{\mathcal{M}}$.

The LB operator ${\mathcal{L}}$ is self-adjoint and positive-semidefinite.
These facts, together with the compactness of ${\mathcal{M}}$, imply that
${\mathcal{L}}$ has a real, positive and discrete eigenvalue spectrum
$\\{\lambda_{i}\\}_{i=1}^{\infty}$ such that
${\mathcal{L}}\bm{\phi}_{i}=\lambda_{i}\bm{\phi}_{i}$, where $\bm{\phi}_{i}$
is the eigenfunction associated with eigenvalue $\lambda_{i}$. The eigenvalues
are ordered in increasing order as
$0<\lambda_{1}\leq\lambda_{2}\leq\lambda_{3}\leq\ldots$. The eigenfunctions
are orthonormal and thus form an eigenbasis of $L^{2}({\mathcal{M}})$ in the
intrinsic sense.

Denoting $[\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)$
and $e^{-t{\mathcal{L}}}\bm{\phi}_{i}=e^{-t\lambda_{i}}\bm{\phi}_{i}$, 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{.}$
(6)

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 depends only on the function $\tilde{h}$ and on the eigenvalues of the
LB operator. Summing over all $i$, we thus get

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

##  3 Convergence of filtering on sampled manifolds

Our goal is to derive a non-asymptotic approximation bound for manifold
filtering on sampled manifolds, providing theoretical guarantees when the
sampled manifold is modeled as a graph and showing that graph filtering can be
used to approximate manifold filtering. We start by constructing the graph
corresponding to the sampled manifold.

###  3.1 Sampled manifolds as graphs

Let $X=\\{x_{1},x_{2},\ldots x_{n}\\}$ be a set of $n$ points sampled
uniformly and independently at random from the $d$-dimensional manifold
${\mathcal{M}}$ according to measure $\mu$. The empirical measure associated
with $\text{d}\mu$ is $p_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}$, where
$\delta_{x_{i}}$ is the Dirac measure supported on $x_{i}$. Similar to the
definition of inner product in $L^{2}({\mathcal{M}})$ (3), the inner product
in $L^{2}({\mathbf{G}}_{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}).$ (8)

The norm in $L^{2}({\mathbf{G}}_{n})$ with measure $p_{n}$ is therefore

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

for $u,v\in L^{2}({\mathcal{M}})$. 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}.$

From $X$, we construct an undirected graph ${\mathbf{G}}_{n}$ by seeing the
sampled points as nodes. The weights of the edges connecting nodes $x_{i}$ and
$x_{j}$ are determined by

$w_{ij}=\frac{1}{n}\frac{1}{\epsilon(4\pi\epsilon)^{d/2}}\exp\left(-\frac{\|x_{i}-x_{j}\|^{2}}{4\epsilon}\right),$
(9)

where $\|x_{i}-x_{j}\|$ stands for the Euclidean distance between points
$x_{i}$ and $x_{j}$ and $\epsilon$ is a parameter related to the Gaussian
kernel [19]. The adjacency matrix ${\mathbf{A}}_{n}\in{\mathbb{R}}^{n\times
n}$ can be written as $[{\mathbf{A}}_{n}]_{ij}=w_{ij}$ for $1\leq i,j\leq n$.
Thus, the graph Laplacian associated with this graph can be written as

${\mathbf{L}}^{\epsilon}_{n}=\mbox{diag}({\mathbf{A}}_{n}\bm{1})-{\mathbf{A}}_{n}$

with $[{\mathbf{L}}^{\epsilon}_{n}]_{ij}=-w_{ij}$ if $i\neq j$ and
$[{\mathbf{L}}^{\epsilon}_{n}]_{ii}=\sum_{k=1}^{n}w_{ik}$ [20].

To discretize manifold signals $f\in L^{2}({\mathcal{M}})$ on the sampled
manifold, we define a uniform sampling operator
${\mathbf{P}}_{n}:L^{2}({\mathcal{M}})\rightarrow L^{2}({\mathbf{G}}_{n})$
yielding signals ${\mathbf{f}}\in L^{2}({\mathbf{G}}_{n})$ defined explicitly
as

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

This indicates that ${\mathbf{f}}$ shares the function values of the manifold
signal $f$ at the sample points $X$. Seeing the graph Laplacian as an operator
acting on ${\mathbf{f}}:X\to{\mathbb{R}}$, we can write the diffusion
operation on each point $x$ explicitly as

${\mathbf{L}}^{\epsilon}_{n}{\mathbf{f}}(x_{i})=\sum_{j=1}^{n}w_{ij}\left({\mathbf{f}}(x_{i})-{\mathbf{f}}(x_{j})\right),\quad
i=1,2,\ldots n.$ (11)

It can be seen that this formulation can extend to a continuous manifold
signal $f$, which we denote as

${\mathbf{L}}^{\epsilon}_{n}f(x)=\frac{1}{n}\frac{1}{\epsilon(4\pi\epsilon)^{d/2}}\sum_{j=1}^{n}\left(f(x)-f(x_{j})\right)e^{-\frac{\|x-x_{j}\|^{2}}{4\epsilon}},\;x\in{\mathcal{M}}.$
(12)

If we further extend the set of sample points from $X$ to all the points on
the manifold, we finally get the functional approximation of the graph
Laplacian,

${\mathbf{L}}^{\epsilon}f(x)=\frac{1}{n}\frac{1}{\epsilon(4\pi\epsilon)^{d/2}}\int_{\mathcal{M}}\left(f(x)-f(y)\right)e^{-\frac{\|x-y\|^{2}}{4\epsilon}}\text{d}\mu(y),$
(13)

which operates on all $x\in{\mathcal{M}}$.

###  3.2 Graph Laplacian approximation of the LB operator

We first demonstrate the consistency of the discrete graph Laplacians defined
in (12) when operating on the eigenfunctions $\bm{\phi}_{i}\in
L^{2}({\mathcal{M}})$ of the LB operator ${\mathcal{L}}$. The quality of the
approximation given by the discrete Laplace operator on the sampled manifold
is quantified by the following non-asymptotic result.

######  Theorem 1.

Let ${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ be a compact smooth
differentiable $d$-dimensional manifold with LB operator ${\mathcal{L}}$,
whose spectrum is given by $\\{\lambda_{i},\bm{\phi}_{i}\\}_{i=1}^{\infty}$,
and assume $\bm{\phi}_{i}\in C({\mathcal{M}})$. Let ${\mathbf{G}}_{n}$ be the
discrete graph connecting points $\\{x_{1},x_{2},\ldots,x_{n}\\}$ sampled
uniformly and independently at random from ${\mathcal{M}}$, with edge weights
as in (9) and $\epsilon=\epsilon(n)>n^{-1/(d+4)}$. Then, it 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}}+C_{2}\sqrt{\epsilon}\right)\lambda_{i}^{\frac{d+2}{4}},$
(14)

with probability at least $1-\delta$. The constants $C_{1}$, $C_{2}$ depend on
the volume of the manifold.

###### Proof.

See Appendix A.1. ∎

This theorem provides a point-wise upper bound for the error incurred when
using the discrete graph Laplacian to approximate the LB operator operating on
the eigenfunctions of ${\mathcal{L}}$. We can see that this bound is not only
related to the number of sampling points $n$, but also grows with the
corresponding eigenvalue $\lambda_{i}$. This makes sense considering that
higher eigenvalues correspond to eigenfunctions with high oscillation [21].

Based on this approximation result, we can further derive a non-asymptotic
approximation bound relating the spectra of the graph Laplacian and the LB
operator using the Davis-Khan theorem [22]. This result, stated in Theorem 2,
will allows us to analyze the approximation of a manifold filter by a graph
filter through their spectral representations.

######  Theorem 2.

Let ${\mathcal{M}}\subset{\mathbb{R}}^{\mathsf{N}}$ be a compact smooth
differentiable $d$-dimensional manifold with LB operator ${\mathcal{L}}$ whose
spectrum is given by $\\{\lambda_{i},\bm{\phi}_{i}\\}_{i=1}^{\infty}$. Let
${\mathbf{L}}_{n}^{\epsilon}$ be a discrete graph Laplacian defined as in (12)
with $\\{x_{1},x_{2},\ldots,x_{n}\\}$ sampled uniformly and independently at
random from ${\mathcal{M}}$ whose spectrum is given by
$\\{\lambda_{i,n}^{\epsilon},\bm{\phi}_{i,n}^{\epsilon}\\}_{i=1}^{n}$. Fix
$K\in\mathbb{N}$ and asumme that $n$ is sufficiently large so that
$\epsilon=\epsilon(n)>n^{-1/(d+4)}$. Then, with probability at least
$1-2e^{-n}$, we have

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

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

###### Proof.

See Appendix A.2. ∎

###  3.3 Graph filtering approximation of manifold filtering

Equipped with theoretical approximation results for both the eigenvalues and
eigenfunctions of the Laplacian operators, we can now prove that graph filters
can approximate manifold filters well in the spectral domain. We first show
that we can generalize the definition of manifold convolutional filters to
sampled manifolds using the same impulse response $\tilde{h}$.

From the definition in (5), recall that the manifold filter is parametric on
the LB operator when the impulse response $\tilde{h}(t)$ is fixed. By
replacing the LB operator with the discrete graph Laplacian defined in (12),
we can then obtain a graph convolutional filter

${\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}.$
(16)

This can be seen as a continuous-time graph filtering process, different from
the discrete-time graph filtering process ${\mathbf{h}}_{\mathbf{G}}$ in (1),
where the exponential term $e^{-{\mathbf{L}}_{n}^{\epsilon}}$ can be seen as
the graph shift operator. The frequency representation of this 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},$
(17)

which reveals the full dependency on the eigendecomposition of
${\mathbf{L}}_{n}^{\epsilon}$. Thus, we can relate graph filtering and
manifold filtering using the spectral approximation results for the graph
Laplacian and LB operator presented in Theorem 2.

Unlike the finite spectrum of the graph Laplacian, the LB operator
${\mathcal{L}}$ possesses an infinite spectrum. We consider Weyl’s law [23]
when analyzing the spectral properties of ${\mathcal{L}}$. This classical
result states that the eigenvalues $\lambda_{i}$ of ${\mathcal{L}}$ grow in
the order of $i^{2/d}$. Therefore, the difference between neighboring
eigenvalues becomes quite small in the high frequency spectrum, i.e., large
eigenvalues accumulate. Leveraging this fact, we can use a partition strategy
to separate the spectrum into finite groups as in Definition 1.

######  Definition 1.

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

The following defined $\alpha$-FDT filter allows obtaining the
$\alpha$-separated spectrum as in Definition 1.

######  Definition 2.

[13] ($\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)$ (18)

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

To derive an approximation bound, we will also need the manifold filter to
have a Lipschitz frequency response as in Definition 3.

######  Definition 3 (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{.}$ (19)

Equipped with the above requirements for the filter frequency response, we can
finally establish the upper bound on the manifold filter approximation error
on the sampled manifold.

######  Theorem 3.

Let $X=\\{x_{1},x_{2},...x_{n}\\}$ be a set of $n$ points sampled by an
operator ${\mathbf{P}}_{n}$ (10) from a $d$-dimensional manifold
${\mathcal{M}}\subset{\mathbb{R}}^{N}$. Let ${\mathbf{G}}_{n}$ be a discrete
graph approximation of ${\mathcal{M}}$ constructed from $X$ with weight values
as in (9) with $\epsilon=\epsilon(n)\geq n^{-1/(d+4)}$. Let
${\mathbf{h}}(\cdot)$ be the convolutional filter parameterized by the LB
operator ${\mathcal{L}}$ of the manifold ${\mathcal{M}}$ (5) or by the
discrete graph Laplacian operator ${\mathbf{L}}_{n}^{\epsilon}$ of the graph
${\mathbf{G}}_{n}$. Under the assumption that the frequency response of filter
${\mathbf{h}}$ is Lipschitz continuous and $\alpha$-FDT with
$\alpha^{2}\gg\epsilon$ and
$\gamma=\Omega_{2}^{\prime}\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\qquad\qquad\leq\left(\frac{N\Omega_{2}^{\prime}}{\alpha}+A_{h}\Omega_{1}\right)\sqrt{\epsilon}+C_{gc}\sqrt{\frac{\log
n}{{n}}}$ (20)

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

###### Proof.

See Appendix A.3. ∎

From this theorem, we see that if we take $\epsilon=n^{-1/(d+4)}$, the
difference between filtering on the manifold and the sampled manifold is in
the order of $O(n^{-1/(2d+8)})$. Thus, with a large enough number of sampling
points, this approximation provides a good accuracy with high probability.
This provides a formal theoretical guarantee for the ability of graph filters
to approximate manifold filters on sampled manifolds, enabling approximate
linear information processing on continuous non-Euclidean domains.

##  4 Numerical experiments

We consider a problem of automatic navigation control of an agent [24]. We
intend to control an agent to find a path to the goal without colliding to
obstacles. We sample grid points over the free space which means avoiding the
obstacle areas to construct a graph structure. We generate four trajectories
with Dijkstra’s shortest path algorithm leading a starting point to the goal.
Each point along the trajectory is labeled with the direction of the velocity.
The adjacency matrix can be calculated based on the weight value defined in
(9) with the Euclidean distance between each two points. We note that if the
direct path between two points goes through the obstacles, we set the distance
between them as infinity, i.e. the weight value as zero, so as to better
capture the geometric structure. The input graph signal is the position of the
nodes and the output of the graph filter is the direction of this node leading
to the goal. We construct a one-layer and two-layer graph filters with $5$
filter taps in each layer. We train all the architectures for $30,000$ epochs
with SGD optimizer with the learning rate set as $0.0002$. The performance of
the learned graph filter is testified by randomly generating $100$ starting
points and computing the trajectories. If the trajectory can reach the goal
without colliding into the obstacles, the trajectory is marked as “success”.

(a) Training dataset

(b) Learned direction

Fig. 1: Graph filtering performance with $n=413$

(a) Training dataset

(b) Learned direction

Fig. 2: Graph filtering performance with $n=1117$

We first sample $n$ points uniformly over the free space avoiding the black
obstacles as shown in Fig. 1(a) ($n=413$) and Fig. 2(a) ($n=1117$). In Fig.
1(a) and Fig. 2(a), the red stars depicting labeled points as training dataset
and the blue arrows attached to the red stars point to the optimal directions
leading to the goal. The blue stars depict unlabeled points over the free
space. We implement a 1-layer or 2-layer graph filters to learn and estimate
the directions for all the unlabeled points. Figure 1(b) and 2(b) show the
learned directions starting from each unlabeled points as the red arrows show
using graph filtering. The numbers of successful trajectories within $100$
generated testing are shown in Table 1. We can see that graph filtering can
efficiently learn the potential successful trajectories for unlabeled points
based on these sampled manifolds. More sampling points characterize the free
space more accurately, which leads to more successful testing trajectories.
This is also in accordance with our theoretical result presented in Theorem 3.
Moreover, more layers of filters also learn a more accurate prediction.

| $n=413$ | $n=1117$
---|---|---
1-layer graph filter | 74 | 75
2-layer graph filter | 79 | 84
Table 1: Number of successful trajectories.

##  5 Conclusions

In this paper, we introduced manifold convolutional filters defined with the
exponential Laplace-Beltrami operator to process geometric data. To access the
manifold model, we sample uniformly over the manifold and construct a graph
model as a sampled manifold. We first prove the non-asymptotic approximation
error bound of discrete graph Laplacian to LB operator in both operator and
spectral aspects. By transferring the manifold filtering to the sampled
manifold, the approximation of the graph filtering to the manifold filtering
can be derived. The non-asymptotic error bound decreases with the number of
sampling points growing. The approximation of graph filtering is verified
empirically on a navigation control problem over a manifold.

## References

  * [1] 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.
  * [2] Z. Wang and M. Gombolay, “Learning scheduling policies for multi-robot coordination with graph attention networks,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 3, pp. 4509–4516, 2020.
  * [3] 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.
  * [4] 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.
  * [5] 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.
  * [6] 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.
  * [7] 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.
  * [8] Z. Wang, L. Ruiz, and A. Ribeiro, “Convolutional neural networks on manifolds: From graphs and back,” _arXiv preprint arXiv:2210.00376_ , 2022.
  * [9] 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.
  * [10] 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.
  * [11] 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.
  * [12] 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.
  * [13] Z. Wang, L. Ruiz, and A. Ribeiro, “Stability of neural networks on riemannian manifolds,” in _2021 29th European Signal Processing Conference (EUSIPCO)_. IEEE, 2021, pp. 1845–1849.
  * [14] 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.
  * [15] 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.
  * [16] 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.
  * [17] 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.
  * [18] S. Rosenberg and R. Steven, _The Laplacian on a Riemannian manifold: an introduction to analysis on manifolds_. Cambridge University Press, 1997, no. 31.
  * [19] 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.
  * [20] R. Merris, “A survey of graph laplacians,” _Linear and Multilinear Algebra_ , vol. 39, no. 1-2, pp. 19–31, 1995.
  * [21] 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.
  * [22] Y. Yu, T. Wang, and R. J. Samworth, “A useful variant of the davis–kahan theorem for statisticians,” _Biometrika_ , vol. 102, no. 2, pp. 315–323, 2015.
  * [23] W. Arendt, R. Nittka, W. Peter, and F. Steiner, “Weyl’s law: Spectral properties of the laplacian in mathematics and physics,” _Mathematical analysis of evolution, information, and complexity_ , pp. 1–71, 2009.
  * [24] J. Cervino, L. Chamon, B. D. Haeffele, R. Vidal, and A. Ribeiro, “Learning globally smooth functions on manifolds,” _arXiv preprint arXiv:2210.00301_ , 2022.
  * [25] M. Belkin and P. Niyogi, “Convergence of laplacian eigenmaps,” _Advances in neural information processing systems_ , vol. 19, 2006.
  * [26] U. Von Luxburg, M. Belkin, and O. Bousquet, “Consistency of spectral clustering,” _The Annals of Statistics_ , pp. 555–586, 2008.
  * [27] 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\.

##  Appendix A Appendix

###  A.1 Proof of Theorem 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 (13). We first focus on the operator
difference between ${\mathbf{L}}^{\epsilon}$ and ${\mathcal{L}}$. From [19],
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}},$ (21)

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

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

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}}.$ (23)

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).$
(24)

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}}.$ (25)

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

###  A.2 Proof of Theorem 2

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

######  Lemma 1.

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}})|}.$ (26)

###### Proof.

The first inequality is directly from [26, 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{\|}.$
(27)

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{\|}$
(28)
$\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{\|}$
(29) $\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{\|}$
(30) $\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}\|$ (31)
$\displaystyle=\min_{j\neq
i}|\lambda_{i}({\mathbf{B}})-\lambda_{i}({\mathbf{A}})|\|{\mathbf{u}}_{i}-Pr_{{\mathbf{w}}_{i}}{\mathbf{u}}_{i}\|,$
(32)

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 [27, Lemma 5c]

######  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. 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|}$
(33)

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 1 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},$
(34)

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 2, the difference
of the eigenvalues can also be bounded in the order of $O(\sqrt{\epsilon})$.

###  A.3 Proof of Theorem 3

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}-\sum_{i=1}^{\infty}\hat{h}(\lambda_{i})\langle
f,\bm{\phi}_{i}\rangle_{{\mathcal{M}}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right\|$
(35)

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.$ (38) $\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.$ (42)

With the triangle inequality, we start by analyzing the output difference of
$h^{(0)}(\lambda)$ as

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

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

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

The first term is bounded as

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

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

$\displaystyle\Bigg{\|}\sum_{i=1}^{N_{s}}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i}^{n}-\langle
f,\bm{\phi}_{i}\rangle_{{\mathcal{M}}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right)\Bigg{\|}$
$\displaystyle\leq\Bigg{\|}\sum_{i=1}^{N_{s}}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i}^{n}-\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\rangle_{{\mathbf{G}}_{n}}{\mathbf{P}}_{n}\bm{\phi}_{i}\right)\Bigg{\|}$
$\displaystyle+\left\|\sum_{i=1}^{N_{s}}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\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\|$
(47)

From the convergence stated in Theorem 2, we have

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

Therefore, the first term in (47) can be bounded as

$\displaystyle\left\|\sum_{i=1}^{N_{s}}{h}^{(0)}(\lambda_{i})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\rangle_{{\mathbf{G}}_{n}}\bm{\phi}_{i}^{n}-\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\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}-{\mathbf{P}}_{n}\bm{\phi}_{i}\|\leq
N_{s}\Omega_{2}\sqrt{\epsilon}.$ (49)

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

$\displaystyle\Bigg{\|}\sum_{i=1}^{N_{s}}{h}^{(0)}(\lambda_{i}^{n})(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\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}^{N_{s}}|{h}^{(0)}(\lambda_{i}^{n})|\left|\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\rangle_{{\mathbf{G}}_{n}}-\langle
f,\bm{\phi}_{i}\rangle_{\mathcal{M}}\right|\|{\mathbf{P}}_{n}\bm{\phi}_{i}\|.$
(50)

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

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

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}^{N_{s}}\hat{h}(\lambda_{i}^{n})\left(\langle{\mathbf{P}}_{n}f,\bm{\phi}_{i}^{n}\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}){\mathbf{P}}_{n}f\right\|$
$\displaystyle\leq\left\|(\hat{h}(C_{l})+\delta){\mathbf{P}}_{n}f-(\hat{h}(C_{l})-\delta){\mathbf{P}}_{n}f\right\|\leq
2\delta\|{\mathbf{P}}_{n}f\|,$ (52)

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

$\displaystyle\|{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f-{\mathbf{h}}({\mathbf{L}}_{n}){\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}){\mathbf{P}}_{n}f-\sum_{l\in{\mathcal{K}}_{m}}{\mathbf{h}}^{(l)}({\mathbf{L}}_{n}){\mathbf{P}}f\Bigg{\|}$
(53)
$\displaystyle\leq\|{\mathbf{P}}_{n}{\mathbf{h}}^{(0)}({\mathcal{L}})f-{\mathbf{h}}^{(0)}({\mathbf{L}}_{n}){\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}){\mathbf{P}}_{n}f\|.$
(54)

Above all, we can claim that

$\|{\mathbf{h}}({\mathbf{L}}_{n}){\mathbf{P}}_{n}f-{\mathbf{P}}_{n}{\mathbf{h}}({\mathcal{L}})f\|\leq\left(N\Omega_{2}+A_{h}\Omega_{1}\right)\sqrt{\epsilon}+C\sqrt{\frac{\log
n}{n}}$ (55)