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

Many real world phenomena are intrinsically dynamic by nature, and ideally neural networks, encoding the knowledge about the world should also be based on more explicit time-conditioned representation and learning mechanisms. However, most currently available deep learning (DL) architectures are inherently static and do not systematically integrate time-dimension into the learning process. As a result, such model architectures often cannot reliably, accurately and on time learn many salient time-conditioned characteristics of complex interdependent systems, often resulting in outdated decisions and requiring frequent model updates.

In turn, in the last few years we observe an increasing interest to integrate deep neural network architectures with persistent homology representations of the learned objects, typically in a form of some topological layer in DL (Hofer et al., 2019; Carrière et al., 2020; Carlsson & Gabrielsson, 2020). Such persistent homology representations allow us to extract and learn descriptors of the object shape. (By shape here we broadly understand data characteristics that are invariant under continuous transformations such as bending, stretching, and compressing.) Such interest in combining persistent homology representations with DL is explained by the complementary multi-scale information topological descriptors deliver about the underlying objects, and higher robustness of these salient object characterisations to perturbations.

Here we take the first step toward merging the two directions. To enhance DL with the most salient time-conditioned topological information, we introduce the concept of zigzag persistence into time-aware DL. Building on the fundamental results on quiver representations, zigzag persistence studies properties of topological spaces which are connected via inclusions going in both directions (Carlsson & Silva, 2010; Tausz & Carlsson, 2011; Carlsson, 2019). Such generalization of ordinary persistent homology allows us to track topological properties of time-conditioned objects by extracting and tracking salient time-aware topological features through time-ordered inclusions. We propose to summarize the extracted time-aware zigzag persistence in a form of zigzag persistence images and then integrate the resulting information as a learnable time-aware zigzag layer into GCN.

The key novelty of our paper can be summarized as follows:

• •

  This is the first approach bridging time-conditioned DL with time-aware persistent homology representations of the data.

• •

  We propose a new vectorized summary for time-aware persistence, namely, zigzag persistence image and discuss its theoretical stability guarantees.

• •

  We introduce the concepts of time-aware zigzag persistence into learning time-conditioned graph structures and develop a zigzag topological layer (Z-GCNET) for time-aware graph convolutional networks (GCNs).

• •

  Our experiments on application Z-GCNET to traffic forecasting and Ethereum blockchain price prediction show that Z-GCNET surpasses 13 state-of-the-art methods on 4 benchmark datasets, both in terms of accuracy and robustness.

Zigzag Persistence is yet an emerging tool in applied topological data analysis, but many recent studies have already shown its high utility in such diverse applications as brain sciences (Chowdhury et al., 2018), imagery classification (Adams et al., 2020), cyber-security of mobile sensor networks (Adams & Carlsson, 2015; Gamble et al., 2015), and characterization of flocking and swarming behavior in biological sciences (Corcoran & Jones, 2017; Kim et al., 2020). An alternative to zigzag but a closely related approach to assess properties of time-varying data with persistent homology, namely, crocker stacks, has been recently suggested by Xian et al. (2020), though the crocker stacks representations are not learnable in DL models. While zigzag has been studied in conjunction with dynamic systems (Tymochko et al., 2020) and time-evolving point clouds (Corcoran & Jones, 2017), till now, the utility of zigzag persistence remains untapped not only in conjunction with GCNs but with any other DL tools.

Time series forecasting From a deep learning perspective, Recurrent Neural Networks (RNNs) are natural methods to model time-dependent datasets (Yu et al., 2019). In particular, the stable architecture of Long Short Term Memories (LSTMs), and its variant called Gate Recurrent Unit (GRU), solves the gradient instability of predecessors and adds extra flexibility due to their memory storage and forget gates. The ability of LSTM and GRU to selectively learn historical patterns awaken an interest among researchers and major companies to solve a variety of time-dependant machine learning problems (Chae et al., 2018; Schmidhuber, ; Yuan et al., 2019; Shin & Kim, 2020). Although most of variants of LSTM architecture performs similarly well in large scale studies, see (Greff et al., 2017), GRU models has fewer parameters and, in general, perform similarly well as LSTM (Gao et al., 2020). Applications of RNN are limited by the underlying structure of the input data, these methods are not designed to handle data from non-Euclidean spaces, such as graphs and manifolds.

