MFNP: A Meta-optimized Model for Few-shot Next POI Recommendation

1 Introduction

POI recommendation has become an important sub-field of recommender system [Feng et al., 2015; Liu et al., 2016]. As a natural extension of general POI recommendation, next POI recommendation [Cheng et al., 2013] aims to predict which POI in a target region a user will go next. Compared with the general POI recommendation, next POI recommendation focuses more on exploiting sequential patterns hidden in the check-in sequence to fulfil users' current demands.

In the literature, existing methods adopt sequential analysis models like improved RNN [Feng et al., 2018], LSTM [Zhao et al., 2020], and GRU [Manotumruksa et al., 2018] to capture dynamic user preferences for Next POI recommendation. However, the check-in records of users may be sparse and insufficient to support effective model training, which impedes effective recommendation of above methods for cold-start users [Luo et al., 2020]. To help them identify potentially interested POIs, some approaches solve the sparsity problem of cold-start user by utilizing auxiliary information, such as geographical influence [Chang et al., 2018], cross-domain interactions [Zhang et al., 2020] and social correlations [Cho et al., 2011]. However, these approaches may recommend the same POIs for users with similar context, and neglect users' real interests accordingly. It thus calls for few-shot models that can fully capture the preferences of cold-start users.

∗Corresponding author

Inspired by recent advances of meta-learning in few-shot learning, some studies [Lee et al., 2019; Dong et al., 2020] are proposed to adopt it to solve the cold start problem in general recommendation. Meta-learning learns the experience between similar tasks for quick adaptation to new tasks with only a few training data. The recommendation for each user is usually regarded as a learning task, and a global parameter with strong generalization ability is learned to guide model parameter initialization of each task. The initialized parameters are then turned by target user's check-in data until task-specific parameters are derived for personalized recommendation. In this way, the preferences of coldstart users can be effectively modelled through the experience of modelling preferences of users in warm state. Since meta-learning has been proven to be successful for general recommendation in cold-start scenarios [Bharadhwaj, 2019; Lu et al., 2020], it is a great opportunity for few-shot next POI recommendation.

Different from general recommendation, next POI recommendation requires considering the phenomenon of user interest drift [Yin et al., 2016], since a user may have different preferences in different regions. Existing meta-learning based methods derive personal preferences through user-specific setting [Lee et al., 2019; Dong et al., 2020], which neglect the above phenomenon. Unfortunately, modelling personal preferences in region granularity faces severe data sparsity problem. To alleviate this sparsity problem, crowd preferences hidden in all check-ins in this region can be integrated. Since similar users always follow similar behaviour patterns, the crowd preferences should be obtained from similar users, instead of all users to avoid divergence. Besides, it is also challenging to design meta-learning tasks that can accurately model region-dependent user preferences by transferring the knowledge of user and crowd preferences via adaptive fusion.

In this paper, we investigate few-shot next POI recommendation while considering the phenomenon of user interest drift, and propose a Meta-optimized model for Few-shot Next POI recommendation (MFNP in short). In MFNP, we build a meta-learner for each user to provide a personalized model, based on their own check-in records. Aside from user-specific tasks, our model also consists of region-specific tasks to capture region-dependent crowd preferences for the target region. To better transfer shared preferences across similar users, we group all users by clustering first and adopt an adaptive network to balance the importance of crowd preferences of different user groups. At last, to address data sparsity, a fusion method is proposed to adaptively fuse personal preferences and region-dependent crowd preferences, such that regiondependent user preferences can be modelled via knowledge transfer. The main contributions of this work are as follows:

• We propose a novel meta-optimized model, which is the first to utilize meta-learning for few-shot next POI recommendation. By considering user interest drift, it integrates carefully designed user-specific and regionspecific tasks, such that region-level user preferences can be captured by the transferred knowledge of personal and crowd preferences via adaptive fusion.
• We propose a cluster-based adaptive network to model more meaningful region-dependent crowd preferences. By merging different types of crowd patterns on clustered users, it ensures shared preferences to be shared among similar users, thus avoids the divergence among different types of users.
• Experimental results on two real datasets show that our model outperforms state-of-the-art methods on next POI recommendation for cold-start users.

2 RelatedWork

2.1 Next POI Recommendation

