mlsanityData to 14 Oct 2026

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

arXiv 2306.13926 ↗First posted 24 Jun 2023cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

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 Dq-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.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 43 of its 75 references that are in the map. First posted on arXiv 24 Jun 2023.

Builds on

43 of 75 references.

References · 43

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  7. 2016Variational Graph Auto-Encoderscited by 1,382
  8. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,139
  9. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  10. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  11. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  12. 2018Link Prediction Based on Graph Neural Networkscited by 832
31 more
  1. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  2. 2020Benchmarking Graph Neural Networkscited by 680
  3. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 545
  4. 2019Self-Attention Graph Poolingcited by 421
  5. 2020Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learningcited by 297
  6. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 261
  7. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 222
  8. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  9. 2020Feature Learning in Infinite-Width Neural Networkscited by 190
  10. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  11. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
  12. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  13. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
  14. 2018Contextual Stochastic Block Modelscited by 134
  15. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  16. 2020Feature Purification: How Adversarial Training Performs Robust Deep Learningcited by 107
  17. 2022Vision Transformers provably learn spatial structurecited by 93
  18. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
  19. 2014Exact Recovery in the Stochastic Block Modelcited by 78
  20. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  21. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  22. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  23. 2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 49
  24. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  25. 2019Stochastic Blockmodels meet Graph Neural Networkscited by 39
  26. 2020On Graph Neural Networks versus Graph-Augmented MLPscited by 30
  27. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  28. 2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16
  29. 2021Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspectivecited by 14
  30. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 12
  31. 2023Per-Example Gradient Regularization Improves Learning Signals from Noisy Datacited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 6; 2025: 3; 2026: 1.

12 papers.

  1. 2024On the Feature Learning in Diffusion Modelscited by 20
  2. 2024On the Comparison between Multi-modal and Single-modal Contrastive Learningcited by 10
  3. 2023Benign Oscillation of Stochastic Gradient Descent with Large Learning Ratescited by 8
  4. 2024Provably Neural Active Learning Succeeds via Prioritizing Perplexing Samplescited by 5
  5. 2024Provable Benefit of Cutout and CutMix for Feature Learningcited by 4
  6. 2025On the Role of Label Noise in the Feature Learning Processcited by 4
  7. 2025How Does Label Noise Gradient Descent Improve Generalization in the Low SNR Regime?cited by 4
  8. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  9. 2025NodeReg: Mitigating the Imbalance and Distribution Shift Effects in Semi-Supervised Node Classification via Norm Consistencycited by 1
  10. 2024LAMP: Learnable Meta-Path Guided Adversarial Contrastive Learning for Heterogeneous Graphscited by 0
  11. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  12. 2026Neuron Block Dynamics for XOR Classification with Zero-Margincited by 0