Heterogeneous Graphs

Chapter 1: Formal Definition

A heterogeneous graph is a graph G = (V, E, τ, φ) where two type-mapping functions make it heterogeneous:

τ(v) maps each node to its node type from a set A of node type names. φ(e) maps each edge to its edge type from a set R of edge type names. When |A| = 1 and |R| = 1, we recover the standard homogeneous graph.

But the most useful concept for heterogeneous GNNs is the relation type. A relation type combines the source node type, the edge type, and the destination node type into a triplet:

For example, in the academic graph:

Each relation type r defines a distinct neighborhood. For a node v, its type-r neighbors are:

The key design choice in heterogeneous GNNs: each relation type r gets its own message-passing mechanism. What this mechanism looks like — a fixed matrix, learned attention, something else — is what separates RGCN from HGT from metapath approaches.

Chapter 2: Can We Just Add Features?

Before building something complicated, let's ask whether we even need a new architecture. Can we just encode type as a feature and use a standard GNN?

The simplest approach: assign each node type a one-hot vector. If there are 3 node types, Paper gets [1,0,0], Author gets [0,1,0], Venue gets [0,0,1]. Concatenate this to the node's feature vector. Run a standard GCN. Done?

Problem 1: Feature Dimension Mismatch

Different node types naturally have different feature dimensions. Authors might be represented by 128-dim name embeddings. Papers might have 768-dim BERT embeddings of their abstract. Venues might have 64-dim location features. You can't feed all of these through one weight matrix W ∈ ℝ^d×d — they're different shapes.

You could pad them all to the maximum dimension, but you'd be feeding zeros as features for most entries, which wastes capacity and misleads the model.

Problem 2: Different Relations Deserve Different Weights

Suppose you want to predict a paper's research topic. The citation structure tells you a lot — papers citing similar papers tend to be on similar topics. But the venue structure also helps — venues have their own topic focus. A single weight matrix W applies the same linear transformation to messages from both relations simultaneously. It can't learn "treat citation messages this way, venue messages that way."

Problem 3: Over-Squashing Gets Worse

When you add type features and collapse everything into one message-passing scheme, you're asking a single channel to carry both relational semantics AND content. The gradient signal for "learn what citations mean" competes with "learn what authorship means." Keeping them separate gives each relation a dedicated learning channel.

Chapter 3: RGCN: Relation Weights

In 2018, Schlichtkrull et al. proposed the Relational Graph Convolutional Network (RGCN). The core idea is elegantly simple: give each relation type its own weight matrix.

Recall standard GCN message passing for a node v:

One weight matrix W for all neighbors, regardless of edge type. RGCN changes this by making W depend on the relation type r:

Let's decode every piece:

What's Actually Happening

For each relation type r, RGCN does a mini-GCN: aggregate messages from r-type neighbors, transform with W_r. Then it sums up all these per-relation aggregations, adds the self-loop term, and applies a nonlinearity. Each W_r is free to learn a completely different linear map.

Data Flow: Concrete Example

Say node v is a Paper. Its relations are: (Author, writes, Paper), (Paper, cites, Paper), (Venue, published_in, Paper). At layer l, v's update is:

# h[v] shape: (d,) — current Paper embedding
# W_writes shape: (d_out, d_author) — transforms Author embeddings
# W_cites shape: (d_out, d_paper) — transforms Paper embeddings
# W_pub shape: (d_out, d_venue) — transforms Venue embeddings
# W_self shape: (d_out, d_paper) — transforms Paper self

msg_writes = mean([W_writes @ h[u] for u in N_writes(v)])
msg_cites  = mean([W_cites  @ h[u] for u in N_cites(v)])
msg_pub    = mean([W_pub    @ h[u] for u in N_pub(v)])
self_msg   = W_self @ h[v]

h_new[v] = relu(msg_writes + msg_cites + msg_pub + self_msg)

Each relation gets its own weight matrix. Each weight matrix can be a different shape (to handle different input feature dimensions). The outputs are all projected to the same d_out dimension so they can be summed.

Chapter 4: Basis Decomposition

RGCN is elegant. But it has a parameter count problem. Suppose you have R = 50 relation types (common in real knowledge graphs), d = 256 hidden dimensions, and L = 3 layers. Each layer needs R + 1 = 51 weight matrices of size d × d = 256 × 256. That's 51 × 65,536 = 3.3 million parameters per layer, or ~10 million parameters total.

