Discovering Subsequence Patterns for Next POI Recommendation

1 Introduction

With the rapid growth of Location-Based Social Networks (LBSNs), such as Yelp and Foursquare, point-of-interest (POI) recommendation has attracted wide attention from both academia and industry [Zhang and Wang, 2015; Yin et al., 2016; Wang et al., 2018]. As a natural extension of general POI recommendation, next POI recommendation aims at predicting the POIs that are most likely to be visited next given the user's check-in history. Compared with the general POI recommendation, next POI recommendation focuses more on exploiting user movement patterns hidden in the historical check-in sequence.

Next POI recommendation has attracted great research interest recently. Early studies model the influence of previously visited POIs on future ones in a static manner. They regard each POI sequence as a Markov chain [Cheng et al., 2013; Feng et al., 2015; He et al., 2016; Zhao et al., 2016] and then integrate the sequential patterns in terms of transition probability between POIs to the conventional matrix factorization models. Recent studies adopt recurrent neural network (RNN) based models to keep track of the sequential dependencies [Kong and Wu, 2018; Liu et al., 2016; Zhao et al., 2019]. However, such sequential dependencies cannot fully account for human mobility [Cho et al., 2011; Kong and Wu, 2018]. The user's check-in behaviors may be influenced by a subsequence of previously visited POIs as a whole rather than single POIs, which is beyond POI-level sequential patterns. Figure 1 shows the subsequence pattern of the user's check-in sequence. Modern cities consist of functional zones such as residential areas, business districts, and educational areas, etc. It is quite possible that people's movement patterns sometimes only exist among functional zones rather than single POIs. Besides, their movements within a specific zone could not show any sequential pattern. Thus, the check-in subsequence generated within a functional zone should be treated as a whole to represent the semantics or function of the corresponding geographical region. Moreover, such subsequences are not limited to the functional zones. Actually, they can result from different factors in reality. For example, a subsequence may be generated because all the POIs in the subsequence match the user's personal interests. The set of POIs in the subsequence will perform as a whole when influencing the user's future visit.

∗Corresponding Author

Nevertheless, discovering and integrating subsequencelevel sequential patterns for the next POI recommendation is challenging. The reason is that it is extremely difficult and even impossible to predefine the length or granularity of effective and meaningful subsequence (i.e., semantic subsequence) due to their variety and complexity [Cho et al., 2011]. In fact, these semantic subsequences have different granularities or lengths. In order to exploit and integrate such multi-granularity sequential patterns in the next POI recommendation, we need to automatically analyze the underlying structures and identify each semantic subsequence in the user's check-in sequence.

In this paper, we aim to automatically detect and identify each semantic subsequence of POIs and discover their sequential patterns (i.e., sequential dependencies among semantic subsequences). To this end, we propose a novel model Adaptive Sequence Partitioner (ASP). Specifically, we design a hierarchical framework to automatically learn the latent structures of the user's check-in sequence, which is similar to the latent topic discovery from texts [Blei et al., 2003], but much more challenging due to the consideration of POI order structure. Technically, we adopt a stacked recurrent neural network to hierarchically learn the representations from the check-in sequence. In this design, the higher layer learns from the lower in order to perform an abstraction with a larger level of granularity. In order to automatically identify the partition of each layer, we introduce the boundary detector into the RNN cell and adopt the state-based methods to detect boundaries in the input sequence. In this way, successive cells with the same state will formalize a segment and be updated in a lower frequency, while the higher layers can iteratively learn from the lower and formalize the larger segment. As a result, the latent structure can be well captured into the segments with different levels of granularity. In order to aggregate the structures from different stacked layers, we further introduce the layer-wise attention to learn the alignment for each layer.

However, the intrinsic sparsity of the user's check-in sequence may become the bottleneck of our proposed ASP and lead to overfitting. This is because LBSN data has a low sampling rate in both space and time compared with GPS trajectories [Wang et al., 2016; Lv et al., 2018]. We need to incorporate domain knowledge to alleviate the issue of data sparsity in order to leverage the power of deep neural networks. To this end, we propose to integrate the domain knowledge in both spatial and temporal contexts (i.e., the spatial and temporal effects on the user's check-in behaviors) and develop a novel Power-law Attention (PA) mechanism with fewer parameters to replace the conventional vanilla attention mechanism. Specifically, we adopt the power-law decay towards the distance and exponential decay towards the time interval into the standard attention alignments among all the representations of outputs. In this way, PA could express the model that is equivalent to the real-world average willingness-to-visit [Cho et al., 2011; Yuan et al., 2013] under power law.

