{'fraction_non_alphanumeric': 0.038647892819979185, 'fraction_numerical': 0.009918054110301769, 'mean_word_length': 4.541989547666246, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RNTrajRec: Road Network Enhanced Trajectory Recovery with Spatial-Temporal Transformer

GPS trajectories are the essential foundations for many trajectory-based applications, such as travel time estimation, traffic prediction and trajectory similarity measurement. Most applications require a large amount of high sample rate trajectories to achieve a good performance. However, many real-life trajectories are collected with low sample rate due to energy concern or other constraints.We study the task of trajectory recovery in this paper as a means for increasing the sample rate of low sample trajectories. Currently, most existing works on trajectory recovery follow a sequence-to-sequence diagram, with an encoder to encode a trajectory and a decoder to recover real GPS points in the trajectory. However, these works ignore the topology of road network and only use grid information or raw GPS points as input. Therefore, the encoder model is not able to capture rich spatial information of the GPS points along the trajectory, making the prediction less accurate and lack spatial consistency. In this paper, we propose a road network enhanced transformer-based framework, namely RNTrajRec, for trajectory recovery. RNTrajRec first uses a graph model, namely GridGNN, to learn the embedding features of each road segment. It next develops a spatial-temporal transformer model, namely GPSFormer, to learn rich spatial and temporal features along with a Sub-Graph Generation module to capture the spatial features for each GPS point in the trajectory. It finally forwards the outputs of encoder model into a multi-task decoder model to recover the missing GPS points. Extensive experiments based on three large-scale real-life trajectory datasets confirm the effectiveness of our approach.


I. INTRODUCTION
GPS trajectories are the essential foundations of many applications such as travel time estimation [1], [2], traffic prediction [3]- [5], trajectory similarity measurement [6]- [10] and etc. In order to achieve good performances, most of these applications require a large number of high sample rate trajectories [11], as trajectories of low sample rate lose detailed driving information and increase uncertainty. However, as pointed out in previous works [11], [12], a large number of trajectories generated in real-life have low sample rate, e.g., taxis usually report their GPS locations every 2 ∼ 6 minutes to reduce energy consumption [13]. Consequently, it is hard for most existing models developed for the applications mentioned above to utilize these trajectories effectively. In addition, GPS trajectories have to be first mapped to the road network via map matching before being used by many applications. Most existing map matching algorithms are based on Hidden Markov Model (HMM) [14] and its variants, and they can achieve a high accuracy only when the trajectories are sampled in a relatively high rate [15]. Although some existing works aim to increase the accuracy of map matching, including HMM-based methods [16], [17] and learning based methods [12], [15], we have not yet found a good solution to address the issues caused by low-sample trajectories.
Trajectory recovery, that aims to increase the sample rate via recovering the missing points of a given trajectory, enriches low-sample trajectories from a different perspective. We can assume that vehicles are moving with the uniform speeds and insert new points (generated by linear interpolation) between every two consecutive GPS points in the input trajectory [18]. Though easy for implementation, it suffers from poor accuracy. Recently, two learning-based methods have been developed for trajectory recovery, including DHTR [19] and MTrajRec [11]. Both methods follow sequence-to-sequence [20] diagram, with an encoder model to generate the representation of a given trajectory and a decoder model to recover the trajectory point by point. Nevertheless, all existing works still suffer from following two major limitations.
• Most of these existing works ignore the road network structure, making the prediction lack spatial consistency to a certain degree. • Most of these existing works use a simple encoder model to represent trajectories and hence are unable to fully utilize the rich contextual information of GPS trajectories. For example, MTrajRec only employs a simple gated recurrent unit (GRU) [21] for trajectory representation.
To facilitate the understanding of the above two limitations, we plot an example in Fig. 1(a). The three orange-colored points labelled as p i (i ∈ [1,3]) form an input trajectory of low sample rate. As observed, the distance between each two consecutive points is relatively long (as there are many missing GPS points between them). The task of trajectory recovery is to recover the missing points and map all the GPS points (including the input points and recovered points) to the road network to generate a high-sample trajectory, e.g., the 13 bluecolored points labelled as q j (j ∈ [1,13]) together with the underlying road segments (represented by black color lines) shown in Fig. 1(a) form an output trajectory. This task is not trivial. Both the road network structure and context information of the input trajectory are essential to guarantee the high accuracy of the recovered trajectories. Their significance lies in four aspects. i) When two newly generated consecutive points are located at two different road segments, we have to rely on the road network to recover the trajectory. As illustrated in Fig. 1(b), new points q 4 and q 5 are near a major intersection I 1 that has complex topology. It's impossible to recover the underlying road segments if the road network structure is not considered. Note in Fig. 1(b) and (c), circles represent intersections and lines with arrows stand for directional road segments from one intersection to another. ii) Raw GPS points by nature have errors (e.g., most GPS-enabled smartphones are accurate to within a 4.9 m radius under open sky). As shown in Fig. 1(a), raw GPS points p 1 , p 2 and p 3 are not located at any road segments. Consequently, underlying road network provides an effective means to correct the errors as vehicles must move along the road network. iii) Raw points in the input trajectory might be far away from each other, and underlying road network reveals how vehicles can move from a point to another, e.g., we cannot simply use a straight line to connect p 1 to p 2 in Fig. 1(a). iv) Two consecutive GPS points in the input trajectory may be located at two different road segments while there are multiple candidate routes available to connect them. For example, we plot three candidate routes from p 1 to p 2 in Fig. 1(c), where triangles of the same color form one candidate route. The contextual information of the trajectory provides useful clues when filtering out impossible candidate route(s). For example, the position of p 3 suggests that the candidate route T 3 is unlikely to be the one as it requires detour to travel from p 2 to p 3 . Those familiar with map matching might notice that some aspects discussed above are applicable to map matching too. Map matching could be considered as a sub-step of trajectory recovery, while trajectory recovery is more challenging as it not only maps GPS points to road segments but also recovers missing GPS points that truly capture a vehicle's movement.
To address the limitations of existing trajectory recovery methods and meanwhile take advantage of end-to-end framework, we propose a novel transformer-based model, namely RNTrajRec, a Road Network enhanced Trajectory Recovery framework with spatial-temporal transformer. To capture the road network structure, RNTrajRec first develops a grid-partitioned road network representation module, namely GridGNN, to learn the hidden-state embedding for each road segment. To capture both the spatial-temporal features and the contextual information of trajectory, RNTrajRec then develops a novel transformer-based model, namely GPSFormer, which first represents each GPS point in a trajectory as a sub-graph road network that surrounds the GPS point through a Sub-Graph Generation module, and then introduces a novel spatialtemporal transformer model to learn rich spatial and temporal patterns of a GPS trajectory. It finally adopts a well-designed decoder proposed in [11] on top of the encoder model to recover the missing GPS points in the trajectory. Overall, our major contributions are summarized below.
• We propose a novel framework, namely RNTrajRec.
To the best of our knowledge, RNTrajRec is the first attempt to combine road network representation with GPS trajectory representation for the task of trajectory recovery. • To consider the road network structure around each GPS point in a given trajectory, we propose a novel spatial-temporal transformer network, namely GPS-Former, which consists of a transformer encoder layer for temporal modeling and a graph transformer model, namely graph refinement layer, for spatial modeling. Meanwhile, a Sub-Graph Generation module is developed to capture the spatial features for each GPS point. • We propose a novel model for road network representation, namely GridGNN, which seamlessly combines gridlevel representation with road network representation. • We conduct extensive experiments on three real-life datasets to compare RNTrajRec with existing methods 1 . Experimental results demonstrate that RNTrajRec significantly outperforms state-of-the-art solutions.

