LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence

Understand

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.