Location Predicts You: Location Prediction via Bi-direction Speculation and Dual-level Association

1 Introduction

Human mobility modeling on spatiotemporal data has gained significant research interests due to its importance for human behavior understanding and applications for the construction of smart city [Yu et al., 2019; Wang et al., 2021b; Wang et al., 2021a]. One of the most important applications is the next location prediction, which aims to predict the next Point-of-Interest (POI) someone tends to visit based on his/her historical trajectory data.

In recent years, plenty of research efforts have been made on the location prediction [Yang et al., 2020], including Matrix Factorization based [Ren et al., 2017], Markov Chain (MC) based [Zhang et al., 2014a; Chen et al., 2014] and neural network based methods [Karatzoglou et al., 2018]. To our knowledge, these methods only investigated how the user chooses places, i.e., focusing on the users' preferences on POIs from the perspective of the human side. Unfortunately, despite the success of these works for enriching the representation, modeling users' interests from the human trajectory history is still limited by the data sparsity due to the fact that most users share few records online. In addition, most of methods predicted someone's next location according to his/her own trajectory independently. But the data sparsity makes it difficult to mine explicit mobility patterns for each user or to capture the casual behavior of the user. Hence, the next location prediction is still a challenging task.

∗Corresponding Author

To address the issues above, in this paper, we propose a novel Bi-direction Speculation and Dual-level Association method (BSDA). The characteristics of our method are reflected in the following aspects: 1) From the Perspective of the Location Side: we consider that the POI appeals or chooses the users autonomously. If we set a POI as the subject, another model should be capable of predicting the next user who will visit this POI, according to the historical data of this POI. 2) Cross-User Association: we believe that some users have similar interests and they may visit the same places. When we can not predict one's next location accurately due to his incomplete historical trajectory data, the POI candidate of users who are similar to him might be his choice. 3) Cross-POI Association: it is also reasonable that similar places appeal to common users. Hence, the most similar POIs also benefit the prediction of next coming users.

Motivation

We conduct some preliminary statistic analysis on the Gowalla dataset [Cho et al., 2011] to demonstrate our motivations described above.

Firstly, we investigate how the POI appeals or chooses the visiting users. We count the visiting times of the users for several randomly selected POIs. Figure 1(a) shows the results of 15 POIs. The horizontal axis stands for the threshold of the visiting times of each user, while the vertical axis denotes the number of users visiting the corresponding POI. The figure demonstrates that for a certain POI, some users visit frequently while the others visit occasionally, and only a few users visit 3-8 times. Here is an example to illustrate this phenomenon. A library appeals to people who like reading but does not attract those who don't have relevant habits. We also explore temporal patterns in POIs' behavior by calculating the densities of visitors at different time slots in a day and on different days in a week. Figure 1(b) shows the statistic results of randomly selected 35 POIs. The figure demonstrates that POIs have different temporal patterns as their distinct difference in densities on the two time scales. It is easy to understand that an amusement park often has more visitors at weekends than on weekdays, while an office building always has an opposite pattern. Additionally, a bar is usually busy at night, while a museum only accommodates visitors in the morning. These findings show that POI has its behavior patterns to appeal to a certain kind of users. Intuitively, it is reasonable that the task can be considered from the perspective of the location side.

Secondly, we intend to validate that similar users may visit the same places. We judge the similarity of each pair of users according to whether they visit the same place on the same day. The more common places they visit, the more similar the users' visiting patterns are. We also count the number of common POIs of each pair of users. Figure 1(c) shows the results of user similarity vs. #common POI. Figure 1(c) easily demonstrates that the user similarity and the number of common POIs are proportional to each other (highly related). Hence, the next POIs of one's most similar users can be considered as the choice, on condition that we can not predict his/her next POI accurately due to the incomplete historical trajectory data.

Thirdly, we evaluate whether similar places may appeal to common users. We judge the similarity of each pair of POIs according to whether they appeal to the common users on the same day. The more common visitors they have, the more similar their behavior patterns are. We also count the number of common users of each pair of POIs. Figure 1(d) shows the results of POI similarity vs. #common user. Figure 1(d) easily demonstrates that the POI similarity and the number of common users are proportional to each other (highly related). Hence, the next visitors of similar POIs can be considered as the choice of the focused POI.

