Bi-Level Graph Structure Learning for
Next POI Recommendation

Next POI recommendation aims to infer the users’ dynamic preferences and predict where the user will go next, given the historical check-ins and a set of POI candidates.

Recurrent neural networks (RNNs) and self-attention have shown promising performance in handling sequential data, hence they have been widely used as the backbone of the next POI recommenders [15, 16, 17, 18]. Some studies are dedicated to capturing sequential dependencies in sequences to model the dynamic user preferences [19, 20, 21, 22]. On the other hand, POI features and historical check-ins contain rich collaborative signals, such as spatial location, visited time, and frequency of consecutive visits, and are therefore leveraged to make more effective recommendations from sparse data. Early works introduce these collaborative signals directly into the backbone, such as computing transition matrices or gates in RNNs [23, 24, 25, 26] and attention maps in self-attention [27].

Recently, it has been found that these collaborative signals can be represented by graphs and the GNNs can be employed to effectively capture the correlations among POIs [12, 3, 13]. For example, STP-UDGAT [1] constructs three types of POI graphs based on the spatial distance, time interval, and consecutive visiting, so as to learn user preferences in different views. GETNext [6] introduces a global trajectory graph to better leverage the extensive collaborative signals from different users. HMT-GRN [4] constructs global spatio-temporal graphs to model collaborative signals among POIs and utilizes auxiliary tasks to alleviate the data sparsity issue.

Although great success has been achieved, these existing graph-based methods rely on pre-defined rules to construct graphs, which leads to noise and incompleteness in the graph and degenerates the performance of GNNs [28]. Although GraphFlashback [2] attempts to automatically learn latent POI graphs based on a holistic knowledge graph, the topology of such latent graphs lacks interpretability and still neglects the underlying hierarchical structure in POI features. SNPM [29] is another attempt to infer latent graph structures. However, it only considers relationships within the same region and remains constrained by a pre-defined graph structure. Our proposed BiGSL addresses the above issues by hierarchical and pairwise structure learning.

Although GNNs have achieved superior performance in analyzing graph-structured data, most GNNs are highly sensitive to the quality of graph structures and usually require a credible graph structure that is hard to construct in real-world applications [30]. Given that GNNs recursively aggregate information from neighborhoods to update node embeddings, the iterative nature of this process has consequential cascading effects. Small noise in a graph will be propagated to the neighboring nodes, subsequently affecting the embeddings of numerous other nodes [14, 31]. Recently, considerable literature has arisen around the theme of graph structure learning (GSL), which targets at jointly learning an optimized graph structure and corresponding representations. Existing GSL methods can be roughly grouped into three categories: metric learning that models or refines the edge weights by measuring the similarity between node representations [32, 33, 34], probabilistic modeling that models the probability distribution of edges and then samples a graph from this distribution [30, 35, 36], and direct optimization that treats the graph adjacency matrix as parameters and optimizes it directly along with GNN parameters [37, 38, 39].

Although these studies leverage graph structure learning to refine the graph structures, they are not tailored for next POI recommendation. They only learn pairwise relationships between nodes and lack consideration on meaningful hierarchical structure. NCL [40] extracts coarse-grained prototypes for cross-granularity contrastive learning in graph collaborative filtering, inspiring us to construct hierarchical graph structures using prototypes. Distinct from previous graph structure learning methods, we not only adaptively learn pairwise relationships between POIs to suppress the potential noise, but also construct hierarchical structures to further enrich the neighborhoods of POIs by extracting POI prototypes, so as to capture the global relationships between POIs effectively and provide accurate recommendations.

The key components of our proposed BiGSL are model-agnostic and can be plugged into any sequential recommendation model. To show the effectiveness of our approach, we choose a simple yet effective recommender as the backbone, which contains only an embedding layer, an LSTM layer and a dense layer with softmax normalization.

The embedding layer offers dense POI ID embeddings and user ID embeddings. We describe a POI $l_{i}$ (a user $u_{m}$) with an embedding vector $\boldsymbol{l}_{i}\in\mathbb{R}^{d_{2}}$ ($\boldsymbol{u}_{m}\in\mathbb{R}^{d_{2}}$), where $d_{2}$ denotes the embedding size.

