mlsanityData to 13 Oct 2026

New Insights into Graph Convolutional Networks using Neural Tangent Kernels

arXiv 2110.04060 ↗First posted 8 Oct 2021cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

Graph Convolutional Networks (GCNs) have emerged as powerful tools for learning on network structured data. Although empirically successful, GCNs exhibit certain behaviour that has no rigorous explanation -- for instance, the performance of GCNs significantly degrades with increasing network depth, whereas it improves marginally with depth using skip connections. This paper focuses on semi-supervised learning on graphs, and explains the above observations through the lens of Neural Tangent Kernels (NTKs). We derive NTKs corresponding to infinitely wide GCNs (with and without skip connections). Subsequently, we use the derived NTKs to identify that, with suitable normalisation, network depth does not always drastically reduce the performance of GCNs -- a fact that we also validate through extensive simulation. Furthermore, we propose NTK as an efficient `surrogate model' for GCNs that does not suffer from performance fluctuations due to hyper-parameter tuning since it is a hyper-parameter free deterministic kernel. The efficacy of this idea is demonstrated through a comparison of different skip connections for GCNs using the surrogate NTKs.

Key facts. Cited by 4 papers in the map (data through 13 Oct 2026). Builds on 25 of its 33 references that are in the map. First posted on arXiv 8 Oct 2021.

Builds on

25 of 33 references.

References · 25

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,318
  2. 2017Graph Attention Networkscited by 8,888
  3. 2017Inductive Representation Learning on Large Graphscited by 6,303
  4. 2018How Powerful are Graph Neural Networks?cited by 4,373
  5. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,610
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,086
  7. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,574
  8. 2019Simplifying Graph Convolutional Networkscited by 1,474
  9. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  10. 2020Simple and Deep Graph Convolutional Networkscited by 857
  11. 2015Gated Graph Sequence Neural Networkscited by 794
  12. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 737
13 more
  1. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 658
  2. 2017Deep Neural Networks as Gaussian Processescited by 618
  3. 2017Exploring Generalization in Deep Learningcited by 596
  4. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  5. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 573
  6. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  7. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  8. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  9. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
  10. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 130
  11. 2020The Recurrent Neural Tangent Kernelcited by 67
  12. 2020Every Model Learned by Gradient Descent Is Approximately a Kernel Machinecited by 54
  13. 2018Mean-field theory of graph neural networks in graph partitioningcited by 16

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 3.

4 papers.

  1. 2023Graph Neural Tangent Kernel: Convergence on Large Graphscited by 16
  2. 2023Principles for Initialization and Architecture Selection in Graph Neural Networks with ReLU Activationscited by 3
  3. 2022Graph Convolutional Networks from the Perspective of Sheaves and the Neural Tangent Kernelcited by 2
  4. 2023Neural Tangent Kernels Motivate Graph Neural Networks with Cross-Covariance Graphscited by 0