Next Point-of-Interest Recommendation with Inferring Multi-step Future Preferences

1 Introduction

In recent years, the large volume of check-in records provided by location-based services, e.g., Foursquare, greatly promotes the researches on next point-of-interest (POI) recommendation [Liao et al., 2018; Zhao et al., 2019; Zhao et al., 2020; Sun et al., 2021; Chen et al., 2021]. These methods aim at modeling sequential check-in behaviors and predicting time-sensitive POI visits, which emphasize that learning user preference from past and current check-in behaviors is a fundamental problem in boosting the next POI prediction.

With the assumption that users' next movements are highly correlated with their latest check-in behaviors, many next POI recommenders focus on modeling users' current checkins (i.e., short-term behaviors). For instance, the pioneer work FPMC-LR [Cheng et al., 2013] models two successive check-ins with localized region constraint incorporated. Afterwards, the studies derived from metric embedding, e.g., PRME [Feng et al., 2015], and Word2Vec, e.g., HCT [Zhang et al., 2019], aim to model the sequential check-ins and learn transition regularities by capturing the local co-occurrence of POIs. Later, recurrent neural networks (RNN) and its variants, such as ST-RNN [Liu et al., 2016] and ARNN [Guo et al., 2020], have gained much attention to capture users' current preferences by modeling the whole sequential information rather than the pairs of POIs within a trajectory as in the above studies. Meanwhile, a few methods fusing both past (i.e., long-term behaviors) and current sequential behaviors have achieved state-of-the-art performance in the next POI prediction [Wu et al., 2020; Sun et al., 2020].

∗Corresponding Author.

Despite the success of the above models, we argue that they are not sufficient to learn accurate user preference, as they completely ignore the potential impact of future behaviors. Intuitively, a user's next movement may be affected by the multi-step future behaviors in addition to past and current behaviors, as they may have activity planning in mind. For illustration, Fig. 1 presents Alice's two daily trajectories. We attempt to make a recommendation for her at lunchtime. In trajectory 1⃝, Alice went to a restaurant l4 close to her office l3, which implies that her next movement is highly influenced by her recent visits (e.g., office). While in trajectory 2⃝, we observe that Alice checked in at a library l6 and then she went to a distant restaurant l7 rather than a nearby restaurant l5. Afterwards, she went to a cinema at l8 and shopping at l9 after leaving l7. That is to say, she most likely has an activity planning ahead of the check-in at a restaurant.

The above example emphasizes the potential impact and indicates promising improvements of future behaviors bringing in for next POI prediction. This is further verified by the most recent effort [Shao et al., 2021], which leverages users' past and pre-specified future courses to achieve outstanding performance in multiple consecutive course recommendations. Nevertheless, in the next POI recommendation scenario, it is always impossible to acquire users' explicit multi-step future behaviors, for example, as in Alice's trajectory 2⃝, such activities, going to a cinema at l8 and shopping at l9, are regarded as her future behaviors and always unavailable when recommending a restaurant for her at l7. As a result, incorporating such future behaviors is non-trivial and still an open question in next POI recommendation.

To this end, we propose a novel Context-aware Future Preference inference Recommender (CFPRec) to help infer and integrate user future preference in a self-ensembling manner, which consists of past and current preference encoders as well as future preference extractor. In particular, we employ a Transformer layer and an LSTM layer to model users' past and current preferences, respectively. Meanwhile, we devise three auxiliary objectives to supervise the past preference learning. The periodic property of users' daily checkin behaviors [Liu et al., 2016; Feng et al., 2018] motivates our design of the extractor for implicit future preference inference via a self-ensembling way, i.e., the multi-step future preferences are derived from the learned past preference with a two-layer attention aggregation, which mitigates the challenge of the absence of explicit future behaviors. As such, CFPRec encodes both left and right contexts (i.e., past/current and future preferences) for the next POI prediction.

Our main contributions lie in three-fold. (1) To the best of our knowledge, we are the first to investigate the effect of multi-step future preferences in next POI recommendation. (2) The proposed CFPRec jointly models users' past, current and future sequential behaviors to gain more expressive preference representation. Particularly, a future preference extractor is devised to infer the implicit future preference from the learned past preference in a self-ensembling manner. (3) The experimental results on three real-world datasets show that our CFPRec outperforms state-of-the-arts with average lifts of 16.4% and 21.6% on HR and NDCG, respectively.