II. RELATED WORK
Spatial-Temporal Transformer. Transformers have achieved great success in many artificial intelligence fields, such as natural language processing [22]- [24] and computer vision [25]- [27]. Therefore, it has naturally attracted a lot of interest from academia and industry with many variants [28]- [30] being proposed. As a result, there is a growing interest in applying transformer architecture for graph representation [31]- [33]. However, most of these works solve graph modeling on fixed graph structure, which is not suitable for modeling dynamic graphs with temporal dependency.
Recently, several works have been proposed for dynamic graph modeling with transformer framework to solve pedestrian trajectory prediction [34], dynamic scene graph generation [35], 3D human pose estimation [36], activity recognition [37], [38] and etc. Specifically, Yu et al [34] propose a novel spatio-temporal transformer framework with intra-graph crowd interaction for trajectory prediction. However, the number of pedestrians (i.e. the number of nodes at each timestamp) is quite small and fixed. Cong et al [35] use the same transformer structure for both spatial and temporal modeling with a masked multi-head self-attention layer for temporal modeling. However, the time cost for each layer is O l 2 · v 2 , with l the length of the sequence and v the averaged number of nodes in each graph structure. Zheng et al [36] use a patch embedding for spatial position embedding and propose a spatial attention network. However, the input and the output have different structures and hence the model is not stackable. Li et al [37] propose a spatial-temporal transformer framework tailored for group activity recognition. Zhang et al [38] propose a spatialtemporal transformer with a directional temporal transformer block to capture the movement patterns of human posture.
In this work, we regard a GPS point as a weighted sub-graph of the road network surrounding the GPS point. Therefore, the graph structures of points along a trajectory could be different from each other. We propose a spatial-temporal transformer network that has the following three advantages. i) Our model is more flexible as it has zero restriction on the number of nodes or edges for each graph. ii) The time cost for each layer is O l 2 + l · v , which is more efficient and scalable. Note that due to the sparseness of road network, a sub-graph of a road network with v road segments only has O (v) edges connecting these road segments. iii) The input and the output share the same structure, therefore, our model is stackable. Road Network Representation Learning. Most of the existing works regard road network as a directed graph. Node2vec [39] and DeepWalk [40] are two novel models to model road segments as shallow embeddings. With the rapid development of graph neural network (GNN), many graph convolutional networks (e.g., GCN [41], GraphSage [42], GAT [43] and GIN [44]) are suitable for road network representation. Recently, several works have been proposed specifically for road network representation learning [45]- [47]. Among them, STDGNN [45] regards road network as a dual graph structure with a node-wise GCN modeling the features of intersections and an edge-wise GCN modeling the features of road segments, HRNR [46] constructs a three-level neural architecture to learn rich hierarchical features of road network, and Toast [47] proposes a traffic context aware skipgram module for road network representation and a trajectoryenhanced transformer module for route representation.
In this work, we regard each road segment as a sequence of grids that the road segment passes through and use recurrent neural network to model grid sequence dependency and graph neural network to model graph structure. With this design, our road network representation can capture both nearby neighborhood features and graph topology features.
GPS Trajectory Representation Learning. Learning-based methods for representing GPS trajectory have been studied wildly these years. Among them, T2vec [6], NeuTraj [7], T3S [8], and Traj2SimVec [9] are representative models. T2vec proposes the first deep learning model for trajectory similarity learning with BiLSTM [48] modeling temporal dependency. NeuTraj integrates a spatial-memory network for trajectory encoding and uses distance-weighted rank loss for accurate and effective trajectory representation learning. T3S uses a self-attention based network for structural information representation and a LSTM [48] module for spatial information representation. Traj2SimVec proposes a novel sub-trajectory distance loss and a trajectory point matching loss for robust trajectory similarity computation. However, these works only consider GPS trajectory in Euclidean space but ignore the important road network topology. Recently, Han et al [10] propose a graph-based method along with a novel spatial network based metric similarity computation. However, it mainly focuses on representing point-of-interests (POIs) in road networks. Since POIs are discrete GPS points on road network and GPS points in a trajectory are continuous, it cannot be directly used for GPS trajectory representation learning. To the best of our knowledge, our work is the first attempt to solve GPS trajectory representation learning in spatial networks. Trajectory Recovery. Recovering low sample trajectory is important for reducing uncertainty [11], [19], [49], [50]. Specifically, DHTR [19] proposes a two-stage solution that first recovers high-sample trajectory followed by a map matching algorithm (i.e. HMM [14]) to recover the real GPS locations. AttnMove [49] designs multiple intra-and inter-trajectory attention mechanisms to capture user-specific long-term and short-term patterns. Bi-STDDP [50] integrates bi-directional spatio-temporal dependence and users' dynamic preferences to capture complex user-specific patterns. However, both Attn-Move and Bi-STDDP use user-specific history trajectories and are designed for recovering missing POI check-in data, which is very different from our setting. MTrajRec [11] proposes an end-to-end solution with a map-constraint decoder model, which significantly outperforms two-stage methods. However, it ignores the important road network structure, leaving rooms for further improving the accuracy. In this paper, we propose a novel GPSFormer module to learn rich spatial and temporal features of trajectories from the road network.

III. PRELIMINARY
In this section, we formally introduce the key concepts related to this work and define the task of trajectory recovery. The notations used in this paper are briefly summarized in Table I and fully explained throughout the paper.
Definition 1: (Road Network.) A Road Network is modeled as a directed graph G = (V, E), where V represents the set of road segments and E ⊆ V × V captures the connectivity of these road segments, i.e., an edge e i , e j ∈ E if and only if there exists a direct connection from road segment e i to road segment e j .

