Sparse Graph Learning from Spatiotemporal Time Series
Authors: Andrea Cini, Daniele Zambon, Cesare Alippi; Journal: 24(242):1−36, 2023.
Abstract
Graph neural networks have shown remarkable success in analyzing spatiotemporal time series. These networks leverage relational constraints to enhance the performance of neural forecasting architectures. However, in many cases, the relational information that characterizes the data-generation process is unavailable. This poses a challenge of inferring the appropriate relational graph from the data for subsequent processing stages. To address this, we propose novel and practical probabilistic score-based methods that learn the relational dependencies as distributions over graphs, while optimizing the overall task performance. Our graph learning framework is grounded in theoretical foundations and utilizes variance reduction techniques for Monte Carlo score-based gradient estimation. We demonstrate the effectiveness of our approach in the context of time series forecasting. By tailoring the gradient estimators to the graph learning problem, we achieve state-of-the-art performance while controlling the sparsity of the learned graph and ensuring computational scalability. We evaluate the proposed method on synthetic and real-world benchmarks, highlighting its utility as both a stand-alone graph identification procedure and a graph learning component within an end-to-end forecasting architecture.
[abs]