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

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

## 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 (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [Graph Convolutional Neural Networks via Scattering](https://mlsanity.com/paper/1804.00099/) (2018)
- [Graphon Signal Processing](https://mlsanity.com/paper/2003.05030/) (2020)
- [Stability of Graph Scattering Transforms](https://mlsanity.com/paper/1906.04784/) (2019)
- [On the Transferability of Spectral Graph Filters](https://mlsanity.com/paper/1901.10524/) (2019)
- [Interpretable Stability Bounds for Spectral Graph Filters](https://mlsanity.com/paper/2102.09587/) (2021)
- [A User Guide to Low-Pass Graph Signal Processing and its Applications](https://mlsanity.com/paper/2008.01305/) (2020)
- [On the Stability of Graph Convolutional Neural Networks under Edge Rewiring](https://mlsanity.com/paper/2010.13747/) (2020)
- [Strong Consistency, Graph Laplacians, and the Stochastic Block Model](https://mlsanity.com/paper/2004.09780/) (2020)
- [Stability of Graph Convolutional Neural Networks to Stochastic Perturbations](https://mlsanity.com/paper/2106.10526/) (2021)

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

- [Learning Stochastic Graph Neural Networks with Constrained Variance](https://mlsanity.com/paper/2201.12611/) (2022)
- [Space-Time Graph Neural Networks with Stochastic Graph Perturbations](https://mlsanity.com/paper/2210.16270/) (2022)
- [Stability of Graph Convolutional Neural Networks through the lens of small perturbation analysis](https://mlsanity.com/paper/2312.12934/) (2023)
- [Robust Graph Neural Network based on Graph Denoising](https://mlsanity.com/paper/2312.06557/) (2023)
- [On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective](https://mlsanity.com/paper/2506.01213/) (2025)

## 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.