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

Hoang-Son Nguyen, Yiran He, Hoi-To Wai

Abstract

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.

Introduction

Graph Convolutional Networks (GCNs) rely on graph filters to process data. A critical question for deploying these models is stability: if the graph topology changes—for instance, due to noise or dynamic links—does the output of the filter change drastically?

Existing theoretical bounds often suggest that the change in filter output is proportional to the number of edges rewired. This implies that if you rewire a large portion of the graph, the filter becomes "unstable" and the model's performance might collapse. However, in many real-world scenarios like social networks, edges might be noisy, but the high-level community structure remains intact. This paper challenges the conventional wisdom, proving that low-pass graph filters remain stable even with a massive number of edge rewires, provided the underlying community structure is preserved.

Methodology: Frequency Domain Analysis

The authors depart from standard polynomial-based analysis and instead treat graph filter stability using frequency domain analysis. They define a "low-pass" filter as one that significantly attenuates high-frequency components (associated with large eigenvalues of the Graph Shift Operator) compared to low-frequency components.

They derive a new bound for the "graph filter distance" that depends on the low-pass ratio (how well the filter suppresses noise), the spectral gap of the graph, and the structural similarity of the principal eigenvectors. This shift in perspective shows that the location of edge changes (within or between communities) is far more important than the absolute quantity of changes.

Key Results

Asymptotic Stability in Synthetic Models

Using Stochastic Block Models (SBM) and Planted Partition Models (PPM), the authors observed the behavior of filters as the number of nodes ($n$) increased from 200 to 2,000.

Figure 2: Stability comparison for high-pass (left) and low-pass (right) filters using the unnormalized Laplacian. Note the $10^7$ difference in scale on the y-axis, highlighting the extreme instability of high-pass filters compared to the stability of low-pass filters.

As shown in Figure 2, for low-pass filters, the filter distance converges toward zero as the number of nodes increases, regardless of the rewiring ratio ($p_{re} = 0.1, 0.5, 0.9$). Conversely, high-pass filters show massive instability; with unnormalized Laplacians, the filter distance for high-pass filters was roughly $10^7$ times larger than for low-pass filters.

Robustness on Real-World Data

The theory was further tested on the email-Eu-core network, which contains 1,005 nodes across 42 departments.

Figure 5: Graph filter distance vs. rewiring ratio on the email-Eu-core dataset. The low-pass filter (red) remains significantly more stable than the high-pass filter (green) as the proportion of rewired edges increases.

In Figure 5, the low-pass filter (red) remains stable across a range of rewiring ratios (up to 20% of edges rewired), while the high-pass filter (green) sees its error distance increase exponentially. This confirms that low-pass filters act as a natural "denoiser," filtering out the high-frequency noise introduced by edge rewiring within communities.

Conclusion

This work demonstrates that structure matters more than quantity when it comes to graph stability. By focusing on low-pass filters, GCNs can maintain robust performance even in environments with high topological noise, provided the fundamental community structure of the graph is not destroyed. Future work may explore adaptive filter designs that learn optimal cutoff frequencies to maximize stability for specific noisy datasets.

Summary updated

Abstract

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.
BibTeX
@inproceedings{nguyen2022stability,
  author = {Hoang-Son Nguyen and Yiran He and Hoi-To Wai},
  title = {{On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewires}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  url = {https://openreview.net/forum?id=rxcwgrwnF9},
}
Figure