Definition
Temporal graph network (TGN) is a GNN for continuous-time dynamic graphs, given as a stream of timestamped events. It combines a per-node memory, updated by a recurrent cell whenever the node takes part in an event, with a temporal graph attention layer over the node's past neighbours. Introduced by Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti and Michael Bronstein (Twitter), "Temporal Graph Networks for Deep Learning on Dynamic Graphs" (arXiv, 2020).
Many graphs are streams of events rather than fixed objects: users edit Wikipedia pages, post in subreddits, follow accounts, make payments. Each event is , an interaction between nodes and at time , often with a feature vector. The usual task is future link prediction: given everything before , score whether and interact at (see Link prediction). A second is dynamic node classification, for example predicting that a user is about to be banned.
A static GNN such as GraphSAGE sees one frozen graph. Running it on the whole history leaks the future into the past, and rerunning it on every snapshot is expensive and coarse in time. Earlier continuous-time models each solved part of the problem. JODIE (Kumar, Zhang and Leskovec, KDD 2019) keeps an RNN memory per user and item. DyRep (Trivedi et al., ICLR 2019) updates memories with attention over neighbours. TGAT (Xu et al., ICLR 2020) has no memory but attends over temporal neighbours with a learned time encoding. TGN puts these pieces into one framework, in which each earlier model is a special case.
Memory: messages and a recurrent update
- memory of node just before ; it starts at zero and changes only when takes part in an event
- time of 's last memory update, so says how long has been silent
- message: the paper's best variant is the identity, a plain concatenation (an MLP is the alternative)
- combines the messages a node receives in one batch; "keep only the most recent" and "mean" were tested
- the memory updater: a Gated recurrent unit (GRU) cell, or a Long short-term memory (LSTM) cell
Embedding: temporal graph attention
Memory alone has a weakness. A node that has been silent for a long time keeps an old memory, because only its own events update it. The embedding module fixes this by aggregating over the node's temporal neighbours, whose memories may be fresh. Only events before are used, so the model never looks ahead.
- input to the layer: memory plus the node's own features, if any
- temporal neighbours of : nodes it interacted with before , the most recent ones by default
- TGAT's time encoding, a vector of cosines with learnable frequencies and phases , so the attention can weigh events by their age
- attention weights, computed with multiple heads as in Multi-head attention
For link prediction, a decoder MLP takes and outputs a probability. Each true event is paired with a negative, the same source and a random destination, and the loss is Binary cross-entropy. The metric is average precision (AP). The paper also tests two cheaper embedding modules: identity, , and JODIE's time projection, which scales the memory by .
Training without leaking the future
Events are processed in chronological batches of 200. A naive loop would update memory with batch and then predict batch , so the memory would already contain the answer. TGN reverses the order. It stores each batch's raw messages, and at the start of the next batch it first updates memory with them, then predicts. Because that update runs inside the forward pass, the GRU and message modules get gradients. The cost is staleness: an event cannot see earlier events of its own batch through memory, only through the graph that the embedding module reads.
| model | memory | memory updater | embedding module |
|---|---|---|---|
| JODIE | yes | RNN | time projection: (1 + w Δt) ∘ s |
| DyRep | yes | RNN, messages from attention over neighbours | identity |
| TGAT | no | — | temporal graph attention, 2 layers |
| TGN-attn | yes | GRU | temporal graph attention, 1 layer |
Paper setting (Rossi et al., 2020)
- Wikipedia
- users editing pages over one month: 9,227 nodes, 157,474 timestamped edges, 172-d edge features from the edit text; bipartite
- users posting to subreddits over one month: 10,984 nodes, 672,447 edges, 172-d edge features; bipartite
- Splits
- chronological 70 % / 15 % / 15 %; the inductive setting scores links involving nodes never seen in training
- Main model
- TGN-attn: GRU memory, identity message, most-recent aggregator, one attention layer with 2 heads over 10 most recent neighbours, batch 200
- Future link prediction (AP)
- transductive 98.46 on Wikipedia and 98.70 on Reddit; inductive 97.81 and 97.55
- Ablations
- removing the memory or replacing attention with the identity embedding both cost accuracy; most-recent neighbour sampling beat uniform; with memory, one attention layer was about as good as two
| event | nodes | t | batch | memory read (last update) | stale? |
|---|---|---|---|---|---|
| e1 | A–B | 1 | 1 | A: none, B: none | no |
| e2 | B–C | 2 | 1 | B: none (e1 not yet absorbed), C: none | yes, B |
| e3 | A–C | 4 | 1 | A: none, C: none | yes, A and C |
| e4 | C–D | 5 | 2 | C: t = 4, D: none | no |
| e5 | A–B | 7 | 2 | A: t = 4, B: t = 2 | no |
| e6 | B–D | 8 | 2 | B: t = 2, D: none | yes, B and D |
So 3 of the 6 events are stale at batch size 3. With batch size 1 none are and with batch size 6 five are. At the start of batch 3, node B has two stored messages, from e5 and e6. The "most recent" aggregator keeps only e6's, , and the GRU applies it once. Smaller batches mean fresher memory but more sequential steps, which is why batch size is a speed–accuracy knob.
1import torch2from torch_geometric.datasets import JODIEDataset3from torch_geometric.loader import TemporalDataLoader4from torch_geometric.nn import TGNMemory5from torch_geometric.nn.models.tgn import IdentityMessage, LastAggregator, LastNeighborLoader67data = JODIEDataset("data/JODIE", name="wikipedia")[0] # 157,474 events, 172-d messages8train, val, test = data.train_val_test_split(val_ratio=0.15, test_ratio=0.15)9loader = TemporalDataLoader(train, batch_size=200, neg_sampling_ratio=1.0)10nbrs = LastNeighborLoader(data.num_nodes, size=10) # 10 most recent neighbours1112d = 10013memory = TGNMemory(data.num_nodes, data.msg.size(-1), d, d,14 message_module=IdentityMessage(data.msg.size(-1), d, d),15 aggregator_module=LastAggregator())1617for batch in loader: # chronological batches18 opt.zero_grad()19 n_id, edge_index, e_id = nbrs(batch.n_id)20 assoc[n_id] = torch.arange(n_id.size(0))21 s, last_update = memory(n_id) # applies the previous batch's stored messages22 z = gnn(s, last_update, edge_index, data.t[e_id], data.msg[e_id])23 pos = link_pred(z[assoc[batch.src]], z[assoc[batch.dst]])24 neg = link_pred(z[assoc[batch.src]], z[assoc[batch.neg_dst]])25 loss = bce(pos, torch.ones_like(pos)) + bce(neg, torch.zeros_like(neg))26 memory.update_state(batch.src, batch.dst, batch.t, batch.msg) # store this batch27 nbrs.insert(batch.src, batch.dst)28 loss.backward()29 opt.step()30 memory.detach() # truncate backprop through timeWhere it's used
Social and content platforms
predicting the next follow, post or interaction from an event stream; the authors were at Twitter
Transactions
fraud and anomaly detection, where the timing and recency of payments between accounts carry the signal
Recommendation
user–item interaction streams, the setting of JODIE's Wikipedia, Reddit and LastFM data
Check yourself
Why does TGN update memory with the previous batch's messages at the start of each batch, rather than with the current batch's messages?
Check yourself
At query time , node 's past events are at . With most-recent sampling, which neighbours does attention see and with which time encodings?
Remember
- ✓Continuous-time dynamic graph = stream of timestamped events; main task is future link prediction, scored by AP against sampled negatives.
- ✓Memory: messages to both endpoints, aggregated per batch, then .
- ✓Embedding: attention over the most recent earlier neighbours, keys with ; it counters stale memory.
- ✓Batches of 200: apply the previous batch's messages, predict, then store this batch's messages. No leakage, but in-batch memory is stale.
- ✓JODIE, DyRep and TGAT are special cases. TGN-attn: 98.46 / 98.70 transductive AP on Wikipedia / Reddit.