Discovering Collaborative Signals for Next POI Recommendation with Iterative Seq2Graph Augmentation

1 Introduction

The fast growth of location-based social networks (LBSNs) facilitates the development of point-of-interest (POI) recommender systems, which help users explore attractive places by capturing their preferences from visiting history [Cheng et al., 2013; Feng et al., 2015; Yin and Cui, 2016; Chang et al., 2020]. Among a variety of POI recommendation tasks, next POI recommendation is arguably the most prominent one. Unlike conventional POI recommendation that only considers users' general long-term preferences, next POI recommendation suggests a user the most suitable destinations based on a short check-in trajectory, thus requiring the model to effectively capture dynamic user preferences and account for temporal influences.

The majority of next POI recommendation approaches are based on sequential models, ranging from the simplistic Markov chain (MC) [Cheng et al., 2013] and SkipGram methods [Feng et al., 2017] to the recently dominating recurrent neural networks (RNNs) [Li et al., 2018; Zhao et al., 2020]. In a nutshell, those sequential models take an arbitrary user's POI check-in sequence as their input, and learn the latent representations of both POIs and user preferences to facilitate inference of the next POI.

With the demonstrated capability of learning informative POI and user representations from sequential data, RNNbased models are currently the state-of-the-art solutions to most next POI recommendation tasks [Liu et al., 2016; Sun et al., 2020; Zhao et al., 2020; Wang et al., 2020; Li et al., 2019]. Despite the versatility of sequential POI recommenders, most existing approaches lack the ability to uncover the collaborative signals [Wang et al., 2019] among relevant POIs when learning POI representations. More concretely, the recommendation process of most sequential approaches is purely conditioned on the POIs within the given sequence, neglecting the rich contexts from highly correlated POIs across sequences. Take Figure 1(a) as an example, POIs p1, p4 and p7 from three POI sequences all transit to POI p2, demonstrating strong semantic correlations that can potentially enrich the expressiveness of p2's learned representation. However, as each POI sequence is assumed to be independent of other sequences in those sequential methods, such high-order collaborative signals (see Figure 1(b)) could hardly be captured from all scattered POI sequences, which results in the degradation of model performance. Consequently, given the commonly sparse data on POI-POI transitions [Yin et al., 2016; Qian et al., 2019], the expressiveness of learned POI representation is heavily constrained, impeding the eventual recommendation effectiveness.

Therefore, we aim to address the aforementioned limitations in the existing sequence modelling scheme of next POI recommenders. Instead of straightforwardly modelling independent POI sequences, we innovatively present a solution with graph-augmented POI sequences. Essentially, in a graph-augmented POI sequence, POIs are nodes that are chronologically ordered and associated with neighbour POI nodes via semantic edges, e.g., the one-hop transition relationships observed from other sequences. We refer to this notion as Seq2Graph augmentation in our paper. On the one hand, by bringing the notion of graph-structured data to POI sequences, we can effectively infuse various contexts (e.g., correlated POIs and side information like category tags) into each learned POI representation. As illustrated in Figure 1(b), by augmenting the three sequences with Seq2Graph, p2's surrounding POI nodes offer rich knowledge for describing the properties of p2, hence, the collaborative signals from semantically correlated POIs are thoroughly utilised for learning high-quality POI representations. On the other hand, the capability of learning complex sequential dependencies among POIs is fully retained by the augmented sequences.

To this end, we propose the Sequence-to-Graph POI Recommender (SGRec), a novel solution to next POI recommendation that simultaneously leverages the information from both the graph and sequence sides. In SGRec, we first build a category-aware graph attention layer, which embeds every POI in the sequence by merging the contexts from its neighbour POI nodes. Though in general sequential recommendation, recommenders based on graph neural networks (GNNs) [Wu et al., 2019; Qiu et al., 2020b; Qiu et al., 2020a] start to emerge, the embedding of each item (i.e., node) is mostly learned by aggregating the latent features of co-occurring items from the same input sequence, where the collaborative signals are overlooked. In contrast, SGRec makes full use of the information from neighbour POI nodes sampled from all other POI sequences to learn POI embeddings, which subsequently benefits the learning of user temporal preferences via a position-aware attention mechanism. To further alleviate the data sparsity, we introduce category-awareness into our proposed model. Specifically, we innovatively design an auxiliary objective of learning category-wise transitions. Intuitively, we bind the directional category-category relations with the edges between two connected POIs when learning POI embeddings, and ask the model to predict the category of the upcoming POI, which is in parallel with the next POI prediction task. By gaining knowledge from the much denser category-wise interactions, SGRec can effectively enhance its capability of learning the fine-grained sequential dependencies and users' temporal preferences, thus yielding better performance in next POI recommendation.

