Research map / Graph learning / GNN architectures
Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes REST, which decouples forward and backward passes in historical-embedding GNN training so the memory table refreshes more often than model parameters, reducing staleness and improving accuracy and convergence on large graphs.
Problem
Historical-embedding GNN training methods (GAS, VR-GCN, MVS-GCN, GraphFM) suffer from stale embeddings that bias gradients, causing inferior accuracy and slow convergence on large graphs, especially with small batch sizes.
Approach
Decouple forward and backward propagation: run F extra no-gradient forward passes that refresh the historical embedding memory with in-batch nodes, then one gradient-bearing forward/backward pass to update parameters, shrinking the update-frequency gap from k to k/F. A variant (REST-IS) refreshes memory with neighbor nodes of the sampled batch as an importance-sampling proxy.
Key results
- REST with GCNII reaches 73.2% on ogbn-arxiv and REST-IS with APPNP reaches 80.5% on ogbn-products in the main comparison.
- On ogbn-products with batch size 5 and APPNP, GAS improves from 75.0% to 79.7% (REST) and 80.4% (REST-IS).
- On ogbn-papers100M, GAS+REST improves accuracy from 64.9% to 67.6% while running in about half the time (4100s vs 8840s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add REST (decoupled forward/backward frequencies, F=1) (ablation) | GAS · ogbn-products, GCN, BS 10 | accuracy: +2.9 (76.5 to 79.4) | Helped |
| add REST (decoupled forward/backward frequencies, F=1) (ablation) | GAS · ogbn-arxiv, GCN, BS 5 | accuracy: +3.5 (67.6 to 71.1) | Helped |
| add REST-IS (importance sampling variant) (ablation) | GAS · ogbn-products, APPNP, BS 5 | accuracy: +5.4 (75.0 to 80.4) | Helped |
| add REST-IS importance sampling vs REST uniform sampling (ablation) | GAS with GCN backbone · ogbn-products, GCN, BS 10 | accuracy: -0.8 (79.4 to 78.6) | Hurt |
| add REST (ablation) | GAS with GraphFM-style comparisons / GraphFM · ogbn-products, GCN, BS 10 (GraphFM) | accuracy: +3.0 (76.9 to 79.9) | Helped |
| add REST (ablation) | GAS on large datasets · ogbn-papers100M and MAG240M | accuracy: +2.7 on papers100M (64.9 to 67.6); +6.4 on MAG240M (61.2 to 67.6) | Helped |
| increase number of propagation layers from 1 to 5 with REST (ablation) | GAS+REST on ogbn-arxiv · ogbn-arxiv, APPNP, layers L=1 to L=5 | accuracy: GAS+REST rises 71.9 to 72.5 at L=5; GAS drops over layers | Mixed |
| add REST to VR-GCN and MVS-GCN (ablation) | VR-GCN / MVS-GCN · ogbn-products and Reddit and ogbn-arxiv, various batch sizes | accuracy: e.g. VR-GCN +1.1 on products BS 10000 (76.3 to 77.4); MVS-GCN +1.2 (76.7 to 77.9) | Helped |
| reduce learning rate instead of REST frequency (ablation) | REST training · ogbn-products | accuracy: learning rate 0.0002 gives 79.7 vs Frequency 5 gives 80.5 | Hurt |
| add LMC+REST (decoupled gradient memory updates) (ablation) | LMC · ogbn-products, GCN | accuracy: +2.6 (77.5 to 80.1) | Helped |
Surprising findings
- Historical embedding methods such as GAS and GraphFM fail to consistently outperform the simple GraphSAGE sampler on ogbn-products.
- Reducing the learning rate by the same factor as the frequency F does not match REST's accuracy and convergence speed.
Limitations
- Each training iteration requires F additional forward passes, so per-epoch cost increases.
- Theoretical convergence claim relies on upper-bound arguments under Lipschitz assumptions rather than tight guarantees.
Experimental setup
Datasets: Reddit ogbn-arxiv ogbn-products ogbn-papers100M MAG240M
Benchmarks: Reddit ogbn-arxiv ogbn-products ogbn-papers100M MAG240M
Metrics: accuracy memory usage (MB) running time (s)
Baselines: GraphSAGE FastGCN LADIES Cluster-GCN GraphSAINT SGC VR-GCN MVS-GCN GAS GraphFM LMC Refresh
Builds on: GNNAutoScale GraphFM VR-GCN MVS-GCN
Closest papers by meaning
- Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuning (ICLR 2025 · similarity 0.88)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.88)
- MuseGNN: Forming Scalable, Convergent GNN Layers that Minimize a Sampling-Based Energy (ICLR 2025 · similarity 0.87)
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.87)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.87)
- Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.