PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-based Time Series Clustering for End-to-End Hierarchical Forecasting

Andrea Cini, Danilo Mandic, Cesare Alippi

arXiv:2305.19183v2cs.LGcs.AI

TL;DR

Graph-based forecasting has explored relational structure and hierarchical constraints, but their combination with learnable pooling remains underexplored. HiGP integrates graph message passing, pooling, and forecast reconciliation, and the paper reports favorable benchmark performance and meaningful learned clusters.

  • Problem

    Graph-based forecasting methods process inputs at a single spatial resolution, while learnable pooling and the combination of hierarchical and relational constraints remain underexplored.

    Source: §1 · p. 1

  • Method

    HiGP combines graph message passing and trainable pooling to learn hierarchical clusters from data, with a differentiable reconciliation stage enforcing aggregation constraints.

    Source: §1 · pp. 1–2

  • Results

    HiGP is reported to achieve state-of-the-art forecasting accuracy on relevant benchmarks and to learn meaningful hierarchical cluster assignments.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    In the considered settings, hierarchical forecasting provides self-supervision for cluster learning and is associated with improved accuracy over flat architectures on average.

    Source: §5.1 · p. 8

    The reconciliation solution requires O(M^3) space and O(M^2) time, which can be prohibitive for large series collections, though it remains practical for up to a few thousand nodes.

    Source: §3.3 · p. 6

Abstract

from arXiv · show

Relationships among time series can be exploited as inductive biases in learning effective forecasting models. In hierarchical time series, relationships among subsets of sequences induce hard constraints (hierarchical inductive biases) on the predicted values. In this paper, we propose a graph-based methodology to unify relational and hierarchical inductive biases in the context of deep learning for time series forecasting. In particular, we model both types of relationships as dependencies in a pyramidal graph structure, with each pyramidal layer corresponding to a level of the hierarchy. By exploiting modern - trainable - graph pooling operators we show that the hierarchical structure, if not available as a prior, can be learned directly from data, thus obtaining cluster assignments aligned with the forecasting objective. A differentiable reconciliation stage is incorporated into the processing architecture, allowing hierarchical constraints to act both as an architectural bias as well as a regularization element for predictions. Simulation results on representative datasets show that the proposed method compares favorably against the state of the art.

1. Introduction

The paper targets the underexplored combination of hierarchical and relational inductive biases in graph-based forecasting. It proposes HiGP, which learns hierarchical structure from data and is reported to achieve state-of-the-art accuracy on relevant benchmarks.

1. Introduction

  • Hierarchical forecasting combines forecasts across levels under aggregation constraints, and related cluster-based methods predict aggregates as an intermediate step toward a total forecast.The cited discussion links forecast combination with reduced variance and describes forecast reconciliation as a special case of forecast combinations.Source: §1 · p. 1
  • The paper identifies an open gap in combining learnable graph pooling with hierarchical constraints, while existing graph-based forecasting methods process inputs at a single spatial resolution.Single-resolution processing might cause propagation bottlenecks and oversmoothing.Source: §1 · p. 1
  • HiGP combines graph pooling and neural message passing to process series at multiple spatial resolutions while embedding hierarchical and relational structures as inductive biases.The approach propagates representations through the hierarchy and enforces prediction coherence with aggregation constraints.Source: §1 · pp. 1–2
  • The paper’s contributions include learning a hierarchical structure by clustering input series and integrating that procedure into an end-to-end forecasting model.The proposed framework embeds hierarchical constraints as inductive biases in graph-based forecasting architectures.Source: §1 · p. 2
  • HiGP achieves state-of-the-art forecasting accuracy on relevant benchmarks and can learn meaningful cluster assignments.The framework is also presented as a self-supervised architecture for learning those assignments.Source: §1 · p. 2

2. Preliminaries

The preliminaries define hierarchical series as raw sequences augmented with progressively aggregated levels and describe the coherence constraints on forecasts. They also set up forecasting for spatially correlated series represented by a graph, using temporal encoding followed by message passing.

2. Preliminaries

  • The forecasting setting uses a weighted adjacency matrix that is constant over time and assumes homogeneous sensors and static topology; the target is point forecasting over an H-step horizon.The passage describes extensions beyond these settings as outside the paper’s scope.Source: §2 · p. 2
  • The reference spatiotemporal graph neural network encodes each input series temporally, then applies message-passing layers over graph neighbors before decoding predictions.The message and update functions can be implemented with MLPs, and sequence encoding may use an RNN.Source: §2 · p. 2
  • A hierarchy augments raw time series with progressively aggregated levels, and an aggregation matrix encodes the constraints linking aggregates to bottom-level observations.A forecast is coherent when it satisfies the corresponding equality constraints.Source: §2 · p. 3