The contributions of our paper are three-fold:

• We introduce a new take on modelling POI sequences for recommendation by constructing graph-augmented POI sequences to fully capture the collaborative signals from semantically correlated POIs while mining sequential properties.
• We propose SGRec, a novel next POI recommender that selectively aggregates information from both neighbour POI nodes and edges to expressively embed POIs in a sequence. Besides, with an additional focus on learning category-wise transition patterns, SGRec further complements its capability of learning sequential dependencies from sparse POI-level interactions.
• We extensively evaluate SGRec on two benchmark datasets, where the results suggest that it outperforms the state-of-the-art baselines with significant margins.

2 RelatedWork

Next POI recommendation mainly explores user-POI interactions and the temporal influences to make recommendation on user's next move. The consecutive check-ins that happen in a relatively short time period carry strong sequential information. Cheng et al.[2013] combine first-order Markov chain and matrix factorisation techniques to model POI-POI transitions and user-POI interactions. Recently, recurrent neural networks (RNNs) have demonstrated superior power in sequential data modelling, which drives the studies on exploring user transition patterns. Liu et al.[2016] extend the vanilla RNN with time-specific and distance-specific transition matrices for spatial and temporal pattern modelling. Li et al.[2018] use LSTM with attention mechanism to adaptively choose important contextual factors for recommendation. Meanwhile, Zhao et al.[2019] add time and distance gates into LSTM to capture users' dynamic preferences.

Different from those existing work that mainly adapts RNNs for sequential pattern mining, which do not explicitly consider the POI correlations across sequences, our work transforms sequences into graph-structured data, thus enabling the proposed GNN-based model to explore the important cross-sequence collaborative information.

3 Preliminaries

Let P = {p1, p2, ..., p|P|}, U = {u1, u2, ..., u|U|}, and C = {c1, c2, ..., c|C|} be the sets of POIs, users and POI categories. We use boldface letters for all latent vectors, e.g., p, u, c ∈ RD to denote the features of the POI p ∈ P, the user u ∈ U and category c ∈ C, where D is the dimension size.

Definition 1: POI. A POI represents a specific location, e.g., a cinema. Each POI p ∈ P is associated with a category label cp ∈ C.

Definition 2: Check-in. A check-in record can be represented by si = (u, p, cp, t), where u ∈ U, p ∈ P, cp ∈ C and t denotes the timestamp when the check-in is observed.

Definition 3: Check-in Sequence. A check-in sequence is a set of chronologically ordered check-in records of a certain user within a short time interval, e.g., 24 hours. We use S = {s1, s2, ..., sn} to denote a check-in sequence, where the last check-in sn is recorded from user's current location pn. Problem 1: Next POI Recommendation. Given a check-in sequence Su of user u, our goal is to recommend K POIs that u is likely to visit at her/his next move.

4 Methodology

In this section, we first describe the process of Seq2Graph augmentation. Then, we present the details of our proposed SGRec model illustrated in Figure 2.

4.1 Seq2Graph Augmentation

Graph-Augmented POI Sequences. Given a check-in POI sequence Su, each visited unique POI is treated as a node vp, indexed by p. Two consecutive POI nodes are connected by a directional edge, i.e., vpi → vpi+1 indicating the user moved from the POI pi to pi+1, where 1 ≤ i ≤ n - 1. As shown in Figure 2, in a graph-augmented POI sequence, each POI node vp from sequence Su owns a set of first-order neighbour nodes denoted by N(vp). In particular, for q ∈ P, we have vq ∈ N(vp) if a directional edge vq → vp appears in existing POI sequences belonging to the user u. Note that vp is also added into N(vp). An augmented sequence of Su is denoted by Gs = {Vs, Es} = {N(vp1 ) ∪ N(vp2 ) ∪ ... ∪ N(vpn ), E(vp1 ) ∪ E(vp2 ) ∪ ... ∪ E(vpn )}, where we use Vs and Es to represent the sets of all nodes and edges within Gs, and N(vpi ) and E(vpi ) to denote the sets of all neighbour nodes and edges regarding the i-th POI vpi in the sequence Su, respectively.

