Filling the G_ap_s: Multivariate Time Series Imputation by Graph Neural Networks
Authors: Andrea Cini
Ivan Marisca
Cesare Alippi
Venue: ICLR 2022 Poster (2022)
Keywords: graph neural networks
missing data
time series analysis
time series imputation

Abstract: Dealing with missing values and incomplete time series is a labor-intensive, tedious, inevitable task when handling data coming from real-world applications. Effective spatio-temporal representations would allow imputation methods to reconstruct missing temporal data by exploiting information coming from sensors at different locations. However, standard methods fall short in capturing the nonlinear time and space dependencies existing within networks of interconnected sensors and do not take full advantage of the available - and often strong - relational information. Notably, most state-of-the-art imputation methods based on deep learning do not explicitly model relational aspects and, in any case, do not exploit processing frameworks able to adequately represent structured spatio-temporal data. Conversely, graph neural networks have recently surged in popularity as both expressive and scalable tools for processing sequential data with relational inductive biases. In this work, we present the first assessment of graph neural networks in the context of multivariate time series imputation. In particular, we introduce a novel graph neural network architecture, named GRIN, which aims at reconstructing missing data in the different channels of a multivariate time series by learning spatio-temporal representations through message passing. Empirical results show that our model outperforms state-of-the-art methods in the imputation task on relevant real-world benchmarks with mean absolute error improvements often higher than 20%.

Published as a conference paper at ICLR 2022
FILLING THE A: MULTIVARIATE TIME SERIES IMPUTATION BY GRAPH NEURAL NETWORKS
Andrea Cini"!, Ivan Marisca"), Cesare A 'The Swiss AI Lab IDSIA, Università della Svizzera italiana "Politecnico di Milano
ABSTRACT
Dealing with missing values and incomplete time series is labor-intensive, te- dious, inevitable task when handling data coming from real-world applications. Effective spatio-temporal representations would allow imputation methods to re- construct missing temporal data by exploiting information coming from sensors at different locations. However, standard methods fall short in capturing the nonlin- ear time and space dependencies existing within networks interconnected sen- sors and do not take full advantage of the available and often strong relational information. Notably, most state-of-thee ff-thhe-rtt art imputation methods based on deep learning do explicitly model relational aspects and, in any case, do not exploit processing frameworks able to adequately represent structured spatio-temporal data. Conversely, graph neural networks have recently surged in popularity as both expressive and scalable tools for processing sequential data with relational inductive biases. In this work, we present the first assessment of graph neural networks in the context of multivariate time series imputation. In particular, we introduce a novel graph neural network architecture, named GRIN, which aims reconstructing missing data in the different channels of a multivariate time series by learning spatio-temporal representations through message passing. Empirical results show that our model outperforms state-of- ffte--of-thearre art methods in the imputation task on relevant real-world benchmarks with mean absolute error improvements often higher than 20%.
INTRODUCTION
Imputation of missing values is prominent problem in multivariate time-series analysis (TSA) from both thcoretical and practical perspectives (Little & Rubin 2019). In fact, in a world of complex in- terconnected systems such as those characterizing sensor networks or the Internet of Things, faulty sensors and network failures are widespread phenomena that cause disruptions in the data acqui- sition process. Luckily, failures of these types are often sparse and localized at the single sensor level, i.e., they do not compromise the entire sensor network once. In other terms, the case that, at certain time step, missing data appear only at some of the channels of the result- ing multivariate time series. In this context, spatio-temporal imputation methods (Yi et al. 2016 Yoon al. 2018b) aim reconstructing the missing parts of the signals by possibly exploiting both temporal and spatial dependencies. reconstruct missing values by taking into account past and future values, and the concurrent mea- surements of spatially close neighboring sensors too. Here, spatial similarity does not necessarily mean physical (e.g., geographic) proximity, but rather indicates that considered sensors are related w.r.t. a generic (quantifiable) functional dependency (e.g., Pearson correlation or Granger causality Granger 1969) and/or that are close in a certain latent space. Relational information, then, can be interpreted as a set of constraints linking the different time series that allows replacing the malfunctioning sensors with virtual ones.
often
particular, effective spatio-temporal approaches would
Among different imputation methods, approaches based on deep learning (LeCun et al. 2015 Schmidhuber 2015 Goodfellow et al., (016)) have become increasingly popular ( YYonn et al. 201 8a Cao et al. 201 8 Liu et al. 2019). However, these methods often completely disregard available rela- tional information or rely on rather simplistic modifications of standard neural architectures tailored
"qqual contribution. Correspondence andrea. cini (usui.....

---

Published as a conference paper at ICLR 2022
for sequence processing (Hochreiter & Schmidhuber 1997. Chung et al. 2014 Bai et al. 2018 Vaswani et al. 2017). We argue that stronger, structural, inductive biases are needed to advance the state of the art in time series imputation and allow to build effective inference engines in the context of large and complex sensor networks as those found in real-world applications.
In this work, model input multivariate time series as sequences of graphs where edges represent relationships among different channels. We propose graph neural networks (GNNs) (Scarselli et al.) 2008 Bronstein al. 2017; Battaglia al. 2018) as the building block of a novel, bidirectional, recurrent neural network for multivariate time series imputation (MTSI). Our method, named Graph Recurrent Imputattion Nenwork (GRIN), has at its core recurrent neural network cell where gates are implemented by pressage-passingg neural networks (MPNNs; Gilmer et al.] 2017). Two of these networks process the input multivariate time series in both forward and backward time directions at each node, while hidden states are processed by a message-passienn constrained to learn how to perform imputation by looking at neighboring nodes. In fact, by consid- ering each edge soft functional dependency that constraints the value observed at corresponding nodes, we argue that operating in the context of graphs introduces a positive inductive bias for MTSI. Our contributions are manifold: 1) we introduce a methodological framework to exploit graph neural networks in the context of MTSI, 2) we propose a novel, practical and effective implementation of a GNN-based architecture for MTSI, and 3) we achieve -ate-offtthe-at results on several and varied MTSI benchmarks. Our method does not rely on any assumption on the distribution of the miss- ing values (e.g.. presence and duration of transient dynamics and/or length of missing sequences) other than stationarity of the underlying process. The rest of the paper is organized as follows. In Section
imputation layer which is
/ we diseuss the related works. Then, in Section 3 we formally introduce the problem set- tings and the task of MTSI. We present our approach to MTSI in Section 4 by describing the novel framework to implement imputation architectures based on GNNs. We proceed with an empirical evaluation of the presented method against state-of-the-art baselines in Section 5 and, finally, we draw our conclusions in Section 6
RELATED WORKS
Time series imputation There exists a large literature addressing missing value imputation in time series. Besides the simple and standard interpolation methods based on polynomial curve fitting. popular approaches aim at filling up missing values by taking advantage of standard forecasting methods and similarities among time series. For example, several approaches rely on k-nearest neighbors (Troyanskaya et al. 2001 Beretta & Santaniello 2016). the expectation intittttiiommimmizzttiin algorithm (Ghahramani & Jordan| 1994, Nelwamondo et al. 2007) or linear predictors and state- |012|KKihrro
space models (Durbin & Koopman| 2012 Kihoro et al. [2013). Low-rank approximation methods, such as matrix factorization (Cichocki & ( are also popular alternatives which can also account for spatial (Cai et al.) 2010: Rao et al. 2015) and temporal (Yu et al. 2016; Mei et al.) 2017) information. Among linear methods, STMVL (Yi et al. 2016) combines temporal and spatial interpolation to fill missing values in geographically tagged time series.
More recently, several deep learning approaches have been proposed for MTSI. Among the oth- ers, deep autoregressive methods based recurrent neural networks (RNNs) found widespread
success (Lipton et al. 2016 Che et al. 2018 Luo et al. 2018 Yoon et al., 2018b Cao et al. 2018). GRU-D (Che et al. 2018) learns how to process sequences with missing data by controlling the decay of the hidden states of a gated RNN. Cao et al. (2018) propose BRITS, a bidirectional GRU-D-like RNN for multivariate time series imputation that takes into account correlation among different channels to perform spatial imputation. Other successful strategies in the literature have been proposed that exploit the adversarial training framework to generate realistic reconstructed se- quences Yoon et 2001[118a|] Fedus et al. [2018] Luo et al.) 2018 2019). Notably, GAIN (Yoon et al.) 2018a) uses GANs (Goodfellow et al., 2014) to learn models that perform imputation in the i.i.d. settings. Luo et al.) (2018) aim, instead, at learning models that generate realistic synthetic se- quences and exploit them to fill missing values. MMao et al. (202 use an approach similar to GAIN, but condition the generator on the predicted label for the target incomplete time series. Concurrently to our work, Kuppannagari et al. (202I) developed a graph-based spatio-temporal denoising autoen- coder for ceatio-tempora data coming from smart grids with known topology. Liu et al. (201)), instead, uses adversarial learning to train a multiscale model that imputes highly sparse time series in hierarchical fashion. However, we argue that none of the above-cited methods can take full
2

---

