Heterogeneous Graphs

Slide 5 sets the goal. Until now every graph had one edge type: all edges meant the same thing. Many real graphs have several node types and several edge types; these are called heterogeneous graphs. The lecture covers three ways to learn on them: Relational GCNs (R-GCN), the design space for heterogeneous GNNs, and the Heterogeneous Graph Transformer (HGT).

Slides 6–8 build one small example step by step. The same drawing of about ten nodes is coloured in two ways:

• Slide 6, 2 node types: red nodes are papers (type A), blue nodes are authors (type B).
• Slide 7, 2 edge types: yellow edges are Like, green edges are Cite.
• Slide 8 combines both: a graph can have multiple types of nodes and edges at the same time.

Slide 9 counts what this gives. An edge connects a start node and an end node, each of which can be a paper or an author, and the edge itself can be Like or Cite. So there are \(2\times 2\times 2 = 8\) possible relation types:

(Paper, Cite, Paper), (Paper, Like, Paper), (Paper, Cite, Author), (Paper, Like, Author), (Author, Cite, Author), (Author, Like, Author), (Author, Cite, Paper), (Author, Like, Paper).

A relation type is the triple (node_start, edge, node_end). We use the relation type to describe an edge, rather than only the edge type, because the relation type better captures the interaction between nodes and edges. "Cite" from a paper to a paper is a different act from "Cite" from an author to a paper, even though the edge label is the same.

Check yourself: with \(T\) node types and \(E\) edge types, how many relation types are possible? show answer

\(T\cdot E\cdot T\). Real graphs use only some of them.

Slide 10 gives the formal definition. A heterogeneous graph is

\[ G=(V,E,\tau,\phi) \]

• Nodes with node types: \(v\in V\); the node type of \(v\) is \(\tau(v)\).
• Edges with edge types: \((u,v)\in E\) (an edge is described as a pair of nodes); the edge type of \((u,v)\) is \(\phi(u,v)\).
• The relation type of edge \((u,v)\) is the tuple \(r(u,v)=\big(\tau(u),\ \phi(u,v),\ \tau(v)\big)\).

Other definitions of heterogeneous graphs exist, but they all describe graphs with node types and edge types.

Slides 11–13 show that many real graphs are heterogeneous:

• Slide 11, biomedical knowledge graphs: example node Migraine; example relation (fulvestrant, Treats, Breast Neoplasms); example node type Protein; example edge type Causes. The figure is a dense graph with nodes coloured by type (drug, disease, protein, …).
• Slide 11, event graphs: example node SFO; example relation (UA689, Origin, LAX); node type Flight; edge type Destination.
• Slide 12, e-commerce graph: node types User, Item, Query, Location, …; edge types Purchase, Visit, Guide, Search, …. The figure shows users on the left, items in the middle (shoes, bags) and queries on the right. Important: different node types can have different feature spaces (a user profile vector and an item image vector need not have the same length or meaning).
• Slide 13, academic graph: node types Author, Paper, Venue, Field, …; edge types Publish, Cite, …. The figure links two authors to venues (KDD, ICML, AAAI) and venues to fields (Mining, Vision, Machine Learning). A standard benchmark comes from the Microsoft Academic Graph.

Can two nodes be linked by several edges of different types? Yes. A heterogeneous graph is in general a multigraph: an author can both "write" and "cite" the same paper, and each edge is handled by its own relation.

Slide 14 makes an important observation: we could also treat node and edge types as features. For example, append a one-hot indicator: feature [1, 0] to each author node and [0, 1] to each paper node. In the same way, give edges a one-hot edge-type feature. Then the heterogeneous graph reduces to a standard graph, and any ordinary GNN can run on it.

So when do we need a heterogeneous graph? Slide 15 gives two cases:

1. Different node or edge types have different shapes of features. An author node has a 4-dim feature, a paper node a 5-dim feature. One shared weight matrix cannot take inputs of different sizes.
2. Different relation types represent different types of interactions. (English, translate, French) and (English, translate, Chinese) need different models: the transformation of a message should depend on the relation, not just be shifted by an extra feature bit.

