Heterogeneous Graph Transformer

Ziniu Hu, Yuxiao Dong, Kuansan Wang, Yizhou Sun

TL;DR

The Heterogeneous Graph Transformer (HGT) is a novel GNN architecture designed to handle massive, dynamic, and multi-typed graphs. By using type-dependent attention and relative temporal encoding, HGT outperforms state-of-the-art models by up to 21% on billion-edge datasets like the Open Academic Graph.

What Problem Does This Paper Address?

Most Graph Neural Networks (GNNs) are built for homogeneous graphs, where every node (e.g., a person) and every edge (e.g., a friendship) is treated as the same type. However, the real world is messy and heterogeneous. Consider an academic network: it contains papers, authors, institutions, and venues, all linked by different relationships like "writes," "affiliates with," or "cites."

Existing solutions for these complex graphs face three major hurdles:

  1. Manual Design: They often require "meta-paths" (e.g., Author-Paper-Venue), which need expert domain knowledge to define.
  2. Static Nature: They ignore how relationships evolve over time (e.g., the "hot topics" of a conference in 1990 are different from those in 2020).
  3. Scalability: Most models break down when faced with "Web-scale" data containing hundreds of millions of nodes.

Methods

The authors introduce the Heterogeneous Graph Transformer (HGT) to tackle these issues through three key innovations:

  • 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 it makes sense (e.g., "first author" and "second author" relations can share knowledge about the "Author" type).
  • Relative Temporal Encoding (RTE): To handle the dynamic nature of graphs, HGT borrows the concept of positional encoding from the original Transformer. It uses sinusoid functions to encode the time gap between nodes. This allows the model to capture temporal dependencies and even generalize to future, unseen timestamps.
  • HGSampling: To make training feasible on massive graphs, the authors developed a specialized mini-batch sampling algorithm. Unlike standard samplers that might accidentally ignore rare node types, HGSampling maintains separate "budgets" for each node type to ensure the sampled sub-graphs are both balanced and dense.

Datasets

The model was pushed to its limits using the Open Academic Graph (OAG), which features:

  • 179 million nodes and 2 billion edges.
  • Two domain-specific subsets: Computer Science (CS) and Medicine (Med).
  • Tasks included Paper-Field prediction, Paper-Venue prediction, and Author Disambiguation.

This dataset is significantly larger and more complex than the "toy" benchmarks (like Cora or Pubmed) often used in GNN research.

Key Insights and Ideas

  • Implicit Meta-paths: HGT doesn't need humans to define meta-paths. By stacking multiple layers, the model automatically learns "soft" meta-paths. For example, it can figure out that a paper's representation is best informed by the venue it was published in and the fields of its authors.
  • Parameter Efficiency: By decomposing the interaction into source, edge, and target components, HGT achieves higher modeling capacity with fewer parameters than some dedicated heterogeneous baselines.
  • Time as a Feature: The RTE mechanism proves that time isn't just a metadata tag; it's a structural component. The model successfully captured how the "similarity" between conferences like KDD and NeurIPS has increased over the last two decades as data mining and machine learning converged.

Key Results

  • Superior Performance: HGT consistently outperformed all baselines (including GCN, GAT, RGCN, and HAN) by 9% to 21% across various tasks.
  • Ablation Success: Removing the heterogeneity-aware parameters caused a 4% performance drop, while removing the temporal encoding caused a 2% drop, proving both components are vital.
  • Scalability: HGT is one of the few models capable of training on a billion-edge graph while maintaining a comparable "batch time" to much simpler models.

Limitations and Future Work

While HGT excels at representation learning (understanding the graph), the authors note it hasn't yet been applied to generative tasks, such as predicting the title of a future paper based on a citation graph.

The authors also suggest that pre-training HGT on massive unlabeled graphs could significantly boost performance on "low-resource" tasks where labeled data is scarce—a strategy that has already revolutionized Natural Language Processing.

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 it 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 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 dataset and source code of HGT are publicly available at https://github.com/acbull/pyHGT.
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},
}

Loading related content...

Figure