1. Heterogeneous Graphs
A heterogeneous graph has multiple node types and edge types. Example: Amazon graph with users, products, brands; edges: purchase, view, brand_of.
Homogeneous GNNs treat all nodes the same - wrong when types have different semantics and dimensions.
2. Metapaths
A metapath is a typed path schema: User → Purchase → Product → Brand. It defines semantic relationships between same-type nodes (two users who bought from same brand).
HAN (Hu et al.): attention over metapath-based neighbor groups. MAGNN: embed metapath instances with intra- and inter-metapath attention.
3. R-GCN
Paper: Schlichtkrull et al. - Modeling Relational Data with GCNs (2018)
$$\mathbf{h}_i^{(l+1)} = \sigma\left(\sum_{r \in \mathcal{R}} \sum_{j \in \mathcal{N}_r(i)} \frac{1}{c_{i,r}} \mathbf{W}_r^{(l)} \mathbf{h}_j^{(l)} + \mathbf{W}_0^{(l)}\mathbf{h}_i^{(l)}\right)$$Separate weight matrix $\mathbf{W}_r$ per relation type $r$. $c_{i,r}$ normalizes by neighborhood size. Basis or block-diagonal decomposition reduces parameters when many relation types exist.
4. HGT
Paper: Hu et al. - Heterogeneous Graph Transformer (2020)
Type-specific attention: meta-relation triple $(s, r, t)$ defines how source type $s$ sends message via relation $r$ to target type $t$. HGT scales to billion-edge graphs (Microsoft Academic Graph).
5. Knowledge Graph Embeddings
Knowledge graphs store facts as triples $(h, r, t)$ - head entity, relation, tail entity.
- TransE: $\mathbf{h} + \mathbf{r} \approx \mathbf{t}$ (simple, fails on 1-to-N relations)
- DistMult: $\langle \mathbf{h}, \mathbf{r}, \mathbf{t} \rangle$ score (bilinear, symmetric)
- ComplEx: complex-valued embeddings (handles asymmetric relations)
- R-GCN + embeddings: combine structural GNN with translational scoring for link prediction
6. Link Prediction
Score candidate edge $(i, j)$:
- Decoder on embeddings: $\sigma(\mathbf{h}_i^T \mathbf{W} \mathbf{h}_j)$
- DistMult/TransE score on final GNN embeddings
- Negative sampling: corrupt true triples, train with BCE or margin ranking loss
Metrics: MRR, Hits@K. Critical for recommendation and KG completion.