PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Reconstruct Missing Data from Spatiotemporal Graphs with Sparse Observations

Ivan Marisca, Andrea Cini, Cesare Alippi

arXiv:2205.13479v2cs.LGcs.AI

TL;DR

Sparse spatiotemporal time series make imputation from available observations a challenging task. SPIN uses sparse spatiotemporal attention to propagate valid observations jointly across time and space, and the paper reports wide-margin gains over state-of-the-art imputation methods in highly sparse settings.

  • Problem

    Spatiotemporal time series often contain incomplete, irregularly sampled observations, motivating imputation from the available data.

    Source: §1 · p. 2, §3 · p. 4

  • Method

    SPIN is a graph-based architecture that uses sparse spatiotemporal attention to propagate valid observations jointly through points in time and space.

    Source: §1 · p. 2, §6 · p. 10

  • Results

    SPIN outperforms state-of-the-art imputation methods by a wide margin in highly sparse settings; on point-missing data, it performs on par with the state of the art.

    Source: §5.2 · p. 9, §6 · p. 10

  • Takeaways & Limitations

    Joint propagation lets SPIN carry information between far-apart observations without intermediate autoregressive predictions.

    Source: §5.2 · p. 9, §6 · p. 10

    The framework can handle dynamic relationships, but the paper mostly focuses on static topologies and assumes sensor-level covariates are available at each time step.

    Source: §3 · p. 3

Abstract

from arXiv · show

Modeling multivariate time series as temporal signals over a (possibly dynamic) graph is an effective representational framework that allows for developing models for time series analysis. In fact, discrete sequences of graphs can be processed by autoregressive graph neural networks to recursively learn representations at each discrete point in time and space. Spatiotemporal graphs are often highly sparse, with time series characterized by multiple, concurrent, and long sequences of missing data, e.g., due to the unreliable underlying sensor network. In this context, autoregressive models can be brittle and exhibit unstable learning dynamics. The objective of this paper is, then, to tackle the problem of learning effective models to reconstruct, i.e., impute, missing data points by conditioning the reconstruction only on the available observations. In particular, we propose a novel class of attention-based architectures that, given a set of highly sparse discrete observations, learn a representation for points in time and space by exploiting a spatiotemporal propagation architecture aligned with the imputation task. Representations are trained end-to-end to reconstruct observations w.r.t. the corresponding sensor and its neighboring nodes. Compared to the state of the art, our model handles sparse data without propagating prediction errors or requiring a bidirectional model to encode forward and backward time dependencies. Empirical results on representative benchmarks show the effectiveness of the proposed method.

1 Introduction

Spatiotemporal graphs encode temporal and spatial structure, but real sensor data are often incomplete, and autoregressive imputation can compound errors in highly sparse settings. The paper proposes task-aligned attention and a graph architecture to reconstruct missing observations from available data.

1 Introduction

  • Spatiotemporal graph neural networks encode spatial and temporal dependencies as architectural biases for processing multivariate time series.Graphs represent spatial relationships among sensors.Source: §1 · p. 1
  • Autoregressive imputation can compound errors in highly sparse data, motivating an architecture that reconstructs missing observations from available data.The introduction notes that propagating imputed values through space and time alongside noisy observations may exacerbate error accumulation.Source: §1 · p. 2
  • SPIN uses sparse spatiotemporal attention to propagate observed values and learn predictive representations for missing observations across the graph.The approach is designed to avoid propagating biased representations typical of autoregressive methods and to reconstruct observations at arbitrary nodes.Source: §1 · p. 2
  • The proposed graph neural network incorporates inductive biases tailored to multivariate time-series imputation.The paper also reports empirical assessment against existing approaches, particularly in highly sparse settings.Source: §1 · p. 2

2 Related works

Prior imputation work spans statistical, matrix-factorization, recurrent, generative, attention-based, and graph-based approaches. The paper positions its contribution against methods that do not explicitly model spatial dependencies or that remain vulnerable to compounding errors.

2 Related works

  • Deep autoregressive models, including bidirectional-RNN BRITS and graph-based GRIN, are prominent imputation approaches, but the paper argues recurrent graph states can still compound errors.BRITS uses one-step-ahead forecasting and linear regression for spatial information; GRIN combines a bidirectional graph RNN with a message-passing spatial decoder.Source: §2 · p. 3
  • Several attention-based imputation methods do not explicitly account for spatial dependencies within a graph-processing framework.The paper also notes continuous-time, hierarchical, and application-specific graph-based approaches.Source: §2 · p. 3
  • Related attention work includes anisotropic graph filters and spatiotemporal forecasting, while TraverseNet uses spatiotemporal autoregressive attention to exchange messages between nodes.Attention has also been used for incomplete-data pretraining and for reconstructing missing features in static graphs.Source: §2 · p. 3

