Location Prediction over Sparse User Mobility Traces Using RNNs: Flashback in Hidden States!

1 Introduction

User mobility modeling is one of the most important problems in understanding human dynamics, which also serves as a fundamental ingredient for developing smart city applications. One key task of user mobility modeling is to predict a user's next location based on users' historical mobility traces [Noulas et al., 2012]. Traditional methods often resort to user mobility features - either hand-crafted features such as historical visit counts [Noulas et al., 2012], or automaticallylearnt features using graph embedding techniques [Xie et al., 2016]) - to capture user mobility patterns. However, by generating static features from historical data, these techniques predict user locations without really considering the sequential patterns of user mobility, which have been shown as an important clue for location prediction [Liu et al., 2016].

Recently, Recurrent Neural Networks (RNNs) have been shown as a successful tool to model sequential data and thus started to be used also for user mobility modeling [Zhao et al., 2019]. However, classical RNN architectures, such as vanilla RNN, Long Short-Term Memory (LSTM) and Gated Recurrent Unit (GRU), were originally designed for language modeling to learn from word sequences (sentences) and they are not able to handle sparse (and incomplete) mobility traces. For example, on Foursquare, one of the most popular Location Based Social Networks (LBSNs), a user's mobility trace is stored as a sequence of check-ins, where each check-in represents the user's presence at a specific Point of Interests (POIs) such as a restaurant or a gym, at a specific time. As users share their check-ins on a voluntary basis on this platform, such mobility traces are often sparse; on our collected Foursquare dataset, we find that the average time between successive check-ins are about 59 hours. Such sparsity and incompleteness of input sequences hinders the application of RNNs to the location prediction problem [Feng et al., 2018]. To handle such sparse mobility traces, existing works strive to incorporate spatiotemporal factors into RNN architectures, as spatiotemporal contexts have indeed been shown as strong predictors for user mobility prediction [Yang et al., 2015].

In the current literature, the most popular scheme to achieve this goal is to incorporate spatiotemporal factors into the recurrent hidden state passing process of RNNs. Specifically, given a user mobility trace represented as a sequence of POIs {..., pi-1, pi, pi+1, ...}, a classical RNN learns from the sequence by outputting a hidden state hi from the current POI pi and the previous hidden state hi-1, i.e., hi = F(pi, hi-1) where F(·) denotes a RNN unit (e.g., vanilla RNN, LSTM or GRU). Subsequently, to add spatiotemporal factors, existing techniques first compute the temporal and spatial distances between the previous checkin and the current check-in, denoted as ∆Ti-1,i, ∆Di-1,i, respectively, and then feed them as additional inputs to the RNN unit, i.e., hi = F(pi, hi-1,∆Ti-1,i,∆Di-1,i), as illustrated in Figure 1. In the current literature, this scheme has been instantiated by either using spatiotemporal-specific transition matrices parameterized by ∆Ti-1,i and ∆Di-1,i in RNNs [Liu et al., 2016], or extending/adding gates controlled by ∆Ti-1,i and ∆Di-1,i to LSTM [Kong and Wu, 2018; Zhao et al., 2019]. However, this scheme cannot fully benefit from rich historical spatiotemporal contexts encoded in the mobility trace, due to the following reasons.

First, from a temporal perspective, feeding temporal distances between successive check-ins to the RNN unit may ignore the temporal periodicity of user mobility. Specifically, the periodicity of human activities is universal [Gonzalez et al., 2008]. Figure 2(a) shows the return probability of user check-ins over time, defined as the probability of a user re-checking in at a POI a certain period of time after her first check-in at that POI, on our collected Foursquare dataset. We observe a clear daily (periodic) revisiting pattern. In the context of location prediction, such a periodicity implies that historical check-ins with a temporal distance (taken from the current time) closer to these daily peaks (1 day, 2 days, etc.) have higher predictive power. However, iteratively feeding temporal distances between successive check-ins into the RNN unit (as shown in Figure 1) often fails to benefit from this periodicity property. Figure 2(a) illustrates such an example, where ∆Ti-1,i and ∆Ti,i+1 refers to the temporal distances between successive check-in pairs pi-1 → pi and pi → pi+1, respectively. If we consider the temporal distance in two steps (pi-1 → pi+1), we find that ∆Ti-1,i+1 is close to the 1 day peak, indicating that pi-1 is very helpful for predicting the next location. In contrast, this cannot be captured if we iteratively feed temporal distances ∆Ti-1,i and ∆Ti,i+1 into the RNN unit.

