# Time-Evolving Graph Convolutional Recurrent Network for Traffic Prediction
## 3 Proposed Method
### Temporal Recurrent Module  
RNN is devised as a recurrent structure which processes input signals and updates hidden states step-by-step. This kind of structure is suitable for combining with time-evolving graphs to model the dynamics of spatial dependency. As is shown in Figure 3, in each time step, a different adaptive graph is selected according to the time index in a day. Then, following [12,19], we replace the matrix multiplication in GRU with the graph convolution module introduced in the previous subsection. The structure of the resulting recurrent unit is shown in Figure 4, which is referred to as Time-evolving Graph Convolutional GRU (TGCGRU).  
For each time slot \(t\), given the corresponding time-evolving graph \(\mathbf{A_{{}_{\!I_{t}}}^{1e}}\), the calculations in TGCGRU are formulated as follows:  
\[\begin{split}\mathbf{r}_{t}&=\sigma\Big{(}\Theta_{ r}*_{G}\left(\mathbf{X}_{t}\|\mathbf{H}_{t-1},\mathbf{A_{{}_{\!I_{t}}}^{1e}} \right)+\mathbf{b}_{r}\Big{)},\\ \mathbf{u}_{t}&=\sigma\Big{(}\Theta_{u}*_{G}\left( \mathbf{X}_{t}\|\mathbf{H}_{t-1},\mathbf{A_{{}_{\!I_{t}}}^{1e}}\right)+\mathbf{ b}_{u}\Big{)},\\ \mathbf{C}_{t}&=\tanh\!\Big{(}\Theta_{c}*_{G}\left( \mathbf{X}_{t}\|(\mathbf{r}_{t}\odot\mathbf{H}_{t-1}),\mathbf{A_{{}_{\!I_{t}}}^ {1e}}\right)+\mathbf{b}_{c}\Big{)},\\ &\quad\mathbf{H}_{t}=\mathbf{u}_{t}\odot\mathbf{H}_{t-1}+(1- \mathbf{u}_{t})\odot\mathbf{C}_{t},\end{split} \tag{8}\]  
where \(\mathbf{X}_{t}\in\mathbb{R}^{N\times F}\), \(\mathbf{H}_{t}\in\mathbb{R}^{N\times h}\) denote the input traffic features and output hidden state at time step \(t\), respectively, \(h\) is the hidden size of TGCGRU. The notation \(\|\) denotes concatenation operation, \(\sigma(\cdot)\) is the sigmoid function, and \(\odot\) denotes the Hadamard product. \(\mathbf{r}_{t}\in\mathbb{R}^{N\times h}\) and \(\mathbf{u}_{t}\in\mathbb{R}^{N\times h}\) represent the reset gate and update gate, respectively. \(\Theta_{r}\), \(\Theta_{u}\), \(\Theta_{C}\) are parameters for the corresponding graph convolution modules and \(\mathbf{b}_{r}\in\mathbb{R}^{N}\), \(\mathbf{b}_{u}\in\mathbb{R}^{N}\), \(\mathbf{b}_{C}\in\mathbb{R}^{N}\) are trainable bias vectors. These parameters share all the time steps.  
We stack multiple TGCGRUs to form an RNN sequence-to-sequence architecture [37] for multi-step traffic prediction, as is shown at the top of Figure 3. On the decoder side, an additional fully-connected layer is used to map the output hidden state of TGCGRU to the output features. The output features of all time steps in the decoder are the predictions we need. Both the embedding parameters for time-evolving graph generation and the parameters in TGCGRU are trained together in an end-to-end manner. To relieve the discrepancy in input distribution between the training and testing stage, the scheduled sampling [38] strategy is applied. During training, the decoder takes as input either the  
Figure 4: The structure of time-evolving graph convolutional gate recurrent unit.  
ground truth with probability \(\varepsilon\) or the prediction of the previous step with probability \(1-\varepsilon\). The probability of the \(i\)-th iteration \(\varepsilon_{i}\) is calculated as  
\[\varepsilon_{i}=\frac{\tau}{\tau+\exp\Bigl{(}\frac{i}{\tau}\Bigr{)}}, \tag{9}\]  
where \(\tau\) is a constant to control the speed of probability decay.