Relational Conformal Prediction for Correlated Time Series
Authors: Andrea Cini
Alexander Jenkins
Danilo Mandic
Cesare Alippi
Filippo Maria Bianchi
Venue: ICML 2025 poster (2025)
Keywords: uncertainty quantification
conformal prediction
time series forecasting
graph deep learning
Primary area: general_machine_learning->sequential_network_and_time_series_modeling
TL;DR: We propose an effective and sound conformal prediction method for uncertainty quantification in correlated time series forecasting by relying on graph deep learning operators.

Abstract: We address the problem of uncertainty quantification in time series forecasting by exploiting observations at correlated sequences. Relational deep learning methods leveraging graph representations are among the most effective tools for obtaining point estimates from spatiotemporal data and correlated time series. However, the problem of exploiting relational structures to estimate the uncertainty of such predictions has been largely overlooked in the same context. To this end, we propose a novel distribution-free approach based on the conformal prediction framework and quantile regression. Despite the recent applications of conformal prediction to sequential data, existing methods operate independently on each target time series and do not account for relationships among them when constructing the prediction interval. We fill this void by introducing a novel conformal prediction method based on graph deep learning operators. Our approach, named Conformal Relational Prediction (CoRel), does not require the relational structure (graph) to be known a priori and can be applied on top of any pre-trained predictor. Additionally, CoRel includes an adaptive component to handle non-exchangeable data and changes in the input time series. Our approach provides accurate coverage and achieves state-of-the-art uncertainty quantification in relevant benchmarks.