There are many ways to convert a heterogeneous graph into a standard (homogeneous) graph, so the choice is a modelling decision.

Slide 16 states the trade-off. A heterogeneous graph is a more expressive representation: it captures different types of interactions between entities. But it also comes with costs: it is more expensive (computation, storage) and has a more complex implementation.

Slide 18 recalls the GCN layer (Kipf and Welling, ICLR 2017):

\[ \mathbf{h}_v^{(l)}=\sigma\Big(\mathbf{W}^{(l)}\sum_{u\in N(v)}\frac{\mathbf{h}_u^{(l-1)}}{|N(v)|}\Big). \]

As message + aggregation: the message of neighbour \(u\) is \(\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}/|N(v)|\); the aggregation is the sum over \(u\in N(v)\) followed by \(\sigma\).

Slides 19–20 extend GCN step by step. Start with a directed graph with one relation. The input graph has six nodes A–F; A is the target node. How do we update A's representation? Answer (slide 20): only pass messages along the direction of edges. The computation graph of A therefore uses only A's in-neighbours (B, C, D), then their in-neighbours, and so on. The figure shows this tree: A at the left, boxes (neural networks) in the middle, and the in-neighbours of in-neighbours on the right.

Slide 21 asks: what if the graph has multiple relation types? The graph now has coloured, directed edges: B→A and D→A with relation \(r_1\), C→A with \(r_2\), C→B and E→C with \(r_3\), F→C with \(r_2\), F→E with \(r_1\).

Slide 22 gives the idea: use different neural network weights for different relation types: weights \(\mathbf{W}_{r_1}\) for \(r_1\), \(\mathbf{W}_{r_2}\) for \(r_2\), \(\mathbf{W}_{r_3}\) for \(r_3\). Slide 23 draws the resulting computation graph of A: each edge in the tree passes through the box with the colour of its relation, so a message coming over an \(r_2\) edge is transformed by \(\mathbf{W}_{r_2}\), and so on; then A aggregates.

Intuition: in ordinary GCN, every neighbour "speaks the same language". In R-GCN, each relation is a different channel with its own translator \(\mathbf{W}_r\). A citation and an authorship can now change A's embedding in different directions.

Slide 24 adds a self-loop to GCN, so a node keeps its own information:

\[ \mathbf{h}_v^{(l)}=\sigma\Big(\sum_{u\in N(v)}\mathbf{W}^{(l)}\frac{\mathbf{h}_u^{(l-1)}}{|N(v)|}+\mathbf{W}^{(l)}\mathbf{h}_v^{(l-1)}\Big). \]

Slide 25: now introduce a set of neural networks, one per relation type: a weight for rel_1, …, a weight for rel_N, plus a weight for the self-loop. The figure shows each weight acting on the star of neighbours that use that relation.

Slide 26 gives the definition of the Relational GCN:

\[ \mathbf{h}_v^{(l+1)}=\sigma\Big(\sum_{r\in R}\ \sum_{u\in N_v^r}\frac{1}{c_{v,r}}\mathbf{W}_r^{(l)}\mathbf{h}_u^{(l)}+\mathbf{W}_0^{(l)}\mathbf{h}_v^{(l)}\Big),\qquad c_{v,r}=|N_v^r|. \]

Here \(R\) is the set of relations, \(N_v^r\) the neighbours of \(v\) under relation \(r\), and \(c_{v,r}\) the node degree within the relation. Written as message + aggregation:

• Message from each neighbour of a given relation: \(\mathbf{m}_{u,r}^{(l)}=\frac{1}{c_{v,r}}\mathbf{W}_r^{(l)}\mathbf{h}_u^{(l)}\).
• Self-loop message: \(\mathbf{m}_v^{(l)}=\mathbf{W}_0^{(l)}\mathbf{h}_v^{(l)}\).
• Aggregation: sum over messages from neighbours and the self-loop, then apply the activation: \(\mathbf{h}_v^{(l+1)}=\sigma\big(\mathrm{Sum}(\{\mathbf{m}_{u,r}^{(l)},u\in N(v)\}\cup\{\mathbf{m}_v^{(l)}\})\big)\).