2 RelatedWork

A line of research work on next POI recommendation assumes that users' next check-in behaviors are highly influenced by their recent visits. Hence, a class of Markov-based methods [He et al., 2016; Zhao et al., 2016] is introduced to learn the transition probability between successive checkins. Due to the success of the RNN in modeling sequential data, many approaches are derived from RNN and its variants (e.g., LSTM [Hochreiter and Schmidhuber, 1997]), which are able to characterize users' current preferences (i.e., short-term preferences) by modeling the whole sequential behaviors. ST-RNN [Liu et al., 2016] and SERM [Yao et al., 2017] adopt RNN to model spatiotemporal regularities. ATST-LSTM [Huang et al., 2019] and ARNN [Guo et al., 2020] extend the LSTM with an attention mechanism to capture the relevant behaviors within trajectories. To overcome the long-term dependency problem of the RNN based methods, STAN [Luo et al., 2021] employs the bi-attention model to learn correlations between non-consecutive check-in behaviors for next POI prediction.

Another line of studies exploits both past and current sequential behaviors, which has shown great benefits in next POI recommendation. For example, DeepMove [Feng et al., 2018] applies a GRU unit to model the current sequential information and leverages the attention module to capture the most related context from the past trajectories. Similarly, PLSPL [Wu et al., 2020] learns a user's location- and category-level preference from current trajectory via two parallel LSTM units and extracts the general preference from a past long-range sequence by using attention mechanism. STGN [Zhao et al., 2019] equips the LSTM with time and distance gates to model users' long-term (i.e., past) and shortterm (i.e., current) interests simultaneously. Although such RNN/LSTM based methods have shown the powerful ability in modeling sequential trajectories, they cannot capture the geographical correlations among non-consecutive POIs due to the nature of the standard RNN. As a result, LSTPM [Sun et al., 2020] is proposed to address such a limitation by employing a geo-dilated RNN.

In fact, users' next movements might be influenced by their future POI visits in addition to past and current behaviors. However, the absence of explicit future behaviors brings challenges to learn future preferences, which hinders the effectiveness of next POI recommenders in capturing accurate user preference. A few efforts on sequential item recommendation tend to augment the recommendation quality by fusing future signals. Specifically, GRec [Yuan et al., 2020] utilizes a gapfilling mechanism to model past and future contexts of a target item in the model training. A more recent study, FAT [Lu et al., 2021], proposes to infer potential future preferences from other similar users. Considering the special characteristics of the next POI recommendation scenario, the periodic property of users' daily check-in behaviors motivates our design of the extractor for future preference inference from the learned past preference. Eventually, we achieve to model users' past, current and future preferences for more accurate next POI prediction in a self-ensembling fashion.

3 The ProposedMethod

Fig. 2 illustrates the framework of CFPRec, which consists of three modules: (1) past preference encoder, which models users' past long-range trajectories to capture the contextaware correlations between non-consecutive check-in behaviors; (2) current preference encoder, which learns users' current preference by modeling the latest sequential check-ins; and (3) future preference extractor, which equips with a two-layer attention aggregation for inferring multi-step future preferences. As such, our proposed CFPRec is capable of incorporating past, current and future preferences for more accurate next POI recommendation. Before diving into each module, we first give the problem formulation and then introduce our proposed CFPRec.

Problem Formulation. Let U = {u1, u2, . . . , u|U|} denote a set of users; L = {l1, l2, . . . , l|L|} be a set of POIs (i.e., locations); C = {c1, c2, . . . , c|C|} be a set of categories of POIs; and T = {t1, t2, . . . , t24, tw0 , tw1 } be a set of time slots (map one day into 24 slots) as well as weekday (tw0 ) and weekend (tw1 ). A check-in record r = (u, l, c, g, t) indicates that user u visited POI l at time t, where l is characterized by category c and geocoded by g, i.e., (longitude, latitude). For each user u ∈ U, let Su = {Su 1 , Su 2 , . . . , S u n } denote her trajectories (i.e., check-in sequences), where the i-th trajectory Su i = {r1, r2, . . . , r|Su i |} denotes a set of chronologically ordered check-in records within a day. User u's latest trajectory Su n = {r1, r2, . . . , rk} is regarded as the current sequential behaviors Su cur (i.e., short-term behaviors), and the past behaviors Su past (i.e., long-term behaviors) are formed by the trajectories {Su 1 , . . . , S u n-1 } that happened before Su cur in the past several days (e.g., 7 or 14 days).

