Rong Gao, Jing Li＊, Bo Du, Xuefei Li, Jun Chang, Chengfang Song, Donghua Liu

School of Computer Science, Wuhan University, Wuhan 430072, China

Abstract: Recently, as location-based social network (LBSN) rapidly grow, point-of-interest (POI) recommendation has become an important way to help people locate interesting places. Nowadays, there have been deep studies conducted on the geographical and social in fluence in the point-of-interest recommendation model based on the rating prediction. The fact is, however, relying solely on the rating fails to re flect the user’s preferences very accurately, because the users are most concerned with the list of ranked point-of-interests (POIs) on the actual output of recommender systems. In this paper, we propose a co-pairwise ranking model called Geo-Social Bayesian Personalized Ranking model (GSBPR), which is based on the pairwise ranking with the exploiting geo-social correlations by incorporating the method of ranking learning into the process of POI recommendation. In this model, we develop a novel BPR pairwise ranking assumption by injecting users’ geo-social preference. Based on this assumption, the POI recommendation model is reformulated by a three-level joint pairwise ranking model.And the experimental results based on real datasets show that the proposed method in this paper enjoys better recommendation performance compared to other state-of-the-art POI recommendation models.

Key words: location-based social network(LBSN); point-of-interest (POI) recommendation; geographical in fluence; social in fluence;Bayesian personalized ranking (BPR)

I. INTRODUCTION

Along with the development of social media and the emergence of O2O business model,the location-based social networks have grown exponentially with such typical case as Foursquare and Gowalla. In the meantime, the advancement of GPS positioning technology and the wireless Internet technology have made it easy for users to indicate their location (called point-of-interest), share photos of that location,leave comments and tips on that location via check in, which turns the effective integration and interaction between the online data and of fline people’s activity into reality. The location-based social network has now become the ideal platform for learning users’ online activities and movement pattern through the effort of accumulating millions of check in data. It also provides a platform for the establishment of many important online applications such as the Personalized Location Recommendation System [1,2], Travel Route Recommendation[3,4,5,6,7,8] , Network Security System[9,10]and the User Behavior Mining System[11] to name just a few. As an important application in location-based social network, POI recommendation on one hand helps users explore new POIs and enriches their life experience.On the other hand, it also helps service providers to provide accurate personalized services to potential users, thereby helping businesses increase revenue [12]. As a result, in recent years, the POI recommendation systems have received an increasing amount attention from the academic and industrial fields.

The recommendation system [13] has been deeply studied by academic and widely applied in e-commerce systems, such as commodity recommendation in Amazon, movie recommendation in Netflix, music recommendation in Last.fm and so on. Particularly,the recommendation system based on location-based social network is featured by the following three unique attributes:

(1) Big Data: on the basis of users’ check in behaviors, the location-based social network generates massive amount of location data as well as abundant contextual information including social correlations[14,15],text information [16,17], image information[18,19,20,21,22,23,24,25], video information[26,27,28] and category information[29].The characteristics of big-data such as volume,velocity and variety in the location-based social network are of signi ficant application and research values [30,31].

(2) Geographical in fluence: In LBSNS, the users are required to interact with each other so as to check in the POIs. However, the POIs are different from such items as books, movies and commodities in those traditional recommendation systems in terms of the geographical features. Consequently, the geographic information makes a great effect to the user’s check in behavior, which is called geographical in fluence. As Tobler pointed out in his First Law of Geography [32] , things close to each other in geographical space should have more connections. Therefore, the closer POIs are more likely to be favored by users than those far away from the users.

(3) Social in fluence: Based on the assumption that friends tend to share similar preferences, the social information among users are used to advance the performance of recommendation algorithms [33,34,35], because in the location-based social network, friends’ behaviors and preferences can reveal important clues and references when a user’s historical check in data is too sparse.

In this paper, the authorship propose a co-pairwise ranking model called Geo-Social Bayesian Personalized Ranking model(GSBPR).

In the POI recommendation domain, the key task is to estimate the target user’s preference to the unknown POIs and then return to POIs with a ranked list that are likely to suit his/her interests as the recommendation result for the target users. Therefore, researchers have put forward several POI recommendation algorithms by combining the tasks in the recommendation domain and the unique attributes of the POI recommendation system mentioned above. Most of these researches focus on fitting the location aware preference rating function based on the contextual information of POIs. Specifically speaking, the various type of contextual information includes Location geographic information [36,37,38], temporal influence [39,40] and social friends[41, 42,43] whose POI recommendations are based on the collaborative filtering model. Nevertheless,the researchers have recently found that the current POI recommendation models are still in face of the following three challenges:

(1) As mentioned above, the task of most recommendation systems is to generate and display a top-k list of POIs for the target user,while the predicted rating value is only used to generate the top-k list. Under normal circumstances, however, the predicted rating values are not directly displayed to the users, which then make the accuracy of such predictions less important. The correct order of the POIs in the final top-k list is now the key to recommendation. Therefore, users’ single rating to the POI prediction does not precisely reflect users’ preferences.

