# Time-Evolving Graph Convolutional Recurrent Network for Traffic Prediction
## 3 Proposed Method
### Generation of Time-Evolving Adaptive Graphs  
As mentioned above, the spatial relationships among traffic nodes vary along with time, so our aim is to model these dynamics adaptively using time-evolving adjacency graphs. Moreover, we assume that the dynamics of the spatial adjacency also follow the periodicity in a day. Thus, the same time slot on different days can share a graph. Previous works [14; 21] adopt matrix multiplication of trainable node embeddings to construct static adjacency graphs. The obtained adaptive graphs are evaluated to be effective in capturing global spatial information. To extend the adaptive graph to a time-evolving manner, a simple idea is to directly assign a distinct set of node-embedding parameters to each time slot. However, such a method may lead to a large number of trainable parameters, making it hard to converge, especially when the number of traffic nodes \(N\) is large. To reduce the number of model parameters, we employ a tensor-composing method similar to [32] to generate the time-evolving adjacency graphs.  
Suppose that a day is divided into \(N_{t}\) time slots, and the traffic network contains \(N\) traffic nodes. We first construct three embedding matrices \(\mathbf{E}^{t}\in\mathbb{R}^{N_{t}\times d}\), \(\mathbf{E}^{s}\in\mathbb{R}^{N\times d}\), \(\mathbf{E}^{e}\in\mathbb{R}^{N\times d}\) and a core tensor \(\mathbf{C}\in\mathbb{R}^{d\times d\times d}\), where \(d\) is the embedding dimension, \(d\ll N\). Specifically, \(\mathbf{E}^{t}\) represents the embedding matrix of different time slots in a day, \(\mathbf{E}^{s}\) represents the embedding matrix of source nodes, \(\mathbf{E}^{e}\) represents the embedding matrix of target nodes. Tensor \(\mathbf{C}\) builds connections among these embeddings and models the implicit factors shared across time and space. All these embeddings and the core tensor are trainable and randomly initialized. Next, a spatiotemporal tensor \(\mathbf{A}^{\prime}\in\mathbb{R}^{N_{t}\times N\times N}\) is calculated as the following formula:  
\[\mathbf{A}^{\prime}=\mathbf{C}\times_{1}\mathbf{E}^{t}\times_{2}\mathbf{E}^{s }\times_{3}\mathbf{E}^{e}, \tag{2}\]  
where \(\times_{i}\) denotes the tensor mode-\(i\) product [33]. Specifically, the elements in \(\mathbf{A}^{\prime}\) can be denoted as  
\[\mathbf{A}^{\prime}_{i,j,k}=\sum_{w=1}^{d}\sum_{v=1}^{d}\sum_{u=1}^{d}\mathbf{ C}_{u,v,w}\mathbf{E}^{t}_{i,u}\mathbf{E}^{s}_{j,v}\mathbf{E}^{e}_{k,w}. \tag{3}\]  
Then, non-linear transformation and normalization are applied to \(\mathbf{A}^{\prime}\) to obtain the tensor of time-evolving graphs \(\mathbf{A}^{te}\in\mathbb{R}^{N_{t}\times N\times N}\):  
\[\mathbf{A}^{te}=softmax\big{(}LeakyReLU\big{(}\mathbf{A}^{\prime}\big{)}\big{)}, \tag{4}\]  
Figure 3: Overview of the proposed model TEGCRN.  
where the softmax normalization is operated in the last dimension. The \(l\)-th slice of \(\mathbf{A^{te}}\) along its first dimension \(\mathbf{A^{te}_{i}}\) is the adaptive spatial adjacency graph of the \(l\)-th time slot in a day.  
With the approach above, we build connections between the representations of traffic nodes and the representations of time slots through the calculations of tensor composing. The resulting adaptive time-evolving graphs actually denote how much importance should be attached to different node pairs in different time slot of a day when aggregating spatial information in the road network. Later, these graphs will be used in the graph convolution module to extract detailed spatial information.