Topology-Aware Conformal Prediction for Stream Networks

We sincerely thank for the reviewer’s comment.

Assumptions and Limitations

• The i.i.d. error assumption underlying Theorem 5.6 is a standard setup when establishing conditional coverage gap guarantees, which is also used in [1] (see Assumption 4.1). The assumption ensures tractability in the theoretical analysis of time-varying nonconformity scores, as it allows the score at a new time point to be meaningfully compared to those from past calibration time points. Importantly, the i.i.d. assumption in our analysis applies specifically to the true error process $\varepsilon_t$, not to the observed time series $y_t$ or the predicted residuals $\hat{\varepsilon}_t$. This setting covers a broad class of time series models, including non-stationary processes where the innovations are i.i.d., such as autoregressive models. Additionally, when the i.i.d. assumption may not hold, our method resorts to the Adaptive Conformal Inference (ACI) mechanism, which adaptively adjusts the threshold $\alpha_t$. While this approach no longer guarantees conditional coverage, it retains asymptotic average coverage without requiring distributional assumptions on $\varepsilon_t$. We will clarify this distinction in the revised manuscript.

• The volume of the prediction set is locally adaptive in STACI and STACI accounts for serial correlation. Please see more in the related work discussion.

• STACI scales well for graphs with a moderate number of nodes (typically fewer than 30). Applying joint conformal prediction, or general uncertainty quantification, to hundreds of nodes is statistically uninformative due to the curse of dimensionality, as the resulting prediction set volumes become overwhelmingly large. Our framework focuses on localized subgraphs where uncertainty quantification remains both tractable and practically meaningful. This also aligns with practical needs in domains like traffic or hydrology where stakeholders are often concerned with the overall status or joint safety of a spatial region.

Related Work Discussion

Here we would like to put some clarifications on our work as well as the discussion for the related work, particularly [1]&[2] as mentioned. In short, while both methods incorporate temporal adaptivity, STACI inherently distinguishes local MultidimSPCI [1] and show superior performance in our setting.

Specifically, in the local version of [1], the algorithm constructs the sample covariance matrix and nonconformity scores at each time step using the most recent $T$ observations, and suggests the possible introduction of an additional local term using the most recent $k = 0.1T$ observations to regularize short-term variability (Section 3.4, Equation 11). This design indeed provides temporal regularization and adaptivity to local serial correlation. Similarly, STACI also incorporates local adaptivity and serial correlation. We compute conformity scores using covariance matrix based on a rolling window of the most recent $n$ residuals, which reflects temporal local variation.

