Source-linked AI summary
ImputeFormer: Low Rankness-Induced Transformers for Generalizable Spatiotemporal Imputation
Tong Nie, Guoyang Qin, Wei Ma, Yuewen Mei, Jian Sun
TL;DR
Missing spatiotemporal observations are a persistent imputation challenge. ImputeFormer incorporates low-rank structure into a Transformer, and the paper reports strong accuracy, efficiency, generalizability, versatility, and interpretability across benchmarks.
Problem
Missing observations are common in spatiotemporal monitoring, motivating models that can impute values from limited observations.
Source: §1 · p. 1Method
Results
ImputeFormer consistently achieves state-of-the-art imputation accuracy while exhibiting high computational efficiency, generalizability, versatility, and interpretability.
Source: §6 · p. 9Takeaways & Limitations
The conclusion presents ImputeFormer as having potential to advance research on spatiotemporal data.
Source: §6 · p. 9
Abstract
from arXiv · showhide
Missing data is a pervasive issue in both scientific and engineering tasks, especially for the modeling of spatiotemporal data. This problem attracts many studies to contribute to data-driven solutions. Existing imputation solutions mainly include low-rank models and deep learning models. The former assumes general structural priors but has limited model capacity. The latter possesses salient features of expressivity but lacks prior knowledge of the underlying spatiotemporal structures. Leveraging the strengths of both two paradigms, we demonstrate a low rankness-induced Transformer to achieve a balance between strong inductive bias and high model expressivity. The exploitation of the inherent structures of spatiotemporal data enables our model to learn balanced signal-noise representations, making it generalizable for a variety of imputation problems. We demonstrate its superiority in terms of accuracy, efficiency, and versatility in heterogeneous datasets, including traffic flow, solar energy, smart meters, and air quality. Promising empirical results provide strong conviction that incorporating time series primitives, such as low-rankness, can substantially facilitate the development of a generalizable model to approach a wide range of spatiotemporal imputation problems.
1 INTRODUCTION
Missing observations challenge spatiotemporal monitoring, while low-rank and deep models offer structural priors and expressive capacity, respectively, but have complementary limitations. ImputeFormer incorporates low-rankness into a Transformer to balance signal and noise in imputation.
1 INTRODUCTION
- Missing records can be substantial in monitoring data, including about 30% invalid air-quality records and approximately 85% missing records in some Uber Movement subsets.The introduction cites station malfunction as one cause of invalid air-quality measurements.Source: §1 · p. 1
- Low-rank models can oversmooth data and lose informative signals, whereas deep models can retain high-frequency noise and produce sharp imputations.The introduction identifies a need to balance structural priors with model expressivity for generalizable imputation.Source: §1 · pp. 1–2
- ImputeFormer integrates low-rankness into a Transformer to balance signal and noise for general spatiotemporal imputation.The approach uses projected temporal attention and embedded spatial attention, with a Fourier sparsity loss to regularize the spectrum.Source: §1 · p. 2
- The authors report advantages in accuracy, efficiency, and versatility across traffic, solar energy, electricity-consumption, and air-quality datasets.They also describe case studies as revealing interpretability and providing insights into deep imputation.Source: §1 · p. 2
2 PRELIMINARY
The preliminary section sets out the multivariate time-series data notation and motivates low-rank structure through redundancy, attention-map spectra, and Fourier sparsity.
2 PRELIMINARY
- The data are represented by an observed sensor-by-time matrix, ground-truth matrix, temporal exogenous variables, and sensor metadata.The notation assigns X to observations, Y to ground truth, U to exogenous variables, and V to sensor metadata.Source: §2 · p. 2
- The imputation model is trained on observed data and can be applied to a different time span than its training set.The mask indicator marks masked locations during training and observed locations during inference.Source: §2 · p. 2
- PEMS08 can be reasonably reconstructed from five dominant patterns, while spatial attention singular values and spatial and temporal Fourier spectra exhibit low-rankness or sparsity.The figure reports a long-tailed attention singular-value distribution with most values small, and Fourier spectra with most amplitudes near zero.Source: Figure 2 · p. 3
3 RELATED WORK
Related work covers low-rank and deep-learning approaches to multivariate time-series imputation, including graph and Transformer methods. It notes capacity constraints in low-rank models and complexity concerns for sparse cross-attention.
3 RELATED WORK
- Prior imputation work is organized into low-dimensional/rank models and deep-learning models, with examples spanning matrix factorization, tensor completion, recurrent networks, GANs, and diffusion models.The review describes low-rank methods as concise and numerically efficient, but says their limited capacity hinders practical effectiveness.Source: §3 · p. 3
- Graph neural networks have been combined with recurrent models for traffic imputation, while other methods address kriging as a specialized imputation scenario.The cited examples include MDGCN and GACN for traffic, and IGNNK, STAR, and STCAGCN for kriging.Source: §3 · p. 3
- Transformer-based methods use cross-channel attention, masked self-attention, or sparse cross-attention for imputation, but SPIN’s cross-attention has high complexity for larger graphs.The review describes SPIN as combining sparse cross-attention with temporal self-attention over observed spatiotemporal points.Source: §3 · p. 3
4 LOW RANKNESS-INDUCED TRANSFORMER
ImputeFormer integrates low-rank factorization into a Transformer and reports linear complexity in spatial and temporal dimensions, without requiring a predefined graph.
4 LOW RANKNESS-INDUCED TRANSFORMER
- ImputeFormer integrates low-rank factorization into the Transformer, avoids predefined graphs, and achieves linear complexity with respect to spatial and temporal dimensions.Its global adaptive interactions between series distinguish it from graph-based approaches requiring a predefined graph.Source: §4 · p. 3
4.1 Architectural Overview
- The architecture addresses spurious correlations, high-rank attention estimates, and the scalability costs of pairwise attention using time-series structural priors.These concerns motivate enhancing the Transformer rather than applying its canonical block directly to imputation.Source: §4.1 · pp. 3–4
4.2 Spatiotemporal Input Embedding
- Input embedding expands incomplete observations into hidden states, adds sinusoidal time-of-day encodings, and uses learnable node embeddings as abstract sensor representations.The node embeddings are described as low-dimensional representations of incomplete series.Source: §4.2 · p. 4
4.3 Temporal Projected Attention
- Projected temporal attention uses C<T coordinates to reduce attention rank and complexity while retaining a large hidden dimension and dominant correlations.The method gives O(TC) rather than O(T^2) complexity and describes the retained correlations as eliminating spurious ones.Source: §4.3 · pp. 4–5
4.4 Spatial Embedded Attention
- Low-dimensional node embeddings define global sensor correlations, producing factorized low-rank spatial attention with O(ND_emb) complexity and robustness to missing values.The embedding dimension is much smaller than the model dimension, while the feedforward dimension remains large to maintain capacity.Source: §4.4 · p. 5
4.5 Fourier Imputation Loss
- Training combines ℓ1 reconstruction on manually whitened observations with Fourier ℓ1 regularization, which encourages global spectral compatibility and supports highly sparse observations.The authors motivate Fourier ℓ1 as an efficient surrogate for rank regularization, avoiding direct rank optimization.Source: §4.5 · p. 6
5 EMPIRICAL EVALUATIONS
ImputeFormer performs strongly across traffic, energy, and environmental benchmarks, with reported gains in efficiency and robustness across evaluation scenarios. Case studies examine the model’s learned spectra, spatial embeddings, and temporal attention.
5.1 Results on Traffic Benchmarks
- ImputeFormer consistently achieves the best performance across traffic benchmarks, with structured block missing more challenging than point missing.In block-missing cases, the vanilla Transformer is ineffective, while ImputeFormer outperforms other models by a large margin.Source: §5.1 · p. 6, Table 2 · p. 7
5.2 Results on Environmental and Energy Data
- ImputeFormer exhibits superiority beyond traffic on AQI, Solar, and CER-EN benchmarks; embedded attention can alleviate spurious correlations from weak spatial energy correlations.The correlation of solar stations cannot be described by physical distance and can be inferred from the data.Source: §5.2 · pp. 6–7, Table 3 · p. 7
5.3 Ablation Study
- Removing either temporal or spatial attention substantially degrades performance; spatial interaction matters for block missing, while temporal modules matter for point missing.MLP incorporation benefits imputation little, while FIL generalizes on unobserved points and reduces estimation errors compared with hierarchical loss on supervised points.Source: Table 4 · p. 7, §5.3 · p. 7
5.4 Model Efficiency
- 15 times faster than SPIN, ImputeFormer also shows high training efficiency and cost-effective GPU memory consumption.The comparison is presented in Figure 3.Source: Figure 3 · p. 7, §5.4 · p. 7
5.5 Robustness and Versatility Analysis
- In zero-shot tests, ImputeFormer and SPIN were robust to changed missing rates, and ImputeFormer generalized to different sequence lengths.The missing-rate evaluation uses a single trained model; the sequence-length evaluation likewise uses one trained model.Source: Table 5 · p. 8, §5.5 · p. 8, Figure 4 · p. 8
- Under sparse observations, ImputeFormer was more robust; hybrid masking helped at uncertain rates, and FIL helped unless spectral sparsity was over-penalized.Most models performed best when training masking matched point-missing rates, whereas combined masking was more advantageous when block-missing rates were uncertain.Source: Table 6 · p. 8, §5.5 · p. 8, Table 7 · p. 8
5.6 Case Studies: Interpretability
- ImputeFormer’s spectrum resembled complete data (the first 85 SVs account for 80% of energy), while its low-rank sensor embeddings formed clusters aligned with proximal sensors.As embedded-attention layers deepen, learned attention maps approach actual ones; incomplete data instead produce noisy correlations with little informative pattern.Source: §5.6 · p. 9, Figure 6 · p. 9, Figure 7 · p. 9
- Projected temporal attention routes incomplete-state information into compact representations and uses a small number of temporal modes to reconstruct useful representations.After projected attention, hidden states have lower singular values than incomplete inputs and are closer to complete representations.Source: §5.6 · p. 9, Figure 11 · p. 9, Figure 10 · p. 9
6 CONCLUSION
The paper presents ImputeFormer, a low rankness-induced Transformer for spatiotemporal imputation. Across varied benchmarks, it reports state-of-the-art accuracy alongside efficiency, generalizability, versatility, and interpretability.
6 CONCLUSION
- ImputeFormer combines low-rank factorization, projected temporal attention, embedded spatial attention, and a Fourier sparsity loss.These designs incorporate structural priors into a Transformer and regularize the solution’s spectrum.Source: §6 · p. 9
- Across varied benchmarks, ImputeFormer consistently achieves state-of-the-art imputation accuracy and exhibits high computational efficiency, generalizability, versatility, and interpretability.Source: §6 · p. 9
- The authors identify time-series representation learning and multipurpose time-series pretraining as future directions.Source: §6 · p. 9
A.1 Additional Discussions
The appendix contrasts how imputation architectures use temporal and spatial information, then argues that fixed time-axis mappings are poorly suited to arbitrary missingness. It introduces projected temporal attention as a pattern-adaptive alternative related to, but distinct from, prior linear attention.
A.1.1 Architectural Comparison
- The appendix frames this comparison as a structural difference among imputation paradigms.Figure 12 illustrates the architectural comparison.Source: §A.1.1 · p. 11, Figure 12 · p. 11
- ImputeFormer uses projected attention over time and node-representation-based embedded attention across space, unlike the compared recurrent-GCN and full pairwise Transformer designs.MPGRU combines Bi-RNNs over consecutive time points with GCNs over predefined graphs; the canonical Transformer computes pairwise correlations along both axes.Source: Figure 12 · p. 11
A.1.2 Effective Input Embedding
- Fixed time-axis weights depend on relative position rather than data flow, so arbitrary missing locations can create spurious relationships and overfitting to training missing patterns.The authors therefore advise against linear mappings on the time axis for varying missing time points.Source: §A.1.2 · p. 11
A.1 Additional Discussions
- Temporal projected attention shares an idea with Wang et al.’s [39] linear attention but uses different mechanisms and formulations.The passage introduces the projected-attention formulation for Q, K, V and projector P.Source: §A.1.3 · p. 11
A.1.3 Low-Rankness in Self-Attention.
ImputeFormer factorizes attention explicitly and adapts its temporal factors to input patterns, in contrast with Linformer’s static compression matrices. The authors report equal computational complexity but greater model capacity for ImputeFormer.
A.1.3 Low-Rankness in Self-Attention
- The excerpt gives the nested expression SelfAtten(Q, P, SelfAtten(P, K, V)); it does not specify an application or define these symbols in the cited passage.Source: §A.1.3 · p. 11
- ImputeFormer directly factorizes the full attention matrix from T×T into T×C and C×T, whereas Linformer first computes full attention and then compresses it.The paper identifies this explicit factorization as beneficial for redundancy and missingness in the attention matrix.Source: §A.1.3 · p. 11
- ImputeFormer derives its T×C factor from QP^T, making it pattern-adaptive, while Linformer’s learnable E and F matrices are static and agnostic to missing patterns.The compared linear-attention formulation assigns E and F dimensions C×T.Source: §A.1.3 · p. 11
- At the same O(4TDC) complexity, ImputeFormer has C×D learnable parameters versus Linformer’s T×C, which the authors describe as larger model capacity.The passage also characterizes ImputeFormer’s formulation as explicit and symmetric.Source: §A.1.3 · p. 11
A.2 Reproducibility
The reproducibility appendix reports shared implementation settings and evaluates the model across traffic, energy, and air-quality data. It specifies dataset characteristics, missingness scenarios, and the train-test protocols used for different method classes.
A.2 Reproducibility
- Experiments use one NVIDIA RTX A6000 GPU, hidden size 256, input projection size 32, node embedding size 64, projected size 6, three attention layers, and sequence length 24.Training, validation, and evaluation splits follow [7] [26], with metrics reported on masked evaluation points.Source: §A.2.1 · p. 11
- The benchmark spans traffic speed and volume, Solar and CER-EN energy series, and AQI air-quality measurements, including AQI data with nearly 26% missingness.The described datasets include METR-LA and PEMS-BAY, four PeMS traffic-volume datasets, smart-meter series, and AQI36.Source: §A.2.2 · pp. 11–12
- Figure 13 presents traffic speed and volume imputation visualizations under different missing patterns.Source: Figure 13 · p. 12
- Traffic, Solar, and CER-EN tests use 25% point missingness or block failures, with additional sparse-condition tests reaching approximately 90–95% missingness.Deep models are tested out of sample on disjoint training and test sequences, while matrix and tensor models use in-sample tests.Source: §A.2.3 · p. 12
A.2.3 Experimental Settings and Baseline Methods.
The experiments compare ImputeFormer with statistical, low-rank, and deep imputation baselines, and test architectural and loss variations. Evaluation uses MAE on artificially masked points unavailable to models during training and evaluation.
A.2.3 Experimental Settings and Baseline Methods
- Baselines include Average, TRMF, LRTC-AR, MICE, SPIN, GRIN, SAITS, BRITS, rGAIN, Transformer/ST-Transformer, TiDER, TimesNet, and BiMPGRU.The selection covers statistical and optimization models as well as deep-learning methods.Source: §A.2.3 · p. 12
- Ablations replace or remove temporal and spatial interaction modules, alter the FIL loss, and vary spatial-temporal block order or joint attention.Two datasets are used for these studies, with other settings held constant.Source: §A.2.3 · p. 12
- MAE is computed on simulated missing points, which are marked unavailable to the models throughout the evaluation process.The missingness rate is denoted p_missing, and the mask marks unobserved points as one and observed points as zero.Source: §A.2.3 · p. 12
A.3 Imputation Visualization
Figure 13 illustrates reasonable imputations from ImputeFormer through learned spatiotemporal structures. The model can produce detailed reconstructions, including in block-missing cases by using node embeddings to query spatial relations.
A.3 Imputation Visualization
- ImputeFormer generates reasonable imputations by learning inherent spatiotemporal structures.The paper illustrates these examples in Figure 13.Source: §A.3 · p. 12
- Deep architectures’ representation power supports detailed reconstruction, unlike the oversmoothing attributed to previous low-rank models [4] [30].Source: §A.3 · p. 12
- In block-missing cases with limited temporal information, node embeddings serve as queries to spatial relations for effective imputation.Source: §A.3 · p. 12