PaperlayerView exact revision on arXiv

Source-linked AI summary

ST-UNet: A Spatio-Temporal U-Network for Graph-structured Time Series Modeling

Bing Yu, Haoteng Yin, Zhanxing Zhu

arXiv:1903.05631v2cs.LGstat.ML

TL;DR

Spatio-temporal graphs are important in dynamic settings, yet their irregular structure complicates simultaneous modeling of spatial properties and temporal patterns. ST-UNet uses a U-shaped multi-scale architecture with paired spatio-temporal pooling and unpooling. Across several real-world datasets, it consistently outperforms other state-of-the-art methods on spatio-temporal prediction tasks.

  • Problem

    Spatio-temporal graphs have irregular structure, and conventional convolutional or recurrent models are limited in capturing their spatial properties and temporal patterns together.

    Source: §1 · pp. 1–2

  • Method

    ST-UNet combines multi-granularity graph convolution and dilated recurrent skip connections with paired spatio-temporal pooling and unpooling in a U-shaped network.

    Source: §1 · p. 2, §3.2 · pp. 4–5

  • Results

    Across several real-world datasets, ST-UNet consistently outperforms other state-of-the-art methods on spatio-temporal prediction tasks.

    Source: §4.2 · p. 6, §5 · p. 7

  • Takeaways & Limitations

    The paper reports that ST-UNet balances efficiency and capacity with considerable flexibility for multi-scale graph-sequence modeling.

    Source: §3.4 · p. 5, §5 · p. 7

Abstract

from arXiv · show

The spatio-temporal graph learning is becoming an increasingly important object of graph study. Many application domains involve highly dynamic graphs where temporal information is crucial, e.g. traffic networks and financial transaction graphs. Despite the constant progress made on learning structured data, there is still a lack of effective means to extract dynamic complex features from spatio-temporal structures. Particularly, conventional models such as convolutional networks or recurrent neural networks are incapable of revealing the temporal patterns in short or long terms and exploring the spatial properties in local or global scope from spatio-temporal graphs simultaneously. To tackle this problem, we design a novel multi-scale architecture, Spatio-Temporal U-Net (ST-UNet), for graph-structured time series modeling. In this U-shaped network, a paired sampling operation is proposed in spacetime domain accordingly: the pooling (ST-Pool) coarsens the input graph in spatial from its deterministic partition while abstracts multi-resolution temporal dependencies through dilated recurrent skip connections; based on previous settings in the downsampling, the unpooling (ST-Unpool) restores the original structure of spatio-temporal graphs and resumes regular intervals within graph sequences. Experiments on spatio-temporal prediction tasks demonstrate that our model effectively captures comprehensive features in multiple scales and achieves substantial improvements over mainstream methods on several real-world datasets.

1 INTRODUCTION

Spatio-temporal graphs are dynamic graph sequences, but their irregular structure makes standard grid-based operations difficult to apply. ST-UNet proposes a multi-scale U-shaped model to learn and predict graph-structured time series.

1 INTRODUCTION

  • Dynamic graphs have received less attention than static graphs, although spatio-temporal graphs arise in settings such as traffic sensors and human action sequences.The paper frames its goal as interpreting these graphs and forecasting node values or labels, or predicting the graph over the next few time steps.Source: §1 · p. 1
  • Graph structure lacks the regular-grid alignment and node locality or order assumed by standard convolution and pooling operations.Prior work combines graph convolution with recurrent or convolutional models for tasks including action recognition and traffic prediction.Source: §1 · pp. 1–2
  • Multi-scale analysis is needed to capture local and global properties of dynamic graphs, motivating the use of U-shaped networks.The paper notes that graph pooling is difficult to extend, while U-Net-style designs can represent both local and global information.Source: §1 · p. 2
  • ST-UNet combines multi-granularity graph convolution with dilated recurrent skip connections in a U-shaped architecture.ST-Pool coarsens the graph using deterministic partitions and abstracts temporal dependencies at multiple resolutions; paired ST-Unpool restores graph structure and temporal dependencies, while higher-level features are concatenated with upsampled outputs.Source: §1 · p. 2

2 RELATED WORK

Related work describes spectral graph convolution and structured-sequence models, including graph U-Net. The cited graph U-Net operations are limited to static graphs and may not preserve local spatial relations.

2 RELATED WORK

  • Spectral graph convolution applies a kernel to a graph signal using Fourier coefficients and a truncated Chebyshev expansion on the rescaled Laplacian.The graph Fourier basis is formed from eigenvectors of the normalized graph Laplacian.Source: §2 · p. 2
  • Structured RNN and graph-convolutional recurrent networks model structured sequences, while later studies embed graph convolutions in sequence-learning designs.The cited approaches include node- and edge-specific recurrent networks and replacing regular 2D convolution with spectral graph convolution.Source: §2 · p. 2
  • Graph U-Net extends pooling and upsampling to static graphs, but its pooling learns node selection and does not preserve the input graph structure.The passage notes this may be an issue for tasks where local spatial relations are critical.Source: §2 · p. 2

