key: cord-0039646-1voqlrvl
authors: Rahmani, Hossein A.; Aliannejadi, Mohammad; Baratchi, Mitra; Crestani, Fabio
title: Joint Geographical and Temporal Modeling Based on Matrix Factorization for Point-of-Interest Recommendation
date: 2020-03-17
journal: Advances in Information Retrieval
DOI: 10.1007/978-3-030-45439-5_14
sha: b09cc4109388b54917a2a07fd6d1d24355baaeb5
doc_id: 39646
cord_uid: 1voqlrvl

With the popularity of Location-based Social Networks, Point-of-Interest (POI) recommendation has become an important task, which learns the users’ preferences and mobility patterns to recommend POIs. Previous studies show that incorporating contextual information such as geographical and temporal influences is necessary to improve POI recommendation by addressing the data sparsity problem. However, existing methods model the geographical influence based on the physical distance between POIs and users, while ignoring the temporal characteristics of such geographical influences. In this paper, we perform a study on the user mobility patterns where we find out that users’ check-ins happen around several centers depending on their current temporal state. Next, we propose a spatio-temporal activity-centers algorithm to model users’ behavior more accurately. Finally, we demonstrate the effectiveness of our proposed contextual model by incorporating it into the matrix factorization model under two different settings: (i) static and (ii) temporal. To show the effectiveness of our proposed method, which we refer to as STACP, we conduct experiments on two well-known real-world datasets acquired from Gowalla and Foursquare LBSNs. Experimental results show that the STACP model achieves a statistically significant performance improvement, compared to the state-of-the-art techniques. Also, we demonstrate the effectiveness of capturing geographical and temporal information for modeling users’ activity centers and the importance of modeling them jointly.

With the availability of Location-based Social Networks (LBSNs) such as Yelp and Foursquare users can share their locations, experiences, and content associated with the Point-of-Interests (POIs) via check-ins. Employing the successes in the area of Recommender Systems (RSs), POI recommendation helps to improve the user experiences on LBSNs, suggesting POIs according to users' past checkin history. POI recommendation helps users explore new interesting POIs while helping businesses to increase their revenues by providing context-aware advertisements. As such, POI recommendation has attracted much attention from both research and industry [4, 6, 22] .

One of the most important challenges that limit the accuracy of POI recommendation is the data sparsity problem [1, 25, 26] . Numerous users are active on LBSNs with millions of POIs already being listed on these platforms. However, in practice, users are able to only visit a very limited number of POIs. Hence, the user-POI matrix used in different Collaborative Filtering (CF) approaches becomes sparse, limiting the attainable recommendation accuracy [3, 24] . To address this problem, several studies have incorporated contextual information such as geographical and temporal influences separately into their model [7, 21, 30, 31] . For example, relevant studies have tried to incorporate geographical [9, 21, 28] and temporal influences [16, 20, 27] in their proposed model. Moreover, as argued in [9] [10] [11] , users commonly check in to POIs around several geographical centers. While modeling these centers it is assumed that they are static and do not change according to temporal information. This assumption may not be correct and taking into account both geographical and temporal influences might help to model the users' behavior with a higher accuracy. For instance, if we consider working time and leisure time, this suggests that users tend to explore POIs around their activity centers in leisure time, while they prefer to visit the same locations more often while they are at work. For example, a person would go to the same restaurant every day to have lunch while working during the weekdays. However, the same user might decide to visit a more diverse set of POIs and visit new places while on holidays (i.e., leisure time). Therefore, the users' check-in behavior and activity centers are dependent on their temporal states (e.g., working time vs. leisure time).

To elaborate more, in Fig. 1 , we have depicted a randomly selected user's check-ins from the Gowalla dataset [22] during working and leisure time. As seen, this user follows a temporal center-based check-in pattern; that is, the activity centers are different at different temporal states. Also, while we compare Fig. 1a with Figs. 1b and c, we see that the activity centers are different from each temporal state, compared to all the check-ins. Based on these observations, we conclude that joint modeling of geographical and temporal information is an effective approach for defining users' activity centers. In this paper, we take a step for joint modeling of geographical and temporal information. Our contributions can be summarized as follows: -We propose a novel contextual model that jointly considers both geographical and temporal information. -We propose a spatio-temporal activity-centers model that consider users' center-based behavior in different temporal states. -We propose static and temporal MF models to study the users' preference and behavior both in static and temporal manners. In the static MF, we train the model on the whole user-POI matrix, whereas in the temporal MF, we train the model using different user-POI matrices for every time slot. -We address the data sparsity problem by incorporating the proposed contextual model into the traditional MF model and propose a novel MF framework.

