mlsanityData to 7 Oct 2026

SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds

arXiv 2402.08653 ↗First posted 13 Feb 2024cs.LG cs.AIcited by 4

Not on the map. Why?

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.

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

Builds on

41 of 67 references.

References · 41

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  5. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  6. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  7. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  8. 2017Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecastingcited by 1,125
  9. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  10. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  11. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  12. 2019Graph Neural Networks for Social Recommendationcited by 711
29 more
  1. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  2. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  3. 2018Graph Convolutional Networks for Text Classificationcited by 345
  4. 2020GPT-GNN: Generative Pre-Training of Graph Neural Networkscited by 302
  5. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  6. 2022Forecasting Global Weather with Graph Neural Networkscited by 165
  7. 2017Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samplescited by 147
  8. 2019Stability Properties of Graph Neural Networkscited by 125
  9. 2018Learning graphs from data: A signal representation perspectivecited by 119
  10. 2018Adversarial Attacks on Node Embeddings via Graph Poisoningcited by 109
  11. 2023DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusioncited by 85
  12. 2016Hiding Individuals and Communities in a Social Networkcited by 77
  13. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  14. 2018Fast Gradient Attack on Network Embeddingcited by 65
  15. 2022Anti-Symmetric DGN: a stable architecture for Deep Graph Networkscited by 58
  16. 2020Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studiescited by 42
  17. 2022On the Robustness of Graph Neural Diffusion to Topology Perturbationscited by 30
  18. 2021Interpretable Stability Bounds for Spectral Graph Filterscited by 28
  19. 2017Large Scale Graph Learning from Smooth Signalscited by 27
  20. 2023Adversarial Robustness in Graph Neural Networks: A Hamiltonian Approachcited by 24
  21. 2014Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov Random fieldscited by 19
  22. 2021SPADE: A Spectral Method for Black-Box Adversarial Robustness Evaluationcited by 16
  23. 2022GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networkscited by 14
  24. 2018Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositionscited by 8
  25. 2021BulletTrain: Accelerating Robust Neural Network Training via Boundary Example Miningcited by 8
  26. 2021SGL: Spectral Graph Learning from Measurementscited by 5
  27. 2021Task and Model Agnostic Adversarial Attack on Graph Neural Networkscited by 5
  28. 2018Short Cycles via Low-Diameter Decompositionscited by 1
  29. 2023SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurementscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 1.

4 papers.

  1. 2025SALMAN: Stability Analysis of Language Models Through the Maps Between Graph-based Manifoldscited by 1
  2. 2024Post-hoc and manifold explanations analysis of facial expression data based on deep learningcited by 0
  3. 2024A Spectral Framework for Evaluating Geodesic Distances Between Graphscited by 0
  4. 2026Widest-Path Reachability Fields for Connectivity-Preserving Slender Structure Segmentationcited by 0