Delving into Non-Exchangeability for Conformal Prediction in Graph-Structured Multivariate Time Series

Point forecasting for graph-structured multivariate time series is a fundamental problem, but rigorous uncertainty quantification for such predictions is still underexplored. Conformal prediction (CP) offers uncertainty estimation with a solid coverage guarantee under the exchangeability assumption, which requires the joint data distribution to be unchanged under permutation. However, in graph-structured time series, inherent cross-node coupling can violate the exchangeability condition, making direct application of CP unreliable. Inspired by the spectral graph theory, such coupling resides in global trends and can be characterized by the low-frequency components, while high-frequency components are nearly exchangeable. Therefore, we propose a novel concept named Spectral Graph Conditional Exchangeability (SGCE), which conditions exchangeable high-frequency components on low-frequency ones to preserve global trends and enable effective CP in the spectral domain. Based on SGCE, we further propose Spectral Conformal prediction via wAveLEt transform (SCALE). SCALE uses graph wavelets to decompose low/high-frequency components and conformalizes high-frequency residuals via adaptive gating over a low-frequency embedding. Experimental results on real-world benchmark datasets across multiple application domains show that SCALE not only achieves valid coverage but also consistently improves the coverage-efficiency trade-off over the state-of-the-art CP methods.

Many real-world systems, such as traffic networks, power grids, and environmental monitoring systems, are made up of many connected sensors or locations whose values change over time. Forecasting these systems is important, but a single predicted value is often not enough: users also need to know how uncertain the prediction is. This is difficult because connected locations can strongly influence each other, which can make standard uncertainty estimation methods unreliable. This paper studies why this difficulty occurs in graph-structured time series and proposes a new method called SCALE. The key idea is to separate the data into broad global trends and more local fluctuations using graph wavelets. The global trends help describe the overall behavior of the system, while the local fluctuations are easier to calibrate for reliable uncertainty estimates. By combining these two types of information, SCALE builds prediction intervals that are both reliable and not unnecessarily wide. Experiments on traffic, air quality, electricity, and climate datasets show that SCALE provides valid uncertainty estimates and improves the balance between coverage and interval width compared with existing methods.