# WL meet VC

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

## 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 (most cited first, 30 of 83)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters](https://mlsanity.com/paper/1705.07664/) (2017)
- [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)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)

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

- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees](https://mlsanity.com/paper/2412.16441/) (2024)
- [A graphon-signal analysis of graph neural networks](https://mlsanity.com/paper/2305.15987/) (2023)
- [Distinguished In Uniform: Self Attention Vs. Virtual Nodes](https://mlsanity.com/paper/2405.11951/) (2024)
- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [Approximately Equivariant Graph Networks](https://mlsanity.com/paper/2308.10436/) (2023)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman](https://mlsanity.com/paper/2306.03266/) (2023)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Almost Surely Asymptotically Constant Graph Neural Networks](https://mlsanity.com/paper/2403.03880/) (2024)
- [Efficient Link Prediction via GNN Layers Induced by Negative Sampling](https://mlsanity.com/paper/2310.09516/) (2023)
- [VC dimension of Graph Neural Networks with Pfaffian activation functions](https://mlsanity.com/paper/2401.12362/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Generalization Limits of Graph Neural Networks in Identity Effects Learning](https://mlsanity.com/paper/2307.00134/) (2023)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity](https://mlsanity.com/paper/2605.07097/) (2026)
- [PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning](https://mlsanity.com/paper/2405.06418/) (2024)
- [Understanding Generalization in Node and Link Prediction](https://mlsanity.com/paper/2507.00927/) (2025)
- [On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry](https://mlsanity.com/paper/2510.10101/) (2025)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [Generalization of Graph Neural Networks through the Lens of Homomorphism](https://mlsanity.com/paper/2403.06079/) (2024)
- [A note on the VC dimension of 1-dimensional GNNs](https://mlsanity.com/paper/2410.07829/) (2024)
- [On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model](https://mlsanity.com/paper/2510.21392/) (2025)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)
- [Generalization Bounds for Spectral GNNs via Fourier Domain Analysis](https://mlsanity.com/paper/2604.00918/) (2026)
- [Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2605.25452/) (2026)
- [AutoGrable: What Is a Good Graph for a Table?](https://mlsanity.com/paper/2608.11431/) (2026)

## 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.