Source-linked AI summary
Filling the G_ap_s: Multivariate Time Series Imputation by Graph Neural Networks
Andrea Cini, Ivan Marisca, Cesare Alippi
TL;DR
Missing-value imputation in interconnected sensor time series requires methods that exploit nonlinear temporal, spatial, and relational dependencies. The paper introduces GRIN, a graph neural network architecture that learns spatio-temporal representations through message passing. GRIN achieves better reconstruction accuracy than state-of-the-art baselines across the considered scenarios, with more than 20% lower MAE than the closest baseline in one AQI setting.
Problem
Existing deep-learning imputation methods often do not explicitly model relational information or adequately represent structured spatio-temporal data in interconnected sensor networks.
Method
GRIN models multivariate time series as graph sequences and uses bidirectional recurrent processing with message-passing neural networks for neighboring-node imputation.
Results
GRIN achieves better reconstruction accuracy than state-of-the-art baselines across all considered scenarios and lowers MAE versus the closest baseline by more than 20% in out-of-sample AQI experiments.
Takeaways & Limitations
Graph neural networks provide a flexible framework for leveraging relational information and functional dependencies in multivariate time-series imputation.
Takeaways & Limitations
The framework assumes a stationary missing-data distribution and mainly evaluates the missing-at-random setting; extensions to non-stationary settings remain future work.
Abstract
from arXiv · showhide
Dealing with missing values and incomplete time series is a labor-intensive, tedious, inevitable task when handling data coming from real-world applications. Effective spatio-temporal representations would allow imputation methods to reconstruct missing temporal data by exploiting information coming from sensors at different locations. However, standard methods fall short in capturing the nonlinear time and space dependencies existing within networks of interconnected sensors and do not take full advantage of the available - and often strong - relational information. Notably, most state-of-the-art imputation methods based on deep learning do not explicitly model relational aspects and, in any case, do not exploit processing frameworks able to adequately represent structured spatio-temporal data. Conversely, graph neural networks have recently surged in popularity as both expressive and scalable tools for processing sequential data with relational inductive biases. In this work, we present the first assessment of graph neural networks in the context of multivariate time series imputation. In particular, we introduce a novel graph neural network architecture, named GRIN, which aims at reconstructing missing data in the different channels of a multivariate time series by learning spatio-temporal representations through message passing. Empirical results show that our model outperforms state-of-the-art methods in the imputation task on relevant real-world benchmarks with mean absolute error improvements often higher than 20%.
1 INTRODUCTION
Missing-value imputation is especially challenging in interconnected sensor systems, where useful reconstruction requires modeling temporal, spatial, and relational dependencies. The paper proposes GRIN, a bidirectional recurrent graph neural network that performs imputation through message passing.
- Motivation: Sensor and network failures often create sparse, localized missing values affecting only some channels at a time.This motivates methods that can reconstruct incomplete signals without losing information from functioning sensors.
- Motivation: Effective spatio-temporal imputation should use past and future observations together with measurements from spatially close neighboring sensors.
- Motivation: Deep-learning imputation methods often disregard relational information or incorporate it through simplistic sequence-model modifications.
- Contribution: GRIN represents multivariate time series as graph sequences and uses message-passing neural networks within a bidirectional recurrent architecture.Forward and backward networks process the series, while a message-passing imputation layer uses neighboring nodes.
2 RELATED WORKS
Prior time-series imputation work spans interpolation, forecasting, similarity-based, probabilistic, and recurrent deep-learning methods. However, these approaches generally do not fully exploit graph processing for relational and nonlinear spatio-temporal dependencies.
- Time series imputation: Classical imputation methods use polynomial interpolation, forecasting, nearest neighbors, expectation-maximization, linear predictors, or state-space models.
- Deep learning approaches: Deep autoregressive approaches use recurrent networks to process missing data, including GRU-D's hidden-state decay mechanism and BRITS's bidirectional architecture.
- Graph representation: Figure 1 depicts a multivariate time series as a sequence of graphs, with identified nodes and red markers for missing values.
- Limitations of prior work: Existing methods seek to exploit relational information and nonlinear spatio-temporal dependencies but do not fully use graph-processing flexibility and expressiveness.
- Graph neural networks for TSA: Graph neural networks for time-series analysis have mainly been applied by replacing sequential-model operators with graph-domain operators.Examples include GRU gates implemented with spectral GNNs or diffusion-convolutional networks.
3 PRELIMINARIES
The paper formalizes multivariate time series as sequences of weighted directed graphs whose nodes carry sensor attributes and whose edges encode relations. It defines missingness, reconstruction objectives, operational settings, and assumptions for imputation.
- Sequences of graphs: Each time step contains a weighted directed graph G_t = ⟨X_t, W_t⟩ with node attributes and edge weights representing sensor relationships.Nodes are assumed to have unique IDs for consistent processing across time.
- Assumptions: The framework mainly assumes a fixed graph topology, with W_t = W and N_t = N at every time step.The formulation can be extended to attributed-edge, global-attribute, or heterogeneous graphs.
- Sequences of graphs: A multivariate time series fits this framework by mapping each sensor channel to a node and constructing adjacency weights from relations such as correlation or kernels.If no relational information is available, the identity matrix is possible but undermines the graph formulation's purpose.
- Missing data: Missingness is represented at each step by a binary mask M_t indicating which node attributes are available.
- Assumptions: Missing-data distributions are assumed stationary, with experiments focusing mostly on missing at random, while concurrent failures and extended missing blocks are not otherwise restricted.Performance is expected to scale with the number of simultaneous faults and the duration of missing bursts.
- Imputation objective: The reconstruction objective compares imputed values against unknown complete data using an element-wise error function, requiring surrogate training objectives in practice.The paper distinguishes in-sample fitting on one sequence from out-of-sample training and evaluation on disjoint sequences.
4 GRAPH RECURRENT IMPUTATION NETWORK
GRIN models multivariate time series as graph sequences and combines recurrent message passing with bidirectional, two-stage imputation. Its spatial decoder refines predictions using local relational information before an MLP produces final imputations.
- Graph formulation: GRIN represents each multivariate time step as a graph whose nodes are channels and whose edges encode relationships among them.The model processes the resulting graph sequence with graph neural networks.
- Spatial decoder: The spatial decoder performs two consecutive imputations: a first prediction from hidden representations, followed by relational refinement using neighboring observed values and the previous hidden state.The filler operator preserves observed entries and replaces missing ones with predictions.
- Spatio-temporal encoder: Its spatio-temporal encoder processes the input and mask sequentially with a recurrent network whose gates are implemented by message-passing layers.The encoder produces node-wise, time-wise hidden representations.
- Spatial decoder: Each unidirectional module feeds second-stage imputations back into recurrent processing so the hidden representation can advance to the next graph.This creates a recurrent imputation loop rather than a one-shot reconstruction.
- Bidirectional model: The bidirectional model runs duplicated GRIN modules forward and backward, then uses an MLP to aggregate their representations into final imputations.The model is trained using reconstruction errors from all imputation stages in both directions.
5 EMPIRICAL EVALUATION
The evaluation compares GRIN with state-of-the-art baselines across air-quality, traffic, and smart-grid datasets under in-sample and out-of-sample missingness settings. GRIN achieves state-of-the-art performance across the evaluated scenarios and shows improved flexibility in handling relational structure.
- Datasets: GRIN is evaluated against state-of-the-art baselines on four datasets spanning air quality, traffic, and smart-grid applications.The air-quality evaluation includes both 437-sensor and 36-sensor datasets, while traffic uses PEMS-BAY and METR-LA.
- Results: GRIN achieves state-of-the-art performance on all evaluated datasets and scenarios.The reported benchmarks include air-quality, traffic, and energy-consumption data.
- Evaluation protocol: The experiments evaluate in-sample and out-of-sample imputation, using block-missing and point-missing settings to simulate incomplete observations.Traffic and energy datasets use out-of-sample evaluation, while air-quality datasets use both settings.
- Results: More than 20% lower MAE than the closest baseline is reported for GRIN in the air-quality out-of-sample setting.The comparison is specifically stated for AQI.
- Results: GRIN outperforms BRITS for isolated air-quality sensors and remains more accurate on the 36-dimensional dataset.The isolated sensors correspond to stations more than 40 km from any other station.
- Flexibility: The experiments also indicate that GRIN can be used when relational information is not readily available.This conclusion is drawn from the application-field experiments.
6 CONCLUSIONS
The paper presents GRIN for multivariate time-series imputation using graph neural networks and reports improved reconstruction accuracy across considered scenarios. It also identifies virtual and active sensing, non-stationary settings, and theoretical reconstruction guarantees as future directions.
- Figure 3 illustrates reconstruction from sensors removed from training, suggesting GRIN might support virtual sensing.
- GRIN imputes missing multivariate time-series data by leveraging relational information among sensor networks and functional dependencies.
- GRIN offers higher flexibility and better reconstruction accuracy than state-of-the-art baselines across all considered scenarios.
- Future work includes theoretical guarantees for accurate reconstruction, non-stationary extensions, and further evaluation in virtual and active sensing.
A DETAILED EXPERIMENTAL SETTINGS
The experiments use fixed training procedures, MAE-based GRIN optimization, common preprocessing, and implementations based on established open-source libraries and codebases.
- Models train for up to 300 epochs with early stopping, cosine learning-rate decay from 0.001, and 160 randomly sampled batches of 32 per epoch.Early stopping uses validation patience of 40 epochs.
- GRIN minimizes a loss composed of terms using the element-wise mean absolute error function.
- Data are normalized across the feature dimension, graph-wise for GRIN and node-wise for BRITS, rGAIN, and VAR.Evaluation-masked data are never used during training.
- Implementations use Python with PyTorch, NumPy, Neptune, scikit-learn, fancyimpute, and adapted or author-provided baseline code.The paper states that reproducibility code is available online.
B DATASETS
The evaluation covers air-quality, traffic, and energy-consumption datasets with graph structures derived from geographic or time-series relationships and controlled missing-data settings.
- Evaluation includes point-missing and block-missing settings, with blocks defined as bursts longer than 2 and no longer than 48 time steps.
- The datasets include air-quality recordings from 437 stations across 43 Chinese cities, traffic data from PEMS-BAY and METR-LA, and 485 CER smart-meter series.
- B.1 AIR QUALITY: Air-quality adjacency matrices use thresholded Gaussian kernels over geographic distances, with the threshold corresponding to approximately 40 km.
- Traffic experiments use 24-step input sequences, geographic-distance adjacency kernels, and a 70%/10%/20% train-validation-test split.
- CER adjacency is a k-nearest-neighbor graph with k = 10, built from week-wise correntropy similarities among time series.
C.1 SYNTHETIC DATA
The controlled synthetic experiment evaluates GRIN against BRITS on charged-particle trajectories, while additional comparisons examine matrix factorization and scalability.
- C.1 SYNTHETIC DATA: The synthetic benchmark simulates 10 charged particles moving in a 10 × 10 box under elastic collisions and Coulomb interactions.
- C.1 SYNTHETIC DATA: GRIN and BRITS receive only particle positions, without charge information, and use compact hidden representations.
- C.1 SYNTHETIC DATA: GRIN outperforms BRITS by more than an order of magnitude in MSE across the synthetic datasets, although BRITS is more accurate with varying charge.
- C.2 EMPIRICAL COMPARISON AGAINST MATRIX FACTORIZATION WITH SIDE INFORMATION: Spatial and temporal regularization improve matrix factorization over vanilla MF, but deep-learning methods and linear VAR achieve far superior reconstruction accuracy in the air-quality setting.
- C.3 SCALABILITY: Using MPNNs for recurrent-cell gates increases computational complexity by O(E) with sparse implementation or O(N^2) with dense node interactions.
C.4.1 ARCHITECTURAL ABLATIONS
The ablation study finds that both the spatial decoder and bidirectional architecture improve imputation performance, especially when missing values occur in blocks.
- The spatial decoder and bidirectional architecture improve performance in the ablation study.
- Their benefits appear particularly relevant when missing data occur in blocks.
- The reported ablation results use MAE averaged over 5 runs across Point Missing and Block Missing settings.
C.4.2 GRAPH STRUCTURE ABLATIONS
Graph-structure ablations show that adjacency constraints affect reconstruction accuracy and that spatial information contributes to multivariate time-series imputation.
- The experiments compare fully connected and edgeless adjacency matrices against the thresholded kernel on METR-LA Block Missing data.
- Graph-structure constraints affect the accuracy of missing-data imputation.
- Spatial information is relevant for the imputation task.
- BRITS performance is reported as a reference in the adjacency-matrix comparison.
C.5 SENSITIVITY ANALYSIS
The sensitivity analysis evaluates performance as missingness increases in an out-of-sample setting. GRIN outperforms BRITS across all considered sparsity scenarios, despite evaluation using masks that create a distribution shift.
- GRIN outperforms BRITS in all considered scenarios with increasing missing-data sparsity.
- Evaluation results are averaged over 5 different masks for each sparsity level in the out-of-sample setting.
- Models are trained with 60% of input data randomly masked, while evaluation uses masks with increasing sparsity.
- The increasing-sparsity evaluation causes a distribution shift relative to training.
- Figure 5 graphically presents the results reported in Table 10.