A Graph-based Representation Framework for Trajectory Recovery via Spatiotemporal Interval-Informed Seq2Seq

1 Introduction

Low-sampling rate datasets present a formidable obstacle when it comes to analyzing and utilizing trajectory data in urban settings. Such limitations often lead to significant inaccuracies and spatial disparities in vital tasks such as estimating travel times [Wang et al., 2022; Zhang et al., 2018], forecasting traffic flow [Li and Zhu, 2021; Lan et al., 2022] and trajectory similarity measurement [Yao et al., 2022; Han et al., 2021]. Therefore, it becomes imperative to develop methods for enhancing the sampling rate by effectively recovering the missing points within a trajectory.

∗The Corresponding Author

Recently, there has been a surge in deep learning-based models for trajectory recovery, such as MTrajRec [Ren et al., 2021] and RNTrajRec [Chen et al., 2023]. These methods adopt a sequence-to-sequence [Sutskever et al., 2014] architecture, featuring an encoder model responsible for generating representations of the input trajectory and a decoder model tasked with recovering the trajectory point by point. Representation learning, a deep learning technique that automatically discovers meaningful patterns from raw data, has been widely used to model trajectory data [Jiang et al., 2023] and road networks [Zhang and Zhao, 2021; Fu and Lee, 2020], in a wide range of downstream tasks [Li et al., 2018; Yang et al., 2021]. Furthermore, it plays a vital role in trajectory recovery. For instance, RNTrajRec utilizes road network representation learning and trajectory representation learning within the encoder to effectively capture both temporal and spatial features for each GPS point in the trajectory.

Nevertheless, it is important to note that all existing works still grapple with three significant limitations: (1) Ignorance of dynamic trajectory-road network interactions: Much of the existing research tends to either overlook the road network entirely or solely focus on static road networks, which contain only the fixed topology of the road network and do not account for the dynamic trajectory information traversing it. However, this trajectory-aware road network interplay plays a crucial role in the task of trajectory recovery. For instance, as illustrated in Figure 1, when provided with the road segments where the blue trajectory points are located, it becomes necessary to recover the missing road segments where the purple trajectory points circled in red are situated. In this context, road segments passing through or close to the blue trajectory gain higher consideration for selection compared to other road segments farther away from the blue trajectory points. (2) Neglect of extracting the overall and synergistic spatiotemporal trajectory representation: Most studies solely rely on grid information or raw GPS points as input, resulting in extracted trajectory representations that lack comprehensiveness and synergy. (3) Failure of considering the crucial spatiotemporal intervals when employing a seq2seq: Many prior studies have relied on simple seq2seq models, often overlooking the crucial role of spatiotemporal intervals between trajectory points. However, it is essential to recognize that these intervals hold significance. For instance, smaller intervals between the first and second points within a trajectory imply similar embeddings, while larger intervals between the first and last points indicate weaker correlations. Failing to account for these spatiotemporal intervals between points can impede the effective extraction of comprehensive spatiotemporal contextual information among trajectory points, thereby hindering the recovery accuracy.

To overcome the three limitations inherent in existing trajectory recovery methods, we introduce a groundbreaking graph-based representation framework with a spatiotemporal interval-informed seq2seq model, known as GRFTrajRec. GRFTrajRec takes its first stride by harnessing trajectoryaware graph representation, enhancing the understanding of trajectory road network interactions and facilitating the extraction of detailed embedding features for road segments while considering dynamic trajectory information. Furthermore, it employs trajectory representation to capture overall and synergistic spatiotemporal features at each trajectory point. Finally, accounting for spatiotemporal intervals between points, GRFTrajRec utilizes a spatiotemporal intervalinformed seq2seq model to effectively integrate and leverage both road and trajectory representations, thereby enabling the precise recovery of missing GPS points. In summary, our key contributions can be outlined as follows:

• We propose a novel framework, namely GRFTrajRec 1 . To the best of our knowledge, GRNTrajRec is the first attempt to use trajectory-road network interaction for the task of trajectory recovery.
• We introduce a trajectory-aware graph representation for extracting advanced road embedding, enabling a deep understanding of the interplay between trajectories and roads, considering dynamic trajectory information. Additionally, we leverage trajectory representation to capture the spatiotemporal features of each trajectory point.
• We propose a spatiotemporal interval-informed seq2seq model that combines an attention-enhanced transformer and a feature differences-aware decoder, all considering the spatiotemporal intervals between points. This model enhances the integration of road and trajectory representations, extracting comprehensive spatiotemporal contextual information between trajectory points.
• Extensive experimental results obtained from three reallife datasets conclusively and unequivocally demonstrate that GRFTrajRec outperforms all competitors in both prediction accuracy and spatial consistency.

