Spatial-temporal traffic modeling with a fusion graph reconstructed by tensor decomposition

Traditional convolution has a strong ability to explore local spatial correlations, but it is mainly qualified for handling standard grid data rather than non-Euclidean data such as the rode-network traffic data. Recently, graph convolution networks, which can remedy this limitation and capture the structural characteristics of networks, have been developed rapidly. There are mainly two categories of graph convolution neural networks: Spectral GCN and Spatial GCN. Spectral GCN transforms the convolution networks from the spatial domain into the spectral domain for convenience of leveraging the spectral theory to conduct convolution operation on the graph directly. The SCNN model proposed by [27] adopted a learnable diagonal matrix to replace the convolution kernel of the spectral domain and realizes the graph convolution operation. However, it is time-consuming to calculate the eigenvalue decomposition of the Laplacian matrix and the model parameters are complex. In order to solve the above problems, ChebNet model was proposed by [28], which used Chebyshev polynomials instead of convolution kernels in the spectral domain, and saves time without decomposition. To further simplify the model, [29] proposed the first-order ChebNet model, in which each convolution kernel has only one parameter. Spatial GCN generalizes the traditional convolutional network from the Euclidean space to the vertice domain directly. The GNN model [30] uses the random walk method to transform the graph structure data, but it tried to force a graph to be a rule structure. GraphSAGE [31] sampled the neighbor vertices of each vertex in the graph, and then aggregated the information contained in the neighbor vertices according to the aggregation function. GAT [32], a powerful GCN variant, aggregated the features of neighboring vertices to the center vertex through using attention layers to adjust the importance of neighbor nodes dynamically.

Traffic flow forecasting belongs to correlated time series analysis (or multivariate time series analysis) and has been studied for decades. Owing to the strong learning and nonlinear representation abilities, deep learning based traffic flow forecasting methods have been extensively researched and gained outstanding achievements. Most previous studies of this kind [33, 34, 35] have relied on LSTM or GRU to model the temporal dynamics of the sequential traffic data. Some studies use temporal convolutional networks [36] to enable the model to process extremely long-time sequences with less time. Although employing temporal correlations of traffic data fully to improve the prediction accuracy, these models neglects the spatial correlation among the traffic series from different sources (spaces/regions/sensors) which may have a great influence on the prediction results. Then, CNN that is apt at learning the spatial correlation was introduced to capture temporal and spatial correlations simultaneously with RNN to improve the prediction accuracy[37, 38, 39, 40].

Although the hybrid model of CNN and RNN improved the prediction performances significantly, it can only deal with data in the Euclidean space, hence fail to fully represent and dig the comprehensive structural information of the real-world large-scale road network that is spatially irregular and topological. Subsequently, GCN-based models that process the road network as a graph directly, avoiding to destroy the topological structure are utilized for more practical traffic data forecasting. Some works[21, 41] deployed a spectral-domain GCN to capture the spatial correlations among traffic series and used RNN to model and aggregate the temporal correlations to improve the prediction accuracy. Many recent studies [42, 43] further use complex spatial-temporal attention mechanisms to help a spectral-domain GCN to capture dynamic spatial-temporal correlations. However, the spectral-based method, in which the graph structure is fixed, is computationally complex. Recently, researches gradually pay attention to the Spatial GCN based traffic data forecasting models[16, 44, 20, 22, 23], and demonstrated the main concerns to improve the prediction accuracy are to construct a adjacency graph as informative as enough and to implement effective convolution on the graph to aggregate the spatial-temporal features.

Tensor decomposition is the higher-order generalization of matrix decomposition [45]. It decomposes high-dimensional tensors into a sum of products of lower dimensional factors. Due to its strong capability of uncovering underlying the hidden low-dimensional structure of high-dimensional data, tensor decomposition has been widely used for data compression, dimension reduction, missing data recovery, and etc [46].

One of the features and benefits of deep learning models is the deep structure, which whereas leads to numerous model training parameters and low training efficiency. Motivated by the data compression methods, some researchers tried to utilize tensor decomposition to compress the neural model for deep learning to make a trade-off between the precision and computational efficiency. There are mainly three kinds of tensor decomposition based neural model compression methods. The first kind is to compress the whole deep learning architectures through constructing the corresponding tensor network representation, which has been successfully applied to Restricted Boltzmann Machines and convolutional architectures[47]. The second kind leverages tensor decomposition on the single layers of the network. For instance, [48] introduced the Tucker Tensor Layer as an alternative to the dense weight-matrices of neural networks. Besides, [49] introduced a multitask representation learning framework leveraging tensor factorisation to share knowledge across tasks in fully connected and convolutional DNN layers.

