mlsanityData to 14 Oct 2026

Interpretable Stability Bounds for Spectral Graph Filters

arXiv 2102.09587 ↗First posted 18 Feb 2021cs.LGcited by 28

Not on the map. Why?

Abstract (arXiv)

Graph-structured data arise in a variety of real-world context ranging from sensor and transportation to biological and social networks. As a ubiquitous tool to process graph-structured data, spectral graph filters have been used to solve common tasks such as denoising and anomaly detection, as well as design deep learning architectures such as graph neural networks. Despite being an important tool, there is a lack of theoretical understanding of the stability properties of spectral graph filters, which are important for designing robust machine learning models. In this paper, we study filter stability and provide a novel and interpretable upper bound on the change of filter output, where the bound is expressed in terms of the endpoint degrees of the deleted and newly added edges, as well as the spatial proximity of those edges. This upper bound allows us to reason, in terms of structural properties of the graph, when a spectral graph filter will be stable. We further perform extensive experiments to verify intuition that can be gained from the bound.

Key facts. Cited by 28 papers in the map (data through 14 Oct 2026). Builds on 19 of its 40 references that are in the map. First posted on arXiv 18 Feb 2021.

Builds on

19 of 40 references.

References · 19

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  3. 2019Simplifying Graph Convolutional Networkscited by 1,477
  4. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  5. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  6. 2017Graph Signal Processing: Overview, Challenges and Applicationscited by 413
  7. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 397
  8. 2020SIGN: Scalable Inception Graph Neural Networkscited by 284
  9. 2017CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filterscited by 203
  10. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  11. 2018Adversarial Attack and Defense on Graph Data: A Surveycited by 167
  12. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
7 more
  1. 2019Stability Properties of Graph Neural Networkscited by 127
  2. 2020Graph signal processing for machine learning: A review and new perspectivescited by 73
  3. 2019Certifiable Robustness to Graph Perturbationscited by 62
  4. 2019On the Transferability of Spectral Graph Filterscited by 28
  5. 2020Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networkscited by 27
  6. 2020A User Guide to Low-Pass Graph Signal Processing and its Applicationscited by 25
  7. 2020On the Stability of Graph Convolutional Neural Networks under Edge Rewiringcited by 25

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 6; 2023: 5; 2024: 4; 2025: 2; 2026: 2.

28 papers.

Sort:

  1. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  2. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  3. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
  4. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 53
  5. 2021Transferability Properties of Graph Neural Networkscited by 43
  6. 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
  7. 2023A Survey on Spectral Graph Neural Networkscited by 26
  8. 2021Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networkscited by 19
  9. 2024Spectral Invariant Learning for Dynamic Graphs under Distribution Shiftscited by 19
  10. 2021Graph Structural Attack by Perturbing Spectral Distancecited by 16
  11. 2021Fairness-Aware Node Representation Learningcited by 14
  12. 2024Sparse Covariance Neural Networkscited by 7
16 more
  1. 2021On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewirescited by 5
  2. 2021Adversarial Attacks on Graph Classification via Bayesian Optimisationcited by 5
  3. 2022Learning Stochastic Graph Neural Networks with Constrained Variancecited by 5
  4. 2023Stability of Graph Convolutional Neural Networks through the lens of small perturbation analysiscited by 5
  5. 2024SAGMAN: Stability Analysis of Graph Neural Networks on the Manifoldscited by 4
  6. 2022Deep representation learning: Fundamentals, Perspectives, Applications, and Open Challengescited by 3
  7. 2023Framelet Message Passingcited by 3
  8. 2024Simplified PCNet with Robustnesscited by 3
  9. 2022Stable and Transferable Hyper-Graph Neural Networkscited by 2
  10. 2023Graph Neural Networks over the Air for Decentralized Tasks in Wireless Networkscited by 2
  11. 2023On the Trade-Off between Stability and Representational Capacity in Graph Neural Networkscited by 2
  12. 2026Stability of Flow Models for Graph Signalscited by 2
  13. 2022Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Modelcited by 1
  14. 2025On the Convergence and Size Transferability of Continuous-depth Graph Neural Networkscited by 1
  15. 2025On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspectivecited by 0
  16. 2026Data-Driven Graph Filters via Adaptive Spectral Shapingcited by 0