1 Source codes: https://github.com/zhaoyaya1234/GRFTrajRec.

2 RelatedWork

Road Network Representation Learning. Many existing works consider the road network as a directed graph. Models like Node2vec [Grover and Leskovec, 2016] and DeepWalk [Perozzi et al., 2014] have been introduced to represent road segments as latent embeddings. With the rapid advancement of graph neural networks (GNNs), various graph convolutional networks, such as GCN [Kipf and Welling, 2017], GraphSage [Hamilton et al., 2017], and GAT [Veliˇckovi´c et al., 2018], have proven to be suitable for road network representation. Recent studies have focused on road network representation learning, notably SGMP [Zhang and Zhao, 2021] and Trembr [Fu and Lee, 2020]. SGMP offers a framework for spatial network representation, while Trembr's Road2Vec model learns embeddings for road segments by understanding the relationships among these segments.

Trajectory Representation Learning. In recent years, trajectory representation learning has garnered widespread attention, as evidenced in [Li et al., 2023; Jarboui and Perchet, 2021]. Prominent models in this field include DeepTTE [Wang et al., 2022], T2vec [Li et al., 2018], ST2vec [Fang et al., 2022], and Start [Jiang et al., 2023]. DeepTTE employs LSTM modules to capture temporal dependencies and generate trajectory representations. T2vec introduces a pioneering deep learning model for trajectory similarity learning, utilizing BiLSTM [Graves and Graves, 2012] to model temporal dependencies. ST2vec [Fang et al., 2022] focuses on encoding both spatial and temporal information within trajectories. Most recently, Start [Jiang et al., 2023] presents a graph-based trajectory representation method, complemented by an innovative spatial network based on GAT [Veliˇckovi´c et al., 2018].

Trajectory Recovery. Various studies, including [Xia et al., 2022; Zhang et al., 2022; Si et al., 2023; Chen et al., 2023], have proposed innovative solutions to address the trajectory recovery challenge. Notably, DHTR [Wang et al., 2020] proposes a two-stage solution that first recovers a highsample trajectory and then uses a map matching algorithm (i.e., HMM [Newson and Krumm, 2009]) to recover the actual GPS locations. Another significant advancement, MTrajRec, as detailed in [Ren et al., 2021], employs a sequence-tosequence model [Sutskever et al., 2014]. It has outperformed two-stage techniques and is widely adopted in subsequent trajectory recovery research. However, most of these studies overlook the crucial road network structure aspect, which could enhance accuracy. RNTrajRec [Chen et al., 2023] addresses this by introducing GridGNN for road segment feature learning and GPSFormer for detailed trajectory analysis. These components enable a multi-task decoder to efficiently reconstruct missing GPS points using encoder outputs.

3 Preliminaries

Definition 1 (Road Network). A Road Network is modelled 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.

Definition 2 (Trajectory). A trajectory τ can be defined as a sequence of GPS positions with timestamps, i.e., τ = (p1, p2, · · · , pn), where pi = ⟨lat(i) , lng(i) , t(i) ⟩, ∀i, 1 ≤ i ≤ n, which captures the latitude and longitude of the GPS position at timestamp t(i) .

Definition 3 (Road Segment Candidate Probability (RCP τ )). Given a raw trajectory τ = (p1, p2, · · · , pn) and a specified radius R, the road segment candidate frequency N τ j for road segment vj ∈ V is defined as follows: N τ j = ∑ni=1 I[vj is within a radius of R from pi], where I[·] is the identity function. The standardized N τ j is defined as the road segment candidate probability RCP τ j , with ∑|V| j=1 RCP τ j = 1.

Definition 4 (Map-matched Trajectory Point). Given a trajectory point pj and a map-matching function M(·), the map-matched trajectory point aj for pj is defined as aj = M(pj) = ⟨e(j) , r(j) , t(j) , lat(j) pre , lng(j) pre ⟩, where e(j) is the matched road segment, r(j) is the moving ratio (representing the ratio of moving distance over the length of the road segment), and t(j) is the timestamp. The coordinates ⟨lat(j) pre , lng(j) pre ⟩ are the map-matched latitude and longitude on e(j) .

