Where to Go Next: A Spatio-temporal LSTM model for Next POI Recommendation

Pengpeng Zhao, Haifeng Zhu, Yanchi Liu, Zhixu Li, Jiajie Xu, Victor S. Sheng

Predicting human mobility is a complex challenge that extends beyond simple historical patterns. Where a person goes next is deeply contextual: a check-in at a coffee shop ten minutes ago suggests a nearby destination, whereas a check-in from three days ago may have little bearing on current movement. Traditional sequence models often struggle to account for these irregular gaps in time and space. This paper introduces ST-LSTM, a specialized Long Short-Term Memory (LSTM) variant designed to bridge this gap in Next Point-of-Interest (POI) recommendation.

The Challenge of Human Mobility

Most sequential recommendation systems, such as those used for language modeling or "next-basket" shopping, assume that items in a sequence are separated by uniform steps. However, human mobility is fundamentally different because the relationship between successive check-ins is governed by two continuous variables:

  1. Time Intervals ($\Delta t$): The predictive value of a check-in decays as time passes.
  2. Geographical Distance ($\Delta d$): Moving a short distance within a neighborhood represents a different behavioral pattern than traveling across a city.
Comparison of sequence modeling tasks: Language Modeling, Next Basket Recommendation, and Next POI Recommendation.

Existing Recurrent Neural Network (RNN) solutions often ignore these intervals or simplify them into discrete "bins" (e.g., "0-1 hours"), which leads to data sparsity and a loss of precision. The authors propose a model that treats time and distance as continuous variables that directly regulate the flow of information through the network.

Methods: The ST-LSTM Architecture

The core innovation of the Spatio-Temporal LSTM (ST-LSTM) is the addition of two pairs of gates to the standard LSTM architecture. These gates explicitly model the influence of spatio-temporal intervals on both short-term and long-term user interests.

The ST-LSTM cell architecture featuring spatio-temporal gates (T1, D1, T2, D2).
  • Short-term Interest Gates ($T1_t, D1_t$): These gates control the influence of the most recent POI. If the time or distance interval is large, these gates "filter out" the influence of the last check-in, as it is less likely to dictate the immediate next move.
  • Long-term Interest Gates ($T2_t, D2_t$): These gates manage how the cell state (the model's long-term memory) is updated. They help the model memorize spatio-temporal patterns over a user's entire history.

To improve efficiency, the authors also introduced ST-CLSTM, a variant that uses coupled input and forget gates. By performing forget and input actions in a single step, the model reduces parameter count without sacrificing accuracy.

Experimental Setup and Datasets

The model was evaluated on four real-world datasets from Location-Based Social Networks (LBSNs):

  • CA & SIN: Foursquare check-ins in California and Singapore.
  • Gowalla & Brightkite: Standard public LBSN datasets.

Data cleaning involved removing inactive users (fewer than 10 check-ins) and unpopular POIs (visited by fewer than 10 users) to ensure a high signal-to-noise ratio for training.

Key Insights

  • Continuous Modeling: Unlike previous models (like ST-RNN) that used transition matrices for fixed bins, ST-LSTM uses continuous functions to learn the nuances of varying gaps (e.g., 15 vs. 20 minutes).
  • Enforced Decay Logic: The authors enforced a constraint ($W \leq 0$) on the weights of the short-term gates. This ensures that as time or distance increases, the influence of the previous location naturally decreases, mathematically encoding the intuition that "stale" data should matter less.
  • Dual-Layer Context: By separating gates for the hidden state (short-term) and the cell state (long-term), the model can simultaneously track immediate activities (like a shopping trip) while remembering general user preferences (like a love for Italian food).

Results and Performance

ST-LSTM and ST-CLSTM consistently outperformed seven baselines, including standard LSTMs, GRUs, and the previous state-of-the-art ST-RNN.

  • Accuracy: On the Singapore (SIN) dataset, ST-CLSTM achieved an Acc@1 of 0.2037, nearly double the performance of a standard LSTM (0.1261).
  • Cold Start Resilience: The model showed significant strength in "cold start" scenarios. By understanding universal spatio-temporal constraints, it can make better predictions for new users than models relying solely on long historical patterns.
  • Efficiency: The ST-CLSTM variant reduced parameter count and marginally improved performance, suggesting the coupled structure acts as a helpful regularizer.

Conclusion and Future Work

While ST-LSTM excels at handling "where" and "when," it currently treats POIs as abstract IDs. Future work may involve incorporating richer contextual information, such as POI categories (e.g., "Restaurant" vs. "Park"), social network ties, or user reviews, to further refine recommendations within the gated architecture.

Summary updated

Abstract

Next Point-of-Interest (POI) recommendation is of great value for both location-based service providers and users. Recently Recurrent Neural Networks (RNNs) have been proved to be effective on sequential recommendation tasks. However, existing RNN solutions rarely consider the spatio-temporal intervals between neighbor check-ins, which are essential for modeling user check-in behaviors in next POI recommendation. In this paper, we propose a new variant of LSTM, named STLSTM, which implements time gates and distance gates into LSTM to capture the spatio-temporal relation between successive check-ins. Specifically, one-time gate and one distance gate are designed to control short-term interest update, and another time gate and distance gate are designed to control long-term interest update. Furthermore, to reduce the number of parameters and improve efficiency, we further integrate coupled input and forget gates with our proposed model. Finally, we evaluate the proposed model using four real-world datasets from various location-based social networks. Our experimental results show that our model significantly outperforms the state-of-the-art approaches for next POI recommendation.
BibTeX
@misc{zhao2018where,
  author = {Pengpeng Zhao and Haifeng Zhu and Yanchi Liu and Zhixu Li and Jiajie Xu and Victor S. Sheng},
  title = {{Where to Go Next: A Spatio-temporal LSTM model for Next POI Recommendation}},
  year = {2018},
  eprint = {1806.06671},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.06671},
}
Figure