Changing the Graph Is Not Hiding It: Gradient Leakage in Compressed Push-Sum Training

When many devices train one model by talking only to nearby peers, with no central server, the links between them usually change from round to round. Phones move, radio links fade, and some links work in one direction only. A common intuition is that this churn protects privacy, because an eavesdropping peer cannot tell how the messages it receives were mixed. We think this intuition is wrong for the algorithms people actually run on such networks. Push-sum, the standard fix for one-directional, changing links, makes every node send a single extra number alongside its model: its "mass," a running weight that tells receivers how much influence the sender has accumulated. That number starts at a known value (one) and passes through exactly the same unknown mixing as the model. To a curious peer it works like the pilot signal a radio receiver uses to estimate an unknown channel. Gradient tracking, the standard fix for clients whose data differ, adds a second exposed channel: every node injects its fresh, unmixed gradient change into the tracking message it sends out.

This note proposes two things. The first is an attack that uses these two channels to recover private training images over time-varying directed graphs, including when messages are compressed to save bandwidth. The second is a defense whose cost in bits is close to zero. It extends correlated zero-sum masking, which so far works only on static symmetric graphs, by sending the masking noise that fails to cancel (because a message was compressed or dropped) through the error-feedback buffer that compressed training already keeps. If the attack works, the claim that dynamic topology hides information collapses for the push-sum family. If the defense works, a deployment can have bandwidth savings, robustness to changing graphs, and resistance to gradient inversion together, without the extra messages of chunk-and-reshuffle schemes.

Core Claim

We make a falsifiable claim. Take decentralized training that combines push-sum de-biasing, gradient tracking, and compressed messages with error feedback over time-varying directed graphs. An honest-but-curious node that sees only its own incoming messages can estimate the hidden mixing weights from the mass sequence well enough to reach most of the reconstruction quality of an attacker who is told the true weights. It can also isolate a victim's gradient more cleanly from the tracking messages than from the model messages.

Our second claim is that a single-round masking scheme can remove most of this leakage while staying at the bit budget of compressed gradient tracking and within a point of its accuracy. In this scheme, each sender adds noise that sums to zero across its outgoing messages, and any part that does not cancel is carried forward in the error-feedback buffer.

What Prior Work Establishes, and What It Leaves Open

Three papers show that peer-to-peer learning leaks, and all three assume a fixed graph. On the (In)security of Peer-to-Peer Decentralized Machine Learning isolates a victim's contribution from mixed gossip and shows that sparse graphs leak more. Privacy Attacks in Decentralized Learning stacks received messages into a linear system and recovers data from nodes up to 28 hops away. That attack requires the mixing matrix at every round, and its authors note it degrades when the topology is unknown and changing. Topology-Dependent Privacy Bound For Decentralized Federated Learning proves that an adversary learns at most the sum of private data within an "honest component," meaning a connected group of non-colluding nodes. That bound is static.

These papers motivate our work, and the second also supplies our attack skeleton. None of them studies push-sum or gradient tracking. Our contribution on the attack side is to show that the very variable push-sum adds supplies the mixing knowledge the linear-system attack was missing.

Two recent defenses span all three directions and set the bar. Noiseless Privacy-Preserving Decentralized Learning (Shatter) cuts each update into chunks, routes them through virtual nodes over a graph that is reshuffled every round, and reaches LPIPS 0.815 against a gradient inversion attack. It does this at 2 to 2.5 times the payload of standard decentralized SGD and with many more messages. Its graph is a symmetric regular graph, and it has no gradient tracking. Low-Cost Privacy-Preserving Decentralized Learning (Zip-DL) adds correlated noise that sums to zero across a sender's outgoing messages, so the noise cancels in aggregate. It needs one communication round per step, but its cancellation requires every noisy packet to arrive over a symmetric graph, and it is evaluated only against membership inference. We reuse Zip-DL's masking idea. What we add is a repair for exactly the case Zip-DL cannot handle: lost or compressed packets on directed, changing graphs.

On the compression side, Compressed Gradient Tracking for Decentralized Optimization with Linear Convergence supplies the optimizer. It compresses differences between a node's state and a local reference, and keeps an error-feedback buffer, which carries each round's compression error forward so it is eventually transmitted. The paper does not examine privacy.

