GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

• GNNs can leak sensitive relationships and other graph information through their predictions, creating privacy risks for personal and financial networks.The paper frames protection in terms of edge-level privacy and the stronger, harder-to-achieve node-level privacy.Source: §1 · p. 1
• K-hop aggregation makes embeddings interdependent, so standard sample-wise DP approaches do not directly apply and the number of affected embeddings grows with K.An edge change can alter a destination embedding and propagate to neighboring nodes in later layers.Source: §1 · p. 2, Figure 1 · p. 2
• GNN inference queries graph neighborhoods again, so private training alone does not ensure inference privacy.Inference can expose information about neighboring nodes even when model parameters were trained privately.Source: §1 · p. 2, Figure 2 · p. 2
• GAP adds calibrated Gaussian noise to aggregation outputs and uses an encoder, private multi-hop aggregation, and a classifier that does not query edges again.Cached perturbed aggregations are reused during training and inference, with no additional inference privacy cost.Source: §1 · pp. 2–3, Figure 3 · p. 3
• GAP surpasses competing baselines at low privacy budgets under edge- and node-level DP, and performs on par with or better than a private MLP.The paper gives Reddit examples at 𝜖≥0.1 for edge-level DP and 𝜖≥1 for node-level DP.Source: §1 · p. 3

• GNN research includes architectures such as Graph Convolutional Networks, Graph Attention Networks, GraphSAGE, and Graph Isomorphism Networks.The paper points readers to surveys for broader coverage of advances and trends.Source: §2 · p. 3
• Prior attacks target graph properties, subgraph membership, graph reconstruction, links, edge influence, and membership inference.The cited work collectively documents privacy risks for graph embeddings and trained GNNs.Source: §2 · p. 3
• Existing DP-GNN approaches address local privacy, edge perturbation, PATE-style node privacy, or bounded-degree one-layer learning, with constraints including private-edge applicability, public-data dependence, or inference privacy.The one-layer bounded-degree approach also cannot leverage higher-order aggregations.Source: §2 · pp. 3–4
• GAP is presented as supporting edge- or node-level privacy, multi-hop aggregation, and inference privacy without public data or additional inference cost.The paper reports that GAP outperforms other baselines in accuracy-privacy trade-off.Source: §2 · p. 4

3.1 Graph Neural Networks

• A GNN learns node representations by aggregating neighboring embeddings and applying a learnable transformation at each layer, then uses final embeddings for node classification.The initial embeddings are node features; prediction can use a softmax layer on the final embeddings.Source: §3.1 · p. 4

3.2 Differential Privacy

• Differential privacy aims to keep an algorithm’s output distribution similar whether an individual’s data is included, with privacy budget ε governing the privacy-utility trade-off.Post-processing preserves DP, while sequential and parallel composition describe how repeated or disjoint-data mechanisms affect guarantees.Source: §3.2 · p. 5
• Rényi Differential Privacy provides an alternative privacy definition with tighter sequential composition, and can be converted to standard (ε,δ)-DP.The Gaussian mechanism adds noise calibrated to a function’s sensitivity.Source: §3.2 · p. 5

3.3 Problem Definition

• The paper targets privacy for both GNN training and inference because inference still uses adjacency information to predict labels.The learning objective trains model parameters on labeled nodes, while prediction may be transductive on the same graph or inductive on a new graph.Source: §3.3 · p. 5
• Edge-level adjacency differs by one edge, whereas node-level adjacency differs by one node together with its features, labels, and attached edges.These adjacency notions define which graph changes a privacy guarantee must conceal.Source: §3.3 · p. 5
• Edge-level DP protects graph connections, while node-level DP protects the node and its adjacent edges.Node-level protection therefore covers information beyond graph structure alone.Source: §3.3 · p. 5

4.1 Overview

• GAP decouples graph-based aggregation from neural-network transformations in a three-module architecture: encoder, aggregation, and classification.The encoder avoids graph structure, the aggregation module perturbs each aggregation, and the classifier predicts without querying edges further.Source: §4.1 · p. 6

4.2 Encoder Module

• The encoder maps node features to a lower-dimensional representation, reducing the dimensionality of the aggregation module’s input, where Gaussian noise grows with data dimensionality.It is pretrained separately using node features and labels; its encoded representations incorporate label information and reduce the need to update private aggregations with encoder parameters.Source: §4.2 · p. 6

