  The message passing-based graph neural networks (GNNs) have achieved great
success in many real-world applications. However, training GNNs on large-scale
graphs suffers from the well-known neighbor explosion problem, i.e., the
exponentially increasing dependencies of nodes with the number of message
passing layers. Subgraph-wise sampling methods -- a promising class of
mini-batch training techniques -- discard messages outside the mini-batches in
backward passes to avoid the neighbor explosion problem at the expense of
gradient estimation accuracy. This poses significant challenges to their
convergence analysis and convergence speeds, which seriously limits their
reliable real-world applications. To address this challenge, we propose a novel
subgraph-wise sampling method with a convergence guarantee, namely Local
Message Compensation (LMC). To the best of our knowledge, LMC is the {\it
first} subgraph-wise sampling method with provable convergence. The key idea of
LMC is to retrieve the discarded messages in backward passes based on a message
passing formulation of backward passes. By efficient and effective
compensations for the discarded messages in both forward and backward passes,
LMC computes accurate mini-batch gradients and thus accelerates convergence. We
further show that LMC converges to first-order stationary points of GNNs.
Experiments on large-scale benchmark tasks demonstrate that LMC significantly
outperforms state-of-the-art subgraph-wise sampling methods in terms of
efficiency.
