# Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 66 references that are in the map.
- First posted on arXiv 2 Feb 2024.

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

- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [Sparse Networks from Scratch: Faster Training without Losing Performance](https://mlsanity.com/paper/1907.04840/) (2019)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Learning to Drop: Robust Graph Neural Network via Topological Denoising](https://mlsanity.com/paper/2011.07057/) (2020)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training](https://mlsanity.com/paper/2102.02887/) (2021)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Graph Structure Learning with Variational Information Bottleneck](https://mlsanity.com/paper/2112.08903/) (2021)
- [MEST: Accurate and Fast Memory-Economic Sparse Training Framework on the Edge](https://mlsanity.com/paper/2110.14032/) (2021)

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

- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [Graph-Augmented Large Language Model Agents: Current Progress and Future Prospects](https://mlsanity.com/paper/2507.21407/) (2025)
- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [CaT-GNN: Enhancing Credit Card Fraud Detection via Causal Temporal Graph Neural Networks](https://mlsanity.com/paper/2402.14708/) (2024)
- [Causal Deciphering and Inpainting in Spatio-Temporal Dynamics via Diffusion Model](https://mlsanity.com/paper/2409.19608/) (2024)
- [IceBerg: Debiased Self-Training for Class-Imbalanced Node Classification](https://mlsanity.com/paper/2502.06280/) (2025)
- [AirRadar: Inferring Nationwide Air Quality in China with Deep Neural Networks](https://mlsanity.com/paper/2501.13141/) (2025)
- [Fast Track to Winning Tickets: Repowering One-Shot Pruning for Graph Neural Networks](https://mlsanity.com/paper/2412.07605/) (2024)
- [DYNA-PRUNER: Input-Adaptive Data-Model Co-Pruning for Efficient and Scalable Spatio-Temporal Media Prediction](https://mlsanity.com/paper/2606.15346/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs. A promising solution is to remove non-essential edges to reduce the computational overheads in GNN. Previous literature generally falls into two categories: topology-guided and semantic-guided. The former maintains certain graph topological properties yet often underperforms on GNNs due to low integration with neural network training. The latter performs well at lower sparsity on GNNs but faces performance collapse at higher sparsity levels. With this in mind, we take the first step to propose a new research line and concept termed Graph Sparse Training (GST), which dynamically manipulates sparsity at the data level. Specifically, GST initially constructs a topology & semantic anchor at a low training cost, followed by performing dynamic sparse training to align the sparse graph with the anchor. We introduce the Equilibria Sparsification Principle to guide this process, effectively balancing the preservation of both topological and semantic information. Ultimately, GST produces a sparse graph with maximum topological integrity and no performance degradation. Extensive experiments on 6 datasets and 5 backbones showcase that GST (I) identifies subgraphs at higher graph sparsity levels (1.67%~15.85% uparrow) than state-of-the-art sparsification methods, (II) preserves more key spectral properties, (III) achieves 1.27-3.42× speedup in GNN inference and (IV) successfully helps graph adversarial defense and graph lottery tickets.