We conduct several experiments on two well-known real-world datasets, namely, Gowalla and Foursquare, demonstrating the improvement of the proposed method in the accuracy of POI recommendation compared to a number state-of-the-art approaches. Our experiments show that joint modeling of the geographical and temporal influence improves the performance of POI recommendation. Finally, to enable reproducibility of the results, we have made our codes open source. 1

POI recommendation plays an essential role in improving LBSNs user experience. Much work has been carried out in this area based on the core idea behind recommendation systems, assuming that users with similar behavioral histories tend to act similarly [28] . Collaborative Filtering (CF-based) recommendation approaches aim to base recommendations on the similarity between users and items [14, 16] . POI recommendation considers a large number of available POIs (items) while a single user can only visit a few of them. Hence, CF-based approaches applied to POI recommendation often suffer from the data sparsity problem. This leads to poor performance in POI recommendation. Many studies have tried to address the data sparsity problem of CF approaches incorporating additional information into the model [5, 21, 22, 28] . As the users' check-in behavior follows a spatio-temporal mobility pattern, much work has incorporated this critical information. Considering users' movement trajectories between POIs, many of the previous studies have shown that geographical influence is one of the most important factors in POI recommendation [22, 24] .

More specifically, Ye et al. [28] argued that a user's check-in behavior is affected by the geographical influence of POIs, following the power-law distribution and proposed a unified POI recommender system incorporating spatial and social influences to address the data sparsity problem. Ference et al. [14] took into consideration several factors such as user preference, geographical proximity, and social influences for out-of-town POI recommendation. This work, however, did not take into account users' temporal information and in-town users' behavior. Cheng et al. [9, 10] modeled users' check-ins via center-based Gaussian distribution to capture users' movement patterns based on the assumption that users' movements consist of several centers. Li et al. [21] , in another work, modeled the POI recommendation task as a pairwise ranking loss, where they exploited the geographical information using an extra factor matrix. Zhang et al. [31] proposed a method that considered the geographical influence on each user separately. To this end, they proposed a model based on kernel density estimation of the distance distributions between POI check-ins per user. Aliannejadi et al. [2] proposed a ranking model and predicted the appropriateness of a POI given a user's context into the ranking process. Yuan et al. [29] addressed the data sparsity problem based on the idea that users tend to rank higher those POIs that are geographically closer to their visited POIs. Guo et al. [17] proposed a location neighborhood-aware weighted matrix factorization model to exploit the location perspective that incorporates the geographical relationships among POIs. More recently, Aliannejadi et al. [6] proposed a two-phase collaborative ranking algorithm for POI recommendation that takes into account the geographical influence of POIs in the same neighborhood.

Another line of research studies the temporal influence on users' preferences [13, 30, 32] . Temporal information has been shown to improve POI recommendation accuracy and alleviate the problem of data sparsity [22] . Griesner et al. [16] proposed an approach to integrate temporal influences into matrix factorization. Gao et al. [15] computed the similarity between users by dividing users' checkins into different hourly time slots and finding the same POIs at the same time slots in their check-in history to train a user-based CF model. Yao et al. [27] matched the temporal regularity of users with the popularity of POIs to improve a factorization-based algorithm. Le et al. [20] proposed a time-aware personalized model adopting a fourth-order tensor factorization-based ranking, which enables to capture short-term and long-term preferences. Yuan et al. [30] preserved the similarity of personal preference in consecutive time slots by considering different latent variables at each time slot per user. Zhao et al. [33] proposed a latent ranking method to model the temporal interactions among users and POIs explicitly. In particular, the proposed model builds upon a ranking-based pairwise tensor factorization framework.

These previous approaches mainly explored the geographical and temporal information separately. Differently from these studies, our work addresses the data sparsity problem by jointly modeling the geographical and temporal contextual information. Moreover, the previous research modeled users' center-based behavior based on geographical influence. In contrast, we consider the formation of spatio-temporal activity centers for each user. Therefore, we model the users' center-based behavior based on different temporal states.

In this section, we propose a Spatio-Temporal Activity Center POI recommendation model called STACP, which models users' preference and users' context together. In the users' preference model, we design two preference functions for each user to consider both static and temporal users' preferences in the model. Moreover, in the users' context model, we incorporate the influence of geographical and temporal information jointly. In what follows, we first describe an overview of our STACP model and further explain how each part is implemented and which challenges are addressed at each part.

