---
abstract: 'The wide spread of location-based social networks brings about a huge volume of user check-in data, which facilitates the recommendation of points of interest (POIs). Recent advances on distributed representation shed light on learning low dimensional dense vectors to alleviate the data sparsity problem. Current studies on representation learning for POI recommendation embed both users and POIs in a common latent space, and users’ preference is inferred based on the distance/similarity between a user and a POI. Such an approach is not in accordance with the semantics of users and POIs as they are inherently different objects. In this paper, we present a novel spatiotemporal aware (STA) representation, which models the spatial and temporal information as *a relationship connecting users and POIs*. Our model generalizes the recent advances in knowledge graph embedding. The basic idea is that the embedding of a $<$time, location$>$ pair corresponds to a translation from embeddings of users to POIs. Since the POI embedding should be close to the user embedding plus the relationship vector, the recommendation can be performed by selecting the top-*k* POIs similar to the translated POI, which are all of the same type of objects. We conduct extensive experiments on two real-world datasets. The results demonstrate that our STA model achieves the state-of-the-art performance in terms of high recommendation accuracy, robustness to data sparsity and effectiveness in handling cold start problem.'
author:
- |
    Bei Liu[$~^{1}$]{}, Tieyun Qian[$~^{1}$]{}, Bing Liu[$~^{2}$]{}, Liang Hong[$~^{3}$]{}, Zhenni You[$~^{1}$]{}, Yuxiang Li[$~^{1}$]{}\
    [$~^{1}$]{} State Key Laboratory of Software Engineering, Wuhan University, China\
    [$~^{2}$]{} Department of Computer Science, University of Illinois at Chicago, USA\
    [$~^{3}$]{} School of Information Management, Wuhan University, China\
    {qty, beiliu}@whu.edu.cn, liub@cs.uic.edu, {hong, znyou, liyux}@whu.edu.cn\
title: 'Learning Spatiotemporal-Aware Representation for POI Recommendation'
---

Introduction
============

Location-based social networks (LBSN), such as Foursquare, Yelp, and Facebook Places, are becoming pervasive in our daily lives. Users on LBSN like to share their experiences with their friends for points of interest (POIs), e.g., restaurants and museums. The providers of location-based services have collected a huge amount of users’ check-in data, which facilitates the recommendation of POIs to unvisited users. The POI recommendation is of high value to both the users and companies, and thus has attracted much attention from researchers in recent years [@Cheng_tist16; @Zhu_kdd15; @Chen_aaai15; @Gao_aaai15].

Most existing studies mainly focused on leveraging spatial information due to the well-known strong correlation between users’ activities and geographical distance  [@Zheng_www09; @Ye_gis10; @Cho_kdd11]. For example, Ye et al.  proposed a Bayesian collaborative filtering (CF) algorithm to explore the geographical influence. Cheng et al.   captured the geographical influence by modeling the probability of a user’s check-in on a location as a multi-center Gaussian model and then combined it into a generalized matrix factorization model. Lian et al.   adopted a weighted matrix factorization framework to incorporate the spatial clustering phenomenon.

Similar to the geo-spatial information, time is another important factor in POI recommendation. Ye et al.,   found the periodic temporal property that people usually go to restaurants at around noon and visit clubs at night. Yuan et al.,   developed a CF based model to integrate temporal cyclic patterns. Cheng et al.  [@Cheng_ijcai13] explored the temporal sequential patterns for personalized POI recommendation by using the transition probability of two successive check-ins of a user.

Existing studies has exploited spatial or temporal influences mainly using CF  [@Ye_sigir11; @Yuan_sigir13] and Markov transition approaches [@Cheng_ijcai13]. Due to the sparsity of users’ check-in records, it is hard to find similar users or calculates transition probability. Although matrix factorization (MF) methods are effective in dealing with the sparsity in user-POI matrix  [@Cheng_aaai12; @Lian_kdd14], they do not consider the current location of the user. More importantly, while time and location together play a critical role in determining users’ activities in LBSNs, rare work has modeled their joint effects. Considering only one factor will deteriorate the predictive accuracy. For instance, a student may go to a school cafeteria or to a food court in a mall at lunch time depending on he/she is on campus or outside. It is not suggested for a system to recommend the same restaurant to a user at the same time but different location. This example shows the ineffectiveness when using one type of information but ignoring the other. However, taking both time and location into consideration exaggerates the data sparsity.

