PaperlayerView exact revision on arXiv

Source-linked AI summary

Releasing Graph Neural Networks with Differential Privacy Guarantees

Iyiola E. Olatunji, Thorben Funke, Megha Khosla

arXiv:2109.08907v2cs.LGcs.CR

TL;DR

GNNs are vulnerable to membership-inference attacks, and DP-SGD’s assumptions do not transfer straightforwardly to graph data. PrivGnn distills private-graph teacher knowledge into a student trained on public data, with subsampling and noisy labeling. The authors report good accuracy under practical privacy guarantees across six real-world datasets.

  • Problem

    GNNs are vulnerable to membership-inference attacks, while DP-SGD’s i.i.d. batching assumptions do not trivially hold for graph data with message passing.

    Source: §1 · pp. 1–2

  • Method

    PrivGnn transfers knowledge from a private-graph teacher to a public-graph student using Poisson subsampling and noisy pseudo-labels for public nodes.

    Source: §1 · p. 2, §3.1.3 · p. 5

  • Results

    PrivGnn’s experiments on six real-world datasets show good accuracy under practical privacy guarantees, and the paper reports robustness to two membership-inference attacks.

    Source: §1 · p. 3, §6 · p. 13

  • Takeaways & Limitations

    The released student model is differentially private through the applied noise mechanisms and post-processing, within the described public-graph setting.

    Source: §3 · p. 3, §3.1.3 · p. 5

    PrivGnn assumes access to a public graph and provides node-DP guarantees, described as stronger than edge differential privacy.

    Source: §3 · p. 3, §3.1.4 · p. 6

Abstract

from arXiv · show

With the increasing popularity of graph neural networks (GNNs) in several sensitive applications like healthcare and medicine, concerns have been raised over the privacy aspects of trained GNNs. More notably, GNNs are vulnerable to privacy attacks, such as membership inference attacks, even if only black-box access to the trained model is granted. We propose PrivGNN, a privacy-preserving framework for releasing GNN models in a centralized setting. Assuming an access to a public unlabeled graph, PrivGNN provides a framework to release GNN models trained explicitly on public data along with knowledge obtained from the private data in a privacy preserving manner. PrivGNN combines the knowledge-distillation framework with the two noise mechanisms, random subsampling, and noisy labeling, to ensure rigorous privacy guarantees. We theoretically analyze our approach in the Renyi differential privacy framework. Besides, we show the solid experimental performance of our method compared to several baselines adapted for graph-structured data. Our code is available at https://github.com/iyempissy/privGnn.

1 Introduction

GNNs can expose training membership, while standard differential-privacy methods do not transfer straightforwardly to graph data. PrivGnn combines teacher–student distillation with subsampling and noisy labels to release a differentially private GNN.

1 Introduction

  • GNNs are vulnerable to membership-inference attacks, which seek to identify training data points.The introduction also notes that graph structure is encoded in the model and that data-protection policies motivate privacy-preserving GNNs.Source: §1 · pp. 1–2
  • DP-SGD’s i.i.d. batching assumptions do not trivially hold for GNNs, whose message passing links nodes, and its noise can further degrade performance.The introduction also cites slow training and noise proportional to the number of epochs as DP-SGD drawbacks.Source: §1 · p. 2
  • PATE’s disjoint teacher-training splits can destroy graph structure and adversely affect accuracy.Source: §1 · p. 2
  • PrivGnn transfers knowledge from a private-graph teacher to a public-graph student, using Poisson subsampling and noisy pseudo-labels for public query nodes.The released model is the student; the workflow retrieves private neighbors for each public query node before training its teacher.Source: §1 · pp. 2–3, Figure 1 · p. 2
  • The paper presents an RDP analysis with tight privacy-loss bounds and reports large-scale empirical utility and robustness to two membership-inference attacks.Source: §1 · p. 3

2 Related Works

Prior privacy-preserving GNN work includes distributed and centralized approaches, with different privacy assumptions and graph tasks. The section describes challenges in applying DP-SGD to graph data and identifies other approaches to protecting node features or perturbing graph data.

