Learning Graph Neural Networks with Approximate Gradient Descent

Abstract

The first provably efficient algorithm for learning graph neural networks (GNNs) with one hidden layer for node information convolution is provided in this paper. Two types of GNNs are investigated, depending on whether labels are attached to nodes or graphs. A comprehensive framework for designing and analyzing convergence of GNN training algorithms is developed. The algorithm proposed is applicable to a wide range of activation functions including ReLU, Leaky ReLU, Sigmod, Softplus and Swish. It is shown that the proposed algorithm guarantees a linear convergence rate to the underlying true parameters of GNNs. For both types of GNNs, sample complexity in terms of the number of nodes or the number of graphs is characterized. The impact of feature dimension and GNN structure on the convergence rate is also theoretically characterized. Numerical experiments are further provided to validate our theoretical analysis.

arXiv comment23 pages, accepted at AAAI 2021

References in corpus (17)

• Graph Neural Networks: A Review of Methods and Applications
• Recent Trends in Deep Learning Based Natural Language Processing
• The Loss Surfaces of Multilayer Networks
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Learning One-hidden-layer Neural Networks with Landscape Design
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Reliably Learning the ReLU in Polynomial Time
• Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• Topology and Geometry of Half-Rectified Network Optimization
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• Learning Halfspaces and Neural Networks with Random Initialization
• Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networks
• The Landscape of Deep Learning Algorithms