Who Pays for Private Graph Learning? Degree-Aware Signal Routing in Differentially Private GNNs

Graph neural networks (GNNs) are models that classify a node by repeatedly averaging information from its neighbors. When they are trained with differential privacy (DP), meaning calibrated random noise is added so that no single edge or person measurably changes the output, the noise does not fall evenly. A node with five hundred neighbors averages away the noise added to its neighborhood summary. A node with two neighbors gets almost pure noise. We propose to measure precisely how much of the accuracy lost to privacy in private GNNs falls on low-degree nodes, and to separate the two places that loss can come from: noise added to neighbor aggregation, and clipping and noise in private stochastic gradient descent (DP-SGD). We then fix the dominant source with a mechanism that costs no extra privacy budget. A free, privatized degree estimate is read off the noisy aggregation itself, and the classifier uses it to decide, per node, how much to trust its noisy neighborhood versus its own features.

This matters because the private GNNs that work best today, such as GAP, DPAR, and Daigavane et al.'s node-level DP-GNN, report only aggregate accuracy and treat all nodes identically. Two separate literatures predict that this hides an unequal burden. Non-private GNNs already underserve low-degree nodes (Subramonian et al.), and DP-SGD already taxes hard and underrepresented examples most (Bagdasarian et al.). Nobody has checked whether the two compound in private graph learning, or which part of the private pipeline is responsible.

Core Claim

We claim that in decoupled private GNNs the degree-dependent privacy tax is dominated by the signal-to-noise ratio of the perturbed aggregation, not by gradient clipping. Under edge- or node-level DP, the noise added to a neighborhood sum is fixed by the sensitivity, while the signal grows with degree. If each neighbor embedding $h_u$ has unit norm and the noise is $\mathcal{N}(0,\sigma^2 I)$ in $m$ dimensions, the aggregate for node $v$ with degree $d_v$ has

$$ \mathrm{SNR}_v \approx \frac{\|\sum_{u \in N(v)} h_u\|}{\sigma\sqrt{m}} \le \frac{d_v}{\sigma\sqrt{m}}, $$

so a degree-2 node in a homophilous graph sees roughly a hundredth of the signal-to-noise of a degree-200 hub. Normalizing by degree does not help, because a mean over two neighbors changes a great deal when one is removed, so its noise must be correspondingly large.

The proposed fix follows from this mechanism. Before aggregation, we append a constant coordinate to each encoder output and rescale so that the norm stays one: $\tilde h_u = [\alpha h_u, \sqrt{1-\alpha^2}]$ with $0<\alpha<1$. Sensitivity is unchanged. The aggregated last coordinate then equals $\sqrt{1-\alpha^2}\, d_v$ plus the same Gaussian noise. That gives a privatized degree estimate $\hat d_v$ as pure post-processing, at a small cost in embedding norm and no cost in $\epsilon$. The classification module receives $\hat d_v$ for every hop and learns a per-node gate. That gate down-weights hops whose estimated signal-to-noise is low and falls back on the node's own encoded features. The same $\hat d_v$ also defines degree bins for group-adaptive clipping in the style of DPSGD-F, without needing any protected labels. We include this clipping component only if our decomposition shows clipping matters.

What would be new is threefold: a measured decomposition of where degree disparity enters private GNN training, a zero-budget private degree signal, and per-node routing driven by that signal. The closest work, TDP-GNN, allocates per-node budgets using a topological entropy score under local DP. It assumes the server knows the topology, and it deliberately gives hubs more noise. We work in the centralized DP-SGD setting, treat degree itself as private, and aim to protect low-degree nodes rather than discount hubs.

Research Program

The first stage is diagnostic. We take GAP as the reference pipeline. It has three parts: an encoder trained with DP-SGD, a once-only perturbed multi-hop aggregation that is then cached, and a classifier trained with DP-SGD on the cached representations. We swap privacy on and off component by component: aggregation noise only, classifier DP-SGD only, encoder DP-SGD only, and all three. For each configuration we report the privacy cost, meaning non-private accuracy minus private accuracy, separately for each degree quintile.

Two further measurements test the two candidate mechanisms. First, we record per-node gradient norms and clipping rates by degree, which tests the clipping story. Subramonian et al. predict a specific pattern here: under symmetric normalization, low-degree nodes converge slowly, so their gradients stay large and would be clipped more. Second, we record the cosine between each degree bin's mean clipped gradient and the batch update, which tests the misalignment account of Esipova et al.'s gradient-misalignment work on graph data.

The second stage builds the routing mechanism described above. We study the trade-off in $\alpha$: a smaller $\alpha$ gives a better degree estimate but weakens the feature signal. We also prove the privacy accounting is unchanged.

The third stage asks whether the degree channel also carries demographic disparity. On fairness graphs where minority groups tend to sit at lower degree, routing should shrink group gaps without group labels. Where minority groups are not lower-degree, it should not. Either outcome is informative.