4.3 Aggregation Module

• Private Multi-hop Aggregation recursively computes normalized sum aggregations and adds independent Gaussian noise to each row at every hop.The sum aggregation is Aᵀ·X; row normalization bounds each feature vector’s effect on later aggregations, and recursive steps can dampen some previously added noise.Source: §4.3 · pp. 6–7
• Pretraining lets the aggregation mechanism run once for K hops and its output be cached, rather than recomputing aggregation at every training iteration.The paper states that privacy composition is K times instead of K·T, where K is small relative to the number of training iterations T.Source: §4.3 · p. 7, §4.5 · p. 8

4.4 Classification Module

• The classification module processes graph-agnostic features and each private hop aggregation with corresponding MLPs, combines the representations, and predicts labels with a head MLP.Keeping lower-hop and graph-agnostic features available preserves those signals if noise overwhelms higher-hop aggregations.Source: §4.4 · p. 7

4.5 Inference Mechanism

• In transductive inference, the classifier uses cached private aggregations for test nodes; in inductive inference, the new graph is encoded and privately aggregated before classification.The classifier does not need to query graph edges at inference.Source: §4.1 · p. 6, §4.5 · pp. 7–8

5.1 Edge-Level Privacy

• The PMA mechanism satisfies edge-level (α, Kα/2σ²)-RDP, and GAP’s edge-level privacy cost grows with K but is independent of training steps.The architecture avoids repeated aggregation queries at every training update.Source: §5.1 · p. 8
• GAP preserves edge-level privacy at inference without additional privacy cost in both transductive and inductive settings.Transductive inference post-processes cached private aggregations; inductive inference uses disjoint training and test graphs, enabling parallel composition.Source: §5.1 · p. 8

5.2 Node-Level Privacy

• Node-level privacy requires bounded-degree graphs for aggregation sensitivity control and private training of the encoder and classifier because they access node features and labels.The paper proposes DP-SGD or another differentially private learning algorithm for those modules.Source: §5.2 · p. 8
• For maximum degree D and hop count K, PMA satisfies node-level (α, DKα/2σ²)-RDP; GAP’s node-level guarantee also composes the encoder and classifier privacy costs.The stated (ε,δ)-DP bound includes ε₁(α), ε₅(α), DKα/2σ², and log(1/δ)/(α−1).Source: §5.2 · p. 9
• Node-level inference privacy follows the edge-level argument, but an inductive test graph must also have bounded degree.Source: §5.1 · p. 8, §5.2 · p. 9

Choice of aggregation function

• Sum aggregation’s sensitivity does not depend on neighborhood size, unlike Mean and GCN aggregation, which depend on node degrees and require additional privacy budget to perturb them.The paper also identifies Sum as an expressive aggregation function.Source: §6 · p. 9

Normalization instead of clipping

• Normalization bounds each feature’s effect on sum aggregation and, compared with clipping, produces normalized data that the classifier can learn from more readily.The paper notes that non-private GNNs also commonly normalize embeddings to stabilize training.Source: §6 · p. 9

Limitations

• With fixed noise, higher-degree nodes have more accurate noisy aggregates, so low average degree can require higher privacy budgets for acceptable accuracy.The paper says this limited-data effect is shared by DP algorithms generally.Source: §6 · p. 9

Edge-level vs. node-level privacy

• Edge-level privacy is appropriate only when node-level information is nonsensitive or public; sensitive node features or labels call for node-level privacy.Source: §6 · p. 9

7.2 Competing Methods

• Comparisons include GAP and GraphSAGE variants for edge- and node-level privacy, non-private counterparts, and MLP baselines that do not use graph edges.The node-level SAGE-NDP baseline is limited to one GNN layer and receives added test-time aggregation noise for inference privacy.Source: §7.2 · p. 10

7.3 Experimental Setup

• Models are tuned across hop counts and degree bounds, trained with separate procedures for private and non-private methods, and evaluated by average test accuracy with 95% bootstrap confidence intervals.Privacy accounting uses the Analytical Moments Accountant; δ is smaller than the inverse number of private entities.Source: §7.3 · p. 10

7.4.1 Trade-offs between Privacy and Accuracy

