GraphTARIF: Linear Graph Transformer with Augmented Rank and Improved Focus
This work addresses a bottleneck in efficient graph learning for researchers and practitioners, offering an incremental improvement over existing linear attention methods.
The paper tackled the problem of reduced expressiveness in linear attention mechanisms for Graph Transformers, which limits classification ability due to low-rank projections and uniform attention distributions, and proposed a hybrid framework that enhanced rank and focus to achieve competitive performance on graph benchmarks while maintaining scalability.
Linear attention mechanisms have emerged as efficient alternatives to full self-attention in Graph Transformers, offering linear time complexity. However, existing linear attention models often suffer from a significant drop in expressiveness due to low-rank projection structures and overly uniform attention distributions. We theoretically prove that these properties reduce the class separability of node representations, limiting the model's classification ability. To address this, we propose a novel hybrid framework that enhances both the rank and focus of attention. Specifically, we enhance linear attention by attaching a gated local graph network branch to the value matrix, thereby increasing the rank of the resulting attention map. Furthermore, to alleviate the excessive smoothing effect inherent in linear attention, we introduce a learnable log-power function into the attention scores to reduce entropy and sharpen focus. We theoretically show that this function decreases entropy in the attention distribution, enhancing the separability of learned embeddings. Extensive experiments on both homophilic and heterophilic graph benchmarks demonstrate that our method achieves competitive performance while preserving the scalability of linear attention.