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

Megha Khosla (Paper author · Delft University of Technology)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 3 · Caribou

Overview

This talk delves into the critical, yet often overlooked, challenge of membership inference attacks (MIA) on Graph Neural Networks (GNNs), specifically investigating how the underlying graph structure profoundly influences privacy leakage. Presented by Megha Khosla of Delft University of Technology, the research highlights a fundamental difference between traditional machine learning models trained on independent and identically distributed (IID) data and GNNs, where the input for a given node inherently includes its neighborhood. This structural dependency introduces unique vulnerabilities and complexities in assessing privacy risks.

Watch on YouTube · Slides

Visual summary for Impact of Graph Structure on Membership-Inference Risk for Graph Neural Networks by Megha Khosla
Visual summary for Impact of Graph Structure on Membership-Inference Risk for Graph Neural Networks by Megha Khosla

Key moments

  1. 0:00 Introduction to membership inference for graph data
  2. 3:30 How graph structure impacts training and inference
  3. 5:30 Comparing random and structured graph sampling techniques
  4. 8:00 Generalization gap nuance for GNN membership inference
  5. 9:00 Membership advantage vs. performance gap findings
  6. 10:10 Key takeaways and conclusions from the research

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

Speakers: Megha Khosla, Paper author, Delft University of Technology

Conference: PETS

YouTube: https://www.youtube.com/watch?v=Ccw_VPVvaB0

Overview

This talk delves into the critical, yet often overlooked, challenge of membership inference attacks (MIA) on Graph Neural Networks (GNNs), specifically investigating how the underlying graph structure profoundly influences privacy leakage. Presented by Megha Khosla of Delft University of Technology, the research highlights a fundamental difference between traditional machine learning models trained on independent and identically distributed (IID) data and GNNs, where the input for a given node inherently includes its neighborhood. This structural dependency introduces unique vulnerabilities and complexities in assessing privacy risks.

Membership inference attacks aim to determine whether a specific data point (in this case, a node in a graph) was part of the training dataset used to build a machine learning model. This is crucial for two primary reasons: first, the membership itself might be sensitive information that users wish to keep private, such as being identified as part of a specific group used for model training due to a particular characteristic. Second, MIAs often serve as a proxy for more sophisticated attacks; if an adversary cannot even infer membership, it becomes significantly harder for them to reconstruct the original training data or extract sensitive attributes. The talk argues that for GNNs, the way the training graph is constructed and the availability of edge information during inference are pivotal, directly modulating the risk of such attacks.

Background

▶ Watch: Introduction to membership inference for graph data (0:00)

Graph Neural Networks are powerful models designed to process data structured as graphs, common in social networks, recommendation systems, and biological networks. Unlike conventional neural networks that operate on isolated data points, GNNs leverage the relational information embedded in the graph structure. A key characteristic of GNNs is that for any given node V, the model's input is not just the features of V but also an aggregation of the features and representations of its neighborhood. This aggregation process, often occurring in layers, means that the effective "instance" presented to the model is V and its surrounding structure.

This inherent dependency on graph structure introduces complexities that are not present in IID data settings. The speaker identifies two critical stages where graph structure plays a significant role:

  1. Training Graph Construction: How the subset of the larger graph is extracted to train the GNN is paramount. If node V is trained with a rich, interconnected neighborhood, its representation will differ significantly from a scenario where it appears as an isolated node or with a sparse neighborhood. Furthermore, unlike IID sampling where a random sample is generally considered representative, sampling nodes randomly from a graph can drastically alter or even destroy its structural properties, leading to a training graph that is not representative of the overall data distribution.
  1. Inference (Adversarial Knowledge of Structure): The adversary's knowledge of the graph structure during the attack phase is equally important. A model might be trained with node V embedded within a dense neighborhood. However, during an inference attack, the adversary might only have limited knowledge of V's neighborhood. Presenting V with a different neighborhood at test time, even to the same trained model, can lead to different predictions, effectively treating it as a different input instance. This variability in prediction based on available structural context complicates the assessment of membership inference risk.