(2) A growing number of POI recommendation algorithms attempt to improve the recommendation performance with the help of abundant social information available in the location-based social network. For example,although the literature [44] belongs to the POI recommendation based on learning-to-rank, it fails to take the target users’ social correlation into consideration; the literatures [45,46] recommend POIs by integrating their social and geographical correlations on the basis of collaborative filtering model, but it is still not one of learning-to-rank based methods.

(3) The rank-oriented algorithms for recommendation are mainly divided into three categories, namely, by point-wise method, pairwise method and list-wise method [47]. And those methods [36-43] mentioned above actually belongs to the point-wise method which transforms the sorting problem into the regression problem and calculates the rating values of POIs individually without considering the ordering relations among POIs. The list-wise method, in contrast, directly optimizes the ranking of the entire POI recommendation list.However, it is difficcult to extend the contextual information about the fusion of POIs in the list-wise recommendation model, so the effect is not satisfactory in the POI recommendation applications [48].

To tackle the above issues, motivated by the classical pairwise ranking model –the BPR model, we propose a novel POI recommendation algorithm in which the method of pairwise ranking is adopted to integrate the context information (e.g. the geographical information of the POIs and the social information of the users). To be speci fic, based on the observations on users’ preference to the POIs,we make the following two assumptions:

1. In contrast with those distant unchecked-in POIs, those unchecked-in POIs surrounding users’ checked-in POIs are more likely to assigned higher ranks on the final top-k recommendation list.

2. Among those unchecked-in POIs surround the POIs checked-in by users, those POIs checked-in by users’ friends would be assigned higher ranks on the final top-k recommendation list.

The two assumptions above are theoretically supported by the current literatures. The literatures [49,50,51,52] holds that a majority of users prefer to check-in the POIs near those checked in POIs and the adjacent POIs are more geographically related than the distant POIs. Hence, the POIs checked-in by users tend to form a geographic cluster area. Meanwhile, the literatures [53,54] point out that since the users’ interests are similar to that of their friends, it is advisable to predict users’ interests by analyzing their friends’ interests. In other words, friends’ interests and preferences provide important references and guidance for the recommendations for a given user.

On the basis of the two assumptions above,a new POI recommendation model called Geo-Social Bayesian Personalized Ranking model (GSBPR) is proposed in this paper to capture the correlation between personal preferences and geo-social in fluences. Such model aims at improving its recommendation performance by expanding the BPR model in an effort to integrate the geographical influence and social in fluence. This method maximizes the posterior of users’ geographical impact and social impact features, and employs the Bayesian personalized ranking method to optimize the proposed model parameters. As for the two real datasets of Foursquare and Yelp,it has been validated by a number of pervasive experimental evaluation metric that the proposed GSBPR model is superior to the stateof-the-art POI recommendation algorithms in terms of performance.

The contributions of this paper are summarized as follows:

(1) Different from the previous work which directly model on the geographical cluster and user trust relationship, the GSBPR model proposed in this paper captures users’ preferences more accurately. Given that the user’s mobile pattern is not suitable for a speci fic geographical distribution like Gauss distribution [55]or power-law distribution [56,57] , and the diverse reasons for social relationship formation also bring some noises to the social modeling,this paper introduces relevant feedback via the BPR based assumptions and achieves more accurate explanations than the application of classical BPR model. To our knowledge, this is the first time when the geo-social in fluences are integrated with the BPR model for the POI recommendation.

(2) In this paper, a joint ranking model(GSBPR) is proposed to improve the BPR pairwise assumption by injecting geo-social influence. The geo-social feedback derived from the same geographic feedback in this model has a positive effect on the final learning of user preferences. At the same time, it also embodies the actual scene, which is close to the user’s real check-in behaviors. In other words, this is also the first time when the problem of POI recommendation has been reformulated into a three-level joint pairwise ranking scheme on the basis of relevant feedback and the Bayesian personalized ranking method is employed to optimize the model derivation as well as learn the model parameters. Due to the optimal balance of geographical preference and latent factors, the GSBPR model outperforms outperformed other state-of-the-art factorization models and has been theoretically and experimentally proved to be a right choice for personalized POI recommendation task.

II. RELATED WORK

Recently, some interesting works have been done in the field of POI recommendation. In this section, we brie fly reviews recent advances in POI recommendation domain.

2.1 Point-of-interest recommendation