To sum up, the main contributions of our research are summarized as follows:

• We design and develop a novel recommendation framework ASPPA to identify the semantic subsequences of POIs and discover their sequential patterns. Specifically, this model can learn the latent structures by automatically partitioning the POI sequence without handcrafted features.
• We propose a Power-law Attention mechanism to integrate the domain knowledge in both spatial and temporal contexts for the user's check-in sequence. Our design alleviates the data sparsity and largely reduces down the number of parameters.
• We conduct extensive experiments to evaluate our framework on two widely used real-world datasets. The results show that our model is effective and outperform state-of-the-art techniques.

2 RelatedWork

POI recommendation has attracted intensive attention due to a wide range of potential applications. Most existing studies focus on how to model user preferences for POIs with the awareness of the joint effect of rich contexts [Liu et al., 2017]. Some recent studies utilize neural network based approaches for POI recommendation [Yin et al., 2017]. Yang et al. [2017] regard user-user and POI-POI graph as the semi-supervised labels and adopt a multi-layer feed-forward network to conduct collaborative filtering.

The next POI recommendation is an emerging task and has attracted great research interest. Zhao et al. [2016] build a pairwise tensor factorization framework with user-POI, POItime, and POI-POI interactions. He et al. [2016] explore the latent pattern-level preference for each user and propose a tensor-based latent model to capture the successive checkin behavior. Feng et al. [2015] develop a pairwise metric embedding algorithm to jointly model the sequential information and individual preference. Liu et al. [2016] introduce time-specific and distance-specific transition matrix in RNN to model local temporal and spatial contexts. Kong et al. [2018] and Zhao et al. [2019] integrate spatial and temporal gating mechanism into LSTM units to incorporate the necessary information for prediction. Chang et al. [2018] provide a better pre-trained POI embedding model to capture the characteristics of POIs and improve existing POI recommendation models. Wang et al. [2020] develop a next POI recommendation system for mobile devices. Although previous studies exploit the sequential patterns in the user's check-in sequence, they only focus on POI-level and ignore the sequential dependency among semantic subsequences. Kong et al. [2018] explore the area of interest that the user visits, but they need to manually predefine the user's visit sessions. Our ASPPA can detect the semantic subsequences of POIs and further discover their sequential patterns to improve the next POI recommendation.

Figure 2: Architecture of ASPPA model

3 ProposedModel

In this section, we introduce the details of our Adaptive Sequence Partitioner with Power-law Attention (ASPPA) model. Our model identifies the semantic subsequences of POIs and integrates the domain knowledge in spatial and temporal context. To this end, we design an attention-based stacked RNN architecture. As shown in Figure 2, the model consists of two components, i.e., Adaptive Sequence Partitioner (ASP) and Power-law Attention (PA). Next, we give the problem statement and then introduce each component.

3.1 Problem Statement

Let U be the set of users and L be the set of POIs. For each user u, her check-in history (in chronology order) is denoted as Vu = {(lu t , τt) | t = 1, 2, ...}, where each tuple (lu t , τt) is the tth visit of user u ∈ U, with POI lu t ∈ L and time stamp τt. The problem of next POI recommendation is to predict the POIs for user u at the next time step, i.e., for each user we learn a personalized ranking function fu : V → Ω that maps the user's check-in history to a probability distribution for the target POI set

The output is the top-k ranked POIs according to the predicted probabilities.

3.2 Adaptive Sequence Partitioner

We propose the Adaptive Sequence Partitioner (ASP) to learn the latent structures of the user's check-in sequence. In order to capture the sequential patterns of semantic subsequences, we need to learn hierarchically from the check-in sequence, which is similar to the latent topic discovery from texts [Blei et al., 2003]. Thus ASP is designed to be a stacked RNN architecture [Hihi and Bengio, 1995]. As shown in Figure 2, lower layer is served as the input of the upper layer. It transfers the state output h as well as the boundary detector z. If the input boundaries can form the partition and control the update of the sequence, we can learn the subsequence information in each layer and the sequential patterns among these POI subsequences can also be learned from the hierarchy of the model. We will show in the following parts.

