Traditional location service recommendation schemes lack consideration of user preferences and potential social relationships， resulting in recommendation results that fail to meet user’s personalized needs. Graph Neural Networks （GNNs） are widely used in the field of location recommendation by its good graph structure data processing capabilities. However， the previous studies’ centralized data paradigm is easy to lead to the issue of location privacy leakage. Therefore， a Location Privacy-preserving Recommendation scheme based on Federated Graph Neural Network （FedGNN-LPR） was proposed. Firstly， the user’s social relationship embedding and Point-Of-Interest （POI） embedding were learned through the graph attention network. Secondly， a POI-based pseudo labelling model was developed to predict the number of user visits to an unknown location， so as to protect user privacy and alleviate the cold-start problem. Finally， a clustered federated learning strategy based on differential privacy was proposed to protect client interaction data and solve the problem of data heterogeneity. Experiments were conducted on two publicly available real datasets， and the results demonstrate that the proposed scheme is reduced by 7.89% and 9.29% respectively compared to the Federated Averaging （FedAvg） algorithm， and 2.32% and 2.75% respectively compared to the FL+HC algorithm， in terms of Mean Absolute Error （MAE） and Root Mean Square Error （RMSE）. Moreover， it is shown that FedGNN-LPR exhibits better performance on federated learning location recommendation. Therefore， FedGNN-LPR not only protects user location privacy， but also improves location recommendation performance.