🤖 machine learning

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

This paper argues that graph structure fundamentally shapes membership inference risks in Graph Neural Networks, demonstrating that factors like training-graph construction and inference-time edge access directly influence privacy leakage in ways that standard generalization gaps fail to capture.

Original authors: Megha Khosla

Published 2026-06-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Megha Khosla

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Social Network" Leak

Imagine you are a detective trying to figure out if a specific person was part of a secret club. You have a trained "mind-reader" (a Graph Neural Network, or GNN) that knows the club's members very well. Your goal is to ask the mind-reader: "Was this person in the club?"

Usually, in standard machine learning, we assume every person is independent, like individual apples in a basket. But in Graph Neural Networks, people are connected like a social network. Who you know changes who you are. This paper argues that the shape of the social network itself (who is connected to whom) is the biggest factor in whether the detective can successfully guess who was in the club.

The author, Megha Khosla, discovered two main things:

How you build the training list matters: If you build your training list by following friends of friends (Snowball Sampling) vs. picking random strangers (Random Sampling), it changes how much the model "remembers" specific people.
What the detective sees at the end matters: Even if the model is frozen, giving the detective more information about the connections (edges) at the moment of the guess changes the risk of a leak.

Analogy 1: The "Party Guest List" (Training Graph Construction)

Imagine you are trying to teach a robot to recognize the vibe of a specific party. You need to show it photos of the guests.

Random Sampling (The Lottery): You throw a dart at a city map and pick 50 random people to invite to your "training party."
- The Result: You might accidentally pick 50 people who don't know each other. Some might be standing alone in a corner with no friends. The robot learns a weird, disconnected version of the party.
Snowball Sampling (The Chain Letter): You pick one person, then ask them to bring 3 friends, who then bring 3 friends each.
- The Result: You get a very tight-knit group. Everyone knows everyone. However, you likely missed the quiet people on the edge of the room or the different cliques that didn't know your starting person. You have a "biased" view of the party.

The Paper's Finding:
The robot trained on the Snowball method (the chain letter) actually memorized the specific patterns of that tight-knit group too well. Because the group was so specific and biased, the robot could easily tell, "Oh, this person fits the pattern of our specific group," making it easier for a hacker to guess if that person was in the training set.

The Random method was messier and less biased, making it slightly harder for the hacker to spot the difference between a "training guest" and a "stranger."

Analogy 2: The "Detective's Map" (Inference-Time Edge Access)

Now, imagine the robot is trained. A hacker (the detective) wants to test a new person to see if they were in the training set. The hacker has two ways to ask the robot:

The "Isolated" View (No Edges): The hacker shows the robot a photo of the person but cuts off all their friends. The robot has to guess based only on the person's face.
The "Full Map" View (Full Graph): The hacker shows the photo of the person plus a map of all their friends, neighbors, and connections.

The Paper's Finding:
Surprisingly, giving the hacker the Full Map often made the attack harder (safer for privacy) on some datasets, but easier on others.

Why? When the robot sees the full map, it can use the "wisdom of the crowd." If the person is connected to many people the robot knows well, the robot's guess becomes more confident and "averaged out," blurring the line between "member" and "non-member."
The Twist: Sometimes, giving the hacker less information (cutting the edges) actually made the robot's behavior more erratic, which gave the hacker a bigger clue about whether the person was in the training set.

The "Generalization Gap" Trap

In normal machine learning, there is a rule of thumb: "If the model does great on training data but fails on new data (a big 'Generalization Gap'), it is overfitting and leaking secrets."

The paper says: This rule is broken for Graphs.

The Analogy: Imagine a student who memorizes the textbook perfectly (Training) but fails the test (Test). We usually think, "They memorized it too much, so they are leaking the answers."
The Graph Reality: In graphs, the "Test" might fail not because the student memorized the answers, but because the Test Question was drawn from a different neighborhood than the textbook.
The Result: You can have a huge gap between training and test scores (big overfitting) but low privacy risk. Conversely, you can have a tiny gap but high privacy risk. The "Generalization Gap" is a bad ruler for measuring privacy leaks in graphs.