Based on the aforementioned backbone, we point out that existing methods, which employ conventional GNNs on manually constructed graphs to encode the interaction relationship between POIs, cannot model the hierarchical information well. To address this concern, we propose a hierarchical structure learning method to embed the hierarchical information in the graph structures explicitly.

To model the hierarchical nature in POI features, we propose a hierarchical structure learning method. We design a hierarchical structure learning objective to group POIs into different clusters and extract prototypes. Roughly speaking, prototypes can be regarded as the center of clusters that represent a group of semantically similar POIs.

Formally, the goal of graph structure learning is to maximize the following log-likelihood function:

where $\mathbf{\Theta}$ is learnable parameters of model, $\mathbf{X}$ is primitive features of POIs, $\boldsymbol{z}_{i}\in\mathbb{R}^{d_{2}}$ is the learned structure embedding of POI $l_{i}$ that will be used to construct the graph structure. $C$ is the set of cluster centroids, and we use $K=|C|$ to denote the number of clusters. The objective in Eq. 3 is hard to optimize directly because $\boldsymbol{z}_{i},\boldsymbol{c}_{j}$ are both free variables. Therefore, we introduce its tractable lower bound by Jensen’s inequality:

where $Q\left(\boldsymbol{c}_{j}\mid\boldsymbol{z}_{i}\right)$ denotes the distribution of latent variable $\boldsymbol{c}_{j}$ when $\boldsymbol{z}_{i}$ is observed. The goal of graph structure learning can be reformulated to maximize the function over $\boldsymbol{z}_{i}$ when $Q\left(\boldsymbol{c}_{j}\mid\boldsymbol{z}_{i}\right)$ is estimated. Since the cluster centroids are latent, we introduce the Expectation–Maximization (EM) algorithm to formulate the optimization process.

In the E-step, $\boldsymbol{z}_{i}$ is fixed and $Q\left(\boldsymbol{c}_{j}\mid\boldsymbol{z}_{i}\right)$ can be estimated by K-Means algorithm over all $\boldsymbol{z}_{i}$. The distribution is estimated by a hard indicator $\hat{Q}\left(\boldsymbol{c}_{k}\mid\boldsymbol{z}_{i}\right)=1$ if POI $l_{i}$ belongs to $k$-th cluster, and $\hat{Q}\left(\boldsymbol{c}_{j}\mid\boldsymbol{z}_{i}\right)=0$ for other centroids $\boldsymbol{c}_{j}$.

In the M-step, we fix $\hat{Q}\left(\boldsymbol{c}_{j}\mid\boldsymbol{z}_{i}\right)$ and optimize $\boldsymbol{z}_{i}$. By introducing hard indicator $\hat{Q}\left(\boldsymbol{c}_{j}\mid\boldsymbol{z}_{i}\right)$, maximizing the lower bound in Eq. 4 yields a loss function:

Taking inspiration from NCL [40], we assume that the distribution of POIs is isotropic Gaussian over their corresponding clusters and each Gaussian distribution has the same variance. Therefore, the loss function can be written as:

where $\boldsymbol{c}_{k}$ is the centroid of the cluster to which POI $l_{i}$ belongs, and $2\sigma^{2}$ is represented by a temperature coefficient $\tau_{1}$. Since $\boldsymbol{z}_{i}$ and $\boldsymbol{c}_{j}$ have been $l_{2}$-normalized in advance, we can leverage $\left(\boldsymbol{z}_{i}-\boldsymbol{c}_{j}\right)^{\top}\cdot\left(\boldsymbol{z}_{i}-\boldsymbol{c}_{j}\right)=2-2\boldsymbol{z}_{i}^{\top}\boldsymbol{c}_{j}$ to simplify the loss function.

