# A Gated MLP Architecture for Learning Topological Dependencies in Spatio-
Temporal Graphs

Yun Young Choi1∗ Minho Lee2 equal contribution, correspondence to
<EMAIL_ADDRESS>Sun Woo Park3 Seunghwan Lee4 Joohwan Ko5
1National Institute for Mathematical Sciences 2Sogang University
3University of Wisconsin-Madison 4Kyung Hee University 5KAIST

###### Abstract

Graph Neural Networks (GNNs) and Transformer have been increasingly adopted to
learn the complex vector representations of spatio-temporal graphs, capturing
intricate spatio-temporal dependencies crucial for applications such as
traffic datasets. Although many existing methods utilize multi-head attention
mechanisms and message-passing neural networks (MPNNs) to capture both spatial
and temporal relations, these approaches encode temporal and spatial relations
independently, and reflect the graph’s topological characteristics in a
limited manner. In this work, we introduce the Cycle to Mixer (Cy2Mixer), a
novel spatio-temporal GNN based on topological non-trivial invariants of
spatio-temporal graphs with gated multi-layer perceptrons (gMLP). The Cy2Mixer
is composed of three blocks based on MLPs: A message-passing block for
encapsulating spatial information, a cycle message-passing block for enriching
topological information through cyclic subgraphs, and a temporal block for
capturing temporal properties. We bolster the effectiveness of Cy2Mixer with
mathematical evidence emphasizing that our cycle message-passing block is
capable of offering differentiated information to the deep learning model
compared to the message-passing block. Furthermore, empirical evaluations
substantiate the efficacy of the Cy2Mixer, demonstrating state-of-the-art
performances across various traffic benchmark datasets.

##  1 Introduction

Traffic forecasting aims to predict future traffic in road networks based on
preceding traffic data (Li et al., 2017; Deng et al., 2021; Shao et al.,
2022a, b; Zhu et al., 2023). In Intelligent Transportation Systems (ITS),
traffic forecasting has a pivotal role in effective urban management
(Vlahogianni et al., 2004; Yin et al., 2015) due to its potential to benefit a
wide range of applications related to road networks, including route planning,
vehicle dispatching, and congestion mitigation (Wang et al., 2021). Traffic
data is frequently conceptualized as a spatio-temporal graph, where road
connections and traffic flows gleaned from sensors are represented as edges
and nodes (Diao et al., 2019; Wang et al., 2020b). Given this, many turn to
Graph Neural Networks (GNNs), especially those using Message Passing Neural
Networks (MPNNs), to study this data. GNNs based on MPNNs have been
increasingly adopted to learn the complex vector representations of spatio-
temporal graphs, capturing intricate dependencies in traffic datasets (Yu et
al., 2017; Li and Zhu, 2021; Choi et al., 2022a). However, traditional message
passing-based methodologies have exhibited limitations, including the
inability to adequately account for temporal variations in traffic data and
over-smoothing problems (Jiang et al., 2023). Following the success of
Transformers in various domains, they have been employed either independently
or synergetically with MPNNs to address these challenges in traffic
forecasting (Zheng et al., 2020; Xu et al., 2020; Jiang et al., 2023). In some
cutting-edge implementations, they are even coupled with preprocessing
techniques like Dynamic Time Warping (DTW) (Berndt and Clifford, 1994),
showcasing competitive performance outcomes (Jiang et al., 2023).

Previous research efforts have predominantly focused on employing additional
algorithms or incorporating intricate structures to capture the complex
patterns inherent in spatio-temporal graphs. This often results in heuristics
that inflate the complexity of structure and computational costs.
Additionally, many of these studies have leaned heavily on experimental
results to justify their performance improvements, lacking comprehensive
explanations or theoretical grounding. To address these challenges, we start
with a mathematical hypothesis that leverages the topological non-trivial
invariants of a spatio-temporal graph to enhance the predictive performances
of GNNs. This hypothesis aims to discern the spatio-temporal relationships
among nodes within the graph. We demonstrate that topological features shed
light on facets of temporal traffic data that might be overlooked when
focusing solely on the pre-existing edges connecting nodes in a traffic
network.

Building on this mathematical foundation, we propose a simple yet unique
model, Cycle to Mixer (Cy2Mixer), that integrates gated Multi-Layer Perceptron
(gMLP) Liu et al. (2021) and MPNNs, supplemented with topological non-trivial
invariants in graphs, to enhance predictive accuracy. Our Cy2Mixer layer
comprises three key components: (a) Message-passing block: Encompasses spatial
relationships along with local neighborhoods. (b) Cycle message-passing block:
Captures supplementary information among nodes in cyclic subgraphs. (c)
Temporal block: Seizes the temporal characteristics of all nodes. Notably, our
cycle message-passing block aims to encapsulate topological features, enabling
a finer comprehension of the intricate connectivity patterns within the
network inspired by Cy2C-GNNs (Choi et al., 2022b). We validate our
methodology using real-world public traffic datasets, showcasing the
competitive edge of our proposed models. Furthermore, a qualitative assessment
elucidates the efficacy of topological invariants in enhancing the Cy2Mixer’s
predictive performance. Our work also presents an evaluation of the efficiency
in preprocessing and training time of our model relative to recent state-of-
the-art techniques.

The contributions of this work are as follows: (1) We use homotopy invariance
of fundamental groups and homology groups to deduce that topological non-
trivial invariants of a traffic network become a contributing factor for
influencing the traffic forecast. (2) We propose a simple yet novel network,
Cy2CMixer, based on the gMLP and Cy2C-GNNs inspired by the theory of universal
covering spaces. (3) The proposed model not only exhibits minimal
computational cost but also proves to be highly efficient, consistently
delivering superior performance across a variety of datasets, including
traffic forecasting.

##  2 Preliminaries

In this section, we provide explanations for some notations and proceed to
define the traffic prediction problem.

###  2.1 Message passing neural networks (MPNNs)

Each $m$-th layer $H^{(m)}$ of the MPNNs and hidden node attributes
$h_{v}^{(m)}$ with dimension $k_{m}$ are defined as :

$\displaystyle\begin{cases}h_{v}^{(m)}:=\text{COMBINE}^{(m)}\left(h_{v}^{(m-1)},h_{u}^{\prime}\right)\\\
h_{v}^{(0)}:=X_{v}\end{cases},$ $\displaystyle\text{where
}h_{u}^{\prime}=\text{AGGREGATE}_{v}^{(m)}\left(\left\\{\\!\\!\left\\{h_{u}^{(m-1)}\;|\;u\in
N(v)\right\\}\\!\\!\right\\}\right).$

$X_{v}$ is the initial node attribute at $v$ and $N(v)$ is the set of
neighborhood nodes. Note that $\text{AGGREGATE}_{v}^{(m)}$ is a function that
aggregates features of nodes adjacency to $v$, and $\text{COMBINE}^{(m)}$ is a
function which combines features of the node $v$ with those of nodes adjacent
to $v$.

###  2.2 gated Multi-Layer Perceptron (gMLP)

gMLP has been shown to achieve comparable performance to Transformer models
across diverse domains, including computer vision and natural language
processing, with improved efficiency (Liu et al., 2021). With the given input
$X\in\mathbb{R}^{n\times d}$, where $n$ denotes sequence length and $d$
denotes dimension, it can be defined as:

$\displaystyle Z=\sigma(XU),\quad\tilde{Z}=s(Z),\quad Y=\tilde{Z}V,$

where $\sigma$ represents the activation function, which is GeLU (Hendrycks
and Gimpel, 2023) in this context, whereas $U$ and $V$ correspond to linear
projections based on the channel (feature) dimensions, serving roles similar
to the feed-forward network in Transformer. It is important to note that the
layer $s(\cdot)$ corresponds to the Spatial Gating Unit, which is responsible
for capturing cross-token interactions. We construct the aforementioned layer
as follows:

$\displaystyle s(Z)=Z_{1}\odot f_{W,b}(Z_{2}),$

where $f_{W,b}$ denotes a linear projection $f_{W,b}(Z)=WZ+b$. Here, $W$ and
$b$ refer to the weight matrix and bias, respectively. $Z_{1}$ and $Z_{2}$
denote two independent components split from $Z$ along the channel dimension,
and $\odot$ denotes element-wise multiplication.

###  2.3 Traffic Prediction Problem

#### Traffic sensor

Traffic sensors are deployed within the traffic system to record essential
information, such as the flow of vehicles on roads and the speeds of these
vehicles.

#### Traffic network

Traffic network can be represented as
$\mathcal{G}=(\mathcal{V},\mathcal{E},A,A_{C})$, where
$\mathcal{V}=\\{v_{1},\cdots,v_{N}\\}$ denotes the set of $N$ nodes
representing sensors within the traffic network ($|V|=N$). Next,
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ represents the set of
edges, and the adjacency matrix $A$ of the network $\mathcal{G}$ can be
obtained based on the distances between nodes. Additionally, $A_{C}$ is the
clique adjacency matrix of the network, which is incorporated into the GNN
architecture. Note that the clique adjacency matrix is obtained by using the
identical procedure as in the prior study (Choi et al., 2022b). It is
paramount to underscore that $A\in\mathbb{R}^{N\times N}$ and
$A_{C}\in\mathbb{R}^{N\times N}$ are time-independent input variables since
the structure remains unchanged over time.

#### Traffic signal

The traffic signal $X_{t}\in\mathbb{R}^{N\times C}$ represents the data
measured at time $t$ across $N$ nodes in the network. In this context, $C$
denotes the number of features being recorded by the sensors, and in this
study, it represents the flow of the road network.

#### Problem formalization

In traffic forecasting, our objective is to train a mapping function $f$ to
predict future traffic signals by utilizing the data observed in the previous
$T$ steps, which can be illustrated as follows:

$\displaystyle\left[X_{(t-T+1)},\cdots,X_{t};\mathcal{G}\right]\stackrel{{\scriptstyle
f}}{{\longrightarrow}}\left[X_{(t+1)},\cdots,X_{\left(t+T^{\prime}\right)}\right].$

##  3 Mathematical Backgrounds

One of the prominent ways to mathematically quantify the effectiveness and
discerning capabilities of GNNs is to interpret the graph dataset as a
collection of 1-dimensional topological spaces $\mathcal{G}:=\\{G_{i}\\}_{i}$,
and identify the given GNNs as a function $GNN:\mathcal{G}\to\mathbb{R}^{k}$
which represents graphs in a given dataset as real $k$-dimensional vectors.
These approaches were carefully executed in previous literature, which focused
on pinpointing the discernability of various architectural designs for
improving GNNs, as seen in Choi et al. (2022b); Bodnar et al. (2021); Horn et
al. (2021); Park et al. (2022). Throughout these references, the
characterizations of topological invariants of such 1-dimensional topological
spaces provided grounds for verifying whether such GNNs can effectively
capture geometric non-trivial properties of graph datasets, such as cyclic
substructures or connected components of graphs. In light of these previous
studies, it is hence of paramount interest to reinterpret temporal graph
datasets as a collection of higher dimensional topological spaces and
understand what non-trivial properties of such topological spaces the novel
deep learning techniques processing temporal graph datasets should
encapsulate.

Figure 1: An illustration of lifting a cyclic subgraph of the traffic network
$\mathcal{G}$ to a temporal cyclic subgraph of the topological space
$\mathcal{G}\times I$ representing the traffic dataset.

#### Topological Space

In this work, we interpret the traffic dataset as a 2-dimensional topological
space constructed from the traffic network $\mathcal{G}$, and traffic signals
as a function defined over the 2-dimensional topological space. To elaborate,
the previous section indicates that we can identify a traffic network with a
graph $\mathcal{G}=(\mathcal{V},\mathcal{E},A,A_{C})$, and a traffic signal at
time $t$, denoted by $X_{t}\in\mathbb{R}^{N\times C}$, as a collection of
functions $\\{f_{t}:\mathcal{G}\to\mathbb{R}^{N\times C}\\}_{t}$, each of
which represents measurements taken over the graph $\mathcal{G}$ at time $t$.
But notice that the continuous time variable $t$ parametrizes a closed
interval $I:=[t_{s},t_{e}]$, where $t_{s}$ and $t_{e}$ denote the start and
end time of the traffic dataset. This observation allows us to identify a
temporal traffic network as a topological space $\mathcal{G}\times I$, and the
collection of traffic signals varying with respect to a time variable $t$ as a
function over $\mathcal{G}\times I$ satisfying the following condition:

$\displaystyle\begin{split}X:&\mathcal{G}\times I\to\mathbb{R}^{N\times C}\\\
X(g,t)&=X_{t}(g)\text{ for all }t\in I.\end{split}$

#### Temporal cyclic structures

One of the prominent topological properties of a graph is the configuration of
its cyclic subgraphs. The existence of such cyclic subgraphs indicates that
there exists a pair of nodes $v,w\in\mathcal{V}$ which are connected by at
least two distinct paths, each of which is comprised of moving along the edges
of the graph $\mathcal{G}$. In terms of traffic dataset, the existence of a
cyclic subgraph indicates that there are at least two paths that a flow of
traffic can move along from one point to another. This observation hints that
it is of great importance to understand how such cyclic subgraphs of a given
traffic network $\mathcal{G}$ affect predicting future traffic signals. One of
the natural questions we may ask is to understand all possible cyclic
substructures inherent in a traffic signal $X:\mathcal{G}\times
I\to\mathbb{R}^{N\times C}$ one needs to analyze. The following result shows
that cyclic substructures of a traffic signal can be fully understood by
understanding the cycle bases of a traffic network $\mathcal{G}$.

######  Theorem 3.1.

Given any choice of $t_{0}\in I$, let $\pi_{t_{0}}:\mathcal{G}\times
I\to\mathcal{G}\times\\{t_{0}\\}\cong\mathcal{G}$ be the projection map which
sends the interval $I$ to a singleton set $\\{t_{0}\\}$. Let
$\mathcal{C}_{\mathcal{G}\times I}:=\\{C_{1},C_{2},\cdots,C_{n}\\}$ be a cycle
basis of the topological space $\mathcal{G}\times I$. Then the set

$\pi_{t_{0}}\left(\mathcal{C}_{\mathcal{G}\times
I}\right):=\\{\pi_{t_{0}}(C_{1}),\cdots,\pi_{t_{0}}(C_{n})\\}$

is a cycle basis of the traffic network $\mathcal{G}$.

###### Proof.