The key distinction is in the type of regularization: [1] imposes local regularization in time based on residual windows; in contrast, STACI introduces regularization in space, via a topology-induced covariance structure that encodes spatial dependencies through a tail-up model. This spatial structure imposes stronger constraints with fewer parameters, often leading to improved empirical stability and faster convergence. As illustrated in Figure 3 of our appendix, when using only the empirical sample covariance matrix $\lambda = 0$, which corresponds to MultiDimSPCI, the prediction sets suffer from under-coverage unless the calibration window size $n$ (or $T$ in [1]'s notation) is sufficiently large. This issue persists regardless of whether adaptive thresholding (ACI) is applied $\gamma = 0.01$ or not $\gamma = 0$, highlighting the sample inefficiency of unstructured covariance estimation. In contrast, by incorporating topological priors, STACI achieves valid coverage even with a relatively small number of calibration samples, demonstrating improved robustness and data efficiency.

In the original paper, we compare with the classic version of MultidimSPCI [1] instead of the local variant, following the authors experiment setup (Section5, [1]). In response to your suggestion, we provide the comparisons in Tables 1 and 2, following the setting in Sec 6.2 and hyperparameters suggested by [1]. In this problem, the local version of MultidimSPCI do not bring sigificant benefit over its original version, let alone supurpassing our methods. STACI is advantageous in both coverage and efficiency.

Table 1: Coverage Comparison over different datasets and backbone models

Table 2: Efficiency Comparison over different datasets and backbone models

We clarify that while Theorem 1 in our paper shares some similarities in proof structure with Theorem 4.12 in [1], the statement, setting, and generality of the result are different. Specifically, [1] focuses on convergence guarantees when the Mahalanobis nonconformity score is constructed using the empirical sample covariance matrix. Our result establishes convergence guarantees for a general positive semi-definite matrix $A$ or a convergent matrix sequence $A_T$, which includes but is not limited to the sample covariance matrix. This generalization allows us to theoretically justify the use of topology - induced covariance structures or other regularized estimators within the conformal prediction framework that are not discussed in [1]. Furthermore, our analysis includes theoretical conditions under which the choice of $A$ leads to efficient conformal prediction, while [1] does not address how to select $A$ beyond using empirical estimates.

We'll revise the related work to include the suggested concurrent research and refine the discussion on MultidimSPCI to accurately reflect its contributions and our clarifications. Thank you again for your valuable opinions!

Q1: Difference of definition with [2] in Equation 2

A: The quantity $\hat{\epsilon}_t$ in Equation (2) represents the prediction error at time $t$, defined as the difference between the observed value $y_t$ and the prediction $f(x_t)$. While the notation differs from the error vector $r_t$ used in [2], the underlying semantics are equivalent. Both quantify the residuals between predicted and true values at each time step.

Q2: Sizes of datasets and magnitute of temporal distribution shift

A: PeMS-G1 and PeMS-G2 are spatial subsets of the larger California PeMS traffic dataset, each containing 12 nodes and spanning 26208 time steps, as stated in Appendix D.2. We select a localized subgraph within the full traffic network to define a coherent spatial region for conformal prediction.

To assess temporal distribution shifts, we employ two metrics leveraging daily periodicity (288 5-minute observations/day): Average Intra-Period Flow Variance (average daily flow variability) and Average Inter-Period Mean Flow Shift (average day-to-day change in mean daily flow). Due to space limit, we only show the average value over all observation points as follows.

The analysis reveals substantial temporal shifts, with strong intra-day flow pattern shifts (high intra-period variance) and non-negligible inter-day mean flow shifts.

Further, empirical evidence strongly suggests its presence. In particular, as shown in Figure 3, the coverage achieved by ACI with adaptive thresholding $\gamma_t = 0.01$) is substantially higher than that obtained with a fixed threshold ($\gamma = 0$ ). This performance gap reflects ACI’s ability to correct for temporal variation in the error distribution, thereby indirectly confirming that distribution shift exists in the data.

Q4: Scalability of STACI to very large graphs and variable flow topology? [3]

A: STACI scales well for graphs with a moderate number of nodes (typically fewer than 30). In general applying joint conformal prediction or consider joint uncertainty quantification to hundreds or thousands of nodes simultaneously is not statistically meaningful, due to two reasons: 1. They are not interpretable. One cannot obtain any useful insights from a uncertainty set in a super high-dimensional space. In such setting, it is usually done by sampling, i.e., presenting samples from a high-dimensional space. 2. They are usually overly conservative.

By focusing on high-dimensional uncertainty quantification within spatially coherent subregions such as traffic corridors or watershed areas, STACI aligns well with practical needs in domains where stakeholders are primarily concerned with the joint behavior of a specific region rather than the entire network. For example, in freeway traffic management, operators may monitor 10–30 sensor locations along a congested segment to assess regional flow stability; in hydrology, flood risk is often evaluated jointly across 15–25 stream gauges within a watershed. These are typical dimensionalities where joint prediction is both statistically meaningful and computationally tractable, and where STACI is most effectively applied.

Q5: Robustness when the assumed topology does not fully reflect true dependencies

A: When the topology does not fully reflect true dependencies, STACI is designed to be robust to imperfect topological information through the weighting parameter $\lambda \in [0, 1]$, which interpolates between the sample-based covariance matrix and the topology-induced one. The topology-induced covariance may lead to suboptimal efficiency, but the overall coverage guarantee remains valid due to the conformal framework.

We conducted additional ablation studies and observe that even when the topology is only partially accurate, it still contributes useful inductive bias especially in capturing local dependencies and reducing estimation variance, compared to using the sample covariance alone. In Tables 1, we introduced random noise (mean=0, std = noise scale) to observation locations; clean G1 and G2 have longest connected distances of 8.75 and 3.41 miles. Bold rows highlight clean data performance. Results show STACI's robustness to moderate noise, with higher noise levels leading to prediction degradation, mainly through increased inefficiency.

Table 1. Performance of STACI with different backbone GNNs on noisy PEMS03-G1& G2

Q6: Extension to non-flow-based graphs

