On Information Coverage for Location Category Based Point-of-Interest Recommendation

Xuefeng Chen, Yifeng Zeng, Gao Cong, Shengchao Qin, Yanping Xiang, Yuanshun DaiAAAI 2015 · DOI

Introduction

Traditional Point-of-Interest (POI) recommendation systems primarily focus on relevance, often leading to "filter bubbles" where users are suggested a list of homogeneous locations based on their past behavior. For instance, a user who frequently visits malls might receive a list of ten different malls. While accurate, such recommendations lack the variety necessary for a rich urban experience. This paper addresses this limitation by introducing a framework that balances user relevance with Information Coverage, ensuring recommendations span a diverse set of location categories.

The Information Coverage Problem

Most existing POI recommenders operate on similarity: if a user has visited many restaurants, the system recommends more restaurants. However, real-world user behavior suggests a natural inclination toward exploration.

User exploration patterns in Singapore (SIN) and Austin (AUS) datasets showing the ratio of new categories visited over time.

As shown in Figure 3, data analysis of Foursquare (Singapore) and Gowalla (Austin) datasets reveals an "exploration incline." In any given month, approximately 25-30% of a user's visited categories are entirely new to them. This empirical evidence validates the need for diversity-aware recommendation systems that can provide a "flavor" of the city by covering various categories like museums, parks, and cafes alongside preferred categories.

Methodology: The top-K LC-POI Framework

The authors propose a multi-objective optimization framework, top-K LC-POI, which utilizes a scoring function $\sigma(L)$ that combines two primary factors:

  1. Relevance ($R(L)$): Calculated using the User-Spatial-Temporal (UST) framework, accounting for user similarity and geographical influence.
  2. Information Coverage ($I(L)$): A novel metric measuring how well a set of POIs covers different location categories. To prevent ubiquitous categories (e.g., "Office") from dominating, the authors adapt TF-IDF logic, treating categories as "words" and cities as "documents" to prioritize unique local offerings.

Algorithmic Optimization

Maximizing both relevance and category diversity is an NP-hard combinatorial problem. However, the authors prove that the scoring function exhibits Monotone Submodularity—a property of "diminishing returns" where adding a POI to a smaller set increases the total score more than adding it to a larger set.

This mathematical property allows for the use of a Greedy Algorithm (GA) with a guaranteed approximation ratio of $(1 - 1/e)$. To ensure real-time performance, a Pruning Optimization (GA+PO) is introduced to discard POIs with low individual scores before the main search, significantly reducing computational overhead.

Experimental Evaluation

The framework was evaluated using real-world check-in data from Foursquare (Singapore) and Gowalla (Austin).

Key Results

  • Diversity and Accuracy: The proposed Greedy Algorithm improved category diversity (Shannon entropy) by 35% on Foursquare and 13% on Gowalla compared to the baseline, while maintaining approximately 97% of the precision and recall of relevance-only methods.
  • Efficiency: The pruning optimization proved critical for scalability.
Comparison of run times for the standard Greedy Algorithm (GA) versus the optimized versions (GA+PO and GA+PO+CELF) across different beta values.

As illustrated in Figure 6, the GA+PO approach drastically reduces computation time compared to the standard GA, making it suitable for practical deployment even as the number of requested recommendations ($K$) or the diversity weight ($\beta$) increases.

Conclusion

By formalizing Information Coverage and leveraging the property of submodularity, this work provides a robust solution for diversifying POI recommendations without sacrificing accuracy. The introduction of the pruning optimization ensures that these high-quality, diverse recommendations can be generated efficiently in real-time environments. Future work may explore automated parameter tuning to adapt to individual user's explorative tendencies.

Summary updated

BibTeX
@inproceedings{chen2015information,
  author = {Xuefeng Chen and Yifeng Zeng and Gao Cong and Shengchao Qin and Yanping Xiang and Yuanshun Dai},
  title = {{On Information Coverage for Location Category Based Point-of-Interest Recommendation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9191},
}
Figure