Timestamps as Prompts for Geography-Aware
Location Recommendation

Sequential recommendation models, initially based on Markov chain (Baumann et al., 2013; Gambs et al., 2012), were able to predict probability of the next behavior via a transition matrix. Challenged with the flaw of Markov-based model that only the transition probability between two consecutive visits is mainly considered, deep learning-based models, among which RNN (Zhang et al., 2014) models are representative and have been quickly developed as strong baselines, go on stage. Meanwhile, the contributions of other deep learning methods, such as metric embedding algorithms (Feng et al., 2020), convolutional neural networks (Tang and Wang, 2018), reinforcement learning algorithms (Massimo and Ricci, 2018), and graph neural networks (Wu et al., 2019; Yu et al., 2020) can be witnessed. Recently, due to full parallelism and the capacity of capturing long-range dependence, the self-attention networks (Vaswani et al., 2017) are proposed for sequential recommendation and have achieved distinguished performances. For example, GeoSAN (Lian et al., 2020) employs self-attention layers and achieves state-of-the-art performance.

However, most of the methods mentioned predict the next location only through the fusion of historical check-in sequences and associated contextual information, ignoring that the timestamp of the location to be predicted is also of great significance. The proposed TPG framework explicitly models temporal information via a novel temporal prompt.

Next location recommendation, i.e., POI recommendation, which draws considerable attention recent years due to great business value, can be viewed as a special sub-task of sequential recommendation with spatial information (Luo et al., 2021). Regarding the use of spatio-temporal information in next location recommendation, many previous works only use spatio-temporal intervals between two successive visits in a recurrent layer. For example, DeepMove (Feng et al., 2018) combines an attention layer for learning long-term sequential regularity. LSTPM (Sun et al., 2020) proposes a geo-dilated RNN that aggregates locations visited recently, but only for shot-term preference. Inspired by sequential item recommendation (Kang and McAuley, 2018), GeoSAN (Lian et al., 2020) uses self-attention model in next location recommendation within the trajectory. STAN (Luo et al., 2021) adopts a spatial-temporal attention network that aggregates all relevant check-ins in trajectories. GETNext (Yang et al., 2022) proposes a novel graph enhanced Transformer model by exploiting the extensive collaborative signals.

However, these models suffer from limitations in geographic and temporal information modeling. In TPG, we take the challenge of the hard boundary problem in grid mapping, and propose the shifted window mechanism. We also discard the implicit way to fuse the temporal information in TPG. Temporal prompt is proposed for explicitly modeling timestamp of locations to be predicted.

In recent years, we have witnessed the success of pre-trained language models, such as GPT series especially GPT3 (Brown et al., 2020), which has triggered prompt-based learning paradigm, namely “pre-train, prompt, and predict” (Liu et al., 2023), to boom on NLP tasks. At this point, models are no longer designed to adapt to the tasks. Instead, various tasks are modified by templates to get closer to the space of pre-trained model, which is trained with huge language data from the web. During the whole developing process, many prompt design methods have proliferated. One type of the methods (Gao et al., 2021) is proper discrete prompts, concentrating on the design of the templates. Meanwhile, another line of work (Liu et al., 2021) exploited continuous vector embeddings as prompts to improve the performance on NLP tasks. Furthermore, as yet another type, instruction-based prompts contain detail task descriptions and adhere more to the natural language format.

As a matter of fact, recommendation has been co-evolved with NLP techniques for a long time. Inspired by the success of these approaches on NLP tasks, researchers recently transfer the main idea of prompt-based learning to recommendation problems, achieving very promising results. P5 (Geng et al., 2022) creates a collection of personalized prompts and then trains a sequence-to-sequence model on a variety of recommendation related tasks verbalized according to the constructed personalized prompts.

To our best knowledge, our work is the first one to use timestamps as prompts in the self-attention based sequential recommendation framework for location recommendation, which explicitly models temporal information.

