Abstract
Graph neural networks (GNNs) have shown widespread success for learning on graphs, but they still face fundamental drawbacks, such as limited expressive power, over-smoothing, and over-squashing. Meanwhile, the transformer architecture offers a potential solution to these issues. However, existing graph transformers primarily cater to homogeneous graphs and are unable to model the intricate semantics of heterogeneous graphs. Moreover, unlike small molecular graphs where the entire graph can be considered as the receptive field in graph transformers, real-world heterogeneous graphs comprise a significantly larger number of nodes and cannot be entirely treated as such. Consequently, existing graph transformers struggle to capture the long-range dependencies in these complex heterogeneous graphs. To address these two limitations, we present Poly-tokenized Heterogeneous Graph Transformer (PHGT), a novel transformer-based heterogeneous graph model. In addition to traditional node tokens, PHGT introduces a novel poly-token design with two more token types: semantic tokens and global tokens. Semantic tokens encapsulate high-order heterogeneous semantic relationships, while global tokens capture semantic-aware long-range interactions. We validate the effectiveness of PHGT through extensive experiments on standardized heterogeneous graph benchmarks, demonstrating significant improvements over state-of-the-art heterogeneous graph representation learning models.
Introduction
Graph Neural Networks (GNNs) have long been the workhorse for relational data, but they hit a wall when faced with "over-smoothing" (where node representations become indistinguishable) and "over-squashing" (where information is lost as it's compressed through the network). While Transformer architectures offer a fix, they were originally built for sequences or small molecular graphs. Applying them to massive, complex Heterogeneous Graphs—networks with diverse node and edge types like academic databases or e-commerce systems—remains a significant challenge.
Most existing graph transformers are designed for homogeneous graphs (where all nodes and edges are the same type). When applied to heterogeneous graphs (HINs), they struggle with two main issues:
- Semantic Complexity: Standard transformers often ignore high-order "meta-paths" (e.g., Author-Paper-Author) or only use them as secondary features.
- The Receptive Field Dilemma: Real-world HINs are too large for the $O(N^2)$ self-attention mechanism of a standard Transformer. Sampling small local neighborhoods loses "long-range dependencies"—the ability for a node to learn from distant but relevant parts of the graph.
Methodology: The PHGT Framework
PHGT (Poly-tokenized Heterogeneous Graph Transformer) addresses these issues through a three-stage pipeline that rethinks how graph data is "tokenized."
1. Structure Encoder
Before the Transformer even sees the data, PHGT uses a few layers of standard message-passing (like GCN or GAT). This "Structure Encoder" ensures that the initial node embeddings already contain information about the immediate local topology.
2. Poly-Tokenization
This is the core innovation. For every target node, the model creates a sequence of three types of tokens:
- Node Tokens: Embeddings of nodes in a sampled local subgraph.
- Semantic Tokens: PHGT identifies specific meta-path instances (e.g., a specific "Author-Paper-Author" chain) and aggregates them into a single token. This treats complex relationships as "first-class citizens" in the attention mechanism.
- Global Tokens: To see the "big picture," the model runs a fast heterogeneous clustering algorithm. Each cluster becomes a "Global Token," representing a summary of a distant region of the graph.
3. Transformer Block
These tokens are concatenated and fed into a standard Transformer. Because the global tokens provide a summary of the whole graph, the model achieves a "global receptive field" without needing to attend to every single node in the network.
Experimental Evaluation
The authors evaluated PHGT on four standard heterogeneous graph benchmarks from the Heterogeneous Graph Benchmark (HGB): DBLP & ACM (academic networks), IMDB (movie network), and Freebase (a massive knowledge graph).
Key Results and Insights
- Superior Accuracy: PHGT achieved the highest Micro-F1 scores across all four datasets, outperforming both message-passing HGNNs (like HAN and MAGNN) and previous graph transformers (like HINormer).
- Efficiency via Clustering: By using cluster-based global tokens, the model avoids the quadratic complexity of full-graph attention. In efficiency tests, PHGT was 7–11x faster than spectral-based graph coarsening methods.
- Scalability: While conventional graph transformers (like Graphormer) ran out of memory on graphs with more than 8,000 nodes, PHGT continued to run efficiently on much larger scales due to its tokenization strategy.
Conclusion
PHGT demonstrates that GNNs and Transformers are better together. The GNN-based structure encoder handles low-level connectivity, while the Transformer handles high-level reasoning through poly-tokenization. While the model currently relies on pre-defined meta-paths, its ability to capture both intricate local semantics and long-range global dependencies marks a significant step forward for heterogeneous graph representation learning.
Summary updated