# Time-Evolving Graph Convolutional Recurrent Network for Traffic Prediction
## 3 Proposed Method
### Graph Convolution Module  
A graph convolution module is used to capture spatial patterns by aggregating information based on the adjacency graphs. In our proposed model, we conduct graph convolution with both the aforementioned adaptive time-evolving graphs and predefined distance-based static graph. In this way, the static graph captures local patterns, and the time-evolving graphs provide dynamic inter-node dependency from a global view as a complement.  
Following [12], we build a distance-based static graph \(\mathbf{A^{s}}\) using thresholded Gaussian kernel [34] as:  
\[\mathbf{A^{s}_{i,j}}=\left\{\begin{aligned} &\exp\left(-\frac{d_{v_{i},v_{j}}^{2}}{ \sigma^{2}}\right),& d_{v_{i},v_{j}}\leq\kappa\\ & 0,&\mathit{others}\end{aligned}\right., \tag{5}\]  
where \(d_{v_{i},v_{j}}\) denotes the shortest directed distance from node \(v_{i}\) to node \(v_{j}\) in the road network, \(\sigma\) denotes the standard deviation of these distances, and \(\kappa\) is the threshold to control the sparsity of the graph.  
As mentioned in the Section 3.2, in our proposed model the graph convolution operations are integrated with an RNN structure. The recurrent manner in RNN inherently expands the depth of the model. In fact, GCNs may suffer from performance degradation due to the over-smoothing problem when the layers go deeper [31]. It is also argued that the entanglement of information propagation and feature transformation in GCN may limit the model performance [35]. By decoupling feature transformation with propagation and adding residual of input representation [36], or combining the representations of multiple layers [26], these problems can be relieved to some extent. Motivated by these ideas, we employ graph convolution operations in two steps: information propagation and weighted mix-hop operation, similar to the method in [21]. First, for a certain type of adjacency graph, the node information is propagated according to the graph topology and the node representations of \(K\) hops are generated. Denote the origin node representation as \(\mathbf{H_{in}}\in\mathbb{R}^{N\times d_{in}}\), and the representation of the \(k\)-th hop \(\mathbf{H}^{(k)}\) is calculated as:  
\[\mathbf{H}^{(k)}=(1-\alpha)\widetilde{\mathbf{A}}\mathbf{H}^{(k-1)}+\alpha \mathbf{H_{in}}, \tag{6}\]  
where \(\alpha\) is a hyper-parameter to control the ratio of residual original information, \(\widetilde{\mathbf{A}}\in\mathbb{R}^{N\times N}\) is the normalized form of the adjacency graph. Then, weighted mix-hop operation is employed to obtain \(\mathbf{H_{mix}}\in\mathbb{R}^{N\times d_{out}}\) using the propagated representations of all hops as per the following formula:  
\[\mathbf{H_{mix}}=\sum_{k=0}^{K}\mathbf{H}^{(k)}\mathbf{W}^{(k)}, \tag{7}\]  
where \(\mathbf{H}^{(0)}=\mathbf{H_{in}}\), \(\mathbf{W}^{(k)}\in\mathbb{R}^{d_{in}\times d_{out}}\) is the learnable weighted transformation matrix.  
For a time slot \(t\), the corresponding index in a day is \(l_{t}\), graph convolution operations are applied using three graphs: the time-evolving graph in this time slot \(\mathbf{A^{te}_{l_{t}}}\), the distance-based static graph \(\mathbf{A^{s}}\) and its transposed one \(\mathbf{A^{sT}}\). For \(\mathbf{A^{s}}\) and \(\mathbf{A^{sT}}\), asymmetric normalization is applied with \(\widetilde{\mathbf{A}}=\widetilde{\mathbf{D}}^{-1}(\mathbf{A}+\mathbf{I}_{N})\) and \(\widetilde{\mathbf{D}}_{ii}=1+\sum_{j}\mathbf{A}_{ij}\). The time-evolvinggraphs have been normalized during generation. We further aggregate the mix-hop representations of these three graphs to obtain the final output of the entire graph convolution module \(\mathbf{H_{out}}\). For convenience, we briefly denote the calculations in this module as \(\mathbf{H_{out}}=\Theta*_{G}(\mathbf{H_{in}},\mathbf{A_{{}_{\!I_{t}}}^{1e}})\), where \(*_{G}\) denotes the graph convolution operation, \(\Theta\) represents all the trainable parameters in a module. The static graph remains the same in all modules so we omit its notation in the formula.