Abstract: To address the insufficient data issue and the high computational cost of existing algorithms, we present a new TUL model based on graph neural network (GNN). More specifically, the check-in graph is constructed using the check-in points in trajectories, based on which we use a graph neural network to learn the check-in embeddings in the graph, which could preserve users' check-in preference and spatio-temporal visiting patterns in a graph representation learning manner. Subsequently, the check-in representations in the trajectory are fed into a recurrent neural network, followed by a fully connected network, to learn the sequential dependencies of visits while distinguishing different users' trajectories. Experimental evaluations conducted on benchmark datasets show that our method can better capture the underlying moving patterns of users' trajectories more effectively compared with the previous TUL algorithms. Furthermore, the user linking accuracy and learning efficiency are significantly improved compared with the existing methods.