Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons

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

TL;DR

This paper provides a rigorous quantitative explanation for why Graph Neural Networks (GNNs) consistently outperform Multilayer Perceptrons (MLPs). By applying feature learning theory, the authors demonstrate that graph convolutions act as a powerful filter that prioritizes learning meaningful signals while suppressing the memorization of noise, expanding the regime of low test error by a factor of $D^{q-2}$ (where $D$ is the node degree and $q$ is the activation power).

What Problem Does This Paper Address?

While GNNs are the gold standard for graph-structured data, our theoretical understanding of why they work better than standard MLPs has remained somewhat qualitative. Previous theories pointed to "Laplacian smoothing" (averaging neighbor features) or "expressivity" (the ability to distinguish different graph structures).

However, these theories don't fully capture the training dynamics—how the model actually learns during gradient descent. Specifically, they don't quantify the gap in generalization: the ability of a model to perform well on unseen data even when it has enough capacity to "memorize" the noise in the training set (a phenomenon known as benign overfitting). The authors set out to answer: exactly how much better do GNNs generalize, and how does the graph structure facilitate this?

Methods

The researchers employed a feature learning analysis framework. They compared a two-layer Graph Convolutional Network (GCN) against a two-layer MLP using a specific data model:

  1. Signal-Noise Model (SNM): Input features consist of a "signal" (label-relevant info) and "noise" (task-irrelevant info).
  2. Stochastic Block Model (SBM): A standard way to generate synthetic graphs where nodes of the same class are more likely to be connected (homophily).
  3. Weight Decomposition: To track the training process, the authors decomposed the neural network weights into components representing signal learning and noise memorization. This allowed them to mathematically "watch" which parts of the data the model prioritized at each step of gradient descent.

Datasets

The study validates its theoretical findings using a mix of synthetic and real-world data:

  • Synthetic SNM-SBM: Controlled environments to test varying Signal-to-Noise Ratios (SNR), graph densities, and homophily levels.
  • Modified MNIST: The classic digit dataset was adapted into a signal-noise model by adding noise patches to the borders of the images and treating them as nodes in a graph.
  • Real-world Citation & Co-author Networks: The authors analyzed datasets like Cora, Citeseer, Pubmed, WikiCS, and Amazon Computers/Photo to verify that their theoretical assumptions (like feature orthogonality) actually hold in practice.

Key Insights and Ideas

  • The $D^{q-2}$ Advantage: The most striking finding is that GCNs enhance the "benign regime"—the conditions under which a model achieves near-zero test error—by a factor of $D^{q-2}$ compared to MLPs. If you have a dense graph (high $D$) and a high-order activation function (like a cubic ReLU, $q=3$), the GCN becomes vastly more robust to noise than an MLP.
  • Noise Suppression via Aggregation: Graph convolution effectively "shrinks" the norm of noise vectors. Because noise is often random and uncorrelated across neighbors, averaging features (message passing) causes the noise to cancel itself out, while the label-consistent signal is reinforced.
  • Signal Learning Priority: During training, GCNs reach a state where they have learned the signal long before they start memorizing noise. This "head start" is what allows them to generalize so well even if training continues until the training loss is zero.

Key Results

The paper provides both mathematical proofs and empirical evidence:

  • Global Convergence: The authors prove that despite the non-convexity of the problem, GCNs can achieve zero training error in a polynomial number of iterations.
  • Generalization Gap: Empirical heatmaps (Figure 3) show that GCNs maintain perfect test accuracy across a much wider range of sample sizes and noise levels than MLPs.
Figure 1: Illustration of test performance comparison between GNN and MLP. The region below the red curve but above the blue curve (highlighted in orange) indicates the area where GNN can generalize well, but MLP fails to generalize to the test set.
  • Training Dynamics: As shown in Figure 2, while both models drive training loss to zero, the MLP's test loss explodes (due to noise memorization), whereas the GNN's test loss remains near zero.
Figure 2: Training loss and test accuracy comparison. Note how GNN test accuracy stays high while MLP struggles.

Limitations and Future Work

  • Model Depth: The theoretical analysis is limited to two-layer networks. Real-world GNNs are often deeper, which introduces complexities like "over-smoothing."
  • Data Assumptions: The results rely on the Signal-Noise Model and feature orthogonality. While the authors showed these hold somewhat in citation networks, more complex data distributions might behave differently.
  • Activation Functions: The proof requires polynomial ReLU activations ($q > 2$). Extending this to standard ReLU ($q=1$) or other activations remains an open challenge.

Future research could extend this "feature learning" lens to explore how different GNN architectures (like GATs or GraphSAGE) handle the signal-noise trade-off.

Summary updated

Abstract

Graph neural networks (GNNs) have demonstrated remarkable capabilities in learning from graph-structured data, often outperforming traditional Multilayer Perceptrons (MLPs) in numerous graph-based tasks. Although existing works have demonstrated the benefits of graph convolution through Laplacian smoothing, expressivity or separability, there remains a lack of quantitative analysis comparing GNNs and MLPs from an optimization and generalization perspective. This study aims to address this gap by examining the role of graph convolution through feature learning theory. Using a signal-noise data model, we conduct a comparative analysis of the optimization and generalization between two-layer graph convolutional networks (GCNs) and their MLP counterparts. Our approach tracks the trajectory of signal learning and noise memorization in GNNs, characterizing their post-training generalization. We reveal that GNNs significantly prioritize signal learning, thus enhancing the regime of {low test error} over MLPs by $D^{q-2}$ times, where $D$ denotes a node's expected degree and $q$ is the power of ReLU activation function with $q>2$. This finding highlights a substantial and quantitative discrepancy between GNNs and MLPs in terms of optimization and generalization, a conclusion further supported by our empirical simulations on both synthetic and real-world datasets.
BibTeX
@inproceedings{huang2025quantifying,
  author = {Wei Huang and Yuan Cao and Haonan Wang and Xin Cao and Taiji Suzuki},
  title = {{Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=9L0Qz7d4Pb},
}
Figure