Suppose that the POIs are regarded as one of the items (like movies, music and commodities, etc) in those traditional recommendation systems, the recommendation algorithms based on memory and models within the systems can then be adopted to provide recommendation services for the users in LBSN.With the development of LBSN, the sole reliance on the interactions between users and the POIs is unable to provide the expected effective recommendation. Therefore, an increasing number of researchers turn their attention to the contextual information between users and the POIs such as check in time, social correlations and so on. As is proposed in literatures[58,59,60] by Adomavicis and Verbert that the incorporation of the contextual information of a related scene into the recommendation system is helpful to enhance the recommendation accuracy. Hence, the Context-aware Recommender Systems, also called the CARS model,was put forward to solve the problem of “recommending relevant items fitting for users’interests and scene” by means of extending the traditional two-dimensional relational model of “user-item” into a multi-dimensional relational model containing various contextual information. Therefore, the LBSN-based POI recommendation systems would first obtain the contextual information of the users and POIs, and then make recommendations for users according to the collected contextual information. So, the incorporation of users’ and POIs’ contextual information (such as: user social relations, geographic information and check-in time, etc) into the recommendation system plays a crucial role in enhancing the recommendation performance. According to the type of contextual information involved,POI recommendation algorithms are classi fied into the following 5 categories. (1) The POI recommendation method on the basis of pure check in data [61]; (2) POI recommendation based on social influence [62,63];(3) POI recommendation based on temporal influence [64,65];(4) POI recommendation based on geographical influence [49,50];(5) POI recommendation based on comment [66,67].Particularly, many recent studies have shown a strong correlation between user’s check-in behavior and geographical distance as well as social relation in terms of POI recommendations. Cheng et al. [55] hold that users tend to check in around several centers and captures the geographical influence via modeling the probability of a user’s check-in on a location as a Multi-center Gaussian Model (MGM). He also proposes that the social in fluence should be integrated to improve the performance of the POI recommendation algorithm. Ye et al. [56] employed a power-law distribution to model user’s check-in behaviors, and proposed a collaborative POI recommendation algorithm based on geographical in fluence via naive Bayesian. The social and geographical in fluences are integrated into such framework in light of the linear curve fitting method so as to explore the POI recommendation. Gao et al.[51] provided the POI recommendation services by means of integrating the geographical information, social relation and comment information on the basis of classical matrix factorization model. Gao et al. [68] argued that it is advisable to analyze the correlation between social networks and geographical distance on LBSNs and a geo-social correlation model can then be built to solve cold-start location recommendation problem. Zhang et al. [69]proposed a POI recommendation model called CoRe, which adopts the kernel density estimation technique in the modeling of the personalized geographical in fluence of locations as an individual distance distribution for each user rather than a common distribution for all users. At last, user preference, social in fluence,and geographical in fluence are integrated into a uni fied framework for POI recommendation.Obviously, all the methods discussed above are essentially based on the point-wise theory bases on the point-wise theory, aiming at regressing a user’s actual rating value to an unknown POI. Consequently, few researches have been done to develop the personalized POI recommendation by integrating geo-social correlations through learning-to-rank method.We thereby propose a POI recommendation model based on pairwise ranking with the integration of geo-social correlations.

2.2 Rank-oriented Recommendation Algorithm

Definition

In the POI recommendation system, users’preferences are reflected by users’ check in behavior which is regarded as kind of implicit feedback. In such way, the difficulty in POI recommendation occurs because apart from the positive samples, the negative samples and the missing POIs are also mixed in the observation. Therefore, the POI recommendation can also be regarded as One-Class Collaborative Filtering (OCCF)[70,71]. According to the literature [72], the recommendation results derived from users’ rating value on items alone may not accurately reflect users’ preferences. As a result, the researchers consider incorporating the learning-to-rank technique[73] into the recommendation process. It is believed that it is more important to recommend according to the order among items instead of the rank based on item rating values. Inspired by the machine learning ideas, the collaborative filtering recommendation algorithm on the basis of learning-to-rank obtains a ranking model by training data. After that, the optimal solution of the ranking model is obtained by iteratively optimizing the parameters of the ranking model which is used to generate the final recommendation results in the end.

In recent years, the collaborative filtering recommendation algorithms on the basis of rank learning have received more and more attention. Among them, the list-wise method is able to solve the problem of item ranking to some extent because of its attempts to optimize the entire recommendation list. However, there is little contextual information in the model fitting for integration, and it also lacks comprehensive consideration of users’ social relations as well as the contextual information in other items. As a result, the accuracy of the final recommendation model is affected and the model is thereby subject to a certain limitation in practical applications. In contrast,the pair-wise ranking method is superior to the point-wise method in terms of the performance[74] because it formalizes the ranking into two classi fications problems, taking the order relations in the ranking list into full account.The Bayesian personalized ranking model proposed by Rendle et al. [75] is the most popular ranking model in recent years which compares pairwise preferences based on observed and unobserved item ratings and transforms the user browsing item record matrix into the item rating order relation matrix. And thus the BPR learns the ranking models based on pairwise comparison of items such that the Area under the ROC Curves (AUC) can be maximized.After that, more and more researchers began to pay attention to the recommendation problem based on extended BPR model. In literature [76], the matrix factorization model based on the BPR standard is extended to tensor factorization (i.e., RTF) for tag recommendation. In literature [77], BPR criterions are expanded by modeling social relations and social preferences. Similarly, Pan et al .[78]proposed an improved algorithm called Group Bayesian personalized ranking to enhance the recommendation performance by introducing a new assumption based on richer interactions among users.

Nevertheless, there exist only few works where the collaborative filtering recommendation algorithms based on BPR pairwise ranking is applied to POI recommendation when compared with the large number of collaborative filtering recommendation algorithms on the basis of rating prediction. Recently, Li et al. [44] developed a ranking based geographical factorization method (Rank-GeoFM) for POI recommendation based on a new loss metric—Ordered Weighted Pairwise Classi fication(OWPC) criterion[79]. The method considers the ranking problem as a set of pairwise classi fication problems and emphasizes the classification of the top-k POIs in the recommendation list by assigned higher weights. However,the OWPC criterion greatly increases the time complexity of the Rank-GeoFM. Moreover,in the proposed negative item sampler, the unobserved (negative) items are also sampled evenly, which may require extensive sampling before identifying a project that ranks higher than the positive item [80]. In contrast, in this paper, the GSBPR model based on an extended BPR model helps to study the ranking model through pairwise comparison by introducing the geographical and social feedback. Besides,it does not increase the time complexity of the learning and prediction process. Also, the proposed three-level pairwise ranking model in this paper is based on the geographical in fluence and social in fluence in the BPR extended hypothesis modeling, which reflects the realistic scenes and users’ check in behavior in a better way.

