Next POI Recommendation with Dynamic Graph and Explicit Dependency

Feiyu Yin, Yong Liu, Zhiqi Shen, Lisi Chen, Shuo Shang, Peng Han

Introduction

Predicting a user's next Point-of-Interest (POI) is fundamental to modern location-based services, from personalized trip planning to targeted advertising. However, traditional models struggle with three primary challenges: extreme data sparsity, the static nature of POI relationship graphs, and "information oblivion," where long-range dependencies in user trajectories are lost over time.

To address these, the Sequence-based Neighbour search and Prediction Model (SNPM) is proposed. SNPM leverages a dynamic neighbor graph to handle sparsity and context, alongside a multi-step recurrent neural network that explicitly models long-term dependencies using geometric rotation operations.

The SNPM Architecture

The SNPM framework integrates two innovative components: a Sequence-based Dynamic Neighbor Graph (SDNG) and a Multi-Step Dependency Prediction (MSDP) module. The overall architecture, as shown in Figure 1, coordinates these elements to transform raw historical trajectories into accurate next-location predictions.

The overall architecture of the SNPM framework, illustrating the integration of the dynamic neighbor graph and multi-step prediction modules.

Sequence-based Dynamic Neighbor Graph (SDNG)

Unlike static graphs that assume fixed relationships between locations, the SDNG component builds a context-aware graph. It utilizes RotatE knowledge graph embeddings to infer potential transitions in sparse data and clusters POIs into regions. Crucially, it dynamically selects relevant neighbors based on the user's current visited sequence, ensuring that the aggregated information is contextually pertinent to the immediate trajectory.

Multi-Step Dependency Prediction (MSDP)

The core of the prediction module is the Multi-Step Recurrent Neural Network (MSRNN). To combat the vanishing memory of standard RNNs, MSRNN explicitly "looks back" at the last $K$ visited POIs. It employs a rotation operation in complex space (inspired by RotatE) to model the influence of each historical step. This geometric approach provides a more robust and structured representation of long-term patterns compared to traditional gating mechanisms.

Experimental Evaluation

The model was rigorously tested on the Gowalla and Foursquare datasets, which contain millions of check-ins. SNPM demonstrated superior performance, outperforming state-of-the-art baselines like GETNext and Flashback. Specifically, it achieved accuracy gains (Acc@1) of 12.26% on Gowalla and 9.56% on Foursquare.

Beyond raw accuracy, SNPM exhibits significant robustness. As illustrated in Figure 4, the model's performance remains stable across a wide range of hyperparameter settings, including the neighbor search window ($\omega$) and the look-back window ($K$). This stability suggests that the model effectively captures underlying behavioral patterns rather than over-fitting to specific configurations.

Sensitivity analysis demonstrating the robustness of SNPM performance across various hyperparameter settings.

Conclusion

SNPM represents a significant advancement in next POI recommendation by moving beyond static graph structures and implicit sequential modeling. By combining dynamic, context-aware neighbor aggregation with explicit, rotation-based multi-step dependencies, the framework effectively mitigates the issues of data sparsity and information loss. Future work will focus on deeper personalization and optimizing the computational efficiency of the dynamic search process.

Summary updated

Abstract

Next Point-Of-Interest (POI) recommendation plays an important role in various location-based services. Its main objective is to predict the user's next interested POI based on her previous check-in information. Most existing methods directly use users' historical check-in trajectories to construct various graphs to assist sequential models to complete this task. However, as users' check-in data is extremely sparse, it is difficult to capture the potential relations between POIs by directly using these check-in data. To this end, we propose the Sequence-based Neighbour search and Prediction Model (SNPM) for next POI recommendation. In SNPM, the RotatE knowledge graph embedding and Eigenmap methods are used to extract POI relationships implied in check-in data, and build the POI similarity graph. Then, we enhance the model's generalized representations of POIs' general features by aggregating similar POIs. As the context is typically rich and valuable when making Next POI predictions, the sequence model selects which POIs to aggregate not only depends on the current state, but also needs to consider the previous POI sequence. Therefore, we construct a Sequence-based, Dynamic Neighbor Graph (SDNG) to find the similarity neighbourhood and develop a Multi-Step Dependency Prediction model (MSDP) inspired by RotatE, which explicitly leverage information from previous states. We evaluate the proposed model on two real-world datasets, and the experimental results show that the proposed method significantly outperforms existing state-of-the-art POI recommendation methods.
BibTeX
@inproceedings{yin2023next,
  author = {Feiyu Yin and Yong Liu and Zhiqi Shen and Lisi Chen and Shuo Shang and Peng Han},
  title = {{Next POI Recommendation with Dynamic Graph and Explicit Dependency}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25608},
}
Figure