# Early-Bird GCNs: Graph-Network Co-Optimization Towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Tickets

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 32 references that are in the map.
- First posted on arXiv 1 Mar 2021.

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

- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [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)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [An Analysis of Deep Neural Network Models for Practical Applications](https://mlsanity.com/paper/1605.07678/) (2016)
- [Degree-Quant: Quantization-Aware Training for Graph Neural Networks](https://mlsanity.com/paper/2008.05000/) (2020)
- [EarlyBERT: Efficient BERT Training via Early-bird Lottery Tickets](https://mlsanity.com/paper/2101.00063/) (2020)
- [HyGCN: A GCN Accelerator with Hybrid Architecture](https://mlsanity.com/paper/2001.02514/) (2020)
- [Learning Graph Convolutional Network for Skeleton-based Human Action Recognition by Neural Searching](https://mlsanity.com/paper/1911.04131/) (2019)
- [GraphNAS: Graph Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1904.09981/) (2019)
- [Accurate, Efficient and Scalable Graph Embedding](https://mlsanity.com/paper/1810.11899/) (2018)
- [Winning Lottery Tickets in Deep Generative Models](https://mlsanity.com/paper/2010.02350/) (2020)

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

- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (2024)
- [Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks](https://mlsanity.com/paper/2207.08629/) (2022)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks](https://mlsanity.com/paper/2302.02922/) (2023)
- [Localised Adaptive Spatial-Temporal Graph Neural Network](https://mlsanity.com/paper/2306.06930/) (2023)
- [SuperTickets: Drawing Task-Agnostic Lottery Tickets from Supernets via Jointly Architecture Searching and Parameter Pruning](https://mlsanity.com/paper/2207.03677/) (2022)
- [Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness](https://mlsanity.com/paper/2402.01242/) (2024)
- [GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks](https://mlsanity.com/paper/2310.03399/) (2023)
- [Adversarial Erasing with Pruned Elements: Towards Better Graph Lottery Ticket](https://mlsanity.com/paper/2308.02916/) (2023)
- [Early-Bird Diffusion: Investigating and Leveraging Timestep-Aware Early-Bird Tickets in Diffusion Models for Efficient Training](https://mlsanity.com/paper/2504.09606/) (2025)
- [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)
- [RAM: Replace Attention with MLP for Efficient Multivariate Time Series Forecasting](https://mlsanity.com/paper/2410.24023/) (2024)
- [Unifews: You Need Fewer Operations for Efficient Graph Neural Networks](https://mlsanity.com/paper/2403.13268/) (2024)
- [Pre-Training Identification of Graph Winning Tickets in Adaptive Spatial-Temporal Graph Neural Networks](https://mlsanity.com/paper/2406.08287/) (2024)
- [Towards Lightweight Graph Neural Network Search with Curriculum Graph Sparsification](https://mlsanity.com/paper/2406.16357/) (2024)
- [Dynamic Localisation of Spatial-Temporal Graph Neural Network](https://mlsanity.com/paper/2501.04239/) (2025)
- [SliceFine: The Universal Winning-Slice Hypothesis for Pretrained Networks](https://mlsanity.com/paper/2510.08513/) (2025)
- [An LLM-Guided Query-Aware Inference System for GNN Models on Large Knowledge Graphs](https://mlsanity.com/paper/2603.04545/) (2026)
- [Towards Real-Time Temporal Graph Learning](https://mlsanity.com/paper/2210.04114/) (2022)
- [Acceleration Algorithms in GNNs: A Survey](https://mlsanity.com/paper/2405.04114/) (2024)
- [Fast Track to Winning Tickets: Repowering One-Shot Pruning for Graph Neural Networks](https://mlsanity.com/paper/2412.07605/) (2024)
- [GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA](https://mlsanity.com/paper/2604.21290/) (2026)
- [Informative Graph Structure Learning](https://mlsanity.com/paper/2605.16809/) (2026)
- [Early-Bird Decoding: Accelerating Diffusion LLMs with Learnable Block Sizes and Parallel Sampling](https://mlsanity.com/paper/2609.16450/) (2026)

## Abstract (arXiv)

Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art deep learning model for representation learning on graphs. However, it remains notoriously challenging to train and inference GCNs over large graph datasets, limiting their application to large real-world graphs and hindering the exploration of deeper and more sophisticated GCN graphs. This is because as the graph size grows, the sheer number of node features and the large adjacency matrix can easily explode the required memory and data movements. To tackle the aforementioned challenges, we explore the possibility of drawing lottery tickets when sparsifying GCN graphs, i.e., subgraphs that largely shrink the adjacency matrix yet are capable of achieving accuracy comparable to or even better than their full graphs. Specifically, we for the first time discover the existence of graph early-bird (GEB) tickets that emerge at the very early stage when sparsifying GCN graphs, and propose a simple yet effective detector to automatically identify the emergence of such GEB tickets. Furthermore, we advocate graph-model co-optimization and develop a generic efficient GCN early-bird training framework dubbed GEBT that can significantly boost the efficiency of GCN training by (1) drawing joint early-bird tickets between the GCN graphs and models and (2) enabling simultaneously sparsification of both the GCN graphs and models. Experiments on various GCN models and datasets consistently validate our GEB finding and the effectiveness of our GEBT, e.g., our GEBT achieves up to 80.2% ~ 85.6% and 84.6% ~ 87.5% savings of GCN training and inference costs while offering a comparable or even better accuracy as compared to state-of-the-art methods. Our source code and supplementary appendix are available at https://github.com/RICE-EIC/Early-Bird-GCN.