3. Graph-based Hierarchical Clustering and Forecasting

The section develops a graph-based hierarchical forecasting architecture, then describes learning its hierarchy from data and reconciling forecasts to satisfy hierarchical constraints.

3.1. Graph-based Hierarchical Forecasting

  • SRC operators build a pyramidal graph that propagates information within and across hierarchy levels, while pooling lets coarser representations capture broader spatial-scale patterns.Selection maps nodes to supernodes, reduction aggregates features, and connection rewires the graph between levels.Source: §3.1 · pp. 3–4

3.2. End-to-end Clustering and Forecasting

  • HiGP learns cluster assignments through a differentiable selection operator, training clusters to improve forecasting of both bottom-level series and aggregates.A graph-based min-cut regularizer favors pooling connected nodes and discourages degenerate assignments; alternative pooling operators are also compatible.Source: §3.2 · pp. 4–5

3.3. Forecast Reconciliation

  • A differentiable projection reconciles raw predictions into coherent forecasts, with an additional loss penalizing distance from the coherent-forecast space.Computing the projection can be prohibitive for large collections; the regularization term alone is offered as an alternative, while the projection remains practical for up to a few thousand nodes.Source: §3.3 · pp. 5–6

4. Related Work

Prior work addresses hierarchical forecasting, graph forecasting, and graph pooling, but the cited approaches leave a gap around jointly learning hierarchical clusters for forecasting with relational dependencies and coherence constraints.

Hierarchical forecasting

  • Standard hierarchical forecasting reconciles forecasts in a separate stage, while deep-learning methods use hierarchical structure as a hard or soft constraint; these methods do not consider relational dependencies across hierarchy levels.Differentiable reconciliation has also been incorporated into neural architectures, including for probabilistic forecasts.Source: §4 · p. 6

Graph-based forecasting and graph pooling

  • Graph pooling methods include trainable dense or sparse assignments and non-trainable topology-based clustering, but their application to time-series data is described as underexplored.Prior hierarchical graph approaches include pyramidal architectures and domain-specific temporal hierarchies.Source: §4 · p. 6
  • The cited prior methods mostly use fixed cluster assignments and do not jointly optimize forecasts at every hierarchy level while accounting for coherence constraints.Source: §4 · p. 6

5. Experiments

Across the evaluated settings, HiGP variants are among the best-performing methods, and hierarchical forecasting improves average accuracy over flat architectures. HiGP also learns meaningful clusters whose aggregates become progressively smoother across hierarchy levels.

5.1. End-to-end Hierarchical Clustering and Forecasting

  • The evaluation covers four graph-connected benchmark datasets without predefined hierarchies, using multistep-ahead forecasting and MAE and MRE metrics.The benchmarks include Metr-LA and PeMS-Bay traffic data, AQI air-quality measurements, and CER-E energy profiles.Source: §5.1 · pp. 6–7
  • HiGP variants are among the best-performing methods in all considered settings, with hierarchical forecasting improving average accuracy over flat architectures.The GUNet hierarchical message-passing baseline underperforms in these comparisons.Source: Table 1 · p. 7, §5.1 · pp. 7–8
  • HiGP adds hierarchical propagation and level-specific readouts to the baseline template, learning a three-level structure with 20 middle-level supernodes and one top-level aggregate.The selection matrices are learned from trainable log-probability parameters.Source: §5.1 · p. 7
  • Removing either message-passing layers or propagation through the learned hierarchy significantly affects forecasting accuracy on the traffic datasets.The HiGP traffic-dataset results also report state-of-the-art forecasting accuracy.Source: §5.1 · p. 8

5.2. Cluster Analysis

  • HiGP learns meaningful clusters in both scenarios through end-to-end forecasting-error minimization at each hierarchy level, with aggregates exhibiting different patterns and progressively smoother dynamics at higher levels.Figure 3 uses models trained with a 5-level hierarchy and shows medians for levels 1–3; shaded areas correspond to 0.6 and 0.4 quantiles.Source: Figure 3 · p. 8, §5.2 · p. 9

6. Conclusions

The conclusions present HiGP as a framework that unifies relational and hierarchical inductive biases and learns hard cluster assignments end-to-end. The authors identify extensions to the clustering objectives, reconciliation strategies, data settings, and scale as future work.

6. Conclusions

  • HiGP unifies relational and hierarchical inductive biases and learns hard cluster assignments by minimizing forecasting error for aggregates and bottom-level series.The paper reports benchmark performance and meaningful learned hierarchical assignments as support for the approach.Source: §6 · p. 9
  • Future work includes auxiliary clustering objectives, alternative reconciliation strategies, predefined hierarchies, sensitivity to dataset size, and multivariate, heterogeneous, or irregularly sampled series.The authors note that graph-based forecasting often uses more time series than standard hierarchical forecasting benchmarks.Source: §6 · p. 9

