  Subgraph-wise sampling -- a promising class of mini-batch training techniques
for graph neural networks (GNNs -- is critical for real-world applications.
During the message passing (MP) in GNNs, subgraph-wise sampling methods discard
messages outside the mini-batches in backward passes to avoid the well-known
neighbor explosion problem, i.e., the exponentially increasing dependencies of
nodes with the number of MP iterations. However, discarding messages may
sacrifice the gradient estimation accuracy, posing significant challenges to
their convergence analysis and convergence speeds. 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 first subgraph-wise sampling method with provable convergence. The key idea
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.
Moreover, LMC is applicable to various MP-based GNN architectures, including
convolutional GNNs (finite message passing iterations with different layers)
and recurrent GNNs (infinite message passing iterations with a shared layer).
Experiments on large-scale benchmarks demonstrate that LMC is significantly
faster than state-of-the-art subgraph-wise sampling methods.
