Temporal Graphs: Dynamic Graph Evolution

Ramesh's salary account receives ₹50,000 at 9:00 AM on the first of the month. By 9:12 AM, ₹48,000 of it has passed through three intermediate UPI accounts and landed in a fourth, which cashes out at an ATM before noon. A bank's fraud engine that builds one graph a day — nodes as accounts, edges as "who paid whom" — would see, at midnight, that account B received money from A and sent money to C and D. That is exactly what a small kirana store's account looks like too: money comes in from customers, money goes out to a wholesaler. The static snapshot cannot tell a mule account from a legitimate pass-through business, because it has thrown away the one feature that separates them: when each edge happened relative to the others. A kirana store's outgoing payment to its wholesaler happens once a week, at business hours, for a stable pattern of amounts. A mule account's outgoing payments happen within minutes of the incoming one, every time, regardless of hour. The graph structure is identical. The story is only visible in time.

This is the problem temporal graphs are built to solve: model a graph not as one fixed structure but as a structure that evolves, and build machine-learning methods that read the order and spacing of edges as a first-class signal — not as a label you filter on after the fact, but as information that changes what a node's representation means at each instant.

Two ways to formalize "a graph that changes"

A static graph is a pair G = (V, E). A temporal graph adds time, and there are two standard ways to attach it, and the choice matters for which architecture you can use.

Discrete-Time Dynamic Graph (DTDG). You take a sequence of snapshots, one per fixed interval: G = (G_1, G_2, ..., G_T), where each G_t = (V_t, E_t) is an ordinary static graph. This is natural when data genuinely arrives in batches — a daily settlement file, a weekly co-authorship dump, IRCTC's end-of-day report of how many berths were confirmed on each train. The unit of time is the snapshot index, and "how long ago" only has meaning in units of whole snapshots.

Continuous-Time Dynamic Graph (CTDG). You keep the graph as a stream of timestamped events: {(u_1, v_1, t_1, e_1), (u_2, v_2, t_2, e_2), ...}, where each tuple says "an edge (possibly with features e_i, such as a transaction amount) appeared between u_i and v_i at real-valued time t_i." Nothing forces events onto a grid. This is the natural model for UPI transactions, sensor pings, or IRCTC seat bookings, which happen at arbitrary, asynchronous instants — the six minutes between Ramesh's deposit and the mule account's first outgoing hop is real information, and a DTDG with daily snapshots would compress it out of existence.

The two formalizations lead to two families of models. DTDGs pair naturally with "run a GNN per snapshot, then evolve it with a sequence model." CTDGs pair naturally with "maintain a running state per node and update it exactly when an event touches that node."

Encoding time itself

Both families eventually need to turn a timestamp — or a time gap, Δt — into a vector a neural network can consume. Feeding a raw Unix timestamp in directly is a bad idea for the same reason feeding a raw token index into a Transformer would be: the magnitude is huge and arbitrary, and the network has no reason to treat "3600 seconds apart" as meaningfully similar to "3601 seconds apart" versus "10 seconds apart." What the model actually needs is a function of the time difference between two events, since what matters for attention or decay is relative recency, not absolute clock reading.

The standard fix, used in TGAT (Xu et al., ICLR 2020) and descended from Time2Vec, is a functional time encoding built from one linear term and several sinusoids:

φ(t)[0] = ω₀ · t + b₀                    (captures overall trend / linear progression)
φ(t)[i] = sin(ωᵢ · t + bᵢ)   for i = 1..k  (captures periodicity at k learned frequencies)

The sinusoidal terms are justified by Bochner's theorem: any translation-invariant kernel (a kernel that depends only on t₁ − t₂, which is exactly the property you want when comparing "how far apart in time were these two events") can be written as an expectation over random Fourier features of exactly this sin/cos form. In practice the frequencies ωᵢ and phases bᵢ are learned parameters, so training discovers which time-scales matter for the task — an hourly rhythm for retail transactions, a weekly rhythm for salary credits, a sub-minute rhythm for mule layering.

From formalism to architecture: EvolveGCN and TGN

On the DTDG side, EvolveGCN (Pareja et al., AAAI 2020) keeps the graph convolution structure of an ordinary GCN, H_{t+1} = σ(Â H_t W_t), but stops treating the weight matrix W_t as fixed. Instead, W_t itself is the hidden state of a recurrent network (a GRU or LSTM) that reads W_{t-1} and produces W_t: the graph filters evolve through time even though each individual snapshot is processed by an otherwise ordinary GCN. This is elegant because it needs no node ever to be aligned across snapshots by identity — useful when the snapshot graphs don't even share the same node set.