Relational Conformal Prediction for Correlated Time Series
Andrea Cini Alexander Jenkins Danilo Mandic Cesare Alippi 14
Filippo Maria Bianchi 56
Abstract
et al., 2024). In many application domains, such time series are characterized by rich spatiotemporal dependency struc- ture that can be exploited by introducing inductive biases in the forecasting architecture (Cini et al., 2023a), to steer the learning procedure toward the most plausible models. Ac- counting for the existing dependencies, usually represented as a graph, allows the resulting models to obtain accurate predictions with a reduced sample complexity (Jin et al., 2023; Cini al., 2023a). Besides the accuracy of the point estimates, the reliability of the forecasts is critical aspect of the problem and key element to enable effective decision- making in many applications (Makridakis, 1996; Petropou- los et al., 2022). Uncertainty quantification methods (Smith, 2024; Vovk et al., 2005) can improve reliability by provid- ing confidence intervals on the forecasting error magnitude, allowing for making more informed decisions (Hyndman and Athanasopoulos, 2018). This is particularly true for risk-sensitive applications such as healthcare (Makridakis et al., 2019) and load forecasting (Gasparin et al., 2022). In this context, inter-series (spatiotemporal) dynamics offer both a challenge and an opportunity. Indeed, while these dependencies can lead to wide prediction intervals (PIs) if overlooked, they may also provide additional knowledge to reduce uncertainty (Zambon and Alippi, 2022).
We address the problem of uncertainty quantifi- cation in time series forecasting by exploiting observations at correlated sequences. Relational deep learning methods leveraging graph repre- sentations are among the most effective tools for obtaining point estimates from spatiotemporal data and correlated time series. However, the problem of exploiting relational structures to es- timate the uncertainty of such predictions has been largely overlooked in the same context. To this end, we propose a novel distribution-free ap- proach based on the conformal prediction frame- work and quantile regression. Despite the recent applications of conformal prediction to sequen- tial data, existing methods operate independently each target time series and do not account for relationships among them when constructing the prediction interval. We fill this void by in- troducing a novel conformal prediction method based on graph deep learning operators. Our approach, named Conformal Relational Predic- tion (COReL), does not require the relational structure (graph) be known priori and be applied top of any pre- trained predictor. Addi- tionally, COREL includes an adaptive component to handle non-ex eonhexchaneeeale data and changes in the input time series. Our approach provides ac- curate coverage and achieves state-of-the un- certainty quantification in relevant benchmarks.
Existing probabilistic forecasting frameworks often rely on strong distributional assumptions and major modifications of the base point predictor (Benidis et al., 2022; Salinas et al., 2020). As such, they cannot be used to quantify un- certainty given a pre-trained forecasting model. In such a setting, conformal prediction (CP) (Vovk et al., 2005; Angelopoulos et al., 2023) methods are particularly appeal- ing. CP is an uncertainty quantification framework that estimates confidence intervals with marginal coverage guar- antees from observed prediction residuals. One of the main assumptions of standard CP methods is that of exchange- ability between the data used to estimate the confidence intervals and the test data points, i.e., the assumption that their joint probability distribution invariant to the ordering of the associated sequence of random variables (Angelopou- los al., 2024). Although this assumption does not usually hold when operating on time series (Barber et al., 2023), several methods have successfully adapted CP to estimate forecast uncertainty (Stankeviciute et al., 2021; Xu and Xie, 2023a;b; Jensen et al., 2022: Auer et al., 2023). Never- theless, existing CP approaches operate on each (possibly
1. Introduction
Many recent advancements in deep learning methods for time series forecasting rely on learning from large collec- tions of (related) time series (Benidis et al., 2022; Liang
'IDSIA USI-SUPSI, Università della Svizzera italiana SSiss National Science Foundation Postdoc Fellow 'Imperial College London 'Politecnico di Milano 'UT The Arctic University of Nor- way 'NOCCE Norwegian Research Centre AS. Correspondence to: Andrea Cini <andrea.cin @ @usi.hh>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Relational Conformal Prediction for Correlated Time Series
multivariate) time series independently and cannot account for dependencies among correlated time series.
observations up time step I (excluded). Time series are assumed to be homogenous, i.e., all the variables (observ- ables) describe the same physical quantity (e.g.. temperature or energy consumption). Analogously, U2 E R Vdd. indi- cates the d..ddimensiona exogenous covariates associated with each time series. We assume that the i-th time series is generated by a stochastic time-invariant process such as
In this paper, we propose Conformal Relational Predic- tion (CoREL), a novel CP approach leveraging graph representations and graph deep learning (GDL) for quan- tifying uncertainty in correlated time series forecasting. In our framework, a spatiotemporal graph neural net- work (STGNN) (Jin al., 2023; Cini et al., 2023a) trained on calibration set to approximate the quantile function of the distribution of prediction residuals. Relationships among time series, assumed to be sparse, are learned end-to-end from the observed residuals owing to a graph structure learn- ing module integrated into the processing. Our approach estimates the error quantile function for each time series at each time step. by conditioning the shared uncertainty quantification model past observations at neighboring nodes (as defined by the learned graph structure). Finally, an adaptive component is added to handle potential non- stationarities by relying on a small set of parameters specific to each time series. Our approach can be applied to the resid- uals generated by any point forecasting model, even those that completely disregard potential relationships among the input time series.
ot ~ (a)) Xet, U<t).
(I)
Let us hypothesize the existence of sparse predictive causality à la Granger (Granger, 1969), i.e., we assume that the values of a single time series are related to the val- ues of a (small) subset of other time series in the collection. The extension of the framework to collections of multivari- ate time series is orthogonal to the proposed approach (e.g.. see Feldman et al. 2023); focus the univariate case maintain a contained scope. The problem of dealing with non- non-stationary processes will be discussed in Sec. 3.4.
Forecasting We are interested in a model that pro- duces point forecasts by predicting the unknown H-steps- ahead (H > 0) observation X X++ given window W 2 1 of past observations X X-- and the associated exogenous
variables U.
Our main novel contributions can be summarized follows.
X = Fo(, W.)
(2)
The first application of GDL to CP for time series;
Fa denotes generic parametric model family, i.e., simple recurrent neural network (RNN) for univariate time series. Given a trained model, our objective is to build a confidence interval around predictions X.+H. Note that the following easily extends to multi-step predictions X but we focus forecasting the single time step H to simplify the presentation and discussion.
A novel, sound, and effective CP method able to quan- tify uncertainty from observations across a collection of correlated time series;
A family of graph-based architectures to estimate un- certainty that shares most of the learnable parameters among the processed time series, while including node- level parameters that dynamically adapt to changes in each target sequence.
Uncertainty quantification PIs, (X,(()))) such that
Our objective is to estimate
Empirical results show that COREL achieves state-of-the te--hhe-an art performance compared to existing CP approaches for time series in several datasets and under different scenarios.
P ( E C,,,, (X++1) 2 1 -
(3)
where a is the desired confidence level. If the interval satisfies Eq. 3, we say that the PI achieves marginal coverage a. Similarly, we say that the PI provides conditional coverage a
2. Preliminaries
This section introduces the problem settings and the prelim- inary concepts that serve as foundations for our approach.
P P( E C. (X++)) X 21 a. (4)
Conditional coverage provides stronger guarantees and it is often harder to achieve (Angelopoulos et al., 2024). In the following, will omit the dependence of the interval the forecasts and simply write C,,-- Among uncertainty quan- tification methods, we are interested in post-hoc approaches that can build confidence intervals for any given pre-trained point predictor Fg without requiring any modification of the base forecasting architecture.
2.1. Problem Formulation
Consider a collection of N correlated time series. Denote by of E R the scalar target variable associated with the i-th time series at time step t; X, E Nx1 indicates the N stacked target variables w.r.t. the entire time series col- lection. X indicates the sequence within time interval [t, + T); conversely, with the shorthand Xxt refers to
2

---

Relational Conformal Prediction for Correlated Time Series
2.2. Conformal Prediction
dis al., 2022). The simplest approach consists of using a multi-output network to predict set of quantiles of interest and interpolate among them to approximate the entire quan- tile function (Wen et al., 2017). More complex approaches rely on, e-g. splines (Gasthaus et al., 2019). Conversely, implicit quantile networks (IQNs) (Dabney et al., 2018; Os- trovski et al., 2018; Gouttes et al., 2021) approximate the quantile function by being trained to minimize the loss in Eq. 6 given the quantile level as input and sampling random for each sample in mini-batch.
As anticipated in Sec. 1, standard CP methods (Vovk al., 2005; Angelopoulos et al., 2023) are a class of distribution- free uncertainty quantification techniques that build Pls from empirical quantiles of conformal scores. In the forecasting setting, we consider as conformal scores the prediction resid- uals,
(5)
and use R² to denote residuals w.r.t. the entire time series collection. Under appropriate assumptions, CP methods can build valid and informative PIs (Angelopoulos et al., 2023; Barber et al., 2023). Split conformal prediction (SCP) (Vovk et al., 2005) is arguably the most common approach and exploits scores computed on a calibration set that is disjoint from the training data (i.c., a post-hoc approach).
2.4. Graph Deep Learning for Time Series Forecasting
Graph neural networks (GNNs) (Bacciu al., 2020; Bron- stein et al., 2021) process graph-structured data by incor- porating the graph topology as an inductive bias, e.g., by relying on messsage-passing layers (Gilmer et al., 2017). STGNNs (Jin et al., 2023; Cini et al., 2023a) leverage message-passinng layers within sequence modeling archi- tectures to process spatiotemporal data and collections of time series where dependencies are represented as (possi- bly dynamic) graph. We consider as reference architectures time-then-space (TTS) models (Gao and Ribeiro, 2022; Cini et al., 2023a) where each time series in the collection is pro- cessed independently from the others by a temporal encoder whose output is then fed into a stack of GNN layers. In particular, we adopt the following template architecture:
As mentioned, most standard CP methods rely on the as- sumption that calibration and test data are exchangeable, which allows the procedure to treat them symmetrically and obtain valid (marginal) coverage guarantees (Angelopoulos et al., 2024). Since this assumption does not hold when dealing with time series data, there have been several recent results extending the CP framework beyond exchangeabil- ity (Tibshirani al., 2019; Stankeviciute et al., 2021; Gibbs and Candes, 2021: Xu and Xie, 2023a). In particular, Bar- ber et al. (2023) showed that approximate coverage can be achieved by reweighting the residuals to account for the lack of exchangeability between calibration and test set. Auer et al. (2023) Iearn such a reweighting scheme through an attention-basee architecture. Differently, Xu and Xie (2023b) introduce SPCI, a method based on fitting a quan- tile random forest (Meinshausen and Ridgeway, 2006) the most recent prediction residuals at each time step. Sim- ilar to SPCI, our approach relies on quantile regression to build Pls but differently from existing methods, it exploits observations in arbitrary sets of time series by relying on GDL operators.
h 0.0 = SEQENC (zt w::: u(_wx):
H H!+1 (H), [= 0,...,4-11 (8)
y = READOUT (n:"
where A E RNN, is the graph adjacency matrix and ğ a generie node-level prediction associated with the problem at hand. SEQENC(-) and G-N((-) denote, respectively, any se- quence modeling architecture, e.g., an RNN, and any GNN layer, e.g.. based on paassig... Representations can then be mapped into predictions Y, by using any readout block, e.g., a multilayer perceptron (MLP). STGNNs have been used as forecasting architecture (Y, = X,+ with great success. In the following, we will exploit this frame- work backbone for estimating the residual quantile dis- tribution. We refer to Sec. 4 and Jin et al. (2023) for more discussion on the application of STGNNs in the context of time series analysis.
2.3. Quantile Regression
Quantile regression (Koenker and Hallock, 2001) is es- tablished statistical framework that consists of learning a model of the quantile function (the inverse c.d.f.) of a target distribution from observations. In particular, given ~ ppylaa (z) and observations (z1,,1),.... (IN. BN), a standard approach to estimate the a-quantile is to train a model by minimizing the so-called pinball loss
3. Conformal Relational Prediction
(1 (1-))(f((=)- - v). (x)),
(x)x) 2
es (z),
(6)
Our objective is to build Pis by exploiting relational depen- dencies across the residuals of the target time series. We model the dependencies as edges of a graph and learn them under the assumption that the relational structure is sparse, which reduces the computational costs and act as an induc- tive bias on the structure learning architecture. By relying on
(x) <
where qah (z) is the estimate of the a-quantile w.r.t.
Quantile networks Quantile regression has been incorpo- rated in several probabilistic forecasting architectures (Beni-
3

---

Relational Conformal Prediction for Correlated Time Series
CoRel
CoRel
Ret
Q
H S
α
Z
Ret
STGNN
Enc
Qeec
Learnt gruph
Node embeddingg, V
t- W
t
+ H
Ground truth
Predicted g
Prediction interval
Figure Overview of COREL.. Past residuals are used input hybrid global-local graph-based quantile network.
such representation, we can leverage GDL methods for time series to process the data. In particular, we train a STGNN on the residuals of the calibration set to predict the quantiles of the error distribution. Conditioning the prediction on the recent history of related time series allows for taking the dependency structure of the data into account when es- timating uncertainty: key aspect in applying conformal prediction to non-exchangeable data (Barber et al., 2023). Compared to existing methods (Xu and Xie, 2023b; Auer et al., 2023) that only capture temporal dependencies, our approach allows for modeling spatiotemporal dependencies among different time series. Sec. 3.1 presents the details of the proposed conformal inference procedure by assuming that the relational structure at each time step defined by an adjacency matrix A E R N (Sec. 3.1). We then show how to learn the graph structure directly from data and make the model adaptive in Sec. 3.2 and Sec. 3.4, respectively. Finally, we discuss the theoretical properties of the approach in Sec. 3.3. Fig. shows an overview of the architecture.
following processing layers:
h = ENC (ri (ri-1.
(10)
Z: = STGNN (E
(11)
Lia 4
QDEC (a,z), 20,0))
(12)
where r|-1 are prediction residuals (Eq. 5) and 46t is the predicted a-quantile at time step t + H for the i-th time series. ENC( -) denotes any encoding layer, e.g., linear transformation or an MLP. For the STGNN block, several designs are possible (e.g., see Jin et al. 2023); the one we follow the template in Sec. 2.4. QDEC( is a readout mapping the representations each node the prediction of the quantile of specified level a. We refer to the family of quantile networks defined in Eq. 10-12 as relational quantile predictors (RelQPs) and use the notation
a0.2
Qi = (a, V; R,,,, A),
(13)
3.1. Relational Quantile Predictor
where 2p indicates the shared (global) part of the network and Q .R- denotes the predicted a-quantiles time step l w.r.t. the full time series collection. Note that the framework can casily accommodate further inputs at the en- coding block (e.g.. we can condition the regression on X and Uz.) The model is trained by minimizing the pinball loss (Eq. 6) at each time step in the calibration set w.r.t. the full-time series collection. Through the message-passing layers, the residuals of each time series contribute to esti- mating the quantiles of the error distribution at neighboring nodes. In practice, we restrict the input of the regressor to the most recent observations rather than considering the full sequence (the window length here can also be different from the one used by the point predictor).
Consider a standard SCP setup, where the training data are split into training and calibration sets. For the moment, we disregard possible nonstationarities in the data considering the problem setup introduced in See. 2.1 and encode spatial dependencies in the adjacency matrix A E RNNN While the training set is used to fit the point predictor Fo, we use the prediction residuals in the calibration set (Real) to learn the quantile function of the error distribution at each step.
Relational quantile regression We implement the quan- tile regressor as a hybrid global-local STGNN, which mixes global (shared) parameters with local, target-specific com- ponents (Smyl, 2020). Sharing most learnable parameters across all time series reduces sample complexity, while lo- cal parameters allow for tailoring the processing to each series. Specifically, we keep all processing blocks shared and associate a learnable node embedding v¹ E Rd with each time series (Cini et al., 2023b). More specifically, our model is a quantile network (see Sec. 2.3) composed of the
Building the confidence intervals Given the trained quan- tile network 2.., we build the PIs for each target (test) time step as
O = [ + qi ..0/2 , 11 + a. -a/2-
(14)

---

Relational Conformal Prediction for Correlated Time Series
or
Xie and Ermon (2019) paired with straight-thruugh gradi- ent estimator (Bengio et al., 2013) to obtain discrete samples. Optionally, we sparsify the gradients by backpropagating only through random subset of the zero entries of A (more details are provided in App. D). As already mentioned, dif- ferent parametrizations and gradient estimators for subset samplers exist and can be considered. Furthermore, if the sparsity assumption deemed unrealistic for the problem at hand, other distributions (e.g., based on Bernoulli random variables) can be considered (Cini et al., 2023c).
B, arg min
qi
1.1 al22//2
d: //
(15)
B,
Cg = ai+n + q. / Binn H + qi -0.1-//24 (16)
where Ög indicates the estimated PI. While both Eq. 14
and Eq. 16 correspond to the same confidence level, the PI in Eq. 16 can be narrower, at the expense of the additional computation needed to obtain 33 (Xu and Xie, 2023a). In practice, one can choose between the two approaches given computational constraints and the difference in performance observed on validation set. Note that C% can provide only approximate coverage, as it is subject to approximation errors of the true quantile function. Sec. 3.3 will discuss this aspect in detail. A potential drawback of COREL that residuals cannot be assumed exchangeable in most practi- cal scenarios. The error distribution can be non-stationary, making it difficult to obtain any coverage guarantee. To mitigate the problem, Sec. 3.4 discusses an efficient and scalable approach to make the framework adaptive by updat- ing local components of the architecture over time. Finally, is worth noting that the use of relational components in COREL relies on the actual presence of the associated depen- dencies in the data. In practical applications, the presence of spatiotemporal correlations in the residuals can be verified through ad-hoc statistical tests (Zambon and Alippi, 2022; 2023), whose outcome can support the adoption of CORBL.
3.3. Theoretical Analysis and Further Discussion
We start the discussion by providing an intuitive bound on the approximate coverage provided by COREL.
Proposition 3.1. Let Pi (
= PL+H ( I
Xx1, U21) and P (at x== Pyl Po (Fr+H H | Xxi U2)) be the true conditional data- tata-generating distribution at the test point I + H and the probability distribution associated with the learned quantile function Q respectively. Then
Pit (zitu E C2 (xi()))))) 21-a (P (Pt,
where TV(.) denotes the total variation function.
The proof relies on the properties of the total variation of probability measures and can be found in App. A. Here, differently from the problem settings introduced in Sec. 2.1, we do not assume the process to be inve-invariant. Prop. 3.1 links the conditional coverage gap to the approximation er- ror in estimating the quantile function of the residuals. The bound provided in Prop. 3.1 shares similarities with the one in (Barber et al., 2023), which bounds the miscoverage gap for CP from weighted empirical quantiles. Prop. 3.1 can be seen as an analogous result that holds when estimates obtained from empirical quantiles are replaced with a para- metric function approximation. By making assumptions on the expressivity of the quantile regressor in Eq. 13 and on the stationarity process (e.g., by assuming a strongly mixing process), we can expect the total variation between the learned and true distribution shrink asymptotically as the size of the calibration set increases. Moreover, in this case, monitoring the coverage gap on a validation set offers an estimate of the actual miscoverage on test data. Simi- lar analyses have been carried out for recently introduced CP methods for time series (Xu and Xie, 2023b; Lee et al., 2025); we refer the reader these related works. If we instead expect the process to be non-stationary, 2₂ has to be updated over time to keep the coverage gap contained. Within this context, the next section discusses a simple and sample-efficient approach to make COREL adaptive. Fi- nally, the computational complexity of COREL will depend on the STGNN used to implement the ReIQP and the num- ber of edges sampled while learning the relational structure.
3.2. Learning the Relational Structure
Assuming the dependency structure across time series to be unknown, we integrate a graph learning module into the ar- chitecture to derive the operational graph topology directly from the residuals. To do so, we adopt a probabilistic struc- ture learning framework (Niculae et al., 2023; Cini et al., 2023c; Manenti et al., 2024). In particular, we associate each edge with a score شهه and learn a distribution over K-NN graphs parametrized by the matrix $ E N (Cini et al., 2023c; Kazi et al., 2022). Notably, we consider graphs ob- tained by sampling, for each é-th node, K elements without replacement from the categorical distribution
Φ- Eg (Reis V,...)
(17)
exp(sit1] exp(xx00)
M, Categorical
ik E (1....,,N)
N)
(18)
where Eg(-) is a generic trainable encoder with parameters g. In practice, sampling can be done efficiently by exploiting the GumbelTopk trick (Kool et al., 2019) and scores & can be parametrized directly as +- =
End-to-end learning To propagate gradients through the sampling, we rely on the continuous relations introduced by
5

---

Relational Conformal Prediction for Correlated Time Series
For example, the cost of a forward pass for a standard TTS STGNN with window size W and a graph with E edges would scale as O(WN + E) (Cini et al., 2023a).
Conformal prediction Related work on CP for time series has been already discussed in See. 2.2 and Sec. 3. Related to our method, Mao et al. (2024) propose a CP approach for (static) spatially correlated data. Jiang et al. (2024) pro- pose to quantify the uncertainty in predicting power outages by fitting a quantile random forest (Meinshausen and Ridge- way, 2006) on time series from neighboring geographical units. COREL can be framed among the CP methods that learn model of conformal scores distribution (Xu and Xie, 2023b; Lee et al., 2024). Differently from existing methods that operate on each time series separately, the estimates are conditioned on errors at both the target time series as well as at neighboring nodes. To the best of our knowledge, no previous CP method has been designed to specifically oper- ate on collections of correlated time series and exploit graph deep learning operators. CP methods for multivariate time series do exist (Xu al., 2024; Sun and Yu, 2024; Feldman et al., 2023), but operate on single multidimensional time series. Moreover, although global-local models are popular among forecasting architectures (Smyl, 2020; Benidis et al., 2022), COREL is the first CP architecture of this kind. Fi- nally, CP methods have also been applied to static graphs and used to quantify the uncertainty of GNNs, both in induc- tive (Zargarbashi et al., 2023) and transductive (Huang et al., 2024) settings. These methods often assume node/edge ex- changeability (Zargarbashi et al., 2023; Huang et al., 2024) or are limited to node classification (Clarkson, 2023) or link prediction (Zhao et al., 2024). Recently, Davis et al. (2024) proposed CP method for node classification with GNNs in dynamic networks.
3.4. Adaptation
The RelQP model introduced in Sec. 3.1 can yield arbitrarily large coverage gaps in the presence of distribution shifts from the calibration set where the model is trained. Adopt- ing a re-training approach, such as in Xu and Xie (2023b), would be impractical due to the higher sample complex- ity entailed by the deep learning approach that we adopt. Therefore, to mitigate this issue while keeping the computa- tional complexity under control, we update only the local components of the model over time, i.c., the learnable node embeddings V (Cini et al., 2023b). This allows for keeping most of the learnable parameters fixed and fine-tuning only small number of weights for each node. Empirically, we show that this procedure can effectively improve the quality of the uncertainty estimates.
4. Related Work
The problem of quantifying forecast uncertainty is central in fundamental and applied research in time series fore- casting (Hyndman and Athanasopoulos, 2018; Petropoulos et al., 2022). Among deep learning approaches (Benidis et al., 2022), many generative architectures have been pro- posed means to obtain probabilistic forecasts (Salinas et al., 2020; Rangapuram et al., 2018; de Bézenac et al., 2020; Rasul et al., 2021). Most related to our approach are those methods that exploit quantile regression (Wen et al., 2017: Gasthaus et al., 2019; Kan et al., 2022; Gouttes et al., 2021). Similarly to COREL, these quantile regression tech- niques do not usually require strong assumptions on the data distribution.
5. Experiments
We validate COREL across three experimental settings. In the first one (Sec. 5.1), we compare it against state-of-the-ar CP methods operating on the residuals produced by differ- ent forecasting models. Then, we analyze COREL in a controlled environment (synthetic dataset). Finally, we as- sess the effectiveness of the procedure described in Sec. 3.4 in adaptively improving the Pls. We implement COREL as an RNN followed by two message-passing layers. To approximate the quantile function, we train the model by minimizing the pinball loss over a discrete set of quantiles, similarly to Wen et al. (2017). PIs are constructed as in Eq. 14; App. G.2 shows results for the alternative construc- tion in Eq. 16. To learn the graph, we directly parametrize the score matrix & by associating learnable parameter with each of its entries. We use as metries: 1) the differ- ence between the specified confidence level 1 - a and the observed coverage on the test set (ACov), 2) the width of the PI (PI- (PI-Width), and 3) the Winkler score (Winkler, 1972). which is computed as the width of the PI plus penalty for each observation outside of the predicted interval propor- tional to the actual error (Winkler). Note that balancing
Uncertainty quantification in STGNNs Regarding prob- abilistic graph-based forecasting architecture, the existing literature is limited (Jin et al., 2023; Cini et al., 2023a). Wu et al. (2021) investigate the combination of STGNNs with standard uncertainty quantification techniques for deep learning. Pal et al. (2021) use an STGNN to implement a state-space model and quantify uncertainty within a Bayesian framework. Wen et al. (2023) propose probabilis- tic predictor based on combining STGNNs with a diffusion model (Ho et al., 2020). Zambon et al. (2023) introduce a framework for designing probabilistic graph state-space models that can process collections of time series. However, all these methods cannot operate top of an existing pre- trained model and require training an ad-hoc forecasting model. Conversely, COREL is trained, within a CP frame- work, on predicting the quantiles of the error distribution of any existing model, rather than on forecasting the target variable.
6

---

Relational Conformal Prediction for Correlated Time Series
Metric
SCP
NexCP
SeqCP
SPCI
HopCPT
CORNN
COREL
ACov
-1.28
-1.00
-6.93
-1 1.244001
-1.4610.1
-0,494053
-1.29
RNN
PI-Width
20.69
25.23
19.52
19.84
16.62+0.00
19.48
14.38
Winkler
40.80
41.33
50.12
37.95
25.63
30.2440.18
23.78
METR-LA
STGNN TRANSF
ACov
-1.18
-0.97
-6.98
4..0000000
-1.52
-0.55
-1.02.0..3
PI-Width
20.81
25.30
19.44
19.8
16.66+0.13
19.38
14.17#0043
Winkler
40.55
41.64
49.90
37.74
25.37
30.33
23.65:10.19
ΑCov
-0.99
-0.62
-13.6
+0.87
-0.13+t27
-0.34
-0.92
PI-Width
17.30
22.20
12.87
16.38
15.75
16.20+o24
14.65
Winkler
34.94
34.49
40.36
33.66+000
22.80 +
28. 28.74
24.70++0.6
ÂCov
-3,46
0.11
-3.57
+,00
-4.37
+2.24
-3.60
STGNN TRANSF RNN
PI-Width
2.60
3.26
2.75
2.39
1.97=003
1.96
1.83=0as
Winkler
5.69
5.48
5.79
5.29
3.87
4.01
3.71
ACov
-3.35
0.10
-3.53
3,266
-3.95
2.30
=3.97
CER
PI-Width
2.52
3.16
2.67
2.33
2.01
1. 1.94
1.80=002
Winkler
5.60
5.36
5.69
5,20
3.88
3.82
3.67=0.02
ACov
-4.30
0.08
-3.83
4.1 4.070001
-5.062015
-2.13108
=4.99
PI-Width
2.28
3.00
2.42
2.09
1.79=001
1.85
1.77=0005
Winkler
5.11
4.87
4.99
4.76
3.49=n02
3.72+no2
3.76=0.44
STGNN TRANSF RNN
ACov
5.09
-0.63
-3.21
1.79
0.01
-2.06
-2.7820.0
PI-Width
118.06
82.04
74.73
103.8820.0
90.35
71.61
13.13
Winkler
148.61
131.18
135.59
1.3.00.am
133.24
113.11 10.7
107.67
ACov
5.07
-0.66
-3.17
1.60
-2.34
-1.9320.4
11.81
AQI
PI-Width
118.50
81.15
75.08
104.
10.01
80.37
73.25
72.25
Winkler
150.33
132.08
137.62
145.14 14:00
129.85+314
1
108.71
ACov
4.48
-0.32
-2.94
2.64:1001
-0.78
-1.524051
-2.00
PI-Width
111.68
80.01
71.92
99.
79.39 43.38
70.17+030
68.24
Winkler
143.39
127.98
130.86
137.09
121.26:2248
109.65
108.45
Table 1: Performance comparison for 0.1. ACov values color-coded: green (0-2%), yellow (2-3%), orange (3-4%), red( (>4%). The lowest Winkler score for each scenario is shown in bold.
coverage and Pl width is the main challenge. More details and results are provided in the appendix.
decoder-only Transformer (Vaswani al., 2017), and simple TTS STGNN obtained by following the template in Sec. 2.4. The latter uses a pre-defined graph that models the dependencies across the time series. After training, we evaluate each baseline on the calibration set and save the associated residuals, which are then used input to the different CP methods. More details on the datasets and base models are provided in App. C.
5.1. Time Series Forecasting Benchmarks
We consider the following datasets, each coming from dif- ferent application domain: METR-LA from the traffic fore- casting literature (Li et al., 2018); a collection of air quality measurements from different Chinese cities (AQI) (Zheng et al., 2015); a collection of energy consumption profiles acquired from smart meters within the CER smart meter- ing project (CER-E) (Commission for Energy Regulation, 2016; Cini et al., 2022). We follow the preprocessing steps of previous works (Li et al., 2018; Wu et al., 2019; Cini et al., 2023b) and adopt 40% 40//40%%%%% splits for train- ing, calibration, and testing, respectively. For each dataset, we first train 3 different baseline models: simple RNN with gated recurrent unit (GRU) cells (Cho al., 2014), a
Baselines We compared COREL against the following basclines: 1) SCP, the standard split CP; 2) SeqCP, where,
analogously Xu and Xie (2023a), we compute empirical quantiles using only the most recent K residuals at each time step; 3) NexCP (Barber et al., 2023), which computes empir- ical quantiles by assigning exponentially decaying weights to past residuals; 4) SPCI (Xu and Xie, 2023b), which esti- mates the residuals' quantile function from the last few steps of each time series with a random forest; 5) HPP which

---

Relational Conformal Prediction for Correlated Time Series
reweights past residuals by learning attention scores with Modern Hopfield Network (Ramsauer et al., 2021). These baselines are representative of the current state-of-the-art in CP for time series forecasting; in particular, SPCI (based on quantile regression) and HopCPT (based on reweighting) are representative of the main recent paradigms. Note that a comparison with non-post-hoe methods would be problem- atic, as results heavily depend on the base predictors being used. We also include in our comparison model called CORNN, where we use the same architecture as COREL but remove message-passia passing layers and node embeddings. CORNN is an ablation of the introduced designs. Except for HopCPT, which uses a custom procedure (Auer et al., 2023), model selection is performed on a validation set by optimizing the Winkler score.
Table 2: Performance on GPVAR.
GPVAR-RNN
Models
ACov PI-Width Winkler ACov PI-Width Winkler
SCP
-0.02
1.67
2.14
-0.02
1.32
1.66
CORNN
0..1
1.63 2.04 0.0+a0
1.32-0.00
1.66=0.0
COREL
0.0
1.33+000
1.67
0.1
1.32
1.66
w/ true A -0.1 1.32
1.662000
0.0
1.32_am1 1.66=am0
from the auto-regressive polynomial graph filter:
L Q H:
θ 1 1-1
X2-97
1=1 q=1
Results Tab. I reports the results across the datasets and the base prediction models. The first observation is that COREL outperforms the competitors in terms of Winkler score in almost all cases. We observed few exceptions only when the baseline is itself an STGNN, as it is already expected to take care of modeling spatiotemporal dependen- cies. However, note that the STGNN base model has access to pre-defined graph, which is not always available in prac- tical applications. In terms of coverage, COREL achieves good results, with the exception of some cases in the CER-E dataset. However, we note that our model selection pri- oritized the Winkler score which emphasizes the width of the prediction bands besides the coverage. CORNN, the simplified version of our approach, obtains good overall performance and is competitive against the state-of-the-art but, despite providing good coverage, it is outperformed by CoREL in most scenarios in terms of Winkler score. Among the competitors, HopCPT provides competitive results in METR-LA and CER-E but with a larger coverage gap. Ex- cept for SPqCP, the other baselines obtain good coverage in most settings at the expense of drastically wider Pls. Re- garding computational scalability, note that COREL shares most of the learnable parameters among time series and that its training can be efficiently parallelized on a GPU. Further- more besides learnable node embeddings V. COREL relics only on a short window of the most recent observations as an input at each time step. Conversely, SPCI requires training different model for each time series, and HopCPT requires computing attention scores w.r.t. the entire calibration set at each time step.
X1+1 a o tanh (H₂) + o tanh (X,-1) + 7/1 (19)
where parameters O E RQXL, a E E. be E R are kept fixed across nodes and Te o20 with = 0.4. We ran the simulation on a graph with 60 nodes and with a topol- ogy analogous to previous works (Cini et al., 2023b); more details are provided in App. C. We use both a RNN and STGNN as base point predictors. As shown by Zambon and Alippi (2022), STGNNs can obtain forecasting accuracy near the theoretical optimum in this dataset, which results in uncorrelated residuals. As such, we would expect stan- dard SCP to be sufficient when using an STGNN as base model. The objective of this experiment is to show that COREL is effectively able to capture and leverage existing spatiotemporal dependencies.
Results We compare COREL against standard SCP and the CORNN variant. Moreover, we also compare perfor- mance against COREL with access to the true graph used to generate the data. Results are shown in Tab. 2. When using an RNN as a point predictor (GPVAR-RNY) COREL significaanly outperforms both standard SCP and CORNN. Furthermore, COREI achieves results that closely match those obtained with direct access to the ground truth graph, which shows the effectiveness of the proposed architecture in capturing latent relational dependencies. Note that, given the injected Gaussian noise with a = 0.4, the theoretical optimum PI width to obtain (asymptotically) 90% marginal coverage is 1.315. COREL achieves essentially perfect cov- erage with PI width close to the theoretical optimum, while CORNN requires substantially higher PI width to ob- tain similar iiilarr coverage. Finally, results obtained by using an STGNN as bascline (GPVAR-STGNN) show (as expected) that the standard SCP is sufficient when the point-predictts captures all the relevant dependencies. We provide a visual- ization of the learned graph in App. G.I.
5.2. Controlled Environment
We evaluated the behavior of COREL in controlled envi- ronment by simulating a diffusion process on a graph. In particular, the experiment relied on the GPVAR benchmark introduced by Zambon and Alippi (2022), with a setup analo- gous to (Cini et al., 2023b). Data were generated recursively
8

---

Relational Conformal Prediction for Correlated Time Series
Table 3: Adaptation results for CER-E for a reference COREL model. (a = 0.1).
RNN
Transformer
STGNN
ACov
PI-Width
Winkler
ACov
PI-Width
Winkler
ΑCov
PI-Width
Winkler
W/o adapt.
-3.44 0:40
1.84 i ooz
3.71 003
-3.08 2015
1.84 + t00
3.69 1 0.0
-4.07 0
1.80 000
3.78 + 0.0
W/ adapt.
-2.70 0.27
1.85 + oot
3.49 0.2
-2.42 +.20
1.85 + oo1
3.49 + eU4
-3,06 + 0.22
1.81 + 0.0
3.58 + 0.02
5.3. Adaptation
correlated time series, it provides separate Pls for each time series. It would then be interesting to extend the framework with components that model the joint probability distribu- tion of the time series.
In this experiment, evaluate how effectively the adapta- tion technique proposed in Sec. 3.4 provides accurate Pls over time. We focused on the CER-E dataset where the calibration set does not cover a full year, which likely in- troduces a shift at test time given the seasonality of energy consumption. We used COREL with a fixed hyperparameter configuration across scenarios and trained on the calibration set. Embeddings are updated every M time steps by run- ning the training procedure the latest observations and keeping all the parameters frozen except for the embeddings. More details on the hyperparameters are provided in App. B. In practice. this is done by splitting the test set into K = 6 folds and then iteratively fine-tuning the model on each fold. This procedure simulates a real-world scenario where new data become available over time and are used for fine-tuning. Results, reported in Tab. 3, show that this adaptation scheme improves performance by reducing the coverage gap and providing more accurate Pls.
Impact Statement
This paper presents work whose goal is to advance the field of machine learning and time series forecasting. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
A Acknowledgments
This work was supported by the Swiss National Science Foundation grant no. 225351 (Relational Deep Learn- ing for Reliable Time Series Forecasting at Scale) and no. 204061 (HORD GNN: Higher-Order Relations and Dy- namics in Graph Neural Networks), the Hasler Stiftung project Calibrated Uncertainty Estimation for Spatio- Temporal Data, the UKRI CDT Al for Healthcare (grant no. P/S023283/1). and the Norwegian Research Council grant no. 345017 (RELAY: Relational Deep Learning for Energy Analytics). FMB wishes to thank Nvidia Corpora- tion for donating some of the GPUs used in this project. AC conducted part of this work while at the University of Oxford.
6. Conclusion
In this paper, we introduced Conformal Relational Predic- tion (COREL), novel CP method for correlated time series. CoREL exploits graph-based neural operators to implement an uncertainty quantification architecture that can operate on top of any pre-trained point predictor. Furthermore, our ap- proach does not require the relational structure to be known in advance. Results show that the proposed method com- pares favorably against the vant scenarios.
References
in several rele-
Anastasios N Angelopoulos, Stephen Bates, al. Confor- mal prediction: A gentle introduction. Foundations and Trends@ in Machine Learning, 16(4):494-591, 2023.
Limitations and future work We believe that COREL constitutes an important step toward effective spatiotempo- ral CP methods. There are several directions for future work to explore, such as applying the framework to heteroge- neous time series. Future work should focus on mitigating challenges arising from learning in non-stationary environ- ments, e.g., by developing methods and coverage guaran- tees under specific assumptions about the non-stationarity of the data- data-generating process. Applications of COREL to very large time series collections and combinations thereof with scalable graph- braph architectures (Chiang et al., 2019; Cini et al., 2023c) are an additional direction. Finally, while CO accounts for dependencies w.r.t. past observations at
Anastasios N Angelopoulos, Rina Foygel Barber, and Stephen Bates. Theoretical foundations of conformal prediction. arXiv preprint arXiv:2411.11824 2024.
Andreas Auer, Martin Gauch, Daniel Klotz, and Sepp Hochreiter. Conformal prediction for time series with Modern Hopfield Networks. Advances in neural informa- tion processing systems, 2023.
Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs. Neural Networks, 129:203-222 2020.

---

Relational Conformal Prediction for Correlated Time Series
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, 1662))816-845, 2023.
Jase Clarkson. classification. In International Conference Machine Learning, pages 6268-6278. PMLR, 2023.
Distribution free prediction for node
Commission for Energy Regulation. Metering Project Electricity Customer Be- haviour Trial, 2009-2010 [dataset]. Irish So- cial Science Data Archive. SN: 00/2-00, 2016. URL
CER Smart
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint 1rXiv:130..343. 2013.
https:://ww.uud..ie. commlassiooforreneerrgrggaaaaaao
data/
Konstantinos Benidis, Syama Sundar Rangapuram, Valentin Flunkert, Yuyang Wang, Danielle Maddix, Caner Turk- men, Jan Gasthaus, Michael Bohlke-Schneider, David Salinas, Lorenzo Stella, François-Xavier Aubet, Lau- rent Callot, and Tim Januschowski. Deep Learning for Time Series Forecasting: Tutorial and Literature Survey. ACM Comput. Surv, 55(6), dee 2022. ISSN 0360-0300. doi: 10.1 10.1145/3533382. URLhttps: https:ttp///..c... /ttp::::////oo.../////// 1145/3533382.
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional re- inforcement learning. In International conference machine learning, pages 1096-1105. PMLR, 2018.
Ed Davis, Ian Gallagher, Daniel John Lawson, and Patrick Rubin-Delanchy Valid conformal prediction for dynamic GNNs. arXiv preprint arXiv:2405. /9230, 2024.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint 1344:22004.1348,, 2021.
Emmanuel de Bézenac, Syama Sundar Rangapuram, Kon- stantinos Benidis, Michael Kurle, Lorenzo Stella, Hilaf Hasson, Patrick Gallinari, and Tim Januschowski. Normalizing kalman filters for multivariate time series analysis. Advances in Neural Information Processing Systems, 33:2995-3007, 2020.
Richard
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Ben- gio, and Cho-Jui Hsieh. Cluster-GCN: An efficient al- gorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD in- ternational conference on knowledge discovery & data mining, pages 257-266, 2019.
William Falcon and The PyTorch Lightnnng team. PyTorch Lightning, 3 2019. URL https://github. com/ Sy/oorchhiggtttiing//pttore..t lighttin....
Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties neural machine translation: Encoder-decoder approaches. arXiv preprint 1409. 2014.
Shai Feldman, Stephen Bates, and Yaniv Romano. Cali- brated multiple-output quantile regression with represen- tation learning. Journal of Machine Learning Research, 24(24):1-48, 2023.
Andrea Cini and Ivan Marisca. Torch Spatiotem- poral, 2022. URL https://githan com/
Matthias Fey and Jan Eric Lenssen. Fast graph represen- tation learning with PyTorch Geometric. arXiv preprint 19X3v:1903.02400 2019.
wwrchSpptictempoonn
Andrea Cini, Ivan Marisca, and Cesare Alippi. Filling the G ap s: Multivariate Time Series Imputation by Graph Neural Networks. In International Conference on Learn- ing Representations, 2022.
Jianfei Gao and Bruno Ribeiro. On the Equivalence Between Temporal and Static Equivariant Graph Representations. International Conference on Machine Learning, pages 7052-7076. PMLR, 2022.
Andrea Cini, Ivan Marisca, Daniele Zambon, and Cesare Alippi. Graph Deep Learning for Time Series Forecasting. arXiv preprint (tt::2331.19977. 2023a.
Alberto Gasparin, Slobodan Lukovic, and Cesare Alippi. Deep learning for time series forecasting: The electric load case. CAAI Transactions on Intelligence Technology, 7(1): 2022.
Andrea Cini, Ivan Marisca, Daniele Zambon, and Cesare Alippi. Taming Local Effects in Graph-based Spatiotem- poral Forecasting. Advances in Neural Information Pro- cessing Systems, 2023b.
Jan Gasthaus, Konstantinos Benidis, Yuyang Wang, Syama Sundar Rangapuram, David Salinas, Valentin Flunkert, and Tim Januschowski. Probabilistic forecast- ing with spline quantile function RNNs. In The 22nd international conference on artificial intelligence and statistics, pages 1901-1910. PMLR, 2019.
Andrea Cini, Daniele Zambon, and Cesare Alippi. Sparse graph learning from spatiotemporal time series. Journal of Machine Learning Research, 24(242): 2023c.
10

---

Relational Conformal Prediction for Correlated Time Series
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34:1660-1672, 2021.
Anees Kazi, Luca Cosmo, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein. Differentiable graph mod- ule (dgm) for graph convolutional networks. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272. PMLR, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 3nd International Conference on Learning Representations, ICLR 2015, 2015.
Adèle Gouttes, Kashif Rasul, Mateusz Koren, Johannes Stephan, and Tofigh Naghibi. Probabilistic time se- ries forecasting with implicit quantile networks. arXiv preprint arXiv:2107.03744: 2021.
Roger Koenker and Kevin F Hallock. Quantile regression. Journal of economic perspectives, 15(4):143-156 2001.
Wouter Kool, Herke Van Hoof, and Max Welling. Stochas- tic beams and where to find them: The Gumbel-top-K trick for sampling sequences without replacement. In International Conference on Machine Learning pages 3499-3508. PMLR, 2019.
Clive WJ Granger. Investigating causal relations by econo- metric models and cross-spectral methods. Econometrica: journal of the Econometric Society, pages 424-438, 1969.
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 J Smith, et al. Array programming with NumPy. Nature, 585 (7825):357-36,, 2020.
Jonghyeok Lee, Chen Xu, and Yao Xie. Kernel-based op- timally weighted conformal time-series prediction. In The Thirteenth International Conference on Learning Representations, 2025. URL htt.s:: /ttpss//ooeeevieeeeee net
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffu- sion probabilistic models. Advances neural information processing systems, 33:6840-6851, 2020.
Junghwan Lee, Chen Xu, and Yao Xie. Conformal pre- diction for time series with transformer. In ICML 2024 Workshop on Structured Probabilistic Inference & Gener- ative Modeling, 2024. URL https: /oppnrevie..eeeeeeeeeeeee net / forum? Pid 3dDDaaSrye..
Kexin Huang. Ying Jin, Emmanuel Candes, and Jure Leskovec. Uncertainty quantification over graph with conformalized graph neural networks. Advances in Neu- ral Information Processing Systems, 36, 2024.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Dif- fusion Convolutional Recurrent Neural Network: Data- Driven Traffic Forecasting, In International Conference Learning Representations, 2018
Rob Hyndman and George Athanasopoulos. Forecasting: principles and practice. OTexts, 2018
Yuxuan Liang, Haomin Wen, Yuqi Nic, Yushan Jiang, Ming Jin, Dongjin Song, Shirui Pan, and Qingsong Wen. Foun- dation models for time series analysis: A tutorial and survey. arXiv preprint arXiv:2403.14735. 2024.
Vilde Jensen, Filippo Maria Bianchi, and Stian Normann Anfinsen. Ensemble conformalized quantile regression for probabilistic time series forecasting. IEEE Transac- tions on Neural Networks and Learning Systems, 2022.
Spyros Makridakis. Forecasting: its role and value for plan- ning and strategy. International journal of forecasting. 12(4):513-337 1996.
Hanyang Jiang, Yao Xie, and Feng Qiu. Spatio-temporal conformal prediction for power outage data. arXiv preprint arXiv:2411.17099 2024.
Spyros Makridakis, Richard Kirkham, Ann Wake- field, Maria Papadaki. Joanne Kirkham, and Lisa Long. Forecasting, uncertainty and risk; per- spectives clinical decision-making in preventive and curative medicine. International Journal of Forecasting, 35(2):659-666, 2019. ISSN 0169- 2070. doi: http://boiaogg0o.00////jooaoazaa 003. htRLhcpps//w...ceeeeedeeeee com/
Ming Jin, Huan Yee Koh, Qingsong Wen, Daniele Zam- bon, Cesare Alippi, Geoffrey I Webb, Irwin King, and Shirui Pan. A Survey on Graph Neural Networks for Time Series: Forecasting. Classification, Imputation, and Anomaly Detection. arXiv preprint arXiv:2307.03759 2023.
Kelvin Kan, François-Xavier Aubet, Tim Januschowski, Youngsuk Park, Konstantinos Benidis, Lars Ruthotto, and Jan Gasthaus. Multivariate quantile function forecaster. In International Conference on Artificial Intelligence and Statistics, pages 10603-10621. PMLR, 2022.
science/artion ccceeee//rrtadee/////////2220000
Alessandro Manenti, Daniele Zambon, and Cesare Alippi. Learning Latent Graph Structures and their Uncertainty. arXiv preprint arXiv:2405. 19933, 2024.

---

Relational Conformal Prediction for Correlated Time Series
Huiying Mao, Ryan Martin, and Brian J Reich. Valid model- free spatial prediction. Jourmal of the American Statistical Association, 119(446)904-914 2024.
Manuela Pedio, Diego J. Pedregal, Pierre Pinson, Patrícia Ramos, David E. Rapach, J. James Reade, Bahman Rostami-Tabar, Michal Rubaszek, Georgios Sermpinis, Han Lin Shang, Evangelos Spiliotis, Aris A. Syntetos, Priyanga Dilini Talagala, Thiyanga S. Talagala, Len Tash- man, Dimitrios Thomakos, Thordis Thorarinsdottir, Ezio Todini, Juan Ramón Trapero Arenas, Xiaoqian Wang, Robert L. Winkler, Alisa Yusupova, and Florian Ziel. Forecasting: theory and practice. International Journal of Forecasting, 38(3):705-871, 2022. ISSN 0169-2070. doi:
Nicolai Meinshausen and Greg Ridgeway. Quantile regres- sion forests. Journal of machine learning research, 7(6), 2006.
Vlad Niculae, Caio F Corro, Nikita Nangia, Tsvetomila Mi- haylova, and André FT Martins. Discrete latent structure in neural networks. arXiv preprint arXiv:2301.07473, 2023.
1.001.
Georg Ostrovski, Will Dabney, and Rémi Munos. Autore- gressive quantile networks for generative modeling. In International Conference Machine Learning, pages 3936-3945. PMLR, 2018
Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Lukas Gruber, Markus Holzleitner, Thomas Adler, David Kreil, Michael K Kopp. Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. Hopfield networks is all you need. In International Conference on Learning Representations, 2021. URL https: http:///ppeeeeeeeeeeeeeeeeeeeeee net forum? id=t189Rn2Iicd.
Soumyasundar Pal, Liheng Ma, Yingxue Zhang, and Mark Coates. RNN with Particle Flow for Probabilistic Spatio- temporal Forecasting. In Proceedings of the 38th Inter- national Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8336-8348 PMLR, 18-24 24-2411 Jul 2021.
Syama Sundar Rangapuram, Matthias W Seeger, Jan Gasthaus, Lorenzo Stella, Yuyang Wang, and Tim Januschowski. Deep state space models for time series forecasting. Advances in Neural Information Processing Systems, 31:7785-7794, 2018
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zem- ing Lin, Natalia Gimelshein, Luca Antiga, Alban Des- maison, Andreas Kopf, Edward Yang, Zachary De Vetito Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chin- tala. PyTorch: An Imperative Style, High- Perforrero Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Sys- tems 32, pages 8024-8035. Curran Associates, Inc., 2019.
Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf. Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting. In Inter- national Conference on Machine Learning, pages 8857- 8868. PMLR, 2021.
David Salinas, Valentin Flunkert, Jan Gasthaus, and Tim Januschowski. DeepAR: Probabilistic forecasting with autoregressive recurrent networks. International Journal of Forecasting, 36(3):1181-11)) 2020.
Fotios Petropoulos, Daniele Apiletti, Vassilios Assi- makopoulos, Mohamed Zied Babai, Devon K. Barrow, Souhaib Ben Taieb, Christoph Bergmeir, Ricardo Bessa, Jakub Bijak, John E. Boylan, Jethro Browell, Claudio Carnevale, Jennifer L. Castle, Pasquale Cirillo, Michael Clements, Clara Cordeiro, Fernando Luiz Cyrino Oliveira, Shari De Bacts, Alexander Dokumentov, Joanne Ellison, Piotr Fiszeder, Philip Hans Franses, David T. Frazier, Michael Gilliland, M. Sinan Gönül, Paul Goodwin, Luigi Grossi, Yael Grushka-Cockayne, Mariangela Guidolin, Massimo Guidolin, Ulrich Gunter, Xiaojia Guo, Renato Guseo, Nigel Harvey, David F. Hendry, Ross Hollyman, Tim Januschowski, Jooyoung Jeon, Victor Richmond R. Jose, Yanfei Kang, Anne B. Koehler, Stephan Kolassa, Nikolaos Kourentzes, Sonia Leva, Feng Li, Konstantia Litsiou, Spyros Makridakis, Gael M. Martin, Andrew B. Martinez, Sheik Meeran, Theodore Modis, Konstantinos Nikolopoulos, Dilck Önkal, Alessia Paccagnini, Anas- tasios Panagiotelis, loannis Panapakidis, Jose M. Pavía,
Victor Garcia Satorras, Syama Sundar Rangapuram, and Tim Januschowski. Multivariate time series fore- casting with latent graph inference. arXiv preprint arXhv:2203.03423,,, 2022.
David I 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 networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013.
Ralph Smith. Uncertainty quantification: theory, imple- mentation, and applications. SIAM, 2024.
Slawek Smyl. A hybrid method of exponential smoothing and recurrent neural networks for time series forecasting. International Journal of Forecasting, 36(1):75-855 2020.
12