2 Related Works

  • GNNs encode graph structure through neighbor aggregation and are vulnerable to membership-inference attacks.Source: §2 · p. 3
  • Distributed approaches address settings with data split among parties, including node-level privacy, federated recommendation, node classification, and secure pooling.The cited works assume varying partitions of features, edges, nodes, and labels.Source: §2 · p. 3
  • Centralized methods include private node-feature representations, DP-SGD adaptations, and randomized response applied to node features and graph structure.The section notes that one DP-SGD adaptation’s guarantees might not hold because graph message passing conflicts with its i.i.d. batching assumptions.Source: §2 · p. 3

3 Our Approach

PrivGnn assumes access to a labeled private graph and an unlabeled public graph, and transfers private-graph knowledge to a public-graph student through query-specific teachers. Random subsampling, noisy pseudo-labels, and RDP analysis support its node-level privacy guarantees.

3 Our Approach

  • PrivGnn assumes a labeled private graph and an available public graph with node features but no labels.The public graph supplies query nodes and data for student training.Source: §3 · p. 3

3.1 PRIVGNN Framework

  • The framework has three phases: private-data selection, retrieval of noisy pseudo-labels, and student-model training.It samples public query nodes and uses their noisy labels to train the student.Source: §3.1 · p. 4

3.1.1 Private data selection (Lines 4-5)

  • For each query, Poisson subsampling selects private nodes before the method retrieves K nearest neighbors by feature distance to build an induced subgraph for a query-specific teacher.The sampled subset is selected independently at sampling ratio γ; the retrieved subgraph supplies features and labels for teacher training.Source: §3.1.1 · pp. 4–5

3.1.2 Retrieving noisy pseudo-labels (Lines 6-7)

  • A teacher trained on the selected private subgraph predicts each public query using its ℓ-hop neighborhood, and independent Laplacian noise is added to posterior coordinates to produce the pseudo-label.The noise scale is β = 1/λ.Source: §3.1.2 · p. 5

3.1.3 Student model (transductive) training

  • The public student is trained transductively on privately pseudo-labeled query nodes and unlabeled public data, then released as differentially private through the two noise mechanisms and post-processing.Private teachers answer only a selected number of queries because each query incurs additional privacy cost.Source: §3.1.3 · p. 5

3.1.4 Privacy analysis

  • The privacy analysis uses RDP to characterize guarantees and compose heterogeneous mechanisms, including mechanisms applied to subsamples, before conversion to (ε, δ)-DP.The paper also invokes subsampling amplification and advanced RDP composition.Source: §3.1.4 · pp. 5–6

3.2 Privacy Guarantees of PRIVGNN

  • Theorem 7 states that Algorithm 1 satisfies (ε, δ)-DP for any δ > 0, with the bound depending on query nodes and the Laplace scale.The proof sketch composes noisy-label privacy costs across subsampled data and Q queries; the displayed bound is described as a rough upper bound, while experiments numerically compute ε.Source: §3.2 · p. 7

4 Experimental Evaluation

The evaluation is organized around comparisons with baselines, privacy and utility trade-offs, and the effects of design choices. Experiments use four main graph datasets, with additional datasets, specified baselines, and shared model and privacy settings.

4 Experimental Evaluation

  • The evaluation asks how PrivGnn compares with baselines in performance and privacy, and examines neighbor sampling, query-count privacy budgets, sampling ratios, and design choices.Additional experiments examine membership-inference robustness, dataset-size sensitivity, pre-training, resource requirements, and cases with more informative features.Source: §4 · p. 7

4.1 Experimental Setup

  • Experiments use Amazon, Amazon2M, Reddit, and Facebook, with additional ArXiv and Credit defaulter graph experiments on highly informative features.Dataset statistics are referenced in Table 11.Source: §4.1 · p. 7
  • Baselines include non-private inductive and transductive GNNs plus PateM and PateG variants using MLP and GNN teachers.The transductive baseline trains on the public training split with ground-truth labels and estimates best-possible public-data performance.Source: §4.1 · p. 7
  • Private and public GNNs use two-layer GraphSAGE models, while PateM uses a three-layer MLP; experiments report means over 10 instantiations.The sampling ratio γ is 0.3 except for Amazon2M, where it is 0.1; δ is 10^-4 for Amazon, Facebook, Credit, and Reddit, and 10^-5 for ArXiv and Amazon2M.Source: §4.1 · p. 8

5 Results

Across five research questions, PrivGnn is evaluated for its privacy-utility trade-off, query and sampling choices, ablations, and additional tests. The reported results show better accuracy and lower privacy costs than PATE variants, with performance also varying by design choice.

