Reproduce “Implicit Regularization of Mini-Batch Training in Graph Neural Networks” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Clement Wang, Antoine Vialle, Robin Vaysse, Thomas Bonald
This work characterizes the objective function implicitly optimized when Graph Neural Networks are trained with sampled subgraphs, particularly Random Node Sampling (RNS). It demonstrates that RNS implicitly minimizes a modified objective due to its influence on batch gradient variance, achieving superior accuracy while offering 2x to 12x wall-clock speedups and up to 3x memory reduction on large-scale datasets compared to full-graph training.
Key insights
- Mini-batch SGD in GNNs implicitly minimizes a modified objective that includes a regularization term proportional to the variance of per-batch gradients, directly influenced by the chosen sampler.
- Random Node Sampling (RNS) inherently produces significantly lower batch gradient variance and per-batch loss variance compared to structure-aware samplers, leading to more stable gradient estimates and a beneficial implicit regularization effect.
- RNS's effectiveness is not solely due to preserving local graph structure but also to its ability to maintain favorable gradient statistics, partly by preserving power-law degree distributions in its mini-batches.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.