Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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. 
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.

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

- 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).

- 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 ?

- I really like section 5.2. 

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

- Equation 9 : I think the subscript of h is t-1 and not t-i

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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
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.

In 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].

This 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]?

Yujia Li, Daniel Tarlow, Marc Brockschmidt, Richard S. Zemel: Gated Graph Sequence Neural Networks. ICLR (Poster) 2016

Rao, Nikhil, et al. "Collaborative Filtering with Graph Information: Consistency and Scalable Methods." NIPS. Vol. 2. No. 4. 2015.

Yi, Xiuwen, et al. "ST-MVL: filling missing values in geo-sensory time series data." (2016).

Luo, Yonghong, et al. "E2gan: End-to-end generative adversarial network for multivariate time series imputation." AAAI Press. 2019.

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: Novelty: 

I 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.

Clarity:  

What 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?

Section 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?

Limitation of the approach:

The 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.

Experiment:

The 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

I 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. 

In 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?

I'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? 

How 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. 

What 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_review: There are a few aspects I'm not completely sure of, hence my rating and confidence level:

1. 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. 

2. 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. 

3. 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.
review_title: null

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)