Graph convolutional networks To overcome the limitations of traditional convolution on graph structured data, graph convolution-based methods (Defferrard et al., 2016; Kipf & Welling, 2017; Veličković et al., 2018) are proposed to explore both global and local structures. GCNs usually consists of graph convolution layers which extract the edge characteristics between neighbor nodes and aggregate feature information from neighborhood via graph filters. In addition to convolution, there has been a surge of interest in applying GCNs time series forecasting tasks (Yu et al., 2018b; Yao et al., 2018; Yan et al., 2018; Guo et al., 2019; Weber et al., 2019; Pareja et al., 2020). Although these methods have achieved state-of-the-art performance in traffic flow forecasting, human action recognition, and anti-money laundering regulation, the design of spatial temporal graph convolution network framework is mostly based on modeling spatial-temporal correlation in terms of feature-level and pre-defined graph structure.

Spatio-temporal Data as Graph Structures The spatial-temporal networks can be represented as a sequence of discrete snapshots, $\{\mathcal{G}_{1},\mathcal{G}_{2},\dots,\mathcal{G}_{T}\}$, where $\mathcal{G}_{t}=\{\mathcal{V},\mathcal{E}_{t},W_{t}$} represents the graph structure at time step $t$, $t=1,\ldots,T$. In spatial network $\mathcal{G}_{t}$, $\mathcal{V}$ is a node set with cardinality $|\mathcal{V}|$ of $N$ and $\mathcal{E}_{t}\subseteq\mathcal{V}\times\mathcal{V}$ is an edge set. A nonnegative symmetric $N\times N$-matrix $W_{t}$ with entries $\{\omega^{t}_{ij}\}_{1\leq i,j\leq N}$ represents the adjacency matrix of $\mathcal{G}_{t}$, that is, $\omega^{t}_{ij}>0$ for any $e^{t}_{ij}\in\mathcal{E}_{t}$ and $\omega^{t}_{ij}=0$, otherwise. Let $F,F\in\mathbb{Z}_{>0}$ be the number of different node features associated each node $v\in\mathcal{V}$. Then, a $N\times F$ feature matrix $\boldsymbol{X}_{t}$ serves as an input to the framework of time series process modeling.

Background on Persistent Homology Persistent homology is a mathematical machinery to extract the intrinsic shape properties of $\mathcal{G}$ that are invariant under continuous transformations such as bending, stretching, and twisting. The key idea is, based on some appropriate scale parameter, to associate $\mathcal{G}$ with a graph filtration $\mathcal{G}^{1}\subseteq\ldots\subseteq\mathcal{G}^{n}=\mathcal{G}$ and then to equip each $\mathcal{G}^{i}$ with an abstract simplicial complex $\mathscr{C}(\mathcal{G}^{i})$, $1\leq i\leq n$, yielding a filtration of complexes $\mathscr{C}(\mathcal{G}^{1})\subseteq\ldots\subseteq\mathscr{C}(\mathcal{G}^{n})$. Now, we can systematically and efficiently track evolution of various patterns such as connected components, cycles, and voids throughout this hierarchical sequence of complexes. Each topological feature, or $p$-hole (e.g., number of connected components and voids), $0\leq p\leq d$, is represented by a unique pair $(i_{b},j_{d})$, where birth $i_{b}$ and death $j_{d}$ are the scale parameters at which the feature first appears and disappears, respectively. The lifespan of the feature is defined as $i_{d}-j_{b}$. The extracted topological information can be then summarized as a persistence diagram ${\rm{Dgm}}=\{(i_{b},j_{d})\in\mathbb{R}^{2}|i_{b}<j_{d}\}$. Multiplicity of a point $(i_{b},j_{d})\in\mathcal{D}$ is the number of $p$-dimensional topological features ($p$-holes) that are born and die at $i_{b}$ and $j_{b}$, respectively. Points at the diagonal $\rm{Dgm}$ are taken with infinite multiplicity. The idea is then to evaluate topological features that persist (i.e. have longer lifespan) over the complex filtration and, hence, are likelier to contain important structural information on the graph.

