TL;DR
This paper introduces Bi-STDDP, a novel neural network framework designed to identify missing Point-of-Interest (POI) check-ins in human mobility data. By analyzing check-in sequences both before and after a missing timestamp and combining this with multi-scale user preferences, the model effectively "fills in the blanks" of sparse location histories, significantly outperforming traditional next-location prediction methods.
What Problem Does This Paper Address?
Location-Based Social Networks (LBSNs) like Foursquare and Gowalla generate massive amounts of POI check-in data, which is invaluable for understanding human mobility. However, real-world check-in data is notoriously messy. It suffers from severe data sparsity, missing geolocation information (e.g., due to poor GPS signals indoors or in tunnels), and even "unreal" check-ins caused by device failures or user cheating.
While substantial research has focused on predicting future locations (POI recommendation), very little work addresses imputing past missing data. Standard next-location models only look backward in time. To accurately identify a missing check-in from the past, a model needs to look bi-directionally—utilizing context from both before and after the missing event—while strictly respecting the physical constraints of time and space (e.g., a user cannot physically travel 100 miles in 5 minutes).
Methods
The authors propose the Bi-directional Spatial and Temporal Dependence and Users' Dynamic Preferences (Bi-STDDP) model. The architecture is split into two main components, as illustrated below:
-
Bi-directional Spatio-Temporal Dependence: Instead of treating space and time separately, the model couples them. It extracts a global spatial vector (measuring the geographical distance from the last known POI to all candidate POIs) and a local temporal interval (the time elapsed). It then uses an element-wise product to fuse them. This mathematically captures the physical constraint that short time intervals limit how far a user could have traveled. This is done for both the forward sequence (past) and backward sequence (future).
-
Users' Dynamic Preferences: User preferences change depending on the time of day and day of the week. Bi-STDDP encodes the target time into a 7-dimensional vector representing two scales: weekday vs. weekend, and five distinct daily time slots (morning, noon, afternoon, night, and late night). This temporal pattern is combined with latent user and POI embeddings through a multi-layer feed-forward network to capture evolving user tastes.
Finally, the spatio-temporal representations and dynamic preferences are mapped into the same coordinate space, and a Softmax layer outputs a probability distribution over all candidate POIs to identify the most likely missing location.
Datasets
The model was evaluated on three large-scale, real-world LBSN datasets:
- NYC: Foursquare check-ins in New York City over 10 months (April 2012 to February 2013).
- TKY: Foursquare check-ins in Tokyo over the same period.
- Gowalla: A global dataset collected from February 2009 to October 2010.
All three datasets exhibit extreme sparsity, with over 99.4% of potential user-POI interactions being unobserved.
Key Insights and Ideas
- The Power of the Future: Knowing where a user went after a missing check-in is just as valuable as knowing where they were before. Traditional sequential models (like standard RNNs or LSTMs) throw away this future context.
- Spatio-Temporal Coupling: Modeling space and time independently is insufficient for mobility. By using an element-wise product between spatial distance vectors and temporal intervals, the network naturally learns physical travel constraints via gradient descent.
- Locality Dominates History: Interestingly, the authors found that a context window of $w=1$ (only looking at the immediate previous and immediate next check-ins) yielded the best performance. Looking further back or forward into a user's history actually introduced noise and degraded performance, proving that missing data imputation is highly dependent on immediate local context.
Key Results
The Bi-STDDP model was compared against standard baselines, including counting-based methods, metric embeddings (PRME), and advanced sequential neural networks (LSTM, GRU, ST-RNN, PACE).
- Substantial Accuracy Gains: On the NYC dataset, Bi-STDDP achieved a 33.87% improvement in Recall@1 compared to the best-performing baseline, ST-RNN. Similar dominant performance was observed across TKY and Gowalla datasets.
- Forward-Compatibility: Even when stripped of its backward-looking component to perform standard next-location prediction (denoted as F-STDDP), the model still outperformed all existing state-of-the-art recommendation baselines.
The impact of hyperparameter tuning (embedding dimensions and hidden units) on these metrics is visualized below:
Limitations and Future Work
While the paper demonstrates excellent results, a few limitations open doors for future research:
- Contextual Simplicity: The model relies purely on coordinates and timestamps. It does not incorporate richer semantic data, such as POI categories (e.g., "restaurant" vs. "movie theater") or textual data from user comments/tweets, which could further refine preference matching.
- Scalability: Computing a global spatial distance vector against all candidate POIs can become computationally expensive as the number of POIs grows into the millions (as seen in the Gowalla dataset). Future iterations might require candidate pre-filtering or hierarchical spatial indexing to scale efficiently.
Summary updated