# Heterogeneous Graph Structure Learning for Next Point-of-Interest Recommendation
## 4 Heterogeneous Graph Structure Learning Model
### Graph Structure Learning  
Although subgraphs constructed based on meta-paths can capture the relations between nodes from various perspectives, the noise and missing key edges in the graph may affect the encoding results, which, in the end, may impact the final recommendation outcomes. Such manually defined graphs often contain redundant edges and miss some critical ones. Graph structure learning continuously optimizes the graph structure during training, thereby obtaining higher-quality representation vectors based on the continuously optimized graph.  
In this part, we use graph structure learning to continuously update the meta-path subgraph. This part use E\({}_{u0}\), E\({}_{u1}\), E\({}_{u2}\), E\({}_{p0}\), E\({}_{p1}\), and E\({}_{p2}\) as the input. When reconstructing a subgraph of a meta-path, the representations obtained from the subgraph and the corresponding node representation from the interaction graph are used. For example, when reconstructing \(G_{uu1}\), we use E\({}_{u1}\) obtained from \(G_{uu1}\) and the user representations from E\({}_{u0}\). The process can be expressed as follows:  
\[E_{i,j}^{uu1}\,=\,\sum_{g\in\{G_{uu1},G_{up}\}}\,\beta_{g}(cos(e_{i}^{g}e_{j}^ {g})) \tag{11}\]  
where \(E_{i,j}^{uu1}\) indicates the probability whether there is an edge between node \(i\) and \(j\), g represents the graph, which includes \(\left\{G_{uu1},G_{up}\right\}\), \(\beta_{g}\) is a hyper-parameter used to balance the importance of different graphs, \(cos\) is the cosine similarity calculation function, and e\({}_{i}^{g}\) and e\({}_{j}^{g}\) are the representations of node \(i\) and \(j\) in the graph g. Then, we remove \(m^{-}\) edges with the lowest probabilities and add the the most probable \(m^{+}\) edges. By doing so, we can obtain the optimized graph \(G_{u1}\). In a similar way, we can obtain \(G_{u2}\) using E\({}_{u2}\) and E\({}_{u0}\), \(G_{p1}\) using E\({}_{p1}\) and E\({}_{p0}\), and \(G_{p2}\) using E\({}_{p2}\) and E\({}_{p0}\). We use the heuristic method to reduce the memory overload by avoiding back-propagation through dynamic graph operations. Moreover, the heuristic method increases the interpretability when we add or remove edges. The cosine-similarity threshold provides explicit control over edge sparsity and semantic consistency, while, if we use differentiable graph learning, the learned edge weights lack the explainability.  
After obtaining the four optimized graphs, we can obtain the representation vectors of nodes by using different graph neural networks for encoding. The calculation method is as follows:  
\[\begin{split}\text{E}_{u}^{1}&=\text{GNN}\Big{(}A_{u1 },\text{E}_{u1}^{l}\Big{)},\ \ \text{E}_{u}^{2}=\text{GNN}\Big{(}A_{u2},\text{E}_{u2}^{l}\Big{)}\\ \text{E}_{p}^{1}&=\text{GNN}\Big{(}A_{p1},\text{E}_{ p2}^{l}\Big{)},\ \ \text{E}_{p}^{2}=\text{GNN}\Big{(}A_{p1},\text{E}_{p2}^{l}\Big{)}\end{split} \tag{12}\]  
where \(A_{u1}\), \(A_{u2}\), \(A_{p1}\), and \(A_{p2}\) are the adjacency matrices of \(G_{u1}\), \(G_{u2}\), \(G_{p1}\), and \(G_{p2}\), and \(\text{E}_{u}^{1}\), \(\text{E}_{u}^{2}\), \(\text{E}_{p}^{1}\), and \(\text{E}_{p}^{2}\) are the results of graph encoding. Then, the representation vectors of users and POIs are fused, respectively, to obtain the final representations:  
\[\text{E}_{u}=\text{E}_{u}^{1}\ \bigoplus\ \text{E}_{u}^{2},\ \ \text{E}_{p}= \text{E}_{p}^{1}\ \bigoplus\ \text{E}_{p}^{2} \tag{13}\]  
where \(\bigoplus\) denotes the average pooling, and \(\text{E}_{u}\) and \(\text{E}_{p}\) are the final representations of users and POIs, which will then be applied in the sequence modeling.