ProDiff: Prototype-Guided Diffusion for Minimal Information Trajectory Imputation
Authors: Tianci Bu
Le Zhou
Wenchuan Yang
Jianhong Mou
Kang Yang
Suoyi Tan
Feng Yao
Jingyuan Wang
Xin Lu
Venue: ICML 2025 poster (2025)
Keywords: Minimal Information Trajectory Imputation
Prototype Learning
Diffusion Model
Primary area: applications->time_series
TL;DR: A prototype-guided diffusion model that captures macro-level mobility patterns while maintaining high fidelity in minimal information trajectory imputation.

Abstract: Trajectory data is crucial for various applications but often suffers from incompleteness due to device limitations and diverse collection scenarios. Existing imputation methods rely on sparse trajectory or travel information, such as velocity, to infer missing points. However, these approaches assume that sparse trajectories retain essential behavioral patterns, which place significant demands on data acquisition and overlook the potential of large-scale human trajectory embeddings.
To address this, we propose ProDiff, a trajectory imputation framework that uses only two endpoints as minimal information. It integrates prototype learning to embed human movement patterns and a denoising diffusion probabilistic model for robust spatiotemporal reconstruction. Joint training with a tailored loss function ensures effective imputation.
ProDiff outperforms state-of-the-art methods, improving accuracy by 6.28\% on FourSquare and 2.52\% on WuXi. Further analysis shows a 0.927 correlation between generated and real trajectories, demonstrating the effectiveness of our approach.

ProDiff: Prototype-Guided Diffusion for Minimal Information Trajectory
Imputation
Tianci Bu "1 Le Zhou
Wenchuan Yang"
Jianhong Mou
Kang Yang?
Suoyi Tan
Feng Yao
Jingyuan Wang 345
Xin Lu
Abstract
Traditional Imputation
Predefined graphs
Trajectory
Trajectory data is crucial for various applications but often suffers from incompleteness due to de- vice limitations and diverse collection scenarios. Existing imputation methods rely on sparse tra- jectory travel information, such velocity, infer missing points. However, these approaches assume that sparse trajectories retain essential behavioral patterns, which place significant de- mands on data acquisition and overlook the poten- tial of large-scale human trajectory embeddings. To address this, we propose ProDiff, trajec- tory imputation framework that uses only two endpoints as minimal information. It integrates prototype learning to embed human movement patterns and a denoising diffusion probabilistic model for robust spatiotemporal reconstruction. Joint training with tailored loss function ensures effective imputation. ProDiff outperforms state- of-the-art methods, improving accuracy by 6.28% FourSquare and 2.52% on WuXi. Further anal- ysis shows a 0).27 correlation between generated and real trajectories, demonstrating the effective- ness of our approach.
GroundTruth
Trajectory
Minimal Info Imputation
Imputation
Fiintte Turka
Complex
Ads Cherry
BRU
Protutyyes space
Trajectory
Figure Comparison traditional and proposed trajectory im- putation. Traditional methods preserve movement patterns but impose device constraints and rely on predefined graphs. Our ap- proach directly embeds trajectories into vector space for minimal information imputation.
Zhang et al., 2023; Zheng et al., 2014; Hettige et al., 2024; et al., 2022b). Such data primarily originates from Location- Based Services (LBS) using cell tower signals (Lu al., 2012), satellite-based systems such GPS, GLONASS, BeiDou, QZSS, and Galileo, as well as IP-based location methods utilized by online platforms.
Most of the trajectory mining tasks (Bao et al., 2021; Yao et al., 2017; Wang et al., 2018) and methods(Li et al., 2018; Huang al., 2022: Shen al., 2020) are based on the as- sumption of complete and accurate trajectory data (Chen et al., 2024), making them sensitive to the granularity and accuracy of sampled data. However, contemporary loca- tion data collection, reliant on mobile networks or satellite communications, often hindered by base station cover- age gaps, signal instability, and environmental interference, leading frequent missing data. Traditional methods like linear interpolation (Blu al., 2004) and vector autoregres- sive models (Lütkepohl, 2013) provide efficient solutions but often fail to capture the full data distribution. Deep learning- based imputation methods like Wu et al. (2023); Du et al. (2023); Xia et al. (2021) capture spatial-temporal dependencies using self- atf-ntttntion mechanisms or convolu- tional neural network, while some methods based on graph
1. Introduction
Mining spatio-temporal patterns from trajectory data has broad applications, such as infectious diseases control, hu- man behavioral analysis, and urban planning (Jia et al., 2020;
'qqual contribution 'College of Systems Engineering. National University of Defense Technology, Changsha, China "School of In- formation, Renmin University of China, Beijing, China "School of Computer Science and Engineering, Beihang University, Beijing, China "School of Economics and Management, Beihang Univer- sity, Beijing 100191, China 'Engineering Research Center of Ad- vanced Computer Application Technology. Ministry of Education. Correspondence to: Jingyuan Wang <jywang www...cu........ edu.en>> Xin Lu Iuin.lu.labe outlook.com>>.
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

ProDiff:: Proiotype-Cuided Diffusion for Minimal Information Trajectory Imputation
neural networks (Chen et al., 2023; Wei al., 2024) rely on predefined graph structures to extract spatial-temporal features. Recently, generative methods such as generative adversarial networks (GANs) (Jiang et al., 2023b) and varia- tional autoencoders (VAEs) (Chen et al., 2021) have shown promise in trajectory synthesis, and the emergence of de- noising diffusion probabilistic models (DDPMs) (Ho et al., 2020) has further advanced the field. For instance. DiffTraj (Zhu et al., 2024a) leverages diffusion model to capture group-level trajectories, generating synthetic trajectory data while preserving privacy.
We relax the prior assumption that sparse trajectories in- herently retain movement patterns and introduce trajec- tory imputation under minimal information constraints.
We propose a prototype- based condition extractor that embeds human trajectories into a vector space, captur- ing macro-level behavioral patterns for the first time in trajectory imputation.
We develop ProDiff, a framework that jointly optimizes generative modeling and prototype learning, effectively reconstructing missing trajectory data while reducing independent errors.
Despite progress, existing trajectory imputation methods face notable limitations. First, they typically assume that sampled trajectories, despite large intervals, retain essential movement patterns, interpolating local points using global trajectories thereby imposing constraints devices and op- erational environments. Second, they fail to fully embed the vast amount of unlabeled human trajectories, which exhibit consistent macro-level patterns that enable imputation under more relaxed conditions, as shown in Fig. 1. Although recent work (Wei et al., 2024) has leveraged unlabeled tra- jectories aid imputation, it required the graph structures as the foundamental element for prediction.
We conduct extensive experiments WuXi (Song et al., 2017) and Foursquare (Yang et al., 2014), demon- strating superior imputation accuracy across differ- ent trajectory window sizes. Our code is available at https: https:://githune httpt/uua.....o//o000ooo///ooooo
2. Related Work
Please refer to Appendix A for an extensive discussion of related work. Here we provide its summary.
To address these limitations, we introduce ProDiff, framework integrating Prototype learning with a denois- ing Diffusion probabilistic model. ProDiff operates under minimal information constraints, modeling a trajectory as a sequence of points and interpolating missing locations using only two endpoints within fixed-length window. This relaxes the prior assumption that sparse trajectories must retain essential movement patterns. ProDiff consists of two key components: (i) Diffusion- based generative model: The diffusion model reconstructs human movement by it- eratively denoising from a latent space, offering reliable spatiotemporal modeling. (ii) Prototype-based condition extractor: This module learns prototypes that represent in- dividual movement patterns, embedding diverse trajecto- ries into vector space through self-supervised learning, Given known trajectory information as queries, it extracts comprehensive pattern representation to guide the difffusion model in generating realistic, individualized trajectories. To effectively couple these two components, we design a joint training loss function that integrates generative and prototype learning objectives. This ensures more com- pact embedding space while mitigating independent error accumulation and irreversible information loss typically introduced by multi-stage training. Experimental results demonstrate the effectiveness of the proposed ProDiff and prove that the captured underlying trajectory structures can signficantly improve the imputation accuracy.
Spatial-Temporal Sequence Imputation. Traditional im- putation methods evolved from simple statistical approaches like linear interpolation (Blu et al., 2004) to probabilistic frameworks such as PCA and Bayesian networks (Qu et al., 2009; Shi et al., 2013), are fast but often too simple to cap- ture complex distributions. Deep learning revolutionized the field through two paradigms: non non-generative models like GRU-D (Che et al., 2018) with temporal decay mech- anisms and SAITS (Du et al., 2023) using masked self- attention, and generative approaches where diffusion mod- cls like Diffusion-TS (Yuan & Qiao, 2024) now dominate by disentangling -ead-seassnalltty components.
Trajectory Data Mining. Trajectory analysis spans fore- casting, estimation, and anomaly detection. CNN/RNN architectures (Bao et al., 2021; Yang et al., 2017) pioneered point-wise prediction, while road-aware models like WDR (Wang et al., 2018) advanced travel time estimation through road network embeddings. Anomaly detection evolved from Rased classifiers (Song et al., 2018) to latent space methods like GM-VSAE (Liu et al., 2020). The emerging mobility generation field bridges forecasting and synthesis, exemplified by DiffTraj (Zhu et al., 2024a) applying raw GPS diffusion, yet lacks physics-aware trajectory topology preservation gap our work addresses.
Mobility Data Synthesizing. Early synthesis relied on statistical approximations (Simini et al., 2021) until VAES (Chen et al., 2021) and GANs (Jiang et al., 2023b) intro- duced deep generative modeling. Graph- based innovations like RNTrajRee (Chen et al., 2023) captured semantics
In summary, the contributions of this work are as follows:
2

---

ProDiff:: Prototype-Guided Diffusion for Minimal Information Trajectory Imputation
Forward Process
q x
X
/
Concatinaate
Noise Schedule
Noise
ResNet Block
ResNet Block
ResNet
Prototype Condition Extractor (PCE)
Block
Self-
Encoder
Features
Query
Prototype Leaming
Allention
Diffusson Process
ResNet
Condition Ancoder
Block
Base Condition
ResNet Block
Condition Diffission Model
Guassian
ResNet Block
Extract
Po (X 2.)
Fully Connect Layer
Figure 2. Left illustrates how prototype learning and diffusion models interact. The diffusion process progressively corrupts trajectories with Gaussian noise, preserving only the endpoints, while prototype learning embeds trajectories and extracts patterns. During denoising, prototype-hased conditions, combined with endpoint features, guide the diffusion model. A joint loss function optimizes both components, ensuring offective trajectory reconstruction. Right is the architecture of the diffusion base model.
through spatial-temporal transformers, while attention archi- tectures (Xia et al., 2021) explicitly modeled cross-region dependencies. Modern diffusion frameworks such as Con- trolTraj (Zhu et al., 2024b) enable conditional generation via traffic signal conditioning but remain resolution-rigid.
3.2. Base Network Components
Diffusion Base Model. To capture spatiotemporal depen- dencies in trajectory imputation, we employ ID-UNet with residual network (ResNet) blocks. The ID-UNet con- sists of down-sampling and up-sampling modules, linked by self-attention layer. Each module encodes hidden fea- tures using group normalization, nonlinear activation, and ID-CNN layers. The self-attention mechanism refines tra- jectory representations via:
3. ProDiff Model
3.1. Problem Definition
Definition 3.1. Spatio-Temppral Trajectory. A spatio- temporal trajectory is sequence of human activity points, denoted as X, E IR"", where n represents the num- ber of attributes. Each point consists of time, longitude, and latitude, i.e., X,,j = {4 Loni, lalı,;), satisfying t.g 14,++1. The trajectory of an individual is defined X, [x,,,,.,,,,,, x,,,, where is the trajectory length.
Qnky 2h Vdn
Self-Aut(Q1,, KA, Vx.) = Sootmax
Vn,
(1)
where Qs. Kn. and Vn, are derived from hidden features h. The features obtained through self-attention are then passed through the up-sampling module to output the predicted noise, as shown in the right of Fig. 2.
Definition 3.2. Trajectory Sequence Window. To process trajectories, we define sliding window of size & (k < 1) that partitions trajectory X; into overlapping segments. Each segment is represented as Sp [sp,1, .........p.. Sp.4l. yield- ing | k + segments per trajectory. Given M trajectories, the total number of segments for fixed is EM (4--k +)),, where trajectories shorter than l are discarded.
Base Condition. Trajectory imputation relies on re- constructing intermediate points from the trajectory end- points. Specifically, given of trajectory points S $r.1,..., s. E Rexd where k denotes the trajectory length, we generate a mask M = [mı..... m&] E B which is corresponding to S,. For any element my:
if 0orj k m, 2 otherwise.
1,
Definition 3.3. Minimal-Informatee Imputation. Given
trajectory X; (x.,,,..., x;,), where each point Xi,j (ti., lon lat,, represents spatio-temporal coordinate, we define the minimal-inforee infommatnnff imputation problem as reconstructing X,,; .., X1,1- given only the endpoints X,,1 and X;,
This mask, when applied to trajectory points, encodes the locations to acquire the base condition B while guiding the diffusion model in reconstructing the missing points.
3

---

ProDiff: Proiotype-Cuided Diffusion for Minimal Information Trajectory Imputation
Test Process
Prototypes
Training Process
Here, P represents the prototype-conditioned feature, align- ing trajectory embeddings with learned movement patterns. Dis(Q", P.) can be an arbitrary distance function between query Q and 1th prototype P.. With encoder optimization, the prototypes representing movement patterns are refined, and the PCE can effectively enhance the diffusion model's guidance by matching the base condition with the prototype and generating comprehensive prototype condition.
2
Loss Function
Chere 1
Choster N
Protolype Condition
Pscudo Label
PCE
Query
FC Layer
K-means Cluster
Query Features
Features
To integrate the base condition and prototype condition, we encode and combine them using Wide & Deep (WD) network, which contains two fully connected layers for each condition. Then the final joint condition Jo is formulated as:
Transformer Encoder
Test Data
Training Data
Fmbedding
J J= =D=WD(B)) + +WDBB)
Figure 3. Composition of prototype condition extractor and its workflow during the training and test (hlack and blue lines).
Fig. details the specific workflow of the prototype network. On the right and middle sections, complete trajectories are used train the prototype network, enhancing the gen- eration of prototypes that accurately represent movement patterns. This training is optimized through unsupervised contrastive loss and the joint loss function. On the left and middle sections, during testing, trajectories are encoded and used to query the trained prototypes to generate the prototype condition.
3.3. Prototype Condition Extractor
Embedding Trajectory Data. To exploit large-scale un- labeled data, we introduce Prototype Condition Extrac- tor (PCE) that embeds trajectories into vector space and extracts latent movement patterns. For each trajectory S; = [st,,, ..., S Rexd of window size k, the trajectory representation H, computed as:
3.4. Jointly Training Objective
Given i.i.d. samples ~ p. a diffussion probabilistic model approximates the data distribution by learning pe (Z)) the forward process, Gaussian noise diffuses the data via the stochastic differential equation (SDE):
H = Σ (Encoder(s.,))).
(3)
Prototypes P E IR xd where N, denotes the number of prototypes and d, represents the embedded dimension are then generated via fully connected layer:
dz f(Z, t) g(t)dw,
(8)
(4) where Wp and bp are learnable parameters. Since the hidden feature Hp is considered as trajectory representa- tion which is summed up from the features of all points in trajectory S. Moreover, prototypes P are generated by Hp expressing the generic movement pattern of trajectory S, which are iteratively refined and serve as conditioning features for inference.
P= Hp + bp:
where f(-) is the drift coefficient, g(-) is the diffusion co- efficient, and w is standard Wiener process. The reverse process, conditioned on Jc, is given by:
dz [f(z,t) (() V log (Z)J))dt+ (9)
where Vz log pr (Z(J9) is the conditional score function. The denoising network estimates this score function:
ca (Z. 1. 1. -9)) 2 log
(10)
Conditioning the Diffusion Model. While the base condi- tion serves as guide, it often provides implicit information, making it difficult for the model to derive sufficient insights directly. To enhance the diffusion model's guidance, we encode trajectory data into queries Q* {Q1,-.. .... QB) E TR Bxd of B trajectories and project them into the prototype space using:
where the joint condition J = (Zo). The joint loss function is:
C,(0,)) (.(0,n)-EuuEurppee. [[|e co (o. (11)
0 and are the optimized parameters of denoising network and joint condition extraction network.
D Diss Q6, Pt), PN,))]
(5) To enhance prototype learning for unsupervised trajectory
P DPP.
(6) data, we introduce additional loss functions to refine f

