Time-Conditioned Dances with Simplicial Complexes: Zigzag Filtration Curve based Supra-Hodge Convolution Networks for Time-series Forecasting

Yuzhou Chen, Yulia Gel, H. Vincent PoorNeurIPS 2022 · OpenReview

Abstract / TL;DR Graph neural networks (GNNs) have become a go-to tool for multivariate time-series forecasting in domains ranging from traffic monitoring to financial analytics. However, most existing GNNs are limited to capturing simple pairwise relationships and often ignore how the underlying network topology evolves over time. To address these blind spots, researchers introduce ZFC-SHCN (Zigzag Filtration Curve based Supra-Hodge Convolution Networks). This novel architecture leverages algebraic topology to model higher-order interactions and track dynamic structural shifts, achieving state-of-the-art accuracy with high computational efficiency.

The Blind Spots of Current GNNs

Most current GNNs used for forecasting suffer from two major limitations:

  1. The Pairwise Limitation: They primarily focus on dyadic (node-to-node) relationships. In reality, many systems involve "polyadic" interactions where groups of three or more entities influence each other simultaneously—such as a cluster of traffic sensors or a basket of correlated financial assets.
  2. Static Topology: They often treat the underlying graph as static, failing to capture how the "shape" or connectivity of the data changes over time.

While Topological Data Analysis (TDA) offers tools like "zigzag persistence" to track these structural changes, these methods have historically been too computationally expensive or complex to integrate seamlessly into deep learning pipelines.

A Topological Approach: Methods and Innovations

The researchers bridge this gap with two primary methodological innovations:

1. Zigzag Filtration Curve (ZFC)

In TDA, zigzag persistence tracks how topological features (like loops or voids in the data) appear and disappear as you move through a sequence of time steps.

Zigzag Filtration Sequence

The ZFC is a new, computationally efficient summary of this process. It converts complex topological "birth and death" events into a stable, vector-based representation that a neural network can easily process. By using "filtration curves" instead of memory-intensive "persistence images," the authors achieve robust results with significantly lower computational overhead.

2. Supra-Hodge Convolution

To handle higher-order interactions, the authors move beyond standard graph Laplacians to Hodge Laplacians. This allows the model to perform convolutions on simplices (edges, triangles, etc.) rather than just individual nodes. They utilize a "multiplex" graph representation—essentially stacking graphs from different time steps—to allow information to diffuse across both space and time simultaneously.

These topological and higher-order features are ultimately combined and fed into a Gated Recurrent Unit (GRU) to produce the final forecast.

Key Insights and Results

The model was validated on a diverse range of datasets, including California highway traffic (PeMSD4/8), COVID-19 hospitalizations, Ethereum blockchain token prices, environmental data, and synthetic Vector Autoregression (VAR) data.

Why it works: * Holes are Informative: The "shape" of data—specifically the presence of loops or voids in the network—contains predictive signals that raw values or simple correlations miss. * The Power of the Simplex: By modeling "diffusion over simplices," the network learns the "physics" of the system better. For example, a traffic accident doesn't just affect one road; it impacts a local "complex" of interconnected streets.

Performance: ZFC-SHCN outperformed 14 state-of-the-art baselines (including DCRNN, STGCN, and StemGNN) across nearly all benchmarks.

  • Traffic: Achieved a relative gain in RMSE of 2.06% to 5.63% over the next best models.
  • COVID-19: Showed massive improvements, with relative gains in RMSE ranging from 1.47% to a staggering 65.55% depending on the state.
  • Synthetic Benchmarks: Demonstrated clear superiority on controlled VAR datasets, outperforming even other topological models like Z-GCNETs.
Performance on VAR Datasets

Crucially, the model demonstrated this state-of-the-art performance while requiring fewer computational resources than its closest topological competitors.

Limitations and Future Work

Despite the improvements in efficiency, the computational complexity of TDA remains a challenge for extremely large-scale graphs (e.g., millions of nodes). Furthermore, the theoretical framework for statistical inference on zigzag persistence is still developing.

Looking ahead, the authors suggest extending the ZFC-SHCN framework to anomaly detection in streaming data, where sudden changes in topology could serve as early warning signals for system failures or security breaches.

Summary updated

Abstract

Graph neural networks (GNNs) offer a new powerful alternative for multivariate time series forecasting, demonstrating remarkable success in a variety of spatio-temporal applications, from urban flow monitoring systems to health care informatics to financial analytics. Yet, such GNN models pre-dominantly capture only lower order interactions, that is, pairwise relations among nodes, and also largely ignore intrinsic time-conditioned information on the underlying topology of multivariate time series. To address these limitations, we propose a new time-aware GNN architecture which amplifies the power of the recently emerged simplicial neural networks with a time-conditioned topological knowledge representation in a form of zigzag persistence. That is, our new approach, Zigzag Filtration Curve based Supra-Hodge Convolution Networks (ZFC-SHCN) is built upon the two main components: (i) a new highly computationally efficient zigzag persistence curve which allows us to systematically encode time-conditioned topological information, and (ii) a new temporal multiplex graph representation module for learning higher-order network interactions. We discuss theoretical properties of the proposed time-conditioned topological knowledge representation and extensively validate the new time-aware ZFC-SHCN model in conjunction with time series forecasting on a broad range of synthetic and real-world datasets: traffic flows, COVID-19 biosurveillance, Ethereum blockchain, surface air temperature, wind energy, and vector autoregressions. Our experiments demonstrate that the ZFC-SHCN achieves the state-of-the-art performance with lower requirements on computational costs.
BibTeX
@inproceedings{chen2022time,
  author = {Yuzhou Chen and Yulia Gel and H. Vincent Poor},
  title = {{Time-Conditioned Dances with Simplicial Complexes: Zigzag Filtration Curve based Supra-Hodge Convolution Networks for Time-series Forecasting}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=2Ln-TWxVtf},
}
Figure