## 3 Hierarchical Graph Learning for Next POI Recommendation
### Hierarchical Graph Construction
#### 3.1.2 Region-Level Graph Construction  
For the region-level graph, each node represents a region, defined as a group of spatially proximate check-in locations that are frequently visited together. To maintain the sequential order of node visits and preserve temporal relationships, we employ a strict rule-based clustering approach. We adopt stay points as the representation of spatio-temporal clusters. Specifically, following the approach of extracting stay points [33], we have designed a procedure to extract spatio-temporal clusters based on a time threshold (\(t_{\text{thresh}}\)) and a distance threshold (\(d_{\text{thresh}}\)). For a trajectory containing \(n\) check-ins, a spatio-temporal cluster \(C\) is generated, starting from the first check-in. When subsequent check-ins do not exceed the distance and time thresholds compared to the previous one, they are merged into the current cluster; otherwise, a new cluster is generated. Here, \(p_{i}.T\) and \(p_{j}.T\) denote the timestamps of check-ins \(p_{i}\) and \(p_{j}\), respectively. The attributes \(s.\text{arv}T\) and \(s.\text{lev}T\) represent the arrival and departure times of a spatio-temporal cluster \(s\). The algorithm for spatio-temporal cluster extraction is shown as Algorithm 1 below.  
Figure 3: The structure of the hierarchical graph, which comprises three layers: the check-in layer (**bottom**), the region layer (**middle**), and the global layer (**top**). In the bottom-up phase, check-in embeddings are aggregated via multi-head attention into region-level cluster representations, which are further propagated into the global layer. The top two layers also incorporate intra-layer message exchange among structurally connected nodes. In the top-down phase, the global and regional embeddings are projected back to enrich check-in representations via a multi-layer perceptron (MLP). This cross-scale architecture enables the model to learn both fine-grained and coarse-grained user mobility patterns.  
The edges between spatio-temporal clusters can be established in two ways: by using user information and by analyzing the similarity of clusters.  
User Information: First, we discuss edge generation based on user information. According to previous research [34], users exhibit certain regularities in their travel patterns, particularly the tendency to repeatedly visit certain preferred locations. Based on this assumption, we hypothesize that there is a certain degree of similarity between the locations visited by the same user, and thus, there should be edges between these clusters in the hypergraph. For instance, if a user's trajectory on Monday is refined into spatio-temporal clusters \(C_{1}\) and \(C_{2}\) and the same user's trajectory on Tuesday is refined into \(C_{3}\), we infer that there is some similarity between \(C_{3}\) and \(C_{1},C_{2}\) due to the user's daily routine. Therefore, edges that facilitate information aggregation between them are warranted. This method aims to enable clusters belonging to the same user to share check-in information, thereby accurately capturing the user's fine-grained preferences.  
Similarity of Clusters: However, relying solely on the same user's data to fuse information neglects the integral trends of user movement, especially in regions with high popularity. To address this, we also define edges between similar spatio-temporal clusters. For example, if a user's weekend trajectory is refined into clusters \(C_{1}\) and \(C_{2}\), and another user's weekend trajectory into \(C_{3}\), and if \(C_{2}\) and \(C_{3}\) are similar in context, we consider there to be an edge that can facilitate information integration between these clusters, thereby reflecting the overall trend of location popularity. Specifically, we utilize the Jaccard similarity, a commonly used measure in computing sequence similarity. Through these edges, the hypergraph model can more effectively capture the complex relationships between clusters and different users, thereby improving the accuracy of the next POI recommendations.