Why normalise per relation, not by total degree? If node \(v\) has 100 "cites" neighbours and 2 "written-by" neighbours, a total-degree average would drown the two authors. Normalising each relation separately gives each relation channel its own averaged voice, and then the channels are added.

Check yourself: if there is only one relation and \(\mathbf{W}_0=\mathbf{W}_r\), what does R-GCN become? show answer

GCN with a self-loop on a directed graph, mean over in-neighbours.

Slide 27 points at the cost. Each relation has \(L\) matrices \(\mathbf{W}_r^{(1)},\mathbf{W}_r^{(2)},\dots,\mathbf{W}_r^{(L)}\), and each \(\mathbf{W}_r^{(l)}\) has size \(d^{(l+1)}\times d^{(l)}\), where \(d^{(l)}\) is the hidden dimension in layer \(l\). So the number of parameters grows rapidly with the number of relations. Knowledge graphs can have thousands of relations, and many relations have few edges, so overfitting becomes an issue. Two methods regularise \(\mathbf{W}_r^{(l)}\):

(1) Block-diagonal matrices (slide 28). Key insight: make the weights sparse. Use a block-diagonal \(\mathbf{W}_r\): the figure shows a square matrix with a few small dense blocks on the diagonal and zeros elsewhere. With \(B\) blocks, the parameter count drops from

\[ d^{(l+1)}\times d^{(l)}\quad\text{to}\quad B\times\frac{d^{(l+1)}}{B}\times\frac{d^{(l)}}{B}. \]

Limitation: only nearby neurons/dimensions can interact through \(\mathbf{W}\). Dimension 1 can never influence dimension \(d\) in one layer.

(2) Basis / dictionary learning (slide 29). Key insight: share weights across different relations. Represent each relation's matrix as a linear combination of basis transformations:

\[ \mathbf{W}_r=\sum_{b=1}^{B}a_{rb}\cdot\mathbf{V}_b, \]

where the basis matrices \(\mathbf{V}_b\) are shared across all relations and \(a_{rb}\) is the importance weight of matrix \(\mathbf{V}_b\) for relation \(r\). Now each relation only needs to learn \(\{a_{rb}\}_{b=1}^{B}\), which is \(B\) scalars.

Intuition: the \(\mathbf{V}_b\) are a small vocabulary of "basic transformations", and each relation is a recipe that mixes them. Rare relations borrow statistical strength from frequent ones, because they share the same \(\mathbf{V}_b\).

Slide 30, entity/node classification. Goal: predict the label of a given node. R-GCN uses the representation of the final layer. If we predict the class of node A from \(k\) classes, take the final layer (prediction head) \(\mathbf{h}_A^{(L)}\in\mathbb{R}^k\); each entry of \(\mathbf{h}_A^{(L)}\) represents the probability of that class (in practice, after a softmax).

Slide 31, link prediction: make predictions using pairs of node embeddings, \(\hat{y}_{uv}=f(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)})\). What are the options for \(f\)? Slide 32 recalls the simplest one, the dot product \(\hat{y}_{uv}=(\mathbf{h}_u^{(L)})^\top\mathbf{h}_v^{(L)}\). It only applies to 1-way prediction: it predicts whether an edge exists, but it cannot say which relation the edge has.

Slide 33 recalls the transductive link-prediction split from earlier lectures. The figure shows one 5-node graph whose edges are split into four groups:

1. At training time: use training message edges to predict training supervision edges.
2. At validation time: use training message edges and training supervision edges to predict validation edges.
3. At test time: use training message, training supervision and validation edges to predict test edges.