Definition 5 (Map-matched ϵ-Sampling Rate Trajectory). A map-matched trajectory ˜ τ with ϵ-sampling rate is a sequence of map-matched trajectory points, i.e., ˜ τ = (a1, a2, · · · , am), where aj = ⟨e(j) , r(j) , t(j) , lat(j) pre , lng(j) pre ⟩, ∀j, 1 ≤ j ≤ m and aj+1.t(j+1) - aj.t(j) = ϵ. For simplicity, we name ˜ τ as

ϵ-MM trajectory ,with ϵ representing the sampling rate.

Definition 6 (Trajectory Recovery). Given a lowsampling-rate trajectory τ = (p1, p2, · · · , pn) with corresponding map-matched road segment sequence τ ′ = (M(p1),M(p2), ...,M(pn)) and a target sampling rate ϵ, we aim to recover the real map-matched ϵ sampling-rate trajectory ˜ τ = (a1, a2, · · · , am). This is to say, for each low-sampling-rate trajectory, we will infer its missing points and map match it onto the road network simultaneously.

4 Methodology

In this section, we detail the components of the proposed framework GRFTrajRec for trajectory recovery, depicted in Figure 2. (1) We employ the Figure 2.(a) trajectory-aware graph representation and Figure 2.(b) spatiotemporal trajectory representation to derive an overall representation Z τ for the low-sampling trajectory. (2) Using the attention-enhanced transformer encoder described in the Figure 2.(c) spatiotemporal interval-informed seq2seq model with Z τ , we generate the initial GRU hidden cell h(0) gru. (3) Utilizing the feature differences-aware decoder in the Figure 2.(c) based on h(0) gru, we decode the high-sampling trajectory ˜ τ point by point.

4.1 Trajectory-Aware Graph Representation

In this subsection, we initially analyze the static road network topology to derive a geographical graph representation. Next, we introduce CandiGNN (Candidate Graph Neural Network)

to acquire a candidate road network representation. This enables a more profound and nuanced comprehension of the intricate relationship between trajectories and roads by leveraging dynamic trajectory information. Lastly, we integrate the geographical representation with the dynamic candidate representation to obtain the ultimate trajectory-aware graph representation.

Geographical Representation: GeoGAT. The topology of the road network plays a crucial role in the formation of a trajectory. To capture the structural information, we first utilize Node2Vec [Grover and Leskovec, 2016] to obtain a geographical representation gi for road segment vi. Next, we feed gi to a graph attention network (GAT [Veliˇckovi´c et al., 2018]) step by step to obtain a smoothed road geographical representation ˜gi ∈ Rdhid .

Candidate Representation: CandiGNN. While GeoGAT effectively captures the geographic characteristics of road segments, it has limitations in extracting dynamic recovery information from the original trajectory sequence. To address this limitation, we introduce road segment candidate probability (RCP) in Definition 3. This probability represents the likelihood that a road segment either passes through a trajectory point or is close to a trajectory point. The higher the RCP value for a road segment, the greater the probability that it will pass through a trajectory point, and subsequently, the greater the probability that it will be selected as the road segment where the missing points are located.

To extract the candidate representation of the graph effectively, we propose a novel graph neural network called CandiGNN. In its message-passing process, CandiGNN leverages candidate probability in measuring the correlations between candidate road segments. First, we take random vector c(0) i ∈ Rdin as the initialized candidate representation for node vi. We use the difference in candidate probabilities to represent the information mobility between road segments, then the attention weight α(l) ij between nodes vi and vj in the l-th update are computed as:

where c(l) i , c(l) j ∈ Rdin represent the candidate representations for nodes vi and vj respectively during the l-th update of parameters, W (l) 0 ∈ Rdin×din ,W (l) 1 ∈ Rdin×1 are learnable parameters. The negative input slope of LeakyReLU is set to 0.2 [He et al., 2015]. Then we obtain the road candidate representation ˜ci ∈ Rdhid for node vi through combining the features of its neighbors using the attention weights αlij as:

where W (l) 2 ,W (l) 3 ∈ Rdin×dmid ,W (l) 4 ∈ Rdmid×dmid and W (l) 5 ∈ Rdmid×dhid are the learnable parameters.

