# GenTrajRec: A Graph-Enhanced Trajectory Recovery Model Based on Signaling Data
## 4 Methodology
### Transition Graph Embedding  
We utilize the coarse trajectory transition graph to model the transition patterns between base stations. There are multiple trajectory-transition patterns, which means the edges can be constructed in multiple ways. Most researchers constructed the global graph based on geographical distances. However, this concept of direct spatial proximity does not account for the actual adjacency between two locations. Taking vehicles as an example, the presence of one-way streets might require a detour to reach the destination, meaning the two locations cannot be considered practically adjacent. Additionally, in real-world scenarios, their proximity relationship varies with different modes of travel. For instance, a distance of 1 km could be considered adjacent for cars, but for pedestrians, these two base stations might not be considered adjacent. Because of the thoughts above, we use the transition patterns and the time interval between base stations to construct the transition graph. We consider that an edge can only be established between two base stations if the time for a mobile phone user to travel from one base station to another is less than a certain time threshold. If an edge already exists between two base stations, the weight of the edge increases. We define all the trajectory sequences as \(\mathbf{P}_{traj}=(\mathbf{P}_{sub}^{1},\mathbf{P}_{sub}^{2},\ldots,\mathbf{P}_{sub}^{n})\) where \(\mathbf{P}_{sub}^{i}=(s_{i,1},s_{i,2},\ldots,s_{i,k})\). Each \(s_{i,j}\) represents the location and time information presented in the preliminaries of the coarse trajectory sequence at step \(j\), which can be denoted as \(s_{i,j}=(l_{ij},t_{i,j})\). The graph construction algorithm is shown in Algorithm 1. We construct a directed graph \(G=(V,E)\). \(V\) is the nodes of the graph, which represents the coarse area index. The node contains the latitude and longitude and the ID of the base station. \(E\) is the edges of the graph. In our work, we construct the graph by transition time. For instance, for user \(u^{\prime}\)s trajectory sequence, suppose the time threshold is \(\alpha\), for \(p_{u,i}^{n}=(v_{u,i}^{n},x_{u,i}^{n},y_{u,i}^{n},t_{u,i}^{n}(in),t_{u,i}^{n}( out))\), if \(|t_{u,i+1}^{n}(in)-t_{u,i}^{n}(in)|<\alpha\), we reckon there is an edge between \(v_{u,i}^{n}\) and \(v_{u,i+1}^{n}\). We construct the graph using all the trajectory sequences and the number of the pairs are regarded as the weights of the edges. The graph is supposed to find hidden transition patterns. Thus, we use Node2 Vec [39] as the sampling method, to generate positive samples and randomly selected nodes as negative samples. To obtain the embedding of the whole trajectory, we set a single positive random walk trace ID sequence as \((v_{pos,0},v_{pos,1},\ldots,v_{pos_{k-1}})\), and the negative random walk trace ID sequence as \((v_{neg,0},v_{neg,1},..,v_{neg_{k-1}})\). Then, we set a sliding window with the size of \(w\) to obtain the sub-trace, and the formula for the trace embedding is  
\[\mathbf{r}_{pos,0},\mathbf{r}_{pos,1},\ldots,\mathbf{r}_{pos,k-w}=\text{unfold}(v_{pos,0},v_{pos,1},v_{pos,2},\ldots,v_{pos,k}), \tag{6}\]  
where \(\mathbf{r}_{pos,i}\) is a sub-trace with a size of w. For each trace, the formula for embedding the trace is as follows. \[\mathbf{w}_{pos,i}=\text{Embedding}(\mathbf{r}_{pos,i}), \tag{7}\]  
and the embedding for the whole single trace is  
\[\mathbf{x}_{pos}=\frac{1}{k-w-1}*\sum_{i=1}^{k-w-1}\mathbf{w}_{0}\cdot\mathbf{w}_{pos,i}, \tag{8}\]where \(\mathbf{w}_{pos,i}\) is the embedding of the node \(v_{pos,i}\in V\). Equation (8) is the embedding of the whole trace; since \(v_{pos,0}\) is the start of the trace, we want to obtain the whole representation of the sampling trace, and the procedure for the negative sample will be the same.