Topology-Dependent Privacy Bound For Decentralized Federated Learning

Qiongxiu Li, Wenrui Yu, Changlong Ji, Richard Heusdens

Abstract

Decentralized Federated Learning (FL) has attracted significant attention due to its enhanced robustness and scalability compared to its centralized counterpart. It pivots on peer-to-peer communication rather than depending on a central server for model aggregation. While prior research has delved into various factors of decentralized FL such as aggregation methods and privacy-preserving techniques, one crucial aspect affecting privacy is relatively unexplored: the underlying graph topology. In this paper, we fill the gap by deriving a stringent privacy bound for decentralized FL under the condition that the accuracy is not compromised, highlighting the pivotal role of graph topology. Specifically, we demonstrate that the minimum privacy loss at each model aggregation step is dependent on the size of what we term as 'honest components', the maximally connected subgraphs once all untrustworthy participants are excluded from the networks, which is closely tied to network robustness. Our analysis suggests that attack-resilient networks will provide a superior privacy guarantee. We further validate this by studying both Poisson and power law networks, showing that the latter, being less robust against attacks, indeed reveals more privacy. In addition to a theoretical analysis, we consolidate our findings by examining two distinct privacy attacks: membership inference and gradient inversion.

Introduction

Standard Federated Learning (FL) typically relies on a central server to aggregate model updates from clients. While effective, this architecture creates a "single point of failure" and a significant privacy risk, as the server acts as a massive honeypot for sensitive data. Decentralized FL mitigates these risks by utilizing peer-to-peer communication, where nodes reach consensus through local interactions. However, decentralization introduces its own vulnerabilities, particularly from "honest-but-curious" neighbors who may collude to extract private information. This study investigates how the specific arrangement of these peer-to-peer connections—the graph topology—dictates the inherent privacy limits of the system.

The Theory of Honest Components

The core of our theoretical contribution is the identification of Honest Components. These are defined as the maximally connected subgraphs formed by honest nodes after all corrupt or colluding nodes are removed from the network. We prove that an adversary can, at best, learn the aggregate sum of private data within each honest component.

Using mutual information to quantify privacy leakage, we derive a bound showing that the minimum information loss for an individual node is approximately $1 / (2(m-1))$, where $m$ represents the number of nodes in its honest component. This inverse relationship implies that "safety in numbers" is a mathematical reality in decentralized networks: as the size of the honest component increases, the ability of an attacker to isolate and unmask individual data points diminishes sharply.

Mutual information $I(S_i; \Sigma_1)$ vs. size of honest component $m_1$, showing the sharp decline in privacy leakage as component size increases.

Topology, Robustness, and Privacy

The relationship between topology and privacy is mediated by network robustness. We compared two primary network structures: Poisson Networks, which are characterized by a uniform degree distribution, and Power Law Networks, which are defined by a few high-degree "hubs" and many low-degree nodes.

Our analysis reveals that Poisson networks are more robust against targeted attacks. In contrast, Power Law networks are fragile; an adversary only needs to corrupt a few central hubs to fragment the network into small, isolated honest components, thereby maximizing privacy leakage. This confirms that network density is less important than the distribution of connections; a robust topology like a Poisson graph offers significantly better protection than a fragile "hub-and-spoke" power-law network.

Empirical Validation: Gradient Inversion

To validate our theoretical bounds, we simulated state-of-the-art privacy attacks, including Membership Inference and Gradient Inversion. In Gradient Inversion tests, we attempted to reconstruct original training images from the gradient updates shared between nodes.

The results confirm our theory: when the honest component size is small (e.g., $m_k=1$), the reconstruction is nearly perfect, indicating total privacy loss. As the component size grows, the reconstructed images become increasingly noisy and unrecognizable, demonstrating the protective effect of larger honest groups.

Visual results of gradient inversion attacks for different honest component sizes $m_k$. As $m_k$ increases, the reconstructed images become noisier.

Conclusion

This research establishes that graph topology is a fundamental determinant of privacy in decentralized FL. By maximizing the size of honest components through robust network design, practitioners can significantly enhance the privacy guarantees of decentralized systems without sacrificing model accuracy. Future work will explore these bounds in the context of active adversaries and larger-scale deployments.

Summary updated

Abstract

Decentralized Federated Learning (FL) has attracted significant attention due to its enhanced robustness and scalability compared to its centralized counterpart. It pivots on peer-to-peer communication rather than depending on a central server for model aggregation. While prior research has delved into various factors of decentralized FL such as aggregation methods and privacy-preserving techniques, one crucial aspect affecting privacy is relatively unexplored: the underlying graph topology. In this paper, we fill the gap by deriving a stringent privacy bound for decentralized FL under the condition that the accuracy is not compromised, highlighting the pivotal role of graph topology. Specifically, we demonstrate that the minimum privacy loss at each model aggregation step is dependent on the size of what we term as 'honest components', the maximally connected subgraphs once all untrustworthy participants are excluded from the networks, which is closely tied to network robustness. Our analysis suggests that attack-resilient networks will provide a superior privacy guarantee. We further validate this by studying both Poisson and power law networks, showing that the latter, being less robust against attacks, indeed reveals more privacy. In addition to a theoretical analysis, we consolidate our findings by examining two distinct privacy attacks: membership inference and gradient inversion.
BibTeX
@inproceedings{li2024topology,
  author = {Qiongxiu Li and Wenrui Yu and Changlong Ji and Richard Heusdens},
  title = {{Topology-Dependent Privacy Bound For Decentralized Federated Learning}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=wB01ytsxTe},
}
Figure