Integrating Personalized Spatio-Temporal Clustering for Next POI Recommendation

Chao Song, Zheng Ren, Li LuAAAI 2025 · DOI

TL;DR

This paper introduces iPCM, a novel model that integrates personalized spatio-temporal clustering with user trajectory data to improve next Point-of-Interest (POI) recommendations. By learning individual user preferences for both location and time, iPCM significantly outperforms existing state-of-the-art methods, addressing the limitations of traditional approaches that struggle with broad search scopes and lack personalization.

What Problem Does This Paper Address?

Recommending the next Point-of-Interest (POI) a user might visit is a crucial task in Location-Based Social Networks (LBSNs). These networks generate vast amounts of data about user activities, including check-ins at various locations (POIs) with timestamps. Traditional recommendation algorithms often struggle with the sheer volume of data, leading to decreased accuracy due to broad searching scopes and computational overhead. Users, however, exhibit distinct patterns: they tend to visit nearby POIs (spatial clustering) and frequent certain locations during specific times of the day (temporal clustering). These patterns are not uniform across all users; they are personalized. While individual user data can be insufficient to capture these personalized spatio-temporal clustering effects, this paper aims to bridge this gap by developing a model that leverages both global trajectory data and user-specific features to learn these personalized patterns effectively.

Methods

The proposed model, iPCM (integrated Personalized Spatio-Temporal Clustering Model), is built upon several key components:

  • Embedding Module: This module generates embeddings for POIs, users, spatial regions, and time periods.
  • POI Embedding: A global POI graph is constructed based on visit sequences, and a Gated Graph Neural Network (GGNN) is used to generate POI embeddings.
  • User Embedding: A user-POI bipartite graph is created, and user embeddings are derived by aggregating the embeddings of POIs they have visited.
  • Region Embedding: POIs are clustered into spatial regions using a k-means algorithm, and region embeddings are generated via GGNN on a region-region graph.
  • Time Embedding: The day is divided into time slices, which are then clustered into time periods using ordered sample clustering. Time period embeddings are generated using the time2vec method.
  • Fusion Module: Embeddings from POI, user, region, and time period are concatenated and passed through a fully connected layer to create a fused check-in embedding.
  • Encoding and Decoding Module:
    • Transformer Encoder: The fused check-in embeddings of a user's trajectory are fed into a Transformer encoder to capture sequential dependencies and extract effective features.
  • MLP Decoder: Multi-Layer Perceptrons (MLPs) are used to decode the Transformer's output to predict the next POI, time period, and region.
  • Probability Adjustment Module: This module refines the POI prediction by incorporating the predicted region and time period. It uses user-period-POI and user-region-POI tensors to adjust the prediction probabilities, aiming to narrow down the search scope and reduce noise.

Datasets

The experiments were conducted on four real-world Foursquare datasets:

  • NYC: Collected from New York City (April 2012 - February 2013).
  • TKY: Collected from Tokyo during the same period.
  • SIN: Collected from Singapore.
  • OSK: Collected from Osaka.

These datasets contain user, POI, POI category, GPS coordinates, and timestamp information. POIs appearing less than 10 times and users with fewer than 20 check-ins were excluded. The data was split into 80% for training, 10% for validation, and 10% for testing. Trajectories were defined on a day-by-day basis, with trajectories longer than 50 check-ins truncated to the last 50.

Key Insights and Ideas

  • Personalized Spatio-Temporal Clustering is Key: The paper strongly emphasizes that individual users exhibit unique patterns of visiting POIs in both space and time. Simply clustering globally or treating all users the same misses this crucial personalization.
  • Leveraging Global Data for Personalization: A significant challenge is learning personalized patterns from potentially sparse individual data. iPCM addresses this by using global historical trajectory data to inform the learning of these personalized clusters.
  • The Power of Integrated Features: Combining POI, user, region, and time embeddings provides a richer representation of check-in events, allowing the model to capture more nuanced user behavior.
  • Transformer for Sequential Understanding: The use of a Transformer encoder is a natural fit for processing sequential trajectory data, effectively capturing dependencies between check-ins.
  • Probability Adjustment for Refinement: The post-prediction adjustment using region and time information is a clever way to refine the recommendations, especially when direct region prediction might be too broad.

Key Results

The iPCM model consistently outperformed several state-of-the-art baseline models across all four datasets and evaluation metrics (Acc@1, Acc@5, Acc@10, and MRR). Specifically, iPCM achieved an average improvement of:

  • 452.96% over MF (Matrix Factorization)
  • 49.13% over FPMC (Factorized Personalized Markov Chains)
  • 8.29% over GETNext (Transformer-based with global patterns)
  • 5.88% over AGRAN (Adaptive Graph Representation Learning)

Ablation studies demonstrated that each component (POI, user, time clustering, region clustering) contributes to the overall performance, with the full iPCM model yielding the best results. Sensitivity analysis showed that the model's performance is relatively robust to variations in the number of time periods and spatial regions.

Limitations and Future Work

  • Data Sparsity: While the paper addresses data sparsity by using global data, individual user data can still be a limiting factor for highly personalized recommendations.
  • Computational Cost: Integrating multiple complex modules like GGNN and Transformers can lead to significant computational demands, though the paper does not explicitly detail this as a limitation.
  • Future Work: The authors suggest exploring more advanced methods for spatio-temporal clustering and potentially incorporating additional contextual information (e.g., social connections, weather) to further enhance recommendation accuracy. The paper also hints at the potential for further refinement of the probability adjustment module.

Summary updated

BibTeX
@inproceedings{song2025integrating,
  author = {Chao Song and Zheng Ren and Li Lu},
  title = {{Integrating Personalized Spatio-Temporal Clustering for Next POI Recommendation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i12.33368},
}
Figure