Heterogeneous Graphs: When Nodes and Edges Are Not All One Type

Nearly every real graph has more than one kind of node. The standard GNN layer assumes exactly one, and the assumption is not cosmetic — it is baked into the shape of the weight matrix. Here is where it fails and what the fix costs.

A graph with four types

Take a retail graph with two node types and two edge types. Users have a 32-dimensional feature vector: tenure, region one-hot, coarse activity buckets. Products have a 768-dimensional feature vector: a text embedding of the title and description. There are 4,000,000 users and 250,000 products. Edges are (user, viewed, product) — 900,000,000 of them — and (user, purchased, product), of which there are 12,000,000.

That is four types in the sense that matters: two node types, two edge types, and therefore four distinct message paths once you add the reverse directions.

Where one layer breaks

A graph convolution layer computes, for each node, a transform of the mean of its neighbours’ features. Write it as h_i' = sigma(W · mean(h_j for j in N(i))). Now try to run it on this graph and it fails immediately in three separate ways.

The shapes do not match. A user’s neighbours are products, so mean(h_j) over that neighbourhood is a 768-vector, while the user’s own h_i is a 32-vector. There is no single W that consumes both. This is not a subtle modelling disagreement; it is a dimension error, and it is why every heterogeneous framework begins with a per-type input projection mapping each node type into one shared hidden width.

The mean destroys the distinction that matters. Suppose you project both types to 256 dimensions so the arithmetic runs. A user with 300 views and 4 purchases now has their representation formed from a mean in which purchases contribute roughly 1.3% of the mass. The purchase signal — the one you actually want — is averaged into noise by the views. The layer is not wrong, it is answering a question nobody asked: what does this user’s undifferentiated product neighbourhood look like.

Direction is a type too. The message from a product to a user (“what kind of thing does this person buy”) and from a user to a product (“what kind of person buys this”) are different functions. Treating the edge as undirected forces one weight matrix to serve both.

Per-relation weights and what they cost

The direct fix is one weight matrix per relation. Michael Schlichtkrull and colleagues introduced this as the relational graph convolutional network in Modeling Relational Data with Graph Convolutional Networks (2017). Each relation aggregates its own neighbours with its own weights, and the results are summed:

for each relation r in R:
    m_r = normalise_r( sum over j in N_r(i) of  W_r . h_j )
h_i' = sigma( W_self . h_i  +  sum over r of m_r )

Now purchases and views have separate parameters and cannot drown each other. The cost is parameters. With hidden width 256 and the four directed relations above, plus a self-loop relation:

per relation:   256 x 256          =    65,536 parameters
relations:      viewed, viewed_rev,
                purchased, purchased_rev,
                self                =         5
layer total:    5 x 65,536          =   327,680 parameters
three layers:                       =   983,040 parameters

Note that the relation count, not the node-type count, is what drives this. Adding a third node type with one new edge type costs one more matrix; adding fifty edge types between the two types you already had costs fifty. When people say a heterogeneous model “did not scale”, the relation cardinality is almost always what they ran into.

Manageable here. It stops being manageable on a knowledge graph: with 200 relation types, one layer is 200 × 65,536 = 13.1 million parameters, three layers is 39 million, and rare relations have a few dozen training edges each to fit 65,536 parameters against. That is overfitting by construction, and it is why the R-GCN paper introduces basis decomposition — every W_r is written as a learned linear combination of B shared basis matrices, so the parameter count becomes B × 65,536 plus B coefficients per relation, and B is a knob you set well below the relation count.

Metapaths and typed attention

A second family says the useful structure is not the single edge but the typed path. A metapath is a type sequence such as user–purchased–product–purchased–user, which connects two users who bought the same thing. Follow it and you get a homogeneous neighbourhood you can run an ordinary attention layer over. Xiao Wang and colleagues’ Heterogeneous Graph Attention Network (WWW 2019) does exactly this with two attention levels: node-level attention weights neighbours within one metapath, and semantic-level attention weights the metapaths against each other, so the model learns that co-purchase matters more than co-view rather than being told.

The catch is that somebody has to choose the metapaths, and the choice is a strong prior. Ziniu Hu and colleagues’ Heterogeneous Graph Transformer (WWW 2020) removes it, parameterising the attention itself by the types of the source node, target node and edge, so type-specific behaviour is learned without an enumerated path list. For the general attention mechanism underneath both, see graph attention networks.

The four traps

• Missing reverse edges. Store (user, viewed, product) only and messages flow one way. The product never hears from its viewers, and half your graph is inert. Every framework expects reverse relations to be materialised explicitly; nothing warns you when they are absent, and the model still trains.
• Relation imbalance. 900 million views against 12 million purchases is a 75:1 ratio. Per-relation weights stop the averaging problem but not the gradient one — the view relation sees 75 times the updates. Per-relation normalisation, or sampling a fan-out per relation rather than per node, is what actually equalises them.
• Sampling fan-out is per relation now. A fan-out of 15 on a node with two relation types means 15 total or 15 each, depending on the library. The difference is a factor of two in the working set computed in graph sampling strategies, and it is worth reading your implementation rather than assuming.
• Type-mixed evaluation. Accuracy averaged over user and product predictions tells you about whichever type is more numerous. Report per type.

There is also a decision that precedes all of this and gets made by accident: what deserves to be a node type at all. Region is an attribute on the user in the example above, but it could equally be a node with users attached to it. Promoting it changes the model materially — it creates a two-hop path between every pair of users in the same region, so region membership starts propagating representations rather than merely tagging them. That is sometimes what you want and sometimes a channel through which four million users blur into a handful of regional averages. The test is whether you want messages to flow between the rows that share the value. If not, keep it a feature.

One thing typing does not fix: depth still hurts. Per-relation weights give each hop more expressive power but the repeated averaging is the same operator, so a six-layer heterogeneous model oversmooths for the same reason a six-layer GCN does.