Sequential, Temporal and Graph Machine Learning

Introduction

Many machine-learning problems are not independent and identically distributed. A sensor reading depends on earlier readings, an event may be caused by a preceding event, and a recommendation depends on relationships among users and items. Sequential, temporal and graph machine learning addresses these dependencies explicitly.

A useful distinction is:

• Sequence data: observations ordered by position or time, such as words, transactions or physiological measurements.
• Time-series data: observations indexed by time, often with sampling intervals, seasonality and missing timestamps.
• Relational or graph data: entities connected by edges, such as customers, roads, web pages or proteins.
• Temporal graphs: graphs whose nodes, edges, attributes or topology change over time.

The central modelling challenge is to preserve information from the past without allowing leakage from the future, while learning representations that support forecasting, event prediction and network analytics.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Formulate sequential problems using state-space models and recurrent networks.

2. Derive and interpret the Kalman filtering update under linear-Gaussian assumptions.

3. Design temporal-transformer workflows using causal attention, positional information and time-aware validation.

4. Explain graph convolution, message passing and temporal graph learning.

5. Select losses, evaluation metrics and negative-sampling strategies for graph prediction.

6. Build an end-to-end modelling and deployment strategy while accounting for leakage, drift, scalability, privacy and fairness.

1. A Unified View of Sequential and Relational Learning

Let observations be $y_{1:T}=(y_1,,y_T)$ and covariates be $x_{1:T}$. A forecasting model estimates

\[

p(y_{t+1:t+h}\mid y_{1:t},x_{1:t+h}).

\]

The conditioning set must contain only information available at prediction time. For event prediction, the target may be $P(e_{t+\Delta}=1\mid \mathcal H_t)$, where $\mathcal H_t$ is the history up to time $t$. For a graph $G=(V,E)$, node prediction estimates $P(y_v\mid G,X)$, while link prediction estimates $P((u,v)\in E)$ or the probability that a future interaction occurs.

Three dependency mechanisms commonly appear:

1. Latent state dependence: a hidden state summarizes the past.

2. Attention dependence: the model learns which prior positions matter.

3. Topological dependence: information propagates through edges.

These mechanisms can be combined. For example, a fraud system may use a recurrent representation of a merchant's transaction history, a transformer over recent events, and a graph representation of connected accounts.

2. State-Space Models and Bayesian Filtering

A discrete state-space model separates an unobserved state from measurements:

\[

z_t=F_tz_{t-1}+B_tu_t+w_t,\qquad y_t=H_tz_t+v_t,

\]

where $z_t$ is the latent state, $u_t$ an optional input, $F_t$ the transition matrix, $B_t$ the control matrix, $H_t$ the observation matrix, and $w_t,v_t$ process and observation noise. In the linear-Gaussian case, $w_t\sim\mathcal N(0,Q_t)$ and $v_t\sim\mathcal N(0,R_t)$, independently. The Kalman filter is exact for the posterior mean and covariance in this special case.

Prediction and update

Given filtered estimates $(\hat z_{t-1|t-1},P_{t-1|t-1})$:

\[

\hat z_{t|t-1}=F_t\hat z_{t-1|t-1}+B_tu_t,

\]

\[

P_{t|t-1}=F_tP_{t-1|t-1}F_t^\top+Q_t.

\]

The innovation and its covariance are

\[

r_t=y_t-H_t\hat z_{t|t-1},\qquad S_t=H_tP_{t|t-1}H_t^\top+R_t.

\]

The Kalman gain, updated state and updated covariance are

\[

K_t=P_{t|t-1}H_t^\top S_t^{-1},

\]

\[

\hat z_{t|t}=\hat z_{t|t-1}+K_tr_t,

\]

\[

P_{t|t}=(I-K_tH_t)P_{t|t-1}.

\]

The Joseph form, often numerically safer, is

\[

P_{t|t}=(I-KH)P^-(I-KH)^\top+KRK^\top.

\]

Worked scalar example

Suppose a scalar state has prior estimate $\hat z^-=10$ and prior variance $P^-=9$. A measurement is $y=13$, the observation model is $y=z+v$ ($H=1$), and measurement variance is $R=6$. Then

\[

K=\frac{P^-}{P^-+R}=\frac{9}{15}=0.6,

\]

and the innovation is $13-10=3$. Therefore,

\[

\hat z^+=10+0.6(3)=11.8.

\]

The posterior variance is

\[

P^+=(1-0.6)9=3.6.

\]

The estimate moves toward the observation, but not all the way, because measurement noise is substantial. The Kalman gain is dimensionless only when state and observation use compatible units; in general its units follow from $P^-H^\top S^{-1}$.