Gating Mechanism. In ASP, the subsequence is identified through the partition of each layer. Inspired by [Chung et al., 2017], ASP adopts a binary boundary detector z to control the pattern of cell update. Specifically, for ℓ layer, ASP has the input, forget, output gates (iℓt , f ℓ t , oℓt ), cell proposal ˜ cℓt and the pre-activation of boundary detector ˜ zℓ t , which are obtained by

where iℓt , f ℓ t , oℓt , ˜ cℓt ∈ RNh , ˜ zℓ t ∈ R. σ is the logistic sigmoid function. φ is the hyperbolic tangent function. W j i (i > 0) is the linear transition matrix from layer i to layer j. hℓt is the hidden output for layer ℓ at time t. For the top layer, we do not include the output from upper layers. For the bottom layer, h0t is the POI embeddings xt. The input boundaries z0 t = 1 make sure that all the inputs are valid.

Figure 3 compares the gating mechanism between LSTM and ASP. We can see that ASP integrates the information from upper and lower layers with a stacked RNN architecture. The gate values are generated the same as LSTM with the previous hidden state hℓt-1 , the upper layer hℓ+1 t-1 and the lower layer hℓ-1 t which are controlled by the boundary detectors z. The boundary detector z is learned through preactivation ˜ z and served as the outputs of this time step. We will show it in the follow parts.

Cell Update. The cell state c of ASP is updated according to the gates. In order to transfer the cell information in a stable way as well as to form the partition, we identify the recurrent generalization in different depths [Krueger et al., 2017]. Specifically, the cell state updates in three different ways according to the combination of boundary detectors

where ⊙ denotes the element-wise product. UPDATE operation is the same as LSTM. The current cell state ct is updated with the previous cell state ct-1 and cell proposal ˜ ct after the trade-off from forget gate ft and input gate it respectively. Following the idea of Krueger et al. [2017], we incorporate COPY operation that selects some RNN cells to hold as the previous time steps. However, rather than randomly selection to alleviate the issue of over-fitting, the COPY operation is learned to generate a more coalesce granularity. Furthermore, in order to learn the new geographical region the user begins to visit, we also generate the FLUSH operation to clear the cell state and only preserve the information of this time step. The FLUSH can start a new semantic subsequence.

Then the final output of the cell < hℓt , zℓ t > is obtained by

where hℓt gets updated the same as LSTM except when the cell state is COPY to transfer the state from the last time step. Boundary proposal ˜ zℓ t is projected to {0, 1}with step function in order to generate a binary boundary.

With ASP, the check-in sequence [hℓ1 , ..., hℓT ] is hierarchically projected to semantic spaces. Since the stacked layers in ASP capture different granularities, the sequence composition should be determined by all of them. Therefore we propose the layer-wise attention mechanism αh ℓ = σ (vT ℓ hℓt ) to get the combined output. The layer-wise attention learns the weights of each layer by aggregating all the time steps until now. So we can provide a uniform alignment for each time step by considering the overall effect of the entire sequence. Then we aggregate the hidden states ˜ht = ReLU (Wh ∑ℓ αh ℓ hℓt ) to get the output of each time step.

3.3 Power-lawAttentionMechanism

We propose the Power-law Attention (PA) mechanism to integrate spatial and temporal contexts of each check-in into our model. We first introduce spatio-temporal bias

where vo, vt ∈ {(li, τi)} are the check-in points, ∆o,t = τo - τt is the time interval, do,t = D(lo, lt) is the geographical distance, λ and k are the time and distance decays, respectively. We also ensure that it has a negative effect on the bias. With this bias, the weight score is defined as

where ˜ht is the output state of ASP. Then we can calculate the attention vector

Now we consider the user's real-world check-in behavior. Previous studies indicate that the spatial items obey the First Law of Geography [Tobler, 1970], which shows the user's willingness-to-visit ¯w on a pair of POIs. It can be formulated as a power-law distribution

where a and k are parameters of the power law, D(li, lj) is the geographical distance of POI li and lj. It has been widely used in POI recommendation problems [Yuan et al., 2013; Cho et al., 2011].

Inspired by the First Law of Geography, we can extend the geographical distribution ¯w to the spatio-temporal willingness

where ao,t is obtained by

This coefficient is the non-linear transformation of the user's current state ˜ht with the exponential decay towards time interval ∆o,t. In this way, the user's willingness incorporates both the spatial and temporal effects. It obeys the power law towards the distance, which is the same as the First Law of Geography. Furthermore, the coefficient considers the representation of current POI as well as the time interval.

