# Heterogeneous Graph Structure Learning for Next Point-of-Interest Recommendation
## 4 Heterogeneous Graph Structure Learning Model
### Sequence Modeling
#### 4.4.2 Sequence Encoding  
After constructing the user's check-in sequence graph, this paper designs a graph encoder based on the attention mechanism to capture relations between POIs. Specifically, it extracts features of POIs from a graph perspective and aggregates them into a representation vector for the check-in sequence (see Figure 3 for the detailed architecture). In addition to the sequential order of visited POIs, the temporal and spatial information between two check-ins is equally critical. The impacts of time intervals and geographical distances vary: shorter time intervals reflect stronger correlations between POIs, and larger geographical distances may indicate shifts in user preferences. Thus, we integrate both temporal and spatial information into the sequence modeling process.  
Specifically, for a trajectory graph \(G_{s}\), the sequence representation is generated based on POI embedding \(E_{p}\), time interval \(\Delta t_{ij}\) and spatial distance \(\Delta d_{ij}\) between two consecutive check-ins \(i\) and \(j\), and the graph attention network (GAT). The attention coefficients are computed as follows:  
\[a_{ij}=W\Big{(}x_{i}^{s}\odot x_{j}^{s}+\Delta d_{ij}+\Delta t_{ij}\Big{)} \tag{15}\]  
where \(a_{ij}\) is the attention coefficient between nodes \(i\) and \(j\), \(x_{i}^{s}\) and \(x_{j}^{s}\) are POI representations from E\({}_{p}\), and \(\odot\) denotes element-wise multiplication. In addition, we argue the visited POI would not only be influenced by the previous visits, but also have a relation with the  
Figure 3: A schematic diagram of sequence modeling.  
future one. Therefore, in order to model the bidirectional relations, we compute attention coefficients in two directions to model both historical and future influences:  
\[\begin{array}{c}a_{ij}^{(in)}=W^{(in)}\Big{(}\mathrm{x}_{i}^{s}\odot\mathrm{x }_{j}^{s}+\Delta d_{ij}+\Delta t_{ij}\Big{)}\\ a_{ij}^{(out)}=W^{(out)}\Big{(}\mathrm{x}_{i}^{s}\odot\mathrm{x}_{j}^{s}+ \Delta d_{ij}+\Delta t_{ij}\Big{)}\\ a_{ij}=a_{ij}^{(in)}\parallel a_{ij}^{(out)}\\ \mathrm{x}_{i}^{s}=\sum\limits_{j\in N_{i}}a_{ij}\mathrm{x}_{j}^{s}\end{array} \tag{16}\]  
where \(\parallel\) denotes a concatenation operation, \(N_{i}\) is the set of neighboring nodes of \(i\), and \(x_{i}^{s}\) is the updated representation for POI \(i\) in the sequence. The final output can be represented as \(\mathrm{X}^{s}=\big{[}\mathrm{x}_{1}^{s},\mathrm{x}_{2}^{s},\dots,\mathrm{x}_ {n}^{s}\big{]}\). To further capture user preferences from multiple perspectives, we apply a self-attention mechanism to encode the node representation:  
\[\mathrm{X}_{seq}=\mathrm{FFN}\Big{(}\mathrm{Attention}(\mathrm{W}_{Q}^{s} \mathrm{X}^{s},\mathrm{W}_{K}^{s}\mathrm{X}^{s},\mathrm{W}_{V}^{s}\mathrm{X}^ {s})\Big{)} \tag{17}\]  
\[\mathrm{Attention}(Q,K,V)=\mathrm{Softmax}\Big{(}\frac{QK^{T}}{\sqrt{d}}\Big{)} V+V \tag{18}\]  
where \(\mathrm{W}_{Q}^{s}\), \(\mathrm{W}_{K}^{s}\), and \(\mathrm{W}_{V}^{s}\) are trainable parameters, and FFN is a feed-forward network. \(\mathrm{X}_{seq}\) includes all the node representations within a sequence. By averaging the node representations in the sequence, we can obtain the graph's representation \(\mathrm{e}_{s}\), which is also the user's sequence preference.