Introduction
Graph Neural Networks (GNNs) have long been the standard for processing graph-structured data. However, as datasets grow in complexity and scale, traditional GNNs face significant hurdles, including over-smoothing, over-squashing, and limited expressive power. While Transformers have revolutionized fields like Natural Language Processing (NLP) and Computer Vision (CV) by capturing long-range dependencies through global self-attention, their application to large-scale heterogeneous graphs has been limited by quadratic computational complexity and the difficulty of modeling diverse node and edge types.
This paper introduces the Poly-tokenized Heterogeneous Graph Transformer (PHGT), a novel architecture designed to bridge the gap between the reasoning capabilities of Transformers and the structural complexity of large-scale heterogeneous graphs.
The Challenge of Heterogeneous Graphs
Real-world graphs, such as e-commerce platforms or academic citation networks, are inherently heterogeneous, containing multiple types of nodes and relationships. Standard Transformers often fail to capture these rich semantics because they treat all connections uniformly. Furthermore, the $O(N^2)$ complexity of global self-attention makes them impractical for massive networks where every node cannot realistically attend to every other node.
The PHGT Architecture: Poly-Tokenization
The core innovation of PHGT is the Poly-tokenization Mechanism. Instead of treating every node as a single token, PHGT represents a target node using three distinct "grains" of information, allowing the model to capture local, semantic, and global contexts simultaneously:
- Node Tokens: These represent the immediate local neighborhood. By sampling a subgraph around the target node, the model treats individual neighbors as tokens, preserving fine-grained local structure.
- Semantic Tokens: To capture high-order relationships, PHGT utilizes meta-paths (e.g., Author-Paper-Conference). Instances of these paths are aggregated into tokens, allowing the Transformer to treat complex semantic patterns as first-class citizens.
- Global Tokens: To provide a "bird's-eye view" of the entire graph without quadratic costs, PHGT employs a fast heterogeneous clustering algorithm. Each cluster becomes a global token, enabling nodes to interact with distant parts of the graph via these summaries.
The architecture integrates a Structure Encoder to capture initial local connectivity, followed by the poly-tokenization step and multiple Transformer blocks where these diverse tokens interact via multi-head self-attention.
Experimental Evaluation
PHGT was evaluated on four major heterogeneous graph benchmarks: DBLP, ACM, IMDB, and Freebase. The model consistently outperformed state-of-the-art baselines, including traditional HGNNs (like HAN) and recent graph transformers (like HINormer). For instance, on the DBLP dataset, PHGT achieved a Micro-F1 score of 95.33%, surpassing previous benchmarks.
Scalability and Efficiency
A key advantage of PHGT is its efficiency. In time-cost experiments, PHGT proved to be 7–11x faster than spectral graph coarsening methods. More importantly, it addresses the memory limitations of "global" graph transformers. While models like Graphormer often suffer from Out-Of-Memory (OOM) errors as graph sizes exceed 8,000 nodes, PHGT maintains a stable and low memory footprint.
Conclusion
PHGT demonstrates that the combination of GNNs for structural encoding and Transformers for high-level reasoning is a powerful approach for heterogeneous graph analysis. By using poly-tokenization, the model achieves a global receptive field and captures complex semantics without sacrificing scalability. Future work may focus on automating meta-path discovery and refining the end-to-end learnability of the clustering process to further enhance performance.
Summary updated