Graph Fusion Layer. We propose a co-attention fusion module to fuse the geographical representation and candidate representation to get the final trajectory-aware graph representation. Given a raw trajectory τ with corresponding mapmatched road segment IDs src, for simplicity, its static geographical representation and dynamic candidate representation acquired by src are denoted by Gτ = (˜g1, ˜g2, . . . , ˜gn) and Cτ = (˜c1, ˜c2, . . . , ˜cn), where Gτ ,Cτ ∈ Rn×dhid . We integrate Gτ ,Cτ to get final road segment representation. Specifically, we concatenate Gτ and Cτ to get Hτ ∈ Rn×2×dhid and calculate the fusion attention:

where W (l) q ,W (l) k ,W (l) v ∈ Rdhid×dhid are learnable parameters. Denote the fusion result as ˜Hτ ∈ Rn×2×dhid and we obtain the final output Hτroad ∈ Rn×dgraph , where dgraph = 2dhid, using a feedforward network FNN(·) and batch normalization Norm(·) as does in [Vaswani et al., 2017]:

4.2 Spatiotemporal Trajectory Representation

In this subsection, building upon existing approaches relying on grid information or raw GPS points, integrating overall spatial sequences and relative positions in high-sampling trajectories, we present a spatiotemporal trajectory representation meticulously designed to capture overall and synergistic spatiotemporal information inherent in trajectory sequences.

Time-Aware Representation. To capture the temporal information of a trajectory τ, we first convert its timestamp sequence (t1, t2, · · · , tn) into a sequence in seconds and normalize each timestamp to the range of [0, 1] using min-max normalization. Denote (ts1 , ts2 , · · · , tsn ) as the standardized time sequence. Then, we obtain the time representation of the sequence T τ ∈ Rn×dtime via linear projection:

where W (l) t ∈ R1×dtime are learnable parameters.

Spatial-Aware Representation. To enhance the extraction of spatial information from the raw sequence τ = (p1, p2, · · · , pn), we divide the entire road network area into grids identified by coordinates ⟨xi, yi⟩. In this way, each point pi is located in a specific grid. We also define tidi = ⌊ t(i)-t(0) ϵ ⌋ as the index for the points in the target ϵ-MM trajectory ˜ τ, where ϵ denotes the desired sampling rate and t(i) is the timestamp of i-th point in the low-sampling-rate trajectory τ. Consequently, each raw point pi is represented as a triplet ⟨xi, yi, tidi⟩ , ∀i, 1 ≤ i ≤ n.

Initially, we retrieve the spatial grid representation Gridi ∈ R1×dgrid using the grid coordinates ⟨xi, yi⟩:

where max(x) represents the maximum value among all x coordinates within the area, and Embedding refers to the embedding technique in [Mikolov et al., 2013]. Then we use tidi to get the spatial positional encoding POSi ∈ R1×dpos using the following equation:

In conclusion, note dsp = dgrid + dpos + 3, the final spatialaware representation Sτ ∈ Rn×dsp , is obtained by:

We concatenate the spatial-aware representation Sτ and temporal-aware representation T τ to obtain the spatiotemporal representation of trajectory τ, denoted by Hτtraj ∈ Rn×dtraj , where dtraj = dsp + dtime.

4.3 Spatiotemporal Interval-Informed Seq2Seq

In this subsection, we present a spatiotemporal intervalinformed seq2seq model that combines an attention-enhanced transformer with a feature-aware decoder. This model leverages spatiotemporal intervals between points to enhance the extraction of contextual information between trajectory points, effectively integrating road and trajectory representations for improved performance.

Attention-Enhanced Transformer Encoder. For trajectory τ, we concatenate its graph representation Hτroad , trajectory representation Hτtraj , road features RF ∈ Rn×dRF , road segment IDs src ∈ Rn×1 , and trajectory velocity speed ∈ Rn×1 , culminating in the formation of the full representation of the trajectory τ, i.e., GST τ ∈ Rn×(dgraph+dtraj+dRF+2) . Then we apply a linear layer on GST τ and add the position embedding [Vaswani et al., 2017] to obtain the spatial-temporal input Zτ ∈ Rn×dhid to the transformer encoder. Considering the time interval ∆tid = |tidi - tidj| and geographic distance interval dis = distance(⟨lat(i) , lng(i) ⟩, ⟨lat(j) , lng(j) ⟩) between samples in the trajectory, we propose an enhanced selfattention mechanism to obtain the contextual trajectory representation ˜Zτ = ( ˜Zτ1 , ˜Zτ2 , . . . , ˜Zτn , ˜Zτi ∈ R1×dhid ):