Published as a conference paper at ICLR 2022
EXTRAC GRAMH
N
T
W
G
Figure 1: Representation of a multivariate time series as sequence of graphs. Red circles denote nodes with missing values, nodes are identified.
advantage of relational information and nonlinear spatio-temporal dependencies. Most importantly the above methods do not fully exploit the flexibility and expressiveness enabled by operating in the context of graph processing.
Graph neural networks for TSA Graph neural networks have been exploited in TSA mostly in spatio-temporal forecasting methods. The idea behind most of the methods present in the literature to modify standard neural network architectures for sequential data by relying on operators that work in the graph domain. For example, Secle,,SSceeeeee et al. (2188) propose GRU cell where gates are imple- mented by spectral GNNs (Defferrard et 2016); Li et al. (2018) propose an analogous architecture replacing spectral GNNs with diffusion-convolltiin
network (Atwood & 'Towsley] 2016). Note that these models are different w.r.t. approaches that use recurrent networks to propagate information graph-wise (Scarselli et al. 2008 [i et al. 2016). Yu et al. (2017) and/Wu et al. (2019) 2020b) pro- pose, instead, spatio-temporal convolutional neural networks that alternate convolutions on temporal and spatial dimensions. Similar approaches have also been studied in the context of attention-based models (Vaswani et al.) (017)) with spatio-temporal Transformer-lis
architectures (Zhang et al., 2018 Cai al., 2020). Another particularly interesting line of research is related the problem of learning the graph structure underlying input multivariate time series (Kipf et al. [0088] Wu al. 2020b] [Shang et al., 2020). While previously mentioned approaches focus on multivariate time series prediction, other methods aim at predicting changes in graph topology (Zambon et al.) Paassen et al. 2020). Conversely, methods such as Temporal Graph Networks (Rossi et al, 2020 are tailored to learn node embeddings in dynamical graphs. Finally, recent works have pro- GNNs for imputing missing features in the context of i.i.d. data. Among the others, Spinelli et al. (2020) propose adversarial framework to train GNNs on the data reconstruction task, while You et al. (2020) propose a bipartite graph representation for feature imputation. Lately, GNNs have also been exploited for spatial interpolation (Appleby al., 2020 Wu et al.) (020a) sometimes
2019
posed
referred to as kriging (Stein) 1999). To the best of our knowledge, no previous GNN-based method targeted missing value imputation for generic multivariate time series.
PRELIMINARIES
Sequences of graphs We consider sequences of weighted directed graphs, where we observe graph G. with N, nodes at each time step I. A graph is couple G. (Xt, W,), where X; RRN xd is the node-attribute matrix whose i-th row contains the d-dimensional node-attribute vector of E Rd associated with the i-th node; entry v.. of the adjacency matrix W. < N.N, denotes the scalar weight of the edge (if any) connecting the i-th and j-th node. Fig. D exemplifies this modelling framework. We assume nodes to be identified, i.c., to have a unique ID that enables time-wise consistent processing. This problem setting can be easily extended more general classes of graphs with attributed edges and global attributes. In this work, we mainly focus on problems where the topology of the graph fixed and does not change over time, i.e. at each time step W. W and N, N.
Any generic multivariate time series fits the above framework by letting each channel of the se- quence (i.e., each sensor) correspond to a node and using the available relation information to build an adjacency matrix. no relational information is available, one could use the identity matrix, but this would defeat the purpose of the formulation. A more proper choice of W, can be made using any standard similarity score (e.g.. Pearson correlation) or a (thresholded) kernel. A more advanced approach instead could aim at learning an adjacency directly from data by using, for instance, spatial attention scores or resorting to graph learning techniques, K.g., et al, (2018). From now on, we assume that input multivariate time series have homogeneous channels, L.e,, sensors of the same
3

---

