Abstract: This paper is published in CIKM ’21 by Huawei Cloud Database Innovation Lab and Data and Intelligence Lab of University of Electronic Science and Technology of China. This paper proposes the first trajectory recovery model to overcome the problems of multi-level periodicity, periodic offset and data sparsity that are common in human movement trajectory data.

This article is shared from huawei cloud community “CIKM’21PeriodicMove Paper interpretation”, author: Cloud database innovation Lab.

takeaway

PeriodicMove: Shift-Aware human mobility Recovery with graph neural networks Network is a paper published in CIKM ’21 by Huawei Cloud Database Innovation Lab and Data and Intelligence Lab of UELECTRONIC Science and Technology of China. This paper puts forward the first trajectory recovery model to overcome the problems of multi-level periodicity, periodic offset and data sparsity commonly existing in human movement trajectory data. CIKM is one of the top academic conferences in the field of information retrieval and data mining. A total of 1251 papers were submitted to the conference, including 271 accepted papers, with an acceptance rate of about 21.7%. This paper is one of the key technical achievements of cloud database innovation LAB in trajectory analysis.

1, the

With the introduction of various location-based services, it is particularly important to recover and complete the sparse human movement trajectory data to improve the accuracy of these downstream tasks. However, the recovery of human movement trajectory data faces great challenges:

  • There are complex transfer patterns among locus points

  • Multilevel periodicity and periodic offset are common in human movement trajectory data

  • At present, the trajectory data collected are relatively sparse

In this paper, we propose a graph neural network-based human behavior trajectory recovery model called PeriodicMove. In this model, we first construct a directed graph for each historical trajectory and use graph neural networks to capture complex transition patterns between locations. Then, we design two attention mechanisms to capture the multilevel periodicity and periodic deviation of human behavior trajectory respectively. Finally, we design a space-aware loss function to introduce the spatial proximity information of positions into the model, thus alleviating the data sparsity problem to some extent. We performed extensive experiments on two representative human trajectory datasets, and our model PeriodicMove achieved a 2.9%-9% performance improvement over the current SOTA model.

2, model,

2.1 Model Architecture

Our model mainly consists of five parts: the graph neural network layer, the sequential embedding layer, the two attention mechanism layers and the final fusion recovery layer

2.2 Figure neural network layer

In order to capture the complex spatial transfer relationship between track points in the trajectory, we first build a graph for each trajectory according to the way shown in the figure, and then use the graph neural network to learn the complex spatial transfer mode between track nodes in the directed graph

2.3 Timing embedding layer

We use the relative phase of trigonometric functions mentioned in Attention Is All You Need to describe the relative order relations in track sequences. Then we spliced the results of graph neural network layer and temporal embedding layer to form embedding vector representation containing complex spatio-temporal dependencies

2.4 Attention mechanism layer

The Cross Attention Layer is mainly used to solve the phenomenon of periodic offset in the data of human movement track. We compare the movement mode of the current moment T with that of all the moments in each historical track, and aggregate the relevant historical information at the moment T of the historical track based on a similarity weight to solve the phenomenon of periodic offset

After passing the Cross Attention Layer, the track point representation at each moment of each historical track can be understood as the offset calibration according to each moment of the current track to be completed. Next, in the Soft Attention Layer, we perform a Attention operation on the t moment of the current track and the track representation of the t moment of each historical track, forming a multi-level periodic representation of the historical track

2.5 Fusion Recovery Layer

In the final fusion recovery layer, we use the historical trajectory enhancement sequence that contains complex spatio-temporal dependence, contains multi-level periodicity and overcomes the phenomenon of periodic offset to assist the current trajectory to perform the final completion recovery

2.6 Distance Loss design

In the scenario with highly sparse trajectory data, cross entropy loss cannot capture spatial proximity well, which is an important feature of human movement recovery. Therefore, we designed a Distance Loss function to incorporate spatial proximity information into the model, and adopted Noise Contrastive Estimation (NCE) to accelerate the training of the model. The visualization results show that the addition of Distance Loss can effectively help the model capture spatial proximity information

3, the experimental

3.1 Experimental Results

Our model PeriodicMove provides a 2.9-9% performance improvement over the current SOTA model (2021-AAAI)

3.2 Ablation experiment

We conducted ablation experiments on five parts of the model respectively, and the experimental results showed that each module made certain contributions to our task. Among them, the effect of the model declined the fastest after removing the Soft Attention Layer module, indicating that multi-level periodicity plays a very important role in human movement trajectory data recovery task

3.3 Robustness experiment

We conducted a robustness experiment between this model and the latest SOTA model (2021-AAAI) at different miss rates. It can be seen from the experimental results that both models have good robustness, but the effect of our model at each miss rate has been improved to some extent by AttnMove

4, application

In various location-based services, such as personalized geographical location recommendation, urban intelligent traffic scheduling and trajectory anomaly detection, the accuracy of these downstream tasks will be affected as long as the trajectory data collected is sparse. The aim of our paper is to restore the sparse trajectory data to dense and fine trajectory data to improve the accuracy of these downstream tasks

Huawei cloud database innovation lab’s official website: www.huaweicloud.com/lab/clouddb…

Click to follow, the first time to learn about Huawei cloud fresh technology ~