GraphSAINT

Scaling GCNs to large graphs meant fighting neighbor explosion: a two-layer minibatch can pull in thousands of nodes per target. Prior work sampled across layers, which kept minibatches small but sparse and slow. GraphSAINT flips the perspective: sample the training graph first, then build a complete GCN on the sampled subgraph. Because sampling is decoupled from propagation, each minibatch is a small but well-connected graph, which trains faster and more accurately. The catch is that influential nodes get sampled more often, biasing the estimator, so the paper adds normalization terms that provably remove the bias, plus lightweight samplers (node, edge, random-walk based) designed for variance reduction.\n\nThe ICLR 2020 paper reports new state-of-the-art micro-F1 at the time on both PPI (0.995) and Reddit (0.970), with better training time than layer-sampling baselines on five large graphs. It also shows the sampler composes with other architectures: GraphSAINT minibatches plus JKNet or GAT backbones set the new records. GraphSAINT remains one of the standard scalable-training recipes alongside Cluster-GCN and is implemented in DGL.

Paper-reported: 0.995 micro-F1 on PPI and 0.970 on Reddit (new SOTA at publication), with faster training than layer-sampling baselines on five large graphs (Zeng et al., ICLR 2020).