Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper presents a novel neural architecture for the imputation task in the context of multivariate spatio temporal series (for instances in sensor networks). The core idea is derived from the constatation that autoregressive models for this task are prone to error propagation, especially in the case of huge sparsity of available data. The authors propose to use an attention mechanism - spatial and temporal - in order to learn representations of the graph nodes and to use those embeddings to derivate the missing values rather than the values of previous/next temporal steps. The model is derived from the now classical GNN framework. A spatio-temporal cross-attention layer is proposed for the message passing between nodes and a temporal self-attention layer for the inference of a context representation vector of the time history of the considered node. Two approaches are presented to reduce the time complexity of the learning phase, the first one using classic subsampling methods in graphs, and the other one based on a hierarchical attention mechanism. Experiments are conducted on 4 datasets to compare the proposed approach to state of the art methods.  
strengths_and_weaknesses: Strengths:
* the paper is well written, easy to follow
* the SOTA is well covered and the proposed approach is well positioned
* I found the proposed model original, clever, and very well explained.
* The novelty is not great as a lot of research has been devoted to the subject of GNN and time series, but the proposed architecture is elegant and intuitive. 

Weaknesses : 
* Further experiments and analyses would have been useful to assess the real capabilities of the model (see section Questions).


questions: * Ablation study : I wonder what is exactly the role of the self-attention intra-node mechanism and I am curious of the results if this element is not used ?
* Spatiotemporal positional encoding : there is very few discussion in the article about the importance of the spatiotemporal positional encoding nor analysis of the learned representations, can  you provide some insights on the importance of accurate/not accurate initial spatial information ? It is possible to analyze the learned representations to tell something about the sensors geographic distribution ?
limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes two variants (a basic one, SPIN, and a hierarchical one, SPIN-H) of attention-based message-passing networks to learn representations of a multivariate time series over a static graph, and which cope well with a large amount of missing data. The network learns representations that can reconstruct missing observations not only from the other temporal data at the node, but also from its neighboring nodes. Its experimental performance is better than other state-of-the art methods when a long sequence of temporal data is missing ("block missing") or when the amount of missing data is large, and comparable to the best methods when data are removed i.i.d in time ("point missing") in a moderate amount (<= 50%). 


strengths_and_weaknesses: The paper is well written, and the approach makes sense, in particular to cope with long blocks of missing data a particular node. 

The performance of SPIN and SPIN-H is compared empirically to multiple benchmarks in Section 5, but only under the perspective of MAE performance. In particular, the computational and memory complexities are not compared to these methods, although the justification for SPIN-H is precisely a decrease in complexity by a factor K/T over SPIN, where K << T is the number of "hubs" added in the network and T the length of the time-sequence taken for learning.

The paper could investigate deeper other properties of SPIN and SPIN-H (see also below).


questions: 1) SPIN is designed to handle blocks of missing data at one point over a long period of time. In Table 2, the amount of missing data gets very large, but are the data removed i.i.d (as in the point missing model of Table 1) or not (e.g., by picking some nodes which lose a lot of data?)

2) SPIN-H is computationally less expensive than SPIN by a K/T factor, but Appendix A shows that the number of parameters is 10 fold larger. How do you compare the two in that regard? How do you assess the cost of introducing an information bottleneck mentioned at L255?

3) Why does SPIN-H work better than SPIN on AQI-36, and worse on AQI (Table 1)? 

4) Why does SPIN-H work better on the two other datasets PEMS-BAY and METR-LA when the amount of missing data is >= 50% (Table 2) and worse when the  the amount of missing data is = 25% (Table 1)? Does the hierarchy provide some form of regularization, like graph sub-sampling, which large amounts of missing data?

5) In eq (7), how is w_\alpha obtained - directly from (5)?

6) Minor nits: What does the green surface on the left of Fig 2 represent? 
Typos at L119 (Pearson and not Person), L161 (adds and not add), L206 (to weigh and not to weight).

-----------------------------------------------------------

Update after discussion with authors: The rebuttal addresses (most of) my comments. The new results of Appendix E strengthen the interest of SPIN(-H) over other benchmarks. I still think that the paper would benefit from a deeper comparative analysis of the computational and memory complexities of SPIN vs SPIN-H, as well as vs the other benchmarks, and I understand from the authors' reply in the discussion that this will be done. I agree with the other reviewers that the paper impact might be limited, but overall I find the paper to be well written and bringing a contribution to the state of the art, hence my score for the review. 

limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors propose an attention-based model for missing data reconstruction from spatiotemporal graphs. The core part of the method is a sparse spatiotemporal attention mechanism that learns representations localized in time and space from sparse data. Empirical results show that the proposed method outperforms existing approaches, especially when the missing rate is high.
strengths_and_weaknesses: Strengths:
1. The writing is clear and the figures are illustrative.
2. Experiments show promising results.

Weaknesses:
1. Some claims are questionable and might be over-claimed (see “Questions”).
2. There are already some works on sparse attention with spatiotemporal data. (For example, [1] has a similar idea of utilizing valid spatiotemporal data points only to generate representations. There might be more works along this line though.) The authors shall provide more context of sparse attention with spatiotemporal data. 
3. The authors should have more ablation study experiments to explain the effect of the claimed contributions - sparse spatiotemporal attention mechanism, the inductive biases, etc.
4. In Figure 1, there should be an “MLP” block between the concatenation of (spatiotemporal cross-attention, temporal self-attention, skip connection) and “Add & Norm”, according to Equation 12.

[1]. Huang, Z., Sun, Y., & Wang, W. (2020). Learning continuous system dynamics from irregularly-sampled partial observations. Advances in Neural Information Processing Systems, 33, 16177-16187.

questions: 1. Line 56: “Conversely”. From my understanding of the proposed “spatiotemporal cross-attention” and “temporal self-attention”, they also set the attention coefficients of spatiotemporal points with missing values to zero. How is this method different from the so-called “trivial way”: constraining the attention coefficients of time steps corresponding to missing data to zero?
2. Line 58: “we seek to design an architecture where each processing stage is aligned with the task of reconstructing missing spatiotemporal observations.”. How is the design in each stage aligned with the task of reconstructing?
3. Line 60: “Our model can be seen as a learned, self-organizing, spatiotemporal diffusion process”. How is it related to the diffusion process?
4. Line 66: “reconstructing observations at arbitrary locations”. As described in lines 265-266, the spatial encoding is trained as learnable parameters different for each node. How can the proposed method reconstruct observations at arbitrary locations? What if the queried location has never appeared in training data and its embedding is never defined in training? The method actually assumes that the locations in evaluation are exactly the same locations in training.
5. Line 71: “ equipped with inductive biases that make the model tailored for the multivariate time series imputation task”. What is the inductive bias that makes the model tailored for the multivariate time series imputation task?

limitations: The authors have adequately addressed the limitations.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces SPIN, a spatiotemporal graph network with a new spatiotemporal attention for reconstructing missing data points in multivariate time series. The proposed attention mechanism consists of the inter-node cross-attention and the intra-node self-attention. Compared to the autoregressive methods propagating the biased representations, one advantage of SPIN is that the reconstruction only relies on the observations. They also propose the hierarchical attention to reduce the computational cost. Their empirical evaluation shows that SPIN outperforms existing baselines generally and is clearly advantageous when the missing ratio is large. 
strengths_and_weaknesses: Strengths:

* The paper tackles an important problem and the proposed spatiotemporal attention mechanism is sound.
* The visualizations of the model architecture and the attention mechanism are illustrative and help in understanding.
* The method section is well structured and easy to follow even though there are many design details.
* The related work section offers a good overview of the existing work.

Weaknesses:

1. Although the quantitative results show the effectiveness of the method, it would be even better if there are qualitative results visualizing either the imputed data points or the cross-attention weights and self-attention weights.
2. Although the authors compare the computation complexity between SPIN and SPIN-H, it would be more comprehensive if the comparison to baselines in terms of time cost or memory cost could be reported.  

questions: 1. What is $w_\alpha$ in equation (7)? Is it a learnable paramter?
2. Why do you use the Bahdanau attention instead of the dot-product attention? 
limitations: I can find one sentence in the conclusion discussing the limitation. But I don't find any discussion about the potential societal impact.
review_title: null

Meta-review: metareview: The paper tackles the important problem of spatiotemporal data imputation via a novel GNN architecture and corresponding spatiotemporal attention mechanism that are both cogent and intuitive. 

The author feedback satisfactorily addresses key concerns. In particular the ablation study is a great plus and the virtual sensing results further expand the relevance of the approach. 

The AC finds the "auxiliary task learning" setting presented by the authors very interesting and strongly encourages the authors to explore such a setting as future work!
confidence: Certain
Decision: Accept