Notation
Definition G The topology structure of the road network. G τ The subgraphs structure for the given trajectory τ .
The subgraph structure of the i th sample point in the given trajectory τ .

Σ grid
The grid embedding table.

Σ road
The road segment embedding table. e i ,ē,ẽ,ê A certain road segment in the road network.

X road
The representation of the road network.
The representation for the subgraphs of the given trajectory τ after l layers of GPSFormer.
The representation for the subgraph of the i th sample in the given trajectory τ after l layers of GPSFormer.
The input features for the given trajectory τ to the transformer encoder layer at the l th layer of GPSFormer. The final trajectory-level representation for the given trajectory τ . c The constraint mask vector defined in the decoder model. L id , L rate , L enc The loss functions employed in RNTrajRec.
Definition 2: (Trajectory.) A Trajectory τ /ρ is defined as a sequence of l tuples, i.e. τ /ρ = (p 1 , t 1 ), (p 2 , t 2 ), · · · , (p l , t l ) , where l refers to the length of the trajectory, p i refers to the i th sample point in τ /ρ, and t i is the sample time of p i in τ /ρ. Note, the time interval between two adjacent sample points in a trajectory (i.e., t i+1 − t i ) defines the sample interval of this trajectory.
GPS devices have measurement errors. Throughout the paper, we use terms Raw GPS Trajectory and Map-matched GPS Trajectory to refer to a GPS trajectory (denoted as τ ) directly obtained from certain GPS device and that (denoted as ρ) after running a map matching algorithm (e.g. HMM [14]) respectively. Note, p i in a raw GPS trajectory τ records its exact location using latitude and longitude, while p j in a map-matched GPS trajectory ρ captures its location based on the road segment e j that p j is located at and moving ratio r j ∈ [0, 1) that captures the moving distance of p j over the total length of e j (e.g., if r j = 0.5, the point p j is located at the middle point of road segment e j ). In addition, a raw GPS trajectory τ typically does not have a fixed sample interval, and we use the average time interval τ instead. A low-sample trajectory has a long sample interval.
Definition 4: (Trajectory Recovery.) Given a low-sample Raw GPS Trajectory τ with measurement errors (e.g., orange GPS points in Fig. 1(a)), the task of Trajectory Recovery aims to recover the real Map-matched ρ -Sample Interval Trajectory ρ (e.g., blue GPS points in Fig. 1(a)). Specifically, for each low-sample trajectory, it infers the missing GPS points and maps each GPS point (including the GPS points in the input trajectory τ ) onto the road network to obtain the real GPS locations of the moving trajectory. Note that the sample interval ρ of the recovered trajectory ρ must be much smaller than that of the given Raw GPS Trajectory τ .

IV. METHODOLOGY
This section introduces our proposed RNTrajRec, with the overall framework presented in Fig. 2.

A. Model Overview
The first component of RNTrajRec is GridGNN, a gridpartitioned road network representation module that learns spatial features for each road segment, as shown in Fig. 2(a). Given a road network G = (V, E), GridGNN learns rich road network features X road ∈ R |V |×d , where d is the hidden size of the model.
The second component of RNTrajRec is GPSFormer, a spatial-temporal transformer based GPS trajectory encoder that encodes raw GPS points p 1 , p 2 , · · · , p lτ in a trajectory τ into hidden vectors, as shown in Fig. 2(b). To obtain the input of GPSFormer, we first extract the road network features around each GPS point p i through the Sub-Graph Generation module. After the generation process, each GPS point p i ∈ τ is represented as a weighted directed sub- where V τ,i captures the road segments selected by the module that surround the GPS point p i ∈ τ , E τ,i is the set of edges in the selected sub-graph of the road network, and W τ,i refers to the set of weights between p i and each selected road segment in the sub-graph. Note that we useĜ instead of G to represent a sub-graph. Each generated sub-graph gathers road network features from X road to form its initial representation, i.e. Z (0) τ,i ∈ R |Vτ,i|×d . We further perform weighted mean pooling on graph to get the input representation of the trajectory τ , i.e.Ĥ (0) τ ∈ R lτ ×d . We then forward a mini-batch of b trajectory features along with the sub-graph structure into N stacked GPSFormerBlock layers, which is a combination of transformer encoder layer for For each road segment, a grid GRU cell is used to aggregate the grid sequence followed by a stack of M GAT modules to capture the spatial information. (b) The architecture of GPSFormer. Given a GPS trajectory, GPSFormer first extracts the road network features around each GPS point through the Sub-Graph Generation module. The features along with the sub-graphs are passed through several spatial-temporal transformer layers to learn the spatial and temporal features. (c) The architecture of decoder model. Given the output from the encoder model, an attention module is adopted to compute the similarity between the hidden-state vector of GRU cell and the outputs of encoder model and generate the input hidden-state vectors a (j) for timestamp j. A multi-task learning module is proposed that first predicts the target road segment e j , followed by a regression task for predicting moving ratio on the predicted road segment, i.e. r j . The entire model is trained end-to-end with Adam optimizer. temporal modeling and graph refinement layer, namely GRL, for spatial modeling.
The last component of RNTrajRec is a decoder model, proposed in [11] specifically designed for trajectory recovery task. Given the outputs of a mini-batch of b trajectories from the encoder model, i.e. H (N ) ∈ R b×lτ ×d , the decoder model first uses an attention module to calculate the similarity between the hidden-state vectors of the Gated Recurrent Unit (GRU) [21] cell (i.e., the query vectors) and the outputs from the encoder model (i.e., the key vectors) to obtain the input hidden vector a (j) at the j th timestamp. Furthermore, a multitask learning module is proposed specifically for trajectory recovery task that first predicts the target road segment e j and then predicts the corresponding moving ratio r j via a regression task, which will be detailed in Section V.