3 Preliminaries

The preliminaries represent sensor observations as a sequence of spatiotemporal graphs with availability masks. Imputation estimates the complete sequence by minimizing reconstruction error, using a surrogate objective because the complete data are unknown.

3 Preliminaries

  • Each time step is represented by sensor measurements and covariates on a graph whose weighted edges encode relationships among sensors.The graph is represented by an adjacency matrix, and observations are organized as a sequence of spatiotemporal graph triplets.Source: §3 · p. 3
  • The framework can represent dynamic relationships, though the paper mostly focuses on static topology; sensor-level covariates serve as spatiotemporal coordinates.Those coordinates are assumed available at each node and time step.Source: §3 · p. 3
  • A binary availability mask represents missing measurements, which may arise in multi-step sensor faults or across a network subregion.Missingness is treated at the sensor and time-step level.Source: §3 · pp. 3–4
  • Multivariate time-series imputation estimates the complete sequence by minimizing reconstruction error, using a surrogate objective because the complete sequence is unavailable.The objective uses an element-wise error function, and missingness can be simulated to compute reconstruction error.Source: §3 · p. 4

4 Learning representations from sparse spatiotemporal data

SPIN aligns graph-attention propagation with reconstruction from observed points, learning representations for target node-time locations. Its sparse attention aggregates valid observations from a node and its neighbors, with staged propagation and optional complexity-reduction strategies.

Model overview

  • Modular approaches can incur computational overhead and compounding prediction errors, while masking faulty sensors can compromise message passing in highly sparse observations.The paper identifies these concerns as challenges for existing approaches to sparse spatiotemporal data.Source: §4 · p. 4
  • SPIN learns representations for discrete points in spatiotemporal graphs from disjoint observed and target sets, then uses a nonlinear readout to produce imputations.The architecture is designed to align its structure with the reconstruction task.Source: §4 · pp. 4, 6

Sparse spatiotemporal attention

  • The sparse attention layer updates each node-time representation using observed temporal data from that node and its neighboring nodes.It combines inter-node temporal cross-attention with intra-node temporal self-attention.Source: §4 · pp. 5–6

Two-phase propagation

  • SPIN masks target-set tokens during early propagation to pass only valid information, then unlocks paths so learned representations can reach higher-order neighborhoods.The hyperparameter η controls how many layers use masked connections; the second phase propagates learned representations, not unavailable observations.Source: §4 · p. 6

Graph subsampling and hierarchical attention

  • Training on sampled k-hop subgraphs centered on n targets reduces computation by acting on n and k, while hierarchical attention uses K hub nodes to reduce complexity to O((Nmax + Emax)KT), with K ≪ T.The hub approach introduces an information bottleneck.Source: §4 · p. 7

Spatiotemporal positional encoding

  • SPIN's positional encoding combines temporal and spatial encodings independently of observations, allowing inference at target points.Temporal encodings use sine and cosine transforms of time; each node has a learnable spatial vector, combined by a nonlinear transformation.Source: §4 · p. 7

5 Empirical evaluation

The evaluation compares SPIN and SPIN-H with imputation baselines on real-world sensor datasets under standard and increasingly sparse missingness. SPIN-based models rank best across tested sparsity levels, while on standard settings they outperform baselines in almost all scenarios.

5.1 Experimental setting

  • The study reports mean absolute error averaged across imputation windows in an out-of-sample setting with disjoint training and test sets.Traffic data are split sequentially into training, validation, and test sets.Source: §5.1 · pp. 7–8
  • The evaluation uses three real-world sensor datasets, including traffic benchmarks with simulated point or block missingness and air-quality data with about 36% missingness in AQI-36.The full AQI dataset has 25.67% missing values and an evaluation mask that follows prior-month missingness patterns.Source: §5.1 · p. 8
  • Baselines include graph-based GRIN, a spatiotemporal Transformer, SAITS, BRITS, rGAIN, and statistical, matrix-factorization, and mean-imputation methods.The comparison also includes MEAN, KNN, MF, MICE, and VAR.Source: §5.1 · p. 8
  • Attention-based operations can run in parallel, whereas GRIN processes the sequence sequentially, with a consequent slowdown.The supplied complexity passages also compare the asymptotic complexities of SPIN, SPIN-H, the Transformer, and GRIN.Source: §5.1 · pp. 8–9