III. PRELIMINARIES

In this section, the problem of POI recommendation is firstly formalized. Next, since the BPR model is designed for optimizing users’ preferences over pair-wise samples (i.e.,positive sample against negative or missing sample), we introduce several concepts used in this paper, that is, positive feedback, geographic feedback, geo-social feedback and negative feedback. The objective of this paper is to learn users’ preference through integrating positive feedback, geographic feedback,geo-social feedback and negative feedback so as to provide each user with a personalized POI recommendation list. At last, the basic idea of the Bayesian personalized ranking model is brie fly summarized.

3.1 Problem Formulation

In the POI recommendation systems,is usually used to denote user set, anddenote the set of all POIs, whereinMandNrepresent the number of users and POIs respectively. Compared with other recommendation systems,every POI in this system is geographically encoded by < latitude, longitude > in addition to the unique identification. Users’ check in record forms the user-POI check-in frequency matrixC∈RM×N, which is normally very sparse because most users only check in a small part of POIs. At the same time, the elementCvlin Matrix C represents the check in frequency of uservin the POI ofl. The purpose of POI recommendation is to exploit users’ check-in data and other contextual information in LBSNs to predict users’ visiting frequency at POIs that they never check-in before as well as to provide users POI list that would arouse their interests according to the predicted frequency.

In this paper, we de fine that uservchecks in the POIland the set of user-POI (v,l)pairs is then denoted as positive feedback in the form ofDifferent from the definition of negative feedback proposed by Rendle et al. [75], we introduces new feedback by taking the neighborhood information of POI and user social in fluence into consideration. In particular, within the POI geographical networks ofG=(L,F), (l,g)∈Fshows thatlandgshare the same geographical neighborhood; while in the social network ofS=(U,E), if (v,u)∈Ereveals a connection between uservand useru, these two users are then identified as friends. If POIlandgare geographical neighbors, and POIgis not checked in by the userv, then the set of(v,g) pairs is identi fied as geographical feedback in the form of. If the POIkin the set of (v,g) pairs is at least checked in by a user’s friendu, the set of (v,k) pairs is then defined as geo-social feedback in the form of. As a result, as for POIwwhich is checked in neither by uservnor by the user’s friends and not in any geographical neighborhood of all checked-in POIs, the set of (v,w) pairs is then identi fied as negative feedback in the form of

Fig. 1. A graphical illustration of BPR model.

3.2 BPR: bayesian personalized ranking from implicit feedback

The BPR model the maximum model of posterior estimation based on the Bayesian theory is a famous ranking-based optimization model proposed by Rendle et al. [75]. To be speci fic,Rendle assumes that useruprefers the POIitojso the rating pair of (u,i) instead of(u,j) can be observed whereinUandIrepresent user set and item set respectively. The framework of BPR model is shown in figure 1.

The definitions above are assumed as follows:

where ? represents the parameter set of the ranking model, whilestand for the prediction rating score of the ranking function.

Therefore, The Bayesian formulation officnding the correct personalized ranking for all items is to maximize the following posterior probability.

here, ?uis the desired but latent preference structure for user u. All users are presumed to act independently of each other. We also assume the ordering of each pair of items for a speci fic user is independent of the ordering of every other pair.

To be speci fic:

Based on all the formulas above, the final objective function is summarized as :among them,λ?represents the specific regularization parameter of the model, whileis the training dataset.

The BPR ranking model adopts a widely used stochastic gradient descent (SGD) algorithm to optimize the objective functions in Equation (6).

IV. GSBPR MODEL

In this section, we thoroughly analyze the drawbacks in the BPR assumption for POI recommendation tasks, and then a new model assumption is put forward according to the analysis above as well as the relevant concepts mentioned in section 3.1 by explicitly modeling the structure of geographical and social in fluences. What’s more, the proposed GSBPR model is elaborated, the model derivation and parameter learning process based on Bayesian personalized ranking technique are depicted.Figure 2 shows the framework of our GSBPR recommender model.

4.1 Model assumption

The tasks of POI recommendation based on BPR assumption suffer from the following three drawbacks. (1) Because the BPR model is originally designed for item recommendations, the application for POI recommendation making it unable to explicitly consider the characteristics of geo-spatial preferences.

However, it has already been confirmed in the literatures [36,37,38,44,49,50,51,56] that the geo-spatial proximity influence plays an effective and obvious role in improving the performance of POI recommendation. (2)The non-positive user-POI pair sampling by the BPR model is equivalent to the positive user-POI sampling, making a large number of unobserved user-POI pair unfit for learning modeling. (3) In the social networks, users’behavior and activities are not only related to their own interests, but also shares close relations with their friends’ preferences and behaviors that tend to provide important references and clues. Specifically speaking,inspired by literature [75], a novel assumption proposed in this paper explicitly models the geo-spatial proximity and the users’ friend structure. Therefore, in view of the above three points, this paper aims at improving the final recommendation quality of the POIs by taking the geo-spatial proximity between users and POIs and the social connections among users into full account.