To this end, we propose a novel Bi-direction Speculation and Dual-level Association method (BSDA) for the next location prediction by mining both users' interests in POIs and POIs' appeal to users. From the point of the human side, we pay attention to when and where the user is likely to go. While from the point of the location side, we focus on when and who will visit this place. Specifically, we first develop two networks to explore users' interests and POIs' appeal separately. In addition, we exploit the cross-user and cross- POI association to alleviate the data sparsity by mining similar users and POIs to enrich the candidates. In particular, we learn the POI similarity and user similarity matrices through the historical trajectory data and fuse them with the outputs of two networks to predict the next location of all related users. We verify the effectiveness of our proposed model on two public check-in datasets and experimental results show that BSDA outperforms state-of-the-art methods for the location prediction task.

The contributions of our paper are summarized as follows: 1) We first investigate the phenomena of POIs' behavior patterns about appeal to users, user similarity and POI similarity. 2) We propose a novel Bi-direction Speculation and Duallevel Association method (BSDA) for location prediction by mining both users' interests and POIs' appeal, as well as fusing with cross-user and cross-POI association. 3) Evaluations on two public real-world datasets show that BSDA achieves significant improvements over the state-of-the-art methods.

2 RelatedWork

Current methods on location prediction can be mainly categorized into three groups: Matrix Factorization (MF) based, Markov Chain (MC) based, and RNN based. MF-based methods [Koren et al., 2009; Liu et al., 2013] are good at capturing users' general preferences but cannot mine users' sequential patterns. MC-based methods [Zhang et al., 2014a; Chen et al., 2014; He and McAuley, 2016] are capable of capturing the sequential transitions but the first-order MCs fail to learn the long-term preference. By combining the power of MF and MC, [Rendle et al., 2010] proposed a factorizing personalized MCs to obtain both long-term preference and short-term transitions. [Wang et al., 2015] made an extension with global user vectors to learn users' hierarchical representation. [Feng et al., 2015] also proposed a personalized ranking metric embedding for personalized recommendation by integrating sequential information, individual preference and geographical influence. However, these methods mainly focus on modeling the user-POI interaction or the transitions between successive POIs to mine users' preferences, limited by the data sparsity since most users share few records online.

RNN [Zhang et al., 2014b] and its variants LSTM [Hochreiter and Schmidhuber, 1997] and GRU [Cho et al., 2011], have shown great advantages in sequential modeling task. For instance, [Yao et al., 2017] learned temporal regularity, activity semantics, and user preference by embedding sequential context and temporal information together into LSTM. [Sun et al., 2020] incorporated both long- and short-term preferences and considered geographical relations between two nonconsecutive POIs. Other deep models such as memory network and attention mechanism [Vaswani et al., 2017] were also widely employed [Ying et al., 2018]. [Huang et al., 2018] proposed to discriminate the significance of individual user behaviors using the feature-wise masked self-attention. Similarly, [Yu et al., 2019] applied an attention-based adaptive fusion to dynamically combine users' long- and shortterm interests. These methods mainly pay attention to modeling users' behavior patterns by mining the latent representation of users' interests. Some methods leverage contextual information to enrich the representation [Yu et al., 2020]. [Lim et al., 2020] proposed a graph attention network that not only exploits personalized user preferences but also explores new POIs from other users. However, the problem is studied only from the perspective of the human side, still limited by the data sparsity.

[Feng et al., 2017] proposed POI2Vec which can predict the potential future visitors for a location by modeling the POI sequential transition. Although POI2Vec introduces the task of predicting future visitors, its one-direction single module for modeling users' patterns is more close to our User-net. However, we design two parallel modules to treat users and POIs as subjects to do the bi-direction speculation. Furthermore, three points about our dual-level association need to be emphasized. 1) Our proposed association is to adjust the POI or user candidate list, which occurs after training while sharing parameters or using embedding is during training. 2) In POI-net and User-net, our proposed similarities is to provide more possible candidates based on patterns, not just shared data. 3) Our dual-level association is time-aware, i.e., the output candidate list is dynamically adjusted according to the similar behavior at a given time.

