Personalized Ranking Metric Embedding for Next New POI Recommendation

1 Introduction

With the increasing popularity of location-based social networks (LBSNs), users would like to share their locations by checking-in points-of-interest (POIs). The large amount of check-in data offers opportunity to better understand users' mobility behavior, based on which recommending POIs will become valuable. POI recommendation is of great value to help users explore their surroundings. Importance of POI recommendation has attracted a significant amount of research interest on developing recommendation techniques [Cho et al., 2011; Ye et al., 2011; Cheng et al., 2012; Yuan et al., 2013; Lian et al., 2014; Li et al., 2015].

Compared to the POI recommendation, the next POI recommendation [Cheng et al., 2013] has received relatively little research attention. Besides users' preference, the next POI recommendation additionally considers the sequential information of users' check-ins. The sequential behavior is important for POI recommendation because human movement exhibits sequential patterns [Ye et al., 2013]. We verify users' sequential behavior in the analysis of two real-world datasets. Meanwhile, we observe that users often visit new POIs that they have not been visited before. In this paper, we focus on the Next New POI recommendation problem (simplified as N 2 -POI recommendation), which is to recommend new POIs to be visited next given a user's current location.

The challenge of N 2 -POI recommendation is to learn transitions of users' check-ins that are commonly represented by a first-order Markov chain model. Due to the sparse transition data, it is difficult to estimate the transition probability in Markov chain, especially for the unobserved transition. Factorized Personalized Markov Chain (FPMC) [Rendle et al., 2010] method has been used to calculate the item transitions. FPMC exploits matrix factorization technique to factorize the Markov transition matrix. To model the transition, FPMC represents each item with two independent vectors. However, these two vectors are related to the same item and their latent relationship is not exploited (more details in Section 2). Consequently, this technique is not sufficiently effective to learn the item transitions.

By projecting every POI into one object in a lowdimensional Euclidean latent space, we use the Metric Embedding algorithm to effectively compute the location transition in a Markov chain model. Intuitively, the distance of two objects measures the strength of their sequential relation. We further propose a pair-wise ranking Metric Embedding algorithm that ranks potential POIs in a latent space. Subsequently, we develop a Personalized Ranking Metric Embedding model (PRME), which jointly models the sequential information and individual preference. Since users incline to visit the POIs close to their current positions, geographical influence is important for the recommendation task. We extend the PRME model to accommodate geographical influence in the N 2 -POI recommendation. We summarize the main contributions of this paper as follows.

• We develop a pair-wise Metric Embedding algorithm to model the sequential transition of POIs. To the best of

• our knowledge, this is the first work that uses the Metric Embedding method for the POI recommendation.
• To model the personalized sequential information, we propose a novel PRME algorithm , which jointly considers sequential transition and user preference. We further develop a PRME-G algorithm to incorporate geographical influence for the N 2 -POI recommendation problem.
• We conduct comprehensive experiments by comparing our algorithms with the state-of-the-art techniques over two real-world datasets.

2 RelatedWork

Location recommendation has attracted intensive research attention recently. Most of previous methods are based on Collaborative Filtering (CF) technique. One of the most popular CF algorithms is the user-based CF [Ye et al., 2011; Yuan et al., 2013; Chen et al., 2015], which takes advantage of checkins of similar users for the recommendation purpose. Another CF method is Matrix Factorization [Cheng et al., 2012; Lian et al., 2014], which learns the general taste of a user by factorizing the observed user-item preference matrix. The CF based algorithms mainly exploit the user preference to make recommendations. Currently, geographical influence has been fused with the CF algorithms to enhance POI recommendation. For example, Gaussian Mixture distribution[Cho et al., 2011; Cheng et al., 2012] and power law distribution [Ye et al., 2011; Yuan et al., 2013] have been proposed to model the geographical influence.

Sequential influence has been considered for the POI recommendation. Most of the studies utilize the Markov chain property to predict the next check-ins. Zhang et al. [Zhang et al., 2014] predict the sequential probability through an additive Markov chain. However, this method fails to assign the transition probability for the unobserved data because it directly constructs the Markov chain model based on check-in data. Instead of using transition pattern of POIs, [Liu et al., 2013; Ye et al., 2013] exploit the transition pattern of POI categories to predict future check-ins. However, the accuracy of these methods highly depends on the category information.