Fig. 2. The GSBPR recommendation framework.

Assumption-A:represents userv’s preference for the POIl;stands for userv’s preference for the POIg; whilemeans that uservprefersltog. Among them, only the rating pair (v,l) instead of(v,g) can be observed and the POIgandlshares the same geographical neighborhood.Moreover,stands for userv’s preference for the POIw;shows that uservprefers the POIgtowprovided that the rating pair (v,w) is unable to be observed andwdoes share a same neighborhood with any checked-in POIs. On the basis of Equation (1),this assumption can be formulated as follows:

Assumption-B: On the basis of assumption-A, the user social information is introduced in assumption-B where the interests of friends also provide important references and clues for the recommendation. Obviously,inl’s geographical neighborg, users show more preferences for the POIswhich has been checked in by users’ friends. Therefore,compared with those distant and unchecked POI, users show greater preferences for those unchecked POIs near the area of checked-in POIs. And among the checked-in POIs mentioned above, those POIs checked in by their friends are more favored by users. As a result,on the basis of Equation (1) and Equation (8),it is easy to infer as follows:

Obviously, the mentioned Equation (9) is more pervasive compared with Equation (8)because it considers both the geo-spatial proximity and geographical feedback of the POI but also the in fluence of user social networks.Assumption B is more in line with the realistic scenes in real cases of POI recommendation.

4.2 Model derivation

In this section, the geo-social influences are used to improve personalized ranking for collaborative filtering. Given the set of user-POI(v,l) pairs, the POI geographical networksG=(L,F) and the social networkS=(U,E)fromMusers andNPOIs . The goal of this paper is to learn a ranking function for each user u.

Then, the derivation process of Bayesian ranking technique based on two assumptionsAandBis elaborated and the performance of GSBPR model on the basis of these two assumptions are also depicted.

According to the Equation (8) and (9) in assumptionAandB, we adopt the method of maximum posterior probability to determine userv’s order relation ?vwith all POIs and eventually generates a recommendation list. In accordance with the Bayesian theory, the formula below is therefore achieved by means of maximum posterior estimation.

where Θ stands for the proposed model parameters. We presumed that each user is specific and their check in information towards the POIs stays independent. The order relation of a given POI pair is independent of the ranking relation of any other POI pairs. Consequently,the likelihood function of all users towards the overall POIs is summarized as (12) shown in the bottom at this page, whereξ(x) stands for the indicator function. Ifxis true, the value ofξ(x) is 1 and ifxis false, the value ofξ(x) equals to 0. While in the formula ofthe quintet (v,l,s,g,w) indicates that uservprefersltos,g,w, shows greater preferences forsthangandw, andgis more preferred thanw.

Due to the totality and antisymmetry of a pairwise ordering scheme, Equation (12) can be simpli fied to.

In this paper, the logistic functionis used to approximatep(·)and the following formula is then obtained.

In order to complete the Bayesian modeling approach of the personalized ranking task, it is assumed in this paper that the general prior probability distribution of the parameter agrees with a normal distribution with zero mean and variance-covariance matrix ΣΘ.And the formula below is obtained:

So far, according to Equation (6) and Equation (11)-(15), the objective loss function of the GSBPR model in this paper is obtained as the formula below:

In Equation (16),the regularization term ofis used to avoid the over fitting in the learning process whereinλΘis the regularization parameter. Finally, the matrix factorization model is used to predict function? in this paper and the formula below is therefore obtained.

According to Equation (17),Qvrepresents the overall latent feature vector matrix ofHlandHs,Hg,Hwstand for the overall latent feature vector matrix of the POIl,s,g,wrespectively.bl,bs,bg,bwrepresent the bias item of the POIs ofl,s,g,w.?represents the dimension of the matrix factorization model. The row vectorqvof each row in the matrixQvcorresponds to the feature vector of each user. And the row vectorshl,hs,hg,hwof each row in the matrixHl,Hs,Hg,Hwcorresponds to the feature vector of each POI.

4.3 Model learning

Similar to the BPR model, we also adopt the widely used stochastic gradient descent (SGD)algorithm to optimize Equation (16) and obtain the following formulas on the basis of Equation (7):

Among them,λqstands for the regularization parameter ofQvandλhrepresents the regularization parameter ofHl,Hs,Hg,Hw,whileλbindicates the regularization parameter ofbl,bs,bg,bw. In the meantime, we updates the model parameters in accordance with the gradients above and the below formula is obtained accordingly.

In Equation (22),γrepresents the learning rate and algorithm 1 is about the description of the procedures of model learning.

4.4 Analyses of time complexity

Algorithm 1 indicates the overall procedure of the learning parameter. In Equation (22), the complexity of update rule isand the total time complexity of the POI recommendation algorithm in this paper isin whichTrepresents the iteration number,stands for the user number and?means the potential dimension number. According to literature [75], the time complexity isif a single user’s preference for a single POI is predicted.

