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

Abstract

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.

arXiv commentIn NeurIPS 2019. Code available: https://github.com/KangchengHou/gntk

References in corpus (14)

• Semi-Supervised Classification with Graph Convolutional Networks
• Neural Message Passing for Quantum Chemistry
• Molecular Graph Convolutions: Moving Beyond Fingerprints
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• Interaction Networks for Learning about Objects, Relations and Physics
• On Exact Computation with an Infinitely Wide Neural Net
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Measuring abstract reasoning in neural networks
• Anonymous Walk Embeddings
• What Can Neural Networks Reason About?
• RetGK: Graph Kernels based on Return Probabilities of Random Walks
• Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks

Cited by in corpus (48)

• A Comprehensive Survey on Deep Graph Representation Learning
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• What Can Neural Networks Reason About?
• Graph Kernels: A Survey
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• Graph Kernels: State-of-the-Art and Future Challenges
• Tensor Programs II: Neural Tangent Kernel for Any Architecture
• KGNN: Harnessing Kernel-based Networks for Semi-supervised Graph Classification
• Subgroup Generalization and Fairness of Graph Neural Networks
• Convolutional Kernel Networks for Graph-Structured Data
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Inclusion of Domain-Knowledge into GNNs using Mode-Directed Inverse Entailment
• Tensor Programs III: Neural Matrix Laws
• How hard is to distinguish graphs with graph neural networks?
• Evaluating Logical Generalization in Graph Neural Networks
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics
• On the infinite width limit of neural networks with a standard parameterization
• Deep Graph Similarity Learning: A Survey
• X-CBA: Explainability Aided CatBoosted Anomal-E for Intrusion Detection System
• Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime
• Global Attention Improves Graph Networks Generalization
• From Local Structures to Size Generalization in Graph Neural Networks
• Learning Deep Graph Representations via Convolutional Neural Networks
• Deep Active Learning by Leveraging Training Dynamics
• Information Obfuscation of Graph Neural Networks
• Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective
• The Recurrent Neural Tangent Kernel
• Topology and Content Co-Alignment Graph Convolutional Learning
• Optimal quantization of the mean measure and applications to statistical learning
• Shift Invariance Can Reduce Adversarial Robustness
• Quaternion Graph Neural Networks
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks
• Unsupervised Neighborhood Propagation Kernel Layers for Semi-supervised Node Classification
• Neural Tangent Kernel Maximum Mean Discrepancy
• Neural Bandit with Arm Group Graph
• Wasserstein Embedding for Graph Learning
• Exploring the Uncertainty Properties of Neural Networks' Implicit Priors in the Infinite-Width Limit
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction
• Uniform Convergence, Adversarial Spheres and a Simple Remedy
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• On Inductive Biases for Machine Learning in Data Constrained Settings
• New Insights into Graph Convolutional Networks using Neural Tangent Kernels
• A Neural Tangent Kernel Perspective of Infinite Tree Ensembles
• Density of States Graph Kernels
• Enhanced Recurrent Neural Tangent Kernels for Non-Time-Series Data
• Unintended Effects on Adaptive Learning Rate for Training Neural Network with Output Scale Change