Research map / Graph learning / GNN architectures
Accurate and Scalable Graph Neural Networks via Message Invariance
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 TOP, a subgraph-sampling mini-batch method for GNNs that replaces out-of-batch message passing with a linear, pre-estimated topological compensation learned from random-initialization embeddings, enabling fast training on billion-edge graphs.
Problem
Mini-batch GNN training suffers from neighbor explosion; subgraph sampling is fast but drops out-of-batch messages (MP_OB), hurting accuracy, while recursive samplers are accurate but slow.
Approach
Define message invariance: a transformation g of in-batch embeddings that reproduces out-of-batch embeddings, so MP_OB can be converted into an in-batch edge reweighting. TOP estimates a linear g by least squares on random-initialization basic embeddings, precomputes the compensation edges, and then trains GCN-style models on the modified in-batch subgraph only.
Key results
- Average relative approximation error of TOP across datasets and GNNs is 3.46% at 10% subgraph ratio, versus 17.86% for CLUSTER and 15.54% for GAS.
- TOP achieves up to 11x speedup over GAS per epoch on Ogbn-products, and is orders of magnitude faster than CLUSTER and GAS on Ogbn-papers100M.
- Against NS and LABOR, TOP speedup is more than 2x on all datasets with accuracy close to full-batch.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TOP instead of GAS | Subgraph sampling for GNNs · Average across datasets, 10% subgraph ratio | relative approximation error: 15.54% -> 3.46% | Helped |
| Use TOP instead of CLUSTER | Subgraph sampling for GNNs · Average across datasets, 10% subgraph ratio | relative approximation error: 17.86% -> 3.46% | Helped |
| Use TOP instead of GAS | Subgraph sampling for GNNs · Average across datasets, 10% subgraph ratio | test accuracy degradation: 2.36% -> 0.31% | Helped |
| Use TOP instead of CLUSTER | Subgraph sampling for GNNs · Average across datasets, 10% subgraph ratio | test accuracy degradation: 3.68% -> 0.31% | Helped |
| Remove validation and test nodes from sampled subgraphs (ablation) | CLUSTER on Ogbn-products and Ogbn-papers · Ogbn-products and Ogbn-papers | test accuracy | Hurt |
Surprising findings
- Basic embeddings from random initialization suffice to estimate the compensation accurately, without training-time updates in most experiments.
Limitations
- Message invariance via linear transformation is only approximate for non-linear GNNs; non-linear transformations need empirical evaluation.
- Results with 5 GNN backbones on mainly 8 datasets; generalization to graph transformers or global communication not shown.
- Pre-processing estimates compensation from random-initialization embeddings, which can have high error when they fail to capture the trained model's embeddings.
Experimental setup
Datasets: Reddit Yelp Ogbn-arxiv Ogbn-products Ogbn-papers100M amazon-ratings minesweeper questions
Benchmarks: Reddit Yelp Ogbn-arxiv Ogbn-products Ogbn-papers100M
Metrics: test accuracy runtime GPU memory relative approximation error accuracy degradation
Baselines: Full-batch CLUSTER GAS SAINT IBMB NS LABOR LMC
Builds on: GAS Cluster-GCN GraphSAINT LMC LABOR
Closest papers by meaning
- Towards Dynamic Message Passing on Graphs (NeurIPS 2024 · similarity 0.89)
- Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs (ICML 2024 · similarity 0.89)
- Graph Coarsening with Message-Passing Guarantees (NeurIPS 2024 · similarity 0.88)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.88)
- Spatio-Spectral Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.88)
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.