<p>The widespread sharing of point-of-interest (POI) visitation experiences through location-based social networks (LBSNs) has led to massive mobility check-in data, making next POI recommendation a critical task for personalized services. Although existing deep learning-based methods have achieved impressive performance in this task, there exist several issues, including difficulty in recommending new POIs, limited exploitation of heterogeneous semantic relations, and insufficient consideration of user mobility intent. These issues ultimately constrain the quality of personalized recommendations. To overcome these issues, this study formulates the next POI recommendation framework from an intent-aware exploration perspective, and proposes a novel intent-aware recommendation model based on multi-relational heterogeneous graph, named SeekNew. Specifically, a multi-relational heterogeneous graph module and an intent-aware tree module are proposed and integrated to improve the accuracy of the next POI recommendation, especially the recommendation of new POIs, and a sample-wise loss weighting strategy is proposed to amplify the influence of rare samples for balanced model optimization. The proposed multi-relational heterogeneous graph module models multiple heterogeneous relations among entities in LBSNs for enhancing the quality of trajectory representations. The proposed intent-aware tree module hierarchically infers users’ next mobility intent for effectively narrowing the solution space of candidate POIs. Experimental results on check-in data from three cities demonstrate that SeekNew outperforms state-of-the-art baselines, with notable improvements in recommending new POIs.</p>