These fundamental differences led to the central research question: "How strongly does the amount of edge information available during training and test modulate the node-level membership-inference risk?" The research aims to quantify this modulation by comparing different graph sampling techniques and varying the adversarial knowledge of graph structure during inference.

Key Findings

▶ Watch: Comparing random and structured graph sampling techniques (5:30)

The research reveals several critical findings that challenge conventional wisdom regarding membership inference in machine learning, particularly in the context of GNNs:

  1. Impact of Training Graph Construction: The method used to construct the training graph significantly impacts the resulting graph structure and, consequently, the membership inference risk.
  • Random Sampling, a common technique where nodes are picked randomly and an induced subgraph is formed, often completely destroys the original graph structure, leading to a reduction in average node degrees and potentially disconnecting components.
  • Structured Sampling, specifically snowball sampling, which starts from a seed node and iteratively samples its neighbors (and their neighbors), is shown to preserve graph structure more effectively. In this work, the snowball sampling strategy specifically retained only three random neighbors at each iterative stage. This controlled preservation of structure led to different average degree distributions across datasets compared to random sampling. For example, on the dense Chameleon dataset, random sampling maintained a higher average degree due to the graph's inherent density, while snowball sampling, by design, restricted the average degree.
  1. Performance Gap and Membership Inference Risk are Not Always Correlated in GNNs: A widely accepted heuristic in traditional machine learning is that a higher generalization gap (the difference in performance between training and test data, often referred to as performance gap in the talk) correlates with a higher membership inference risk. The intuition is that models that memorize training data more (leading to a larger generalization gap) are more susceptible to MIAs. However, this research demonstrates a nuanced relationship in GNNs.
  • The performance gap in GNNs is dynamic; even for a fixed, trained model and fixed data points, changing the available edge information during inference can alter the model's performance and, thus, the performance gap. The talk illustrates this with a plot showing different performance gaps when using "no edges," "all edges," or the "original split" of edges.
  • Crucially, when "none of the edges" are used during inference, the model's performance on both training and test data can significantly degrade, leading to a very high performance gap. Counter-intuitively, under these conditions, the membership advantage (the attacker's ability to infer membership) can be low. This is because the attacker, much like the model, lacks the critical structural information encoded in the edges, which are necessary signals for distinguishing members from non-members.
  • Conversely, snowball sampling showed a stronger, more direct correlation between performance gap and membership advantage, suggesting that preserving structure provides more consistent signals for attackers.
  1. Edge Information is a Critical Signal for Attackers: The study highlights that the attacker's access to edge information at inference time is paramount. If the model is deprived of edge information, its predictions become less reliable, and consequently, the attacker's ability to infer membership is diminished, even if the model's overall performance suffers significantly. This suggests that the "informational content" of the edges is a key factor in MIAs against GNNs.

Technical Deep Dive

▶ Watch: Generalization gap nuance for GNN membership inference (8:00)

The core of this research lies in understanding the interplay between Graph Neural Network (GNN) mechanics, graph sampling strategies, and the adversary's knowledge of graph structure during inference, all contributing to membership inference risk.

Graph Neural Networks and Node-Level Prediction:

GNNs operate by iteratively aggregating information from a node's local neighborhood. For a given node V, its representation is updated based on its own features and the aggregated features of its direct neighbors. This process can extend over multiple layers, effectively incorporating information from increasingly distant neighbors. Therefore, the "input instance" for predicting something about node V is intrinsically V and its neighborhood. The talk focuses on node-level prediction tasks, where the model is trained to predict a property of individual nodes (e.g., a user's political affiliation).

Membership Inference Attack (MIA) Setup:

The adversarial goal in a membership inference attack is to determine if a specific node V was part of the GNN's training dataset. The adversary is assumed to have access to the trained GNN model and potentially some part of the overall graph. The attack model is trained by observing the target GNN's outputs (e.g., prediction probabilities or embeddings) for nodes known to be members and non-members, then using this to predict membership for unseen nodes. The metric used to quantify the attacker's success is membership advantage, calculated by training an attack model with true labels of membership and non-membership, and measuring its accuracy above random guessing.