This objective suggests that in the M-step, the structure embedding of each POI and its corresponding cluster centroid should be as close as possible. We achieve this by iteratively conducting K-Means in the E-step and minimizing $\mathcal{L}_{HSL}$ in the M-step. With the above objective, the hierarchical nature in POI features can be captured in the structure embedding and the prototypes can be obtained by averaging POI representations in each cluster. The prototype will be used to represent the coarse-grained semantics of clusters and to extend the neighborhoods of POI nodes.

Compared to heuristic grouping approaches, such as grouping temporal features by date, our clustering-based method enables the adaptive uncovering of intricate hierarchical structures in POI features, which may be irregular and not aligned with pre-defined heuristic rules.

After hierarchical structure learning, we can define an adjacency matrix $\mathbf{A}^{\mathrm{Hier}}\in\mathbb{R}^{N\times K}$ between POIs and prototypes based on the hard indicator:

Although hierarchical structure information has been explicitly captured, the GNNs are still susceptible to the presence of data noise and incompleteness in the graph structures. Traditional rule-based graph construction relies on pre-defined rules or assumptions, inevitably leading to noisy and missing edges. In contrast, graph structure learning methods can alleviate these issues by automatically identifying patterns and inferring the topological structure.

To address the issue of noisy and incomplete graphs, we adopt a deep graph structure learning method to learn pairwise relationships between POIs adaptively:

where $\boldsymbol{x}_{i}\in\mathbb{R}^{d_{1}}$ is the primitive feature (e.g., latitude and longitude in the spatial view) of POI $l_{i}$, which is used to construct graphs, $\boldsymbol{z}_{i}\in\mathbb{R}^{d_{2}}$ is the structure embedding transformed by learnable parameters $\mathbf{W}_{1}\in\mathbb{R}^{d_{2}\times d_{1}},\mathbf{W}_{2}\in\mathbb{R}^{d_{2}\times d_{2}},\boldsymbol{b}_{1},\boldsymbol{b}_{2}\in\mathbb{R}^{d_{2}}$. $\mathbf{A}^{\mathrm{POI}}\in\mathbb{R}^{N\times N}$ is the adjacency matrix of POI graph. To refine $\mathbf{A}^{\mathrm{POI}}$ into a sparse and normalized adjacency matrix, we also conduct $\epsilon$-neighborhood sparsification and normalization post-processing, which are widely used in graph structure learning [41, 42, 43].

Distinct from the previous methods that only consider the resemblance between POIs, we also capture the relationships between coarse-grained prototypes to further explore the hierarchical structure. Following the pairwise structure learning defined in Eq. (8) and (9), we take the cluster centroids as the primitive features to construct the connections between the prototypes:

Following bi-level graph structure learning, we obtained bi-level graphs that encompass both fine-grained POI-level information and coarse-grained prototype-level information. The prototype-level information unveils the collective characteristics of similar POIs. A conventional graph can be symbolized as $\mathcal{G}=(\mathcal{V},\mathbf{A})$, where $\mathcal{V}$ represents the set of nodes, and $\mathbf{A}$ denotes the adjacency matrix. We present the formalized notation for a bi-level graph as $\mathcal{G}=(\mathcal{V}^{\mathrm{POI}},\mathcal{V}^{\mathrm{Proto}},\mathbf{A}^{\mathrm{POI}},\mathbf{A}^{\mathrm{Proto}},\mathbf{A}^{\mathrm{Hier}})$, where $\mathcal{V}^{\mathrm{POI}}$ and $\mathcal{V}^{\mathrm{Proto}}$ respectively signify the sets of POI nodes and prototype nodes, and $\mathbf{A}^{\mathrm{POI}}\in\mathbb{R}^{N\times N},\mathbf{A}^{\mathrm{Proto}}\in\mathbb{R}^{K\times K},\mathbf{A}^{\mathrm{Hier}}\in\mathbb{R}^{N\times K}$ are the three adjacency matrices learned through bi-level graph structure learning. These matrices portray the interconnections between POI-POI, prototype-prototype, and POI-prototype, respectively.

The hierarchical and pairwise structure learning methods produce high-quality hierarchical graphs, which not only are confronted with less noise and missing information, but also manifest the hierarchical information in POI features through the graph topology.

