Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-Offs Zhiyang Wang , Graduate Student Member, IEEE, Luana Ruiz , Member, IEEE, and Alejandro Ribeiro , Senior Member, IEEE

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.

G EOMETRIC data, or data supported in non-Euclidean do- mains, 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 [7], [11], [27]. GNNs have been shown to do well at processing information over the manifold both experimentally and theoretically [16], [25], [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 nonasymptotic convergence analysis of GNNs on graphs sampled from a graphon (also referred to as a transferability analysis) gives a more precise characterization of the discriminabilityconvergence 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 nonasymptotic 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 L of the manifold M ⊂ R 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 [14], [15], [31], [32]. Similarly, the convergence and transferability of neural networks on graphs have been studied in many works including [21], [29], [33], [34]. 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. Very relevant to this paper, the spectral convergence of relatively sparse graphs sampled from manifolds has been studied at length in [35]. Other settings of transfer learning on GNNs have been studied in [36], [37] with different graph similarity measurement without focus on the graph limits.

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 [38], 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 [38] 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 frequencydependent 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. SectionVII concludes the paper. Proofs are deferred to the appendices and supplementary materials.

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

Let G = (V, E, W) be an undirected graph with node set V, |V| = n, and edge set E ⊆ V × V. The edges in E may be weighted, in which case the edge weights are assigned by a function W : E → R. In this paper, we are interested in graph signals x ∈ R n supported on the nodes. For 1 ≤ i ≤ n, [x] i represents the value of the signal at node i. Graph shift. Operating on graph signals x, we define the graph shift operator (GSO) S ∈ R n×n . The GSO is any matrix satisfying [S] ij = 0 if and only if (i, j) ∈ E or i = j, e.g., the adjacency matrix A, [A] ij = W(i, j), or the graph Laplacian L = diag(A1) -A [13], [39]. 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, [Sx] i = j,(i,j)∈E [S] ij [x] j . In the case of an undirected graph, the GSO is symmetric and can therefore be decomposed as S = VΛV H . The eigenvalues in the diagonal matrix Λ are seen as spectral frequencies, and the eigenvectors in V are the corresponding 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 [13], [15], [40] with coefficients {h k } Kt-1 k=0 is given by

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

Hence, the graph frequency response of the graph convolution is given by h(λ) = Kt-1 k=0 h k λ k , which only depends on the weights h k and on the eigenvalues of 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 σ :

The lth layer of a GNN produces F l signals x p l , each called a feature, given by

for 1 ≤ p ≤ F l . At each layer l = 1, 2 . . . , L, the number of input and output features are F l-1 and F l respectively. The filter h lpq G (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 Φ G (H, S, x), where H denotes a set of the graph filter coefficients at all layers.

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

where dμ(x) is the volume element with respect to the measure μ over M. Similarly, the norm of the manifold signal f is

Manifold shift. The manifold M is locally Euclidean, and the local homeomorphic Euclidean space at each point x ∈ M is defined as the tangent space T x M [41]. The disjoint union of all tangent spaces over M is called the tangent bundle and denoted T M. The gradient ∇ : L 2 (M) → L 2 (T M) is the differentiation operator and maps scalar functions to tangent vector functions over M [25], [42]. The adjoint of ∇ is the divergence, which is defined as div : L 2 (T M) → L 2 (M). The Laplace-Beltrami (LB) operator L : L 2 (M) → L 2 (M) is defined as the divergence of the gradient [43]. Formally, the operation is written as

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 [44]. 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 -dtL f . Since the LB operator is self-adjoint and positive-semidefinite and the manifold M is compact, L has real, positive and discrete eigenvalues {λ i } ∞ i=1 , which can be written as

where φ i is the eigenfunction associated with eigenvalue λ i . The eigenvalues, or manifold frequencies, are ordered in increasing order as 0 < λ 1 ≤ λ 2 ≤ λ 3 ≤ . . ., and the eigenfunctions, or manifold oscillation modes, are orthonormal and form an eigenbasis of L 2 (M) in the intrinsic sense. The φ i are also eigenfunctions of the shift operator e -dtL , with corresponding eigenvalues e -dtλi . Manifold convolution. Integrating e -dtL f over [0, ∞) yields the infinite-horizon diffusion process

Let h : R + → R denote the filter impulse response. Based on this diffusion process,a manifold filter can be defined via the manifold convolution [23],

Note that the map h := h(L) is parametric on the LB operator, and is a spatial map acting directly on x ∈ M.

, the manifold convolution can be represented in the manifold frequency domain as

Hence, the frequency response of the filter h(L) is given by ĥ(λ) = ∞ 0 h(t)e -tλ dt, which only depends on the impulse response h and the LB eigenvalues λ = λ i . Further summing over all i and projecting back onto the spatial domain, we can alternatively represent h(L) as

Manifold neural network. Similarly to the GNN, we can define the manifold neural network (MNN) as a cascade of layers l = 1, 2 . . . , L each of which consists of a bank of manifold filters and a pointwise nonlinearity σ. Layer l can be explicitly written as

Authorized licensed use limited to: University of Pennsylvania. Downloaded on July 26,2024 at 11:14:28 UTC from IEEE Xplore. Restrictions apply.

where each signal f p l , 1 ≤ p ≤ 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 Φ(H, L, f), where H is a function set gathering the impulse responses of the manifold filters h pq l for all features and all layers.

Given discrete set of points sampled from the manifold M, we can construct a discrete approximation of 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 [45].

Let X be a set of n points {x 1 , x 2 , . . . , x n } sampled uniformly, identically and independently from the manifold M according to measure μ. The discrete empirical measure associated with these points is defined as p n = 1 n n i=1 δ xi , where δ xi represents the Dirac measure at x i . For signals u, v ∈ L 2 (M), the inner product associated with measure p n is defined as

and so the norm in

and the norm is u 2 L 2 (Gn) = u, u L 2 (Gn) . We construct an undirected geometric graph 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 of their Euclidean distance. Explicitly, the weight of edge (i, j), denoted w ij , is given by

where x ix j is the Euclidean distance between x i and x j . The geometric adjacency matrix A n and the geometric graph Laplacian L n can therefore be expressed as

Since it is constructed from points x i ∈ 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 ∈ L 2 (M) on this graph, as well as the reconstruction from the graph signal back to the manifold signal, we define a uniform sampling operator

The application of the operator P n to f yields the geometric graph signal

I.e., f is a signal on the graph 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 [47].

Definition 1: We call the sampling and interpolation operators P n and I n asymptotically reconstructive if for any manifold signal f ∈ L 2 (M), it holds

Moreover, the sampling and interpolation operators P n and I n are bounded if there exists a constant D such that

Seeing the geometric graph Laplacian L n as an operator acting on f : X → R, we can write the diffusion operation at each point x i explicitly as

for i = 1, 2, . . . , n. This operation can be further extended to continuous manifold signals f : M → R as

where x ∈ M. If we additionally extend the set of sampled points from X to all of the manifold M, we obtain the functional approximation of the geometric graph Laplacian

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

Dense geometric graphs can be constructed when pairs of points x i and x j are connected with a weight function K defined on an unbounded support (i.e. [0, ∞)), 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 corresponding graph Laplacians vis-à-vis the Laplace-Beltrami operator [48], [49], [50]. In the Gaussian case, the weight function K is computed explicitly as

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 M ⊂ R N be equipped with LB operator L, whose eigendecomposition is given by (7). Let G n be a dense geometric graph constructed from n points sampled u.i.d. from M with the edge weights defined as ( 14) and ( 21), = (n) > n -1/(d+4) . Then, with probability at least 1δ, the following holds for each pair of {λ i ,

The constants C 1 , C 2 depend on the volume of the manifold and are defined in Appendix B.

Proof: See Section B in supplemental materials. We can see that the quality of the approximation of L by L n relates not only to the number of sampling points n but also grows with the corresponding eigenvalue λ i . In high frequency domain, a larger eigenvalue leads to a larger difference between the geometric graph Laplacian L n and the Laplace-Beltrami operator L when operating on the corresponding eigenfunction φ i of L. This can be interpreted to mean that eigenfunctions associated with eigenvalues oscillates faster [51] and have slower convergence.

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

Proposition 2: Let M ⊂ R N be equipped with LB operator L, whose eigendecomposition is given by (7). Let L n be the discrete graph Laplacian of the dense geometric graph G n defined as in ( 19) and ( 21), with spectrum given by {λ d+4) . Then, with probability at least 1e -2n d+3 , we have

with

Proof: See Section C 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 λ 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.

We can construct relatively sparse graphs by setting the weight function K 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 [35] with normalization, which has been shown to well approximate the LB operator,

where α d is the volume of the unit ball in R d . As shown by the indicator function, edges only connect points whose distance is within the radius √ . From the theory of random geometric graphs [53], the order of the radius decides the order of the average node degree. I.e., if is in the order of Θ(1), the expected node degree is in the order of Θ(n), which is a dense regime. If is in the order of Θ((log(n)/n) 2/d ), the expected node degree is in the order of Θ(log(n)), which is a relatively sparse regime. When setting in the order of Θ(n -2/d ), the graph is sparse with average node degree Θ(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 [35,Theorem 3.3]: Let M ∈ R N be equipped with LB operator L, whose eigendecompostion is given by (7). Let G n be a sparse geometric graph constructed from n points sampled u.i.d. from M with the edge weights defined as ( 14) and (24), > (log(n)/2n) 2/(d+2) . Then, with probability at least 1δ, the following holds for each pair of {λ i ,

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 the difference between the graph Laplacian and the Laplace-Beltrami operator is in the order of O( ln(2n/δ)/(n d+2 ), √ ) in the sparse graph setting, which is slightly larger than the order O( ln(1/δ)/(n d+2 ), √ ) 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 [35,Theorem 2.4,Theorem 2.6]: Let M ⊂ R N be equipped with LB operator L, whose eigendecomposition is given by (7). Let L n be the discrete graph Laplacian of graph G n defined as (19) and (24), with spectrum

Then, with probability at least 1 -2ne -cn d+3 , we have

with a i ∈ {-1, 1} for all i < K and θ the eigengap of L, i.e., θ = min 1≤i≤K {λ iλ i-1 , λ i+1λ i }. The constants C K,1 , C K,2 depend on λ K , d and the volume of 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 (< λ K ). Comparing with the bounds given in Proposition 2, the orders of the errors both depend on variable 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 sparse ones.

Remark 1: We note that in (24) controls the connectivity radius of each node to its neighboring nodes, and that the average vertex degree is given by α d n d/2 according to the random geometric graph theory [54]. In the case of Proposition 4, where 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.

Equipped with Propositions 2 and 4 relating the spectrum 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.

If we fix the impulse response function 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 L n acting on a geometric graph signal as defined in (18). Explicitly,

This can be interpreted as a discrete geometric graph filtering process in continuous-time, where the exponential term e -L n should be seen as the GSO. This is slightly different than the graph convolutional filtering h 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

where {λ i,n , φ i,n } n i=1 is the spectrum of L n . 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.

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 [55]. This classical result states that for any compact region the eigenvalues {λ i } ∞ i=1 of L grow proportionally to i 2/d . This indicates that large eigenvalues 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 M ⊂ R N and let L be its LB operator with eigenvalues {λ k } ∞ k=1 . Let C 1 be an arbitrary constant and α d the volume of the d-dimensional unit ball. Let Vol(M) denote the volume of manifold M. For any α > 0 and d > 2, there exists N 1 ,

such that, for all k > N 1 , λ k+1λ k ≤ α.

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] (α-separated spectrum): The α-separated spectrum of the LB operator L is defined as

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

Definition 3 [17,Definition 5] (α-FDT filter): The α-frequency difference threshold (α-FDT) filter is defined as a filter h(L) whose frequency response satisfies

with γ k ≤ γ for some γ > 0 and k = 1, . . . , 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):

Letting the geometric graph filter (27) be a Lipschitz continuous α-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 on a dense geometric graph.

Theorem 1 (Convergence of filters on dense geometric graphs): Let M ⊂ R N be equipped with LB operator L, whose eigendecomposition is given by (7). Let L n be the discrete graph Laplacian of the dense graph G n defined as in (19) and (21), with spectrum given by {λ i,n , φ i,n } n i=1 . Fix K ∈ N + and assume that = (n) > n -1/(d+4) Let h(•) be the convolutional filter. Under the assumption that the frequency response of filter h is Lipschitz continuous and α-FDT with α 2

, α > C M,d K 2/d-1 and γ = Ω 2,K √ /α, with probability at least 1e -2n d+3 it holds that

where N is the partition size of the α-FDT filter and C gc depends on both d and the volume of M. Proof: See Appendix A. From this theorem, we can see that, if we take the probability as δ ≤ e -2n d+3 , the order of can be derived as O((ln(1/δ)/(2n)) 1/(d+3) ). Therefore, given enough sampling points, one can guarantee good approximation accuracy with high probability. Also note that a higher dimension leads to a larger , 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 α-FDT filter lifts the limitation on the spectrum required in Propositions 2 and 4. This is achieved by setting α large enough that eigenvalues larger than λ K are grouped. A smaller K leads to a larger α, 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 Ω 1,K and Ω 2,K scale with λ K as Propositions 2 and 4 show. Meanwhile, α 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 α (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 α leads to a smaller number of partitions, as the number of singletons decreases, which results in the decrease of the error bound in (33). 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 M ⊂ R N be equipped with LB operator L, whose eigendecomposition is given by (7). Let L n be the discrete graph Laplacian of G n defined as in (19) and (24). Fix K ∈ N + and assume that = (n) > (log(n)/n) 1/d Let h(•) be the convolutional filter. Under the assumption that the frequency response of the filter h is Lipschitz continuous and α-FDT with α 2

, α > C M,d K 1-2/d and γ = C K,2 /α, with probability at least 1 -2n exp(-Cn d+3 ) it holds that

where N is the partition size ofthe α-FDT filter and C gc depends on both d and the volume of M. Proof: See Appendix A. If we take the probability as δ ≤ 2ne -Cn d+3 , the order of can be derived as O((ln(2n/δ)/n) 1/(d+3) ), which is slightly larger than the order derived in the dense geometric graph setting in Proposition 4. Similar comments apply that, 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.

As filtering on the constructed geometric graph can successfully approximate filtering on the manifold, we can cascade geometric graph filters and point-wise nonlinearities σ to construct a geometric GNN to provide a good approximation of the manifold neural network. Given the geometric graph filter defined in (27), the geometric GNN on G n can be written as

where h pq l (L n ) 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 ≤ q ≤ F l-1 and 1 ≤ p ≤ F l . We denote the number of features in the l-th layer F l (we have dropped the subscript n in x p l and x q l-1 for simplicity). Gathering the filter functions in the set H, this geometric GNN on G n can be represented more concisely as the map Φ(H, L n , x).

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 σ is normalized Lipschitz continuous, i.e., |σ(a)σ(b)| ≤ |a -b|, with σ(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 Φ(H, L, •) be an L-layer MNN on M (12) with F 0 = F L = 1 input and output features and F l = F, l = 1, 2, . . . , L -1 features per layer. Let Φ(H, L n , •) be the GNN with the same architecture applied to the geometric graph G n . If the nonlinearities satisfy Assumption 1 and the manifold filters satisfy h(L n )P n f -

with high probability.

Proof: See Section D 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 Δ fil,n , replaced with the error bounds from Theorem 1 and Theorem 2 for dense and sparse graphs respectively.

We note that the approximation error constant Δ 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].

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 G n1 and G n2 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 M ⊂ R N be equipped with LB operator L. Let L n1 be the discrete graph Laplacian of the graph G n1 defined as in (19) and ( 21) or (24). Let L n2 be the discrete graph Laplacian of the graph G n2 constructed in the same manner as G n1 . Let Φ(H, •, •) be an L-layer GNN with F 0 = F L = 1 input and output features and F l = F, l = 1, 2, . . . , 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

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 Δ fil,n1 and Δ fil,n2 , 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.

Approximation vs. discriminability tradeoff. In the convergence results for geometric graph filters on both dense graphs (Theorem 1) and relatively sparse graphs (Theorem 2), the approximation error bounds depend on the size of the partition (N ), the frequency partition threshold (α), the Lipschitz continuity constant (A h ) and the weight function parameter ( ), 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 α-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 leads to a larger approximation error bound, but at the same time the variation range γ in the α-FDT filter becomes larger which results in better discriminability. In conclusion, there is a tradeoff 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 tradeoff 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, though not showing explicitly in Theorem 3, 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 , dense graphs have a slightly smaller approximation error bound when compared with sparse graphsthus 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.

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 = h(kT s ) [16]. By fixing the time horizon with finite K t samples, we can write the practical geometric filter as

which recovers the graph convolution definition in ( 1) with e -L n seen as the graph shift operator.

We consider a problem of automatic navigation control [56]. We intend to navigate an agent starting from a given point to find a path to the goal without colliding into the obstacles. We uniformly sample n grid points over the free space while avoiding the obstacle areas. We first generate several trajectories with Dijkstra's shortest path algorithm that leads the agent from a randomly selected starting point to the pre-selected goal. Every point on a generated trajectory can be labeled with a 2-d direction vector leading to the next point along the trajectory, which finally reaches the goal. This experiment aims to learn a successful trajectory starting from any given point over the space by predicting the potential directions of all the unlabeled points based on the labeled directions on the generated trajectories. By connecting every pair of points that are not intercepted by the obstacles, we can construct a geometric graph structure involving the topological space information. The geometric Laplacian matrix of the constructed graph L n 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 output is the direction vector pointing to the next point 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. We control the number of labeled points 30% of the total sampled points. The weights of the edges are calculated based on the Euclidean distance between the nodes and the weight function is determined as (21) with = 0.2. We use the Laplacian matrix 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 add a penalty term which is the scaled derivative of the filter function C L | ĥ (λ)| to the loss function similar to the Lipschitz regularization scheme in [57]. A larger penalty constant C L indicates a smoother filter function. All architectures also include a linear readout layer to map the 64 features on each node to a 2-d direction vector. 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. We run 5 independent realizations and show the average successful rates and the standard deviation across these realizations.

Convergence analysis. The convergence is tested by calculating the norm of the differences between the outputs of the final graph filter layer for each architecture. By training the graph filters and GNNs Φ(H n , •, •) on geometric graphs with n = 190, 276, 435, 630, 780 and graph filters and GNNs Φ(H n0 , •, •) on graphs with n 0 = 1225, we plot the differences between the output on the relatively large enough geometric graphs with size n 0 = 1225 measured as Φ(H n0 , L n0 , x n0 ) -Φ(H n , L n0 , x n0 ) . From Figure 2 we can see that the output Differences of the outputs of Lipshitz GNN with penalty terms.

differences decrease and converge as the trained geometric graph size grows, which is accordant with Corollary 1. This also verifies the convergence of geometric GNNs as presented in Theorem 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. 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.

TABLE I SUCCESSFUL RATES WHEN TESTING THE ARCHITECTURES TRAINED ON GEOMETRIC GRAPHS WITH n = 435, 630, 780, 1225 ON THE GEOMETRIC GRAPH WITH n 0 = 1225 Graph Filter GNN Lipschitz GNN n = 435 0.73 ± 0.12 0.71 ± 0.15 0.77±0.14 n = 630 0.72 ±0.10 0.76± 0.11 0.80 ±0.14 n = 780 0.80±0.12 0.83±0.09 0.82± 0.11 n = 1225 0.84± 0.08 0.82±0.07 0.84±0.09

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 0 = 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.

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.

We further evaluate the convergence results on the Model-Net10 [58] 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. 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 All the architectures are trained by minimizing the crossentropy 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 sampled points, and plotting the norm of differences between the final graph filter layer outputs 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.

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 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. 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 1000 NODES. AVERAGE OVER 5 DATA REALIZATIONS Graph Filters GNN Lipschitz GNN n = 300 21.15% ± 3.48% 9.35% ± 2.46% 7.63% ± 3.36% n = 500 18.09% ± 6.28% 7.80% ± 3.50% 7.54% ± 4.01% n = 700 17.31% ± 6.59% 8.16% ± 2.95% 7.97% ± 2.45% n = 900 15.58% ± 4.54% 7.20% ± 3.77% 6.68% ± 3.94% 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 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. 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 Authorized licensed use limited to: University of Pennsylvania. Downloaded on July 26,2024 at 11:14:28 UTC from IEEE Xplore. Restrictions apply.

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 SIZE 1000. AVERAGE OVER 5 DATA REALIZATIONS Graph Filters GNN Lipschitz GNN n = 300 19.83% ± 5.94% 7.74% ± 4.05% 7.68% ± 3.75% n = 500 21.97% ± 4.17% 10.10% ± 1.40% 8.60% ± 2.95% n = 700 13.85% ± 3.81% 7.45% ± 4.03% 8.02% ± 2.77% n = 900 16.62% ± 2.38% 7.92% ± 3.14% 7.44% ± 3.30% 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 1000 nodes 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.

In 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.

We first write out the filter representation as

We denote the index of partitions that contain a single eigenvalue as a set K s (|K s | = N s ) and the rest as a set K m (|K m | = N m ). We decompose the α-FDT filter function as ĥ(λ) = h (0) (λ) + l∈Km h (l) (λ) as

with C l some constant in Λ l (α). With the triangle inequality, we start by analyzing the output difference of h (0) (λ) as

The first term in ( 40) 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 λ i ≤ λ K , we have

The square of the first term is bounded as

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

From the convergence stated in Theorem 4, we have

with the eigengap θ ≥ α under the α-FDT filter. Therefore, the first term in (44) can be bounded as

The last equation comes from the definition of norm in L 2 (G n ).

The second term in (44) can be written as

Because {x 1 , x 2 , • • • , x n } is a set of uniform sampled points from M, based on Theorem 19 in [59] we can claim that

Consider the boundedness of frequency response |h (0) (λ)| ≤ 1 and the bounded energy P n φ i , we have

Combining the above results, we can bound the output difference of h (0) . Then we need to analyze the output difference of h (l) (λ) and bound this as

where h (l) (L) and h (l) (L n ) are filters with filter function h (l) (λ) on the LB operator L and graph Laplacian L n respectively. Combining the filter functions, we can write

With γ = Ω 2,K √ /α, we have

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

We decompose the operator difference between the graph Laplacian and the LB operator with an intermediate term L , which is the functional approximation defined in (20). We first focus on the operator difference between L and L. From [49], we can get the bound as

For the Sobolev norm of eigenfunction φ i , according to [60,Lemma 4.4] we have

which leads to

For the operator difference between L n and L with Hoeffding's inequality as

Therefore, we can claim that with probability at least 1δ, we have

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

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

Lemma 2: Let A, B be self-adjoint operators with {λ i (A), u i } ∞ i=1 and {λ i (B), w i } ∞ i=1 as the corresponding spectrum. Let P r wi be the orthogonal projection operation onto the subspace generated by w i . Then we have a i u iw i ≤ 2 u i -P r wi u i ≤ 2 Bu i -Au i min j =i |λ j (B)λ i (A)| .

(

Proof: The first inequality is directly from [59, Proposition 18]. Let P r ⊥ wi be the orthogonal projection onto the complement of the subspace generated by w i . Then we have u i -P r wi u i = P r ⊥ wi u i = j =i u i , w j w j . (59) Authorized licensed use limited to: University of Pennsylvania. Downloaded on July 26,2024 at 11:14:28 UTC from IEEE Xplore. Restrictions apply.

Therefore, we have P r ⊥ wi Bu i -P r ⊥ wi Au i = j =i Bu i , w j w jj =i Au i , w j w j (60) = u i , Bw j w j - together with Bu i -Au i ≥ P r ⊥ wi Bu i -P r ⊥ wi Au i . We can conclude the proof.

The following lemma is adapted from [48, Lemma 5c] Lemma 3: Let A, B be self-adjoint operators with {λ i (A), u i } ∞ i=1 and {λ i (B), w i } ∞ i=1 as the corresponding spectrum. Then we have

With the above lemmas and our proposed Theorem 1, which includes the operator difference, we can prove Theorem 2. We first fix some K ∈ N, wich provides an upper bound for λ i ≤ λ K for all 1 ≤ i ≤ K. By taking the probability 1n -2 and = n -1/(d+4) , we can conclude that the operator difference in Theorem 1 can be bounded with order O( √ ), with the constant scaling with λ

where we denote the constant as Ω 1 to include the effects of K, the eigengap and the volume of M. This upper bound of the eigenfunction difference leads to

Combining with Lemma 3, the difference of the eigenvalues can also be bounded in the order of O( √ ).

To bound the output difference of MNNs, we need to write in the form of features of the final layer Φ(H, L n , P n f ) -P n Φ(H, L, f))

x q n,L -P n f q L . (67)

By inserting the definitions, we have h pq l (L n )x q n,l-1 -P n F l-1 q=1 h pq l (L)f q l-1

(69)

h pq l (L n )x q n,l-1 -P n h pq l (L)f q l-1

(70)

The difference can be further decomposed as h pq l (L n )x q n,l-1 -P n h pq l (L)f q l-1 ≤ h pq l (L n )x q n,l-1h pq l (L n )P n f q l-1

+ h pq l (L n )P n f q l-1 -P n h pq l (L)f q l-1

(71)

≤ h pq l (L n )x q n,l-1h pq l (L n )P n f q l-1 + h pq l (L n )P n f q l-1 -P n h pq l (L)f q l-1

(72)

The second term can be bounded with h(L n )P n f -P n h(L)f L 2 (Gn) ≤ Δ fil,n . The first term can be decomposed by Cauchy-Schwartz inequality and non-amplifying of the filter functions as

Δ fil,n x q n,l-1

x q l-1 -P n f q l-1 , (

where C per representing the constant in the error bound of manifold filters in (33). To solve this recursion, we need to compute the bound for x p l . By normalized Lipschitz continuity of σ and the fact that σ(0) = 0, we can get

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