Formally, let U = {u 1 , u 2 , u 3 , ..., u m } be the set of users and L = {l 1 , l 2 , l 3 , ..., l n } be the set of POIs. Further, let m and n be the number of users and POIs, respectively. Then, the users visit-frequency can be encoded in R m×n , where entries r u,l ∈ R can represent the previous POI check-ins of user u ∈ U to POI l ∈ L. Also, L u shows all POIs checked-in by user u. To address the data sparsity problem and explore the contextual influence we need to fuse the users' context with the users' preference model in a fusion framework. We fuse users' static and temporal preferences on a POI and the score of whether a user will visit that place based on our contextual influence model. STACP is proposed to estimate the recommendation score that a user u visits a POI l as follows:

where U T u L l andR u,l respectively denote static and temporal users' preference model, and P (u, l|C u,t ) denotes the users' context model.

In the following, we first introduce the user context model, where we show users' behavior in a joint model of geographical and temporal influences. Moreover, we propose our temporal center allocation method. Finally, we describe our users' static and temporal preference model. Fig. 1 , users' behaviors are center-based and these centers are different based on the periodicity of temporal information (see Fig. 1b and c) . This phenomenon points to the shortcoming of the previous geographical and temporal models that considered geographical and temporal influences separately. As shown previously, the second characteristic of users' behavior is that users tend to visit POIs that are near their current centers. We apply these two characteristics jointly to model users' check-in behavior and propose the spatio-temporal activity-centers model. That is, the score of a user u, visiting a POI l, given the temporal multi-center set C u,t of user u in time t and temporal state T , is defined as follows:

where l denotes a POI and C u,t is the set of centers for the user u in time t, given the temporal state T . For each center, calculating (2) consists of the multiplication of two terms. The first term determines the score of the POI l belonging to the center c u,t , which is related to the distance between the POI l and the center c u,t . The second term denotes the effect of check-in frequency freq cu,t , on the center c u,t .

Further, we define the multi-center activity function P (u, l|C u,t ) as a linear interpolation under two temporal states, as follows:

where we consider it for working time P (u, l|C u,t ; W T ) and leisure time P (u, l|C u,t ; LT ) where λ shows the impact of each temporal state. The model can be generalized to define other temporal states. For example, we could apply it for weekday/weekend, monthly, or daily patterns.

As argued earlier, the users' activities follow a center-based pattern. Furthermore, these centers are different depending on the temporal state. To model the users' behavior in a spatio-temporal manner, we propose a temporal multi-center clustering algorithm among each user's checkins based on the Pareto principle [18] , as the most visited POIs account for a few users. First, for each user u and temporal state t, we rank all POIs L u according to the check-in frequency. Next, we select the most visited POI and combine all other visited POIs within d kilometers from the selected POI, to create a region. Let N u be the user u's total check-in numbers, r be the current region and N r,u be the total check-in number of current region of user u. To decide if a center should be added to the user's profile, we consider a threshold of α. A new center is considered if Nr,u Nu > α. We repeat this procedure until we cover all of the user u's checked-in POIs.

To model the user's preference based on check-in data, we apply Matrix Factorization (MF) in two ways: a static model of user's preference (SMP) and a temporal model of user's preference (TMP). In SMP, we consider the traditional matrix factorization method to model the static behavior of users. The goal of MF is to find two low-rank matrices U ∈ R K×|U | and L ∈ R K×|L| based on the frequency matrix R such that R ≈ U T L. The predicted recommendation score of a user u, like a POI l, is determined by:

via solving the following optimization problem which places Beta distributions as priors on the latent matrices U and L, while defining a Poisson distribution on the frequency:

where σ = {σ 1 , ..., σ K } and ρ = {ρ 1 , ..., ρ K } are parameters for Beta distributions, and c is a constant term. In TMP, to model the temporal behavior of users, inspired by [15] , we divide the original user-POI frequency matrix R into t sub-matrices according to the different temporal states T . Then each sub-matrix only containing check-in actions that happened at the corresponding temporal state. For example, we can consider t = 2 for working time and leisure time in our case. Then, we apply MF on each R t to compute user u's preference on POI l at time t. Finally, we sum them intoR, representing the user check-in preferences of each POI. It should be mentioned that a more advanced method of automated periodic pattern extraction from spatio-temporal data as proposed in [8] can also be used for a more data-informed decision to be made for the parameter (t).

In this section, several experiments are conducted to compare the performance of STACP with the other state-of-the-art POI recommendation methods.