A: The current formulation of STACI is tailored to flow-based structures such as stream networks, where directionality and upstream-downstream relationships are well-defined. In non-flow-based graphs, such as social networks, the corresponding topology-induced covariance structure equires modeling efforts and current tail up model may not be applicable. To apply STACI in such settings, one would need to adopt alternative network parameterizations such as diffusion kernels or graph Laplacians that better capture the relevant spatial dependencies. We view this as a promising future direction and have outlined it in our conclusion, where we suggest extending STACI to general spatio-temporal graphs using more flexible graph-based covariance models.

Q7: Expansion of baseline methods

A: Unlike most GNN-based methods that provide independent marginal prediction intervals, STACI performs joint uncertainty quantification for all nodes in a local region, yielding multivariate prediction sets in ${R}^I$ that capture spatial correlations. Table 2 compares STACI (with various GNN backbones) against DeepSTUQ [1], a state-of-the-art Bayesian GNN for uncertainty quantification. DeepSTUQ failed to achieve 95% coverage on dataset G1. With desired coverage met, our methods demonstrate superior efficiency.

To enable a meaningful comparison of set efficiency, we aggregate the marginal intervals from DeepSTUQ into a hyper-rectangle and compute its volume as a proxy. Theoretically, to ensure joint coverage $\geq95\%$, each marginal interval would need to be Bonferroni-adjusted to $1 - \alpha/I$ ( 99.58% when $I = 12$), which leads to overly inflated volumes and high coverage. Instead, we report volumes using unadjusted 95% marginal intervals, which better reflects how DeepSTUQ might be used in practice. We acknowledge that this does not guarantee joint coverage, but it provides a practical and meaningful basis for comparison.

Table 2. Performance of DeepSTUQ and STACI on PEMS03-G1 and G2

Q8: Clarification of dataset types and topological structure

A: In our experiments, we use the traffic dataset, where sensor observations are recorded at fixed locations along freeway segments. The underlying topology is constructed from the physical road network, with directed edges representing traffic flow direction between road segments.

While our empirical evaluation focuses on traffic data, the STACI framework is applicable more broadly to domains that share the following structural characteristics: (1) observations are collected at discrete spatial sites located on segments (e.g., roads or stream reaches), and (2) the observed data reflects flow with a meaningful directionality (e.g., vehicle movement or water discharge). This includes applications in hydrology, transportation, and other spatio-temporal systems where directional flow and location-based measurements define the graph structure.

Response to weakness:

• Complexity analysis & ACI and Topology Estimator Evaluation. Due to space limit, please refer to our response to W1 & W3 of reviewer mDnW.

• CP Baseline Coverage. Please see response to W2.2 of reviewer q8kS.

We thank the reviewer again for your helpful suggestions.

[1] Qian, Weizhu, et al. "Uncertainty quantification for traffic forecasting: A unified approach."

[2] Xu et al. , "Conformal prediction for multi-dimensional time series by ellipsoidal sets"

Q1a: Problem definition clarification
A: We appreciate the reviewer’s suggestion to improve clarity. The stream network is represented as a directed acyclic graph, where each node corresponds to a spatial observation site located on a stream segment. For example, in the traffic dataset, stream segments represent roads, and observation sites are traffic sensors placed along those roads. A visual illustration is provided in Figure 1 of the main paper. Note that each location belongs to exactly one segment, while a segment can contain multiple observation sites.

Q1b: Notations for segments
A:We use i to index sites, and j to index segments. a network consists of multiple stream segments, where all the possible locations on a segment $j$ is represented by a geolocation set $r_j \subset L$. A segment may contain one or multiple observational sites. The geolocation of a site $i$ is denoted by $l_i \in L$. $u, v \in L$ are dummy variables for arbitrary locations on the network. The use of $s_i$ was a typo and should be corrected to $r_i$ and thanks for pointing out.

Q2: Tail-up scaling parameters $\phi$ and $\sigma^2$: design and learning
A: The parameters $\phi$ and $\sigma^2$ in Equation (5) are scaling factors estimated during the construction of the topology-induced covariance matrix $\hat{\Sigma_G}$ used in the Mahalanobis non-conformity score. They are not learned jointly with the predictive model’s weights. The weights of backbone GNNs are learned on training data and fixed, but $\phi$ and $\sigma^2$ are optimized on the calibration data. Specifically, $\phi$ and $\sigma^2$ are selected by minimizing the discrepancy between the sample covariance matrix and $\hat{\Sigma}_{{G}}$, allowing the tail-up model to better reflect the empirical correlation structure. $\sigma^2$ controls the overall magnitude of spatial dependence, while $\phi$ determines the rate of decay of spatial correlation with hydrologic distance.