The theorem is a corollary of Hatcher (2002)[Proposition 1.18, Corollary
2.11]. To elaborate, the map $\pi_{t_{0}}:\mathcal{G}\times I\to\mathcal{G}$
is a homotopy equivalence between the space $\mathcal{G}\times I$ representing
the temporal traffic data and the space $\mathcal{G}$ representing the traffic
network. The map induces an isomorphism between the fundamental groups and the
homology groups of two topological spaces with rational coefficients. That is,
these two maps are isomorphisms of groups for all indices $i\geq 0$:

$\displaystyle\begin{split}(\pi_{t_{0}})_{*}:\pi_{1}(\mathcal{G}\times
I)\to\pi_{1}(\mathcal{G})\\\ (\pi_{t_{0}})_{*}:H^{i}(\mathcal{G}\times
I,\mathbb{Q})\to H^{i}(\mathcal{G},\mathbb{Q})\end{split}$

The isomorphisms between the fundamental groups $\pi_{1}$ and the first
homology groups $H_{1}$ indicate that the set
$\pi_{t_{0}}(\mathcal{C}_{\mathcal{G}\times I})$ has to be a cycle basis of
$\mathcal{G}$. ∎

The above theorem shows in particular that any cyclic subgraph of the traffic
signal $\mathcal{G}\times I$ is comprised of nodes of form
$(c_{1},t_{1}),(c_{2},t_{2}),\cdots,(c_{n},t_{n})\in\mathcal{G}\times I$,
where the nodes $c_{1},c_{2},\cdots,c_{n}$ are on a common cyclic subgraph of
$\mathcal{G}$, and the coordinates $t_{i}$ correspond to different temporal
instances. Theorem 3.1 mathematically demonstrates that the topological non-
trivial invariants of a traffic network $\mathcal{G}$ can become a
contributing factor for influencing the temporal variations measured among the
nodes of traffic dataset, a potential aspect of temporal traffic data that may
not be fully addressed from solely analyzing the set of pre-existing edges
connecting the nodes of a traffic network. To elaborate, topological non-
trivial invariants of $\mathcal{G}$ elucidate restrictions associated to
constructing a global traffic signal $X:\mathcal{G}\times
I\to\mathbb{R}^{N\times C}$ from coherently gluing a series of local temporal
traffic signals $\\{X_{t}\\}$ measured at each time $t$. This originates from
previously studied mathematical insights that obstructions in gluing
continuous functions $f_{\alpha}:U_{\alpha}\to\mathbb{R}^{k}$ defined over
collections of open covers $U_{\alpha}\subset Y$ of a topological space (such
that $\cup_{\alpha}U_{\alpha}=Y$) to a continuous function
$f:Y\to\mathbb{R}^{k}$ can be detected from topological (or cohomological)
invariants of the topological space $Y$ (see for example Chapter 2 or 3 of
Hartshorne (1977)). Given that traffic forecasting beyond time $t=t_{e}$
requires a thorough understanding of traffic signals
$X:\mathcal{G}\times[0,t_{e}]\to\mathbb{R}^{N\times C}$, we can hence conclude
that a potential candidate to boost performances of traffic forecasting
algorithms is to effectively incorporate topological invariants of traffic
networks $\mathcal{G}$.

#### Temporal cliques

Theorem 3.1 demonstrates that every cyclic structure of temporal graph
datasets $\mathcal{G}\times I$ originating from lifting the cyclic structures
of the baseline traffic network $\mathcal{G}$ to any time period using the
projection map $\pi_{t_{0}}$. In fact, the lifting procedure does not require
that the cyclic structure over $\mathcal{G}\times I$ has to be defined over a
fixed time $t$. Rather, the cyclic subgraph of $\mathcal{G}$ can be lifted to
a cyclic subgraph of $\mathcal{G}\times I$ in a manner that the nodes on the
subgraph express traffic signals measured at different moments of time.

One of the topological invariants that conventional GNNs fail to incorporate
effectively is the cyclic substructures of graphs Xu et al. (2019); Bodnar et
al. (2021). These unsuccessful attempts originate from the capability of GNNs
to distinguish any pairs of two graphs $G$ and $H$ up to isomorphism of their
universal covers or unfolding trees. One effective method to overcome these
limitations is by substituting cyclic subgraphs into cliques. An approach
inspired by the theory of covering spaces, the strategy alters the geometry of
universal covers to allow GNNs to encapsulate cyclic structures effectively
(Choi et al., 2022b). We implement the application of the analogous operation
to temporal traffic data by utilizing the clique adjacency matrix $A_{C}$, the
incorporation of which is equivalent to connecting nodes representing traffic
at different instances of time with edges. In other words, the clique
adjacency matrix $A_{C}$ allows room for GNNs to determine whether additional
interactions among nodes of $\mathcal{G}$, whose measurements are taken at
varying moments of time, are relevant components for forecasting traffic
signals. By doing so, we are able to effectively encapsulate the potential
effects of topological invariants of traffic networks on temporal traffic
measurements, observation of which was inferred from Theorem 3.1. Figure 1
illustrates how lifting a cyclic subgraph of $\mathcal{G}$ to a new cyclic
subgraph of $\mathcal{G}\times I$ of varying temporal instances can enrich our
prediction of future traffic signals. The two cycles are subgraphs colored in
red. Note that in this example, the temporal cyclic subgraph spans over time
$t=t_{0}$ and the end time $t=t_{e}$ of the dataset. By changing the colored
cyclic subgraph into cliques, we add edges to nodes on the cyclic subgraph
lying in two different instances of time. These edges establish relations
among measurements taken at different nodes and time periods.

Figure 2: The overall framework of Cy2Mixer. Layers within the green box
indicate the Cy2Mixer encoder layer, which comprises a temporal block, spatial
message-passing block, and cycle message-passing block to ensure a
comprehensive understanding of both temporal and spatial aspects.

##  4 METHODOLOGY

In this section, we present the architecture of Cy2Mixer and elaborate on how
it distinguishes itself from other models. Figure 2 provides a comprehensive
visualization of our model’s framework. This architecture is primarily
composed of three main components: the embedding layer, a stack of $L$
Cy2Mixer encoder layers, and the output layer. Further details on these
components are elaborated upon subsequently.

###  4.1 Embedding Layer

Our model follows the structure of the embedding layer from Liu et al. (2023).
Given the time-series data $X_{t-T+1:t}$, the feature embedding is defined as
$X_{\textit{feat}}=\text{FC}(X_{t-T+1:t})$, where FC represents a fully
connected layer and $X_{\textit{feat}}\in\mathbb{R}^{T\times N\times d_{f}}$.
Additionally, to account for both weekly and daily periodicities, the temporal
embedding $X_{\textit{temp}}\in\mathbb{R}^{T\times N\times d_{t}}$ is
produced. This is achieved by referencing the day-of-week and timestamp-of-day
data to extract two distinct embeddings, which are subsequently concatenated
and broadcasted to generate the final temporal embedding with dimension
$d_{t}$. Furthermore, to address diverse temporal patterns specific to each
node, an adaptive embedding of dimension $d_{a}$, represented as
$X_{\textit{ast}}\in{\mathbb{R}^{T\times N\times d_{a}}}$, is introduced to
capture diverse temporal patterns for each node. These three embeddings are
concatenated, forming the output $H\in\mathbb{R}^{T\times N\times d_{h}}$ of
the embedding layer:

