Heterogeneous Graph Transformer

Ziniu Hu, Yuxiao Dong, Kuansan Wang, Yizhou Sun

Abstract

Recent years have witnessed the emerging success of graph neural networks (GNNs) for modeling structured data. However, most GNNs are designed for homogeneous graphs, in which all nodes and edges belong to the same types, making them infeasible to represent heterogeneous structures. We present the Heterogeneous Graph Transformer (HGT) architecture for modeling Web-scale heterogeneous graphs. To model heterogeneity, we design node- and edge-type dependent parameters to characterize the heterogeneous attention over each edge, empowering HGT to maintain dedicated representations for different types of nodes and edges. To handle dynamic heterogeneous graphs, we introduce the relative temporal encoding technique into HGT, which is able to capture the dynamic structural dependency with arbitrary durations. To handle Web-scale graph data, we design the heterogeneous mini-batch graph sampling algorithm—HGSampling—for efficient and scalable training. Extensive experiments on the Open Academic Graph of 179 million nodes and 2 billion edges show that the proposed HGT model consistently outperforms all the state-of-the-art GNN baselines by 9%–21% on various downstream tasks.

The Challenge of Heterogeneity

Most Graph Neural Networks (GNNs) are built for homogeneous graphs, where every node and every edge is treated as the same type. However, real-world data is inherently heterogeneous. Consider an academic network: it contains diverse entities like papers, authors, institutions, and venues, linked by various relationships such as "writes," "affiliates with," or "cites."

An example of a heterogeneous graph schema in the academic domain.

Existing solutions for these complex graphs face three major hurdles:

  1. Manual Design: They often rely on "meta-paths" (e.g., Author-Paper-Venue), which require expert domain knowledge to define.
  2. Static Nature: They ignore how relationships evolve over time.
  3. Scalability: Most models cannot handle "Web-scale" data containing hundreds of millions of nodes.

The HGT Architecture

The Heterogeneous Graph Transformer (HGT) addresses these issues through three key innovations integrated into its layer architecture.

The HGT layer architecture, featuring Heterogeneous Mutual Attention, Message Passing, and Target-Specific Aggregation.

1. Heterogeneous Mutual Attention

Instead of using a single weight matrix for all edges, HGT uses the "meta-relation" triplet—$\langle \text{source type, edge type, target type} \rangle$—to parameterize its attention mechanism. This allows the model to learn dedicated representations for different entity types while sharing parameters where appropriate (e.g., "first author" and "second author" relations can share knowledge about the "Author" type).

2. Relative Temporal Encoding (RTE)

To handle the dynamic nature of graphs, HGT introduces relative temporal encoding. It uses sinusoid functions to encode the time gap between nodes, allowing the model to capture temporal dependencies and generalize to future, unseen timestamps. This mechanism proves that time is a structural component; for instance, it can capture how the similarity between research fields converges over decades.

3. HGSampling for Scalability

To make training feasible on massive graphs, the authors developed HGSampling, a specialized mini-batch sampling algorithm. Unlike standard samplers that might ignore rare node types, HGSampling maintains separate "budgets" for each node type to ensure sampled sub-graphs are both balanced and dense.

Experimental Results

The model was evaluated using the Open Academic Graph (OAG), featuring 179 million nodes and 2 billion edges. This dataset is significantly more complex than standard GNN benchmarks like Cora or Pubmed.

  • Performance: HGT consistently outperformed state-of-the-art baselines (including GCN, GAT, RGCN, and HAN) by 9% to 21% across tasks like Paper-Field prediction and Author Disambiguation.
  • Ablation Studies: Removing heterogeneity-aware parameters caused a 4% performance drop, while removing temporal encoding caused a 2% drop, validating the importance of both components.
  • Implicit Meta-paths: By stacking multiple layers, HGT automatically learns "soft" meta-paths without human intervention, effectively informing a paper's representation through its venue and the fields of its authors.

Conclusion

HGT represents a significant step forward in scaling GNNs to real-world, multi-typed, and dynamic data. By treating heterogeneity and time as first-class citizens in the architecture, it achieves superior performance and scalability. Future work includes applying HGT to generative tasks and exploring large-scale pre-training strategies to further boost performance on low-resource tasks.

Summary updated

Abstract

Recent years have witnessed the emerging success of graph neural networks (GNNs) for modeling structured data. However, most GNNs are designed for homogeneous graphs, in which all nodes and edges belong to the same types, making them infeasible to represent heterogeneous structures. In this paper, we present the Heterogeneous Graph Transformer (HGT) architecture for modeling Web-scale heterogeneous graphs. To model heterogeneity, we design node- and edge-type dependent parameters to characterize the heterogeneous attention over each edge, empowering HGT to maintain dedicated representations for different types of nodes and edges. To handle dynamic heterogeneous graphs, we introduce the relative temporal encoding technique into HGT, which is able to capture the dynamic structural dependency with arbitrary durations. To handle Web-scale graph data, we design the heterogeneous mini-batch graph sampling algorithm---HGSampling---for efficient and scalable training. Extensive experiments on the Open Academic Graph of 179 million nodes and 2 billion edges show that the proposed HGT model consistently outperforms all the state-of-the-art GNN baselines by 9%--21% on various downstream tasks.
BibTeX
@inproceedings{hu2020heterogeneous,
  author = {Ziniu Hu and Yuxiao Dong and Kuansan Wang and Yizhou Sun},
  title = {{Heterogeneous Graph Transformer}},
  booktitle = {The Web Conference},
  year = {2020},
  doi = {10.1145/3366423.3380027},
}
Figure