  Personalized PageRank (PPR) is a fundamental tool in unsupervised learning of
graph representations such as node ranking, labeling, and graph embedding.
However, while data privacy is one of the most important recent concerns,
existing PPR algorithms are not designed to protect user privacy. PPR is highly
sensitive to the input graph edges: the difference of only one edge may cause a
big change in the PPR vector, potentially leaking private user data.
  In this work, we propose an algorithm which outputs an approximate PPR and
has provably bounded sensitivity to input edges. In addition, we prove that our
algorithm achieves similar accuracy to non-private algorithms when the input
graph has large degrees. Our sensitivity-bounded PPR directly implies private
algorithms for several tools of graph learning, such as, differentially private
(DP) PPR ranking, DP node classification, and DP node embedding. To complement
our theoretical analysis, we also empirically verify the practical performances
of our algorithms.
