PaperlayerView exact revision on arXiv

Source-linked AI summary

Z-GCNETs: Time Zigzags at Graph Convolutional Networks for Time Series Forecasting

Yuzhou Chen, Ignacio Segovia-Dominguez, Yulia R. Gel

arXiv:2105.04100v1cs.LGstat.ML

TL;DR

The paper addresses limited integration of time and topological information in deep learning for dynamic, interdependent data. It introduces zigzag persistence images and a time-aware zigzag layer for GCNs, and reports that Z-GCNETs outperform 13 state-of-the-art methods on 4 datasets while improving forecasting performance and robustness.

  • Problem

    Most deep-learning architectures are static and do not systematically integrate time, while time-conditioned topological information remains insufficiently integrated into deep learning.

  • Method

    The paper introduces zigzag persistence, zigzag persistence images, and a learnable time-aware zigzag topological layer integrated into graph convolutional networks.

  • Results

    Z-GCNETs surpass 13 state-of-the-art methods on 4 benchmark datasets spanning traffic forecasting and Ethereum blockchain price prediction, with enhanced forecasting performance and robustness gains.

  • Takeaways & Limitations

    Time-aware zigzag topological information can be integrated into GCNs for spatio-temporal graph-structured forecasting tasks.

Abstract

from arXiv · show

There recently has been a surge of interest in developing a new class of deep learning (DL) architectures that integrate an explicit time dimension as a fundamental building block of learning and representation mechanisms. In turn, many recent results show that topological descriptors of the observed data, encoding information on the shape of the dataset in a topological space at different scales, that is, persistent homology of the data, may contain important complementary information, improving both performance and robustness of DL. As convergence of these two emerging ideas, we propose to enhance DL architectures with the most salient time-conditioned topological information of the data and introduce the concept of zigzag persistence into time-aware graph convolutional networks (GCNs). Zigzag persistence provides a systematic and mathematically rigorous framework to track the most important topological features of the observed data that tend to manifest themselves over time. To integrate the extracted time-conditioned topological descriptors into DL, we develop a new topological summary, zigzag persistence image, and derive its theoretical stability guarantees. We validate the new GCNs with a time-aware zigzag topological layer (Z-GCNETs), in application to traffic forecasting and Ethereum blockchain price prediction. Our results indicate that Z-GCNET outperforms 13 state-of-the-art methods on 4 time series datasets.

1. Introduction

The paper targets the gap between dynamic phenomena and largely static deep-learning architectures by combining time-conditioned topological representations with graph convolution. It introduces zigzag persistence images and a time-aware zigzag layer, with experiments reporting gains over established methods.

  • Most existing deep-learning architectures do not systematically integrate time into learning, limiting their ability to capture salient time-conditioned characteristics of complex interdependent systems.
  • Zigzag persistence tracks salient topological features through time-ordered inclusions, including inclusions that proceed in both directions.
  • The paper’s first contribution is bridging time-conditioned deep learning with time-aware persistent-homology representations of data.
  • The authors propose zigzag persistence images as a vectorized summary of time-aware persistence and discuss their theoretical stability guarantees.
  • Z-GCNET introduces time-aware zigzag persistence into graph convolutional networks as a learnable topological layer for time-conditioned graph structures.
  • Z-GCNET surpasses 13 state-of-the-art methods on 4 benchmark datasets in traffic forecasting and Ethereum blockchain price prediction, in accuracy and robustness.

2. Related Work

Related work spans zigzag persistence applications, recurrent approaches to time series, and graph convolutional networks for non-Euclidean data. These strands motivate combining temporal modeling, graph structure, and topological representations.

  • Zigzag persistence has been applied to brain sciences, imagery classification, mobile-sensor-network cybersecurity, and biological flocking and swarming behavior.
  • RNNs, including LSTMs and GRUs, are natural methods for time-dependent datasets and can selectively learn historical patterns.
  • RNN applications are limited because these architectures are not designed for data from non-Euclidean spaces such as graphs and manifolds.
  • GCNs address graph-structured data by extracting neighbor-edge characteristics and aggregating neighborhood features through graph filters.

