Content-Aware Hierarchical Point-of-Interest Embedding Model for Successive POI Recommendation

1 Introduction

In recent years, many mobile-based social media platforms such as Twitter, Facebook, Instagram, and Foursquare have grown in popularity.

Users on these platforms generate a large amount of data which includes text content with temporal and spatial information. Such information is particularly useful for understanding user behavior and preferences for a point-of-interest (POI) which is a specific location that someone finds interesting. In mobile-based applications, it is necessary but challenging to recommend where a user will visit next based on temporal and spatial information.

Recently, several models based on conventional sequentialdata modeling approaches and designed to recommend the next POI have been proposed. Markov Chain based models [Cheng et al., 2013; Chen et al., 2014] exploit a user's checkin sequence information while considering temporal and spatial constraints. Based on tensor factorization, STELLAR [Zhao et al., 2016] models POI pairs visited successively. Also, ST-RNN [Liu et al., 2016a] employs a recurrent neural network (RNN) and achieves state-of-the-art performance in modeling sequential data.

Although ST-RNN achieves state-of-the-art performance, it still has room for improvement. Since ST-RNN employs randomly initialized vectors as POI representations, it does not utilize the characteristics of POIs or the relationships between POIs. ST-RNN uses only the time interval between two check-ins and the distance between two POIs as factors to recommend the next POI.

Although POI embedding models [Liu et al., 2016b; Feng et al., 2017; Zhao et al., 2017] have been recently proposed to capture relationships between POIs, they have not yet been employed in successive POI recommendation tasks. In addition, the existing POI embedding models use only user checkin context to capture the geographical influence of POIs, but they do not utilize text content which provides information about the characteristics of a POI. For example, if a POI's text content includes the words "latte," "coffee," and "drinks," the POI has characteristics associated with a cafe. Figure 1 shows the examples of text contents of the POI "Yankee Stadium" written by users.

In this paper, we first describe our newly constructed dataset that includes text contents collected from Instagram, and analyze the characteristics of the dataset used for our POI embedding study. Second, we propose CAPE, which is a Content-Aware hierarchical POI Embedding model for POI recommendation. From text contents, CAPE captures not only the geographical influence of POIs, but also the characteristics of POIs. CAPE consists of a check-in context layer and a text content layer. In the check-in context layer, embedding vectors of POIs in a user's check-in sequence are trained to be close to each other in the vector space using Skip-gram [Mikolov et al., 2013]. At the same time, in the text content layer, POI embedding vectors are trained to capture the characteristics of a POI from the words used in the POI's text content. In the experimental section, we implement the successive POI recommendation models and apply our CAPE model to the POI recommendation models. The experimental evaluation on our dataset shows that CAPE contributes to improving the performance of successive POI recommendation models. The evaluation result also shows that CAPE captures the geographical influences of POIs and characteristics of POIs. CAPE outperforms previously proposed POI embedding models.

The contributions of this paper are summarized as follows.

• We construct a new large-scale POI dataset and analyze the dataset to investigate its applicability to POI recommendation studies. We show the importance of text content in POI embedding.
• We propose CAPE which is a new content-aware hierarchical POI embedding model that utilizes a user's checkin sequence and text content about POIs. To the best of our knowledge, CAPE is the first content-aware POI embedding model.
• CAPE which captures the geographical influence and characteristics of a POI significantly improves the performance of successive POI recommendation models.
• We release our newly constructed large-scale dataset which includes text content written by mobile-based social network users. Our source code implemented in an open library is also publicly available.

The remainder of this paper is organized as follows. In Section 2, we summarize previously proposed successive POI recommendation models and POI embedding models. In Section 3, we introduce our newly constructed dataset which includes text content, and investigate the necessity of contentaware POI embedding. In Section 4, we describe our proposed model CAPE. In Section 5, we compare our proposed model with existing POI embedding models, and analyze the experimental results. Last, in Section 6, we provide our concluding remarks of this paper.

2 RelatedWork

2.1 Successive POI Recommendation

