PaperlayerView exact revision on arXiv

Source-linked AI summary

GETNext: Trajectory Flow Map Enhanced Transformer for Next POI Recommendation

Song Yang, Jiamou Liu, Kaiqi Zhao

arXiv:2303.04741v1cs.IRcs.LG

TL;DR

Next POI recommendation must combine spatial, temporal, preference, and collaborative information, yet existing sequence-based methods omit global signals and struggle with limited histories. GETNext introduces a global trajectory flow map and integrates it with user, spatio-temporal, and time-aware category representations in a transformer. Experiments report large-margin improvements over state-of-the-art methods, including up to 11% higher top-5 accuracy on NYC.

  • Problem

    Existing next POI methods mainly treat the task as sequence prediction, omitting collaborative signals and facing challenges with short trajectories, inactive users, and temporal category patterns.

  • Method

    GETNext builds a user-agnostic global trajectory flow map and combines its transition patterns with user preferences, short-term spatio-temporal context, and time-aware category embeddings in a transformer.

  • Results

    GETNext significantly outperforms state-of-the-art methods across real-world datasets, with up to 11% higher top-5 accuracy on NYC.

  • Takeaways & Limitations

    The unified graph-and-transformer design provides a way to exploit generic movement patterns alongside personalized context for next POI prediction and cold-start challenges.

  • Takeaways & Limitations

    The method models temporal patterns at the POI-category level because individual POI patterns are sparse and noisy.

Abstract

from arXiv · show

Next POI recommendation intends to forecast users' immediate future movements given their current status and historical information, yielding great values for both users and service providers. However, this problem is perceptibly complex because various data trends need to be considered together. This includes the spatial locations, temporal contexts, user's preferences, etc. Most existing studies view the next POI recommendation as a sequence prediction problem while omitting the collaborative signals from other users. Instead, we propose a user-agnostic global trajectory flow map and a novel Graph Enhanced Transformer model (GETNext) to better exploit the extensive collaborative signals for a more accurate next POI prediction, and alleviate the cold start problem in the meantime. GETNext incorporates the global transition patterns, user's general preference, spatio-temporal context, and time-aware category embeddings together into a transformer model to make the prediction of user's future moves. With this design, our model outperforms the state-of-the-art methods with a large margin and also sheds light on the cold start challenges within the spatio-temporal involved recommendation problems.

1 INTRODUCTION

Next POI recommendation must combine spatial, temporal, preference, and collaborative signals, while existing sequence-based approaches struggle with short trajectories, inactive users, and time-category patterns. GETNext addresses these issues with a global trajectory flow map and a transformer that integrates global transitions, user preferences, short-term context, and time-aware category embeddings.

  • Existing next POI methods mainly treat recommendation as sequence prediction, using recurrent models to encode spatio-temporal information.
  • Sequence-based methods face reduced performance on short trajectories, low accuracy for inactive users, and difficulty linking POI categories with temporal patterns.
  • A shared trajectory fragment between users suggests generic movement patterns that can supplement limited individual histories.
  • GETNext constructs a user-agnostic graph whose POI nodes encode location, category, and check-in counts, while weighted directed edges represent successive co-visits.
  • The model combines global transition patterns, general user preferences, short-term spatio-temporal context, and time-aware category embeddings in a transformer framework.
  • 11% top-5 accuracy improvement is reported on the NYC dataset, where experiments show GETNext significantly outperforms state-of-the-art methods.

2 RELATED WORK

Related work predominantly models next POI recommendation as a sequential task with Markov chains, matrix factorization, recurrent networks, or attention. GETNext differs by explicitly using a unified graph to encode global POI transition patterns for next POI recommendation.

  • Early next POI studies used Markov chains and matrix factorization, including personalized Markov chains for sequential transitions.
  • Deep-learning approaches introduced recurrent models that capture temporal dynamics, spatial context, and users’ long- and short-term preferences.
  • Prior graph-based recommendation studies modeled conventional POI recommendation with structures such as tripartite or multiple bipartite graphs.
  • No earlier work explicitly leveraged a unified graph structure for next POI recommendation, according to the paper’s review.
  • A recent method captured local one-hop transitions through sampled neighboring check-ins, whereas GETNext’s trajectory flow map represents global multi-hop patterns among all POIs.

3 PROBLEM FORMULATION

The task predicts a user’s likely next POIs from current and historical trajectories. Check-ins record user, POI, and timestamp information, and trajectories are formed by grouping consecutive check-ins within short time intervals.

  • Each POI is represented by latitude, longitude, category, and check-in frequency, with categories drawn from a fixed list.
  • A check-in is defined as a user visiting a POI at a specific timestamp.
  • All check-ins from a user form a chronological check-in sequence.
  • Sequences are split into consecutive trajectories containing check-ins within a short time interval, such as 24 hours.
  • Given historical trajectories and a current trajectory, the model predicts the most likely future POIs, normally with k=1 next visit.

4.1 Model Structure Overview

GETNext combines a trajectory-flow-map representation with contextual embeddings and transformer-based sequence modeling. The flow map contributes generic movement patterns, while contextual modules encode users, categories, and time before final transition adjustment.

  • Model Structure Overview: The trajectory flow map summarizes historical trajectories and influences recommendations through POI embeddings and a transition attention map.The map is used both to encode generic movement patterns and to model transitions between POIs.
  • Model Structure Overview: A GNN produces POI embeddings incorporating each POI’s category, location, and check-in frequency.
  • Model Structure Overview: Contextual modules combine user embeddings with POI embeddings and combine category embeddings with time encodings.These combinations capture personalization and temporal preferences for different POI categories.
  • Model Structure Overview: A transformer encoder and MLP heads predict a POI from unified check-in embeddings, after which the transition attention map adjusts the prediction through a residual connection.

4.2 Learning with Trajectory Flow Map

GETNext learns POI representations from a user-agnostic weighted directed graph of historical movements, then uses explicit transition attention to adjust predictions. This design supplies generic movement information even when current trajectories are short.

  • Learning with Trajectory Flow Map: The trajectory flow map is a user-agnostic weighted directed graph whose nodes are POIs and whose edges represent consecutive visits.Node attributes include location, category, and check-in frequency; edge weights count co-visits across historical trajectories.
  • POI Embedding: A GCN learns POI embeddings from the flow map’s topology and node features by repeatedly aggregating neighborhood information with each node’s own embedding.The model uses a normalized Laplacian, trainable layer transformations, leaky ReLU nonlinearity, stacked layers, and dropout before the last layer.
  • POI Embedding: Each learned POI embedding represents the POI’s position within historical trajectories of all users and captures generic movement patterns.These embeddings are passed to the downstream transformer to model visiting behaviors.
  • Learning with Trajectory Flow Map: Flow-map POI embeddings provide rich information for prediction when the current trajectory is short.
  • Transition Attention Map: The transition attention map explicitly models transition probabilities between POIs and adjusts later transformer recommendations using the row corresponding to the trajectory’s last POI.The map is derived from the graph and node features, while the selected row provides unnormalized movement probabilities to candidate POIs.

4.3 Contextual Embedding Module

The contextual embedding module fuses user, POI, category, and time information into check-in representations. It models temporal category preferences with time2vector because category-level patterns are more stable than individual-POI patterns.

  • Contextual Embedding Module: The module combines user embeddings, POI embeddings, POI category embeddings, and time encodings to represent contextual information.
  • POI-User Embeddings Fusion: A learned user embedding captures a user’s general behavior from historical check-in sequences, while POI embeddings encode user-agnostic patterns.
  • POI-User Embeddings Fusion: Concatenated POI and user embeddings pass through a dense layer that fine-tunes their fused representation without changing the embedding size.
  • Time-Category Embeddings Fusion: Train-station check-ins peak around 8AM and 6PM, whereas bar check-ins occur mostly after 6PM.These contrasting category patterns motivate time-aware category modeling.
  • Time-Category Embeddings Fusion: Category-level temporal patterns are modeled instead of individual-POI patterns because individual POIs have sparse and noisy check-ins.In the NYC dataset, each POI averages fewer than 6 check-ins, compared with more than 570 per category.
  • Time-Category Embeddings Fusion: Time2vector divides each day into 48 thirty-minute slots, combines time and category embeddings, and concatenates the result with the fused POI-user embedding.The resulting check-in embeddings form the sequence supplied to the transformer encoder.

4.4 Transformer Encoder and MLP Decoders

GETNext uses a transformer encoder with MLP heads to integrate historical check-ins for next-POI, time, and category prediction. Self-attention weights check-in contributions, while auxiliary time and category tasks regularize POI prediction.

  • Transformer Encoder: The encoder replaces the transformer decoder because the task predicts only the next immediate POI from a check-in sequence.It stacks standard encoder layers with positional encoding, multi-head self-attention, and position-wise fully connected networks.
  • Transformer Encoder: Historical check-in embeddings are stacked into an input tensor X[0] ∈ R^k×d, where d = 2 × (Ω + Ψ).The tensor contains embeddings for the k historical check-ins and feeds the first encoder layer.
  • Transformer Encoder: Self-attention learns each check-in’s contribution and aggregates the trajectory simultaneously for prediction.The attention mechanism computes correlations between check-ins, normalizes weights with softmax, and merges multiple attention spaces.
  • MLP Decoders: Three MLP heads predict the next POI, visit time, and POI category from the encoder output.The POI head uses only the final row for the future-move recommendation, and its output is combined with the transition attention map.
  • MLP Decoders: Time prediction calibrates temporal modeling, while category prediction regularizes POI prediction because categories are easier to forecast than exact POIs.The model jointly trains cross-entropy losses for POI and category prediction with MSE for time prediction; the normalized time loss is amplified 10-fold.

5 EXPERIMENTS

The experiments evaluate GETNext on three public location-based-service datasets using standard top-k accuracy and MRR metrics. The study compares the model with classical, sequential, and recommendation baselines under stated preprocessing and implementation settings.

  • Datasets and Setup: Experiments use FourSquare-NYC, FourSquare-TKY, and Gowalla-CA, with each record containing user, POI, category, coordinates, and timestamp.The datasets cover New York City, Tokyo, and California/Nevada across different collection periods.
  • Datasets and Setup: The preprocessing excludes POIs with fewer than 10 check-ins and filters users according to dataset criteria.
  • Evaluation Metrics: Performance is measured with Acc@k and MRR, where Acc@k checks top-k inclusion and MRR reflects the rank of the correct POI.Higher values indicate better performance.
  • Baselines: Baselines include Matrix Factorization, FPMC, LSTM, and other sequential or personalized recommendation methods.FPMC combines matrix factorization with a Markov chain, while LSTM models short- and long-term sequential patterns.
  • Implementation: The implementation uses PyTorch with POI and user embedding dimensions Ω = 128 and time and category embedding length Ψ = 32.The GCN has three hidden layers with 32, 64, and 128 channels.

5.2 Results

GETNext outperforms the baselines across the evaluated datasets and shows advantages for inactive users and short trajectories. The trajectory flow map contributes substantially, although performance remains lower on the sparser CA dataset.

  • Overall Results: All models perform better on NYC and TKY than CA because CA’s POIs are spread across a much larger, sparser region.CA covers California and Nevada, whereas NYC and TKY constrain POIs within city areas.
  • Overall Results: GETNext achieves 24.35% top-1 accuracy on NYC versus 22.31% for the best baseline STAN.It also records about 11% improvement in top-5 accuracy and an 8.7% increase in top-20 accuracy on NYC.
  • Inactive Users: For inactive NYC users, GETNext reaches 12.24% top-1 and 43.94% top-10 accuracy, compared with 9.06% and 31.24% for STGN.The evaluation groups users by trajectory counts in the training set and uses the global flow map to leverage other users’ sequences.
  • Short Trajectories: On short NYC trajectories, GETNext has 21.86% top-1 accuracy and 57.82% top-20 accuracy, while STGN has 7.23% and 33.28%.GETNext shows no significant recommendation difference between short and long trajectories, whereas STGN is sensitive to trajectory length.
  • Trajectory Flow Map: Removing the trajectory flow map lowers top-10 accuracy for inactive users from 42.11% to 34.70% and short-trajectory performance from 52.06% to 47.21%.These comparisons support a benefit from the global trajectory flow map for cold-start settings.

5.4 Ablation Study

The ablation study finds that the full GETNext model performs best, with the trajectory flow map and GCN contributing more strongly than the other evaluated components.

  • Ablation Results: The full model achieves the best performance among the seven evaluated configurations.The ablations remove or replace the trajectory flow map, transformer encoder, time and category information, GCN, and fusion components.
  • Ablation Results: Removing the trajectory flow map reduces top-1 accuracy from 24.35% to 21.63% on NYC.
  • Ablation Results: The transformer contributes by using self-attention to extract useful historical information with fewer parameters to train than the compared sequential handling.

6 CONCLUSION

GETNext uses a global, user-agnostic trajectory flow map with spatio-temporal embeddings and a Transformer to model next POI movements. Experiments on three real-world datasets show large-margin improvements over current state-of-the-art models, while future work distinguishes temporal patterns and user behavior types.

  • GETNext uses graph-based learning on a global graph structure for next POI recommendation.The model introduces a trajectory flow map to capture generic user movement patterns.
  • The trajectory flow map addresses inactive-user and short-trajectory issues by capturing generic movement patterns.
  • GETNext encodes spatio-temporal contexts with user-POI and time-category embeddings before Transformer-based prediction.Its output is further enhanced through a transition attention map.
  • Experiments on three real-world datasets show that GETNext significantly outperforms current state-of-the-art models by a large margin.The experiments also verify the benefits of the model’s different components.
  • Future work will distinguish temporal patterns such as workdays versus weekends and build trajectory flow maps for behavior-based user types.
Loading 2303.04741v1…