Second, from a spatial perspective, feeding spatial distances between successive check-ins to the RNN unit oversimplifies the spatial regularity of user mobility. Specifically, it has been found that a user's check-ins in a region that she frequently visited are highly biased to certain POIs [Yang et al., 2015]. In other words, those regions often have certain implicit "functions", such as working or shopping. Subsequently, the closer the user is to such a region, the more predictable her behavior is. This suggests that the closer a past check-in is located to the current location, the more helpful it is for the next location prediction. However, only considering spatial distances between successive check-ins fails to capture such distances over space. Figure 2(b) shows an example. We observe that the spatial distance in two steps ∆Di-1,i+1 is much smaller than both ∆Di-1,i and ∆Di,i+1, suggesting that pi-1 is more helpful for location prediction. In contrast, this cannot be captured if we consider spatial distances ∆Di-1,i and ∆Di,i+1 only.

Against this background, we propose Flashback, a general RNN architecture designed for modeling sparse user mobility traces, with a particular consideration on leveraging rich historical spatiotemporal contexts by considering flashbacks on hidden states in RNNs. More precisely, departing from the widely adopted scheme of adding spatiotemporal factors into the recurrent hidden state passing process of the RNNs, our solution explicitly uses the spatiotemporal context to search past hidden states with high predictive power (i.e., historical hidden states that share similar spatiotemporal contexts to the current one) for predicting the next location; as a result, our scheme can directly benefit from rich temporal (i.e, periodicity as shown in Figure 2(a)) and spatial (i.e., distances over space as shown in Figure 2(b)) contexts encoded in user mobility traces. Moreover, as we do not modify the hidden state passing process of RNNs (while many existing techniques do), our Flashback can be easily instantiated with any RNN units (e.g., vanilla RNN, LSTM or GRU). We conduct a thorough evaluation of our method compared to a sizable collection of baselines on two real-world LBSN datasets. Results show that Flashback consistently and significantly outperforms all baseline techniques. In particular, it yields an improvement of 15.9% to 27.6% over the best performing spatiotemporal RNNs.

2 RelatedWork

Location prediction is a key problem in human mobility modeling, which predicts the location of a user based on the user's historical mobility traces. Traditional methods for location prediction often resort to various mobility features, such as hand-craft features including historical visit counts [Noulas et al., 2012; Yang et al., 2016] and activity preferences [Yang et al., 2015], or automatically-learnt features using graph embedding techniques [Xie et al., 2016; Yang et al., 2019]. In addition, generative/factorization models have also been used to solve location prediction/recommendation problems [Kurashima et al., 2013; Yang et al., 2013a; 2013b]. However, these techniques have intrinsic limitations when capturing the sequential patterns of user mobility.

To capture user sequential mobility patterns, (Hidden) Markov Chains have been widely used for sequential prediction [Mathew et al., 2012; Cheng et al., 2013; Feng et al., 2015]. The basic idea is to estimate a transition matrix encoding the probability of a behavior based on previous behaviors. A typical technique here is Factorizing Personalized Markov Chains (FPMC) [Rendle et al., 2010], which estimates a personalized transition matrix via matrix factorization techniques. FPMC has been extended to the location prediction problem by further considering spatial constraints [Cheng et al., 2013; Feng et al., 2015] in building the transition matrices.

Recently, Recurrent Neural Networks (RNNs) have been shown as a successful tool to model sequential data [Mikolov et al., 2010], capturing complex long- and short-term dependency over input sequences. To handle sparse and incomplete sequences, existing techniques strive to add context factors into the RNNs. For example, temporal factors can be added by truncating each sparse input sequence into several short sessions [Hidasi et al., 2016; Feng et al., 2018], or by considering temporal factors as additional inputs to the RNN units [Neil et al., 2016; Zhu et al., 2017]. For the problem of location prediction over sparse user mobility sequences, spatiotemporal factors have been shown as strong predictors [Yang et al., 2015]. The most popular scheme to incorporate spatiotemporal factors into RNNs is adding the spatiotemporal distances between (mostly successive) check-ins as additional inputs to the RNN units (as illustrated in Figure 1). For example, STRNN [Liu et al., 2016] uses spatiotemporalspecific transition matrices parameterized by the spatiotemporal distances in RNNs; HST-LSTM [Kong and Wu, 2018] extends existing gates in LSTMs to let these gates take the spatiotemporal distance as an additional input; STGN [Zhao et al., 2019] adds additional gates controlled by the spatiotemporal distances to LSTMs. However, as discussed in the Introduction, such schemes cannot fully benefit from the rich historical spatiotemporal contexts encoded in mobility traces. Therefore, we propose in this paper Flashback, a general RNN architecture that explicitly uses spatiotemporal contexts to search past hidden states with high predictive power for location prediction, in order to directly benefit from the rich spatiotemporal contexts encoded in user mobility traces.

