# Pre-Training Identification of Graph Winning Tickets in Adaptive Spatial-Temporal Graph Neural Networks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 12 Jun 2024.

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

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition](https://mlsanity.com/paper/1801.07455/) (2018)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [Adaptive Graph Convolutional Recurrent Network for Traffic Forecasting](https://mlsanity.com/paper/2007.02842/) (2020)
- [Spatial-Temporal Graph ODE Networks for Traffic Flow Forecasting](https://mlsanity.com/paper/2106.12931/) (2021)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [Dynamic Graph Convolutional Recurrent Network for Traffic Prediction: Benchmark and Solution](https://mlsanity.com/paper/2104.14917/) (2021)
- [Graph Neural Controlled Differential Equations for Traffic Forecasting](https://mlsanity.com/paper/2112.03558/) (2021)
- [Decoupled Dynamic Spatial-Temporal Graph Neural Network for Traffic Forecasting](https://mlsanity.com/paper/2206.09112/) (2022)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [LargeST: A Benchmark Dataset for Large-Scale Traffic Forecasting](https://mlsanity.com/paper/2306.08259/) (2023)
- [Spatio-Temporal Meta-Graph Learning for Traffic Forecasting](https://mlsanity.com/paper/2211.14701/) (2022)
- [EarlyBERT: Efficient BERT Training via Early-bird Lottery Tickets](https://mlsanity.com/paper/2101.00063/) (2020)
- [STG2Seq: Spatial-temporal Graph to Sequence Model for Multi-step Passenger Demand Forecasting](https://mlsanity.com/paper/1905.10069/) (2019)
- [Early-Bird GCNs: Graph-Network Co-Optimization Towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Tickets](https://mlsanity.com/paper/2103.00794/) (2021)
- [Localised Adaptive Spatial-Temporal Graph Neural Network](https://mlsanity.com/paper/2306.06930/) (2023)
- [Modeling Spatio-temporal Dynamical Systems with Neural Discrete Learning and Levels-of-Experts](https://mlsanity.com/paper/2402.05970/) (2024)

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

- [HieraMix: A Hierarchical MLP-Mixer for Large-Scale Traffic Forecasting](https://mlsanity.com/paper/2512.07854/) (2025)
- [A General ReLearner: Empowering Spatiotemporal Prediction by Re-learning Input-label Residual](https://mlsanity.com/paper/2602.02563/) (2026)

## Abstract (arXiv)

In this paper, we present a novel method to significantly enhance the computational efficiency of Adaptive Spatial-Temporal Graph Neural Networks (ASTGNNs) by introducing the concept of the Graph Winning Ticket (GWT), derived from the Lottery Ticket Hypothesis (LTH). By adopting a pre-determined star topology as a GWT prior to training, we balance edge reduction with efficient information propagation, reducing computational demands while maintaining high model performance. Both the time and memory computational complexity of generating adaptive spatial-temporal graphs is significantly reduced from O(N2) to O(N). Our approach streamlines the ASTGNN deployment by eliminating the need for exhaustive training, pruning, and retraining cycles, and demonstrates empirically across various datasets that it is possible to achieve comparable performance to full models with substantially lower computational costs. Specifically, our approach enables training ASTGNNs on the largest scale spatial-temporal dataset using a single A6000 equipped with 48 GB of memory, overcoming the out-of-memory issue encountered during original training and even achieving state-of-the-art performance. Furthermore, we delve into the effectiveness of the GWT from the perspective of spectral graph theory, providing substantial theoretical support. This advancement not only proves the existence of efficient sub-networks within ASTGNNs but also broadens the applicability of the LTH in resource-constrained settings, marking a significant step forward in the field of graph neural networks. Code is available at https://anonymous.4open.science/r/paper-1430.