Source-linked AI summary
Heterogeneous Graph Transformer
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Yizhou Sun
TL;DR
HGT addresses the difficulty of applying GNNs to heterogeneous, dynamic, and Web-scale graphs. It combines meta-relation-based attention, relative temporal encoding, and HGSampling, and consistently outperforms baseline models across large academic-graph tasks.
Problem
Most GNNs target homogeneous graphs, while heterogeneous graphs require representations for varied node and edge types, changing temporal structure, and Web-scale data.
Method
HGT uses meta-relation-dependent attention, relative temporal encoding, inductive timestamp assignment, and HGSampling for dynamic heterogeneous graph modeling and scalable training.
Results
HGT consistently outperforms state-of-the-art GNN baselines and dedicated heterogeneous models by 9–21% across downstream tasks on academic graphs.
Takeaways & Limitations
HGT captures heterogeneity and implicit meta-path importance while achieving better generalization with fewer resource demands than heterogeneous baselines.
Takeaways & Limitations
A baseline with a unique weight matrix for each relation could not be optimized under the experimental GPU-memory setting because it contained too many parameters.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
HGT addresses heterogeneity, temporal dynamics, and Web-scale scalability in heterogeneous graphs through type-aware attention, relative temporal encoding, and heterogeneous subgraph sampling. Experiments on academic graphs show consistent gains over existing GNN baselines and heterogeneous models.
- Heterogeneous graphs combine different node and edge types, as illustrated by OAG’s papers, authors, institutions, venues, and fields.
- Existing heterogeneous GNNs often require manually designed meta paths, domain knowledge, or approaches that do not scale to hundreds of millions of nodes and billions of relationships.
- HGT uses node- and edge-type dependent attention parameters based on meta relation triplets to maintain dedicated representations for heterogeneous interactions.
- Relative temporal encoding models structural dependencies across edges occurring at different times, including arbitrary, unseen, and future timestamps.
- HGSampling creates balanced, dense heterogeneous subgraphs for efficient mini-batch training on Web-scale graphs.
- 9–21% gains over state-of-the-art GNNs and dedicated heterogeneous models were observed across downstream tasks on OAG and domain-specific academic graphs.The OAG contains 179 million nodes and 2 billion edges spanning 1900–2019.
2 PRELIMINARIES AND RELATED WORK
The paper reviews heterogeneous graph and GNN foundations, then motivates HGT’s use of complete meta relations, implicit meta paths, temporal encoding, and scalable sampling. HGT extends prior heterogeneous GNNs by modeling richer relation context while controlling resource demands.
- 2.1 Heterogeneous Graph Mining: A heterogeneous graph is a typed directed graph whose nodes and edges may represent multiple kinds of entities and relations.
- 2.1 Heterogeneous Graph Mining: A meta relation records the source-node type, edge type, and target-node type as ⟨τ(s),ϕ(e),τ(t)⟩.
- 2.2 Graph Neural Networks: General GNNs extract information from source representations and aggregate neighborhood messages to update target-node representations.
- 2.3 Heterogeneous GNNs: Prior heterogeneous GNNs commonly parameterize weights using node type or edge type alone, limiting their use of heterogeneous graph properties.
- 2.3 Heterogeneous GNNs: HGT decomposes interactions and transformation matrices by complete meta relations, capturing shared and relation-specific patterns with equal or fewer parameters.
- 2.3 Heterogeneous GNNs: HGT automatically learns the importance of implicit meta paths, incorporates temporal information through relative temporal encoding, and supports Web-scale training through heterogeneous mini-batch sampling.
3 HETEROGENEOUS GRAPH TRANSFORMER
HGT models heterogeneous graphs by using meta-relation-dependent transformations throughout attention, message passing, and aggregation. It produces contextualized node representations while incorporating parameter sharing across heterogeneous relations.
- Overall architecture: HGT uses meta relations—source-node type, edge type, and target-node type—to parameterize heterogeneous mutual attention, message passing, and propagation.This design distinguishes operators for different relations while sharing parameters across their components.
- Overall architecture: HGT aggregates information from source nodes to target nodes through heterogeneous mutual attention, heterogeneous message passing, and target-specific aggregation.The architecture operates on linked node pairs in a sampled heterogeneous subgraph.
- Heterogeneous mutual attention: Unlike GAT’s shared weight matrix, HGT uses node-type-specific projections and edge-type-specific transformations to model differing feature distributions and semantic relations.The attention mechanism maps target nodes to queries and source nodes to keys before incorporating edge-type information.
- Message passing and aggregation: HGT computes attention over neighboring source nodes, then uses attention-weighted messages to aggregate information from neighbors with different feature distributions.The attention vectors are normalized across each target node’s neighbors and used as aggregation weights.
- Dynamic heterogeneous graphs: Relative Temporal Encoding preserves edges across timestamps and augments source representations using relative time gaps before HGT processing.This allows HGT to model temporal dependencies with arbitrary durations, including unseen and future timestamps.
4 WEB-SCALE HGT TRAINING
Web-scale heterogeneous GNN training requires sampling methods that avoid type imbalance while preserving informative subgraphs, alongside timestamp assignment for nodes without fixed times.
- 4.1 HGSampling: Full-batch GNN training is not scalable for Web-scale graphs because it computes every node representation at each layer.Existing sampling methods can produce subgraphs extremely imbalanced across node types when applied directly to heterogeneous graphs.
- 4.1 HGSampling: HGSampling addresses heterogeneous-graph sampling by targeting balanced node and edge types while keeping sampled subgraphs dense.These goals reduce information loss and sample variance during mini-batch training.
- 4.1 HGSampling: HGSampling maintains a separate budget for each node type and samples an equal number of nodes per type using importance sampling.Sampled nodes contribute their direct neighbors to type-specific budgets, with normalized degree used in sampling probabilities to reduce variance.
- 4.1 HGSampling: The algorithm reconstructs a sampled adjacency matrix after selecting nodes across relation-specific adjacency matrices.Its inputs include adjacency matrices for each ⟨source node type, edge type, target node type⟩ relation, output nodes, a per-type sample number, and sampling depth.
- 4.2 Inductive Timestamp Assignment: Inductive timestamp assignment gives plain nodes timestamps based on linked event nodes during subgraph sampling.Event nodes retain their own timestamps, while nodes without fixed times inherit timestamps from connected event nodes.
5 EVALUATION
Evaluation spans large heterogeneous academic graphs, multiple downstream tasks, and comparisons with homogeneous and heterogeneous GNN baselines. HGT consistently outperforms the baselines, while ablations and case studies examine its components and temporal modeling.
- Web-Scale Datasets: The evaluation uses OAG plus Computer Science and Medicine subgraphs, with the latter two containing tens of millions of nodes and hundreds of millions of edges.OAG contains more than 178 million nodes and 2.236 billion edges, with papers spanning 1900–2019.
- Tasks and Evaluation: HGT is evaluated on Paper–Field, Paper–Venue, and Author Disambiguation tasks using NDCG and MRR, with pre-2015 papers for training and 2016–2019 papers for testing.Models are trained five times, reporting mean and standard deviation of test performance.
- Experimental Results: HGT significantly and consistently outperforms all baselines on both metrics, tasks, and datasets.The comparisons include homogeneous GCN and GAT and heterogeneous RGCN, HetGNN, and HAN models.
- Experimental Results: 20%: HGT’s average improvement over GCN, GAT, RGCN, HetGNN, and HAN across four tasks and three large-scale datasets.HGT also has fewer parameters and comparable batch time relative to heterogeneous GNN baselines.
- Ablation Study: Removing heterogeneous weight parameterization reduces performance by 4%, while removing Relative Temporal Encoding produces a 2% drop.The ablation results support the contribution of both meta-relation parameterization and temporal encoding.
- Case Study: Temporal case studies show conference relationships changing from 2000 to 2020, including shifts involving WWW, KDD, and NeurIPS.The study reports that Relative Temporal Encoding captures temporal evolution in heterogeneous academic graphs.
6 CONCLUSION
HGT models Web-scale heterogeneous and dynamic graphs by combining type-aware interaction modeling, temporal encoding, and scalable sampling. Experiments on the Open Academic Graph support its effectiveness across downstream tasks, while graph generation and pretraining remain future directions.
- 6 CONCLUSION: HGT models Web-scale heterogeneous and dynamic graphs with type-aware interactions, relative temporal encoding, and heterogeneous mini-batch graph sampling.The meta relation decomposes interactions and transformation matrices; RTE incorporates temporal information, while HGSampling supports efficient scalable training.
- 6 CONCLUSION: Comprehensive Open Academic Graph experiments show HGT captures heterogeneity and outperforms state-of-the-art GNN baselines across various downstream tasks.
- 6 CONCLUSION: Future work will test whether HGT can generate heterogeneous graphs and support tasks with scarce labels through pretraining.Examples include predicting new papers and their titles.