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 \textbf{G}raph \textbf{T}ransformer \textbf{SP}arsification
(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.

研究论文简介：为解决图形变换器（GTs）的高计算成本问题，在现有 GT 模型特征的基础上探索了图形变换器稀疏化的可行性，并提出了一个能够减少 GTs 计算复杂度的综合框架（GTSP），通过实验验证该框架能有效降低计算成本，同时在精度上只有微弱的降低或甚至有所提升。