Relational Conformal Prediction for Correlated Time Series

Thanks for the review, please find point-by-point answers below.

Unclear if smaller PIs (or lower Winkler) simply stem from anti-conservativeness.

There might be a misunderstanding. The Winkler score (see Eq. 26 in the Appendix) encompasses both coverage and efficiency, i.e., a smaller PI width does not imply a lower Winkler score. Furthermore, CP methods cannot guarantee exact coverage in these scenarios due to non-exchangeability (see comment on guarantees below).

Discussion of the learned graph topology.

Experiments on GPVAR and the inclusion of the CoRNN datasets go exactly in this direction. CoRel consistently outperforms the CoRNN baseline in Tab1 showing the effectiveness of the proposed designs. Results on GPVAR show that CoREL matches the performance achievable by accessing the ground truth graph and achieves UQ performance comparable to the theoretical optimum. We will also include visualizations of the learned graph (e.g., https://imgur.com/a/uJaYNnX) - see our answer to Rev oUbs for more discussion on these results on the GPVAR dataset.

No theoretical guarantees for non-asymptotic coverage: claiming that it falls within CP is not justified.

Without any strong assumption, CP methods for TS forecasting cannot offer non-asymptotic coverage guarantees as TS data are, in general, not exchangeable (see [1]). As discussed in our paper, most CP methods for TS rely on learning either a model [2,4] or a reweighting scheme [1, 3]. The same is true for adaptive methods such [5]. CoRel belongs to the family of methods that rely on a model trained on non-conformity scores; it is distribution-free and can be applied on top of any base point predictor.

Typo eq. 9

Thanks, the correct version is:

$\hat y^i_{t} = Readout \left(h_t^{i,L}\right)$

Q1 Why only residuals as input and not also the history of the TS?

There might be a misunderstanding, as stated in lines 195–198 (right), we also use the actual time series as part of the input.

Q2 Motivation to feed to the decoder TS independently rather than matrix Z_t in Eq.(12).

Because: (1) it would result in a fully connected layer with a large number of learnable parameters likely to incur overfitting; (2) it would constrain the model to operate on the full set of TS at once while the proposed architecture can operate on any subset separately (more scalable); (3) it would defeat the purpose of using a message-passing architecture rather than a simple fully connected MLP; (4) while the UQ procedure accounts for past observations at correlated TS, prediction intervals for each TS are independent of the others (see below). Note that analogous parameter-sharing architectures, with message passing and sequence modeling operators, are at the core of graph-based processing for TS [6].

Q3 Conformal sets are cubes (cf. Eq. (14)). This appears suboptimal, as it does not leverage the learned structure.

There might be a misunderstanding, which might be due to the admittedly dense notation (we will make sure to improve it). Our framework leverages the learned correlation structure to account for dependencies w.r.t. past observations at correlated TS rather than to model the joint distribution of future observations. In particular, we model conditional probabilities as in Eq. 1 (i.e., we model $p(x_t^i|X_{<t}, U_{<t}) \forall i$ rather than $p(X_t|X_{<t}, U_{<t}))$. While modeling joint probabilities within our framework can be interesting, it is a different problem out of scope here. We will clarify this aspect and mention it as an important direction. Thanks for raising this point.

Q4 The way this sparsity prior is used is not clear to me.

As explained in Sec. 3.2 we parametrize the graph learning module to learn at most K<<N edges for each node. This improves scalability and can also improve sample efficiency [7].

Q5 The way the adaptive version of the method works is not clear to me.

We train the entire model on the full calibration set and use adaptation at test time. Basically, at test time, we simulate a real-world scenario where new data become available over time and are used for fine-tuning. Instead of retraining the entire model (as in [2]), we just fine-tune the node embeddings. Instead of finetuning at each time step (high variance and high computational cost), we fine-tune the model every M time step.

[1] Barber et al. “Conformal prediction beyond exchangeability” Ann. Statist. 2023
[2] Xu et al. “Sequential Predictive Conformal Inference for Time Series” ICML 2023
[3] Auer et al. “Conformal Prediction for Time Series with Modern Hopfield Networks” NeurIPS 2023
[4] Xu et al. ”Conformal prediction interval for dynamic time-series” ICML 2021
[5] Gibbs et al. “Adaptive conformal inference under distribution shift” NeurIPS 2021
[6] Cini et al. “Graph deep learning for time series forecasting” arXiv 2023
[7] Cini et al. “Sparse graph learning from spatiotemporal time series” JMLR 2023

Thank you for the review. Please find our comments below.

Comparisons against standard CP methods in terms of runtime are needed to fully validate efficiency claims.

The main two baselines to compare to here would be SCPI and HopCPT. Scalability issues for SCPI comes from training a different model for each time series which results in high computational costs when dealing with multiple TS. Regarding HopCPT, the main computational bottleneck is due to attention scores being computed w.r.t. the considered sequence at each time step which results in a quadratic complexity w.r.t. the sequence length. Conversely, CoRel shares most of the parameters among the time series collection and its training can be efficiently parallelized on a GPU. Furthermore, it relies only on a short window of the most recent observations + node embeddings at each time step. If we consider LA (which is the smallest dataset in terms of numbers of time series) training and testing require ~3 days for SCPI , ~11 hours for HopCPT and ~5 minutes for CoRel. We will put more emphasis on this aspect in the paper.

W1 Graph inference and message passing may introduce scalability issues.

Scalability is inherently an issue when dealing with multiple TS simultaneously, so it can be a challenge, but not a limitation of our method. Additionally, graph inference and message-passing layers can have different computational complexity, depending on how the different components are implemented. Research on scalable graph structure learning methods (e.g., [1]) and STGNN architectures is very active (e.g., see [2,3] for discussion on existing architectures); these approaches could be integrated in the framework. Furthermore, one can rely on graph subsampling techniques (e.g., [4]) to enable scalability. We will mention these points in the paper, thank you.

W2 No formal guarantee that the learned graph structure is optimal[...] Visualizations or comparisons could help.

First of all, there is not a clear optimality criterion here as the graph is directly learned end-to-end with the quantile regressor and as such it will strongly depend on the actual implementation of the quantile network (e.g., no. of layers, no. of message-passing steps, and so on). Learning a graph here serves the purpose of obtaining good performance on the downstream task. That being said, the experiment on the synthetic GPVAR dataset (where the ground-truth graph is known a priori) shows that CoRel can match the performance of the model that has access to the true graph and in this scenario, the learned graph closely matches the ground truth. A visualization of the learned graph against the ground truth is available here: https://imgur.com/a/uJaYNnX. As shown by the picture the learned graph includes all the actual edges plus some additional links. As detailed in the paper, in GPVAR, data were created by injecting Gaussian noise into the diffusion process with a std of 0.4 which implies that having direct access to the data-generating process would allow one to obtain (asymptotically) a 90% marginal coverage with a PI width of 1.315. CoRel achieves essentially perfect coverage with PI width of 1.329 $\pm$ .002 (close to the theoretical optimum) while CoRNN requires a PI width of 1.63 $\pm$ 0.01 to obtain similar coverage. We will include these comments and visualizations of the learned adjacency matrix in the paper. Thank you for raising this point.

W3 No benchmark against other graph-based uncertainty quantification approaches such as [1]. It would be interesting to compare and discuss the results here.

We discuss several graph-based approaches for uncertainty quantification in the related works, but, as noted in the paper, none of these are post hoc methods and, as such, cannot be directly compared to our approach. Existing CP approaches for graphs are also not applicable to TS processing, e.g., the referenced paper targets link prediction. Nonetheless, we agree that the discussion on this aspect can be extended further, and we will include [1] as a relevant reference.

Q2 Not deeply familiar with the specifics of the datasets [...] Are there any limitations to CoRel? Under what conditions might its performance degrade? A discussion on limitations would be valuable.

The considered datasets are well-known in correlated TS forecasting and have been extensively used in the related literature. CoRel relies on the assumption of the existence of a Granger causality among TS (as mentioned in the paper), if that is not the case we can expect its performance to be analogous to that of the CoRNN baseline. Indeed, as shown in the experiments, the gap in performance between CoRel and CoRNN is smaller when using an STGNN as a base model, as the STGNN already partially captures relational dependencies. In the updated paper, we will comment on these aspects and provide additional details on future work (see rebuttals to other reviewers).

Thank you for the review! Please find our answers to your questions below.

Missing reference.

We agree it is a relevant reference. We will include it in the updated version of the paper. Thank you.

Typos.

Thank you for spotting those!

Prop 3.1 [...] blankets everything that could undermine the conformal guarantee under the total variation. [...] The authors claim that [we can expect the total variation between the learned and true distribution to shrink asymptotically] but provided no proof to support this claim. [...] this is a common argument, but even supporting citations will help, a proof with the specific setup will be better.

Thank you for the comment. As noted, a proof would require assumptions on the data generation process and on the specific implementation of the quantile regressor and message-passing operators. We feel this would not add a lot to the paper since, as you noted, a similar analysis has been done in recent works by Lee, Xu, and Xie. We do, however, agree on the necessity to further discuss this aspect and the related references; we will do this in the updated version. Thanks again for the comment.

Thanks for the review please find our comments below.

Further comparisons with existing methods and additional concrete examples of scenarios where COREL outperforms other methods can bolster the robustness. [...] This comparative approach is valid but could be strengthened by including a wider variety of baseline models and clarifying their selection rationale.

Thank you for the comment. The included baselines are representative of the current state of the art and existing approaches to the problem; SCPI and HopCPT, in particular, are modern and very competitive baselines. The paper includes results from 3 datasets and 3 different base models together with 1 synthetic dataset with 2 base models for a total of 11 different benchmark scenarios. We will also include the compute time of the different baselines (see our rebuttal to Rev oUbs). We believe this is an adequate evaluation setup as it highlights the strengths and weaknesses of the different methods in different settings. Nevertheless, we agree that the motivations for choosing the selected baselines could have been discussed more. We will include these considerations in the paper.

Controlled environment adds rigor but assumes the simulation accurately represents real-world scenarios, which may not always hold.

There might be a misunderstanding. The objective of the experiment on the synthetic dataset is not to mimic a real-world scenario but to show that CoRel can learn and exploit latent relationships among time series. Indeed, its performance here matches that achievable by a model with access to the ground truth relational structure, and its UQ performance is close to the theoretical optimum. For further discussion and analysis, see also our comments on the GPVAR experiment in response to Rev oUbs.

The adaptability experiments evaluating COREL's performance in non-stationary settings are crucial, but more detail on the fine-tuning methods used would enhance transparency.

Details of the fine-tuning procedure are provided in the appendix. In short, embeddings are updated every M time steps by running the training procedure on the latest observations and keeping all the parameters frozen except for the embeddings. Are there specific aspects that you believe would benefit from more discussion? We will move part of the description of the adaptation procedure to the main body of the paper and we are available for further clarifications.

W1 The integration of graph deep learning may increase computational complexity and resource requirements, potentially limiting its practical deployment in resource-constrained environments.

The additional computational complexity is inherent in operating on multiple TS simultaneously. Thus, it is more a challenge of the problem settings rather than an issue with our approach. Furthermore, CoRel is much more scalable than the baselines in these settings as discussed in the rebuttal to Reviewer oUbs’ comments. There are also techniques to make the graph-based processing scalable that could be applied here as well. These techniques range from graph sub-sampling (e.g., [1,2]) to scalable architectures (e.g., [3,4]). We will include a discussion of this aspect in the paper.

W2 The paper could provide more clarity on the assumptions made about the structure and nature of the underlying data, which may affect generalizability.

We do not rely on strong assumptions about the correlated TS besides the existence of Granger causality among them for the graph-based approach to be beneficial. Stationarity assumptions are also discussed in the paper. The sparsity assumption is more of an inductive bias/regularization for learning a sparse graph. If the sparsity assumption is deemed to be unrealistic for a problem at hand, it would be possible to use operators to learn a dense graph, e.g., by modeling each edge as a Bernoulli RV. We will add a comment on this aspect in the paper.

W3/Q1 While adaptability is addressed [...] authors can possibly further explore how well their method performs in broader non-stationary conditions.

We provide a simple and effective method to make our approach adaptive and show its effectiveness in 3 different scenarios. However, adaptability is not the central focus of our work, which focuses on CP on related TS. We believe that a dedicated study would be needed to address non-stationary settings in depth, as we discuss in the future work section. We will emphasize the importance of this direction in the updated paper.

[1] Hamilton et al. “Inductive representation learning on large graphs” NeurIPS 2017
[2] Chiang et al. “Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks” KDD 2019
[3] Frasca et al. “SIGN: Scalable Inception Graph Neural Networks” arXiv 2020
[4] Cini et al. “Scalable Spatiotemporal Graph Neural Networks” AAAI 2023

Thank you for your review! Please find our point-by-point answers below.

Results show that the proposed model is better on Winkler score but not on the other two metrics. Hence, cannot claim that the proposed model is superior.

Coverage and PI Width on their own do not say much about UQ performance, as one can trivially get high coverage with an arbitrarily large prediction interval or get small PI Width with a narrow, but not valid, one. Doing well on both aspects at the same time is the challenge: the Winkler score (see Appendix) considers coverage and PI width at the same time. We will add this comment to the paper.

It would have been important to show how modeling spatio-temporal relationships has provided additional insights.

The inclusion of the CoRNN baseline which does not include any message passing or graph learning component, provides the insights asked by the reviewer by showing the impact of the proposed designs. Furthermore, experiments on the synthetic GPVAR dataset (where spatial dependencies determine the observed dynamics) show that CoRel can match the performance of a model that has access to the ground-truth graph and obtain UQ performance close to the theoretical optimum (see rebuttal to Rev oUbs). Additionally, there is a wide literature on how modeling and learning relational dependencies is beneficial in TS (e.g., see [1,2]). Our framework allows one to benefit from such representations in post hoc UQ.

I did not see any experimental designs or analyses of the same or results of such experimental designs.

There might be a misunderstanding. We designed a set of benchmarks for assessing post hoc UQ quantification on correlated TS. The selected datasets have already been used in the context of TS forecasting, but their use in the context of UQ is new. This also required setting up different base models to test UQ methods in different scenarios for each dataset. Furthermore, we also included a synthetic dataset to further validate the proposed designs. We believe that experiments do show the effectiveness of CoRel.

The authors focused on univariate analysis. Ideally, one should demonstrate the approach with multivariate time series.

Our approach can be extended to collections of multivariate TS by pairing the proposed framework with a quantile regressor able to handle multivariate data at each node, e.g., [3], or by simply using a separate quantile regressor for each output channel. Note, however, that this is orthogonal to the proposed approach. We will include a comment on this in the paper.

While the approach is different from previous works, it's important to quantitatively demonstrate how predicting the quantiles of the error distribution is better than forecasting the target.

There might be a misunderstanding. As with any CP method, CoRel quantifies the uncertainty of the predictions of a base pre-trained model. This is a fundamentally different problem from learning a probabilistic predictor directly. It is not possible to set up a direct comparison as the results would heavily depend on the base predictor. This difference is pointed out in Sec. 1 and 4, we will make sure to further emphasize this aspect.

One does not know actual utility of this work to an application engineer. How does this work make a difference in real life?

We agree on the importance of engineering applications. The usefulness of more accurate UQ (and CP methods in particular) in real-world applications is widely recognized [4]. However assessing the practical impact of a particular method in a specific application and downstream task is orthogonal to our contribution, which is on fundamental research in ML and statistics.

Would a 1 or 2 %improvement in Winkler score make a great difference? Any difference for the user?

There may be a misunderstanding. Differences in Winkler score are quite significant in all the considered scenarios (even more than 10% in some cases) and a 10% difference in performance is highly significant in any engineering application. As discussed in previous answers, coverage and PI width should be considered together. For an example of how CoRel's prediction intervals look compared to the CoRNN baseline in a given scenario (LA dataset with an RNN base model), see https://imgur.com/a/UYIj0nR. Additionally, we believe that the consistent performance improvements and methodological novelty make our paper a relevant contribution on its own, besides specific applications. The analysis of specific applications in science and engineering is out of scope and would require separate studies.

[1] Jin et al. “A survey on graph neural networks for time series” TPAMI 2024
[2] Cini et al. “Graph deep learning for time series forecasting” arXiv 2023
[3] Feldman et al. “Calibrated Multiple-Output Quantile Regression with Representation Learning” JMLR 2023
[4] Smith, “Uncertainty Quantification: Theory, Implementation, and Applications” SIAM 2013