Interpretable Stability Bounds for Spectral Graph Filters

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.

References in corpus (15)

• Statistical mechanics of complex networks
• Semi-Supervised Classification with Graph Convolutional Networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Geometric deep learning: going beyond Euclidean data
• Simplifying Graph Convolutional Networks
• Adversarial Attacks on Neural Networks for Graph Data
• Adversarial Attack and Defense on Graph Data: A Survey
• Graph Isomorphism in Quasipolynomial Time
• Construction and properties of assortative random networks
• Graph signal processing for machine learning: A review and new perspectives
• Stability Properties of Graph Neural Networks
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective
• Certifiable Robustness to Graph Perturbations
• On the Stability of Graph Convolutional Neural Networks under Edge Rewiring

Cited by in corpus (4)

• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Understanding over-squashing and bottlenecks on graphs via curvature
• Bayesian Estimation of Graph Signals
• Fairness-Aware Node Representation Learning