To fully exploit the learned hierarchical graphs, we design a multi-relational graph attention network. First, we define the neighborhood of each POI node based on the hierarchical graph. As shown in Fig. 3, we define three types of neighbor nodes. As “” is the target node to be updated, “” represents the connected POI nodes that are most semantically similar to the target node, “” is the prototype of cluster that the target node belongs to, which can provide coarse-grained information about this group of similar nodes, and “” represents 2-hop prototype neighbors that provide information about more potential similar groups. Thus, there are three types of relations between target node and its neighbor nodes: $\mathcal{R}=\{\raisebox{-0.1pt}{\includegraphics[width=9.49997pt]{./figures/icons/icon_target_node.pdf}}-\raisebox{-0.1pt}{\includegraphics[width=9.49997pt]{./figures/icons/icon_poi_neigh.pdf}},\raisebox{-0.1pt}{\includegraphics[width=9.49997pt]{./figures/icons/icon_target_node.pdf}}-\raisebox{-0.1pt}{\includegraphics[width=9.49997pt]{./figures/icons/icon_1hop_proto_neigh.pdf}},\raisebox{-0.1pt}{\includegraphics[width=9.49997pt]{./figures/icons/icon_target_node.pdf}}-\raisebox{-0.1pt}{\includegraphics[width=9.49997pt]{./figures/icons/icon_2hop_proto_neigh.pdf}}\}$. Then, the graph representation learning is defined as:

where $\boldsymbol{l}_{i}\in\mathbb{R}^{d_{2}}$ denotes the ID embedding of POI $l_{i}$, $\boldsymbol{p}_{i}\in\mathbb{R}^{d}_{3}$ is the hidden representation learned from the bi-level graph, and $\mathcal{N}^{r}_{i}$ denotes the neighborhood of $l_{i}$ under relation $r\in\mathcal{R}$. $\mathbf{W}_{r}\in\mathbb{R}^{d_{3}\times d_{2}}$ and $\boldsymbol{a}_{1}\in\mathbb{R}^{2d_{3}}$ are learnable weights, and $\phi(\cdot)$ denotes LeakyReLU activation function. $W_{r}$ is subscripted with $r\in\mathcal{R}$, indicating that aggregation patterns at different levels are modeled separately. The information propagation from $\boldsymbol{l}_{j}$ to $\boldsymbol{l}_{i}$ is controlled by attention weight $\alpha_{ij}$ and topology score $s_{ij}$, which is related to learned graph structure:

where $l_{i}$ belongs to the $p$-th cluster when $j$ is $2$-hop prototype neighbor.

In POI recommendation, multiple features are widely used to construct graphs, such as spatial graph, temporal graph, and transition graph. We claim that each feature provides a feature view. In each view, a set of POI representations can be obtained by conducting graph representation learning. POI representations derived from multiple views convey both shared and complementary information. However, existing methods for fusing representations tend to rely on simple techniques such as summation or concatenation. As a result, important informative features may be overlooked.

In deep learning, linear disentanglement has been used to obtain distinguishable and generalizable representations [44, 45]. To fully exploit the information embedded in multiple views, we propose a contrastive multiview fusion method that captures both view-shared and view-specific information. Each POI representation is decomposed into view-shared and view-specific parts. View-shared information denotes the common characteristics of POIs across all views. Extracting view-shared information aids in constructing robust and generalizable POI representations. In contrast, view-specific information reflects the unique attributes of POIs within a specific view. For instance, a pair of POIs might exhibit strong geographical connections but not exhibit the same peak visitation times. By distinguishing view-specific information, our model can more flexibly adapt to the information presented by different views, offering potential for explaining the decision-making process.

To achieve the aforementioned semantic decoupling, we introduce two optimization objectives to guide the semantics of the learnable representations.