Two papers constrain our design. Mixed Quantization Enabled Federated Learning to Tackle Gradient Inversion Attacks reports that quantization with hidden scale factors drops the PSNR of the Deep Leakage from Gradients attack from 55.3 to 8.1 dB. That attack matches gradients by Euclidean distance. Inverting Gradients shows that attacks matching gradient direction, via cosine similarity, are insensitive to scale, so hiding scales alone should not be trusted. This is why every defense here is tested against the cosine attack. The push-sum machinery comes from Nedic et al. and its stochastic extension Nedic et al.. The client-drift motivation for gradient tracking comes from Chen et al..

Research Program

The mass-aided attack. In push-sum, node $j$ sends its model state $x_j^t$ and its mass $y_j^t$, both scaled by the same outgoing weight. Every node's mass starts at one, so the masses an attacker receives over a window of rounds are a known-input, linear readout of the products of the unknown mixing matrices. The model messages are the same products applied to unknown private states.

The attacker estimates the effective mixing weights by fitting the received mass sequence under a sparsity and non-negativity prior. Here "effective" means only the path products that reach the attacker, not the full matrices. It then plugs the estimate into the knowledge-matrix and generalized-least-squares pipeline of Privacy Attacks in Decentralized Learning. Finally, it runs the cosine-similarity inversion of Inverting Gradients on the isolated gradient.

One scalar per message may not identify all weights. We will therefore measure how identifiability grows with window length, graph sparsity, and drop rate, rather than assume it.

The tracker-differencing channel. In gradient tracking, the outgoing tracker equals mixed incoming trackers plus $\nabla f_i(x_i^{t+1}) - \nabla f_i(x_i^t)$, the node's own gradient change, added after mixing. Once mixing is estimated, an attacker can subtract the mixed part and sum the remainders over rounds. This telescopes to the victim's current gradient, which then feeds the inversion step.

With compressed difference messages, the residual left in the error-feedback buffer is eventually transmitted too. We will test whether compression actually conceals anything, or only delays it by a few rounds.

We will also run the attack on an AB-style variant, which mixes model and tracker with separate row- and column-stochastic weights and sends no mass scalar, in the spirit of FAB. This checks whether the leak is specific to push-sum.

The defense. Each node adds zero-sum noise $\eta_{i\to j}^t$ to its compressed tracker and model messages across its intended out-neighbors and itself, so that $\sum_{j} \eta_{i\to j}^t = 0$. Noise that fails to cancel has two sources: a dropped packet, detected by a one-bit acknowledgement, and the compressor's distortion of the noisy message. Both are added to the node's error-feedback buffer and re-sent in later rounds.

The intended invariant is that, summed over nodes and over time, injected noise cancels. Any finite delay in that cancellation then shows up as a bounded transient rather than persistent variance. We will prove this for strongly convex objectives, extending the analysis in Compressed Gradient Tracking, and check it empirically for deep networks. The privacy argument is empirical, through attacks. A formal guarantee in the style of Zip-DL's pairwise network differential privacy is a stretch goal, not a promise.

Baselines

The naive reference point is undefended compressed push-sum gradient tracking over the same time-varying digraphs, using top-k sparsification with error feedback. We also run it at full precision, so we can see how much compression alone changes leakage. Both are trained with identical seeds and schedules. The defense must stay within one accuracy point of the compressed version and match its bits per round.

On the attack side, there are three references. The strongest is the linear-system attack of Privacy Attacks in Decentralized Learning given oracle access to the true mixing weights, which serves as an upper bound. The second is the same attack using a static-graph assumption that ignores dynamics; this is what a reader of prior work would expect an attacker to do. The third is direct cosine inversion on raw received messages without isolation, following Inverting Gradients, which reports about 14 dB PSNR on a trained ResNet-20 on CIFAR-10 in the centralized setting.

The mass-aided attack beats the static assumption if it closes most of the gap to the oracle in PSNR and LPIPS. We consider the gap closed if the attack recovers at least half of the oracle's improvement over raw inversion. Every attack gets the same number of inversion iterations and the same image prior.