3 Flashback

Flashback is designed for modeling sparse user mobility traces, with a particular focus on leveraging rich spatiotemporal contexts by doing flashbacks on hidden states in RNNs. Instead of implicitly considering context factors by adding spatiotemporal factors into the recurrent hidden state passing process of RNNs (as most existing techniques do), our solution explicitly uses the spatiotemporal contexts to search past hidden states with high predictive power (i.e., historical hidden states that share similar contexts as the current one) for location prediction; it can thus directly benefit from rich spatiotemporal contexts encoded in user mobility traces.

3.1 Overview

Figure 3 shows an overview of our Flashback architecture. Given a user's mobility trace represented as a POI sequence {..., pi-3, pi-2, pi-1, pi, pi+1...}, we denote the temporal and spatial distances between two check-ins pi and pj as ∆Ti,j and ∆Di,j, respectively. As shown in Figure 3, our recurrent hidden state passing process remains unaltered from classical RNNs i.e., hi = F(pi, hi-1), letting RNNs capture sequential user mobility patterns. However, instead of using only the current hidden state hi to predict the next location pi+1 (as classical RNNs do), we leverage the spatiotemporal context to search past hidden states with high predictive power. To achieve this goal, we compute the weighted average of the historical hidden states hj, j < i, with a weight W(∆Ti,j , ∆Di,j ) as an aggregated hidden state. This weight is parameterized by the temporal and spatial distances (∆Ti,j and ∆Di,j, respectively) between check-in pi and pj and measures the predictive power of the hidden state hj (more information on this point below). Finally, in order to model individual users preferences, we define a learnable user embedding vector for each user, which is concatenated with the aggregated hidden state and then fed into a fully connected layer for predicting the next location, as shown in Figure 3.

In summary, to effectively predict locations from sparse user mobility traces, Flashback 1) uses RNNs to capture sequential patterns, 2) leverages spatiotemporal contexts to search past hidden states with high predictive power, and 3) incorporates user embeddings to consider users preferences.

3.2 Context-Aware Hidden StateWeighting

The weight W(∆Ti,j , ∆Di,j ) is designed to measure the predictive power of the hidden state hj according to its spatiotemporal contexts.

First, from a temporal perspective, our primary goal is to incorporate the periodicity property of user behavior (as shown in Figure 2(a)) into W(∆Ti,j,∆Di,j). Specifically, we use a Havercosine function, a typical periodic function with outputs bounded in [0, 1], parameterized by ∆Ti,j (in days) as follows:

where hvc(x) = 1+cos(x) 2 is the Havercosine function modeling the daily periodicity. Moreover, as we can see from Figure 2(a), the return probability exponentially decreases when increasing ∆Ti,j, which indicates that besides the periodicity, the older a check-in is, the less impact it has for prediction. Subsequently, we add a temporal exponential decay weight to model this factor:

where α is a temporal decay rate, controlling how fast the weight decreases over time ∆Ti,j .

Second, from a spatial perspective, we consider the fact that the closer a check-in is to the current location, the more helpful it is for location prediction (as shown in Figure 2(b)). Accordingly, we use a distance exponential decay weight to model this factor:

where ∆Di,j is the L2 distance between the GPS coordinates of POIs pi and pj, and β is a spatial decay rate, controlling how fast the weight decreases over spatial distance ∆Di,j .

Finally, we obtain the weight W(∆Ti,j,∆Di,j) by combining the temporal and spatial weights together:

where the first Havercosine term captures the periodicity property of user check-ins, and the exponential terms model the spatiotemporal decay of the impact of historical check-ins on location prediction. Figure 4 offers a visualization of the weights over space and time.

3.3 Discussions

Why Does Flashback Work?

