Stability of Neural Networks on Manifolds to Relative Perturbations
This addresses the stability problem for GNNs in large-scale applications like wireless resource allocation, but it is incremental as it builds on existing manifold-based analyses.
The paper tackled the stability of Graph Neural Networks (GNNs) on large graphs by analyzing convolutional neural networks on manifolds, proving that networks with constructed filters are stable to relative perturbations of the Laplace-Beltrami operator and observing a trade-off between stability and discriminability.
Graph Neural Networks (GNNs) show impressive performance in many practical scenarios, which can be largely attributed to their stability properties. Empirically, GNNs can scale well on large size graphs, but this is contradicted by the fact that existing stability bounds grow with the number of nodes. Graphs with well-defined limits can be seen as samples from manifolds. Hence, in this paper, we analyze the stability properties of convolutional neural networks on manifolds to understand the stability of GNNs on large graphs. Specifically, we focus on stability to relative perturbations of the Laplace-Beltrami operator. To start, we construct frequency ratio threshold filters which separate the infinite-dimensional spectrum of the Laplace-Beltrami operator. We then prove that manifold neural networks composed of these filters are stable to relative operator perturbations. As a product of this analysis, we observe that manifold neural networks exhibit a trade-off between stability and discriminability. Finally, we illustrate our results empirically in a wireless resource allocation scenario where the transmitter-receiver pairs are assumed to be sampled from a manifold.