5.1 Privacy-utility Trade-off (RQ 1)

  • PrivGnn significantly outperforms PateM and PateG in accuracy while incurring lower privacy budgets; it also surpasses B1 on Amazon2M, Facebook, and Reddit when λ > 0.4.At λ = 0.2 on Amazon, reported accuracy improvements over PateM and PateG are 40% and 300%, respectively; PrivGnn’s ε is 8.53 versus PATE values from 157.90 to 173.82 across datasets.Source: §5.1 · p. 9

5.2 Effect of K on the Accuracy (RQ 2)

  • Higher K generally increases accuracy: K = 750 improves Amazon accuracy by over 50% versus K = 300, while K above 1000 adds only marginal accuracy on Amazon2M, Reddit, and Facebook.The authors infer that K should depend on average degree: smaller K suffices for sparse Amazon, while larger K helps higher-degree graphs.Source: §5.2 · p. 9

5.3 Effect of |Q| on the Accuracy and Privacy (RQ 3)

  • Using 500 rather than 1,000 query nodes yields negligible accuracy change except on Amazon2M, while PrivGnn’s ε falls by 50% on Amazon, Reddit, and Facebook and 40% on Amazon2M.The reported privacy-budget reduction versus PATE variants exceeds 20 times across all datasets.Source: §5.3 · p. 10, Figure 3 · p. 10, Table 2 · p. 11

5.4 Varying Subsampling Ratio γ (RQ 4)

  • With γ = 0.1 rather than 0.3, Amazon2M accuracy decreases by 6%, while Reddit accuracy decreases by 35% and its privacy budget falls by 315%.The authors conclude that smaller γ can substantially reduce privacy costs with relatively lower accuracy degradation on larger datasets.Source: §5.4 · pp. 10–11, Table 3 · p. 11

5.5 Ablation Studies (RQ 5)

  • At λ = 0.2, SingleGNN performs worse than PrivGnn, with drops of 23% on Amazon2M and 12% on Reddit, highlighting the benefits of multiple subsampling and KNN components.KNN uses the most informative node for a query when training and predicting its pseudo-label.Source: §5.5 · p. 12
  • Additional experiments report that PrivGnn reduces two membership-inference attacks to random-guess performance and is not sensitive to private/public graph size.Highly informative features also yield better performance than PateM and PateG, while pre-training slightly improves PrivGnn’s performance.Source: §5.5 · p. 12

6 Conclusion

PrivGnn transfers private-graph teacher knowledge to a student model and uses subsampling and noisy labels to provide differential privacy guarantees. Experiments on six real-world datasets show good accuracy under practical privacy guarantees.

6 Conclusion

  • Personalized teachers use each query node’s K-nearest neighbors, and ablations support these design choices.The paper analyzes privacy using Rényi differential privacy.Source: §6 · pp. 12–13

Appendix

  • The appendix covers detailed accuracy results, theoretical proofs, membership-inference attacks, sensitivity analyses, applications, baselines, and resource requirements.It also highlights the work’s limitations.Source: Appendix · p. 15

A Detailed Results

The detailed results are presented as mean-accuracy tables for methods across datasets and for varying query counts.

A Detailed Results

  • Table 5 reports performance for each method on all datasets, while non-private baselines B1 and B2 do not vary with λ.The accompanying text identifies the reported values as mean accuracies.Source: A Detailed Results · p. 15, Table 5 · p. 16
  • Table 6 reports mean accuracy as the number of queries varies.Source: Table 6 · p. 16

B Detailed Proof

The appendix motivates and analyzes privacy amplification by subsampling, then gives a Rényi differential privacy proof and reports membership-inference results. In Attack-1, PrivGnn reduced attack performance to near-random guessing.

B Detailed Proof

B.1 Privacy Amplification by Subsampling

  • Subsampling can amplify privacy because a differing record is less likely to appear in the random sample.The appendix applies a Poisson-subsampled RDP amplification bound.Source: §B.1 · p. 17

B.2 Proof of our Privacy Guarantee

  • The privacy proof models private-data sampling for GNN training and Laplace-noised labels for each public query node.It composes privacy loss across queries and converts the RDP bound to an (ε, δ)-DP guarantee.Source: §B.2 · pp. 17–18