B. Road Network Representation: GridGNN
As stated in Section I, the road network structure is essential for the task of trajectory recovery. GridGNN is proposed to well capture the spatial features of road network. It partitions the road network into m × n equal-sized grid cells. Accordingly, each road segment can be represented as a sequence of grids that the road segment passes through. Formally speaking, we build a grid embedding table Σ grid ∈ R m×n×d for each grid cell. Similarly, given the road network G = (V, E), we create a road segment embedding table Σ road ∈ R |V |×d , where |V | is the total number of road segments in the road network.
For each road segment e i ∈ V , let S i = g 1 i ,g 2 i , ...,g φi i be a sequence of φ i grids passed through by e i . Since the grid sequence of each road segment has sequential dependencies, we use GRU cell to model the grid-level representation. That is, for each road segment e i and its corresponding grid sequence S i , the grid-level hidden-state vector is given by: Here, j ∈ {1, 2, · · · , φ i }, lookup (i, j) retrieves the grid embedding of position (i, j) from the grid embedding table Σ grid , W x represents the weight for the gate(x) neurons, b x represents the bias for gate(x), and σ (·) represents the gated function, which is implemented as sigmoid function. The initial embedding for each road segment r (0) i is: Here, σ road i ∈ R d is the road segment embedding of the i th road segment from Σ road .
The obtained hidden-state vector r (0) i considers each road segment independently, which does not capture the topology of the road network structure. In order to enhance the representation of road network, we integrate GNN. Specifically, we stack M layers of Graph Attention Network (GAT) module, which uses multi-head attention to efficiently learn the complex graph structure, to obtain final hidden-state vectorsX road ∈ R |V |×d : Here, l ∈ {1, 2, · · · , M }. For the k th attention head, a (l) ij,k represents the attention score between road segments e i and e j at the l th layer, − → a k are learnable weights to obtain attention scores, W k and W k is a learnable weight for feature transformation. [· ·] represents the concatenation operation, and N i represents the neighborhood of road segment e i in the road network.
The final road network representation is given by the concatenation ofX road = {r (M ) i } for each e i ∈ V and the static features f road s ∈ R |V |×fr (i.e. length of the road segment, number of in/out-going edges, etc), followed by linear transformation to obtain d dimension vectors X road .

C. Sub-Graph Generation
Given the representation X road ∈ R |V |×d of the road network, a straight-forward way to obtain the representation of a GPS point is to average over the embeddings of the road segments around the GPS point. However, this approach suffers from the following two problems. a) The influence of the nearby road segments on the given GPS point varies significantly. b) For each GPS point in a trajectory, its surrounding sub-graph structure is important for understanding the movement of the trajectory. Therefore, it is necessary to take the graph structure into consideration.
For a given GPS point p, we first locate the road segments within at most δ meters away from p, via R-tree [51] or any other spatial data structure. Note, δ is a hyper-parameter to control the receptive field of the GPS point. Assume in total ω p road segments are returned, denoted as {e 1 p , e 2 p , · · · , e ωp p }. We further follow the road network G = (V, E) to connect these ω p road segments into a sub- [11], we use the exponential function to model the influence of road segment e on the given GPS point p, as defined in Eq. (5). Here, dist(e, p) represents the distance between the GPS point p and the road segment e, i.e. spherical distance between the GPS point p and its projection to the road segment e, and γ is a hyper-parameter with respect to the road network. To this end, we obtain the weighted sub-graph of a given GPS point, i.e.G p = (V p , E p , W p ), where W p can be derived by Eq. (5).

D. Graph Refinement Layer (GRL)
As mentioned in Section IV-C, graph structure is significant for representing GPS points in spatial network. To this end, we propose a graph refinement layer (GRL) that is capable of capturing rich spatial features.   3 shows the architecture of the proposed graph refinement layer. Though it is inspired by the encoder of transformer model, there are five major differences between transformer encoder and the newly proposed GRL. a) Transformer encoder captures the temporal features across the sequence, while GRL captures the spatial features and uses the output of transformer encoder to update the local features. b) Transformer encoder only takes hidden vectors as input, while GRL takes both the hidden vectors and graph structures as input. c) Motivated by [33] which demonstrates that batch normalization [52] is more suitable for graph transformer, GRL replaces layer normalization [22] with a newly proposed graph normalization, which can be viewed as an extension of batch normalization for graph representation with temporal dependency, to normalize the hidden vectors. d) GRL replaces multi-head attention in transformer encoder with gated fusion [4] to adaptively fuse the input hidden vectors and the node features in the graph structure. e) GRL further replaces the feed forward in transformer encoder with graph forward to capture the rich spatial features around GPS points.
Assume the output hidden vectors at layer l are H (l) τ ∈ R lτ ×d , and the corresponding output graph hidden vectors are Z (l) τ , where each sub-graph features Z (l) τ,i ∈ R |Vτ,i|×d . Following [22], we employ a residual connection for both gated fusion sub-layer and graph forward sub-layer, followed by graph normalization. That is, the output of each sub-layer is given by GraphNorm (x + SubLayer (x)), where SubLayer represents a function that can be either GatedFusion or GraphForward. GraphForward is implemented as a stack of P standard GAT modules defined in Eq. (3) and Eq. (4), while GatedFusion and GraphNorm are detailed below.
1) Gated Fusion: The hidden-state vectors from the output of transformer encoder layer, i.e. T r (l) τ , capture rich temporal features of the given trajectory, while the graph structure, i.e. G τ , captures rich spatial information of each GPS point in the trajectory. Therefore, it is necessary to design a fusion mechanism to adaptively fuse the spatial and temporal features. Inspired by [4], we propose to use gated fusion to combine the hidden vectors at the i th timestamp, i.e. tr (l) Here,tr share the same size, W z,1 , W z,2 and b z represent the learnable weights in the module and σ (·) is the gated activation function, which is implemented as a sigmoid activation function.
We then perform batch normalization on M (l) ∈ R b×lτ ×d with the features {Z Here, γ B and β B are learnable parameters for scalar transformation and shift transformation in batch normalization respectively, and Z (l) τ is the output of graph normalization.

E. Transformer Encoder Layer
Transformer encoder layer contains a multi-head attention sub-layer and a feed forward sub-layer with a residual connection for each of the two sub-layers, followed by layer normalization. That is, the output of each sub-layer is given by LayerNorm (x + SubLayer (x)), where SubLayer represents a function that can be either MultiHead or FFN.
1) Multi-Head Attention: Given a sequence input X ∈ R L×d with L the length of the sequence, multi-head attention is given by: Here, Q, K and V refer to the query, the keys and the values for the input X respectively, W Q i , W K i and W V i are the learnable parameters of the i th attention head for the query, the keys and the values respectively, W O is a learnable parameter for the output, and h captures the number of attention heads.
2) Feed Forward: Feed-forward network contains a fully connected network with ReLU activation function: Here, W 1 and W 2 are two learnable weights, and b 1 and b 2 are the bias for the layer.