---

Relational Conformal Prediction for Correlated Time Series
Kamile Stankeviciute, Ahmed M Alaa, and Mihaela van der Schaar. Conformal time-series forecasting. Advances in neural information processing systems, 34:6216-6228, 2021.
Sang Michael Xie and Stefano Ermon. Reparameterizable subset sampling via continuous relaxations. In Proceed- ings of the 28th International Joint Conference on Artifi- cial Intelligence, pages 3919-3925, 2019.
Sophia Huiwen Sun and Rose Yu. Copula conformal predic- tion for multi-step time series prediction. In The Twelfth International Conference on Learning Representations, 2024.
Chen Xu and Yao Xie. Conformal prediction for time se- ries. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(10)) 2023a.
Chen Xu and Yao Xie. Sequential predictive conformal inference for time series. In International Conference on Machine Learning, pages 38707-38727. PMLR, 2023b.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under co- variate shift, Advances in neural information processing systems, 32, 2019.
Chen Xu, Hanyang Jiang, and Yao Xie. Conformal predic- tion for multi-dimensional time series by ellipsoidal sets. arXiv preprint arXiv:2403..0 038500000000..0 2024.
Guido Van Rossum and Fred L. Drake. Python 3 Reference Manual. CracteSpace, Scotts Valley, CA, 2009. ISBN 1441412697.
Daniele Zambon and Cesare Alippi. AZ-whiteness Test: A Graphs.
Test for Signal Uncorrelation on Advances in Neural Information Processing Systems, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszko- reit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances in Neural Information Processing Systems, pages 5998- 6008, 2017.
Daniele Zambon and Cesare Alippi. Where and How to Improve Graph-based Spatio-temporal Predictors, 2023. URL http: /ttpiv.xiivvv.///a org/ ab3/2302.../2a/ 2302. 01701.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005.
Daniele Zambon, Andrea Cini, Lorenzo Livi, and Ce- sare Alippi. Graph state-space models. arXiv preprint arXiv2300..1741, 2023.
Haomin Wen, Youfang Lin, Yutong Xia, Huaiyu Wan, Qingsong Wen, Roger Zimmermann, and Yuxuan Liang DifISTG: Probabilistic spatio-temporal graph forecast- ing with denoising diffusion models. In Proceedings of the 31st ACM International Conference on Advances in Geographic Information Systems, pages 1-12, 2023.
Soroush H Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neu- ral networks. In International Conference on Machine Learning, pages 12292-12318, PMLR, 2023.
Tianyi Zhao, Jian Kang, and Lu Cheng. Conformalized link prediction on graph neural networks. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4490-4499, 2024.
Ruofeng Wen, Kari Torkkola, Balakrishnan Narayanaswamy, and Dhruv Madeka. A multi- horizon quantile recurrent forecaster. arXiv preprint arXiv:1711.11053, 2017.
Yu Zheng, Xiuwen Yi, Ming Li, Ruiyuan Li, Zhangqing Shan, Eric Chang, and Tianrui Li. Forecasting fine- grained air quality based on big data. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 2267 2267-2276, 2015.
Robert L Winkler. decision-theoretie approach to interval estimation. Journal of the American Statistical Associa- tion, 67(337):187-111, 1972.
Dongxia Wu, Liyao Gao, Matteo Chinazzi, Xinyue Xiong, Alessandro Vespignani, Yi-An Ma, and Rose Yu. Quanti- fying uncertainty in deep spatiotemporal forecasting. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, pages 1841-1851, 2021.
Zonghan WU, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial-temporal graph modeling. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 1907- 1913, 2019.
13