For nonlinear dynamics or observations, the extended Kalman filter linearizes locally, the unscented Kalman filter propagates sigma points, and particle filters approximate the posterior with weighted samples. These methods can fail when nonlinearities are severe, distributions are multimodal, or noise is non-Gaussian.

Learning state-space models

When $F,H,Q,R$ are unknown, they can be estimated using maximum likelihood, expectation-maximization, Bayesian inference or gradient-based neural parameterizations. A practical workflow is to standardize continuous variables, preserve chronological order, initialize covariances with positive-definite matrices, and monitor innovation residuals. Residuals should be approximately zero mean and, under a correct model, uncorrelated over time. The normalized innovation squared can be used as a consistency diagnostic.

3. Recurrent Neural Networks

An RNN updates a hidden state using

\[

h_t=\phi(W_xx_t+W_hh_{t-1}+b),\qquad \hat y_t=g(W_yh_t+c).

\]

Backpropagation through time unrolls this recurrence. Repeated multiplication by Jacobians can cause vanishing or exploding gradients. LSTM cells address this using input, forget and output gates:

\[

i_t=\sigma(W_ix_t+U_ih_{t-1}+b_i),\quad f_t=\sigma(W_fx_t+U_fh_{t-1}+b_f),

\]

\[

o_t=\sigma(W_ox_t+U_oh_{t-1}+b_o),\quad \tilde c_t=\tanh(W_cx_t+U_ch_{t-1}+b_c),

\]

\[

c_t=f_t\odot c_{t-1}+i_t\odot\tilde c_t,\qquad h_t=o_t\odot\tanh(c_t).

\]

GRUs use fewer gates and often provide a useful accuracy-efficiency trade-off. Bidirectional RNNs are suitable for offline sequence labelling but are inappropriate for strictly causal forecasting if the reverse direction accesses future observations.

Training practice

A sequence dataset is usually divided into windows of length $L$: $(x_{t-L+1:t},y_{t+1:t+h})$. Windows must be constructed after the chronological split, or overlapping windows can leak validation information. Teacher forcing supplies the true previous output during multi-step training; inference instead feeds predictions, creating exposure bias. Scheduled sampling, direct multi-horizon heads and probabilistic sequence objectives are possible remedies.

For Gaussian forecasts, a heteroscedastic negative log-likelihood is preferable to a loss that predicts only a mean:

\[

\mathcal L_t=\frac12\left[\log(2\pi\sigma_t^2)+\frac{(y_t-\mu_t)^2}{\sigma_t^2}\right],

\]

with $\sigma_t^2>0$ enforced, for example, by a softplus output. Quantile regression uses the pinball loss and produces calibrated intervals without assuming Gaussian errors. Gradient clipping, recurrent dropout, early stopping based on temporal validation, and learning-rate scheduling are standard safeguards.

4. Temporal Transformers

Self-attention maps queries, keys and values to

\[

\operatorname{Attention}(Q,K,V)=\operatorname{softmax}\left(\frac{QK^\top}{\sqrt{d_k}}+M\right)V,

\]

where $M$ is a mask. For causal forecasting, $M_{ij}=-\infty$ when key position $j>i$, preventing future access. Multi-head attention learns several dependency patterns in parallel, followed by residual connections, normalization and a feed-forward network.

Transformers require order or time information because attention alone is permutation invariant. Absolute positional embeddings, relative positions, elapsed-time encodings and calendar features are alternatives. For irregular events, the time gap $\Delta t$ should not be silently treated as one equal step; it may be embedded or used in a decay mechanism.

A practical temporal-transformer workflow

1. Define the information boundary. Specify the forecast origin, horizon and allowable features. Remove post-outcome fields and delayed labels.

2. Create an event table. Store entity ID, event timestamp, value/features, event type and label timestamp. Sort by event time and resolve duplicate or out-of-order records.

3. Split chronologically. Use rolling-origin validation: train on $[1,t_1]$, validate on $(t_1,t_2]$, and test on $(t_2,t_3]$. Fit scalers and imputers on training data only.

4. Tokenize and encode. A token may represent a time step, event, patch of a long signal or entity-time pair. Add masks for padding and missingness, and encode time gaps and calendar effects.

5. Choose context and horizon. Long contexts increase memory approximately quadratically for standard attention. Downsampling, sparse attention, pooling, recurrent memory or linear-attention variants may be required.

