  Graph embedding has become a powerful tool for learning latent
representations of nodes in a graph. Despite its superior performance in
various graph-based machine learning tasks, serious privacy concerns arise when
the graph data contains personal or sensitive information. To address this
issue, we investigate and develop graph embedding algorithms that satisfy local
differential privacy (LDP). We introduce a novel privacy-preserving graph
embedding framework, named PrivGE, to protect node data privacy. Specifically,
we propose an LDP mechanism to obfuscate node data and utilize personalized
PageRank as the proximity measure to learn node representations. Furthermore,
we provide a theoretical analysis of the privacy guarantees and utility offered
by the PrivGE framework. Extensive experiments on several real-world graph
datasets demonstrate that PrivGE achieves an optimal balance between privacy
and utility, and significantly outperforms existing methods in node
classification and link prediction tasks.