$\displaystyle H=X_{\textit{feat}}||X_{\textit{temp}}||X_{\textit{ast}},$

where the dimension $d_{h}$ is equal to $d_{f}+d_{t}+d_{a}$.

###  4.2 Cy2Mixer Encoder Layer

The core architecture of the Cy2Mixer encoder layer consists of three distinct
blocks, with each calculating the projection values of $Z$ based on the output
$H$ from the embedding layer. Upon splitting $Z$$\in\mathbb{R}^{T\times
N\times 2d_{h}}$ into $Z_{1}$$\in\mathbb{R}^{T\times N\times d_{h}}$ and
$Z_{2}$$\in\mathbb{R}^{T\times N\times d_{h}}$, each block adopts its unique
methodology within the Gating Unit.

#### Temporal Block

This block employs a $3\times 3$ convolution network to get the projection
values of $Z_{2}$. This is subsequently element-wise multiplied with $Z_{1}$,
generating the output of the Gating Unit:

$\displaystyle\tilde{Z}_{\textit{temporal}}=Z_{\textit{temporal},1}\odot\text{Conv}(Z_{\textit{temporal},2}),$

where $\tilde{Z}_{\textit{temporal}}\in\mathbb{R}^{T\times N\times d_{h}}$.
Here, $Z_{\textit{temporal},1}$ and $Z_{\textit{temporal},2}$ represent
$Z_{1}$ and $Z_{2}$ for the Temporal block, respectively.

#### Spatial Message-Passing & Cycle Message-Passing Blocks

These blocks employ the MPNN for their projection function in the Gating Unit.
Notably, the Spatial Message-Passing block uses the standard adjacency matrix,
$A$, whereas the Cycle Message-Passing block operates with the clique
adjacency matrix, $A_{C}$. The clique adjacency matrix, proposed by Choi et
al. (2022b), represents the bases of cycles (or the first homological
invariants of the graph in a graph (Paton, 1969)) in a suitable form that
enables GNNs to effectively process the desired topological features.
Following a process similar to the Temporal block, the $\tilde{Z}$ values for
both blocks are expressed as:

$\displaystyle\tilde{Z}_{\textit{spatial}}=Z_{\textit{spatial},1}\odot\text{MPNN}(Z_{\textit{spatial},2},A),$
$\displaystyle\tilde{Z}_{\textit{cycle}}=Z_{\textit{cycle},1}\odot\text{MPNN}(Z_{\textit{cycle},2},A_{C}),$

where $\tilde{Z}_{\textit{temporal}}\in\mathbb{R}^{T\times N\times d_{h}}$ and
$\tilde{Z}_{\textit{temporal}}\in\mathbb{R}^{T\times N\times d_{h}}$. The
final output of each block, denoted as $Y$, is calculated using the output of
the Gating Unit, $\tilde{Z}$. Considering the effective performance outcomes
of incorporating tiny attention into each block in prior research (Liu et al.,
2021), we have adopted the same structure in our model. Then we concatenate
all of three outputs, namely, $Y_{\textit{temporal}},Y_{\textit{cycle}}$, and
$Y_{\textit{spatial}}$, using a feed-forward network as:

$Y_{\textit{out}}=\text{FC}\left(Y_{\textit{temporal}}||Y_{\textit{cycle}}||Y_{\textit{spatial}}\right),\quad
Y_{\textit{out}}\in\mathbb{R}^{T\times N\times d_{h}}$

###  4.3 Output Layer

After progressing through the stacked sequence of $L$ Cy2Mixer encoder layers,
the output layer extracts the final predictions from the hidden state
$Y_{out}$.

$\hat{Y}=\text{FC}(Y_{out}),\quad Y\in\mathbb{R}^{T^{\prime}\times N\times
d_{o}}.$

Here, $T^{\prime}$ represents the number of time steps to be predicted, and
$d_{o}$ signifies the dimension of the output features.

##  5 Experiments

#### Dataset

We evaluate Cy2Mixer’s performance using five real-world public traffic
datasets. These datasets contain three datasets including only the traffic
data, namely PEMS04, PEMS07, and PEMS08 (Song et al., 2020), and three
datasets including inflow and outflow data, namely NYTaxi Liu et al. (2020),
CHBike Wang et al. (2021), and TDrive Pan et al. (2019). The first three
datasets (PEMS04, PEMS07, PEMS08) follow a predictive modeling scheme where
the data from the previous one hour (12-time steps) is utilized to forecast
the data for the subsequent one hour (12-time steps), while the remaining
three datasets (NYTaxi, CHBike, TDrive) use the previous six steps to predict
the next one step. Further details are provided in the Appendix.

#### Baseline models

In this study, we evaluate our proposed approach against various established
baseline methods in traffic forecasting. We include GNN-based methods such as
DCRNN (Li et al., 2017), STGCN (Yu et al., 2017), GWNet (Wu et al., 2019),
MTGNN (Wu et al., 2020), STFGNN Pan et al. (2019) and STGNCDE Choi et al.
(2022a). We also include STTN Xu et al. (2020), GMAN (Zheng et al., 2020),
ASTGNN Guo et al. (2021), PDFormer (Jiang et al., 2023) and STAEFormer (Liu et
al., 2023), all of which are self-attention-based models designed for the same
task as ours.

#### Experimental settings

We configured our experiments using settings consistent with existing
approaches to ensure fair comparisons. The data split ratios for training,
validation, and testing were set to 6:2:2 for PEMS04, PEMS07, and PEMS08, and
7:1:2 for METR-LA and PEMS-BAY. All experiments were conducted on an NVIDIA
A100 GPU and 80GB memory and implemented using Python version 3.10.4 with
PyTorch. We performed a hyperparameter search to select the optimal model
based on its performance on the validation set. Detailed information about
these hyperparameters is available in the Appendix.

For evaluating our model’s performance, we utilized three widely recognized
metrics for traffic forecasting tasks: Mean Absolute Error (MAE), Root Mean
Square Error (RMSE), and Mean Absolute Percentage Error (MAPE). Similar to
prior research, we assessed the average performance across all 12 forecasted
time steps for the PEMS04, PEMS07, and PEMS08 datasets.

#### Results from benchmark datasets

The comparison results between our proposed method and various baselines on
traffic datasets can be found in Table 1. Based on the results presented in
the table, Cy2Mixer outperforms the baseline models across the majority of
datasets. Comparing the results in PEMS04, it can be observed that Cy2Mixer
demonstrates notable improvements, with MAE decreasing from 18.22 to 18.14,
RMSE improving from 30.18 to 30.02, and MAPE showing an enhancement from
11.98% to 11.93%. In the case of the PEMS07 dataset, the proposed model shows
lower performance than STAEFormer compared to other datasets. This is because
there are no cyclic subgraphs for the PEMS07 dataset, as observed in the
Appendix. This outcome underscores the substantial impact of the cycle
message-passing block on the model while demonstrating that the proposed model
can compete favorably with other models even without utilizing $A_{C}$ to
cycle message-passing block. The robust performance observed in the results of
other datasets also demonstrates that Cy2Mixer performs well regardless of the
number of predicted time steps or the number of features.

Table 1: Traffic flow prediction results for PEMS04, PEMS07, and PEMS08. All
prediction results other than the bold method are cited from available results
obtained from pre-existing publications. Highlighted are the top first,
second, and third results.

