GraphTARIF: Linear Graph Transformer with Augmented Rank and Improved Focus

Zhaolin Hu, Kun Li, Hehe Fan, Yi Yang

Abstract

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.

Introduction

Graph Transformers (GTs) have revolutionized graph representation learning by enabling all-to-all node interactions, capturing long-range dependencies that traditional Graph Neural Networks (GNNs) often fail to reach. However, the standard self-attention mechanism incurs a quadratic computational cost ($O(N^2)$), which is prohibitive for large-scale real-world graphs.

While Linear Self-Attention (LSA) models have been developed to reduce this complexity to $O(N)$, they frequently underperform compared to simple GNNs. This research identifies two primary "silent killers" of performance in LSA:

  1. Low-Rank Bottleneck: LSA attention matrices are mathematically restricted to a low rank, limiting the complexity of interaction patterns they can represent.
  2. High Entropy (Uniformity): LSA tends to produce "flat" or "blurry" attention distributions. This leads to oversmoothing, where node embeddings become nearly identical, destroying the discriminative features necessary for classification.
Comparison of attention distributions in Softmax vs. Linear Attention across heterophilic (Toloker) and homophilic (CS) graphs, highlighting the uniformity issue in standard linear models.

Methodology: The GraphTARIF Framework

To overcome these limitations, we propose GraphTARIF (Linear Graph Transformer with Augmented Rank and Improved Focus). The architecture introduces three key innovations:

High-Rank Augmentation

To break the low-rank mathematical constraint of LSA, GraphTARIF incorporates a parallel branch using a Graph Attention Network (GAT). Since GAT operates on sparse, local edges, it provides a high-rank signal (up to $N-1$). A learnable gating mechanism balances this local structural detail with the global perspective of the linear transformer.

Learnable Log-Power Sharpening

To address the "blurry" attention problem, we introduce a custom sharpening function to transform queries and keys: $$f(x; p, q) = x \cdot (\log(1 + x^p))^q$$ Unlike standard power functions ($x^p$), which can lead to numerical instability and exploding gradients, this log-power formulation sharpens the attention focus (reducing entropy) while growing slowly enough to ensure stable training.

Node-wise Post-modulation

Following the global attention step, the model re-weights the output using the node's original features. This step ensures that the unique "identity" of each node is preserved even after global feature mixing.

Experimental Results

GraphTARIF was evaluated across 14 diverse datasets, including homophilic graphs (e.g., WikiCS, Amazon-Photo), heterophilic graphs (e.g., Roman-Empire, Minesweeper), and large-scale networks (e.g., ogbn-products with 2.4M nodes).

Performance and Efficiency

GraphTARIF consistently outperformed recent state-of-the-art (SOTA) models. It achieved an average performance rank of 1.0 across all heterophilic benchmarks and 1.6 across homophilic benchmarks. Notably, it maintains superior accuracy while remaining highly efficient in terms of both time and memory.

Performance comparison on ROC-AUC vs. Time per Epoch vs. GPU Memory. GraphTARIF (red dot) achieves superior accuracy with high efficiency and low memory footprint.

Key Insights

  • Mathematical Separability: Theoretical analysis (Theorem 1) shows that inter-class variance is upper-bounded by the rank of the attention matrix. By increasing the rank, GraphTARIF directly improves class separability.
  • Scalability: The model demonstrates strictly linear growth in training time and memory usage as node counts increase, making it suitable for production-scale graphs.

Conclusion

GraphTARIF addresses the fundamental weaknesses of linear attention in graph learning by augmenting rank and sharpening focus. While currently focused on node classification, the architectural improvements provide a robust foundation for future applications in link prediction and graph-level tasks. The use of log-power sharpening offers a stable alternative to traditional attention-focusing techniques, with potential applications in other domains where linear attention is gaining traction, such as large language models.

Summary updated

Abstract

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.
BibTeX
@misc{hu2025graphtarif,
  author = {Zhaolin Hu and Kun Li and Hehe Fan and Yi Yang},
  title = {{GraphTARIF: Linear Graph Transformer with Augmented Rank and Improved Focus}},
  year = {2025},
  eprint = {2510.10631},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.10631},
}
Figure