# Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank

arXiv: https://arxiv.org/abs/2207.06944 · HTML: https://mlsanity.com/paper/2207.06944/

## Key facts

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

## Builds on (most cited first, 9 of 9)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Differentially Private Correlation Clustering](https://mlsanity.com/paper/2102.08885/) (2021)
- [Differentially Private Algorithms for Graphs Under Continual Observation](https://mlsanity.com/paper/2106.14756/) (2021)
- [InstantEmbedding: Efficient Local Node Representations](https://mlsanity.com/paper/2010.06992/) (2020)

## Built on by (most cited first, 12 of 12)

- [Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protection](https://mlsanity.com/paper/2307.06422/) (2023)
- [DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy](https://mlsanity.com/paper/2210.04442/) (2022)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Differentially Private Graph Diffusion with Applications in Personalized PageRanks](https://mlsanity.com/paper/2407.00077/) (2024)
- [Privacy-Preserving Graph Embedding based on Local Differential Privacy](https://mlsanity.com/paper/2310.11060/) (2023)
- [Fast Online Node Labeling for Very Large Graphs](https://mlsanity.com/paper/2305.16257/) (2023)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Privately Learning from Graphs with Applications in Fine-tuning Large Language Models](https://mlsanity.com/paper/2410.08299/) (2024)
- [AdvSGM: Differentially Private Graph Learning via Adversarial Skip-gram Model](https://mlsanity.com/paper/2503.21426/) (2025)
- [Adaptive Differentially Private Structural Entropy Minimization for Unsupervised Social Event Detection](https://mlsanity.com/paper/2407.18274/) (2024)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)

## 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.