Learning to Reconstruct Missing Data from Spatiotemporal Graphs with Sparse Observations
Authors: Ivan Marisca
Andrea Cini
Cesare Alippi
Venue: NeurIPS 2022 Accept (2022)
Keywords: missing data
time series imputation
spatiotemporal graph neural networks

Abstract: 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.

Learning to Reconstruct Missing Data from Spatiotemporal Graphs with Sparse Observations
Ivan Marisca" 'Te Swiss AI Lab IDSIA, Università della Svizzera italiana ivan bariscalusi.co ch
Andrea Cini'
The Swiss Al Lab IDSIA, Università della Svizzera italiana andrea cini @usi ch
Cesare Alippi
The Swiss AI Lab IDSIA, Università della Svizzera italiana Politecnico di Milano cesare. alippidusi. ch
Abstract
Modeling multivariate time series as temporal signals over a (possibly dynamic) graph is 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 recursively learn representations 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, c.g., due to the unreliable underlying sensor network. In this context, autoregressive models can brittle and exhibit unstable learning dynamies. The objective of this paper is, then, to tackle the problem of learning effective models reconstruct, i.e., impute, missing data points by conditioning the reconstruction only on the available observations. In particular, we propose novel class of attention-based architectures that, given set 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 emrors requiring bidirectional model to encode forward and backward time dependencies. Empirical results on representative benchmarks show the effectiveness of the proposed method.
1 Introduction
Exploiting structure - both temporal and spatial is arguably the key ingredient for the success of modern deep learning architectures and models. Structure and invariances allow imposing inductive biases to learning systems that act as strong regularizations, thus limiting the space of possible models to the most plausible ones and, consequently, greatly reducing sample complexity. This is the case with spatiotemporal graph neural networks (STGNNs) [[H3] which learn process multivariate time series while taking into account underlying space and time dependencies by encoding structural spatiotemporal inductive biases in their architectures. In particular, graphs used to model the presence of spatial relationships which can be thought of as soft functional dependencies existing
"Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

among the sensors generating the time series 4 However, even when spatiotemporal relationships are present, available data are almost always incomplete and irregularly sampled both spatially and temporally. This is definitely true for data coming from real sensor networks (SNs), where the presence of missing data a phenomenon inherent to any data acquisition or communication process, In this case, common approach is to reconstruct missing time series observations with simple interpolation strategies before proceeding with the downstream task. However, arguably, this induces bias in the inference procedure, possibly made even worse by the strong regularization imposed on the model. More advanced methods deal with missing data by autoregressively replacing missing observations with predicted ones, eventually using bidirectional architectures [S] 6 to exploit both forward and backward temporal dependencies. To account also for spatial dependencies, Cini et al. 4 introduced method, named GRIN, combining a bidirectional autoregressive architecture with message passing graph neural networks [7-10] for spatiotemporal imputation. Despite being the state of the art in imputation, GRIN suffers from the error propagation typical of autoregressive models that bootstrap future inferences from their own predictions. In fact, we argue that the propagation of imputed (biased) values through space and time combined with noisy observations might exacerbate error accumulation in highly sparse data and drive the hidden state of GRIN-like models to possibly drift away. In this paper, we aim tackling this problem by designing an architecture based on a novel attention mechanism that takes spatiotemporal sparsity into account while learning representations and imputing missing values.
Attention-base based models allow distributed representations to emerge by letting each discrete element representing an entity point within a structured enviromment - interact with each other. In fact, these mechanisms for propagating information through structures have been recently linked to collective intelligence [11. In context, each token, represented node in sequence of graphs, represents a point in space and time. A trivial way to account for sparsity in this setting is to constrain the attention coefficients of time steps corresponding to missing data to be zero or simply to add an auxiliary token to indicate missing observations; basically, the resulting reconstruction model would behave similarly to a denoising autoencoder, in the same spirit of BERT-like encoders popular in natural language processing [12]. Conversely, we propose a novel architecture exploiting an inter-node sparse spatiotemporal attention mechanism within the neural message- saasagg-passing framework. In particular, we seek to design an architecture where each processing stage is aligned with the task of reconstructing missing spatiotemporal observations. Our model can be seen a learned, self-organizing, spatiotemporal propagation process that, as we will motivate throughout the paper, is more apt to the purpose of missing data reconstruction than standard mccder-decoder architectures. In fact, compared with the alternatives discussed so far, our method exploits the aforementioned propagation process to learn a predictive representation for each missing observation by relying only on observed values propagated through the spatiotemporal structure. This approach achieves the twofold objective of avoiding propagating biased representation - typical in the autoregressive framework and reconstructing observations at arbitrary nodes in the sensor network. In summary, our main contributions are as follows.
1. We introduce a sparse spatiotemporal attention mechanism to learn, from sparse data, representations localized in time and space.
2. We design a novel graph neural network architecture based on the aforementioned spatiotem- poral attention mechanism and equipped with inductive biases that make the model tailored for the multivariate time series imputation task.
3. We empirically assess the proposed method, showing how it overcomes the limits of existing approaches, particularly in settings with highly sparse data.
The paper is structured as follows. In Section 2 we discuss related works and contrast them with ours.
We formulate the problem of multivariate time series imputation in the context of spatiotemporal graphs in Section 3, and present our approach Section 4 by providing an in-depth discussion of
motivations, design choices, as well as methodological and technical issues. Finally, in Section 5 we report the empirical results on several relevant benchmarks. Conclusions and future works are discussed in Section
2

---

2
Related works
Multivariate time series imputation is a core task in time series analysis. Besides standard statistical approaches based on linear autoregressive models [33155] interpolation [16], methods based on matrix factorization are widely popular
and can also incorporate temporal [8] and graph-side information [9]. Deep learning methods are also commonly used in this regard. In particular, deep autoregressive models based on recurrent neural networkss (RNNs) are currently among the most widely adopted methods (20 S 6 21]. In this direction, BRITS [6] is archetypal of several related works which exploit bidirectional RNNs to perform imputation. Notably, differently from a denoising autoencoder, BRITS uses on-stee-ahhad forecasting as a surrogate task to learn an imputation model while using simple linear regression layer to incorporate spatial information. Several approaches in the literature, then, rely on generative adversarial neural networks [2 often paired with RNNs to
generate imputed subsequences by matching the underlying data distribution [23 24 21]. Recently,
several attention-based imputation techniques have also been proposed (25-27), however, none of these explicitly account for spatial dependencies within the graph processing framework and overlook the spatial dimension of the problem. Other works, instead, address this problem in the context of continuous-tine models (28). Huang et al. [29]. in particular, exploit graph representations to model spatial dynamics. The limits of deep autoregressive approaches in data reconstruction have also been tackled by using hierarchical imputation methods [30, 31]. More related our work, GRIN 4 uses a bidirectional graph RNN, paired with a message passing spatial decoder, to impute time series based on spatiotemporal dependencies. Other graph-based architectures have been used in application-specifee
settings, such as traffic data [32 B3) and load profiles from smart grids [34]. While GRIN achieves remarkable performance, we argue that spatial regularization might not be enough to prevent error compounding in the states of the recurrent graph network.
The attention mechanism has been exploited in several contexts within the graph deep learning literature, in particular in anisotropic graph convolutional filters (35) Among STGNNs, attention- based architectures have been exploited in time series forecasting 37 49 In particular, Tra- verseNet [41] is specially related to our work, since it relies on spatiotemporal autoregressive attention to compute messages exchanged between nodes. One striking example of attention being used suc- cessfully to process incomplete data is in pretraining routines for representation learning in natural language processing [12 42 Finally, graph neural networks are also popular for reconstructing
missing features in static graphs 43.45).
3 Preliminaries
We model multivariate spatiotemporal time series as observations coming from SNs. In a SN every i-th node, i.e., sensor, acquires d-dimensional x; Rd observation at each t-th time step. We denote by X, E Ned the matrix collecting the measurements of N, sensors at time step I, with X being the sequence of T measurements collected in the time interval [t, 1,,4+, T)). We model functional relationships among the sensors as graph edges. Relationships can be often inferred from available side information, e.g., one can extract a graph from the position of each sensor and their reciprocal physical proximity or the structure of the physical system where sensors are placed. In other cases instead, functional dependencies can be inferred directly from data by exploiting some affinity score (e.g., Pearson correlation, Granger causality [46), correntropy 47). etc.), or more advanced techniques (e.g.. graph learning methods 48)) We model the extracted relational information with a weighted, possibly asymmetric adjacency matrix A, E R.N.NN, in which each nonzero entry a/ indicates the weight of the edge going from the i-th node to the j-th. While our framework can account for dynamic relationships, we mostly focus on settings where the topology is static, i.c., A, A and N₁ = N. Finally, we assume to have available sensor-level covariates Q2 E IN Xd, that act as spatiotemporal coordinates to localize a point in time and space (c.g., date/time features and geographic location). Note that coordinates of are assumed available for each node at each time step; in section 4 we discuss how Q: can be learned as a spatiotemporal positional encoding. We then model observations
discrete sequence of spatiotemporal graphs, where each graph is a triplet 9, = (X,, Q., A). Note that, in general, we indicate with capital letters network-leve attributes, while we use lowercase for the sensor level.
As already mentioned, observations might be incomplete due to faults, partial observability, and costs of the data acquisition process. We model data availability with a binary mask mi E {0, which is
3

---

1 if the measurements associated with the i-th sensor are valid at time step t. Conversely, if m 0, we consider the measurements æi to be completely missing, with the exogenous variables qf being instead available. Notice that usually, each mi is realization of random variables with non-trivial distributions exhibiting complex spatiotemporal dynamics and correlations. For instance, sensor fault may last for more than one time step, spatially correlated errors may result in missing data in an entire sub-region of the network.
Multivariate Time Series Imputation Given observations X with missing values indicated by mask M we denote by X the unknown corresponding complete sequence, i.e., the sequence where no observation is missing. Formally, the goal of multivariate time series imputation (MTSI) is to find estimate Xta+r minimizing the reconstruction error
((), m
C (XeLT,, XEATT, XESsT, MasTr)
(I)
where e(., -) is an element- wise error function and m. is the logical binary complement of mi- Notice that, since X is not available, one should find a surrogate objective or simulate the presence of missing data, for which the reconstruction error can be computed.
Learning representations from sparse spatiotemporal data
The autoregressive approach to reconstruction consists in directly modeling distributions p p(a;) Xxx) and using one-step-ahead forecasting as a surrogate objective to learn how to recover missing observations. To exploit available data subsequent to the target time step, is common use bidirectional architecture, i.e., to mirror time w.r.t. the time step of interest and have a second model for estimating y (ar)] xx)) 49 6. Here we use the shorthand X <t and X>x to denote observations collected before and after time step f. respectively. Moreover, third component p (ax {x]"')) must be introduced to account for spatial information at each step. Architectures like GRIN, follow exactly this scheme with different components dedicated to model each of these three aspects. While being effective in practice, these approaches can have multiple drawbacks. Besides the computational overhead of having three separate components and the compounding of prediction errors typical of autoregressive models, the modular approach can fall short capturing global context, as the processing of the structural information is decomposed. Furthermore, integrating the information coming from the different modules also problematic, yielding further compounding of errors. Finally, in the case of highly sparse observations, the spatial processing should be dealt with special care as propagating information through partially observed spatiotemporal graphs adds another layer of complexity. For instance, simply masking out faulty sensors would compromise the flow of information through message-pussingg layers [9].
Model overview To address the limitations of existing methods, we act on the problem more directly by aligning the structure of our proposed architecture closely with the reconstruction task. We denote as observed set XE4TT = { (=+ .f) m = 1, [t, + +T) the set of all observations, paired with their spatiotemporal coordinates. Conversely, we name target set Vu.TT {q- m 0, E [t, +t, } the complement set collecting the coordinates of the dis- crete spatiotemporal points for which we want to reconstruct an observation. We refer to the set of observed and target points of the i-th node as XiaT and ) VE respectively. Then, for all
o E VELTT, we aim learning a structured model for
p(æ², NEAT, A).
(2)
Our approach, named Spatiotemporal Point Inference Network (SPIN), a graph attention network for MTSI, designed to learn representations of discrete points associated with nodes of a sequence of spatiotemporal graphs. Given disjoint observed and target sets X and DiaTT, SPIN is trained to leam model
fo fo RESTT A) = E 1p(2 (2,, q:, Nett, A)]
for all discrete points of E VeTT.. To this end, SPIN learns a parameterized propagation process where each representation, corresponding to specific node and time step, is updated by aggregating

---

Observations Embedding
Lx
Volid Obsenation
[A]
MID
Xus-
Qui
Covariates Embedding
Spetiotemporal Cross- Cross-attention
Temporal Salf aelf-attention
Skip Connection
Figure 1: The architecture of SPIN. At first, encode observations Xt++T and spatiotemporal coordinates Qu++.. obtaining initial representations H ::+-- The representations are updated by stack of L. sparse spatiotemporal attention blocks. Final imputations obtained from H Haar with a nonlinear readout.
information from all the available observations acquired at neighboring nodes weighted by input- dependent attention coefficients. FFigure I| shows overview of the architecture. In the next paragraphs, we will go through each component explaining it in detail and providing motivations for each design choice. We start by describing how set up the propagation process.
Sparse spatiotemporal attention The core component of SPIN novel sparse spatiotemporal attention layer used to propagate information at the level of single observations. Indeed, leveraging on the attention mechanism, we learn representations for each i-th node at each 7-th time step by
simultaneously aggregating information from (I) the observed set of i-th node X - (2) the observed
set X KIAT of its neighbors j E (i).. Figure shows schematic representation of this procedure.
Spatiotemporal Cross attention
Temporal Self attontion
R: (0000000)
{ O 0903 R;
All No
d
MLP
sie-r
time
Skip Connection
s/x Valid missing observation
Encoding missing observation)
/
Spatiotemporal point (missing query/ valid key key)
Example of the sparse spatiotemporal attention layer. On the left, the input spatiotemporal graph, with time series associated with every node. On the right, how the layer acts to update target representation hz (highlighted by the green box), by simultaneously performing inter-node spatiotemporal cross-attention (red block) and intra-node temporal self-attention (violet block).
Figure 2:
Let h. (.(1) dR.h be the learned representation for the i-th node and time step at the l-th layer. The encoding is initialized as
MLP Φ (at, E Xatr
d. E Vattr
(.)
(4)
where qi indicates a positional encoding, as previously anticipated, and MLP is generic multi- layer perceptron. The representation is then updated by joint temporal and spatiotemporal attention operations. To describe the inner working of the proposed attention mechanism, we adopt the terminology of Vaswani et al. [50) and indicate as query the token for which we want to compute an updated representation, key a representation of the source tokens, and value the content representation of each token. The next steps involve computations of spatiotemporal messages, i.c.. representations computed to propagate information from one discrete space-tima point to another. We indicate the propagation along the temporal dimension from time step to time step 7 with subscripts Similarly, superscripts j + i indicate messages sent from the j-th node to the i-th, To avoid overloading the notation, omit the layer superscript in the following. The message ri=t E Rd from the j-th node at time step to the i-th node at time step T is computed as MLP(h h:),
jo
(5)
where, following the adopted terminology, target point representation h; acts as query, source point representation h as key and the computed message ri -- is the value. Notice that, differently from
5

---

the dot-pree dot-product attention mechanism by Vaswani et al. [50,, we take into account both source and target representations to compute the value, similarly the Bahdanau attention [ST] To account for spatial information, this mechanism is used to perform an inter-node temporal cross-attention. More
precisely, for every neighbor Aii)), we use h to query separately every encoding in h associated with a valid observation, and collect the messages in the set
R4- {r! (2 q.) Ne+T))
(6)
Then, we linearly transform messages in R2 (using trainable weights W. E RRxdd)) and obtain message scores og tt with softmax layer, i.e.,
exp W W
E .2 exp(
Then, we aggregate temporal messages coming from each j-th node separately, and obtain an edge-level context vector e!-
Σ &
(8)
which encodes the observed sequence at each j-th node w.r.t. the i-th node and time step T. Anal- ogously, to account for the observed sequence w.r.t. the i-th node itself, we exploit an intra-node temporal self-attention mechanism to query the encodings E corresponding valid observations. Then, the resulting representations are weighted and aggregated to obtain a temporal context vector c² as
MM.P(h h?)
(9)
R₂ = =rr (a. E NatT)
(10)
c Σ arear rle
(11)
where message score a² is obtained similarly as Eq. 7 Note that parameters are not shared between the cross-attention and self-attention blocks. After having obtained context vectors of c,))))
and et (-),(() the encoding h+:(0) is updated with a final aggregation step as
h 1+(+1) MIP h (0)
100
ESENCO e.-
(12)
After L layers, we obtain imputations for all spatiotemporal points in VecTT with a nonlinear readout
DEatr = (#) = MLP(h.(0) | E Va+r).
(13)
Two-phase propagation Masking out tokens in the target set allows SPIN to propagate only valid information. As a downside, this results in blocking the flow of information on paths through points in the target set. This be problematic when the input observations are extremely sparse. Nonetheless, is reasonable to assume that, after only a few propagation steps, the available information has already been partially diffused to locations with missing observations. At this point, interrupted paths can be unlocked, allowing for reaching higher-order neighborhoods. In practice, we introduce hyperparameter 7) to control the number of layers with masked connections and effectively split the propagation process into two phases. It is important to notice that what is being propagated in the second phase are learned representations, not observations (unavailable for masked tokens).
Graph subsampling and hierarchical attention Roughly speaking, the proposed spatiotemporal attention mechanism can be viewed as performing attention over the spatiotemporal graph S. obtained by considering the product graph between space and time dimensions with some connections pruned w.r.t. unavailable data. Let Nmuxx Fmax be the largest number of nodes and edges, respectively, among graphs in Gra+7. Performing graph attention on the surrogate graph S has time and memory complexities that scale with O ((Nmax + T2)) (sparse implementations can alleviate this complexity by replacing T with the number of valid time step pairs). To reduce this computational burden which undermines the application of the proposed method to large graphs and long time

---

horizons we propose two different approaches. The straightforward approach consists in training the model by exploiting graph subsampling, using one of the many possible subsampling strategies from the literature (e.g., (52). ). In practice, at training time, we sample a k-hop subgraph centered on n target nodes and then compute the loss only w.r.t these n nodes. In this way, we can reduce the amount of computation required by acting on n and k. This type of subsampling can also be seen as a form of regularization [53].
A more interesting and orthogonal approach to reduce complexity is to rewire the attention mechanism to be hierarchical [54]. We do this by adding K dummy nodes that act as hubs for propagating information. Let Z' E R x xd= be the hub nodes' representations for central node i, and then, for hub k proceed as follows.
1. Update z by querying {hξ (z,,, qt) E Netrr,, i.e. node encodings associated with valid observations, obtaining Z/:;
2. Update node encoding h. by querying updated ž' and Z of every j-th neighbor in (t)..
The spatiotemporal attention is effectively split into two phases. At first, update each hub node representation similarly as Eq. 11
r MLP 21) (rt, (ae gt) E NetTT
(14)
c
E
a rit
(16)
Tir MLP(2 ck)
R3
(15)
(17)
Then, we obtain context vectors from the updated hub representations as:
rk.- MLP(PLLLB h$
(18)
r - RT
MLP hz) A
(20)
c² = Σ kkk Th.
(19)
c cl
(21)
and update node representation hi as Eq. 12.. In this way, we can reduce the spatiotemporal atten- tion complexity to O ((Nmax + Emax KT) with K < T, at the cost of introducing an information bottleneck. We initialize the hub representations layer 0 with random trainable parameters.
Spatiotemporal positional encoding We now come back to the problem of learning the spatiotem- poral positional encodings Qu:+r. The encoding has capture both spatial and temporal structure and be decoupled from the observations x; to allow inference for points in the target set. These encodings can be directly extracted from available exogenous information (e.g.. sensor location and date/time features) or learned end-to- -o---t--nddd jointly with the other model parameters. We propose a spatiotemporal positional encoding qi = p( [e, v²) obtained by combining a temporal encoding U R Txx and spatial encoding V E NN with non linear transformation p. e.g..
q. MLP((u, v¹).
(22)
For the temporal encoding ut, we use sine and cosine transforms of the time step / w.r.t a period of interest (e.g., day and/or week), to account for seasonalities. For the spatial encoding v', we resort to vector learnable parameters different for each i-th node. More advanced methods could be considered [55 (56).
5 Empirical evaluation
In this section, we evaluate our method on three real-world datasets and compare the performance against state-of-the-art methods and standard approaches for MTSL. As the objective of our approach to address the imputation problem in highly sparse settings, in a second experiment we assess how performance changes as the percentage of missing values increases.
5.1 Experimental setting
In the following experiments, we consider both SPIN and the hierarchical version SPIN-H (Sec. The figure of merit used is the mean absolute error (MAE), averaged across imputation windows.
7

---

Table 1: Performance (in terms of MAE) averaged over 5 independent runs.
Block missing
Point missing
Simulated failures
PEMS BAY
METR-LA
PEMS-BAY
METR-LA
AQ1-36
AQI
Mean
5,46 1 0.0
7.48 0.000
5,42 1 0.00
7.56 0.00
53,48
39.60 1 0.00
KNN
4.30 1 0.0
7.79 1: 0.000
4.30 +: 0.00
7.88 1: 0.00
30.21
0.00
34.10 1: 0.00
MF
3.28 1 0.0
5.46 1: 0.00
3.29
+ 0.01
5,56 1 0.03
30,54
1 0.26
26.74 1: 0.24
MICE
2.94 + 0.02
4.22 = 0.05
3.09
= 0.02
4.42 = 0.07
30.37
= 0.09
26.98 + 0.10
VAR
2.09 0.10
3.11 0.08
1.30 0.00
2.69 0.00
0.08 15.64
22.95 + 0.30
rGAIN
2.18 + 0.01
2.90 = 0.01
1.88 = 0.02
2.83 = 0.01
15.37
0.26
21.78 = 0.50
ERITS
1.70 0.00
2.34 0.011
1.47 = 0.00
2.34 0.00
14.50 0.35
20.21 + 0.22
SAITS
1.56 + 0.01
2.30 = 0.01
1.40 = 0.03
2.26 : 0.00
18.16 0.42
21.33 + 0.15
Transformer
1.70 0.02
3.54 + 0.00
0.74 0.00
2.16 0.00
11.98
18.11 0.25
GRIN
1.14 + 0.0
2.03 + 0.00
0.67 =: 0.00
1.91 + 0.00
12.08 + 0:47
14.73 + 0.15
SPIN
1.06 +: 0.02
1.98 +: 0.01
0.70 = 0.01
1.90 : 0.01
11.77 0.54
13,92 :: 0.15
SPIN-H
1.05 + 0.01
2.05 +: 0.02
0.73 +: 0.01
1.96 + 0.03
10.89 0.27
14.41 +: 0.13
We consider only the out-of-sample scenario 4 in which every parametric model trained and tested on disjoint sets. All the baselines have been implemented in PyTorch [57] using the Torch Spatiotemporal library [58] and, whenever possible, open-source code provided by the authors. The
code to reproduce the experiments of the paper is available online Please refer to the appendix for more details about the experimental setup.
Datasets We consider three openly available datasets coming from real-world SNs. The first two, namely PEMS-BAY and METR-LA 2 are two widely used benchmarks in spatiotemporal forecasting literature, Each of them records traffic measurements every 5 minutes from 325 speed sensors in San Francisco Bay Area and 207 in Los Angeles County Highway, respectively. Since the original datasets have low number of missing values, we use the same setup of 4 to inject missing data with two different policies: 1) Block missing. in which we randomly mask out 5% of the available data and, in addition, we simulate a failure lasting for S ~ Ld(2,, 48) steps with 0.15% probability: 2) Point missing, in which we randomly drop 25% of the available data. As third dataset, we consider AQI [59], which collects one year of hourly measurements of air pollutants from 437 air quality monitoring stations over 43 cities in China. We consider also a smaller version of this dataset (AQI-36) with only the 36 sensors scattered over the city of Beijing. This dataset is popular benchmark for imputation for the high number of missing values (25.67% the complete dataset) and provides a mask for evaluation that simulates the true missing data distribution [15. For a given month, such a mask replicates the missing values patterns the previous month, making this scenario more similar to the Block missing setting, for a total of & 36% missing data. In all settings, all the valid observations masked out are used as targets for evaluation. We obtain an adjacency matrix from the pairwise distance of sensors following previous works 2
Baselines As the target of our approach is the processing of spatiotemporal graphs with missing observations, we compare our method against GRIN [4]. graph-based bidirectional RNN for MTSI with state-of-the -o-the--rtttttt-o performance. We then consider a spatiotemporal Transformer, where we alternate temporal and spatial Transformer encoder layers from [50) and replace missing values with a [MASK] token (as in [12)). We consider also other deep imputation methods: 1) SAITS (25), a recent attention- based architecture based on diagonally- masked self-attention; 2) BRITS (6) which leverages on bidirectional RNN; 3) rGAIN, an adversarial approach which shares similarities with GAIN 23 and SSGAN [21] Finally, we report results of simpler methods that impute missing values using 4) node-level sequence mean (MEAN) or 5) neighbors mean (KNN); 6) Matrix Factorization (MF); 7) MICE [60]; 8) VAR, a vector autoregressive one-step-ahead predictor. Whenever possible, we use results from
8