For a large knowledge graph like Freebase, R can exceed 1,000. You'd need 1,000 × 256 × 256 = 65 million parameters per layer. This is way more than the number of training examples in many graph tasks, guaranteeing overfitting.

Solution: Basis Decomposition

Instead of letting each W_r be a fully free matrix, express it as a linear combination of shared basis matrices:

Here V₁, V₂, ..., V_B are B shared basis matrices (same shape as W_r). Each relation r gets its own coefficients a_r1, a_r2, ..., a_rB — just B scalars. The bases V_b are shared across ALL relations.

Parameter count comparison:

With B = 8 and R = 50, we cut parameters by 6×. With R = 1000, the savings are enormous: from 65M to ~524K + 8K ≈ 532K parameters.

Why Does This Work?

The intuition is that different relation types aren't completely unrelated — they all operate in the same feature space, and many share structural patterns. Authorship and citation are different, but both are "send information from one academic entity to another." The basis matrices capture shared structure; the coefficients a_rb capture what's unique to each relation.

Block Decomposition vs. Basis Decomposition

Chapter 5: HGT: Type-Aware Attention

RGCN assigns a weight matrix per relation, and every neighbor of the same relation type contributes equally (after normalization). But what if some author-to-paper relationships matter more than others? What if the model should learn to pay more attention to highly-cited co-authors?

The Heterogeneous Graph Transformer (HGT) (Hu et al., WWW 2020) answers this by combining the relation-type-specific processing of RGCN with the learned attention of GAT. For each edge (u→v) with relation r = (τ(u), φ(u,v), τ(v)), HGT computes:

Step 1: Type-Specific Q, K, V Projections

Unlike standard GAT (which uses a single shared W_Q), HGT uses different projection matrices for each node type. An Author node and a Paper node get projected differently before attention is computed. This handles the feature dimension mismatch problem from Chapter 2 — each node type can have a different input dimension.

Step 2: Relation-Dependent Attention Score

The matrix W^φ(u,v)_ATT depends on the edge type. So "how much paper v should attend to its writing authors" is computed differently from "how much paper v should attend to papers it cites." The edge type modulates the attention computation itself, not just the messages.

Step 3: Type-Aware Message Aggregation

Even the message transformation depends on edge type. The aggregated message is then passed through a layer norm and a linear projection back to the target node type's dimension.

Parameter Count

HGT's parameters scale with node types, not relation types. W_Q^τ, W_K^τ, W_V^τ, W_MSG^τ are per node type. W_ATT^φ is per edge type. With 3 node types and 4 edge types, you need 3 × 4 + 4 = 16 matrices — far fewer than the R relation types in RGCN.

class HGTLayer:
    def __init__(self, node_types, edge_types, d_in, d_out):
        # One Q, K, V per node type — handles feature dim mismatch
        self.W_Q = {t: Linear(d_in[t], d_out) for t in node_types}
        self.W_K = {t: Linear(d_in[t], d_out) for t in node_types}
        self.W_V = {t: Linear(d_in[t], d_out) for t in node_types}
        # One attention matrix per edge type
        self.W_ATT = {e: Linear(d_out, d_out, bias=False) for e in edge_types}
        # One message matrix per edge type
        self.W_MSG = {e: Linear(d_out, d_out) for e in edge_types}

    def forward(self, G, h):
        # For each node v, for each neighbor u via edge type e:
        for v in G.nodes:
            messages = []
            for u, e in G.in_edges(v, data='etype'):
                Q = self.W_Q[G.ntype[v]] @ h[v]   # query: target type
                K = self.W_K[G.ntype[u]] @ h[u]   # key: source type
                V = self.W_V[G.ntype[u]] @ h[u]   # value: source type
                score = Q.T @ self.W_ATT[e] @ K   # edge-type attention
                msg = self.W_MSG[e] @ V            # edge-type message
                messages.append((score, msg))
            h_new[v] = softmax_aggregate(messages)

Chapter 6: Metapaths

RGCN and HGT aggregate over direct neighbors, one hop at a time. But sometimes the most informative structure comes from longer patterns. Two researchers who both published at the same venue in the same year might be working on the same problem — but they're not directly connected in the graph.

A metapath is a sequence of relation types that defines a higher-order path pattern through the heterogeneous graph. Rather than "Author → Paper → Venue → Paper → Author," you name this whole pattern and traverse it explicitly.