Research Problem. Given a user u's past behaviors Su past and current behaviors Su cur , we aim to recommend a set of POIs for user u to visit at the next timestamp tk+1 by inferring her multi-step future preferences, i.e., at tk+1, . . . , tT .

3.1 Past Preference Encoder

Generally, users often visit POIs for different purposes (i.e., various contextual environments) and such complex nature of users' check-in behaviors brings significant challenges to learn accurate user preference. Fortunately, the periodic property of users' behaviors provides essential signals for user preference learning. Inspired by the recent advance of the context-aware location embedding method [Lin et al., 2021], we employ a bidirectional Transformer [Vaswani et al., 2017] as the past preference encoder for two reasons. First, in the model training process, the Transformer encoder is able to model both left and right contexts for a target POI, which enables to learn more expressive representations for POIs. Second, it shows a powerful ability in capturing context-aware correlations between non-consecutive check-ins and aggregating the most relevant behaviors automatically within a trajectory [Lin et al., 2021].

Accordingly, as shown in the left part of Fig. 2, we propose an extensional Transformer encoder to capture a user's past preference which encodes her spatiotemporal-aware dynamic preference over POI and static preference regarding activity. For example, a user may visit a different restaurant (i.e., POI) at lunchtime with the same activity (i.e., food). Given a user u's past trajectory Su i = {r1, r2, . . . , r|Su i |} and Su i ∈ Su past , each check-in behavior ri = (u, l, c, g, t) is represented as:

where ⊕ denotes the concatenation operation; u, l, c ∈ RD are the embeddings of user, location, category, respectively; t ∈ R2D encodes the time slot and weekday/weekend, i.e., t = tk⊕tw0 /tw1 1 . Thus Su i is transformed by the embedding layer with ESu i = [er1 , er2 , . . . , er|Su i | ], which is then fed into the Transformer layer:

where F (·) is the softmax function; TransLayer(·) is a Transformer layer; HSu i is the output matrix consisting of the hidden vectors and hi ∈ R5D ; WQ,WK,WV ∈ R5D×5D are transformation weight matrices of query, key and value, respectively; ∆dist ∈ R|Su i |×|Su i | is the spatial relation matrix; and given the distance dist(li, lj) derived from gli and glj , ∆dist i,j = (1 + dist(li, lj))-1 measures the spatial influence between locations li and lj.

It is worth noting that the past preference encoder serves as a significant role in capturing user past preference from long-term sequential behaviors. Inspired by the recent study in constructing self-supervised training objective to achieve the masked token prediction [Lin et al., 2021], we devise three auxiliary tasks to further supervise the past preference learning and help to capture more accurate preference representation. Given a sequence Su i , we randomly mask 20% check-in records, e.g., the original r2 = (u, l, c, g, t) will be replaced by rm = (u, lm, cm, gm, tm), and the corresponding embedding vector and hidden state are represented by em and hm, respectively. As such, we conduct multi-task predictions for the original location l, category c and time t by decoding the hidden vector hm via the softmax layer:

where Wl ∈ R5D×|L| ,Wc ∈ R5D×|C| ,Wt ∈ R5D×|T | are the transformation matrices corresponding to such three tasks.

1 All the following t integrates the embeddings of the time slot and weekday/weekend unless specified otherwise.

The loss (negative log-likelihood) of auxiliary tasks is,

where Nm is the set of all masked records.

3.2 Current Preference Encoder

The recurrent module is widely adopted to model users' short-term sequential behaviors among the recent studies [Wu et al., 2020; Sun et al., 2020]. We thus employ an LSTM unit to characterize users' temporal-aware sequential dependency from the current check-in behaviors. As shown in the middle part of Fig. 2, given a user u's current trajectory Su n , each check-in record ri ∈ Su n is embedded by eri as in Eq.(1). Accordingly, the embedded current trajectory ESu n = [er1 , er2 , . . . , erk ] is fed into the LSTM layer:

where hti and hti-1 are the hidden states corresponding to timestamps ti and ti-1, respectively. In this way, the LSTM layer finally outputs a sequence of hidden states for the user's current preference, that is, HSu n = [ht1 , ht2 , . . . , htk ].

3.3 Future Preference Extractor

As depicted in Fig. 1, users may often have activity planning ahead of their next movements, thus fusing future behaviors would facilitate to capture more accurate user preferences w.r.t. their next POI visits. However, as in Alice's trajectory 2⃝, the activities (going to a cinema at l8 and shopping at l9) are regarded as her future behaviors and always unavailable when recommending a restaurant for her at l7. A few bi-directional based methods have encoded past and future behaviors in the model training, i.e., modeling the left and right contexts for the target POI [Lu et al., 2021]. However, in the model prediction, they are unable to access users' explicit future behaviors, which consequently limits their capability on capturing user preference. Fortunately, the periodic property of users' daily check-in behaviors inspires us to derive an extractor, which is equipped with a two-layer attention aggregation for inferring multi-step implicit future preference in a self-ensembling manner, so as to implicitly mimic a user's activity planning before her next visit.

Intra-sequence Attention Aggregation. As a user usually shows a similar preference in the same temporal context (i.e. periodic property), we thus devise a temporal-aware attention to identify the most relevant behaviors within a past trajectory regarding a future temporal context. Specifically, a user's past trajectory Su i ∈ Su past has been encoded into the hidden state matrix HSu i = [h1, h2, . . . , h|Su i |] via the past preference encoder, wherein each hidden vector hi characterizes a user's spatiotemporal-aware dynamic POI preference and static activity preference. Afterwards, a future time embedding tf is used as a query vector attending to each hidden state of the past trajectory and thus the future-temporal trajectory embedding (stf i ) is represented as:

Therefore, stf i is able to indicate potential future behaviors through extracting the most relevant behavior regarding a future timestamp tf from the past trajectory Su i .

Inter-sequence Attention Aggregation. The intra-sequence attention layer emphasizes the effect of future temporal context on the relevant behaviors within a trajectory. Moreover, users' daily sequential preferences are also evolving, such as Alice's two daily trajectories in Fig. 1. We thus propose an inter-sequence attention layer to model the sequential preference evolving process across different trajectories. Consequently, after obtaining multiple future-temporal trajectory embeddings regarding tf , e.g., {stk+1 1 , . . . , stk+1 n-1 }, we use the dynamic user embedding u as the query vector to attend to relevant trajectory preference:

where βi is an attention score; htf refers to the future preference at timestamp tf . Till now, the future preference extractor achieves to infer multi-step future preferences (i.e., Hf = [htk+1 , htk+2 , . . . , htT ]) via self-ensembling, which also inherits users' past preferences.

3.4 Model Training and Complexity Analysis

We now obtain the hidden states characterizing user preference HSu n ,f = [HSu n , Hf ] via the past and current preference encoders as well as the future preference extractor, which enables CFPRec to model both left and right contexts for the target POI during training and prediction without data leakage. With the assumption that user's next movement may be affected by her multi-step future preferences in addition to past and current preferences, the final user preference (hu ) is thus formulated by aggregating each hidden state in HSu n ,f ,

where ωi is the attention score between the dynamic user embedding u and each hidden state hti . The learned user preference hu is then used to decode the probability distribution over the |L| POIs with the softmax function:

where ˆy ∈ R|L| is the predicted probability distribution regarding tk+1; andWo ∈ R5D×|L| is a transformation matrix. Hence, the objective function for the target POI prediction is:

where N is the set of training samples; and ˆ yi is the predicted probability of the ground truth POI corresponding to the i-th training sample. Finally, the overall loss is given by:

where η ∈ [0, 1] is a hyper-parameter to balance the target POI prediction and the auxiliary objective.

Algorithm 1: Training of the CFPRec