Published as a conference paper at ICLR 2022
type. Note that this assumption does not imply loss in generality: it is always possible to standard- ize node features by adding sensor rype attributes and additional dimensions to accommodate the different types of sensor readings. Alternatively, one might directly model the problem by exploiting heterogeneous graphs (Schlichtkrull et al. 2018).
Multivariate time series imputation To model the presence of missing values, we consider, at each step, binary mask M, E {0, 1)N,.xc where each row mi indicates which of the corresponding node attributes of æc are available in X,, It follows that, my 1.j 0 implies x; to be missing; conversely, if m = 1, then æt stores the actual sensor reading. We denote by X, the unknown ground truth node-attribute matrix, i.e., the complete node-attribute matrix without any missing data. We assume stationarity of missing data distribution and, in experiments, we mostly focus on the missing at random (MAR) scenario (Rubin 1976). We neither make assumptions on the number of concurrent sensor failures, nor on the length of missing data blocks, i.c., multiple failures extended over time are accounted for. Clearly, one should expect imputation performance to scale with the number of concurrent faults and the time length of missing data bursts.
The objective of MTSI is to impute missing values in sequence of input data. More formally, given a graph sequence G1.++T of length T. we can define the missing data reconstruction error as
(mi. E (#). )t.))
C X (IA4T X (LATT), M Mustm)
(1)
(m).. m))
where dj is the reconstructed a M (1.4T]] and mi are respectively the logical binary complement of Ma and mi. . is an element-wise error function (e.g., absolute or squared error) and (..)) indicates the standard dot product. Note that, in practice, it is impossible to have access to [1,+22] and, as a consequence, it is necessary to define a surrogate optimization objective by, for example, using forecasting loss or generating synthetic missing values. In the context of trainable, parametric, imputation methods, we consider two different operational settings. In the first one, named in-sample imputation, the model is trained to reconstruct missing values in given fixed input sequence X [I..+T]) i.e., the model is trained on all the available data except those that missing and those that have been removed from the sequence to emulate additional failures for evaluation. Differently, in the second one (referred to as oat-le-sample imputation), the model is trained and evaluated on disjoint sequences. Note that in both cases the model does not have access to the ground-truth data used for the final evaluation. The first operational setting simulates the case where a practitioner fits the model directly on the sequence to fill up its gaps. The second, instead, simulates the case where one wishes to use a model fitted on a set of historical data to impute missing values in an unseen target sequence.
4 GRAPH RECURRENT IMPUTATION NETWORK
In this section, we present our approach, the Graph Recurrent Imputation Network (GRIN), graph- based, recurrent neural architecture for MTSI. Given multivariate time series X [I.,+2] with mask Mr..T. our objective is to reconstruct missing values in the input sequence by combining the information coming from both the temporal and spatial dimensions. To do so, design novel bidirectional graph recurrent neural network which progressively processes the input sequence both forward and backward in time by performing two stages of imputation for each direction. Then, feed-forward network takes as input the representation learned by the forward and backward models and performs final refined- -imputation for each node of the graph and step of the sequence. More precisely, the final imputation depends on the output of two GRIN modules whose learned representations are finally processed (space and time wise) by a last decoding multilayer percep- tron (MLP). An overview of the complete architecture is given in Fig. 2 As shown in the figure, the two modules impute missing values iteratively, using at each time step previously imputed values as input. We proceed by first describing in detail the unidirectional model, and then we provide the bidirectional extension.
Unidirectional model Each GRIN module is composed of two blocks, apatio-tempora encoder and spatial decoder, which process the input sequence of graphs in two stages. The encoder maps the input sequence X [[. spatio-temporal representation H ((,T) E Nexl by
4

---

Published as a conference paper at ICLR 2022
Tixe
STAGE
2 STAGE IMPULATION
DEPUSATIION
H
9.
SPATE-GEMMP: ENCOIDINI
SPATIAL DECODING
MLF
Tine
STAGE DEPUSATTION
2 STAGE IMPURATTOON
Bur
[H
9.
SPATI-GTEMP. ENCODING
DECODING
pume
Valid value
Missing value
Imputed value
1st stage imputation
2nd stage imputation
Figure 2: An overview of the bidirectional architecture. Here, each unidirectional GRIN module is processing the 7-th step of an input sequence with dimensions (sensors). Two values are missing at the considered time step. GRIN performs first imputation, which is then processed and refined by the spatial decoder. These second-stage imputations are then used to continue the processing at the next step. An MLP processes learned representations node and time wise obtain final imputations.
exploiting ad-hoc designed recurrent GNN. The spatial decoder, instead, takes advantage of the learned representations to perform two consecutive rounds of imputation. first-stage imputation is obtained from the representation by using linear readout; the second one exploits available relational, spatial, information at time step f. In particular, the decoder is implemented by an MPNN which learns to infer the observed values at each i-th node æ. by refining first-stage imputations considering - locally - H and values observed at neighboring nodes.
Spatio-temporal Encoder In the encoder, the input sequence [1,++7] and mask M [. are processed sequentially one step at time, by means of a recurrent neural network with gates imple- mented by message-passing layers. Any pressage-passingg operator could be used in principle. In particular, given = i.e., the node features vector at layer k 1, we consider the general class of MPNNs described as
MPNN W.) = ( E Pk ( (z
zi,,,
where (chereN((i) (i) is the set of neighbors of the i-th node in Gt. "kk and Pk generic, differentiable, update and message functions (e.g., MI.Ps,, and Σ a permutation invariant, differentiable aggregation function (e.g., swm or mean). Note that several definitions of neighborhood are possible, e.g., one might consider nodes connected by paths up certain length 1. For the sake simplicity, from now on, indicate with MPNN(2i, 2 Wt) the forward pass of generic K-laayered message-passing, neural network. In the following, we use MPNNs as the building blocks for our spatio-temporal feature extractors. To learn the dynamics of the system, leverage gated recurrent units (GRUs; Cho et al. 2014). As previously mentioned, similarly to Seo et al. (2018) and [L et al. (2018), we implement the GRU gates by relying on the message-passing layers defined above. At the node level, the elements of the message-passing GRU (MPGRU) can be described as:
ri = (MPNN $ (2)
[m. [m W.))
(3)
3 (MPNN [
(2)
[m| W.))
(4)
c tanh Lanh(MPNN) (2))
m ||r! h; W.))
(5)
h uz C h;
ut)
(6)
where rí, uu are the reset and update gates, respectively, h is the hidden representation of the i-th node at time t, and (,(2) is the output of the decoding block at the previous time-step (see next paragraph). The symbols 3 and || denote the Hadamard product and the concatenation operator, spectively. The initial representation H,-1 can either be initialized as constant or with a learnable embedding. Note that for the steps where input data missing, the encoder is fed with predictions from the decoder block, as explained in the next subsection. By carrying out the above computation time and node wise, get the encoded sequence H (I.c-T]--
5

---

Published as a conference paper at ICLR 2022
Spatial Decoder As first decoding step, generate one-step-aheaud predictions from the hidden representations of the MPGRU by means a linear readout
2:0h H Vv + bn:
where Vn E IR is a learnable weight matrix and ba E IRd a learnable bias vector. We then define the filler operator
(Y,) M, X; M Yr;
(8)
intuitively, the filler operator replaces the missing values in the input X, with the values at the same positions in Y, By feeding (,() to the filler operator, we get the first-stage imputation X,
such that the output is X, with missing values replaced by the one-step-ahead predictions P.!1) The resulting node-level predictions then concatenated to the mask M, and the hidden representation H and processed by a final one-layer MPNN which computes for each node an imputation reprexentation st
p ((((( [1]])
Notice that, as previously highlighted, the imputation representations only depend on messages received from neighboring nodes and the representation at the previous step. In fact, by aggregating only messages from the one-hop neighborhood, the representations 8 are independent of the input features zi of the i-th node itself. This constraint forces the model to learn how to reconstruct a target input by taking into account spatial dependencies: this has regularizing effect since the model is constrained to focus on local information. Afterward, we concatenate imputation representation S, with hidden representation H,-1, 1, and generate second-stage imputations by using second linear readout and applying the filler operator:
(2) [S H V. b,;
+ DY, (2)
(10)
Finally, we feed X; as input to the MPGRU (Eq. 3 to update the hidden representation and proceed process the next input graph G411-
Bidirectional Model Extending GRIN to account for both forward and backward dynamics is straightforward and can be achieved by duplicating the architecture described in the two previous paragraphs. The first module will process the sequence in the forward direction (from the beginning of the sequence towards its end), while the second one the other way around. The final imputation is then obtained with MLP aggregating representations extracted by the two modules:
MLP(( ([s) 1 (.:fddd [|s band 1 4.bod I),
|
(11)
where fwd and bwd denote the forward and backward modules, respectively. The final output can then be easily obtained as [(..IT + ( (144))) Note that, by construction, our model can exploit all the available relevant spatio-temporil information, since the only value explicitly masked out for each node is æt. At the same time, it is important realize that our model does merely reconstruct the input as an autoencoder, but it is specifically tailored for the imputation task due to its inductive biases. The model is trained by minimizing the reconstruction error of all imputation stages in both directions (see Appendix
5 EMPIRICAL EVALUATION
In this section, we empirically evaluate our approach against state-of-the-art baselines on four datasets coming from three relevant application domains. Our approach, remarkably, achieves state- of-the-art performance on all of them.
Air Quality (AQI): dataset of recordings of several air quality indices from 437 monitoring stations spread across 43 Chinese cities. We consider only the PM2.5 5 pollutant. Prior works on imputation (Yi et al. 2016 Cao et al. 2018) consider a reduced version this dataset, including only 36 sensors (AQI-36 in the following). We evaluate our model on both datasets. We use as adjacency matrix a thresholded Gaussian kernel (Shuman et al. 2013) computed from pairwise geographic distances.

---

Published as a conference paper at ICLR 2022
Table I: Results on the air datasets. Performance averaged over 5 runs.
In In-sample
Out-of sample
D
M
MAB
MSE
MRE (%)
MAE
MSE
MRE (%)
Mean
53,48 + 0.00
4578.08
0000
76.77 0000
53.48
9000
4578.08
00.00
76.77 + 9:00
KNN
30.21 0.00
2892.31
= 00:00
43.36 0.00
30.21
= 0.00
2892.31
00.00
43.36 :: 0.00
MF
30.54
1 0.26
2763.06
= 63.35
43.84
0.38
AQI-36
MICE
29.89
0.31
2575.53
07.67
42.90
0.15
30.37
9.29
2594.06 U7:17
43.59 + 0.33
VAR
13.16
0:31
513.90 = 12.39
18.89
= 0.31
15.64
:: 0.08
833.46
13:85
22.02 :: 0.11
EGAIN
12.23 0.17
393.76
= 12,06
17.55
0.25
15.37
:: 0.26
641.92 i: 33,89
21.63 1: 0.36
BRITS
12.24 0.26
495.94
43.56
17.57
0.38
14.50
+ 0.35
662.36
65.16
20.41 0.50
MFG
12.46 + 0.35
517.21
= 41.02
0.50 15.09
17.88
16.79
=: 0.52
1 1103.04 + 106.3
23.63 = 0.73
GRIN
10.51 0.28
371.47
12.08 0.47
523.14 57.17
17.00 11 0.67
Mean
39.60 0,00
3231.04
1. 00:00
59,25 0.00
39.60 1. 0.00
3231.00 .04 00.00
59.25 1. 0.000
KNN
34.10
3471.14 =
51.02 = 0.00
34.10 = 0.00
1.41 14 00.00
51.02 + 0.00
MF
26.74 1.
2021.44 1. 27.98
40.01 0.38
MICE
26.39 0.13
1872.53 1. 15,99
39.49 0.19
26.98 1. 0.10
1930.92 10.08
40.37 1. 0.15
AQI
VAR
18.13
0.54
= 918.68
27.13
22.95
= 0.30
1402.84
52.63
33.99
+ 0.44
rG IN
17.69
0.17
861.66 = 17.49
26.48 = 0.25
21.78
= 0.50
1274.93
+ 6022
32.26
+ 0.755
BRITS
17.24
0.13
924.34 1 18.26
25.79 0.20
20.21 1. 0.22
1157.89
25.66
29.94
0.33
MPGRU
15.80
0,00
816.39
1. 08.09 99
23.63
0.08
18.76 1: 0.11
1194.35
1 15.23
27.79
1. 0.16
GRIN
13.10
0.08
615.80 10.09
19.60
0.11
14.73 0.15
775.91 28.49
21.82 0.33
we consider the PEMS-BAY and METR-LA datasets from Li et al. (0018). con- taining data from traffic sensors from the San Francisco Bay Area and the Los Angeles County Highway. We use the same approach of Li et al. (2018) and Wu et al. (2019) to obtain an adjacency matrix.
Traffic:
Smart grids: we consider data from the Irish Commission for Energy Regulation Smart
Metering Project (CER-F; Commission for Energy Regulation 2016). We select only the subset of the available smart meters monitoring the energy consumption of small and medium-sized enterprises (SMEs), i.e., 485 time series with samples acquired every 30 minutes. We build an adjacency matrix by extracting k-nearest neighbor graph (with
k 10) from the similarity matrix built by computing the correntropy (Liu et al. 2007) among the time series.
For the air quality datasets, we adopt the same evaluation protocol of previous works Yi et al. 2016 Cao al.) 2018) and we show results for both the in- in-samle and out-of- oo-sample settings. For the traf- fic and energy consumption datasets, we consider only the out-of-sample scenario (except for matrix factorization which only works in-sample). We simulate the presence of missing data by considering 2 different settings: 1) Block missing, i.e, at each step, for each sensor, we randomly drop 5% of the available data and, in addition, we simulate a failure with probability Pfaiture = 0.15% and sample its duration uniformly in the interval [min. steps, maz steps). where min and maz steps are the number of time steps corresponding respectively to 1 and hours in the traffic case and 2 hours and 2 days for CER-E; 2) Point missing, i.e., simply randomly mask out 25% of the avail- sets. We use as performance metrics
able data. We split all the datasets into vaining/validation// the mean absolute error (MAB), mean squared error (MSE) and mean relative error (MRE: Cao et al. 2018) computed over the imputation window. For all the experiments, we use as message- passing operator the diffusion convolution introduced by Atwood & Towsley (2016). We consider BRITS (Cao et al. 2018) as the principal competing alternative among non-ad adversarial deep autore- gressive approaches, as it shares architectural similarities with our methods. additional baselines we consider: 1) MEAN, i.e., imputation using the node-level average; 2) KNN, i.e., imputation by averaging values of the k 10 neighboring nodes with the highest weight in the adjacency matrix W.; 3) MICE (White et al. 2011 I. limiting the maximum number of iterations to 100 and the num- ber of nearest features to 10; 4) Matrix Factorization (MF) with rank = 10: 5) VAR, i.e., a Vector Autoregressive sne-ttep-aheee ahead predictor; 6) rGA i.c., unsupervised version of SSGAN (Miao) jtt al., 2 which can be seen as GAIN (Yoon et al., 2018a) with bidirectional recurrent encoder and decoder; 7) MPGRU, a one-step-ahead GNN-bbsse predictor similar to DCRNN (Li al. 2018)
7

---

Published as a conference paper at ICLR 2022
Table 2: Results on the traffic and smart grids datasets. Performance averaged over runs.
Block missing
Point missing
D
M
MAE
MSE
MRB(%)
MAE
MSE
MRE(%)
Mean
5,46 0.00
87.56 0:30
8.75 + 0.00
5,42 +: 0.00
86.59 4:000
8.67 = 0.00
KNN
4.30 = 0.00
49,90 0.00
6.90
+ 0.00
4.30 + 0.00
49.80 0:000
6.88 = 0.00
PEMS- -AMS-BAY
MF
3.28 0.01
50.14
5.26
3.29 000
51.39 0.64
5.27 0.02
MICE
2.94 + 0.02
28,28 0.57
4.71
+ 0.33
3.09 + 0.02
31.43 + 0.41
4.95 #: 0.02
VAR
2.09
16,06
3.35
1.30
6.52
2.07
IGAIN
2.18 6:01
13,96 0.20
3.50 + 0.02
1.88 + 0.02
10.37
+ 0.30
3.01 = 0.04
BRITS
1.70
10.50
2.72 + 0.01
1.47 + 0.00
7.94
2.36 + 0.00
MPGRU
1.59 0.00
14.19
0.11
2.56
1: 0.01
1.11
+: 0.00
7.59 0.02
1.77 :: 0.00
GRIN
1.14 0.01
6.60
0.10
1.83 1 0.02
0.67
+ 0.00
1.55 0.01
1.08 :: 0,00
Mean
7.48
139.54
12.96
7.56
142.22 0.00
13.10 0.00
KNN
7.79 = 0.00
124.61
0.00
13.49
+ 0.00
7.88
+ 0.00
129.29 0.000
13.65 = 0.00
METR-LA
MF
5.46
109.61
9.46
0.04
5.56
113.46
9.62 +
MICE
4.22 0.05
51.07
1.25
7.31
+ 0.09
4.42 + 0.07
55,07 1.46
7.65 + 0.12
VAR
3.11
28.00
5.38
2.69
21.10
4.66
rGAIN
2.90 6:01
21.67 0.15
5.02 + 0.02
2.83 + 0.01
20.03 0.099
4.91 = 0.01
BRITS
2.34 6:01
17.00
4.05 + 0.01
2.34 +
16.46
4.05 = 0.00
MPGRU
2.57 0.01
25.15
0.17
4.44 1: 0.01
2.44 +: 0.00
22. 17 0.00
4.22 :: 0.00
GRIN
2.03 0.00
13.26
0.05
3.52 + 0.01
1.91 + 0.00
10.41
3.30 0.00
Mean
1.49 0.00
5,96
72.47 0.00
1.51 0:00
6.09
71.51 0.00
KNN
1.15 = 0.00
6.53 0.00
56.
+ 0.00
1.22 + 0.00
7.23 0.00
57.71
: 0.00
MF
0.97
4.38
47.20
0.11
1.01 + 0.00
4.65
47.87 # 46.59 # 0.25
CER-E
MICE
0.96 0:01
3,08 0.03
46.65
+ 0.44
0.98 + 0.00
3.21 + 0.04
VAR
0.64
1.75 0:06
31.21 +
0.53 - 0.00
1.26
24.94 = 0.02
rGAIN
0.74 0.00
1.77 0.02
36.06 + 0.14
0.71 + 0.00
1.62 + 0.0
33.45 = 0.16
BRITS
0.64 0.00
1.61 0.01
31.05 1: 0.05
0.64 1: 0.00
1.59 0.01
30.07 :: 0.11
MPGRU
0.53 0.00
1.84 0.01
25.88 1: 0.09
0.41 :: 0.00
1.22 0.01
19.51 :: 0.03
GRIN
0.42 0.00
1.07
20.24 0.04
0.29 0.00
0.53
13.71 0.03
We provide further comment and in depth details on baselines and datasets, together with additional experiments on synthetic data in the appendix.
5.1 RESULTS
Empirical results show that GRIN can achieve large improvements in imputation performance on several scenarios, as well as increased flcxibility. fact, differently from the other state-of-the- art baselines, GRIN can handle input with variable number of dimensions. Tab. [ shows the experimental results on the air quality datasets. In the in-sample settings, we compute metrics using as imputation the value obtained by averaging predictions over all the overlapping win- dows; in the out-of-sample settings, instead, we simply report results by averaging the error over windows. GRIN largely outperforms other baselines on both settings. In particular, in the lat- ter case, GRIN decreases MAE w.r.t. the closest baseline by more than 20% in AQI. Interest- ingly, GRIN consistently outperforms BRITS in imputing missing values also for sensors corre- sponding to isolated (disconnected) nodes, i.c., nodes corresponding to stations more than 40 km away from any other station (see B. this is empirical evidence the positive regularizations encoded into GRIN. Our method achieves more accurate imputation also in the 36-dimensional dataset, where we could expect the graph representation to have a lower impact. Results for the traffic and smart grids datasets are shown in Tab. 2 In the traffic dataset, our method outper- forms both BRITS and rGAIN by a wide margin in all the considered settings while using a much lower number of parameters (see A). In the traffic datasets, se 29% w.r.t. BRITS and, in particular, in the Point missing setting of the TEMS-BAY dataset, the error is halved. In CER-E, GRIN consistently outperforms other baselines. Besides show-
average, GRIN reduces MAE by
8

---

Published as a conference paper at ICLR 2022
ing the effectiveness of our approach in a relevant application field, this experiment also goes to show that GRIN can be exploited in settings where relational information is not readily available.
Finally, Tab. D show results in terms of MAE
Table 3: Ablation study. Averages over 5 runs.
oof an ablation study on the out-of-sample see- nario in AQI, METR-LA (in the Block Missing settings), and CER-E (Point Missing setting). In particular, we compare GRIN against 3 base- lines to assess the impact of the spatial decoder and of the bidirectional architecture. The first baseline is essentially a bidirectional MPGRU
Model
AQI
METR-LA
CER-E
GRIN
14.73 1: 0.15
2.03 a.
0.29
w/ sp. dec. w/ denoise dec. MPGRU
15.40 1.14
2.32 am
0.29 0.00
17.23 a 1.13
2.96 1:188
0.32 000
18.76 t:0.1
2.57 a.00
0.41 0.00
where values are imputed by final MLP taking as inputs ( and h while the second one has an analogous architecture, but uses hidden representation and time step (for both directions) and, thus, behaves similarly denoising autoencoder. As reference, we report the results of the uni- directional MPGRU. Results show that the components we introduce do contribute to significantly reduce imputation error. It is clear that spatial decoding and the bidirectional architecture are im- portant to obtain accurate missing data reconstruction, especially in realistic settings with blocks of missing data. Interestingly, the denoising model suffers in the Block missing scenario, while, as one might expect, works well in the Point Missing setting. For additional results and discussion about scalability issues, we refer to the appendix of the paper.
5.2 VIRTUAL SENSING
As a final experiment, we provide quantita- tive and qualitative assessment of the proposed method in virtual sensing. The idea (often stud- ied in the context of kriging- see Section 2 is
Truth
GRIN
PM225 (ugim²)
200
D0. 1014
100
to simulate the presence of a sensor by adding node with no available data and, then, let the model reconstruct the corresponding time se-
PM2.5 (ugim²
150
ries. Note that for the approach to work several assumptions are needed: 1) we have to assume that the physical quantity being monitored can be reconstructed from observations at neighbor- ing sensors; 2) we should assume high-degree of homogeneity of sensors (e.g., in the case of air quality stations should assume that sen- sors are placed at the same height) or that the features characterizing each neighboring sen- sor (e.g., placement) are available to the model. In this context, it is worth noting that, due to the inductive biases embedded in the model, GRIN performs reconstruction not only by minimizing reconstruction error at the single node, but by regularizing the reconstructed value for imputation neighboring sensors. We masked out observed values of the two nodes of AQI-36 with high- est (station no. 1014) and lowest (no. 1031) connectivity, and trained GRIN on the remaining part of the data as usual. Results, in Fig- 33 qualitatively show that GRIN can infer the trend and scale for unseen sensors. In terms of MAE, GRIN scored 11.74 for sensor 1014 and 20.00 for sensor 1031 (averages over 5 independent runs).
no. 1031
100-
50-
Jun 19
12:00
Jun-20 20
12:00 00
1014--un---
20
Figure 3: Reconstruction of observations from sensors removed from the training set. Plots show that GRIN might be used for virtual sensing.
CONCLUSIONS
We presented GRIN, a novel approach for MTSI exploiting modern graph neural networks. Our method imputes missing data by leveraging the relational information characterizing the underlying network of sensors and the functional dependencies among them. Compared against tfate-of-the-an baselines, our framework offers higher fiexibility and achieves better reconstruction accuracy on all the considered scenarios. There are several possible directions for future works. From a theoret- ical perspective, it would be interesting to study the properties that would guarantee an accurate reconstruction. Furthermore, future work should study extensions able to deal with a non-stationary setting and further assess applications of GRIN in virtual and active sensing.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Code reproduce experiments presented the paper provided supplementary material to- gether with configuration files to replicate reported results. All datasets, except CER-E, are open and downloading links are provided in the supplementary material. The CER-E dataset can be obtained free of charge for research purposes (see appendix). For experiments where failures are simulated, we use random number generators with fixed seed for missing data generation to ensure reproducibility and consistency among experiments and basclines.
ACKNOWLEDGMENT
This research funded by the Swiss National Science Foundation project 200021 FORT: A Learning graPh-baSed framework FOr thank the Institute of Computational Science at USI for granting access to computational resources.
1726711 200021_1726711 "ALPS- sysTems". The authors wish to
REFERENCES
Gabriel Appleby, Linfeng Liu, and Li-Ping Liu. Kriging convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3187-3194, 2020.
James Atwood and Don Towsley. Diffusiion-convllttinaa neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprini arXiv: 1803.0127, 2018.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez- Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 180.:v888000120000 2018.
Lorenzo Beretta and Alessandro Santaniello. Nearest neighbor imputation algorithms: critical evaluation. BMC medical informatics and decision making, 16(3):197-208, 2016.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 2017.
Deng Cai, Xiaofei He, Jiawei Han, and Thomas Huang. Graph regularized nonnegative matrix factorization for data representation. IEEE transactions pattern analysis and machine intelli- gence, 33(8):1548-1555 1560, 2010.
Ling Cai, Krzysztof Janowicz, Gengchen Mai, Yan, and Rui Zhu. Traffic transformer: Capturing the continuity and periodicity of time series for traffic forecasting. Transactions in GIS, 24(3):
736-755. 2020.
Wei Cao, Dong Wang, Jian Li, Hao Zhou, Yitan Li, and Lei Li. Brits: bidirectional recurrent impu- tation for time series. In Proceedings the 32nd International Conference on Neural Information Processing Systems, pp. 6776-6786, 2018.
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):1-12, 2018.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using mn encoder-decoder for statistical machine translation. arXiv preprint 1406. 2014.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks sequence modeling- arXiv preprint ArXiv:/412.355 2014.
10

---

Published as a conference paper at ICLR 2022
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-721, 2009.
Commission for Energy Regulation. CER Smart Metering Project Electricity Customer Behaviour Trial, 2009-2010 [dataset]. Irish Social Science Data Archive. SN: 0012-00, 2016. URL https:
// // //ww.. ucd. i ssda d comm ssi on www.orrrrrrrreulaaiioooooo
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 2016.
James Durbin and Siem Jan Koopman. Time series analysis by state space methods. Oxford univer- sity press, 2012.
William Fedus, lan Goodfellow, and Andrew M Dai. Maskgan: Better text generation via filling in the In International Conference Learning Representations, 2018.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Benjamin Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. In ICML 2020 Workshop on Graph Representation Learning and Beyond, 2020.
Zoubin Ghahramani and Michael Jordan. Supervised learning from incomplete data via an em approach. In J. Cowan, G. Tesauro, and J. Alspector (eds.), Advances in Neural Information Processing Systems, volume 6. Morgan- Kaufmann, 1994.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farkes Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
lan Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Clive WJ Granger. Investigating causal relations by econometric models and cross cross-spectral methods. Econometrica: journal of the Econometric Society, pp. 424 438, 1969.
William L Hamilton, Rex Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Charles R Harris, K Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, et al. Array program- ming with numpy. Nature, 585(7825):357-362, 2020.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
Hosagrahar V Jagadish, Johannes Gehrke, Alexandros Labrinidis, Yannis Papakonstantinou, Jig- nesh M Patel, Raghu Ramakrishnan, and Cyrus Shahabi. Big data and its technical challenges. Communications of the ACM, 57(7):66-94, 2014.
J Kihoro, K Athiiany et al. Imputation of incomplete nonstationary seasonal time series data. Math- ematical Theory and Modeling, 3412):142-154, 2013.
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, pp. 2688- 2697. PMLR, 2018.
11

---

Published as a conference paper at ICLR 2022
Sanmukh R. Kuppannagari, Yao Fu, Chung Ming Chueng, and Viktor K. Prasanna. Apatio-tempone missing data imputation for smart power grids. In Proceedings of the Twelfth ACM International
Conference on Future Energy Systems, e-Energy '21, pp. 458 466,,,,, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383332. doi: 10.1 N0.1145/344455533466666 URL htttts:::///lorrrrpepottt 11..0...1444444 3466586
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 2015.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net- work: Data-driven traffic forecasting. In International Conference Learning Representattons, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
Zachary C Lipton, David Kale, and Randall Wetzel. Directly modeling missing data in sequences with rnns: Improved classification of clinical time series. In Finale Doshi- Velez, Jim Fackler, David Kale, Byron Wallace, and Jenna Wiens (eds.), Proceedings of the 1st Machine Learning for Healthcare Conference, volume 56 of Proceedings of Machine Learning Research, pp. 253- 270, Northeastern University, Boston, MA, USA, 18-19 Aug 2016. PMLR.
Roderick JA Little and Donald B Rubin. Statistical analysis with missing data, volume 793. John Wiley Sons, 2019.
Weifeng Liu, Puskal Pokharel, and Jose Principe. Correntropy: Properties and applications in non-gaussian signal processing. IEEE Transactions on signal processing, 2007.
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 17238-11243 11248, 2019.
Yonghong Luo, Xiangrui Cai, Ying Zhang. Jun Xu, and Yuan Xiaojie. Multivariate time series impu- tation with generative adversarial networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018.
Yonghong Luo, Ying Zhang, Xiangrui Cai, and Xiaojie Yuan. E'gan: End-to-end generative ad- versarial network for multivariate time series imputation. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 3094-3100 International Joint Conferences on Artificial Intelligence Organization, 7 2019.
Jiali Mei, Yohann De Castro, Yannig Goude, and Georges Hébrail. Nonnegative matrix factorization for time series recovery from a few temporal aggregates. In International Conference on Machine Learning. pp. 2382-2390. PMLR, 2017.
Xiaoye Miao, Yangyang Wu, Jun Wang. Yunjun Gao, Xudong Mao, and Jianwei Yin. Generative semi-supervised learning for multivariate time series imputation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35. pp.
2021.
Fulufhelo V Nelwamondo, Shakir Mohamed, and Tshilidzi Marwala. Missing data: A comparison of neural network and expectation maximization techniques. Current Science, pp. 1514-1521, 2007.
neptune.ai. Neptune: Metadata store for mlops, built for research and production teams that run lot of experiments, 2021. URL htttsss//nepuuue.aat
Benjamin Paassen, Daniele Grattarola, Daniele Zambon, Cesare Alippi, and Barbara Eva Hammer. Graph edit networks. In International Conference Learning Representations, 2020.
12

---

Published as a conference paper at ICLR 2022
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.
Fabian Pedregosa, Gaël Varoquaux. Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Nikhil Rao, Hsiang-Fu Yu, Pradeep Ravikumar, and Inderjit S Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. In NIPS, volume 2, pp. 7. Citeseer, 2015.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning dynamic graphs. arXiv preprint arXiv:2006. 10637, 2020.
Donald B Rubin. Inference and missing data. Biometrika, 63(3):581-592, 1976.
Alex Rubinsteyn and Sergey Feldman. fancyimpute: An imputation library for python. URL https:///itthi: http:/ttthooocooetooooooeoee httm///iiannn/aaaiinnnnn/e
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593-607. Springer, 2018.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural networks, 61:85-117, 2015.
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, pp. 362-373, Springer, 2018.
Chao Shang, Jie Chen, and Jinbo Bi. Discrete graph structure learning for forecasting multiple time series. In International Conference Learning Representations, 2020.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to net- works and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
Indro Spinelli, Simone Scardapane, and Aurelio Uncini. Missing data imputation with adversarially- trained graph convolutional networks. Neural Networks, 129:249-201 260, 2020.
Michael L Stein. Interpolation of spatial data: some theory for kriging. Springer Science & Business Media, 1999.
Olga Troyanskaya, Michael Cantor, Gavin Sherlock, Pat Brown, Trevor Hastie, Robert Tibshirani, David Botstein, and Russ B Altman. Missing value estimation methods for dna microarrays. Bioinformatics, (76))520-525, 2001.
Guido Van Rossum and Fred L. Drake. Python 3 Reference Manual. CreateSpace, Scotts Valley, CA, 2009. ISBN 1441412697.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Ian 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.
Yuankai Wu, Dingyi Zhuang, Aurelie Labbe, and Lijun Sun. Inductive graph neural networks for spatiotemporal kriging. arXiv preprint 20ti::20000075227 2020a.
13

---

Published as a conference paper at ICLR 2022
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial-temporal graph modeling. arXiv preprint arXiv: 10X::11906.00121,,00 2019.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang. Con- necting the dots: Multivariate time series forecasting with graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 753 763, New York, NY, USA, 2020b. Association for Computing Machinery.
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-Fifhh International Joint Conference Artificial Intelligence, IJ,AI' pp. 2704-2710. AAAI Press, 2016. ISBN 9781577357704.
Jinsung Yoon, James Jordon, and Mihaela Schaar. Gain: Missing data imputation using generative adversarial nets. In International Conference Machine Learning, pp. 5689-5698. PMLR, 20.8a.
Jinsung Yoon, William R Zame, and Mihaela van der Schaar. Estimating missing data in temporal data streams using multi-directional recurrent neural networks. IEEE Transactions on Biomedical Engineering, 66(5):1477-145) 2018b.
Jiaxuan You, Xiaobai Ma, Daisy Yi Ding, Mykel Kochenderfer, and Jure Leskovec. Handling miss- ing data with graph representation learning. Neural Information Processing Systems (NeurIPS, 2020.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint 17X1v:1709.04875, 2017.
Hsiang-Fu 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.
Daniele Zambon, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Autoregressive models for sequences of graphs. In 2019 International Joint Conference on Neural Networks (IJCNN), pp- 1-8. IEEE, 2019.
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 Un- certainty in Artificial Intelligence 2018, UAI 2018, 2018
Yu Zheng, Licia Capra, Ouri Wolfson, and Hai Yang. Urban computing: concepts, methodologies, and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 5(3):1-55, 2014.
Yu Zheng, Xiuwen Yi, Ming Li, Ruiyuan Li, Zhangqing Shan, Eric Chang, and Tianrui Li. Fore- casting fine-grained air quality based big data. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 2267-2276, 2015.
14

---

Published as a conference paper at ICLR 2022
APPENDIX
A DETAILED EXPERIMENTAL SETTINGS
In this appendix, we give more details on the experimental settings used to evaluate our approach. We train all the models by sampling at random 160 batches of 32 elements for each epoch, we fix the maximum number of epochs to 300 and we use early stopping on the validation set with a patience of 40 epochs. All methods are trained using cosine learning rate scheduler with initial value of 0.001, decayed over the 300 training epochs. During training, we randomly mask out an additional 5% of the input data for each batch foster robustness noise and missing data.
For GRIN we minimize the following loss function is
C C (M,+T)) (I.,+T) M(++T)
L ())fudd (I,TTT) M Mt,0+T) + ( yll [I.++T): Ma.++T) [1,+T]
[1,4T]
+ L (1) XI,4T), M[J+T) C (2),bud [[,+T]]
X [I.+T)) M M(,+T)
[1,41]
where each -,.,., ) is of the form Eq. and the element-wise error function is MAE. Note that here we are using X [I.c+T] and M (,+47] instead of X [I.C+T] and M [1,0+T]-
For BRITS, To account for the larger input dimension, for the other datasets we increase the number of hidden neurons in the RNNs cells to 128 for AQI/METR-LA and 256 for
the
network hyperparameters of Cao et al. (2018) for the AQI-36 dataset.
The number
of neurons was tuned on the validation sets. For rGAIN we use the same number of units in the cells of the bidirectional RNN used by BRITS, but we concatenate random vector (sampled from a uniform distribution) of dimension & 4 to the input vector in order to model the sampling of the data generating process. To obtain predictions, we average out the outputs of = forward passes. For VAR we used an order of 5 and trained the model with SGD. Since the VAR model needs past 5 observations to predict the next step, we pad each sequence using the mean for each channel. Here we used batch size to 64 and learning rate of 0.0005. The order was selected with a small search the range [2, 12]: we found out a window size of 5 to be ideal for all the considered datasets. For GRIN we use the same hyperparameters in all the datasets: hidden dimension of 64 neurons for both the spatio-temports MLP. We use diffusion convolution message- message-passing operation, with diffusion step A 2 in the spatio-temporal encoder and & = 1 in the temporal decoder. Note that, due to the architectural differences, the other neural network baselines have number of parameters that is far higher than GRIN (depending on the considered dataset, up to Re 4M against s 200K). For MPGRU we use the same hyperparameters of GRIN (64 units for both the spatio-temporal encoder and the decoder).
encoder and the spatial decoder and of 64 neurons for the
For data processing we use the same steps of Li et al. (2018), data are normalized across the fea- ture dimension (which means graph-wise for CRIN and node-wise for BRITS/GAINVVRR) Data masked out for evaluation are never used to train any model.
All the models were developed in Python (Van Rossum & Drake 2009) using the following open- source libraries:
PyTorch (Pazzke et al.
2019)
numpy
(Harris al.
2020
Neptune neptume.al ai
2021);
scikit-lears (Pedregosa al.
2011
fancyimpute (Rubinsteyn & Feldman).
https::/neptune.ail
15

---

Published as a conference paper at ICLR 2022
The implementation of the diffusion convolutional operator adapted from the Graph -aaeeeet codebase For the implementation of BRITS, we used the code provided by the author The code to reproduce the experiments of the paper is available onlind
Table 4: Statistics adjacency matrices used in the experiments. Self loops excluded.
GRAPH
N. NEIGHBORS
Dataset
type
nodes
edges
mean
median
isolated nodes
AQI CER-E PEMS-BAY METR-LA
undirected
437
2699
12.35
9.0
14
directed
485
4365
9.0
9.0
0
directed
325
2369
7.29
7.0
12
directed
207
1515
7.32
7.0
5
B DATASETS
In this appendix, provide details the datasets that used to experiments. Tab. shows detailed statistics for graph structure associated with each dataset, while Fig. 4 shows the corresponding adjacency matrices. Tab. 5 shows missing data statistics. In the following subsections, we go deeper into details for each dataset.
Table 5: Statistics missing data distribution. (P) and (B) indicate the Point Missing and Block Missing settings, respectively. With block, we refer to missing data bursts longer than time steps and shorter than equal 48.
ORIGINAL DATA
INJECTED FAULTS
% missing
avg. block
median block
%
avg. block
median block
AQI
25.67
6.69
10.67
7.59
4.0
AQI-36
13.24
7.24
11.33
6.52
4.0
BEMS-BAY
(P)
0.02
12.0
12.0
25.0
3.33
3.0
(B)
9.07
27.26
28.0
METR-LA
(P)
8.10
12.44
9.0
23.00
3.33
3.0
(B)
8.4
25.68
26.0
CER-E
(P)
0.04
48.0
48.0
24.97
3.33
3.0
(B)
8.38
22.45
21.0
B. AIR QUALITY
Air pollution is nowadays a ubiquitous problem. The Urban Computing project (Zheng et al. 2014
2015) published several datasets containing real measurements of different indices affecting human life in urban spaces. We consider as benchmark the dataset regarding the air quality index (AQI). The complete dataset contains hourly measurements of six pollutants from 437 air quality moni- toring stations, spread over 43 cities in China, over a period of one year (from May 2014 to April 2015). Prior works on imputation (Yi al. 2016; Cao al. 2018 considered a reduced version of this dataset, including only 36 sensors (AQI-36). This dataset is particularly interesting as a bench- mark for imputation due to the high rate missing values (25.7% AQI and 13.2% AQI-36). Along with Yi et al. (2016), December. We consider both the in-sample and oft-olesample scenarios. In latter case, we do not consider windows overlapping with any of the months. We the procedure of Yi et al. (016)) to simulate the presence of missing data for evaluation.
consider the test set the months of March, June, September and
htteer//aaaaaabcc//aaaaaaaaaagaa WaveNNet
https://giithbb..cm/rrraaaaa
16

---

Published as a conference paper at ICLR 2022
AQI
CER-E
PEMS-BAY
METR-LA
1.0
0..5
0.0
Figure 4: Adjacency matrices of the different datasets.
We select windows of data of length = 24 for AQI and = 36 for AQI-36 (in line with Cao et al. 2018)). ) To evaluate the imputation performances, truth the value x if: (I) the value is not missing (m, hour and day the following month. Besides air quality readings, the dataset provides geographic coordinates of each monitoring station. To obtain adjacency matrix from the geographic distances between nodes, we use thresholded Gaussian kernel (hhman et 2013); the weight w w of the edge connecting i-th and j-th node is
mask out from the test set and use as ground-
and (2) the value is missing the same
exp dist(i.)) 7
dist (i.j) 2
w
(12)
0
otherwise
where dist (., is the geographical distance operator, 7 controls the width of the kernel and is the threshold. We set to the standard deviation of geographical distances in AQI-36 in both datasets. We set so that corresponds to distance of As 40 km.
B.2 TRAFFIC
The study of traffic networks is key for the development of intelligent transportation systems and a relevant application field for network science. While previous works (Yu al., 2017 et al. 2018 Wu et al. 2019 Shang et al., (020) have assessed spatio-temporal deep learning methods for the traffic forecasting task, we focus on reconstruction. We use as benchmark the PEMS-BA -BY and METR-LA datasets from Li et al. (2018). PEMS-BAY contains 6 months of data from 325 traffic sensors in San Francisco Bay Area, while METR-LA contains 4 months sensor readings from 207 detectors in the Los Angeles County Highway (Jagadish et al. 2014); for both datasets, the sampling rate corresponds to minutes.
We use input sequences of 24 steps, which correspond to 2 hours of data. For adjacency, a thresholded Gaussian kernel applied to geographic distances following previous works Wu et al. 2019). We split the data into three folds, using 70% of them for training and the remaining 10% and 20% for validation and testing, respectively.
B.3 SMART GRIDS
We consider data from the Irish Commission for Energy Regulation (CER) Smart Metering Project We select only the subset of the available smart meters monitoring energy consumption of small and medium-sizee enterprises (SMEs), i.c., 485 time series with samples acquired every 30 minutes. Note that access to dataset can be obtained free of charge for research purposes.
We build adjacency matrix by extracting k-nearest neighbor graph (with k 10) from the similarity matrix built by computing the week-wise correntropy eL al. 2007) among time series. 70% 10%%2%% split for training, validation and testing and use
As in the traffic case, window size of 24 steps. Data were normalized using standard scaling as in the previous settings, and we did not perform additional preprocessing steps.
https:: http:://wwwww..
17

---

Published as a conference paper at ICLR 2022
C ADDITIONAL RESULTS
In this appendix, we show an additional experiment in a controlled environment, comparison against additional baselines, additional ablation studies, and sensitivity analyses.
C. SYNTHETIC DATA
In this experiment, we test our method on the simulated particle system introduced by Kipf et al. [2018 We simulate the trajectories of N 10 particles in a (10 x 10) box with elastic collision. Each particle carries a either positive or negative charge q {1, -1}. Two particles attract each other if they have opposite sign, otherwise they repel. Interaction forces between two particles are ruled by Coulomb's s law. We collect two datasets, each containing 5000 independent simulations of T = 36 steps each. In the first dataset, particles have the same charge in every simulation. In the second one, sample the charges uniformly at random the beginning of every simulation. In both scenarios, the initial location and velocity of the particles are drawn randomly. At each step, we randomly remove blocks of consecutive readings with a probability Pfatture 2.5% and length sampled uniformly from the interval [4, 9). Here, a reading consists of the (I, y) coordinates of the particle's position. We further mask out 2.5% of positions random. The percentage of values not masked out is RJ 74%. For evaluation purposes, we generate another mask using the same missing data distribution and use the masked values as ground-truth for evaluation. We split dataset in training/validatioonnes folds using 70% 11111110///22 splits, respectively.
Table 6: Results on the synthetic datasets. Performance averaged over 5 runs.
Fixed charge
Varying charge
Model
MAE
MSE
MAE
MSE
BRITS 0. 1202 + 0.0033
0.0878 = 0.0002
0. 1089
+ 0.0007
0.0840 + 0.0011
GRIN
0.0500 + 0.0055
0.0061
0.0010
0.0530
0.0092
0.0074 + 0.0033
Improv.
2.41x x
x
2.05x
11.35x
We test our method (GRIN) and BRITS in both synthetic datasets. We use 32 units for the hidden layer of BRITS ( 25K parameters) and 16 units for both the encoder and decoder GRIN (+s 10K parameters). Results are reported in Tab. 6 Both the methods take as input only the particles' po- sitions, with no information about the charges. As can be seen, consistently with what observed by Kipf et al. (2018), relational representations are impressively effective in this scenario. Our method outperforms the bascline by more than an order of magnitude in terms of MSE. Surpris- ingly, BRITS is more accurate in the setting with varying charge. Our hypothesis is that the added stochasticity acts as a regularization and forces BRITS to learn a more general model.
C.2 EMPIRICAL COMPARISON AGAINST MATRIX FACTORIZATION WITH SIDE INFORMATION
Table 7: Comparison of regularized matrix factorization methods on air quality datasets. Results averaged over 5 independent runs.
AQI-36
AQI
Model
MAE
MSE
MRE (%)
MAE
MSE
MRE (%)
30.54 i: 0.26
2763.06
1 63.35
43.84
0.38
26.74 : 0.24
2021.44 ..44 27.8
40.01
0.35
GRMP
19.29 0.39
1054.48
40.79
27.68
0.5
26.38
0.32
2031.21
7
39.48
0.48
TRME
15.97
+ 0.14
1178.65
+ 60.14
22.92
0.20
21.86
+ 0.28
1516.81
+ 45.53
32.71
0.42
GRIN
10.51 = 0.25
371.47 +: 17.38
15.09
+ 0.40
13.10 =: 0.08
615.80 :: 10.09
19.60 : 0.11
several matrix factorization approaches often studied in the context of recommender systems can be regularized by considering priors the spatio-temporal struc-
As mentioned in Section 2
18

---

Published as a conference paper at ICLR 2022
ture of the data. Intuitively, spatial regularization is achieved by imposing soft constraints the smoothness of the interpolated function w.r.. nodes of an underlying graph (Cai et al., 2010 Rao et al. 2013). Temporal regularization can be obtained by imposing analogous constraints modelling temporal dependencies as eventually weighted edges a graph. In temporal regularized matrix factorization (TRMF: Yu al. 2016), similarly, coefficients of an autoregressive model are used as temporal regularizer.
Tab. 7 shows comparison of different matrix factorization approaches on imputation in the air quality datasets (where we considered the in-sample setting in Section 5 For TRMF we used an implementation adapted from the Transdim repository while for graph regularized matrix factor- ization (GMRF) we use a custom implementation of the method proposed by [Ca et al. (2010). We fixed the rank to be equal to 10 (as the one used in all the experiments for standard MF) and tuned the regularizaaton coefficients on validation set. Results do show that introducing spatial and temporal regularization improve w.r.t. vanilla MF; however, deep learning methods and even linear VAR predictors achieve far superior reconstruction accuracy here. Arguably, low-rank approximation methods might instead have an edge in a low-data regime: this type of analysis is, however, out of the scope of this work.
C.3 SCALABILITY
With reference standard bidirectional GRU, using MPNNs implement the cell's gates in- creases the computational complexity by factor that scales with the number of edges O(E) using an efficient sparse implementation- or with the number of nodes squared O Luckily, this overhead can be amortized as most of the computation can be parallelized. Research on scalable and memory efficient GNNs is a very active field (c.g.. Hamilton et al. 2017 Frasca et al. 2020): depending on the task, the designer can opt for massage passing operators that meet the application requirements in terms of performance, time and space constraints.
C.4 ABLATION STUDY
Here we provide two different ablation studies, the first one on the architecture of GRIN and the second one on the graph structure.
C.4.1 ARCHITECTURAL ABLATIONS
Tab. shows additional results for the ablation study presented in Section Consistently with what we already observed, the spatial decoder and bidirectional architecture improve performance and appear particularly relevant in settings with blocks of missing data.
Table 8: Ablation study. MAE averaged over runs. (P) and (B) indicate the Point Missing and Block Missing settings, respectively.
Model
AQI
METR-LA (B)
METR-LA (P)
CER-E (B)
CER-E (P)
GRIN
14.73 a15
2.03 + 0.00
1.91 0.00
0.42 0.00
0.29 + 0.00
w/o sp. dec.
15.40 0014
2.32 1 001
2.01 0.00
0.49
0.29 0.00
w/ denoise dec.
17.23 : 1.12
2.96 = 0.18
2.09 = 0.02
0.61 = 0.02
0.32 +: 0.00
MPGRU
18.76
2.57
2.44 0.00
0.53
0.41 4 0.00
C.4.2 GRAPH STRUCTURE ABLATIONS
Here we study how exploiting the relational structure of the problem affects the accuracy of the reconstruction. In particular, we run two additional experiments on the METR-LA dataset (Block missing settings), where instead of using as adjacency matrix the thresholded kernel in Eq. [2] we use (1) fully connected graph (W- 1) and (2) graph with no edges (W = D). To provide node i.e., sensor identification, we use learnable embeddings as additional node features. Results are
httpp:://gittubb.com///ii//
19

---

Published as a conference paper at ICLR 2022
shown in Tab. performance for BRITS reported reference. It is clear that the constraints posed by the graph structure do have an impact on the accuracy missing data imputation and, at the same time, that spatial information is relevant for the task.
Table Performance with different adjacency matrices. Results averaged over 5 runs. (B) indicates the Block Missing setting.
METR-LA (B)
Method
MAE
MSE
MRE (%)
GRIN
2.03 + 0.00
13.26 0.85
3.52 IMI
fully connected
2.63 +: 0.0
27.37 0.38
4.56
0.02
no edges
3.42 + 0.04
51.68 0.21
5.93 = 0.08
BRITS
2.34 + 0.01
17.00 0.14
4.05 = 0.01
C.5 SENSITIVITY ANALYSIS
Finally, in this subsection we carry out assessment performance degradation w.r.t. the amount of missing data. Before discussing results, there are few remarks that are worth bringing up regarding imputation in highly sparse settings. In the first place, GRIN, as well as a large portion of the state-of-the-an baselines, is autoregressive model, which means that it might be subject to error accumulation over long time horizons. Furthermore, here, consistently with Section [ we consider the out-of-sample setting which is particularly challenging in the sparse data regime. That being said, GRIN achieves remarkable performance also in this benchmark.
We train one model each for GRIN and BRITS by randomly masking 60% of input data for each batch during training, then, we run the models on the test set by using evaluation masks with increasing sparsity (note that this causes distribution shift in evaluation). For each level of sparsity, evaluation is repeated times by sampling different evaluation masks. Results are reported in Tab, I0 and Fig. shows that GRIN outperforms BRITS in all the considered scenarios.
Table 10: Performance with different amounts of missing data. Results averaged over different evaluation masks in the out-sample setting. (P) indicates the Point Missing setting.
METR-LA (P)
% Missing
10
20
30
40
50
60
70
80
90
GRIN
1.87
1.90
1.94
1.98
2.04
2.11
2.22
2.40
2.84
BRITS
2.32 1.0
2.34
1o0
2.36
2.40 1.00
2.47 1am
2.57 1.000
2.76
cm
3.08
1.0
4.02 no:
4.0
GRIN BRITS
3.5
MAE
3.0
2.5
2.0
20
30
40
60
70
80
90
Missing data (%)
Figure 5: The plot shows graphically the results in Tab.
10
20


Reviews:
[{"review_id": "gzyXg_pBwsz", "reviewer": "Reviewer_jZvK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Novelty: \n\nI think this is the first work that takes available relational information into consideration when building the imputation model, and the utilization of GNN makes sense.\n\nClarity:  \n\nWhat do you mean by \"relational information\"? Is that human-annotated information that, for example, describes which sensors are related? Or is that not provided by humans but automatically learned by the model?\n\nSection 4 is a little bit hard for me to follow to judge the novelty of the proposed architecture. The spatial information is already considered in the first stage as shown in equation 2 (message passing from neighbors), why do we need a second stage that also considers spatial information?  In the \"Unidirectional model\" paragraph of section 4, $H_{[t,t+T]} \\in R^{N_t \\times l}$, what is $l$? In equation 9, the term $h^i_{t-i}$ is really confusing for me, why do you subtract node index i from t?\n\nLimitation of the approach:\n\nThe reliance on RNNs makes the proposed approach unable to handle irregularly sampled data. Also, this paper assumes a static adjacency matrix, which makes it not suitable for dynamic relational data.\n\nExperiment:\n\nThe extensive comparison to BRITS on different datasets clearly shows the advantage of the proposed approach. However, my concern is that the way that the missing data are simulated is too simple: block missing only drops 5% of the data, and point missing only masks out 25% of the data. I am not convinced that the proposed method can work well when the observation becomes very sparse. I suggest increasing the number of missing data and compare to BRITS.", "summary_of_the_paper": "This paper proposes to leverage GNN that takes available relational information for multivariate time series imputation. Each feature dimension of the time series is regarded as a node in GNN and the message-passing is used to implement the update function of bidirectional RNN. On three benchmarks, this new method achieves better performance than the previous STOA method BRITS.", "summary_of_the_review": "My score is 5 for now as there are some clarity issues. But I am happy to increase my score if the authors can answer these questions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "e5nrA-wGR5H", "reviewer": "Reviewer_hJvE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I really enjoyed reading this paper. The derivations are sound and it is very well written. I appreciate the readability of the methods section. The performance obtained in the experimental section are also very convincing.\n\n- After reading this paper, I'm still not exactly sure as why the graph representation of the spatial correlations should lead to better performance. In 5.1, the authors state that \"the results provide empirical evidence of the positive regularization effect of the inductive biases encoded into GRIN\". I think the paper would benefit from a motivational or discussion section where these assumptions are more challenged and where authors could share their intuition and rationale behind this specific inductive bias.\n\n- Regarding the above comment, it therefore seems legitimate to me to study the impact of different choices of graphs one can make. I would then appreciate greatly an experiment where the impact of the type of graph taken would be investigated. In particular, comparing against a fully connected graph (with the position of the nodes given in the input node features) and an identity matrix (as pointed to in section 3 - sequence of graphs).\n\n- It's also not clear to me why you need two steps decoder. If I understand correctly, the. w/o spec decoder of table 3 corresponds to the architecture with the second step removed. Is it also possible to remove only the first imputation step (the linear one) ? Why is this linear step needed ?\n\n- I really like section 5.2. \n\n- You focus on spatio-temporal data. However, do the authors think that this method could be applicable to a broader class of time series where the different dimensions are not different locations ? For example, financial time series or healthcare time series ? If it's not the case , then I think the authors should be more clear about this assumption in the text.\n\n- Equation 9 : I think the subscript of h is t-1 and not t-i\n", "summary_of_the_paper": "This paper proposes a method for time series imputation modeling the spatial dependencies with graphs. The paper leverages a bi-directional temporal graph neural network architecture to learn node level representations that allows to impute missing values with better than state of the art accuracy. ", "summary_of_the_review": "I think it's a nice paper, that would spark a lot of discussion. Some more ablation studies are required to understand the relative importance of the different building blocks in the proposed architecture.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EklGnTpj-H", "reviewer": "Reviewer_9yUs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is well written, and easy to understand. The problem is well motivated, and I didn't see any gaps in the solution presented. \n\nI found it interesting that spatio-temporal methods to impute time series values do not take graphs into account. Nonetheless, there are methods that do model multivariate time series as low rank matrices, and use matrix factorization style methods for imputation. I recommend the authors mention this and compare and contrast to these methods. \n\nIn the related work section , you mention a bunch of methods that use graphs to forecast time series.  Why can't these be used for imputation? This also raises another question: If one can forecast in the presence of missing values, is imputation necessary?\n\nI'm curious about the reason to incorporate backward dynamics. Unlike text, time only moves \"forward\". However, table 3 shows that bidirectionality helps. Can you provide some intuition for this? \n\nHow scalable is the method? GRUs themselves are probably scalable, but adding message passing in the gates adds overhead. I would want to see a memory/runtime comparison to the baseline methods on the datasets. The datasets used themselves are not too large, so maybe even a simulation or some justification might be good. \n\nWhat happens if all 'd' features are missing for a particular node? Is the entire feature vector imputed? It might be good to have a study on a toy dataset where you examine various \"types\" of missing data, varying the length and randomness of missing features and compare your method to some of the baselines. I think this will make the paper far more compelling. ", "summary_of_the_paper": "In this paper, the authors propose a GNN based imputation method for Time Series.  They argue that past works for time series imputation only take time into account, and not the spacial relationships between time series. The model (called GRIN) works by encoding the data via a GNN, and performing 2 rounds of imputation. The GNN itself acts as gates in a GRU that accounts for the sequential information. This is repeated for a \"forward\" and \"backward\" pass, and a final MLP infers the missing value. Experiments on multiple datasets show that the proposed method outperforms baselines. ", "summary_of_the_review": "There are a few aspects I'm not completely sure of, hence my rating and confidence level:\n\n1. Time series imputation itself is sometimes motivated from the point of view of making good predictions. To this end, the authors might want to motivate this aspect a bit more, and also compare to methods that can make predictions from incomplete data. I don't see that addressed in the paper at all. If this is a completely orthogonal problem, that is something that the authors should also clarify. \n\n2. I'm not sure how scalable the method is, which is of importance. Multivariate time series can often get quite large, and the authors should address scalability either via a computational complexity argument, or some empirical evidence. \n\n3. combining time series and graphs is not new. There has been work in the context of forecasting (like the authors mention) and some other papers that have not been cited. The major contribution in this work seems to be adding graphs to a \"GRU\". But this kind of RNN + graph architecture has also been considered before. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1Ldy8dqFSE", "reviewer": "Reviewer_JPtB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper tackles an important and general problem for numerous application areas where time-series data from multiple sensors is processed with missing data (as can be expected in reality). The architecture builds on previous work from graph RNN approaches and message passing neural networks, as is clearly presented in the paper. The emphasis is to include the spatial information of the problem into the architecture, this inductive bias can then help in imputation as the neighbourhood of each missing data point can help in accurately estimating the missing value. This paper is clearly written and covers a lot of related work. The ideas bring the graph structure into the problem setting and the results are impressive.\n\nIn the experiments, BRITS is a state-of-the-art approach, but can you include more state-of-the-art approaches for comparison? For example NAOMI [Liu et al., 2019], E2GAN [Luo et al, 2019]. Additionally, kNN is a good baseline comparison, as it uses the neighbourhood information, other good baselines that use neighbourhood information could be MF with graph side information, e.g. [Rao et al., 2015] or similar, to replace simple MF, and krigging that is a simple popular approach. One last comparison that may be relevant is to another method that uses both spatial and temporal information for MTSI [Yi et al, 2016].\n\nThis architecture seems to share similarities with other RNN like networks that work with graph structures, but do not include imputation, can you compare with this line of work, for example [Li at al., 2016]?\n\nYujia Li, Daniel Tarlow, Marc Brockschmidt, Richard S. Zemel: Gated Graph Sequence Neural Networks. ICLR (Poster) 2016\n\nRao, Nikhil, et al. \"Collaborative Filtering with Graph Information: Consistency and Scalable Methods.\" NIPS. Vol. 2. No. 4. 2015.\n\nYi, Xiuwen, et al. \"ST-MVL: filling missing values in geo-sensory time series data.\" (2016).\n\nLuo, Yonghong, et al. \"E2gan: End-to-end generative adversarial network for multivariate time series imputation.\" AAAI Press. 2019.\n", "summary_of_the_paper": "A novel recurrant graph neural network, for spatio-temporal encoding, coupled with a message passing neural network, for spatial decoding, is proposed for imputing missing values in a multivariate time series; The architecture uses temporal and spatial properties of the data. It seems that the approach of gated recurrent neural networks (and related architectures using gated recurrent units, GRUs) is extended to include the graph topology through neighbourhood message passing. Experiments show impressive results on three benchmark datasets, and comparison with simple and state-of-the-art baselines. A short ablation study excludes the spatial decoder and omits the bi-directional architecture to empricially show that they have a significant impact on the imputation performance. Another short experiment tests the ability of this architecture to replace entire missing sensors, using an air pollution dataset with multiple sensors, results are convincing.", "summary_of_the_review": "A novel contribution that brings the graph structure more strongly into the architecture than previously, building on existing work in the domain. Evaluated on relevant benchmark datasets (although one or two more could be added) against benchmark methods (again where one or two more could be added) and ablation studies included to give some insight to the impact of the contributions on the qulaity of the estimations of the missing data.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for time series imputation modelling the spatial dependencies with graphs, focusing on spatio-temporal data, where the spatial dimensions are represented by a graph.
The reviewers find the approach novel. The paper is well-written and clear. Related work is adequately discussed.
The experiments are convincing.
The reviewers agree that the paper should be accepted.
Decision: Accept (Poster)