New Insights into Graph Convolutional Networks using Neural Tangent Kernels

• URL: http://arxiv.org/abs/2110.04060v2
• Date: Sat, 4 Nov 2023 18:52:26 GMT
• Title: New Insights into Graph Convolutional Networks using Neural Tangent Kernels
• Authors: Mahalakshmi Sabanayagam, Pascal Esser, Debarghya Ghoshdastidar
• Abstract summary: 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) We use the derived NTKs to identify that, with suitable normalisation, network depth does not always drastically reduce the performance of GCNs.
• Score: 8.824340350342512
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Graph Neural Networks Do Not Always Oversmooth [46.57665708260211]
  We study oversmoothing in graph convolutional networks (GCNs) by using their Gaussian process (GP) equivalence in the limit of infinitely many hidden features. We identify a new, non-oversmoothing phase: if the initial weights of the network have sufficiently large variance, GCNs do not oversmooth, and node features remain informative even at large depth.
  arXiv  Detail & Related papers  (2024-06-04T12:47:13Z)
• Efficient kernel surrogates for neural network-based regression [0.8030359871216615]
  We study the performance of the Conjugate Kernel (CK), an efficient approximation to the Neural Tangent Kernel (NTK) We show that the CK performance is only marginally worse than that of the NTK and, in certain cases, is shown to be superior. In addition to providing a theoretical grounding for using CKs instead of NTKs, our framework suggests a recipe for improving DNN accuracy inexpensively.
  arXiv  Detail & Related papers  (2023-10-28T06:41:47Z)
• Neural Tangent Kernels Motivate Graph Neural Networks with Cross-Covariance Graphs [94.44374472696272]
  We investigate NTKs and alignment in the context of graph neural networks (GNNs) Our results establish the theoretical guarantees on the optimality of the alignment for a two-layer GNN. These guarantees are characterized by the graph shift operator being a function of the cross-covariance between the input and the output data.
  arXiv  Detail & Related papers  (2023-10-16T19:54:21Z)
• What Do Graph Convolutional Neural Networks Learn? [0.0]
  Graph Convolutional Neural Networks (GCN) are a common variant of Graph neural networks (GNNs) Recent literature has highlighted that GCNs can achieve strong performance on heterophilous graphs under certain "special conditions" Our investigation on underlying graph structures of a dataset finds that a GCN's SSNC performance is significantly influenced by the consistency and uniqueness in neighborhood structure of nodes within a class.
  arXiv  Detail & Related papers  (2022-07-05T06:44:37Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• AM-GCN: Adaptive Multi-channel Graph Convolutional Networks [85.0332394224503]
  We study whether Graph Convolutional Networks (GCNs) can optimally integrate node features and topological structures in a complex graph with rich information. We propose an adaptive multi-channel graph convolutional networks for semi-supervised classification (AM-GCN) Our experiments show that AM-GCN extracts the most correlated information from both node features and topological structures substantially.
  arXiv  Detail & Related papers  (2020-07-05T08:16:03Z)
• Investigating and Mitigating Degree-Related Biases in Graph Convolutional Networks [62.8504260693664]
  Graph Convolutional Networks (GCNs) show promising results for semisupervised learning tasks on graphs. In this paper, we analyze GCNs in regard to the node degree distribution. We develop a novel Self-Supervised DegreeSpecific GCN (SL-DSGC) that mitigates the degree biases of GCNs.
  arXiv  Detail & Related papers  (2020-06-28T16:26:47Z)
• DeeperGCN: All You Need to Train Deeper GCNs [66.64739331859226]
  Graph Convolutional Networks (GCNs) have been drawing significant attention with the power of representation learning on graphs. Unlike Convolutional Neural Networks (CNNs), which are able to take advantage of stacking very deep layers, GCNs suffer from vanishing gradient, over-smoothing and over-fitting issues when going deeper. This paper proposes DeeperGCN that is capable of successfully and reliably training very deep GCNs.
  arXiv  Detail & Related papers  (2020-06-13T23:00:22Z)
• Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks [0.0]
  Graph convolutional networks (GCNs) have shown promising results in processing graph data by extracting structure-aware features. Here, we propose to augment conventional GCNs with geometric scattering transforms and residual convolutions. The former enables band-pass filtering of graph signals, thus alleviating the so-called oversmoothing often encountered in GCNs.
  arXiv  Detail & Related papers  (2020-03-18T18:03:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.