First, we employ contrastive learning to extract view-shared representations. Henceforth, we employ the symbol $\boldsymbol{p}_{i}^{v}$ to represent the latent representation of the $i$-th POI, obtained through the multi-relational graph attention network within the feature view $v$. Contrastive learning aims to enhance the agreement among diverse views of the same data and has proven effective in multiview and multimodal tasks [46, 47]. In this work, we propose an adaptive contrastive learning auxiliary task to distill the shared information $\boldsymbol{p}_{c,i}\in\mathbb{R}^{d_{3}}$ from multiple views by maximizing the agreement between POI representations under different views and the fused representations. The resulting view-shared loss can be mathematically noted as:

where $I\left(\cdot,\cdot\right)$ represents the mutual information computed using InfoNCE [48]. Specifically, we define $(\boldsymbol{p}_{i}^{v},\boldsymbol{p}_{c,i})$ as positive samples, while all other POI embeddings within the same view $(\boldsymbol{p}_{i}^{v},\boldsymbol{p}_{j}^{v})$ and other fused multiview embeddings $(\boldsymbol{p}_{i}^{v},\boldsymbol{p}_{c,j})_{(j\neq i)}$ are regarded as negative samples:

where $\tau_{2}$ is the temperature parameter and $\theta(\cdot,\cdot)$ is the critic function implemented as a cosine similarity function.

Capturing the unique features held by each view is also crucial for a comprehensive understanding of the semantics of POIs. To this end, we extract view-specific representations to complement the view-shared representations. Specifically, the view-specific representations $\boldsymbol{p}_{s,i}^{v}\in\mathbb{R}^{d}_{3}$ of each view $v$ are obtained by subtracting the view-shared representations $\boldsymbol{p}_{c,i}$ from the view representation $\boldsymbol{p}_{i}^{v}$:

To ensure that view-specific representations do not encode shared information, we employ an orthogonality constraint:

Then, we integrate the view-shared and view-specific representations with an attention module. The importance of each representation for POI $l_{i}$ is formulated as:

where $\boldsymbol{a}_{2}\in\mathbb{R}^{d_{3}}$ is the learnable vector. Then, the final fused multiview representation of POI $l_{i}$ is formulated as:

To allow the recommender to perceive the collaborative signals among POIs in diverse feature views, we introduce fused representations obtained in Eq. 19 into the backbone by combining POIs’ original ID embeddings and fused representations. The details can be found in Appendix A.

We adopt the cross entropy (CE) loss to compute the ranking of ground-truth next POI, which encourages the prediction of ground truth next POI to be ranked more highly:

where $\hat{y}_{i}$ is the predicted probability of the ground-truth next POI for the $i$-th training sample, and $|D_{train}|$ is the total number of samples in training set.

The overall objective function can be formulated as:

where $\beta_{\text{HSL}},\beta_{\mathrm{SH}},\beta_{\mathrm{SP}}$ are hyper-parameters to control the hierarchical structure learning and contrastive multiview fusion.

Since hierarchical structure learning needs to be performed iteratively, the model is optimized with the EM algorithm. To help better understand the optimization process, we provide the detailed workflow for EM-based optimization in Algorithm 1.

Our design encompasses hierarchical structure learning based on the EM algorithm, pairwise structure learning based on metric learning, multi-relational GNN, and contrastive multiview fusion. For our proposed bi-level graph, we use $N$ and $K$ to represent the number of POIs and prototypes, respectively. $E_{1}$, $E_{2}$, and $E_{3}$ are used to denote the number of edges in the adjacency matrices $\mathbf{A}^{\mathrm{POI}}$, $\mathbf{A}^{\mathrm{Hier}}$, and $\mathbf{A}^{\mathrm{Proto}}$, respectively. We analyze the complexity of each component individually:

1. 1.

   Hierarchical Structure Learning: We employ the EM algorithm to learn the hierarchical structure within POI features. In the E-step, we execute K-Means to assign each POI to its corresponding group, and in the M-step, we update the structural representation of the POIs by optimizing $\mathcal{L}_{\text{HSL}}$. In both the E-step and M-step, we need to compute the pairwise distances between POIs and cluster centroids, resulting in a complexity of $O(KN+KN)=O(KN)$.