FPMC [Rendle et al., 2010] is the state-of-the-art personalized Markov chain algorithm. To model the Markov chain transition, FPMC associates each item l with two independent vectors: ⃗ Fl to embody the transition to other items, and ⃗ Tl to represent getting transition from other items. The transition from item li to another item lj is embodied as the inner product of the latent vectors ⃗ Fli · ⃗ Tlj . However, FPMC fails to model relations among multiple items. For example, given li → lj and lj → lk, transition li → lk is expected to have a high probability because both li and lk have close relations with lj . However, FPMC fails to reflect such relationship due to the independent assumption on ⃗ Flj and ⃗ Tlj . This drawback limits its performance.

The work by Cheng et al. [Cheng et al., 2013] is most related to ours. The research aims to recommend POIs for the next hours by merging consecutive check-ins in the previous hours. It employs FPMC to model the personalized POI transition. Based on the current POI, their method only considers the POIs in the defined region as candidates. Lian et al. [Lian et al., 2013] also adopts FPMC to represent the short-term and long-term preference to predict the next check-in. Differently from these studies, we propose a metric embedding model to learn the personalized sequential information.

Embedding items in a low-dimension Euclidean space is mainly used for the purpose of visualization and exploratory data analysis [Roweis and Saul, 2000; Hinton and Roweis, 2002]. Recently Metric Embedding is adopted in the music playlist prediction. Chen et al. [Chen et al., 2012; 2013] propose a Logistic Markov embedding (LME) for generating the playlists. LME maps each song to one point (or multiple points) in a latent Euclidean space. The transition probability from one song to another is related to the Euclidean distance of the two songs in the latent space. The research [Wu et al., 2013; Moore et al., 2013] embeds users and songs into a common latent space to represent the personalized Markov Chain. Our work differs from the aforementioned studies in that we exploit pair-wise ranking scheme to learn the parameters, and adapt Metric Embedding for the POI recommendation task by incorporating multiple factors.

3 Next New POI Recommendation

We use two publicly available datasets. The first dataset is the FourSquare check-ins within Singapore [Yuan et al., 2013] while the second one is the Gowalla check-ins dataset within California and Nevada [Cho et al., 2011]. We use one-year data in both datasets. Each check-in is a tuple in the form of < user, POI, time >. Each POI is associated with the latitude and longitude. We remove users who have check-in fewer than 10 POIs, and POIs which have been visited by fewer than 10 users. The basic statistics of datasets used in this paper are summarized in Table 1.

3.1 Observations on real-world datasets

Observation 1: exploration of new locations

Figure 1 shows the average ratio of new POIs over all users on two datasets for every 50 days. For example, the ratio at the 100th day is the proportion of POIs visited at the 100th day that have not been visited in the previous days. The ratio of new POIs is pretty high (most of the ratios above 0.4) on both datasets, which implies that people always like to explore new POIs. This observation is in accordance with the recent findings [Lian et al., 2013].

Observation 2: temporal influence

Figure 2(a) shows the cumulative distribution function (CDF) of the time difference of two sequential check-ins. Figure 2(a) demonstrates that more than 50% successive check-ins occur in less than 24 hours. Meanwhile, many consecutive checkins occur in a longer time. For more than 25% consecutive check-ins, their time differences are larger than 48 hours.

Observation 3: spatial influence

We compute the geographical distance of two consecutive check-ins and plot the CDF distribution in Figure 2(b), which shows that 70% consecutive check-ins have less than 10km in both datasets. The CDF curve increases fast when distance is small, which implies that most check-ins occur in nearby areas. This result indicates that users' next movements are influenced by their current locations. The finding is in accordance with the reported result [Yuan et al., 2013; Cheng et al., 2013].

3.2 Next new POI problem definition

When two check-ins occur in a short time period, markov chain property exists [Cheng et al., 2013]. This motivates us to consider the POI transition within a short period, which means the next POI is influenced by current POI. Following [Zhang et al., 2014], if the time difference of two consecutive check-ins is smaller than τ, sequential influence shall be considered. Here τ is the time threshold. In Section 6, we investigate the impact of τ. Meanwhile, according to observation 1, users incline to visit new POIs for their exploration interests, indicating that the problem of suggesting new POIs for users is meaningful.

Based on the sequential property within a short time period and users' willingness of new POIs, we formally define the N 2 -POI recommendation problem below.

Definition 1 (N 2 -POI Recommendation Problem ) For a set of users U and a set of POIs L, C is the historical check-in data, and Lu is the set of POIs that user u has visited before. Given current POI lc of user u, the N 2 -POI problem is to recommend a set of POIs S u,lc ⊂ L for the user u to visit next and the POIs are new to the user

