Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes an approach for multivariate time series forecasting by trying to estimate dependence across dimensions via a learned graph structure.  The dimensions are considered as nodes in a graph, and the problem is mapped to learning a discrete graph structure that can help with downstream forecasting task.
The paper shows that a graph neural network (GNN) can be leveraged even though an explicit structure is unknown, to improve forecasting performance. This is achieved while learning the graph structure and forecasting architectures in an end-to-end fashion. The proposed approach is computationally efficient compared to a bilevel optimization approach where a discrete graph structure is learnt in a meta-learning framework. The approach is further claimed to be able to incorporate apriori knowledge of the graph structure by proposing a regularizer that ensures that the learned graph structure stays close to the known graph structure. The proposed approach improves forecasting performance in comparison to several strong baseline methods on three real-world datasets.
In general, the paper is well-written and easy to follow. 

Attempts have been made in the past for learning such a discrete graph structure from data. The authors mention LDS [2] and NRI [3] as closest to their work. The authors attempt to explicitly compare the proposed approach to NRI. The authors claim that "The most essential distinction is the number of structures": one structure is learned in the proposed approach while many structures are learned in NRI. From what I could follow, this single structure is achieved by using the entire multivariate time series data to obtain a feature vector for each dimension (series) via a neural network instead of using window-wise data. In this sense, this appears to be a simplification of NRI, rather than being something novel and different.
The proposed setup and the approach are different and novel compared to NRI as the "Amortized inference is not desired nor relevant": I am not sure how this makes the proposed approach non-trivial given NRI? 
Furthermore, in contrast to LDS, the key contribution of the proposed approach is to get rid of the bilevel optimization. But then, that also seems to rely mainly on the Gumbel reparameterization trick which has been used in NRI for forecasting albeit for a slightly different setting.

Another very closely related approach to the proposed one is that in [1], which the authors seem to be unaware of. 
One of the main claims of the proposed approach is an attempt to learn the graph structure and forecasting model in an end-to-end learning fashion. However, this problem has already been attempted in [1].
Therefore, it is difficult to comment on the novelty and contribution of the paper without a comparison with [1], especially since most of the benchmark tasks and datasets used in this paper are present in [1] as well. 

I have some concerns regarding the empirical evaluation:
1. Can the observations in Fig. 2 be attributed to the graph learning part? Despite the fact that the only difference between DCRNN and the proposed method seems to be the graph structure learning part, it is still not obvious qualitatively as to why the observations of Fig. 2 can be attributed to the graph learning part, e.g. why is "GTS curve better captures the sharp dip toward the end of the series" attributable to the graph learning part qualitatively or as per domain knowledge? I think an empirical analysis on a synthetic dataset to support such claims related to ablation could be useful.
2. In Fig. 4a, the regularization seems to induce sparsity and has been observed by the authors as well: "increasing the regularization magnitude produces sparser graphs". But the efficacy of such regularization on forecasting performance is not clear as k=0 (no kNN regularization) seems to have the best forecasting performance in Fig. 4a. This seems to imply that using kNN graph knowledge is not adding any value.
Similar observations can be made in Fig. 4b, where increasing $\lambda$ leads to increasing MAE. As such, the effect or usefulness of regularization is not clear.
3. The analysis on regularization and learned structures is done using a kNN graph as apriori knowledge for the PMU dataset. Rather than relying on another data-driven graph structure (kNN graph) as ground truth, I wonder if it would be useful to do such analysis on the public datasets (METR-LA and PEMS-BAY) for which the ground truth structures are actually known. As such, the evaluations on "effect of regularization" and "learned structures" do not seem conclusive.
4. In Tables 2 and 3, some of the bolds also apply to GTSv but are missing.

Given the above points, the originality of the work and the contributions are not clear.

Other minor points:
1. Related Work can also benefit from more precise references to papers that use the mentioned architectures for time series forecasting. The current references are too generic.
2. typo: hyperparemeter


References:
[1] Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks, Wu et. al, KDD2020. https://dl.acm.org/doi/abs/10.1145/3394486.3403118
[2] LDS: Learning discrete structures for graph neural networks, Franceschi et. al, ICML, 2019
[3] NRI: Neural relational inference for interacting systems. Kipf et. al, ICML, 2018.
review_title: Official Blind Review 

final_score: rating: 7: Good paper, accept
review_content: Paper summary:

This paper proposes an approach for time series forecasting that learns the graph structure among multiple (multivariate) time series simultaneously with the parameters of a Graph Neural Network (GNN). The problem is formulated as learning a probabilistic graphical model by optimizing the expectation over the graph distribution, which is parameterized by a neural network and encapsulated in a single differentiable objective. Empirical evidence suggests that the proposed GTS obtains superior forecasting performance to both deep and non-deep learning based, as well as graph and non-graph based, competitor forecasting models. In addition, GTS appears to be more computationally efficient compared to LDS, a recently proposed meta-learning graph-based approach.

##########################################################################

Strong points:
1. A time series forecasting model is proposed to automatically learn a graph structure among multiple time series and forecast them simultaneously using a GNN.

2. The graph structure and the parameters of the GNN are learned simultaneously in a joint end-to-end framework.

3. The graph structure is parameterized by neural networks rather than being treated as a (hyper)parameter, thus significantly reducing the training cost compared with the recently proposed bilevel optimization approach LDS. 

4. A structural prior-based regularization is incorporated in GTS. In case a “ground-truth” graph is provided upfront, this may serve as a healthy variation of such a graph for the purpose of more accurate forecast.

5. Extensive experiments are conducted in which the proposed GTS is compared to a number of baselines, including a recently proposed graph structure learning approach, and deep or non-deep learning based (as well as graph or non-graph based) forecasting models.

6. The experimental results demonstrate that GTS outperforms its competitor approaches in terms of forecasting accuracy and is more efficient that the recently proposed LDS.

7. Generally, the paper is well written, while the notation is clear and easy to follow.

##########################################################################

Improvement points:
1. In section 3.4. (Comparison with NRI), the authors state that the “structural prior” $A^{a}$ offers a stronger preference on the existence/absence of each edge than a uniform distribution over all edges. This seems a bit unclear, thus I would encourage the authors to elaborate a bit more on this difference between GTS and NRI w.r.t. the structural prior.

2. In the case of the PMU dataset, despite the fact that the grid topology is not provided, the authors still consider a certain structural prior by constructing a kNN graph among the PMUs. I am wondering whether the correlation between the series (mentioned briefly in Appendix A) is used for the graph construction or another distance/similarity metric is considered?

3. Two variables are recorded by the 42 PMUs, however each node in the constructed graph (shown in Fig. 5) corresponds to one PMU. In case a single node corresponds to a single PMU, then I wonder how the similarity between two PMUs’ recordings is calculated across the two variables (voltage magnitude and current magnitude)?

4. The authors construct the PMU dataset by extracting only one month of data. However, a single month of PMU data would not allow for capturing certain long-term seasonalities (for instance, the PMU recordings are typically impacted by outages that occur more frequently in certain seasons or periods in the year). Is this perhaps due to data unavailability? If that is not the case, I would ask the authors to clarify the reasoning behind the decision to extract the data for February 2017?

5. In Tables 2 & 3 (Appendix C), some of the MAPE values obtained by GST are bolded even though the same percentages are reported for GTSv. In such cases, I would suggest the authors to either bold the MAPEs obtained by both GTS and GTSv, or present the MAPE values using more decimal places.

6. There are several minor textual errors throughout the paper that can be easily addressed. Some of them are summarized as follows:
- The term “LDS” is initially used at the beginning of page 2, but is not defined earlier in the text.
- In the third paragraph on page 2, “computation is expensive” should be replaced by “its computation is expensive”.
- I am wondering whether the training loss $L$ should be used instead of the validation loss $F$ in Eq. (2)? If so, correct accordingly, otherwise disregard this comment.
- In the next-to-last paragraph on page 2, consider replacing “it is better scaled” with “it scales better”.
- In the last paragraph of the Related Work section, “of node classification tasks” should be replaced by “on node classification tasks”.
- At the beginning of section 3, the term “NRI” is used, but is not defined earlier in the text.
- On page 5, consider replacing the abbreviation “ELBO” with “evidence lower bound (ELBO)”. 
- In the first paragraph on page 7, “treating it a (hyper)parameter as in LDS” could be replaced with “treating it *as* a (hyper)parameter *which is the case* in LDS”.
- In the second paragraph on page 8, replace “regularization $\lambda$” with “regularization strength $\lambda$”. In the same sentence, consider adding “the” before both “forecasting error” and “cross entropy”.

##########################################################################

Questions during rebuttal period:
Please address the aforementioned remarks/questions.

