# Traffic Incident Detection Based on Dynamic Graph Embedding in Vehicular Edge Computing
## 3 Traffic Incident Detection Based on Dynamic Graph Embedding
### Dynamic Graph Embedding  
Dynamic graph embedding is utilizing the nonlinear function \(f:G_{t}\to g_{t}\) to learn the representation for mapping the graphs into the embedding space, where \(G_{t}\) is the graph at the time intervals \(t\in[0,T]\) and \(g_{t}\) is the embedding vectors of the graph \(G_{t}\). In this study, the graph \(G\) includes two elements which are correlation coefficient matrix and the graph entropy formulated as \(G_{t}=\langle R(G_{t}),e(G_{t})\rangle\). The object of the dynamic embedding is clustering the graphs based on the similarity. It requires that the dynamic graph embedding considers the similarity of the neighbor structure between the graphs and considers the similarity of graph entropy. We define the graph similarity based on the correlation coefficient matrix and the graph entropy to solve this problem. **Definition 3** (Graph similarity). : _The graph similarity is described as the similarities of the neighbor structure and graph entropy, which is formulated as \(S(G_{i},G_{j})=||R(G_{i})-R(G_{j})||_{2}^{2}+||e(G_{i})-e(G_{j})||_{2}^{2}\) where \(S(G_{i},G_{j})\) indicates the similarity between the graphs \(G_{i}\) and \(G_{j}\). The low similarity \(S(G_{i},G_{j})\) indicates that two graphs \(G_{i}\) and \(G_{j}\) are similar at the neighbor structure and graph entropy._  
In this study, we used a graph proximity-based dynamic graph embedding model (DynGPE) to embed the graphs [30]. Given a dynamic graph \(\mathcal{G}=\{G_{t}|t\in[0,T]\}\), \(G_{i}\) and \(G_{j}\) indicates the graphs at the time interval \(i,j\in[0,T]\). \(G_{i}\) is the most similar graph with \(G_{i}\). The embedding vector \(g_{i}\) is calculated at the embedding layer. The model consists of two autoencoders. The encoder maps the graph \(G_{i}\) into the embedding space by usingthe nonlinear function. The output of the decoder is to reconstruct the graph \(\widehat{G}_{i}\). If the graphs \(G_{i}\) and \(G_{j}\) are close in the embedding space, the graph \(G_{i}\) is similar to the graph \(G_{j}\). The inputs of the two autoencoders are the correlation matrices \(R(G_{i})\) and \(R(G_{j})\) and the hidden layers can learn the features from the correlation matrices by using the nonlinear functions  
\[y^{1}=\delta(W^{l}R(G_{i})+b^{l}) \tag{1}\] \[y^{l}=\delta(W^{l}y^{l-1}+b^{l}) \tag{2}\]  
where \(y^{l}\) indicates the outputs of the \(l\)th hidden layer and \(W^{l}\) and \(b^{l}\) indicate the weights and basis values at the \(l\)th hidden layer, respectively. To make the functions nonlinear, we exploit the ReLU function as an activation function that is denoted as \(\delta\)[31]. The input of the first hidden layer is the correlation matrix of the graph \(G_{i}\), and the input of the next hidden layer is the output of the previous layer. The autoencoder reconstructs the input by reversing the nonlinear functions. Since the graph \(G_{j}\) is the most similar graph with the graph \(G_{i}\) on the neighbor, their embedding vectors are close in the embedding space. Since the autoencoder learns the features by reconstructing the input, the similarity between the input and output is required to be small. We establish the loss function \(\mathcal{L}_{1}=\sum_{i=1}^{T}||G_{i}-\widehat{G}_{i}||_{2}^{2}\) to reduce the error between the input graph and the output where \(T\) is the number of time intervals. To make two similar graphs on entropy close together in the embedding space, we establish the loss function \(\mathcal{L}_{2}=\frac{1}{T}\sum_{i=1}^{T}||g_{i}-g_{j}||_{2}^{2}\). The loss function \(\mathcal{L}_{2}\) includes the embedding vectors of two graphs \(G_{i}\) and \(G_{j}\) so that the distance between them is reduced by optimizing the loss \(\mathcal{L}_{2}\). To avoid the overfitting, we add a regularization term, which is formulated as \(\mathcal{L}_{reg}=\frac{1}{2}\sum_{l=1}^{L}(||W^{l}||_{2}^{2}+||\widehat{W^{l} }||_{2}^{2})\) where \(L\) represents the number of layers and \(W\) represents the weights.