Each check-in $c_{i}^{u}=(u,t_{i},p_{i})$ is a user, POI, time tuple, which denotes a behavior that a user $u$ visits POI $p_{i}$ at time $t_{i}$. Each POI $p_{i}$ has its own geographic coordinates $(x_{i},y_{i})$. Each user $u$ has a sequence of historical check-ins $C_{1\rightarrow n}^{u}=\{c_{i}^{u}\}_{i=1}^{n}$. Given the historical check-in sequences of users, the goal of next location recommendation is to predict the next POI $\rho_{t_{n+1}}$ that a certain user $u$ will visit at a certain time $t_{n+1}$.

The overall architecture of our TPG framework is described in Figure 3. Based on the Transformer’s encoder-decoder structure, TPG can be divided into three parts, i.e., geography-aware encoder, history encoder, and temporal prompt-based decoder. For each check-in, the geographic coordinate of POI can be fed into the geography-aware encoder to get geographical representation $e_{i}^{geo}$. The historical check-in sequences including POI, user, and time information are then fed into the multi-modal embedding module to generate hidden representations $\{e_{i}^{POI}\}_{i=1}^{n}$, $\{e_{i}^{user}\}_{i=1}^{n}$, and $\{e_{i}^{time}\}_{i=1}^{n}$. Together with $\{e_{i}^{geo}\}_{i=1}^{n}$ from the geography-aware encoder, these representations are processed by a history encoder to generate user travel preference representation. Using temporal information of $t_{n+1}$ as prompt, the temporal prompt query and user travel preference memory are then forwarded to the decoder, which is capable of generating more accurate predictions for the next locations.

Sparsity issue is a key challenge in recommendation problem. In particular, as the check-in data gives implicit feedback of visiting behavior (Lian et al., 2014), the data sparsity problem is even worse for POIs compared other item recommendation such as movies or goods, of which users usually only express their opinion with ratings. Thus, when it comes to encoding geographic information of POIs, directly feeding the coordinates of POIs into the learning model makes it difficult for the model to capture geographic correlations. GeoSAN (Lian et al., 2020) embeds the exact position of locations by mapping latitude and longitude into hierarchical grids using tile map system¹¹1https://www.maptiler.com/google-maps-coordinates-tile-bounds-projection as exemplified in Figure 4. The tile map system is a hierarchical multi-resolution pyramid model. The world map is obtained by projecting the entire world into a flat plane by Mercator²²2https://www.britannica.com/science/Mercator-projection. The scale of the plane starts with $512\times 512$ pixels. It grows by a factor of 2 with the increase of levels. For better retrieval and display, the plane is further divided into grids of $256\times 256$ pixels each. From the low level bottom to the high level top of the tile pyramid, the resolution becomes lower and lower, but the geographic range is unchanged via sub-gridding one grid into four grids of the same size. Since the partition of grids is like quadtree, each grid can be identified with a unique quadtree key (quadkey for short). Quadkeys consist of the characters from the set {“0”, “1”, “2”, “3”}. The length of it equals the level of grid.

It indeed can alleviate the sparsity problem to some extent. However, for grids at the same level, the boundary of grids may damage the physical spatial proximity of two POIs around the boundary, which is a violation of Tobler’s First Law of Geography (Tobler, 1970). In other words, lacking connections across adjacent grids limits modeling power of geography-aware encoder. To introduce cross-grid connections, we propose a shifted window mechanism in our geography-aware encoder. As illustrated in Figure 5, for each grid, we move the shifted window along the X and Y direction (and both) by a certain step, which is part of the length of the grid size. In this way, we will get nine grids for each grid, i.e., itself and eight augmented neighbor grids.

Now the remaining task of geography-aware encoder is transforming quadkeys of these nine grids into a continuous latent embedding with rich information. For each quadkey, it is actually a character sequence. Each character in the sequence denotes the index of the grid partition at a certain level. If we want to make effective use of hierarchical spatial information of grids, an intuitive and straightforward approach is to conduct self-attention between these characters. However, since the cardinality of the character set is very small (i.e., only 4), treating a quadkey at character-level cannot achieve the goal of fully encoding the geographic correlations between POIs. Therefore, we consider dividing the character sequence by n-gram, and converting it into a sequence at n-gram-level. In this way, the vocabulary size of the sequence increases from 4 to 4n. For example, if a quadkey is “013201233”, the result of using four-gram is 0132-1320-3201-2012-0123-1233. We then use a stacked self-attention network and a point-wise feed forward network for capturing dependencies among these n-grams. After that, for each grid among these nine grids, average pooling can be utilized to aggregate the sequence of n-gram representations. We then obtain geographic embedding $e_{i}^{geo}$ for the given location $POI_{i}$ by average pooling on aggregated representations of these nine grids. The shifted window mechanism is helpful to reduce possible bias caused by the arbitrary partition of grids via including information from augmented neighbor grids.