To sum up, our method has the following advantages. To our best knowledge, it is the first time that the location prediction problem is considered from both the perspective of the human side and the location side. We propose the bi-direction speculation, i.e., mining both users' interests in POIs and POIs' appeal to users. Moreover, we exploit the cross-user and cross-POI association to alleviate the data sparsity by mining similar users and POIs to enrich the candidates.

3 ProposedMethodology

3.1 ProblemFormulation

Let U = {u1, u2, · · · , uM} be the set of M users and L = {l1, l2, · · · , lN} be the set of N POIs.

Check-in point. When a user u visits a POI l at time t, the check-in point is represented as ru t = 〈u, t, lon, lat, l〉, where lat and lon represent the geographical coordinates of l.

Trajectory. Given a user u, the trajectory is denoted as a set of chronologically ordered check-in points Ru = {ru t1 , ru t2 , · · · , ru tT }, where T is the length of trajectory.

Problemdefinition. Formally, given a user's trajectory history in the last T - 1 steps, the primary goal of the next location prediction task is to predict the top-k most likely POIs {Lk} that this user u will visit at the next time tT .

3.2 Framework Overview

We employ a novel Bi-direction Speculation and Dual-level Association method (BSDA) for the next location prediction. The overall framework is depicted in Figure 2. It mainly consists of three parts: 1) the User-Net and cross-user association for modeling users' interests to speculate where a user is likely to go, 2) the POI-Net and cross-POI association for modeling POIs' appeals to speculate who will visit the POI, and 3) the fusion layer for integrating the results of bi-direction speculations.

3.3 User-Net and Cross-User Association

The User-Net is designed for exploring users' interests in POIs by modeling users' spatiotemporal behavior patterns, which belongs to the traditional location prediction task. Its input is the trajectory history of users and the output is the POI candidate score list. Motivated by the success of Flashback [Yang et al., 2020], our User-Net uses RNNs to capture the sequential patterns and compute the weighted average of the historical hidden states as the aggregated output hwt with a decay weight ω (∆T,∆D) to predict the next location. The decay weight is designed to measure the predictive power of the hidden state hj to the current one ht, j <

t: ω (∆Ti,j,∆Di,j) = hvc (2π∆Ti,j) e-α∆Ti,j e-β∆Di,j , where ∆T denotes the temporal interval, ∆D denotes the geographical distance. The Havercosine term hvc (·) is to capture the periodicity of user behavior. The exponential terms are to capture the impact of historical check-ins. Therefore, the User-Net is capable of capturing the sequential patterns, long-term temporal dependencies and the impact of historical check-ins on the next location prediction.

For each user, we first split the historical trajectory Ru into sub-sequences as the input of the RNN units. At each step t, the hidden state is denoted as ht. Then we leverage the spatiotemporal contexts to generate the decay weight ω (∆T,∆D) for calculating the aggregated output hwt = ∑tj=0 wj ∗hj ∑tj=0 wj . Furthermore, to model personalized preference of each user, we concatenate the user embedding eu with the aggregated outputs hwt and then feed it into a fully connected layer to generate the POI candidate score list suU for user u.

Nevertheless, due to the data sparsity, the prediction performance will be unsatisfactory when a user has few checkins. To tackle this problem, we propose the cross-user association to provide more possible POI candidates according to the most similar users. The user similarity is defined according to whether the user pair visit the same place on the same day. Specifically, the similarity between user um and user un is: τm,n = |Lm∩Ln| |Lm| , where Lm denotes the set of all locations that user m visits. We first generate the user similarity matrix CorrU for measuring how similar the user pair's interests in POIs are, where CorrU ∈ RM×M , each item τm,n, m, n ≤ M in CorrU denotes the similarity between a user pair. CorrU is normalized to [0, 1].

On the other hand, we can generate a POI candidate score matrix SU , where SU = [su1 U ; su2 U ; · · · ; suM U ], SU ∈ RM×N , suU denotes the POI candidate score list of user u at time tT , u ∈ U. We believe that users with similar interests in POIs are likely to visit the same places. If we can not predict one's next location accurately due to his incomplete trajectory history, the next POI candidates of his most similar users can be considered as the choice. Therefore, we multiply the POI candidate score matrix SU with the user similarity matrix CorrU to get the adjusted score matrix ˆSU :