Slide 34 adds relations. Every edge also has a relation type, and this is independent of the 4 categories. In a heterogeneous graph, the homogeneous graph formed by each single relation is split into the 4 categories on its own: training message / training supervision / validation / test edges for \(r_1\), …, the same for \(r_n\). Then the pieces are merged: all training message edges of all relations form the training message set, and so on. This guarantees that every relation, even a rare one, appears in every split.

Why split per relation? A random split over all edges could, by chance, put almost all edges of a rare relation into the test set, so the model would never learn it.

The running graph (slides 35–42) is the six-node graph from slide 21 plus an \(r_3\) edge from E to A. Slide 35 assumes \((E,r_3,A)\) is the training supervision edge and all other edges are training message edges. Use R-GCN to score \((E,r_3,A)\):

• Take the final-layer embeddings \(\mathbf{h}_E^{(L)}\) and \(\mathbf{h}_A^{(L)}\in\mathbb{R}^d\).
• Use a relation-specific score function \(f_r:\mathbb{R}^d\times\mathbb{R}^d\to\mathbb{R}\). One example: \(f_{r_3}(\mathbf{h}_E,\mathbf{h}_A)=\mathbf{h}_E^\top\mathbf{W}_{r_3}\mathbf{h}_A\), with \(\mathbf{W}_{r_3}\in\mathbb{R}^{d\times d}\).

The bilinear form with a matrix per relation solves the "1-way" problem of the dot product: each relation has its own notion of compatibility.

Slides 36–37 give the training procedure:

1. Use R-GCN to score the training supervision edge \((E,r_3,A)\).
2. Create a negative edge by perturbing the supervision edge: corrupt the tail of \((E,r_3,A)\), e.g. \((E,r_3,B)\) or \((E,r_3,D)\). Note: negative edges must not belong to the training message edges or training supervision edges. For example, \((E,r_3,C)\) is not a negative edge, because it is a real message edge.
3. Use the GNN model to score the negative edge.
4. Optimise a standard cross-entropy loss (as in Lecture 6):

\[ \ell=-\log\sigma\big(f_{r_3}(h_E,h_A)\big)-\log\Big(1-\sigma\big(f_{r_3}(h_E,h_B)\big)\Big), \]

where \(\sigma\) is the sigmoid. The first term maximises the score of the training supervision edge; the second minimises the score of the negative edge.

Slide 38 explains evaluation at validation time (test time is the same). We want to predict the validation edge \((E,r_3,D)\) (dashed in the figure). At validation time, the training message edges and training supervision edges are all existing edges (solid lines). Intuition: the score of \((E,r_3,D)\) should be higher than the score of every \((E,r_3,v)\) that is not in the training message or supervision edges, e.g. \((E,r_3,B)\).

Slide 39 lists the steps:

1. Calculate the score of \((E,r_3,D)\).
2. Calculate the score of all the negative edges \(\{(E,r_3,v)\mid v\in\{B,F\}\}\). A and C are excluded, since \((E,r_3,A)\) and \((E,r_3,C)\) belong to training message and supervision edges.
3. Obtain the ranking \(RK\) of \((E,r_3,D)\) among these scores.
4. Calculate the metrics:
   • Hits@k \(=\mathbb{1}[RK\le k]\). Higher is better.
   • Reciprocal rank \(=1/RK\). Higher is better.

Slides 40–42 work through three outcomes, listing the three scores from highest to lowest:

• Slide 40: order D, B, F. \(RK=1\), Hits@2 = 1, reciprocal rank \(=1/1\).
• Slide 41: order B, D, F. \(RK=2\), Hits@2 = 1, reciprocal rank \(=1/2\).
• Slide 42: order B, F, D. \(RK=3\), Hits@2 = 0, reciprocal rank \(=1/3\).

Averaging the reciprocal rank over all validation edges gives the mean reciprocal rank (MRR); averaging Hits@k gives the fraction of validation edges ranked in the top \(k\).

