1. Three Types of Dynamic Graphs
| Type | Description | Example |
|---|---|---|
| Static | Graph fixed in time | Cora citations (snapshot) |
| Discrete-time | Sequence of graph snapshots $G_1, G_2, \ldots$ | Monthly co-purchase networks |
| Continuous-time | Edges arrive with timestamps $(u, v, t)$ | Social interactions, payments |
Why not ignore time? If you shuffle timestamps, you leak future into past. A model that sees tomorrow's edges will look great and fail in production.
2. Snapshot Methods
Run a GNN on each snapshot independently, then aggregate over time with RNN/Transformer/attention.
$$\mathbf{h}_i^{(t)} = \text{GNN}(G_t, \mathbf{X}_t)_i \quad \mathbf{z}_i = \text{TemporalAgg}(\{\mathbf{h}_i^{(t)}\}_{t=1}^T)$$Simple but loses fine-grained event order within snapshots.
3. EvolveGCN & DySAT
EvolveGCN: GCN weights evolve over time via RNN - parameters at step $t$ depend on $t-1$.
DySAT: structural self-attention within each snapshot + temporal self-attention across snapshots.
4. Temporal Graph Networks (TGN)
Paper: Rossi et al. - Temporal Graph Networks (2020)
TGN maintains a memory vector per node, updated when an interaction happens:
- Event $(u, v, t)$ arrives
- Fetch memory $\mathbf{s}_u, \mathbf{s}_v$
- Compute message from event + node states
- Update memories with GRU-like module
- Compute embedding for prediction
Handles streaming edges in real time - used for dynamic link prediction and recommendation.
5. Temporal Link Prediction
Predict whether edge $(u,v)$ will appear in window $[t, t+\Delta]$ given history before $t$.
- Split: train on past edges, test on future edges only
- Negative sampling: random non-edges in same time window
- Metrics: AUC-ROC, AP over future edges
6. When Temporal Modeling Matters
- Yes: social feeds, fraud (evolving rings), traffic, supply chain, interaction recommendation
- No: static molecules, fixed citation networks (unless you add time explicitly)