When several parties train a graph neural network together, they usually share only gradients (the weight updates from each training step) and keep their graphs at home. Recent attacks show that this is not enough: a curious server can solve for the private graph by searching for a dummy graph whose gradients match the ones it received, and it recovers the links nearly perfectly. The textbook fix is to clip each update and add Gaussian noise, as in differentially private stochastic gradient descent (DP-SGD). Differential privacy (DP) means a guarantee that the output barely changes when one record changes. In graph work this fix has repeatedly destroyed accuracy, often down to the level of a model that ignores the graph entirely.
This note argues that much of that collapse comes from calibrating noise to the wrong unit of privacy. If what must stay secret is whether any single relationship exists, a guarantee called edge-level DP, then the noise only has to hide the effect of toggling one edge on a client's summed gradient. With a message-passing design that caps how far one edge can propagate, that effect is a constant independent of graph size, while the useful gradient signal grows with the number of nodes. The proposal builds such a mechanism and derives when it should beat the main alternative of perturbing the graph once before training. It then tests the mechanism against the strongest graph gradient-inversion attacks on standard benchmarks.
Core Claim
The claim is narrow and testable. For a graph network with $k$ message-passing layers, a public degree cap $D$, sum aggregation normalized by $D$ rather than by true degree, and per-node gradient clipping at norm $C$, toggling one edge $(u,v)$ can change the predictions of only those nodes within $k$ hops of $u$ or $v$. The client's summed gradient therefore has edge sensitivity bounded by
$$\Delta_{\text{edge}} \le 2C \sum_{j=0}^{k-1} D^{j},$$
where the sum counts the nodes at most $k-1$ hops from an endpoint whose computation can reach across the edge. Gaussian noise of scale $\sigma \Delta_{\text{edge}}$ per round then gives edge-level DP across $T$ rounds by standard composition. The key quantity is the per-parameter signal-to-noise ratio, which scales like
$$\text{SNR} \propto \frac{n}{\sigma\,\Delta_{\text{edge}}\sqrt{T}},$$
with $n$ the number of training nodes on the client. The form comes from the signal summing over $n$ clipped node gradients while composed noise grows as $\sqrt{T}$. The prediction is that gradient-level edge noise wins on large client graphs trained for few rounds. One-shot graph perturbation wins on small graphs or long training. The proposal aims to locate and explain that crossover. It does not claim that gradient noise dominates everywhere.
Normalizing by true degree is the detail that breaks naive bounds. One added edge would then reweight every neighbor's message, and it would also open a side channel the attacks exploit. Normalizing by the public cap $D$ is the one structural change the mechanism requires. The project measures what that change costs in non-private accuracy.
Where This Sits
Three attack papers motivate the work. Gradient Inversion Attack on Graph Neural Networks (GLG) inverts federated GCN and GraphSAGE gradients with projected gradient descent plus sparsity and feature-smoothness priors. It reaches AUC/AP of 1.0 on structure recovery and remains effective as batch size grows. Its authors leave a formal DP defense open because of accuracy loss. FedGIG: Graph Inversion from Gradient in Federated Learning adds symmetry, dynamic sparsification and a masked graph autoencoder for molecular graphs, reaching 90.6% reconstruction accuracy on MUTAG against 65.4% for the best baseline. It also leaves defenses to future work. LinkTeller recovers edges from a trained model's outputs by measuring influence. Its Theorem 1 states that nodes more than $k$ hops apart have zero influence in a $k$-layer GCN. Our sensitivity bound turns that attacker's observation into a defender's tool.
Three lines of defense constrain the design. LinkTeller's own evaluation of input perturbation (EdgeRand and LapGraph) found that budgets strong enough to stop the attack ($\epsilon<5$) reduce GCN accuracy to MLP level. Model Inversion Attacks against Graph Neural Networks (GraphMI) reports a similar breakdown with generic DP. Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD proves that worst-case DP-SGD carries unavoidable utility limits. We read these results as indictments of mismatched sensitivity, not of gradient noise as such, and our ablations test that reading directly. Towards Private Learning on Decentralized Graphs with Local Differential Privacy (Solitude) recovers accuracy after randomized response by sparsity and smoothness denoising. Those are the same priors GLG and FedGIG exploit, which leaves an unresolved tension that our attack evaluation probes. On the trade-off between expressivity and privacy in graph representation learning releases noisy homomorphism densities calibrated by smooth sensitivity, a static one-shot edge-private embedding. It cuts reconstruction success from 95% to 0.3%. We borrow its idea of instance-aware calibration but apply it during iterative federated training, which that paper does not address. NAP-GNN adapts noise to node importance but perturbs features rather than giving edge-level guarantees, and it is not tested against gradient inversion.
Research Program
The first component is the mechanism itself, which we call EdgeGrad-DP. It is a GCN/GraphSAGE variant with cap-normalized sum aggregation and per-message norm clipping. Edges at degree-capped nodes are dropped using a deterministic rule computed from public node identifiers, so that dropping does not depend on other private edges. A per-round Gaussian step is calibrated to $\Delta_{\text{edge}}$, and privacy is tracked with Rényi accounting. We will try to tighten the bound beyond the ball-counting argument above with layer-wise Lipschitz constants. This matters most for $k=2$, where the $D^{k-1}$ factor dominates. We will also check whether subsampling root nodes per round gives privacy amplification under edge adjacency. A shared edge can couple two sampled computation trees, so the standard amplification argument may not transfer; settling that is a proof obligation, not an assumption.
The second component is the crossover analysis. It compares the SNR expression above with the analogous expression for one-shot noisy aggregates and for randomized response. It then produces a predicted boundary in the space of client size $n$, rounds $T$ and budget $\epsilon$, which the experiments test.
The third component is adversarial evaluation. We run GLG, FedGIG and GraphMI-style inversion against shared gradients, including attacker versions given homophily priors and Solitude-style denoising. This tests whether priors can extract more than the DP hypothesis-testing bound allows. Exceeding that bound would indicate an accounting bug, so the test doubles as an audit.
Baselines
The naive reference points are two. A non-private federated GCN gives the accuracy ceiling and the attack's best case, with GLG's reported structural AUC/AP of 1.0 as the point to compare against. An MLP that ignores edges gives the accuracy floor that LinkTeller reports DP defenses collapsing to. Any private method must land clearly above the MLP at matched $\epsilon$ to justify itself.
The strongest structural competitor is one-shot input perturbation: EdgeRand and LapGraph as defined in LinkTeller, each with and without Solitude-style server denoising. Because all later training is post-processing of the perturbed graph, these baselines pay no composition cost, and that makes them the real threat. The file gives no exact accuracy number for them, only the qualitative drop to MLP level for $\epsilon<5$. We will rerun them ourselves.
The second strong competitor is a one-shot noisy release of cap-normalized aggregates, on which an MLP is then trained. For graph-level tasks we add the smooth-sensitivity homomorphism embedding of Indri et al., which reports MOLHIV AUC 0.692 at $\epsilon=1$ against 0.488 for randomized response. We also include node-level DP-SGD with per-client clipping, which gives a stronger guarantee at higher noise.
All methods share the same client partitions, architecture width and depth where applicable, number of rounds, and the same hyperparameter search budget per method. Privacy accounting is reported in a common $(\epsilon,\delta)$ edge-level form.
The ablations are three. Degree capping without noise isolates the accuracy cost of the architecture. Gradient noise calibrated to the naive worst-case bound, with true-degree normalization and no cap, isolates the calibration. Our mechanism without per-message clipping isolates that component.
Beating the competitors means two things at matched edge-level $\epsilon \in \{0.5,1,2,4,8\}$. On large clients, the method must achieve higher test accuracy than every one-shot baseline. And GLG and FedGIG structural AUC on the shared gradients must stay near 0.5, within what the guarantee permits.
Why not just…?
Why not just perturb the graph once with randomized response and train freely? This is the most serious alternative, because post-processing makes it immune to composition. The evidence against it as a universal answer is that uniform edge flips densify sparse graphs. Personalized Social Recommendations - Accurate or Private? reports near-random recommendation quality under worst-case noise. On MOLHIV, randomized response reaches 0.488 AUC in Indri et al.. Repairing this with denoising, as in Solitude, reintroduces the priors the attacks exploit. Still, we expect it to win on small clients or long training, and the crossover experiment exists to measure exactly where.
Why not just run standard DP-SGD on client gradients? Standard DP-SGD calibrates to the wrong neighbor relation. Node-level or client-level clipping protects far more than a single edge and pays for it, which matches the utility collapse reported by GraphMI and the limits proved in Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD. Our calibration ablation tests this explanation directly. It holds the noise mechanism fixed and changes only the sensitivity bound. If accuracy does not improve, our explanation of the collapse is wrong.
Why not just release noisy aggregated features once and train an MLP on them? This is a strong, simple baseline, and we include it. Our analysis predicts that its per-node noise does not shrink with $n$ the way summed-gradient noise does, but that is a prediction to be tested, not a given. If one-shot aggregates match EdgeGrad-DP across all client sizes, the honest conclusion is that training-time noise is unnecessary for edge privacy, and the note would report that.
Why not just use large batches or dummy edges? Neither gives a guarantee. GLG remains effective as batch size grows, and FedGIG's sparsification removes uncorrelated fake edges. We include large-batch training only as an attack sanity check.
Proposed Experiments
For node classification we use Cora, CiteSeer, LastFM and Facebook, each partitioned into 5 to 20 client subgraphs. OGBN-Arxiv provides the large-$n$ regime the theory says matters. Twitch and Flickr allow LinkTeller-style evaluation of the final model. For graph classification we use MUTAG and MOLHIV, with MUTAG matching FedGIG's reported 90.6% and MOLHIV matching Indri et al.'s 0.692 AUC. The metrics are test accuracy or AUC versus $\epsilon$, together with attack AUC/AP for GLG, FedGIG, GraphMI and LinkTeller. We also report accuracy gaps between low- and high-degree nodes, since Differentially Private Graph Data Release: Inefficiencies & Unfairness warns that structural DP hurts subpopulations unevenly, and degree capping is likely to concentrate harm on hubs.
The decisive check has two parts. First, we sweep client size $n$ by subsampling OGBN-Arxiv and sweep rounds $T$, then plot where EdgeGrad-DP overtakes EdgeRand+denoising and one-shot aggregates. The idea is supported if the empirical boundary follows the $n/\sqrt{T}$ prediction. If no crossover appears, or if it does not move with $n$, the core claim fails. Second, with the best prior-augmented attacker, structural AUC must stay below the bound implied by the guarantee at each $\epsilon$.
References
- Gradient Inversion Attack on Graph Neural Networks
- FedGIG: Graph Inversion from Gradient in Federated Learning
- LINKTELLER: Recovering Private Edges from Graph Neural Networks via Influence Analysis
- Model Inversion Attacks Against Graph Neural Networks
- Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD
- Towards Private Learning on Decentralized Graphs With Local Differential Privacy
- On the trade-off between expressivity and privacy in graph representation learning
- Differentially Private Graph Neural Network with Importance-Grained Noise Adaption
- Personalized Social Recommendations - Accurate or Private?
- Differentially Private Graph Data Release: Inefficiencies & Unfairness