review_title: The proposed GTS appears to advance the current state-of-the-art in graph-based multiple (multivariate) time series forecasting. This is a problem of considerable importance and, as far as I am aware, simultaneously learning the graph structure and forecasting model is understudied topic. As for the several “Improvement points” I raised in this review, I believe that the authors will have the chance to address them in the rebuttal period.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper considers learning both graph structures and NNs for time series data, similar to the idea of LDS (Franceschi et al., 2019). Observing the computation and scalability issues with LDS, authors propose a unilevel optimization form wrt. the mean performance over the graph distribution. This is done via NNs, with input being the observed sequence, to output a real matrix whose elements are then treated as weights for the Gumbel trick. NN structures, training procedure, etc. mostly follow existing works.

Overall, the paper is well presented, easy to understand, with a simple and somewhat effective modification over LDS. I generally like simple ideas with sufficient insights and explanations (though there is not much in this work), but I'm not sure if the empirical improvement is sufficient. I recommend a weak acceptance for now and may change my score after reading other reviews.

I only have one question: the proposed idea is not restricted to time-series case. So how does it perform for non-time-series data? It would be a big benefit if the proposed idea also helps in a more general case than the present scope.

** after reading response ** I thank authors for replying to my question. I maintain the previous rating.




review_title: Simple, somewhat effective idea

Meta-review: This paper presents a graph neural network-based approach to forecasting multiple time series. It incorporates structure learning similar in some ways to NRI (Kipf et al.) and a recurrent graph convolution forecaster given the inferred graph based on DCRNN (Li et al.). The paper shows consistently improved performance over several different kinds of baselines (classical, deep learning, and graph-based deep learning) on three datasets, two of which are public and one proprietary.

Reviewer 1 thought the paper was “well presented and easy to understand”. I agree. The reviewer liked the simplicity of the approach but wondered whether the empirical improvement was sufficient. The reviewer asked about applicability outside the time series domain and the authors provided a satisfying response.

Reviewer 3 thought that simultaneously learning graph structure and forecasting was an “understudied topic”. The reviewer pointed out several strengths including: the end-to-end nature of the approach, the reduction in training cost due to the direct parameterization of the adjacency matrix structure, the optimal structural regularization scheme, and the extensive experimentation. Like R1, they thought the paper was well written. They suggested several points of improvement, which were mainly seeking clarification. They made a good point regarding the PMU dataset in that only one month was considered, which was not enough to capture long-term seasonalities. This seems like a limitation to me. The authors responded to each of the points in turn. Regarding the point about the PMU dataset, the authors stated that the data was extremely noisy, so they settled on a month that was comparatively clean.

The review from R4 was not as positive as the other reviews. R4 proposed that the present work may be a “simplification of NRI” rather than being novel/different because NRI was a windowed-based approach, while GTS was based on the entire time series. The reviewer also pointed out what appears to be a highly relevant paper (Wu et al.); though this appeared in KDD 2020 and in my opinion it’s understandable if the authors missed it. Finally, R4 raised several issues with the empirical evaluation. They make a very good point that the analysis on regularization used the kNN graph where a “ground truth” graph was not available. Why not evaluate the regularizer on the other datasets where ground truth is available? The authors responded with an updated paper addressing this point. The authors responded to other points of criticism and a fairly extensive debate ensued.
The key points of the debate were:
A difference in opinion between the significance in departure between the structure learning mechanism in this work (GTS) and NRI (Kipf et al.)
Overlap between a recently proposed paper (Wu et al., KDD 2020). I am fairly sympathetic with the authors here. That work is fairly late-breaking and they do point out a key difference: "the advantage of our method over MTGNN is clear: we can get structures we desire, not restricted to a degree-k graph. This advantage is an important contribution, because MTGNN hard-wires the graph parameterization and enforces that all nodes have the same number of (out) neighbors. What if one desires instead a graph that approximately obeys spatial proximity, like that in the case of METR-LA? Our method yields such a graph."
Some minor concerns with Fig. 2 and the structural prior/regularization analysis

I have read the paper, and while R4’s concerns are legitimate, I think this paper is clearly over the bar. I support this paper’s acceptance and ask the authors to take the reviews into consideration when revising their paper. As R4 suggests, they could add a controlled set of experiments on a perhaps synthetic dataset to show that the proposed GTS is better than NRI. If the scalability of NRI is a concern, then this can be highlighted to the same extent as LDS.
Decision: Accept (Poster)