Therefore, it can be concluded that in the GSBPR model, the geographical and social in fluences of the BPR extension model don’t increase much time complexity apart from the certain amount generated in the learning and prediction process. Evidently, the GSBPR model can be regarded as the in-depth creative application of the BPR model in the field of POI recommendation.

V. EXPERIMENTS

To verify the performance to the GSBPR algorithm proposed in this paper, this section mainly presents the experimental results of this algorithm and other relevant algorithms on the basis of real datasets. The datasets and evaluation methods adopted in this paper will be introduced first and several experiments are designed to conduct comparative analyses to the performances of this algorithm from different perspectives.

5.1 Dataset description

The two public datasets chosen for algorithm verification in this paper are Foursquare[62]and Yelp[63] which are well-known large scale location-based social network allowing users to check in different locations. In the experiments of this paper, the similarly as preprocessed in literature [52, 55] is employed and those users and POIs with check in records fewer than 5 times are deleted. According to the unique identification of users and POIs,users’ check in records are assembled and the matrix density of the user-POI in this paper are 2.3×10-4and 1.46×10-4resulted from the dataset of Foursquare and Yelp respectively.

Evidently, both datasets are quite sparse and the statistical information of Foursquare and Yelp are shown in table 1 as follows.

5.2 Evaluation metrics

To evaluate the performances of the POI recommendation algorithm in this paper, four standard evaluation metrics are adopted,namely Precision, Recall, nDCG(Normalized Discounted Cumulative Gain) and MAP(Mean Average Precision).

Suppose the given useru, the formulas ofprecision@kandrecall@kare summarized as follows:

In these two Equations,kstands for the length of the recommendation list;resents the recommendation list for useruprovided by the recommendation algorithm;represents the POI list actually checked in by the useru.

In the experiments of this paper, the precision and recall are estimated withk’s value has been configured as 1, 5, 10 respectively.In each turn, whenk’s value has changed,Precision@kandRecall@kof every algorithm are calculated.

In practice, the closer the POIs get to users’preferences, the higher they rank on the top-k list. As a result, the MAP [81] is de fined as:

In the formulas above,I(k) represents the indicator function indicating whether the POI is related to user preference. If is true, the value is 1, otherwise it is 0.precision@krefers to the precision for top-krecommended POIs.

nDCG [82] is one of the important metrics to evaluate the ranking quality in the field ofinformation retrieval. For the target useru,the larger the value of nDCG is, the more suitable the ranking is for users’ preferences and the more advanced the overall performance of the algorithm is.

Table I. Statistics of the two datasets

In Equation (27),Yurepresents the maximal value of DCG for useru,whereexpresses the graded relevance of the result ranked at the positionnwherein ifrelnequals to 1, it is correlated, otherwise it equals 0.nDCG@kis in the range 0 to 1 and higher value means better results. In the experiments of this paper,k=5 is set forMAP(k) andnDCG@k.Note that fork=10,20, results onMAP(k)andnDCG@kare similar withk=5, and we do not show them.

5.3 Experiment scheme

To test the performance of the algorithm proposed in this paper, the experiments are designed to test the algorithm from three different perspectives so as to verify the superior recommendation quality of the proposed algorithm in this paper.

(1) To compare the GSBPR model with five state-of-the-art POI recommendation algorithm so that the effectiveness and progressiveness of the algorithm in this paper can be veri fied.

(2) To make comparative analyses to the influence on the performances of recommendation systems cast by the two elements of geographical information and social relations.

(3) Because the matrix factorization model is adopted in this paper to derive the final objective function of the rank-oriented POI recommendation model, this paper discusses the impact on the final recommendation performance left by the relevant factorization dimension.

5.4 Baselines

To testify the effectiveness and progressiveness of the proposed algorithm in this paper,we select the following 7 state-of-the-art POI recommendation algorithm for comparative study.

(1) USG[56]: It is proposed in literature[56] that the distances among different POIs checked in by the same users follow the power law distribution and assumed that the check in behaviors of all users follow the power law distribution too.

(2) IRenMF[50]: The literature [50] put forward that the geographical proximity of POIs can be used to model the geographical information and exploits two levels of geographical neighborhood characteristics by integrating the item-based collaborative filtering with matrix factorization.

(3) MGM[55]: It is proposed in literature[55] that the multicenter features of users’check in behaviors can be modeled by the multicenter Gauss model.

(4) BPRMF [75]: The BPR criterion adopts the way of pairwise to rank the POIs so as to cope with the issue of OCCF in the recommendation system. In the experiments of this paper, the strategy of uniform sampling is adopted to sample the user-POI pair training model.

(5) MBPR: Motivated by literatures [75]and [38], users check in behavior in the POIs are modeled by the matrix factorization model on the basis of geographical proximity and the loss function of the matrix factorization model is then optimized by the BPR and fit the user’s ordering on the POIs.

(6) GBPR[83]: On the basis of BPR model extension, the POIs are ranked by integrating the geographical proximity but without considering users’ social relations.

(7) SPRE[84]: Proposed by Long et.al [84],the SPRE is an POI recommendation algorithm which integrates user personalization and social relations into consideration, to learn the social relations by ranking embedding model[85,86] for POI recommendation.

