Learning User's Intrinsic and Extrinsic Interests for Point-of-Interest Recommendation: A Unified Approach

1 Introduction

Recent years have witnessed the rapid prevalence of locationbased social network (LBSN) services, such as Foursquare, Yelp, and Facebook, which can significantly facilitate users' outdoor activities by providing a large number of nearby Point-of-Interests (POIs) in a real-time fashion. The availability of large-scale user interaction data with these LBSN services, such as sharing check-in information, provides unparalleled opportunities for developing personalized POI recommender systems [Li et al., 2015; 2016b].

However, the complex nature of user interest and the sparsity of check-in data present significant challenges to develop POI recommender systems. First, only with check-in records, it is difficult to explain which reason impels a user to checkin a location. Thus, modeling user's true and interpretable interest becomes a thorny issue. For example, when an unvisited POI is far away from a user, she may not visit it due to the external geographical restriction, even though she likes the POI. This imposes a challenge on interpreting and modeling a user's decision making on POI check-in. Second, location recommender systems usually suffer from another critical challenge caused by the extremely sparse data. In a real system, there are over millions of locations and users. However, each user only has limited historical check-ins, significantly increasing the difficulty of recommendation.

∗The corresponding author.

Recently, a variety of approaches have been proposed for POI recommendation with matrix factorization from squared error based loss. For example, [Hu et al., 2008; Pan et al., 2008; Devooght et al., 2015] treat user's preferences for observed and unobserved locations as binary values with varying weights. [Liu et al., 2014] models geo-neighboring influence in both instance and region levels, where a user's choice to a location is affected by its neighboring locations, and locations in a region share a similar sparsity structure. [Li et al., 2016a] first utilizes additional knowledge, such as social network, to learn a set of potential locations from a user's all unobserved locations, and then assigns a small fixed value to fit this user's preference for these potential locations. However, all these existing approaches have two limitations. First, they model user's preference in a too general way, and thus fail to capture user's true interest, not to mention interpreting user's check-in decision making process. For example, a low predicted rating of a user for an unvisited POI can not reveal the reason why this user does not like the location. Is it because she does not like or due to the external environment restriction? Second, most existing methods treat user's all unobserved feedbacks as negative in the same way, and thus cannot capture the inherent property of missing data, i.e., a mixture of missed negative and positive values.

To address the aforementioned issues, in this paper, we propose a unified approach that could effectively learn finegrained and interpretable user's interest, and adaptively model missing data. Each user's general interest is modeled as a mixture of her intrinsic and extrinsic interests, where the former one is personal-taste driven and characterizes her own satisfaction regardless of any restriction, and the latter one is environment driven and influenced by external environment, i.e., geographical distance. To capture and distinguish both of them, we first formally define a user's activity area as a set of locations geographically accessible by this user, and then formulate them into pairwise ranking constraints in our unified recommendation approach. Specifically, upon intrinsic interest, one user prefers each visited POI over any unvisited one within the corresponding activity area. On the other hand, upon extrinsic interest, she prefers each visited POI over any unvisited one outside activity area. Moreover, a self-adaptive location-oriented method is proposed to capture the characteristic of missing data, which is formulated as squared error based loss in our unified optimization objective. Finally, the proposed model is evaluated via different validation metrics and compared with several state-of-the-art baseline models on real-world datasets. The experimental results illustrate the superiority of our model for POI recommendation. The major contributions of this paper can be summarized as follows.

• We propose to learn user interest in a precise and interpretable way, which is a mixture of the intrinsic and extrinsic interests. Based on these two types of interests, we formulate pairwise ranking constraints.
• We propose a location-oriented method to adaptively model the missing data, upon which we formulate the squared error based loss.
• We conduct extensive evaluations with real-world datasets to demonstrate the effectiveness of our model.

2 The ProposedMethod

Problem Statement. The recommendation task is defined as: given the check-in behaviors of n users over m locations, we aim at recommending each user with top-K new locations that she might be interested in but has never visited before.

