Heterogeneous Graph Neural Networks

Node/edge types, HAN, HGT, meta-paths, knowledge graphs, when to model heterogeneity

Pinterest has Pin, Board, User, and Image nodes connected by Save, Click, Follow, and Similarity edges. A homogeneous GNN that ignores node and edge types aggregates all neighbor types together — a "Click" edge and a "Purchase" edge contribute identically to the target node's embedding. But a user purchasing an item is a fundamentally different signal than a user clicking it. Treating them the same discards the relational semantics that distinguish high-intent from low-intent interactions — often the most commercially valuable signals in the graph.

Heterogeneous GNNs model type information explicitly. RGCN uses relation-specific weight matrices: one W_r per relation type. With 25 relation types and embedding dimension 256, that is 25 × 256² = 1.6 million parameters just for relation weights — and rare relation types with under 1,000 training edges have insufficient gradient to learn their full matrix. This is the overparameterization problem.

HGT (Heterogeneous Graph Transformer) solves this with shared weights and small relation-specific modifiers. Type-specific key/query/value projections handle the (src_type, edge_type, dst_type) triplet with parameter growth O(|A| × d²) plus O(|R| × d) for relation modifiers — substantially better than RGCN's O(|R| × d²). HGT learns which relation triplets are informative end-to-end without manual meta-path specification.

NOT this. "You can encode type information as a feature instead of modeling it architecturally." Adding a one-hot type embedding to node or edge features and using a homogeneous GNN is a reasonable baseline. It works when relation types are numerous and sparse (100+ types with few examples each) and when you need a fast baseline. It fails when edge types carry fundamentally different semantic meaning — a purchase deserves different aggregation weights than a click, not just a different input feature to the same aggregation function. Architectural heterogeneity is not advanced; ignoring it is a lossy choice that should be made deliberately, not by default.

Key points

• Heterogeneous graph definition: G = (V, E, τ, φ) where τ: V → A maps nodes to types and φ: E → R maps edges to types. E-commerce example: A = {User, Item, Category, Brand}, R = {views, purchases, belongs_to, makes}. Each (src_type, edge_type, dst_type) triplet is a canonical edge type. PyTorch Geometric's HeteroData class represents each canonical type separately — different node types have different feature dimensionalities and different message-passing rules.
• RGCN (Relational GCN, Schlichtkrull et al., 2018): separate weight matrix W_r for each relation type r. Aggregation: h_v = σ(Σ_r Σ_{u∈N^r(v)} (1/c_{v,r}) W_r h_u). With |R| relation types and feature dimension d: |R| × d² parameters for relation weights alone. For 200 relation types and d=256: 200 × 65,536 = 13M parameters. Rare relation types with < 1,000 training edges have insufficient gradient to learn a full d×d matrix. Basis decomposition W_r = Σ_b a_{r,b} V_b with B shared basis matrices reduces parameters from O(|R|×d²) to O(B×d²) + O(|R|×B) — essential at scale.
• Meta-paths define semantic traversal routes through the heterogeneous graph. In an academic graph: Author→Paper→Author (APA, co-authorship), Author→Paper→Venue→Paper→Author (APVPA, same venue). Different meta-paths capture different semantic relationships between the same node pair. Meta-path-based methods (HAN) require domain experts to define which paths are semantically meaningful — this is a bottleneck that requires manual intervention when the domain changes.
• HAN (Heterogeneous Attention Network, Wang et al., 2019): two-level attention. Node-level: GAT-style attention aggregating information within each meta-path's neighborhood. Semantic-level: soft weighting of different meta-path-based embeddings — which meta-path is more informative for this node? Final embedding is a weighted sum across meta-paths. Limitation: meta-paths must be defined manually, cannot be discovered end-to-end, and require domain expertise that may not transfer to new heterogeneous graph problems.
• HGT (Heterogeneous Graph Transformer, Hu et al., 2020): relation-specific attention without meta-paths. Type-specific key/query/value projections for each (src_type, edge_type, dst_type) canonical triplet — a Transformer with relation-specific parameters. Learns which relation triplets are informative end-to-end without manual meta-path specification. Parameter growth is O(|A| × d²) for shared weights plus O(|R| × d) for small relation-specific modifiers — substantially better than RGCN's O(|R| × d²). The recommended default for new heterogeneous graph problems.
• Knowledge graph completion with GNNs: KG-specific GNN-based methods (RGCN + DistMult decoder) aggregate neighborhood context to produce rich entity embeddings before scoring (head, relation, tail) triples. This outperforms pure embedding methods (TransE, RotatE) when entities have high-degree neighborhoods with informative context — the GNN incorporates entity context that TransE-style methods ignore. Underperforms on sparse KGs where most entities have few connections and neighborhood aggregation adds noise rather than signal.
• When to model heterogeneity explicitly vs homogenize: model explicitly when edge types carry fundamentally different semantic meaning (click vs purchase), when sufficient training data exists per relation type for separate parameters, or when the downstream task requires distinguishing relation types. Homogenize when relation types are too numerous and rare (> 100 types, < 1,000 edges each), when type information can be encoded as edge features (one-hot type embedding added to edge features), or when a fast baseline is needed.
• Cold-start for rare node types: a new node type with no trained type-specific parameters cannot produce meaningful embeddings through type-specific projection matrices. Solutions: transfer learning from the most similar existing type (initialize new type's parameters from that type's parameters); feature-based fallback (rely entirely on content features rather than structural parameters for the new type); continual learning with frozen shared weights and fine-tuned type-specific parameters only.

Recap

• Heterogeneous graphs are the production default: click vs purchase edges carry different semantics — homogenizing discards the commercial signal.
• RGCN = one $W_r$ per relation: O(|R|×d²) params. 200 types, d=256 → 13M params; rare relations (<1K edges) can't learn a full matrix.
• Basis decomposition is non-optional for RGCN at scale: $W_r = \sum_b a_{r,b}V_b$ → ~12× fewer params at d=256, B=40.
• Meta-paths (APA, APVPA) define semantic routes but need manual expert definition — a bottleneck.
• HAN: two-level attention (node-level within meta-path + semantic-level across meta-paths); still needs manual meta-paths.
• HGT is the recommended default: relation-specific attention, shared weights + small modifiers → O(|A|×d²)+O(|R|×d), no meta-paths.
• Homogenize deliberately when types are numerous+rare or encodable as edge features — not by default.

Check your understanding