Recommenders that predict a person's next location learn by contrast. They pull the model's summary of a user's history toward the place the user actually visited next, and push it away from places they did not visit. In mobility data that second step is often wrong. When someone visits one of three adjacent coffee shops in a plaza at 3pm, the other two are not evidence of dislike. They are substitutes the user simply did not pick. Pushing them away teaches the model a false boundary. The damage is worst for users with only a handful of visits, where every gradient counts.
This proposal uses an old tool from mobility analysis to decide which "unvisited" places are real negatives. Spatio-temporal density clustering groups location pings into zones that are dense in both space and time; its classical use is detecting where people stop. Here it runs over all users' training check-ins to find substitute sets, meaning places that are density-connected at a given time of day. Those places are softly removed from the negative pool. A second physical test, a travel-speed bound, certifies the opposite case: places that look similar to the target in embedding space but could not have been reached in the elapsed time. These are safe hard negatives. The model therefore gets a two-sided physical rule for which contrasts to trust. The question is whether this rule beats much simpler masking heuristics, and whether its gains concentrate on sparse users.
Core Claim
In contrastive next-place recommendation, the negative pool can be curated by physics rather than by the model's own similarity scores. The claim has two halves. First, places that fall in the same space-time density cluster as the true next place should be down-weighted as negatives. Second, places that the model finds similar but that a speed bound rules out should be up-weighted as hard negatives. We claim this two-sided curation improves ranking for short-history users more than three alternatives: a fixed distance radius, a category-plus-radius rule, or latent-space false-negative detection. The novelty is the source of the false-negative signal. It comes from density structure in space and time-of-day, plus reachability, rather than from latent prototypes or popularity. It is also used inside the contrastive objective rather than as offline cleaning.
Grounding in Prior Work
Several papers motivate the problem. ProGCL shows that in graph contrastive learning the negatives a model finds hardest are disproportionately false negatives. Graph Debiased Contrastive Learning with Joint Representation Clustering argues that pushing apart same-class samples creates gradients that conflict with the pull toward true positives. Both establish that hard-negative mining based on model similarity is unreliable, which is exactly why we want an outside source of truth.
Three sequential-recommendation methods attack false negatives with signals internal to the model. ICLRec clusters sequence embeddings with K-means into "intent" prototypes and avoids pushing apart sequences that share a prototype. UFNRec flags unvisited items that the model persistently scores highly and relabels them as positives, using a teacher network built from an average of past weights. DCRec attributes false negatives to popularity and conformity and down-weights them accordingly. All three were built for item-ID catalogs such as Amazon and Yelp, and none can see coordinates or elapsed time. ICLRec and UFNRec also rely on the model's own judgments, which risks confirming the model's existing errors when histories are short. We test that risk directly rather than assume it.
On the mobility side, iPCM is the closest work combining clustering with next-place prediction. It clusters place coordinates into regions with K-means, clusters hours into periods, and rescales output scores using per-user region and period frequencies. It is purely supervised. Its negatives include unvisited places in the same region, and its regions are fixed before training. Enhancing next POI recommendation via multi-graph modeling and multi-granularity contrastive learning adds contrastive views over graphs but does not treat nearby or functionally equivalent places as possible false negatives.
Our method borrows from two further sources. The dual space-and-duration thresholds of ST-DBSCAN-style clustering come from Urban Resident Travel Survey Method Based on Cellular Signaling Data, which also shows that purely spatial clustering confuses recurring transit with stays. The quasi-stationary assumption, that meaningful activity stays spatially bounded over a time window, comes from Short-Term Spatio-Temporal Clustering of Sporadic and Concurrent Events. The speed bound for pruning impossible movements follows Mobility Sequence Extraction and Labeling Using Sparse Cell Phone Data.
Research Program
Substitute sets. We build these from training check-ins only. Each check-in becomes a point in (latitude, longitude, time-of-day, with time-of-day treated as a circular variable). We run density clustering with a spatial radius and a time-of-day window. The neighbor-count threshold adapts locally, so dense downtown blocks yield tight clusters and sparse suburbs yield wide ones, which addresses the rigid-threshold problem noted in the mobility literature. For a target place $p$ visited at time-of-day $t$, the substitute set $C(p,t)$ contains the other places whose check-ins at that time share $p$'s cluster. Membership is soft: it is the fraction of $p$'s check-ins near $t$ that are density-connected to the other place's check-ins.
Reachability. For a training step whose previous check-in was at location $\ell$ and whose next check-in occurs $\Delta t$ later, a place $j$ is unreachable if $d(\ell, j) > v_{\max}\Delta t$. Here $d$ is great-circle distance and $v_{\max}$ is a city-level speed cap, estimated as a high quantile of observed consecutive-check-in speeds. The cap is used only during training, so no future information leaks into inference.
Objective. With $h$ the sequence encoder's output, $s(h,j)$ its dot-product score with place $j$, and $\tau$ a temperature, the next-place loss is
$$ \mathcal{L} = -\log \frac{e^{s(h,p)/\tau}}{e^{s(h,p)/\tau} + \sum_{j \in \mathcal{N}} w_j \, e^{s(h,j)/\tau}}, \qquad w_j = \big(1-\mu_{C(p,t)}(j)\big)\,\big(1 + \beta\,\mathbb{1}[j \text{ unreachable and } j \in \mathrm{top}_k(h)]\big), $$
The terms are defined as follows:
- $\mathcal{N}$ is a sampled candidate set.
- $\mu_{C(p,t)}(j)\in[0,1]$ is $j$'s soft membership in the substitute set.
- $\mathrm{top}_k(h)$ is the $k$ places the current model scores highest.
- $\beta\ge 0$ controls how strongly certified hard negatives are emphasized.
A standard sequence-level contrastive term in the style of CL4SRec is added unchanged, so any gain can be traced to the negative weights. The backbone is a SASRec-style Transformer with time and location features, kept identical across all methods.
Sparse-user regime. The standard Foursquare protocol removes users with fewer than 20 check-ins, which hides the regime we care about. We therefore also create a truncated-history split. For a random 30% of users, training histories are cut to 3, 5, or 10 check-ins while their test targets are kept. Results are reported per stratum.
Baselines
Do-nothing reference. This is the same backbone trained with uniform random negatives and the CL4SRec sequence term, with $w_j \equiv 1$. Every other row is a delta against it.
Strongest existing method. This is iPCM, the only method in the file built for these exact datasets that combines spatial and temporal clustering with sequence modeling. It reports average gains of 8.29% over GETNext and 5.88% over AGRAN across Acc@1/5/10 and MRR. No reported result found on Lacuna for iPCM's absolute Acc@k or MRR on NYC, TKY, SIN, or OSK, so we will reproduce it under our splits. We will also report the published relative gaps as a sanity check on the reproduction. Because iPCM's score-rescaling module is orthogonal to how negatives are chosen, we also run iPCM with our weights added. Beating iPCM means a higher Acc@5 and MRR than our reproduction on at least three of four cities. For the combined variant, it means improving over plain iPCM in the 3- and 5-check-in strata.
False-negative methods from item recommendation. These are ICLRec, UFNRec, and DCRec. Each is ported onto the same backbone and given place IDs plus our time features. They are the direct competitors for the "which negatives to trust" question.
Ablations. Two ablations isolate the key ingredient. One keeps only the substitute down-weighting ($\beta=0$). The other keeps only the certified hard negatives ($\mu\equiv0$). A third replaces density clusters with iPCM's static K-means regions to test whether density structure in time-of-day matters.
Fairness. All methods get the same data splits, the same negative-sample count, the same embedding size, and a matched hyperparameter search of 30 trials on validation MRR. Results are averaged over five seeds.
Why not just…?
Why not just mask every unvisited place within a fixed radius of the target, perhaps restricted to the same category? This is the real threat, and the proposal is built around it. Foursquare provides categories, and "same category within 200m" is a one-line substitute rule. Nothing in the file shows such a rule failing. Density clusters should win for two reasons. They adapt radius to local density, and they depend on time-of-day, so a bar and a café can be substitutes at night but not at noon. Both effects are testable. We run radius-only and radius-plus-category masking, with the radius tuned per city on validation. If either matches the density version within seed noise in the sparse strata, the clustering component is not earning its place. In that case we would report the simpler rule and keep only the reachability half.
Why not just use the model's own similarity to find false negatives, as ICLRec or UFNRec do? Their reported gains are on item catalogs: ICLRec reports 7.47% to 33.33% over baselines including CL4SRec, and UFNRec reports 0.63% to 12.07%. Neither result comes from location data. ProGCL's finding that model-similar negatives are often false is the core reason to distrust model-based detection. The file gives no direct evidence about how these methods behave on very short histories. We measure it two ways. The first is per-stratum accuracy. The second is a diagnostic: for each method's flagged false negatives, the precision against held-out substitution, meaning places the same user visits in the same time-of-day slot in other weeks.
Why not just run ST-DBSCAN offline and feed cleaned sequences to a standard recommender? On Foursquare, check-ins are already discrete places. Offline stay detection would mostly delete short check-ins. It would not change which places are treated as negatives, which is where the collision happens. We include this two-stage pipeline as a baseline. It should help little, and if it helps as much as our method, our diagnosis of the problem is wrong.
Why not drop negatives entirely with a non-contrastive objective? A Non-Contrastive Learning Framework for Sequential Recommendation with Preference-Preserving Profile Generation removes negative sampling. That works for the sequence-level term, but the next-place ranking loss still needs negatives. We swap our sequence term for theirs as a secondary check that our gains do not depend on the sequence-level loss.
Proposed Experiments
Data and metrics. We use Foursquare NYC, TKY, SIN, and OSK with iPCM's preprocessing and 80/10/10 split, plus our truncated-history split. Metrics are Acc@1, Acc@5, Acc@10, and MRR, reported overall and by history-length stratum.
Check 1: does collision exist? Before any training comparison, we measure on the do-nothing baseline what fraction of sampled negatives fall in the target's substitute set. We also measure how often those places are the user's own held-out substitutes. If the fraction is negligible, the project stops there.
Check 2: where do the gains land? We expect the improvement over the do-nothing reference to shrink as history length grows. A flat or reversed pattern would contradict the sparsity story even if overall accuracy improves.
Check 3: is density better than distance? This is the radius and category comparison described above.
Check 4: what does each half contribute? These are the two ablations, testing whether substitute down-weighting and certified hard negatives add up or whether one carries the effect.
Check 5: does the result survive iPCM? iPCM with our weights must beat plain iPCM on sparse users. Otherwise iPCM's frequency rescaling already captures what our negative curation provides.
References
- ProGCL: Rethinking Hard Negative Mining in Graph Contrastive Learning
- Graph Debiased Contrastive Learning with Joint Representation Clustering
- Intent Contrastive Learning for Sequential Recommendation
- UFNRec: Utilizing False Negative Samples for Sequential Recommendation
- Debiased Contrastive Learning for Sequential Recommendation
- Integrating Personalized Spatio-Temporal Clustering for Next POI Recommendation
- Enhancing next POI recommendation via multi-graph modeling and multi-granularity contrastive learning
- Urban Resident Travel Survey Method Based on Cellular Signaling Data
- Short-Term Spatio-Temporal Clustering of Sporadic and Concurrent Events
- Mobility Sequence Extraction and Labeling Using Sparse Cell Phone Data
- Contrastive Learning for Sequential Recommendation
- A Non-Contrastive Learning Framework for Sequential Recommendation with Preference-Preserving Profile Generation