Spatiotemporal GNNs (DCRNN, Graph WaveNet, BigST)

"A single loop detector told me its own future. A thousand of them, wired into a graph, told me the traffic jam three exits down before it arrived."

A Forecasting AI Agent

Every model here answers three questions in its own way: how to move information across space, how to move it through time, and how to keep both affordable as the network grows. We take the three landmark architectures in order, because each was invented to fix a specific limitation of the one before it.

DCRNN: diffusion convolution inside a recurrent cell

What the Diffusion Convolutional Recurrent Neural Network (Li et al., 2018) does is deceptively simple: take a standard sequence-to-sequence GRU and replace every matrix multiply inside the gates with a graph diffusion convolution. Why diffusion, and not the symmetric spectral convolution you might expect, is the key idea. Traffic and flow are directed: congestion spreads upstream against the flow differently than it clears downstream. DCRNN models signal propagation as a random walk that can travel both ways, so the graph convolution over signal \(X\) with \(K\) diffusion steps is

where \(P_f\) and \(P_b\) are the forward and backward transition matrices (row-normalized by out-degree and in-degree) and \(K\) is the number of hops the signal is allowed to diffuse. How the temporal axis is handled: this convolution is dropped into the GRU update, reset, and candidate gates, giving a Diffusion Convolutional GRU. An encoder consumes the observed window, and a decoder emits the multi-step forecast, trained with scheduled sampling so the decoder gradually learns to trust its own predictions rather than the ground truth it saw during teacher forcing. On the METR-LA (Los Angeles loop detectors) and PEMS-BAY (Bay Area) benchmarks this was the design that first made deep spatiotemporal forecasting clearly beat classical methods.

Graph WaveNet: learn the graph, convolve the time

What Graph WaveNet (Wu et al., 2019) changes is both axes at once. On the spatial axis it introduces a self-adaptive adjacency matrix that is learned end to end, with no map required:

Why this matters: each node gets a learnable source embedding (a row of \(E_1\)) and target embedding (a row of \(E_2\)); their product discovers hidden dependencies directly from the data, the softmax makes each node's influences a normalized distribution, and the low rank \(c \ll N\) keeps it cheap. You can use \(\tilde{A}_{\text{adp}}\) alone (no prior graph at all) or add it to the distance graph, letting the model correct the map. How the temporal axis works is the other half of the name: instead of a recurrent cell, Graph WaveNet stacks dilated causal convolutions in the WaveNet style from Chapter 14. Doubling the dilation each layer grows the receptive field exponentially, so a long horizon is captured in a handful of layers that all run in parallel, sidestepping the sequential bottleneck of an RNN. Each block interleaves a temporal convolution with a graph convolution over the (adaptive plus fixed) adjacency, so space and time are refined in alternation.

import torch, torch.nn as nn, torch.nn.functional as F

class STBlock(nn.Module):
    """One Graph-WaveNet-style block: dilated causal conv, then adaptive graph conv."""
    def __init__(self, ch, n_nodes, emb=10, dilation=1, k=2):
        super().__init__()
        self.filt = nn.Conv2d(ch, ch, (1, 2), dilation=(1, dilation))  # gated TCN
        self.gate = nn.Conv2d(ch, ch, (1, 2), dilation=(1, dilation))
        self.E1 = nn.Parameter(torch.randn(n_nodes, emb))   # source node embeddings
        self.E2 = nn.Parameter(torch.randn(n_nodes, emb))   # target node embeddings
        self.k = k
        self.mix = nn.Conv2d(ch * (k + 1), ch, (1, 1))      # combine diffusion hops

    def forward(self, x):                                   # x: [B, ch, N, T]
        h = torch.tanh(self.filt(x)) * torch.sigmoid(self.gate(x))   # temporal axis
        A = F.softmax(F.relu(self.E1 @ self.E2.t()), dim=1)          # learned graph
        outs, z = [h], h
        for _ in range(self.k):                             # diffuse k hops in space
            z = torch.einsum('bcnt,nm->bcmt', z, A)
            outs.append(z)
        return self.mix(torch.cat(outs, dim=1))             # [B, ch, N, T-dilation]

The code above makes the coupling concrete: one block does a temporal convolution and a spatial diffusion back to back, and the adaptive adjacency A is a first-class learned parameter, not an input.

BigST: linear complexity for very large networks

When both earlier models break is scale. DCRNN's recurrence is inherently sequential, and any model that materializes a dense \(N \times N\) adjacency (including the adaptive one) costs \(O(N^2)\) memory and compute per step. At a few thousand nodes that is fine; at a city-scale road network of 20,000 or more detectors it is fatal, which is exactly the regime Section 54.5 is devoted to. What BigST (Han et al., VLDB 2024) contributes is a spatiotemporal GNN with linear complexity in the number of nodes. How it gets there has two moves. First, it decouples the expensive long-sequence feature extraction into a preprocessing stage, so the graph model consumes compact per-node representations rather than raw long histories. Second, it replaces the quadratic all-pairs spatial interaction with a linearized approximation: a random-feature kernel rewrites the softmax attention over nodes so that the \(N \times N\) matrix is never formed, turning \(O(N^2)\) into \(O(N)\). The result forecasts on road networks an order of magnitude larger than the classic benchmarks while keeping accuracy competitive with the quadratic models, on a single GPU.

Choosing among the three

When to reach for each is a function of graph trust and network size. Use a DCRNN-style diffusion recurrent model when you have a trustworthy directed physical graph (a pipe network, a validated road map) and a few thousand nodes or fewer: the geometric prior is an asset and the recurrence is affordable. Use Graph WaveNet when your map is missing, incomplete, or suspect, or when you want the model to discover latent couplings; the adaptive adjacency plus parallel dilated convolutions is the most broadly effective mid-scale default. Reach for BigST or another linear-complexity design when \(N\) runs into the tens of thousands and a dense adjacency will not fit in memory. Across all three, the leakage discipline of Chapter 5 is non-negotiable: split strictly along time, never shuffle windows across the train and test boundary, and normalize using only training-set statistics, or every reported error is optimistic.

What's Next

In Section 54.4, we turn the same message-passing machinery from forecasting to diagnosis. When a fault appears in a sensor network, the pattern of how anomalies propagate along the graph edges is itself the evidence: message passing can localize the failing node, distinguishing a broken sensor from a real physical event rippling through its neighbors.