mlsanityData to 14 Oct 2026

Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?

arXiv 2309.07452 ↗First posted 14 Sep 2023cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

A rising trend in theoretical deep learning is to understand why deep learning works through Neural Tangent Kernel (NTK) [jgh18], a kernel method that is equivalent to using gradient descent to train a multi-layer infinitely-wide neural network. NTK is a major step forward in the theoretical deep learning because it allows researchers to use traditional mathematical tools to analyze properties of deep neural networks and to explain various neural network techniques from a theoretical view. A natural extension of NTK on graph learning is textitGraph Neural Tangent Kernel (GNTK), and researchers have already provide GNTK formulation for graph-level regression and show empirically that this kernel method can achieve similar accuracy as GNNs on various bioinformatics datasets [dhs+19]. The remaining question now is whether solving GNTK regression is equivalent to training an infinite-wide multi-layer GNN using gradient descent. In this paper, we provide three new theoretical results. First, we formally prove this equivalence for graph-level regression. Second, we present the first GNTK formulation for node-level regression. Finally, we prove the equivalence for node-level regression.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 48 of its 84 references that are in the map. First posted on arXiv 14 Sep 2023.

Builds on

48 of 84 references.

References · 48

  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  2. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  4. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  6. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  7. 20203DSSD: Point-based 3D Single Stage Object Detectorcited by 440
  8. 2018Deep Learning on Graphs: A Surveycited by 393
  9. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  10. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 179
  11. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  12. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
36 more
  1. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  2. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  3. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  4. 2020GNN3DMOT: Graph Neural Network for 3D Multi-Object Tracking with Multi-Feature Learningcited by 113
  5. 2017Knowledge Transfer for Out-of-Knowledge-Base Entities: A Graph Neural Network Approachcited by 102
  6. 2023Fast Attention Requires Bounded Entriescited by 102
  7. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  8. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  9. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  10. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  11. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  12. 2017Learning ReLUs via Gradient Descentcited by 54
  13. 2019Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluationscited by 50
  14. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  15. 2017Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minimacited by 40
  16. 2022A Faster Small Treewidth SDP Solvercited by 36
  17. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  18. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  19. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  20. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  21. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  22. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  23. 2020Generalized Leverage Score Sampling for Neural Networkscited by 26
  24. 2018BourGAN: Generative Networks with Metric Embeddingscited by 22
  25. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  26. 2022A Sublinear Adversarial Training Algorithmcited by 22
  27. 2018Subspace Embedding and Linear Regression with Orlicz Normcited by 19
  28. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  29. 2017Learning Non-overlapping Convolutional Neural Networks with Multiple Kernelscited by 14
  30. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  31. 2023Faster Algorithms for Structured Linear and Kernel Support Vector Machinescited by 13
  32. 2020Average Case Column Subset Selection for Entrywise ℓ1-Norm Losscited by 12
  33. 2017Near Optimal Sketching of Low-Rank Tensor Regressioncited by 11
  34. 2021Accumulation of Sub-Sampling Matrices with Applications to Statistical Computationcited by 10
  35. 2023Unveiling the Unseen: A Comprehensive Survey on Explainable Anomaly Detection in Images and Videoscited by 7
  36. 2022Adore: Differentially Oblivious Relational Database Operatorscited by 6

Built on by

Cited by year

Citing papers per year: 2024: 5; 2025: 3.

8 papers.

  1. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 22
  2. 2024Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyondcited by 15
  3. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  4. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  5. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  6. 2024A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizabilitycited by 7
  7. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
  8. 2025Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsificationcited by 0