Appendix

  • The appendix provides additional experimental setup, dataset details, and empirical results..Source: Appendix · p. 13

A. Hardware and software platforms

  • The experimental setup and baselines were developed with Python and relied on open-source libraries including NumPy, PyTorch, PyTorch Lightning, PyTorch Geometric, and Torch Spatiotemporal.Source: A. Hardware and software platforms · p. 13

B. Datasets

The experiments use four datasets covering traffic, energy consumption, and air quality, with graph information and dataset-specific forecasting windows. The appendix identifies the dataset sources and reports that the datasets are open or available free for research.

B. Datasets

  • The spatiotemporal forecasting benchmarks include Metr-LA loop-detector measurements from Los Angeles County, PeMS-Bay traffic-speed measurements, CER-E energy-load profiles, and AQI hourly PM2.5 measurements.CER-E consumption measurements are aggregated into 30-minute intervals and recorded by 485 smart meters in Irish small and medium-sized enterprises.Source: B. Datasets · p. 13
  • The datasets are openly available or obtainable free of charge for research, and the experiments derive adjacency matrices and exogenous variables following prior work.Table 3 provides dataset statistics.Source: B. Datasets · p. 13, Table 3 · p. 13
  • Input-window and forecast-horizon lengths are Metr-LA and PeMS-Bay W = 12 and H = 12, CER-E W = 48 and H = 6, and AQI W = 24 and H = 3.Training, validation, and testing use a sequential 70%/10%/20% split, except AQI, which follows the splits of Yi et al. (2016).Source: B. Datasets · p. 14

C.1. Reference architectures

The reference architecture is a time-then-space forecasting template whose recurrent encoder is followed by graph message passing and a forecasting readout. HiGP and GUNet modify the template for hierarchical processing, while the tuned HiGP adds skip connections and a deeper readout.

C.1. Reference architectures

  • The reference template uses a recurrent temporal encoder, two graph neural network layers, and an MLP readout for forecasting.Its learnable weights and biases are described alongside the GRU and generic message-passing layers.Source: §C.1 · p. 14
  • HiGP modifies the template to account for hierarchy, while GUNet adds pooling and lifting operations.The tuned HiGP version adds skip connections and uses a deeper readout.Source: §C.1 · p. 14

C.2. Hyperparameters and training details

The experiments use validation-based early stopping, dataset-specific model settings, and a three-level hierarchy for HiGP.

C.2. Hyperparameters and training details

  • Models used validation-based early stopping, batch size 64, and at most 200 epochs of up to 300 batches each.Adam started at learning rate 0.003, reduced by a factor of 0.25 every 50 epochs.Source: §C.2 · p. 14
  • Hidden-layer widths were set to 64 or 32 based on validation error, while HiGP’s regularization coefficient was tuned on Metr-LA and rescaled for other datasets.HiGP used λ = 0.25 on Metr-LA; HiGP (T) was tuned separately on each dataset’s validation set.Source: §C.2 · p. 14
  • HiGP used a three-level hierarchy with 20 middle-level super-nodes and one top-level total aggregate, with spatial propagation only at the base level.Diff-TTS used diffusion order k = 2 and GUNet used pooling factor p = 0.1.Source: §C.2 · p. 14

D. Additional results

Sensitivity analyses examine hierarchy size and reconciliation strategy on CER-E. The results indicate that hierarchy settings should be task-tuned, while reconciliation and hierarchical biases can improve forecasting accuracy.

D.1. Sensitivity analyses

  • A simple three-level hierarchy with few clusters consistently outperformed flat predictors, although hierarchy size should be tuned to the task.The sensitivity analysis used a simplified model with 32 hidden units on CER-E; Table 4 compares cluster configurations by MAE over four runs.Source: §D.1 · p. 14, Table 4 · p. 15
  • The reconciliation comparison evaluates Reconciled, Only loss, and Fit only base; results support accuracy gains from reconciliation and hierarchical biases.Table 5 compares reconciliation strategies by MAE on CER-E over four runs; the passage does not provide specific cell values.Source: §D.1 · pp. 14–15, Table 5 · p. 15

D.2. Cluster analysis

The Air Quality cluster visualization shows sensor locations, network partitions, and the pooled graph at the hierarchy’s first level.

D.2. Cluster analysis

  • The Air Quality visualization maps sensor locations and cluster partitions, alongside the pooled graph for the hierarchy’s first level.Figure 4 provides a complementary visualization of learned clusters in the AQI dataset.Source: §D.2 · p. 15, Figure 4 · p. 15

Related papers

Loading 2305.19183v2…