2. 2.

   Pairwise Structure Learning: We learn the POI-level pairwise structure by computing the pairwise similarity between POI nodes. The same operation is also performed on prototype nodes. Therefore, the complexity of this part is $O(N^{2}+K^{2})$.

3. 3.

   Multi-Relational GNN: We modify the vanilla GNN to accommodate our bi-level graph, which includes $N+K$ nodes and $E_{1}+E_{2}+E_{3}$ edges. Since the complexity of a vanilla GNN layer is $O(N+E)$, where $N$ and $E$ are the number of nodes and edges respectively, we can conclude that the complexity of our modified graph model is $O(N+E_{1}+E_{2}+E_{3})$. Since we only update the representations of POI nodes, the complexity is independent of $K$.

4. 4.

   Contrastive Multiview Fusion: To implement the representation decomposition and fusion we proposed, we need to calculate $\mathcal{L}_{\mathrm{SH}}$ and $\mathcal{L}_{\mathrm{SP}}$. The complexity of computing these two losses is $O(VN^{2})$ and $O(V^{2}N)$, respectively. Since the number of views $V$ is a very small constant, the complexity of this part is $O(VN^{2}+V^{2}N)=O(N^{2})$.

Based on the above analysis, we can conclude that the total complexity of our design is $O(KN+N^{2}+K^{2}+N+E_{1}+E_{2}+E_{3})$. In our model, the following inequalities hold:

• •

  $K\ll N$ (the number of prototypes is much less than the number of POIs)

• •

  $N<E_{1}$ (the degree of each POI node is greater than 1)

• •

  $E_{1}<N^{2}$ (POIs are not fully connected)

• •

  $E_{2}=N$ (each POI belongs to only one cluster)

• •

  $E_{3}<E_{1}$ (the number of prototype-prototype edges is less than the number of POI-POI edges)

Thus, the total complexity of our design can be simplified as $O(N^{2})$. The efficiency bottlenecks lie in the POI-level pairwise structure learning and the contrastive fusion, which involves the scalability issues of graph structure learning and contrastive learning. In fact, several methods have been proposed to enhance the efficiency of these two techniques [49, 50]. These methods provide valuable support for further enhancing efficiency.

We compare BiGSL with the baselines and the results are summarized in Table II. Under all the metrics, BiGSL can significantly outperform all the baselines on each of the datasets, which demonstrates its effectiveness in improving next POI recommendation.

Among baseline models, graph-based models, such as GETNext, Graph-Flashback, SNPM, and HMT-GRN, perform better than other models. It is not a surprise since graph-based models are better at capturing global POI-POI relationships and transition patterns across users.

GETNext, Graph-Flashback, SNPM, and HMT-GRM are the best-performing baseline models, they still have some deficiencies compared to our proposed BiGSL. HMT-GRN takes into account the hierarchical structure in spatial features by introducing objectives of auxiliary tasks at the regional levels. However, these objectives in multi-task learning paradigm are independent, therefore fall short in modeling the interaction between different levels. Additionally, it utilizes spatial and temporal graphs constructed according to pre-defined rules, resulting in performance affected by the noise in the graphs. The advantage of our method over GETNext lies in our consideration of graph-based encoding for multiple features, which is more capable of capturing the intricate relationships between POIs than the direct embedding layer used in GETNext. Graph-Flashback considers learning a latent POI graph with the knowledge graph containing spatio-temporal information, but it does not explicitly consider hierarchical structure when learning latent graphs. Although SNPM adopts the Eigenmap method to infer the latent graph structure, it remains constrained by pre-defined rules, which results in inferior performance compared to ours. Moreover, for fusing multiple features, they either simply perform a linear combination of multiple features or directly embed them into a unified latent graph, leading to suboptimal results and lacking interpretability. For modeling hierarchical structures, even though some baseline models employ stacked hierarchical encoders to extract subsequence-level information from sequences, they are limited to capturing hierarchical patterns in sequence features and are incapable of modeling more comprehensive topological structure between POIs. Due to these limitations in their modeling capabilities, the performance of these methods is not as effective as our proposed method.

