mlsanityData to 14 Oct 2026

On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewires

arXiv 2110.07234 ↗First posted 14 Oct 2021eess.SP cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

Recently, the stability of graph filters has been studied as one of the key theoretical properties driving the highly successful graph convolutional neural networks (GCNs). The stability of a graph filter characterizes the effect of topology perturbation on the output of a graph filter, a fundamental building block for GCNs. Many existing results have focused on the regime of small perturbation with a small number of edge rewires. However, the number of edge rewires can be large in many applications. To study the latter case, this work departs from the previous analysis and proves a bound on the stability of graph filter relying on the filter's frequency response. Assuming the graph filter is low pass, we show that the stability of the filter depends on perturbation to the community structure. As an application, we show that for stochastic block model graphs, the graph filter distance converges to zero when the number of nodes approaches infinity. Numerical simulations validate our findings.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 20 of its 27 references that are in the map. First posted on arXiv 14 Oct 2021.

Builds on

20 of 27 references.

References · 20

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  3. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  4. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  5. 2017Graph Signal Processing: Overview, Challenges and Applicationscited by 413
  6. 2017Community Detection and Stochastic Block Modelscited by 319
  7. 2013Consistency of spectral clustering in stochastic block modelscited by 129
  8. 2019Stability Properties of Graph Neural Networkscited by 127
  9. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 118
  10. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 76
  11. 2020Graph signal processing for machine learning: A review and new perspectivescited by 73
  12. 2018Graph Convolutional Neural Networks via Scatteringcited by 46
8 more
  1. 2020Graphon Signal Processingcited by 37
  2. 2019Stability of Graph Scattering Transformscited by 34
  3. 2019On the Transferability of Spectral Graph Filterscited by 28
  4. 2021Interpretable Stability Bounds for Spectral Graph Filterscited by 28
  5. 2020A User Guide to Low-Pass Graph Signal Processing and its Applicationscited by 25
  6. 2020On the Stability of Graph Convolutional Neural Networks under Edge Rewiringcited by 25
  7. 2020Strong Consistency, Graph Laplacians, and the Stochastic Block Modelcited by 21
  8. 2021Stability of Graph Convolutional Neural Networks to Stochastic Perturbationscited by 18

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 2; 2024: 0; 2025: 1.

5 papers.

  1. 2022Learning Stochastic Graph Neural Networks with Constrained Variancecited by 5
  2. 2022Space-Time Graph Neural Networks with Stochastic Graph Perturbationscited by 5
  3. 2023Stability of Graph Convolutional Neural Networks through the lens of small perturbation analysiscited by 5
  4. 2023Robust Graph Neural Network based on Graph Denoisingcited by 4
  5. 2025On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspectivecited by 0