Rank-GeoFM: A Ranking based Geographical Factorization Method for Point of Interest Recommendation

Xutao Li, Gao Cong, Xiaoli Li, Tuan-Anh Nguyen Pham, Shonali KrishnaswamySIGIR 2015 · DOI

TL;DR

This paper introduces Rank-GeoFM, a novel method for Point of Interest (POI) recommendation that tackles the challenges of sparse check-in data and the incorporation of contextual information. By framing recommendation as a ranking problem and leveraging geographical influences, Rank-GeoFM significantly improves accuracy over existing methods.

What Problem Does This Paper Address?

Location-based social networks (LBSNs) have exploded in popularity, enabling users to "check in" at Points of Interest (POIs) like restaurants and shops. This rich data offers opportunities for personalized POI recommendations, helping users discover new places and businesses attract customers. However, two major challenges hinder current recommendation systems:

  1. Data Sparsity: Check-in data is inherently sparse. Most users only check into a tiny fraction of available POIs, creating a user-POI matrix with very few entries. This makes it difficult for traditional collaborative filtering methods to find meaningful patterns. When considering context (like time), this sparsity becomes even more pronounced.
  2. Contextual Information: POIs are often associated with various contextual factors such as geographical location, time of day, and user social connections. Effectively leveraging these diverse contextual cues is crucial for accurate recommendations, but existing methods often struggle to generalize across different types of context.

Methods

Rank-GeoFM addresses these challenges with a two-pronged approach:

  • Ranking-Based Factorization: Instead of directly predicting check-in frequencies (which is problematic with implicit feedback and sparsity), Rank-GeoFM frames the problem as learning a ranking of POIs for each user. It assumes that higher check-in frequency implies higher preference. The model aims to minimize "ranking incompatibility," which measures how many POIs are ranked lower by the model than they should be based on observed check-in data. This ranking approach is more robust to sparse and implicit feedback data.
  • Geographical Factorization: The core of the method is a factorization model that learns latent representations for users and POIs. Crucially, it incorporates geographical influence by modeling the probability that a user will visit a POI based on its proximity to other POIs they have visited. This is achieved by introducing an additional latent factor matrix and a geographical influence matrix derived from POI distances.
  • Efficient Optimization: To handle the non-differentiable nature of the ranking objective and the computational cost of calculating gradients over all POIs, the authors propose:
  • A continuous approximation of the objective function using the sigmoid function.
  • A fast learning scheme that uses sampling to estimate the ranking incompatibility and compute gradients, significantly reducing computational complexity.

The model is also generalized to incorporate other contextual information, such as temporal data, by extending the factorization framework.

Datasets

The authors evaluate their method on two real-world LBSN datasets:

  • Foursquare: Singapore check-in data (Aug. 2010 - Jul. 2011).
  • Gowalla: California and Nevada check-in data (Feb. 2009 - Oct. 2010).

For POI recommendation, user-POI matrices were constructed. For time-aware POI recommendation, user-time-POI tensors were created by discretizing time into 24-hour slots. The datasets are noted to be highly sparse, with matrix densities below 0.5% and tensor densities below 0.05%.

Key Insights and Ideas

  • Ranking is Key for Sparse Implicit Data: Framing POI recommendation as a ranking problem, rather than direct prediction, is more effective for handling sparse, implicit feedback data. This allows unobserved POIs to contribute to learning.
  • Geographical Proximity Matters: Explicitly modeling the influence of nearby POIs significantly boosts recommendation accuracy, highlighting the importance of spatial context.
  • Efficient Sampling for Scalability: The proposed fast learning scheme using sampling is crucial for making the ranking-based factorization computationally feasible for large-scale datasets.
  • Unified Framework for Context: The factorization approach provides a flexible framework that can naturally incorporate various contextual factors (geographical, temporal, etc.) by adding corresponding latent factor terms.

Key Results

  • POI Recommendation: Rank-GeoFM consistently outperformed state-of-the-art methods like GeoMF and BPR-MF, achieving significant improvements in precision and recall (e.g., over 41.6% improvement in Pre@5 on Foursquare compared to GeoMF). The geographical component alone provided substantial gains over non-geographical ranking methods.
  • Time-aware POI Recommendation: Rank-GeoFM also outperformed strong baselines like BPP and UTE+SE, demonstrating its effectiveness in handling temporal context.
  • Efficiency: The fast learning scheme enabled Rank-GeoFM to train models significantly faster than a naive implementation, achieving a well-trained model in hours rather than days.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the continuous approximation of the objective function is an approximation.
  • The fast learning scheme relies on sampling, which introduces a probabilistic element.
  • Future Work:
    • The authors suggest extending the model to incorporate other types of context, such as POI categories, by adding corresponding latent factor terms to the recommendation score.
  • Investigating how other contextual information impacts recommendation performance.

Summary updated

BibTeX
@inproceedings{li2015rank,
  author = {Xutao Li and Gao Cong and Xiaoli Li and Tuan-Anh Nguyen Pham and Shonali Krishnaswamy},
  title = {{Rank-GeoFM: A Ranking based Geographical Factorization Method for Point of Interest Recommendation}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2015},
  doi = {10.1145/2766462.2767722},
}
Figure