# Impact of Graph Structure on Membership-Inference Risk for Graph Neural Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 28 references that are in the map.
- First posted on arXiv 23 Jan 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [ML-Leaks: Model and Data Independent Membership Inference Attacks and Defenses on Machine Learning Models](https://mlsanity.com/paper/1806.01246/) (2018)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Node-Level Membership Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2102.05429/) (2021)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [Locally Private Graph Neural Networks](https://mlsanity.com/paper/2006.05535/) (2020)
- [Adapting Membership Inference Attacks to GNN for Graph Classification: Approaches and Implications](https://mlsanity.com/paper/2110.08760/) (2021)
- [Investigating Membership Inference Attacks under Data Dependencies](https://mlsanity.com/paper/2010.12112/) (2020)
- [Releasing Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2109.08907/) (2021)
- [PANORAMIA: Privacy Auditing of Machine Learning Models without Retraining](https://mlsanity.com/paper/2402.09477/) (2024)
- [Membership Inference Attacks on Knowledge Graphs](https://mlsanity.com/paper/2104.08273/) (2021)

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

- [Bayesian Membership Privacy for Graph Neural Networks](https://mlsanity.com/paper/2606.04069/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) are widely used for tasks such as node classification and link prediction, but their use in sensitive settings raises concerns about training-data leakage. Prior work on privacy leakage in GNNs largely borrows assumptions from non-graph domains, overlooking the role of graph structure. We argue for a graph-specific analysis of privacy risk and study how graph structure affects node-level membership inference. We formalize membership inference (MI) over node-neighborhood tuples and investigate two important dimensions: (i) training-graph construction and (ii) inference-time edge access. We compare snowball sampling, a structure-aware procedure, with uniform random node sampling for constructing training graphs. Our experiments show that snowball sampling often hurts generalization relative to random sampling due to its coverage bias. In contrast, allowing access to inter-train-test edges at inference improves test accuracy, reduces the train-test gap, while also having a strong and setting-dependent effect on membership advantage. These results show that graph structure directly shapes privacy risk. We further show that the generalization gap, measured as the performance difference between training and test nodes, is an incomplete proxy for membership inference risk: membership advantage can rise or fall independently of changes in this gap, with inference-time edge access often playing a crucial role. Theoretically, we show that for node-level tasks, standard privacy-auditing results based on membership inference do not directly carry over to inductive graph settings, because training and test nodes are structurally dependent rather than interchangeable. We release the code and data at https://github.com/PriXAI/GraphStructurePrivacyAnalysis-public.