Research map / Graph learning / GNN architectures
Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Links GNN expressivity to the lottery ticket hypothesis: proves that sparse initializations of moment-based GNNs can retain 1-WL expressivity (Strong Expressive LTH), relates expressivity to gradient diversity, and validates empirically on TUDatasets with GIN and GCN.
Problem
Whether sparse (pruned) GNN initializations preserve the expressivity needed to distinguish non-isomorphic graphs, and whether this expressivity determines if a pruned GNN is a winning lottery ticket.
Approach
Formal criteria tying pruning of graph and MLP parameters to preservation of distinguishability (WL expressivity); proves existence of maximally expressive trainable sparse subpaths in moment-based GNNs (SELTH); shows gradient diversity is governed by embedding orthogonality; and empirically measures pre-training expressivity as a predictor of post-training accuracy.
Key results
- Pre-training expressivity of randomly pruned GIN/GCN correlates with post-training accuracy; highly expressive sparse GINs outperformed dense unpruned models up to 80% pruning.
- Probability of post-training expressivity >= kappa given pre-training expressivity < kappa is only about 0.02-0.04 across thresholds, so sparse GNNs rarely gain expressivity during training.
- Across 13,500 runs, sparse models with higher untrained expressivity were more likely to be winning tickets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase pre-training expressivity of the sparse initialization | Sparse GIN and GCN · 10 TUDatasets | post-training accuracy | Helped |
| increase pre-training expressivity of the sparse GIN | GIN · 10 TUDatasets, up to 80% pruning | post-training prediction quality | Helped |
| initialize the sparse GNN with low expressivity | Sparse GIN and GCN · 10 TUDatasets | post-training expressivity | Hurt |
| prune the first layer so that it cancels distinguishing feature differences | Moment-based GNN · Structurally isomorphic, feature-divergent graphs | classification accuracy | Hurt |
Surprising findings
- Post-training expressivity is generally lower than pre-training expressivity; sparse GNNs rarely transition from low to high expressivity during training.
- The correlation between pre-training expressivity and post-training accuracy is statistically significant but weakest at mid pruning ratios.
Limitations
- Theory covers moment-based GNNs with injective activations and assumes a perfect classifier; results are not directly proven for GAT or GCN.
- Lemma on maximum accuracy requires knowing all isomorphism types, which is impractical; the empirical study is limited to graph-level classification on TUDatasets.
- Convergence and generalization claims are inferred rather than strictly proven, since Theorem on gradient diversity gives only bounds.
Experimental setup
Datasets: TUDataset (10 datasets)
Benchmarks: TUDataset (10 datasets)
Metrics: test accuracy pre-training expressivity (fraction of distinguishable non-i post-training expressivity Pearson correlation winning ticket probability (accuracy drop < 0.05)
Baselines: dense unpruned GIN dense unpruned GCN
Builds on: Strong Lottery Ticket Hypothesis Graph Isomorphism Network Deep Sets Unified GNN Sparsification
Closest papers by meaning
- A Unifying Relational Perspective on Expressive Lottery Tickets (ICML 2026 · similarity 0.93)
- The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks (ICLR 2019 · similarity 0.92)
- Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Sparse Neural Networks (NeurIPS 2021 · similarity 0.92)
- Searching Lottery Tickets in Graph Neural Networks: A Dual Perspective (ICLR 2023 · similarity 0.91)
- Find A Winning Sign: Sign Is All We Need to Win the Lottery (ICLR 2025 · similarity 0.90)
- On the Sparsity of the Strong Lottery Ticket Hypothesis (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.