Iterative Seq2Graph Augmentation. Though a check-in POI sequence is usually short, each POI in the sequence may appear in multiple POI sequences. Thus, to incorporate richer contextual information and alleviate the data sparsity, we propose to collaboratively investigate different visited POIs with graph-augmented POI sequences. Due to the potentially high computational cost and excessive noise incurred by the sheer amount of neighbour nodes for each POI in the sequence, we present a dynamic neighbour node sampling in SGRec, which obtains a subset of nodes for subsequent computation in each training epoch. Concretely, as shown in the left side of Figure 2, given one sequence Su, we first obtain all neighbour nodes associated with the original sequence Su, then generate Gs by uniformly sampling a certain proportion γ of nodes from the neighbour sets. The sampling strategy in Seq2Graph augmentation will be re-executed in each training epoch. As a result, different variants of the graph-augmented POI sequences are generated, bringing diverse cross-sequence contextual information into the given check-in sequence. The augmented sequences are then fed into our proposed SGRec model for learning POI representations and user preferences.

4.2 Category-Aware Graph Attention Layer

Introducing category-awareness to GNN could enable the model to learn from the much denser sequential dependencies among POI categories on top of modelling the sparse POI transitions. In SGRec, we design a category-aware attention mechanism when aggregating node information, which seamlessly infuses categorical side information into POI embeddings. First, we create an embedding vector rci→cj ∈ RD

for each unique category-wise transition relation ci → cj . Instead of defining a separate category sequence, for each POI node vp ∈ G, we concatenate the POI embedding with its corresponding category embedding to build a unified node embedding:

where p and cp are respectively node vp's POI and category latent vectors, and [·; ·] denotes a concatenation operation.

One major advantage of SGRec against existing GNNbased sequential recommenders [Wu et al., 2019; Qiu et al., 2019] is its capability of considering the heterogeneous edge information, i.e, the association between POI categories. Specifically, each directed edge from Es corresponds to a pair of categories (e.g., food → hotel). As proved in the work of GAT [Velickovic et al., 2018], selectively aggregating information from the target node's neighbours is beneficial for learning high-quality embeddings. However, it is devised for the nodes with only homogeneous pairwise relationships. Inevitably, in our graph-augmented POI sequences where diverse edges (i.e., different category-wise relations) exist between two POI nodes, quantifying the pairwise attention between nodes will sacrifice such crucial contextual information. Thus, we propose a novel attention network, where the interactions between two nodes are additionally conditioned on their edge's properties. In our case, for each POI node vp ∈ G and its neighbour vq, the feature of their directional edge q → p corresponds to the relation embedding rcq→cp . We first inject the edge feature into the neighbour node embedding via a non-linear transformation:

where wa ∈ R2D×2D is a trainable weight matrix and MLP(·) : 4D → 2D denotes a multi-layer perceptron.

Then, we devise a scoring function a(·, ·) to measure the importance of neighbour node vq to the target node vp:

where Wb ∈ R2D×2D is a transformation matrix, and Wgat ∈ R4D and bgat ∈ R are the weight matrix and bias.

Afterwards, we use softmax to normalise the calculated attention scores across all vp's neighbours:

Finally, we obtain the updated node embedding of vp, i.e., hp, via the following:

where Φ ∈ R2D×2D is a trainable weight matrix. For every vp ∈ Gs, the produced compact embedding hp ∈ R2D encodes the information from both corresponding neighbour POIs and category labels, while the impact from categorywise dependencies and spatial factor is further taken into account during the information aggregation stage in Eq. (5). Recall that hp is an updated version of vp, with its first and second halves correspond to embeddings of the POI p (i.e., p) and its category (i.e., cp). In order to capture higher-order information, we update p and cp using the first and second half of hp after every training epoch, respectively:

where we use hp(a : b) to denote the operation of obtaining the values from a-th dimension to b-th dimension of the vector hp and ← is an assignment operator. In this way, the topological information of the global POI transition patterns is preserved in the embedding layer.

4.3 User Temporal Preference Encoding

So far, the latent POI representation hp carries relevant spatial and categorical perspectives. However, in POI recommendation, the final decision is also heavily associated with users' short-term preferences. [Wu et al., 2019] applies an attention mechanism that estimates the impact of historical data points to the last one. However, simply applying the attention mechanism on all POI embeddings hardly capture sufficient sequential and spatial properties from the data. To this end, inspired by [Zhang et al., 2017], we design a positionaware attention mechanism that encodes the sequential information into the final embedding via positional embeddings. Intuitively, the impact of previous check-ins on the current one will degrade through time. For example, given two sequences: p1 → p2 → p4 and p1 → p2 → p3 → p5 → p6 → p4. p2's influence to p4 is apparently higher in the first sequence. In this regard, we define a positional embedding matrix Q = [q1, q2, ..., qn] ∈ Rn×D , which assigns a unique latent embedding to each offset position. Here, n equals to the maximum length of the truncated sequences in the dataset. Specifically, for the i-th POI pi in Su, we first assign the position embedding qn-i+1 to it, where n - i is the offset between the i-th check-in and the last one. Then, we build an attention scoring function b(·, ·) that incorporates the sequential information (i.e., relative position) to estimate the impact of pi to the last POI pn:

where {Wh1,Wh2} ∈ R2D×D , Wq ∈ RD×D and Wpat ∈ RD are trainable weight matrices. Finally, we encode the user's short-term preferences into a single sequence-level embedding vector s ∈ R2D through an attentively weighted sum across all POI embeddings within Su:

4.4 Next POI and Category Prediction

Regarding the large amount of POI candidates, the sparsity of observable transitions between POIs sets an obstacle for deep models to fully capture useful POI-wise sequential dependencies for recommendation. In contrast, the category tags associated with POIs are significantly denser in terms of both quantity and pairwise transitions. In light of this, we formulate a multi-task learning scheme in SGRec, which jointly predicts the exact POI and the next POI category for the user's next visit. Specifically, we first estimate the probability that each POI will be visited:

where Wp ∈ R2D×|P| and bp ∈ R|P| are the transformation matrix and bias of a fully-connected layer, ◦ denotes the element-wise multiplication which fuses the user's sequencelevel temporal preference (i.e., s) with her/his instant preference (i.e., the most recent POI representation hpn ), u is the user's long-term preference embedding.

Besides, the next POI category can be predicted via:

where Wc ∈ RD×|C| and bc ∈ R|C| are the transformation matrix and bias of a fully-connected layer, and cpn ∈ RD is the last POI's category embedding. The rationale of designing this auxiliary task is to enhance our model's capability of capturing category-wise transitions, which is a crucial context in next POI recommendation. In the inference phase, we only perform POI prediction, and select K POIs with the highest probabilities in ̂ypoi as the top-K recommendation result.

4.5 Model Optimisation

We apply the cross-entropy loss function to quantify the error of both POI and category prediction tasks for SGRec:

where m ≤ M is the index of training samples, ypoi m and ycat m are the one-hot vectors of POI and category ground truths respectively. η is a hyperparameter that decides the weight of next category loss, and Ψ is the set of all trainable parameters for L2 regularisation under the control of λ. Such multi-task training objective enhances our model's capability of bridging the crucial recommendation context (i.e., the upcoming POI category) with user preferences, thus allowing for accurate POI recommendation under data sparsity.

5 Experiments

5.1 Datasets and EvaluationMetrics

We evaluate our proposed SGRec on two public realworld check-in datasets, which are originally crawled from Foursquare and Gowalla and have been extensively used in the previous studies. Foursquare dataset 1 includes check-ins recorded in Tokyo from Apr. 2012 to Feb. 2013. Gowalla dataset 2 contains the check-in records over the world from Feb. 2009 to Oct. 2010. We first filter out the inactive users who have less than 10 check-ins and unpopular POIs that are visited by less than 10 users. Then, we sort the check-in records of each user in ascending order of timestamp and split them into sequences when the time interval of two consecutive check-ins is longer than 1 day and 3 days for Gowalla and Foursquare, respectively. We then discard the sequences that have less than 10 check-ins to ensure the sequence length and truncate long check-in sequences by setting maximum sequence length n = 20. Finally, we randomly choose 80%, 10% and 10% of each user's check-in sequences from both datasets as training, validation and test sets. The statistics of both preprocessed datasets are summarised in Table 1.

We choose Hit Ratio at Rank K (HR@K) and Normalised Discounted Cumulative Gain (nDCG@K) at Rank K on topK ranked POIs, which are commonly adopted in information retrieval and recommender systems [Chen et al., 2019; Chen et al., 2020] for top-K performance and overall ranking performance, respectively. In each test check-in sequence, the last check-in record is used as the ground truth, and the remaining parts are fed into the model for prediction. Note that the Seq2Graph augmentation is not applied in the test.

1 https://sites.google.com/site/yangdingqi/home

2 http://snap.stanford.edu/data/loc-gowalla.html

5.2 Baseline Methods

We compare SGRec with the most representative next POI approaches: 1) FPMC-LR [Cheng et al., 2013]: The model combines the first-order Markov chain and matrix factorisation for next POI recommendation. 2) GRU [Cho et al., 2014]: A popular variant of RNN, which controls the information flow using two gates. 3) TMCA [Li et al., 2018]: The model uses LSTM equipped with a multi-level attention module to fuse each POI information into a sequence vector. 4) ST-CLSTM [Zhao et al., 2019]: A state-of-the-art method that introduces two additional gates in LSTM on the time interval and distance to capture the spatial-temporal contexts. 5) SR-GNN [Wu et al., 2019]: Currently, there is no existing GNN-based next POI recommenders. Thus, we consider SRGNN, a GNN-based model for sequential recommendation, as our baseline method.

