Negative Sampling in Next-POI Recommendations: Observation, Approach, and Evaluation

To recommend the points of interest (POIs) that a user would check-in next, most deep-learning (DL)-based existing studies have employed random negative (RN) sampling during model training. In this paper, we claim and validate that, as the training proceeds, such an RN sampling in reality performs as sampling easy negative (EN) POIs (i.e., EN sampling) that a user was highly unlikely to check-in at her check-in time point. Furthermore, we verify that EN sampling is more disadvantageous in improving the accuracy than sampling hard negative (HN) POIs (i.e., HN sampling) that a user was highly likely to check-in. To address this limitation, we present the novel concept of the Degree of Positiveness (DoP), which can be formulated by two factors: (i) the degree to which a POI has the characteristics preferred by a user; (ii) the geographical distance between a user and a POI. Then, we propose a new model-training scheme based on HN sampling by using DoP. Using real-world datasets (i.e., NYC, TKY, and Brightkite), we demonstrate that all the state-of-the-art models trained by our scheme showed dramatic improvements in accuracy by up to about 82.8%.