Geometric Graph Filters and Neural Networks: Limit Properties and
  Discriminability Trade-offs
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.
Zhiyang Wang, Luana Ruiz, Alejandro Ribeiro
# Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs

###### 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 exhibits 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.

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

## I Introduction

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

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

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

**Contributions.** In this paper, we prove and analyze a non-asymptotic approximation error bound for GNNs on graphs sampled from manifold, thus closing the gap between GNNs and MNNs with an explicit numerical relationship. We start by importing the definition of the manifold filter as a convolutional operation where the diffusions are exponentials of the Laplace-Beltrami (LB) operator \(\mathcal{L}\) of the manifold \(\mathcal{M}\subset\mathbb{R}^{\text{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,