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

arXiv: https://arxiv.org/abs/2605.04957 · HTML: https://mlsanity.com/paper/2605.04957/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 45 references that are in the map.
- First posted on arXiv 6 May 2026.

## Builds on (most cited first, 26 of 26)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [GMAN: A Graph Multi-Attention Network for Traffic Prediction](https://mlsanity.com/paper/1911.08415/) (2019)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Spatial-Temporal Identity: A Simple yet Effective Baseline for Multivariate Time Series Forecasting](https://mlsanity.com/paper/2208.05233/) (2022)
- [A Survey on Graph Neural Networks for Time Series: Forecasting, Classification, Imputation, and Anomaly Detection](https://mlsanity.com/paper/2307.03759/) (2023)
- [Exploring Progress in Multivariate Time Series Forecasting: Comprehensive Benchmarking and Heterogeneity Analysis](https://mlsanity.com/paper/2310.06119/) (2023)
- [Sequential Predictive Conformal Inference for Time Series](https://mlsanity.com/paper/2212.03463/) (2022)
- [Conformal prediction for time series](https://mlsanity.com/paper/2010.09107/) (2020)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Conformal Prediction for Deep Classifier via Label Ranking](https://mlsanity.com/paper/2310.06430/) (2023)
- [Conformal Prediction for Time Series with Modern Hopfield Networks](https://mlsanity.com/paper/2303.12783/) (2023)
- [Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks](https://mlsanity.com/paper/2107.10234/) (2021)
- [Error-quantified Conformal Inference for Time Series](https://mlsanity.com/paper/2502.00818/) (2025)
- [Relational Conformal Prediction for Correlated Time Series](https://mlsanity.com/paper/2502.09443/) (2025)
- [Verifying the Smoothness of Graph Signals: A Graph Signal Processing Approach](https://mlsanity.com/paper/2305.19618/) (2023)
- [Short-Term Electricity-Load Forecasting by Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2408.16202/) (2024)
- [Exploring the Noise Robustness of Online Conformal Prediction](https://mlsanity.com/paper/2501.18363/) (2025)
- [Neural Conformal Control for Time Series Forecasting](https://mlsanity.com/paper/2412.18144/) (2024)
- [Non-exchangeable Conformal Prediction for Temporal Graph Neural Networks](https://mlsanity.com/paper/2507.02151/) (2025)

## Abstract (arXiv)

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 traffic datasets 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.