Exploring sparsity in graph transformers.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Neural Networks

Background:

• Graph Transformers (GTs) demonstrate high performance on graph-related tasks.
• The substantial computational expense of GTs limits their practical application, particularly in resource-limited settings.
• Existing GT models exhibit redundancy, suggesting potential for optimization.

Purpose of the Study:

• To investigate the feasibility and effectiveness of sparsifying Graph Transformers.
• To propose a comprehensive framework for reducing the computational complexity of GTs.
• To enable efficient deployment of GTs in resource-constrained environments.

Main Methods:

• Developed a Graph Transformer Sparsification (GTSP) framework targeting four key areas: input graph data, attention heads, model layers, and model weights.
• Incorporated differentiable masks for each compressible component to facilitate end-to-end pruning.
• Conducted extensive experiments on established GT models like GraphTrans, Graphormer, and GraphGPS.

Main Results:

• GTSP significantly reduces computational costs, demonstrated by a 30% decrease in Floating Point Operations on the OGBG-HIV dataset.
• Achieved marginal accuracy loss, and in some cases, accuracy improvements, such as a 1.8% increase in Area Under the Curve.
• Provided novel insights into attention head characteristics and attention mechanism behavior.

Conclusions:

• The proposed GTSP framework is effective in reducing the computational complexity of Graph Transformers.
• Sparsification offers a viable strategy for enhancing the efficiency of GTs without substantial performance degradation.
• The findings offer valuable directions for future research in efficient graph transformer architectures.