Graph Neural Tangent Kernel: Convergence on Large Graphs

Sanjukta Krishnagopal, Luana Ruiz
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:17827-17841, 2023.

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 problem’s learning directions, converges to the spectrum of the GNTK. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-krishnagopal23a, title = {Graph Neural Tangent Kernel: Convergence on Large Graphs}, author = {Krishnagopal, Sanjukta and Ruiz, Luana}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {17827--17841}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/krishnagopal23a/krishnagopal23a.pdf}, url = {https://proceedings.mlr.press/v202/krishnagopal23a.html}, 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 problem’s learning directions, converges to the spectrum of the GNTK. 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.} }
Endnote
%0 Conference Paper %T Graph Neural Tangent Kernel: Convergence on Large Graphs %A Sanjukta Krishnagopal %A Luana Ruiz %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-krishnagopal23a %I PMLR %P 17827--17841 %U https://proceedings.mlr.press/v202/krishnagopal23a.html %V 202 %X 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 problem’s learning directions, converges to the spectrum of the GNTK. 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.
APA
Krishnagopal, S. & Ruiz, L.. (2023). Graph Neural Tangent Kernel: Convergence on Large Graphs. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:17827-17841 Available from https://proceedings.mlr.press/v202/krishnagopal23a.html.

Related Material