Location Prediction over Sparse User Mobility Traces Using RNNs: Flashback in Hidden States!

Dingqi Yang, Benjamin Fankhauser, Paolo Rosso, Philippe Cudré-MaurouxIJCAI 2020 · DOI

TL;DR

This paper introduces "Flashback," a novel RNN architecture that significantly improves next-location prediction accuracy for sparse user mobility data. By intelligently "looking back" at historical hidden states weighted by spatiotemporal context, Flashback effectively leverages rich, often overlooked, user movement patterns.

What Problem Does This Paper Address?

Predicting a user's next location based on their historical movements is crucial for many applications, from personalized recommendations to smart city planning. While Recurrent Neural Networks (RNNs) are well-suited for sequential data like mobility traces, real-world user data is often sparse – check-ins are infrequent and irregularly spaced. This sparsity makes it difficult for standard RNNs to capture the underlying patterns. Existing methods try to incorporate spatiotemporal information (time and distance between check-ins) into RNNs, but they often oversimplify these factors, failing to fully utilize the rich historical context. For instance, they might only consider the immediate past check-in's temporal and spatial distance, missing out on how periodicity (e.g., daily routines) or longer-range spatial relationships can be highly predictive.

Methods

The core innovation of Flashback is its "flashback" mechanism, which allows the RNN to selectively revisit past hidden states. Unlike traditional approaches that simply feed spatiotemporal distances as additional inputs to the RNN, Flashback computes a weighted average of historical hidden states. The weights are dynamically determined by a function that considers both the temporal and spatial distances between the current check-in and past ones.

Specifically, the weight function combines:

  • Temporal Periodicity: A Havercosine function captures daily or other periodic patterns in user behavior.
  • Temporal Decay: An exponential decay factor accounts for the fact that older check-ins generally have less predictive power.
  • Spatial Decay: Another exponential decay factor reflects that closer past locations are more relevant for predicting the next location.

This weighted aggregation of past hidden states creates an "aggregated hidden state" that is then used, along with a user embedding, to predict the next location. This approach allows Flashback to explicitly leverage spatiotemporal contexts to find historically relevant hidden states, effectively creating an "attention" mechanism over past states. A key advantage is that Flashback's core RNN processing remains standard, making it easily adaptable to different RNN architectures like vanilla RNN, LSTM, and GRU.

Datasets

The authors evaluated Flashback on two real-world Location-Based Social Network (LBSN) datasets:

  • Gowalla: Contains approximately 3.3 million check-ins from over 52,000 users collected between 2009 and 2010.
  • Foursquare: Contains approximately 9.4 million check-ins from over 46,000 users collected between 2012 and 2014.

The datasets were split into 80% for training and 20% for testing.

Key Insights and Ideas

  • The Power of "Looking Back": The paper convincingly argues that simply feeding temporal and spatial distances as inputs to RNNs is insufficient. The true value lies in using these contexts to selectively recall relevant past states.
  • Spatiotemporal Context is Key: The proposed weighting mechanism effectively models both the periodicity of human activities and the decreasing relevance of distant or old locations.
  • Flashback as a General Enhancement: The architecture is designed to be a plug-in enhancement for existing RNNs, demonstrating its versatility and ease of integration.
  • Sparsity is a Major Hurdle: The paper highlights the significant challenge posed by sparse mobility data and shows how Flashback directly addresses this by making better use of limited information.

Key Results

Flashback consistently and significantly outperformed a comprehensive set of baseline methods, including user preference-based methods, feature-based methods, Markov-chain-based methods, basic RNNs, and state-of-the-art spatiotemporal RNNs.

  • On the Gowalla dataset, Flashback achieved an improvement of 27.7% in MRR over the best baseline.
  • On the Foursquare dataset, the improvement was 15.9% in MRR.
  • Flashback demonstrated substantial gains (at least 27.5%) over basic RNNs, showcasing the effectiveness of its flashback mechanism.
  • The optimal temporal decay rate (α = 0.1) suggests that a slow decay is beneficial, allowing periodic patterns to contribute significantly.
  • The spatial decay factor (β) showed that increasing spatial proximity strongly improves performance, up to a certain point.
  • The number of past hidden states considered (k) showed diminishing returns after around 20 states, aligning with the temporal decay mechanism.

Limitations and Future Work

  • Learnable Decay Rates: The authors suggest that in future work, they plan to incorporate learnable spatiotemporal decay rates to further automate the learning process, rather than relying on empirically tuned values.
  • Computational Efficiency: While not explicitly detailed as a limitation, the paper mentions that some baselines (like DeepMove) are computationally expensive. Flashback's design, by avoiding modification of the core RNN state-passing, might offer better efficiency, though this is not a primary focus of the paper.
  • Generalizability: While tested on two large datasets, further validation on more diverse mobility datasets could strengthen the findings.

Summary updated

BibTeX
@inproceedings{yang2020location,
  author = {Dingqi Yang and Benjamin Fankhauser and Paolo Rosso and Philippe Cudré-Mauroux},
  title = {{Location Prediction over Sparse User Mobility Traces Using RNNs: Flashback in Hidden States!}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/302},
}
Figure