The "Exchangeability" Problem (The Theoretical Bit)

The paper also proves a math problem: In standard data, if you swap two people in the dataset, nothing changes. This is called "Exchangeability."

But in graphs, you cannot swap people.

If you swap a "popular" person with a "loner," the whole structure of the social network changes. The "loner" might now be connected to 50 people they didn't know before.
Because the structure changes when you swap people, the standard mathematical guarantees for privacy (like Differential Privacy) don't work the same way. The way you built the graph (the sampling method) leaks information before the model even starts learning.

Summary of Key Takeaways

Structure is King: The way you connect the dots (the graph structure) is just as important as the data itself when it comes to privacy.
Snowball Sampling is Risky: Building your training data by following chains of friends (Snowball) creates a biased, tight-knit group that is easier for hackers to exploit than a random list of people.
Context Matters: Whether a hacker knows the connections (edges) between people changes the risk. Sometimes giving them more info helps the model hide; sometimes it helps the hacker.
Don't Trust the "Gap": Just because a model performs poorly on new data doesn't mean it's leaking secrets, and just because it performs well doesn't mean it's safe. You have to look at the graph structure to know the truth.

The Bottom Line: You can't treat graph data like a simple list of items. To protect privacy, you have to understand how the "social network" was built and how the connections are used.

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

Problem Statement

Graph Neural Networks (GNNs) are widely deployed for tasks such as node classification and link prediction, yet their application in sensitive domains raises significant concerns regarding training-data leakage. While prior work on privacy leakage in GNNs has largely adapted assumptions from independent and identically distributed (i.i.d.) domains, this approach overlooks the critical role of graph structure. Specifically, existing studies often treat data instances as independent, failing to account for the interdependence of nodes caused by edges.

This paper addresses the node-level membership inference (MI) problem: given a trained GNN, can an adversary determine whether a specific node was part of the training set? The authors argue that in graph-based learning, the definition of a "data instance" is not merely a node feature vector but a node–neighborhood tuple. Consequently, privacy risk is modulated by two graph-specific dimensions often ignored in standard analyses:

Training-graph construction: How the training subgraph is sampled (e.g., random vs. snowball sampling).
Inference-time edge access: The extent of graph structure (edges) available to the adversary during the attack.

The paper posits that standard privacy auditing results, which rely on statistical exchangeability, may not directly apply to inductive graph settings where training and test nodes are structurally dependent.

Methodology

Theoretical Framework

The authors formalize node-level MI by defining the input instance as a tuple $z_v = (x_v, y_v, N^L(v), \{x_u : u \in N^L(v)\})$ , where $N^L(v)$ is the $L$ -hop neighborhood. They adapt the definition of statistical exchangeability to GNNs. The paper proves (Theorem 3.2) that in inductive settings, whether using random or snowball sampling, the joint distribution of training and test node–neighborhood tuples is not statistically exchangeable. This is because the neighborhood structure of a test node depends on the specific set of sampled training nodes and the sampling process itself (e.g., the order of traversal in snowball sampling), violating the permutation invariance required for standard differential privacy (DP) auditing guarantees.

Experimental Setup

The study evaluates the impact of graph structure on MI risk using three datasets: Cora, Chameleon, and PubMed.

Sampling Strategies: The authors compare Uniform Random Node Sampling (standard in literature) against Snowball Sampling (common in real-world scenarios like contact tracing and social network construction). Snowball sampling starts from seed nodes and iteratively adds neighbors, introducing coverage bias toward high-degree hubs.
Inference Regimes: The authors analyze three edge-access scenarios at inference time:
1. Original: Only edges within the training set and within the test set are used (train/test edges are disjoint).
2. FullGraph: All edges from the underlying graph, including those connecting training and test nodes, are available.
3. NoEdges: No graph structure is used; predictions rely solely on node features.
Attack Model: To isolate the effect of graph structure from shadow-model artifacts, the authors bypass the traditional shadow-model approach. Instead, they directly train a binary classifier (a 2-layer MLP) on the true membership status of a fraction ( $r \in \{0.1, 0.2, 0.5, 0.8\}$ ) of member and non-member nodes, using the target model's prediction probabilities and cross-entropy loss as inputs.
Models: Experiments utilize GCN, GAT, and GraphSage architectures.

