# Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels

arXiv: https://arxiv.org/abs/1905.13192 · HTML: https://mlsanity.com/paper/1905.13192/

## Key facts

- Cited by 161 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2019.

## Built on by (most cited first, 30 of 161)

- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [Subgraph Federated Learning with Missing Neighbor Generation](https://mlsanity.com/paper/2106.13430/) (2021)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)
- [Fast Finite Width Neural Tangent Kernel](https://mlsanity.com/paper/2206.08720/) (2022)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics](https://mlsanity.com/paper/2105.03703/) (2021)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [KerGNNs: Interpretable Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/2201.00491/) (2022)
- [Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing](https://mlsanity.com/paper/2102.08786/) (2021)
- [Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs](https://mlsanity.com/paper/2212.09034/) (2022)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Fast Graph Condensation with Structure-based Neural Tangent Kernel](https://mlsanity.com/paper/2310.11046/) (2023)
- [Deep Active Learning by Leveraging Training Dynamics](https://mlsanity.com/paper/2110.08611/) (2021)
- [Neural Tangent Kernel Beyond the Infinite-Width Limit: Effects of Depth and Initialization](https://mlsanity.com/paper/2202.00553/) (2022)
- [NeuralEF: Deconstructing Kernels by Deep Neural Networks](https://mlsanity.com/paper/2205.00165/) (2022)
- [Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime](https://mlsanity.com/paper/2112.08297/) (2021)
- [Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling](https://mlsanity.com/paper/2207.03584/) (2022)
- [Graph Condensation: A Survey](https://mlsanity.com/paper/2401.11720/) (2024)
- [Neural Network Field Theories: Non-Gaussianity, Actions, and Locality](https://mlsanity.com/paper/2307.03223/) (2023)
- [Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels](https://mlsanity.com/paper/2104.02995/) (2021)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)

## Abstract (arXiv)

While graph kernels (GKs) are easy to train and enjoy provable theoretical guarantees, their practical performances are limited by their expressive power, as the kernel function often depends on hand-crafted combinatorial features of graphs. Compared to graph kernels, graph neural networks (GNNs) usually achieve better practical performance, as GNNs use multi-layer architectures and non-linear activation functions to extract high-order information of graphs as features. However, due to the large number of hyper-parameters and the non-convex nature of the training procedure, GNNs are harder to train. Theoretical guarantees of GNNs are also not well-understood. Furthermore, the expressive power of GNNs scales with the number of parameters, and thus it is hard to exploit the full power of GNNs when computing resources are limited. The current paper presents a new class of graph kernels, Graph Neural Tangent Kernels (GNTKs), which correspond to infinitely wide multi-layer GNNs trained by gradient descent. GNTKs enjoy the full expressive power of GNNs and inherit advantages of GKs. Theoretically, we show GNTKs provably learn a class of smooth functions on graphs. Empirically, we test GNTKs on graph classification datasets and show they achieve strong performance.