Scalable Trajectory-User Linking with Dual-Stream Representation Networks

Hao Zhang, Wei Chen, Xingyu Zhao, Jianpeng Qi, Guiyuan Jiang, Yanwei YuAAAI 2025 · DOI

TL;DR

This paper introduces ScaleTUL, a novel deep learning framework for scalable trajectory-user linking (TUL). By employing a dual-stream representation network with spatio-temporal augmentations, ScaleTUL effectively captures complex mobility patterns and addresses the limitations of existing methods in handling large-scale datasets.

What Problem Does This Paper Address?

The core problem this paper tackles is scalable trajectory-user linking (TUL). TUL aims to identify the individual who generated an anonymous trajectory, which has applications in personalized recommendations, behavior analysis, and security. Existing TUL methods, while showing promise, struggle with two major limitations:

  1. Scalability: Most current deep learning approaches are designed for hundreds of users and are formulated as multi-class classification problems. This becomes inefficient and performance-degrading when dealing with real-world scenarios involving millions of users and trajectories.
  2. Representation Learning: Traditional methods often overlook the inherent irregularities and diverse spatio-temporal dependencies within trajectories, especially when dealing with sparse or noisy data. This leads to suboptimal representations that fail to capture nuanced user behavior.

Methods

ScaleTUL introduces a novel approach to address these challenges through a two-stage training pipeline:

  1. Spatio-Temporal Augmentation Strategy: To combat data sparsity and capture diverse mobility patterns, ScaleTUL employs two augmentation techniques:
  2. Temporal Augmentation: Introduces trajectories with different time granularities (e.g., weekly, bi-weekly) to capture periodic user visitation preferences.
  3. Spatial Augmentation: Applies random location masking to simulate irregular mobility patterns and missing data, enhancing model robustness.
  4. Dual-Stream Trajectory Encoder: This component is designed to learn unified trajectory representations by fusing different temporal-spatial dependencies. It consists of:
  5. Unified Embedding Layer: Integrates geographic, temporal, and semantic information of each check-in location into a unified representation.
  6. Short-Term Encoder: A Bi-directional LSTM variant captures short-term movement patterns.
  7. Long-Term Encoder: A structured state space model (SSM) captures long-term spatio-temporal dependencies, leveraging its hardware-aware efficiency.
  8. A learnable parameter balances the outputs of the short-term and long-term encoders.
  9. Representation Alignment Module: This module utilizes a supervised contrastive learning framework (an extension of InfoNCE) to align trajectory representations. By leveraging available user labels, it encourages representations of the same user's trajectories to be closer in the latent space while pushing apart those of different users.
  10. Trajectory-User Linking Layer: A final projection layer further enhances trajectory representations, and a cosine similarity loss is used to link trajectories to their corresponding users. This approach is chosen over traditional cross-entropy loss for better scalability.

Datasets

The paper evaluates ScaleTUL on real-world check-in mobility datasets from:

  • Three Cities: Tokyo (TKY), New York City (NYC), and Santiago.
  • Nationwide U.S. Dataset: Covering a large geographical area.

For these datasets, the authors select varying numbers of top users (400, 800, 5000, and 10000) to demonstrate scalability. The data is split into 80% for training and 20% for testing, with 20% of the training data reserved for validation.

Key Insights and Ideas

  • Augmentation is Crucial for Irregular Data: The spatio-temporal augmentation strategy is vital for handling the inherent sparsity and irregularity of real-world trajectory data, significantly improving model generalization.
  • Dual-Stream Encoding Captures Multi-Scale Patterns: Combining short-term (LSTM) and long-term (SSM) encoders effectively captures diverse spatio-temporal dependencies, which is essential for accurate trajectory representation.
  • Supervised Contrastive Learning for Better Alignment: Leveraging user labels within a contrastive learning framework leads to more discriminative trajectory representations than purely unsupervised methods, reducing misclassifications.
  • Cosine Similarity for Scalable Linking: Using cosine similarity loss in the final linking stage is a more scalable approach for large numbers of users compared to traditional classification losses.
  • SSMs Offer Efficiency for Long-Term Dependencies: The adoption of SSMs for long-term encoding demonstrates their effectiveness and efficiency in handling long sequences, a key requirement for large-scale TUL.

Key Results

ScaleTUL consistently outperforms state-of-the-art baselines across all evaluated metrics (Acc@k, Macro-F1, Micro-F1) on the tested datasets.

  • City Datasets: ScaleTUL achieves significant improvements, especially when the user count increases to 800, showing an average improvement of 6.68% in Acc@1 and 5.2% in Macro-F1 compared to the best baseline on TKY and NYC.
  • Nationwide U.S. Dataset: Even with up to 10,000 users, ScaleTUL maintains strong performance, surpassing previous best models like MainTUL by 6.89% in Acc@1 and 6.11% in Macro-F1 for 5k users.
  • Efficiency: ScaleTUL demonstrates superior running time efficiency, particularly on the TKY dataset, achieving a speed improvement of approximately 96.04% over S2TUL-HRSTS. It also has fewer trainable parameters than MainTUL for large user counts.

Limitations and Future Work

  • Limitations:
    • The paper notes that while the model performs well, the "OOM" (Out of Memory) results for S2TUL on larger US datasets indicate scalability challenges for some baseline methods, which ScaleTUL successfully overcomes.
  • The ablation study shows that while masking rate improves performance, excessive masking can lead to performance degradation, suggesting a need for careful tuning.
  • Future Work: The paper does not explicitly detail future work directions, but the success of ScaleTUL in handling large-scale, irregular trajectory data suggests potential applications in other spatio-temporal domains and further exploration of advanced augmentation and encoding techniques. The efficiency gains also open doors for real-time TUL applications.

Summary updated

BibTeX
@inproceedings{zhang2025scalable,
  author = {Hao Zhang and Wei Chen and Xingyu Zhao and Jianpeng Qi and Guiyuan Jiang and Yanwei Yu},
  title = {{Scalable Trajectory-User Linking with Dual-Stream Representation Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i12.33443},
}
Figure