Stability of Neural Networks on Manifolds to Relative Perturbations

Zhiyang Wang, Luana Ruiz, Alejandro Ribeiro

TL;DR

This paper bridges the gap between the empirical success of Graph Neural Networks (GNNs) on large graphs and theoretical stability bounds that typically explode as graph size increases. By treating large graphs as samples from a continuous manifold, the authors prove that Manifold Neural Networks (MNNs) are stable to relative perturbations when using a specific class of "Frequency Ratio Threshold" (FRT) filters.

What Problem Does This Paper Address?

Graph Neural Networks are remarkably effective at scaling to massive datasets, yet theoretical analysis often tells a different story. Standard stability results for GNNs usually produce error bounds that grow with the number of nodes ($N$), suggesting that larger graphs should be inherently less stable—a prediction contradicted by practice.

To solve this, researchers look at the "limit" of a graph: a manifold. If we can prove a neural network is stable on a manifold, we can better understand its behavior on very large graphs sampled from that manifold. Furthermore, most existing work focuses on absolute perturbations (adding a fixed amount of noise). This paper tackles relative perturbations, which scale with the operator itself. This is a more realistic model for real-world changes, such as perturbing the weights of every edge in a network proportionally.

Methods

The authors define Manifold Neural Networks (MNNs), which are the continuous counterparts to GNNs. The core of an MNN is the manifold convolution, which relies on the Laplace-Beltrami operator ($L$)—the manifold version of the graph Laplacian.

The key technical contributions are:

  1. Relative Perturbation Model: They define a perturbed operator $L' = L + EL$, where $E$ is a symmetric error operator.
  2. Frequency Ratio Threshold (FRT) Filters: Because the spectrum of a manifold is infinite and eigenvalues can cluster together, the authors propose FRT filters. These filters group eigenvalues based on their ratios and ensure that the filter's response is similar for eigenvalues within the same group.
  3. Stability Proof: Using Weyl’s law (which describes how eigenvalues grow on a manifold), they prove that MNNs built with these FRT filters have a bounded change in output when the underlying manifold is perturbed.

Datasets

The paper does not use standard vision or NLP datasets. Instead, it evaluates the theory using a synthetic wireless resource allocation scenario:

  • Setup: An ad-hoc wireless network with $n=50$ nodes dropped randomly in a 2D area.
  • Task: Maximize the sum-of-rate capacity under power constraints (a common problem in communications).
  • Perturbation: The authors trained a GNN on the original network and then tested it on a version where the channel matrix was scaled by log-normal noise to simulate relative perturbations in the environment.

Key Insights and Ideas

  • The "Large Graph" Paradox: Traditional GNN bounds fail for large $N$ because they don't account for the underlying continuous structure. Manifolds provide the right mathematical language to discuss "infinite" graphs.
  • Weyl’s Law is Critical: The authors use Weyl’s law to show that while eigenvalues are infinite, they grow at a predictable rate ($i^{2/d}$). This allows them to partition the infinite spectrum into a finite number of groups ($M$).
  • Stability vs. Discriminability: There is an inherent trade-off. To make a network more stable, you must use "smoother" filters (higher $\gamma$ in FRT filters). However, very smooth filters lose the ability to distinguish between different high-frequency signals, potentially reducing the network's performance.
  • Nonlinearity to the Rescue: Interestingly, the authors note that while stable filters might lose some discriminative power, the point-wise nonlinearities (like ReLU) in the neural network can help recover this by spreading information across the spectrum.

Key Results

  • Theorem 1: This is the mathematical heart of the paper. It provides a stability bound for MNNs that depends on the number of layers, the filter properties, and the magnitude of the relative perturbation ($\epsilon$), but notably not on the number of nodes in a sampled graph.
  • Numerical Validation: In the wireless simulation, the "Difference of Ratios" (a measure of instability) remained small (between 0.25 and 0.5) even as the number of layers increased. While the error does grow with depth and the number of filters (features) per layer, the growth is controlled, justifying the theoretical stability bound.

Limitations and Future Work

  • Theoretical vs. Practical: MNNs are a theoretical construct. While they provide insights into GNNs, the bridge between the continuous manifold bound and a discrete graph with a finite number of nodes is discussed conceptually but not fully quantified in this specific paper.
  • Filter Design: The FRT filters are a specific mathematical construction used to prove the theorem. In practice, most practitioners use simple polynomial filters (like ChebNet). Future work could explore how closely standard GNN architectures naturally approximate these stable FRT filters.
  • Complexity of $M$: The bound depends on $M$, the number of partitions of the spectrum. For complex manifolds, $M$ could be large, potentially loosening the bound.

Summary updated

BibTeX
@inproceedings{wang2022stability,
  author = {Zhiyang Wang and Luana Ruiz and Alejandro Ribeiro},
  title = {{Stability of Neural Networks on Manifolds to Relative Perturbations}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  doi = {10.1109/icassp43922.2022.9747865},
}
Figure