mlsanityData to 7 Oct 2026

Exploring Sparsity in Graph Transformers

arXiv 2312.05479 ↗First posted 9 Dec 2023cs.LG cs.AIcited by 3

Not on the map. Why?

Abstract (arXiv)

Graph Transformers (GTs) have achieved impressive results on various graph-related tasks. However, the huge computational cost of GTs hinders their deployment and application, especially in resource-constrained environments. Therefore, in this paper, we explore the feasibility of sparsifying GTs, a significant yet under-explored topic. We first discuss the redundancy of GTs based on the characteristics of existing GT models, and then propose a comprehensive Graph Transformer SParsification (GTSP) framework that helps to reduce the computational complexity of GTs from four dimensions: the input graph data, attention heads, model layers, and model weights. Specifically, GTSP designs differentiable masks for each individual compressible component, enabling effective end-to-end pruning. We examine our GTSP through extensive experiments on prominent GTs, including GraphTrans, Graphormer, and GraphGPS. The experimental results substantiate that GTSP effectively cuts computational costs, accompanied by only marginal decreases in accuracy or, in some cases, even improvements. For instance, GTSP yields a reduction of 30% in Floating Point Operations while contributing to a 1.8% increase in Area Under the Curve accuracy on OGBG-HIV dataset. Furthermore, we provide several insights on the characteristics of attention heads and the behavior of attention mechanisms, all of which have immense potential to inspire future research endeavors in this domain.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 42 of its 59 references that are in the map. First posted on arXiv 9 Dec 2023.

Builds on

42 of 59 references.

References · 42

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,708
  6. 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,250
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  8. 2019Similarity of Neural Network Representations Revisitedcited by 1,695
  9. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 994
  10. 2016Deep Networks with Stochastic Depthcited by 973
  11. 2019Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Prunedcited by 844
  12. 2019Are Sixteen Heads Really Better than One?cited by 803
30 more
  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  2. 2020A Generalization of Transformer Networks to Graphscited by 653
  3. 2021Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networkscited by 521
  4. 2019Rigging the Lottery: Making All Tickets Winnerscited by 491
  5. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  6. 2019Reducing Transformer Depth on Demand with Structured Dropoutcited by 434
  7. 2017Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Sciencecited by 325
  8. 2016Exponential expressivity in deep neural networks through transient chaoscited by 260
  9. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 193
  10. 2021Chasing Sparsity in Vision Transformers: An End-to-End Explorationcited by 181
  11. 2021Learned Token Pruning for Transformerscited by 138
  12. 2022NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphscited by 137
  13. 2020Distilling Knowledge from Graph Convolutional Networkscited by 128
  14. 2021A Unified Lottery Ticket Hypothesis for Graph Neural Networkscited by 118
  15. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 113
  16. 2022Transformer for Graphs: An Overview from Architecture Perspectivecited by 107
  17. 2021Sparse Training via Boosting Pruning Plasticity with Neuroregenerationcited by 83
  18. 2022Hierarchical Graph Transformer with Adaptive Node Samplingcited by 72
  19. 2021Graph-Free Knowledge Distillation for Graph Neural Networkscited by 46
  20. 2019Sparse Graph Attention Networkscited by 41
  21. 2020On Self-Distilling Graph Neural Networkcited by 35
  22. 2020Binary Graph Neural Networkscited by 32
  23. 2020Bi-GCN: Binary Graph Convolutional Networkcited by 27
  24. 2021Early-Bird GCNs: Graph-Network Co-Optimization Towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Ticketscited by 27
  25. 2022Survey on Graph Neural Network Acceleration: An Algorithmic Perspectivecited by 26
  26. 2023Rethinking Graph Lottery Tickets: Graph Sparsity Matterscited by 23
  27. 2019Fast Haar Transforms for Graph Neural Networkscited by 20
  28. 2022Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networkscited by 18
  29. 2022Towards Sparsification of Graph Neural Networkscited by 18
  30. 2023Are More Layers Beneficial to Graph Transformers?cited by 14

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 2.

3 papers.

  1. 2024Gradformer: Graph Transformer with Exponential Decaycited by 10
  2. 2025Biologically Plausible Brain Graph Transformercited by 9
  3. 2025Graph Fourier Transformer with Structure-Frequency Informationcited by 0