How does Graph Structure Modulate Membership-Inference Risk for Graph Neural Networks?
Megha Khosla · 2026
Read How does Graph Structure Modulate Membership-Inference Risk for Graph Neural Networks? by Megha Khosla (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17130.txt.
Introduction
Megha Khosla asks how graph shape sways leak risk in graph neural nets. Such nets learn from webs of linked facts. They ace tasks like node tags and link calls. But they may leak if a fact was in their train set. Foes can probe that leak with sly asks. Her 2026 preprint ties the leak risk to the web's shape.
Dense hubs and tight crowds may leak more than loose webs. Shape-wise maps can warn where leaks run high. Health and bank webs need such warns most. Their facts are the most dear if leaked. This work gives builders a shape check for risk.
Catalog record
| CREATOR | Megha Khosla |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-17130
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
How does Graph Structure Modulate Membership-Inference Risk for Graph Neural Networks? Megha Khosla Abstract Graph neural networks (GNNs) have become the standard tool for encoding data and their complex relationships into continuous representations, improving prediction accuracy in several machine learning tasks like node classification, link prediction etc. However, their use in sensitive applications has raised concerns about the potential leakage of training data. Research on privacy leakage in GNNs has largely been shaped by findings from non-graph domains, such as images and tabular data. We emphasize the need of graph specific analysis and investigate the impact of graph structure on node level membership inference. We formalize MI over node–neighbourhood tuples and investigate two important dimensions: (i) training – graph construction and (ii) inference-time edge access. Empirically, snowball’s coverage bias often harms generalisation relative to random sampling, while enabling inter–train–test edges at inference improves test accuracy, shrinks the train–test gap, and yields the lowest membership advantage across most of the models and datasets. We further show that the generalisation gap empirically measured as the performance difference between the train and test nodes is an incomplete proxy for MI risk: access to edges dominates—MI can rise or fall independent of gap changes. Finally, we examine the auditability of differentially private GNNs, adapting the definition of statistical exchangeability of train-test data points for graph based models. We show that for node level tasks the inductive splits (random or snowball sampled) break exchangeability, limiting the applicability of standard bounds for membership advantage of differential private models. I Introduction Graph Neural Networks (GNNs) have become the de-facto standard for learning on relational data, delivering state-of-the-art results in chemistry, recommender systems, knowledge graphs, and more [ 7 , 26 , 25 ] . However on the downside, GNNs have been shown to leak private information about the very graphs they are trained on [ 5 , 3 , 9 , 15 , 30 , 32 , 4 , 31 , 19 ] . Existing privacy risk studies for GNNs mainly adapt techniques from the i.i.d. scenario of images [ 28 ] , treating each example as independent and largely ignoring the graph structure that binds data points together. We focus on membership inference risk: given access to a trained model, an adversary aims to determine whether a specific data instance was included in its training set. In graph based machine learning using graph neural networks, what is considered as a data instance depends on the task: node-level tasks view each node as an instance (e.g., predicting a protein’s function in a PPI network), edge-level tasks treat each edge as an instance (e.g., recommending a friendship), and graph-level tasks consider the entire graph as a single instance (e.g., classifying a molecule’s toxicity). Our study focuses on the node-level cases, where those instances are inherently interdependent due to the existence of edges between them. This inter-instance dependency is largely absent from prior privacy analyses and leads us to ask: How strongly does the amount of edge information available during training and at inference modulate node-level membership-inference risk? To investigate this question, we start from the inductive setting of [ 19 ] , where training and test node sets are disjoint and, during training, neither test nodes nor any train–test edges are available. A common way to instantiate such splits is to sample train/test nodes uniformly at random and use the induced subgraphs; while this preserves independence among sampled nodes, it is often unrealistic as random node sampling can result in isolated nodes if none of their neighbours are included, undermining the rationale for graph-based learning. A more plausible training paradigm is edge-guided sampling. Analogous to a web crawler that follows hyperlinks, we adopt snowball sampling : starting from seeds, we iteratively add a fixed number of randomly chosen neighbours until the desired training size is reached. This produces a well-connected training graph but is inherently coverage-biased in which expansions tend to remain within a few regions, oversampling high-degree hubs while leaving peripheral or distinct communities under-represented. The resulting training distribution is therefore non-i.i.d. with respect to the full graph, motivating our first axis of inquiry: how does such biased coverage affect generalisation to held-out nodes and, in turn, membership-inference (MI) risk? A natural second, graph-specific axis is edge access at inference . In our node–neighbourhood formulation, each query supplies a subgraph, and a GNN’s prediction for the given node depends on that subgraph at query time. Even with a fixed train–test node split, adding or withholding edges can substantially alter the outputs of a frozen model. Unlike i.i.d. domains, an adversary may legitimately provide relational context when probing membership. We therefore ask: how does the adversary’s edge knowledge modulate MI success? Thirdly, MI success is often linked to overfitting and generalisation error [ 34 ] . Because the true data-generating distribution is unknown, practitioners use the empirical train–test gap as a surrogate. Yet prior work suggests that attacker performance does not always increase with this empirical gap in graph settings [ 19 ] . Here, the gap itself depends not only on which nodes are selected for train/test but also on which neighbourhoods are presented at inference. This leads to our third guiding question: what is the relationship between the generalisation gap and membership inference risk across training-graph constructions (random vs. snowball) and inference-time edge regimes? Finally, we study the theoretical implications of graph sampling and edge structure on bounding membership advantage (MA) for differentially private models. We adapt the definition of statistical exchangeability from [ 12 ] to GNNs by treating each example as a node and neighbourhood tuple and show that inductive train/test constructions, whether by random node sampling or snowball sampling, break exchangeability because neighbourhoods are restricted to, and dependent on, the sampled training subgraph. Consequently, the standard MA bounds are not reliable auditing surrogates in these regimes. We identify conditions under which exchangeability can hold, clarifying when DP-based MA bounds are auditable and when empirical MI evaluation is necessary. Next, we introduce the GNN architectures used in our experiments and then provide a brief overview of membership-inference attacks and defenses for GNNs to contextualize our study. II Background and Related Work We begin with a brief overview of graph neural networks which will serve as target or victim models in this work. Specifically, to demonstrate the effect of graph structure on effectiveness of MI attack, we employ three types of GNNs which differ in strategies to aggregate information from the node’s neighborhood towards learning its representation. II-A Graph Neural Networks Graph Neural Networks (GNNs) are a class of machine learning models designed specifically to learn on graph-structured data. The typical input to a GNN consists of two elements: (\mathbf{X},\mathbf{A}) . Here, \mathbf{X}=(\mathbf{x}_{1}^{\top},\mathbf{x}_{2}^{\top},\ldots,\mathbf{x}^{\top}_{n}) represents the feature matrix for the nodes in the graph where \mathbf{x}_{i} is the input feature vector for node i . The adjacency matrix is represented by \mathbf{A}\in\mathbb{R}^{n\times n} which encodes the connectivity between nodes. The core operation in GNNs is graph convolution, where each node’s representation is updated by aggregating its own features along with the features of its neighbors. After this aggregation step, the node’s representation is transformed using a non-linear function. More formally, let \mathbf{x}_{i}^{(\ell)} denote the feature representation