Stability Properties of Graph Neural Networks
Top Cited Papers
- 25 September 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 68 (1053587X) , 5680-5695
Abstract
Graph neural networks (GNNs) have emerged as a powerful tool for nonlinear processing of graph signals, exhibiting success in recommender systems, power outage prediction, and motion planning, among others. GNNs consist of a cascade of layers, each of which applies a graph convolution, followed by a pointwise nonlinearity. In this work, we study the impact that changes in the underlying topology have on the output of the GNN. First, we show that GNNs are permutation equivariant, which implies that they effectively exploit internal symmetries of the underlying topology. Then, we prove that graph convolutions with integral Lipschitz filters, in combination with the frequency mixing effect of the corresponding nonlinearities, yields an architecture that is both stable to small changes in the underlying topology and discriminative of information located at high frequencies. These are two properties that cannot simultaneously hold when using only linear graph filters, which are either discriminative or stable, thus explaining the superior performance of GNNs.Keywords
All Related Versions
Funding Information
- NSF (CCF 1717120)
- ARO (W911NF1710438)
- ARL DCIST (W911NF-17-2-0181)
- ISTC-WAS
- Intel DevCloud
- Alfred P. Sloan Foundation
- NSF (RI-1816753, CIF 1845360)
- Samsung
This publication has 27 references indexed in Scilit:
- Optimal Graph-Filter Design and Applications to Distributed Linear Network OperatorsIEEE Transactions on Signal Processing, 2017
- Deep learningNature, 2015
- Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency FramesIEEE Transactions on Signal Processing, 2015
- Discrete Signal Processing on Graphs: Frequency AnalysisIEEE Transactions on Signal Processing, 2014
- Invariant Scattering Convolution NetworksIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- An Improved Particle Swarm Optimization (PSO)–Based MPPT for PV With Reduced Steady-State OscillationIEEE Transactions on Power Electronics, 2012
- Group Invariant ScatteringCommunications on Pure and Applied Mathematics, 2012
- Wavelets on graphs via spectral graph theoryApplied and Computational Harmonic Analysis, 2011
- Diffusion waveletsApplied and Computational Harmonic Analysis, 2006
- Diffusion mapsApplied and Computational Harmonic Analysis, 2006