Datasets Metric DCRNN STGCN GWNET MTGNN STFGNN STGNCDE STTN GMAN ASTGNN
PDFormer STAEFormer Cy2Mixer w/o Cycle block Cy2Mixer PEMS04 MAE 22.74 21.76
19.36 19.08 19.83 19.21 19.48 19.14 18.60 18.36 18.22 18.81 18.14 RMSE 36.58
34.77 31.72 31.56 31.87 31.09 31.91 31.60 31.03 30.03 30.18 30.65 30.02 MAPE
14.75% 13.87% 13.30% 12.96% 13.02% 12.77% 13.63% 13.19% 12.63 12.00% 11.98%
12.86% 11.93% PEMS07 MAE 23.63 22.90 21.22 20.82 22.07 20.62 21.34 20.97 20.62
19.97 19.14 19.51 19.45 RMSE 36.51 35.44 34.12 34.09 35.81 34.04 34.59 34.10
34.02 32.95 32.60 33.02 32.89 MAPE 12.28% 11.98% 9.08% 9.03% 9.21% 8.86% 9.93%
9.05% 8.86% 8.55% 8.01% 8.16% 8.11% PEMS08 MAE 18.19 17.84 15.06 15.40 16.64
15.46 15.48 15.31 14.97 13.58 13.46 13.71 13.53 RMSE 28.18 27.12 24.86 24.93
26.21 24.81 24.97 24.92 24.71 23.41 23.25 23.63 23.22 MAPE 11.23% 11.21% 9.51%
10.17% 10.55% 9.92% 10.34% 10.13% 9.49 9.05% 8.88% 9.01% 8.86% NYTaxi MAE
13.63 13.46 13.30 13.23 14.26 13.28 13.37 13.27 12.98 12.36 12.61 12.61 12.59
RMSE 21..97 21.91 21.71 21.61 23.87 21.68 21.84 21.66 21.19 20.18 20.91 20.53
20.45 MAPE 14.35% 14.16% 13.94% 13.82% 14.73% 13.93% 13.98% 13.89% 13.65%
12.79% 12.96% 13.06% 13.03% TDrive MAE 21.94 21.14 19.55 18.96 22.51 19.29
20.51 19.10 18.79 17.79 16.97 17.48 16.99 RMSE 38.41 37.84 36.18 35.69 40.55
36.12 37.14 36.05 33.93 31.55 31.02 31.31 30.82 MAPE 17.57% 17.26% 16.56%
16.41% 18.54% 16.50% 16.66% 16.45% 15.84% 14.68% 13.81% 13.95% 13.56% CHBike
MAE 4.22 4.18 4.13 4.10 4.25 4.11 4.14 4.10 4.02 3.89 4.03 3.89 3.80 RMSE 5.91
5.87 5.81 5.74 5.90 5.80 5.83 5.79 5.71 5.48 5.70 5.46 5.37 MAPE 31.04% 31.00%
30.92% 30.86% 32.27% 30.87% 31.00% 30.91% 30.91% 30.06% 31.49% 30.10% 29,20%

##  6 Ablation study

#### Effectiveness of cycle message-passing block

The design of the cycle message passing block is crucial since it needs to
provide additional topological information within the network. We performed an
ablation study to evaluate the influence of the cycle message-passing block
more comprehensively. Three models were compared: the results of Cy2Mixer’s
cycle message-passing block using the clique adjacency matrix $A_{C}$, the
results when employing the DTW matrix previously utilized in PDFormer (Jiang
et al., 2023) instead of $A_{C}$ to capture long-range relationships (w/ DTW),
and the results where the cycle message-passing block is not used (w/o Cycle
block), as presented in Table 2. PEMS04, PEMS07, and PEMS08 were chosen as the
datasets for the ablation study due to their varying numbers of nodes and time
steps.

These results indicate that even when both the DTW matrix and $A_{C}$ are not
utilized, the proposed model demonstrates relatively respectable performance
when compared to existing models. However, it is evident that the highest
performance is achieved when $A_{C}$ is employed in the cycle message-passing
block. Notably, under the same conditions, generating the DTW matrix for 307
nodes took over 3 hours, while creating the clique adjacency matrix took less
than a minute. This significant difference in computation time can be
attributed to the fact that the DTW method relies on time-dependent similarity
calculations for each node, whereas the clique adjacency matrix construction
does not necessitate considering all time steps. Based on this result, we can
observe that the mathematical proofs we presented indeed have a significant
impact on the model.

Table 2: Ablation study on effect of cycle message-passing block for PEMS04,
PEMS07, and PEMS08. Note that w/ stands for with and w/o stands for without.

Dataset | PEMS04 | PEMS07 | PEMS08
---|---|---|---
Metric | MAE | RMSE | MAPE | MAE | RMSE | MAPE | MAE | RMSE | MAPE
w/o Cycle block | 18.81 | 30.65 | 12.86% | 19.74 | 33.46 | 8.19% | 13.56 | 23.45 | 8.97%
w/ DTW | 18.44 | 30.66 | 12.16% | 19.72 | 33.35 | 8.31% | 13.65 | 23.50 | 8.94%
Cy2Mixer | 18.14 | 30.02 | 11.93% | 19.50 | 33.28 | 8.19% | 13.53 | 23.22 | 8.86%

These results indicate that even when both the DTW matrix and $A_{C}$ are not
utilized, the proposed model demonstrates relatively respectable performance
when compared to existing models. However, it is evident that the highest
performance is achieved when $A_{C}$ is employed in the cycle message-passing
block. Notably, under the same conditions, generating the DTW matrix for 307
nodes took over 3 hours, while creating the clique adjacency matrix took less
than a minute. This significant difference in computation time can be
attributed to the fact that the DTW method relies on time-dependent similarity
calculations for each node, whereas the clique adjacency matrix construction
does not necessitate considering all time steps. Based on this result, we can
observe that the mathematical proofs we presented indeed have a significant
impact on the model.

#### Case study

We conducted a case study to analyze the influence of each component of
Cy2Mixer by comparing it to variants of the proposed model for PEMS04. First,
to demonstrate the effectiveness of our proposed Cy2Mixer block, we compared
cases where only the temporal block was used and cases where only the spatial
message-passing block was used. In this comparison, the self-attention layer,
designed based on the STAEFormer model Liu et al. (2023), replaced the omitted
block. Additionally, for the spatial message-passing block and cycle message-
passing block, we compared models that either do not use adjacency matrix $A$
and clique adjacency matrix $A_{C}$ or use them. Next, we conducted
experiments by comparing models in which either the spatial message-passing
block or the cycle message-passing block was excluded from the structure of
Cy2Mixer. Finally, to demonstrate the effectiveness of tiny attention, we
compared results with models that did not use tiny attention. The results of
these experiments are summarized in the Table 3.

Table 3: Case study on the structure of Cy2Mixer for PeMS04. Spatial block and
Cycle block refer to the spatial message-passing block and cycle message-
passing block, respectively, while w/o stands for without.

PEMS04 MAE RMSE MAPE only Temporal block 18.55 30.31 12.20% only Spatial block
(not using $A$ and $A_{C}$) 22.53 36.33 15.36% only Spatial and Cycle block
(using $A$ and $A_{C}$) 18.56 30.33 12.32% w/o Spatial block 18.85 30.68
12.72% w/o Cycle block 18.81 30.65 12.86% Cycle block w/ $A$ (not using
$A_{C}$) 18.29 30.05 11.95% w/o Tiny attention 18.36 30.15 12.05% Cy2Mixer
18.14 30.02 11.93%

