# Graph Representational Learning: When Does More Expressivity Hurt Generalization?

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 61 of its 87 references that are in the map.
- First posted on arXiv 16 May 2025.

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

- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [Building powerful and equivariant graph neural networks with structural message-passing](https://mlsanity.com/paper/2006.15107/) (2020)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)

## Built on by (most cited first, 5 of 5)

- [On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry](https://mlsanity.com/paper/2510.10101/) (2025)
- [Message Passing on the Edge: Towards Scalable and Expressive GNNs](https://mlsanity.com/paper/2510.13615/) (2025)
- [CondPSE: A Polynomial-Filtered Structural Encoder with Conditional Modulation for Graphs](https://mlsanity.com/paper/2607.25169/) (2026)
- [AutoGrable: What Is a Good Graph for a Table?](https://mlsanity.com/paper/2608.11431/) (2026)
- [From Euclidean to Graph-Structured Data: A Survey of Collaborative Learning](https://mlsanity.com/paper/2609.02984/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are powerful tools for learning on structured data, yet the relationship between their expressivity and predictive performance remains unclear. We introduce a family of premetrics that capture different degrees of structural similarity between graphs and relate these similarities to generalization, and consequently, the performance of expressive GNNs. By considering a setting where graph labels are correlated with structural features, we derive generalization bounds that depend on the distance between training and test graphs, model complexity, and training set size. These bounds reveal that more expressive GNNs may generalize worse unless their increased complexity is balanced by a sufficiently large training set or reduced distance between training and test graphs. Our findings relate expressivity and generalization, offering theoretical insights supported by empirical results.