Training Graph Construction Strategies:

The research meticulously compares two distinct approaches for creating the training graph from a larger, complete graph:

  1. Random Sampling:
  • Mechanism: Nodes are selected uniformly at random from the full graph. The training graph is then formed by taking these selected nodes and all the edges that exist between them in the original graph (an induced subgraph).
  • Impact on Structure: The speaker explicitly states that this method can "completely destroy your graph structure." This is because randomly picking nodes significantly reduces the probability of retaining edges, drastically lowering the average degree, potentially fragmenting connected components, and altering the overall degree distribution compared to the original graph. While simple, it fails to capture the inherent relational properties crucial for GNNs.
  1. Structured Sampling (Snowball Sampling):
  • Mechanism: This technique is inspired by social science surveys. It begins with a randomly chosen "seed node." From this seed, a specified number of its neighbors are randomly sampled. The process then repeats: from each of these newly sampled neighbors, another set of their neighbors is randomly sampled, and so on, for a predetermined number of iterations or until a target sample size is reached.
  • Specifics in this Work: In this study, at each iterative stage of snowball sampling, the researchers "only retain three random neighbors." This parameter is crucial as it directly controls the density and connectivity of the sampled graph.
  • Impact on Structure: Snowball sampling is designed to "preserve the graph structure in some way." By following existing connections, it maintains a more coherent and connected subgraph, reflecting the local structural properties of the original graph better than random sampling. The average degree of nodes within a snowball sample can be managed by the number of neighbors retained at each step. For example, the study observed that for the Chameleon dataset (a dense graph), random sampling still yielded a relatively high average degree, whereas the constrained snowball sampling (with 3 neighbors) resulted in a lower, controlled average degree, demonstrating its ability to change the effective graph structure presented to the GNN.

Inference-Time Edge Access and its Effect on Performance:

Beyond training, the research also investigates how the availability of edge information during inference affects model performance and, consequently, membership inference risk. The speaker details experiments where the trained model's output distributions are compared under different edge access scenarios for the same fixed nodes:

  • Using "all the graph edges": The model has complete access to the node's neighborhood as it exists in the full graph.
  • Using "none of the graph edges": The model is forced to make predictions based solely on the node's own features, effectively treating it as an isolated node.
  • Using "original split": This refers to the edges available during the initial train-test split.

The KL divergence between these output distributions was measured, showing that even with a fixed trained model, changing edge access significantly alters the model's predictions. This directly impacts the performance gap (generalization gap). The talk presents a visual where "red" corresponds to "no edges" (high performance gap), "green" to "all edges," and "orange" to the "original split." This illustrates that the performance gap in GNNs is not a static value but a function of the available structural context.

Decoupling Performance Gap and Membership Advantage:

The most significant technical finding is the breakdown of the assumed correlation between high performance gap and high membership inference risk.

  • Traditional View: A model that overfits (high performance gap) is thought to "memorize" training data, making it easier for an attacker to distinguish members.
  • GNN Reality: The research shows plots of membership advantage versus performance gap. While for snowball sampling, a strong correlation was observed, this was not universally true. Specifically, when "none of the edges" were used during inference, the model performed poorly on both training and test data, resulting in a very high performance gap (represented by "green dots" in the speaker's visual explanation). However, in these scenarios, the **membership advantage was *low***. The speaker clarifies: "But the attacker does not get much signals because the information encoded in the edges is not given to the... model at that instance." This means that while the model struggles to generalize without structural context, the attacker also lacks the crucial "signals" (derived from edge information) needed to reliably infer membership. Conversely, conditions where edge information was available ("blue circles" which were "always high in membership advantage") provided stronger signals for the attacker.

This decoupling implies that simply observing a high generalization error in a GNN does not automatically signify a high membership inference risk. The context of why the generalization error is high (e.g., lack of structural information versus true overfitting) is critical.

Demo / Proof of Concept

▶ Watch: Membership advantage vs. performance gap findings (9:00)

The talk does not include an explicit demonstration or live proof of concept. The findings are presented through empirical results and plots derived from experiments comparing different graph sampling techniques and inference scenarios. The speaker refers to plots showing average degree distributions, KL divergence between output distributions, and the relationship between membership advantage and performance gap across various datasets and experimental conditions.

Defensive Implications

▶ Watch: Key takeaways and conclusions from the research (10:10)

The findings of this research offer crucial insights for developers and practitioners working with Graph Neural Networks, particularly concerning privacy and security:

  1. Training Graph Construction as a Privacy Mechanism: The strategy employed to construct the training graph is not merely an engineering choice for model performance but must be recognized as a fundamental part of the GNN's privacy mechanism. Random sampling, while simple, can inadvertently destroy valuable structural information, potentially altering the privacy properties of the trained model in unexpected ways. Techniques like structured sampling (e.g., snowball sampling), which aim to preserve local graph structure, should be carefully considered, as they can lead to different privacy-utility trade-offs.
  1. Context-Aware Risk Assessment: Traditional assumptions linking a high generalization gap to high membership inference risk do not consistently hold for GNNs. Defenders must adopt a more nuanced, context-aware approach to risk assessment. A GNN exhibiting poor performance or a large generalization gap might not necessarily be highly vulnerable to MIAs if the lack of performance stems from an absence of crucial structural information during inference. Conversely, a model trained and inferred with rich structural context might be more susceptible even with a seemingly smaller performance gap.
  1. Controlling Edge Information at Inference: The research highlights that the amount of edge information available during inference is a critical factor influencing membership inference risk. Organizations deploying GNNs should explore strategies to limit the exposure of sensitive structural information to potential adversaries during the model's operational phase. This could involve techniques like edge anonymization, structural perturbation, or carefully designed access controls that restrict the adversary's view of the graph's full connectivity.
  1. Re-evaluating Privacy Auditing for GNNs: The finding that graph structure can "inhibit the use of membership inference attacks to give lower bounds for DP privacy auditing" is significant. Membership inference attacks are often used as a practical tool to audit the privacy guarantees (e.g., differential privacy) of machine learning models. If the unique structural properties of graphs can decouple MIA success from other privacy metrics, then existing auditing methodologies may need to be revised or supplemented with graph-specific techniques to accurately assess privacy leakages in GNNs.

Key Takeaways

  • Training graph construction is a critical privacy mechanism for GNNs, not just a performance consideration.
  • Graph structure profoundly influences privacy leakage in GNNs, affecting both training and inference.
  • The conventional correlation between a high performance/generalization gap and high membership inference risk does not always hold true for GNNs, especially when edge information is limited during inference.
  • The amount of edge information available to the model (and attacker) during inference is a key modulator of membership inference risk. Limited edge access can reduce an attacker's signals, even if model performance degrades significantly.
  • The presence of graph structure can inhibit the use of membership inference attacks for privacy auditing (e.g., setting lower bounds for differential privacy), necessitating new auditing approaches for GNNs.
  • Defenders should carefully consider graph sampling strategies and the management of edge information to mitigate membership inference risks in GNN deployments.

About the Speaker(s)

Megha Khosla is the author of the paper discussed in this talk and is affiliated with the Delft University of Technology. Her research focuses on the intersection of machine learning, privacy, and graph-structured data, particularly exploring the vulnerabilities and defensive strategies related to Graph Neural Networks.

Reviews

Dr. Zero (Offensive Security Researcher) — STRONG ACCEPT

Khosla proves that porting standard membership inference heuristics to graph neural networks is a fool's errand. She dismantles the assumption that a high generalization gap automatically means high MIA risk by showing how edge removal starves both the model and the attacker of structural signal. It's rigorous, counter-intuitive, and exactly the kind of foundational ML privacy research auditors actually need.

Heather Calloway (CISO) — SOLID

This is deep academic research on ML privacy, specifically targeting Graph Neural Networks (GNNs). While highly technical, it surfaces a critical governance gap for organizations deploying AI on relational data: standard methods for measuring privacy leakage are broken in this context. Worth flagging for your privacy engineering and AI risk teams, though not a direct board-level watch item yet.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026