3. Time-Aware Topological Signatures of Graphs

The method represents evolving spatial-temporal networks as graph snapshots and extends persistent-homology analysis with zigzag persistence to track topological features across time. These features are summarized as stable, finite-dimensional zigzag persistence images for input to graph neural networks.

  • Spatio-temporal Data as Graph Structures: Spatial-temporal data are modeled as a sequence of graph snapshots G_t = {V, E_t, W_t}, with time-varying edges and weights.Each snapshot shares a node set while its connectivity and weights may change over time.
  • Persistent Homology: Persistent homology tracks structural features such as connected components, cycles, and voids across graph filtrations using birth and death parameters.Features with longer lifespans are treated as more likely to contain important structural information.
  • Time-Aware Zigzag Persistence: Zigzag persistence generalizes persistent homology to time-ordered networks connected by inclusions in both directions, enabling topological features to be tracked across changing graphs.The construction uses unions of consecutive graphs and a fixed scale parameter to build a zigzag diagram of simplicial complexes.
  • Time-Aware Zigzag Persistence: A zigzag persistence diagram records when each topological feature is born and dies, including half-time points arising in unions of consecutive snapshots.For a fixed scale ν*, the diagram is a multiset of birth-death points in R2.
  • Zigzag Persistence Images: Zigzag persistence images convert these diagrams into finite-dimensional matrix representations for input to graph neural networks.The pipeline forms a weighted Gaussian persistence surface, discretizes it on a grid, and integrates over grid boxes to obtain pixel values.
  • Zigzag Persistence Images: Zigzag persistence images are theoretically stable with respect to the Wasserstein-1 distance between zigzag persistence diagrams.The stability result applies for a non-negative, continuous, piece-wise differentiable weighting function.

4. Z-GCNETs

Z-GCNETs forecasts multivariate graph time series by combining spatial, temporal, and zigzag-topological representations. It processes sliding-window graph signals and persistence images through graph convolutions, CNN pooling, and GRU forecasting.

  • Forecasting framework: Z-GCNETs maps τ past graph-signal snapshots to future data over horizon h for multi-step forecasting.The input window contains graph signals with N nodes and F node features.
  • Graph convolutions: The model uses a self-adaptive Laplacian and stacked positive powers to aggregate information from neighborhoods at different depths.The Laplacian is constructed from trainable node embeddings, while the power series supports diffusion across multiple spatial levels.
  • Graph convolutions: Spatial graph convolution multiplies layer inputs by the linked Laplacian and applies a factorized trainable projection with shared node embeddings.Weight sharing is used to reduce over-fitting risk and computational complexity.
  • Topological integration: Z-GCNETs integrates structural, temporal, and topological information in the GRU forecasting pipeline.The architecture combines the representations before recurrent prediction.
  • Temporal convolution: The temporal graph convolution uses the entire sliding window to capture temporal correlations without selecting a nested window size.The authors state that long windows capture temporal patterns more effectively than potentially biased or noisy short windows.
  • Topological integration: The time-aware zigzag topological layer learns ZPI features with CNNs, pools them globally, and combines them with spatial and temporal graph-convolution representations.Its output is passed to a GRU, whose update and reset gates support forecasting from the combined representation.

5. Experiments

The experiments evaluate Z-GCNETs on traffic and Ethereum token-network forecasting with multiple dataset splits, horizons, and baselines. The study also examines computation cost and filtration choices.

  • Datasets: The evaluation covers PeMSD4, PeMSD8, Bytom, and Decentraland, representing traffic and Ethereum token networks.Traffic data are aggregated at five-minute intervals, while token networks use daily transactions.
  • Evaluation design: Z-GCNETs is compared with 13 state-of-the-art baselines across four time-series datasets.The baselines include statistical models, recurrent networks, self-attention, spatial-temporal GCNs, and GRU-based GCNs.
  • Experimental settings: Traffic experiments use chronological 60%/20%/20% train-validation-test splits with window size τ = 12 and horizon h = 12.The traffic model uses two layers with 64 hidden units per layer.
  • Experimental settings: Ethereum experiments use 80% training and 20% test data, with one week of history predicting the next week.The token-network model uses τ = 7 and h = 7, and reported results use weight rank clique filtration.