Each check-in is a tuple consisting of user, time and POI information. To tackle with such discrete and heterogeneous data, we need a multi-modal embedding module to transfer check-in data into interpretable information for TPG. Specifically, for encoding time information, timestamps are firstly discretized into $24\times 7=168$ types learnable vectors. For encoding user and POI information, the type number of learnable vectors equals to the unique number of users and POIs in datasets. All these vectors are then linearly projected into $d$-dimensional embeddings $e_{i}^{time}\in\mathbb{R}^{d}$, $e_{i}^{user}\in\mathbb{R}^{d}$, and $e_{i}^{POI}\in\mathbb{R}^{d}$. In this way, for the user $u$, the historical check-in sequence $\{c_{i}^{u}\}_{i=1}^{n}$ can be further denoted as $(\{e_{i}^{POI}\}_{i=1}^{n},\{e_{i}^{user}\}_{i=1}^{n},\{e_{i}^{time}\}_{i=1}^{n},\{e_{i}^{geo}\}_{i=1}^{n})$. Note that since check-in data requires a certain order of precedence, learnable positional embedding is also added into inputs for history encoder.

Compared with previous RNN-based methods, Transformer architecture (Vaswani et al., 2017) can not only avoid recurrence, allowing parallel computing to reduce training time, but also migrate performance degradation problem with regard to long-term dependencies in RNNs. To better capture long range spatial-temporal dependencies in users’ historical check-in sequences, we stack Transformer encoder layers (Vaswani et al., 2017) for constructing the history encoder. Each Transformer encoder layer involves a multi-head self-attention module and a point-wise feed-forward network. We also keep the residual connection and layer normalization employed in Transformer encoder layers. Dividing the attention mechanism into multiple heads to form multiple sub-spaces allows the model to focus on different aspects of information. For each attention head, self-attention result for a check-in $c_{i}$ can be computed as

where $e^{c}_{i}$ is the input check-in embedding for $c_{i}$, $e^{c}_{j}$ is the embedding for contextual check-in in the sequence, and $w_{\{q,k,v,z\}}$ denotes linear transform weights for the query, key, value, and output matrices. The self-attention mechanism aggregates the global context information into each check-in features. After multi-head self-attention results are obtained by concatenating every self-attention result, the encoder is able to jointly attend to information from different representation sub-spaces at different positions. Then, the feed-forward network contains two linear transformations with a ReLU activation in between, which can be denoted as

where $e^{c}_{i^{\prime}}$ is the input embedding after multi-head self-attention, $W_{1}$ and $W_{2}$ denote linear transform weights, and $b_{1}$ and $b_{2}$ are linear transform offsets.

The normal way for existing methods to generate the predictions of next location is based on historical check-ins and the associated contextual information. The model will not explicitly indicate the output with respect to a special temporal information. However, in real world applications, it is important to consider the exact time for next location prediction. Location recommendation is usually employed in map services such as Google Map and location based services such as Foursquare. We can regard the time of user opening the app or clicking the query box in the app as the timestamp of next location. Human mobility has the periodicity (Yuan et al., 2014). People will revisit POIs of the same category around the same hour of different days. While at different hour of a day, people tend to visit different types of POIs. For example, it is the simple fact that if a user clicking the query box in the map app at noon, he/she is probably looking for a restaurant. While in the morning, there is a big chance that he/she wants to search for the route to his/her company. Therefore, if the model does not know the timestamp of next location, it cannot produce results of next locations with high confidence. Thus, an intuitive idea is that we can directly tell the model about the timestamp of next location. A simple method for it is to incorporate this timestamp into inputs. However, since a check-in is a tuple of user, time, and POI, directly adding this single timestamp into inputs is not appropriate. To this end, we propose a temporal prompt-based decoder, using timestamps as prompts and queries for the decoder. There are several advantages of utilizing temporal prompts: (1) It separates historical check-in sequences and temporal information of locations to be predicted, making the model more flexible for generating any future check-in. (2) By explicitly modeling temporal information, the prediction is greatly correlated to the given timestamp. As mentioned above, people’s travel choices are strongly related to timestamps, so this design will most likely improve model performances.