Q3: In Appendix C, Equation (27) introduces ($\eta_t$) as the ACI step size, but line 171 refers to “($\alpha = 0.01$)” as the predefined coverage level. Should this reference be to ($\eta_t$) instead? Please clarify the notation.
A: Thanks for pointing it out. It should refer to $\alpha=0.01$, and we will fix this in the final version.

Q4: Line 169 mentions the guarantee holds even in adversarial online settings. However, no theoretical or empirical support is given. Could you substantiate this claim and describe the adversarial setting more clearly?
A: Yes, we clarify that the asymptotic average coverage guarantee in Proposition 1 is theoretically grounded in Proposition 4.1 of [4], which analyzes Adaptive Conformal Inference (ACI) under arbitary time series data, even chosen in an adversarial manner, without assuming i.i.d. or stationarity. The key mechanism is the dynamic calibration of the quantile threshold $\alpha_t$ based on past coverage. If recent prediction sets are too conservative, the threshold is decreased to improve efficiency; if they under-cover, the threshold is increased to restore validity. This mechanism ensures that the long-run average coverage converges to the target level, regardless of the underlying sequence. Though the proof in [4] is presented for univariate outputs, the argument extends naturally to our setting with high-dimensional multivariate responses, as the calibration procedure operates on scalar-valued conformity scores, regardless of the dimensionality of the input space.

Q5: Line 277 states that the topology-based matrix converges faster than the sample covariance estimator. Could you provide evidence for this claim?

A: The topology-based covariance estimate benefits from strong structural priors. Specifically, the tail-up estimator introduces strong structural regularization by encoding known topological relationships, which parameterizes the covariance structure using two scalars, $\sigma^2$ and $\phi$, in contrast to the $O(I^2)$ parameters needed for a full sample covariance. This regularization improves sample efficiency and stabilizes estimation in high-dimensional, low-sample settings. Empirically, we observe that the topology-regularized estimator achieves better coverage under small calibration sizes. As shown in Figure 3 of the appendix, when using only the sample covariance matrix (i.e., $\lambda = 0$), the coverage deteriorates sharply as the sample size decreases. In contrast, the topology-based estimator maintains reliable coverage even when few residuals are available, supporting the claim of faster empirical convergence. While theoretical convergence rates for topology-aware estimators like the tail-up model remain an open area of research, our observations are consistent with the general statistical principle that incorporating structural priors enables more robust estimation with fewer samples.

Q6: What calibration set size was used to generate the results in Table 1?

A: Calibration set size $n$ is set to be 300, as specified in the default experimental setup (line 310 of the main paper).

Q7: Which backbone model was used to generate the results in Figure 3? Do the trends hold for other backbones like ASTGCN or STGODE?

A: The results in Figure 3 (main paper) were generated using AGCRN, as stated in lines 368–369. We confirm that similar trends hold across other backbones, including ASTGCN and STGODE. Plots for all datasets and backbones are provided in the Appendix (Figure 3).

Q8: The conclusion suggests extending STACI to general spatio-temporal graphs and alternative network parameterizations. Could you elaborate on what you mean by “general spatio-temporal graphs” and give a concrete example of such parameterizations?

A: By general spatio-temporal graphs, we refer to settings that go beyond directed stream networks and include arbitrary graph topologies where node features evolve over time such as social networks, etc. In these cases, spatial dependencies may arise from learned or domain-specific connectivity patterns rather than physical flow, and may not follow upstream-downstream constraints.

The main idea is that incorporating topological structure rather than treating the data as purely multivariate time series can yield more structured and stable estimators of covariance or other quantities used in high-dimensional conformal prediction. For example, one could use diffusion kernels or graph Laplacians to construct covariance structures that reflect node influence or proximity in a soft, learnable manner. This opens the door to extending STACI-like methods to broader domains with complex spatio-temporal dependencies.

Response to weakness

In addition to the specific questions raised, we would like to address several points mentioned in the weaknesses.

w1.2: lack of ACI introduction in the main paper

A: We agree that the role of ACI deserves more attention. The main contribution of our work lies in the topology-based regularization of the covariance structure. Due to space constraints, we included its description in the Appendix. However, we will include a brief summary in the main text to provide readers with a clearer understanding of how ACI interacts with our topology-based regularization.

W2.2: Expanding to additional datasets or baselines

