# Rethinking Graph Lottery Tickets: Graph Sparsity Matters

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 56 references that are in the map.
- First posted on arXiv 3 May 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [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)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [The Lottery Ticket Hypothesis for Pre-trained BERT Networks](https://mlsanity.com/paper/2007.12223/) (2020)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Hyperbolic Entailment Cones for Learning Hierarchical Embeddings](https://mlsanity.com/paper/1804.01882/) (2018)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [When BERT Plays the Lottery, All Tickets Are Winning](https://mlsanity.com/paper/2005.00561/) (2020)
- [One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers](https://mlsanity.com/paper/1906.02773/) (2019)
- [Winning the Lottery with Continuous Sparsification](https://mlsanity.com/paper/1912.04427/) (2019)
- [MEST: Accurate and Fast Memory-Economic Sparse Training Framework on the Edge](https://mlsanity.com/paper/2110.14032/) (2021)
- [Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP](https://mlsanity.com/paper/1906.02768/) (2019)
- [Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpot](https://mlsanity.com/paper/2009.11094/) (2020)
- [Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network](https://mlsanity.com/paper/2103.09377/) (2021)

## Built on by (most cited first, 23 of 23)

- [A Survey on Deep Neural Network Pruning-Taxonomy, Comparison, Analysis, and Recommendations](https://mlsanity.com/paper/2308.06767/) (2023)
- [Graph Condensation for Inductive Node Representation Learning](https://mlsanity.com/paper/2307.15967/) (2023)
- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition](https://mlsanity.com/paper/2405.13707/) (2024)
- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [Successfully Applying Lottery Ticket Hypothesis to Diffusion Model](https://mlsanity.com/paper/2310.18823/) (2023)
- [Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness](https://mlsanity.com/paper/2402.01242/) (2024)
- [Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation](https://mlsanity.com/paper/2310.10998/) (2023)
- [Your Language Model Secretly Contains Personality Subnetworks](https://mlsanity.com/paper/2602.07164/) (2026)
- [TEDDY: Trimming Edges with Degree-based Discrimination strategY](https://mlsanity.com/paper/2402.01261/) (2024)
- [Exploring Sparsity in Graph Transformers](https://mlsanity.com/paper/2312.05479/) (2023)
- [IGNN-Solver: A Graph Neural Solver for Implicit Graph Neural Networks](https://mlsanity.com/paper/2410.08524/) (2024)
- [Multicoated and Folded Graph Neural Networks with Strong Lottery Tickets](https://mlsanity.com/paper/2312.03236/) (2023)
- [Unifews: You Need Fewer Operations for Efficient Graph Neural Networks](https://mlsanity.com/paper/2403.13268/) (2024)
- [Sparse but Strong: Crafting Adversarially Robust Graph Lottery Tickets](https://mlsanity.com/paper/2312.06568/) (2023)
- [On the Equivalence of Graph Convolution and Mixup](https://mlsanity.com/paper/2310.00183/) (2023)
- [Acceleration Algorithms in GNNs: A Survey](https://mlsanity.com/paper/2405.04114/) (2024)
- [Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win](https://mlsanity.com/paper/2506.03919/) (2025)
- [Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms](https://mlsanity.com/paper/2601.22943/) (2026)
- [A Unifying Relational Perspective on Expressive Lottery Tickets](https://mlsanity.com/paper/2608.18819/) (2026)
- [Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks](https://mlsanity.com/paper/2609.31466/) (2026)
- [Stabilizing the Dynamic Low-Rank Training](https://mlsanity.com/paper/2609.32615/) (2026)

## Abstract (arXiv)

Lottery Ticket Hypothesis (LTH) claims the existence of a winning ticket (i.e., a properly pruned sub-network together with original weight initialization) that can achieve competitive performance to the original dense network. A recent work, called UGS, extended LTH to prune graph neural networks (GNNs) for effectively accelerating GNN inference. UGS simultaneously prunes the graph adjacency matrix and the model weights using the same masking mechanism, but since the roles of the graph adjacency matrix and the weight matrices are very different, we find that their sparsifications lead to different performance characteristics. Specifically, we find that the performance of a sparsified GNN degrades significantly when the graph sparsity goes beyond a certain extent. Therefore, we propose two techniques to improve GNN performance when the graph sparsity is high. First, UGS prunes the adjacency matrix using a loss formulation which, however, does not properly involve all elements of the adjacency matrix; in contrast, we add a new auxiliary loss head to better guide the edge pruning by involving the entire adjacency matrix. Second, by regarding unfavorable graph sparsification as adversarial data perturbations, we formulate the pruning process as a min-max optimization problem to gain the robustness of lottery tickets when the graph sparsity is high. We further investigate the question: Can the "retrainable" winning ticket of a GNN be also effective for graph transferring learning? We call it the transferable graph lottery ticket (GLT) hypothesis. Extensive experiments were conducted which demonstrate the superiority of our proposed sparsification method over UGS, and which empirically verified our transferable GLT hypothesis.