By flashing back to the historical hidden states, our Flashback can discount the "noise" from the recurrent hidden state passing process of the RNNs over sparse user mobility traces, and also create an explicit "attention" mechanism by leveraging past hidden states with high predictive power (i.e., historical hidden states that share similar contexts as the current hidden state) for location prediction. Figure 5 shows a toy example from the temporal perspective. On one hand, Figure 5(a) shows an actual (complete) user mobility trace with a clear sequential pattern ("Home-Office-Restaurant-Office-ShoppingBar-Home"), where classical RNNs can effectively capture such a pattern and predict the next location "Home". On the

• (b) Observed (sparse) user mobility trace

Figure 5: A toy example illustrating the working principle of Flashback from a temporal perspective.

other hand, for an observed (sparse) user mobility trace as shown in Figure 5(b), the sequential pattern is difficult to be captured by RNNs, where the hidden state passing process becomes noisy due to the incompleteness of the sequence. Even when considering temporal distances between successive check-ins as additional inputs of the RNN units (as many state-of-the-art techniques do), it still falls short in capturing long-term temporal (i.e, periodicity) dependencies. However, by flashing back to the historical hidden states sharing a similar temporal context as the current one (∆T ≈ 1 day capturing the daily periodicity, i.e., at the similar time on the previous day), Flashback can predict the next location "Home".

How Far to Flash Back?

As Flashback generates an aggregated hidden state from past hidden states, an immediate question here is how many past hidden states should be considered? To answer this question, we review the temporal exponential decay term e-α∆Ti,j in W(∆Ti,j,∆Di,j). Let ∆t denote the average time between successive check-ins. The hidden state k-step back has an average ∆T = ∆t · k, corresponding to a temporal exponential decay term e-α∆t·k . In practice, our empirical analysis shows that the average time between successive check-ins ∆t are 51.28 (2.13 days) hours and 58.59 hours (2.44 days) on our Gowalla and Foursquare datasets, respectively (see Section 4.1), and the optimal temporal decay rate is 0.1 in our experiments on both datasets (see Section 4.3). Therefore, the temporal exponential decay term becomes a function of k. When setting k = 20 for example, this term is around

0.01, which is indeed the upper bound of W(∆Ti,j,∆Di,j) as all other terms inW(∆Ti,j,∆Di,j) are bound to [0, 1]. In other words, a hidden state more than k-step back receives on average a weight less than 0.01, which contributes little to the aggregated hidden state. We also study this point in our experiments, where prediction performance flattens out when k ≥ 20 (see Section 4.4).

4 Experiments

4.1 Experimental Setup

Dataset

We conduct experiments on two widely used check-in datasets collected from two LBSNs: Gowalla and Foursquare, respectively. Table 1 shows the statistics of the datasets. We chronologically split all the mobility traces into 80% for training and 20% for test.

Baselines

We compare Flashback against a sizable collection of stateof-the-art techniques from five categories:

• User Preference-based Methods: 1) WRMF [Hu et al., 2008] learns user preferences on POIs using matrix factorization; 2) BPR [Rendle et al., 2009] learns user preferences on POIs by minimizing a pairwise ranking loss.
• Feature-based methods: 1) Most Frequent Time (MFT, the best-performing feature by [Gao et al., 2012]) ranks a POI according to a user's historical check-in count at a POI and at a specific time slot (24 hours in a day) in the training dataset; 2) LBSN2Vec [Yang et al., 2019] learns user, time and POI feature vectors from a LBSN hypergraph, and ranks a POI according to its similarities with user and time in the feature space.
• Markov-Chain-based Methods: 1) FPMC [Rendle et al., 2010] estimates a personalized transition matrix via matrix factorization techniques; 2) PRME [Feng et al., 2015] learns user and POI embeddings to capture the personalized POI transition patterns. 3) TribeFlow [Figueiredo et al., 2016] uses a semi-Markov chain model to capture the transition matrix over a latent environment.
• Basic RNNs: 1) RNN [Zhang et al., 2014] is a vanilla RNN achitecture; 2) LSTM [Hochreiter and Schmidhuber, 1997] is capable of learning long-term dependency using a memory cell and multiplicative gates; 3) GRU [Cho et al., 2014] captures long-term dependency by controlling information flow with two gates.
• Spatiotemporal RNNs: 1) DeepMove [Feng et al., 2018] adds an attention mechanism to GRU for location prediction over sparse mobility traces; 2) STRNN [Liu et al.,

2016] uses customized transition matrices parameterized by the spatiotemporal distances between check-ins within a time window in RNNs; 3) STGN [Zhao et al., 2019] add additional gates controlled by the spatiotemporal distances between successive check-ins to LSTM, while STGCN is a variant of STGN with coupled input and forget gates for improved efficiency.

