Interpretable Stability Bounds for Spectral Graph Filters
This work addresses the problem of designing robust machine learning models for graph-structured data by providing interpretable stability bounds, though it is incremental as it builds on existing spectral filter theory.
The paper tackles the lack of theoretical understanding of stability properties in spectral graph filters by deriving a novel and interpretable upper bound on filter output changes, expressed in terms of graph structural properties like endpoint degrees and spatial proximity of edges, and validates this bound through extensive experiments.
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.