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

Wei Huang, Yuan Cao, Haonan Wang, Xin Cao, Taiji SuzukiSubmission to ICLR 2024 · Rejected

TL;DR

Why do Graph Neural Networks (GNNs) generalize so much better than traditional Multilayer Perceptrons (MLPs) or Convolutional Neural Networks (CNNs)? This paper provides a rigorous feature learning theoretical analysis showing that graph convolution provably shrinks noise memorization while preserving true signal, boosting the effective signal-to-noise ratio. As a result, two-layer Graph Convolutional Networks (GCNs) trained via gradient descent achieve benign overfitting and near-zero test error across a significantly broader regime where standard architectures fail.

What Problem Does This Paper Address?

Despite the widespread practical success of GNNs over MLPs in graph node classification, the theoretical mechanisms explaining why message passing helps remain incomplete. Prior theoretical studies typically:

  1. Rely on the Neural Tangent Kernel (NTK) regime, which assumes weights barely move during training and fails to explain actual nonlinear feature learning.
  2. Analyze Bayes-optimal linear classifiers, ignoring the non-convex optimization landscape and dynamics of gradient descent.

This paper addresses the central question: What role does graph convolution play during gradient descent training, and what mechanism enables a GCN to generalize better after training compared to a CNN/MLP?

Methods

The authors build a theoretical framework tracking the exact weight dynamics during training:

  • SNM-SBM Generative Model: Combines a two-patch signal-noise model (SNM) with a stochastic block model (SBM). Each node feature $x = [x^{(1)}, x^{(2)}] = [y\mu, \xi]$ contains a label-dependent signal $y\mu \in \mathbb{R}^d$ ($y \in \{-1, +1\}$) and an orthogonal Gaussian noise background $\xi \sim \mathcal{N}(0, \sigma_p^2 (I - \|\mu\|_2^{-2}\mu\mu^\top))$. Edges are sampled with intra-class probability $p$ and inter-class probability $s$, with homophily $p > s$.
  • Two-Layer GCN vs. CNN: Considers two-layer architectures with polynomial ReLU activations $\sigma(z) = \max\{0, z\}^q$ ($q > 2$). The GCN incorporates normalized adjacency aggregation with self-loops ($\tilde{D}^{-1}\tilde{A}$), while the CNN/MLP baseline operates on raw node features ($p = s = 0$).
  • Signal-Noise Weight Decomposition: First-layer weights are decomposed into orthogonal directions: $$w_{j,r}^{(t)} = w_{j,r}^{(0)} + j \cdot \gamma_{j,r}^{(t)} \frac{\mu}{\|\mu\|_2^2} + \sum_{i=1}^n \rho_{j,r,i}^{(t)} \frac{\xi_i}{\|\xi_i\|_2^2}$$
  • Two-Stage Optimization Dynamics:
  • Stage 1 (Signal Learning vs. Noise Memorization): With small initialization $\sigma_0$, cross-entropy loss derivatives are nearly constant. Homophilic graph convolution accelerates signal learning $\gamma^{(t)}$ exponentially while noise coefficients $\rho^{(t)}$ remain tiny.
  • Stage 2 (Convergence & Benign Overfitting): As loss derivatives shrink, training loss converges to an arbitrarily small $\epsilon$ while noise memorization remains strictly controlled.

Datasets

  • Synthetic SNM-SBM Benchmark: Node counts $n \in [200, 7200]$, dimension $d = 500$, noise variance $\sigma_p = 20$, edge probabilities $p = 0.5, s = 0.08$, sweeping Signal-to-Noise Ratios (SNR) from $0.045$ to $0.98$.
  • Real-World / Semi-Synthetic (MNIST): Binary classification of digits '1' and '2' where feature vectors come from MNIST images and graph connectivity is sampled from the SBM.
  • Standard Citation Networks (Empirical Motivation): Cora (2,708 nodes, 5,429 edges), Citeseer (3,327 nodes, 4,732 edges), and Pubmed (19,717 nodes, 44,338 edges).

Key Insights and Ideas

  • Graph Convolution Cancels Noise: Because node noise vectors $\xi_i$ are approximately orthogonal in high dimensions, averaging neighbor features reduces the expected $\ell_2$-norm of noise by a factor of roughly $\sqrt{n(p+s)/2}$ (the square root of the expected degree).
  • Signal Survives under Homophily: In contrast to noise, averaging neighboring signals under homophily ($p > s$) preserves the latent signal vector $\mu$, scaled only by a constant factor $\Xi = \frac{p-s}{p+s}$.
  • Effective SNR Amplification: The paper introduces the effective SNR for GNNs: $$\text{SNR}_G = \text{SNR} \cdot (n(p+s))^{\frac{q-2}{2q}}, \quad \text{where } \text{SNR} = \frac{\|\mu\|_2}{\sigma_p \sqrt{d}}$$
  • Provable Generalization Gap: In the regime where $n \cdot \text{SNR}_G^q = \tilde{\Omega}(1)$ but $n \cdot \text{SNR}^q = \tilde{\mathcal{O}}(1)$, GCNs achieve near-zero population loss ($o(1)$), whereas CNNs/MLPs succumb to harmful overfitting and suffer test loss bounded below by a constant ($\ge C$).

Key Results

  • Global Convergence and Test Bounds: Theorem 3.2 proves that with high probability ($1 - d^{-1}$), gradient descent finds an iterate $t \le T$ such that GCN training loss satisfies $L_S^{GCN}(W^{(t)}) \le \epsilon$ and test loss satisfies $L_D^{GCN}(W^{(t)}) \le c_1 \epsilon + \exp(-c_2 n^2)$.
  • Synthetic Phase Diagram: GCN maintains $1.0$ (100%) test accuracy across almost the entire SNR $\times$ sample size plane, whereas CNN test accuracy collapses to $50\text{--}70\%$ under low SNR despite reaching zero training error.
  • MNIST Verification: When trained on MNIST digit features connected by an SBM graph, GCN achieves nearly $100\%$ training and test accuracy within 100 epochs, whereas the CNN baseline reaches $0$ training loss but plateaus at high test loss and poor test accuracy (~$65\%$).

Limitations and Future Work

  • Shallow Architecture: The theoretical analysis is restricted to a two-layer GCN with fixed second-layer weights; deeper multi-layer networks and multi-hop convolutions are not analyzed.
  • Dense Homophilic Graph Assumption: The proofs require a relatively dense graph regime ($p, s = \Omega(\sqrt{\log(n)/n})$) and homophily ($p > s$); heterophilous or highly sparse graphs may break degree and noise concentration.
  • Activation and Optimizer Restrictions: Analysis relies on polynomial ReLU ($q > 2$) and standard gradient descent; extending this to standard ReLU ($q=1$), adaptive optimizers (Adam), or explicit regularization remains open for future research.

Summary updated

Abstract

Graph neural networks (GNNs) have shown remarkable capabilities in learning from graph-structured data, outperforming traditional multilayer perceptrons (MLPs) in numerous graph applications. Despite these advantages, there has been limited theoretical exploration into why GNNs are so effective, particularly from the perspective of feature learning. This study aims to address this gap by examining the role of graph convolution in feature learning theory under a specific data generative model. We undertake a comparative analysis of the optimization and generalization between two-layer graph convolutional networks (GCNs) and their convolutional neural network (CNN) counterparts. Our findings reveal that graph convolution significantly enhances the regime of low test error over CNNs. This highlights a substantial discrepancy between GNNs and MLPs in terms of generalization capacity, a conclusion further supported by our empirical simulations on both synthetic and real-world datasets.
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},
}

Loading related content...

Figure