Heterogeneous and Temporal Graphs
Why real graphs have typed nodes and edges that a homogeneous model averages together, how relation-specific message passing preserves the distinction, and what adding time requires.
The graphs in textbooks have one node type and one edge type. The graphs in production do not: a commerce graph has users, items, sellers and categories, connected by viewed, purchased, returned and listed. Treating them as one homogeneous graph averages a purchase and a return into the same message, which discards the distinction the model most needs.
Relation-specific message passing
The fix is to give each relation type its own transformation. A node aggregates separately over each relation, then combines:
Each relation \(r\) has its own weight matrix, so "purchased" and "returned" transform their messages differently and the model can learn that one is positive evidence and the other negative.
The cost is parameters proportional to the number of relations, which for a knowledge graph with a thousand relation types is prohibitive. Basis decomposition, expressing each \(W_r\) as a learned combination of a small set of shared basis matrices, is the standard remedy: it shares statistical strength across relations and bounds the parameter count.
Attention-based heterogeneous models take a different route, learning per-relation attention so the aggregation weights depend on the node pair as well as the relation type, which handles the case where a relation's importance varies by context.
Metapaths are the third approach: define semantically meaningful typed paths, such as user-item-user, and aggregate along them. This encodes domain knowledge explicitly and requires someone to choose the metapaths, which is both its strength and its limitation.
Adding time
A temporal graph has edges with timestamps, and the requirement it imposes is strict: a node's representation at time \(t\) must depend only on edges before \(t\). Violating that is the leakage described under link prediction, and it is easy to violate accidentally through a preprocessing step that touches the whole graph.
The two representations are discrete-time, a sequence of graph snapshots processed by a graph network per snapshot and a sequence model across them, which is simple and loses within-snapshot ordering; and continuous-time, where each event updates the involved nodes' memory immediately, which preserves exact ordering and requires a memory module and careful batching, since events within a batch have an order the parallelism does not respect.
When it breaks
Type imbalance skews learning. One relation with a hundred million edges and another with ten thousand means the rare relation's transformation is barely trained, and the aggregate metric is dominated by the common one. Per-relation evaluation is what surfaces it.
Metapath selection is the model. The chosen paths determine what the model can express, so a missing metapath is a capability the model cannot have, and the choice is rarely revisited after the first design.
Temporal batching is where leakage enters. Processing a batch of events in parallel means events later in the batch can influence representations used for earlier ones unless the implementation orders updates explicitly. This is a subtle bug that inflates results and passes every test.
Node features change over time too. A user's attributes at the time of an interaction are not their attributes now, and using current features on a historical edge is the same point-in-time correctness failure that afflicts feature stores, arriving in a setting where it is even easier to overlook.
12 flashcards for this concept
Click a card to reveal the answer.