where A(l) Q ,A(l) K , A(l) V ∈ Rdhid×d′ are learnable parameters, d′ = dhid/hnum, hnum is the number of attention heads, α and β are hyperparameters, f and g are the corresponding probability transformation function.

Feature Differences-Aware Decoder. When decoding the j-th point aj in ˜ τ, the spatiotemporal interval between the (j - 1)-th predicted map-matched trajectory point aj-1 =

⟨e(j-1) , r(j-1) , t(j-1) , lat(j-1) Pre , lng(j-1) Pre ⟩ and an input raw point pi = ⟨lat(i) , lng(i) , t(i) ⟩ varies across all i in the range 1 ≤ i ≤ n. To take this into account, we define a spatiotemporal feature difference vector fi ∈ R1×3 , which represents differences in sequence position, spatial location, and road segment candidate probability:

where RCP τe(t-1) and RCP τM(pi) are the candidate probabilities for road segment e(t-1) and matched road segment M(pi) for pi. We propose a differences-aware decoder that incorporates a GRU model [Cho et al., 2014] with the feature difference vector fi. In the GRU model, the hiddenstate vector at timestamp j is denoted as h(j) gru, initially set to h(0) gru = Mean( ˜Zτ ) ∈ R1×dhid . To capture the correlation between aj-1 and pi, we introduce an attention mechanism attn(j) ∈ R1×dhid based on the feature difference fi:

where W (l) tf ∈ Rdhid×1 , W (l) attn ∈ R(2dhid+3)×dhid are learnable weights. The hidden-state vectors h(j) gru is updated by:

where j ∈ [1, 2, · · · ,m] , p(j-1) ∈ R1×did is the embedding for the predicted road segment e(j-1) , r(j-1) ∈ R1×1 is moving ratio at the (j - 1)-th timestamp, RF (j-1) ∈ R1×dRF is corresponding road features, attn(j) is the attention value.

4.4 Training

We employ a multi-task loss for training the model. Specifically, we consider predicting both the road segment ID and the moving ratio. In accordance with MTrajRec [Ren et al., 2021], we employ the cross-entropy loss L1(θ) for the road segment ID prediction task and mean squared error (MSE) loss L2(θ) for the moving ratio prediction task:

where m is the length ˜ τ, |V| is the size of road segments, aj.e is the ground truth of road segment ID, ˆaj is the prediction,D means the testing dataset consisting of lowsampling-rate trajectories and ϵ-MM trajectories, aj.r is the ground truth of the real moving ratio, p(j) represents the road segment embedding for the predicted road segment at the j-th timestamp,Pθ and Rθ represents the neural network for predicting road segments and the moving ratio. Overall, the final objective function is a weighted sum of the two functions:

5 Evaluation

5.1 Experimental Setup

Datasets. We validate the effectiveness of our model on three real-world trajectory datasets along with their corresponding road networks sourced from OpenStreetMap 2 . The Porto dataset 3 are openly available, while the YanCheng and NanJing datasets are provided by a company partner. Detailed statistics of these datasets are presented in Table 1. For each dataset, we divided the data into training, validation, and testing sets, following a 7:2:1 split ratio. To obtain lowsample trajectories, we set three distinct data missing types: random missing (where the missing trajectory points are scattered randomly), uniform missing (where the missing points are uniformly distributed across the entire trajectory), and block missing (where the missing points form a continuous sub-trajectory segment within the trajectory). Additionally, our experiments adopt two missing rates: 7/8 or 15/16 in line with the rates used in RNTrajRec [Chen et al., 2023].

Baselines. To evaluate the effectiveness of GRFTrajRec, we implement in total seven baselines. i) HMM + Linear [Hoteit et al., 2014] uses linear interpolation to obtain a high sample trajectory, and then uses HMM algorithm to obtain a map-matched ϵ-sampling rate trajectory. ii)

2 https://www.openstreetmap.org

3 https://www.kaggle.com/c/pkdd-15-predict-taxi-servicetrajectory-i/data