Each metapath defines a different kind of "semantic similarity" between nodes. Walking the APVPA path from Author A finds all authors who published at any venue that A also published at — a way to discover researchers working in overlapping fields without direct collaboration.

Metapath-Based Aggregation

In the MAGNN (Metapath Aggregated Graph Neural Network) approach, for each chosen metapath P:

1. Find all metapath instances. These are actual paths in the graph following the metapath pattern. For APVPA starting from author u: enumerate all u → p1 → v → p2 → author_end paths.
2. Encode each instance. Aggregate the node features along the path (e.g., using attention over intermediate nodes).
3. Aggregate across instances. All instances of the same metapath connecting u to its metapath-neighbors are aggregated.
4. Aggregate across metapaths. Use attention to weight which metapaths matter most for the current task.

β_vP is the learned attention weight that node v assigns to metapath P. Different nodes can decide that different metapaths are more relevant to their classification.

Metapaths vs. Standard Multi-Hop GNN

A 2-layer GNN also aggregates 2-hop neighbors. The critical difference: metapaths are selective. A 2-layer GNN from an Author node aggregates over ALL 2-hop neighbors — other authors, papers of papers it cites, venues, institutions. A metapath-based approach only aggregates along semantically meaningful paths. The APVPA path ignores citation structure; the APCPA path ignores venue structure. You choose which semantic signals to model.

Chapter 7: RGCN Showcase

Here's RGCN running live on a small heterogeneous academic graph. Click any node to make it the target node — you'll see how messages from different relation types are aggregated with different weight matrices, and how turning relations on/off changes the resulting embedding.

This is the full RGCN computation in miniature: for each active relation type, aggregate neighbor messages → transform with W_r → sum → ReLU → new embedding. Watch how the embedding visualization changes when you activate/deactivate relation types.

Chapter 8: When Should You Use Heterogeneous GNNs?

You've now seen three approaches: RGCN (per-relation weight matrices), HGT (type-aware attention), and metapath methods. How do you decide which to use — or whether to bother with heterogeneous modeling at all?

The Core Decision: Do Types Carry Semantic Meaning?

Ask this question: Would a domain expert treat different node types differently, or are they interchangeable? If a biologist treats Genes, Proteins, and Diseases as fundamentally different entities with different feature spaces and interaction semantics, use heterogeneous GNNs. If the "types" are just arbitrary labels that don't change how nodes interact, a homogeneous GNN will do fine.

Choosing Among RGCN, HGT, and Metapaths

Real Applications

Microsoft Academic Graph: 100M+ papers, authors, venues, institutions. HGT was specifically designed and benchmarked on this graph. Tasks: predicting paper topics (node classification), predicting missing author-paper relationships (link prediction).

Drug repurposing: Knowledge graphs like Hetionet contain 47,000 nodes across 11 types and 2.2M edges across 24 relation types. RGCN with basis decomposition is the standard baseline for predicting which drugs treat which diseases.

E-commerce recommendation: Alibaba's product recommendation system models Users, Items, Queries, Categories, Brands as different node types. Type-specific message passing significantly outperforms homogeneous GNNs for click-through rate prediction.

Chapter 9: Connections

Heterogeneous GNNs don't exist in isolation. They sit at the intersection of several powerful ideas — some of which we've already covered, and some that come next.

Where This Came From

Where This Goes Next

Lecture 10: Knowledge Graphs. Knowledge graphs (KGs) are a special case of heterogeneous graphs where edges are facts: (head_entity, relation, tail_entity). RGCN is one of the standard baselines for KG embedding and completion. The next lecture focuses on KG-specific methods like TransE and RotatE that exploit the specific structure of triple-based reasoning.

Graph Transformers (Lec 8, previous lesson). HGT is a Graph Transformer applied to heterogeneous graphs. The type-specific Q, K, V projections are exactly the heterogeneous extension of the Graphormer idea: inject structural information (here: node type and edge type) into the attention computation. GPS could in principle be extended heterogeneously.

Scalability (Lec 11). Heterogeneous GNNs face the same mini-batching challenges as homogeneous GNNs, plus additional complexity: when you sample neighbors, you need to stratify sampling by relation type to avoid dropping rare relations entirely.

Key Papers

Related Lessons

"A graph is not just a structure — it is a vocabulary. Different edge types are different words. Using the same weight for every word is like reading a sentence where all words mean the same thing."
— paraphrased from the HGT paper motivation