Graph Neural Networks have achieved tremendous success in modeling complexgraph data in a variety of applications. However, there are limited studiesinvestigating privacy protection in GNNs. In this work, we propose a learningframework that can provide node privacy at the user level, while incurring lowutility loss. We focus on a decentralized notion of Differential Privacy,namely Local Differential Privacy, and apply randomization mechanisms toperturb both feature and label data at the node level before the data iscollected by a central server for model training. Specifically, we investigatethe application of randomization mechanisms in high-dimensional featuresettings and propose an LDP protocol with strict privacy guarantees. Based onfrequency estimation in statistical analysis of randomized data, we developreconstruction methods to approximate features and labels from perturbed data.We also formulate this learning framework to utilize frequency estimates ofgraph clusters to supervise the training procedure at a sub-graph level.Extensive experiments on real-world and semi-synthetic datasets demonstrate thevalidity of our proposed model.