F. GPSFormer
GPSFormer first extracts spatial features for each GPS point in the trajectory through the Sub-Graph Generation module introduced in Session IV-C, and then applies N layers of GPSFormerBlock to capture rich trajectory patterns.
Given a mini-batch of b trajectories {τ 1 , τ 2 , · · · , τ b }. We first obtain the initial hidden-state vectors are H After that, we first add position embedding [22] to H (0) τ and obtain the input to the transformer encoder: Next, we input the hidden-state vectors and graph structures to a stacked of N GPSFormer cells: Here, TransformerEncoder and GraphRefinement stand for the transformer encoder layer and the graph refinement layer introduced in Section IV-E and Section IV-D respectively, and GraphReadout represents graph mean pooling operation similar to Eq. (8)

G. Decoder Model
Let H traj τ be the outputs of the encoder model. For simplicity, we denote the representation of a single trajectory as h traj = {h 1 , h 2 , · · · , h lτ }. The decoder model uses a GRU model to predict the road segment and moving ratio for each timestamp in the target trajectory. Assume the hidden-state vector in the GRU model at timestamp t is given by h An attention mechanism is adopted to obtain the input of GRU cell, i.e. a (t) : Here, v ∈ R d×1 represents the transformation weight, and W g and W h are learnable weights in the attention module.
To this end, the hidden-state vectors of the GRU cell are updated by: Here, j ∈ [1, 2, · · · , l ρ ], x (j−1) and r (j−1) represent the road segment embedding of the predicted road segment and its corresponding moving ratio at the (j − 1) th timestamp, and GRU represents the GRU cell defined in Eq. (1). Finally, h gru is forwarded to a multi-task block to recover the missing trajectory.

V. MULTI-TASK LEARNING FOR TRAJECTORY RECOVERY
Given a mini-batch of b trajectories, we first use the GPSFormer to obtain the trajectory representation for each sample, i.e., H traj τ ∈ R b×lτ ×d , and then forward the hiddenstate vectors to the decoder model to obtain the hidden-state vectors of the GRU cell, i.e., h (j) gru . For the task of predicting road segment ID, following [11], we adopt the cross entropy as the loss function: Here, w id ∈ R d×|V | represents a learnable weight and P θenc,θ dec ẽ gru and the constraint mask c j as defined in the paragraph below, e (j) i represents the ground truth road segment ID at the j th timestamp for the i th trajectory in the mini-batch, and θ enc and θ dec are the learnable parameters in the encoder and decoder model respectively. a) Constraint Mask Layer: The goal of the constraint mask layer is to accelerate the convergence of the decoder model and to tackle the difficulties of finegrained trajectory recovery. Given a raw GPS trajectory τ = (p 1 , t 1 ) , (p 2 , t 2 ) , · · · , (p lτ , t lτ ) and the target mapmatched ρ -sample interval trajectory ρ = q 1 ,t 1 , q 2 ,t 2 , · · · , q lρ ,t lρ , the constraint mask c j ∈ R lρ×|V | is calculated for each timestampt j in the target trajectory. For t j ∈ {t 1 , t 2 , · · · , t lτ }, the GPS point at timestampt j is given in the input trajectory, i.e. t k =t j and q j = p k . Accordingly, we set c j,i = ω (e i , p k ) for each road segment e i having its distance to p k within the maximum error of the GPS device (e.g. 100 meters) and set c j,i = 0 for other road segments. The function ω is defined in Eq. (5), except that we use another hyper-parameter β to replace γ. For timestampt j that does not appear in the input trajectory, we set c j,i = 1 for all road segments e i ∈ V .
Similarly, we adopt the mean square loss for moving ratio prediction task: Here, function f (x, y) = σ x T · y , w rate ∈ R 2 * d×1 represents a learnable weight and x (j) i represents the road segment embedding for the predicted road segment at the j th timestamp of the i th trajectory in the mini-batch, r (j) i represents the ground truth moving ratio for the i th trajectory in the minibatch at the j th timestamp, and σ refers to the sigmoid function.
To further improve the accuracy of RNTrajRec, we propose a graph classification loss with constraint masks. Given the output graph structure from the last graph refinement layer, i.e. Z (N ) τ , we calculate the graph classification loss as: τi,j,ē (W τi,j,ē ) represents the hidden-state vector (constraint weight) for road segmentē in the sub-graph Z (N ) τi,j (Ĝ τi,j ), andē (j) i represents the ground truth road segment ID at the j th timestamp for the i th input raw GPS trajectory in the mini-batch.
Eq. (19) defines the total training loss, where λ 1 and λ 2 are hyper-parameters to linearly balance the three loss functions.  Table II. Since trajectory pattern analysis in urban areas is typically more significant, we keep the central urban area in Chengdu and Porto as the training data, with the size of the selected urban area and the number of road segments covered listed in Table II. To demonstrate the scalability of our model, we select a region in Shanghai that includes most suburban areas in addition to the central urban area and hence is much larger than the central urban area, and name this as Shanghai-L dataset. Its size of the selected area and the number of road segments covered are also listed in Table II. Accordingly, we only consider trajectories passing through those selected areas. We want to highlight that considering a central urban area is a common approach used by many existing works [11], [53]. The selected areas, though much smaller than the entire road network, cover most heavy traffics. We use around 150, 000 trajectories in each dataset for training, and split each dataset into training set, validation set and testing set with a splitting ratio of 7 : 2 : 1.
To obtain high-sample map-matched trajectories, we use HMM [14] algorithm on original raw GPS trajectories followed by linear interpolation [18] to obtain map-matched ρsample interval trajectory and use the high-sample trajectories with sample interval in the range of 10 ∼ 15 seconds as the ground truth. To obtain low-sample trajectories, we randomly sample trajectory points from high-sample trajectories based on sample interval in the range of 80 ∼ 192 seconds. Specifically, for each dataset, we design a trajectory recovery task which uses only 12.5% or 6.25% points of the given trajectory to recover the remaining 87.5% or 93.75% missing points. Therefore, the average sample interval τ of the lowsample input trajectories is 8 or 16 times higher than that of the origin high-sample trajectories, i.e., τ = ρ ×(8 or 16).
2) Evaluation Metrics: The task of trajectory recovery is to recover high-sample ρ -interval trajectories from low-sample raw trajectories. Following [11], we adopt both the accuracy of the road segments recovered and the distance error of location inference to evaluate the performances of different models.

