2020 · 73 citations · 15 references
ComputingComputer ScienceEdge ComputingMachine LearningStochastic ModelingBias-variance TradeoffDeep LearningGraph-based LearningNeural NetworksOptimization For Machine LearningResampling MethodsConvergenceConvergence Rate AnalysisGraph Neural NetworksMini-batch Gradient DescentMini-batch LearningMini-batch TrainingNetwork GraphsStochastic Gradient Descent
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 intoembedding approximation variance in the forward stage andstochastic 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.
15
Inductive Representation Learning on Large Graphs
William L. Hamilton, Rex Ying, Jure Leskovec · arXiv (Cornell University) · 2017 · 4.5K citations · Full text
Graph Convolutional Neural Networks for Web-Scale Recommender Systems
2018 · 2.8K citations · Full text
Xiang Wang, Xiangnan He, Yixin Cao et al. · 2019 · 2.1K citations · Full text
Wei-Lin Chiang, Xuanqing Liu, Si Si et al. · 2019 · 1.2K citations · Full text
Zhiyong Cui, Kristian Henrickson, Ruimin Ke et al. · IEEE Transactions on Intelligent Transportation Systems · 2019 · 955 citations