mlsanityData to 7 Oct 2026

Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank

arXiv 2207.06944 ↗First posted 14 Jul 2022cs.CR cs.LG cs.SIcited by 12

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 9 of its 35 references that are in the map. First posted on arXiv 14 Jul 2022.

Builds on

9 of 35 references.

References · 9

  1. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  2. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  3. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  4. 2020Scaling Graph Neural Networks with Approximate PageRankcited by 174
  5. 2018VERSE: Versatile Graph Embeddings from Similarity Measurescited by 54
  6. 2014PageRank beyond the Webcited by 51
  7. 2021Differentially Private Correlation Clusteringcited by 13
  8. 2021Differentially Private Algorithms for Graphs Under Continual Observationcited by 12
  9. 2020InstantEmbedding: Efficient Local Node Representationscited by 9

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 4; 2024: 4; 2025: 3.

12 papers.

  1. 2023Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protectioncited by 12
  2. 2022DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacycited by 10
  3. 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guaranteescited by 5
  4. 2024Differentially Private Graph Diffusion with Applications in Personalized PageRankscited by 4
  5. 2023Privacy-Preserving Graph Embedding based on Local Differential Privacycited by 3
  6. 2023Fast Online Node Labeling for Very Large Graphscited by 2
  7. 2024Faster Local Solvers for Graph Diffusion Equationscited by 2
  8. 2024Privately Learning from Graphs with Applications in Fine-tuning Large Language Modelscited by 1
  9. 2025AdvSGM: Differentially Private Graph Learning via Adversarial Skip-gram Modelcited by 1
  10. 2024Adaptive Differentially Private Structural Entropy Minimization for Unsupervised Social Event Detectioncited by 0
  11. 2025Differentially Private and Scalable Estimation of the Network Principal Componentcited by 0
  12. 2025Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiencycited by 0