ProDiff: Prototype-Guided Diffusion for Minimal Information Trajectory Imputation

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.

Theoretical Justification

Prototype 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:

$$\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\}),$$

Assumptions

1. 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$.
2. Expressive Embeddings: The embedding $f$ enables diverse prototypes that capture local tangents and reconstruct manifold structures via linear combinations [1].

Main Theorem

Under these assumptions, any global optimum $(f^*, \{p_k^*\})$ satisfies:

1. Prototypes approximate conditional expectations: $p_k^* \approx \mathbb{E}\left[f^*(x) | x \in C_k\right].$
2. Contrastive loss enforces prototype separation, forming diverse directional vectors: $\langle p_i^*, p_j^* \rangle \leq \epsilon$, for $i\neq j$.

Proof Sketch

Using Pollard's consistency theorem [2], the empirical cluster centers converge to conditional expectations:

$$p_k^* \approx \mathbb{E}\left[f^*(x) | x \in C_k\right]$$

From InfoNCE-based contrastive loss [3], optimality conditions ensure prototype distinctiveness:

$$f^*(x)^\top p_y^* - f^*(x)^\top p_k^* \ge \delta,k\neq y.$$

where $\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:

$$\langle p_y^*, p_y^* \rangle - \langle p_y^*, p_k^* \rangle \ge \delta.$$

shifting the terms leads to the observation:

$$\langle p_y^*, p_k^* \rangle \le \Vert p_y^*\Vert^2 - \delta \le \epsilon, k\neq y$$

which indicates that contrastive loss forces prototypes into globally distinct directions, ensuring effective representation of manifold local structures.

Empirical Validation

We validate these properties on real data:

• Mean cosine similarity (prototypes vs. empirical means): 0.9417
• Avg. inter-prototype angle: 84.63°
• Avg. off-diagonal cosine similarity: 0.0915

These results support the theoretical properties. Further visualizations are provided at https://anonymous.4open.science/r/ICML_rebuttal-5296/.

We will incorporate these theoretical and empirical insights into the revised manuscript.

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/).

Our 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.

We will include a detailed discussion of these baselines in the revised manuscript.

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).

To 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.

We 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.

We hope these updates clarify the novelty and practical value of our work and respectfully invite you to reconsider the evaluation.

[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.

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.

Thank you for this insightful comment. We fully agree that leveraging intermediate trajectory points, when available, can significantly enhance trajectory imputation performance.

Although 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.

The 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.

Tab. 1. Comparison of the performance of fixed and randomized trajectory points with different amount of information.

Additionally, 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.

[1]Unique in the crowd: The privacy bounds of human mobility.

W1: In the first paragraph, there are probably more primary sources of location data.

Thank 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.

The updated first paragraph will read:

"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."

W2: The introduction is a bit of confusing, such as lines 64 to 68.

Thank 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.

W3: Clarify whether the diffusion backbone is a standard design or includes specific modifications.

Thank 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.

However, 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.

This 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.

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.

We 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.

Compared 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.

We will clarify this minimal-input design in the revision to better highlight the uniqueness and robustness of our approach.

W5: The realism of the generated trajectories in Fig. 5a appear less convincing compared to those in Fig. 5b and 5c.

Thank 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:

• Mean Latitude Difference: 0.0064
• Mean Longitude Difference: -0.0079
• MAE Latitude: 0.0333
• MAE Longitude: 0.0381

Our 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.

Fig. 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.