On the defense side, the strongest competitor is Shatter (Noiseless Privacy-Preserving Decentralized Learning). It reports LPIPS 0.815 against ROG inversion, median membership-inference AUC of 58%, and update-to-client linkability falling from 36.5% to 2.5% at k=16, at 2 to 2.5 times the payload. We run Shatter with k=16 on the same physical node set, letting its virtual graph reshuffle over the available links, with the same number of training rounds and a matched tuning budget for learning rates. Our defense beats it if it reaches comparable LPIPS (at least 0.8) and AUC within a few points of 58%, under the same cosine attack plus our new attacks, while using one message per link and the compressed bit budget.

We also port Zip-DL (Low-Cost Privacy-Preserving Decentralized Learning) unmodified to the directed setting. It reports tolerance to 25% node dropout on static graphs. We further run Gaussian local noise calibrated to match our attack resistance, and the mixed-quantization defense of Mixed Quantization Enabled Federated Learning, re-evaluated against cosine inversion instead of Euclidean.

Three ablations isolate the key ingredient. The first uses zero-sum masking without error-feedback repair, which should reproduce Zip-DL's drift on lossy digraphs. The second uses error-feedback repair with no mask, which should leak like the naive reference. The third masks only the model channel or only the tracker channel, to locate where the leak lives.

Why not just…?

Why not just add differential-privacy noise to every message? It works, but it costs accuracy. Mixed Quantization Enabled Federated Learning reports DP baselines falling to roughly 78–85% on MNIST against 96.67% for its defense, and Zip-DL reports up to 59% higher accuracy than the pairwise-DP method Muffliato at equal membership-inference resistance. We include calibrated local noise as a baseline. If it matches our accuracy at equal attack resistance on CIFAR-10, the defense half of this proposal is unnecessary, and we would say so.

Why not just use Shatter? This is the real threat on privacy. Shatter already defeats inversion without noise. Its costs are 2 to 2.5 times the payload, k-fold message counts that hurt latency on edge radios, symmetric regular virtual graphs, and no gradient tracking for heterogeneous data. Whether these costs matter is an empirical question. The head-to-head under non-IID splits and link drops settles it. If Shatter matches us on accuracy under drops at similar wall-clock message cost, our defense adds little, and the attack results remain the contribution.

Why not just rely on compression, since quantization already breaks inversion? The 55.3 to 8.1 dB result comes from a Euclidean attack with hidden scales. Direction-matching attacks Inverting Gradients ignore scale. Error feedback also re-sends what compression dropped, so the information may be delayed rather than destroyed. The full-precision versus compressed comparison under the cosine and tracker-differencing attacks tests this directly.

Why not just stop sending the mass, using an AB-style algorithm? This would remove the first channel, but the tracker channel remains. Column-stochastic tracker weights still need out-degree knowledge. Running the attack on the AB variant tells us whether dropping push-sum is a sufficient fix. If it is, that is a cheaper recommendation than our defense, and we would report it as such.

Proposed Experiments

We will use CIFAR-10 with ResNet-18 for training utility (Shatter's setting) and trained ResNet-20 for inversion (Geiping's setting), CIFAR-100 for higher label diversity, and MNIST for fast sweeps. ImageNet is used only for a reduced inversion check against Shatter's 0.815 LPIPS. Data are split non-IID by Dirichlet label skew.

The graphs are 32 to 64 nodes. We use per-round random directed graphs and a Facebook-ego-derived graph with independent link fading. We include Poisson versus power-law degree structure, following Topology-Dependent Privacy Bound, and link-drop rates from 0 to 30%. The metrics are reconstruction PSNR and LPIPS, membership-inference AUC, linkability, test accuracy, rounds to target accuracy, bits per round, and messages per round.

The first decisive check is whether mass-aided weight estimation error falls with window length, and whether reconstruction PSNR follows it toward the oracle curve. If it does not, the "changing graph hides" view is partly vindicated for push-sum, and we report that. The second is whether tracker differencing yields better reconstructions than the model messages at the same round. The third is whether, as the drop rate rises, the unrepaired zero-sum ablation loses accuracy while the repaired version holds within a point of undefended compressed training. Failure on the third check means the error-feedback repair does not work as intended. We also run colluding-attacker sweeps, since Shatter itself notes that collusion re-aggregates dispersed information, and our masking makes no claim beyond honest components.