6. Train with an appropriate objective. Use MSE or MAE for point forecasts, likelihood or quantile loss for uncertainty, and weighted losses when rare events matter. Use AdamW, warm-up when needed, gradient clipping and checkpoint selection by validation performance.

7. Evaluate operationally. Report horizon-specific MAE/RMSE, scale-free error such as MASE where meaningful, calibration of prediction intervals, and performance by season, entity and regime. For event classification include PR-AUC, recall at a fixed alert budget and lead time.

8. Stress test deployment. Test missing events, delayed data, distribution shifts, long sequences and stale features. Log the exact feature timestamp and model version.

Attention weights should not automatically be interpreted as causal explanations. Attribution, perturbation tests and domain validation are needed.

5. Graph Neural Networks

A graph is $G=(V,E,A)$, with node features $X\in\mathbb R^{|V|\times d}$ and adjacency matrix $A$. A common graph convolutional layer is

\[

H^{(l+1)}=\sigma(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}H^{(l)}W^{(l)}),

\]

where $\tilde A=A+I$ adds self-loops and $\tilde D_{ii}=\sum_j\tilde A_{ij}$. The normalization prevents high-degree nodes from dominating and stabilizes scale. This is a particular GCN layer, not a universal definition of graph convolution.

Message-passing networks generalize the idea:

\[

m_v^{(l)}=\operatorname{AGG}^{(l)}(\{\phi^{(l)}(h_v^{(l)},h_u^{(l)},e_{uv}):u\in\mathcal N(v)\}),

\]

\[

h_v^{(l+1)}=\psi^{(l)}(h_v^{(l)},m_v^{(l)}).

\]

Aggregation should be permutation invariant. Graph attention networks learn edge-specific weights; graph isomorphism networks use expressive sum aggregation; relational GNNs distinguish edge types.

Tasks and losses

• Node classification: cross-entropy, focal loss or class-weighted loss on labelled nodes.
• Graph classification: pool node embeddings using sum, mean, attention or a virtual graph token.
• Link prediction: encode nodes to $z_u,z_v$ and score a pair, for example $s(u,v)=z_u^\top z_v$ or an MLP over $[z_u,z_v,z_u\odot z_v]$.
• Edge classification: predict a type or event label for an existing edge.

For binary link prediction with positive set $E^+$ and negative set $E^-$, a weighted logistic loss is

\[

\mathcal L=-\sum_{(u,v)\in E^+}\log\sigma(s_{uv})-\lambda\sum_{(u,v)\in E^-}\log(1-\sigma(s_{uv})).

\]

The negative set must be defined carefully. Uniform random non-edges may be too easy; degree-based, hard-negative or time-aware sampling is often better. For implicit feedback, sampled softmax, Bayesian personalized ranking, or contrastive losses are alternatives. If the graph is temporal, an edge that appears later must not be used as a negative at an earlier time. Evaluation should use time-respecting candidate sets and distinguish transductive from inductive settings.

Graph training implementation

A mini-batch may sample neighbourhoods layer by layer (GraphSAGE), sample edges and construct local subgraphs, or use cluster partitions. Full-batch training is simple but can exceed memory. For large graphs, neighbour sampling, feature caching and sparse matrix operations are essential. Avoid sampling a validation node's future neighbours into its training computation graph. For link prediction, split edges before message passing when the task requires predicting unseen edges; otherwise the adjacency itself reveals the answer.

Oversmoothing occurs when repeated propagation makes node representations similar. Residual connections, normalization, jumping knowledge and shallow architectures help. Oversquashing occurs when exponentially many distant signals are compressed into a fixed-size vector; rewiring, positional encodings and scalable long-range mechanisms can help.

6. Temporal and Dynamic Graphs

A dynamic graph may be represented as snapshots $G_t=(V_t,E_t,X_t)$ or as an event stream $(u_i,v_i,t_i,e_i)$. Snapshot GNNs apply spatial message passing at each time and then use an RNN or temporal convolution:

\[

H_t=\operatorname{GNN}(G_t,X_t),\qquad S_t=\operatorname{RNN}(H_t,S_{t-1}).

\]

Temporal graph attention can attend to prior interactions, while continuous-time models update node memory at event times. The choice depends on whether time is naturally discrete, whether events are sparse, and whether prediction is node-, edge- or graph-level.

For future-link prediction, a sound protocol is: train on events up to $t_1$, validate on $(t_1,t_2]$, and test after $t_2$. At each evaluation time, sample negatives from pairs that have not yet interacted by that time. Metrics include ROC-AUC, PR-AUC, mean reciprocal rank, Hits@K and precision@K. Ranking metrics are more informative when the positive class is extremely sparse.