---

Relational Conformal Prediction for Correlated Time Series
Appendix
A. Proof of Prop. 3.1
As stated in Prop. 3.1, let Pi+ and p indicate the probability distributions associated with the true data distribution ++ H and with the learned quantile function 2x. respectively. It follows from the definition of total variation distance
(V(P,Q) == sups P(B) (()),, that for any event B
P4+ (B) (B) & TV P P(+H) P (B)
(20)
(B) 2 ( (V P(+H).
(21)
For Čo in both Eq. 14 and Eq. 16 we have by construction that
p (mitH E C2,,1 =1 a
(22)
Then, putting together Eq. and Eq. 22 we obtain
Pit (0itH E C ((t(X))t)) 2 21 a- TV (P PiHH)
Hence, the proof is complete.
B. Hardware and software platforms
Benchmarks have been developed with Python (Van Rossum and Drake, 2009) and the following open-source libraries:
Numpy (Harris et al., 2020);
PyTorch (Paszke et al., 2019);
PyTorch Lightning (Falcon and The PyTorch Lightning team, 2019);
PyTorch Geometric (Fey and Lenssen, 2019);
Torch Spatiotemporal (Cini and Marisca, 2022).
Experiments were conducted server equipped with AMD EPYC 7513 CPUs and NVIDIA RTX A5000 GPUs. The code For the
for reproducing the computational experiments is available at ht https::// h/github.b../. com/ cenddreacnni/cooo
HopCPT, SPCI, NexCP, and SeqCP baselines we use the open-source implementation made available by Auer et al. (2023)². In our setup for the experiment in Sec. 5.1, considering the METR-LA dataset and the baselines that require fitting a model, training and testing require days for SPCI, hours for HopCPT, and 5 minutes for COREI.
C. Datasets
We considered several datasets from different application domains, real-world scenarios and a simulated controlled environment. For the real world datasets we followed the pre-processing steps adopted by Cini et al. (2023b).
Air Quality Monitoring The AQI (Zheng al., 2015) dataset consists of 8,760 hourly measurements of pollutant PM2.5 from 437 monitoring stations in China. We use window of W 24 time steps and predict the 3-time-step-ahese observations. For the STGNN base model, we build an adjacency matrix using a thresholded Gaussian kernel computed from pairwise geographic distances (Shuman et al., 2013).
Traffic Forecasting We considered the METR-LA (Li et al., 2018) traffic forecasting dataset, consisting of 34,272 timesteps measurements from 207 loop detectors sampled 5-minute intervals the Los Angeles County Highways. We window of 12 time steps and predict the 12 12-time-stepe 12-time-step-ahead observations. For the STGNN base model, followed previous works (Wu et al., 2019) and built an adjacency matrix using thresholded Gaussian kernel applied to geographic distances.
hhttps://gtt thub. cwm/m1l malljjkk/HopCPP
14

---

Relational Conformal Prediction for Correlated Time Series
Electric Load Forecasting We selected the CER-E dataset (Commission for Energy Regulation, 2016; Cini et al., 2022), comprising 25,728 timesteps of energy consumption readings aggregated at 30-minute intervals from 485 smart meters monitoring small and medium-sized enterprises. We use window of 48 time steps and predict the 5-time-step-ahead observations. For the STGNN base model, we built the adjacency matrix by extracting 10-nearest neighbor graph from week-wise correntropy similarities between time series, following previous work (Cini et al., 2022).
GPVAR For the GPVAR dataset, we generate synthetic data with 40,000 timesteps over an undirected network of 60 nodes connected community graph structure by following the system model Eq. (Zambon and Alippi, 2022). The parameters of the spatiotemporal process are set
2.5
-2.
-0.5
θ =
a= a=b= 0.5,
o = 0.4.
(23)
1.0
3.0
0.0
We used an input window of time steps to predict the next observation. For the STGNN base model, we used the same community graph structure as the adjacency matrix.
Base models We trained three base models (point predictors) for each dataset: a RNN with GRU cells (1 layer with hidden size 32). a decoder-only Transformer (hidden size 32, feed-forward size 64, 2 attention heads, 3 layers, dropout 0.1), and STGNN following the template in Sec. 2.4 (hidden size 32, node embedding size 16, layer GRU, 2 message-passing layers). All models were trained by minimizing the MAE loss using the Adam optimizer for 200 epochs with batch size 32, using 40% of the data for training. 40% for calibration, and 20% for testing. We also use the first 25% of the calibration data as validation set for early stopping. Input features were scaled using standard scaling across time series.
D. Additional details on COREL implementation
Architecture As discussed in Sec. 3 and Sec. 5, we implemented COREL as TTS model with a single-layer GRU followed by 2 message passing layers analogous to those in (Satorras et al., 2022). As readout, we used an MLP mapping the learned representations to predictions of 39 equally spaced quantiles. For the CORNN baseline, we used the same architecture but removed the message passing layers and node embeddings V and allowed the GRU have more than one layer.
Latent graph learning module The graph learning module was implemented described in See. 3.2 by parametrizing with matrix of N x N learnable parameters. To allow for sampling less neighbors than the specified neighborhood size K, we followed previous works (Cini et al., 2023c) and modified the sampling procedure by introducing set of dummy nodes then discarded from the sampled graph before message passing. We use dummy nodes in the GPVAR experiment only. To allow for sparse message-passing operations we use a straight-through gradient estimator (Bengio et al., 2013) and backpropagate gradients only through the sampled edges for each node, plus 10% of the remaining ones. In the GPVAR experiment, we simply propagate gradients w.r.t. the entire adjacency matrix.
Covariates Besides residuals, we use as additional covariates datetime encodings whenever available, plus the value of the target time series w.r.t. the time steps in the input window.
E. Evaluation metrics
1,2,0 22 + a. -0/2 For a prediction interval Ō = [&, + 12 level using three key metrics.
1 and true value xt, evaluation conducted for a desired confidence
Coverage gap by
ACov, measures the difference between the achieved coverage and the target coverage 1 a, and is given
ACov, 100 (1(z; E C. (1 (1-a)).
(24)
where 1 denotes the indicator function.
Prediction interval width
Quantifies the width of the prediction intervals, and is given by
PI- PI-Width; q 1l-a/2
4i /2
(25)
15

---

Relational Conformal Prediction for Correlated Time Series
Winkler Score Combines interval width with a penalty for predictions that fail capture the true value, with misses penalized by factor of 2. The Winkler score is given by
1 1-a/2
41 /0/2) + 2 (0;
g0/22
- -x;)
if xj < ca/2
W
(1 a/22 - 91 )/
if q /222 S 4z S 9
1-a/2
(26)
(a.
al q: )
+ 2 (x;
///3
x; > q;
1-a/2
All the metries are then averaged over all nodes and time steps within the specified set.
F. Hyperparameters and experimental setup
Hyperparameters were tuned separately for each combination of base predictor and dataset on a validation set.
COREL For COREL we tuned the number of neurons in the STGNN with small grid search on 10% of the calibration data. We used the same model selection procedure for CORNN but also tuned the number of GRU layers. For the experiments on real-world data, the model was trained for a maximum of 100 epochs on the calibration set. Each epoch consisted of a maximum of 50 mini-batches of size 64. We used the Adam optimizer (Kingma and Ba, 2015) with an initial learning rate of 0.003 and reduced by 75% every 20 epochs. We used a fixed number of K = 20 neighbors for the graph learning module. For the GPVAR experiment in Sec. 5.2, we fixed the number of neurons to for each layer and used an embedding size of 8. For the adaptation experiment in Sec. 5.3, we use a reference configuration with 64 neurons in each encoder/decoder layers and embedding size of 32. We train the entire model on the full calibration set and use adaptation at test time. In particular, at test time, we fine-tune the node embeddings every M time steps, where M corresponds to of the test set length. For fine-tuning, we fit the embeddings by running 25 epochs of maximum 10 batches each by using samples from the last M steps with fixed learning rate of 0.001.
HPpCPT For HopCPT we followed the model selection procudere described in (Auer et al., 2023). The model was trained for 3000 epochs using batch size of 4 time series. We adopted the paper's AdamW optimizer configuration with standard parameters (81 0.9, 32 0.999, 0.01) and tuned the model by running the same hyperparameter configurations searched by (Auer et al., 2023). All the remaining hyperparameters were set accordingly the original paper.
SeqCP SeqCP, similarly to (Xu and Xie, 2023a), employs a sliding window approach to conformal prediction, assigning equal weights to observations within the most recent K time steps and zero weights to older observations. The window size K was treated as a hyperparameter and tuned over the values {200, 150, 125, 100, 75, 50, 25, 10).
CexCP NexCP implements conformal prediction using exponentially decaying weights controlled by a parameter p. Rather than using a fixed window of historical observations, it assigns weights that decay exponentially with time, giving more recent observations higher importance. The decay parameter p was tuned over the values (0.999, 0.995, 0.993, 0.99, 0.98, 0.95, 0.9}.
As already mentioned, we used the SPCI (Xu and Xie, 2023b) implementation provided by Auer et al. (2023) and followed an analogous protocol for training the mode. In particular, SPCI was run using fixed window length of 100 time steps for all experiments, corresponding to the longest setting in the original paper. The computational demands of SPCI were substantial, as separate quantile random forests had to be trained for each combination of node and target coverage level, making extensive hyperparameter tuning impractical. To further manage the computational costs, we trained each SPCI model only once on the calibration data, rather than implementing the time-adaptive approach where models are re-trained as new observations become available.
SPCI
G. Additional results
G.I. Qualitative analysis of the learned graph on GPVAR
Fig. 2 provides comparison of the graph learned on GPVAR by COREL in See. 5.2. In particular, the rightmost figure obtained by taking the top-K scores associated each row2. The figure shows that the learned graph includes true edges
"The figure does not show edge scores associated dummy nodes; see App. D
16

---

Relational Conformal Prediction for Correlated Time Series
(a) True adjacency matrix
(b) Learned adjacency matrix
Figure 2: Comparison between (a) the true graph and (b) the graph structure learned by COREL in GPVAR.
plus additional links. Note that perfectly recovering the ground truth graph required to achieve optimal performance here.
G.2. Optimization of the Pl width
Here, we show how the width of the PI can be reduced by searching for an appropriate quantile offset Specifically, we perform the optimization described in Eq. 16, which identifies pairs of quantiles yielding the same coverage while achieving the smallest interval width. We summarize results in Tab. 4. As we can the procedure consistently finds intervals with smaller width at the price of slightly reducing the coverage, whether using COREL or the CORNN variant.
Table 4: Changes in A Cov and PI- Width when optimizing 3 (a 0.1).
RNN
Transformer
STGNN
ACov
PI-Width
ACov
PI-Width
ACov
PI-Width
METR-LA
CoRNN 3 optim.
-0.70 0.20
19.69 2:07
-0.52
0.56
19.07
-0.67 1
16.02
-0.80 + 0.28
17.71 +.2
-0.96
0.35
17.16
0.46
-0.88 +0.44
14.98
0.17
COREL 3 optim.
-1.25 +: 0.80
14.24 0.5.3
-0.97
+ 0.51
14.43
1 0.38
-1.31
1.0.8
14.36
1: 0.20
-1.49 + 0.56
13.23 0.46
-1.26
0.42
13.47
0.35
-1.44
4.0.5
13.46 0.20
CER-E
CORNN
-2.09 0.56
1.93 1000
-1.70
0.37
1.99
-2.45
4:441
1.85
3 optim.
-2.63 + 0.65
1.82
-2.28
0.31
1.88
0.02
-3.10 4.022
1.78 0.00
COREL
-3.86 = 0.53
1.83 1000
-3.81
+ 0.50
1.83
= 0.02
-4.87
4:0.1
1.79 0.00
8 optim.
-4.16 + 0.59
1.75 002
-4.10
0.21
1.75
0.02
-5.13
4.051
1.72 +: 0.0
-1.45 061
73.88
-1.08 0.22
74.02
-1.50
0.6
70.42 0.94
CORNN
AQI
3 optim.
-190 + 0.54
70.17 1.2
-1.10
0.25
70.95
0.68
-1.38
0.62
68.24 0.85
COREL
-2.40 + 1.97
70.44 2.60
-3.54
+ 1.80
68.31
= 4.49
-2.61
+ 1.92
67.76 :: 3.12
8 optim.
-2.83 +: 1.86
67.35 231
-4.19
1.96
65.20
4.20
-3.22
2:2
65.32 3/43
17


Reviews:
[{"review_id": "6YBCIhBgoA", "reviewer": "Reviewer_5XUS", "summary": "The paper introduces Conformal Relational Prediction (COREL), a novel approach for uncertainty quantification in correlated time series forecasting using graph deep learning frameworks. COREL overcomes the data exchangeability limitation by employing a spatiotemporal graph neural network (STGNN) to model relationships among multiple time series based on past residuals, enabling the estimation of the quantile function for prediction errors. Unlike existing methods that treat time series independently, COREL captures dependencies among correlated series by conditioning uncertainty estimates on neighboring time series through a learned graph structure. Additionally, it incorporates an adaptive mechanism to handle non-stationary inputs, enhancing prediction intervals (PIs) across varying conditions. Empirical evaluations show that COREL achieves state-of-the-art performance across multiple benchmarks, effectively quantifying uncertainty while preserving high predictive accuracy.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for the review please find our comments below.\n \n> 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.\n\nThank 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.\n\n> Controlled environment adds rigor but assumes the simulation accurately represents real-world scenarios, which may not always hold.\n\nThere 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. \n\n> 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.\n\nDetails 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.\n\n> W1 The integration of graph deep learning may increase computational complexity and resource requirements, potentially limiting its practical deployment in resource-constrained environments.\n\nThe 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.\n\n> W2 The paper could provide more clarity on the assumptions made about the structure and nature of the underlying data, which may affect generalizability.\n\nWe 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.\n\n> W3/Q1 While adaptability is addressed [...] authors can possibly further explore how well their method performs in broader non-stationary conditions.\n\nWe 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.\n\n[1] Hamilton et al. “Inductive representation learning on large graphs” NeurIPS 2017\\\n[2] Chiang et al. “Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks” KDD 2019\\\n[3] Frasca et al. “SIGN: Scalable Inception Graph Neural Networks” arXiv 2020\\\n[4] Cini et al. “Scalable Spatiotemporal Graph Neural Networks” AAAI 2023", "claims_and_evidence": "The claims in the submission are well-supported by clear and compelling evidence, particularly regarding the performance of the Conformal Relational Prediction (COREL) method. The authors provide empirical results demonstrating that COREL outperforms existing conformal prediction approaches across multiple benchmarks.\n\nThe paper also details the algorithmic framework of COREL, highlighting its use of a spatiotemporal graph neural network to capture relationships among time series. Additionally, the inclusion of an adaptive mechanism for handling non-stationary inputs is emphasized as a key contribution, with validation through experimental results.\n\nHowever, further detailed comparisons with a larger set of existing methods and additional concrete examples of scenarios where COREL outperforms other methods can bolster the robustness.", "methods_and_evaluation_criteria": "Yes, it generally does.", "theoretical_claims": "The proof for Prop. 3.1 looks good without any obvious issues.", "experimental_designs_or_analyses": "1. The paper presents sound experimental designs to validate the effectiveness of COREL, notably through comparative experiments against several baseline methods such as SCP, SeqCP, and SCPI across diverse datasets. This comparative approach is valid but could be strengthened by including a wider variety of baseline models and clarifying their selection rationale. \n2. The use of the Winkler score and coverage metrics is appropriate.\n3. The controlled environment testing using a graph diffusion process adds rigor but assumes the simulation accurately represents real-world scenarios, which may not always hold. 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.", "relation_to_broader_scientific_literature": "The key contributions of the paper, particularly the introduction of COREL for uncertainty quantification in correlated time series using graph deep learning, are closely related to the existing literature in several ways. Firstly, the application of GDL to CP for time seriestraditional. \n\nConformal prediction (CP) methods, which often assume exchangeability, have been extended to account for time series data, showing limitations in their application due to non-stationarity in real-world scenarios. COREL builds on these findings by integrating a graph structure learning module to capture spatiotemporal dependencies, which has been noted as beneficial for improving prediction accuracy in various applications. Moreover, COREL's reliance on quantile regression aligns with established statistical frameworks for probabilistic forecasting, while addressing the shortcomings of existing CP techniques that often operate independently on univariate time series. By allowing for collective learning across multiple related time series, COREL advances the state of the art in uncertainty quantification methods, demonstrating effectiveness over traditional approaches and laying the groundwork for future explorations in spatiotemporal CP frameworks.", "essential_references_not_discussed": "None that I can think of now.", "other_strengths_and_weaknesses": "Strengths:\n\n1. COREL introduces a new conformal prediction method that effectively utilizes graph deep learning to quantify uncertainty in correlated time series.\n2. The model captures relationships among time series through a graph structure, enhancing forecasting accuracy by leveraging spatiotemporal dependencies.\n3. Empirical results demonstrate that COREL achieves state-of-the-art performance compared to existing CP approaches across multiple datasets and scenarios.\n4. COREL can be applied to residuals from any point forecasting model, even those that do not consider relationships among input time series, allowing for broader applicability.\n5. The inclusion of node-level parameters that adapt to changes in target sequences addresses non-stationarities effectively.\n\nWeaknesses:\n1. The integration of graph deep learning may increase computational complexity and resource requirements, potentially limiting its practical deployment in resource-constrained environments.\n2. The paper could provide more clarity on the assumptions made about the structure and nature of the underlying time series data, which may affect the generalizability of the findings.\n3. While adaptability is addressed, the actual performance in highly volatile or non-stationary conditions is not thoroughly evaluated and discussed.", "other_comments_or_suggestions": "No alarming typos.", "questions_for_authors": "Authors can possibly further explore how well their method performs in broader non-stationary conditions.", "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": "", "extra_scores": {}}, {"review_id": "X0FZPNaoDS", "reviewer": "Reviewer_aHCK", "summary": "This work is on uncertainty quantification in time series forecasting. The authors proposed a conformal prediction method based on graph neural networks. Their approach is based on quantile regression. A spatiotemporal graph neural network was trained on the residuals of the calibration dataset to predict the quantiles of the error distribution. The predicted residuals are used to learn the quantile function of the error distribution at each time step. The performance metrics used were: the difference between the specified confidence level and the observed coverage on the test set; the width of the PI and the Winkler score. The proposed approach was tested on three benchmark datasets and the proposed model outperforms competitors in terms of Winkler score for most of the test cases. Its performance is comparable to other models based on the other two metrics.\n\n## update after rebuttal\nThe explanations provided by the authors and the changes they intend to make are satisfactory. However, I would stay with the rating recommended earlier.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your review! Please find our point-by-point answers below.\n \n> 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.\n \nCoverage 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.\n\n> It would have been important to show how modeling spatio-temporal relationships has provided additional insights.\n \nThe 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.\n\n> I did not see any experimental designs or analyses of the same or results of such experimental designs.\n \nThere 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.\n \n> The authors focused on univariate analysis. Ideally, one should demonstrate the approach with multivariate time series.\n \nOur 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.\n\n> 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.  \n \nThere 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.\n\n\n> One does not know actual utility of this work to an application engineer. How does this work make a difference in real life?\n \nWe 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.\n \n> Would a 1 or 2 %improvement in Winkler score make a great difference? Any difference for the user?\n \nThere 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.\n \n[1] Jin et al. “A survey on graph neural networks for time series” TPAMI 2024\\\n[2] Cini et al. “Graph deep learning for time series forecasting” arXiv 2023\\\n[3] Feldman et al. “Calibrated Multiple-Output Quantile Regression with Representation Learning” JMLR 2023\\\n[4] Smith, “Uncertainty Quantification: Theory, Implementation, and Applications” SIAM 2013", "claims_and_evidence": "The results presented show that the proposed model is better than other models based on Winkler score but other models perform as well or better based on the other two metrics. Hence, once cannot completley claim that the proposed model is superior to previous models.", "methods_and_evaluation_criteria": "The proposed method and the evaluation criteria are appropriate. But, since the authors claim that this work is mainly addresses the spatio-temporal relationships in multivariate time series data, it would have been better if they clearly demonstrated the value of this method with detailed explanation and results at least for one of the test cases, showing how taking spatio-temporal relationships has provided additional insights into the behavior of the system.", "theoretical_claims": "The authors made a theoretical proposition and also provided a short proof for the same (Section 3.3 and Appendix A)", "experimental_designs_or_analyses": "I did not see any experimental designs or analyses of the same or results of such experimental designs. The authos have essentially tested their proposed method on three standard benchmarks and presented the results.", "relation_to_broader_scientific_literature": "This work could be considered an incremental contribution to uncertainty estimation in multivariate time series forecasting. It is certainly of value but needs further testing and evaluation in detail for specific use cases to see if it has real practical utility.", "essential_references_not_discussed": "The main contribution of this work in the development of STGNN for conformal prediction. The authors cited relevant literature and provided appropriate references. Fairly decent review of the previous work was provided in Section 4. The authors identified the shortcomings of the previous works in terms of STGNNS and CP and cited relevant literature.", "other_strengths_and_weaknesses": "Both STGNNs and conformal prediction methods exist. But where the current work comes out good is in introducing quantile regression for predicting the quantiles of the error distribution of an existing model, rather than on forecasting the target variable. The proposed approach appears to be more adaptive. The local components of the model are updated over time while retaining the global relationships. However, the authors focused only on univariate analysis. Ideally, one should demonstrate the approach with multivariate time series. Secondly, while this approach is different from previous works, it's important to demonstate how predicting the quantiles of the error distribution is better than forecasting the target variables. The advantage has to be shown quantitatively. \nThe authors demonstrated the approach on three benchmarks and provided the standard test results. One of the main drawbacks of this work as well as similar such works is, one does not know actual utility of this work to an application engineer. How does this work make a difference in real life? Would a one or two pecent improvement in Winkler score make a great difference to uncertainty estimation and can it alter final decisionmaking? Are the improvements shown in performance metrics with one or two percent improvements, and in some cases, just in the third or fourth decimal point, make any difference to the end user?", "other_comments_or_suggestions": "It is important to quantitatively demonstrate the value of conformal prediction with quantile regression over forecasting target variables. The comparison has to be on the approach rather than the STGNN model.\nSecondly, it would be better if the authors take a real life example, and demonstrate the value of the work rather than the standard performance metrics showing improvement with a few percent points or improvement in third or fourth decimal. Such works do not really make any difference to practising engineers.\nSimilarly, since this work is on STGNN, it's important to demonstrate the true value with a multivariate time series forecasting test case and provide insights on how incorporating dynamic spatio-temporal realtionships make a difference in uncertainty estimation.", "questions_for_authors": "Please see the earlier comments.", "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": "", "extra_scores": {}}, {"review_id": "y5r80T0oXk", "reviewer": "Reviewer_oqTA", "summary": "The paper presents Conformal Relational Prediction (COREL), which integrating graph deep learning (GDL) operators into the CP framework, allowing relational structures to improve uncertainty estimation for spatio-temporal time series. The method utilizes a STGNN to provide structural embeddings and applies quantile regression to produce the PIs. The algorithm can be modified to become adaptive to data shifts (by modifying local parameters). Strong experimental results supports authors claims.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for the review! Please find our answers to your questions below.\n \n> Missing reference.\n \nWe agree it is a relevant reference. We will include it in the updated version of the paper. Thank you.\n \n> Typos.\n \nThank you for spotting those!\n \n> 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.\n \nThank 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.", "claims_and_evidence": "Yes, the claims are well-supported.", "methods_and_evaluation_criteria": "Great, no notes.", "theoretical_claims": "Correct but not the most illuminating. See question section.", "experimental_designs_or_analyses": "Comprehensive baseline selection, good metrics, nice diverse datasets. Experiment section is well done.", "relation_to_broader_scientific_literature": "GNN structure-informed conformal quantile regression has not been explored before in literature. Given the importance of GNN in modeling Spatiotemporal data, this is very useful, as demonstrated by the authors via experiments.", "essential_references_not_discussed": "should also cite the original conformal quantile regression paper:\n\n@article{romano2019conformalized,\n  title={Conformalized quantile regression},\n  author={Romano, Yaniv and Patterson, Evan and Candes, Emmanuel},\n  journal={Advances in neural information processing systems},\n  volume={32},\n  year={2019}\n}", "other_strengths_and_weaknesses": "Strong paper for uncertainty quantification. Good method, well-motivated and well-presented.", "other_comments_or_suggestions": "typos:\n\n- abstract line 38: \"archives state-of-the-art uncertainty quantification\" → \"achieves state-of-the-art uncertainty quantification\".\n- Method by Xu & Xie 2023b is SPCI (sequential predictive conformal inference) instead of SCPI...", "questions_for_authors": "Prop 3.1 is the main theoretical support for the method. However, it blankets everything that could undermine the conformal guarantee under the total variation. This is not great because in reality it's hard to estimate or control TV (since it is the sup over the entire space). So there is really no guarantees other than \"let's hope our quantile regression works well\".  \n\nThe authors wrote, following prop 3.1\n> By making assumptions on the expressivity of the quantile regressor in Eq. 13 and on the stationarity process (e.g., by assuming a strongly mixing process), we can expect the total variation between the learned and true distribution to shrink asymptotically as the size of the calibration set increases\n\nbut provided no proof to support this claim. (I know this is a common argument, but even supporting citations will help, a proof with the specific setup will be better. ) Most previous conformal work that incorporates quantile regression, from CQR to  SPCI and [this paper](https://openreview.net/forum?id=oP7arLOWix) (also) by Lee, Xu and Xie, contains an actual validity proof.", "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": "", "extra_scores": {}}, {"review_id": "NORzsJ9ADc", "reviewer": "Reviewer_oUbs", "summary": "The work introduces Conformal Relational Prediction (CoREL), a novel distribution-free uncertainty quantification method for time series forecasting that leverages graph deep learning. CoREL integrates spatiotemporal graph neural networks with conformal prediction (CP) to capture relational structures among correlated time series and estimate prediction intervals more effectively.\n\n## update after rebuttal\nThank you to the authors for the rebuttal. Most of my concerns have been adequately addressed and I feel it a good combination about graph representations with time series, so I have decided to raise my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for the review. Please find our comments below.\n\n> Comparisons against standard CP methods in terms of runtime are needed to fully validate efficiency claims.\n \nThe 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.\n\n> W1 Graph inference and message passing may introduce scalability issues.\n \nScalability 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.\n\n> W2 No formal guarantee that the learned graph structure is optimal[...] Visualizations or comparisons could help.\n \nFirst 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. \n\n> W3 No benchmark against other graph-based uncertainty quantification approaches such as [1]. It would be interesting to compare and discuss the results here.\n \nWe 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.\n\n> 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.\n\nThe 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).", "claims_and_evidence": "The work provides strong empirical support for several key claims. CoREL’s ability to capture relational structure for uncertainty quantification is demonstrated through both real-world datasets and a controlled synthetic experiment, confirming that the learned relationships enhance prediction intervals. Additionally, CoRELs adaptive learning mechanism is tested on non-stationary data, showing that it can adjust dynamically to evolving time series patterns.\nHowever, as the paper claims that CoREL scales well and is computationally efficient. The method requires graph inference at every update step, which may introduce non-trivial overhead. Comparisons against standard CP methods in terms of runtime are needed to fully validate efficiency claims.", "methods_and_evaluation_criteria": "The methods of leveraging GNN to capture relational structures in time series make sense overall. The evaluation criteria in experiments such as the coverage rate and prediction interval width aligns with conformal prediction and prior works.", "theoretical_claims": "The theoretical guarantee for Proposition 3.1 is correct.", "experimental_designs_or_analyses": "The experimental design of CoREL demonstrates several strengths, particularly in its comprehensive evaluation across multiple real-world time series datasets. The inclusion of diverse baselines ensures that CoREL's performance is rigorously benchmarked against existing conformal prediction methods. The study also examines the adaptability of CoREL in non-stationary settings by performing cross-validation and fine-tuning, demonstrating its ability to refine uncertainty estimates dynamically.", "relation_to_broader_scientific_literature": "CoREL contributes to the broader scientific landscape by bridging conformal prediction, graph-based deep learning, and uncertainty quantification in structured data. Traditional conformal methods assume independence, limiting their effectiveness in relational settings. By dynamically learning inter-series dependencies, CoREL aligns with advances in spatiotemporal modeling, probabilistic inference, and adaptive learning in graph-based frameworks. Its approach connects with broader efforts in representation learning, self-supervised graph modeling, and uncertainty-aware neural architectures, highlighting the growing need for flexible, data-driven methods that generalize across domains.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. CoREL effectively integrates conformal prediction with graph learning, capturing dependencies in correlated time series. It avoids strong distributional assumptions and dynamically adapts to non-stationary data.\n\n2. The model infers inter-series relationships, eliminating the need for predefined graphs.\n\n3. Comprehensive Evaluation – Tested across diverse datasets with ablation studies, reinforcing its empirical validity.\n\nWeaknesses:\n1. Graph inference and message passing may introduce scalability issues.\n\n2. While the model dynamically learns dependencies, there is no formal guarantee that the learned graph structure is optimal for uncertainty quantification, though it proves effective in experiments. Visualizations or comparisons could strengthen this aspect. \n\n3. While CoREL is compared to standard CP methods, it does not benchmark against other graph-based uncertainty quantification approaches, such as Bayesian graph neural networks or CP for GNNs [1]. It would be interesting to compare and discuss the results here.\n\n[1] Zhao, T., Kang, J., & Cheng, L. (2024, August). Conformalized link prediction on graph neural networks. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 4490-4499).", "other_comments_or_suggestions": "The paper is well-structured, clear, and easy to follow. While there are some weaknesses, they do not significantly impact the overall quality.", "questions_for_authors": "1. Please refer to weaknesses.\n\n2. I am not deeply familiar with the specifics of the datasets, but I wonder if they exhibit strong correlations. Are there any limitations to CoREL? Under what conditions might its performance degrade? A discussion on the method’s limitations would be valuable.", "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": "", "extra_scores": {}}, {"review_id": "3XKLmr1Ki5", "reviewer": "Reviewer_uUN5", "summary": "This paper introduces a method for improving uncertainty quantification in time series forecasting by leveraging correlations between sequences. The authors propose Conformal Relational Prediction (COREL) that integrates conformal prediction and quantile regression with graph-based deep learning. The method captures relationships between time-series without requiring prior knowledge of the graph structure. It also adapts to non-exchangeable data and time series variations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for the review, please find point-by-point answers below.\n \n>Unclear if smaller PIs (or lower Winkler) simply stem from anti-conservativeness.\n \nThere 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).\n \n> Discussion of the learned graph topology.\n \nExperiments 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.\n \n> No theoretical guarantees for non-asymptotic coverage: claiming that it falls within CP is not justified.\n \nWithout 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.\n \n> Typo eq. 9\n \nThanks, the correct version is:\n \n$$\\hat y^i_{t} = Readout \\left(h_t^{i,L}\\right)$$\n \n> Q1 Why only residuals as input and not also the history of the TS?\n \nThere might be a misunderstanding, as stated in lines 195–198 (right), we also use the actual time series as part of the input.\n\n> Q2 Motivation to feed to the decoder TS independently rather than matrix Z_t in Eq.(12).\n \nBecause: (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].\n \n> Q3 Conformal sets are cubes (cf. Eq. (14)). This appears suboptimal, as it does not leverage the learned structure.\n \nThere 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. \n \n> Q4 The way this sparsity prior is used is not clear to me.\n \nAs 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].\n \n> Q5 The way the adaptive version of the method works is not clear to me.\n \nWe 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.\n \n[1] Barber et al. “Conformal prediction beyond exchangeability” Ann. Statist. 2023\\\n[2] Xu et al. “Sequential Predictive Conformal Inference for Time Series” ICML 2023\\\n[3] Auer et al. “Conformal Prediction for Time Series with Modern Hopfield Networks” NeurIPS 2023\\\n[4] Xu et al. ”Conformal prediction interval for dynamic time-series” ICML 2021\\\n[5] Gibbs et al. “Adaptive conformal inference under distribution shift” NeurIPS 2021\\\n[6] Cini et al. “Graph deep learning for time series forecasting” arXiv 2023\\\n[7] Cini et al. “Sparse graph learning from spatiotemporal time series” JMLR 2023", "claims_and_evidence": "I appreciate the authors' effort in comparing their method against multiple baseline approaches across different datasets. However, the results in Table 1 are challenging to interpret. Notably, CoREL consistently fails to achieve the targeted marginal coverage across datasets. As a result, it is unclear whether the smaller prediction interval widths (or lower Winkler scores) reflect the superiority of the proposed method or simply stem from its anti-conservativeness.", "methods_and_evaluation_criteria": "The metrics and dataset considered to evaluate the method make sense for the application at hand. Nevertheless, the paper focus on the prediction interval widths, which is inherently due to the fact the method gives confidence regions (in R^N where N is the number of time series) which are cubes. In my opinion, this is one limitation of the method. Please refer to the section \"Questions to for authors\" for more details).", "theoretical_claims": "There is no contribution on the theoretical side in the paper. Proposition 3.1 follows from the definition of the total variation distance.", "experimental_designs_or_analyses": "The method proposed by the authors learn the graph topology used in the GNN to estimate quantiles from the residuals on the calibration set. Nevertheless, the authors do not discuss the learned graph topology (e.g. from in interpretability viewpoint). I would have been also interesting to conduct an ablation study to see if learning the graph really helps compared to considering a", "relation_to_broader_scientific_literature": "The paper is at the crossroad of several important topic in the field of uncertainty quantification. The propose method aims to quantify uncertainty when dealing with spatio-temporal data in a multivariate settings. \nMost existing methods in the litterature on conformal prediction typically focus on one of these challenges (i.e. methods designed to deal with multivariate output data, or spatial data or non exchangeable data). \n\nNevertheless, the way the paper is written gives the impression that the introduced method is a conformal prediction approach. However, the method lacks a theoretical guarantee of non-asymptotic valid coverage. Therefore, claiming that it falls within the conformal framework is not justified, in my opinion.", "essential_references_not_discussed": "Relevant related works are cited as far as I am aware.", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "Here are some typos:\n\n- Eq (9): h_t^L should be H_t^L.\n\n- In Eq.(9), should it be \\hat y^{i}_t  and $h^{i,L}_t$ ?", "questions_for_authors": "I would be grateful if the authors could clarify the following aspects:\n\n- Why only the residuals are provided as input in the RelQPs and not providng also the history of the time-series themselves ? \n\n- Could the authors comment on the motivation to feed to the decoder the time series independently rather than having still a single decoder but that would take as input the matrix Z_t to predict quantiles in Eq.(12)?\n\n- The final conformal sets are cubes (cf. Eq. (14)). This form of conformal sets appears suboptimal, as it does not leverage the correlation structure learned by the RelQPs between the time series to produce a confidence region that adapts to the dependence structure of the data rather than remaining cubic.\n\n- In the paper, the authors explain that \"the relational structure is sparse\" (between the N time series). The way this sparsity prior is used as an inductive bias in the model architecture and/or the optimization scheme is not very clear to me. It seems that this question is touched in Appendix D but there were not enough details for me to understand completely. Could the authors provide more information on this sparsity aspect ?\n\n- The way the adaptive version of the method works is not clear to me. In Section 5.3, it is stated that \"we split the test set in K = 6 folds and then iteratively evaluated and fine-tuned the model on each fold.\" How to use the method is practice (since in real aplication, the test set is in the future and we don't have measurements) ? In my understanding, people would need to split the calibration set into two parts: one used to train RelQPs and the used to fine-tune the learnable node embeddings V.", "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": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: This paper considers the problem of uncertainty quantification in relational/spatial time series prediction problems. The proposed approach synergistically combines the benefits of graph deep learning (spatio-temporal GNN) and conformal prediction based distribution-free uncertainty quantification to solve this problem. Specifically, spatio-temporal GNN provides structural embeddings and quantile regression is applied to produce prediction intervals. Experimental results are strong.

This paper received mostly positive reviews, but reviewers' also raised a number of constructive questions/concerns. The author response addresses these concerns and all the reviewers' supported accepting the paper. Therefore, I recommend accepting this paper.
Decision: Accept (poster)