Interpretable Stability Bounds for Spectral Graph Filters

Henry Kenlay, Dorina Thanou, Xiaowen Dong
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:5388-5397, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-kenlay21a, title = {Interpretable Stability Bounds for Spectral Graph Filters}, author = {Kenlay, Henry and Thanou, Dorina and Dong, Xiaowen}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {5388--5397}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/kenlay21a/kenlay21a.pdf}, url = {https://proceedings.mlr.press/v139/kenlay21a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Interpretable Stability Bounds for Spectral Graph Filters %A Henry Kenlay %A Dorina Thanou %A Xiaowen Dong %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-kenlay21a %I PMLR %P 5388--5397 %U https://proceedings.mlr.press/v139/kenlay21a.html %V 139 %X 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.
APA
Kenlay, H., Thanou, D. & Dong, X.. (2021). Interpretable Stability Bounds for Spectral Graph Filters. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:5388-5397 Available from https://proceedings.mlr.press/v139/kenlay21a.html.

Related Material