There exist several successive POI recommendation models which are based on sequential-data modeling approaches. Zhao et al. [Zhao et al., 2016] proposed a spatial-temporal latent ranking (STELLAR) method that employs a rankingbased pairwise tensor factorization framework to model consecutive POIs. To capture and exploit the temporal influence of check-in times on POI recommendation, STELLAR models not only POI-POI pairs but also time-POI pairs. However, STELLAR is unable to model the whole check-in sequence of a user because it focuses on pairs of consecutive POIs. Cheng et al. [Cheng et al., 2013] and Chen et al. [Chen et al., 2014] proposed recommendation models based on Factorizing Personalized Markov Chain (FPMC) [Rendle et al., 2010] which extends the Markov chain model by factorizing the probability transition. Considering a user's movement constraints, the model by Cheng et al. [Cheng et al., 2013] embeds the personalized Markov chain. The model by Chen et al. [Chen et al., 2014] combines the personalized Markov chain with the global Markov chain to capture global behavioral patterns. However, since the FPMC based models linearly combine all the embedded Markov chains and constraints, they require a strong independence assumption among different factors [Wang et al., 2015]. With the success of RNN in sequential data modeling, RNN is also used to model a user's check-in sequence for successive POI recommendation. Liu et al. [Liu et al., 2016a] proposed ST-RNN which extends RNNs with time- and distance-specific transition matrices to model local temporal and spatial contexts, respectively.

Although the above models have achieved satisfactory results in some applications, the models are unable to utilize the characteristics of POIs and the relationships between POIs because they employ randomly initialized vectors as POI representations. In this paper, we focus on improving the performance of the existing POI recommendation models using our pre-trained POI embedding model CAPE, which captures the characteristics of POIs.

2.2 POI Embedding

As word embedding has proven to be successful in the NLP field, studies have proposed POI embedding models that capture the geographical influence of POIs from a user's checkin sequence. Liu et al. [Liu et al., 2016b] assume that a POI is influenced by other POIs in a user's check-in sequence. They treated each POI as a "word" and each user's sequential check-in information as a "sentence," and used Skip-gram [Mikolov et al., 2013] to train a POI's latent representation vector. Furthermore, they proposed a time-aware POI recommendation model that uses a time latent representation vector. Feng et al. [Feng et al., 2017] proposed POI2Vec, which is a POI latent representation model to incorporate geographical influence. They developed a hierarchical binary tree based on the physical distance between POIs to reflect the geographical influence. Zhao et al. [Zhao et al., 2017] considered the temporal characteristics of POIs. Because of the low correlation between POIs visited on different days, they treated a user's check-ins of one day as a "sentence". Then, they proposed a temporal POI embedding model that differentiates between weekdays and weekends using a specific temporal state.

There are few studies that use text content for POI embedding. However, our model utilizes a user's check-in sequence information and text content for POI embedding.

3 Data Description and Analysis

In this section, we first describe our large-scale dataset which includes text content, and then analyze the properties of the dataset.

3.1 Data Description

Since most of the existing POI recommendation studies do not use text content, there is no suitable dataset that contains text content. Although Yang et al. [Yang et al., 2013] use text content to understand user sentiment and improve the POI recommendation performance, their dataset is unsuitable for learning POI representations. First, many POIs in their dataset do not have text contents written by users. Second, the dataset is not large enough for training POI representations. Therefore, we constructed a new dataset that contains text contents which refer to POIs. We collected data from Instagram, which is one of the most popular mobile-based social networks. Instagram data includes not only user POI check-in information, but also text content written by users. We collected Instagram data created in New York City and preprocessed the collected data utilizing the same method of Zhao et al. [Zhao et al., 2017]. We removed the POIs with less than five checked-ins and the users who had less than ten posts. After preprocessing, our new dataset 1 includes 2,216,631 check-ins at 13,187 POIs of 78,233 users. The statistics of our dataset are summarized in Table 1.

3.2 Empirical Analysis

Instagram generates a large amount of location-aware data each day. However, the Instagram dataset has been used in only one POI recommendation study [Wang et al., 2017] that used images to understand user preference about POIs. Therefore, we conducted a data analysis to determine whether our newly constructed dataset is suitable for the successive