---

ProDiff:: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
and capture semantic movement patterns. The first classifi- cation consisteney loss, LC1, enforces alignment between K-means clustering and prototype-based learning. Given trajectory features Hp = {H1. H..... and Ne clusters, K-means assigns pseudo-labels Pkmeans, which guide pro- totype learning via:
I enables diverse prototypes that capture local tangents and reconstruct manifold structures via linear combinations (Roweis & Saul, 2000). With these assumptions, we have:
Theorem 3.4 (The Optimality of Prototype Learning). Any global optimua (f", (P%T) satisfies:
No E
1. Prototypes approximate conditional expectations: p = (x) E C
(ci())=
Phmeans log( Pproto)
(12)
2. Contrastive loss enforces prototype separation, form- ing diverse directional vectors: (p:.p)) S c. c. i # j.
where Sproto represents the prototype-asiined label. To ensure compact, discriminative feature space, we employ contrastive loss that optimizes prototype separation. Given trajectory features Hp and prototypes P = {P',..., PN, J. let P and P be the closest and farthest prototypes, re- spectively. The loss is defined as:
Proof. Using Pollard's consistency theorem (Pollard, 1981), the empirical cluster centers converge to conditional expec- tations:
Pk R E (x* E Ck).
(c2(7)=BB [max (0, d(H,, -() P )-)m)) (13)
From InfoNCE-based contrastive loss (Saunshi et al., 2019). optimality conditions ensure prototype distinctiveness:
where m is a margin ensuring separation, and d(.s) is
(x) [x) - f² ph 8, Vk + y.
distance metric (e.g., Euclidean). Afterward, the final objective integrates all loss functions:
where > 0 ,Since the clustering term already guarantees that pS = [f) x E Cyyl averaging over cluster Cy gives:
[(,,7) (1,)00,7) + A2Car (1) + AaCc2(1), (14)
where \1, A2 A control the weight of each term. The full training process is outlined in Algorithm 1.
(gg pT)) (F pk: 6.
shifting the terms leads to the observation:
3.5. Inference Processes
( 1 5 < e, #
In the Inference process, given information about two points trajectory with sequential order, the corresponding base condition can be generated according to Eq. 2. The base condition is utilized as query and projected into the space of trained robust prototypes to obtain the prototype condi- tion, and finally the joint condition is obtained through Eq. 7. Then, the inference process conduct the trained denoising function co to denoise from a standard Gaussian noise Z step by step. A more detailed algorithm can be found in Algorithm 2.
which indicates that contrastive loss forces prototypes into globally distinct directions, ensuring effective representation of manifold local structures.
4. Experiments
4.1. Datasets
Our experiments utilize two well-established trajectory datasets: (1) WuXi: Extracted from mobile signal data (Song et al., 2017), covering WuXi, China, over six months (Oct 2013-Mar 2014). It records locations whenever users' phones are active. For efficiency, we use 10-day subset, concatenating individual trajectories. (2) Foursquare: A public dataset (Yang et al., 2014) containing check-ins over 10 months (Apr 2012 2013) in New York and Tokyo. Each check-in includes a timestamp, GPS coordinates, and semantic tags. All datasets are anonymized, ensuring no privacy concerns. Tab. in Appendix D provides details.
3.6. On the Prototype Loss for Trajectory Learning
Prototype learning can be seen as the combination of clus- tering and contrastive learning. Formally, for data points X (#1, Tn, }, the embedding function f Rd R and prototypes .o....PPK. P are optimized by,
Σ [5(x))) Pv. py.11 21 + Aecontrast (f(x)) Pucr (p&H). f.(pa)
min
In trajectory imputation scenario, we propose two basic assumptions which ensure the representiveness of macro- level human movement patterns: (1) Human trajectory data is drawn from a mixture of distributions, each localized on manifold region M with mean Pig. (2) The embedding
4.2. Evaluation Metric and Baseline
We evaluate trajectory imputation by comparing against (i) time-series interpolation methods and (ii) -ppecii approaches, with corresponding evaluation metrics.
5

---

ProDiff: Prolotype-Cuided Diffusion for Minimal Information Trajectory Imputation
Table 1. Comparison of model performance for different thresholds and different trajectory lengths on WuXi and FourSquare.
WuXi
FourSquare
Method
TC@2k
TC@4k
TC@6k
TC@8k
TC@ 10k
TC TC@2k
6C
TC@8k
TC@10K
VAR (Lütkepohl. 2013)
0.5194
0,5632
0.6050
0.6441
0.6811
0,5000
0.5000
0.5000
0,5000
0,5000
SAITS (Du et al., 2023)
0,5059
0,5224
0.5498
0.5861
0,6311
0,5000
0,5000
0,5000
0,5000
0,5000
TimesNet (Wu al., 2023)
0,5080
0.5290
0,5593
0.5955
0.6352
0.5015
0.5054
0,5133
0.5258
0,5431
1
Diff-TS (Yuan & Qiao, 2024)
0,5123
0,5462
0.5951
0.6496
0.7060
0,5268
0.5714
0,6173
0.6571
0.6932
DiffTaa (Zhu et al., 2024a)
0.6958
0,8198
0.8816
0,9169
0.9402
0.5945
0.6845
0.7574
0,8189
0,8666
Diff+Mask (Ours)
0.6584
0.7731
0,8400
0.8834
0,9159
0.6541
0.7379
0.8010
0.8525
0.8928
ProDiff (Ours)
0.7155
0.8414
0,9006
0.9326
0.9520
0.6644
0,7452
0.8087
0.8596
0.8971
VAR (Litteepoll, 2013)
0.3360
0.3437
0.3556
0,3692
0,3840
0.3333
0.3333
0.3334
0.3334
0.3335
SAITS (Du et al. 2023)
0,3427
0.3762
0.4275
0,4880
0,5533
0.3333
0,3333
0,3333
0.3333
0,3333
TimesNet (Wu et al., 2023)
0,3419
0,3654
0.4029
0.4500
0.5044
0,3386
0.3530
0.3756
0,4039
0. 0.4341
T
Diff-TS (Yuan & Qiao, 2024)
0.3515
0.4011
0.4726
0.5491
0.6211
0.3761
0.4283
0,4827
0,5383
0,5874
DaffTra (Zhu al., 2024a)
0.5976
0.7476
0.8227
0.8688
0,9005
0.4277
0.5404
0.6428
0.7314
0,8025
Diff-Mask (Ours)
0,5767
0.7324
0.8228
0,8802
0,9180
0,4859
0,5970
0.6902
0.7671
0.8265
ProDiff (Ours)
0,5978
0,7686
0,8518
0.8992
0.9285
0,5005
0.6093
0.7013
0.7772
0.8345
VAR (1 (Lättepphhl, 2013)
0,2537
0.2627
0,2739
0.2861
0.2986
0,2500
0,2500
0.2500
0,2500
0,2500
SAITS (Du el al., 2023)
0,2572
0,2764
0,3059
0,3485
0,3976
0,2500
0.2502
0,2505
0,2509
0,2513
TimesNet (Wu et al.. 2023)
0.2520
0,2574
0.2663
0.2785
0.2942
0,2516
0.2563
0.2634
0.2715
0,2808
1
Diff-TS (Yuan & Qiao, 2024)
0.2689
0.3199
0.3907
0,4676
0.5453
0.3233
0.3932
0,4611
0.5358
0.5964
DiffTraj (Zhu et al., 2024a)
0,5418
0.7009
0,7868
0,8414
0,8795
0.3316
0.4526
0,5671
0.6688
0.7520
Diff+Mask (Ours)
0.4486
0,5946
0.6943
0.7631
0.8107
0,3957
0.5300
0.6431
0,7350
0.8045
ProDiff (Ours)
0.5752
0.7501
0.8236
0.8663
0.8945
0.4000
0.5331
0.6474
0.7404
0.8090
VAR (Littkephhl, 2013)
0,2012
0.2047
0.2102
0,2177
0.2270
0,2000
0.2000
0,2000
0,2000
0,2000
SAITS (Du et al., 2023)
0,2080
0,2316
0,2686
0.3158
0.3692
0,2000
0,2000
0,2000
0,2000
0,2000
TimesNet (Wu al., 2023)
0,2073
0.2275
0,2591
0.3035
0.3559
0.2003
0,2013
0,2034
0.2064
0,2110
Diff-TS (Yuan & Qiao, 2024)
0,2173
0.2655
0.3367
0.4190
0.5000
0.2751
0.3484
0.4207
0.4990
0.5646
DiffTra (Zhu et al., 2024a)
0.4994
0.6687
0.7640
0.8259
0.8692
0.2762
0.4024
0.5300
0.6453
0.7386
Diff+Mask (Ours)
0.3793
0.5104
0.6046
0.6773
0.7344
0.3412
0,4800
0.5999
0.7023
0.7868
ProDiff (Ours)
0.4996
0.6994
0.8048
0.8667
0.9053
0.3522
0.4910
0.6105
0.7146
0.7920
For time-series interpolation, we benchmark against classi- cal methods like Vector Autoregression (VAR) (Lütkepohl, 2005) and state-of-the-arr apatio-tempora models, includ- ing SAITS (Du et al., 2023), TimesNet (Wu et al., 2023), Diffusion-TS (Yuan & Qiao, 2024), and Diff (Zhu et al., 2024a). To measure imputation accuracy, we introduce tra- jectory coverage (TC@7), which quantifies the proportion of generated points si within threshold from the ground truth S;
4.3. Implementation Details
Our experiments balance the effectiveness of each module in the joint training; we set λ1, d2, As to 1. Gradient updates were facilitated using the Adam optimizer, initialized with a learning rate of 2e-4, We summarize the hyperparameter settings for the diffusion model and PCE in Tab. 2.
Table 2. General setting of ProDiff model
Diffusion
PCE
1 k TCOT = k 1=1
Parameter
Setting value
Parameter
Setting value
I (d(s),), < <),,
(15)
Diffusion Steps
500
Prototypes
20
Embedding Dim
128
Embedding Dim
512
8 (lineur schedule) 0.0001-00.05
Heads
8
where si is the generated points, and I(.) is indica- tor function that equals when d(sā,j 8..)) is less than the threshold 7 and 0 otherwise.
ResNet Blocks
2
Encoder Blocks
Sampling Blocks
4
Forward Dim
256
Input Length
3 ~~ 10
Dropout ratio
0.1
For trajectory-specifee baselines, we compare against RN- TrajRec (Chen et al., 2023), TrajeGe (Jiang et al., 2023b), MM-STGED (Wei et al., 2024), AttnMove (Xia et al., 2021), and DiffTraj (Zhu et al., 2024a). To ensure fairness, we remove modules reliant unavailable auxil- iary information. Performance is assessed using standard trajectory generation metrics, including Density, Distance, Segment Distance, Radius, MAE, and RMSE. Further de- tails on evaluation protocols and baselines are provided in Appendix D.
4.4. Main Results
The trajectory coverage across different baselines and win- dow sizes is presented in Tab. 1, where "TC@2k" represents the percentage of generated values within 2km of the true location, with TC@4k-10K extending up to 10km. The highest and second-highest values are marked in red and blue, respectively. We evaluate performance separately for time-series interpolation methods and snjeecorry-spccinn approaches.
6

---

ProDiff: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
a
SegDistance
Distance
RNTajRec
NN-STIGED
AttnMove
Pro
310
Radius
Density
MAE
RMSE MH-STGED
RNTA/Rec
T5-PajGen
AitoMove
ProDUI
Figure 4. a. Radar charts illustrate normalized performance different models across six distinct metrics. b. Histogram comparing the performance of each model across different metrics, with dashed lines indicating the best-performing model's values for each metric.
(1) Comparison with Time-Series Interpolation Meth- ods. ProDiff consistently outperforms sequence imputation models across datasets. On the WuXi dataset with & 4, ProDiff achieves 71 71.55% at TC @
with CC1 and Lc2 further enhancing its effectiveness in cap- turing movement patterns. Notably, the performance gain of PCE is more pronounced at longer distances when A = 8, suggesting that its effectiveness increases with extended trajectory segments.
(<70%), As the threshold increases exceeding all baselines maintains high accuracy
ProDiff 20..... with its advan- tage over the second- brooddbbetttt method expanding from 1.18% at TC@2k 3.61% % at TC@ 10k. Furthermore, ProDiff demon- strates robustness across datasets and segment sizes, where other models, such DiffTraj. suffer sharp declines at larger thresholds (TC@6k-10k) On the FourSquare dataset, DiffTraj's s TC@ 2k score for k = 8 drops by 21.02%, while ProDiff only decreases by 11 1..5%. Additionally, while Diff- Traj loses its second-place ranking to Diff-Mask, ProDiff retains its lead, indicating its ability to learn stable move- ment patterns via the prototype condition extractor.
Table 3. Performance comparison of removing different modules.
Method
TC@:2k
TC@
TC&
TC@8k
TC@ 10k
ProDiff 0.5978
0.7686
0.8518
0.8992
0.9285
1
w.o. Pro 0.5767
0.7324
0.8228
0,8802
0.9180
w.o. Lei
0.5939
0.7556
0.8371
0.8867
0.9195
w.o. Lea
0.5952
0.7560
0.8374
0.8869
0.9199
ProDiff 0,5752
0,7501
0,8236
0.8663
0,8945
w.o. Pro 0.4486
0.5946
0.6943
0.7631
0.8107
T
Cen 0.5395
0.7205
0. 0.7966
0,8399
0.8691
Lea 0,4888
0.6638
0.7473
0.7984
0.8340
(2) Comparison with Srajeciory-Specifie Methods. Fig. 4 further validates ProDiff's superiority among trajectory models. Panel (a) presents normalized scores across all metrics, while panel (b) details model-specific performance. ProDiff consistently sets the benchmark across six addi- tional metries. While density scores are similar among mod- els. ProDiff exhibits substantial lead in spatial distribution metrics (e.g., Distance, Segment Distance, Radius, MAE, RMSE), highlighting its effectiveness in diverse conditions.
Table 4, Performance comparison for eVAE and cGAN,
Method
TC@2k
TC@4k
TC@6k
TC@8k
TC@ 10k
eVAE+MASK
0.2616
0.2936
0.3385
0.3926
0.4513
eVA++pro
0.3416
0.3685
0.4082
0.4540
0.5009
cGAN+MASK
0.2760
0.3240
0.3742
0.4285
0.4896
cGAN+pro
0.3074
0.3997
0.4746
0.5361
0.5883
Generalization Across Generative Models. To evaluate PCE's generalizability, we integrated with cVAE and cGAN, applying both MASK and PCE to these models (Tab, 4). At the 10k threshold, adding only MASK yields 45.13% for cVAE and 48. 48.96% for cGAN, whereas incorporating PCE improves accuracy to 50.09% and 58.83%, respec- tively. This highlights PCE's ability to enhance movement pattern learning across different generative frameworks.
4.5. Ablation Study
We conducted three ablation experiments the WuXi dataset to validate the contributions of our key components. We also investigate the accerlaration of the proposed ProD- iff, and the results are provided in Appendix D.
Effect of Prototype Condition Extractor. assess the impact of individual modules. we removed the prototype condition extractor (PCE), cross-entropy loss (Lc1), and contrastive loss (Loz) while keeping the joint loss intact. As shown in Tab. 3, PCE consistently improves performance,
4.6. Utility of Generated Data
To evaluate the real- real-world applicability of ProDiff generated data, we tested its performance on traffic flow analysis in
7

---

ProDiff: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
Region F
Region E
Closest neighbour
Closest
woighbou
Region A
Region
Closest
neighbour
Closes
Region B
neighbour
Region
Closest neighbour
neighbour
Figure 5. Trajectory data representation after dimensionality reduction by PaCMAP, randomly selected samples and neighboring samples plot trajectories to interpret human trajectory patterns captured by prototype learning.
WuXi, using & = 6 trajectory imputations over 7000 individ- uals across 10 days. The city was divided into Ikm x Ikm grids (longitude gap x 0.009%), where each grid's value increments as individuals' trajectories pass through. Fig. 6(a) (top) compares real and ProDiff- ProDiff-generate traffic maps, revealing highly similar spatial patterns. To further ana- lyze peak and trend consistency, we extracted and projected traffic edges (Fig. 6(a), bottom), showing near-identical fluctuations between real and generated data. Additionally, correlation coefficients and spatial distributions between real and generated data (Fig. 6(b), 6(c)) further confirm the reli- ability of ProDiff's imputation. These results demonstrate that ProDiff can generate realistic and usable trajectory data, making it applicable downstream mobility analysis tasks.
GroundTruth
Generated
Similar
Flow
b
1) Catinde Diemioran
Comckrion
Confficiene 0,927
prediction
400
Table Impact of different numbers of prototypes (N) and trajec-
2) Longinus Dienhation
tory length (k).
N
TC@2k
TC@4k
TC@6 6k
TC@88 8k
TC@ 10k
15
0.5881
0.7583
0.8433
0.8928
0,9237
500 orggn
1000
T
0,5978
0.7686
0.8518
0.8992
0,9285
25
0,5868
0.7570
0.8441
0.8951
0,9265
Suaturio af
0.5755
0.7552
0.8217
0.8763
0.8951
Figure 6. Comparison of traffic patterns between groundtruth and generated data. b. The correlation coefficient between groundtruth and generated data. c. Comparison of spatial dis- tributions after normalization of both real and generated data.
T
20
0,5752
0.7501
0.8236
0.8663
0.8945
0.5785
0.7553
0.8237
0.8634
0.9017
8

