Graph Neural Networks Provably Benefit from Structural Information: A Feature Learning Perspective

• URL: http://arxiv.org/abs/2306.13926v2
• Date: Mon, 14 Aug 2023 09:04:14 GMT
• Title: Graph Neural Networks Provably Benefit from Structural Information: A Feature Learning Perspective
• Authors: Wei Huang, Yuan Cao, Haonan Wang, Xin Cao, Taiji Suzuki
• Abstract summary: Graph neural networks (GNNs) have pioneered advancements in graph representation learning. This study investigates the role of graph convolution within the context of feature learning theory.
• Score: 53.999128831324576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) have pioneered advancements in graph representation learning, exhibiting superior feature learning and performance over multilayer perceptrons (MLPs) when handling graph inputs. However, understanding the feature learning aspect of GNNs is still in its initial stage. This study aims to bridge this gap by investigating the role of graph convolution within the context of feature learning theory in neural networks using gradient descent training. We provide a distinct characterization of signal learning and noise memorization in two-layer graph convolutional networks (GCNs), contrasting them with two-layer convolutional neural networks (CNNs). Our findings reveal that graph convolution significantly augments the benign overfitting regime over the counterpart CNNs, where signal learning surpasses noise memorization, by approximately factor $\sqrt{D}^{q-2}$, with $D$ denoting a node's expected degree and $q$ being the power of the ReLU activation function where $q > 2$. These findings highlight a substantial discrepancy between GNNs and MLPs in terms of feature learning and generalization capacity after gradient descent training, a conclusion further substantiated by our empirical simulations.

Related papers

• CNN2GNN: How to Bridge CNN with GNN [59.42117676779735]
  We propose a novel CNN2GNN framework to unify CNN and GNN together via distillation. The performance of distilled boosted'' two-layer GNN on Mini-ImageNet is much higher than CNN containing dozens of layers such as ResNet152.
  arXiv  Detail & Related papers  (2024-04-23T08:19:08Z)
• Label Deconvolution for Node Representation Learning on Large-scale Attributed Graphs against Learning Bias [75.44877675117749]
  We propose an efficient label regularization technique, namely Label Deconvolution (LD), to alleviate the learning bias by a novel and highly scalable approximation to the inverse mapping of GNNs. Experiments demonstrate LD significantly outperforms state-of-the-art methods on Open Graph datasets Benchmark.
  arXiv  Detail & Related papers  (2023-09-26T13:09:43Z)
• Neighborhood Convolutional Network: A New Paradigm of Graph Neural Networks for Node Classification [12.062421384484812]
  Graph Convolutional Network (GCN) decouples neighborhood aggregation and feature transformation in each convolutional layer. In this paper, we propose a new paradigm of GCN, termed Neighborhood Convolutional Network (NCN) In this way, the model could inherit the merit of decoupled GCN for aggregating neighborhood information, at the same time, develop much more powerful feature learning modules.
  arXiv  Detail & Related papers  (2022-11-15T02:02:51Z)
• Parameter Convex Neural Networks [13.42851919291587]
  We propose the exponential multilayer neural network (EMLP) which is convex with regard to the parameters of the neural network under some conditions. For late experiments, we use the same architecture to make the exponential graph convolutional network (EGCN) and do the experiment on the graph classificaion dataset.
  arXiv  Detail & Related papers  (2022-06-11T16:44:59Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  We consider the problem of learning a graphon neural network (WNN) by training GNNs on graphs sampled Bernoulli from the graphon. Inspired by these results, we propose an algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training.
  arXiv  Detail & Related papers  (2021-06-07T15:05:59Z)
• Variational models for signal processing with Graph Neural Networks [3.5939555573102853]
  This paper is devoted to signal processing on point-clouds by means of neural networks. In this work, we investigate the use of variational models for such Graph Neural Networks to process signals on graphs for unsupervised learning.
  arXiv  Detail & Related papers  (2021-03-30T13:31:11Z)
• Node2Seq: Towards Trainable Convolutions in Graph Neural Networks [59.378148590027735]
  We propose a graph network layer, known as Node2Seq, to learn node embeddings with explicitly trainable weights for different neighboring nodes. For a target node, our method sorts its neighboring nodes via attention mechanism and then employs 1D convolutional neural networks (CNNs) to enable explicit weights for information aggregation. In addition, we propose to incorporate non-local information for feature learning in an adaptive manner based on the attention scores.
  arXiv  Detail & Related papers  (2021-01-06T03:05:37Z)
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks [80.55378250013496]
  We study how neural networks trained by gradient descent extrapolate what they learn outside the support of the training distribution. Graph Neural Networks (GNNs) have shown some success in more complex tasks.
  arXiv  Detail & Related papers  (2020-09-24T17:48:59Z)

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.