5.5 Parameter settings

The cross validation method is used to test the performance of the proposed algorithm in this paper. Speci fically speaking, 80% of the data in the dataset is used as training data, and 20%as the test data. A total of 5 tests are conducted to ensure that all data is tested once. Finally,the average accuracy is used as the evaluation criterion of the algorithm, so as to ensure the reliability of algorithm veri fication. In order to get more reliable results, we recommend the optimal parameter selection for the final comparative results according to the different parameters settings recommended by referring to the relevant literature or experimental results of the correlation algorithm. In the algorithm of this paper, the learning rateγ=0.05 and then uses the same values for M-BPR, BPR-MF,GBPR, SPRE and GSBPR.

Based on the dimensions of matrix factorization, the value of?, whose in fluence will be discussed in details later, is defined as 30 in this paper. TheMAP(5) andnDCG@5 performance on the validation data is used to select the regularization parameters, which isthe same as in literature [27]. As for the regularization parameter, it is de fined in the dataset of Foursquare thatλq= 0.03,λh= 0.03,andλb= 0.05, while in the dataset of Yelp,λq=0.08,λh= 0.02,andλb= 0.05. In this paper,the standard deviationσis used to sample the normal distribution of the zero mean value whereinσ= 0.1.

Table II. Comparisons between GSBPR model and other models via the metrics of nDCG@5 and MAP(5).

5.6 Experimental results

Due to the low matrix density of user-POI,the precision of POI recommendation is generally not very high. As concluded from the table above, the matrix density of user-POI in these two datasets are separately 2.3×10-4and 1.46×10-4. Therefore, in our experiment,it is common to get low values in precision and recall, and all the contrast models perform better on the Foursquare dataset than on the Yelp dataset. Also, recommending more POIs for users can help users discover more POIs,which is helpful to promote users to check in more POIs. As the number of POIs increases,there will be a constant drop in precision and a constant rise in recall.

Fig. 3. Comparisons between Foursquare-based model and other models in terms of recommendation performance.

Fig. 4. Comparisons between Yelp-based GSBPR model and other models in terms of recommendation performance.

5.6.1 Method comparison

As shown in figure 3, 4 and table 2, we have conducted a comparative study on USG,IRenMF, MGM, BPRMF, MBPR,SPRE and GBPR proposed in this paper.

USG:this method improves the recommendation performance to some extent and integrates user social influence. The method assumes that the distance between multiple POIs meets the power-law distribution. However, due to the differences in users’ check in behaviors in practice, the recommendation performance of USG ranks the last but two, as shown in figure 3, 4 and table 2.

IRenMF:This method assumes that it is more suitable to recommend POIs in geographic neighborhood of the POIs where users have checked in to the users. However, greatly affected by the data sparsity problem, IRenMF also lacks consideration for other contextual information such as social influence and comment text information. Consequently,as shown in figure 3, 4 and table 2, IRenMF ranks the last but one in the recommendation performance list compared with other methods.

MGM:This method assumes that all users’check-in behaviors should follow the multicenter Gaussian distribution. The distance between check-in POIs has been modeled as the distance between central point and POIs.However, this method is devoid of comprehensive and deep analysis to users’ check in behaviors, the final models deviate from users’actual check in behaviors. In fact, the multicenter Gauss distribution is not suitable for modeling user’s check in behaviors, which is also in consistent with the experimental results in literature [36,37,39,63]. As a result, MGM shows the worst recommendation performance compared with several other methods as indicated in figure 3, 4 and table 2.

BPRMF:BPRMF, MBPR, GBPR,SPRE and GSBPR all regard the recommendation problem as the OCCF recommendation, but as revealed in figure 1-2 and table 2, the performance of BPRMF is inferior to MBPR,GBPR,GSBPR, SPRE but superior to USG, MGM and IRenMF in term of all measurements in both datasets. And the two possible explanations are as follows: 1) The fact that BPRMF is superior to USG,MGM and IRenMF precisely verifies the validity of the pairwise preference assumption. 2) MBPR,GBPR,SPRE ,GSBPR perform better than BPRMF because it is still the underlying assumption of BPRMF that users’ check in behaviors follow the Gauss distribution without considering the differences of users check in behavior.

MBPR:MBPR fully considers the geographical proximity of POIs modeled by matrix factorization and fits the order relations of POI pairs by means of ranking in the BPR criterion. The recommendation performance of the POIs can be effectively improved because the regularization factor constrains the process of matrix factorization under the in fluence of geographical proximity. Therefore, as shown in figure 3, 4 and table 2, the MBPR model enjoys better recommendation performance than the models like USG,MGM,IRenMF and BPRMF.

GBPR:Compared with the models mentioned above, the GBPR models deeper-level ranking orders among different POIs. Different from the BPRMF and the MBPR models that only model the ranking order between the observed and unobserved POIs, the GBPR models two ranking orders in the ranking hypothesis which is Equation(8). Obviously,incorporating the geographic neighborhood information in the ordering hypothesis is indeed more effective than the assumption of simple pairwise preferences in BPRMF and MBPR.However, as revealed in figure 1, 2 and table 2, the lack of modeling in user social relations making it rank only the third in the recommendation performance list compared with the GSBPR model.

