# Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspective

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 42 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 25 of 25)

- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Regularizing Neural Networks by Penalizing Confident Output Distributions](https://mlsanity.com/paper/1701.06548/) (2017)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Spatial-Temporal Graph ODE Networks for Traffic Flow Forecasting](https://mlsanity.com/paper/2106.12931/) (2021)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [Does GNN Pretraining Help Molecular Representation?](https://mlsanity.com/paper/2207.06010/) (2022)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Dirichlet Graph Variational Autoencoder](https://mlsanity.com/paper/2010.04408/) (2020)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Rethinking Graph Regularization for Graph Neural Networks](https://mlsanity.com/paper/2009.02027/) (2020)
- [SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization](https://mlsanity.com/paper/2303.09778/) (2023)
- [Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks](https://mlsanity.com/paper/2006.08550/) (2020)
- [Graph Out-of-Distribution Generalization via Causal Intervention](https://mlsanity.com/paper/2402.11494/) (2024)
- [Generalization bounds for graph convolutional neural networks via Rademacher complexity](https://mlsanity.com/paper/2102.10234/) (2021)
- [Efficient Traffic Prediction Through Spatio-Temporal Distillation](https://mlsanity.com/paper/2501.10459/) (2025)
- [Graph Out-of-Distribution Generalization with Controllable Data Augmentation](https://mlsanity.com/paper/2308.08344/) (2023)
- [MedGNN: Towards Multi-resolution Spatiotemporal Graph Learning for Medical Time Series Classification](https://mlsanity.com/paper/2502.04515/) (2025)
- [Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization](https://mlsanity.com/paper/2410.08473/) (2024)
- [Cluster-guided Contrastive Class-imbalanced Graph Classification](https://mlsanity.com/paper/2412.12984/) (2024)
- [Enhancing Graph Representation Learning with Localized Topological Features](https://mlsanity.com/paper/2501.09178/) (2025)
- [USER: Unsupervised Structural Entropy-based Robust Graph Neural Network](https://mlsanity.com/paper/2302.05889/) (2023)
- [Generalization of Graph Neural Networks is Robust to Model Mismatch](https://mlsanity.com/paper/2408.13878/) (2024)

## Abstract (arXiv)

Graph neural networks (GNNs) have emerged as a fundamental tool for learning from graph-structured data, achieving strong performance across a wide range of applications. However, understanding their generalization capabilities remains challenging due to the complex structural dependencies inherent in such data. Existing generalization analyses largely follow the classical machine learning paradigm, focusing primarily on model complexity while overlooking the fundamental role of graph structure. Therefore, in this work, we systematically investigate this role by asking: does the graph structure actually influence generalization, and if so, by how much? To answer the first question and validate our intuition, we theoretically prove that incorporating more edges into the prediction process transforms the input representations to be overly accommodating to the output model, thereby inducing overfitting. To address the second question, we formulate a structural complexity measure based on the number of effective edges and derive a Rademacher complexity-based generalization bound. In doing so, we demonstrate that GNN generalization depends explicitly on structural complexity, alongside traditional parameter-dependent factors. Motivated by these theoretical findings, we propose a structural entropy regularization method. This approach controls structural complexity by regulating effective edges to balance underfitting and overfitting, ultimately improving the generalization performance of GNNs.