mlsanityData to 14 Oct 2026

Graph Representational Learning: When Does More Expressivity Hurt Generalization?

arXiv 2505.11298 ↗First posted 16 May 2025cs.LGcited by 5

Not on the map. Why?

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.

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

61 of 87 references.

References · 61

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  3. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  4. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  5. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  7. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  8. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  9. 2019Provably Powerful Graph Networkscited by 389
  10. 2018Invariant and Equivariant Graph Networkscited by 346
  11. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
  12. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
38 more
  1. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  2. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  3. 2021Identity-aware Graph Neural Networkscited by 198
  4. 2020Random Features Strengthen Graph Neural Networkscited by 186
  5. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 183
  6. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  7. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  8. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
  9. 2021Equivariant Subgraph Aggregation Networkscited by 154
  10. 2019On the Universality of Invariant Networkscited by 152
  11. 2019A Survey on Graph Kernelscited by 148
  12. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  13. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  14. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  15. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 97
  16. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 85
  17. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 69
  18. 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
  19. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 64
  20. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
  21. 2022Ordered Subgraph Aggregation Networkscited by 57
  22. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 56
  23. 2019Coloring graph neural networks for node disambiguationcited by 52
  24. 2021Graph Neural Networks with Local Graph Parameterscited by 52
  25. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 48
  26. 2021Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passingcited by 47
  27. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  28. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 41
  29. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 39
  30. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  31. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  32. 2023WL meet VCcited by 31
  33. 2023A graphon-signal analysis of graph neural networkscited by 30
  34. 2018Lov'asz Meets Weisfeiler and Lemancited by 27
  35. 2020Graph Homomorphism Convolutioncited by 27
  36. 2023Graph Neural Networks Use Graphs When They Shouldn'tcited by 26
  37. 2022Generalized Laplacian Positional Encoding for Graph Representation Learningcited by 21
  38. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 17

50 most cited of 61 All 61 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 2
  2. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0
  3. 2026CondPSE: A Polynomial-Filtered Structural Encoder with Conditional Modulation for Graphscited by 0
  4. 2026AutoGrable: What Is a Good Graph for a Table?cited by 0
  5. 2026From Euclidean to Graph-Structured Data: A Survey of Collaborative Learningcited by 0