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

By Simon Shaolei Du, Kangcheng Hou, Barnab'as P'oczos, Ruslan Salakhutdinov, Ruosong Wang, Keyulu Xu. Neural Information Processing Systems, 2019

311 citations recorded by the source corpus.

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.

View Paper: https://www.semanticscholar.org/paper/f338528c156f275fcff3e310e157b23980e1bd19

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Neural Tangents: Fast and Easy Infinite Neural Networks in Python (2019, background): “, 2019), as well as graph neural networks (Du et al., 2019).”
Enhanced Convolutional Neural Tangent Kernels (2019, background): “A recent line of work studied overparameterized neural networks where all layers are trained [Allen-Zhu et al., 2018, Du et al., 2019b, 2018, Li and Liang, 2018, Zou et al., 2018].”
Tensor Programs II: Neural Tangent Kernel for Any Architecture (2020, background): “After Yang [63], several works dove into specific kinds of NTKs, such as convolutional [6], graph [19], hypernetworks [48], RNNs [2], attention [34], or NTK with orthogonal initialization [37].”
Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics (2021, background): “, 2020b) and graph neural networks (Du et al., 2019), but none of them formally proved NTKINIT or NTKTRAIN for those architectures.”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, methodology): “[51] model similarity of two graphs using the similarity of the “tangent space” of the objective w.”
Tensor Programs III: Neural Matrix Laws (2020, result): “This resolved many open questions regarding the training and generalization of neural networks, and was followed by intense activity generalizing these results to more modern neural architectures [1, 5, 12, 18, 26, 49].”
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks (2019, background): “Du et al. (2019) showed graph neural tangent kernel (GNTK) can achieve better performance than its counter part, graph neural network (GNN), on datasets with up to 5000 samples.”
On the infinite width limit of neural networks with a standard parameterization (2020, background): “The analytic forms for the various kernels inspire some additional interesting observations: • For the NTK parameterization, the kernel resulting from a Bayesian neural network and from gradient descent training of the readout layer of an inﬁnite width network are the same.”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “Garg et al. (Garg et al., 2020) and Verma & Zhang (Verma & Zhang, 2019) studied the generalization abilities of GNNs, and (Du et al., 2019) related wide GNNs to a variant of the neural tangent kernel (Arora et al., 2019; Jacot et al., 2018).”
How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks (2020, methodology): “This has also been described in several previous works (Du et al., 2019c; Chizat et al., 2019; Bietti & Mairal, 2019).”