Finally, a filtration of the weighted graph $\mathcal{G}$ can be constructed in multiple ways. For instance, (i) we can select a scale parameter as edge weight and, as an abstract simplicial complex $\mathscr{C}$ on $\mathcal{G}$, consider a Vietoris–Rips (VR) complex $\mathscr{VR}^{\nu_{*}}(\mathcal{G})=\{\mathcal{G}^{{}^{\prime}}\subseteq\mathcal{G}|diam(\mathcal{G}^{{}^{\prime}})\leq\nu_{*}\}$, that is, $\mathscr{VR}^{\nu_{*}}(\mathcal{G})$ consists of nodes with a shortest weighted path of at most $\nu_{*}$. Hence, for a set of scale thresholds $\nu_{1}\leq\ldots\nu_{n}$, we obtain a VR filtration $\mathscr{VR}^{{1}}\subseteq\ldots\subseteq\mathscr{VR}^{{n}}$. Alternatively, (ii) we can consider a sublevel filtration induced by a continuous function $f$ defined on nodes of $\mathcal{G}$. Let $f:V\rightarrow\mathbb{R}$ and $\nu_{1}<\nu_{2}<\ldots<\nu_{n}$ be a sequence of sorted filtered values, then $\mathscr{C}^{i}=\{\sigma\in\mathscr{C}:\max_{v\in\sigma}f(v)\leq\nu_{i}\}$. Note that a VR filtration (i) is a subcase of sublevel filtration (ii) with $f$ being the diameter function (Adams et al., 2017; Bauer, 2019).

Time-Aware Zigzag Persistence Since our primary aim is to assess interconnected evolution of multiple time-conditioned objects, the developed methodology for tracking topological and geometric properties of these objects shall ideally account for their intrinsically dynamic nature. We address this goal by introducing the concept of zigzag persistence into GNN. Zigzag persistence is a generalization of persistent homology proposed by (Carlsson & Silva, 2010) and provides a systematic and mathematically rigorous framework to track the most important topological features of the data persisting over time.

Let $\{\mathcal{G}_{t}\}_{1}^{T}$ be a sequence of networks observed over time. The key idea of zigzag persistence is to evaluate pairwise compatible topological features in this time-ordered sequence of networks. First, we define a set of network inclusions over time

where $\mathcal{G}_{k}\cup\mathcal{G}_{k+1}$ is defined as a graph with a node set $V_{k}\cup V_{k+1}$ and an edge set $E_{k}\cup E_{k+1}$. Second, we fix a scale parameter $\nu_{*}$ and build a zigzag diagram of simplicial complexes for the given $\nu_{*}$ over the constructed set of network inclusions

Using the zigzag filtration for the given $\nu_{*}$, we can track birth and death of each topological feature over $\{\mathcal{G}_{t}\}_{1}^{T}$ as time points $t_{b}$ and $t_{d}$, $1\leq t_{b}\leq t_{d}\leq T$, respectively. Similarly to a non-dynamic case, we can extend the notion of persistence diagram for the analysis of topological characteristics of time-varying data delivered by the zigzag persistence.

Inspired by the notion of a persistent image as a summary of ordinary persistence (Adams et al., 2017), to input topological information summarized by ZPD into a GNN, we propose a representation of ZPD as zigzag persistence image (ZPI). ZPI is a finite-dimensional vector representation of a ZPD and can be computed through the following steps:

• •

  Step 1: Map a zigzag persistence diagram $\rm{DgmZZ}_{\nu_{*}}$ to an integrable function $\rho_{\rm{DgmZZ}_{\nu_{*}}}:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$, called a zigzag persistence surface. The zigzag persistence surface is given by sums of weighted Gaussian functions that are centered at each point in $\rm{DgmZZ}_{\nu_{*}}$.

• •

  Step 2: Perform a discretization and linearization of a subdomain of zigzag persistence surface $\rho_{\rm{DgmZZ}_{\nu_{*}}}$ in a grid.

• •

  Step 3: The ZPI, i.e., a matrix of pixel values, can be obtained by subsequent integration over each grid box.

The value of each pixel $z\in\mathbb{R}^{2}$ within a ZPI is defined as:

where $\rm{DgmZZ}^{\prime}_{\nu_{*}}$ is the transformed multi-set in $\rm{DgmZZ}_{\nu_{*}}$, i.e., $\rm{DgmZZ}^{\prime}_{\nu_{*}}(x,y)=(x,y-x)$; $g(\mu)$ is a weighting function with mean $\mu=(\mu_{x},\mu_{y})\in\mathbb{R}^{2}$ and variance $\vartheta^{2}$, which depends on the distance from the diagonal. Here the zigzag persistence surface is defined by $\rho_{\rm{DgmZZ}_{\nu_{*}}}=\sum_{\mu\in ZPD^{\prime}}g\left(\mu\right)\exp{\bigl{\{}-{||z-\mu||^{2}}/{2\vartheta^{2}}\bigr{\}}}$.

Tracking evolution of topological patterns in these sequences of time-evolving graphs allows us to glean insights into which properties of the observed time-conditioned objects, e.g., traffic data or Ethereum transaction graphs, tend to persist over time and, hence, are likelier to play a more important role in predictive tasks.