A: Regarding the baselines, as shown in Xu et al. [3], those methods significantly underperform compared to MultiDimSPCI, especially in high-dimensional joint prediction tasks. For this reason, we focused our comparisons primarily on MultiDimSPCI, which represents the strongest known baseline in this setting. Notably, our method outperforms MultiDimSPCI.

W2.3: Lines 375–377 claim “significantly higher coverage and superior efficiency” but Table 1 shows STACI’s coverage exceeds the best baseline in only one cell (ASTGCN, PeMS-G1) and by just 0.12. I think more evidence is needed to better support the claim.

A: We respectfully clarify that in conformal prediction, the primary objective is to achieve the target coverage level (e.g., 95%) while minimizing the size of the prediction sets. Once valid coverage is attained, efficiency becomes the key metric: a more efficient method yields tighter prediction sets without sacrificing validity. Therefore, coverage above the target is not inherently better; in fact, methods that consistently exceed 0.95 may be overly conservative and less informative. In this context, STACI achieves coverage close to the nominal level while producing smaller prediction sets in most scenarios, indicating a more efficient uncertainty quantification.

W2.4: Including a baseline that applies ACI with the vanilla sample covariance matrix would isolate the incremental benefit of the topology-based estimator. Without it, one cannot tell whether gains arise from ACI, from the topology-aware covariance, or from their combination.

A: We included such ablation experiments in Figure 3 in the main paper and in the Appendix to disentangle the effects of ACI (via $\gamma = 0$ vs. $\gamma = 0.01$) and the use of the topology-induced covariance matrix (via varying $\lambda$). When $\gamma$ is 0, ACI is not applied, but STACI can still achieve better performance than most other baselines.

w2.5:Details such as the number of nodes, edges, and time steps are absent, making it difficult to judge whether the method scales to large real-world stream networks.

A: Detailed dataset statistics, including the number of nodes, edges, and time steps, are provided in Appendix D.2. We will ensure this is made clearer in the main text as well.

[4] Gibbs, Isaac, and Emmanuel Candes. "Adaptive conformal inference under distribution shift."

We sincerely thank the reviewer for the feedback. Here we provide response to weaknesses:

W1: The usage of graph kernel matrices introduces O(n^2) memory and compute complexity, limiting scalability to large graph.

A: Here we provide a detailed complexity analysis. The psuedo-codes of our algorithm can be found in Algorithm 1 of Appendix. Compare to MultiDimSPCI, for each test time point we need: 1) additional estimation of tailup parameters ($\phi$ and $\sigma^2$) using historical covariance matrix (line 6), 2) weighted addition of spatial covaraince and emperical covaraince (line 7). Consider the node size is $n$ and the optimization methods (e.g., least square in our implementation) iteration round $N_i$. The former estimation takes $O(N_i⋅n^2)$, and the later addition takes $O(n^3)$, as pseudo-inverse of matrix is involved. However, MultiDimSPCI also needs matrix inverse for mahalabis distance calculation (line 8), which also takes $O(n^3)$. Additionally, estimation of only two parameters $\phi$ and $\sigma^2$ can converge fast. Therefore, our method do not need significantly more time than the baseline method, consistent to the Table 1 running time results in Appendix D.5.

W2: The framework depends on the choice of graph kernel to compute influence scores. It is unclear how to select or learn the best kernel for a given task.

A: Our method currently employs the tail-up model, which is well-suited for directed flow networks with upstream–downstream relationships. While this choice is task-specific, we emphasize that the STACI framework is modular: the topology-induced covariance matrix $\hat{\Sigma}_{\mathcal{G}}$ can in principle be replaced by any other graph-based kernel or learned spatial structure. It is an interesting research direction to explore data-driven alternatives, such as graph diffusion kernels or attention-based learned structures.

W3: The experiments lack ablation on the major components of the framework.

A: We agree that ablation is important and have provided relevant experiments in both the main paper and appendix (e.g., Figure 3), where we vary the reliance on the graph-induced covariance via the mixing parameter $\lambda \in [0, 1]$ . These results demonstrate that the topology-aware component improves coverage and stability, particularly under limited calibration samples. Additionally, we study the effect of adaptive conformal inference (ACI) by varying $\gamma$ and show how its interaction with the graph structure affects both coverage and efficiency. We will revise the manuscript to make this connection more explicit and clarify which components are responsible for observed gains.

Once again, we thank the reviewer for the comments and positive assessment of the technical contribution, theoretical guarantees, and practical motivation of our framework.