Researches on the next-POI recommendation aim to exploit sequential patterns of users. Some early works [Cheng et al., 2013] utilize personalized Markov chains to capture the sequential correlation between POIs. Recently, some efforts take advantage of sequential deep neural models, and design customized gates in the RNN [Liu et al., 2016; Feng et al., 2018], LSTM [Sun et al., 2020] and GRU [Manotumruksa et al., 2018] to make full use of spatio-temporal information. For example, Time-LSTM [Zhu et al., 2017] designs a temporal gate for integrating temporal contexts, and an additional spatial gate is been equipped in STGCN [Zhao et al., 2020] to learn from spatial contexts. Since users must physically visit POIs in the real world, most models are suffered from the sparse data of users' check-ins [Feng et al., 2018]. To help cold-start users identify potentially interested POIs, some approaches utilize auxiliary information. Some works try to combine the social influence [Cho et al., 2011] or contextual influence [He et al., 2016] with human mobility patterns.

However, these approaches may recommend the same POIs for users with similar content and neglect users' real interests. Few-shot learning models are thus needed to fully capture the preferences of cold-start users.

2.2 Meta-learning for Cold-start Recommendation

As meta-learning has proven to be successful in the few-shot learning field, recent works introduce it into the recommender system to overcome the cold-start problem. Following the settings of few-shot learning, the early works [Li et al., 2019] regard recommendation for each user as a task, and learn from few user-item interactions and user profiles. They mainly adopt an optimization-based meta-learning approach such as model-agnostic meta-learning for model training. Moreover, these methods are designed for the general recommendation along with abundant auxiliary information (e.g. user profiles, item attributes). MeLU [Lee et al., 2019] identifies reliable evidence candidates based on the users' profile and the attributes of items. Also relying on the auxiliary information of users and items, MAMO [Dong et al., 2020] extends two designed memory matrices to provide personalized initialization for each user.

However, the above methods neglect user interest drift and fail to model user preference in region granularity. To this end, this paper proposes a novel meta-optimized approach to effectively model region-dependent user preferences for fewshot next POI recommendation.

3 Definition

Let U={u1, u2, ..., un} denotes a set of users and V={v1, v2, ..., vn} be a set of POIs. Follow the work in [Yin et al., 2016], we use K-means to cluster all the POIs into several regions according to the geographic distances, where regions can be denoted as R={r1, r2, ..., rn}. For each POI vi, we use li to denote its corresponding geographical attribute in terms of longitude and latitude coordinates, and ri to denote its region for each POI vi (vi ∈ V ).

Definition of check-in sequence. A user u's check-in sequence is represented by an ordered list: S(u) = {v1, v2, ..., vj , vk, ..., v|Su|}, v|Su| denotes the current POI. In this list, j < k indicates that behavior vj is occurred before vk .

Definition of region's trajectory set. We define user u's check-ins in a region r as a trajectory: s(u)r = {v1, v2, ..., vi, ..., v|su|}, where each POI vi is located in r. A region r's trajectory set is represented by a set: sr = {s(u1), s(u2), ..., s(uj), .., s(u|sr|)}, which is collected from all the trajectories that occured in r. |sr| denotes the number of visitors who visited region r.

Problem Formalization. Given a user u ∈ U and a set of POIs V , with the user's historical check-in sequence Su = {v1, v2, vt-1} where vt-1 is the most recent POI that u has visited, next POI recommendation aims to recommend the top-k POIs that user u may be interested at a future time t.

4 Our Model

In this section, we propose a meta-optimization framework MFNP to support accurate next POI recommendation for cold-start users. Figure 1 shows the architecture of the model. We introduce the recommender model and meta-optimization learner in sections 4.1 and 4.2 respectively.

4.1 Recommender Model

The proposed base model for recommending the next POI contains three modules: a user-specific module to capture personal preferences in a region-dependent way from users' personal check-in sequences; a region-specific module to capture the similar users' region-dependent crowd preferences in the same region; a prediction module to infer the interested POIs for users.

User-specific Preference Modelling

Inspired by previous solutions [Lee et al., 2019; Li et al., 2019], we first regard the recommendation for each user as a learning task to capture their region-independent personal preferences by using their own check-in data without considering the specific region.

Understanding users' instant demands and modelling their short-term preferences play an important role in the next POI recommendation. We represent users' personal preferences with sequential models to explore their behaviour patterns from their complete check-in sequences. Given the check-in sequence Su of user u, we first learn the temporal dependencies by a standard LSTM:

where ht-1 and ht-2 is the hidden state of LSTM at t - 1 and t - 2 respectively, xt-1 is the embedding vector for POI vt-1 ∈ Su.

Since RNN-based methods merely follow the temporal order, they can not capture the spatial dependencies from the visited POIs which are geographically scattered in the real world. Therefore, we apply the geo-dilated LSTM scheme [Sun et al., 2020] to explore the geographical relations among non-consecutive POIs. The geo-dilated LSTM

picks POIs from the check-in sequences as the input with different skip lengths, which determined by the geographical relevance. For example, given a check-in sequence Sn = {v1, v2, v3, v4, v5}, v3 has two preceding POIs in the temporal sequence: v1 and v2. Since the geographical distance between v1 and v3 is shorter than the distance between v1 and v2, there exists a geo-dilated sequences {v1, v3}. After finding the path from v1 to v5, we can construct the input set Sgeo n = {{v1, v3}, {v3, v5}}. Then the preferences of users which conclude the spatial dependencies can be learned by the dilated LSTM scheme with the input Sgeo n :

where δ is the skip length which will be automatically determined on geographical factors, h′t-δ is computed from the last sequence {xδ, xt-1} ∈ Sgeo n .

At time t - 1, the final representation of user's regionindependent preference is an average of the latent representations ht-1 and h′t-1 :

Region-specific Preference Modelling

Different from the general recommendation, users' preferences may be region-varying in the POI recommendation. However, due to the sparse check-in data, it is impossible for us to model users' region-dependent preferences in each region separately. With the rapid development of social media and the Internet, people are more easily influenced by others' successful experiences, resulting in that similar users may follow a similar behaviour pattern [Yin et al., 2016]. This allows us to model region-dependent crowd preferences from similar people in the same region.

To achieve this, we propose a cluster-based adaptive network to locate the user group where the user belongs to, so that region-dependent crowd preferences can be modelled more accurately. Specifically, we cluster users into different user groups based on the representation P t-1 u obtained by Eq.(3) by HDBSCAN algorithm [McInnes et al., 2017]:

where cu is the user group of u.

Given the region r where the recent POI vt-1 is located in, we can filter the trajectories which are generated by users who belong to cu. All trajectories are sorted in temporal order sr = {s1, s2, ..., sm, ...sn}. The information of all POIs in each trajectory sm is encoded by a LSTM layer:

where ht-1 is the hidden state of LSTM, xt is the embedding vector for t-th POI vt ∈ sm.

Following [Sun et al., 2020], we have to incorporate the temporal and spatial factors with users' personal trajectories instead of a naive combination of all the corresponding trajectories. This is due to the fact that the popularity of POIs among the crowd is changing over time. For example, people may choose fast food on weekdays at lunchtime and seek for cinema on weekends night. Meanwhile, the crowd checkin sequence which is closer to the user's current geographic location may be more referential.

Therefore, we first apply a time-weighted operation to incorporate such information to capture the time-sensitive property. We map one week into 48 time slots (24 slots for hours on weekdays and 24 slots for hours on weekends). For each slot o, we construct a POI set Go = {v1, v2, ..., v|Go|}, where v ∈ V is a POI visited by at least one user in time slot o. We calculate the temporal similarity τi,j between the i - th and j - th time slots by Jaccard index:

Then, we can derive a sequence of trajectory time slots according to the check-in time of all the POIs in sm. The time slots sequences can be represented as {p1, p2, ...p|sm|}, where p ∈ {1, 2, ..., 48}. Given the target user's current time slot o, the sequence-level representation sm for sm is generated as follows:

where τo,pt is the temporal similarity between the current time slot o and the time slot of the j-th visited POI in sm. Besides, we use the similar way to generate the sequence-level representation Su for Su, while the time-weighted operation is replaced by an average pooling.

After learning the representations {s1, s2, ..., sn} for all trajectories in sr = {s1, s2, ..., sn}, we can derive regiondependent crowd preference pru with respect to the user's personal trajectory Su using a geo-nonlocal operation to integrate spatial factors:

Algorithm 1 The training process of MFNP

Input: The meta training user set Utrain and their check-in sequences

Output:Meta parameters φu, φg , φr