In this paper, we propose a novel spatiotemporal aware (STA) model, which captures the joint effects of spatial and temporal information. Our model has the following distinct characteristics.

-   STA takes location and time as a whole to determine the users’ choice of POIs.

-   STA embeds a spatiotemporal pair $<$time, location$>$ as *a relationship* connecting users and POIs.

By considering the time and location at the same time, our model can be successfully applied to real-time POI recommendation. Furthermore, distributed representations of STA are very effective in solving the problem of data sparsity.

Two recent works  [@Feng_ijcai15; @Xie_cikm16] also exploited the power of distributed representation for alleviating data sparsity. The personalized ranking metric embedding (PRME) by Feng et al.   projected each POI and each user into a latent space, and then recommended a POI $v$ to a user $u$ at location $l$ based on the Euclidean distance between the POI and the user $\parallel\vec{u}-\vec{v}\parallel^2$ and that between the POI and the location $\parallel\vec{l}-\vec{v}\parallel^2$. Xie et al.  proposed a graph based embedding model (GE) by embedding graphs into a shared low dimensional space, and then computed the similarity between a user $u$’s query $q$ at current time $t$ and location $l$ and a POI $v$ using an inner product, $S(q,v)=\vec{u}^T\cdot\vec{v}+\vec{t}^T\cdot\vec{v}+\vec{l}^T\cdot\vec{v}$. While PRME, especially GE, shows significant improvements over many other baselines, these two methods have the drawback that they embed both users and POIs in a common latent space, and users’ preference is inferred based on the distance/similarity between a user and a POI. Such an approach is unnatural since users and POIs are inherently different objects. In contrast, our STA model generalizes recent advances in knowledge graph embedding  [@Lin_aaai15]. A user $u$ reaches an interested POI $v_q$ via an edge $tl$ denoting the $<$time, location$>$ pair, i.e., $\vec{u} + \vec{tl} \approx \vec{v_q}$. With this transformation, we can do recommendation for $u$ by selecting the top-*k* POIs similar to POI $v_q$, which are all of the same type of objects with similar semantics.

Problem Definition and Preliminary
==================================

Definition 1. (***POI***) A POI *v* is defined as a unique identifier representing one specific position (e.g., a cafe or a hotel), and *V* is a set of POIs, i.e., $V=\{v|v=(pid, position)\}$.

Definition 2. (***Check-in Activity***) A check-in activity is a quadruple (u, t, l, v), which means a user *u* visits a POI *v* in location *l* at time *t*.

Definition 3. (***Spatiotemporal pattern***) A spatiotemporal pattern, denoted as *tl*, is a combination of a time slot *t* and a location *l* like $<$11 a.m., Los Angeles$>$. For ease of presentation, we summarize the notations in Table \[tbl:note\]. The POI recommendation problem investigated in this paper has the same settings as that in  [@Xie_cikm16]. The formal problem definition is as follows.

[c|c]{} Variable & Interpretation\
*u*, *v* & the user *u* and POI *v*\
*t* & the time slot discretized from timestamp\
*l* & the location mapped from (longitude, latitude)\
*tl* & the spatiotemporal pattern $<$t, l$>$\
$\vec{u}$,$\vec{tl}$,$\vec{v}$ & embeddings of *u*, (*t,l*), and *v*\
$u_q$, $t_q$, $l_q$ & query user $u_q$, his/her current time $t_q$ and location $l_q$\
$v_q$ & the potential POI that query user $u_q$ is interested in\

**Problem Definition** (Location-based Recommendation) Given a dataset $D=\{d|d=(u,t,l,v)\}$ recording a set of users’ activities, and a query $q=(u_q, t_q, l_q)$, we aim to recommend top-*k* POIs in *V* that the query user $u_q$ would be interested in.

**Preliminary - KG Embedding** The knowledge graph (KG) is a directed graph whose nodes and edges describing *entities* and their *relations* of the form (*head, relation, tail*), denoted as (*h, r, t*). The goal of knowledge graph embedding is to learn a continuous vector space where the embeddings of entity and relation can preserve certain information of the graph. Bordes et al.  presented a simple yet effective approach TransE to learn vector embeddings for both entities and relations in KG. The basic idea is that the relationship between entities corresponds to a translation the embeddings of entities, namely, $\vec{h}+\vec{r}\approx\vec{t}$ when (*h ,r, t*) exits in graph. Later, a model named TransH [@Wang_aaai14] was proposed to enable an entity to have distinct representations when it is involved in different relations.