Throughout, we treat Müller et al.'s finding that DP-GNN utility depends on homophily as a constraint. In heterophilic graphs, neighbors carry little useful signal, so the gate should learn to rely on own features for everyone. Subramonian et al. also report that degree bias largely vanishes there. We therefore predict that our gains shrink on heterophilic graphs, and we test this.

Baselines

The naive reference is GAP run unchanged at matched $\epsilon$, with its published hyperparameter recipe re-tuned under the same search budget as our method. Its reported results anchor the regime: 94.0% accuracy on Reddit under node-level DP at $\epsilon=8$, and 76.3% on Facebook under edge-level DP at $\epsilon=4$ (GAP). To beat it, we must cut the bottom-quintile privacy cost by a margin larger than the seed-to-seed spread across ten seeds, while keeping overall accuracy within one point. No reported result found on Lacuna for degree-stratified accuracy of any private GNN, so we will produce these numbers ourselves.

The strongest competitor on the fairness question is DPSGD-Global-Adapt (gradient misalignment), dropped into GAP's encoder and classifier. Like our method, it needs no group labels. On unbalanced MNIST it raised minority-class accuracy from 26.3% to 65.5%. It is the right method to beat if the disparity turns out to be a clipping problem.

We also run DPSGD-F (Removing Disparate Impact) with groups defined by our private degree bins. On Adult it reduced the male/female privacy cost from 7.4% vs 2.8% to 2.9% vs 1.6%.

For node-level DP comparisons we include DPAR, which reports 0.3421 vs GAP's 0.34 on Cora at $\epsilon=1$ and 0.8569 vs 0.6563 on MS Academic. Its PageRank-based neighbor selection may itself favor hubs. We also include DP-MLP as the "ignore the graph" floor, and non-private GCN as the ceiling.

Every method gets the same data splits, the same privacy accountant, the same $\epsilon$ grid of 1, 2, 4, and 8 with $\delta$ fixed, and an equal number of tuning trials. Two ablations isolate our key ingredient. The first gives the gate the true degree, which shows the cost of privatizing degree. The second gives the gate a constant input, which shows whether a learned global hop weighting already captures the gain.

Why not just…?

Why not just run DPSGD-Global-Adapt on a private GNN? This is the real threat. If our diagnostic shows that clipping and misalignment drive most of the degree gap, Global-Adapt may close it and our routing would be unnecessary. We do not argue around this: the stage-one decomposition decides it. Our hypothesis is the opposite. GAP's aggregation noise is injected before any gradient is computed, so no change to the optimizer can recover signal that the cached features no longer contain. The "aggregation noise only" condition directly tests whether a large degree gap persists with no DP-SGD at all.

Why not just spend a little budget on a separate Laplace degree query? This works, and it is the honest alternative to our free estimate. We run it at matched total $\epsilon$, splitting the budget between the degree query and training. Our construction must match or beat it. If it does not, we adopt the separate query and the contribution reduces to the routing itself.

Why not just reweight or oversample low-degree nodes? Oversampling raises a node's influence on the model, and therefore its sensitivity, so the extra noise required cancels the benefit (Bagdasarian et al.). Reweighting also failed to remove the gap on census data (DPSGD-F). We still include degree-reweighted DP-SGD as a cheap baseline.

Why not just fall back to a DP-MLP for low-degree nodes? A hard per-node fallback is a special case of our gate, and the constant-gate ablation covers the global version. Abandoning the graph entirely is costly: DP-GCN reaches about 62% on ogbn-arxiv against about 52% for DP-MLP (Daigavane et al.). We will report the fraction of nodes the learned gate effectively routes to features only.

Proposed Experiments

For edge-level DP we use Facebook and Cora. For node-level DP we use Reddit and ogbn-arxiv, the regimes where GAP and Daigavane et al. report results. For demographic analysis we use Pokec-z, Pokec-n, German, and Credit, as in EDITS and FUGNN. We report overall accuracy, accuracy and privacy cost per degree quintile, the bottom-to-top quintile privacy-cost gap, and, on the fairness graphs, statistical parity and equal-opportunity differences. All results use ten seeds.

The first decisive check is the decomposition. If the aggregation-noise-only condition accounts for less than half of the degree gap, we expect Global-Adapt to win, and we would redirect the method toward the clipping side. The second check is whether the bottom-quintile gain from routing grows as $\epsilon$ shrinks, as the signal-to-noise argument predicts. The third is whether the gain largely disappears on graphs with low edge homophily, which we construct by controlled edge rewiring on Cora while holding degree fixed. This last test separates degree effects from homophily effects. It also tells us whether EDITS-style debiasing by rewiring would move a graph into the regime where private GNNs lose utility, as Müller et al.'s results warn.