# Differentially Private Graph Diffusion with Applications in Personalized PageRanks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 63 references that are in the map.
- First posted on arXiv 22 Jun 2024.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection](https://mlsanity.com/paper/1905.10881/) (2019)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Private Graph Data Release: A Survey](https://mlsanity.com/paper/2107.04245/) (2021)
- [Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank](https://mlsanity.com/paper/2207.06944/) (2022)
- [ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2304.08928/) (2023)
- [Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protection](https://mlsanity.com/paper/2307.06422/) (2023)
- [Privacy in Targeted Advertising: A Survey](https://mlsanity.com/paper/2009.06861/) (2020)
- [Graph Neural Diffusion Networks for Semi-supervised Learning](https://mlsanity.com/paper/2201.09698/) (2022)
- [Privacy-Preserving Analytics on Decentralized Social Graphs: The Case of Eigendecomposition](https://mlsanity.com/paper/2206.09388/) (2022)

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

- [Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness](https://mlsanity.com/paper/2410.01068/) (2024)
- [Privately Learning from Graphs with Applications in Fine-tuning Large Language Models](https://mlsanity.com/paper/2410.08299/) (2024)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)
- [Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States](https://mlsanity.com/paper/2506.00158/) (2025)

## Abstract (arXiv)

Graph diffusion, which iteratively propagates real-valued substances among the graph, is used in numerous graph/network-involved applications. However, releasing diffusion vectors may reveal sensitive linking information in the data such as transaction information in financial network data. However, protecting the privacy of graph data is challenging due to its interconnected nature. This work proposes a novel graph diffusion framework with edge-level differential privacy guarantees by using noisy diffusion iterates. The algorithm injects Laplace noise per diffusion iteration and adopts a degree-based thresholding function to mitigate the high sensitivity induced by low-degree nodes. Our privacy loss analysis is based on Privacy Amplification by Iteration (PABI), which to our best knowledge, is the first effort that analyzes PABI with Laplace noise and provides relevant applications. We also introduce a novel Infinity-Wasserstein distance tracking method, which tightens the analysis of privacy leakage and makes PABI more applicable in practice. We evaluate this framework by applying it to Personalized Pagerank computation for ranking tasks. Experiments on real-world network data demonstrate the superiority of our method under stringent privacy conditions.