# Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs

arXiv: https://arxiv.org/abs/2212.09034 · HTML: https://mlsanity.com/paper/2212.09034/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 71 references that are in the map.
- First posted on arXiv 18 Dec 2022.

## Builds on (most cited first, 30 of 50)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)

## Built on by (most cited first, 30 of 42)

- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion](https://mlsanity.com/paper/2301.09474/) (2023)
- [AutoML-Agent: A Multi-Agent LLM Framework for Full-Pipeline AutoML](https://mlsanity.com/paper/2410.02958/) (2024)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Rethinking Propagation for Unsupervised Graph Domain Adaptation](https://mlsanity.com/paper/2402.05660/) (2024)
- [Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization](https://mlsanity.com/paper/2306.01103/) (2023)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition](https://mlsanity.com/paper/2405.13707/) (2024)
- [Graph Data Condensation via Self-expressive Graph Structure Reconstruction](https://mlsanity.com/paper/2403.07294/) (2024)
- [GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2306.11264/) (2023)
- [Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons](https://mlsanity.com/paper/2306.13926/) (2023)
- [Graph Structure and Feature Extrapolation for Out-of-Distribution Generalization](https://mlsanity.com/paper/2306.08076/) (2023)
- [UniIF: Unified Molecule Inverse Folding](https://mlsanity.com/paper/2405.18968/) (2024)
- [Supercharging Graph Transformers with Advective Diffusion](https://mlsanity.com/paper/2310.06417/) (2023)
- [Architecture Matters: Uncovering Implicit Mechanisms in Graph Contrastive Learning](https://mlsanity.com/paper/2311.02687/) (2023)
- [Mixture of Weak & Strong Experts on Graphs](https://mlsanity.com/paper/2311.05185/) (2023)
- [Fast Graph Sharpness-Aware Minimization for Enhancing and Accelerating Few-Shot Node Classification](https://mlsanity.com/paper/2410.16845/) (2024)
- [Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks](https://mlsanity.com/paper/2411.02279/) (2024)
- [Contextualizing MLP-Mixers Spatiotemporally for Urban Data Forecast at Scale](https://mlsanity.com/paper/2307.01482/) (2023)
- [How Graph Neural Networks Learn: Lessons from Training Dynamics](https://mlsanity.com/paper/2310.05105/) (2023)
- [On the Topology Awareness and Generalization Performance of Graph Neural Networks](https://mlsanity.com/paper/2403.04482/) (2024)
- [OrthoReg: Improving Graph-regularized MLPs via Orthogonality Regularization](https://mlsanity.com/paper/2302.00109/) (2023)
- [Towards Data-Centric Automatic R&D](https://mlsanity.com/paper/2404.11276/) (2024)
- [On the Utilization of Unique Node Identifiers in Graph Neural Networks](https://mlsanity.com/paper/2411.02271/) (2024)
- [Graph Neural Network Generalization with Gaussian Mixture Model Based Augmentation](https://mlsanity.com/paper/2411.08638/) (2024)
- [Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspective](https://mlsanity.com/paper/2412.09805/) (2024)
- [Learning for Transductive Threshold Calibration in Open-World Recognition](https://mlsanity.com/paper/2305.12039/) (2023)
- [Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants](https://mlsanity.com/paper/2409.06998/) (2024)
- [Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation](https://mlsanity.com/paper/2503.18195/) (2025)
- [Wide & Deep Learning for Node Classification](https://mlsanity.com/paper/2505.02020/) (2025)

## Abstract (arXiv)

Graph neural networks (GNNs), as the de-facto model class for representation learning on graphs, are built upon the multi-layer perceptrons (MLP) architecture with additional message passing layers to allow features to flow across nodes. While conventional wisdom commonly attributes the success of GNNs to their advanced expressivity, we conjecture that this is not the main cause of GNNs' superiority in node-level prediction tasks. This paper pinpoints the major source of GNNs' performance gain to their intrinsic generalization capability, by introducing an intermediate model class dubbed as P(ropagational)MLP, which is identical to standard MLP in training, but then adopts GNN's architecture in testing. Intriguingly, we observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training. This finding sheds new insights into understanding the learning behavior of GNNs, and can be used as an analytic tool for dissecting various GNN-related research problems. As an initial step to analyze the inherent generalizability of GNNs, we show the essential difference between MLP and PMLP at infinite-width limit lies in the NTK feature map in the post-training stage. Moreover, by examining their extrapolation behavior, we find that though many GNNs and their PMLP counterparts cannot extrapolate non-linear functions for extremely out-of-distribution samples, they have greater potential to generalize to testing samples near the training data range as natural advantages of GNN architectures.