where ˆSU ∈ RM×N . Finally, for a user u, we can get the adjusted POI candidate score list ˆsuU from ˆSU.

3.4 POI-Net and Cross-POI Association

Based on the observations on the POIs in Figure 1(a) and Figure 1(b), we derive the assumption that a POI can appeal or choose the users autonomously and there exist patterns in POIs' behavior. Hence, we intend to explore POIs' appeals and predict the next user who will visit the POI. From the perspective of the location side, we assume that POIs' appeals are dynamically changed over time. Therefore, we exploit POIs' dynamic appeals by using RNNs to capture temporal patterns considering different time slots in a day and different days in a week.

Given the historical data, we first represent POIs' records in form of user sequences. For each POI l, we denote its visiting point as alt = 〈l, u, s, d〉. Here we represent time t on two scales, i.e. s denotes the time slot in a day and d denotes the day in a week. The whole visiting history of POI l is denoted as a set of chronologically ordered visiting points Al = {alt1 , alt2 , · · · , altT′ }, where T ′ is the length of visiting history. In the POI-Net, given a POI's visiting history in the last T ′ -1 steps, the primary goal of the POI-Net is to predict the top-k most likely users Uk who may visit this POI at the next time tT ′ . In this paper, we take the basic RNN to model POIs' behavior patterns and use the current hidden state ht to predict the next user. Besides, to model the personalized appeal of each POI, we concatenate the POI embedding el with the current hidden state ht and then feed it into a fully connected layer to generate the user candidate score list slL for POI l.

However, the performance of the user prediction is unsatisfactory because some POIs are checked in very few times. To deal with this problem, after capturing the POIs' appeal by the RNNs, we further employ a cross-POI association approach to improve the performance of the next user prediction. The POI similarity is according to whether the POI pair are visited by the same user on the same day. Specifically, the similarity τm,n between POI lm and POI ln is the number of days on which POI m and n appeal the same user, i.e., Um,d ∩ Un,d ̸= ∅, where Um,d denotes the set of visitors of location m on day d. We first generate the POI similarity matrix CorrL for measuring how similar the POI pair's appeal to users are, where CorrL ∈ RN×N , each item τm,n,m, n ≤ N in CorrL denotes the similarity between a POI pair. CorrL is normalized to [0, 1]. Meanwhile, we generate a user candidate score matrix SL which consists of the user candidate score list of each POI in set L, i.e. SL = [sl1 L ; sl2 L ; · · · ; slN L ], SL ∈ RN×M , slL denotes the user candidate score list of POI l at time tT ′ , l ∈ L. Under the assumption that similar POIs appeal to common users, we can provide more possible user candidates for a POI l by using the next user candidates of its most similar POIs. Hence, we multiply the POI similarity matrix CorrL and the user candidate score matrix SL to get the adjusted score matrix ˆSlL:

where ˆSL ∈ RN×M .

3.5 Bi-direction Speculation

After predicting the next POI that a user will visit from the User-Net and cross-user association, and the next user that a POI will appeal from the POI-Net and cross-POI association, we integrate them for bi-direction speculation to improve the performance of the next location prediction. In this way, we achieve a more reasonable and precise location prediction result. In detail, after generating the adjusted POI candidate score matrix ˆSU and the user candidate score list ˆSL, we apply a fusion layer to integrate the two by maxpooling. The maxpooling operation is to take the lager value for the corresponding position in ˆSU and ˆS⊤L , where the output SF ∈ RM×N . The key formula of the hybrid representation SF is as follows:

For a user u, we can get the final hybrid POI candidate score list suF from SF . Finally, we rank possible POIs in suF according to the scores and get the top-k most likely POIs {Lk} for location prediction.

4 Experiments and Analysis

4.1 Experimental Settings

