Convergence of Graph Neural Networks on Relatively Sparse Graphs

In this paper we study the connection between graph filters, graph neural networks (GNNs) and manifold filters, manifold neural networks (MNNs), Specifically, we consider the case when we have access to a set of uniformly sampled points from the manifold based on which we construct a relatively sparse graph to approximate the manifold, which is a suitable model for many real world applications. We prove a non-asymptotic approximation error bound or convergence rate for the graph filters and the GNNs on the relatively sparse graphs to the filters and neural networks on the manifold that the graphs are sampled from. An interesting trade-off between the convergence and the discriminability of the graph filters can be observed from the non-asymptotic error bound which indicates that graph filters cannot give good convergence and discriminability at the same time. While the nonlinearity function in GNNs can alleviate this trade-off and allows the GNNs to both converge to the MNNs and discriminate well. Equipped with this non-asymptotic error bound, we further interpret the transferability property of GNNs when the graphs are sampled from a common manifold. We verify our conclusions with a point-cloud classification problem.

I. Introduction

Modern signal processing now has shown increasing interest in data supported on geometric structures in non-Euclidean domains. This is motivated by a large number of applications, including but not limited to robot flocking [1], [2], molecular representations [3], [4], 3D shape analysis [5], [6] and wireless resource allocation [7], [8]. Graphs and manifolds are most commonly used to model the data structures in non-Euclidean domains [9]. Convolutional filters and convolutional neural networks, as the standard invariant and stable information processing tools which also allow feature sharings [10], have been established soundly on graphs as well as manifolds. Graph convolutional filters [11], [12], graph neural networks (GNNs) [13]–[15] together with manifold convolutional filters [16], [17] and manifold neural networks (MNNs) [18], [19] are therefore the prominent choices for non-Euclidean information processing in discrete and continuous domains respectively.