ECHO: Adaptive Correction for Subgraph-Wise Sampling with Lightweight Hyperparameter Search

Graph neural networks (GNNs) excel in a wide range of complex graph-based tasks. When training GNNs on large datasets, subgraph-wise sampling (SS) methods have shown remarkable speed-up per epoch by avoiding recursive sampling in node-wise sampling (NS) ones. However, this comes at the cost of a larger variance in estimating stochastic gradients, resulting in either slow convergence or low accuracy. In this paper, we first delve into the variance of SS methods and reveal that it can be further decoupled into two components: graph drop variance and skewed sample variance. We then propose ECHO that mitigates the negative impact of variances, in order to achieve comparable accuracy to node-wise sampling while greatly accelerating training in large datasets. Specifically, ECHO introduces a variance-aware hyperparameter search algorithm that leverages lightweight variance estimation in the preprocessing stage. In the training stage, ECHO adaptively incorporates neighbor sampling epochs into the training process as correction according to the training loss. Our theoretical analysis and extensive experiments demonstrate that ECHO achieves fast convergence with high accuracy. Specifically, ECHO achieves up to 3.5 \(\times \) training time speed-up and comparable accuracy compared to node-wise sampling; in comparison with SS baselines, ECHO achieves the best accuracy and up to 11 \(\times \) convergence speed-up.