Why rank instead of classify? In a real graph almost all pairs are non-edges, so accuracy is meaningless. Ranking asks the practical question: "if I show the top \(k\) candidates, is the true one among them?" Hits@k is coarse (it ignores where inside the top \(k\)); MRR is smooth but dominated by the top positions.

Excluding known edges from the candidate list is called the filtered setting. Without it, a model would be punished for ranking another true edge, such as \((E,r_3,A)\), above \((E,r_3,D)\).

Slides 43–46 present a standard benchmark, ogbn-mag, built from the Microsoft Academic Graph (MAG) [Wang et al., Quantitative Science Studies 2020].

• Slide 43, four types of entities: papers (736k nodes), authors (1.1m nodes), institutions (9k nodes), fields of study (60k nodes).
• Slide 44, four directed relations: an author is "affiliated with" an institution; an author "writes" a paper; a paper "cites" a paper; a paper "has a topic of" a field of study. The schema figure shows the four vertex types with these edges; the paper vertex carries properties (features, year, label).
• Slide 45, prediction task: each paper has a 128-dimensional word2vec feature vector. Given the content, references, authors and author affiliations, predict the venue of each paper. This is a 349-class classification problem, since 349 venues are considered. The split is time-based: training papers were published before 2018, test papers after 2018.

Slide 46 shows the leaderboard rows. The SOTA method at rank 1, SeHGNN (with ComplEx embeddings), has test accuracy 0.5719 ± 0.0012 and validation accuracy 0.5917 ± 0.0009 with 8,371,231 parameters. An R-GCN baseline (NeighborSampling with R-GCN aggregation, rank 21) has test accuracy 0.4678 ± 0.0067 and validation accuracy 0.4761 ± 0.0068 with 154,366,772 parameters. SeHGNN combines ComplEx knowledge-graph embeddings (next lecture) with a simplified GCN.

Notice the parameter counts: the R-GCN baseline uses about 18 times more parameters and is about 10 accuracy points worse. Much of R-GCN's size comes from per-relation weights and per-node embeddings.

Slide 47 summarises R-GCN:

• Relational GCN is a graph neural network for heterogeneous graphs.
• It can perform entity classification as well as link prediction.
• The ideas extend easily into RGNN variants: RGraphSAGE, RGIN, RGAT, etc. (keep the per-relation weights, change the aggregator).
• Benchmark: ogbn-mag, predicting paper venues.

Why a time-based split? It mimics the real use case (predict the venue of new papers from old data) and is harder than a random split, because topics and venues drift over time.

Slide 49 asks how to extend the general GNN design space (from Lectures 4–5) to heterogeneous graphs. Recall its five parts: (1) message, (2) aggregation, (3) layer connectivity, (4) graph augmentation, (5) learning objective. The figure shows two stacked GNN layers, each with message and aggregation.

(1) Message. Slide 50 recalls the homogeneous version: message function \(\mathbf{m}_u^{(l)}=\mathrm{MSG}^{(l)}(\mathbf{h}_u^{(l-1)})\); each node creates a message that will be sent to other nodes later; example: a linear layer \(\mathbf{m}_u^{(l)}=\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}\).

Slide 51, heterogeneous message computation. Observation: a node can receive multiple types of messages, and the number of message types equals the number of relation types. Idea: create a different message function for each relation type:

\[ \mathbf{m}_u^{(l)}=\mathrm{MSG}_r^{(l)}\big(\mathbf{h}_u^{(l-1)}\big),\qquad r=(u,e,v), \]

where \(r\) is the relation between the node \(u\) that sends the message, the edge type \(e\), and the node \(v\) that receives it. Example: a linear layer \(\mathbf{m}_u^{(l)}=\mathbf{W}_r^{(l)}\mathbf{h}_u^{(l-1)}\).

(2) Aggregation. Slide 52 recalls: each node aggregates the messages from its neighbours, \(\mathbf{h}_v^{(l)}=\mathrm{AGG}^{(l)}(\{\mathbf{m}_u^{(l)},u\in N(v)\})\), e.g. Sum, Mean or Max; for example \(\mathbf{h}_v^{(l)}=\mathrm{Sum}(\{\mathbf{m}_u^{(l)},u\in N(v)\})\).