C PrivGNN and Membership Inference Attacks

  • The appendix describes membership inference as shadow-model training, attack-model training, and inference against the target model.The attack model is a binary classifier distinguishing training from non-training nodes.Source: C PrivGNN and Membership Inference… · p. 18

C.1 Identifying Private Nodes via MI (Attack-1)

  • Attack-1 achieved AUROC above 0.75 on every dataset against non-private B1, but at most 0.54 against PrivGnn.Source: §C.1 · p. 18

C.2 Identifying Private Nodes by Proxy via MI (Attack-2)

Across these appendix sections, PrivGnn is evaluated through membership-inference attacks, dataset and feature analyses, and comparisons with additional baselines. The sections also describe potential applications and the privacy-utility effect of varying teacher queries.

C.2 Identifying Private Nodes by Proxy via MI (Attack-2)

  • 0.40, 0.51, and 0.54 AUROC on Amazon, ArXiv, and Reddit show Attack-2 at near-random guessing, versus 0.82, 0.75, and 0.87 for non-private B1.Attack-2 tests whether privately labeled public nodes can be distinguished from other public nodes.Source: Figure 4 · p. 19, §C.2 · p. 19

D.1 Impact of Highly Informative Node Features

  • On ArXiv, PrivGnn’s performance was 15% lower than PateM at λ = 0.2, but 1169% higher than PateG.PateM was on par with PrivGnn on both datasets; ArXiv’s average node degree was at most 2.Source: §D.1 · p. 19, Figure 5 · p. 20

D.2 Effect of the Size of the Public Dataset

  • After swapping the public and private dataset portions, PrivGnn showed no significant performance difference and outperformed private baselines on the flipped datasets.The authors report that its performance is not sensitive to public or private dataset size.Source: §D.2 · p. 20, Figure 6 · p. 21

D.3 Real-world Scenario / Motivation

  • The paper describes real-world settings where public and private graphs coexist, including Wikidata and the private Google knowledge graph.It notes that Google’s graph is partly based on Freebase, later acquired by Wikidata.Source: §D.3 · p. 21

D.3.1 Application Example

  • A content-labeling model released without privacy protection could expose participants to membership inference and risk disclosure of costly annotations or trade secrets.The example considers labeling users as bots or real users.Source: §D.3.1 · p. 21

D.4 Joint Training of the Private and Public Graph

  • Joint training baseline B3 and B2 have comparable results, supporting B2 as an estimate of the best possible accuracy on the public graph.Source: §D.4 · p. 22, Table 8 · p. 22

D.5 Adding Noise Directly to the Groundtruth Label of Query Nodes

  • The noisy-oracle baseline B4 performs similarly to or slightly better than PrivGnn, but its extremely high privacy budget makes it unusable.B4 adds Laplace noise directly to ground-truth query labels, an unavailable label source in the paper’s setting.Source: §D.5 · p. 22

D.6 Privacy-utility Tradeoff by Varying the Number of Queries

  • With λ = 0.4, reducing teacher queries lowers accuracy and improves privacy; performance degrades severely below 400 queries.The authors attribute the utility loss to noisy and limited training data.Source: §D.6 · p. 22

D.7 Improving Performance via Pre-training

The section reports gains from pre-training PrivGnn’s student on public graph data and distinguishes its global graph-level privacy setting from several related approaches. It also explains why direct comparisons with those approaches are limited by differing privacy guarantees or data requirements.

D.7 Improving Performance via Pre-training

  • Figure 7 plots accuracy and achieved privacy across query counts, fixing λ=0.4 and γ=0.3 except for Amazon2M, where γ=0.1.Accuracy is the red line on the left axis and privacy the blue line on the right; markers correspond to query counts.Source: Figure 7 · p. 24
  • Pre-training uses graph reconstruction on the public dataset, then initializes the student before fine-tuning it on privately labeled nodes.The authors state that this pre-training uses public data and does not constitute a privacy risk.Source: §D.7 · p. 24
  • At |Q|=300, pre-training increased accuracy by up to 35% on Amazon2M and 17% on ArXiv; at |Q|=1000, increases were up to 4% and 9%, respectively.Table 10 reports the pre-trained model’s percentage difference from randomly initialized PrivGnn.Source: §D.7 · p. 24, Table 10 · p. 25