MAE & RMSE. Mean Absolute Error (MAE) and Root Mean
Square Error (RMSE) are common performance metrics typically used for regression tasks. Following [11], we adopt road network distance to calculate the distance error between two GPS points. That is, given a predicted map-matched trajectorŷ ρ = (ê 1 ,r 1 , t 1 ) , (ê 2 ,r 2 , t 2 ) , ..., ê lρ ,r lρ , t lρ , we derive the location of the GPS pointp i based onê i andr i ; similarly, we can find the ground truth GPS point p i for trajectory ρ. Accordingly, M AE (ρ,ρ) = 1 Recall & Precision & F1 Score. Given a predicted travel path Eρ = {ê 1 ,ê 2 , ...,ê lρ } extracted from a predicted trajectorŷ ρ and the ground truth travel path E ρ = {e 1 , e 2 , ..., e lρ } extracted from the ground truth trajectory ρ, we follow previous work [11], [54], [55] and define Recall (ρ,ρ) = |Eρ∩Eρ| |Eρ| , and P recision (ρ,ρ) = |Eρ∩Eρ| |Eρ| . We also adopt F1 score to further evaluate the models, i.e. F 1 (ρ,ρ) = 2×Recall(ρ,ρ)×P recision(ρ,ρ) Recall(ρ,ρ)+P recision(ρ,ρ) . Accuracy. The accuracy between predicted trajectoryρ and ground truth trajectory ρ is calculated by Accuracy (ρ,ρ) = 1 lρ lρ i=1 1{e i =ê i }, which evaluates the model's ability to match the recovered GPS trajectory to the corresponding road segments. SR%k. In order to further evaluate the robustness of the models, we create another task, namely elevated road recovery, to evaluate models' ability to accurately recover trajectories on elevated roads and nearby trunk roads. As mentioned in [56], GPS locations can be inaccurate in densely populated and highly built-up urban areas, making the task of trajectory recovery more challenging and significant. As we foresee the recovered trajectories in those areas contain more errors, we propose to use SR%k instead of average F1 score that is more sensitive to poor cases. Specifically, given a predicted travel path Eρ and ground truth travel path E ρ , we choose a subtrajectory E ρ of lengthl ρ which drives on or near an elevated road along with the predicted sub-trajectory Eρ. Then, SR%k calculates the proportion of trajectories with F 1( E ρ , Eρ) value exceeding k to evaluate the models' ability to discriminate complex roads using contextual trajectory information.
3) Parameter Settings: In our experiments, we implement RNTrajRec and all the baseline models in Python Pytorch [57] framework. We set the size of hidden-state vectors d to 512 for Chengdu and Porto datasets. Due to memory limitation, we set d to 256 for Shanghai-L dataset. We use the same size of hidden-state vectors for all the models across datasets. Also, we set the size of grid cell to 50m × 50m. For our model, we set both the number of GAT modules in road network representation M and the number of GPSFormer layers N to 2, and set the number of GAT modules in graph refinement layer P to 1. Also, we set hyper-parameters δ and γ to 400 and 30 meters respectively, set the number of attention heads h in both Eq. (4) and Eq. (10) to 8 and λ 1 , λ 2 in Eq. (19) to 10 and 0.1 respectively. The size of f r is set to 11, i.e. 8 for level of road segment, 1 for length of road segment, 1 for number of in-edges and 1 for number of out-edges, and that for f l is set to 25, i.e. 24 for one-hot vector for hour of the day and 1 for holiday or not. Following [11], we set hyperparameter β (used to set constraint mask) to 15 meters. All the models are trained with Adam optimizer [58] for 30 epochs with batch size 64 and learning rate 10 −3 . All the experiments are conducted on a machine with AMD Ryzen 9 5950X 16 cores CPU and 24GB NVIDIA GeForce RTX 3090 GPU.

4) Compared models:
To evaluate the effectiveness of RNTrajRec, we implement in total eight baselines. i) Linear [18]+HMM uses linear interpolation to obtain a highsample trajectory, and then HMM algorithm to obtain a map-matched ρ -sample interval trajectory. ii) DHTR+HMM replaces Linear with a hybrid Seq2Seq model with kalman filter [59]. iii) t2vec proposes a deep learning network for trajectory similarity learning with a BiLSTM [48] model to capture the temporal dependency of the given trajectory. iv) Transformer [22] learns the representation with temporal dependency. Follow [11], we use grid cell index and time index for each sample point in the trajectory. v) NeuTraj adds a spatial attention memory model to LSTM to capture rich nearby spatial features for trajectory representation. vi) T3S combines a self-attention network with a spatial LSTM model to capture spatial and structural features of trajectories. vii) GTS [10] is the state-of-the-art method for learning trajectory similarity in spatial network which uses POIs as input. To adapt GTS to our problem setting, we regard each intersection in the road network as a POI, and cut every long road segment into segments every 100 meters and treat each cut point as a POI. Also, we use the embedding vector of the nearest POI to obtain the representation of each GPS point in the trajectory. viii) MTrajRec is the state-of-the-art method for trajectory recovery task.
Remark 1: Traj2SimVec is a novel model for trajectory similarity learning with auxiliary supervision for sub-trajectory. However, its encoder model is simply a RNN-based model, which is similar to t2vec. Since we mainly compare the performance of different models on GPS trajectory representation learning, we do not include this method for comparison.
Remark 2: We refer to A+Decoder as using the encoder model proposed in A and the decoder model proposed in [11] for trajectory recovery task.

B. Performance Evaluation
We report the experimental results in Table III. Numbers in bold font indicate the best performers, and numbers underlined represent the best performers among existing baselines without considering our model. As shown, RNTrajRec outperforms all baseline models on all the datasets.
In particular, Linear+HMM performs the worst on all the datasets and its performance drops significantly as the sample interval becomes longer, e.g. the accuracy drops from 0.4916 to 0.2858 when the sample interval increases from 96 seconds to 192 seconds on Chengdu dataset. We also observe that DHTR+HMM outperforms Linear+HMM, which confirms that linear interpolation is not suitable for recovering low sample GPS trajectories.
Another observation is that NeuTraj and GTS, two models proposed for GPS trajectory learning, outperform MTrajRec when they include a decoder model proposed in [11] on top of their encoder models. This well demonstrates that these two models are able to capture spatio-temporal information in low-sample trajectories.
It is observed that end-to-end methods perform better than two-stage methods. Among existing end-to-end models, we observe that NeuTraj achieves the highest accuracy on Chengdu and Porto datasets, while GTS significantly outperforms NeuTraj on Shanghai-L dataset. We believe that it is due to the complex road network structure in Shanghai-L that leads to the high performance for graph-based method. In addition, our method consistently outperforms all these models with a large margin. To be more specific, as compared with the best baseline, RNTrajRec improves F1 score and accuracy by an average of 4.85% and 8.48% respectively, and reduces MAE and RMSE by an average of 27.42 and 35.91 meters respectively for Chengdu dataset; it improves F1 score and accuracy by 4.94% and 9.14% respectively and reduces MAE and RMSE by 46.49 and 56.55 meters respectively for Shanghai-L dataset; it improves F1 score and accuracy of the best baseline by 4.42% and 8.78% respectively and reduces MAE and RMSE by 6.75 and 22.96 meters respectively on Porto dataset. This clearly proves the effectiveness of RN-TrajRec for trajectory recovery, which is mainly contributed by following two reasons. Firstly, RNTrajRec pays attention to the important road network information and road network structure around each GPS point in the trajectory. Secondly, several novel modules are proposed in this paper, such as GridGNN and GPSFormer, that enable the model to learn rich spatial and temporal features of the given trajectory.