Our BiGSL achieves the best performance, which unequivocally outperforms all baseline models and verifies the effectiveness of our proposed methods. Compared with existing graph-based models, the BiGSL model automatically learns hierarchical structures and pairwise structures embedded in the POI features, and fuses the information mined from them in a more effective manner.

To analyze the effectiveness of the different components, we conduct an ablation study. We denote the base model as BiGSL and drop different components to form variants. The main components in our model are listed as:

• •

  HSL: The hierarchical structure learning module, which is responsible for capturing clustering and hierarchical information in POI features and extracting prototypes. Removing this component will result in no more prototype neighbors in graph representation learning.

• •

  PSL: The pairwise structure learning module, which learns relative relationships between POIs or prototypes adaptively. Removing this module means that we use pre-defined rules for graph construction and the hierarchical structure learning based on the learned structure embedding will not be employed.

• •

  Shared (Shar): The view-shared loss $\mathcal{L}_{\mathrm{SH}}$ in the contrastive multiview fusion, which aims to extract information shared by representations in multiple views.

• •

  Specific (Spec): The view-specific loss $\mathcal{L}_{\mathrm{SP}}$ in the contrastive multiview fusion, which ensures the view-specific representations of different feature views do not encode view-shared information.

The results are summarized in Table III. We have the following observations from this table.

We observe that the hierarchical structure learning helps to improve the model performance, verifying the effectiveness of this component. Since this component mainly leverages the loss function $\mathcal{L}_{\mathrm{HSL}}$ to control the optimization process in the EM algorithm, to further understand the influence of this component, we visualize the effect of $\mathcal{L}_{\mathrm{HSL}}$ on graph structure learning in Fig. 4.

From Fig. 4, we can intuitively find that the structure embedding learned based on either spatial or temporal features has more obvious clustering under the guidance of $\mathcal{L}_{\mathrm{HSL}}$. This indicates that the introduction of $\mathcal{L}_{\mathrm{HSL}}$ can effectively capture the hierarchical properties in POI features and guide the learning of structure embedding. In addition, the spatial structure embedding has more pronounced clustering than temporal structure embedding, indicating that spatial features naturally exhibit more significant hierarchical structures. Consequently, in graphs constructed with these embeddings, connected POIs are more semantically similar. The prototypes extracted from clusters present more coarse-grained group features, thus constructing effective hierarchical structures.

The results in Table III also demonstrate the effectiveness of pairwise structure learning and contrastive multiview fusion. Note that view-specific information has a more significant impact on contrastive fusion than view-shared information, which indicates that the difference in semantics of different features is more pronounced than similarity, and it is meaningful to fully consider multiple features in POI recommendation.

We conduct sensitivity analysis with four hyper-parameters on the hierarchical structure learning and the contrastive multiview fusion, which are the most pivotal parts of BiGSL. The investigated hyper-parameters include the number of clusters $K$, the weights of loss function $\beta_{\text{HSL}}$, $\beta_{\text{SH}}$, $\beta_{\text{SP}}$, and the temperature coefficients $\tau_{1},\tau_{2}$. Fig. 5 and Fig. 6 shows the effect of varied hyper-parameter values, from which we have the following observations.

We adopt a clustering-based grouping method in Section 4.2 to construct hierarchical relationships. Regarding the feature grouping scheme, we compare our clustering-based grouping with the approach of not conducting feature grouping (i.e., not modeling the hierarchical structure). We also compare changing the grouping of spatial features from clustering-based to grid-based grouping, and the grouping of temporal features from clustering-based to date-based grouping. Experiments are conducted on Gowalla and Foursquare, with the results presented in Table IV.

From Table IV, we observe that compared to not conducting feature grouping, traditional grouping schemes do not always improve performance. An improvement is only noted on Gowalla when temporal features are grouped by date, but this still falls short of our clustering-based grouping method. This indicates that the hierarchical structure within POI features is complex and nonlinear, making it challenging to be directly modeled by heuristic rules. Conversely, our method is capable of adaptively modeling the complex hierarchical structure within POI features through the K-Means clustering and EM algorithm framework.

