# SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds

arXiv: https://arxiv.org/abs/2402.08653 · HTML: https://mlsanity.com/paper/2402.08653/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 67 references that are in the map.
- First posted on arXiv 13 Feb 2024.

## Builds on (most cited first, 30 of 41)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Graph Convolutional Networks for Text Classification](https://mlsanity.com/paper/1809.05679/) (2018)
- [GPT-GNN: Generative Pre-Training of Graph Neural Networks](https://mlsanity.com/paper/2006.15437/) (2020)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Forecasting Global Weather with Graph Neural Networks](https://mlsanity.com/paper/2202.07575/) (2022)
- [Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples](https://mlsanity.com/paper/1704.07433/) (2017)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion](https://mlsanity.com/paper/2301.09474/) (2023)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Fast Gradient Attack on Network Embedding](https://mlsanity.com/paper/1809.02797/) (2018)
- [Anti-Symmetric DGN: a stable architecture for Deep Graph Networks](https://mlsanity.com/paper/2210.09789/) (2022)
- [Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies](https://mlsanity.com/paper/2003.00653/) (2020)
- [On the Robustness of Graph Neural Diffusion to Topology Perturbations](https://mlsanity.com/paper/2209.07754/) (2022)
- [Interpretable Stability Bounds for Spectral Graph Filters](https://mlsanity.com/paper/2102.09587/) (2021)

## Built on by (most cited first, 4 of 4)

- [SALMAN: Stability Analysis of Language Models Through the Maps Between Graph-based Manifolds](https://mlsanity.com/paper/2508.18306/) (2025)
- [Post-hoc and manifold explanations analysis of facial expression data based on deep learning](https://mlsanity.com/paper/2404.18352/) (2024)
- [A Spectral Framework for Evaluating Geodesic Distances Between Graphs](https://mlsanity.com/paper/2406.10500/) (2024)
- [Widest-Path Reachability Fields for Connectivity-Preserving Slender Structure Segmentation](https://mlsanity.com/paper/2607.07123/) (2026)

## Abstract (arXiv)

Modern graph neural networks (GNNs) can be sensitive to changes in the input graph structure and node features, potentially resulting in unpredictable behavior and degraded performance. In this work, we introduce a spectral framework known as SAGMAN for examining the stability of GNNs. This framework assesses the distance distortions that arise from the nonlinear mappings of GNNs between the input and output manifolds: when two nearby nodes on the input manifold are mapped (through a GNN model) to two distant ones on the output manifold, it implies a large distance distortion and thus a poor GNN stability. We propose a distance-preserving graph dimension reduction (GDR) approach that utilizes spectral graph embedding and probabilistic graphical models (PGMs) to create low-dimensional input/output graph-based manifolds for meaningful stability analysis. Our empirical evaluations show that SAGMAN effectively assesses the stability of each node when subjected to various edge or feature perturbations, offering a scalable approach for evaluating the stability of GNNs, extending to applications within recommendation systems. Furthermore, we illustrate its utility in downstream tasks, notably in enhancing GNN stability and facilitating adversarial targeted attacks.