7. Integrated Case: Illustrative Payment-Network Monitoring

Background and problem

Consider a fictional payment platform with merchants, customer accounts and devices as nodes. Transactions are timestamped directed edges. The platform wants early detection of account takeover and coordinated fraud, while limiting false alerts.

Analysis

A static classifier misses burst behaviour and newly formed rings. A temporal model is needed because an account's risk depends on recent velocity, time gaps and prior alerts. A graph model is needed because suspicious accounts may share devices, addresses or merchants. Labels are delayed and highly imbalanced.

Approach

The engineering team constructs features using only data available at each transaction time: rolling counts, amount statistics, device reuse and graph neighbourhood summaries. A temporal transformer encodes the last 128 events per account, with causal masking and time-gap embeddings. A relational message-passing network encodes account-device-merchant connections. Their representations are concatenated with transaction features and passed to an event-risk head.

Training uses chronological rolling splits. The classification objective combines weighted binary cross-entropy with a ranking term that compares fraudulent events against sampled legitimate events. Negative examples are sampled from transactions occurring in the same time window, rather than from an unrealistically easy historical pool. Threshold selection is based on recall at the operational alert budget, not accuracy. Calibration is checked on a later validation period.

Outcome and governance

In this illustrative case, the integrated model improves early recall at a fixed daily investigation capacity, but performance falls during a new promotional campaign. Monitoring identifies covariate drift in transaction volume and device-sharing patterns. The system therefore uses drift alarms, periodic retraining, analyst feedback and a fallback rules engine.

Sensitive attributes are excluded unless legally and ethically justified; nevertheless, proxy discrimination may remain in graph structure. Access controls, retention limits, explanation records, human review and audit logs are required. Automated account restriction should have an appeal process and should not rely on an uncalibrated score alone.

Learning points

Temporal validation is as important as architecture. Graph construction can encode leakage. Rare-event metrics must reflect operational capacity. A sophisticated model does not remove the need for governance, monitoring and human accountability.

8. Model Selection, Evaluation and Deployment

Use a persistence or seasonal-naive baseline for forecasting, logistic or gradient-boosted baselines for events, and degree/common-neighbour heuristics for link prediction. A complex model is justified only by reproducible improvement under the same information boundary.

For forecasting, report MAE, RMSE, weighted errors and interval coverage. RMSE penalizes large errors more strongly than MAE. For classification, ROC-AUC can be misleading under severe imbalance; PR-AUC, precision at capacity, recall, calibration and cost-weighted utility are often preferable. For graphs, report results over multiple negative samples and random seeds, and specify whether test nodes or edges were visible during training.

Common failure modes include future leakage, random rather than temporal splitting, inappropriate imputation, hidden duplicates, nonstationary labels, overly easy negatives, graph disconnects caused by preprocessing, and evaluation on a graph whose test edges were used for message passing. Reproducibility requires versioned data snapshots, fixed split definitions, random seeds, feature-time metadata and documented hyperparameter searches.

Contemporary directions include neural controlled differential equations for irregular streams, foundation models for long contexts, retrieval-augmented temporal systems, graph transformers, self-supervised masked-event learning, causal representation learning and privacy-preserving federated graph learning. These approaches remain subject to computational cost, distribution shift, interpretability and sound evaluation.

Chapter Summary

Sequential models represent dependence through latent states, recurrence or attention. State-space models provide interpretable probabilistic filtering, with the Kalman filter being exact only under linear-Gaussian assumptions. RNNs and gated variants learn nonlinear sequential representations but require careful handling of gradient stability, teacher forcing and multi-step error. Temporal transformers model long-range dependencies through masked attention and require explicit time representations, leakage-safe windows and chronological validation. GNNs learn from topology through permutation-invariant message passing; link prediction requires carefully designed losses, negative sampling and temporal splits. Dynamic graphs combine spatial propagation with temporal evolution. Across all approaches, baselines, uncertainty, calibration, drift monitoring, scalability, privacy and fairness are essential to reliable deployment.

Key Terms

State-space model: A probabilistic model separating latent state dynamics from observations.

Kalman filter: An exact recursive Bayesian estimator for linear-Gaussian systems.

Innovation: The difference between an observation and its predicted value.

Recurrent neural network: A neural model that updates a hidden state sequentially.

LSTM: A gated recurrent architecture designed to preserve information over long intervals.

Teacher forcing: Training a decoder with the true previous output.

Causal mask: An attention mask preventing access to future positions.

Temporal transformer: A transformer adapted to ordered or timestamped data.

