Graph-Time Convolutional Neural Networks: Architecture and Theoretical Analysis

Mohammad Sabbaqi, Elvin Isufi

Abstract

Devising and analyzing learning models for spatiotemporal network data is of importance for tasks including forecasting, anomaly detection, and multi-agent coordination, among others. Graph Convolutional Neural Networks (GCNNs) are an established approach to learn from time-invariant network data. The graph convolution operation offers a principled approach to aggregate multiresolution information. However, extending the convolution principled learning and respective analysis to the spatiotemporal domain is challenging because spatiotemporal data have more intrinsic dependencies. Hence, a higher flexibility to capture jointly the spatial and the temporal dependencies is required to learn meaningful higher-order representations. Here, we leverage product graphs to represent the spatiotemporal dependencies in the data and introduce Graph-Time Convolutional Neural Networks (GTCNNs) as a principled architecture to aid learning. The proposed approach can work with any type of product graph and we also introduce a parametric product graph to learn also the spatiotemporal coupling. The convolution principle further allows a similar mathematical tractability as for GCNNs. In particular, the stability result shows GTCNNs are stable to spatial perturbations but there is an implicit trade-off between discriminability and robustness; i.e., the more complex the model, the less stable. Extensive numerical results on benchmark datasets corroborate our findings and show the GTCNN compares favorably with state-of-the-art solutions. We anticipate the GTCNN to be a starting point for more sophisticated models that achieve good performance but are also fundamentally grounded.

Introduction

Many critical real-world datasets are inherently spatiotemporal, characterized by signals evolving over a network structure through time. Examples include traffic flow across highway sensors or temperature readings from a distributed weather station network. Effectively modeling such data requires capturing both spatial dependencies (interactions between neighboring nodes) and temporal patterns (evolution of a node's state over time).

Current methodologies typically employ hybrid architectures, stacking Graph Convolutional Neural Networks (GCNNs) for spatial processing with Recurrent Neural Networks (RNNs) or temporal CNNs. While effective, these models often treat space and time as separable dimensions, potentially overlooking complex joint interactions. Alternatively, fused models that attempt joint processing often lack a rigorous mathematical foundation, complicating theoretical analysis of their stability and robustness. This paper introduces Graph-Time Convolutional Neural Networks (GTCNNs), a "first-principles" framework that treats spatiotemporal data as a single signal on a product graph.

Methodology: Product Graphs and GTCNNs

The core innovation of the GTCNN is the use of Product Graphs to represent spatiotemporal dependencies. By "multiplying" a spatial graph $\mathcal{G}$ (representing the network topology) with a temporal graph $\mathcal{G}_T$ (representing the flow of time), we obtain a product graph $\mathcal{G}_\diamond$. In this structure, each node represents a specific location at a specific time index.

Construction of the spatiotemporal product graph and definitions for Kronecker, Cartesian, and Strong products.

The authors define Graph-Time Convolutional Filters that operate directly on these product graphs. To handle the computational complexity of large graphs over long time horizons, they introduce a recursive "shift-and-sum" implementation. This approach ensures that the computational cost remains linear with respect to the number of edges, making the model scalable for real-world applications.

Information aggregation patterns for different product graphs and the recursive shift-and-sum implementation of the GTCNN filter.

Furthermore, the framework supports Parametric Product Graphs, where the coupling weights between spatial and temporal dimensions are learned during training. This allows the model to adaptively determine the relative importance of spatial versus temporal neighbors for a given task.

Theoretical Analysis and Insights

A key advantage of the GTCNN framework is its mathematical tractability, allowing for rigorous theoretical guarantees:

  • Permutation Equivariance: The model's output is independent of the arbitrary indexing of nodes, a crucial property for graph-based learning.
  • Joint Spectral Domain: GTCNNs operate in a joint graph-time frequency domain, enabling the design of filters that target specific spatiotemporal frequencies.
  • Stability-Robustness Trade-off: The paper proves that GTCNNs are stable to perturbations in the graph structure. However, it identifies a fundamental trade-off: increasing a model's discriminative power (complexity) typically reduces its stability. Sensitivity is shown to increase as the time window $T$ or node count $N$ grows.

Experimental Results

The GTCNN was evaluated across several benchmark datasets, including synthetic source localization and real-world traffic (METR-LA, PEMS-BAY) and weather (Molene, NOAA) forecasting.

  • Forecasting Performance: In traffic forecasting, GTCNN outperformed standard GCNNs and remained highly competitive with state-of-the-art models like Graph WaveNet and STGCN, particularly in short-term horizons.
  • Robustness: In source localization tasks, GTCNN demonstrated significantly higher accuracy than vanilla GCNNs, validating the strength of its spatiotemporal inductive bias.
  • Empirical Stability: Tests confirmed that GTCNN maintains high performance even when the underlying graph topology is noisy or perturbed, outperforming baseline models that ignore the temporal graph structure.

Conclusion and Future Work

GTCNN provides a mathematically grounded and stable architecture for spatiotemporal learning. While it excels in short-term forecasting and robustness, future work will address its limitations in capturing very long-term dependencies—where dilated convolutions currently hold an advantage—and further improving scalability for massive datasets. The framework serves as a foundational step toward more sophisticated, theoretically grounded spatiotemporal models.

Summary updated

Abstract

Devising and analyzing learning models for spatiotemporal network data is of importance for tasks including forecasting, anomaly detection, and multi-agent coordination, among others. Graph Convolutional Neural Networks (GCNNs) are an established approach to learn from time-invariant network data. The graph convolution operation offers a principled approach to aggregate multiresolution information. However, extending the convolution principled learning and respective analysis to the spatiotemporal domain is challenging because spatiotemporal data have more intrinsic dependencies. Hence, a higher flexibility to capture jointly the spatial and the temporal dependencies is required to learn meaningful higher-order representations. Here, we leverage product graphs to represent the spatiotemporal dependencies in the data and introduce Graph-Time Convolutional Neural Networks (GTCNNs) as a principled architecture to aid learning. The proposed approach can work with any type of product graph and we also introduce a parametric product graph to learn also the spatiotemporal coupling. The convolution principle further allows a similar mathematical tractability as for GCNNs. In particular, the stability result shows GTCNNs are stable to spatial perturbations but there is an implicit trade-off between discriminability and robustness; i.e., the more complex the model, the less stable. Extensive numerical results on benchmark datasets corroborate our findings and show the GTCNN compares favorably with state-of-the-art solutions. We anticipate the GTCNN to be a starting point for more sophisticated models that achieve good performance but are also fundamentally grounded.
BibTeX
@article{sabbaqi2023graph,
  author = {Mohammad Sabbaqi and Elvin Isufi},
  title = {{Graph-Time Convolutional Neural Networks: Architecture and Theoretical Analysis}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2023},
  url = {https://openreview.net/forum?id=XZED5nSUw2},
}
Figure