Input: U, {Su1 , Su2 , . . . , Su|U| }, max iter, η, D, T, γ Output: Trained model {Θ} 1 Initialize model parameters Θ, N = ∅; // Training instance construction 2 foreach u ∈ U do 3 foreach Su i ∈ Su do 4 Su past = {Su 1 , Su 2 , . . . , Su n-1}, Su cur = Su n 5 {Su past , Su cur} ↦→ N // Update parameters Θ 6 foreach iter ∈ {1, 2, . . . ,max iter} do 7 Select instance {Su past , Su cur} from N 8 Update Θ by minimizing the objective in Eq.(12)

Complexity Analysis. Algorithm 1 outlines the training process of the CFPRec, where we first construct training instances (lines 2-5) and then update parameters (lines 6-8). During the model training, the computational complexities of the past preference encoder, current preference encoder and future preference extractor are respectively O((n - 1) · | ¯ S|2 · D), O(| ¯ S| · D2 ) and O(D), where n is the number of sequences in a training instance; | ¯ S| is the average sequence length; D is the embedding size. Since n, | ¯ S| < D, the overall complexity of CFPRec for each training instance is around O(| ¯ S| ·D2 ). Normally, | ¯ S| < 10 and D ≤ 100, implying CFPRec is scalable to large-scale datasets.

4 Experiments

We conduct experiments to investigate the following research questions 2 . (RQ1) Does the proposed CFPRec outperform state-of-the-art baselines? (RQ2) How do different components of CFPRec affect its performance? (RQ3) How do key hyper-parameters of CFPRec affect its performance?

4.1 Experimental Setup

Datasets and Metrics. We adopt three datasets collected from Foursquare [Yang et al., 2016] in three cities, i.e., Singapore (SIN), New York City (NYC) and Phoenix (PHO), as shown in Table 1. Following [Sun et al., 2020], we remove POIs with less than 10 interactions and filter out inactive users with less than 5 trajectories and trajectories with less than 3 check-in records. We then split the trajectories of each user in the ratio of 8:1:1 based on timestamps, where the earliest 80% is regarded as training set; the second last 10% as validation set and the last 10% as test set. Finally, we employ two widely-used metrics, i.e., HitRate@K (HR@K) and NDCG@K, to evaluate the performance of all methods. Generally, higher metric values indicate better ranking performance. For a more robust comparison, we run each method 10 times, and report the averaged results as the final results.

Baselines. We compare CFPRec with eight baselines. (1) MostPop recommends POIs via popularity; (2) BPRMF is a Bayesian Personalized Ranking [Rendle et al., 2009] based matrix factorization method; (3) ST-RNN [Liu et al.,

2 Our code is available at https://github.com/wuziqi2/CFPRec

2016] is a pioneer RNN based model that incorporates spatiotermpoal contexts between successive check-ins for next POI recommendation; (4) ATST-LSTM [Huang et al., 2019] is an attention-based spatiotemporal LSTM model which focuses on the relevant historical check-ins in a trajectory; (5) MCARNN [Liao et al., 2018] is a multi-task context aware RNN based model which leverages the spatial-activity topic for the next activity and location prediction; (6) PLSPL [Wu et al., 2020] is a state-of-the-art next POI recommender which equips with two modules to capture user's past and current preference, respectively; (7) iMTL [Zhang et al., 2021] is a state-of-the-art multi-task based next POI recommender which models sequential correlations of activities and locations via a two-channel encoder; (8) CTLE [Lin et al., 2021] is a state-of-the-art contextual location embedding method which is built upon a bi-directional Transformer framework.

Parameter Settings. We empirically find out the best parameter settings for all methods. In particular, the embedding size D is searched in [20, 100] stepped by 20; the learning rate γ and regularization coefficient are searched in {0.0001, 0.001, 0.01, 0.1}. The rest parameters of each method are searched as suggested by the original papers. For CFPRec, we implement it with Pytorch, and Adam is adopted as the optimizer; D = 60/40/60 for SIN, NYC and PHO; the number of iterations are correspondingly set as 25/25/15 for SIN, NYC and PHO; γ = 0.0001; η = 1; the number of Transformer blocks is 1; the number of LSTM layers is 3/2/2 for SIN, NYC and PHO.

4.2 Results and Analysis