3 METHODOLOGY

The methodology formulates prediction on spatio-temporal graphs and introduces a U-shaped, multi-scale architecture with paired pooling and unpooling operations.

3.1 Spatio-temporal Graph Modeling

  • Spatio-temporal prediction forecasts a future length-H sequence of node attributes from the previous J observations on a graph.A spatio-temporal graph has node attributes that evolve over time.Source: §3.1 · pp. 2–3

3.2 Pooling Operation on Spatio-temporal Graphs

  • Spatial pooling partitions a graph into supernodes, reducing its size by half per level; the same deterministic partition is applied at each time step.The partition is based on an approximate maximum-weight matching, and pooled features aggregate over the nodes in each partition.Source: §3.2 · p. 4
  • Dilated recurrent skip-connections span skip lengths between recurrent units, adding temporal resolutions and broadening dependencies with fewer parameters and high efficiency.The skip length controls the dilation at each layer.Source: §3.2 · p. 5

3.2 Pooling Operation on Spatio-Temporal Graphs

  • ST-Pool combines spatial feature aggregation over non-overlapping graph partitions with temporal dilation across recurrent units in the same layer.The operation downsamples a spatio-temporal graph across both its spatial and temporal projections.Source: §3.2 · pp. 3, 5

3.3 Spatio-temporal Unpooling Operation

  • ST-Unpool reverses the node mapping and restores regular temporal dependencies by feeding each time-step output into a vanilla recurrent layer.Spatial upsampling may use direct copy, ordered deconvolution, or weighted deconvolution.Source: §3.3 · p. 5

3.4 Architecture of Spatio-Temporal U-Net

  • ST-UNet contracts graph-convolved features through ST-Pool, restores their resolution with ST-Unpool, fuses same-level features, and applies a final graph convolution for prediction.The authors describe the U-shaped, multi-scale design and its paired operators as contributions for graph-structured time series.Source: §3.4 · p. 5

4 EXPERIMENTAL STUDIES

Experiments evaluate ST-UNet on moving-MNIST and traffic prediction, then examine its pooling and unpooling operations and its performance on large graphs.

4.1 Spatio-temporal Sequence Modeling on Moving-MNIST

  • On moving-MNIST, ST-UNet outperforms GCGRU in node-level sequence prediction, as illustrated by the predicted sequences.Figure 2 shows ground truth in the first row, followed by ST-UNet and GCGRU predictions.Source: Figure 2 · p. 6, §4.1 · p. 6

4.2 Graph-structured Time-series Modeling on Traffic Prediction

  • The traffic task uses one hour of observed data to forecast traffic status 15, 30, and 60 minutes ahead on METR-LA and PeMS datasets.The datasets contain traffic records aggregated at five-minute intervals.Source: §4.2 · p. 6

4.3 Ablation Study of ST-Pool & ST-Unpool

  • Ablations show that spatial and temporal pooling and unpooling enhance prediction, with their combined use further improving performance and generalization.The variants remove both operations, use them only temporally, use them only spatially, or use the full model.Source: §4.3 · p. 6

4.4 Comparison Study of Upsampling Approaches in ST-Unpool

  • Direct-copy upsampling generally performs better than the other tested approaches, especially for longer-term prediction.The authors suggest it may be steadier and more robust; local super-node properties may not suffice for complex feature reconstruction.Source: §4.4 · pp. 6–7

4.2 Graph-structured Time-series Modeling on Traffic Prediction

  • ST-UNet achieves the best performance across all three forecasting windows and adopted metrics on METR-LA and PeMS-M.The comparison covers prediction performance across both datasets.Source: §4.2 · p. 6, Table 1 · p. 7

4.5 Scalability and Efficiency Study on Large-scale Graph Data

  • On PeMS-L, ST-UNet achieves a better outcome in less than half the time DCRNN needs, balancing efficiency and prediction accuracy.DCRNN normally takes more than 10 minutes per epoch with batch size 16; PeMS-L contains over one thousand sensor nodes.Source: §4.5 · p. 7

5 CONCLUSION

The conclusion presents ST-UNet as a multi-scale architecture for learning and predicting graph-structured time series, combining graph convolution with dilated recurrent skip-connections.

5 CONCLUSION

  • Experiments show consistent gains over other state-of-the-art methods on several real-world datasets, while the pooling and unpooling operations improve efficiency and balance efficiency with capacity.The paper identifies comprehensive spatio-temporal feature extraction and flexibility as promising for structured sequence modeling.Source: §5 · p. 7

Related papers

Loading 1903.05631v2…