• 1: Randomly initial the meta parameters φu, φg, φr
• 2: Randomly initial user clusters c
• 3: while not done do
• 4: for u ∈ Utrain do
• 5: Initial the global parameter θu, θg, θr
• 6: Calculate user preferences pt-1 u by Eq.(1-3)
• 7: Locate the user group cu of u by Eq.(4)
• 8: Calculate crowd preferences pru by Eq.(5-10)
• 9: Get prediction ˆy by Eq.(11)
• 10: Local update θu, θg, θr by Eq.(12)
• 11: end for
• 12: Update the global parameter φu, φg, φr by Eq.(13)
• 13: Update the clusters c of users by HDBSCAN
• 14: end while

where C(S) = ∑|sr | m exp ( 1 du,m S⊤u sm) is the normalization factor by taking the user's most recently visited location into account. du,m is the geographical distance between the location lt-1 of the current POI vt-1 and the location lsm of trajectory sm, where lsm is defined via the average pooling operation for all the visited POIs in the trajectory sm. The pairwise function f (·) calculates an affinity score between the user's personal trajectory Su and the region-based trajectories sm, and g(·) generates the representation for sm. Specifically, in our solution, f (Su, sm) and g (sm) are defined as:

where Su and sm are the representations of user's personal check-in sequence Su and region-based trajectory sm, respectively, while Wr is a trainable projection weight matrix.

Prediction

After obtaining the representations of both personal preferences pt-1 u and region-dependent crowd preferences pru , we compute the probability distribution ˆy over all POIs in |V | as:

where ⊕ is the concatenation operation of personal preferences and region-dependent crowd preferences, Wp is a trainable projection matrix for all POIs. Consequently, the POI most likely to be visited by the target user at the next time step t is the one with the largest probability.

4.2 Meta-optimized Framework

Inspired by recent advances of meta-training [Li et al., 2019; Dong et al., 2020], we adopt the MAML-based model to optimize the user-specific and region-specific module. Algorithm1 shows the detailed training process of MFNP.

Local Update

At the beginning of the training process, we randomly initialize the global parameters. For each user, we have a support set and a query set. During the local update phase (i.e. learning on the support set), we first initialize the local recommender parameters θu, θg, θr as the meta parameters φu, φg, φr, where θu, θg, θr represent the parameters of the user-specific preference module, region-specific preferences module and the prediction module, respectively. Calculated by Eq.(1-3), we can obtain region-independent personal preferences. After locating the corresponding user group, we calculate the region-dependent crowd preferences by Eq.(5-10). The prediction is calculated through the above two preferences by Eq.(11). The optimization goal of local training is to minimize the loss of the recommendation for a single user, the parameters can be locally updated as follows:

Global Update

The aim of the meta optimization is to minimize the expected loss on the query set. After the local training on the support set, we update the global parameters according to the loss on query sets. Suppose the recommender model is denoted as Rˆ θ∗ , where θ = {θu, θg, θr}. After the local training on support set, we get the model Rˆ θ∗ with updated parameter ˆ θ. Our goal is minimizing the training loss for users u ∈ Utrain on query sets for q ∈ Q. Then, the global parameters are updated by:

5 Experiment

5.1 Dataset

We conduct experiments on two public LBSNs datasets, namely Foursquare [Yang et al., 2015] and Gowalla [Yin et al., 2013]. The statistics of both datasets are shown in Table 1. The Foursquare dataset contains the POI check-in records created by users living in New York from February 2009 to October 2010, while Gowalla contains worldwide check-ins from February 2009 to October 2010. For both datasets, we eliminate unpopular POIs that are visited by less than 10 users and trim the number of check-in records for each user as with 10 records to force the model to learn from few samples. Each user is regarded as a sample in the dataset. We randomly separate the users into training and testing users with a ratio of 80:20.

Especially, for all the meta-optimized methods, the checkin sequence of a single user are further divided into support set and query set by employing the data augmentation strategy (e.g., a sequence {v0, v1, v2, v3} can be divided into two new successive sequences: {v0, v1, v2} as the support set and {v0, v1, v2, v3} as the query set).

5.2 ComparedMethods and Settings

We adopt the following baselines for recommender systems, where MeLU and MAMO are based on meta-optimization for general recommendation, and the other methods are sequential-based model for next POI recommendation.

