# Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 58 references that are in the map.
- First posted on arXiv 4 Jun 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [Rethinking Graph Lottery Tickets: Graph Sparsity Matters](https://mlsanity.com/paper/2305.02190/) (2023)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [You are caught stealing my winning lottery ticket! Making a lottery ticket claim its ownership](https://mlsanity.com/paper/2111.00162/) (2021)
- [Multi-Precision Policy Enforced Training (MuPPET): A precision-switching strategy for quantised fixed-point training of CNNs](https://mlsanity.com/paper/2006.09049/) (2020)
- [A Generalized Weisfeiler-Lehman Graph Kernel](https://mlsanity.com/paper/2101.08104/) (2021)
- [Adaptive Precision Training (AdaPT): A dynamic fixed point quantized training approach for DNNs](https://mlsanity.com/paper/2107.13490/) (2021)
- [Expressive Power of Temporal Message Passing](https://mlsanity.com/paper/2408.09918/) (2024)
- [The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure](https://mlsanity.com/paper/2312.04762/) (2023)
- [On the Two Sides of Redundancy in Graph Neural Networks](https://mlsanity.com/paper/2310.04190/) (2023)
- [On the Relationship Between Robustness and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2504.13786/) (2025)
- [Multicoated and Folded Graph Neural Networks with Strong Lottery Tickets](https://mlsanity.com/paper/2312.03236/) (2023)

## Abstract (arXiv)

The lottery ticket hypothesis (LTH) is well-studied for convolutional neural networks but has been validated only empirically for graph neural networks (GNNs), for which theoretical findings are largely lacking. In this paper, we identify the expressivity of sparse subnetworks, i.e. their ability to distinguish non-isomorphic graphs, as crucial for finding winning tickets that preserve the predictive performance. We establish conditions under which the expressivity of a sparsely initialized GNN matches that of the full network, particularly when compared to the Weisfeiler-Leman test, and in that context put forward and prove a Strong Expressive Lottery Ticket Hypothesis. We subsequently show that an increased expressivity in the initialization potentially accelerates model convergence and improves generalization. Our findings establish novel theoretical foundations for both LTH and GNN research, highlighting the importance of maintaining expressivity in sparsely initialized GNNs. We illustrate our results using examples from drug discovery.