1 Our newly constructed dataset is available at https://dmis.korea.ac.kr/cape

0

0

Figure 3: Jaccard similarity between the POI sets

POI recommendation task. We also analyzed the relationships between words and POIs to capture the importance of text content in POI embedding.

Geographical influence

According to POI recommendation studies [Ye et al., 2011; Liu et al., 2013], location-based social network users tend to visit POIs located near the POIs that the users have already visited. We investigate whether the users in our dataset have a similar tendency. We measure the average distance between POIs in a user's check-in information (Check-ins) and compare this distance with the average distance between all the POIs in the dataset (Global). We make two user checkin information sets using the methods of Liu et al. [Liu et al., 2016b] and Zhao et al. [Zhao et al., 2017], respectively. The first set which we refer to as the (Check-ins All) set consists of all the check-ins of each user. The second set which is called the (Check-ins Day) set contains all the sequential POI check-ins which are organized by day. As shown in Figure 2, we observe that the average distances between POIs in the (Check-ins All) set and the (Check-ins Day) set are about 2.98 and 5.74 times smaller, respectively, than the average distance between all the POI pairs in the (Global) set. These results demonstrate that POIs visited by each user are close in proximity and are geographically influenced by each other. They also show that Instagram users tend to visit POIs located near POIs the users have already visited.

Textual Influence on POIs

We qualitatively analyze the relationship between words and POIs in the dataset. We measure the correlation between the words by calculating the Jaccard similarity of POIs in their text content. We first remove stop-words and construct a set of POIs for each word. Only POIs whose text content mentions a word more than five times are included in the POI set of the word. For example, when word w1 is used in the text content of POIs l1, l2, and l3, the POI set of word w1 is {l1, l2, l3}. We make the POI sets for the top 2000 words sorted by frequency, and calculate the average Jaccard similarity value for all the pairs of words (Top 2000 Words). We also compute the similarity values of the following word pairs: (coffee, cafe), (baseball, Yankees), and (cafe, baseball). The results are shown in Figure 3. As expected, (coffee, cafe) and (baseball, Yankees) have a much higher Jaccard similarity than (cafe, baseball) as the former pairs share similar semantic contexts and thus have larger POI overlaps. It is also interesting to see that the Jaccard similarity of (cafe, baseball) is substantially lower than the average Jaccard similarity of all the pairs in the Top 2000 Words set. This result demonstrates that the text content correlates with the POIs, which motivates us to use the text content in our POI embedding.

4 Method

In this section, we describe our content-aware hierarchical POI embedding model CAPE, which captures not only the geographical influence of POIs, but also the characteristics of POIs from text content. CAPE consists of a check-in context layer and a text content layer.

4.1 Check-in Context Layer

As explained in the data analysis section, POIs visited by each user, especially those which are consecutive in the user's check-in context, are geographically influenced by each other. To capture this geographical influence of POIs, the check-in context layer employs the Skip-gram based POI embedding model proposed in the study by Liu et al. [Liu et al., 2016b]. For a better understanding of the check-in context layer, we define some data concepts as follows.

Definition 1 (Check-in Data) Each check-in data d consists of user u, POI l, text content x, and check-in time t. We denote dataset D and check-in data d as D = (d1, d2, ...) and d = (u, l, x, t), respectively.

Definition 2 (User Check-in Information) The user checkin information is a list of POIs sorted by check-in time. The check-in information of the user u ∈ U is defined as qu = (l1, l2, ...) where U is the set of users in D.

Definition 3 (Target and Context POI) In the user checkin sequence, the b POI visited before and after one target POI li is defined as the context POI for the target POI li. b is the pre-defined context window size.

The context layer is described in Figure 4. The context layer considers a user's check-in information as a "sentence" and each POI in a sequence as a "word" to use Word2Vec [Mikolov et al., 2013] for POI embedding. According to Zhao et al. [Zhao et al., 2017], the POIs that are visited by a user in the same day are more related to each other. Based on this, we treat a sequence of POIs visited by a user in the same day as a "sentence". The check-in context layer trains the POI embedding vector by maximizing the objective function Octx in the following way,