Not only did each component significantly impact the model’s performance, but
there was also a substantial performance improvement when topological
information was incorporated into both the spatial message-passing block and
the cycle message-passing block through the adjacency matrix and the clique
adjacency matrix. This is evident from the significant reduction in MAE, RMSE,
and MAPE when $A$ and $A_{C}$ were omitted in the spatial message-passing
block (the second result) compared to when they were included (the third
result). This indicates that in Cy2Mixer, these two matrices exert significant
influence on the model’s performance. We compared the model’s performance
using $A$ instead of $A_{C}$ in the cycle message-passing block to assess if
the performance improvement was due to increased parameters or the influence
of $A_{C}$. This comparison demonstrated the effectiveness of $A_{C}$ in
Cy2Mixer, with visualized results provided in the Appendix.

#### Additional experiments for different spatio-temporal learning tasks.

We conducted additional experiments to validate the proposed Cy2Mixer not only
for traffic forecasting but also for various other spatio-temporal tasks.
Among these tasks, we specifically verified its performance in the context of
air pollution prediction. A whole 4-year dataset KnowAir was used for
predicting particles smaller than 2.5$\mu\mathrm{m}$ ($\text{PM}_{2.5}$)
concentrations (Wang et al., 2020a). Dataset covers in total 184 cities, which
can be expressed as nodes, and the dataset is split into 3 sub-datasets based
on dates. Since the compared models in this context differ from the models
used in the main text, Cy2Mixer was compared with models designed for air
pollution prediction; GRU, GC-LSTM (Qi et al., 2019), and
$\text{PM}_{2.5}$-GNN (Wang et al., 2020a). The results of this comparison
were evaluated using root mean squre error (RMSE) and critical success index
(CSI), which are commonly used meteorological metrics, and the results are
presented in Table 4.

Table 4: Air pollution prediction results for KnowAir datasets. All prediction
results other than the bold method are cited from available results obtained
from pre-existing publications. Highlited are the top first, second, and third
results.

Dataset | Sub-dataset 1 | Sub-dataset 2 | Sub-dataset 3
---|---|---|---
Metric | RMSE | CSI(%) | RMSE | CSI(%) | RMSE | CSI(%)
GRU | 21.00 ± 0.17 | 45.38 ± 0.52 | 32.59 ± 0.16 | 51.07 ± 0.81 | 45.25 ± 0.85 | 59.40 ± 0.01
GC-LSTM | 20.84 ± 0.11 | 45.83 ± 0.43 | 32.10 ± 0.29 | 51.24 ± 0.13 | 45.01 ± 0.81 | 60.58 ± 0.14
$\text{PM}_{2.5}$-GNN | 19.93 ± 0.11 | 48.52 ± 0.48 | 31.37 ± 0.34 | 52.33 ± 1.06 | 43.29 ± 0.79 | 61.91 ± 0.78
$\text{PM}_{2.5}$-GNN no PBL | 20.46 ± 0.18 | 47.43 ± 0.37 | 32.44 ± 0.36 | 51.05 ± 1.15 | 44.71 ± 1.02 | 60.64 ± 0.84
$\text{PM}_{2.5}$-GNN no export | 20.54 ± 0.16 | 45.73 ± 0.58 | 31.91 ± 0.32 | 51.54 ± 1.27 | 43.72 ± 1.03 | 61.52 ± 0.95
Cy2Mixer no Cycle block | 19.76 ± 0.13 | 47.95 ± 0.33 | 31.31 ± 0.20 | 52.03 ± 0.95 | 43.27 ± 0.41 | 61.65 ± 0.52
Cy2Mixer | 19.34 ± 0.13 | 48.58 ± 0.56 | 31.29 ± 0.19 | 51.64 ± 0.90 | 43.19 ± 0.98 | 62.06 ± 0.69

Cy2Mixer consistently demonstrated the highest predictive performance across
most datasets. Notably, it achieved this without relying on specific domain
knowledge, distinguishing it from the previous $\text{PM}_{2.5}$-GNN model.
This versatility suggests that the proposed Cy2Mixer can be applied to various
spatio-temporal tasks beyond traffic prediction with ease.

##  7 Conclusion

In this paper, we have mathematically investigated the effects of topological
non-trivial invariants on capturing the complex dependencies of spatio-
temporal graphs. Through our investigation, we gained insight into how the
homotopy invariance of fundamental groups and homology groups can be a
contributing factor in influencing the predictive performance of spatio-
temporal graphs. We then introduce a simple yet novel model, Cy2Mixer, based
on the mathematical background and inspired by gMLP. Cy2Mixer comprises three
major components: a temporal block, a spatial message-passing block, and a
cycle message-passing block. Notably, the cycle message-passing block enriches
topological information in each of the Cy2Mixer encoder layers, drawing from
cyclic subgraphs. Indeed, Cy2Mixer achieves state-of-the-art or second-best
performance on traffic forecast benchmark datasets. We further investigate the
effects of the cycle message-passing block on benchmark datasets to compare
the DTW method, which makes a new adjacency based on the time-dependent
similarity for each node. Compared to the DTW method, the cycle message-
passing block captures the spatio-temporal dependency more effectively with a
significantly lower computational cost. For future work, we plan to extend our
study to other spatio-temporal tasks and additional GNN tasks, such as link
prediction, by integrating self-supervised techniques to enhance predictive
performance compared to other state-of-the-art studies.

