CDSA: Cross-Dimensional Self-Attention for Multivariate, Geo-tagged Time Series Imputation

1 Introduction

• Missing data arises from sensor damage or communication errors, and its patterns can be almost random or follow varied characteristics.These data are used in applications including air-quality, health-care, and traffic monitoring.Source: §1 · p. 1
• RNNs process time steps sequentially, limiting parallel training and direct modeling of relationships between distant time stamps.The paper positions self-attention as a way to model pairwise relationships explicitly.Source: §1 · p. 2
• The paper presents its work as the first application of self-attention to imputation for multivariate, geo-tagged time series.Its contribution replaces conventional RNN-based models for this task.Source: §1 · p. 2
• CDSA models attention jointly across time, location, and measurement in a dimension-wise decomposed manner that is computationally efficient and independent of processing order.The paper studies several ways to model self-attention across dimensions.Source: §1 · p. 2
• The paper reports that its model outperforms state-of-the-art models on both data imputation and forecasting tasks.The evaluation covers three standard benchmarks and a newly collected traffic dataset.Source: §1 · p. 2

2 Related Work

• Statistical imputation methods often impose assumptions, such as smooth curves or low-rank constraints, when reconstructing missing values.Kriging variogram models capture variance with respect to geodesic distance [Stein 2012].Source: §2 · p. 3
• RNN-based imputation models address temporal relationships, but sequential processing leads to long training times and prevents direct modeling of distant data relationships.Examples include DCGRU [Li et al. 2018], GRUI [Luo et al. 2018], and bidirectional RNN imputation [Cao et al. 2018].Source: §2 · p. 3
• Self-attention has been applied to sequence, image-generation, and graph-structured tasks, while this paper applies it to multidimensional data imputation and studies cross-dimensional attention.The cited applications include machine translation, image generation [Yang et al. 2016; Zhang et al. 2018a], and graph-structured data [Veličković et al. 2017].Source: §2 · p. 3

3.1 Conventional Self-Attention

• Conventional self-attention maps each word to Query, Key, and Value vectors, then uses attention to update its Value representation.For time-series data, a straightforward adaptation treats each time stamp as one word embedding and models attention over time.Source: §3.1 · pp. 3–4

3.2 Cross-Dimensional Self-Attention

• CDSA considers three ways to model attention across time, location, and measurement: independent streams, a joint map, and a joint yet decomposed design.The input can be reshaped by dimension or flattened across all units.Source: §3.2 · p. 4

3.2.1 Independent

• Independent builds parallel attention streams for time, location, and measurement, then fuses their outputs with trainable weights.The streams can use separately set hyperparameters.Source: §3.2.1 · p. 4

3.2.2 Joint

• Joint flattens the three-dimensional input and builds a TLM × TLM attention map to directly model relationships among all units.Each unit is mapped to Query, Key, and Value vectors.Source: §3.2.2 · p. 4

3.2.3 Decomposed

• Decomposed CDSA combines dimension-specific attention maps to capture both within-dimension and cross-dimensional relationships, with outputs and gradients independent of processing order.Its attention weights are products of the weights from the time, location, and measurement maps.Source: §3.2.3 · pp. 4–5
• The Decomposed design significantly reduces FLOPs relative to Joint and uses fewer variables than Independent.Table 1 reports the computational-complexity comparison.Source: Table 1 · p. 5, §3.2.3 · p. 5

3.3 Framework

• Imputation uses CDSA in an eight-layer Transformer encoder, whose final Value tensor feeds a jointly trained network to reconstruct values.Forecasting uses a Transformer encoder and decoder with nine layers each, followed by a feed-forward network for predictions.Source: §3.3 · p. 5

3.4 Implementation Details

• Inputs are normalized using training-data means and standard deviations, missing entries are set to zero, and Adam minimizes RMSE.Training uses a single NVIDIA GTX 1080 Ti GPU.Source: §3.4 · pp. 5–6

4.1 Datasets, Tasks, Evaluation Metrics

• The evaluation covers NYC-Traffic burst-loss imputation, two KDD-2015 tasks, KDD-2018 imputation, and METR-LA traffic-speed forecasting.NYC-Traffic evaluation varies missing rates from 20% to 90%; METR-LA predicts the second hour from the first and scores several forecast horizons.Source: §4.1 · p. 6

4.2 Comparisons with State-of-the-art

• CDSA outperforms traditional and RNN-based methods across NYC-Traffic missing rates, improves on traditional methods for KDD-2015 PM2.5, and matches IIN on MAE while improving MRE.For KDD-2015 Temperature and Humidity, it consistently outperforms state-of-the-art methods.Source: Table 2 · p. 7, §4.2 · p. 7, Table 3 · p. 7
• On KDD-2018, CDSA improves on traditional methods and MTSI; on METR-LA forecasting, it beats previous methods in most cases, with clear gains at 60 minutes.The reported comparison spans KDD-2018 MSE and METR-LA MAE/RMSE/MAPE.Source: Table 4 · p. 7, §4.2 · p. 7, Table 5 · p. 8

4.3 Discussions

• For METR-LA forecasting, using RMSE as the training loss gives the best performance among the compared losses.The comparison is reported in Table 6.Source: §4.3 · p. 8, Table 6 · p. 8
• The Decomposed attention design performs best on all four datasets and reduces computational complexity by combining Independent-style attention maps with Joint-style shared Values.Independent has more variables and FLOPs than Decomposed, while Joint has much higher FLOPs because it builds a large attention map.Source: §4.3 · p. 8, Table 7 · p. 8, Table 8 · p. 9
• In the PM10 example, CDSA uses both PM10 and PM2.5 at an earlier time to impute a missing PM10 value.The visualization describes attention across time and measurement dimensions.Source: §4.3 · p. 8, Figure 4 · p. 9

• The proposed cross-dimensional self-attention model achieves superior results to state-of-the-art methods on imputation and forecasting tasks.The authors plan to extend CDSA to higher-dimensional, multimodal inputs and publicly release the collected NYC-Traffic dataset.Source: §5 · p. 9