5.3 Implementation Details

SGRec is implemented using PyTorch with Nvidia GTX 1080 Ti. For consistency, we apply the same dimension size D for all embeddings and weight matrices. Specifically, we set the D to 120, neighbour sampling rate γ to 0.2, category loss weight η to 0.2 and the number of stacked CA-GAT layers to 2 and 3 for Foursquare and Gowalla, respectively. All the trainable parameters in our model are optimised using Adam optimiser with the batch size of 64, learning rate of 0.005 and L2 regularisation strength λ of 1e - 5.

5.4 Analysis on Recommendation Effectiveness

We summarise the evaluation results of all models on next POI recommendation task with Table 2. From the statistics in the table, we can draw the following observations:

1) The results on Foursquare and Gowalla datasets show that our proposed SGRec significantly outperforms all baseline methods on both evaluation metrics. On Gowalla dataset, compared with the second-best approach ST-CLSTM, SGRec gains 4.15% and 7.36% improvement on HR@5 and nDCG@5 respectively. On Gowalla dataset, SGRec provides around 35% improvement on average over the best competitors, which clearly demonstrates the effectiveness of SGRec. It is worth mentioning that the density of observed user-POI interactions of Gowalla (0.001) is substantially lower than that of Foursquare (0.052), the huge performance improvement on Gowalla dataset further proves the strong capability of our model on handling sparse data.

2) RNN-based methods (GRU, TMCA and ST-CLSTM) perform better than MC-based method, FPMC-LR mainly because of their ability to capture long-term user preferences. Among all RNN-based methods, ST-CLSTM receives the best results. This is because TMCA merely measures the importance of different POIs within a single sequence yet neglects the time influence. However, due to the lack of capturing the collaborative signals across sequences, those RNNbased methods result in sub-optimal performance.

3) SR-GNN receives comparable results as ST-CLSTM. It proves the capability of GNN in unveiling the implicit POI transitions. However, since SR-GNN ignores the temporal sequential signals when modelling POI transition patterns, it is inferior to our method on both datasets.

5.5 Ablation Study

To verify the contribution of each proposed component in SGRec, we implement several degraded versions of SGRec for ablation study. The results of ablation tests on Foursquare and Gowalla datasets are presented in Table 3.

After either disabling Seq2Graph augmentation or removing CA-GAT, SGRecns and SGRecw/o.cagat both suffer from similar decreases in the performance on both datasets due to the loss of collaborative signals. When the next category prediction objective is removed, SGRecnc has a clear performance drop proving that learning category-level transitions is effective for alleviating the POI-level sparsity. By removing the position-aware attention module, SGRecw/o.pattn receives performance degradation, which implies that capturing the sequential information and user temporal preferences is of great importance for the next POI task.

5.6 Hyperparameter Analysis

We further analyse the impact of different hyperparameter values to SGRec, the results are shown in Figure 3. Figure 3(a) describes HR@20 for various dimensionality values ranging from 20 to 200 on two datasets. The model reaches the best performance when D = 120. We also examine the impact of different neighbour sampling rates. As shown in Figure 3 (b), the model performance has a clear growth when the rate goes up from 0% to 10%. It is worth noting that we disable the iterative embedding update, i.e., Eq.(6), when γ = 0%. The result depicts the generalisation capability of SGRec on large-scale datasets since the full power of our model can be exploited with a small number of sampled neighbours. However, the performance has a slight drop when γ ≥ 30% on Foursquare. We think this is because sampling too many neighbours will become harmful to preserve the original sequence's information. Figure 3(c) shows the impact of the category loss weight coefficient η, the model has best performance when η = 0.4. Figure3(d) shows that stacking 2 and 3 CA-GAT layers in SGRec can achieve the best performance on both datasets.

6 Conclusion

To deal with the lack of collaborative information and sparse POI-wise interactions within existing sequential POI recommenders, we propose a novel solution named SGRec in this paper. SGRec introduces the notion of Seq2Graph augmentation for incorporating collaborative signals when learning POI embeddings, and leverages its category-awareness to enhance the user preference modelling capacity. Our extensive experiments fully show the effectiveness and robustness of SGRec, demonstrating its strong real-life practicality.

Acknowledgements

This work is partially supported by Australian Research Council Discovery Project (ARC DP190102353, DP190101985, CE200100025).