mlsanityData to 14 Oct 2026

WL meet VC

arXiv 2301.11039 ↗First posted 26 Jan 2023cs.LG cs.DM cs.DScited by 31

Not on the map. Why?

Abstract (arXiv)

Recently, many works studied the expressive power of graph neural networks (GNNs) by linking it to the 1-dimensional Weisfeiler--Leman algorithm (1-mathsfWL). Here, the 1-mathsfWL is a well-studied heuristic for the graph isomorphism problem, which iteratively colors or partitions a graph's vertex set. While this connection has led to significant advances in understanding and enhancing GNNs' expressive power, it does not provide insights into their generalization performance, i.e., their ability to make meaningful predictions beyond the training set. In this paper, we study GNNs' generalization ability through the lens of Vapnik--Chervonenkis (VC) dimension theory in two settings, focusing on graph-level predictions. First, when no upper bound on the graphs' order is known, we show that the bitlength of GNNs' weights tightly bounds their VC dimension. Further, we derive an upper bound for GNNs' VC dimension using the number of colors produced by the 1-mathsfWL. Secondly, when an upper bound on the graphs' order is known, we show a tight connection between the number of graphs distinguishable by the 1-mathsfWL and GNNs' VC dimension. Our empirical study confirms the validity of our theoretical findings.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). Builds on 83 of its 136 references that are in the map. First posted on arXiv 26 Jan 2023.

Builds on

83 of 136 references.

References · 83

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  5. 2017Inductive Representation Learning on Large Graphscited by 6,320
  6. 2018How Powerful are Graph Neural Networks?cited by 4,393
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  9. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  10. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  11. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  12. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
38 more
  1. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
  2. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  3. 2019Benign Overfitting in Linear Regressioncited by 549
  4. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  5. 2019Provably Powerful Graph Networkscited by 389
  6. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  7. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 311
  8. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 310
  9. 2020Can Graph Neural Networks Count Substructures?cited by 236
  10. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  11. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  12. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  13. 2017CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filterscited by 203
  14. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  15. 2021Identity-aware Graph Neural Networkscited by 198
  16. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  17. 2020Random Features Strengthen Graph Neural Networkscited by 186
  18. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  19. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  20. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  21. 2021Equivariant Subgraph Aggregation Networkscited by 154
  22. 2019Relational Pooling for Graph Representationscited by 150
  23. 2019A Survey on Graph Kernelscited by 148
  24. 2021Nested Graph Neural Networkscited by 137
  25. 2020Directional Graph Networkscited by 133
  26. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 124
  27. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  28. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  29. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  30. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  31. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  32. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 97
  33. 2018Convolutional Neural Network Architectures for Signals Supported on Graphscited by 95
  34. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  35. 2021Topological Graph Neural Networkscited by 87
  36. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 85
  37. 2021The Logic of Graph Neural Networkscited by 85
  38. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81

50 most cited of 83 All 83 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 6; 2024: 14; 2025: 5; 2026: 6.

31 papers.

Sort:

  1. 2024GFT: Graph Foundation Model with Transferable Tree Vocabularycited by 85
  2. 2023On the Stability of Expressive Positional Encodings for Graphscited by 33
  3. 2024Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Treescited by 32
  4. 2023A graphon-signal analysis of graph neural networkscited by 30
  5. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 20
  6. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 17
  7. 2023Approximately Equivariant Graph Networkscited by 16
  8. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  9. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  10. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  11. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  12. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
19 more
  1. 2023Efficient Link Prediction via GNN Layers Induced by Negative Samplingcited by 6
  2. 2024VC dimension of Graph Neural Networks with Pfaffian activation functionscited by 6
  3. 2024Future Directions in the Theory of Graph Machine Learningcited by 6
  4. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 5
  5. 2023Generalization Limits of Graph Neural Networks in Identity Effects Learningcited by 3
  6. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  7. 2026Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexitycited by 3
  8. 2024PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learningcited by 2
  9. 2025Understanding Generalization in Node and Link Predictioncited by 2
  10. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 2
  11. 2025The Parameterized Complexity of Computing the VC-Dimensioncited by 2
  12. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 1
  13. 2024A note on the VC dimension of 1-dimensional GNNscited by 1
  14. 2025On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Modelcited by 0
  15. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
  16. 2026Generalization Bounds for Spectral GNNs via Fourier Domain Analysiscited by 0
  17. 2026Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networkscited by 0
  18. 2026AutoGrable: What Is a Good Graph for a Table?cited by 0
  19. 2026Dimension-Free Scaling Laws for Size Generalization: An Exponential Separationcited by 0