Spatio-Temporal Attention based Recurrent Neural Network for Next Location Prediction

With the advances in technology and smart devices, more and more attention has been paid to model spatial correlations, temporal dynamics, and friendship influence over point-of-interest (POI) checkins. Besides directly capturing general user's checkin behavior, existing works mostly highlight the intrinsic feature of POIs, i.e., spatial and temporal dependency. Among them, the family of methods based on Markov chain can capture the instance-level interaction between a pair of POI checkins, while recurrent neural network (RNN) based approaches (state-of-the-art) can deal with flexible length of checkin sequence. However, the former is not good at capturing high-order POI transition dependency, and the latter cannot distinguish the exact contribution of each POI in a historical checkin sequence. Moreover, in recurrent neural networks, local and global information is propagated along the sequence through one bottleneck i.e., hidden states only.In this work, we design a novel model to enforce contextual constraints on sequential data by designing a spatial and temporal attention mechanisms over recurrent neural network that leverages the importance of POIs visited by users in given time interval and geographical distance in successive checkins. Attention mechanism helps us to learn which POIs bounded by time difference and spatial distance in user checkin history are important for the prediction of next POI. Moreover, we also consider periodicity and friendship influence in our model design. Experimental results on two real location based social networks Gowalla, and BrightKite show that our proposed method outperforms the existing state-of-the-art deep neural network methods for next POI prediction and understanding user transition behavior. We also analyze the sensitivity of parameters including context window for capturing sequential effect, temporal context window for estimating temporal attention and spatial context window for estimating spatial attention respectively.