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.

去中心化学习中采用随机游走算法以节点间的通信图为边更新模型，通过 Pairwise Network Differential Privacy 推导出隐私损失，研究结果表明随机游走算法相较于热点算法在节点邻近情况下提供更好的隐私保证。