Key Results

1. Impact of Sampling Strategy on Generalization

Snowball Sampling vs. Random Sampling: Snowball sampling often results in a larger generalization gap (difference between training and test accuracy) compared to random sampling. This is attributed to coverage bias, where snowball sampling oversamples high-degree hubs and specific graph regions while under-representing peripheral communities. This bias leads to a non-i.i.d. training distribution that generalizes poorly to held-out nodes.
Edge Density: Snowball sampling tends to produce training graphs with higher connectivity (except in low-homophily datasets like Chameleon where random sampling can yield higher density due to lack of neighbor capping).

2. Impact of Inference-Time Edge Access

Performance: Allowing access to FullGraph edges (including inter-train-test edges) generally improves test accuracy and reduces the train–test gap, as the model can leverage more complete neighborhood information.
Privacy Leakage (Membership Advantage): The effect on MI risk is complex and setting-dependent:
- Original Split: Often yields the highest membership advantage, as the structural context of training nodes (disjoint from test nodes) creates a distinct behavioral signature.
- FullGraph: Surprisingly, providing full edge access often reduces membership advantage (making members and non-members harder to distinguish), particularly for GCN and GAT. The mixing of information across train-test boundaries blurs the distinction between the two groups.
- NoEdges: While this setting often increases the performance gap (due to lack of structural context), it frequently results in lower membership advantage compared to the Original split. This suggests that a large generalization gap is not a reliable proxy for high privacy risk in graphs.

3. Decoupling Generalization Gap and Privacy Risk

The paper demonstrates that the generalization gap is an incomplete proxy for membership inference risk.

In several scenarios (e.g., NoEdges setting), the performance gap increases while membership advantage decreases.
Conversely, in some cases (e.g., FullGraph on homophilic graphs like Cora), membership advantage can be higher than in the NoEdges setting even when the performance gap is lower.
This decoupling indicates that privacy leakage is driven not just by overfitting (memorization) but by structural dependencies and the specific information available during inference.

4. Model-Specific Sensitivity

GCN and GAT: These models, which average neighbor features, are highly sensitive to edge access. The "FullGraph" setting significantly reduces their vulnerability to MI attacks by smoothing representations across the entire graph.
GraphSage: Shows more stable membership advantage across different edge-access settings. The authors hypothesize this is due to GraphSage's mechanism of concatenating self-features with aggregated neighbor features rather than averaging them, preserving more node-specific signals.

Significance and Claims

The paper claims that graph structure directly shapes privacy risk in ways that cannot be captured by standard i.i.d. assumptions.

Invalidity of Standard Auditing: The authors theoretically establish that inductive graph learning breaks statistical exchangeability. Therefore, empirical membership advantage cannot be directly translated into a lower bound on the differential privacy budget, as is common in non-graph settings. The data-generating distribution itself (via sampling bias) may leak membership information independent of the model's learned parameters.
Re-evaluating Threat Models: The study argues that realistic privacy evaluations for GNNs must explicitly model the adversary's knowledge of the graph structure (both during training construction and at inference). Assuming an adversary has access to the full graph or no edges at all leads to vastly different risk assessments.
Limitations of Generalization Metrics: The paper concludes that relying solely on the generalization gap to estimate privacy risk is insufficient for GNNs. Privacy leakage can rise or fall independently of the generalization gap, driven by the specific interplay between sampling strategies and inference-time edge availability.

The authors release their code and data to facilitate further research into graph-specific privacy analysis, emphasizing the need for new privacy notions that account for training graph construction strategies.