Slide 53, heterogeneous aggregation. Observation: each node can receive multiple types of messages, and several neighbours can belong to each message type. Idea: a 2-stage aggregation:

\[ \mathbf{h}_v^{(l)}=\mathrm{AGG}_{all}^{(l)}\Big(\mathrm{AGG}_r^{(l)}\big(\{\mathbf{m}_u^{(l)},u\in N_r(v)\}\big)\Big). \]

• Within each message type, aggregate the messages that belong to that relation type with \(\mathrm{AGG}_r^{(l)}\).
• Then aggregate across the relation types with \(\mathrm{AGG}_{all}^{(l)}\).
• Example: \(\mathbf{h}_v^{(l)}=\mathrm{Concat}\big(\mathrm{Sum}(\{\mathbf{m}_u^{(l)},u\in N_r(v)\})\big)\): sum within each relation, concatenate across relations.

R-GCN is one point in this space: linear per-relation messages, mean within each relation (via \(1/c_{v,r}\)), sum across relations.

(3) Layer connectivity. Slide 54 recalls: add skip connections and pre/post-process layers. The figure stacks MLP layers (pre-process), GNN layers (with a skip connection) and MLP layers (post-process). Pre-processing layers matter when encoding node features is necessary, e.g. when nodes represent images or text. Post-processing layers matter when reasoning or transformation over node embeddings is needed, e.g. graph classification or knowledge graphs. In practice, adding these layers works great.

Slide 55, heterogeneous pre/post-process layers: use MLP layers per node type. Since the output of a GNN is node embeddings, \(\mathbf{h}_v^{(l)}=\mathrm{MLP}_{T(v)}(\mathbf{h}_v^{(l)})\), where \(T(v)\) is the type of node \(v\). This is exactly how different feature shapes (slide 15) are handled: a 4-dim author vector and a 5-dim paper vector go through their own pre-process MLPs into one common hidden size. Other successful designs are also encouraged: skip connections, batch/layer normalisation, ….

(4) Graph manipulation. Slide 56 recalls: if the input graph lacks features, use feature augmentation. For structure: if the graph is too sparse, add virtual nodes or edges; if too dense, sample neighbours during message passing; if too large, sample subgraphs to compute embeddings (covered later in "Scaling up GNNs").

Slide 57, heterogeneous version. Feature manipulation: two common options, compute graph statistics (e.g. node degree) within each relation type, or across the full graph (ignoring relation types). Structure manipulation: neighbour and subgraph sampling are also common; two options again, sample within each relation type (this ensures neighbours of every type are covered) or sample across the full graph.

(5) Prediction heads. Slide 58 recalls the homogeneous heads:

• Node level: \(\hat{y}_v=\mathrm{Head}_{node}(\mathbf{h}_v^{(L)})=\mathbf{W}^{(H)}\mathbf{h}_v^{(L)}\).
• Edge level: \(\hat{y}_{uv}=\mathrm{Head}_{edge}(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)})=\mathrm{Linear}(\mathrm{Concat}(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)}))\).
• Graph level: \(\hat{y}_G=\mathrm{Head}_{graph}(\{\mathbf{h}_v^{(L)}\in\mathbb{R}^d,\forall v\in G\})\).

Slide 59 makes each one type-aware:

• Node level, one head per node type: \(\hat{y}_v=\mathrm{Head}_{node,T(v)}(\mathbf{h}_v^{(L)})=\mathbf{W}_{T(v)}^{(H)}\mathbf{h}_v^{(L)}\).
• Edge level, one head per relation: \(\hat{y}_{uv}=\mathrm{Head}_{edge,r}(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)})=\mathrm{Linear}_r(\mathrm{Concat}(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)}))\).
• Graph level: pool each node type separately, then aggregate: \(\hat{y}_G=\mathrm{AGG}\big(\mathrm{Head}_{graph,i}(\{\mathbf{h}_v^{(L)}\in\mathbb{R}^d,\forall T(v)=i\})\big)\).