t2vec [Li et al., 2018] proposes a deep learning network for trajectory similarity learning with a BiLSTM [Graves and Graves, 2012] model. iii) ST2vec [Fang et al., 2022] encodes spatial and temporal information of trajectories. iv) Transformer [Vaswani et al., 2017] learns the representation with temporal dependency. v) MTrajRec [Ren et al., 2021] solve the map-constrained trajectory recovery problem via seq2seq multi-task learning. vi) RNTrajRec [Chen et al., 2023] is the state-of-the-art method for trajectory recovery task. vii) Start [Jiang et al., 2023] is the state-of-the-art method for trajectory representation in spatial networks which is applicable for many trajectory-based downstream tasks.

Parameter Settings. We implemented all the baseline models on a machine equipped with an Intel(R) Xeon(R) 32core CPU E5-2620 v4 @ 2.10GHz and a 12GB NVIDIA TITAN V GPU. All models were trained using the Adam optimizer for at most 50 epochs, with a batch size of 128 and a learning rate of 1e-3. For the Porto dataset, we configured the hidden-state size hyperparameter d to be 512. For the YanCheng and NanJing datasets, we set it to 128. We explore (alpha ∈ {1,10,100,1000}, beta ∈ {1,10,100,1000}, lambda ∈ {10,20,30,40,50}). The optimal model parameters are Porto (100, 100, 10), YanCheng (1, 1, 10) and NanJing (1, 1, 10) while the worst model parameters are Porto (1, 1, 20), YanCheng (1000, 1000, 20) and NanJing (1000,1000,20).

Metrics. Following RNTrajRec [Chen et al., 2023], we adopt the accuracy, recall, precision, f1score of the road segments recovered and the RN_MAE,RN_RMSE of distance on road network, as well as MAE and RMSE of the euclidean distance between predicted and actual points to evaluate the performances of different models.

5.2 Overall Performance

We conducted a comprehensive performance evaluation in the scenario of random missing data using the Porto and YanCheng datasets, as summarized in Table 2. The figures highlighted in bold signify the top-performing models. Notably, GRFrajRec consistently outperforms the baseline models across all datasets, demonstrating significant advantages across most metrics. Meanwhile, Linear+HMM consistently underperforms across all datasets. Notably, both TFrajRec and MTrajRec demonstrate superior performance on ID prediction metrics (accuracy, f1score), showcasing their ability to capture spatiotemporal information in low-sample trajectories. However, they fall short in segment prediction error metrics (RN_MAE,RN_RMSE) due to their lack of consideration for the road network's topological aspects. In contrast, RNTrajRec and StartRec incorporate the topological characteristics of the road network, resulting in improved performance in segment prediction error metrics. Remarkably, their ID prediction performance is on par with the previous two models. Our framework, GRFrajRec, emerges as the standout performer, excelling in both ID prediction metrics and road network segment prediction error metrics.

5.3 Further Experiments

We extend our experimentation to include the Nanjing dataset and introduce two additional missing types: uniform missing and block missing. This broader scope allows us to assess the generalizability and robustness of our model across various scenarios and datasets with differing distributions and complexities. The results, as depicted in Figure 3 alongside Table 2, consistently reaffirm the superior performance of GRFTrajRec across all missing types and datasets. This robust performance underscores the adaptability, versatility and reliability of GRFTrajRec in diverse real-world settings. These findings bolster confidence in the effectiveness of GRFTrajRec and highlight its potential for real-world applications across different contexts and real data distributions.

5.4 Ablation Study

To further verify the effectiveness of different modules in our model, we have devised five variants of GRFTrajRec: i) GRF-ATF removes the spatiotemporal interval consideration in the attention-enhanced transformer encoder and uses the traditional transformer. ii) GRF-FD removes the spatiotemporal interval consideration in the feature differencesaware decoder and uses the traditional GRU. iii) GRF-GR removes the trajectory-aware graph representation. iv) GRFCG+ removes CandiGNN but add the traditional GCN [Kipf and Welling, 2017] to the trajectory-aware graph representation. v) GRF-TR removes the spatiotemporal trajectory representation. The experimental results are detailed in Table 3. It's evident from the data that GRFTrajRec consistently surpasses all its variants across the majority of settings, highlighting the importance and effectiveness of these modules.

