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

Wei Huang, Yuan Cao, Haonan Wang, Xin Cao, Taiji Suzuki

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.

Introduction

While Graph Neural Networks (GNNs) have empirically outperformed Multilayer Perceptrons (MLPs) on graph-structured data for years, a rigorous quantitative understanding of this advantage from a training perspective has been lacking. Existing theories often attribute GNN success to Laplacian smoothing or expressivity, but they rarely address the dynamics of the optimization process itself. This paper addresses this gap by asking: Does graph structure help a model prioritize signal over noise during gradient descent?

Methodology

The researchers utilize Feature Learning Theory to analyze the trajectory of model weights during training. The study employs a Signal-Noise Model (SNM) combined with a Stochastic Block Model (SBM) to create synthetic datasets where signal and noise components are precisely controlled.

The comparison focuses on a two-layer Graph Convolutional Network (GCN) versus a standard two-layer MLP. Both models use a polynomial ReLU activation function ($\sigma(z) = \text{max}\{0, z\}^q$ for $q > 2$), which serves to amplify the speed difference between learning strong signals and weak noise. By decomposing weight updates into signal-tracking and noise-tracking coefficients, the authors provide a mathematical proof of the GNN's preference for signal learning.

Datasets

  • Synthetic Data: Generated using the SNM-SBM model to control the Signal-to-Noise Ratio (SNR) and graph density.
  • Modified MNIST: MNIST images were converted into a graph problem by adding Gaussian noise patches and using an SBM to create connections between images based on digit labels.
  • Real-world Benchmarks: Datasets like Cora, Citeseer, Pubmed, and Coauthor CS were analyzed to validate the assumption of orthogonal noise structures in real-world features.

Theoretical Insights: The Noise Filter Effect

The most significant theoretical insight is that graph convolution acts as a powerful noise suppressor. While an MLP processes the raw, noisy features of individual nodes, a GCN aggregates features across a neighborhood. Because the noise is random and zero-mean, it tends to cancel out during aggregation, while the consistent signal is preserved and amplified.

Quantitatively, the paper proves that GNNs can achieve low test error in a regime that is significantly broader than that of MLPs, with the advantage scaling by a factor proportional to the graph's connectivity ($D^{q-2}$, where $D$ is the expected degree). This implies that the benefit of GNNs scales exponentially with the density of the graph.

Empirical Results and Benign Overfitting

The theoretical findings are supported by simulations on synthetic data. The results demonstrate a clear "orange zone"—a wide range of SNR levels and sample sizes where GCNs achieve near-perfect test accuracy while MLPs fail entirely.

Generalization regimes for MLP and GCN. The orange region highlights the expanded success regime for GCNs where they successfully learn signals that MLPs cannot.

Furthermore, the study explores the phenomenon of benign overfitting. As shown in the training curves, GNNs can perfectly fit noisy training data (reaching zero training loss) while still maintaining excellent generalization on the test set. This occurs because the signal-related weights grow much faster and larger than the noise-related weights during the early stages of gradient descent.

Training and test performance comparison between GNN and MLP. The GNN achieves near-zero test loss and high test accuracy, whereas the MLP fails to generalize despite fitting the training data.

Conclusion

This work provides a formal framework for understanding why GNNs are superior feature learners on graph data. By showing that graph convolutions effectively increase the "effective SNR" of the input, the authors quantify the structural advantage of GNNs. Future research may extend these insights to deeper architectures and more complex relational models like Graph Attention Networks or Transformers.

Summary updated

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.
BibTeX
@misc{huang2023graph,
  author = {Wei Huang and Yuan Cao and Haonan Wang and Xin Cao and Taiji Suzuki},
  title = {{Graph Neural Networks Provably Benefit from Structural Information: A Feature Learning Perspective}},
  year = {2023},
  eprint = {2306.13926},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.13926},
}
Figure