On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction

Abstract

Graph Convolutional Networks (GCNs) have achieved impressive empirical advancement across a wide variety of semi-supervised node classification tasks. Despite their great success, training GCNs on large graphs suffers from computational and memory issues. A potential path to circumvent these obstacles is sampling-based methods, where at each layer a subset of nodes is sampled. Although recent studies have empirically demonstrated the effectiveness of sampling-based methods, these works lack theoretical convergence guarantees under realistic settings and cannot fully leverage the information of evolving parameters during optimization. In this paper, we describe and analyze a general doubly variance reduction schema that can accelerate any sampling method under the memory budget. The motivating impetus for the proposed schema is a careful analysis of the variance of sampling methods where it is shown that the induced variance can be decomposed into node embedding approximation variance (zeroth-order variance) during forward propagation and layerwise-gradient variance (first-order variance) during backward propagation. We theoretically analyze the convergence of the proposed schema and show that it enjoys an $\mathcal{O}(1/T)$ convergence rate. We complement our theoretical results by integrating the proposed schema in different sampling methods and applying them to different large real-world graphs.

References in corpus (19)

• KGAT: Knowledge Graph Attention Network for Recommendation
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Graph Convolutional Matrix Completion
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Benchmarking Graph Neural Networks
• Adaptive Sampling Towards Fast Graph Representation Learning
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks
• Stochastic Gradient Descent with Biased but Consistent Gradient Estimators
• Bandit Samplers for Training Graph Neural Networks
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth
• Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
• Constant Time Graph Neural Networks
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• A Biased Graph Neural Network Sampler with Near-Optimal Regret