5.2 Results

  • Both SPIN methods outperform baselines in almost all standard scenarios, with clearer gains for block missingness and results on par with state of the art for point missingness.SPIN performs better than the spatiotemporal Transformer except on AQI-36; SPIN-H is generally on par with SPIN and can be a lightweight alternative.Source: Table 1 · p. 8, §5.2 · p. 9
  • Across point-missing sparsity levels and block-missing failure probabilities, SPIN-based models rank best in MAE averaged over 5 evaluation masks; SPIN and SPIN-H deteriorate more slowly than baselines as sparsity increases.Source: Table 2 · p. 9, Table 3 · p. 9, §5.2 · p. 10

6 Conclusion and Future Works

The conclusion presents SPIN as a graph-based method for reconstructing missing observations in sparse spatiotemporal time series. It highlights sparse spatiotemporal and hierarchical attention, strong results in highly sparse settings, and a possible supervision shortfall in extremely sparse training.

6 Conclusion and Future Works

  • SPIN uses sparse spatiotemporal attention to propagate valid observations jointly through discrete points in time and space.The paper presents this mechanism as a way to overcome major limitations of autoregressive methods.Source: §6 · p. 10
  • A hierarchical attention mechanism can drastically reduce the approach's time and space complexities.Source: §6 · p. 10
  • The authors report wide-margin improvements over state-of-the-art imputation methods in highly sparse settings, but note that extremely sparse training can reduce supervision and slow learning.They suggest an auxiliary learning task as a possible future response.Source: §6 · p. 10

A Detailed experimental setup

The appendix describes SPIN training, its hyperparameters, and implementation details. Training supervises layerwise imputations using observations withheld from each minibatch input, while evaluation-masked data are never used for training.

A Detailed experimental setup

  • The experimental setup follows Cini et al. [4] and uses their reported results whenever possible.The appendix refers readers to [4] for baseline details.Source: A Detailed experimental setup · p. 15
  • SPIN uses four layers, with three masked-connection layers, hidden size 32, and two-layer MLPs of hidden size 32; SPIN-H uses five layers and four hubs per node.SPIN-H uses hub size 128; hyperparameters were selected from a small validation-set search, and the authors expect further tuning could improve performance.Source: A Detailed experimental setup · p. 15
  • The loss supervises imputation at each layer using randomly withheld input observations, while evaluation-masked values are never used for training.The removed-data ratio is sampled from 0.2, 0.5, or 0.8 for each minibatch sample.Source: A Detailed experimental setup · p. 15
  • The spatiotemporal Transformer uses five layers and four attention heads, while SAITS uses author-provided code and validation-set random search for hyperparameter selection.Source: A Detailed experimental setup · p. 15
  • The models were implemented in Python with PyTorch, PyG, and Torch Spatiotemporal, and experiment tracking used Neptune.SPIN training took 4–26 hours on an NVIDIA A100 node; SPIN-H took 4–14 hours on a Titan V node, depending on dataset.Source: A Detailed experimental setup · p. 15

B Datasets

The appendix specifies dataset windows, data splitting, preprocessing, and construction of the sensor graph. It uses distance-based adjacency and normalizes features to zero mean and unit variance.

B Datasets

  • The experiments use 24-step windows, except AQI-36, which uses 36 steps; traffic data are split sequentially into 70% training, 10% validation, and 20% test.For air-quality data, the test set consists of March, June, September, and December.Source: B Datasets · p. 15
  • Data are normalized across the feature dimension to zero mean and unit variance, graph-wise for graph-based models.Source: B Datasets · p. 16
  • Sensor adjacency is derived from pairwise geographical distances using a thresholded Gaussian kernel.The kernel uses a shape parameter and a threshold.Source: B Datasets · p. 16

C Virtual sensing

Figure 3 visualizes SPIN-H imputations for completely missing sequences at nodes masked during training, averaged over five independent runs.

C Virtual sensing

  • Figure 3 visualizes five-run-average SPIN-H imputations for completely missing sequences at nodes masked during training.Source: Figure 3 · p. 16

D Ablation study

The ablation study removes spatiotemporal cross-attention and temporal self-attention from SPIN-H; both components contribute positively to imputation accuracy across the evaluated settings.

D Ablation study

  • Removing either spatiotemporal cross-attention or temporal self-attention from SPIN-H reduces imputation accuracy.The ablation evaluates MAE and MRE on METR-LA (Point missing) and AQI-36.Source: D Ablation study · pp. 16–17
  • The ablation compares versions without spatiotemporal cross-attention and without temporal self-attention against SPIN, SPIN-H, and the Transformer.Source: D Ablation study · p. 16
  • METR-LA (Point missing) uses uniformly random masking, whereas AQI-36 uses its empirical missing-data distribution.Source: D Ablation study · p. 17
Loading 2205.13479v2…