Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
arXiv:2006.13866
Abstract
Sampling methods (e.g., node-wise, layer-wise, or subgraph) has become an indispensable strategy to speed up training large-scale Graph Neural Networks (GNNs). However, existing sampling methods are mostly based on the graph structural information and ignore the dynamicity of optimization, which leads to high variance in estimating the stochastic gradients. The high variance issue can be very pronounced in extremely large graphs, where it results in slow convergence and poor generalization. In this paper, we theoretically analyze the variance of sampling methods and show that, due to the composite structure of empirical risk, the variance of any sampling method can be decomposed into \textit{embedding approximation variance} in the forward stage and \textit{stochastic gradient variance} in the backward stage that necessities mitigating both types of variance to obtain faster convergence rate. We propose a decoupled variance reduction strategy that employs (approximate) gradient information to adaptively sample nodes with minimal variance, and explicitly reduces the variance introduced by embedding approximation. We show theoretically and empirically that the proposed method, even with smaller mini-batch sizes, enjoys a faster convergence rate and entails a better generalization compared to the existing methods.
References in corpus (14)
- PyTorch: An Imperative Style, High-Performance Deep Learning Library
- Semi-Supervised Classification with Graph Convolutional Networks
- Inductive Representation Learning on Large Graphs
- KGAT: Knowledge Graph Attention Network for Recommendation
- Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
- Graph Convolutional Matrix Completion
- FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
- GraphSAINT: Graph Sampling Based Inductive Learning Method
- Stochastic Training of Graph Convolutional Networks with Variance Reduction
- Not All Samples Are Created Equal: Deep Learning with Importance Sampling
- Adaptive Graph Convolutional Neural Networks
- Randomized Dual Coordinate Ascent with Arbitrary Sampling
- Stochastic Dual Coordinate Ascent with Adaptive Probabilities
- Coordinate Descent with Bandit Sampling