With above settings, the attention weight αt in Equation 7 is equivalent to the average spatio-temporal willingness wo,t because of the following formula transformation

Then the dynamic representation of the user's check-in history can be represented by ˆh = ∑Tt=1 αt ˜ht, which shows that PA actually learns the user power-law willingness to visit the POIs under spatial and temporal contexts when it assigns the attention weights towards different time steps. This can effectively integrate the influence from different time steps.

The output layer of ASPPA consists of two fully connected layers and a drop-out layer. In order to control the negative samples for each training case and optimize the ranking metric for downstream parameter learning, we solve the following objective function

where Q is the query set, Θ denotes all the model parameters, λ′ is the weight decay coefficient of the L2 norm regularization posed on all trainable parameters.

4 Experiments

4.1 Experiment Setup

Dataset

We evaluate our proposed techniques on two real-world LBSN datasets, namely Gowalla and Foursquare, which have been widely used by previous studies on next POI recommendation [Feng et al., 2015; Zhao et al., 2019]. Gowalla 1 dataset includes the world-wide check-in data from February 2009 to October 2010. Foursquare 2 dataset includes check-in data from April 2012 to September 2013 within the United States (except Alaska and Hawaii). We filter out those users with fewer than 10 check-in POIs and POIs with fewer than 10 visitors as previous studies [Feng et al., 2015; Zhao et al., 2019] did.

In order to simulate the real-world next POI recommendation scenario, we rank the check-in history of each user in ascending order of the time step and split the dataset D into Dtrain : Dvalidation : Dtest as 8:1:1 according to previous studies [Liu et al., 2016; Chang et al., 2018].

Evaluation Metrics

To evaluate the performance of ASPPA, we employ Hits@k and MRR. For each test case, we recommend the POIs with top-k highest scores among all possible candidates in L. If the POI in the recommended list is actually visited by the user, the value of hit@k of a test case is 1; otherwise it is 0. The overall Hits@k is defined as Hits@k = #hit@k ||Dtest || where #hit@k is the number of hits in the test set and ||Dtest || denotes the number of test cases. MRR is the average reciprocal rank of positive examples. This metric reflects the overall ranking ability of the model.

Comparison Methods

We compare our ASPPA with following methods for next POI recommendation.

• MF: Most Frequented Location Model is a statistical based model. It calculates the POI distribution of a user based on the statistics of her previous check-ins. It captures the cyclical check-in habit of the user. This is a widely-adopted baseline method in some real-world LBSN services [Cho et al., 2011].
• PRME: Personalized Ranking Metric Embedding [Feng et al., 2015] develops a pair-wise metric embedding method to capture the interaction between the candidate and previous POIs.

1 http://snap.stanford.edu/data/loc-gowalla.html

2 https://sites.google.com/site/yangdingqi/home/foursquaredataset

• PRME-G: PRME-G [Feng et al., 2015] embeds users and POIs into the geographical context space. It extends the metric similarity scores under the real-world spatial influence.
• LSTM: Long Short-Term Memory [Hochreiter and Schmidhuber, 1997] is a widely used neural network to predict future behavioral trajectories. Compared with conventional RNN model, LSTM models the short-term and longterm sequential patterns by the gating mechanisms.
• Time-LSTM: Time-LSTM [Zhu et al., 2017] is a state-ofthe-art variant of LSTMmodel in recommender systems. The authors develop three versions of Time-LSTM in the paper and we adopt the third version because it achieves the best performance on our datasets. Time-LSTM improves the modeling of sequential patterns by explicitly capturing the multiple time structures in the check-in sequence.
• ST-RNN: Spatial Temporal Recurrent Neural Network [Liu et al., 2016] adopts RNN to model the user's previous checkin sequence. It captures spatial and temporal contexts with time and distance transition matrix.
• STGN: Spatio-temporal Gated Network [Zhao et al., 2019] achieves the state-of-the-art performance in the problem of next POI recommendation. It extends the LSTM gating mechanism with the spatial and temporal gates to capture the user's space and time preference.

Implementation and Training

