Volume 5 • Issue 2 • PP: 07–11 • 2025
Certified Sensitivity-Regularized Polynomial Graph Filters for Stable Graph Neural Computation
Open Access & Copyright
© 2025 The Author(s). Published by ASPG. This article is licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
View PDF Abstract
Polynomial graph filters Ha(S) = ΣKk =0 akSk are local, scalable, and central to spectral graph neural computation, but their output may vary sharply when the graph shift S is perturbed. This paper develops a finite-radius perturbation calculus that requires neither commutativity nor eigengaps. For ∥S∥2 ≤ ρ and ∥E∥2 ≤ ε, we prove the certificate ∥Ha(S+E)−Ha(S)∥2 ≤ ΣKk =1 |ak|(ρ +ε)k−ρk, show equality for aligned positive polynomials, derive an explicit second-order remainder, and propagate the certificate through multilayer graph neural networks. The bound induces a sensitivity-weighted quadratic design whose unique minimizer is available in closed form. Controlled analysis uses three spectral responses, degree K = 8, and 2,304 filter evaluations on Erd˝os–Rényi, stochastic-block, Barabási– Albert, and random-geometric graphs. Relative to unconstrained least squares, the proposed design reduces the mean finite-radius certificate by 74.9%, the first-order coefficient sensitivity by 72.9%, and observed operator sensitivity by 6.9%. It matches accuracy-controlled ridge filtering within 0.3% in observed sensitivity while yielding a 7.3% smaller certificate. The result is a compact, auditable robustness layer for graph filters and polynomial graph-convolution banks.
Keywords
References
[1] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 83–98, 2013.
[2] A. Ortega, P. Frossard, J. Kovaˇcevi´c, J. M. F. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” Proceedings of the IEEE, vol. 106, no. 5, pp. 808–828, 2018.
[3] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in Advances in Neural Information Processing Systems 29, 2016, pp. 3844–3852.
[4] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in International Conference on Learning Representations, 2017.
[5] F. Gama, J. Bruna, and A. Ribeiro, “Stability properties of graph neural networks,” IEEE Transactions on Signal Processing, vol. 68, pp. 5680–5695, 2020.
[6] H. Kenlay, D. Thanou, and X. Dong, “On the stability of polynomial spectral graph filters,” in 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, pp. 5350–5354.
[7] H. Kenlay, D. Thanou, and X. Dong, “Interpretable stability bounds for spectral graph filters,” in Proceedings of the 38th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 139, 2021, pp. 5388–5397.
[8] L. Ruiz, F. Gama, and A. Ribeiro, “Graph neural networks: Architectures, stability, and transferability,” Proceedings of the IEEE, vol. 109, no. 5, pp. 660–682, 2021.
[9] X. Wang, E. Ollila, and S. A. Vorobyov, “Graph convolutional neural networks sensitivity under probabilistic error model,” IEEE Transactions on Signal and Information Processing over Networks, vol. 10, pp. 788–803, 2024.
[10] J. Zhang and Z. Zhao, “Improved stability bounds for graph convolutional neural networks under graph perturbations,” in 2024 IEEE Information Theory Workshop (ITW), 2024, pp. 307–312.
[11] S. Rey, V. M. Tenorio, and A. G. Marques, “Robust graph filter identification and graph denoising from signal observations,” IEEE Transactions on Signal Processing, vol. 71, pp. 3651–3666, 2023.
[12] L. Testa, S. Sardellitti, and S. Barbarossa, “Robust filter design for graph signals,” in 2024 32nd European Signal Processing Conference (EUSIPCO), 2024, pp. 827–831.
[13] F. R. K. Chung, Spectral Graph Theory, ser. CBMS Regional Conference Series in Mathematics. Providence, RI: American Mathematical Society, 1997, vol. 92.
[14] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: Frequency analysis,” IEEE Transactions on Signal Processing, vol. 62, no. 12, pp. 3042– 3054, 2014.
[15] D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129–150, 2011.
[16] E. Isufi, A. Loukas, A. Simonetto, and G. Leus, “Autoregressive moving average graph filtering,” IEEE Transactions on Signal Processing, vol. 65, no. 2, pp. 274–288, 2017.
[17] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein, “CayleyNets: Graph convolutional neural networks with complex rational spectral filters,” IEEE Transactions on Signal Processing, vol. 67, no. 1, pp. 97–109, 2019.
[18] R. Levie, W. Huang, L. Bucci, M. M. Bronstein, and G. Kutyniok, “Transferability of spectral graph convolutional neural networks,” Journal of Machine Learning Research, vol. 22, no. 272, pp. 1–59, 2021.
[19] J. C. Mason and D. C. Handscomb, Chebyshev Polynomials. Boca Raton, FL: Chapman and Hall/CRC, 2003.
[20] L. N. Trefethen, Approximation Theory and Approximation Practice. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2013.
[21] K. Huang,W. Cao, H. Ta, X. Xiao, and P. Liò, “Optimizing polynomial graph filters: A novel adaptive krylov subspace approach,” in Proceedings of the ACM Web Conference 2024, 2024, pp. 1057–1068.
[22] D. Zügner and S. Günnemann, “Certifiable robustness and robust training for graph convolutional networks,” in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019, pp. 246–256.
[23] N. J. Higham, Functions of Matrices: Theory and Computation. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2008.
[24] R. Bhatia, Matrix Analysis. New York, NY: Springer, 1997.
[25] G. W. Stewart and J.-G. Sun, Matrix Perturbation Theory. Boston, MA: Academic Press, 1990.
[26] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, UK: Cambridge University Press, 2004.
[27] G. H. Golub and C. F. V. Loan, Matrix Computations, 4th ed. Baltimore, MD: Johns Hopkins University Press, 2013.
Cite This Article
Choose your preferred format
Publisher's Note
The statements, opinions, and data presented in this article are solely those of the author(s) and do not necessarily represent those of ASPG, the journal, or its editors. ASPG and the editors disclaim responsibility for any harm arising from the use of any ideas, methods, instructions, or products described in this article, to the fullest extent permitted by applicable law.