mlsanityData to 7 Oct 2026

Graph Neural Tangent Kernel: Convergence on Large Graphs

arXiv 2301.10808 ↗First posted 25 Jan 2023cs.LG math.ST stat.APcited by 16

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) achieve remarkable performance in graph machine learning tasks but can be hard to train on large-graph data, where their learning dynamics are not well understood. We investigate the training dynamics of large-graph GNNs using graph neural tangent kernels (GNTKs) and graphons. In the limit of large width, optimization of an overparametrized NN is equivalent to kernel regression on the NTK. Here, we investigate how the GNTK evolves as another independent dimension is varied: the graph size. We use graphons to define limit objects -- graphon NNs for GNNs, and graphon NTKs for GNTKs -- , and prove that, on a sequence of graphs, the GNTKs converge to the graphon NTK. We further prove that the spectrum of the GNTK, which is related to the directions of fastest learning which becomes relevant during early stopping, converges to the spectrum of the graphon NTK. This implies that in the large-graph limit, the GNTK fitted on a graph of moderate size can be used to solve the same task on the large graph, and to infer the learning dynamics of the large-graph GNN. These results are verified empirically on node regression and classification tasks.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 32 of its 45 references that are in the map. First posted on arXiv 25 Jan 2023.

Builds on

32 of 45 references.

References · 32

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  8. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  9. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  10. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  11. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  12. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 332
20 more
  1. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  2. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  3. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  4. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  5. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  6. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
  7. 2018Convolutional Neural Network Architectures for Signals Supported on Graphscited by 94
  8. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  9. 2019Harnessing the Power of Infinitely Wide Deep Nets on Small-data Taskscited by 87
  10. 2019Enhanced Convolutional Neural Tangent Kernelscited by 76
  11. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  12. 2020Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspectivecited by 60
  13. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  14. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  15. 2021Transferability Properties of Graph Neural Networkscited by 42
  16. 2020Graphon Signal Processingcited by 37
  17. 2021Learning by Transference: Training Graph Neural Networks on Growing Graphscited by 22
  18. 2022Implicit Graphon Neural Representationcited by 18
  19. 2022Training Graph Neural Networks on Growing Stochastic Graphscited by 5
  20. 2021New Insights into Graph Convolutional Networks using Neural Tangent Kernelscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 0; 2025: 8; 2026: 5.

16 papers.

Sort:

  1. 2025Nonparametric Teaching for Graph Property Learnerscited by 5
  2. 2025Dynamic Bundling with Large Language Models for Zero-Shot Inference on Text-Attributed Graphscited by 3
  3. 2023Manifold Filter-Combine Networkscited by 2
  4. 2025The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysiscited by 2
  5. 2023A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphscited by 1
  6. 2023Neural Tangent Kernels Motivate Graph Neural Networks with Cross-Covariance Graphscited by 0
  7. 2025Convexified Message-Passing Graph Neural Networkscited by 0
  8. 2025Simplifying Graph Kernels for Efficientcited by 0
  9. 2025Neighborhood Sampling Does Not Learn the Same Graph Neural Networkcited by 0
  10. 2025On the Convergence and Size Transferability of Continuous-depth Graph Neural Networkscited by 0
  11. 2025Fighter: Unveiling the Graph Convolutional Nature of Transformers in Time Series Modelingcited by 0
  12. 2026Pruning at Initialisation through the lens of Graphon Limit: Convergence, Expressivity, and Generalisationcited by 0
4 more
  1. 2026Topological Neural Tangent Kernelcited by 0
  2. 2026Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networkscited by 0
  3. 2026Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networkscited by 0
  4. 2026Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attackscited by 0