In greater detail, the preference decoder takes queries (i.e., time representation $e_{n+1}^{time}$) and encoder memory (i.e., user travel preference representation $e^{C}$) as inputs. We construct the temporal prompt-based decoder by stacking Transformer decoder layers(Vaswani et al., 2017), each of which consists of a multi-head self-attention sub-layer, an encoder-decoder attention sub-layer, and a feed-forward network sub-layer. User travel preferences and timestamp information are deeply fused in each encoder-decoder attention sub-layer. Each attention head of the encoder-decoder attention sub-layer can be represented by

where notations are consistent with Eq. 1.

After adding up and feeding the results into the feed-forward networks for further projection, the output embedding decodes the fused check-in features and has the same length as the query embedding. The output here is actually the embedding of predicted next location.

As for the training scheme, we adopt the negative log likelihood with sampled Softmax as the recommendation loss for each user $u$. The recommendation loss can be depicted as:

where $\tilde{y}$, $y^{+}$, and $y^{-}$ indicate the inferred location embedding, the ground truth of location which user $u$ visits at time $t_{n+1}$, and the randomly sampled negative data which user does not visit at $t_{n+1}$, respectively.

We compare the performance of our proposed TPG with baselines mentioned above. Table 2 reports the performance of TPG and eight baselines in terms of Recall@k and NDCG@k on five real world datasets. The “Improv.” column refers to the improvement rate of TPG compared to the second best model. Based on the results, we observe that:

(1) Our proposed TPG significantly outperforms all the baseline methods on all datasets w.r.t. both NDCG@k and Recall@k and all values of k. Our proposed method achieves up to 20.2% and 16.2% improvements over the best-performing baseline in terms of NDCG@5 and Recall@5. It demonstrates the effectiveness and superiority of our proposed TPG, which makes effective usage of geographic information and temporal signal of the next location.

(2) Compared with RNN-based approaches, pure attention-based methods such as MobTCast, STAN, GeoSAN, and our proposed TPG clearly achieve better performances. It is reasonable since attention mechanism can capture global contextual information in spatial-temporal check-in sequences, while RNN-based methods suffer from the risk of forgetting past long-range information. Among RNN-based models, DeepMove and CARA generally have relatively better performances than others, which attributes to their consideration of spatial-temporal modelling, and short-term and long-term periodicity modeling. These designations make up for the inherent defects of RNN to a certain extent. Compared with attention-based state-of-the-art model MobTCast, STAN, and GeoSAN, the substantial improvement achieved by TPG demonstrates the importance of explicitly using temporal signal of the next location and shifted window mechanism for geo-gridding. Although STAN generally performs better than MobTCast and GeoSAN, it costs extremely large memory overhead and calculation time overhead due to matrix operations for all historical check-ins. Our method TPG is far superior to other methods in terms of computing time, memory, and accuracy.

(3) The density of check-in records for different datasets can be represented by #check-ins $/$ (#users $\times$ #locations). The sparsities are 0.001, 0.007, 0.027, 0.009, and 0.120 for Gowalla, Brightkite, NYC, TKY, and SIN, respectively. This can explain why the improvement brought by TPG is larger in NYC and SIN than in TKY. Besides, it is obvious that TPG has a strong ability to handle sparse data like Gowalla.

By introducing temporal prompts, TPG is able to make interval predictions with accurate timestamps of locations to be predicted. Relevant results are given in Table 3. We here mask one (“int. 1” in Table 3), two (“int. 2” in Table 3), and three (“int. 3” in Table 3) most recent check-in(s) of users to test TPG and two baselines STAN and GeoSAN ’s performances on all datasets. The detailed setting is using first 96, 97, 98 check-ins to predict the 100-th check-in in each user’s trajectory.

