# Differentially Private Decentralized Learning with Random Walks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 54 references that are in the map.
- First posted on arXiv 12 Feb 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Inverting Gradients -- How easy is it to break privacy in federated learning?](https://mlsanity.com/paper/2003.14053/) (2020)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging](https://mlsanity.com/paper/2206.05091/) (2022)
- [Differentially Private Distributed Optimization](https://mlsanity.com/paper/1401.2596/) (2014)
- [On the (In)security of Peer-to-Peer Decentralized Machine Learning](https://mlsanity.com/paper/2205.08443/) (2022)
- [Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms](https://mlsanity.com/paper/1806.02246/) (2018)
- [Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Case](https://mlsanity.com/paper/1802.04085/) (2018)
- [A principled framework for the design and analysis of token algorithms](https://mlsanity.com/paper/2205.15015/) (2022)
- [Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible](https://mlsanity.com/paper/1706.03316/) (2017)
- [Network Shuffling: Privacy Amplification via Random Walks](https://mlsanity.com/paper/2204.03919/) (2022)
- [From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning](https://mlsanity.com/paper/2302.12559/) (2023)
- [Straggler-Resilient Differentially-Private Decentralized Learning](https://mlsanity.com/paper/2212.03080/) (2022)
- [Information-Theoretic Privacy in Distributed Average Consensus](https://mlsanity.com/paper/1809.01794/) (2018)

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

- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy](https://mlsanity.com/paper/2510.19934/) (2025)
- [Differential Privacy Analysis of Decentralized Gossip Averaging under Varying Threat Models](https://mlsanity.com/paper/2505.19969/) (2025)
- [DICE: Data Influence Cascade in Decentralized Learning](https://mlsanity.com/paper/2507.06931/) (2025)
- [Unified Privacy Guarantees for Decentralized Learning via Matrix Factorization](https://mlsanity.com/paper/2510.17480/) (2025)
- [Fedivertex: a Graph Dataset based on Decentralized Social Networks for Trustworthy Machine Learning](https://mlsanity.com/paper/2505.20882/) (2025)
- [ImprovDML: Improved Trade-off in Private Byzantine-Resilient Distributed Machine Learning](https://mlsanity.com/paper/2506.15181/) (2025)
- [Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning](https://mlsanity.com/paper/2511.19513/) (2025)

## Abstract (arXiv)

The popularity of federated learning comes from the possibility of better scalability and the ability for participants to keep control of their data, improving data security and sovereignty. Unfortunately, sharing model updates also creates a new privacy attack surface. In this work, we characterize the privacy guarantees of decentralized learning with random walk algorithms, where a model is updated by traveling from one node to another along the edges of a communication graph. Using a recent variant of differential privacy tailored to the study of decentralized algorithms, namely Pairwise Network Differential Privacy, we derive closed-form expressions for the privacy loss between each pair of nodes where the impact of the communication topology is captured by graph theoretic quantities. Our results further reveal that random walk algorithms tends to yield better privacy guarantees than gossip algorithms for nodes close from each other. We supplement our theoretical results with empirical evaluation on synthetic and real-world graphs and datasets.