Figure 5: The illustration of the text content layer.

Given the target POI li, probability P(li+j|li) of the context POI li+j is computed by using the soft-max function as follows,

where l and l′ are input and output vectors of POI l respectively, and |L| is the number of POIs in the dataset. To speed up the learning process, we apply the negative sampling technique [Mikolov et al., 2013], and the loss function for the check-in context layer lossctx is then defined as follows:

where σ(·) is the sigmoid function, Lneg is the set of m negative POI samples, and l′ is the output representation vector of negative sample l.

4.2 Text Content Layer

Existing POI embedding models that utilize a user's check-in information capture only the geographical influence of POIs, and thus fail to capture the characteristics of POIs. The text content of an Instagram post provides information on what activities people have done at each POI. To capture the characteristics of a POI from text content, we propose a text content layer. Before describing the layer, we define two more concepts as follows.

Definition 4 (Text Content) Each text content si consists of words, and is defined as si = {w1, w2, ...} where w is a word. Each POI li contains multiple text contents written about the POI li. The set of multiple contents xi about POI li is defined as xi = {s1, s2, ... }.

Definition 5 (Target and Context Word) In the text content si, each of the c words located before and after target word wj is defined as the context of wj. c is the pre-defined context window size for the text content.

The text content layer is described in Figure 5. We first treat a text content as a "sentence" and train the word embedding vector w using Word2Vec [Mikolov et al., 2013]. Then, the content layer trains the POI vector and word embedding vector together, maximizing the objective function Octn.

Given the POI li and target word wj in the text content s, the objective function is computed using the sum of probability of the context word wj+k. We formulate the probability P(wj+k|wj, li) using a soft-max function as follows:

where ⊕ is a concatenate function, |V | is the number of words in the dataset. w and w′ are input and output word representation vectors, respectively, in the soft-max layer. Similar to Equation 3, we formulate the loss function for the content layer lossctn using the negative sampling technique as follows:

where Vneg is the set of negatively sampled m words and w′ is the output vector of negative sample word w.

In this paper, we sample the words that are highly associated with a POI li as a text content s′i to filter many meaningless words such as "selfie" and "follow". We compute the association weight between a word and a POI, which is similar to tf-idf, as follows:

where TF(wj, li) is the frequency of wj used in li's text contents and DF(wj) is the number of POIs whose text contents contain the word wj . Then, we sample the top-k words sorted by association weight for each POI. The loss function is modified as:

where s′i is the set of sampled words for POI li.

Finally, we combine the check-in context and text content layers. The final objective function of our content-aware POI embedding model CAPE is represented with hyperparameter α as follows:

CAPE simultaneously learns the geographical influence and semantical characteristics of POIs, maximizing objective function Oemb.

5 Experimental Evaluation

To qualitatively assess CAPE on the successive POI recommendation task, we conduct an experimental evaluation.

5.1 Experimental Setup

Successive POI Recommendation

Given a time-ordered user check-in sequence, recommendation models utilize the first (n-1) POIs as an input and predict the n-th POI as the recommended POI. We implement the following POI recommendation models that utilize user checkin sequences. (1) STELLAR [Zhao et al., 2016], the tensor factorization based model which trains pairs of consecutive POIs to predict the next POI; (2) LSTM, a simple RNN based model using LSTM cells; (3) GRU, a simple RNN based model using GRU cells; (4) ST-RNN [Liu et al., 2016a], the state-of-the-art POI recommendation model, which employs RNN and incorporates the time interval between two checkins and the distance between two POIs as factors.

Baselines

We compare CAPE with the following four baseline POI embedding models. (1) Random, a simple baseline POI representation model, which uses a randomly initialized vector and is employed by most POI recommendation studies that use the check-in sequence data of users; (2) SG [Liu et al., 2016b], a Skip-gram based POI embedding model which models user check-in sequences; (3) POI2Vec [Feng et al., 2017], a hierarchical binary tree based model which utilizes spatial location information; (4) Geo-Teaser [Zhao et al., 2017], a geo-temporal sequential embedding rank model, which uses both the geographical influence and temporal characteristics of each POI. We measure changes in performance when we apply each POI embedding model to the recommendation models.