For STAN and GeoSAN, we observe that compared with using all check-in data, the more the latest check-in(s) is/are masked, the more the performances drop marginally. It is reasonable since some previous studies (Pi et al., 2020) have demonstrated that a user’s recent behavior has a great impact on the user’s next behavior. However, the situation is totally different for TPG’s interval prediction. The performances are sometimes even better than the next location recommendation. These impressive results are very strong arguments for the benefit of explicit temporal information modeling by using timestamps as prompts.

We conduct an extensive ablation study on TPG, to dive into the effectiveness of each module in our proposed model. It should be emphasized that our base model (denoted as TPG in the first row of Table 4) does not have user embedding. We consider the following variants of our model for ablation:

• •

  Remove TP (Temporal-based Prompt): We use locations as query of the decoder, instead of using temporal-based prompts.

• •

  Remove TE (Time Embedding): We remove time embedding of check-in sequences, only using POI embedding and geography embedding as inputs of history encoder.

• •

  Remove SW (Shifted Window Mechanism): We remove the shifted window mechanism in the geography-aware encoder.

• •

  Remove GE (Geography Encoder): We remove the geography encoder and only use POI embedding and time embedding as inputs of history encoder.

• •

  Add UE (User Embedding): We add user embedding into the history encoder by concatenating it with POI embedding, geography embedding, and time embedding.

The performance comparisons are shown in Table 4. From the comparisons, we have several findings:

(1) The overall performance of the model drops without temporal-based prompts, especially on Foursquare datasets with local regions. This phenomenon indicates the significance of explicitly incorporating temporal signal of the next location. Furthermore, results of “Remove TE” is generally slightly better than “Remove TP” in Gowalla Foursquare datasets, while still worse than TPG. It indicates that if time information is not used appropriately, it brings additional noise to the model and degrades the performances. It also proves that the temporal-based prompt strategy proposed in this paper makes effective use of time information.

(2) The results of “Remove SW” is worse than original TPG in most cases. It demonstrates that our proposed shifted window mechanism is an efficient augmentation method for spatial information. It can bridge the semantic gap of adjacent grids in terms of spatial distribution, and improves the accuracy and stability of the model. Performances of “Remove GE” is even worse than “Remove SW”. It is reasonable since geographic information is of great significance in location-based applications.

(3) “Add UE” generally leads to great performance reduction compared with TPG. This is because adding user embedding to inputs of history encoder may contribute to the misaligned between the vector space of check-in sequences and the vector space of locations. This suggests future work to appropriately use user information to enhance the performance.

We conduct sensitivity analysis on two important parameters, namely, geography embedding dimension and step size of the shifted windows. We first investigate model sensitivity with regard to geography embedding dimension. We vary the dimension used in the geography-aware encoder from 10 to 60 with a step of 10. The experimental results on two datasets NYC and TKY are reported in Figure 6. We can come to a conclusion that a small dimension for geography embedding will make the performance very poor. This is because small dimensions are difficult to describe the complex geographic relationships between POIs, which will cause great information loss. The model performance reaches the peak when the geography dimension is 50. When the dimension increases to 60, the performance decreases a bit. This may be explained that the size of the semantic space formed by the geography-aware encoder is certain. When the embedding dimension is too high, the information is unsaturated, and noise may be introduced instead.

We further investigate model sensitivity with regard to the step size of the shifted windows. We vary the step size used in the shifted window mechanism from 0.25 to 1 with a step of 0.25. Note that the step size here means the proportion of moving length and grid size. We still take two datasets NYC and TKY as examples. The experimental results are showed in Figure 7. We can find that the performance peaks at a small step size 0.25 for shifted window mechanism, and dropped until the step size is 0.75. Such phenomenon conforms to the First Law of Geography, which indicates “everything is related to everything else, but near things are more related than distant things.” We can also observe that when the step size is 1, there is a performance improvement. When the step size is 1, the model actually degenerates to directly aggregate the neighbor grids of the grid itself at each level. This phenomenon proves the defect of previous methods, that is, they do not fully consider the correlations of adjacent grids.