5.3. Comparison with the Baseline Methods

Z-GCNETs consistently outperform state-of-the-art baselines across traffic and Ethereum token forecasting, while ablations show value from their topological, spatial, and temporal components.

  • Baseline comparison: Z-GCNETs consistently outperform state-of-the-art methods on PeMSD4 and PeMSD8 using MAE, RMSE, and MAPE.RMSE gains over the next most accurate methods range from 0.44% to 2.06%.
  • Baseline comparison: 3.42% and 2.94% RMSE margins separate weight-rank-clique Z-GCNETs from AGCRN on Bytom and Decentraland, respectively.
  • Ablation study: Removing zigzag learning, spatial graph convolution, or temporal graph convolution reduces performance relative to the complete Z-GCNETs architecture.
  • Ablation study: 6.46% relative RMSE gain on PeMSD4 results when Z-GCNETs retains temporal graph convolution in multi-step forecasting.

PeMSD4

Experiments examine which topological dimensions and threshold settings matter for Z-GCNETs under dynamic-network and noisy-data conditions.

  • Topological features: 1-dimensional topological features consistently outperform 0-dimensional features on PeMSD4 and PeMSD8 under the same ν∗ scale.
  • Threshold sensitivity: PeMSD4 forecasting results are not significantly affected by varying ν∗.
  • Noise robustness: Robustness is assessed by adding zero-mean i.i.d. Gaussian noise with variance ς^2 to 30% of the training sets.The evaluated noise levels use ς ∈ {2, 4}.

6. Conclusion

The conclusion presents Z-GCNETs as a time-aware GCN layer that tracks persistent topological characteristics across time. Experiments indicate improved forecasting performance and robustness on spatio-temporal graph data.

  • Contribution: Z-GCNETs introduces a time-aware zigzag topological layer for time-conditioned graph convolutional networks.
  • Contribution: The layer tracks salient time-aware topological characterizations of data that persist over time.
  • Conclusion: Integrating the layer into GCNs results in enhanced forecasting performance and substantial robustness gains on spatio-temporal graph-structured data.

A. Additional Experimental Settings

The experiments use dataset-specific optimization, graph-link, batch-size, and training settings for transportation and Ethereum token networks.

  • Optimization: PeMSD4 and PeMSD8 use Adam with initial learning rate 0.003 and decay rate ρ = 0.3.
  • Optimization: Bytom and Decentraland use learning rate 0.001 and decay rate ρ = 0.1.
  • Network settings: The Laplacianlink length is 2 for transportation networks and 3 for token networks.
  • Training settings: Batch sizes are 64 for PeMSD4 and 8 for PeMSD8 and Ethereum token networks.

B. The Choice of Filtration

The study compares three zigzag filtrations and finds that filtration choice matters more for heterogeneous dynamic graphs than for sparse graphs. Power filtration performs best for Decentraland.

  • The experiments compare weight rank clique, power, and weighted-degree sublevel filtrations on Ethereum token networks.Table 8 reports MAPE results for different zigzag filtrations.
  • For sparse graphs such as Bytom, the three filtrations produce similar results.
  • Power filtration is the winner for the more heterogeneous Decentraland graph.The passage attributes this to better capture of its richer topological structure over time.

C. Ablation study on Ethereum token networks

An ablation study on Bytom and Decentraland evaluates the contributions of zigzag persistence representation learning, spatial graph convolution, and temporal graph convolution. The complete Z-GCNETs model outperforms versions without each of these components.

  • The ablation study evaluates Z-GCNETs on the Bytom and Decentraland Ethereum token networks.Table 9 summarizes the ablation results using MAPE.
  • Z-GCNETs outperforms the model without zigzag persistence representation learning.
  • Z-GCNETs outperforms models without spatial or temporal graph convolution.The compared variants are GCNSpatial and GCNTemporal.
Loading 2105.04100v1…