Graph Neural Tangent Kernel: Convergence on Large Graphs

2023/01/25 by Sanjukta Krishnagopal, Krishnagopal, Sanjukta, Luana Ruiz +1 · 7 citations
Computer Science · Materials Science · Neuroscience · #Advanced Graph Neural Networks #Applications (stat.AP) #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Functional Brain Connectivity Studies #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning in Materials Science #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2301.10808

openalex publication_date 2023/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Fighter: Unveiling the Graph Convolutional Nature of Transformers in Time Series Modeling
• On the Convergence and Size Transferability of Continuous-depth Graph Neural Networks
• Neighborhood Sampling Does Not Learn the Same Graph Neural Network
• Simplifying Graph Kernels for Efficient
• Convexified Message-Passing Graph Neural Networks
• Dynamic Bundling with Large Language Models for Zero-Shot Inference on Text-Attributed Graphs
• Nonparametric Teaching for Graph Property Learners

Related

• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?
• New Insights into Graph Convolutional Networks using Neural Tangent Kernels
• Learning by Transference: Training Graph Neural Networks on Growing Graphs
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks