Limitless stability for Graph Convolutional Networks
Not on the map. Why?
Abstract (arXiv)
This work establishes rigorous, novel and widely applicable stability guarantees and transferability bounds for graph convolutional networks -- without reference to any underlying limit object or statistical distribution. Crucially, utilized graph-shift operators (GSOs) are not necessarily assumed to be normal, allowing for the treatment of networks on both undirected- and for the first time also directed graphs. Stability to node-level perturbations is related to an 'adequate (spectral) covering' property of the filters in each layer. Stability to edge-level perturbations is related to Lipschitz constants and newly introduced semi-norms of filters. Results on stability to topological perturbations are obtained through recently developed mathematical-physics based tools. As an important and novel example, it is showcased that graph convolutional networks are stable under graph-coarse-graining procedures (replacing strongly-connected sub-graphs by single nodes) precisely if the GSO is the graph Laplacian and filters are regular at infinity. These new theoretical results are supported by corresponding numerical investigations.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 15 of its 32 references that are in the map. First posted on arXiv 26 Jan 2023.
Builds on
15 of 32 references.
References · 15
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
- 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
- 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
- 2019Self-Attention Graph Poolingcited by 421
- 2017CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filterscited by 203
- 2019Stability Properties of Graph Neural Networkscited by 125
- 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
- 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
- 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
- 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
- 2015A Mathematical Theory of Deep Convolutional Neural Networks for Feature Extractioncited by 46
3 more
Built on by
Citing papers per year: 2023: 2.
2 papers.