Beyond Long Tail POIs: Transition-Centered Generalization for Human Mobility Prediction
Dingyang Lyu, Zhengjia Xu, Jey Han Lau, Jianzhong Qi · 2026
Read Beyond Long Tail POIs: Transition-Centered Generalization for Human Mobility Prediction by Dingyang Lyu, Zhengjia Xu, Jey Han Lau, Jianzhong Qi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05771.txt.
Introduction
Predicting where someone goes next usually fails on rarely visited places. Dingyang Lyu, Zhengjia Xu, Jey Han Lau, and Jianzhong Qi argue the deeper problem is transitions: many failures involve popular places reached by rare or unseen moves. A destination can be famous while the journey to it is nearly unique.
They formulate mobility prediction as compositional generalization over transitions. Models must assemble known movement patterns into novel source-destination pairs. The reframing shifts attention from the long tail of places to the long tail of journeys, where they show much of the error actually lives.
Catalog record
| CREATOR | Dingyang Lyu, Zhengjia Xu, Jey Han Lau, Jianzhong Qi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05771
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Long Tail POIs: Transition-Centered Generalization for Human Mobility Prediction Dingyang Lyu, Zhengjia Xu, Jey Han Lau, Jianzhong Qi Abstract Human mobility prediction forecasts a user’s next Point of Interest (POI) from historical trajectories, supporting applications from recommendation to urban planning. Recent studies have recognized the problem with long-tail POIs in human mobility prediction, which are POIs with few visit records, making new visits to such POIs difficult to predict. Our analysis shows that many predictions fail even for visits to popular POIs. The underlying cause is often transition-level sparsity: the corresponding source–destination transition appears rarely, or never appears, in the training set. We therefore argue that a core bottleneck in human mobility prediction lies in transition-level long-tail generalization. We formulate this problem as compositional generalization and propose a t R ansition r E construction framework for C ompositional gener A lization in next- P OI prediction ( RECAP ). RECAP reconstructs long-tail transitions from two generalizable signals: multi-hop transitivity in the global transition graph and revisit evidence from a user’s historical trajectory. It further uses warm-transition holdout training to discourage memorization of frequent transitions and encourage generalization from transferable signals. Experiments on multiple real-world datasets show that RECAP consistently improves prediction accuracy, with clear gains on tail transitions. 1 Introduction Human mobility prediction is a fundamental task in urban computing and location-based services [ 5 , 35 , 33 ] . Predicting the next Point of Interest (POI) a user will visit from historical check-ins supports applications such as location-based recommendation, trip planning, and urban planning [ 21 , 24 ] . Progress in this area has been driven by stronger sequence encoders, such as the shift from Recurrent Neural Networks (RNNs) [ 5 , 35 ] to Attention models [ 21 , 8 , 6 ] , and by the evolution from single-sequence modeling to graph-enhanced spatio-temporal modeling that captures collaborative movement patterns across users [ 22 , 37 , 31 , 28 , 19 ] . Recent studies highlight the problem caused by long-tail POIs [ 33 , 30 ] , where a small set of POIs receives most visits while a large fraction of POIs remain infrequent, and have proposed training strategies that reduce the dominance of popular POIs and let rarely visited POIs borrow signals from semantically related POIs. Figure 1 : An example of prediction failure of LoTNext on a popular destination due to an unseen transition on NYC. Figure 2 : Accuracy aligns more with transition frequency than destination frequency: n denotes the sample count in each frequency bin on NYC. Prior works have mainly studied the long-tail problem at the POI level [ 33 , 30 , 41 ] . We observe that prediction failures can occur even for highly popular POIs. As shown in Figure 2 , LoTNext [ 33 ] , a state-of-the-art (SOTA) long-tail model, fails to predict Bus Station despite its high visit frequency in the NYC [ 36 ] training set, ranking at the 0.99 percentile. In this case, the ground-truth transition Coffee Shop \rightarrow Bus Station is absent from the training set, while the incorrectly predicted transition Coffee Shop \rightarrow Bakery appears multiple times. This example exposes a transition-level failure mode: the destination POI is frequent, yet its pairing with the current source POI lacks direct training support. Figure 2 further shows that prediction accuracy on test transitions is more closely associated with their occurrence frequency in the training set than with the destination POI popularity. The counts of pairs in different transition frequency bins ( n in Figure 2 a) also reveal a highly long-tailed transition distribution: a large fraction of test transitions appear only a few times in training, or never appear at all (i.e., transition frequency =0 ). Transitions that appear frequently in training have substantially higher accuracy, whereas low-frequency or unseen transitions are much more difficult to predict. These findings motivate a shift of the long-tail formulation from the item (i.e., POI) level to the transition level, making generalization over long-tail transitions a central task. Challenges. The transition-level long-tail problem can be viewed as a compositional generalization problem. Since training trajectories (i.e., POI visit sequences) cover only a sparse subset of possible POI-to-POI transitions, many tail transitions must be inferred from related evidence, such as inferred user preferences from their historical trajectory or collaborative signals from other users. The key difficulty is therefore to compose a plausible source-destination pairing when the exact POI-to-POI transition has limited direct supervision. This raises two coupled challenges. (1) How to introduce generalizable signals for tail transitions: The prediction model needs signals that transfer beyond observed transitions. For many rare or unseen transitions, the target POI may have appeared in the user’s history. What is new is its combination with a different source POI under the current context. We refer to these cases as user history revisits . Others are transitive completions : the target POI does not appear in the user’s visible history, so recovery must rely on cross-user collaborative signals. (2) How to encourage the prediction model to use generalizable signals rather than memorizing frequent transitions: The skewed transition distribution means that frequent transitions dominate the training objective. In this compositional-generalization setting, model capacity can be spent fitting frequent transitions (i.e., head transitions ) that transfer poorly to tail transitions [ 16 ] . This leads to shortcut bias, where popularity and head-transition statistics provide sufficient predictive cues for many training cases and reduce the incentive to learn more transferable rules. Training must therefore discourage shortcut solutions and encourage tail-transition reconstruction from generalizable signals. Our Contributions. We address these challenges and propose a t R ansition r E construction framework for C ompositional gener A lization in next- P OI prediction ( RECAP ). RECAP reconstructs transition signals from two explicit evidence sources. For user history revisits, it exposes revisit candidates from the user’s historical trajectory and calibrates them under the current context. For transitive completions, it uses multi-hop paths in the transition graph to connect the current source POI with plausible POIs through intermediate POIs. We further use warm-transition holdout training to reduce reliance on memorized head transitions. To our knowledge, this is the first work in next POI prediction that explicitly models the transition-level long-tail problem. Our main contributions are as follows. • We formulate next POI prediction from a transition-level perspective and identify the transition long-tail problem, where test transitions are rare or unseen in training even when their source or destination POIs have been observed. • We introduce RECAP, a transition-centered model that combines user-history revisit signals, multi-hop transition-graph signals, and warm-transition holdout training to reconstruct tail transitions. • Experimental results on three real-world datasets show that RECAP substantially and consistently outperforms SOTA methods, with an average improvement of 38.61% on tail transitions. 2 Related Work Next POI Prediction. Existing methods can be grouped into sequential and graph-based. Sequential methods treat each user’s check-ins as an ordered trajectory and learn POI visit (i.e., check-in) patterns with RNN or attention-based models. ST-RNN [ 17 ] uses temporal intervals and geographical distances to guide recurrent transitions, DeepMove [ 5 ] adds historical attention to recurrent trajectory encoding, Flashback [ 35 ] and REPLAY