HEGformer: Representation Learning on Heterogeneous Graph Neural Network with Efficient Transformer

Heterogeneous Graph Neural Networks (HGNNs) have shown remarkable success in learning from real-world graph data by capturing complex heterogeneous characteristics like various semantic and relational information across different node and edge types.However, as graphs grow in size and complexity, existing models struggle with scalability. Current graph transformers are often constrained by sampling algorithms, limiting their receptive fields and preventing them from fully leveraging the transformer’s capability. Simply expanding the receptive field (i.e., long-range dependencies) leads to quadratic computational costs, resulting in time and memory constraints. In addition, although some transformer architectures are trying to overcome the quadratic computational complexity, few of them have considered the relational graph structure or heterogeneity.To address these challenges, we proposed HEGformer, an innovative integration of Graph Transformers and Heterogeneous Graphs. We propose two techniques: Relational Local Sensitive Hashing (R-LSH) and Relational-aware Enhanced Attention (REA). R-LSH extends the traditional Local Sensitive Hashing approach by incorporating relational information between different node types, significantly reducing the quadratic computational cost commonly associated with vanilla Graph Transformers while maintaining relational integrity. REA leverages node-type information to create global relational contexts, enhancing attention mechanisms to be more type-aware and computationally efficient. Our methods demonstrate improved scalability and competitive performance on graph-based tasks of various sizes, offering a powerful model for future research in large-scale, complex graph analytics.