## References

  * Berndt and Clifford [1994] Donald J Berndt and James Clifford.  Using dynamic time warping to find patterns in time series.  In Proceedings of the 3rd international conference on knowledge discovery and data mining, pages 359–370, 1994.
  * Bodnar et al. [2021] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Liò, Guido F Montufar, and Michael Bronstein.  Weisfeiler and lehman go cellular: Cw networks.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 2625–2640. Curran Associates, Inc., 2021.
  * Choi et al. [2022a] Jeongwhan Choi, Hwangyong Choi, Jeehyun Hwang, and Noseong Park.  Graph neural controlled differential equations for traffic forecasting.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6367–6374, 2022.
  * Choi et al. [2022b] Yun Young Choi, Sun Woo Park, Youngho Woo, and U Jin Choi.  Cycle to clique (cy2c) graph neural network: A sight to see beyond neighborhood aggregation.  In The Eleventh International Conference on Learning Representations, 2022.
  * Deng et al. [2021] Jinliang Deng, Xiusi Chen, Renhe Jiang, Xuan Song, and Ivor W Tsang.  St-norm: Spatial and temporal normalization for multi-variate time series forecasting.  In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 269–278, 2021.
  * Diao et al. [2019] Zulong Diao, Xin Wang, Dafang Zhang, Yingru Liu, Kun Xie, and Shaoyao He.  Dynamic spatial-temporal graph convolutional neural networks for traffic forecasting.  In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 890–897, 2019.
  * Guo et al. [2021] Shengnan Guo, Youfang Lin, Huaiyu Wan, Xiucheng Li, and Gao Cong.  Learning dynamics and heterogeneity of spatial-temporal graph data for traffic forecasting.  IEEE Transactions on Knowledge and Data Engineering, 34(11):5415–5428, 2021.
  * Hartshorne [1977] Robin Hartshorne.  Algebraic geometry.  Graduate Texts in Mathematics, pages 60–68, 206–224, 1977.
  * Hatcher [2002] Allen Hatcher.  Algebraic Topology.  Cambridge University Press, 2002.
  * Hendrycks and Gimpel [2023] Dan Hendrycks and Kevin Gimpel.  Gaussian error linear units (gelus), 2023.
  * Horn et al. [2021] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt.  Topological graph neural networks.  arXiv preprint arXiv:2102.07835, 2021.
  * Jiang et al. [2023] Jiawei Jiang, Chengkai Han, Wayne Xin Zhao, and Jingyuan Wang.  Pdformer: Propagation delay-aware dynamic long-range transformer for traffic flow prediction.  arXiv preprint arXiv:2301.07945, 2023.
  * Li and Zhu [2021] Mengzhang Li and Zhanxing Zhu.  Spatial-temporal fusion graph neural networks for traffic flow forecasting, 2021.
  * Li et al. [2017] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu.  Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.  arXiv preprint arXiv:1707.01926, 2017.
  * Liu et al. [2020] Lingbo Liu, Jiajie Zhen, Guanbin Li, Geng Zhan, Zhaocheng He, Bowen Du, and Liang Lin.  Dynamic spatial-temporal representation learning for traffic flow prediction.  IEEE Transactions on Intelligent Transportation Systems, 22(11):7169–7183, 2020.
  * Liu et al. [2021] Hanxiao Liu, Zihang Dai, David So, and Quoc V Le.  Pay attention to mlps.  Advances in Neural Information Processing Systems, 34:9204–9215, 2021.
  * Liu et al. [2023] Hangchen Liu, Zheng Dong, Renhe Jiang, Jiewen Deng, Jinliang Deng, Quanjun Chen, and Xuan Song.  Spatio-temporal adaptive embedding makes vanilla transformer sota for traffic forecasting.  arXiv preprint arXiv:2308.10425, 2023.
  * Pan et al. [2019] Zheyi Pan, Yuxuan Liang, Weifeng Wang, Yong Yu, Yu Zheng, and Junbo Zhang.  Urban traffic prediction from spatio-temporal data using deep meta learning.  In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1720–1730, 2019.
  * Park et al. [2022] Sun Woo Park, Yun Young Choi, Dosang Joe, U Jin Choi, and Youngho Woo.  The pwlr graph representation: A persistent weisfeiler-lehman scheme with random walks for graph classification.  In Topological, Algebraic and Geometric Learning Workshops 2022, pages 287–297. PMLR, 2022.
  * Paton [1969] Keith Paton.  An algorithm for finding a fundamental set of cycles of a graph.  Communications of the ACM, 12(9):514–518, 1969.
  * Qi et al. [2019] Yanlin Qi, Qi Li, Hamed Karimian, and Di Liu.  A hybrid model for spatiotemporal forecasting of pm2. 5 based on graph convolutional neural network and long short-term memory.  Science of the Total Environment, 664:1–10, 2019.
  * Shao et al. [2022a] Zezhi Shao, Zhao Zhang, Fei Wang, Wei Wei, and Yongjun Xu.  Spatial-temporal identity: A simple yet effective baseline for multivariate time series forecasting.  In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 4454–4458, 2022.
  * Shao et al. [2022b] Zezhi Shao, Zhao Zhang, Wei Wei, Fei Wang, Yongjun Xu, Xin Cao, and Christian S Jensen.  Decoupled dynamic spatial-temporal graph neural network for traffic forecasting.  arXiv preprint arXiv:2206.09112, 2022.
  * Song et al. [2020] Chao Song, Youfang Lin, Shengnan Guo, and Huaiyu Wan.  Spatial-temporal synchronous graph convolutional networks: A new framework for spatial-temporal network data forecasting.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 914–921, 2020.
  * Vlahogianni et al. [2004] Eleni I Vlahogianni, John C Golias, and Matthew G Karlaftis.  Short-term traffic forecasting: Overview of objectives and methods.  Transport reviews, 24(5):533–557, 2004.
  * Wang et al. [2020a] Shuo Wang, Yanran Li, Jiang Zhang, Qingye Meng, Lingwei Meng, and Fei Gao.  Pm2. 5-gnn: A domain knowledge enhanced graph neural network for pm2. 5 forecasting.  In Proceedings of the 28th international conference on advances in geographic information systems, pages 163–166, 2020.
  * Wang et al. [2020b] Xiaoyang Wang, Yao Ma, Yiqi Wang, Wei Jin, Xin Wang, Jiliang Tang, Caiyan Jia, and Jian Yu.  Traffic flow prediction via spatial temporal graph neural network.  In Proceedings of the web conference 2020, pages 1082–1092, 2020.
  * Wang et al. [2021] Jingyuan Wang, Jiawei Jiang, Wenjun Jiang, Chao Li, and Wayne Xin Zhao.  Libcity: An open library for traffic prediction.  In Proceedings of the 29th international conference on advances in geographic information systems, pages 145–148, 2021.
  * Wu et al. [2019] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang.  Graph wavenet for deep spatial-temporal graph modeling.  arXiv preprint arXiv:1906.00121, 2019.
  * Wu et al. [2020] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang.  Connecting the dots: Multivariate time series forecasting with graph neural networks.  In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 753–763, 2020.
  * Xu et al. [2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?, 2019.
  * Xu et al. [2020] Mingxing Xu, Wenrui Dai, Chunmiao Liu, Xing Gao, Weiyao Lin, Guo-Jun Qi, and Hongkai Xiong.  Spatial-temporal transformer networks for traffic flow forecasting.  arXiv preprint arXiv:2001.02908, 2020.
  * Yin et al. [2015] ChuanTao Yin, Zhang Xiong, Hui Chen, JingYuan Wang, Daven Cooper, and Bertrand David.  A literature survey on smart cities.  Sci. China Inf. Sci., 58(10):1–18, 2015.
  * Yu et al. [2017] Bing Yu, Haoteng Yin, and Zhanxing Zhu.  Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting.  arXiv preprint arXiv:1709.04875, 2017.
  * Zheng et al. [2020] Chuanpan Zheng, Xiaoliang Fan, Cheng Wang, and Jianzhong Qi.  Gman: A graph multi-attention network for traffic prediction.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 1234–1241, 2020.
  * Zhu et al. [2023] Weiguo Zhu, Yongqi Sun, Xintong Yi, Yan Wang, and Zhen Liu.  A correlation information-based spatiotemporal network for traffic flow forecasting.  Neural Computing and Applications, pages 1–19, 2023.

##  Appendix A Appendix

#### Dataset description

A detail of statistical information of six traffic datasets is outlined in
Table 5. The first three datasets are graph-based datasets, each with a single
feature, while the latter three are grid-based datasets with two features. The
node counts for the grid-based datasets are 75 (15$\times$5), 270
(15$\times$18), and 1,024 (32$\times$32), respectively. The term “# Cycles”
indicates the number of the cycle bases of graphs, and the term “Average
Magnitude # Cycles” denotes the average number of nodes present in a cycle
subgraph of a graph.

Table 5: Description of statistical information of six traffic datasets.

Datasets | # Nodes | # Edges | # Timesteps | # Time Interval | Time range | # Features | # Cycles | Average Magnitude # Cycles
---|---|---|---|---|---|---|---|---
PEMS04 | 307 | 340 | 16,992 | 5 min | 01/01/2018-02/28/2018 | 1 | 45 | 4.9111
PEMS07 | 883 | 866 | 28,224 | 5 min | 05/01/2017-08/31/2017 | 1 | 0 | 0
PEMS08 | 170 | 295 | 17,856 | 5 min | 07/01/2016-08/31/2016 | 1 | 105 | 7.8571
NYCTaxi | 75 | 484 | 17,520 | 30 min | 01/01/2014-12/31/2014 | 2 | 168 | 4.8810
TDrive | 270 | 1,966 | 4,416 | 30 min | 07/01/2020-09/30/2020 | 2 | 2883 | 14.4707
CHBike | 1,024 | 7,812 | 3,600 | 60 min | 02/01/2015-06/30/2015 | 2 | 714 | 7.9174

#### Hyperparameter search

We conducted a hyperparameter search to find the model, and hyperparameters
for each dataset are listed in Table 6. Note that the embedding dimensions,
$d_{f}$, $d_{t}$, and $d_{a}$, followed the settings of previous research Liu
et al. [2023]. The search ranges were $\\{16,32,64,128\\}$ for hidden
dimension $d_{h}$, $\\{2,3,4,5,6\\}$ for number of layers, and
$\\{0,0.2,0.4,0.6,0.8\\}$ for dropout rate, respectively. Considering previous
research has demonstrated the effectiveness of incorporating tiny attention,
we conducted experiments in our study to compare the performance when tiny
attention is added and when it is not. The selection of the optimal model was
based on its performance on the validation set. We perform the experiments on
STAEFormer [Liu et al., 2023] framework.

Table 6: Hyperparameters for six traffic datasets.

Datasets | # Layers | $d_{f}$ | $d_{t}$ | $d_{a}$ | $d_{h}$ | Batch size | Dropout | Weight decay | Learning rate | Learning rate decay | Tiny attention
---|---|---|---|---|---|---|---|---|---|---|---
PEMS04 | 3 | 24 | 24 | 80 | 152 | 16 | 0.4 | 0.0005 | 0.001 | 0.1 | O
PEMS07 | 4 | 24 | 24 | 80 | 152 | 16 | 0.4 | 0.001 | 0.001 | 0.1 | X
PEMS08 | 3 | 24 | 24 | 80 | 152 | 16 | 0.1 | 0.0015 | 0.001 | 0.1 | O
NYCTaxi | 5 | 24 | 24 | 80 | 256 | 16 | 0.4 | 0.05 | 0.001 | 0.1 | X
TDrive | 6 | 24 | 24 | 80 | 256 | 16 | 0.4 | 0.05 | 0.001 | 0.1 | X
CHBike | 3 | 24 | 24 | 80 | 256 | 16 | 0.4 | 0.05 | 0.001 | 0.1 | O

#### Comparison of the adjacency matrix, clique adjacency matrix, and DTW
matrix.

In this section, a detailed comparison is conducted between the adjacency
matrix and clique adjacency matrix used in Cy2Mixer and the DTW matrix
employed in PDFormer Jiang et al. [2023]. Three matrices that can be
constructed from the traffic network, namely the adjacency matrix $A$, the
clique adjacency matrix $A_{C}$, and the matrix derived from DTW, can be found
in Fig. 3. DTW algorithm is a similarity measure between two time-series that
allows for non-linear alignment of the time series. In the context of
PDFormer, DTW is used to compute the similarity of the historical traffic flow
between nodes to identify the semantic neighbors of each node by calculating a
pairwise distance matrix encompassing all combinations of historical traffic
flow sequences. This distance matrix aids in the computation of a cumulative
distance matrix, representing the minimum distance between two time-series up
to a specific point. Finally, the cumulative distance matrix facilitates the
determination of the optimal warping path, signifying the most favorable
alignment between two time-series. DTW algorithm allows the model to capture
complex traffic patterns that are not easily captured by linear alignment
methods, but it has a significant drawback: it is computationally time-
consuming to compute and often relies on heuristic thresholds and parameters.
To overcome these limitations and capture the desired spatio-temporal
dependencies, we employ the use of the clique adjacency matrix. The clique
adjacency matrix can be computed more efficiently than DTW since it is not
dependent on time. Furthermore, it provides the model with richer topological
information within the graph.

(a) Adjacency matrix

(b) Clique adjacency matrix

(c) Matrix constructed by DTW algorithm

Figure 3: Three matrices of PEMS04: (a) Adjacency matrix $A$, (b) Clique
adjacency matrix $A_{C}$, and (c) Matrix constructed by DTW algorithm,
respectively.

#### Visualization of prediction results for each node

In this section, we present the actual prediction results for each node in
Cy2Mixer, as shown in Fig 4. To determine whether the cycle block had a
significant impact on predictions, we compare the results of Cy2Mixer and a
model that uses adjacency matrix $A$ instead of clique adjacency matrix
$A_{C}$ in the cycle block over 3 hours, or 36 steps, for Node 170, Node 173
connected to Node 170 through the adjacency matrix, and Nodes 0 and 169
connected through the clique adjacency matrix. While both models show similar
performance for Nodes 170 and 173, Cy2Mixer demonstrates better prediction
accuracy for Nodes 0 and 169. This indicates that the cycle block effectively
incorporates information from the clique adjacency matrix.

Figure 4: Visualization of prediction results of Node 170, Node 173 (Connected
to Node 170 in the adjacency matrix), and Nodes 0 and 169 (Connected to Node
170 in the clique adjacency matrix.) in PEMS04 dataset.

#### Comparison of the influence of the predefined adjacency matrix

In this section, we compared whether a predefined adjacency matrix, calculated
based on the distances between nodes, makes a significant difference in the
model’s performance. Recent studies in traffic prediction problems have
explored not using a predefined adjacency matrix, instead learning it
alongside the model Wu et al. [2020]. To conduct this comparison, we adopted
methods from previous studies to create an adjacency matrix and then generated
a clique adjacency matrix from it for training in Cy2Mixer. The results of
this approach are presented in Table 7.

Table 7: Ablation study on effect of predefined adjacency matrix PEMS04,
PEMS07, and PEMS08. Note that w/ stands for with and w/o stands for without.

Dataset | PEMS04 | PEMS07 | PEMS08
---|---|---|---
Metric | MAE | RMSE | MAPE | MAE | RMSE | MAPE | MAE | RMSE | MAPE
w/o Cycle block | 18.81 | 30.65 | 12.86% | 19.74 | 33.46 | 8.19% | 13.56 | 23.45 | 8.97%
w/ learned $A$, $A_{C}$ | 18.81 | 30.54 | 12.22% | 19.74 | 33.37 | 8.33% | 13.56 | 23.46 | 8.92%
Cy2Mixer | 18.14 | 30.02 | 11.93% | 19.50 | 33.28 | 8.19% | 13.53 | 23.22 | 8.86%

The findings indicate that Cy2Mixer does not show significant differences in
performance between using a predefined $A$ and a learned $A$. Particularly,
since learning $A$ and subsequently generating $A_{C}$ is costly, this study
utilized a predefined $A$.