Exploring sparsity in graph transformers

doi:10.1016/j.neunet.2024.106265

Exploring sparsity in graph transformers

2024-06-01

1

OA

AI

DOI：10.1016/j.neunet.2024.106265

Original

Save

View PDF

Abstract

En 中文

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 underexplored topic. We first discuss the redundancy of GTs based on the characteristics of existing GT models, and then propose a comprehensive G raph T ransformer 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 demonstrate that GTSP effectively reduces computational costs, with only marginal decreases in accuracy or, in some instances, even improvements. For example, GTSP results in a 30% reduction in Floating Point Operations while contributing to a 1.8% increase in Area Under the Curve accuracy on the 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. Our code is available at https://github.com/LiuChuang0059/GTSP.

Keywords:

Graph transformers

Graph sparse training

Model pruning

Graph classification

Exploring sparsity in graph transformers

Abstract

AI Summary

Journal

Organization