How to Break It Down for Building It Up? Theory-Guided Graph Decomposition Learning for Spatiotemporal Traffic Prediction.

Abstract

Traffic state prediction based on spatiotemporal data has become a prominent focus in data-driven AI research. While significant progress has been made, most mainstream approaches assume uniform spatial and temporal correlations across conditions and use shared parameters for all scenarios. This simplification overlooks the complexity and heterogeneity inherent in human mobility patterns, often leading to suboptimal predictions. Recently, methods adopting the "decompose, then predict" (DTP) paradigm have gained traction. These methods break down data into smaller, manageable subcomponents, each predicted using dedicated parameters. Although effective in practice, DTP methods face unresolved theoretical questions: What type of decomposition truly makes subcomponents more manageable than the original data? To address this, we present an information theory-based analysis that derives sufficient conditions for a decomposition algorithm to reduce data-induced prediction errors. These conditions suggest that an effective algorithm should ensure decomposed components are as independent as possible, a principle we term the Component Independence Principle. Guided by this principle, we introduce the Theory-guided Graph Decomposition Learning (TGDL) framework, which decomposes graph-based multivariate time series data into approximately independent subgraph components that are easier to predict than the original data. Moreover, TGDL is a portable framework that can be integrated into any graph-based traffic prediction model to improve its predictive performance. Extensive experiments on four public datasets demonstrate the effectiveness of our approach. With a solid theoretical foundation, our TGDL enhances the performance of diverse traffic prediction models, yielding an average improvement of 19.37% across experiments.