Both TransE and TransH project all entities and relations into the same space. However, some entities may have multiple aspects and relations focusing on different aspects of the entities. Such entities are close in the entity space when they are similar, but they should be far away from each other in the relation space if they are strongly different in some specific aspects. To address this issue, Lin et al.  presented a TransR model to project two entities *h* and *r* of (*h,r,t*) into a *r*-relation space as $h_r$ and $t_r$ with operation $M_r$, such that $\vec{h_r}+\vec{r}\approx\vec{t_r}$ holds in the relation space.

Our Proposed Framework
======================

We seek to learn the representations with the following characteristics.

-   Spatiotemporal awareness - Location and time together play a crucial role when a user selects a POI; they should not be separated into individual ones.

-   Semantics consistency - All the POIs, either the query user’s interested POI $v_q$ or all existing POIs $v \in V$, should come from a consistent semantic space.

In order to satisfy the first requirement, we combine each time slot and location as a spatiotemporal pattern $<$*t*, *l*$>$, and convert the quadruples $(u,t,l,v) \in D$ into triples ($u$, $<$$t$, $l$$>$, $v$) in $D'$. We then learn representations for users, spatiotemporal patterns, and POIs from the converted set $D'$ to meet the second condition, using the translation technique originated from knowledge graph embedding.

STA model
---------

For the location-based recommendation problem, we focus on the connections between users and POIs corresponding to the spatiotemporal relations. Intuitively, if a POI *v* is often visited by similar users in location *l* at time *t*, the probability of a query user $u_q$ visiting *v* with the same spatiotemporal relation will be high. On the other hand, users similar in the entity space may visit different POIs under distinct temporal and geographic conditions. In order to capture the strong correlations of users and POIs to the spatiotemporal patterns, we generalize the TransR technique  [@Lin_aaai15] to fit the POI recommendation task. The basic idea is that a user $u$ will reach an interested POI $v_q$ via a translation edge $tl$, i.e., $\vec{u} + \vec{tl} \approx \vec{v_q}$. Fig. \[fig:relation\] illustrates the impacts of *tl* patterns.

![Impacts of spatiotemporal patterns[]{data-label="fig:relation"}](relation3.eps){width="68.00000%" height="4.2cm"}

In Fig. \[fig:relation\], suppose $u_1$, $u_q$, and $u_2$ are three university students, $u_1$ and $u_q$ taking same courses, and $u_2$ and $u_q$ sharing the dormitory. Given two patterns $tl_1=<12 a.m., campus>$ and $tl_2=<8 p.m., dormitory>$, the query user $u_q$ will be translated into two POIs $v_{q1}$ and $v_{q2}$, hence we should recommend for $u_q$ the POI $v_1$ in the left lower sub-figure and $v_2$ in the right lower sub-figure, which are the close neighbor of $v_{q1}$ and $v_{q2}$, respectively. The different recommending results $v_1$ and $v_2$ are caused by the effects of different spatiotemporal relations $tl_1$ and $tl_2$.

We now introduce the detail for STA. For each triple ($u$, $<$$t$, $l$$>$, $v$) in $D'$, the user $u$, the spatiotemporal pair $<$$t$, $l$$>$ ($tl$ in short), and POI $v$ corresponds to the head entity *h*, the relationship edge *r* and the tail entity *t* in TransR, respectively. Their embeddings are set as $\vec{u}$, $\vec{v}$ $\in$ $\Re^d$, and $\vec{tl}$ $\in$ $\Re^m$. For each spatiotemporal pair $tl$, we set a projection matrix $M_{tl} \in \Re^{d\times m}$ to project a user embedding $\vec{u}$ and a POI embedding $\vec{v}$ in the original entity space to $\vec{u_{tl}}=\vec{u}M_{tl}$ and $\vec{v_{tl}}=\vec{v}M_{tl}$ in the relation space, such that $\vec{u_{tl}} + \vec{tl} \approx \vec{v_{tl}}$. This indicates that a POI embedding $\vec{v_{tl}}$ should be the nearest neighbor of $\vec{u_{tl}} + \vec{tl}$. Hence the the score function can be defined as: $$\begin{aligned}
\label{score}
\small
  \nonumber s_{tl}(u, v) = \parallel \vec{u_{tl}} + \vec{tl} - \vec{v_{tl}} \parallel _2^2\\
  \nonumber   s.t. \parallel \vec{u} \parallel _2 \leq 1, \parallel \vec{v} \parallel _2 \leq 1, \parallel \vec{tl} \parallel _2 \leq 1,  \\
   \parallel \vec{u_{tl}} \parallel _2 \leq 1, \parallel \vec{v_{tl}} \parallel _2 \leq 1\end{aligned}$$