For the representation fusion scheme [55, 56], we compared our contrastive fusion with other strategies such as early, intermediate, and late fusion for integrating spatial and temporal representations. In early fusion, we perform a concatenation or a linear sum on the node representations obtained in each view. In the linear sum, the weights for spatial and temporal representations are $\lambda_{1}$ and $1-\lambda_{1}$, respectively. Similarly, in intermediate fusion, we perform a concatenation or a linear sum on the intermediate results after further encoding with the LSTM layer. In the linear sum, the weights for spatial and temporal representation are set as $\lambda_{2}$ and $1-\lambda_{2}$. In late fusion, we average the predicted logits from different views at the decision layer. Comparative experiments are conducted on Gowalla and Foursquare, with the results presented in Table V.

From Table V, we observe that among the compared fusion schemes, early fusion performs the best, while late fusion yields the worst results. This may be due to the high correlation between POI representations from different views, where early fusion facilitates better interaction between representations. Additionally, we notice that linear sum outperforms concatenation, possibly because concatenation increases the hidden layer dimension, leading to over-parameterization due to the introduction of more model parameters. Lastly, when evaluating the performance of linear sum, the optimal value of $\lambda_{1}$ or $\lambda_{2}$ varies across different datasets. This indicates that the optimal weights for linear sum relies on empirical manual selection, whereas our method could adaptively learn the optimal weights.

We compare the actual runtime of our method with the best baseline, HMT-GRN, by recording the total training time required for convergence. All experiments are conducted on a NVIDIA RTX 3090 GPU to ensure fairness in comparison. The runtime required to train HMT-GRN and our method is around 5.2 hours and 6.5 hours, respectively. We observe that due to the difference in the complexity of the training process, our method requires more time per batch compared to HMT-GRN. However, our design does not lead to a significant increase in actual runtime due to the efficient implementation and the PyTorch library’s automatic acceleration of matrix multiplication operations. Therefore, in terms of total training time, our method is comparable to existing methods.

In recommendation, balancing personalization and exploration is a critical challenge. Personalization focuses on learning preferences from POIs which users have already visited. In contrast, exploration evaluates the ability to accurately recommend POIs that users have not visited. Both abilities ensure accuracy and diversity in recommendation.

To evaluate the exploration performance of POI recommendation, we adopt the Next New ($N^{2}$) extension of metrics (i.e., $N^{2}$-Acc@K, $N^{2}$-MRR) proposed in HMT-GRN [4]. This set of metrics only considers Next New POIs that have never been visited by the user, and thus can be used to evaluate the exploratory ability of the recommenders.

The higher-density dataset may provide more global collaborative signals for exploration, so we conduct experiments on the BJ dataset. The results are shown in the Table VI. HMT-GRN is currently the most state-of-the-art model for next new POI recommendation, thanks to its selectivity layer designed to identify whether a POI has been visited by a user. Compared to HMT-GRN, our model significantly enhances the exploration ability without hurting the personalization performance. Note that we do not employ the selectivity layer proposed by HMT-GRN, but only rely on the graph structure learning and the multi-relational graph network to achieve it. The improvement of the $N^{2}$ metric score illustrates that our method can effectively establish connections for POIs with similar feature semantics and explore more potential POIs in recommendation.

In Fig. 7, we visualize an example of the spatial graphs obtained with pre-defined rules (e.g. grid mapping) and our structure learning method, respectively. The POIs with the same color in the figure are connected by edges. For brevity, we only show the colors of the POI nodes here instead of plotting the edges. Intuitively, the graph constructed by pre-defined rules is prone to noise (in the red circles) and incompleteness (in the black circle), i.e., geographically non-aggregated POIs may be connected by edges, while geographically aggregated POIs are grouped into different grids. In contrast, our method adaptively learns a better spatial graph with less uncertainty. The higher graph quality is helpful for the learning of POI representations and downstream POI recommendations.