Dataset Preparation

We evaluate our POI embedding model CAPE on our dataset described in the Data Description and Analysis section. To compare CAPE with the existing POI embedding baseline models, we divide the dataset into training, validation, and test sets using the same method employed in the study of Liu et al. [Liu et al., 2016a]. The most recent check-ins which constitute 20% of the total check-ins of each user are used for the test set. The less recent check-ins which constitute 10% are used for the validation set, and the remaining check-ins which constitute 70% are used for the training set.

Metric

To compare the performance of the recommendation models, we employ two evaluation metrics: Recall@k and Mean Reciprocal Rank (MRR). Recall@k is a popular metric used for ranking tasks, and is computed when the correct successive POI is in the top-k recommended POI list. Since there is only one correct answer in our successive POI recommendation task, we do not employ F1-score@k (or Precision@k) used

(b) Context window size

Figure 6: Effects of hyper-parameters.

in Liu et al. [Liu et al., 2016a]. We report the Recall@k for k = 1, 5, and 10. MRR is used to measure the quality of ranked lists. When the next correct POI is highly ranked in the recommended list, the evaluation score is also high.

5.2 Evaluation Result

Performance Comparison

Table 2 summarizes the experimental results evaluated using the metrics Recall@N and MRR. The results show that pre-trained POI embedding models improve recommendation performance. CAPE, SG, and Geo-Teaser outperform Random by 7.4%, 4.3%, and 1.8%, respectively, in terms of MRR, when applied to the recommendation models. Moreover, CAPE outperforms the POI embedding models in terms of the Recall@k and MRR metrics when applied to the recommendation models. In particular, CAPE outperforms GeoTeaser even though CAPE does not use location information, which is used by Geo-Teaser. These results demonstrate that text contents provide useful information for understanding the characteristics of POIs. Unlike the results reported in the study by Liu et al. [Liu et al., 2016a], the performance of STRNN, which utilizes consecutive check-in time intervals as temporal factors, was lower than that of LSTM. The average time interval between two consecutive check-ins in our Instagram dataset is about 10 times longer than that in the Gowalla dataset. Thus, the context of a target POI, which is the input to ST-RNN, cannot be properly constructed. When the input context is inappropriate, the state of ST-RNN is computed by only previous state. We report that CAPE, SG-CWARP, and Geo-Teaser took about 3 hours 40 minutes, 3 hours, and 7 hours to be optimized, respectively, on a single GTX Titan X GPU machine.

Hyper-parameter Optimization

We observe performance variance when we change the hyperparameters of CAPE. The results are summarized in Figure 6. We first set the range of POI embedding dimension to 50-450. We then observe the performance changes from increasing the dimension in increments of 50. As shown in Figure 6a, the best performance is obtained when the dimension is set to 300, except in the case of STELLAR which achieves the best performance when the dimension is set to 100. Figure 6b and 6c show the variations in performance when we change the check-in context and text content window sizes, respectively. We set the ranges to 1-4, and observe the performance changes after increasing the window sizes by 1. When we set the context and content window sizes to 1 and 2, respectively, the best performance is obtained. CAPE optimizes the linearly combined lossctx and lossctn using a hyper-parameter α. We also investigate the effect of hyper-parameter α. The POI recommendation models, except ST-RNN, obtain the best performance using CAPE when the hyper-parameter α is 0.4. ST-RNN achieves the best performance when the hyper-parameter is 0.3.

6 Conclusion

In this paper, we introduced our newly constructed large-scale dataset and investigated the necessity of using text content in POI embedding. We also proposed CAPE which is a novel content-aware hierarchical POI embedding model for POI recommendation. CAPE captures the characteristics and geographical influence of POIs from the text content and checkin context of users. The experimental results showed that CAPE contributes to improving POI recommendation performance.

Acknowledgements

This research was supported by the National Research Foundation of Korea (No. 2017R1A2A1A17069645, 2017M3C4A7065887).