In decentralized learning, machines train a shared model by exchanging updates only with their graph neighbors, with no central server. The strongest recent privacy defenses for this setting add correlated noise: each pair of neighbors agrees on a random value that one adds and the other subtracts, so the noise cancels when updates are averaged and accuracy stays close to that of a trusted central server. The weakness is that every noise partner is also a neighbor. If a node's neighbors pool what they know, they can subtract every noise term the node used and see its raw update. Its exact gradient can then be turned back into its training images.
We propose to break that coincidence. A node's noise partners should be chosen from a separate correlation graph whose edges deliberately reach beyond its communication neighborhood. To cancel a victim's noise, an adversary would then have to corrupt partners scattered across the network, not just the handful of machines physically adjacent to it. The claim we want to test has two parts. First, the formal privacy of correlated-noise schemes is set by how large the victim's honest component is in the union of the communication and correlation graphs, not in the communication graph alone. Second, adding a sparse set of short-range non-neighbor correlations recovers resistance to gradient inversion under neighbor collusion, while costing far less accuracy than the independent per-node noise it replaces.
Core Claim and Positioning
Three methods supply the mechanism we build on. They also share the assumption we relax. The Privacy Power of Correlated Noise in Decentralized Learning (DECOR) adds pairwise-canceling Gaussian noise along communication edges and matches central-DP error on any connected graph. It explicitly needs 2-connectivity and degrades toward local DP, where every node adds its own independent noise, when neighbors collude. Low-Cost Privacy-Preserving Decentralized Learning (Zip-DL) makes each node's outgoing noise sum to zero across its messages. It assumes symmetric topologies and no collusion. Enforcing Privacy in Distributed Learning with Performance Guarantees places noise in the null space of the combination matrix, again coordinated among neighbor pairs. In all three, the noise partners and the potential colluders are the same set of nodes. We separate them.
Two lines of work motivate the proposal by showing that this coincidence is exploitable. Topology-Dependent Privacy Bound For Decentralized Federated Learning proves, without any DP noise, that curious colluders can learn at best the sum of inputs within an "honest component", meaning a connected group of honest nodes left after removing the colluders. Per-node leakage scales like $1/(2(m-1))$ for component size $m$. In scale-free graphs, corrupting a few hubs drives $m$ to 1 and produces near-perfect image reconstructions. On the (In)security of Peer-to-Peer Decentralized Machine Learning shows that passive peers can use the graph structure to isolate one victim's contribution from neighborhood aggregates, which it calls functional marginalization, and then invert it. It offers attacks but no constructive defense.
Our hypothesis joins the two. Under correlated noise, the relevant "honest component" is a node's component in the graph formed by communication edges plus correlation edges, after colluders are removed. Moving correlation edges off the communication graph enlarges that component exactly in the cases where neighbor collusion would otherwise shrink it to $m=1$.
For accounting we reuse the matrix-mechanism formulation of Taming the Privacy-Utility Trade-off in Decentralized Learning, Unified Privacy Guarantees for Decentralized Learning via Matrix Factorization. That work writes everything a semi-honest observer sees over $T$ rounds as $O_A = AG + BZ$, where $G$ stacks all nodes' gradients, $Z$ is the injected Gaussian noise, and the matrices $A$ and $B$ encode the topology and what the adversary observes. MAFALDA-SGD optimizes $B$ for a single curious observer at cost $O(n^3T + n^2T^3)$. We do not optimize $B$ globally. We restrict it to a structured family, pairwise correlations on a sparse correlation graph plus a small independent term, and use the same rectangular, rank-deficient accounting to compute $\epsilon$ against coalitions rather than single observers.
Mechanism
Each node $i$ perturbs every outgoing message with noise $$z_i = \sum_{j \in P(i)} \pm s_{ij} + \xi_i,$$ where $P(i)$ is node $i$'s set of correlation partners, $s_{ij}$ is Gaussian noise generated from a seed shared only by $i$ and $j$ (added by one and subtracted by the other), and $\xi_i$ is a small independent Gaussian term. DECOR is the special case $P(i)$ = communication neighbors of $i$.
A coalition $C$ can cancel only the terms $s_{ij}$ with $j \in C$. The residual noise protecting $i$ therefore has variance $|P(i)\setminus C|\,\sigma_{c}^2 + \sigma_{\xi}^2$, where $\sigma_c^2$ is the per-pair correlated variance and $\sigma_\xi^2$ the independent variance. When all of $i$'s communication neighbors collude, DECOR leaves only $\sigma_\xi^2$. Our scheme keeps the terms shared with honest partners outside the neighborhood.
What the adversary can still learn from those partners' messages is sums such as $x_i + x_j$. That is precisely an honest-component aggregate in the union graph, which is what the theory of honest components predicts.
The design parameter is the partner distance $d$, the number of communication hops between correlation partners. With $d=1$ we recover DECOR. With larger $d$, opposite-signed noise takes about $d$ gossip steps to meet, so residual noise lingers in the local averages. The cost should therefore grow with $d$ relative to the graph's mixing time. We will measure that cost rather than assume it.
Partner seeds are established once at setup by public-key encryption relayed along paths. Under the semi-honest model, relays forward the encrypted seed faithfully and cannot read it. We will report the one-time cost of this setup and the per-round cost, which is the same as DECOR's.
Research Program
The work has three parts.
The first is analytical. We extend the coalition accounting to the $O_A = AG + BZ$ form. We derive per-node $\epsilon$ as a function of $|P(i)\setminus C|$ and the union-graph honest component. We also characterize when choosing partners at random within distance $d$ makes a randomly placed coalition of a given size unlikely to cover $P(i)$, a covering argument on the correlation graph.
The second is an attack suite that represents a semi-honest adversary as faithfully as we can. A coalition at a vertex cut pools its observations. It solves the linear system to remove every noise term it holds and to marginalize neighbors' contributions in the style of the functional marginalization of On the (In)security of Peer-to-Peer Decentralized Machine Learning. It then runs optimization-based gradient inversion, with and without the generative image prior of Gradient Inversion with Generative Image Prior, in the first training rounds, where inversion is known to be strongest.
The third is the defense. We implement it on top of the DECOR codebase, so that DECOR is the $d=1$ setting of a single implementation.
Baselines
The naive reference point is undefended decentralized SGD, with plain gossip averaging and no noise, under the same coalitions. It anchors both ends of the evaluation: maximal accuracy and, per Topology-Dependent Privacy Bound For Decentralized Federated Learning, near-perfect reconstruction when the honest component is a single node.
Local DP, meaning per-node clipping and independent Gaussian noise, is the opposite end, calibrated to the same $\epsilon$. DECOR reports that local DP "lost nearly 10 accuracy points at low privacy budgets" on MNIST, and that DECOR "stayed within 1% of the centralized accuracy baseline" (The Privacy Power of Correlated Noise in Decentralized Learning).
The strongest competitor is DECOR itself. It is the best published correlated-noise method with central-DP-level utility, and it differs from our proposal in exactly one ingredient: where the correlation partners sit. We will also run Zip-DL, which reports "up to 59% higher accuracy than Muffliato" at equal protection against membership inference (Low-Cost Privacy-Preserving Decentralized Learning). No reported gradient-inversion result was found on Lacuna for DECOR, Zip-DL, MAFALDA-SGD, or TOP-DP, so the inversion numbers for all of them will be produced in this study.
All methods share the same graphs, datasets, model, training rounds, clipping norm, and a matched hyperparameter search budget. They are also matched on a single formal $\epsilon$ computed by our coalition accounting. We will separately report each method's $\epsilon$ under its own original non-collusion accounting.
Beating DECOR means one of two outcomes. Either our method yields significantly higher LPIPS (worse reconstructions for the attacker) under neighbor collusion at equal accuracy, or it yields higher accuracy at equal attack resistance once DECOR's independent term is raised to survive collusion.
For empirical-only defenses, we compare against Shatter's chunking over virtual nodes (Noiseless Privacy-Preserving Decentralized Learning). Shatter reports an ImageNet LPIPS of 0.815 under the ROG attack, though without collusion and without formal DP.
The key ablation sweeps $d$ from 1 to 4 while holding the number of partners and the noise variances fixed. Varying distance alone isolates the decoupling as the cause of any gain.
Why not just…?
Why not just use local DP and skip the topology? Local DP is collusion-proof by construction, but the material consistently shows it is too costly. Its error is roughly $n$ times worse than central DP in DECOR's analysis. It fails to converge at $\epsilon=1$ on Housing in Privacy Amplification by Decentralization. Its steady-state error grows as the step size shrinks in Enforcing Privacy in Distributed Learning with Performance Guarantees. Our accuracy-versus-LPIPS curves will show where on the trade-off curve it lands.
Why not just raise DECOR's independent noise term until it survives collusion? This is the real threat. If the independent term needed to defeat a neighbor coalition costs no more accuracy than distant correlations do, our idea is unnecessary. The ablation settles it directly. For each coalition size, we find the smallest $\sigma_\xi$ at which DECOR's inversion LPIPS matches ours and compare test accuracy. If DECOR with extra independent noise is within noise of our method, we will report that as the answer.
Why not just use secure aggregation or a complete graph? Secure aggregation can be bypassed by functional marginalization across rounds (On the (In)security of Peer-to-Peer Decentralized Machine Learning), and multi-round protocols cost about 10x the communication that Zip-DL needs. A complete graph defeats the purpose of decentralization, and the same insecurity paper finds it is what parity with federated learning requires. We include a dense random-regular graph as a reference showing how much of our gain could instead be bought with extra edges.
Why not just use heuristic obfuscation like CENSOR or Shatter? Neither gives a formal $(\epsilon,\delta)$ guarantee. Shatter states that colluders can reassemble chunks. CENSOR: Defense Against Gradient Inversion via Orthogonal Subspace Bayesian Sampling is designed for a star topology with a central server. Our collusion experiments will run Shatter under the same coalitions to test whether its LPIPS advantage survives them.
Proposed Experiments
We will train on CIFAR-10 with a small CNN and ResNet-18, and use FFHQ faces for perceptual inversion quality. MNIST serves as a comparison point with DECOR's reported numbers, and FEMNIST tests non-IID data. The graphs are ring, torus, random regular, Poisson, and power-law, with Facebook Ego as a real social graph.
Coalitions are placed in three ways: at a victim's full neighborhood, at targeted hubs following the hub-compromise setup of the honest-component paper, and at random, with sizes from 1 to 10% of nodes. We report test accuracy, reconstruction PSNR, SSIM, and LPIPS for the worst-case victim and the median victim, membership-inference AUC, formal $\epsilon$ under coalition accounting, and setup and per-round communication cost.
The first decisive check targets DECOR under full-neighborhood collusion on a ring and a power-law graph. If our hypothesis is right, the attack's PSNR on DECOR should approach that of the undefended baseline, while at $d\ge2$ our method should stay near the local-DP level of protection with accuracy within a few points of DECOR's. If DECOR already resists the inversion attack, the premise fails.
The second decisive check tests the honest-component prediction. Across all graphs and coalitions, per-node LPIPS should track the victim's component size in the union graph more closely than its component size in the communication graph. We will report the rank correlation of LPIPS with each.
The third decisive check is the matched-noise ablation described under baselines. It determines whether decoupling or simply adding more noise is responsible for any gain.
References
- The Privacy Power of Correlated Noise in Decentralized Learning
- Low-Cost Privacy-Preserving Decentralized Learning
- Enforcing Privacy in Distributed Learning With Performance Guarantees
- Topology-Dependent Privacy Bound for Decentralized Federated Learning
- On the (In)security of Peer-to-Peer Decentralized Machine Learning
- Unified Privacy Guarantees for Decentralized Learning via Matrix Factorization
- Gradient Inversion with Generative Image Prior
- Noiseless Privacy-Preserving Decentralized Learning
- Privacy Amplification by Decentralization
- CENSOR: Defense Against Gradient Inversion via Orthogonal Subspace Bayesian Sampling