Research map / Graph learning / GNN architectures
Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness
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.
Proposes Graph Sparse Training (GST), which builds a topology-and-semantic anchor from short full-graph training and then dynamically prunes/regrows edges guided by eigenvalue-variation and gradient-based semantic criteria.
Problem
Graph sparsification for GNN efficiency: topology-guided sparsifiers preserve spectral properties but underperform with GNNs, while semantic-guided sparsifiers collapse at high graph sparsity.
Approach
Treat graph sparsification as dynamic sparse training at the data level: an early-training anchor (mask plus outputs) guides prune-and-regrow of edges using a combined score of Laplacian eigenvalue variation (topology) and KL-output gradient magnitude (semantics), following an "Equilibria Sparsification Principle".
Key results
- GST achieves 1.27-1.67x GPU inference speedup on Cora/Citeseer/PubMed with GCN/GAT and 33.29%-37.22% MACs savings, with averages of 1.30x, 1.37x and 1.45x for GCN, GIN and GAT.
- On Ogbn-ArXiv with 40% sparsity, GST+GraphSAGE/ClusterGCN lose only 0.43% and 0.48% accuracy.
- GST outperforms other sparsifiers by 1.23%-5.39% at 80% graph sparsity on the small benchmarks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add dynamic sparse graph fine-tuning (ablation) | GST · Citeseer + GCN | extreme graph sparsity: 30.41_{\pm0.75} -> 43.43_{\pm1.46} | Helped |
| add the semantic criterion to edge updates (ablation) | GST · Citeseer + GCN | extreme graph sparsity: 39.82_{\pm1.49} -> 43.43_{\pm1.46} | Helped |
| add the topological criterion to edge updates (ablation) | GST · Citeseer + GCN | extreme graph sparsity: 42.08_{\pm0.56} -> 43.43_{\pm1.46} | Helped |
Surprising findings
- GST at 50% graph sparsity on GIN+PubMed improves over the dense baseline by 0.3%, while other sparsifiers drop by 0.36%-3.17%.
- In the ablation, removing the dynamic fine-tuning (GST w/o tuning) causes the largest drop in extreme sparsity, while removing the semantic criterion hurts more than removing the topological one.
Limitations
- Eigenvalue-variation approximation uses only top and bottom K=20 eigenvalues, which is a heuristic.
- Evaluated only on node classification with homophilous benchmarks; heterophilic and heterogeneous graphs are left for future work.
- Several baselines (e.g., MGSpar, WD-GLT) were reimplemented since no official code was provided, which may affect comparability.
Experimental setup
Datasets: Cora Citeseer PubMed Ogbn-ArXiv Ogbn-Proteins Ogbn-Products
Benchmarks: Cora Citeseer PubMed Ogbn-ArXiv Ogbn-Proteins Ogbn-Products
Metrics: accuracy ROC-AUC extreme graph sparsity relative eigenvalue error MACs GPU latency
Baselines: SCAN Local Similarity DSpar UGS WD-GLT MGSpar
Builds on: dynamic sparse training UGS effective resistance sparsification Early-Bird tickets
Closest papers by meaning
- Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks (ICLR 2023 · similarity 0.91)
- Graph Sparsification via Mixture of Graphs (ICLR 2025 · similarity 0.89)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.88)
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.88)
- Towards Pre-trained Graph Condensation via Optimal Transport (NeurIPS 2025 · similarity 0.88)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · 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.