Stability and Generalization of Graph Convolutional Neural Networks

Abstract

Inspired by convolutional neural networks on 1D and 2D data, graph convolutional neural networks (GCNNs) have been developed for various learning tasks on graph data, and have shown superior performance on real-world datasets. Despite their success, there is a dearth of theoretical explorations of GCNN models such as their generalization properties. In this paper, we take a first step towards developing a deeper theoretical understanding of GCNN models by analyzing the stability of single-layer GCNN models and deriving their generalization guarantees in a semi-supervised graph learning setting. In particular, we show that the algorithmic stability of a GCNN model depends upon the largest absolute eigenvalue of its graph convolution filter. Moreover, to ensure the uniform stability needed to provide strong generalization guarantees, the largest absolute eigenvalue must be independent of the graph size. Our results shed new insights on the design of new & improved graph convolution filters with guaranteed algorithmic stability. We evaluate the generalization gap and stability on various real-world graph datasets and show that the empirical results indeed support our theoretical findings. To the best of our knowledge, we are the first to study stability bounds on graph learning in a semi-supervised setting and derive generalization bounds for GCNN models.

Accepted at The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2019)

References in corpus (19)

• 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
• Inductive Representation Learning on Large Graphs
• Spectral Networks and Locally Connected Networks on Graphs
• Deep Convolutional Networks on Graph-Structured Data
• Understanding deep learning requires rethinking generalization
• Variational Graph Auto-Encoders
• Discriminative Embeddings of Latent Variable Models for Structured Data
• How Powerful are Graph Neural Networks?
• Train faster, generalize better: Stability of stochastic gradient descent
• Robust Spatial Filtering with Graph Convolutional Neural Networks
• Adaptive Graph Convolutional Neural Networks
• Graph Capsule Convolutional Neural Networks
• Benefits of depth in neural networks
• Covariant Compositional Networks For Learning Graphs
• Exploring Graph-structured Passage Representation for Multi-hop Reading Comprehension with Graph Neural Networks
• Learning Graph Representations with Embedding Propagation
• Deriving Neural Architectures from Sequence and Graph Kernels
• Unifying local and non-local signal processing with graph CNNs

Cited by in corpus (6)

• Understanding Isomorphism Bias in Graph Data Sets
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
• Learning Universal Graph Neural Network Embeddings With Aid Of Transfer Learning
• Fundamental Limits of Deep Graph Convolutional Networks
• On the Stability of Graph Convolutional Neural Networks under Edge Rewiring
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version