Temporal Graph Networks: Modelling a Graph That Changes Over Time

A social graph, a transaction graph and an interaction log are not static objects with a timestamp column. They are streams of events, and the architecture that handles them keeps a per-node state that the stream updates. That state is the whole idea.

This is not fact versioning

Two different problems share the phrase “temporal graph”. One is bookkeeping: a knowledge graph where an edge carries a validity interval, so you can ask what the graph asserted as of a past date. That is a bitemporal data-modelling problem, solved with valid-time and transaction-time columns, and it has no learning in it.

The other is modelling, and it is what this page is about. Here the timing is the signal. Two users who interacted forty times in an hour and two who interacted forty times over three years produce the same edge in a static graph and mean entirely different things. A model that flattens the stream into an aggregate has thrown away the variable that most predicts the next event.

Why snapshots are the wrong default

The obvious approach is discrete-time: bucket events into daily or weekly snapshots, run a GNN on each, and feed the sequence of node embeddings to a recurrent network. It works, and it has two costs that are usually underestimated.

First, the bucket width is a hyperparameter that silently caps resolution. Events inside a bucket become simultaneous and unordered. If your phenomenon plays out in minutes and your bucket is a day, the model cannot see it, and no amount of training fixes that — the information is gone at the data layer.

Second, cost scales with buckets times graph size rather than with the number of events. A graph that receives a handful of events per day still costs a full forward pass per snapshot per node, so a fine-grained bucket you chose to preserve resolution multiplies the bill by the number of buckets.

The continuous-time formulation avoids both. The graph is a sequence of timed events — an interaction between two nodes at time t, or a node-feature update at time t — and the model consumes events, so cost scales with events and no resolution is discarded.

The four modules

Emanuele Rossi and colleagues at Twitter set out the general framework in Temporal Graph Networks for Deep Learning on Dynamic Graphs (2020), describing it as a combination of memory modules and graph-based operators. It decomposes into four parts, and most published continuous-time models are one choice for each.

Memory

Every node carries a state vector, initialised to zero when the node is first seen. It is a compressed history of everything that has happened to that node. A node that has never appeared has a zero memory, which is precisely the cold-start case handled in link prediction for a node with no edges.

Message function

When an event connects nodes i and j at time t, it produces a message for each endpoint, computed from the two memories, the elapsed time since that node’s last update, and any features on the event itself. The elapsed time is the part people leave out and it is load-bearing: without it the model has no way to distinguish a burst from a trickle.

Memory updater

A recurrent cell — a GRU is the standard choice — folds the message into the node’s memory. If several events touch a node in one batch, their messages are aggregated first, most simply by keeping only the most recent.

Embedding module

You do not use the memory directly. It goes stale: a node that has been quiet for months has a memory reflecting a world that has moved on. Instead the embedding for node i at time t is computed by attending over i’s recent temporal neighbours, combining their memories with the elapsed time since each interaction. This is a graph attention layer with time encoding, and it is what repairs staleness — a quiet node still gets a current embedding, borrowed from neighbours who have been active. Skip this module and you have a per-node RNN with a graph bolted on, which performs like one.

The batching hazard

The memory creates a dependency between training examples that ordinary mini-batching assumes away, and this is the part that is easy to get silently wrong.

Process a batch of events and update memories from them; the loss on later events in that same batch is then computed from memories that already contain those events. The model can predict an interaction it has already been told about. Training loss drops beautifully and nothing generalises — the classic signature of leakage, and the reason a suspiciously good temporal result should be audited before it is celebrated.

The fix in TGN is to stage the update: messages generated by a batch are written to a raw message store, and the memory used to compute a batch’s embeddings is updated only from messages produced by previous batches. Each event therefore updates the memory strictly after it has been predicted. Two consequences follow. Batches must be processed in time order, so the usual shuffle is forbidden. And because updates are sequential, large batches reduce how often the memory refreshes, making batch size a modelling parameter here rather than only a throughput one.

Evaluating without leaking the future

• Split by time, never at random. A random edge split puts future edges in training and past edges in test, which is not the task. Take the first 70% of events by timestamp for training and the rest for evaluation.
• Sample negatives from the right time. A negative example is a pair that did not interact at time t. Sampling uniformly from all nodes includes nodes that did not exist yet, making negatives trivially separable and the score meaningless.
• Report inductive and transductive separately. Predicting an edge between two nodes seen in training is a different problem from predicting one involving a node that appears for the first time in the test period. Averaged together, a strong transductive score hides a useless inductive one.
• Reset the memory before evaluation. If the memory carries state accumulated during training over test-period nodes, the evaluation is not measuring what it claims to. Replaying the test stream from a defined memory state is the only reproducible option.

One structural limitation is worth stating plainly. Most of this literature models edge addition. Deletion — an unfollow, a closed account, a revoked permission — is not naturally an event that adds information to a memory, and treating it as just another event type is a modelling choice rather than a solved problem. If deletions carry most of your signal, check what your chosen implementation actually does with them before trusting the output.