Given the graph $\mathcal{G}$ and graph signals $\boldsymbol{X}^{\tau}=\{\boldsymbol{X}_{t-\tau},\dots,\boldsymbol{X}_{t-1}\}\in\mathbb{R}^{\tau\times N\times F}$ of $\tau$ past time periods (i.e. window size $\tau$; where $\boldsymbol{X}_{i}\in\mathbb{R}^{N\times F}$ and $i\in\{t-\tau,\dots,t-1\}$), we employ a model targeted on multi-step time series forecasting. That is, given the windows size $\tau$ of past graph signals and the ahead horizon size $h$, our goal is to learn a mapping function which maps the historical data $\{\boldsymbol{X}_{t-\tau},\dots,\boldsymbol{X}_{t-1}\}$ into the future data $\{\boldsymbol{X}_{t},\dots,\boldsymbol{X}_{t+h}\}$.

Laplacianlink In spatial-temporal domain, the topology of graph may have different structure at different points in time. In this paper, we use the self-adaptive adjacency matrix (Wu et al., 2019) as the normalized Laplacian by trainable node embedding dictionaries $\boldsymbol{\phi}\in\mathbb{R}^{N\times c}$, i.e., $\boldsymbol{L}=softmax(ReLU(\boldsymbol{\phi}\boldsymbol{\phi}^{\top}))$, where the dimension of embedding $c\geq 1$. Although introducing node embedding dictionaries allows capture hidden spatial dependence information, it cannot sufficiently capture the global graph information and the similarity between nodes. To overcome the limits and explore neighborhoods of nodes at different depths, we define a novel polynomial representation for Laplacian based on positive powers of the Laplacian matrix. In this work, Laplacianlink $\tilde{\boldsymbol{L}}$ is formulated as:

where $K\geq 1$, $\boldsymbol{I}\in\mathbb{R}^{N\times N}$ represents the identity matrix, and $\boldsymbol{L}^{k}\in\mathbb{R}^{N\times N}$, with $0\leq k\leq K$, denotes the power series of normalized Laplacian.

By linking (i.e., stacking) the power series of normalized Laplacian, we build a diffusion formalism to accumulate neighbors’ information of different power levels. Hence, each node will successfully exploit and propagate spatial-temporal correlations after spatial and temporal graph convolutional operations.

Spatial graph convolution To model the spatial network $\mathcal{G}_{t}$ at timestamp $t$ with its node feature matrix $\boldsymbol{X}_{t}$, we define the spatial graph convolution as multiplying the input of each layer with the Laplacianlink $\tilde{\boldsymbol{L}}$, which is then fed into the trainable projection matrix $\boldsymbol{\Theta}=\boldsymbol{\phi}\boldsymbol{V}$ (where $\boldsymbol{V}$ stands for the trainable weight). In spatial-temporal graph modeling, we prefer to use weight sharing in matrix factorization rather than directly assigning a trainable weight matrix in order not only to avoid the risk of over-fitting but also to reduce the computational complexity. We compute the transformation in spatial domain, in each layer, as follows:

where $\boldsymbol{\phi}\in\mathbb{R}^{N\times c}$ is the node embedding and $\boldsymbol{V}\in\mathbb{R}^{c\times(K+1)\times C_{in}\times({C_{out}}/{2})}$ is the trainable weight ($C_{in}$ and $C_{out}$ are the number of channels in input and output, respectively). $\boldsymbol{H}^{(\ell-1)}_{i,\mathcal{S}}\in\mathbb{R}^{N\times({C_{in}}/{2})}$ is the matrix of activations of spatial graph convolution to the $\ell$-th layer and $\boldsymbol{H}^{(0)}_{i,\mathcal{S}}=\boldsymbol{X}_{i}$. As a result, all information regarding the $\ell$-layered input at time $i$ are reflected in the latest state variable.

Temporal graph convolution In addition to spatial domain, the nature of spatial-temporal networks includes temporal relationships among consistent spatial networks. To catch the temporal correlation patterns of nodes, we choose longer window size (i.e., by using the entire sliding window as input) and apply temporal graph convolution to graph signals in sliding window $\boldsymbol{X}^{\tau}$. The mechanism has several excellent properties: (i) there is no need to select a particular size of nested sliding window, i.e., does not introduce additional computational complexity, (ii) temporal correlation patterns can be well captured and evaluated by (long) window sizes, whereas short window sizes (i.e., nested sliding window) are likely to be bias and noise, and (iii) the sliding window $\boldsymbol{X}^{\tau}$ maximizes the efficiency of estimating temporal correlations. The temporal graph convolution is presented in the form:

where $\boldsymbol{U}^{(\ell)}\in\mathbb{R}^{c\times C_{in}\times({C_{out}}/{2})}$ is trainable weight and $\boldsymbol{U}^{(0)}\in\mathbb{R}^{c\times F\times({C_{out}}/{2})}$, $\boldsymbol{Q}\in\mathbb{R}^{\tau\times 1}$ is the trainable projection vector in temporal graph convolutional layer, and $\boldsymbol{H}^{(\ell-1)}_{i,\mathcal{T}}\in\mathbb{R}^{\tau\times N\times({C_{in}}/{2})}$ is the hidden matrix fed to the $\ell$-th layer and $\boldsymbol{H}^{(0)}_{i,\mathcal{T}}=\boldsymbol{X}^{\tau}\in\mathbb{R}^{\tau\times N\times F}$.

Time-aware zigzag topological layer To learn the topological features across a range of spatial and temporal scales, we extend the CNN model to be used along with ZPI. In this research, we present a framework to aggregate the topological persistent features into the feature representation learned from GCN. Let $\text{ZPI}^{\tau}$ denotes the ZPI based on the sliding window $\boldsymbol{X}^{\tau}$. (Here for brevity we suppress dependence of ZPI on a scale parameter $\nu_{*}$.) We design the time-aware zigzag topological layer to (i) extract and learn the spatial-temporal topological features contained in ZPI, (ii) aggregate transformed information from (spatial or temporal) graph convolution and spatial-temporal topological information from zigzag persistence module, and (iii) mix spatial-temporal and spatial-temporal topological information. The information’s extraction, aggregation, and combination processes are expressed as:

where $f_{\text{cnn}}^{(\ell)}$ represents the convolutional neural network (CNN) in the $\ell$-th layer, $\xi_{\text{max}}(\cdot)$ denotes global max-pooling operation, $\boldsymbol{Z}^{(\ell)}\in\mathbb{R}^{({C_{out}}/{2})}$ is the learned zigzag persistence representation from CNN, $\boldsymbol{S}^{(\ell)}_{i}\in\mathbb{R}^{N\times({C_{out}}/{2})}$ is the aggregated $\text{spatial}^{2}$-temporal representation, $\boldsymbol{T}^{(\ell)}_{i}\in\mathbb{R}^{N\times({C_{out}}/{2})}$ is the aggregated spatial-$\text{temporal}^{2}$ representation, and the output of time-aware zigzag topological layer $\boldsymbol{H}^{(\ell)}_{i,out}\in\mathbb{R}^{N\times C_{out}}$ combines hidden states $\boldsymbol{S}^{(\ell)}_{i}$ and $\boldsymbol{T}^{(\ell)}_{i}$ at time $i$.

GRU with time-aware zigzag topological layer GRU is a variant of LSTM network. Compared with LSTM, GRU has a simpler structure, fewer training parameters, and more easily overcome vanishing and exploding gradient problems. The feed forward propagation of GRU with time-aware zigzag topological layer is recursively conducted as:

where $\varphi(\cdot)$ is a non-linear function, i.e., the ReLU function; $\odot$ is the elementwise product; $\boldsymbol{z}_{i}$ and $\boldsymbol{r}_{i}$ are update gate and reset gate, respectively; $\boldsymbol{b}_{z}$, $\boldsymbol{b}_{r}$, $\boldsymbol{b}_{o}$, $\boldsymbol{W}_{z}$, $\boldsymbol{W}_{r}$, and $\boldsymbol{W}_{o}$ are trainable parameters; $\left[\boldsymbol{O}_{i-1},\boldsymbol{H}_{i,out}\right]$ and $\boldsymbol{O}_{i}$ are the input and output of GRU model, respectively. In this way, Z-GCNETs contains structural, temporal, and topological information.

Inspired the recent call for developing time-aware deep learning mechanisms by the US Defense Advanced Research Projects Agency (DARPA), we have proposed a new time-aware zigzag topological layer (Z-GCNETs) for time-conditioned GCNs. Our idea is based on the concepts of zigzag persistence whose utility remains unexplored not only in conjunction with time-aware GCN but DL in general. The new Z-GCNETs layer allows us to track the salient time-aware topological characterizations of the data persisting over time. Our results on spatio-temporal graph structured data have indicated that integration of the new time-aware zigzag topological layer into GCNs results both in enhanced forecasting performance and substantial robustness gains.

The project has been supported in part by the grants NSF DMS 1925346, NSF ECCS 2039701, and NSF ECCS 1824716.