# Traffic Incident Detection Based on Dynamic Graph Embedding in Vehicular Edge Computing
## 1 Introduction  
Ambient Intelligence (AmI) consists of technologies integrated into the physical environment for providing users with assistive and predictive support seamlessly. It combines artificial intelligence and the Internet of Things (IoT) with the pervasiveness of smart objects. In AmI-enabled environments, IoT is evolving as an intermediary layer between hardware systems and applications that offer intelligent services to people [1, 2]. IoT connects a variety of networked devices that are embedded with sensors, applications, and other technologies in order to communicate and share data with other devices and systems [3]. With billions of time series data collected from IoT in AmI-enabled environments, effective data mining methods are necessary to address these data [4]. Anomaly detection is a vital research issue in data mining. It aims to identify the significantly different data from the most observations [5]. Therefore, applying outlier detection technologies to the IoT time series can save computing time and predict the risk in smart environments. For example, in transportation systems based on AmI, IoT, and vehicular edge computing (VEC), anomaly detection can help vehicular users know the road condition in advance and avoid time loss caused by traffic incidents [6, 7]. The existing approaches focusing on the outlier detection on the time series are learning the prior knowledge using the supervised learning model [8] or utilizing the statistical methods to compute the probability distribution of the data [9]. The statistical methods require that the data has a normal distribution and detect the outliers based on the statistical indices. The supervised learning learns the patterns of inliers and outliers from the training datasets and fits the supervised learning models. However, the patterns of outliers are diverse, so that the models cannot learn the patternsof all types of outliers. To overcome this problem, we discover the correlation between the multiple IoT time series for anomaly detection. Traffic incident detection is one of the critical research issues in smart transportation systems [6; 7; 10; 11]. In this study, we focus on the traffic incident detection problem with multiple traffic time series data. In this regard, we pose the following research questions:  
* How to extract incident patterns from multiple traffic time series data? (Q1)
* How to construct the model for detecting incidents from extracted patterns? (Q2)
* How to demonstrate the efficiency of the model? (Q3)  
To address the research questions, we propose a new method to detect traffic incidents by identifying the anomaly among multiple traffic time series data. The proposed system collects traffic data from roadside units and connected vehicles and then detects the traffic incidents from the collected data to help users avoid the incidents and save travel time. We identify the correlation among the traffic time series to construct the dynamic graph. The graph is a typical data structure that consists of the vertices and edges for representing the correlation among the multiple data. The sliding window is exploited to generate the time intervals, and each time interval can be represented by using the graph. The dynamic graph consists of these graphs in continuous time. The graph entropy quantifies the information of the graph, and we compute the similarity between two graphs based on the graph entropy. The graphs with similar entropy have a small distance in the embedding space, while the graphs with anomalies are far from the regular graphs. Therefore, they can easily be detected as anomalies. The key contributions of this study are summarized as follows:  
* We propose a new idea for incident detection by discovering the correlation among multiple time series to build the graph and exploit the correlation to calculate the entropy of the graph. * We present the definitions of graph similarity based on the graph entropy for estimating the similarity between the two graphs.