Datasets. We conduct experiments on two widely-used real-world check-in datasets: Gowalla and Foursquare. Gowalla [Cho et al., 2011] is collected from February 2009 to October 2010 from the Gowalla Website. Foursquare [Yang et al., 2014] is collected from April 2012 to January 2014. They both contain check-in records in form of userID, POIID, latitude, longitude, and timestamp. Following the setting in [Yang et al., 2020], we eliminate inactive users who have records less than 100. We take the first 80% check-ins as the training set, the other 20% as the testing set.

Evaluation Metrics and Parameters. We evaluate the effectiveness of the proposed method by using average Accuracy@K and Mean Reciprocal Rank (MRR) [Yang et al., 2020]. Acc@K is the percentage of correct predictions for a list of predictions with length K: Acc@K = Ncorrect K . To get more convincing results, we repeat each experiment 15 times and take the average metric values for evaluations. We empirically set the dimension of hidden states for RNN units and the dimension of embeddings as 10. Parameters in flashback block including temporal decay α and spatial decay β follows the setting in [Yang et al., 2020].

Compared Methods. We compare our proposed BSDA with the following methods: 1) BPR [Rendle et al., 2009] is a popular matrix factorization method. 2) FPMC [Rendle et al., 2010] is a personalized Markov Chain algorithm by combining the matrix factorization and Markov chain. 3) RNN [Zhang et al., 2014b] is a vanilla RNN architecture. 4) PRME [Feng et al., 2015] is a personalized ranking metric embedding method for modeling the sequential transitions. 5) STRNN [Liu et al., 2016] extends RNN and models local temporal and spatial contexts. 6) DeepMove [Feng et al.,

2018] is an attentional recurrent network for mobility prediction. 7) LBSN2Vec [Yang et al., 2019] is a hypergraph embedding approach combining the random-walk-with-stay scheme and node embedding learning for feature learning. 8) STGN [Zhao et al., 2020] is a spatiotemporal gated network by enhancing LSTM. 9) Flashback [Yang et al., 2020] is an RNN-based model for modeling sparse user mobility traces by doing flashbacks on hidden states in RNNs.

4.2 Performance Comparison

The results of our proposed model BSDA and compared methods on two datasets evaluated by Accuracy@K and MRR are shown in Table 1. From the table we can observe that: 1) All RNN-based methods including RNN, STRNN, DeepMove, STGN and Flashback perform better than FPMC since they can learn high-order sequential transitions from users' historical trajectories while FPMC can only learn loworder transitions according to the latest check-in. 2) Methods obtain better performances on Foursquare. This is probably because the data in Gowalla is more sparse. 3) BSDA outperforms all other methods on both datasets, showing its effectiveness for the next location prediction. It improves 25.56%, 28.21%, 20.49%, 22.91%, at Acc@1, Acc@5, Acc@10, MRR respectively compared with Flashback on Gowalla dataset and improves 22.92%, 22.46%, 14.43%, 18.40%, at Acc@1, Acc@5, Acc@10, MRR respectively on Foursquare dataset. The significant improvements of BSDA indicate that it can capture more useful information via bi-direction speculation and dual-level association.

4.3 Model Analysis and Discussion

Effectiveness of Key Components

We further implement three variants to evaluate the contribution of each key component in our proposed BSDA to the performance, including the cross-POI association, the crossuser association and the next user prediction. The variants are as follows: 1) BSDA w/o Cross-POI Association: we remove the cross-POI association, integrating the User-Net, the crossuser association, and the POI-Net for prediction. 2) BSDA w/o Cross-User Association: we remove the cross-user association, integrating the User-Net, the POI-Net, and the crossPOI association for prediction. 3) BSDA w/o user prediction: we remove the POI-Net and the cross-POI association, using the User-Net and the cross-user association for prediction.

Table 2 shows the result of the ablation study. From the table, we can observe that the variant without user prediction block gets the worst performance while the BSDA achieves the best performance. The variant without the cross-POI association and the one without the cross-user association perform slightly worse than BSDA but better than the variant without user prediction. The result demonstrates that each key component in BSDA plays important role in improving the location prediction performance.

Discussions

In addition to the comparisons above, we also conduct some experiments for the model analysis further. Due to the space limitation, we only show the results on the Gowalla dataset.