For our proposed Flashback, as it does not depend on any specific RNN units, we instantiate it using all the three basic RNNs, named as Flashback (RNN), Flashback (LSTM), and Flashback (GRU). We train Flashback by backpropagation through time using the Adam stochastic optimizer with cross entropy loss. We implement Flashback in PyTorch, and our code and datasets are available here 1 .

Evaluation Protocol and Metrics

We evaluate Flashback in the next location prediction task, where we predict where a user will go next, given a sequence of her historical check-ins, as shown in Figure 3. We report two widely used metrics for location prediction: average Accuracy@N (Acc@N), where N = 1, 5, 10, and Mean Reciprocal Rank (MRR). We empirically set the dimension of hidden states and all (POI and user) embedding size as 10 for all RNN-based techniques. We search the optimal temporal and spatial decay rate (α and β, respectively) on a log scale (see Section 4.3 for more details).

4.2 Location Prediction Performance

Table 2 shows the results on both Gowalla and Foursquare. In general, we observe that Flashback consistently and significantly outperforms all baseline techniques. In particular, compared to the best-performing baselines (spatiotemporal RNNs in most cases), Flashback shows an improvement of 27.7% and 15.9% in MRR, on Gowalla and Foursquare, respectively.

In addition, compared to the basic RNNs, Flashback consistently yields significant improvements of at least 27.5%, showing the effectiveness of leveraging past hidden states for next location prediction. Interestingly, we also observe a large variation on the performance of basic RNN, LSTM, and GRU (e.g., we see an MRR of 0.1507, 0.1144 and 0.0993 on the Gowalla dataset, respectively), showing their different capacities of modeling sparse user mobility traces. However, despite their different modeling capacities, Flashback implemented with RNN, LSTM, and GRU has a much smaller variation in terms of its performance (with an MRR of 0.1925, 0.1778 and 0.1731 on Gowalla, respectively). Such an observation shows that Flashback can boost the performance of any basic RNNs to a maximum extent, by fully benefiting from rich historical spatiotemporal contexts.

4.3 Impact of Spatiotemporal Decay Rates

In this experiment, we evaluate the impact of the temporal and spatial decay factors (α and β, respectively) on location prediction by varying α and β on a log scale. Figure 6 shows the results. On one hand, when increasing the spatial decay factor β, we observe that the prediction performance increases, and then flattens out after β = 100 (on Foursquare) or β = 1000 (on Gowalla). This observation verifies the fact that the spatial distance is a very important factor defining context similarity for next location prediction problem; with a large β, the context similarity decreases fast with increasing spatial distances 2 . On the other hand, when decreasing temporal decay factor α, the prediction performance slightly increases, and achieves the best performance at α = 0.1, implying a slow temporal decay over time which allows the hidden states at the periodicity peak to contribute more to location prediction. In other words, a low value of α indeed shows that the periodicity helps for predicting the next location.

1 https://github.com/eXascaleInfolab/Flashback code/

4.4 How Far to Flash Back?

In this experiment, we study the impact of the number of involved past hidden states k (when flashing back) on the performance of location prediction. Figure 7 shows the results. We observe that performance increases with increasing k, as more hidden states can better help location prediction. The performance flattens out after k ≥ 20, as further hidden states have little contribution due to the temporal decay, which corresponds to our previous discussion in Section 3.3.

2 We compute spatial distance ∆D using the L2 distance (in kilometers) between the GPS coordinates of two POIs.

5 Conclusion

In this paper, we propose Flashback, a general RNN architecture designed for modeling sparse user mobility traces by leveraging rich spatiotemporal contexts. Specifically, instead of implicitly considering context factors by adding spatiotemporal factors into the recurrent hidden state passing process of RNNs (as most existing techniques do), our solution explicitly uses the spatiotemporal contexts to search past hidden states with high predictive power (i.e., historical hidden states that share similar contexts as the current hidden state) for location prediction; subsequently, Flashback can directly benefit from rich spatiotemporal contexts encoded in user mobility traces. Our extensive evaluation compares Flashback against a sizable collection of state-of-the-art techniques on two real-world LBSN datasets. The results show that Flashback consistently and significantly outperforms state-of-theart spatiotemporal RNNs by 15.9% to 27.6% when tackling the next location prediction task.

In future work, we plan to incorporate learnable spatiotemporal decay rates to fully automate our learning process.

Acknowledgements

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement 683253/GraphInt).