Stability of Neural Networks on Manifolds to Relative Perturbations

Zhiyang Wang, Luana Ruiz, Alejandro Ribeiro

Abstract

Graph Neural Networks (GNNs) demonstrate remarkable empirical success on large-scale graphs, yet traditional theoretical stability bounds often diverge as the number of nodes increases. This paper bridges this gap by analyzing neural networks on continuous manifolds, which serve as the limit for large graphs. We define Manifold Neural Networks (MNNs) and prove they are stable to relative perturbations when employing Frequency Ratio Threshold (FRT) filters. Our analysis shows that stability depends on the manifold's underlying geometry rather than the discrete node count, providing a more realistic theoretical foundation for GNN performance.

Introduction: The "Large Graph" Paradox

Standard stability analysis for GNNs typically yields error bounds that grow with the number of nodes $N$. This suggests that larger graphs should be inherently less stable, a prediction that contradicts practical observations where GNNs scale effectively to massive datasets. To resolve this, we treat large graphs as samples from a continuous manifold. If a neural network is stable on the manifold, its discrete counterparts on large sampled graphs should exhibit similar stability.

Furthermore, most existing research focuses on absolute perturbations (additive noise). This work tackles relative perturbations, where the error scales with the operator itself (e.g., $L' = L + EL$). This model better reflects real-world scenarios, such as proportional changes in edge weights across a network.

Methodology: Manifold Neural Networks and FRT Filters

The core of an MNN is the manifold convolution, which utilizes the Laplace-Beltrami operator ($L$). Unlike discrete graphs, the spectrum of a manifold is infinite. To ensure stability, we introduce Frequency Ratio Threshold (FRT) filters.

Illustration of Frequency Ratio Threshold (FRT) filters grouping eigenvalues on a manifold.

FRT filters partition the infinite spectrum into groups based on eigenvalue ratios. By ensuring the filter response is similar for eigenvalues within the same group, we can bound the change in output even when the underlying manifold is perturbed. This construction leverages Weyl’s law, which describes the predictable growth rate of eigenvalues ($i^{2/d}$), allowing us to manage the infinite spectrum with a finite number of partitions.

Numerical Validation: Wireless Resource Allocation

We evaluate the theory using a synthetic wireless resource allocation scenario involving an ad-hoc network of 50 nodes. The task is to maximize sum-of-rate capacity under power constraints. We trained a GNN on the original network and tested it against relative perturbations simulated by scaling the channel matrix with log-normal noise.

Numerical validation showing the difference of ratios (instability) as a function of the number of layers for different feature sizes F.

The results in Figure 2 demonstrate that the "Difference of Ratios"—a metric for instability—remains controlled as the number of layers increases. While error growth is observed with increasing depth and feature count ($F$), it remains bounded, validating our theoretical stability results.

Discussion and Conclusion

Our findings highlight a fundamental trade-off between stability and discriminability. Smoother filters (higher $\gamma$ in FRT filters) enhance stability but may lose the ability to distinguish high-frequency signals. However, point-wise nonlinearities like ReLU can help recover this discriminative power by spreading information across the spectrum.

While MNNs are a theoretical construct, they provide critical insights into why GNNs remain stable on large graphs. Future work will further quantify the bridge between continuous manifold bounds and discrete graph implementations, and explore how standard architectures like ChebNet approximate these stable filter designs.

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