First, we evaluate the performance of our method with different fusion strategies for bi-direction speculation. To be specific, we aggregate the results of the User-Net and POINet using different fusion methods including weighted addition, multiplication, maxpooling and minpooling. Results in Table 3 demonstrate that the maxpooling is the best choice for the integration for bi-direction speculation. It is reasonable since we intend to improve the performance of location prediction from the human side by using the user prediction from the location side. In this case, we can adjust the POI candidate score by giving a bigger score to the possible candidate or a small score to the impossible candidate. Besides, we evaluate the two prediction networks separately. In the BSDA, we take the raw data of the User-net for the user prediction in the POI-net. From Table 3, we can find that the performance of the user prediction on the raw data is unsatisfactory. This is because the approach of data pre-processing is to eliminate the inactive users with few check-ins, not considering selecting POIs for the user prediction in POI-net. Therefore, the POI-net for the user prediction will perform badly when most POIs have few check-ins. Despite this, POI-net contributes to the performance of BSDA. It outputs the probability list of users who will visit a given POI at a given time. A POI may appeal a certain group, making user candidates within a limited scope. Therefore, time-aware probability can tell users apart. When we make bi-direction speculation, collaborative analysis is effective since the results of user prediction can help find abnormal values and then adjust.

Moreover, we discuss how to measure the similarity between the two POIs. In the literature, spatial influence is commonly considered as an essential factor in the next location prediction, where the spatial influence usually means the geographical distance. This is easy to understand that one's decision about where to go next is closely related to the last few visits. It may contribute more to the decision if the recent check-in is close to the current location while less if it is far away. Obviously, this spatial influence is crucial for capturing transitions between successive check-ins. However, the purpose of the cross-POI association is to find more possible user candidates according to the most similar POIs under the assumption that similar places may appeal to common users. So we need to find out the characteristics of POIs that appeal to common users instead of the geographical distance.

4.4 Case Study

To give a clear illustration of the performance of BSDA, Figure 3 shows three cases corresponding to each component of BSDA. The ground truth is in the red dotted box. In Figure 3(a), we display the case for the cross-user association. Given the check-in trajectory of user u164 , we intend to predict the next location. But it is a challenging task since the next location is l59 where u164 has never checked in. In this case, we find u164's most similar user u89 to deal with the problem because we believe that similar users may visit the same place. Therefore, benefiting from the check-in history of u89, we predict the next location l59 successfully.

Furthermore, in Figure 3(b), we display the case for the cross-POI association. Similarly, we may fail to predict the next user only based on l282's visiting records since the data is too sparse to involve user u85. In this case, l303, as l282's most similar POI, provides the user candidate for us and helps to predict the next user u85 successfully.

Finally, Figure 3(c) illustrates how the bi-direction speculation helps the next location prediction. Specifically, form the perspective of the human side, we give a top-5 POI candidate ranking list, where l901 is the first while the ground truth l77 is the second. However, from the perspective of the location side, we infer that u195 is unlikely to visit l901 in the near future according to its top-5 user candidates. Therefore, combining the results of both perspectives, we predict the next location l77 successfully.

Figure 3: Prediction cases by our proposed BSDA. The ground truth is in the red dotted box.

5 Conclusion and FutureWork

In this paper, we propose a novel Bi-direction Speculation and Dual-level Association method (BSDA) for the next location prediction by mining both users' interests in POIs and POIs' appeal to users. Specifically, we first develop two networks to explore users' interests and POIs' appeal separately. Additionally, we exploit the cross-user and cross-POI association to alleviate the data sparsity by mining similar users and POIs to enrich the candidates. Evaluations on two public realworld datasets show that BSDA achieves significant improvements over the state-of-the-art methods. To our knowledge, we are the first one to propose the bi-direction speculation for the location prediction, i.e., from both the perspective of the human side and the location side.

The function of each component of BSDA can be analyzed separately as well as the whole method, and possible refinement of each component may be future research. In the future, we plan to extend BSDA by incorporating auxiliary information. Besides, the performance of the next user prediction in POI-Net is unsatisfactory. Thus we will try to improve its performance for benefiting the location prediction better. Furthermore, we will find more effective measures of user and POI similarity to provide more convincing candidates.

Acknowledgments

This work was supported by the National Nature Science Foundation of China (U1803262).