---

ProDiff:: Prolotype-Cuided Diffusion for Minimal Information Trajectory Imputation
4.7. Hyperparameter Sensitivity.
scalable solution for urban mobility analysis and behavioral modeling. Moving forward, we aim to extend ProDiff to adaptive and personalized trajectory generation, integrat- ing reinforcement learning and uncertainty- aware models to enhance reliability under dynamic and noisy conditions.
We analyze the effect of prototype count (N), trajectory length (k), and diffusion steps (d) (Tab. 5, Appendix Tab. 7). Increasing N from 15 to 20 improves TC@ 10k to 0.9285 for k = 6, while k = 8 benefits from N = 25, suggest- ing behavioral variations across window sizes. Diffusion steps significantly affect performance, with 300 steps yield- ing optimal TC@ 10k (0.9300). Beyond this, performance plateaus, while computational cost increases, making 300 steps practical balance between accuracy and efficiency.
A cknooleedmmnnts
Prof. Xin Lu's work was supported by the National Nat- ural Science Foundation of China (72025405, 72421002, 92467302, 72474223, 72301285), the Science and Technol- ogy Innovation Program of Hunan Province (2023JJ40685, 2024RC3 and the Major Program of Xiangjiang Lab- oratory (24XICCI101001), Prof. Jingyuan Wang's 's work was partially supported by the National Natural Science Foundation of China (No. 72222022, 72171013). Suoyi Tan was supported by the National Nature Science Foun- dation of China (No. 72474223, 72001211 ), the science and technology innovation Program of Hunan Province (No. 2024RC3 133), and the National University of Defense Tech- nology Cornerstone Project (No. JS24-04).
4.8. Interpretability Analysis
Understanding whether prototype learning captures inter- pretable movement patterns in low-dimensional space is essential for evaluating the effectiveness of the joint proto- type learning-diffusion framework. Fig. 5 visualizes this process, where trajectory data is fed into the trained pro- totype condition extractor, clustered using K-means (top 6 classes), and reduced in dimensionality via PaCMAP. To interpret the latent space, we zoom into each class, plotting selected samples and their nearest neighbors. The learned movement patterns exhibit clear semantic coherence. Re- gion A captures trajectories with start and end points in close proximity, reflecting movement within similar loca- tions. Region B extends this pattern, with slightly farther start and end points, aligning with the proximity of the yel- low and green clusters. Region C represents trajectories con- strained within similar locations. Region D deviates from previous patterns, showing long-distance migration with return to the starting point. Region E follows a linear mi- gration and return pattern. Region F is similar to Region A, but its neighboring trajectories occur in different locations. These findings demonstrate the model's ability to embed human trajectory, capture structured movement behaviors, distinguish variations, and optimize representations during training, improving trajectory imputation performance when integrated with the diffusion framework.
Impact Statement
Trajectory Imputation is essential for dealing with incom- plete trajectory data, a common issue stemming from de- vice limitations and varied collection scenarios. Our work presents ProDiff, a prototype-guide diffusion model, to ef- fectively impute trajectories using only minimal information. This approach allows for robust spatiotemporal reconstruc- tion of human movement, even from highly sparse data. While there will be important impacts resulting from im- proved trajectory imputation in general, here we focus on the impact of using our ProDiff framework for minimal in- formation imputation. There are many benefits to using our method, such as significantly improving imputation accu- racy and effectively embedding and capturing macro-level human movement patterns. This paper presents work whose goal is to advance the field of Trajectory Data Mining and Spatio-tempor Data Analysis. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
5. Conclusion
This paper addresses the trajectory imputation problem, fo- cusing on generating realistic trajectories with minimal in- formation. Unlike conventional methods that rely on sparse trajectory pattern, we propose ProDiff, a prototype-gun -ggiddd diffusion model that captures macro-level mobility patterns while maintaining high fidelity in trajectory generation. Our experiments demonstrate that ProDiff outperforms state-of- the-art approaches on two datasets, improving trajectory imputation accuracy. Ablation studies confirm that pro- totype learning significantly enhances trajectory represen- tation, while diffusion modeling effectively reconstructs realistic movements. Beyond imputation, ProDiff may be generalized to broader trajectory-relatee related tasks, offering a
References
Bao, Y., Huang, Z., Li, L., Wang, Y., and Liu, Y. A bilstm- cnn model for predicting users' next locations based on geotagged social media. International Journal of Geo- graphical Information Science, 35(4)6639,660, 2021.
Blu, T., Thévenaz, P., and Unser, M. Linear interpolation revitalized. IEEE Transactions on Image Processing, 13 (5).710-719,200)
Che, Z., Purushotham, S.,, Cho, K., Sontag, D., and Liu, Y.

---

ProDiff:: Prolotype-Cuided Diffusion for Minimal Information Trajectory Imputation
Recurrent neural networks for multivariate time series with missing values. Scientific reports, 8(1 6(1)66085 2018.
Ji, J., Wang, J., Wu, J., Han, B., Zhang. J., and Zheng. Y. Pre- cision cityshield against hazardous chemicals threats via location mining and self-supervised learning. In Proceed- ings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3072-3080, 2022h.
Chen, W., Liang, Y., Zhu, Y., Chang, Y., Luo, K., Wen, H., Li, L., Yu, Y., Wen, Q. Chen, C., et al. Deep learning for trajectory data management and mining: A survey and beyond. arXiv preprint arXiv:2403.14151. 2024.
Ji, J., Wang, J., Huang, C., Wu, J., Xu, B., Wu, Z.,, Zhang. J., and Zheng, Y. Spatio-temporal self-supervised learning for traffic flow prediction. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp. 4356- 4364, 2023.
Chen, X., Xu, J., Zhou, R., Chen, W., Fang. J., and Liu, C. Trajvae: variational autoencoder model for trajectory generation. Neurocomputing. 428:332-339, 2021.
Chen, Y., Zhang. H., Sun, W., and Zheng, B. Rntrajrec: Road network enhanced trajectory recovery with spatial- temporal transformer. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pp. 829-842. IEEE, 2023.
Jia, J. S., Lu, X., Yuan, Y., Xu, G., Jia. J., and Christakis, A. Population flow drives spatio-temporal distribution of covid- 19 in china. Nature, 582(7812))3899-334 2020.
Jiang, J., Han, C., Zhao, W. X., and Wang, J. Pdformer: Propagation delay-aware dynamic long-range transformer for traffic flow prediction. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp. 4365- 4373, 2023a.
De Montjoye, Y.-A., Hidalgo, C. A., Verleysen, M., and Blondel, V. D. Unique in the crowd: The privacy bounds of human mobility. Scientific reports, 3(1):1-5, 2013.
Doersch, C. Tutorial on variational autoencoders. arXiv preprint arXiv:/606.05908, 2016.
Jiang, W., Zhao, W. X., Wang, J., and Jiang, J. Continuous trajectory generation based two-stage gan. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4374-4382, 2023b.
Du, W., Côté, D., and Liu, Y. Saits: self-attention-basee imputation for time series. Expert Systems with Applica- tions, 219:1 219:119619, 19619, 2023.
Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. Transformers are mns: Fast autoregressive transformers with linear attention. In International conference on ma- chine learning, pp. 5156-5165. PMLR, 2020.
Goodfellow, I., Pouget-Absas Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial networks. Communications of the ACM, 63(1 144, 2020.
Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Muchine Learning (ICML 2000). pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Hettige, K. H., Ji, J., Xiang, S., Long, C., Cong, G., and Wang, J. Airphynet: Harnessing physics-guider neural networks for air quality prediction. The 12th Interna- tional Conference on Learning Representations, 2024.
Li, R., Li, C., Ren, D.,, Chen, G., Yuan, Y., and Wang, G. Bediff: Bidirectional consistent diffusion for instanta- neous trajectory prediction. Advances in Neural Informa- tion Processing Systems, 36: 16:14400 14400-14411, 2023.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-688 66511, 2020.
Li, Y., Fu, K. Wang. Z., Shahabi, C., Ye, J., and Liu, Y. Multi-task representation learning for travel time estima- tion. In Proceedings of the 24th ACM SIGKDD interna- tional conference on knowledge discovery & data mining, pp. 1695-1704, 2018
Huang, I., Yang, Y., Chen, H., Zhang, Y., Wang, Z., and He, L. Context-aware road travel time estimation by coupled tensor decomposition based on trajectory data. Knowledge-Baud Based Systems, 245:108594 2022.
Huang. L.. Huang, J., Li, H., and Cui, J. Robust spatial temporal imputation based on spatio-temporal generative adversarial nets. Knowledge- -aseed Systems, 179:110919, 2023.
Liu, Y., Zhao, K., Cong, G., and Bao, Z. Online anomalous trajectory detection with deep generative sequence mod- eling. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 949-960. IEEE, 2020.
Ji, J., Wang, J., Jiang, Z., Jiang, J., and Zhang, H. Stden: Towards physics-guided guided neural networks for traffic flow prediction. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 4048 4048-40566 4056, 2022a.
Liu, Z. Wang, J., Li, Z., and He, Y. Full bayesian signifi- cance testing for neural networks in traffic forecasting. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), 2024.
10

---

ProDiff:: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
Lu, X., Bengtsson, L.,, and Holme, P. Predictability of population displacement after the 2010 haiti earthquake. Proceedings of the National Academy of Sciences, 109 (99)11157--118811 2012.
Song, J., Meng, C., and Ermon, S. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02500,, 2020.
Song, L., Wang, R., Xiao, D., Han, X., Cai, Y., and Shi, C. Anomalous trajectory detection using recurrent neural network. In Advanced Data Mining and Applications: 14th International Conference, ADMA 2018, Nanjing, China, November 16-18, 2018, Proceedings 14, pp. 263- 277. Springer. 2018.
Lütkepohl. H. New introduction to multiple time series analysis. Springer Science & Business Media, 2005.
Lüt H. Vector autoregressive models. In Hand- book of research methods and applications empirical macroeconomics, pp. 139-164. Edward Elgar Publishing, 2013.
Song, X., Ouyang, Y., Du, B., Wang, J., and Xiong, Z. Recovering individual's commute routes based on mo- bile phone data. Mobile Information Systems, 2017(1): 7653706, 2017.
Ma, J., Shou, Z., Zareian, A., Mansour, H., Vetro, A., and Chang, S.-F. Cdsa: cross-dimensional self-attention for multivariate, geo-tagged time series imputation. arXiv preprint arXiv:1905.00 09904, 2019.
Tan, H., Feng, G., Feng, J., Wang, W., Zhang, Y.J.,, and Li, F. A tensor-based method for missing traffic data completion. Transportation Research Part C: Emerging Technologies, 28:15-27 2013.
Pappalardo, L., Manley, E., Sekara, V., and Alessan- dretti, L. Future directions in human mobility sci- ence. Nature Computational Science, 3(7):588 600, July 2023. ISSN 2662-8457. doi: 10.1038/ s43588- 43388--023-0046944 URL http://dx doi. 10. 10.1003/stt /4388//3388--- 0096-444
Wang. J., Gu, Q Wu, J., Liu, G., and Xiong, Z. Traffic speed prediction and congestion source exploration: A deep learning method. In 2016 IEEE 16th international conference on data mining (ICDM), pp. 499-508. IEEE, 2016.
Pollard, D. Strong consistency of k-means clustering. The annals of statistics, pp. 135-140, 1981.
Wang, J., Wu, N., Lu, X., Zhao, W. X., and Feng, K. Deep trajectory recovery with fine- gra-grai calibration using kalman filter. IEEE Transactions on Knowledge and Data Engineering, 33(3):921 2019.
Qu, L., Li, L., Zhang, Y., and Hu, J. Ppea-based missing data imputation for traffic flow volume: A systematical approach. IEEE Transactions on intelligent transporta- tion systems, 10(3):512-555 522, 2009.
Wang, J., Wu, N., and Zhao, W. X. Personalized route recommendation with neural network enhanced search algorithm. IEEE Transactions on Knowledge and Data Engineering, 34(12):5910-592 2021.
Roweis, S. T. and Saul, L. K. Nonlinear dimensionality re- duction by locally linear embedding. science, 290(5500); 2323-2326, 2000.
Saunshi, N., Plevrakis, O., Arora, S., Khodak, M., and Khan- deparkar, H. A theoretical analysis of contrastive unsu- pervised representation learning. In International Con- ference on Machine Learning, pp. 5628-5637 PMLR, 2019.
Wang. Z., Fu, K., and Ye, J. Learning to estimate the travel time. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 858 08--66,,22 2018
Wei, T. Lin, Y., Lin, Y., Guo, S., Zhang, L., and Wan, H. Micro-macro spatial-temporal graph-based encoder- decoder for map-constrained trajectory recovery. IEEE Transactions Knowledge and Data Engineering, 2024.
Shen, Y., Jin, C., Hua, J., and Huang, D. Tipnet: A neural network for travel time prediction based on tensor de- composition and graph embedding. IEEE Transactions on Knowledge and Data Engineering, 34(9)451444426 2020.
Wu, H., Hu, T., Liu, Y., Zhou, H., Wang, J., and Long, M. Timesnet: Temporal 2d-variation modeling for gen- eral time series analysis. In International Conference Learning Representations, 2023.
Shi, F., Zhang, D., Chen, J., and Karimi, H. R. Missing value estimation for microaray data by bayesian princi- pal component analysis and iterative local least squares. Mathematical Problems in Engineering, 2013(1):162938, 2013.
Wu, N., Wang, J., Zhao, W. X., and Jin, Y. Learning to effec- tively estimate the travel time for fastest route recommen- dation. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 1923-1932, 2019.
Simini, F., Barlacchi, G., Luca, M., and Pappalardo, L. A deep gravity model for mobility flows generation. Nature communications, 12(1):6576, 2021.

---

ProDiff:: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
Wu, N., Zhao, X. W., Wang, J., and Pan, D. Learning effective road network representation with hierarchical graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discov- ery & data mining, pp. 6-14, 2020.
Zhu, Y., Yu, J., Zhao, X., Liu, Q. Ye, Y., Chen, W., Zhang, Z., Wei, X., and Liang, Y. Controltraj: Controllable tra- diffusion
jectory generation with model. In Proceedings of the 30th ACM SIGKDD Con- ference on Knowledge Discovery and Data Mining, pp- 4676-4687, 2024b.
Xia, T., Qi. Y., Feng, J., Xu, F., Sun, F., Guo, D., and Li, Y. Attnmove: History enhanced trajectory recovery via attentional network. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 35, pp. 4494 4502, 2021.
Xu, Y., Bazarjani, A., Chi, H.-g., Choi, C., and Fu, Y. Un- covering the missing pattern: Unified framework towards trajectory imputation and prediction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pat- tern Recognition, pp. 9632-9643, 2023.
Yang, C., Sun, M., Zhao, W. X., Liu, Z., and Chang, E. Y. neural network approach to jointly modeling social networks and mobile trajectories. ACM Transactions on Information Systems (TOIS), 35(4):1-28, 2017.
Yang, D., Zhang, D., Zheng, W., and Yu, Z. Modeling user activity preference by leveraging user spatial tempo- ral characteristics in lbsns. IEEE Transactions Systems, Man, and Cybernetics: Systems, 45(1):129-11) 142, 2014.
Yao, D., Zhang, C., Huang, J., and Bi, Serm: recurrent model for next location prediction in semantic trajectories. In Proceedings of the 2017 ACM on Conference on In- formation and Knowledge Management, pp. 2411-2414, 2017.
Yuan, X. and Qiao, Y. Diffusion-ts: Interpretable diffu- sion for general time series generation. In International Conference on Learning Representations, 2024.
Zandbergen, P. A. Ensuring confidentiality of geocoded health data: Assessing geographic masking strategies for leeeel data. Advances in medicine, 2014(1): 567049, 2014.
Zhang, J., Tan, S., Peng, C., Xu, X., Wang, M., Lu, W., Wu, Y., Sai, B., Cai, M., Kummer, A. G., et al. Heterogeneous changes in mobility in response to the sars-cov-2 omicron ba. 2 outbreak in shanghai. Proceedings of the National Academy of Sciences, 20307112220000 2023.
Zheng, Y., Capra, L., Wolfson, O., and Yang, H. Urban computing: concepts, methodologies, and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 5(3):1-55, 2014.
Zhu, Y.. Ye, Y., Zhang, S., Zhao, X., and Yu, J. J. Diff- traj: generating gps trajectory with diffusion probabilistic model. In Proceedings of the 37th International Confer- ence on Neural Information Processing Systems, 2024a.
12

---

ProDiff:: Prolotype-Cuided Diffusion for Minimal Information Trajectory Imputation
A. Detailed Related Work
Spatial-Temporal Sequence Imputation. Imputation methods for spatial-temporal sequences can be broadly divided into two categories: traditional methods and deep learning methods. Traditional methods include linear interpolation (Blu et al., 2004) and mean value filling, which are fast but overly simplistic and struggle to estimate the overall data distribution (Huang et al., 2023). More advanced probabilistic methods, such as probabilistic PCA (Qu et al., 2009) and expectation maximization (Shi et al., 2013), aim to capture the data distribution more accurately. Autoregressive methods like Vector Autoregressive ( (VAR) (Lütkepohl, 2013) and matrix/tensor- based methods (c.g., Tucker decomposition (Tan et al., 2013)) have also been used to address missing data in spatial-temporal contexts.
Deep learning-base based imputation methods can be further divided into non-generative and generative approaches. Non- generative methods primarily rely on RNNs and attention mechanisms. For example, GRU-D (Che et al., 2018) proposes a variant of the gated recurrent unit (GRU) to handle missing data in time series, while TimesNet (Wu et al., 2023) leverages 2D convolutional neural networks to model temporal dependencies. Attention-based methods, such as CDSA (Ma et al., 2019) and SAITS (Du et al., 2023), focus on capturing both short-term and long-term dependencies across multiple dimensions (time, location, measurement). Generative methods include variational autoencoders (VAEs) (Doersch, 2016), generative adversarial networks (GANs) (Goodfellow et al., 2020), and diffusion probabilistic models, which have become increasingly popular. For instance, Diffusion-TS (Yuan & Qiao, 2024) combines diffusion models with time series decomposition to address missing data.
Trajectory Data Mining. Trajectory data mining based on deep learning methods can be categorized into several tasks, including trajectory forecasting, travel time estimation, and anomaly detection (Chen et al., 2024). Trajectory forecasting involves predicting future locations( Wang et al., 2021; Wu et al., 2019) or traffic conditions Wu et al., 2020; Liu et al., 2024; Ji et al., 2023; Jiang et al., 2023a; Ji et al., 2022a). Common approaches include CNN-based models (Bao et al., 2021) and RNN-based models (Yang et al., 2017; Yao et al., 2017), with recent advances exploring diffusion techniques like BCDiff (Li et al., 2023) that bidirectionally refine historical and future trajectories through coupled diffusion models with adaptive gating mechanisms. Travel Time Estimation (TTE) or Estimated Time of Arrival (ETA) involves analyzing trajectory sequences to predict travel time. For example, eRCNN (Wang al., 2016) uses raw GPS data with recurrent convolutional neural network to estimate travel time and speed. Road-based TTE approaches, such as WDR (Wang et al., 2018), model the correlation between trips and roads using regression framework.
Trajectory anomaly detection aims to identify abnormal movement patterns. Offline detection methods, like ATD-RNN (Song et al., 2018), use RNNs with fully connected layers for anomaly detection. Online detection methods leverage reinforcement learning to model the transition probability between road segments, treating anomaly detection as a sequential decision problem (Chen et al., 2024). GM-VSAE (Liu et al., 2020) adapts an RNN-based VAE model to learn the probability distribution in the latent space.
Recent advancements address data incompleteness challenges through unified frameworks, GC-VRNN (Xu et al., 2023) pioneers joint trajectory imputation and prediction using multi-space graph neural networks to capture spatio-temporal missing patterns and temporal decay modules for information recovery. Mobility generation tasks have also gained attention, with models like DiffTraj (Zhu et al., 2024a) utilizing diffusion models to generate synthetic trajectories at the population level. Our proposed task combines trajectory forecasting and mobility generation, where generative trajectory interpolation aligns with mobility generation, and generalized trajectory interpolation is considered a higher-order forecasting task.
Mobility Data Synthesizing. The generation of synthetic mobility data has been extensively studied to address privacy concerns, data scarcity, and high collection costs (Jia et al., 2020; Zhang et al., 2023; Zheng et al., 2014). Early non- generative approaches primarily relied on statistical models (Simini et al., 2021; Wang et al., 2019), perturbation techniques (Zandbergen, 2014), or simulations (Simini et al., 2021). While these methods offer insights into movement dynamics, they often fail to capture complex spatial-temporal relationships in real-world scenarios (Pappalardo et al., 2023).
With advancements in deep learning, generative approaches have gained prominence. Variational Autoencoders (VAEs) like VAE (Chen et al., 2021) leverage temporal dependencies produce realistic trajectories, while GAN-based frameworks such as TS-TrajGen (Jiang et al., 2023b) use coarse-to-fine fine modeling to generate synthetic trajectories from spatial grid transformations. However, these models often face limitations in achieving high-resolution fidelity, particularly when translating grid-based representations into fine-graines data.
Graph-bac based approaches have been widely investigated due to their ability to capture spatial- relationships effectively. For example, RNTrajRec (Chen et al., 2023) employs a graph framework that integrates graph representations of
13

---

ProDiff: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
trajectory points and spatial-temporal transformers model dependencies along the trajectory. significantly enhancing trajectory recovery aceuracy. Similarly, MM-STGED (Wei et al., 2024) utilizes graph-based encoder-decoder structure to represent trajectories spatial-temporal graphs, capturing both micro-level semantics of GPS points and macro-level semantics of shared travel patterns.
Attention-based architectures, such as AttnMove (Xia et al., 2021), leverage attention mechanisms to model spatial-temporal correlations explicitly, facilitating the reconstruction of missing trajectory data and improving performance in downstream applications. Recent innovations in trajectory generation include the use of denoising diffusion probabilistic models (DDPMs) (Ho al., 2020), which iteratively refine noisy inputs to produce high-fidelity synthetic data. For instance, DiffTraj (Zhu al., 2024a) captures ppatial-tmporrll dependencies without relying intermediate transformations, offering significant advantages in privacy preservation and data utility. Additionally, ControlTraj (Zhu et al., 2024b) extends the diffusion framework by integrating conditional signals for controllable generation, improving its applicability across varied scenarios.
B. Detailed Denoising Network
B.1. Denoising Diffusion Probabilistic Model
The diffusion probabilistic model has gained increasing attention in recent years for its success in various data generation tasks. The model consists of forward process that gradually perturbs the data distribution with noise, and reverse (denoising) process that learns reconstrust the original data distribution.
Forward Process. Given set of data samples æ ~ ((zo), the forward process adds T'' time-steps of Gaussian noise N/()) to it, where T is an adjustable parameter. Formally, the forward process can be defined as a Markov chain from data 2g to the latent variable ar:
((11TT (D) II g xz-1)
(16)
( x x1-1)) N(m v B,
(17)
in which { (0,1))/11 B2
BT) the corresponding variance schedule. Since it is impractical
back-propagate the gradient by sampling from Gaussian distribution, adopt parameterization trick to keep the gradient derivable and the æ, can be expressed æ, vā,zo vI â,e, where (0, and ā II (1 B.).
Reverse Process. The reverse diffusion process, also known as the denoising processing, aims to reconstruct the original data distribution from the noisy data 2т ~ (0, I). Accordingly, this process can be formulated by the following Markov chain:
po (o( p((r)( II Po po (x--1 xx))
(18)
Po (= xx.) N' (o t), o (xx,
(19)
where 14g (2g(2),))) () and (ate, () the mean and variance parameterized by 0, respectively. Based on the literature, for any 3, 1-Ge-1 (t > 1) and B1 3r, the parameterizations of My and or are defined by: T-a.
1 1( Be
(g 1) Va, v1 at
c(2r11)
3 00 () =
(20)
14

---

ProDiff:: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
C. Method
Algorithm 1 Training of ProDiff
for i == .,2.....00 do
Get base condition B
Get prototype condition P by PCE network
Get W W, W
((P)) by Wide & Deep network Get conditional guidance J WD(B") PD)
(Zo) = =
Sample Z ~ p where p represents the distribution of original data Sample ~ 2110, T], (N, lxxa)
Z Z vI- dyC
Updating the gradient VafnC. which means optimizing Ex-eco, Br Boo (V/yylle =o(Ze, L, S (o))
end for
Algorithm Sampling ProDiff
1: Get data and Sample Żr ~ (0,
2: Get base condition B
3: Get prototype condition p by PCE network
4: Get W WD(B") WD(")) by Wide & Deep network
5: Get conditional guidance -== WDB") (DP)))
6: for t= == T.T
s..... do Zr, Jc) according to (20)
7: Compute μs
8: Compute po
Z Z,, Jo) according to (19)
9: end for
10: Return: Zo
D. Experiment
D.1. Dataset
We evaluate the performance of ProDiff and baselines methods on two datasets, WuXi and FourSquare.
The mobile phone dataset WuXi used in this study were collected between October 24, 2013, and March 24, 2014, in evenly distributed across the area. Every hour, these users generate around 40 million raw records, each containing essential location information, including cell-id and area-id, which correspond to specific cell towers. Each record in the dataset includes four key components: user ID, cell tower ID, timestamp, and a tag. The timestamp indicates the exact moment the record was created, while the tag specifies the type of activity associated with the record. For the purpose of this study, we focused on data from ten consecutive days, concatenating individual trajectories during this period. This subset includes 33000 active users and 671,124 location updates, of which 30,000 users are used for training and 3,000 users for testing.
Wuxi, China, encompassing approximately six million
The FourSquare dataset contains Foursquare check-ins over ten months (from April 12, 2012, to February 16, 2013), filtered for noise and invalid check-ins. It includes active users in two major cities, New York and Tokyo, with each check-in associated with a timestamp, GPS coordinates, and semantic meaning. We did not use the taxi-related dataset because human trajectories have a higher degree of freedom compared to car trajectories. Due to the volume of data, only Tokyo data was used on the FourSquare dataset. Tab. summarizes the statistical information of these two datasets, which includes 2,293 active users with 573,703 location updates.
D.2. Preprocess
In trajectory data analysis, careful preparation of raw data is fundamental to ensure the reliability and precision of computational models. Our preprocessing approach transforms raw GPS coordinates into a format optimized for training
15

---

ProDiff:: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
Table 6. Statistics of human mobility datasets.
Dataset
WuXi
FourSquare
Time Span (day)
111
310
Used Time Span (day)
10
310
Train Active Users
30000
1834
Test Active Users
3000
459
Location Updates
671,124
573,703
Average Distance (meter)
3336.33
4301,51
Average Time (hour)
7.8
37.15
deep learning systems, focusing on two key steps: segmentation and normalization.
Segmentation involves dividing continuous trajectory data into fixed-length segments using a sliding window method. This technique incrementally generates samples from single trajectory. Trajectories matching the target length are directly included as individual samples, while longer paths are systematically partitioned into uniform segments. This creates discrete, standardized inputs for model training.
Normalization adapts the data for diffusion-based models, which rely on introducing and removing Gaussian noise during training. To align with the noise distribution, spatial coordinates are scaled to a dimensionless, standardized range (e.g.. [0, II.. This eliminates scale variations between features, allowing the model to focus on spatial patterns rather than magnitude differences. Crucially, the process is fully reversible after model inference, outputs can be rescaled their original geographic coordinates, preserving real-world interpretability.
D.3. Evaluation Metric and Baseline
The trajectory imputation task aims fill in missing points as accurately as possible under the given point conditions. To assess performance, propose novel trajectory coverage metric, measuring the percentage of generated locations within specified distance from the groundtruth. Given threshold т, we count the number of generated points within distance from the groundtruth and divide by the total length of the trajectory to limit it to the [0, 1] interval. For any trajectory
S = [St.1, & of length k, we construct a masked trajectory S = [st.1, Sy,k). Given this condition and threshold
T, ProDiff generates the missing points, and we calculate the trajectory coverage TC&r as the following equation:
TC
I(d(s)). < <T,,
(21)
where si, is the generated points from ProDiff, and I[(-) is an indicator function that equals when d(si,; ) is less than the threshold 7 and otherwise. We use the haversine function as the distance metric, which calculates the great-cirele distance between two points on the Earth's 's surface, accurately reflecting the true distance by converting latitude and longitude into radians.
We select traditional methods and the current state-of-the-art spatio-temporal sequence methods based the Diffusion model, as well as trajectory-related methods to realize the trajectory imputation task. The compared baselines are set as follows:
VAR: Vector Autoregression (VAR) is a traditional model used to capture the linear interdependencies among multiple time series data. By considering each variable's own lagged values and the lagged values of other variables in the system, VAR models can effectively analyze the dynamic relationships and forecast future movements of the variables (Lütkepohl, 2005).
SAITS: SAITS is an advanced model(Du al., 2023) designed to handling missing data in time series analysis. By
leveraging self-attention mechanisms, SAITS aims to capture both short-term and long-term dependencies within time series data, This model stands out due to its ability to focus on the most relevant parts of the input data.
TimesNet: TimesNet a progressive model (Wu et al., 2023) which treats time series data as 2D tensors, allowing it to leverage powerful 2D convolutional neural networks to model temporal dependencies. This approach is suitable for a wide range of applications, including missing value handling, forecasting, and anomaly detection.
16

---

ProDiff:: Proiotype-Cuided Diffusion for Minimal Information Trajectory Imputation
Diffusion-TS: A current SOTA method (Yuan & Qiao, 2024) for time series generation task based on diffusion model and it also applies missing value processing tasks. Diffusion-TSS decomposes time series into interpretable variables, combining seasonal trend decomposition techniques and denoising diffusion models.
Generating GPS Trajectory with Diffusion Probabilistic Model is a SOTA model(Zhu et al., 2024a) designed for generating realistic GPS trajectories. Dif progressively refines random noise into coherent and plausible GPS trajectory data through a series probabilistic steps. It is worth noting that while DiffTraj can also be used for the trajectory imputation task, generates trajectories at the population level, which is fundamentally different from what we have done at the individual level.
DiffTraj:
We further evaluated our model against external baselines and metrics. Specifically, we incorporated RNTrajRec(Chen et al., 2023), ISSTraaGGen(Jaang et al., 2023b), MM-STGED(Wei et al., 2024), and AttnMove(Xia et al., 2021) baseline models:
RNerajRec: RNTrajReccChen et al., 2023) employs a graph-based framework that integrates graph representations of trajectory points and trajectory recovery accuracy.
transformers to model dependencies along the trajectory, significantly enhancing
TSaaaanGe et al., 2023b) proposes a hierarchical generation framework that employs coarse-to-fine modeling to synthesize realistic trajectories. It first learns spatial grid-based latent representations to capture macroscopic movement patterns, then refines trajectories through adaptive spatial transformations and temporal interpolation. This approach effectively addresses the sparsity of raw GPS data while preserving topological consistency with road networks.
TS-TrajGenn
MM-STGED: MMM-STGED(Wei et al., 2024) utilizes a graph-based encoder-decoder structure to represent trajectories as spatial-temporal graphs, capturing micro-level semantics of GPS points and macro-level semanties of shared travel patterns.
AttnMove: AttnMove(Xia al., 2021), leverage attention mechanisms to model spatial-temporal correlations explicitly, facilitating the reconstruction of missing trajectory data and improving performance in downstream applications.
To ensure fair comparisons, specific modules in these baselines were removed to avoid reliance on unavailable additional information from our datasets. Additionally, we introduced extra metrics to assess the spatial distribution of generated trajectories:
Density: Measures the cosine similarity of grid density between real and generated trajectories (higher is better).
Distance: Evaluates the difference in travel distance between real and generated data, calculated as the sum of distances between consecutive points (lower is better).
Segment Distance: Assesses the difference in segment distance between real and generated data, defined the distance between consecutive points (lower is better).
Radius: Evaluates the root mean square distance of all activity locations from the central location, indicating the spatial range (lower is better).
MAE: Mean absolute error, measuring the average magnitude of errors between real and generated trajectories (lower is better).
RMSE: Root mean square error, evaluating the square root of the average squared differences between predicted and actual values (lower better).
D.4. Exploratory Study
To assess ProDiff's performance under varying information conditions, we conducted two additional sets of experiments for the trajectory imputation task. Specifically, given a trajectory length of 10, in addition fixing the begin and end points, supplementary information points were added to guide the model to accomplish better generation, as shown in the first four rows of Tab. 8. Meanwhile, motivated by the conclusion in the literature (De Montjoye al., 2013) (that 95% of the personnel's 's trajectories can be determined by arbitrarily giving 4 points), we modify the information of the fixed points to randomly selecting x points during both training and testing. This scenario, represented in the last four rows of Tab. 8, is more challenging since the selected points vary and thus introduce more complexity. From the results of whole table, some key findings can be obtained: (i) Impact of Increased Information: The results show a significant improvement in trajectory imputation when the number of given points increases from 2 to 4. Beyond four points, the enhancement in performance
17

---

ProDiff: Prototype-Cuided Diffusion for Minimal Information Trajectory Imputation
becomes marginal. (ii) Fixed Random Points: When fixing four points, our method's performance aligns closely with the findings of (De Montjoye al., 2013). However, when points selected randomly, the model's performance diverges more noticeably from the literature's s conclusion. This discrepancy likely arises because random points disrupt the consistency of trajectory sampling, increasing the difficulty of model learning. The results highlight the potential of ProDiff in accurately imputing missing trajectory points with a sufficient number of fixed reference points. However, the challenge remains when dealing with randomly selected points, indicating an area for future improvement.
Table 7. Impact of different diffusion steps (d).
d
TC@2K 2k
TC@4k
TC@66
TC@8K
TC@ 10k
100
0.5750
0.7445
0.8329
0.8853
0.9187
300
0.6015
0.7697
0.8524
0.9005
0.9300
500
0.5978
0.7686
0.8515
0.8992
0.9285
700
0.5881
0.7551
0.8399
0.8897
0.9216
Table Comparison of the performance of fixed and randomized trajectory points with different amount of information. "3/10" means that given a trajectory of length 10, three points are provided at indices [0, 4, 9]. Similarly, "4/10" provides points at indices [0, 3, 6, 91, "5/10" at indices [0, 4, 6, 9]. represents random selecting experiments.
Info
TC@2k
TC@ 4k
TC@6k
TC@8K 8k
TC@ 10k
2/10
0.4996
0.6994
0.8048
0.8667
0.9053
3/10
0.5865
0.7638
0.8498
0.8990
0.9292
4/10
0.6820
0.8305
0.8979
0.9347
0.9561
5/10
0.7362
0.8637
0.9179
0.9466
0.9633
2/10
0,4143
0.6282
0.7402
0.7996
0,8351
3/10
0.5364
0.7098
0.7897
0,8363
0.8663
4/10
0.6051
0.7501
0.8269
0.8738
0.9047
5/10*
0.6817
0.8062
0.8706
0,9089
0.9336
D.5. Ablation Study
Diffusion models typically involve higher computational costs, which may potentially limit their application large-scale trajectory data scenarios. tackle the efficiency issue, we have developed two variants that integrate DDIM sampling (ProDDIM) (Song et al., 2020) and LA (PrnDDIM+Linear Attention) (Katharopoulos et al., 2020), respectively.
We carried out experiments the WuXi dataset with k=8. As presented in Tab. 9, both variants achieve at least approximately 10x speed-up compared to ProDDPM, while only experiencing minor performance reductions. These findings indicate that our proposed model serves as a general framework. It can be effectively combined with various acceleration techniques, thereby facilitating its deployment in real-world applications and addressing the computational efficiency concerns associated with diffusion models the context of large-scale trajectory data.
Table 9. Accelerated verisons the ProDiff model (Thpt: Throughput; PPT: Processing Per Time-unit)
Method
TC@4k TC@2k
TC@6k
TC@
TC@ 10k
Thpt(s/sample)
PPT(sample/s)
ProDDPM (Ours)
0.5752
0.7501
0.8236
0.8663
0.8945
77.9346
0.0128
ProDDIM(Ours)
0.5430
0.7131
0.7773
0.8303
0.8741
788.6852
0.0013
ProDDIM+LA(Ous)
0.5350
0.7197
0.7725
0.836
0.8785
768.5845
0.0013
18


Reviews:
[{"review_id": "JMwmw61Uyg", "reviewer": "Reviewer_8Fbd", "summary": "In this work, the authors design ProDiff, a diffusion-based model for spatial data imputation. The research direction is interesting and the problem is practical, given various noises of real-world data. ProDiff consists of two components, prototype learning and a denoising diffusion probabilistic model. With minimal information as input, the proposed method achieved good performance. Experiments on two real-world datasets demonstrate the practical effectiveness of ProDiff compared to existing methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: In the first paragraph, there are probably more primary sources of location data.**\n\nThank you for pointing this out. We agree that our original manuscript could more comprehensively reflect the sources of trajectory data. In the revised manuscript, we will clarify this by explicitly adding other satellite systems (e.g., GLONASS from Russia, BeiDou from China, QZSS from Japan, and Galileo from Europe), and IP-based localization used by online platforms.\n\nThe *updated first paragraph* will read:\n\n\"Mining spatio-temporal patterns from trajectory data has broad applications in infectious disease control, human behavioral analysis, and urban planning. Such data primarily originate from Location-Based Services (LBS) using cell tower signals, satellite-based systems such as GPS, GLONASS, BeiDou, QZSS, and Galileo, as well as IP-based location methods utilized by online platforms.\"\n\n\n**W2: The introduction is a bit of confusing, such as lines 64 to 68.**\n\nThank you for the comment. We agree that lines 64–68 could have been expressed more clearly. The intention was to highlight the difference between our method and prior works, but we recognize that this discussion is somewhat misplaced here. In the revised manuscript, we will refine the entire introduction to improve clarity, reorganizing the content and explicitly positioning our approach relative to existing methods in a more appropriate context.\n\n\n**W3: Clarify whether the diffusion backbone is a standard design or includes specific modifications.**\n\nThank you for highlighting this. As noted, our diffusion backbone adopts a widely used architecture in the field which includes 1D U-Net with ResNet blocks and self-attention layers due to its strong performance in sequence modeling. This design aligns with established diffusion model practices.\n\nHowever, our key innovation lies in the *conditioning network and mechanism*. While prior works often use simple concatenation or shallow fusion for conditional inputs, we propose a modified Wide & Deep network that explicitly models the interaction between trajectory prototypes and conditioning signals. Specifically, We add more deep branch which is composed of multiple linear & non-linear layers that are designed to extract high-level representations from matched prototype embeddings, enabling the model to better capture trajectory patterns.  This design allows for both memorization and generalization, making the conditioning more expressive and adaptive.\n\nThis integration is unique to our model and enables the diffusion process to simultaneously leverage both the base conditions and learned trajectory prototypes in a more structured and effective way. We will revise the manuscript to make these design choices and their motivations clearer.\n\n\n**W4: For experiments, is there specific pre-processing of the training data? Since the authors mention the goal is imputing trajectories with fewer constraints, the reader assumes the generation setup is more challenging than previous works.**\n\nWe appreciate your question regarding preprocessing. Besides standard preprocessing (trajectory segmentation and min-max normalization), we adopt a more challenging setup: only endpoints are given as inputs, and Gaussian noise is added to intermediate points.\n\nCompared to prior methods that often use intermediate positions or extra features (e.g., speed, direction), our setting provides far less information, making the task more difficult and unconstrained. \n\nWe will clarify this minimal-input design in the revision to better highlight the uniqueness and robustness of our approach.\n\n\n**W5: The realism of the generated trajectories in Fig. 5a appear less convincing compared to those in Fig. 5b and 5c.**\n\nThank you for appreciating Fig 5b and 5c and for the thoughtful comment on Fig. 5a. To quantify these differences clearly, we computed batch-level statistics:\n\n- Mean Latitude Difference: 0.0064\n- Mean Longitude Difference: -0.0079\n- MAE Latitude: 0.0333\n- MAE Longitude: 0.0381\n\nOur batch-level statistics show that the differences between the generated and ground-truth data are minimal (~0.03–0.04°), but because we aggregate the data into grid cells with a *very fine* spatial resolution of *0.009°*, even these minute discrepancies are noticeably amplified in the visualization.\n\nFig. 5a aims to visually illustrate alignment between generated and actual flow distributions. Figures 5a–c collectively provide complementary perspectives: spatial visualization (Fig. 5a), correlation analysis (Fig. 5b), and distributional alignment (Fig. 5c) to demonstrate that our model effectively captures realistic trajectory patterns. We will refine Fig. 5a and clarify its intent to avoid confusion in the revision.", "claims_and_evidence": "claims are clear", "methods_and_evaluation_criteria": "Yes, the methods make sense", "theoretical_claims": "yes", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "Spatial data imputation, this direction could have broad impact in the research community such as urban science.", "essential_references_not_discussed": "References are good", "other_strengths_and_weaknesses": "1.In the first paragraph, there are probably more primary sources of location data. Such as other satellite systems from Russia, CHina, Japan, etc. Also, lots of online platforms utilize IP-based locations. \n\n2.The introduction is a bit of confusing, such as lines 64 to 68. \n\n3.From Fig 2, it seems the diffusion base model is very similar to existing models. Maybe some clarifications about this is beneficial, e.g., is this adapted from other works or this is a typical design choice for diffusion models. \n\n4. For experiments, is there specific pre-processing of the training data? Since the authors mention the goal is imputing trajectories with fewer constraints, the reader assumes the generation setup is more challenging than previous works. \n\n5. I like the visualization of Fig. 5 a. However, it is hard to tell how realistic the generated results are. Actually, they look quite different. Fig 5 b,c are much better.", "other_comments_or_suggestions": "no", "questions_for_authors": "no", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UrNagwP32A", "reviewer": "Reviewer_NUSr", "summary": "This paper studied the task of trajectory imputation and propose ProDiff as a trajectory imputation framework that uses only two endpoints as minimal information, in order to improve previous approaches which place significant demands on data acquisition and overlook the potential of large-scale human trajectory embeddings. The experiments on FourSquare and WuXi show the proposed approach outperforms state-of-the-art methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1：The reviewer suggested discussing how the proposed method could better leverage intermediate trajectory points when available, as they may provide valuable information for imputation beyond using only endpoints.**\n\n\n\nThank you for this insightful comment. We fully agree that leveraging intermediate trajectory points, when available, can significantly enhance trajectory imputation performance.\n\nAlthough ProDiff was initially designed to operate under minimal-information conditions (using only endpoints), it can seamlessly incorporate additional intermediate points. To illustrate this capability, we conducted supplementary experiments comparing scenarios with varying amounts of intermediate trajectory points.\n\nThe results (the first four rows of Tab. 1.) show performance improvements as additional fixed intermediate points are provided. Specifically, we observed significant accuracy gains as the number of known trajectory points increased from two endpoints (2/10) to five points (5/10). This clearly demonstrates the beneficial effect of integrating intermediate trajectory points. Notably, incremental performance gains became marginal beyond four points, suggesting that once essential trajectory patterns are sufficiently captured, further intermediate points provide diminishing returns.\n\n\n\n**Tab. 1. Comparison of the performance of fixed and randomized trajectory points with different amount of information.** \n\n| Fixed Points          | TC@2k  | TC@4k  | TC@6k  | TC@8k  | TC@10k |\n| --------------------- | ------ | ------ | ------ | ------ | ------ |\n| 2/10                  | 0.4996 | 0.6994 | 0.8048 | 0.8667 | 0.9053 |\n| 3/10                  | 0.5865 | 0.7638 | 0.8498 | 0.8990 | 0.9292 |\n| 4/10                  | 0.6820 | 0.8305 | 0.8979 | 0.9347 | 0.9561 |\n| 5/10                  | 0.7362 | 0.8637 | 0.9179 | 0.9466 | 0.9633 |\n| **Randomized Points** |        |        |        |        |        |\n| 2/10†                 | 0.4143 | 0.6282 | 0.7402 | 0.7996 | 0.8351 |\n| 3/10†                 | 0.5364 | 0.7098 | 0.7897 | 0.8363 | 0.8663 |\n| 4/10†                 | 0.6051 | 0.7501 | 0.8269 | 0.8738 | 0.9047 |\n| 5/10†                 | 0.6817 | 0.8062 | 0.8706 | 0.9089 | 0.9336 |\n\n\n\nAdditionally, we explored scenarios where intermediate points were randomly selected each time (indicated by †), creating a more challenging environment as the points varied across instances, as shown in the last four rows of Tab. 1. This approach aimed to verify the conclusion from existing literature [1], which suggests that four randomly selected points can determine 95% of the trajectory. However, when points are selected randomly, the model’s performance diverges more noticeably from the literature’s conclusion. This discrepancy likely arises because random points disrupt the consistency of trajectory sampling, increasing the difficulty of model learning. The results highlight the potential of ProDiff in accurately imputing missing trajectory points with a sufficient number of fixed reference points, while also remains when dealing with randomly selected points, indicating an area for future improvement.\n\n\n\n[1]Unique in the crowd: The privacy bounds of human mobility.", "claims_and_evidence": "The claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense for the problem.", "theoretical_claims": "The proofs for theoretical claims are correct.", "experimental_designs_or_analyses": "The experimental designs and ayalyses are comprehsnive and soundness for me.", "relation_to_broader_scientific_literature": "The authors suggest that the trajectory imputation task can benefit in infectious diseases control, human behavior alanalysis, and urban planning.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is well written. The claims in this paper are well supported, implementations details are clearly discussed and the experiments are comprehensive. \n\nI suggest there is room for improvement in better leveraging the intermediate trajectory points when they are available. If these points are not affected by noise interference, they can deliver effective information for trajectory imputation. I agree that using the end points are able to  solve this probelm, but I also appreciate a discussion about how the proposed approach may leverge the intermediate trajectory points.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uLcIh7O8jC", "reviewer": "Reviewer_xUz8", "summary": "The paper proposes ProDiff, a prototype-guided diffusion model for trajectory imputation using only two endpoints as minimal information. It integrates prototype learning to embed human movement patterns and employs a denoising diffusion probabilistic model to reconstruct missing spatiotemporal data. A joint loss function ensures effective training. Experiments on WuXi and FourSquare datasets show that ProDiff outperforms state-of-the-art methods, with a 6.28% improvement in accuracy on FourSquare and 2.52% on WuXi. Additionally, a 0.927 correlation between generated and real trajectories suggests high fidelity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1**: Thank you for your insightful comment. We agree the original lacked theoretical grounding and now present a concise framework supporting prototype-based modeling of macro-level human movement.\n\n### Theoretical Justification\n\nPrototype learning combines clustering and contrastive learning. Formally, for data points $X=\\{x_1,...,x_n\\}$, the embedding function $f: \\mathbb{R}^d \\rightarrow \\mathbb{R}^m$, and prototypes $\\{p_1,...,p_K\\}$ are optimized by:\n$$\n\\min_{f,\\{p_k\\}}\\sum_{i=1}^n\\Vert f(x_i)-p_{y_i}\\Vert ^2+\\lambda\\ell_{\\mathrm{contrast}}(f(x_i),p_{y_i},\\{p_k\\}),\n$$\n\n**Assumptions**\n1. **Mixture of Distributions**: Human trajectory data is drawn from a mixture of distributions, each localized on a manifold region $\\mathcal{M}$ with mean $\\mu_k$.\n2. **Expressive Embeddings**: The embedding $f$ enables diverse prototypes that capture local tangents and reconstruct manifold structures via linear combinations [1].\n\n**Main Theorem**\n\nUnder these assumptions, any global optimum $(f^*, \\{p_k^*\\})$ satisfies:\n1. Prototypes approximate conditional expectations: $p_k^* \\approx \\mathbb{E}\\left[f^*(x) | x \\in C_k\\right].$ \n2. Contrastive loss enforces prototype separation, forming diverse directional vectors:  $\\langle p_i^*, p_j^* \\rangle \\leq \\epsilon$, for $i\\neq j$.\n\n**Proof Sketch**\n\nUsing Pollard's consistency theorem [2], the empirical cluster centers converge to conditional expectations:\n$$\np_k^* \\approx \\mathbb{E}\\left[f^*(x) | x \\in C_k\\right]\n$$\nFrom InfoNCE-based contrastive loss [3], optimality conditions ensure prototype distinctiveness:\n$$\nf^*(x)^\\top p_y^* - f^*(x)^\\top p_k^* \\ge \\delta,k\\neq y.\n$$\nwhere $ \\delta>0$ . Since the clustering term already guarantees that $p_y^* \\approx \\mathbb{E}\\left[f^*(x) \\mid x\\in C_y\\right]$, averaging over cluster $C_y$ gives:\n$$\n\\langle p_y^*, p_y^* \\rangle - \\langle p_y^*, p_k^* \\rangle \\ge \\delta.\n$$\nshifting the terms leads to the observation:\n$$\n\\langle p_y^*, p_k^* \\rangle \\le \\Vert p_y^*\\Vert^2 - \\delta \\le \\epsilon, k\\neq y\n$$\nwhich indicates that contrastive loss forces prototypes into globally distinct directions, ensuring effective representation of manifold local structures.\n\n### Empirical Validation\n\nWe validate these properties on real data:\n- Mean cosine similarity (prototypes vs. empirical means): 0.9417\n- Avg. inter-prototype angle: 84.63°\n- Avg. off-diagonal cosine similarity: 0.0915\n\nThese results support the theoretical properties. Further visualizations are provided at https://anonymous.4open.science/r/ICML_rebuttal-5296/.\n\nWe will incorporate these theoretical and empirical insights into the revised manuscript.\n\n**W2**：We appreciate the reviewer’s feedback and apologize for overlooking references [4-6]. We carefully reviewed [4–6] that propose unified frameworks for imputation, bidirectional diffusion, and partial observation handling,  and re-implement [4] (GC-VRNN) and [5] (BCDiff) on the WuXi dataset for direct comparison (Table below, more results at https://anonymous.4open.science/r/ICML_rebuttal-5296/). \n\nOur ProDDPM outperforms both, as it is specifically designed for human trajectory imputation, whereas GC-VRNN is designed for visual multi-agent settings and BCDiff is less aligned with our task.\n\nWe will include a detailed discussion of these baselines in the revised manuscript.\n|Method|TC@2k|TC@6k|TC@10k|Time (sample/s)| Speed (s/sample)|\n|-|-|-|-|-|-|\n|GC-VRNN|0.438|0.662|0.771|7404.35|0.0001|\n|BCDiff|0.561|0.787|0.871|41.13|0.0243|\n|ProDDPM|0.575|0.824|0.895|77.93|0.0128|\n|ProDDIM|0.543|0.777|0.874|788.68|0.0013|\n|ProDDIM+LA|0.535|0.773|0.879|768.58|0.0013|\n\n**W3**: Thank you for raising this important point. we acknowledge that diffusion models generally incur higher computational costs compared to alternatives like GC-VRNN, which is faster yet significantly less accurate (GC-VRNN TC@10k=0.771 vs. ProDDPM TC@10k=0.895).\n\nTo address efficiency concerns, we developed two variants that incorporate DDIM sampling (ProDDIM) and LA (ProDDIM+LA), and achieve ~10× speed-up over ProDDPM, with only minor performance reductions. These results demonstrate the practicality of ProDDIM for large-scale applications when paired with proper acceleration.\n\nWe apologize for any confusion regarding anonymization and emphasize that this was an accidental mistake rather than an intentional breach of anonymity or policy violation. Upon noticing your comment, we immediately corrected the anonymized repository to eliminate your concern and prevent further misunderstandings.\n\nWe hope these updates clarify the novelty and practical value of our work and respectfully invite you to reconsider the evaluation.\n\n[1] Roweis & Saul, Locally Linear Embedding. [2] Pollard, Strong Consistency of k-means. [3] Saunshi et al., Theory of Contrastive Learning. [4] GC-VRNN: Unified Framework for Trajectory Imputation. [5] BCDiff: Bidirectional Diffusion for Trajectory Prediction. [6] Improving driving safety with POP: Accurate partially observed trajectory prediction.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "Good", "essential_references_not_discussed": "They miss some reference in trajectory imputation.\nFor example, [1] and [2]\n\n[1] Uncovering the Missing Pattern: Unified Framework Towards Trajectory Imputation and Prediction\n[2] BCDiff: Bidirectional Consistent Diffusion for Instantaneous Trajectory Prediction\n[3] Improving autonomous driving safety with pop: A framework for accurate partially observed trajectory predictions\nThe author should discuss them.", "other_strengths_and_weaknesses": "Strengths:\nThe combination of prototype learning and diffusion models is novel for trajectory imputation.\n\nComprehensive comparisons against state-of-the-art time-series interpolation and trajectory-specific models demonstrate consistent superiority across various trajectory window sizes.\n\nWeaknesses\n1. The paper assumes that learned prototypes can capture macro-level human movement patterns, but there is no strong theoretical justification for their optimality beyond empirical evidence.\n2. They miss some reference in trajectory imputation.\nFor example, [1] and [2]\n\n[1] Uncovering the Missing Pattern: Unified Framework Towards Trajectory Imputation and Prediction\n[2] BCDiff: Bidirectional Consistent Diffusion for Instantaneous Trajectory Prediction\n[3] Improving autonomous driving safety with pop: A framework for accurate partially observed trajectory predictions\nThe author should discuss them.\n\n3. Diffusion models can be computationally expensive, and there is limited discussion on efficiency in large-scale real-time applications.", "other_comments_or_suggestions": "none", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Research Integrity Issues (e.g., plagiarism)"]}}]

Author rebuttal:

Meta-review: All reviewers are positive about the paper. The combination of prototype learning and diffusion models is well received as a valid approach to address the trajectory imputation task. The authors provide comprehensive comparisons against state-of-the-art time-series interpolation and trajectory-specific models. They also did a good job during the rebuttal in addressing the reviewers’ questions. 
The ACs echo the reviewers' comments and recommend including the added theoretical analysis and new experiments (e.g., comparisons with GC-VRNN, BCDiff, and ProDDIM/ProDDIM+LA) and the final camera-ready version.
Decision: Accept (poster)