C. Additional Experiment Results
We conducts additional experiments on two new datasets, namely Shanghai and Chengdu-Few, to evaluate the performance of RNTrajRec in various data distributions.
For Shanghai dataset, we select another area in Shanghai with a total number of 9, 298 road segments, covering an area of 6.4×14.4 km 2 , and meanwhile keep the other settings (e.g., trajectory sample interval time) of original Shanghai-L dataset. Experiment result shown in Table IV verifies that RNTrajRec still performs the best among all the baseline models.
Because of its design, RNTrajRec might benefit more from a training dataset that contains a large number of trajectories, as compared to other baselines. In order to demonstrate that our model is equally competitive even when the training set contains much fewer trajectories, we construct a new dataset, namely Chengdu-Few, that randomly samples only 20,000 trajectories (roughly 20% of the origin Chengdu dataset) from the original training dataset in Chengdu and meanwhile keep the other settings (e.g., # of road segments and size of the training area) of original Chengdu dataset. In such a setting, our model needs to learn the representation of each road segment along with the representation of each subgraph with limited trajectories.
As reported in Table IV, our method outperforms all the baseline in Chengdu-Few dataset and we believe the reasons lie in the following two aspects. Firstly, when the training set has a limited number of trajectories, many road segments appear only a few times in the training dataset. However, when graph neural network updates a certain road segment, the features of the surrounding road segments are also updated, which offers opportunities for each road segment to learn a good feature representation with limited number of trajectories. Secondly, the input features of each subgraph are obtained from the representation of the road network directly. Therefore, as long as each road segment in the road network has a well-trained feature representation, it's possible for each subgraph to obtain a good feature representation. Last but not the least, we find that although our model still achieves the best results on the new Chengdu-Few dataset, the improvement is slightly less significant than that achieved under the original Chengdu dataset, e.g., on Chengdu dataset, our model outperforms the best baseline by 7.42% in accuracy and 5.80% in F1 score; on Chengdu-Few dataset, these two numbers drop to 6.57% in accuracy and 2.75% in F1 score. We think the main reason is that a transformer model typically requires a large amount of training data. Consequently, when the amount of training data is insufficient, the quality of the final representation will be affected (to a certain degree). Fig. 4 reports the experimental result for elevated road trajectory task on Chengdu dataset. We design this task to serve two main purposes. First, elevated roads and nearby trunk roads normally experience high traffic volume and their traffic conditions are typically more complicated (e.g., elevated roads are more likely to experience traffic congestion during peak hours). Therefore, evaluating the models' ability to discover these sophisticated spatio-temporal patterns is significant. Second, the road network structure around the elevated road is more complex than other urban roads. For example, there are usually two-way trunk road segments under the elevated road segments, which brings greater challenges to the recovery of the road segments on these elevated roads.

D. Robustness Study
As shown in Fig. 4, RNTrajRec significantly outperforms all the baseline models. Interestingly, all the learning-based models significantly outperform HMM-based methods (i.e. Linear/DHTR+HMM), which shows the inability of HMM to discover these complex patterns. In addition, our model can achieve a high F1 score (> 0.8) for 58.8% trajectories, which outperforms the best baseline by 14.4%.

E. Efficiency Study
In addition to the effectiveness of different methods, we also evaluate their efficiency by considering two different aspects, including inference time that refers to the time required to recover a trajectory during the inference phase and the number of parameters. As shown in Fig. 6, RNTrajRec requires less time during the inference than NeuTraj+Decoder, and comparable time cost against GTS+Decoder when using only one layer of GPSFormer. However, our model significantly outperforms both NeuTraj+Decoder and GTS+Decoder in terms   .
of accuracy even if we set N = 1. Besides, DHTR+HMM is observed to spend the most time during inference, probably due to the inefficiency of the adopted kalman filter module. Another observation is that Linear+HMM requires the least time during inference, however it suffers from low accuracy for trajectories with low sample rate. In short, RNTrajRec requires 50.2 microseconds to recover a low-sample trajectory, which is efficient and practical in practice.

Remark:
The time spent to obtain the road network representation via GridGNN is excluded from the inference time reported above. This is because the road network representation can be learned in advance as it is independent of the input trajectory used for the inference task.

Fig. 5 visualizes trajectories recovered by different models,
where the input trajectory is a low-sample elevated road trajectory. We sample partial underlying road network structures (e.g., elevated road segments represented by red lines and main road segments represented by black lines) in the two dash-line rectangles of Fig. 5(a). As we can observe from the visualization, the road network near the elevated roads is complicated. Purple lines in figures represent the ground truth trajectory and orange, green, blue-colored trajectories represent the trajectory recovered by MTrajRec, GTS+Decoder, and RNTrajRec respectively. We can observe that the trajectory recovered by our model matches the ground truth much better (e.g., the trajectories in the green circles provide one example), as RNTrajRec is able to capture the spatial and temporal patterns of trajectories in a more accurate manner. We further plot snapshots of two sections of restored trajectories (bounded by rectangles labelled 1 and 2 ) by different models in the elevated road using the small pictures in the lower right corner in Fig. 5 (b)-(d), together with three recovered points from each section and their corresponding ground truth as examples. It can be observed that both road sections restored by MTrajRec and those restored by GTS+Decoder deviate from the ground truth, while the road sections restored by our model match the ground truth trajectory perfectly. In addition, we want to highlight that points recovered by the two baseline models lack spatial consistency due to their insufficient use of road network. For example, the orange/green star in Fig. 5 (b/c)-2 is a point on the main road, while the next recovered point (i.e., the orange/green circle) is located on the elevated road. Although the two points seem to be located on the same road in our visualization, the shortest path distance between those two points is larger than 2000 metres, implying that the recovered path between these two points is very different from the ground truth. In other words, the fact that our model can recover more accurate trajectories for elevated roads with complex network topology is significant.

G. Ablation Study
To further prove the effectiveness of the modules proposed in the paper, we create five variants of RNTrajRec. w/o GRL replaces the graph refinement layer (GRL) in GPSFormer with standard transformer layer and ignores the graph structure input, i.e. G τ and Z (0) τ ; w/o GF replaces gated fusion discussed in Session IV-D1 with concatenation operation and feed forward network; w/o GN replaces graph normalization discussed in Session IV-D2 with standard layer normalization in transformer encoder; w/o GAT employs feed forward network but not graph attention network in graph refinement layer; w/o GCL removes graph classification (GCL) loss defined in Eq. (18). Experimental results are listed in Table V. We can observe that RNTrajRec consistently outperforms all its variants, which proves the significance of these modules.
As mentioned in Section IV-C, the local surrounding graph structure of GPS points is important for understanding the movement of a trajectory. Therefore, we observe a significant drop in overall performance after removing GRL, especially for Recall and F1 Score. Besides, we observe that RNTrajRec w/o GRL significantly outperforms Transformer+Decoder, with the input to the transformer layer being their only difference. Therefore, we conclude that a well-designed input embedding is significant for complex encoding models like transformer.
GRL is considered the most important component in RN-TrajRec, in which graph normalization, gated fusion and graph forward is replaced with layer normalization, multi-head attention and feed forward network in original transformer respectively. In order to better justify the design of these individual modules, we design ablation study to answer the following three questions.
• Q1: Why we use graph normalization to replace layer normalization in graph refinement layer?
• Q2: Why we use graph attention network to replace feed forward network in graph refinement layer?
• Q3: Why we use gate fusion instead of other simple method (say concatenation or MLP) in graph refinement layer? Q1: Why Graph Normalization? The idea of designing the graph normalization is inspired by [33], in which an experiment has been conducted to demonstrate that batch normalization is more suitable for graph transformers. Therefore, we design a similar normalization strategy for dynamic graph transformer (or spatial-temporal transformer). In addition, we observe that layer normalization ignores other nodes in the same sub-graph, which may cause the normalized features of different nodes in the same sub-graph lack discrimination.
Q2: Why Graph Attention Network? There are two main reasons behind the design of an additional graph attention network in graph refinement layer. First, as mentioned in Session IV-C, each subgraph Z (0) τ,i directly uses the features in the road segments as the input but totally ignores the relationship inside each subgraph. Second, transformer encoder discussed in Session IV-E can effectively aggregate features from the entire trajectory, therefore, the relationship in each subgraph can be refined with the output of transformer encoder.
Q3: Why Gated Fusion? As mentioned in Session IV-D, we adopt gated fusion to adaptively fuse the input hidden vectors and the node features in the graph structure.
Extensive results reported in Table V well verify that the performance of RNTrajRec will degrade if any of the three parts are replaced/removed.
As for GCL, it is mainly to guide the process of trajectory encoding so as to generate more accurate trajectory representation. As shown in Table V, we observe that GCL indeed improves the accuracy of the recovered trajectory.
In addition, we study the effectiveness of different road network representation methods. As shown in Fig. 7(a), we compare GridGNN with three novel graph neural networks (GNNs), namely GCN, GIN and GAT for graph representation. All these models are implemented using standard DGL [60] library. We observe that GridGNN consistently performs the best, which shows the effectiveness of integrating grid information for road network representation. In addition, GAT outperforms GIN and GCN for graph representation, which shows the significance of self-attention mechanism.
H. Parameter Analysis 1) The impact of the number of GPSFormerBlock N : The number of GPSFormerBlock N directly influences the complexity of RNTrajRec. To examine its impact, we vary N in RNTrajRec from 1 to 5 and report the results in Fig. 7(b). Note, when N is too large, the model will be more prone to overfitting, resulting in a decrease in its performance. We observe from the results that RNTrajRec achieves the highest accuracy when N = 3. However, considering the efficiency of the model and the usage of GPU memory, we set N to 2.
2) The influence of receptive field of GPS point δ: The value of receptive field of GPS point δ decides the size of the surrounding sub-graph of each GPS point in the trajectory. A larger δ allows the sub-graph to capture more information of surrounding area with a higher memory cost. In order to study the impact of δ on RNTrajRec's performance, we vary δ from 100 meters to 800 meters. As shown in Fig. 7(c), RNTrajRec achieves the highest accuracy when δ is set to 600 meters. To balance between the effectiveness and efficiency of the model, we set δ to 400 meters.
3) The influence of hyper-parameter γ in Eq. (5): We vary the hyper-parameter γ from 10 meters to 50 meters. With the increase of γ, the initial hidden-state vectors H (0) τ will pay more attention to the road segments that are closer to the GPS point, while pay less attention to those far away from the GPS point. Because of the uncertainty of GPS errors, the effect of increasing γ on the model is also uncertain. As shown in Fig. 7(d), we observe that the performance of the model does not vary much as γ changes. We believe the main reason is that GPSFormer can dynamically adjust the weight of each node in the sub-graph for the current GPS point, making the model insensitive to the changes of hyper-parameter γ.