SPRE: The ranking embedding model which has been put forward in recent years is often used to deal with some sparse data and mine the unobserved data, which has achieved satisfactory effects. The SPRE model maps each user to an object in a low dimensional Euclidean potential space and uses a metric embedding algorithm to effectively compute social relationships so that the social embedding model effectively alleviates the problem of sparse social relations data. However, limited by the fact that the SPRE model considers only the social in fluence without the geographical in fluence in POI recommendation, it only yields the second best recommendation performance compared with the GSBPR model,as illustrated in figure 3, 4 and table 2 above,even if it is on the basis of the most popular rank embedding model extension. This phenomenon also conforms to the conclusions of literatures [63,69]. That is, the impact of geographic in fluence on the final recommendation performance improvement is greater than the social impact, and the integration of multiple context information would greatly enhance the final performance of the POI recommendation.

GSBPR:As shown in figure 3, 4 and table 2, the GSBPR model shows the best performance on the basis of the two datasets. It enjoys significant improvement in comparison with the models mentioned above, which thereby verify the validity of the algorithm in this paper. The reasons are as follows: 1)Compared with the above models, the GSBPR model fully considers the social relations of users based on POIs, and the influence of geographical factors based on the features of geographical neighborhood. As shown in figure 3, 4 and table 2, we can thus see that the assumption of GSBPR by injecting geo-social preference is indeed more effective than that of simple pairwise preference assumed in BPR and the assumption of GBPR by injecting geo-spatial preference; 2) Being ranking learning oriented, the GSBPR model conducts indepth analysis to the social in fluence of users.Compared with the GBPR model, the GSBPR model integrates both the user social relations and the geographical neighborhood information in the ranking hypothesis and eventually transforms the POI recommendation into a three-level ranking model, which effectively enhance the performance of POI recommendation algorithm.

5.6.2 The impact of matrix factorization dimensions

In the process of matrix factorization, the corresponding dimension?will affect the performance of matrix factorization. The larger the dimension, the more time and memory the algorithm will run and the size of the dimension also affects the number of iterations in the optimization process. As a result, it is necessary to study the in fluence on the performance of ranking learning oriented recommendation algorithm left by the factorization dimension.In this section, we show the experimental results. Note that for some experiments, results onMAP(k) andnDCG@kare similar with precision and recall, and we do not show them. As a result, the models BPRMF, MBPR and GBPR are selected to be the contrast methods and prove the in fluence of dimension on the algorithm in this paper in accordance with the measurements ofPrecision@5 andRecall@5.

The experimental results are indicated in figure 5 and figure 6 and this paper only presents the results ofPrecision@5 andRecall@5 on these two datasets. Other measurements show a similar variation trend toPrecision@5 andRecall@5. It can be seen from the figure 5 and figure 6 above that dimension?has a certain impact on the final recommendation results. And the following 3 conclusions can be gained from the two datasets: 1) When the value of?is more than 30,the GSBPR model has a comparatively stable performance without becoming sensitive along with the change of?. This result indicates that for the recommendation tasks, the ranking learning oriented method achieves the best fit the training data, which is in consistent with the conclusions in literature [47]. 2) When the value of?is between 30 and the enlargement of matrix factorization dimensions may also be associated with some problems. For example, after the introduction of noise, the performance of POI recommendation algorithm does not improve as the dimensions enlarge.3) GSBPR consistently outperforms BPRMF,MBPR, and GBPR with the same number of dimensions on two datasets, which further validates the effectiveness of the algorithm in this paper. As a result, the experimental selection of?=30 as default value is reasonable.

Fig. 5. Analysis of the impact of GSBPR model on dimensionality based on Foursquare dataset.

Fig. 6. Analysis of the impact of GSBPR model on dimensionality based on Yelp dataset.

VI. CONCLUSION

With the development of mobile devices and GPS technology, location-based social network is becoming more and more common.As an effective means to alleviate the problem of information overload, POI recommendation systems have been integrated into social networks efficiently. In response to the problem that the current POI recommendation model yields a low performance towards the rating prediction problem. It regards the recommendation problem as a ranking problem, which is inspired by the idea of learning-to-rank in information retrieval field. A new pairwise preference hypothesis is proposed after extending the BPR based learning-to-rank method. The POI recommendation services are explored by transforming the POI recommendation model into a three-level ranking model (GSBPR)through the injection of geo-spatial preference and user social relations into the classic BPR model. With the exploitation of geo-social correlation, a more accurate POI pair order than that generated by the classic BPR model is achieved. Finally, in the real dataset of LBSN,the GSBPR model displays satisfying performance in terms of such metrics as precision,recall, NDCG and MAP and it also outperforms the state-of-the-art POI recommendation algorithms.

As a part of our future work, we aim at selecting a more accurate users’ preference order on POIs by incorporating the sentiment factors extracted from the text information which is evaluated by the user’s POI, or integrating the time factor so as to further enhance the performance of the POI recommendation algorithm.

ACKNOWLEDGEMENTS

This work is supported by National Basic Research Program of China (2012CB719905),National Natural Science Funds of China(41201404) and Fundamental Research Funds for the Central Universities of China(2042018gf0008).