Research map / Federated learning and privacy / Differential privacy
Differentially Private Graph Diffusion with Applications in Personalized PageRanks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a noisy graph diffusion framework with per-iteration Laplace noise and degree-based clipping that gives edge-level (personalized) RDP for PPR, using a new infinity-Wasserstein tracking analysis of privacy amplification by iteration.
Problem
Releasing graph diffusion vectors such as personalized PageRank can leak edge (link) information, and output-perturbation DP methods give poor utility-privacy tradeoffs; the PABI analysis was limited to Gaussian noise and relied on loose diameter bounds.
Approach
Inject Laplace noise at every diffusion iteration (not only at output), clip diffusion values by node degree to limit sensitivity from low-degree nodes, and analyze privacy via PABI with a dual-noise splitting and an infinity-Wasserstein distance tracking bound that replaces the diameter-based bound.
Key results
- On real-world graphs, the noisy PPR outperforms DP-PushFlowCap and Edge-Flipping on NDCG@100 and Recall@100 across privacy budgets epsilon from 0.01 to 1, especially for epsilon <= 0.5.
- The degree-based thresholding beats the graph-independent clipping by about 0.15 to 0.2 NDCG for epsilon from 0.1 to 3.
- The infinity-Wasserstein tracking gives orders-of-magnitude smaller diameter than the l1-projection or thresholding-induced diameter bounds, and needs about 10x smaller noise scale than the composition theorem.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use noisy graph diffusion instead of DP-PUSHFLOWCAP and Edge-Flipping | Noisy graph diffusion for PPR · BlogCatalog, Flickr, TheMarker | NDCG@100 | Helped |
| Use noisy graph diffusion instead of DP-PUSHFLOWCAP and Edge-Flipping | Noisy graph diffusion for PPR · BlogCatalog, Flickr, TheMarker | Recall@100 | Helped |
| Use degree-based thresholding instead of graph-independent uniform thresholding (ablation) | Noisy graph diffusion for PPR · BlogCatalog | NDCG: 0.15 to 0.2 | Helped |
| Use ∞-Wasserstein distance tracking instead of diameter-based bounds (ablation) | Noisy graph diffusion for PPR · BlogCatalog | NDCG | Helped |
| Use Laplace noise instead of Gaussian noise (ablation) | Noisy graph diffusion for PPR · BlogCatalog | ranking performance: approximately 0.05 | Helped |
| Calibrate noise with the proposed theorem instead of the standard RDP composition theorem (ablation) | Noisy graph diffusion for PPR · BlogCatalog | noise scale: 10 times smaller | Helped |
| Add projection onto the unit ℓ1 ball after each Laplace-noise step (ablation) | Noisy graph diffusion for PPR · PPR ranking tasks | utility | Helped |
| Vary the threshold parameter η across 1 × 10^{-10} to 1 × 10^{-4} (ablation) | Noisy graph diffusion for PPR · BlogCatalog, Flickr, TheMarker | NDCG | Helped |
Surprising findings
- Gaussian noise is shown to be suboptimal to Laplace noise for graph diffusion in l1 space, with about 0.05 NDCG gap in strong privacy regime.
- Edge-Flipping cannot be run on Flickr within 12 hours per trial.
Limitations
- Evaluated mainly on PPR diffusion; other diffusions such as heat kernel are left to future work.
- Only edge-level privacy is considered; node-level DP is not addressed.
- Bounds depend on a threshold parameter eta that must be tuned per dataset.
Experimental setup
Datasets: BlogCatalog Flickr TheMarker
Benchmarks: BlogCatalog Flickr TheMarker
Metrics: NDCG@100 Recall@100 personalized edge-level (epsilon, delta)-DP
Baselines: DP-PushFlowCap Edge-Flipping
Builds on: Privacy Amplification by Iteration (Feldman et al.) Altschuler and Talwar PABI bound Epasto et al. DP PPR (DP-PushFlowCap) Renyi differential privacy
Closest papers by meaning
- Differentially Private Decentralized Learning with Random Walks (ICML 2024 · similarity 0.86)
- On Differential Privacy for Adaptively Solving Search Problems via Sketching (ICML 2025 · similarity 0.85)
- On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.85)
- Poincaré Differential Privacy for Hierarchy-Aware Graph Embedding (AAAI 2024 · similarity 0.85)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.85)
- Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.