Datasets. We use two real-world check-in datasets from Gowalla and Foursquare provided by [ as validation data. We determine the statistically significant differences in the results using the two-tailed paired t-test at a 95% confidence interval (p < 0.05). -TopPopular [12] : A simple and non-personalized method that recommends the most popular POIs to users. Popularity is measured by the number of check-ins. -PFM [23] : A MF method, which can model the frequency data directly.

PFM places Beta distributions as priors on the latent matrices U and V , while defining a Poisson distribution on the frequency. -PFMMGM [9] : A method based on the observation that a user's check-ins follow a Gaussian distribution that combines geographical and social influence with MF. -LRT [15] : A method that incorporates temporal information in a latent ranking model and learns the user's preferences based on temporal influence. -PFMPD: A geographical method using the Power-law distribution [28] that models people's tendency to visit nearby POIs. We integrate this geographical model with the Probabilistic Factor Model (PFM). -LMFT [26] : A method that applies temporal information on the user's recent activities and multiple visits to a POI. -iGLSR 3 [31] : A method that personalizes social and geographical influences on POI recommendation using a Kernel Density Estimation (KDE) approach. -Rank-GeoFM [21] : A ranking-based MF model that includes the geographical influence of neighboring POIs while learning user preference rankings for POIs. -MLP [19] : A component of the NeuMF framework that models the user-POI interaction using the concatenation of latent factors via Multi-layers Neural Network. -L-WMF [17] : A location neighborhood-aware weighted probabilistic matrix factorization model. L-WMF incorporates the geographical relationships among POIs as regularization to exploit the geographical characteristics from a location perspective. -STMCP-NoCTX: A variation of our model which excludes the contextual model. We include this model as a baseline to demonstrate the effectiveness of our contextual model. -STMCP-NoTC: A variation of our model in which we remove the temporal states and consider geographical centers without temporal differences. We include this model to show the effectiveness of temporal centers in our model.

Performance Evaluation Against Compared Methods. Table 1 shows the results of experiments based on the Gowalla and Foursquare datasets. As seen, STACP obtains the best performance compared to the other POI recommendation methods in terms of all evaluation metrics on both of the datasets. Dacrema et al. in [12] show that even some state-of-the-art deep-learning-based methods are not able to outperform a non-personalized method such as TopPopular. This is the reason why we have also selected this method as a baseline to compare with STACP. It seems that in comparison to two non-personalized baseline methods, TopPopular and PFM, our method achieves significantly better performance. Comparing with other geographical-based methods, PFMPD, PFMMGM, iGLSR, and L-WMF, it is seen that STACP followed by Rank-GeoFM perform best. One reason for the performance of Rank-GeoFM is that it considers the geographical neighborhoods as a major element in the factorization method. Also, Rank-GeoFM takes a ranking approach to modeling the interactions between users and POIs. This means that instead of considering a point-wise loss function, it applies a pairwise loss function in geographical factorization.

Results show that STACP beats all geographical-based methods in terms of all metrics for all different values of N in both datasets. This is expected as the previous models only consider the basic idea of the geographical influence that users tend to visit nearby POIs. Also, our proposed model outperforms the LRT and LMFT that modeled temporal information to improve the accuracy of POI recommendation. The reason is that these methods do not consider the geographical information. Compared to the neural baseline, MLP, the improvements of STACP in terms of Recall@20 and nDCG@20 on Gowalla dataset are 65% and 66%, respectively. This shows the effectiveness of our users' preference and users' context models, which considers both geographical and temporal information jointly to model users' activity centers.

Effect of Activity Centers. In this experiment, we compare the performance of STACP with its variation where we only consider geographical information in allocating activity centers (i.e., STACP-NoTC). Therefore, we remove temporal states t from Eq. (2) . The goal is to demonstrate the effect of the spatio-temporal activity centers on the performance of STACP. As seen in Table 1 , STACP exhibits a significant improvement over STACP-NoTC in terms of all evaluation metrics for both datasets. We see that STACP improves STACP-NoTC by 42% in terms of Recall@20. This indicates that users follow a spatio-temporally centered behavior. This objectively validates our analysis in Sect. 1, in which users' centers are different based on the different temporal states.

Effect of Contextual Model. Next, we study the effect of the contextual model. To this end, we compare the performance of STACP with its variation where no contextual information is used while training the model (i.e., STACP-NoCTX). In other words, in this experiment Eq. (2) is excluded from Eq. (1). As seen in Table 1 , a statistically significant improvement of STACP over STACP-NoCTX is observed in terms of all evaluation metrics on both datasets. This observation suggests that using contextual information enables STACP to model the users' behavior more accurately. Moreover, it indicates that by incorporating the contextual information, we can address the data sparsity problem.

In this experiment, our goal is to study the effect of data size on the performance of our model. As such, we train STACP, as well as all the baseline methods with different data sizes. To do so, for each user, we only consider a certain percentage of visited POIs in the training set randomly, ranging from 40% to 100%. We see in Figs. 2a and b the performance of STACP and all baseline models in terms of nDCG@20 for different training data sizes. The results show that STACP is more effective in comparison with the baselines as the size of the training data varies, indicating that it addresses the data sparsity problem more effectively. As we see in Fig. 2a , when we change the data size from 100% to 40% on Gowalla, the performance of STACP decreases by about 35%, while for the competitor baseline method Rank-GeoFM the value of decrease is 45%. This shows that STACP is more robust when we do not have access to enough data from users. More interesting, the performance of LMFT, a temporal-information-based competitor baseline, decreases by 65% when the size of data changes to 40%. This indicates the unsuitability of the methods that only consider the temporal information. Also, it is worth noting that we observe a more robust behavior of STACP compared to the STACP-NoCN. Thus, the proposed context model enables STACP to deal with noise and data sparsity more effectively. This is clearer when STACP outperforms the best competitor baseline (i.e., Rank-GeoFM) with a larger margin, 33%, in terms of nDCG@20 on Gowalla. Figure 3 shows the performance of STACP for different values of d, α and λ. We report in Fig. 3a the effect of different values of d on the performance of STACP in terms of Precision@20 and Recall@20 metrics, respectively. It can be seen that the optimal value of d for both datasets is 15. These results show that users tend to visit nearby POIs to their centers, which are formed in regions. Figure 3b , on the other hand, shows the effect of different α values on the performance of STACP. We can see that the optimal value is achieved at α = 0.02 for both datasets. More importantly, as seen in Fig. 3c , the optimal value for λ that shows the impact of different temporal states is 0.5. This confirms our assumption and shows that users follow a spatio-temporal activity centered behavior. In fact, when we set this parameter to 1 (i.e., just working time) or 0 (i.e., just leisure time), the performance decreases.

In this paper, we study the problem of POI recommendation. We have investigated in detail the characteristics of the user mobility behavior on a large-scale check-in dataset. Based on the extracted properties, we propose a novel spatiotemporal activity-centers model to jointly model the geographical and temporal influence of the user's check-in behavior. We then consider the user's temporal information and the user's preferences on POIs. Finally, we propose the STACP model as a uniform framework for combining these three components to recommend POIs. Experimental results on the datasets show that our model significantly outperforms the state-of-the-art models. In our future work, we may consider more information such as the user's comments and social relations to improve the performance.

Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions

Venue appropriateness prediction for personalized context-aware venue suggestion

Personalized context-aware point of interest recommendation

A cross-platform collection for contextual suggestion

Personalized keyword boosting for venue suggestion based on multiple LBSNs

A joint two-phase time-sensitive regularized collaborative ranking model for point of interest recommendation

GeoTeCS: exploiting geographical, temporal, categorical and social aspects for personalized POI recommendation

Recognition of periodic behavioral patterns from streaming mobility data

Fused matrix factorization with geographical and social influence in location-based social networks

A unified point-of-interest recommendation framework in location-based social networks

Friendship and mobility: user movement in location-based social networks

Are we really making much progress? A worrying analysis of recent neural recommendation approaches

Time weight collaborative filtering

Location recommendation for out-of-town users in location-based social networks

Exploring temporal effects for location recommendation on location-based social networks

POI recommendation: towards fused matrix factorization with geographical and temporal influences

Location perspective-based neighborhood-aware POI recommendation in location-based social networks

Neural collaborative filtering

A time-aware personalized point-of-interest recommendation via high-order tensor factorization

Rank-GeoFM: a ranking based geographical factorization method for point of interest recommendation

An experimental evaluation of pointof-interest recommendation in location-based social networks

Probabilistic factor models for web site recommendation

LGLMF: local geographical based logistic matrix factorization model for POI recommendation

Category-aware location embedding for point-of-interest recommendation

Incorporating spatial, temporal, and social context in recommendations for location-based social networks

POI recommendation: a temporal matching between POI popularity and user regularity

Exploiting geographical influence for collaborative point-of-interest recommendation

Joint geospatial preference and pairwise ranking for point-of-interest recommendation

Time-aware point-ofinterest recommendation

iGSLR: personalized geo-social location recommendation: a kernel density estimation approach

Geo-Teaser: geo-temporal sequential embedding rank for point-of-interest recommendation

STELLAR: spatial-temporal latent ranking for successive point-of-interest recommendation

Acknowledgment. This work was partially supported by a Swiss State Secretariat for Education, Research and Innovation (SERI) mobility grant between Switzerland and Iran.