# Preserving Node-level Privacy in Graph Neural Networks

arXiv: https://arxiv.org/abs/2311.06888 · HTML: https://mlsanity.com/paper/2311.06888/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 63 references that are in the map.
- First posted on arXiv 12 Nov 2023.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [Hypothesis Testing Interpretations and Renyi Differential Privacy](https://mlsanity.com/paper/1905.09982/) (2019)
- [Node-Level Membership Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2102.05429/) (2021)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Adapting Membership Inference Attacks to GNN for Graph Classification: Approaches and Implications](https://mlsanity.com/paper/2110.08760/) (2021)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Releasing Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2109.08907/) (2021)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2310.15526/) (2023)
- [LPGNet: Link Private Graph Networks for Node Classification](https://mlsanity.com/paper/2205.03105/) (2022)
- [Differentially Private Continual Release of Graph Statistics](https://mlsanity.com/paper/1809.02575/) (2018)

## Built on by (most cited first, 11 of 11)

- [Towards Lifecycle Unlearning Commitment Management: Measuring Sample-level Unlearning Completeness](https://mlsanity.com/paper/2506.06112/) (2025)
- [Revisiting Differentially Private Hyper-parameter Tuning](https://mlsanity.com/paper/2402.13087/) (2024)
- [The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditing](https://mlsanity.com/paper/2506.16666/) (2025)
- [Attributing Data for Sharpness-Aware Minimization](https://mlsanity.com/paper/2507.04059/) (2025)
- [AdvSGM: Differentially Private Graph Learning via Adversarial Skip-gram Model](https://mlsanity.com/paper/2503.21426/) (2025)
- [Pre-trained Encoder Inference: Revealing Upstream Encoders In Downstream Machine Learning Services](https://mlsanity.com/paper/2408.02814/) (2024)
- [Structure-Preference Enabled Graph Embedding Generation under Differential Privacy](https://mlsanity.com/paper/2501.03451/) (2025)
- [DP-GPL: Differentially Private Graph Prompt Learning](https://mlsanity.com/paper/2503.10544/) (2025)
- [Efficient Text-Attributed Graph Learning through Selective Annotation and Graph Alignment](https://mlsanity.com/paper/2506.07168/) (2025)
- [Differentially Private Relational Learning with Entity-level Privacy Guarantees](https://mlsanity.com/paper/2506.08347/) (2025)
- [GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning](https://mlsanity.com/paper/2511.10936/) (2025)

## Abstract (arXiv)

Differential privacy (DP) has seen immense applications in learning on tabular, image, and sequential data where instance-level privacy is concerned. In learning on graphs, contrastingly, works on node-level privacy are highly sparse. Challenges arise as existing DP protocols hardly apply to the message-passing mechanism in Graph Neural Networks (GNNs). In this study, we propose a solution that specifically addresses the issue of node-level privacy. Our protocol consists of two main components: 1) a sampling routine called HeterPoisson, which employs a specialized node sampling strategy and a series of tailored operations to generate a batch of sub-graphs with desired properties, and 2) a randomization routine that utilizes symmetric multivariate Laplace (SML) noise instead of the commonly used Gaussian noise. Our privacy accounting shows this particular combination provides a non-trivial privacy guarantee. In addition, our protocol enables GNN learning with good performance, as demonstrated by experiments on five real-world datasets; compared with existing baselines, our method shows significant advantages, especially in the high privacy regime. Experimentally, we also 1) perform membership inference attacks against our protocol and 2) apply privacy audit techniques to confirm our protocol's privacy integrity. In the sequel, we present a study on a seemingly appealing approach citesajadmanesh2023gap (USENIX'23) that protects node-level privacy via differentially private node/instance embeddings. Unfortunately, such work has fundamental privacy flaws, which are identified through a thorough case study. More importantly, we prove an impossibility result of achieving both (strong) privacy and (acceptable) utility through private instance embedding. The implication is that such an approach has intrinsic utility barriers when enforcing differential privacy.