Message passing: Iterative exchange and aggregation of information across graph edges.

Graph convolution: A graph-local feature transformation, often using normalized adjacency.

Node embedding: A vector representation learned for a graph node.

Link prediction: Estimation of an existing or future relationship between entities.

Negative sampling: Selecting non-positive examples for efficient discriminative training.

Temporal graph: A graph whose structure or attributes evolve over time.

Oversmoothing: Loss of node distinguishability after excessive graph propagation.

Oversquashing: Compression of many distant signals into limited representation capacity.

Concept drift: Change in the data-generating process affecting model performance.

Calibration: Agreement between predicted probabilities and observed frequencies.

Rolling-origin validation: Repeated chronological train-validation evaluation.

Information leakage: Use of information unavailable at the prediction time.

Review Questions

Short Answer Questions

1. What assumptions make the Kalman filter an exact Bayesian estimator?

2. Why is causal masking necessary in temporal forecasting?

3. Distinguish oversmoothing from oversquashing in GNNs.

4. Why can PR-AUC be more informative than accuracy for fraud detection?

5. What is the purpose of negative sampling in link prediction?

Long Answer Questions

1. Derive the scalar Kalman update and explain the effect of prior and measurement variance.

2. Compare RNNs, LSTMs and temporal transformers for long irregular sequences.

3. Explain a leakage-safe workflow for temporal-transformer forecasting.

4. Describe message passing, GCN normalization and scalability techniques for large graphs.

5. Discuss ethical, privacy and governance risks in temporal graph analytics.

Analytical / Application Questions

1. Design a rolling-origin evaluation protocol for predicting next-day energy demand with missing and irregular observations.

2. Propose a temporal link-prediction experiment for a social network, including negative sampling, losses, metrics and leakage controls.

3. A fraud model has high ROC-AUC but low precision at the investigation team's fixed capacity. Diagnose possible causes and recommend model, threshold and monitoring changes.

Multiple Choice Questions with Answers

Question 1

In the scalar Kalman example with prior estimate 10, prior variance 9, observation 13 and measurement variance 6, what is the updated estimate?

A. 10.60

B. 11.80

C. 12.40

D. 13.00

Correct Answer: B. 11.80

Question 2

Which condition makes the standard Kalman filter exact for the posterior mean and covariance?

A. Any nonlinear dynamics with Gaussian noise

B. Linear dynamics and observations with Gaussian noise

C. Discrete observations with no noise

D. Only stationary time series

Correct Answer: B. Linear dynamics and observations with Gaussian noise

Question 3

What does a causal attention mask prevent?

A. Use of node degrees

B. Attention to future positions

C. Use of positional information

D. Gradient propagation

Correct Answer: B. Attention to future positions

Question 4

Which loss is directly suitable for a Gaussian forecast with predicted mean and variance?

A. Gaussian negative log-likelihood

B. Hinge loss only

C. Unweighted accuracy

D. Jaccard loss only

Correct Answer: A. Gaussian negative log-likelihood

Question 5

Why are self-loops commonly added in a GCN?

A. To remove all graph edges

B. To preserve a node's own representation during aggregation

C. To guarantee a directed acyclic graph

D. To make every node have degree zero

Correct Answer: B. To preserve a node's own representation during aggregation

Question 6

Which practice is most appropriate for temporal link prediction?

A. Use future edges as negatives for earlier times

B. Randomly shuffle all events before splitting

C. Evaluate with time-respecting positives and negatives

D. Include test edges in training message passing without qualification

Correct Answer: C. Evaluate with time-respecting positives and negatives

Question 7

What is oversmoothing in a deep message-passing GNN?

A. Node representations become increasingly indistinguishable

B. The graph gains new nodes automatically

C. All edges become labelled

D. Training uses too few negative samples

Correct Answer: A. Node representations become increasingly indistinguishable

Question 8

Which metric is especially useful when ranking rare future interactions?

A. Mean reciprocal rank

B. Mean input magnitude

C. Training batch size

D. Number of model parameters

Correct Answer: A. Mean reciprocal rank

Question 9

Which action best prevents scaler-induced temporal leakage?

A. Fit the scaler on the complete dataset

B. Fit the scaler separately using future test labels

C. Fit the scaler on training data only

D. Fit the scaler after deployment

Correct Answer: C. Fit the scaler on training data only

Question 10

What is the principal purpose of hard-negative sampling in link prediction?

A. To remove all positive edges

B. To create more challenging non-edge examples

C. To guarantee perfect calibration

D. To eliminate the need for validation

Correct Answer: B. To create more challenging non-edge examples