Notations. Scalars, vectors and matrices are denoted by lower case letters, bold face lower case letters and bold face capital letters, respectively. Sets are represented by calligraphic capital letters. ui denotes the i-th column of matrix U. Frobenius and Euclidean norms are denoted by || · ||F and || · ||, respectively. Rn is defined as the set {1, · · · , n}. A predicted value is denoted with aˆ(hat) over it. C is used to denote the n-by-m check-in frequency matrix.

2.1 Our Framework

Matrix factorization techniques have been popularly used to solve recommendation tasks by mapping both user and location into latent low-dimensional spaces [Salakhutdinov and Mnih, 2007; Hu et al., 2008; He et al., 2016]. Specifically, each user-specific hidden vector is used to model this user's interest, and is then learned via an appropriate loss function. However, unlike traditional product consumption, user's check-in behaviors are constrained by many external factors, such as geographical distance. The complex nature in human mobility leads to the incapability of previous approaches for modeling a user's true interest in POI and interpreting her decision making process. Inspired by the studies in psychology and sociology about distinguishing whether or not a user's behavior is affected by external factors [Ryan and Deci, 2000; Calder and Staw, 1975], we propose to model each user's general interest from two aspects: (1) intrinsic interest, where she visits a location for the sake of her own inherent likeness regardless of any restriction, (2) extrinsic interest, where her check-in decision making process is influenced by geographical distance. Formally, they are are defined as:

Definition 1 (Intrinsic Interest) It is an internal form of interest and driven by personal taste. For example, it is the self-desire for a user to visit a POI with her own satisfaction.

Definition 2 (Extrinsic Interest) It is an external formof interest and driven by environment. For example, a user's preference for a POI is influenced by geographical distance.

These two types of user interest have different contributions to each individual user's check-in decision. Hence, each user's general interest is regarded as a mixture of her intrinsic and extrinsic interests. Suppose the general, intrinsic and extrinsic interests of user i are represented by d-dimensional vectors u(g) i , u(i) i , and u(e) i , respectively. Their relationship can be formulated as follows,

where ⊙ denotes the element-wise multiplication. And ai ∈ Rd×1 and bi ∈ Rd×1 are the mixture weights of intrinsic and extrinsic interest, respectively. Figure 1 provides an illustration example for u(g) i , u(i) i , and u(e) i .

We also propose to capture the characteristic of missing data (or unobserved data), i.e., a mixture of negative and missed positive values, for addressing the data sparseness issue in location recommendations. Let us assume each location j is also characterized by a latent vector vj ∈ Rd×1 as in the matrix factorization technique [Salakhutdinov and Mnih, 2007]. Consequently, towards modeling user's intrinsic and extrinsic interest and the missing data, the overall loss function of our framework is formulated as:

where θr (·) is the regularization term placed on all variables to avoid over-fitting. θc (·) incorporates additional constraints that model user's intrinsic interest U(i) and extrinsic interest U(e) , and will be introduced in Section 2.2. ℓ(·) is the empirical loss used to model both observed and unobserved data, and introduced in Section 2.3 (P is aslo introduced).

2.2 Modeling User Intrinsic and Extrinsic Interests

Based on the definition 1 and 2, the distinction between user's intrinsic and extrinsic interests sheds light on whether there exists the involvement of external influence. In POI recommendation task, a user's check-in decision making process is significantly affected by geographical factor. Thus, in this paper, we focus on modeling user's interests with geographical influence. Before introducing how to model user's two types of interests, we first define user's activity area as follows:

Definition 3 (User's Activity Area) Each individual user has one or more activity areas, within each of which this user is capable of geographically accessing each POI regardless of any geo-restriction.

Each user's activity areas can be calculated through many ways according to real-world application scenarios. One method is using clustering technique based on user's historical locations. In each cluster, we first select all locations within a circle with a specified distance as radius and each visited location as a center, and then merge them as the activity area. Formally, we define nai as the number of activity areas for the i-th user, where each of them h ∈ Rnai comprises a set of her visited locations Aih. Based on the definition of activity area, we will introduce how to model user's intrinsic and extrinsic interests in followings of this section.

Modeling User Intrinsic Interest U(i) . Based on the definition 1, each user's intrinsic interest suggests her to choose any locations that she likes regardless of any external georestriction. Within each activity area, the user is able to geographically access each location. It indicates that a user's check-in decision making process on those locations within her activity areas is restriction-free. Thus, within each activity area, compared to those unobserved locations, one user's intrinsic interest in an observed location plays an important role in her decision making process. In other words, upon intrinsic interest, each individual user i prefers each observed location j over any unobserved location l in each activity area, which can be formulated as follows:

where ¯ Aih is a set of unvisited locations of user i in her hth activity area, and (u(i) i )T vj indicates her preference for location j driven by intrinsic interest. Figure 2 shows an example to illustrate Eq.(3), where user u would like to check-in l1 ∼ l2 rather than l3 ∼ l5 upon her intrinsic interest.

Modeling User Extrinsic Interest U(e) . For those locations outside a user's activity areas, she has a small chance to visit them due to long distance. For example, although a user living at California likes a restaurant in New York, she would not go to check-in this restaurant for the sake of distance restriction. Thus, compared to those unobserved locations outside a user's activity areas, her extrinsic interest in an observed location has more impact on her check-in decision than her intrinsic one. Thus, upon extrinsic interest, each user i prefers each observed location j over any unobserved one outside the activity areas, which is formulated as follows:

whereA∗i is a set of unvisited locations of user i outside activity areas, and (u(e) i )T vj indicates her preference for location j driven by extrinsic interest. Figure 2 shows an example to illustrate Eq.(4), where user u would like to check-in l1 ∼ l2 rather than l6 ∼ l8 upon her extrinsic interest.

Our Method V.S. Existing Approaches. We would clarify that the existing approaches can be viewed as a special case of our method. If the size of activity area is infinite, which means the activity area of each user includes the whole location set, the constraints in Eq.(4) then will be eliminated, i.e., U(e) = 0. If the size of activity area is zero, indicating that each location is a single activity area, the constraints in Eq.(3) then will be eliminated, i.e., U(i) = 0. In both situations, only either intrinsic or extrinsic interest of user i contributes to her general interest, i.e., U(g) = U(i) or U(g) = U(e) , which is the same as existing approaches without distinguishing user's two types of interests. Thus, introducing the activity area can provide us finer-grained granularity to explore better accuracy of POI recommender systems.

The advantage of modeling user's general interest from two aspects is as follows: (1) It makes location recommendation systems behave in an explainable way by interpreting user's choice for locations from both internal and external perspective. (2) It provides a fine-grained and accurate way to learn user's interest. Finally, we can obtain the ranking constraint θc (·) of Eq.(2) by penalizing those violated constraints shown in Eq.(3) and Eq.(4) as follows:

where ˆ r(i) ij = (u(i) i )T vj, ˆ r(e) ij = (u(e) i )T vj, T = {i, h, j|i ∈ Rn, h ∈ Rnai , j ∈ Aih}, (x)+ = max(x, 0) is plus function, and λic , λec are parameters weighting two ranking constraints.

2.3 Modeling the Missing Data

Due to the large set of locations, it is crucial to model the missing data as well for addressing data sparseness and improving learning accuracy. Most recent approaches [Hu et al., 2008; Liu et al., 2014] focus on squared error based loss and treat all unobserved feedbacks as negative in the same way. However, it is not realistic in real-world scenario. An unvisited location of one user does not necessarily indicate that she dislikes it, whereas it happens possibly due to her unawareness. In other words, some of the unvisited locations might be those users are interested in, while others are actually those they dislike. Thus, each user's preferences for unobserved locations are a mixture of negative and missed positive values. Motivated by this intuition, we propose a location-oriented method to adaptively learn the potential values for missing entries, instead of treating them equally as a predefined value. To achieve this, we introduce an augmented matrix P ∈ Rn×m that is designed only for unobserved feedbacks and learned during the training. Suppose the predicted preference of user i for location j is approximated by ˆ rij = (u(g) i )T vj 1 . The empirical loss ℓ(·) of Eq.(2) with squared error is formulated as:

where W ∈ Rn×m is a weight matrix associated with checkin frequency and a parameter γ ∈ (0,+∞), and defined as wij = √1 + γ ∗ cij . R ∈ Rn×m is a one-class feedback matrix with observed feedback as one and unobserved feedback as zero, i.e., rij = 1 if cij ̸= 0 and rij = 0 if cij = 0. Specifically, P has two properties: (1) It is location-oriented, i.e., comprising m latent factors, for efficient computing; (2) It has a small variation range for decreasing the noise in model learning. Thus, P can be formulated by introducing a mdimensional vector q as follows,

where qmin and qmax are parameters used to bound P into a small range around zero. In Eq.(6), it is clear that R is used to model observed feedbacks, while P accounts for unobserved feedbacks and explains the difference of missing data.

Discussion. If qmin = qmax = 0, it leads to the basic implicit-feedback based approaches by fitting a binary matrix [Hu et al., 2008; Pan et al., 2008]. If qmin = qmax ̸= 0, it leads to the constant imputation-based approaches by assigning a predefined non-zero numeric value for unobserved feedback [Yao et al., 2014; Li et al., 2016a]. If qmin ̸= qmax, our method is distinct from existing approaches by adaptively separating all the unobserved feedbacks, which has two advantages: (1) capturing the inherent property exhibited in unobserved data, i.e., a mixture of negative and positive values, and (2) automatically learning the optimal values for unobserved data instead of specifying a fixed value.

2.4 Optimization Algorithm

So far we have introduced our solutions to capture user's intrinsic and extrinsic interests, and address missing data issue in POI recommendation. With these solutions, the loss function of the proposed model, denoted as IEMF, is achieved by integrating Eq.(5) and Eq.(6) into the framework in Eq.(2):

1 We will also incorporate geographical influence into final prediction with ˆ rij in a multiplicative or additive manner as [Li et al., 2016a; Ye et al., 2011].

Algorithm 1: IEMF Optimization

Input: λic , λec , λiu , λeu , λv, λz, λp, α, γ, qmin, qmax, η, maxIter Output: U(i) , U(e) , V, Z, q 1 Randomly initialize U(i) , U(e) , V, Z, q, t ← 1 2 while t ⩽maxIter do 3 Randomly sample a tuple (i, h, j, k, l, S-), where i is a user, h is activity area index, j is a visited location within the acticity area, k is an unvisited location within this activity area, l is an unvisited location outside activity areas, and S- is a set of other unvisited locations with size as |S-|. 4 eio ← wio(ˆ rio - ˜ rio), ∀o ∈ S 5 ejk ← λicwijy′ (ˆ r(i) ik - ˆ r(i) ij ), ejl ← λec wijy′ (ˆ r(e) il - ˆ r(e) ij ) 6 u(i) i ← u(i) i -η(∑o∈S eio(ai ⊙vo) +ejk(vk -vj) +λiuu(i) i ) 7 u(e) i ← u(e) i -η(∑o∈S eio(bi ⊙vo) +ejl(vl -vj) +λeuu(e) i ) 8 zi ← zi - η(∑o∈S eio(a′i ⊙ u(i) i +b′i ⊙u(e) i ) ⊙vo +λzzi) 9 vj ← vj - η(eiju(g) i - ejku(i) i - ejlu(e) i +λvvj) 10 vk ← vk - η(eiku(g) i + ejku(i) i +λvvk) 11 vl ← vl - η(eilu(g) i + ejlu(e) i +λvvl) 12 vo ← vo - η(eiou(g) i +λvvo), ∀o ∈ S13 qo ← (vo - η(-eio + λqqj ))q , ∀o ∈ S ∗- 14 t ← t + 1 15 end 16 returnU(i) , U(e) , V, Z, q

where 1n×d is a n-by-d matrix of ones, and the weight matrix W is also used to balance the optimization of squared error and ranking error. To solve above optimization problem, we need some preprocessing and approximation steps. First, we eliminate the constraints imposed on A and B by introducing a helper matrix Z ∈ Rn×d with zik ∈ (-∞, +∞), and using a sigmoid function to bound the value to [0, 1] as follows,

where σ(x) = 1 1+exp(-x) is sigmoid function. Second, the plus function used in Eq.(5) is not twice differentiable and can be smoothly approximated by the integral to a smooth approximation of the sigmoid function [Lee and Mangasarian, 2001; Chen and Mangasarian, 1993], given by:

where α ∈ (0, +∞) is a parameter. With these two steps, the optimization problem shown in Eq.(8) can be transformed to,

where ˜R = R+P, q ∈ [qmin, qmax], and θr (·) is defined with regularization parameters λ∗ as follows:

As there is no close-form for each variable with ALS approach, a Stochastic Gradient Descent (SGD) using the boostrap sampling with replacement algorithm is developed to solve the optimization problem. The optimization algorithm is iteratively performed by sampling a tuple (i, h, j, k, l, S-) and updating corresponding variables. More details of optimization are provided in Algorithm 1, where S = {j, k, l} ∪

S-, S ∗- = {k, l} ∪ S-, a′i = σ′ (zi), b′i = -σ′ (zi), (·)q is bounded value between qmin and qmax, and σ′ (x) = σ(x)(1 - σ(x)), y′ (x) = 1 1+exp(-αx) are the derivatives of σ(x) and y(x), respectively.

Complexity Analysis. Sampling a tuple (i, h, j, k, l, S-) has a constant cost O(|S-|) in each update, where |S-| is the size of sampled unobserved POIs and usually very small. Hence, the overall complexity of optimization algorithm is O(d|S-|#iter), where #iter is the total number of iterations. In practical, #iter ≫ d|S-| is proportional to the number of the observed check-ins.

3 Experiments

3.1 Datasets

We use Gowalla and Foursquare datasets to evaluate model performance. Gowalla and Foursquare contain check-in data, ranging from January 2009 to August 2010, and from December 2009 to June 2013, respectively. Each check-in record in the datasets includes a user ID, a location ID and a timestamp, where each location has latitude and longitude information. We split the training and testing data as follows: for each individual user, (1) aggregating check-ins for each location; (2) sorting locations according to the first checked-in timestamp; (3) selecting the earliest 80% to train the model and using the next 20% as testing. The data statistics are shown in Table 1.

3.2 Parameter Settings

All regularization parameters are set as 0.01. The parameter λiu , α, η and d are set as 0.01, 5, 0.001, and 10. The λeu , |S-|, qmin, and qmax are set as 0.1 (or 1), 10 (or 150), -0.3 (or -0.05) and 0 (or 0.05) in Gowalla (or Foursquare) dataset. The number and radius of activity area are set as 1 and 2km.

3.3 EvaluationMetrics

We quantitatively evaluate model performance in terms of top-K recommendation performance, i.e., Precion@K and Recall@K, and ranking performance, i.e., MAP. They are formally defined as follows:

where Si(K) is a set of top-K unvisited locations recommended to user i excluding those locations in the training, and Ti is a set of locations that are visited by user i in the testing. p(j) is the precision of a cut-off rank list from 1 to j, and rel(j) is an indicator function that equals to 1 if the location is visited in the testing, otherwise equals to 0.

3.4 Baseline Methods

To comprehensively demonstrate the effectiveness of our model, we compare them with the following popular models:

• (c) Recall@K on Foursquare

(d) Recall@K on Gowalla

Figure 3: Performance comparison in terms of precision@K and recall@K on Foursquare and Gowalla datasets.

• ARMF [Li et al., 2016a], which learns a set of user's potential locations from her unobserved locations using social network, and then incorporates them into matrix factorization with category and geographical information.
• IRenMF [Liu et al., 2014], which incorporates neighboring characteristics in both instance level and region level into weighted matrix factorization;
• USG [Ye et al., 2011], which incorporates geographical influence, social network and user interest into user-based collaborative filtering in an additive manner;
• BRP [Rendle et al., 2009], which optimizes the ordering relationship of user's preferences for the observed location and the unobserved location;
• WRMF [Hu et al., 2008], which minimizes the squared error loss by assigning both observed and unobserved checkins with different weights based on matrix factorization.

3.5 Performance Comparison

In this section, we evaluate model performance from Precision@K, Recall@K and MAP on two datasets shown in Figure 3 and Table 2. We summarize the following observations.

First, our method outperforms all the other baseline methods. This superior result is for the sake of modeling finegrained user interest, unobserved data and geographical influence together. Our better performance over those baseline methods with geo-influence, i.e., ARMF, USG, and IRenMF, further illustrates the benefit of capturing user's two forms of interest and adaptively learning unobserved data.

Second, WRMF and BRP perform differently in two datasets, where the former one is based on squared error and the latter is based on ranking error. Until now, there is no explicit clue to demonstrate which method is suitable for which type of data from Precision@K, Recall@K and MAP. From the technical viewpoint, our approach can be viewed as a unified method for ranking and squared error based loss functions. It is a tradeoff between these two popular matrix factorization methods. Although our approach does not have closed-form solution as WRMF does, the effective SGD with sampling can achieve the same effectiveness.

Third, those methods with geo-influence, i.e., IEMF, ARMF, USG, and IRenMF, are better than other methods without geo-influence, i.e., BPR and WRMF. This result further clarifies the importance of geo-influence in location recommendation, which also distinguishes location recommendation task from traditional item recommendation task.

3.6 Study of Influence of Parameters λiu and λeu

We study the influence of parameters λiu and λeu . Specifically, we set λiu = 0.01 and then train our model with different λeu , where the results are shown in Figure 4. From the results, we observe that the optimal λeu /λiu is 100 and 10 on Foursquare and Gowalla datasets, respectively. It indicates that the weight placed on the ranking constraint about extrinsic interest should be larger than the one about intrinsic interest. There are two reasons: for each user, (1) the number of unobserved locations outside her activity areas is usually larger than those within activity areas, and thus, a large λeu can allow IEMF to model more unobserved data; (2) she has a large probability to check-in the locations within her activity areas due to geo-influence, and thus, a too large λiu will increase the noise for model learning. If λeu /λiu is too large, IEMF almost focuses on optimizing the ranking constraint related to extrinsic interest, definitely resulting in a poor result.

4 RelatedWork

Related work of this paper can be grouped into two categories. The first category is about matrix factorization (MF) [He et al., 2016; Chen et al., 2016; Kabbur et al., 2013; Balakrishnan and Chopra, 2012; Pil´aszy et al., 2010; Salakhutdinov and Mnih, 2007; Pan and Chen, 2013]. The core of MF is to map user and item with two into low dimensional latent space. Different loss has been developed to model the implicit feedback. For example, [Hu et al., 2008; Pan et al., 2008] propose to minimize the sum-of-squared error with different weight over all user-item pairs, where the observed and unobserved feedbacks are assigned to one and zero, respectively. Another loss function is based on ranking error [Rendle et al., 2009; Rendle and Freudenthaler, 2014] by optimizing the ranking order between observed examples and unobserved ones.

The second category is about POI recommendation with geo-influence [Li et al., 2015; Lian et al., 2014; Lichman and Smyth, 2014; Li et al., 2016c]. For example, [Ye et al., 2011; Li et al., 2016a] propose to use a power law distribution to estimate the check-in probability with distance. With geoinfluence, one user's interest in a location then can be calculated by a user-based collaborative filtering [Ye et al., 2011] or learned by MF models [Li et al., 2016a]. Also, [Liu et al., 2014] proposes to model geographical neighboring influence from both instance level and region level.

Different from the aforementioned methods, in this paper, we propose a new fine-grained approach to model a user's general interest from both intrinsic and extrinsic perspectives. In addition, the unobserved feedbacks (i.e., missing data) are modeled by a self-adaptive location-oriented approach.

5 Conclusion

In this paper, we proposed a unified approach to integrate squared error loss and ranking error loss for solving location recommendation task by effectively learning fine-grained and interpretable user interest, and adaptively modeling the missing data. Specifically, each user's general interest is modeled as a mixture of her intrinsic and extrinsic interests, upon which we formulated the ranking constraints in our unified approach. Additionally, a self-adaptive location-oriented method is proposed to capture the characteristic of missing data, and is then formulated as the squared error loss in our unified optimization objective. To evaluate our model, we conducted extensive experiments on real-world datasets and compared our method with several baselines. The experimental results have shown the effectiveness of our model.

Acknowledgments

This work is partially supported by the NIH (1R21AA023975-01) and NSFC (61602234, 61572032, 91646204, 61502077).