Check yourself: why pool each node type separately at graph level? show answer

A graph with 1,000 papers and 3 authors would otherwise have its author signal averaged away.

Slide 61 recalls Graph Attention Networks (GAT):

\[ \mathbf{h}_v^{(l)}=\sigma\Big(\sum_{u\in N(v)}\alpha_{vu}\mathbf{W}^{(l)}\mathbf{h}_u^{(l-1)}\Big). \]

The \(\alpha_{vu}\) are attention weights: not all of a node's neighbours are equally important. Attention is inspired by cognitive attention: \(\alpha_{vu}\) focuses on the important parts of the input and fades out the rest; the network should devote more computing power to that small but important part. Question: can we adapt GAT for heterogeneous graphs?

Slide 62: HGT uses scaled dot-product attention, proposed in the Transformer:

\[ \mathrm{Attention}(Q,K,V)=\mathrm{softmax}\Big(\frac{QK^\top}{\sqrt{d_k}}\Big)V, \]

with query \(Q\), key \(K\), value \(V\), each of shape (batch_size, dim). They are obtained by linear layers on the input: \(Q=\text{Q\_Linear}(X)\), \(K=\text{K\_Linear}(X)\), \(V=\text{V\_Linear}(X)\). The diagram shows the pipeline MatMul → Scale → Mask (optional) → SoftMax → MatMul.

Slide 63 [Hu et al., WWW 2020] recalls GAT on a homogeneous graph in this notation. \(H^{(l)}\) is the \(l\)-th layer representation, and for target node \(t\):

\[ H^{(l)}[t]\leftarrow\underset{\forall s\in N(t),\,\forall e\in E(s,t)}{\mathrm{Aggregate}}\big(\mathrm{Attention}(s,t)\cdot\mathrm{Message}(s)\big). \]

The figure shows source nodes \(s_1,\dots\) around target \(t\). The question in red: how do we take the relation type (node_s, edge, node_e) into the attention computation?

Slide 64 writes the (homogeneous) mutual attention as Transformer heads: for head \(i\),

\[ \text{ATT-head}^i(s,t)=\big(K^i(s)\,Q^i(t)^\top\big),\quad K^i(s)=\text{K-Linear}^i\big(H^{(l-1)}[s]\big),\quad Q^i(t)=\text{Q-Linear}^i\big(H^{(l-1)}[t]\big). \]

This is a set of neural networks for the attention score of each edge: the source is projected to a key, the target to a query, and their dot product scores the edge.

Slide 65 gives the motivation. GAT is unable to represent different node and edge types. The R-GCN fix, introducing a set of neural networks for each relation type (node_s, edge, node_e), is too expensive for attention. Slide 67 shows that first attempt explicitly: keys and queries indexed by the edge's relation,

\[ \text{ATT-head}^i(s,e,t)=\big(K^i_{\phi(e)}(s)\,Q^i_{\phi(e)}(t)^\top\big),\quad K^i_{\phi(e)}(s)=\text{K-Linear}^i_{\phi(e)}\big(H^{(l-1)}[s]\big),\quad Q^i_{\phi(e)}(t)=\text{Q-Linear}^i_{\phi(e)}\big(H^{(l-1)}[t]\big), \]

i.e. a separate set of attention networks per relation type, too expensive.

Slide 66, the innovation: decompose heterogeneous attention into a node-type-dependent and an edge-type-dependent mechanism. In the example (paper and author node types, Write and Cite edge types) the figure shows a target Paper; a Paper neighbour (via Cite) goes through K-Linear\(_{Paper}\), an Author neighbour (via Write) through K-Linear\(_{Author}\); the target goes through Q-Linear\(_{Paper}\); then the matrices ATT\(_{Cite}\) and ATT\(_{Write}\) combine key and query into scores. With 3 node types and 2 edge types this needs 3 node weight matrices and 2 edge weight matrices. Without decomposition: \(3\cdot2\cdot3=18\) relation types, so 18 weight matrices (if all relation types exist).

