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

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.

Introduction

While it is common knowledge in the machine learning community that Graph Neural Networks (GNNs) outperform Multilayer Perceptrons (MLPs) on graph-structured data, the theoretical "why" has remained somewhat qualitative. Previous research pointed toward concepts like Laplacian smoothing (filtering noise) or expressivity (the ability to distinguish different graph shapes). However, there was a lack of quantitative analysis comparing the two from an optimization and generalization perspective.

This paper addresses this gap by asking: What specific role does graph convolution play during training, and to what extent does it improve generalization? By applying feature learning theory, the authors demonstrate that graph convolutions significantly prioritize learning "signals" over memorizing "noise," expanding the regime where models can generalize by a factor related to the graph's average node degree.

Theoretical Framework: Feature Learning Theory

The authors utilize feature learning theory, a framework that tracks how neural network weights evolve during training, to analyze a unified data model:

1. The SNM-SBM Model: They combine a Signal-Noise Model (SNM) for node features with a Stochastic Block Model (SBM) for graph structure. Node features consist of a "signal" (label-relevant information) and "noise" (irrelevant data).
2. Weight Decomposition: Weights of a two-layer GCN are decomposed into coefficients representing "signal learning" and "noise memorization."
3. Comparative Analysis: By tracking these coefficients during gradient descent, the authors compare the rates of signal learning and noise memorization in GCNs versus standard MLPs.
4. Polynomial ReLU: The analysis uses a polynomial ReLU activation ($\sigma(z) = \max\{0, z\}^q$ for $q > 2$), capturing the non-linear dynamics of modern networks more accurately than linear models.

Key Findings: The Degree Advantage

The most striking finding is that GNNs enhance the "low test error regime" by a factor of $D^{q-2}$, where $D$ is the expected degree of a node. Essentially, the more connected the graph, the better the GNN is at filtering out noise compared to an MLP.

Expand

Source, p. 5

Graph convolution acts as a massive speed boost for signal learning while simultaneously acting as a brake for noise memorization. Because neighbors often share the same signal but have independent noise, aggregating them reinforces the signal and cancels out the noise. This advantage holds regardless of whether the graph is homophilic or heterophilic, provided the structural pattern is consistent.

Empirical Validation

The study validates its theory using synthetic SNM-SBM data, modified MNIST (with added noise patches), and citation networks like Cora, Citeseer, and Pubmed.

Expand

Source, p. 7

The results show that GNNs exhibit "benign overfitting." Even if a GNN is trained until it perfectly fits noisy training data (zero training loss), it can still achieve near-zero test error because it learned the signal much earlier and more strongly than it memorized the noise. In contrast, as shown in the empirical results, MLPs struggle significantly as noise increases, failing to generalize even when training loss is minimized.

Conclusion

This work provides a rigorous theoretical foundation for the superiority of GNNs over MLPs. By quantifying the generalization advantage as a function of graph degree and activation power, it moves beyond qualitative intuition. Future work may extend these findings to deeper architectures, standard ReLU activations, and more complex data distributions to further bridge the gap between theory and the diverse GNN applications found in practice.