• MeLU [Lee et al., 2019] obtains auxiliary information from the user profile and item attributes and optimized the recommender model which composed of a fully connected layer as meta-learning.
• MAMO [Dong et al., 2020] extends the MeLU with two designed memories to provide personalized initialization for each user.
• STRNN [Liu et al., 2016] applies time-specific transition matrices and distance-specific transition matrices in RNN to integrate spatial and temporal contexts.
• T-LSTM [Zhu et al., 2017] equips time gates with LSTM for modelling the temporal interval between check-ins from users' sequential actions.
• STGCN [Zhao et al., 2020] extends a spatial gate on the T-LSTM network architecture to model spatial intervals between check-ins for the next POI recommendation.
• LSTPM [Sun et al., 2020] develops a context-aware non-local network to model long-term preferences and a geo-dilated LSTM to model short-term preferences, which considers both spatial and temporal factors.

Following the work in [Feng et al., 2018], we set the dimension of embeddings and the hidden states to 500 for all deep learning-based methods. The K of region clusters is set to 30, while the number of cluster of users is set to 6. All the parameters in our model are optimized using the gradient descent optimization algorithm Adam with the batch size of 1 and the learning rate of 0.0001.

5.3 Evaluation

To evaluate the performance of each method, we adopt two evaluation metrics Accuracy (Acc@K) and Normalized Discounted Cumulative Gain (NDCG@K). Acc@K measures whether the ground truth existed in the top-K list, and NDCG@K measures whether the ground truth is in a front position. In this paper, we choose the popular K = {1, 5, 10} for evaluation.

5.4 Performance

Firstly, although MeLU and MAMO can learn from few training samples, they still perform worse than other sequential models, due to the lack of sufficient auxiliary information in the next POI recommendation. Secondly, both LSTPM and STGCN are superior to other methods, since they both adaptively model the preferences of users according to the current states of users. At last, our proposed model significantly outperforms all the baseline methods on both datasets in terms of the Acc@K and NDCG@K metric. It indicates the effectiveness of the MFNP model, due to the way of building meta-learners on both user-specific tasks and region-specific tasks. It demonstrates that our model can explore the preferences of the other users and adapt them to the cold-start users. Moreover, the performance of Foursquare performs better than Gowalla. That is because the users' check-in in Gowalla is sparser than those in Foursquare. The performance of our model further verifies that our work can do well under the scenario of data sparsity in the next POI recommendation.

Effectiveness of Region-specific Preference

To verify whether the region-specific module and the corresponding operation is necessary for MFNP, we conduct the experiment on two variants of our MFNP model.

• MFNP-User This version removes the whole regionspecific preference module and only capture users' region-independent preferences from the check-in sequence of themselves.
• MFNP-Crowd This version applies the average operation instead of the adaptive method for considering the spatial and temporal factors when combining regiondependent crowd preferences.

As shown in Table 3, we can observe that MFNP-Crowd always perform better than MFNP-User, showing that regiondependent crowd preferences are effective for the next POI recommendation for cold-start users. Since MFNP is always significantly better than MFNP-Crowd, we can draw the conclusion that considering region-dependent crowd preferences of similar users with spatial and temporal factors are helpful for providing personalized region-dependent crowd preferences for users.

Impact of the Number of User Clusters

The performance of MFNP maybe highly sensitive to the number of user clusters. To investigate whether the performance of our model is sensitive to the number of user clusters and explore the optimal parameters, we test the performance of MRNP by varying the number of user types and regions. As shown in Figure 2, we can observe that the accuracy of the next POI recommendation first increases and then decrease and then becomes stable as the number of user clusters gradually increases. The optimal parameter setting of the number of clusters is C=6 for Foursquare and Gowalla.

6 Conclusion

In this paper, we investigate few-shot next POI recommendation while considering the phenomenon of user interest drift. We build a meta-learner for each user to provide a personalized model according to their own check-in records. In addition, we propose a region-specific preference module to capture region-dependent crowd preferences of similar users in the same region with the target user. An adaptive method is proposed to combine these preferences with spatial and temporal factors. Experimental results on real datasets demonstrate the effectiveness of our model, which can significantly improve the performance of recommending the next POI for cold-start users.

Acknowledgements

This work is supported by the NSFC projects under grant number (61872258, 61876117, 61772356, 61972069, 61836007, 61832017, 62072125), the major project of natural science research in Universities of Jiangsu Province under grant number 20KJA520005 and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.