The use of tensor decomposition methods in graph data processing appears a lively research field recently. Tensor decomposition extracts the hidden information or main components in the original higher-order data. Graph neural networks perform end-to-end calculations on graph data. However, these graph data contain plenty of potential information. Hence, tensor decomposition is adopted to mine the hidden information of the graph data for improving the performances of the graph neural networks. For instances, to reduce the computational burden, Xu [50] utilized Tucker decomposition to perform separate filtering in small-scale space, time, and feature modes, while Zhao [51] used tensor decomposition to extract the graph structure features of each view in the common feature space.Such kinds of models have also been adopted to traffic data forecasting[52, 53].

It can been seen that the cooperation of tensor decomposition helps improve the efficiency and accuracy of deep learning including the graph neural networks models.

Inspired by [22], as shown in Fig. 1, we unify the relationship of a node with its spatially neighboring nodes and the relationship of the node with itself in neighboring time steps into a graph as input.

As shown in Fig. 2(a), we use $A_{S}^{t_{i}}\in R^{N\times N}$ to represent the adjacent matrix of the given spatial graph in the $t_{i}$ time step and $A_{T}^{t_{l}\rightarrow t_{k}}\in R^{N\times N}$ to represent the adjacent matrix of the temporal graph between the adjacent time steps $t_{l}$ and $t_{k}$, which equals to the connectivity denoted by the blue arrows in Fig. 1. $A\in R^{3N\times 3N}$, a block matrix, is made up of $A_{S}^{t_{i}}$ and $A_{T}^{t_{l}\rightarrow t_{k}}$, which represents the adjacent matrix of the localized spatial-temporal graph constructed from Fig. 1. $A_{S}^{t_{i}}$ or $A_{T}^{t_{l}\rightarrow t_{k}}$ is the single block of $A$. For each node $i$ in the spatial graph, we recalculate its new index in the local spatial-temporal graph by $(t-1)N+i$, where $t(1\leq t\leq 3)$ represents the time step number in the local spatial-temporal graph. The entries of $A$ are denoted as:

where $v_{i}$ denotes the node $i$ in localized spatial-temporal graph.

However, the 0-1 binary entries can only depict whether there is connectivity between two adjacent nodes, but fail to show the magnitude of the connectivity (i.e. the weight of each entry). To solve this problem, many existing researches[22, 23]update the weights of each block (sub-graph) separately though learning models, which leads to increment in the volume of model learning parameters and ignores the possible potential correlations among the blocks, e.g, the spatial connectivity in the $t_{1}$ time step $A_{S}^{t_{1}}$ may be correlated with that in the $t_{2}$ time step $A_{S}^{t_{2}}$. Instead, this paper tries to utilize an information maximization mapping method that attempts to minimize the model parameters and consider the spatial-temporal correlations among the blocks fully to update the weights of all the entries of $A$ simultaneously, i.e. reconstruct the graph. First, for more general and natural spatial-temporal correlations expression [24], we construct the block matrix $A$ into a tensor model as $\mathcal{A}\in R^{N\times N\times M}$ through a reshaping operation, as shown in Fig. 2(b), in which N represent the number of nodes in the spatial graph, and $M=9$ represents the number of blocks in $A$. The $(k,l)\textit{th}$ block in the block matrix $A$ is arranged as the $(l+3(k-1))\textit{th}$ lateral slice in the tensor $\mathcal{A}$. Then, Tucker decomposition, a kind of multiple linear mapping, is deployed to reconstruct $\mathcal{A}$. It decomposes $\mathcal{A}$ into a core tensor $\mathcal{G}$ multiplied by the factor matrix $U_{i},i=1,2,3$ along each mode as follows:

where, $\mathcal{G}\times_{i}U_{i}$ denotes the n-mode product of $\mathcal{G}\in R^{P\times Q\times R}$ with $U_{i}\in R^{L_{i}\times P}$, $L_{i}$ is the dimension of the i-th mode of $A$; P, Q and R are the number of components (i.e., columns) in the factor matrices; $\circ$ represents the vector outer product and $u_{i_{p}}$ is the p-th column vector of $U_{i}$. Finally, the core tensor $\mathcal{G}$, which can capture the hidden information and interaction characteristics among each mode of $\mathcal{A}$, is used to reconstruct the fusion graph as ${A}^{\prime}$ off-line though an unfolding-like operation, as shown in Fig. 2(c). Specifically, in the unfolding-like operation, every three slices $\mathcal{G}(:,:,m:m+2)$ are arranged in the m-th row of the new block matrix ${A}^{\prime}$. The objective function of Tucker decomposition for $\mathcal{A}$ is compactly formulated as:

where $\mathbb{S}(D,d)=\left\{\mathbf{U}\in\mathbb{R}^{D\times d};\quad\mathbf{U}^{\top}\mathbf{U}=\mathbf{I}_{d}\right\}$ is the Stiefel manifold containing all rank-d orthonormal bases in $\mathbb{R}^{D}$ and $\|\cdot\|_{F}^{2}$ denotes the L2 (or Frobenius) norm returning the summation of the squared entries of its tensor argument. If $\left\{\mathbf{U}_{n}^{\mathrm{tckr}}\right\}_{n\in[N]}$ is solution to 4, then the core tensor is expressed by:

Specifically, the L1-Tucker decomposition [54], an improved Tucker decomposition model which replaces the L2 norm in the objective function of Tucker decomposition into L1 norm and has shown high efficiency, is adopted in this paper. The objective function of the L1-Tucker decomposition for $\mathcal{A}$ is as follows:

It is notable that, to keep the size of the graph unchangeable, during the tensor decomposition, the size of the core tensor is fixed as the as same as the original tensor.

The Spatial-Temporal Synchronous Graph Convolutional Module (STSGCM) [22] is deployed in this paper to capture the localized spatial-temporal heterogeneous correlations in the graph reconstructed in Section 4.1. Furthermore, to learn the global spatial-temporal homogeneous correlations, we assemble a Dilated Convolution Module [16] with STSGCM into a spatial- temporal tensor graph convolution layer (STTGCL). Fig 3 shows the specific structure of the model.

We verified the effectiveness of our proposed model on four highway traffic datasets (http://pems.dot.ca.gov/). These data are collected from the Caltrans Performance Measurement System (PeMS). The flow data is aggregated to 5 minutes, which means there are 12 points in the traffic flow data for one hour and 288 points for one day. Table I provides the detailed information of the four datasets. One hour 12 continuous time steps historical data is used to predict next hour’s 12 continuous time steps data.

Our proposed model will be compared with the following models:

• •

  SVR [56]: Support Vector Regression is a classical traditional time series analysis model.

• •

  LSTM [12]: Long-Short Term Memory belongs to a typical kind of Recurrent Neural Networks.

• •

  DCRNN [44]: Diffusion Convolution Recurrent Neural Network is a model that uses diffusion recurrent neural networks to capture spatial-temporal dependencies.

• •

  STGCN [16]: Spatial-temporal Convolution Network integrates Chebnet and 2D convolution to obtain spatial-temporal correlations.

• •

  ASTGCN(r) [42]: Attention Based Spatial Temporal Graph Convolutional Networks introduces spatial-temporal attention mechanisms into the graph convolution network model. Only recent components of modeling periodicity is taken to keep fair comparison

• •

  Graph WaveNet [20]: A framework combines adaptive adjacency matrix into graph convolution with 1D dilated convolution.

• •

  STSGCN [20]: Spatial-temporal Synchronous Graph Convolution Network uses local spatiotemporal sub-graph modules to independently model local correlations.

• •

  STFGNN [23]: Spatial-Temporal Fusion Graph Neural Networks integrates the fusion graph module and a new gate convolution module into a unified layer, which can learn the temporal and spatial dependencies to deal with long sequences.

To keep fair comparison with the previous works, all the data is split with the ratio 6:2:2 into training sets, verification sets and test sets. All experiments are repeated on all datasets for ten times.

The number of time steps in a local temporal-spational network is selected as 3 and the model consists of 4 STTGCLs. Each STTGCM includes 3 graph convolutional operations with 64, 64, 64 filters respectively. The dilated coefficient of the dilated convolution module is 2. In the training process, we set the batch size to be 32, learning rate to be 0.003 and epoch equals to 5000, and we used an early-stop strategy. The threshold parameter of loss function $\delta$ is 1. All experiments were trained and tested under the computational environment with one Intel(R) Core(TM) i9-12900KF CPU @ 5.20Ghz and NVIDIA GeForce RTX 3090 Ti. Besides, in this work, we deploy the core tensor obtained by the tensor decomposition to reconstruct the graph adjacency matrix. Since the diagonal entries of the core tensor represent the connection of a node with itself at the same time step, which should be the largest theoretically. So we adjust them to be the max value 1 manually during the decomposition.

The mean absolute error(MAE), the mean absolute percentage error (MAPE) and the root mean square error (RMSE) are used to evaluate the prediction performances of the proposed model:

where n is the total number of 5-min traffic flow data for prediction in test datasets. $Y$ and $Y^{\prime}$ are the true and predicted values respectively.