---

Table 2: Performance (MAE) with increasing data sparsity in the Point missing setting (averaged over 5 evaluation masks).
METR-LA
PEMS-BAY
AQI
Missing rate
Missing rate
Missing rate
%
75 %
%
%
%
50%
%
%
BRITS
+ 0:30
+ 0.00
5.19
+ 0.02
1.55 0.00
2.17 0.00
3.91
0.02
14,90
18.29
29.83
SAITS
2.48 0.00
3.74
1 0.001
6.72
0.01
1.50
1 0.00
2,96
1 0.01
7.40
1 0.01
15.36
1 0.02
20.64
0.05
34.57 1 0.05
Transformer
2.31 0:00
2.71
+: 0.00
5.13
-: 0.01
0.85
1: 0.00
1.13
+ 0.00
2.70
001
9.11
10:40.00 0.02
12.56
25.65
GRIN
2,05 1 0.00
2.39
1 0.00
4,08
1. 0.02
0.79
1 0
1.09 1 0.00
2.70
0.01
8:43
1.0.1.00 0.01
0.02 10.97
20.38 1 0.10
SPIN
2.02 0.00
2.24 1: 0.00
2.89
0.01
0.79
0.00
1.00 0.00
1.71 0.00
8.15
0.01
9.96
15.31
SPIN-H
2.01 + 0,00
2.20 + 9.00
2.82 = 0.00
0.79 + 0.00
0.97 + 0.00
1.68 9.00
8.67 + 0.02
10.27 0002
15.75 + 0.07
Table 3: Performance (MAE) with an increasing number of simulated failures in the Block missing setting (averaged over evaluation masks).
METR-LA
PEMS-BAY
AQI
Failure probability 10%
Failure probability
Failure probability
5%
15%
5%
10
15 %
%
10% %
%
BRITS
0.00
0.06
8.29 1 0.00
4,14
1 0.05
0.05
5.84
0.000
0,30
31,90
37.62
SAITS
4.73 +
6.66 + ous
7.27 + 0.03
3.88
+ 0.09
7.62
0.21
8.01
+011
20.78
0.30
30.16 0.39
36.34 0.33
Transformer
6.03 0.04
7.19 + 0.5
8.06
3.69
+ 0.06
5.09
0.05
6.02
0004
29.21
0.3
33.62
37.31 0014
GRIN
3.05 0.00
4.52 2 0.0
5.82 2: 0.06
2.26 1 0:03
3:45 0.06
4.35 0.00
15.62
0:24
22.08
0.39
29:03 1:42
SPIN
2.71 0.02
3.32 + 0.2
3.87 = 0.05
1.78 1.83
2.15 + 0.03
2.41 8.02
14.29
0.34
18.71
24.34
SPIN-H
2.64 + 0.02
3.17 + 8.02
3.61 + 0.04
1.75 + 0.04
2.16 + 0.03
2.48 + o002
14.55 + 0.26
19.37 0.26
25.38 + 0.37
Computational complexity We recall that time and memory complexity of SPIN and SPIN- H scales with O ((Nmax + Emax) and O ((Nmax + KT), respectively. For the sake of comparison, here we also report the asymptotic complexity for the spatiotemporal Transformer and GRIN. The Transformer alternates temporal attention O (Nmax and spatial attention O (TN max) with resulting O ((Nmax + T) T) complexity. As pertaining to GRIN, let R be the spatial receptive field (i.e., number of graph convolution layers) of the inner MPGRU cell. Then, GRIN's time complexity scales with O (Tx)) in the unidirectional model. Note that while most of the operations in the attention-based models can be executed in parallel, GRIN needs to process the entire sequence sequentially, with consequent slowdown.
5.2 Results
Table reports experimental results. Both SPIN methods outperform the baselines in almost all scenarios. Not surprisingly, improvements are more evident when entire blocks of data are missing, as in the AQI datasets and Block missing settings. Differently from the autoregressive methods, the sparse spatiotemporal attention mechanism of SPIN, in fact, allows for propagating far-apart observations without the need for intermediate and biased predictions. Conversely, in the Point missing setting, SPIN methods perform on par with the state of the art. With respect to the spatiotemporal Transformer, SPIN performs better in all settings except for AQI-36, which can be attributed to the ineffectiveness of spatial attention alone in determining the dependencies among the different spatial locations. Notice also that, in almost all cases, SPIN-H performs par with SPIN (even better the smaller dataset AQI-36), making it a valid lightweight alternative to SPIN.
To further assess the advantages of SPIN in reconstructing sequences with highly sparse observations, we compare our methods against the most relevant baselines on the same datasets, but considering two additional scenarios with increased sparsity. In the first setting, the missing rate is progressively increased by associating to each observation an increasing probability p of being removed; this corresponds to sparser version of the Point missing scenario of the previous experiment. In the second case, we instead operate in the Block missing setting by increasing the probability fo of a failure at each step, i.e., the probability for each sensor of going offline for random number ~ (12, 36) of future (consecutive) time steps. In practice, we test the models on the same test split of the previous experiment but, instead of using the previous evaluation masks, we update them according to the different missing data distributions. Note that higher missing rates and failure probabilities correspond to higher numbers of (consecutive) missing values. In the Block missing case,

---

failure probabilities p 5% p 10%, and p 15% correspond to a missing rate of = 70-75%. 90-92%, and 96-97%, respectively. For the traffic datasets, we use the weights of the models trained on the Point missing setting of [Tall 1 Table 2 and [Table 3 show results (in terms of MAE) averaged over different evaluation masks for both scenarios and across different missing rates and failure probabilities. In all the considered experiments, SPIN-based models rank as the best-performing methods for any sparsity level. Moreover, our approach is robust to changes in the missing data distribution. In fact, compared to the baselines, the performance of both SPIN and SPIN-H deteriorates at a slower rate as the sparsity data increases. Notably, GRIN would require much more data to match the performance of SPIN, and the improvement over other iitention-basedd methods, i., SAITS and Transformer, is also striking.
6 Conclusion and Future Works
We introduced a graph-hased architecture, named SPIN, to reconstruct missing observations in sparse spatiotemporal time series. To overcome the major limitations of autoregressive methods, we designed a novel sparse spatiotemporal attention mechanism to propagate valid observations through discrete points in time and space, jointly. Furthermore, we showed how the time and space complexities of the approach can be drastically reduced by considering a novel hierarchical attention mechanism. Empirical analysis shows that the proposed method outperforms by a wide margin oa-e-of-the--. art methods for imputation in highly sparse settings. We noticed that in some extremely sparse training settings, SPIN might suffer from a lack of supervision that may slow down learning; future works might try to address this problem by introducing an additional auxiliary learning task. Other possible extensions could investigate spatiotemporal positional encoding methods and their application in SNs.
Acknowledgements
This work was supported by the Swiss National Science Foundation project FNS 204061: Higher- Order Relations and Dynamics in Graph Neural Networks. The authors wish to thank the Institute of Computational Science USI for granting access computational resources.
References
[1] Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, pages 362-373. Springer, 2018.
[2] Yaguang Li. Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net- work: Data-driven traffic forecasting. In International Conference on Learning Representations, 2018.
[3] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chenggi Zhang. Graph wavenet for deep spatial-temporal graph modeling. arXiv preprint arXiv:1906.0012// 2019.
[4] Andrea Cini, Ivan Marisca, and Cesare Alippi. Filling the g_ap_s: Multivariate time series imputation by graph neural networks. In International Conference on Learning Representations, 2022. URL
net/ htt.//fommmiidx0uu S3vJ7
[5] Jinsung Yoon, William R Zame, and Mihaela van der Schaar. Multi-directional recurrent neural networks: novel method for estimating missing data. In Time Series Workshop at the 34th International Conference Machine, pages 1-5,2017 2017.
[6] Wei Cao, Dong Wang, Jian Li, Hao Zhou, Yitan Li, and Lei Li. Brits: bidirectional recurrent imputation for time series. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 6776-6786, 2018
[7] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-80, 2008.
10

---

[8] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34 (4):18-42, 2017.
[9] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263- 1272. PMLR, 2017.
[10] Peter W Battaglia, Jessica Hamrick, Victor Bapst, Alvaro Sanchez-Goozzlez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1xXiv:806.01126 2018.
[11] David Ha and Yujin Tang. Collective intelligence for deep learning: A survey of recent developments. arXiv preprint arX17 2021.
[12] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 18880000005 2018.
Ming-Wei
[13] James Durbin and Siem Jan Koopman. Time series analysis by state space methods. Oxford university press, 2012.
[14] J Kihoro, K Athiany, et al. Imputation of incomplete nonstationary seasonal time series data. Mathematical Theory and Modeling, 3(12):142-155 2013.
[15] Xiuwen Yi, Yu Zheng, Junbo Zhang, and Tianrui Li. St-mvl: Filling missing values in geo- sensory time series data. In Proceedings of the Twenty-Fijf International Joint Conference on Artificial Intelligence, IJCAI 16, page 2704-2710. AAAI Press, 2016. ISBN 9781577357704.
[16] Lorenzo Beretta and Alessandro Santaniello. Nearest neighbor imputation algorithms: a critical evaluation. BMC medical informatics and decision making, 16(3):197-208, 2016.
[17] Andrzej Cichocki and Anh-Huy Phan. Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE transactions on fundamentals of electronics, communications and computer sciences, 92(3):708-772 2009.
[18] Hsiang-Fu Yu, Nikhil Rao, and Inderjit S Dhillon. Temporal regularized matrix factorization for high-dimensional time series prediction. Advances in neural information processing systems, 29:847-855, 2016.
[19] Nikhil Rao, Hsiang-Fu Yu, Pradeep Ravikumar, and Inderjit S Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. NIPS, volume 2, page 7. Citeseer, 2015.
[20] Zhengping Che, Sanjay Purushotham, Kyunghyun Cho, David Sontag, and Yan Liu. Recurrent neural networks for multivariate time series with missing values. Scientific reports, 8(1):1112, 2018.
[21] Xiaoye Miao, Yangyang Wu, Jun Wang, Yunjun Gao, Xudong Mao, and Jianwei Yin. Generative semi-supers superviie learning for multivariate time series imputation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8983-8991, 2021.
[22] Ian Goodfellow, Jean Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil
[23] Jinsung Yoon, James Jordon, and Mihacla Schaar. Gain: Missing data imputation using generative adversarial nets. In International Conference on Machine Learning, pages 5689- 5698. PMLR, 2018
[24] Yonghong Luo, Ying Zhang, Xiangrui Cai, and Xiaojie Yuan. E'gan: End-to-end generative adversarial network for multívariate time series imputation. In Proceedings of the Twenty- Fighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 3004-3100. International Joint Conferences Artificial Intelligence Organization, 7 2019.
11

---

[25] Wenjie Du, David Côté, and Yan Liu. Saits: Self-attention basedd imputation for time series. arXiv preprint arXiv:2202.08516, 2022.
[26] Yusuke Tashiro, Jiaming Song, Yang Song, and Stefano Ermon. Csdi: Conditional score-based diffusion models for probabilistic time series imputation. Advances in Neural Information Processing Systems, 34, 2021.
[27] Satya Narayan Shukla and Benjamin Marlin. Multi-time attention networks for irregularly sampled time series. In International Conference on Learning Representations, 2020.
[28] Yulia Rubanova, Ricky TQ Chen, and David K Duvenaud. Latent ordinary differential equations for irreullaly-samppled time series. Advances in neural information processing systems, 32, 2019.
[29] Zijie Huang, Yizhou Sun, and Wei Wang. Learning continuous system dynamics from ireeularly-saman sampled partial observations. Advances in Neural Information Processing Sys- tems, 33:16177-16187. 2020.
[30] Yukai Liu, Rose Yu, Stephan Zheng, Eric Zhan, and Yisong Yue. Naomi: Non-autoregressive multiresolution sequence imputation. Advances in Neural Information Processing Systems, 32: 11238-11248, 2019.
[31] Siyuan Shan, Yang Li, and Junier B Oliva. Nrtsi: Non-recurrent time series imputation. arXiv preprint a1X1v:2102.03340, 2021.
[32] Yuebing Liang, Zhan Zhao, and Lijun Sun. Dynamic spatiotemporal graph convolutional neural networks for traffic data imputation with complex missing patterns. arXiv preprint arXiv:2109.08357, 2021.
[33] Yongchao Ye, Shiyao Zhang, and James JQ Yu. Spatial-temporal traffic data imputation via graph attention convolutional network. In International Conference on Artificial Neural Networks, pages 241-252. Springer, 2021.
[34] Sanmukh R. Kuppannagari, Yao Fu, Chung Ming Chueng, and Viktor K. Prasanna. Spatio- temporal missing data imputation for smart power grids. In Proceedings of the Tweifth ACM International Conference on Future Energy Systems, e-Energy '21, page 458-465, New York. NY, USA, 2021. Association for Computing Machinery, ISBN 978 178114500 450383332. doi: 10.
1447555.3466586. URL
111p/4441.1455/445555555 3466586
[35] Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv: 1803.88033355 2018.
[36] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[37] Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In 34th Conference on Uncertainty Artificial Intelligence 2018 UAI 2018, 2018
[38] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang. and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In Interna- tional Joint Conference on Artificial Intelligence (IJCAI). pages 1548-1554, 2021.
[39] Chuanpan Zheng, Xiaoliang Fan, Cheng Wang, and Jianzhong Qi. Gman: A graph multi- attention network for traffic prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1234-1241, 2020.
[40] Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. Attention based spatial- temporal graph convolutional networks for traffic flow forecasting. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 922 929,9999999 2019.
[41] Zonghan Wa, Da Zheng, Shirui Pan, Quan Gan, Guodong Long, and George Karypis. Tra- versenet: Unifying space and time message passing for traffic forecasting. IEEE Tronsactions on Neural Networks and Learning Systems, 2022.
12

---

[42] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. Advances in neural information processing systems, 32, 2019.
[43] Indro Spinelli, Simone Scardapane, and Aurelio Uncini. Missing data imputation with adversarially-trriied graph convolutional networks. Neural Networks, 129:249-200 2200, 2020.
[44] Jiaxuan You, Xiaobai Ma, Daisy Yi Ding, Mykel Kochenderfer, and Jure Leskovec. Handling missing data with graph representation learning. Neural Information Processing Systems (NeurIPS, 2020.
[45] Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong. and Michael Bronstein. On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features. arXiv preprint arXiv: I. 121222 2021.
[46] Clive WJ Granger. Investigating causal relations by econometric models and cross-spectral methods. Econometrica: journal of the Econometric Society, pages 424-438, 1969.
[47] Weifeng Liu, Puskal P Pokharel, and Jose C Principe. Correntropy: Properties and applications in non-gaussian signal processing. IEEE Transactions on signal processing, (5261)558665598 2007.
[48] Thomas Kipf. Ethan Fetaya, Kuan-Chich Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning. PMLR, 2018.
pages
[49] Jinsung Yoon, William Zame, and Mihaela van der Schaar. Estimating missing data in temporal data streams using multi-directions recurrent neural networks. IEEE Transactions on Biomedical Engineering, 66(5):1477-14)) 2018
[50] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
[51] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: /409.04333 2014.
[52] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020. URL htttps://ppereevieet
[53] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020. URL https:// ntt/ffrrmm id Hkx Hkx1qkkrPPr
[54] Joshua Ainslie, Santiago Ontañón, Chris Alberti, Philip Pham, Anirudh Ravula, and Sumit Sanghai. Ete: Encoding long and structured data in transformers. CoRR, abs/2004.08483, 2020. URL /ttptttss////xii..a org/
abs/ wwtp:///////aaa/a///eeeaaee
08483
[55] Seyed Mehran Kazemi, Rishab Goel, Sepehr Eghbali, Janahan Ramanan, Jaspreet Sahota, Sanjay Thakur, Stella Wu, Cathal Smyth, Pascal Poupart, and Mareus Brubaker. Time2vec: Learning vector representation of time. arXiv preprini (oXXiv:990700555 2019.
[56] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnbll structural and positional representations. In International Conference on Learning Representations, 2022. URL id=wIT]nvGphYJ]
[57] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32:8026-8037, 2019.
13

---

[58] Andrea Cini and Ivan Marisca, Torch Spatiotemporal, 3 2022. URL https:://gtthiii com/
[59] Yu Zheng, Xiuwen Yi, Ming Li, Ruiyuan Li, Zhangqing Shan, Eric Chang, and Tianrui Li. Forecasting fine-grained air quality based on big data. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 2267-2276, 2015.
[60] lan R White, Patrick Royston, and Angela M Wood. Multiple imputation using chained equations: issues and guidance for practice. Statistics in medicine, 30(4))377-399 2011.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 4 [nd
(b) Did you describe the limitations of your work? [Yes] Assumptions discussed in
Section limits Sections #and 6
(c) Did you discuss any potential negative societal impacts of your work? [No] do not see any potential harm to society in the proposed method.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We provide the experimental setup, as well all datasets used, supplementary material.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] As supplementary material.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] As supplementary material.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] We provide links to datasets and code
that contain also information about the license.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "MYRntLxLbQW", "reviewer": "Reviewer_K4Xt", "summary": "This paper introduces SPIN, a spatiotemporal graph network with a new spatiotemporal attention for reconstructing missing data points in multivariate time series. The proposed attention mechanism consists of the inter-node cross-attention and the intra-node self-attention. Compared to the autoregressive methods propagating the biased representations, one advantage of SPIN is that the reconstruction only relies on the observations. They also propose the hierarchical attention to reduce the computational cost. Their empirical evaluation shows that SPIN outperforms existing baselines generally and is clearly advantageous when the missing ratio is large. ", "questions": "1. What is $w_\\alpha$ in equation (7)? Is it a learnable paramter?\n2. Why do you use the Bahdanau attention instead of the dot-product attention? ", "limitations": "I can find one sentence in the conclusion discussing the limitation. But I don't find any discussion about the potential societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The paper tackles an important problem and the proposed spatiotemporal attention mechanism is sound.\n* The visualizations of the model architecture and the attention mechanism are illustrative and help in understanding.\n* The method section is well structured and easy to follow even though there are many design details.\n* The related work section offers a good overview of the existing work.\n\nWeaknesses:\n\n1. Although the quantitative results show the effectiveness of the method, it would be even better if there are qualitative results visualizing either the imputed data points or the cross-attention weights and self-attention weights.\n2. Although the authors compare the computation complexity between SPIN and SPIN-H, it would be more comprehensive if the comparison to baselines in terms of time cost or memory cost could be reported.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LtY__L7_qXN", "reviewer": "Reviewer_tTGX", "summary": "In this paper, the authors propose an attention-based model for missing data reconstruction from spatiotemporal graphs. The core part of the method is a sparse spatiotemporal attention mechanism that learns representations localized in time and space from sparse data. Empirical results show that the proposed method outperforms existing approaches, especially when the missing rate is high.", "questions": "1. Line 56: “Conversely”. From my understanding of the proposed “spatiotemporal cross-attention” and “temporal self-attention”, they also set the attention coefficients of spatiotemporal points with missing values to zero. How is this method different from the so-called “trivial way”: constraining the attention coefficients of time steps corresponding to missing data to zero?\n2. Line 58: “we seek to design an architecture where each processing stage is aligned with the task of reconstructing missing spatiotemporal observations.”. How is the design in each stage aligned with the task of reconstructing?\n3. Line 60: “Our model can be seen as a learned, self-organizing, spatiotemporal diffusion process”. How is it related to the diffusion process?\n4. Line 66: “reconstructing observations at arbitrary locations”. As described in lines 265-266, the spatial encoding is trained as learnable parameters different for each node. How can the proposed method reconstruct observations at arbitrary locations? What if the queried location has never appeared in training data and its embedding is never defined in training? The method actually assumes that the locations in evaluation are exactly the same locations in training.\n5. Line 71: “ equipped with inductive biases that make the model tailored for the multivariate time series imputation task”. What is the inductive bias that makes the model tailored for the multivariate time series imputation task?\n", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The writing is clear and the figures are illustrative.\n2. Experiments show promising results.\n\nWeaknesses:\n1. Some claims are questionable and might be over-claimed (see “Questions”).\n2. There are already some works on sparse attention with spatiotemporal data. (For example, [1] has a similar idea of utilizing valid spatiotemporal data points only to generate representations. There might be more works along this line though.) The authors shall provide more context of sparse attention with spatiotemporal data. \n3. The authors should have more ablation study experiments to explain the effect of the claimed contributions - sparse spatiotemporal attention mechanism, the inductive biases, etc.\n4. In Figure 1, there should be an “MLP” block between the concatenation of (spatiotemporal cross-attention, temporal self-attention, skip connection) and “Add & Norm”, according to Equation 12.\n\n[1]. Huang, Z., Sun, Y., & Wang, W. (2020). Learning continuous system dynamics from irregularly-sampled partial observations. Advances in Neural Information Processing Systems, 33, 16177-16187.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HSI-O2Hrmqi", "reviewer": "Reviewer_PQtk", "summary": "The paper proposes two variants (a basic one, SPIN, and a hierarchical one, SPIN-H) of attention-based message-passing networks to learn representations of a multivariate time series over a static graph, and which cope well with a large amount of missing data. The network learns representations that can reconstruct missing observations not only from the other temporal data at the node, but also from its neighboring nodes. Its experimental performance is better than other state-of-the art methods when a long sequence of temporal data is missing (\"block missing\") or when the amount of missing data is large, and comparable to the best methods when data are removed i.i.d in time (\"point missing\") in a moderate amount (<= 50%). \n\n", "questions": "1) SPIN is designed to handle blocks of missing data at one point over a long period of time. In Table 2, the amount of missing data gets very large, but are the data removed i.i.d (as in the point missing model of Table 1) or not (e.g., by picking some nodes which lose a lot of data?)\n\n2) SPIN-H is computationally less expensive than SPIN by a K/T factor, but Appendix A shows that the number of parameters is 10 fold larger. How do you compare the two in that regard? How do you assess the cost of introducing an information bottleneck mentioned at L255?\n\n3) Why does SPIN-H work better than SPIN on AQI-36, and worse on AQI (Table 1)? \n\n4) Why does SPIN-H work better on the two other datasets PEMS-BAY and METR-LA when the amount of missing data is >= 50% (Table 2) and worse when the  the amount of missing data is = 25% (Table 1)? Does the hierarchy provide some form of regularization, like graph sub-sampling, which large amounts of missing data?\n\n5) In eq (7), how is w_\\alpha obtained - directly from (5)?\n\n6) Minor nits: What does the green surface on the left of Fig 2 represent? \nTypos at L119 (Pearson and not Person), L161 (adds and not add), L206 (to weigh and not to weight).\n\n-----------------------------------------------------------\n\nUpdate after discussion with authors: The rebuttal addresses (most of) my comments. The new results of Appendix E strengthen the interest of SPIN(-H) over other benchmarks. I still think that the paper would benefit from a deeper comparative analysis of the computational and memory complexities of SPIN vs SPIN-H, as well as vs the other benchmarks, and I understand from the authors' reply in the discussion that this will be done. I agree with the other reviewers that the paper impact might be limited, but overall I find the paper to be well written and bringing a contribution to the state of the art, hence my score for the review. \n", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written, and the approach makes sense, in particular to cope with long blocks of missing data a particular node. \n\nThe performance of SPIN and SPIN-H is compared empirically to multiple benchmarks in Section 5, but only under the perspective of MAE performance. In particular, the computational and memory complexities are not compared to these methods, although the justification for SPIN-H is precisely a decrease in complexity by a factor K/T over SPIN, where K << T is the number of \"hubs\" added in the network and T the length of the time-sequence taken for learning.\n\nThe paper could investigate deeper other properties of SPIN and SPIN-H (see also below).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9y51eDhKmUo", "reviewer": "Reviewer_PQKX", "summary": "The paper presents a novel neural architecture for the imputation task in the context of multivariate spatio temporal series (for instances in sensor networks). The core idea is derived from the constatation that autoregressive models for this task are prone to error propagation, especially in the case of huge sparsity of available data. The authors propose to use an attention mechanism - spatial and temporal - in order to learn representations of the graph nodes and to use those embeddings to derivate the missing values rather than the values of previous/next temporal steps. The model is derived from the now classical GNN framework. A spatio-temporal cross-attention layer is proposed for the message passing between nodes and a temporal self-attention layer for the inference of a context representation vector of the time history of the considered node. Two approaches are presented to reduce the time complexity of the learning phase, the first one using classic subsampling methods in graphs, and the other one based on a hierarchical attention mechanism. Experiments are conducted on 4 datasets to compare the proposed approach to state of the art methods.  ", "questions": "* Ablation study : I wonder what is exactly the role of the self-attention intra-node mechanism and I am curious of the results if this element is not used ?\n* Spatiotemporal positional encoding : there is very few discussion in the article about the importance of the spatiotemporal positional encoding nor analysis of the learned representations, can  you provide some insights on the importance of accurate/not accurate initial spatial information ? It is possible to analyze the learned representations to tell something about the sensors geographic distribution ?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* the paper is well written, easy to follow\n* the SOTA is well covered and the proposed approach is well positioned\n* I found the proposed model original, clever, and very well explained.\n* The novelty is not great as a lot of research has been devoted to the subject of GNN and time series, but the proposed architecture is elegant and intuitive. \n\nWeaknesses : \n* Further experiments and analyses would have been useful to assess the real capabilities of the model (see section Questions).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept