PaperlayerView exact revision on arXiv

Source-linked AI summary

STAN: Spatio-Temporal Attention Network for Next Location Recommendation

Yingtao Luo, Qiang Liu, Zhaocheng Liu

arXiv:2102.04095v1cs.IRcs.AI

TL;DR

Next-location recommenders often miss correlations among non-adjacent locations, non-consecutive visits, and repeated-item frequency. STAN uses explicit spatiotemporal self-attention with a bi-layer architecture to aggregate trajectories and recall candidates, and it surpasses state-of-the-art models by 9–17%.

  • Problem

    Existing models rarely capture non-adjacent and non-consecutive spatiotemporal correlations, while self-attention and recurrent approaches struggle to represent personalized item frequency.

  • Method

    STAN uses a spatiotemporal bi-attention architecture with explicit relative spatial and temporal information, combining trajectory aggregation with candidate recall and personalized item frequency.

  • Results

    9–17%: STAN improves recall rates over state-of-the-art baseline models.

  • Takeaways & Limitations

    STAN’s weighted representations let candidate recall consider all trajectory check-ins, including repeated locations, while explicitly modeling non-adjacent and non-consecutive relationships.

  • Takeaways & Limitations

    Self-attention normalization in prior models reduces historical representations to a single vector, making personalized item frequency difficult to reflect.

Abstract

from arXiv · show

The next location recommendation is at the core of various location-based applications. Current state-of-the-art models have attempted to solve spatial sparsity with hierarchical gridding and model temporal relation with explicit time intervals, while some vital questions remain unsolved. Non-adjacent locations and non-consecutive visits provide non-trivial correlations for understanding a user's behavior but were rarely considered. To aggregate all relevant visits from user trajectory and recall the most plausible candidates from weighted representations, here we propose a Spatio-Temporal Attention Network (STAN) for location recommendation. STAN explicitly exploits relative spatiotemporal information of all the check-ins with self-attention layers along the trajectory. This improvement allows a point-to-point interaction between non-adjacent locations and non-consecutive check-ins with explicit spatiotemporal effect. STAN uses a bi-layer attention architecture that firstly aggregates spatiotemporal correlation within user trajectory and then recalls the target with consideration of personalized item frequency (PIF). By visualization, we show that STAN is in line with the above intuition. Experimental results unequivocally show that our model outperforms the existing state-of-the-art methods by 9-17%.

1 INTRODUCTION

Next POI recommendation uses historical check-ins to model user movement, but existing approaches leave important spatiotemporal correlations and personalized frequency insufficiently addressed. STAN introduces bi-layer attention to aggregate relevant trajectory visits and recall candidates using explicit spatiotemporal effects.

  • Historical check-in trajectories help providers understand user preferences and support decisions about where to go and how to plan the day.
  • Existing models have not effectively learned correlations between non-adjacent locations and non-contiguous visits within user trajectories.Relevant locations visited days earlier may matter more than irrelevant locations visited immediately before.
  • Hierarchical gridding loses spatial-distance information, while prior models often overlook personalized item frequency from repeated visits.Gridding treats nearby and distant neighboring locations similarly, and normalization or recurrent memory mechanisms make repeated-location frequency difficult to represent.
  • STAN uses two self-attention layers with explicit point-to-point spatiotemporal effects to aggregate important historical locations and recall plausible candidates.The architecture assigns different weights to visits within the trajectory and addresses long-term dependency problems associated with recurrent layers.
  • STAN combines spatiotemporal aggregation, linear spatial interpolation, and bi-attention for PIF, and experiments on four real-world datasets report accuracy gains exceeding 10% over state-of-the-art models.The contribution passage reports an accuracy improvement of more than 10%.

2 RELATED WORKS

Sequential recommendation research developed from Markov and deep-learning models toward approaches incorporating temporal, spatial, and long-term trajectory information. However, recurrent and self-attention models still struggle to capture personalized item frequency, motivating STAN’s design.

  • Next POI recommendation is a spatially informed special sub-task of sequential recommendation.
  • Sequential Recommendation: Markov-based models estimate next behavior through transition matrices but struggle with intermittent visits because sequential data are sparse.
  • Sequential Recommendation: RNN-based models became strong baselines by modeling sequential behavior and incorporating temporal intervals or long- and short-term trajectory patterns.
  • Sequential Recommendation: RNN-based and self-attention recommenders have difficulty capturing personalized item frequency from repeated visits.Self-attention normalization reduces previous histories to a single vector, making candidate matching poorly reflect frequency information.

3 PRELIMINARIES

The paper formulates next-location prediction from a user’s historical trajectory, candidate locations, and spatiotemporal relation matrices. It represents trajectories with fixed-length check-in sequences and explicitly models temporal intervals and geographical distances.

  • Historical Trajectory: Each historical check-in is a user-location-timestamp tuple, and variable-length trajectories are converted into fixed-length sequences by truncating recent visits or right-padding zeros.
  • Trajectory Spatio-Temporal Relation Matrix: Trajectory spatiotemporal relations represent pairwise temporal intervals and geographical distances between visited locations.Temporal intervals are defined as absolute timestamp differences, while spatial distances use the Haversine distance between GPS coordinates.
  • Trajectory Spatio-Temporal Relation Matrix: The formulation separately represents trajectory spatial and temporal relation matrices as n×n matrices.
  • Candidate Spatio-Temporal Relation Matrix: Candidate spatiotemporal relations encode distances from each candidate location to each historical check-in and time intervals from the next timestamp to prior visits.
  • Mobility Prediction: The next-location task predicts the desired location from a user trajectory, candidate locations, and trajectory and next-location spatiotemporal relation matrices.

4 THE PROPOSED FRAMEWORK

STAN combines multimodal representations with spatiotemporal self-attention to aggregate relevant trajectory visits and match location candidates. Its bi-layer design preserves contributions from all updated check-ins while training uses negative sampling to address unbalanced candidate labels.

  • Framework overview: STAN comprises multimodal embedding, self-attention aggregation, attention matching, and balanced-sampler modules.The embedding module encodes user, location, and time; later modules aggregate check-ins, score candidates, and sample negatives.
  • Multimodal Embedding Module: User, location, and time embeddings are summed into a dense representation for each check-in.Continuous timestamps are mapped to 168 weekly-hour dimensions, and each trajectory becomes a sequence of d-dimensional vectors.
  • Spatio-Temporal Embedding Layer: Spatiotemporal relations are represented through dense spatial and temporal interval embeddings rather than sparse interval discretization.An alternative interpolation layer approximates this representation by linearly interpolating upper- and lower-bound unit embeddings.
  • Self-Attention Aggregation Layer: Self-attention assigns different weights to visits and enables point-to-point interactions using explicit spatial distances and time intervals.Causal masking feeds only the first m′ visits when predicting the next location.
  • Attention Matching Layer: The matching layer computes each candidate’s probability from candidate embeddings, updated trajectory representations, and candidate spatiotemporal relations.All updated check-in representations participate in candidate matching, retaining personalized item-frequency information.
  • Balanced Sampler: Balanced negative sampling addresses inefficient cross-entropy optimization caused by unbalanced positive and negative candidate samples.Using all L−1 negatives is costly, whereas binary sampling may leave many non-label samples unused; the sampler controls the number of negatives s.

5 EXPERIMENTS

The experiments evaluate STAN on four real-world datasets using causality-preserving splits and compare it with recurrent, self-attention, and other state-of-the-art baselines.

  • Evaluation design: The experiments report top-k recall performance, model stability, and visualizations of STAN attention weights.The evaluation includes dataset statistics, recommendation results, hyperparameter stability, and attention visualization.
  • Datasets and setup: STAN is evaluated on Gowalla, SIN, TKY, and NYC using raw GPS-based trajectories.Validation and test inputs use progressively longer check-in prefixes, with future visits withheld from prediction.
  • Experimental protocol: The dataset splits follow causality by ensuring that no future data is used to predict future data.This constraint is applied to the validation and test construction.
  • Baseline models: The evaluation compares STAN with recurrent, temporal-spatial, semantic-spatial, long-short-term, and self-attention recommendation baselines.Compared models include STRNN, DeepMove, STGN, ARNN, LSTPM, TiSASRec, and GeoSAN.

5.3 Evaluation Matrices

Recommendation performance is evaluated with Recall@5 and Recall@10, using shared training settings and a fixed trajectory-length limit.

  • Metrics: Recall@5 and Recall@10 measure the rate at which the true next location appears among the top-k predicted candidates.Higher Recall@k indicates better recommendation performance.
  • Evaluation procedure: The evaluation drops the balanced sampler and directly recalls the target from the attention matching layer’s candidate-location output.The balanced sampler is used during training, not target recall evaluation.
  • Hyperparameters: Common settings include learning rate 0.003, dropout 0.2, 50 training epochs, and a maximum trajectory length of 100.Embedding dimension is set to 50 for TKY, SIN, and NYC, and 10 for Gowalla.

5.5 Recommendation Performance

STAN outperforms the compared models on recommendation recall, while the results attribute advantages to modeling non-consecutive visits, non-adjacent locations, and personalized item frequency.

  • Recommendation results: 9%-17% improvement in recall rates is reported for STAN over all compared models.The paper reports this comparison across the evaluated datasets and baselines.
  • Baseline comparison: Self-attention baselines such as TiSASRec and GeoSAN perform better than RNN-based baselines in the comparison.The paper associates the stronger baseline performance with modeling temporal intervals, geographical partitions, or periodicity.
  • Model comparison: STAN uniquely combines spatiotemporal intervals for non-consecutive visits and non-adjacent locations with a PIF-aware bi-layer attention architecture.TiSASRec uses temporal intervals, while GeoSAN uses geographical partitions.
  • Variant analysis: The −ALL variant is slightly worse than GeoSAN, slightly better than TiSASRec, and much better than the RNN-based models.This variant retains the bi-layer system that considers personalized item frequency while removing spatiotemporal intervals and the balanced sampler.

5.6 Ablation Study

The ablation study examines STAN’s spatial and temporal interval representations and balanced sampler, showing that these components substantially affect recall performance.

  • Ablation design: The ablation study removes different components from STAN, whose base configuration includes spatiotemporal intervals and a balanced sampler.The compared modules include spatial intervals, temporal intervals, and sampling components.
  • Sampling: 5-12% increase in recall rates is attributed to the balanced sampler in the ablation results.The paper describes the sampler as crucial for improving recommendation performance.
  • Spatiotemporal intervals: 4-8% increase in recall rates is reported when spatial distances and temporal intervals are added.These intervals explicitly represent correlations between non-consecutive visits and non-adjacent locations.
  • Component removal: Recall@5 and Recall@10 decrease drastically when neither spatiotemporal intervals nor the balanced sampler is used.The resulting −ALL model still outperforms previously reported RNN-based models and retains PIF consideration through its bi-layer system.

5.7 Stability Study

STAN remains stable across embedding dimensions and negative-sample settings, with performance changing little across broad hyperparameter ranges but degrading beyond a dataset-dependent sampling threshold.

  • Embedding Dimension: d=50 is the best embedding dimension, while performance changes by less than 6% on Gowalla and less than 2% on other datasets.When d exceeds 30, the performance change is less than 0.5%.
  • Number of Negative Samples: Fewer than 20 negative samples produce stable recommendations across all datasets.STAN is specifically insensitive to the number of negative samples in this range.
  • Number of Negative Samples: 121944 locations in Gowalla indicate that larger datasets require a larger optimal number of negative samples.The reported dataset size is associated with the need for more negative samples.
  • Number of Negative Samples: Recall drops drastically when the number of negative samples exceeds the threshold.The balanced sampler is reported as crucial for improving recommendation performance.

5.8 Interpretability Study

The interpretability study visualizes STAN’s attention correlations, showing how spatially distant and temporally non-consecutive visits can receive related representations.

  • Correlation Matrix: The correlation matrix represents each visited location’s weighted influence on another location.It is computed by applying softmax to query-key multiplication in the self-attention aggregation layer.
  • Correlation Matrix: Multiplying the correlation matrix by the original check-in embeddings updates the trajectory representations.The matrix values tend toward 1 or 0 after softmax.
  • Spatial and Temporal Correlation: Locations 3, 4, 5, and 6 are spatially distant restaurants that remain correlated because they are often visited at the same meal times.The example demonstrates spatial correlation beyond adjacent locations.
  • Spatial and Temporal Correlation: The restaurant visits are temporally non-consecutive yet are aggregated together by STAN.The example uses a sliced sparse trajectory with irrelevant visits removed.

6 CONCLUSION

STAN combines spatiotemporal attention with weighted trajectory representations and continuous spatial discretization to model relevant visits and improve next-location recommendation.

  • Conclusion: STAN uses a bi-attention system that aggregates spatiotemporal intervals before recalling the target.Its weighted trajectory representations also incorporate personalized item frequency.
  • Conclusion: STAN’s attention mechanism aggregates non-adjacent locations and non-consecutive visits through explicit spatiotemporal correlations.Figure 5 illustrates this mechanism through visited-location aggregation and a correlation matrix.
  • Conclusion: 9-17% is the reported improvement in recall rates over state-of-the-art baseline models.The comparison is described as unequivocally demonstrating STAN’s superiority.
  • Conclusion: Linear interpolation replaces hierarchical gridding to preserve continuous spatial distance while providing dense representations.This technique is integrated into STAN’s spatial discretization.
Loading 2102.04095v1…