Comparison Results (RQ1). The performance of all methods are presented in Table 2. For the three datasets, MostPop performs the worst, which suggests the necessity of personalization in next POI recommendation. BPRMF is defeated by RNN based models as it fails to capture the sequential regularity from users' check-in behaviors. The comparisons for all the RNN based methods are discussed as follows. (1) ATST-LSTM performs better than ST-RNN which indicates that leveraging the attention mechanism in modeling sequential behaviors can enhance the quality of next POI recommendation. (2) The relative higher performance of MCARNN, iMTL, and PLSPL shows that jointly modeling users' spatiotemporal-aware activity and location preference is beneficial to capture users' preferences for their next POI visits. (3) PLSPL shows promising results which illustrates the significance of modeling past and current sequential behaviors for more accurate next POI recommendations, while ignoring to model the future preference hinders its user preference learning compared with our CFPRec. (4) Our CFPRec achieves better performance than the state-of-the-art Transformer based CTLE, which also helps verify the benefits of inferring users' future preferences in the next POI recommendation. Overall, CFPRec significantly outperforms all baselines with average lifts of 16.4% and 21.6% on HR and NDCG, respectively, where the significance is determined by a paired t-test with p < 0.01.

Ablation Study (RQ2). We explore the efficacy of different components on CFPRec by comparing with its five variants. (v1) it removes the auxiliary objective in the past preference encoder; (v2) it omits the future preference extractor; we follow [Wu et al., 2020] to characterize user preference by modeling both past and current sequential behaviors in a concatenation way; (v3) it only adopts one-step future preference at tk+1; (v4) it replaces the two-layer attention aggregation in the future preference extractor with the average pooling; and (v5) it removes both past preference encoder and future preference extractor, i.e., we only adopt LSTM to model users' sequential behaviors for recommendation. Note that we do not consider the variant omitting the past preference encoder, as it is mainly used to infer the implicit future preference with the periodic property. Our CFPRec can model multi-step future preferences. However, in this paper, we consider twostep future preferences due to the limited trajectory length.

We only report the results on NDCG@10 as shown in Fig. 3(e) due to space limitation, and similar trends can be observed on HR@10. From the results, we note that CFPRec generally achieves better performance than its variants, validating the design efficacy of different components. First, CFPRec consistently outperforms v1, implying the benefits of auxiliary objective in past user preference learning. Second, it surpasses both v2 and v5 (the worst variant), which suggests that modeling both users' past and future preference indeed boosts the performance of next POI recommendation. Meanwhile, CFPRec defeats v3 in most cases exhibits the value of multi-step future preferences. Lastly, v4 generally underperforms CFPRec showing the advantage of the two-layer attention aggregation in inferring users' future preferences.

Parameter Sensitivity Analysis (RQ3). We now examine the impacts of key parameters on CFPRec, including embedding size D, the importance of auxiliary tasks η, the number of Transformer blocks, and the number of LSTM layers. We only report the results on HR@10 as depicted in Fig. 3(ad) due to space limitation, and similar trends can be found on NDCG@10. We note that (1) as the embedding size D increases, the performance of CFPRec first climbs up, then reaches its peak, and finally keeps stable or slightly drops on all datasets; (2) the performance of CFPRec gradually improves with the increasing of η on all datasets, and the best setting is 1; (3) the best performance of CFPRec is achieved with only one block on all datasets, indicating more blocks may not guarantee a better result; and (4) similar performance variation regarding the number of LSTM layers on all datasets is observed as for the embedding size D.

5 Conclusion

In this paper, we propose a novel method, CFPRec, to jointly model users' past, current and future preferences for next POI recommendation. Specifically, we design the past preference encoder to model users' past preferences via a Transformer layer, which further employs three auxiliary objectives to help supervise the user preference learning from past trajectories. The current preference encoder then aims to model users' latest sequential behaviors by an LSTM layer. Lastly, a future preference extractor is devised by equipping with a two-layer attention aggregation to infer multi-step future preferences. Experimental results on three real-world datasets demonstrate the superiority of CFPRec against state-of-the-art baselines.

Acknowledgments

This research is supported by the MOE AcRF Tier 1 funding (RG90/20) awarded to Dr. Jie Zhang, and is also partially supported by the Centre for Frontier AI Research and the Institute of High Performance Computing, A*STAR.