A Closer Look at Graph Transformers: Cross-Aggregation and Beyond

Di Jin · Zhen Wang (Northwestern Polytechnical University) · Xiaochun Cao (SUN YAT-SEN UNIVERSITY) · Jiaming Zhuo (Hebei University of Technology) · Ziyi Ma (Hebei University of Technology) · Yintong Lu (Hebei University of Technology) · Yuwei Liu (Hebei University of Technology) · Kun Fu (Hebei University of Technology) · Chuan Wang (Beijing Jiaotong University) · Wu Wenning (Northwest Polytechnical University Xi'an) · Liang Yang (Hebei University of Technology)

benchmark datasets consistency constraintcross aggregationdual cross-attention moduleeffective aggregationgraph neural networks graph transformersinteractive learninglinear computational complexity long-range dependencies overfitting representational alignment structural biasestopology informationuniversal graph cross-attention transformer

Graph Transformers (GTs), which effectively capture long-range dependencies and structural biases simultaneously, have recently emerged as promising alternatives to traditional Graph Neural Networks (GNNs). Advanced approaches for GTs to leverage topology information involve integrating GNN modules or modulating node attributes using positional encodings. Unfortunately, the underlying mechanism driving their effectiveness remains insufficiently understood. In this paper, we revisit these strategies and uncover a shared underlying mechanism—Cross Aggregation—that effectively captures the interaction between graph topology and node attributes. Building on this insight, we propose the Universal Graph Cross-attention Transformer (UGCFormer), a universal GT framework with linear computational complexity. The idea is to interactively learn the representations of graph topology and node attributes through a linearized Dual Cross-attention (DCA) module. In theory, this module can adaptively capture interactions between these two types of graph information, thereby achieving effective aggregation. To alleviate overfitting arising from the dual-channel design, we introduce a consistency constraint that enforces representational alignment. Extensive evaluations on multiple benchmark datasets demonstrate the effectiveness and efficiency of UGCFormer.