Interview: Heterogeneous Graphs

A graph with multiple node types and/or edge types. Example: users, products, categories with purchase, view, and belongs_to edges. Each type has different semantics - one weight matrix is not enough.

Separate weight matrix $\mathbf{W}_r$ per relation type $r$. Aggregate messages from each relation separately with normalization $c_{i,r}$, plus self-loop transform $\mathbf{W}_0$. Basis decomposition reduces parameters when there are many relations.

A typed path schema like User → Purchase → Product → Brand. Connects same-type nodes through semantic paths. HAN uses attention over metapath-based neighbor groups.

For triple $(h, r, t)$: minimize $\|\mathbf{h} + \mathbf{r} - \mathbf{t}\|$. Head plus relation should approximate tail. Simple but fails on 1-to-N relations (one head, many tails).

Hide test triples, rank all candidate tails (or heads) for each query, report MRR and Hits@K. Use negative sampling during training. Filter out other true triples when ranking (filtered setting).

Heterogeneous Graph Transformer - type-specific attention using meta-relation triples $(s, r, t)$. Scales to billion-edge heterogeneous graphs. Used on Microsoft Academic Graph.