Slide 68, heterogeneous mutual attention:

\[ \text{ATT-head}^i(s,e,t)=\big(K^i(s)\,W^{ATT}_{\phi(e)}\,Q^i(t)^\top\big), \] \[ K^i(s)=\text{K-Linear}^i_{\tau(s)}\big(H^{(l-1)}[s]\big),\qquad Q^i(t)=\text{Q-Linear}^i_{\tau(t)}\big(H^{(l-1)}[t]\big). \]

Each relation \((\tau(s),\phi(e),\tau(t))\) still gets a distinct set of projection weights, but they are composed from shared parts: \(\tau(s)\) and \(\tau(t)\) (the node types) parameterise K-Linear\(_{\tau(s)}\) and Q-Linear\(_{\tau(t)}\), which return the key and query vectors \(K(s)\), \(Q(t)\); the edge type \(\phi(e)\) directly parameterises \(W_{\phi(e)}\).

Slide 69, a full HGT layer:

\[ \widetilde{H}^{(l)}[t]=\underset{\forall s\in N(t)}{\bigoplus}\Big(\mathrm{Attention}_{HGT}(s,e,t)\cdot\mathrm{Message}_{HGT}(s,e,t)\Big). \]

The attention part was just computed. HGT decomposes the message weights the same way:

\[ \mathrm{Message}_{HGT}(s,e,t)=\big\Vert_{i\in[1,h]}\ \text{MSG-head}^i(s,e,t),\qquad \text{MSG-head}^i(s,e,t)=\text{M-Linear}^i_{\tau(s)}\big(H^{(l-1)}[s]\big)\,W^{MSG}_{\phi(e)}, \]

with M-Linear weights for each node type and \(W^{MSG}\) weights for each edge type; \(\Vert\) concatenates the \(h\) heads.

Slide 70, performance on ogbn-mag (predict paper venues): HGT (LADIES sampling, rank 18) has test accuracy 0.4927 ± 0.0061 and validation accuracy 0.4989 ± 0.0047 with 21,173,389 parameters, versus the R-GCN baseline at 0.4678 ± 0.0067 / 0.4761 ± 0.0068 with 154,366,772 parameters. HGT uses much fewer parameters (about 7 times fewer), even though attention is expensive to compute, and performs better than R-GCN, thanks to the weight decomposition over node and edge types.

Why does factorising work? It assumes that "how a paper presents itself as a key" does not depend much on which relation it is used in, and that each edge type is a single interaction pattern between those projections. The count grows like \(|T|+|E|\) instead of \(|T|^2|E|\).

Slide 71 returns to the design-space figure: heterogeneous GNNs extend GNNs by separately modelling node/relation types plus an additional AGG (the across-relation aggregation).

Slide 72 summarises the lecture:

• Heterogeneous graphs: graphs with multiple node or edge types. Key concept: the relation type (node_s, edge, node_e). Be aware that we don't always need heterogeneous graphs: one-hot type features plus an ordinary GNN can be enough.
• Learning with heterogeneous graphs. Key idea: separately model each relation type.
  • Relational GCNs (per-relation weights; block-diagonal or basis regularisation; node classification and link prediction with ranking metrics).
  • Design space for heterogeneous GNNs (per-relation messages, two-stage aggregation, per-type MLPs and heads, per-relation sampling).
  • Heterogeneous Graph Transformer (attention with weights factorised by node type and edge type).

Check yourself: for a graph with 4 node types and 4 edge types (like ogbn-mag), how many relation-type matrices would unfactorised attention need in the worst case, and how many does HGT need per head? show answer

\(4\cdot4\cdot4=64\) vs. about \(4+4\) groups of matrices: K-, Q-, M-Linear per node type plus \(W^{ATT}\), \(W^{MSG}\) per edge type.