E.1 Differences with LPGNN Sajadmanesh & Gatica-Perez (2020)

  • LPGNN and HETERORR perturb node-level features or graph data under local-DP guarantees, whereas PrivGnn targets global differential privacy for the graph and released model.The paper says these differing guarantees make direct privacy comparisons inappropriate.Source: §E.1 · p. 25, §E.5 · p. 26

E.2 Differences with VFGNN Zhou et al. (2020)

  • VFGNN uses secure multi-party computation and noisy local embeddings, while FedGNN adds noise to local gradients; their settings do not provide a fair direct comparison with PrivGnn.Removing VFGNN’s secure computation would require local-DP noise, and PrivGnn’s unlabeled public graph lacks labels for FedGNN-style local training.Source: §E.2 · p. 26, §E.3 · p. 26

E.4 Differences with SAPGNN Shan et al. (2021)

  • SAPGNN combines secretly shared local gradients, while GAP requires labeled public data; the paper therefore says the methods cannot be compared directly with PrivGnn.A rough GAP comparison reports 78% accuracy at ε=16 versus PrivGnn’s 70% at a similar ε, but the paper cautions that the settings differ substantially.Source: §E.4 · p. 26, §E.6 · p. 26

E.7 Differences with Zhang et al. (2022)

  • The paper says Zhang et al.’s approach cannot be fairly compared because its overall ε is unclear and its DPSGD assumptions do not fit graph message passing.The discussed method uses APPR to select top-K relevant neighbors for aggregation.Source: §E.7 · p. 27

E.8 Differences with Daigavane et al. (2021)

  • Daigavane et al.’s privacy guarantee is limited to one-layer GNNs and requires neighborhood features at inference, unlike PrivGnn’s separate-graph inductive setting.Source: §E.8 · p. 27

F Datasets

The experiments use six graph datasets spanning product, social, citation, and financial tasks, with private and public graph partitions. The section also defines non-private and PATE baselines and reports shared model-training settings.

F Datasets

  • Amazon and Amazon2M are product co-purchase graphs for category prediction, while Reddit links posts by shared commenters and labels them by community.The Amazon dataset uses a 2,500-node private graph and 3,000-node public train and test sets; Amazon2M has over two million nodes, split into one million private nodes and the remainder public.Source: F Datasets · p. 27
  • Facebook predicts students’ class year from friendship links, ArXiv is a paper-citation network, and Credit predicts payment default from a financial similarity graph.Facebook splits nodes evenly between private and public graphs; ArXiv uses papers through 2017 privately and later papers for public training and testing; Credit has 10,000 private and 15,000 public nodes.Source: F Datasets · pp. 27–28
  • PrivGnn pseudo-labels at most 1,000 public query nodes, and dataset-specific portions of public data are reserved for testing.The test portions are 50% for Amazon, Amazon2M, Reddit, and Credit; 40% for ArXiv; and 20% for Facebook.Source: F Datasets · p. 28, Table 11 · p. 28

G Baselines

  • The baselines include a non-private model trained on private data, a transductive model trained on labeled public data, and PATE variants using GNN teachers or feature-only MLP teachers.PATE partitions private nodes into disjoint subsets and adds noise to aggregated teacher votes; the number of partitions was chosen experimentally.Source: G Baselines · p. 28

G.1 Model and Hyperparameter Setup

  • The GNN teacher and student use two-layer GraphSAGE models with hidden dimension 64, ReLU, dropout 0.5, and learning rate 0.01.Models were trained for 200 epochs with Adam and negative log-likelihood; experiments used 10 instantiations.Source: §G.1 · pp. 28–29

H The Runtime and Space Requirement of PRIVGNN

PrivGnn’s training cost depends on its number of queries, but its space use is limited because teacher models can be discarded after querying. The released model has the same time and space requirements as its corresponding non-private GNN.

H The Runtime and Space Requirement of PRIVGNN

I Limitations and Future Works

The authors identify query reduction and analysis of learned representations as areas for further work. Fewer queries reduce the privacy budget but also affect accuracy.

I Limitations and Future Works

  • Fewer queries significantly reduce ε, but also have a relative effect on released-model accuracy.The authors suggest exploring active learning or unsupervised query-reduction methods that can achieve high accuracy.Source: I Limitations and Future Works · p. 29
  • Explanation methods are needed to examine PrivGnn’s learned representations and compare private with non-private models.The authors say such analysis would help clarify the internal workings of private models.Source: I Limitations and Future Works · p. 29

Related papers

Loading 2109.08907v2…