As discussed in subsection 4.1, the importance of trajectory-aware graph representation (GR) becomes evident in extracting advanced road embeddings. Removing GR from GRFTrajRec leads to a significant decline in overall performance. Notably, GRFTrajRec consistently outperforms GRF-CG+, only when replacing CandiGNN with the traditional GCN, highlighting the necessity of a dedicated graph neural network for trajectory recovery. Moreover, the omission of the spatiotemporal interval consideration in the feature differences-aware decoder results in a notable drop of over 0.4 across all datasets. This highlights the effectiveness of considering spatiotemporal interval in the decoder, reaffirming its importance in enhancing recovery accuracy. Across various metrics, GRFTrajRec consistently outperforms both GRF-ATF and GRF-TR, demonstrating the contributions of the attention-enhanced transformer and spatiotemporal representation learning in improving recovery accuracy. Overall, the trajectory-aware graph representation and the feature differences-aware decoder emerge as the two most crucial components within GRFTrajRec, underscoring their indispensable roles in achieving superior recovery performance.

5.5 Case Study

We conduct the visualization comparison experiment on the trajectory recovery task. The input is a low-sampling trajectory, while the ground truth is the actual trajectory at a higher sampling rate. We provide the trajectory recovery results of our model, GRFTrajRec, as well as two of the current bestperforming models, RNTrajRec and StartRec.

As illustrated in Figure 4, while all three models can recover the approximate high-sampling trajectory, our model's trajectory recovery closely aligns with the ground truth. In contrast, RNTrajRec and StartRec exhibit noticeable deviations from the ground truth, particularly at the trajectories' ends. Our model's precision in achieving seamless recovery from start to finish is bolstered by its holistic consideration of the interaction between road networks and trajectories, along with the spatiotemporal intervals between trajectory points. The dynamic interaction effectively incorporates missing information into the representation of low-sampling trajectories. Additionally, the spatiotemporal intervals between points facilitate a nuanced understanding of the specific spatiotemporal relationships among missing points and other data points. This comprehensive analysis enhances our ability to accurately pinpoint the spatiotemporal positions of each missing point, reducing overall recovery errors and notably enhancing trajectory recovery accuracy.

5.6 Efficiency Study

In addition to evaluating method effectiveness, we also assess efficiency from two perspectives: inference time for recovering a trajectory and the number of model parameters.

As shown in Figure 5, when compared to RNTrajRec and StartRec, which share similar inference times and model parameters, GRFTrajRec demonstrates superior performance in both accuracy (ACC) and mean absolute error (MAE) metrics. Many other models, despite having relatively fewer parameters or shorter runtimes, often compromise accuracy (ACC) or substantially increase mean absolute error (MAE).

Our model's longer inference time is due to the consideration of spatiotemporal intervals in seq2seq modelling, which significantly improves prediction accuracy (ACC) and reduces prediction error (MAE), as revealed in our ablation experiments in subsection 5.4. Thus, we believe that the little increase in the inference time is a worthwhile trade-off, considering it leads to enhanced ACC and reduced MAE.

5.7 Assessment of Trajectory Recovery Necessity

Assessing the necessity of trajectory recovery is paramount across various tasks, scenarios and different data densities, to effectively optimize predictive models based on trajectory data and ultimately save costs. For instance, by evaluating the impact of trajectory data of varying densities on model performance, we can determine when trajectory recovery is advantageous. We predict driver IDs using trajectory representation from the model in subsection 4.2. We employ 10,000 trajectories (sample one point per second), adjusting the missing rate to control trajectory data density. We observe a significant drop in model performance when the missing rate exceeds 0.75 (sample 0.25 points per second). (1) In scenarios with several points sampled per second below 0.25 due to data collection limitations, indicating excessively sparse sampling, trajectory recovery may enhance model performance. (2) Conversely, if the number of points sampled per second is above 0.25, and the data density is relatively high, model optimization takes precedence over trajectory recovery.

6 Discussion and Conclusion

In this paper, we introduce a new graph-based framework for trajectory recovery with spatiotemporal interval-informed seq2seq, GRFTrajRec. Experiments demonstrate that GRFTrajRec outperforms current methods by better integrating trajectory-road network interactions and considering spatiotemporal intervals. For future work, we aim to focus on advancing trajectory-network interaction analysis beyond only using road segment candidate probability modelling and explore calculating spatiotemporal intervals for selected points rather than all to speed up the computational speed.

Acknowledgments

This work is supported by the MOE Project of Key Research Institute of Humanities and Social Sciences (No.22JJD110001), the National Natural Science Foundation of China (No.72171229) and the Outstanding Innovative Talents Cultivation Funded Programs 2023 of Renmin University of China. This work is also partly supported by the Marsden Fund Council from Government funding (MFP-UOA2123) administered by the Royal Society of New Zealand, and NSF IIS award #2153369.