Note that in the N 2 -POI recommendation problem we only recommend new POIs to users. In contrast, a next POI prediction task outputs both the visited and un-visited POIs as the results. As reported in [Lian et al., 2013], if we only use the frequently visited POIs of a user to predict his next POIs, a high prediction precision can be achieved. In addition, it's challenging to estimate the implicit transition probability of potential new POIs based on the sparse historical data. Thus, the N 2 -POI recommendation problem is harder than the next POI prediction problem.

4 Personalized RankingMetric Embedding

We first introduce Metric Embedding algorithm with Pairwise Ranking to model location transitions in Section 4.1. The Personalized Ranking Metric Embedding (PRME) is then presented in Section 4.2. Section 4.3 states PRME-G model, which jointly incorporates sequential transition, user preference, and geographical influence.

4.1 Pairwise RankingMetric Embedding

Embedding POIs in latent space

To model the sequential information, we need learn the transition probability in a Markov chain model. However, due to the data sparsity, it is infeasible to estimate the transitions by using standard counting methods. Metric embedding model can be used to handle the data sparsity and be generalized to the unobserved data. We represent each POI as one point in a latent space. We assume that Euclidean distance between POIs in the latent space reflects the transition probability. The larger the distance, the lower the strength of transitions. With all POIs embedded in a latent space, our model estimates the sensible transition probabilities of POIs. It is also possible to assign meaningful probabilities to those unobserved transitions.

In the Metric Embedding model, each POI l has a position X(l) in a K-dimensional space. Given the observed sequential POI transitions, the goal is to learn the positions of all POIs. We relate the transition probability of a pair, li and lj, to the Euclidean distance as defined in Eq. 1.

where ||X(li) - X(lj)||2 = ∑Kk=1 (Xk(li) - Xk(lj))2 , K is the number of dimensions of the latent space and Z(li) = ∑|L| n=1 e-||X(ln)-X(li)||2 is the normalization term.

Compared to matrix factorization in FPMC, Metric Embedding (ME) can better model the sequential transition. It represents each item as a single point in a latent space rather than two independent vectors. This representation is more natural to embody the latent relations of items. For example, given observed transition li → lj and lj → lk, li → lk is expected to be a potential transition. ME is able to capture this kind of relation. ||X(li) -X(lk)||2 would be small, because both X(li) and X(lk) will be pulled closely to a same position X(lj ).

Ranking based metric embedding

Eq. 1 only exploits the observed check-ins to learn the latent position of each POI. Since the observed data is very sparse, we learn the latent position by fitting the rankings for the POI transition. Consequently, we can additionally make use of the unobserved data to learn the parameters. We utilize POI pairs as training data and optimally estimate the pair-wise ranking. We assume that the observed next POI is more related to current POI than the unobserved POI. For example, if transition lc → li is observed and lc → lj is not observed, POI li should be ranked higher than POI lj . We model it as a ranking > over POIs:

The goal of POI recommendation is to provide a ranking of all the items, and accordingly recommend the top items. Furthermore, since we are interested in the ranking of POIs, we can simplify the computation by only keeping the Euclidean distance ||(X(li) -X(lj)||2 in the latent space (abbreviated as Dli,lj ). Instead of utilizing the exponential function, we use the Euclidean distance to rank the POIs.

4.2 Personalized RankingMetric Embedding

Individual preference has been proved to be an important factor for the POI recommendation because each user would prefer some favorite POIs. Given current location lc of user u, the recommended N 2 -POI shall not only be related to lc , but also capture user's preference.

We use ME to model the user-item preference. We project each POI and each user into a latent space. The distance between a user and a POI reflects the strength of their relations. Intuitively, if user u likes POI l, the distance ||X(u)-X(l)||2 in latent space should be small. Otherwise, ||X(u) -X(l)||2 would be large. By doing this, we model the user-item preference in a latent low-dimension space.

Since RME exploits transition data of all users, it does not reflect the user-specific transition. We further develop a Personalized Ranking Metric Embedding (PRME) method, which considers sequential information and individual preference together. We utilize two latent spaces: one is the sequential transition space and the other is the user preference space. Each POI l has one latent position XS (l) in the sequential transition space, and the Euclidean distance of two POIs li and lj is defined as DS li,lj = ||XS (li) -XS (lj)||2 . In the user preference space, each user u has a latent position XP (u) and each POI l has a latent position XP (l). DP u,l = ||XP (u) - XP (l)||2 denotes the Euclidean distance of user u and POI l in the user preference space.

Given current location lc of user u, we model personalized sequential transition for a candidate POI l by combining the two kinds of metric. As two components contribute differently into the metric score of POI l, we use a linear interpolation to weight the two metrics.

where α ∈ [0, 1] controls the weight of different kinds of distance.

Based on observation 2 (in Section 3.1), some successive check-ins have large time difference, which may indicate their irrelevance. We assume that if the time interval between two adjacent check-ins is larger than threshold τ, only the user preference is considered. We then recompute the distance metric Du,l,lc below.

where ∆(l, lc ) is the time difference of two successive checkins l and lc .

4.3 Incorporating Geographical Influence

As stated in Section 3.1, given current location, users would like to visit the near POIs rather than the far way POIs. Geographical distance affects users' visiting behavior. Thus we propose the PRME-G model to incorporate the geographical influence into the PRME model.

We accommodate the geographical influence by using the weight of the geographical distance. For any pair of POIs, we can calculate the geographical distance via their longitude and latitude. Given the geographical distance dlc ,l, we use a weight function wlc ,l. In this paper, wlc ,l = (1 + dlc ,l)0.25 . The fused distance metric becomes Du,lc ,l · wlc ,l. When the distance of a POI is large, the fused metric would be large, and thus this POI is less likely to be recommended. The integrated metric with geographical influence is defined as below.

Note that the PRME-G model is not special for N 2 -POI recommendation and is general for solving next POI prediction problem. We do not show the improvement for predicting next POI due to the limited space.

5 Parameter Learning

5.1 Optimization Criterion

Assuming that users' check-ins are independent with each other, we can derive the optimization criterion of PRME model. Analogous to Bayesian Personalized Ranking (BPR) approach [Rendle et al., 2009], we estimate the PRME model by using maximum a posterior (MAP):

where Θ = {XS (L), XP (L), XP (U)} is the set of parameters.

Using logistic function σ(z) = 1 1+e-z , ranking probability can be further written as

With Gaussian priors on the parameters, we have the final objective function in Eq. 9, where λ is a parameter controlling the regularization term.

5.2 Learning Algorithm

Directly solving Eq. 9 is time consuming. Following the approach of BPR, we independently draw the training tuple and utilize Stochastic Gradient Descent to update the parameters. Based on the historical check-in data, we can obtain a set of observations {< u, lc , li >}, where lc is the current location of user u and li is the next check-in. For each observation, we randomly generate a POI lj, which is not observed given u and lc . Given a training tuple < u, lc , li, lj >, the update procedure is described as below:

where z = Du,lc ,lj -Du,lc ,li , and γ is the learning rate.

The learning algorithm of PRME is summarized in Algorithm 1. First, we initialize all the parameters with a Normal distribution (Line 1). For each observation < u, lc , li >, we randomly generate a POI lj that user u has not visited after lc . We then calculate the time difference ∆(lc , li) to determine whether it is related to lc . If ∆(lc , li) < τ, latent positions in both user preference latent space (Line 6) and sequential transition space (Line 7) are updated. If ∆(lc , li) ≥ τ , only user preference is considered (Line 9). Note that all the update procedures (Lines 6,7,9) are based on Eq. 10. For PRME-G model, we utilize DG u,lc ,l in Eq. 9 as the optimization criterion and use the similar procedure to learn parameters.

The time complexity of the algorithm is O(IK|C|), where I is the number of iterations, K is the number of dimensions and |C| is the number of observed check-ins in the dataset.

Algorithm 1: PRME

input : check-in data C, learning rate γ, regularization λ, component weight α, time threshold τ output: model parameters Θ = {XS (L), XP (L), XP (U)} 1 Initialize Θwith Normal distribution N(0, 0.01); 2 repeat 3 for Each observation < u, lc , li > do 4 Randomly generate an unobserved POI lj ; 5 if ∆(lc , li) < τ then 6 Update XP (u), XP (li), XP (lj ); 7 Update XS (lc ), XS (li), XS (lj ); 8 if ∆(lc , li) ≥ τ then 9 Update XP (u), XP (li), XP (lj ); until convergence; 10 return Θ = {XS (L),XP (L),XP (U)}

6 Experiments

6.1 Experimental Setup

Experimental setting

In the experiments, we use the two datasets introduced in Section 3. For the one-year check-ins data, we use the check-ins in the first 10 months as training set, the 11th month as tuning set, and the last month as test set. We exploit two wellknown measure metrics [Yuan et al., 2013], namely Precision@N and Recall@N (denoted by Pre@N and Rec@N respectively). Given a user and his current location, we use the next check-in in successive τ hours as the ground truth. The time window threshold τ is set at 6 hours following [Cheng et al., 2013]. Based on the tuning set, the number of dimensions is set at K = 60, learning rate γ = 0.005, regularization term λ = 0.03 and component weight α = 0.2.

Evaluated methods

In the experiments, we compare PRME and PRME-G with the following baselines:

• Popu: the most popular POIs are recommended (user count ranking scheme in [Ye et al., 2013]).
• UCF: User based CF [Yuan et al., 2013; Ye et al., 2011]
• MF: Matrix Factorization with BPR [Rendle et al., 2009], which factorizes the user-item preference matrix.
• MC: first order Markov chain model [Zhang et al., 2014], which computes the transition probability by counting method.
• PME: the personalized metric embedding [Wu et al., 2013; Moore et al., 2013], which projects users and POIs in a common latent space.
• FPMC: the state-of-the-art personalized next POI recommendation algorithm [Cheng et al., 2013; Rendle et al., 2010].

6.2 Performance of Methods

We compare the precision and recall of various methods in Figure 3. The lower precision and recall of Popu method indicates that this naive approach is not feasible for the next POI recommendation. Both UCF and MF perform poorly because they do not make use of sequential information. This result shows the conventional POI recommendation algorithms, which mainly exploit the user preference, are not effective for the N 2 -POI recommendation. The relatively high performance of MC method demonstrates that the sequential information plays an important role in the N 2 -POI recommendation. The PME performance is not acceptable because the learning of sequential transition and user preference would be interfered with each other in a common latent space. Note that FPMC is state-of-the-art personalized Markov chain algorithm. PRME consistently outperforms FPMC, which illustrates that representing each POI as one point in latent space is more effective than two independent vectors. PRMEG achieves the best performance, which shows that the geographical influence is beneficial for the N 2 -POI recommendation. All reported improvements over baseline methods are statistically significant with p-value < 0.01.

We further compare PRME and FPMC with the localized region constraint [Cheng et al., 2013]. Figure 4 shows the precision with different region constraints. The local region constraint means we only consider the candidate POIs with no more than d km (d=10, 20 and 40) from current location. Note that PRME and FPMC use the same setting. Under different local region constraints, PRME outperforms FPMC, which further verifies the advantage of PRME.

(b) Recall on FourSquare

(c) Precision on Gowalla

(d) Recall on Gowalla

• (a) Pre@10 on FourSquare (b) Rec@10 on FourSquare

(c) Pre@10 on Gowalla

(d) Rec@10 on Gowalla

Figure 5: The effect of time threshold τ on Foursquare and Gowalla.

6.3 Effect of Parameters

Effect of time threshold τ

Figure 5 depicts the impact of the time threshold τ (τ = 3, 6 and 24 hours). PRME and PRME-G outperform the baselines with various τ. Besides, when τ is large, the performance of sequence based methods (MC, PME, FPMC,PRME and PRME-G) decreases. This is because the location sequential transition becomes weak when time difference is large.

Effect of component weight α

Figure 6 shows the effect of weight α. The performance at α = 0 (only sequential transition) is much better than α = 1 (only user preference). This result implies that sequential influence is more important than user preference in the N 2 -POI recommendation problem. The best performance is obtained when α = 0.2. Hence, we set α = 0.2 in our experiments.

Effect of number of dimensions K

We further investigate the impact of K with FPMC and PRME. Figure 7 shows the precision and recall for various K. When K ≥ 20, PRME outperforms FPMC in recommendation quality, which implies the superiority of PRME. The performance of FPMC and PRME increases with K because high dimensions can better embody the latent metric relationships. Empirically, we set K = 60 in our experiments, which achieves a satisfying trade off between recommendation quality and running time.

7 Conclusion and FutureWork

In this paper, we study the next new POI recommendation problem. We propose a novel pair-wise Metric Embedding to model the sequential POI transition. We further develop PRME-G that jointly models three factors: sequential transition, individual preference, and geographical influence. Performance of our algorithms is demonstrated by extensive experiments on two datasets.

Several interesting future directions exist for further exploration. First, metric embedding can be used to provide visualization of the POI-POI and user-POI relationships. Second, the PRME model is not specific for POI recommendation task and can be utilized for other applications, such as product recommendation and friend recommendation.

Acknowledgements

This work was supported in part by a grant awarded by Microsoft. ShanShan Feng would like to acknowledge the Ph.D. grant from Advanced Environmental Biotechnology Centre, Nanyang Environment and Water Research Institute, Interdisciplinary Graduate School, Nanyang Technological University, Singapore.