Given the score function defined in Eq. \[score\] for a triple ($u$, $tl$, $v$), the entire objective function for training is as follows. $$\label{obj}
\small
    L = \sum_{(u,tl,v) \in T} \sum_{(u',tl,v') \in T'} max(0, s_{tl}(u, v) + \gamma - s_{tl}(u', v')),$$ where max(*a*,*b*) is used to get the maximum between *a* and *b*, $\gamma$ is the margin, *T* and *T’* are the sets of correct and corrupted triples, respectively. The corrupted triples are generated by replacing the head and tail entities in correct triples using the same sampling method as that in [@Wang_aaai14].

We adopt stochastic gradient descent (SGD) (in mini-batch mode) to minimize the objective function in Eq. \[obj\]. A small set of triplets, is sampled from the training data. For each such triplet, we sample its corresponding incorrect triplets. All the correct and incorrect triples are put into a mini-batch. We compute the gradient and update the parameters after each mini-batch. When the iteration reaches a predefined number, we learn all the embedding for users, POIs, and spatiotemporal patterns.

Recommendation Using STA
------------------------

Once we have learned the embeddings, given a query user $u_q$ with the query time $t_q$ and location $l_q$, i.e., *q* = ($u_q$, $t_q$, $l_q$), we first combine $t_q$ and $l_q$ as a spatiotemporal pattern $tl_q$, and then we can get the potential POI $v_q$ using Eq. \[querypoi\]. $$\label{querypoi}
\small
   %\vec{v_{tlq}} = \vec{u_{tlq}} + \vec{tl_q}
   \vec{v_q} = \vec{u_q} M_{tl} + \vec{tl_q}$$

The learned POI embedding $v_q$ naturally reflects the user’s preference, because it encodes the users’ past activities in $\vec{u_q}$. It also captures the geographic and temporal influence in $\vec{tl_q}$.

For each POI $v \in V$, we compute its distance to the POI $v_q$ in the normed linear space as defined in Eq.  \[simpoi\], and then select the *k* POIs with the smallest ranking scores as recommendations. $$\label{simpoi}
\small
   %d(v_{tl}, v_{tlq}) = \parallel \vec{v_{tl}} - \vec{v_{tlq}} \parallel_1
   d(v, v_q) = \parallel \vec{v} M_{tl} - \vec{v_q} \parallel_1$$

We would like to emphasize our differences in computing $v_q$ and recommending POIs from those in  [@Lin_aaai15; @Xie_cikm16]. First, we can find an explicit POI $v_q$ directly from the latent space through the translation of the embedding of the spatiotemporal pattern on the user’s embedding, while others compute an implicit $v_q$ by its distance/similarity to user $u_q$. Second, since the embeddings for POIs in *V* are also from the same space, we can choose the ones which are the closest neighbors of $v_q$ in this space. This indicates that our recommended POIs are semantically consistent with the query user’s interested POI $v_q$.

Dealing with Cold Start POIs
----------------------------

Considering the cold start POIs, which contain geographic and content information like tags but do not have any check-ins [@Xie_cikm16], we can simply extend our model to include the POI-POI relationship through the translation of content patterns. We call this model STA-C. The rationale is that, if two POIs share a common tag or location, there will be a high degree of similarity between them, and their vector representations should be close to each other. Based on this observation, we define the score function as following:

$$\label{scorecold}
\small
\begin{aligned}
\begin{split}
s_{tlw}(u, v, s)  & = s_{tl}(u, v) + s_{wl}(v, s) \\
    %& = s_{tl}(u, v) + s_{w}(v, s) \\
    & = \parallel \vec{u_{tl}} + \vec{tl} - \vec{v_{tl}} \parallel _2^2 + \parallel \vec{v_{wl}} + \vec{wl} - \vec{s_{wl}} \parallel _2^2,
\end{split}
\end{aligned}$$

where *s* is a POI sharing at least one $<$word, location$>$ pair with POI *v*, and the objective function for cold start POIs is defined as:

$$\label{objcold}
\small
\begin{aligned}
\begin{split}
    LC = & \sum_{(u,tl,v) \in T} \sum_{(u',tl,v') \in T'} max(0, s_{tl}(u, v) + \gamma - s_{tl}(u', v')) + \\
    & \sum_{(v,wl,s) \in W} \sum_{(v',wl,s') \in W'} max(0, s_{wl}(v, s) + \gamma - s_{wl}(v', s'))
\end{split}
\end{aligned}$$

We once again use stochastic gradient descent to minimize the objective function *LC* in Eq. \[objcold\]. The only difference is the sampling procedure. For STA-C, since we have two types of edges, we sample the triplets (u, tl, v) and (v, wl, s) and their corresponding incorrect triples alternatively to update the model.

Our STA-C model proposed for dealing with cold start POIs can also be applied to the normal POI recommendation problem. However, it requires that those POIs should contain content information. For the recommendation on datasets like Gowalla, STA-C is not valid. Hence we only treat it as an extended model. Please also note that, it is STA-C that uses the same information as GE does. Our standard STA model, on the other hand, uses less information than GE because it does not include the contents of POIs.

Experimental Evaluation
=======================

In this section, we first introduce the experimental setup and then compare our experimental results with those of baselines. Finally we show the performance of our method for addressing the data sparsity and cold start problem.

Experimental Setup
------------------

**Datasets** We evaluate our methods on two real-life LBSN datasets: Foursquare and Gowalla. A number of researchers have conducted experiments on data collected from these two social networks  [@Yuan_sigir13; @Chen_aaai15; @Gao_aaai15; @Xie_cikm16; @Yin_tkde16]. However, many of them are collected from various regions or in different time spans. For a fair comparison with GE, we use the publicly available version [^1] provided by the authors of  [@Xie_cikm16].

The two datasets have different scales such as geographic ranges, the number of users, POIs, and check-ins. Hence they are good for examining the performance of algorithms on various data types. Their statistics are listed in Table \[tbl:dataset\].

[ccc]{} & **Foursquare** & **Gowalla**\
\# of users & 114,508 & 107,092\
\# of POIs & 62,462 & 1,280,969\
\# of Check-ins & 1,434,668 & 6,442,892\
\#std time slots & 24 & 24\
\# of locations & 5,846 & 200\
\# of $<$t, l$>$ patterns & 28,868 & 3,636\

Each check-in is stored as user-ID, POI-ID, POI-location in the form of latitude and longitude, check-in timestamp, and POI-content (only for Foursquare). In order to get the spatiotemporal patterns $<$t, l$>$ in Table \[tbl:dataset\], we use the same discretized method as that in  [@Xie_cikm16], i.e., dividing time into 24 time slots which correspond to 24 hours, and the whole geographical space into a set of regions according to 5,846 administrative divisions (for Foursquare) and 200 regions clustered by a standard *k*-means method (for Gowalla). We finally get 28,868 and 3,636 $<$t, l$>$ pairs on Foursquare and Gowalla, respectively.

**Baselines - {GE, STA-E, STA-H}** We use GE, the state-of-the-art location based recommendation approach in  [@Xie_cikm16], as our baseline. GE adopts a graph-based embedding framework. It learns the embeddings based on the POI-POI, POI-Time, POI-Location, and POI-Words graphs. By integrating the sequential, geographical, temporal cyclic, and semantic effect into a shared space, GE effectively overcomes the data sparsity problem and reaches the best performance so far.

We do not compare our method with other existing approaches because, GE has already significantly outperformed a number of baselines including JIM  [@Yin_cikm15joint], PRME  [@Feng_ijcai15], and Geo-SAGE  [@Wang_kdd15Geo]. We thus only show our improvements over GE.

Also note that although we choose the TransR technique in knowledge graph embedding to materialize our STA model, the essential of our proposed framework is the translation of $<$time, location$>$ pairs in the embedding space. This indicates that we do not rely on a specific translation model. Hence we can use TransE  [@Bordes_ml14] and TransH  [@Wang_aaai14] to realize STA. We denote the resulting methods as STA-E and STA-H baselines, respectively.

**Settings** We first organize the quadruples (u, v, t, l) in each dataset by users to get each user’s profile $D_u$. We then rank the records in $D_u$ according to the check-in timestamps, and finally divide these ordered records into two parts: the first 80% as the training data, and the rest 20% data as the test data. Moreover, the last 10% check-in records in the training data are used as a validation set for tuning the hyper-parameters. We use the accuracy@*k* (*k* = {1, 5, 10, 15, 20}) as our evaluation metric. All these settings, as well as the computation approach to accuracy@*k*, are same as those in  [@Xie_cikm16].

We use the default settings in the original TransR  [@Lin_aaai15] as the parameter settings for our STA model. Specifically, we set the learning rate $\lambda = 0.0001$, the margin $\gamma = 2$, the mini-batch size $B=4800$, and the embedding dimensions $m = d = 100$, and we traverse over all the training data for 1000 rounds.

Comparison with baselines
-------------------------

For a fair comparison, we implement GE using the same LINE software provided by the authors of  [@Tang_www15] on our data divisions. All the parameters for GE are same as those in  [@Xie_cikm16]. We find a slightly difference (less than 1% in accuracy) between the original results and those by our implemented GE. This is understandable and acceptable considering the randomness when sampling negative edges in LINE and initiating the centers of clusters of regions. All parameters for STA-E and STA-H use the default settings in  [@Bordes_ml14] and  [@Wang_aaai14]. We present the comparison results on Foursquare and Gowalla in Fig. \[fig:comp\] (a) and (b), respectively.

![image](comp.eps){width="82.00000%" height="5.2cm"}

From Fig. \[fig:comp\] (a), it is clear that all our proposed STA-style models significantly outperform GE. For instance, the accuracy@1 for STA, STA-H, and STA-E is 0.307, 0.280, 0.255, respectively, much better than 0.225 for GE. Similar results can be observed in Fig.  \[fig:comp\] (b) on Gowalla dataset. This clearly demonstrates the effectiveness of our translation based framework.

While STA shows drastic improvement over GE for all *k*s on Foursquare, the trend is not that obvious on Gowalla when *k* = 15, 20. This is because there is a much smaller number of relations in Gowalla than that in Foursquare. As shown in Table  \[tbl:dataset\], Gowalla only has 3,636 relation patterns ($<$t, l$>$ pairs) while Foursquare has 28,868 pairs. Hence the learnt embeddings for entities and relations are worse than those on Foursquare, and incur the less accurate results when *k* is large.

Besides the improvement over GE, STA outperforms STA-H and STA-E as well. The reason is that TransR can differentiate the entities in the transformed relation space. Nevertheless, we see a less significant enhancement of STA over STA-H on Gowalla. This also conforms to the characteristics of the data: the graph of Gowalla is much larger but has less *tl* relation edges than that of Foursquare, and the advantage of TransR over TransE is not obvious on such a dataset.

Effects of Model Parameters
---------------------------

The effects of embedding dimension *d* on Foursquare and Gowalla are shown in Table \[tab:dimf\] and Table \[tab:dimw\], respectively.

           1       5      10      15      20
  ----- ------- ------- ------- ------- -------
   70    0.281   0.376   0.409   0.433   0.451
   80    0.294   0.384   0.417   0.445   0.462
   90    0.300   0.390   0.425   0.459   0.476
   100   0.307   0.393   0.434   0.461   0.483
   110   0.311   0.407   0.439   0.463   0.486
   120   0.312   0.407   0.439   0.464   0.486

  : Effects of Dimensionality on Foursquare

\[tab:dimf\]

           1       5      10      15      20
  ----- ------- ------- ------- ------- -------
   70    0.355   0.432   0.474   0.503   0.527
   80    0.358   0.436   0.478   0.508   0.530
   90    0.359   0.439   0.482   0.509   0.535
   100   0.361   0.445   0.486   0.511   0.539
   110   0.361   0.445   0.488   0.513   0.540
   120   0.361   0.445   0.488   0.513   0.540

  : Effects of Dimensionality on Gowalla

\[tab:dimw\]

We can see that the experimental results are not very sensitive to the dimension *d*. With an increasing number of dimension, the accuracy on Gowalla is almost unchanged, i.e., the improvement is less than 1% in nearly all cases. The accuracy on Foursquare is slightly enhanced with a large dimension *d*, and finally it becomes stable.

To investigate the effects of time interval, we divide timestamps by three methods, i.e., splitting time into 24, 7, and 2 time slots, corresponding to the daily, weekly, and weekday/weekend patterns, respectively. Figure \[fig:time\] shows the effects of various time intervals.

![image](time.eps){width="82.00000%" height="5.5cm"}

We observe that the impact of the daily patterns is the most significant on both datasets. In addition, the results for different patterns vary widely, suggesting a good strategy for dividing the time slot is important.

Sensitivity to Data Sparsity
----------------------------

To investigate the sensitivity to data sparsity of STA and GE, we conduct extensive experiments to evaluate the performance on two datasets by reducing training data. More precisely, we keep the testing dataset unchanged and reduce the training data randomly by a ratio of 5% to 20% stepped by 5. Due to the space limitation, we only present the results by reducing 20% training data Table \[tab:20less\]. The trends with other ratios are all alike.

We have the following important notes for Table \[tab:20less\].

-   With the reduction of training data, the accuracy values for STA and GE both decrease. However, STA always achieves the best results at different *k* values on two datasets.

-   The reduction of accuracy of our STA model is much smaller than that of GE. For instance, the accuracy@1 of GE decreases from 0.225 to 0.154, showing a 31.69% drop. In contrast, our STA model only has a 20.00% change. This strongly suggests that our model is more robust to the data sparsity.

-   The declination of accuracy on Foursquare is more obvious than on Gowalla. The reason may be that Foursquare is much sparser in users’ check-ins than Gowalla, hence reducing the training data has a greater impact on Foursquare.

Test for Cold Start Problem
---------------------------

In this experiment, we further compare the effectiveness of our extended STA-C model with GE when addressing the cold-start problem. The cold start POIs are defined as those visited by less than 5 users  [@Yin_tkde16]. To test the performance of cold start POI recommendations, we select users who have at least one cold-start check-in as test users. For each test user, we choose his/her check-in records associated with cold-start POIs as test data and the remains as training data. Since there is no content information for POIs in Gowalla, we conduct experiments, just as GE did, only on Foursquare. The results are shown in Fig. \[fig:cold\].

![Test for Cold Start Problem on Foursquare[]{data-label="fig:cold"}](cold1.eps){width="56.00000%" height="3.6cm"}

From Fig. \[fig:cold\], it is clear that our proposed STA-C model consistently beats GE when recommending cold start POIs. The superior performance of STA-C model is due to the translation of content and geography information *wl* from an ordinary POI *v* to a cold start POI $v_c$. As long as there is an existing *v* sharing one $<$word, location$>$ pair with $v_c$, our STA-C model can get a translation for $v_c$. In contrast, GE utilizes the bipartite graphs of POI-Word and POI-Location. The weight of an edge in the graph is calculated by a TF-IDF value of the word or the frequency of a location. The edge weight is proportional to the probability of edge sampling. Since there are few check-in records for cold start POIs, a $v_c$-word and $v_c$-location edge has an extremely rare chance to be selected and updated. Consequently, the learnt embedding for $v_c$ will be poor and further deteriorates the recommendation accuracy.

Conclusion
==========

We present a novel spatiotemporal aware model STA for learning representations of users, spatiotemporal patterns, and POIs. The basic idea is to capture the geographic and temporal effects using a $<$time, location$>$ pair, and then model it as a translation connecting users and POIs. We realize STA using the knowledge graph embedding technique. Our method has two distinguished advantages. 1) We learn a joint representation for spatiotemporal patterns whose components contribute together to a user’s choice in POIs. 2) The translation mechanism enables the learnt POI embeddings to be in the same semantic space with that of the query POI.

We conduct extensive experiments on two real-life datasets. Our results show that STA achieves the state-of-the-art performance in recommendation accuracy. It also significantly outperforms the baselines in terms of the effectiveness in addressing both the data sparsity and cold start problems.

Acknowledge {#acknowledge .unnumbered}
===========

The work described in this paper has been supported in part by the NSFC project (61572376).

Antoine Bordes, Xavier Glorot, Jason Weston, and Yoshua Bengio. A semantic matching energy function for learning with multi-relational data. , 94(2):233–259, 2014.

Xuefeng Chen, Yifeng Zeng, Gao Cong, Shengchao Qin, Yanping Xiang, and Yuanshun Dai. On information coverage for location category based point-of-interest recommendation. In [*Proc. of AAAI*]{}, page 37¨C43, 2015.

Chen Cheng, Haiqin Yang, Irwin King, and Michael R Lyu. Fused matrix factorization with geographical and social influence in location-based social networks. In [*Proc. of AAAI*]{}, pages 17–23, 2012.

Chen Cheng, Haiqin Yang, Michael R. Lyu, and Irwin King. Where you like to go next: Successive point-of-interest recommendation. In [*Proceedings of IJCAI*]{}, pages 2605–2611, 2013.

Chen Cheng, Haiqin Yang, Irwin King, and Michael R Lyu. A unified point-of-interest recommendation framework in location-based social networks. , 8(1):1–21, 10 2016.

Eunjoon Cho, Seth A. Myers, and Jure Leskovec. Friendship and mobility: user movement in location-based social networks. In [*Proceedings of SIGKDD*]{}, page 1082¨C1090, 2011.

Shanshan Feng, Xutao Li, Yifeng Zeng, Gao Cong, Yeow Meng Chee, and Quan Yuan. Personalized ranking metric embedding for next new poi recommendation. In [*Proc. of 24th IJCAI*]{}, pages 2069–2075, 2015.

Huiji Gao, Jiliang Tang, Xia Hu, , and Huan Liu. Content-aware point of interest recommendation on location-based social networks. In [*Proceedings of 29th AAAI*]{}, pages 1721–1727, 2015.

Defu Lian, Cong Zhao, Xing Xie, Guangzhong Sun, Enhong Chen, and Yong Rui. Geomf: joint geographical modeling and matrix factorization for point-of-interest recommendation. In [*Proceedings of SIGKDD*]{}, pages 831–840, 2014.

Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In [*Proc. of 29th AAAI*]{}, pages 2181–2187, 2015.

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In [*Proceedings of WWW*]{}, pages 1067–1077, 2015.

Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In [*Proc. of 28th AAAI*]{}, pages 1112–1119, 2014.

Weiqing Wang, Hongzhi Yin, Ling Chen, Yizhou Sun, Shazia Sadiq, and Xiaofang Zhou. Geo-sage: A geographical sparse additive generative model for spatial item recommendation. In [*Proceedings of SIGKDD*]{}, pages 1255–1264, 2015.

Min Xie, Hongzhi Yin, Hao Wang, Fanjiang Xu, Weitong Chen, and Sen Wang. Learning graph-based poi embedding for location-based recommendation. In [*Proc. of CIKM*]{}, pages 15–24, 2016.

Mao Ye, Peifeng Yin, and Wang Chien Lee. Location recommendation for location-based social networks. In [*Proc. of ACM SIGSPATIAL*]{}, pages 458–461, 2010.

Mao Ye, Krzysztof Janowicz, and Wang Chien Lee. What you are is when you are: the temporal dimension of feature types in location-based social networks. In [*Proc. of ACM SIGSPATIAL*]{}, pages 102–111, 2011.

Mao Ye, Peifeng Yin, Wang-Chien Lee, and Dik-Lun Lee. Exploiting geographical influence for collaborative point-of-interest recommendation. In [*Proceedings of SIGIR*]{}, pages 325–334, 2011.

Hongzhi Yin, Xiaofang Zhou, Yingxia Shao, Hao Wang, and Shazia Sadiq. Joint modeling of user check-in behaviors for point-of-interest recommendation. In [*Proceedings of CIKM*]{}, pages 1631–1640, 2015.

Hongzhi Yin, Xiaofang Zhou, Bin Cui, Hao Wang, Kai Zheng, and Nguyen Quoc Viet Hung. Adapting to user interest drift for poi recommendation. , 28(10):2566–2581, 2016.

Quan Yuan, Gao Cong, Zongyang Ma, Aixin Sun, and Nadia Magnenat Thalmann. Time-aware point-of-interest recommendation. In [*Proc. of SIGIR*]{}, pages 363–372, 2013.

Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. Mining interesting locations and travel sequences from gps trajectories. In [*Proc. of WWW*]{}, pages 791–800, 2009.

Wen-Yuan Zhu, Wen-Chih Peng, Ling-Jyh Chen, Kai Zheng, and Xiaofang Zhou. Modeling user mobility for location promotion in location-based social networks. In [*Proceedings of SIGKDD*]{}, pages 1573–1582, 2015.

[^1]: https:/sites.google.com/site/dbhongzhi
