Overview
Experiments show consistent compute savings across three GTs and three datasets with concrete numeric gains, but the study prunes components separately and leaves joint pruning and per-graph tuning for future work.
Citations0
Evidence Strength0.70
Confidence0.80
Risk Signals10
Trust Signals
Findings with numeric evidence: 3/3
Findings with evidence refs: 3/3
Results with explicit delta: 3/3
Reproducibility
Status: Code + data available
Open source: Partial
At A Glance
Cost impact: 70%
Production readiness: 60%
Novelty: 50%
Why It Matters For Business
GTSP can reduce Graph Transformer compute and memory by tens of percent while keeping or improving accuracy on evaluated benchmarks, enabling cheaper training and deployment on constrained hardware.
Who Should Care
Summary TLDR
The paper introduces GTSP, a practical mask-based framework that sparsifies Graph Transformers along four axes: input tokens (nodes), attention heads, layers, and weights. GTSP uses learnable masks, Gumbel-softmax top-k selection for tokens, gradient-based importance for heads, stochastic layer dropping, gradual magnitude pruning plus regrowth for weights. On GraphTrans/Graphormer/GraphGPS across NCI1, OGBG-HIV, and OGBG-Molpcba, GTSP cuts FLOPs by ~30–47% while keeping accuracy similar and sometimes improving it (e.g., ROC-AUC 0.7633→0.7773 on OGBG-HIV for 50% weight sparsity). The paper studies each pruning axis separately and warns that joint pruning and per-graph ratio tuning remain open
Problem Statement
Graph Transformers match or exceed GNNs but cost much more compute and memory because of multi-head self-attention. Existing GNN pruning methods target edges or channels and node-classification tasks; they don't directly transfer to Graph Transformers used for graph-level tasks. The paper asks: can we safely sparsify Graph Transformers across tokens, heads, layers, and weights to cut compute while keeping performance?
Main Contribution
A systematic analysis of redundancy in Graph Transformers across four components: input tokens, attention heads, layers, and weights.
GTSP: a unified, mask-based sparsification framework with differentiable token selection, head importance scoring, stochastic layer dropping, and gradual weight pruning with regrowth.
Key Findings
Weight pruning (50% sparsity) can increase AUC on OGBG-HIV while cutting compute.
Token pruning gives the largest FLOPs cuts but risks accuracy loss on small graphs.
Results
| Metric | Value | Baseline | Delta | Split / Dataset | Evidence | Evidence Ref |
|---|---|---|---|---|---|---|
| OGBG-HIV ROC-AUC | Baseline 0.7633 → GTSP-WP (50%) 0.7773 | 0.7633 | +0.014 | OGBG-HIV | GTSP weight pruning 50% improved ROC-AUC while reducing FLOPs | Table 1 |
| NCI1 FLOPs reduction (token pruning) | FLOPs −47.4% | 0% FLOPs saving | −47.4% | NCI1 | Top-k token pruning (TP) yields largest FLOPs cut on small dataset | Table 1 |
What To Try In 7 Days
Run 40–50% weight magnitude pruning with regrowth on your Graph Transformer; compare ROC-AUC and FLOPs.
If graphs are large, test token (node) pruning with top-k selection and validate accuracy on a holdout set.
Try stochastic layer dropping to halve depth and measure inference latency and accuracy trade-offs.
Optimization Features
Token Efficiency
Model Optimization
System Optimization
Training Optimization
Inference Optimization
Reproducibility
Risks & Boundaries
Limitations
Paper focuses on pruning each component separately; joint pruning interactions are not evaluated.
Token pruning can harm accuracy on small graphs (20–30 nodes); per-dataset tuning is needed.
When Not To Use
On small graphs where removing tokens removes crucial nodes.
When you need an out-of-the-box joint pruning recipe — paper treats axes independently.
Failure Modes
Over-pruning can drop accuracy sharply if important heads or nodes are removed.
Token selector may get stuck in local structures without proper score perturbation.