Stability Properties of Graph Neural Networks

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 consists 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.

Submitted to IEEE Transactions on Signal Processing

References in corpus (14)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Graph Convolutional Neural Networks for Web-Scale Recommender Systems
• Discrete Signal Processing on Graphs
• Adversarial Attacks on Neural Networks for Graph Data
• Convolutional Neural Network Architectures for Signals Supported on Graphs
• Adversarial Attack and Defense on Graph Data: A Survey
• Universal Invariant and Equivariant Graph Neural Networks
• Certifiable Robustness and Robust Training for Graph Convolutional Networks
• Invariant and Equivariant Graph Networks
• Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective
• Graph Convolutional Neural Networks via Scattering
• Invariance-Preserving Localized Activation Functions for Graph Neural Networks
• Certifiable Robustness to Graph Perturbations
• Diffusion Scattering Transforms on Graphs

Cited by in corpus (51)

• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Kernel Mean Embedding of Distributions: A Review and Beyond
• Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks
• Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks
• Graph-based Deep Learning for Communication Networks: A Survey
• Graph signal processing for machine learning: A review and new perspectives
• Gated Graph Recurrent Neural Networks
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Invariance-Preserving Localized Activation Functions for Graph Neural Networks
• Coordinated Sum-Rate Maximization in Multicell MU-MIMO with Deep Unrolling
• Graphon Signal Processing
• Graphon Neural Networks and the Transferability of Graph Neural Networks
• Bayesian Estimation of Graph Signals
• Stochastic Graph Neural Networks
• A Tutorial on Ultra-Reliable and Low-Latency Communications in 6G: Integrating Domain Knowledge into Deep Learning
• Wide and Deep Graph Neural Network with Distributed Online Learning
• Algebraic Neural Networks: Stability to Deformations
• Graph-based Algorithm Unfolding for Energy-aware Power Allocation in Wireless Networks
• Graph Policy Gradients for Large Scale Robot Control
• Convolutional Learning on Multigraphs
• Graph Neural Networks for Motion Planning
• Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning
• On Local Distributions in Graph Signal Processing
• Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping
• A Simple Spectral Failure Mode for Graph Convolutional Networks
• Input State Stability of Gated Graph Neural Networks
• Learning Stochastic Graph Neural Networks with Constrained Variance
• Graph and graphon neural network stability
• Graph Convolution with Low-rank Learnable Local Filters
• Spatiotemporal Covariance Neural Networks
• Interpretable Stability Bounds for Spectral Graph Filters
• $p$-Laplacian Based Graph Neural Networks
• Modelling Graph Errors: Towards Robust Graph Signal Processing
• Complete Neural Networks for Complete Euclidean Graphs
• Wireless Link Scheduling via Graph Representation Learning: A Comparative Study of Different Supervision Levels
• Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model
• VGAI: End-to-End Learning of Vision-Based Decentralized Controllers for Robot Swarms
• Stability of Neural Networks on Riemannian Manifolds
• Quiver Signal Processing (QSP)
• On the Stability of Graph Convolutional Neural Networks under Edge Rewiring
• Represented Value Function Approach for Large Scale Multi Agent Reinforcement Learning
• Scalable Perception-Action-Communication Loops with Convolutional and Graph Neural Networks
• Stability of Graph Convolutional Neural Networks to Stochastic Perturbations
• Foresight of Graph Reinforcement Learning Latent Permutations Learnt by Gumbel Sinkhorn Network
• Convolutional Filtering and Neural Networks with Non Commutative Algebras
• Graph Neural Networks for Distributed Linear-Quadratic Control
• Wide and Deep Graph Neural Networks with Distributed Online Learning
• Spherical Convolutional Neural Networks: Stability to Perturbations in SO(3)
• Framework for Designing Filters of Spectral Graph Convolutional Neural Networks in the Context of Regularization Theory
• Interferometric Graph Transform for Community Labeling