In ASPPA, we adopt three ASP layers with the dimension of hidden states Nh in order to keep balance of the model effectiveness and efficiency. For consistency, we apply the dimension Nd of the output vector and the dimension Na of the attention projection vector the same as Nh. The dimension of POI embeddings is Ne. We also embed the weekday w ∈ [0, 6] and hour h ∈ [0, 23] of the query time and concatenate with the user's check-in history ˆh. Besides, in order to determine the time and distance decay λ and k, we apply the grid search over {0.0001, 0.001, 0.01, 0.1, 1}. The following experimental results of ASPPA are based on the best tuning performance on the validation set (λ = k = 0.001, Ne = 128, Nh = 256, learning rate 0.01 and dropout 0.5 for both datasets).

In the training procedure, we leverage the mini-batch SGD algorithm. Specifically, we set the batch size to 1024 according to device capacity. Note that the step function of zℓ t in Equation 4 is not differentiable, we manually apply the unchanged gradient when calculating gradients. We adopt Xavier initialization to initialize the weights of our network. For the implementation of comparison methods, we obtain the source code from the authors and report the best results after tuning all the hyper-parameters on the validation set.

4.2 Results and Discussion

Overall Performance

We evaluate the top-k recommendation performance (Hits@k) and overall ranking ability (MRR) in Table 1. All differences between our model and others are statistically significant (p < 0.01). We can see that our model consistently and significantly outperforms all compared models. Take Gowalla dataset as an example. When we score all the 32510 POIs and recommend the highest scored POI to the user, 12.12% of the test cases in Dtest are predicted correctly. When we recommend the top-20 highest scored POIs, 35.73% of the test cases have the user's actually visited POI in the recommended list. In addition, we have the following observations based on the experimental results.

Firstly, the excess performance of MF compared with other baselines shows the prediction ability beyond periodic habit. ASPPA makes significant improvement compared with MF as k increases. This shows that ASPPA can capture more subtle temporal dynamics to make a longer candidate list while the periodical guess of MF only works for the most frequent check-ins.

Secondly, the overall performance of all models on Foursquare is slightly better than that on Gowalla. The reason is that locations in Foursquare are limited in the United States. So the underlying movement patterns for users in Foursquare datasets are more uniform, where MF also shows a better periodic performance in Foursquare. Even Foursquare dataset is more sparse than Gowalla with more users but less userPOI interactions, each model still benefits from the uniform pattern in a limited manner. The superiority of our proposed ASPPA is more obvious in Foursquare, showing that ASPPA can learn more from sparse data compared with other alternatives. This is because ASPPA can capture the semantic subsequence patterns and incorporates the domain knowledge in both spatial and temporal contexts.

Thirdly, the RNN based models (LSTM, Time-LSTM, STRNN, STGN, ASPPA) achieve better performance than the metric embedding ones. The sequential recommendation can not only capture the neighboring constraints as the metric embedding models but also learn the user's sequential patterns. This would lead to better potential performance gain when a large number of sequential user interactions are available in real world scenarios. Since learning from the user's sequential patterns is the key to improve the sequential recommendation, ASPPA recognizes the latent structure to identify the sequential pattern among semantic subsequences beyond POI-level sequential patterns and further improves the overall performance.

Ablation Analysis

We conduct ablation tests with two variants that remove one component at a time. The first variant, ASPPA-PA removes the hierarchical framework and boundary detectors of each cell, which is equivalent to the power-law attention based LSTMmodel. The second variant, ASPPA-ASP replaces the power-law attention with vanilla attention by regarding the spatio-temporal bias b′o,t in Equation 6 as the normal bias variable. Due to the space limitation, we only show the Hit@k on both datasets. And regarding MRR we achieve results with similar trends. Figure 4 shows that the performance gain on Gowalla dataset of adopting subsequence information is more than 25% for all the metrics and while that in Foursquare is 35%. It demonstrates that recognizing semantic subsequences with multi-granularity latent structure is necessary for improving next POI recommendation.

5 Conclusion

In this work, we propose a novel model ASPPA for the problem of next POI recommendation. We adopt a stacked recurrent neural network framework Adaptive Sequence Partitioner to identify the sequential patterns among semantic subsequences by automatically learning the latent structure in the user's check-in sequence. To alleviate the data sparsity, we propose the Power-law Attention mechanism to integrate the domain knowledge in both spatial and temporal contexts. The experimental results on two real-world datasets show that our proposed framework is effective and significantly outperforms state-of-the-art methods.

Acknowledgments

This work was supported by NSFC (91646202, 61972069, 61836007, 61832017, 61532018), National Key R&D Program of China (2018YFB1404401,2018YFB1402701), ARC Discovery Project (Grant No. DP190101985 and DP170103954).