• Under edge-level privacy, GAP-EDP exceeds the best competitor by about 26, 14, and 15 accuracy points on Facebook, Reddit, and Amazon; under node-level privacy, GAP-NDP leads by about 13, 13, and 4 points, respectively.In the non-private setting, GAP is competitive with GraphSAGE, with slight accuracy decreases on Facebook and Amazon.Source: §7.4.1 · p. 11, Table 2 · p. 11
• GAP-EDP consistently outperforms SAGE-EDP, while GAP-NDP matches or exceeds MLP-DP and outperforms SAGE-NDP across tested privacy budgets.GAP-EDP approaches non-private GAP at lower budgets and always exceeds vanilla MLP; SAGE-EDP struggles on higher-degree graphs and cannot beat MLP on Amazon.Source: §7.4.1 · p. 11, Figure 6 · p. 12

7.4.2 Resilience Against Privacy Attacks

• At ε=16, differential privacy reduces membership-inference attack AUC to about 50%, the random baseline, across datasets for private GNN methods.The attack uses a shadow graph and model; non-private methods are vulnerable particularly on Facebook and Amazon.Source: §7.4.2 · pp. 11–12, Table 3 · p. 12

7.4.3 Ablation Studies

• The encoder improves GAP accuracy across datasets; more hops can help until added aggregation noise offsets the benefit, with lower privacy budgets favoring smaller hop counts.Encoder gains are attributed to reduced aggregation-input dimensionality and are more pronounced for node-level privacy.Source: §7.4.3 · pp. 12–13, Figure 7 · p. 13, Figure 8 · p. 13
• Increasing GAP-NDP’s degree bound keeps improving Reddit accuracy, while Facebook and Amazon peak and then decline as added neighbors trade off against greater sensitivity and noise.The accuracy gain from increasing the bound grows with a higher privacy budget.Source: §7.4.3 · p. 13, Figure 9 · p. 13

8 Conclusion

• GAP applies the Gaussian mechanism to GNN aggregation and targets both edge-level and node-level differential privacy for training and inference.The paper identifies tighter composition for large hop counts and extensions to other tasks as future directions.Source: §8 · p. 13
• Experiments on real-world graph datasets show favorable privacy-accuracy trade-offs and significant outperformance of existing methods.Source: §8 · p. 13
• The paper proposes future work on robust aggregation, tighter composition for large hop counts, additional tasks and scenarios, and extended theoretical analysis.Source: §8 · p. 13

A.1 Proof of Theorem 1

• Under row-normalized input features, summation aggregation has edge-level sensitivity ΔAgg = 1.Source: §A.1 · p. 17
• Each Gaussian-mechanism application to the aggregation output is (α, α/2σ^2)-RDP.The proof uses the sensitivity bound established by Lemma 1.Source: §A.1 · p. 17
• Composing the K aggregation mechanisms gives total privacy cost (α, Kα/2σ^2)-RDP.Source: §A.1 · p. 17

A.2 Proof of Proposition 2

• The PMA mechanism is the only step that uses graph adjacency, with privacy cost (α, Kα/2σ^2)-RDP.Source: §A.2 · p. 17
• Because EM does not use graph edges and classification post-processes private aggregated features, the total privacy cost remains unchanged.The classifier does not access graph edges again.Source: §A.2 · p. 17

A.3 Proof of Theorem 2

• With row-normalized features, neighborhood summation has node-level sensitivity Δagg = 1.Source: §A.3 · p. 17
• For maximum degree D, independently noised aggregation queries have privacy cost (Dα, α/2σ^2)-RDP because each node contributes to at most D queries.The queries are non-adaptive, and Gaussian noise is independently drawn for each query.Source: §A.3 · p. 18
• Across K aggregation steps, PMA has total privacy cost (α, αDK/2σ^2)-RDP.Source: §A.3 · p. 18

A.4 Proof of Proposition 3

• Algorithm 2 has total node-level privacy cost (α, ε1(α) + D_Kα/2σ² + ε5(α))-RDP.The proof derives this bound by adaptive composition.Source: §A.4 · p. 18
• The first step privately processes node features and labels with (α, ε1(α))-RDP.Under node-level DP, the proof treats an individual's features, label, and edges as private.Source: §A.4 · p. 18
• Steps 4 and 5 provide (α, D_Kα/2σ²)-RDP and (α, ε5(α))-RDP mechanisms, respectively.These mechanisms process private node features exposed by steps 2 and 3.Source: §A.4 · p. 18