Research map / Graph learning / GNN architectures
How Graph Neural Networks Learn: Lessons from Training Dynamics
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.
Studies GNN training dynamics in function space via the NTK, shows gradient descent aligns the NTK with the graph adjacency ("kernel-graph alignment"), and proposes parameter-free Residual Propagation that matches GNN accuracy while being much faster.
Problem
Whether GNNs learn the desired generalizable function during gradient-descent optimization, and when and why they generalize or fail (e.g., on heterophilic graphs), is poorly understood beyond expressiveness results.
Approach
Analyze GNN training dynamics through the neural tangent kernel and show that, in the overparameterized regime, the GNN NTK is recursively built from the adjacency matrix so it aligns with the graph (kernel-graph alignment); a parameter-free Residual Propagation algorithm replaces the NTK with a power of the adjacency matrix to propagate residuals.
Key results
- Residual Propagation reaches 78.25% test accuracy on OGBN-Products versus 75.64% for GCN, and 78.17% ROC-AUC on Proteins versus 72.51% for GCN.
- Each RP step is reported as roughly 12 to 14 times faster than a GCN training step on OGB datasets, with memory use reduced to 0.094x to 0.363x of GNN.
- Empirically, GNN NTK kernel-graph alignment stays high across synthetic homophily levels, and kernel-target alignment drops with lower homophily, degrading test accuracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the GNN with adjacency-based Residual Propagation | GNN · Arxiv test | accuracy: 71.74 $\pm$ 0.29 -> 70.06 $\pm$ 0.00 | Hurt |
| Replace LP with adjacency-based Residual Propagation | LP · Proteins test | ROC-AUC: 74.73 $\pm$ 0.00 -> 78.17 $\pm$ 0.00 | Helped |
| Replace the GNN with adjacency-based Residual Propagation | GNN · Products test | accuracy: 75.64 $\pm$ 0.21 -> 78.25 $\pm$ 0.00 | Helped |
| Replace GNN gradient descent with sparse adjacency-based Residual Propagation | GNN · Arxiv | speedup / step: $\times$ 14.48 | Helped |
| Replace GNN gradient descent with sparse adjacency-based Residual Propagation | GNN · Proteins | speedup / step: $\times$ 14.00 | Helped |
| Replace GNN gradient descent with sparse adjacency-based Residual Propagation | GNN · Products | speedup / step: $\times$ 12.46 | Helped |
| Replace GNN gradient descent with sparse adjacency-based Residual Propagation | GNN · Arxiv | memory: $\times$ 0.094 | Helped |
Surprising findings
- Residual Propagation outperforms GNNs on several OGB benchmarks despite having no trainable parameters.
- RP in practice performs well even when it does not converge in theory, with test performance not compromised.
Limitations
- Theoretical analysis holds in the infinite-width, overparameterized regime, approximating finite-width GNN training.
- Generalization bound and Bayesian optimality rely on homophily-based assumptions and i.i.d. training samples.
- RP may not converge in general since the propagation matrix is not restricted to PSD.
Experimental setup
Datasets: OGBN-Arxiv OGBN-Proteins OGBN-Products Cora Citeseer Pubmed Computers Photo CS Physics roman-empire amazon-ratings
Benchmarks: OGBN-Arxiv OGBN-Proteins OGBN-Products Cora Citeseer Pubmed roman-empire amazon-ratings minesweeper tolokers questions
Metrics: accuracy ROC-AUC speedup memory usage
Baselines: GCN LinearGNN label propagation MLP SGC
Builds on: neural tangent kernel label propagation SGC GCN APPNP
Closest papers by meaning
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.92)
- What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.91)
- Dynamic Rescaling for Training GNNs (NeurIPS 2024 · similarity 0.90)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.90)
- Neural Tangent Kernels Motivate Cross-Covariance Graphs in Neural Networks (ICML 2024 · similarity 0.90)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.90)
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.