Stability and Generalization of Graph Convolutional Neural Networks
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsGraph LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization
Graph convolutional networks (GCNs) have emerged as powerful models for graph learning tasks, exhibiting promising performance in various domains. While their empirical success is evident, there is a growing need to unde…
Graph LearningStability to Deformations of Manifold Filters and Manifold Neural Networks
The paper defines and studies manifold (M) convolutional filters and neural networks (NNs). \emph{Manifold} filters and MNNs are defined in terms of the Laplace-Beltrami operator exponential and are such that \emph{graph…
Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion
Graph neural networks are widely used tools for graph prediction tasks. Motivated by their empirical performance, prior works have developed generalization bounds for graph neural networks, which scale with graph structu…
Generalization BoundsGraph Neural Networks: Architectures, Stability and Transferability
Graph Neural Networks (GNNs) are information processing architectures for signals supported on graphs. They are presented here as generalizations of convolutional neural networks (CNNs) in which individual layers contain…
Recommendation SystemsAn Experimental Study of the Transferability of Spectral Graph Networks
Spectral graph convolutional networks are generalizations of standard convolutional networks for graph-structured data using the Laplacian operator. A common misconception is the instability of spectral filters, i.e. the…
BenchmarkingGeneral ClassificationGraph ClassificationGraph Regression+1