On the CTDG side, Temporal Graph Networks (TGN) (Rossi et al., 2020) give every node v a memory vector m_v(t) that is updated only when an event touches v, not on a clock tick. When event (u, v, t, e) arrives, TGN computes a message from the two nodes' current memories, their memory ages, and the edge feature, then feeds that message through a learned updater (a GRU) to produce the new memory for v. A separate embedding module — commonly a temporal self-attention layer in the style of TGAT — later combines a node's memory with attention over its recent temporal neighborhood, using the time encoding above as part of the attention key, to produce the actual task-facing embedding. Crucially, this memory update is causal: computing m_v(t) is only allowed to use events with timestamp ≤ t. That single constraint is what makes the model deployable — at inference time in a live fraud system you genuinely do not have tomorrow's transactions, so a model architecture that assumed you did would be worthless in production even if it scored beautifully offline.

Worked example: catching a mule-account ring, event by event

To make the memory-update idea completely mechanical, here is a simplified version of it — plain arithmetic instead of TGN's learned GRU and message MLP, so every number can be checked by hand — run over Ramesh's scenario. Four accounts: A (Ramesh's salary account, established), B (first mule hop), C (a merchant/cash-out point), D (second mule hop). Each account carries a scalar memory that starts at 1.0 for the two "established" accounts (A, C) and 0.0 for the two brand-new ones (B, D) — a fresh account with zero transaction history is itself a weak risk signal. Memory decays with a one-hour half-life between touches, then absorbs an incoming message:

decay(Δt) = 2^(-Δt)                         (half-life = 1 hour)

on event (u, v, t, a):
    m_u ← memory[u] · decay(t − last[u])     # sender's memory, aged
    m_v ← memory[v] · decay(t − last[v])     # receiver's memory, aged
    message = m_u + a                        # sender's state + transaction-amount signal
    memory[v] ← m_v + message                # receiver absorbs the message
    memory[u] ← m_u                          # sender's aged value is stored back
    last[u] ← t ; last[v] ← t

The event stream, all within twelve minutes:

t=0.00 h : A → B, a=1.0    (Ramesh's salary hop)
t=0.10 h : B → C, a=0.4    (first layering hop, 6 minutes later)
t=0.15 h : B → D, a=0.4    (second layering hop, 3 minutes later)
t=0.20 h : D → C, a=0.35   (fan-in back to the cash-out point)

Tracing it in code, with no helpers — every function used is defined above it:

def decay(delta_t, half_life=1.0):
    return 2 ** (-delta_t / half_life)

memory = {"A": 1.0, "B": 0.0, "C": 1.0, "D": 0.0}
last = {"A": 0.0, "B": 0.0, "C": 0.0, "D": 0.0}

events = [
    ("A", "B", 0.00, 1.0),
    ("B", "C", 0.10, 0.4),
    ("B", "D", 0.15, 0.4),
    ("D", "C", 0.20, 0.35),
]

for u, v, t, a in events:
    m_u = memory[u] * decay(t - last[u])
    m_v = memory[v] * decay(t - last[v])
    message = m_u + a
    memory[v] = m_v + message
    memory[u] = m_u
    last[u] = t
    last[v] = t
    print(f"t={t:.2f}  {u}->{v}  memory[{v}]={memory[v]:.4f}")

Tracing by hand (rounding each intermediate to four decimals, same as the code's own print formatting) reproduces every printed line to within the last displayed digit. Event 1 (A→B, t=0): both nodes have Δt=0 so decay is 1; message = 1.0 + 1.0 = 2.0; memory[B] = 0.0 + 2.0 = 2.0000. Event 2 (B→C, t=0.10): Δt_B = 0.10, decay = 2^(-0.10) = 0.9330, so m_B = 2.0 × 0.9330 = 1.8661; C has the same Δt=0.10 so its decayed value is 1.0 × 0.9330 = 0.9330; message = 1.8661 + 0.4 = 2.2661; memory[C] = 0.9330 + 2.2661 = 3.1991. Event 3 (B→D, t=0.15): Δt_B = 0.05, decay = 2^(-0.05) = 0.9659, m_B = 1.8661 × 0.9659 = 1.8026; D is untouched since the start so m_D = 0; message = 1.8026 + 0.4 = 2.2026; memory[D] = 0 + 2.2026 = 2.2026. Event 4 (D→C, t=0.20): Δt_D = 0.05 → decay = 0.9659, m_D = 2.2026 × 0.9659 = 2.1277; Δt_C = 0.10 → decay = 0.9330, m_C = 3.1991 × 0.9330 = 2.9848; message = 2.1277 + 0.35 = 2.4777; memory[C] = 2.9848 + 2.4777 = 5.4625.

Final memory after twelve minutes: A=1.0000, B=1.8026, C=5.4625, D=2.1277. Now compare against the counterfactual where Ramesh had paid the merchant C directly, a single hop, same total order of magnitude (a=1.0): m_u = 1.0, m_v = 1.0, message = 2.0, memory[C] = 1.0 + 2.0 = 3.0000. A direct, legitimate-looking payment leaves C's memory at 3.00. The layered route through two rapid mule hops — carrying less total amount signal (0.4 + 0.35 = 0.75 versus 1.0) — leaves C's memory at 5.46, over 80% higher, purely because the decay term barely had time to bite between hops. That gap is the entire point of a temporal-graph model: it is a learned, quantitative trace of "money moved through here fast," and it exists nowhere in the daily-aggregated adjacency matrix, which records only that B and D each sent C money once.

Reading the diagram

The figure lays the same four events on a shared time axis, one lane per account, so the causal, left-to-right flow of memory updates is visible directly — this is the mechanism traced above, not a generic network picture.

Follow the arrows left to right: the memory box at each arrowhead is the exact number the traced code prints. Note that C's box appears twice, once after the direct-style second hop (3.199) and again after the fan-in from D (5.462) — the second update happens only 0.10h after the first, so almost none of C's accumulated memory has decayed away before the new message stacks on top of it. That stacking-before-decay is the visual signature of layering.

Common misconception

The mistake most students make on first meeting this topic is to think a temporal graph is just an ordinary graph with a "timestamp" column bolted onto each edge — something you could handle by keeping a regular GCN and just filtering the edge list to t ≤ t_query before running it, or by adding time as one more numeric feature into the same permutation-invariant aggregation a static GNN already does. That is wrong in a way that breaks the model, not just a simplification. Ordinary GCN/GraphSAGE aggregation (mean, sum, or attention over a neighborhood) is order-invariant: it produces the same output no matter what sequence the edges are fed in, because it was designed for a graph that has no sequence. Bolting a timestamp on as an extra feature doesn't fix this — the aggregation still mixes all neighbors together in one symmetric pool, so a node that received money then immediately forwarded it looks identical, feature for feature, to a node that received money and forwarded a different amount to different people a week apart, as long as the *set* of timestamps happens to produce similar summary statistics. What genuinely distinguishes fraud in the worked example is the ordering and the tiny gaps between specific pairs of events — B's outgoing edges only make sense as suspicious relative to B's own incoming edge three minutes earlier. Capturing that requires memory that updates sequentially, event by event, exactly as this chapter's update rule does, or an attention mechanism (TGAT-style) that explicitly weighs neighbors by a learned function of the time gap. Time is not a feature you can add to a static aggregator after the fact — it changes what "aggregation" has to mean.

Active recall

Attempt these before reading the answers below.

1. Why does running an ordinary GCN on one daily-aggregated snapshot of Ramesh's scenario fail to flag the mule ring, even though all four edges are present in that snapshot?
2. In the memory update rule memory[v] ← m_v_decayed + (m_u_decayed + a), what happens to a node's stored memory if a very long time passes with no new event, right before the next one arrives?
3. Using decay(Δt) = 2^(−Δt) with a one-hour half-life, what is the decay factor at Δt = 2 hours?
4. Which formalism — DTDG or CTDG — fits (a) IRCTC recording seat bookings as they happen, and (b) IRCTC publishing a once-daily occupancy report per train? Justify each.
5. Why must temporal message passing be causal — using only events with t' ≤ t when computing a node's embedding at time t — and what specifically goes wrong in a fraud-detection system if this rule is violated?
6. Why encode time with a linear-plus-sinusoid function (Time2Vec/TGAT-style) instead of feeding the raw timestamp value straight into the network?

Answers.

1. A GCN's aggregation step is permutation-invariant over a node's neighborhood — it has no mechanism to represent "B received this money and forwarded it six minutes later" versus "B received this money and forwarded a similar amount a month later." Both produce the same static edge set, hence the same aggregated features, so the snapshot destroys exactly the signal (rapid succession) that flags layering.

2. As Δt → ∞, 2^(−Δt) → 0, so the old stored memory is discarded almost entirely and the update collapses to essentially just the new incoming message — the node's representation is dominated by whatever touched it most recently. This is the intended behavior: long-idle accounts should not carry stale state forward indefinitely.

3. 2^(−2) = 0.25 — after two half-lives, a quarter of the original memory value remains.

4. (a) Bookings happening at arbitrary asynchronous instants are a CTDG — a stream of timestamped events, no natural fixed interval. (b) A once-daily report is a DTDG — one snapshot per day, and "how many days ago" is the only time granularity that exists in the data.

5. Causality is required because in production you never have future transactions available at inference time — a model that (even accidentally) used information from events after the query time during training would show inflated offline accuracy that cannot be reproduced live, since the future data simply doesn't exist yet when a real decision has to be made. This is a label-leakage bug, and it is silent: nothing about the code looks wrong unless you specifically check that every update respects t' ≤ t.

6. A raw timestamp is a huge, roughly arbitrary number with no built-in notion of relative distance the network can exploit, and it carries no periodic structure. The linear term in a Time2Vec-style encoding preserves an overall sense of "later," while the sinusoidal terms — justified by Bochner's theorem as building blocks of any translation-invariant (i.e., gap-dependent) kernel — let the model represent recurring rhythms (hourly, daily, weekly patterns) and, more importantly, let attention or decay mechanisms respond smoothly to the actual gap between two events rather than to their absolute, unbounded clock values.

Think About It

Think about this: How would you explain temporal graphs: dynamic graph evolution to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.