I. Discussion
We have explored many different techniques during the design of RNTrajRec. Though most of our attempts are effective, there is one technique that we tried but did not work. When designing the graph refinement layer, ideally the graph transformer network is able to refine not only the graph embedding of each subgraph but also the weight of each node in every subgraph. Specifically, we try to use the refined graph embedding at layer l, i.e. Z (l) τ , to obtain a new weight for each node by first transforming Z (l) τ , followed by either sigmoid function or softmax function. However, we find out that both sigmoid function and softmax function perform worse than a simple approach that does not refine the weight in each subgraph, i.e. directly using mean pooling as discussed in Section IV-D. We believe the main reason behind this failed attempt is that the linear transformation is too simple to learn valuable weights without proper supervision.

VII. CONCLUSION
Trajectory recovery is a significant task for utilizing lowsample trajectories effectively. In this paper, we propose a novel spatial-temporal transformer-based model, namely RN-TrajRec, to capture rich spatial and temporal information of the given low-sample trajectory. Specifically, we propose a road network representation module, namely GridGNN and a novel spatial-temporal transformer module, namely GPSFormer for encoding a GPS trajectory. We then forward the hidden-state vectors to a multi-task decoder model to recover the missing GPS points. Also, we propose a graph classification loss with constraint mask to guide the process of trajectory encoding. Extensive experiments on three real-life datasets show the effectiveness and efficiency of the proposed method.