💻 computer science

Bayesian Membership Privacy for Graph Neural Networks

This paper introduces Bayesian Membership Privacy (BMP), a novel framework for Graph Neural Networks that addresses the limitations of existing privacy analyses by incorporating node-dependent priors and graph sampling probabilities to provide a more fine-grained, sampling-aware quantification of membership privacy leakage.

Original authors: Sinan Yıldırım, Megha Khosla

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sinan Yıldırım, 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

Imagine you have a giant, complex web of friends (a graph). You train a smart computer program (a Graph Neural Network) to learn patterns from this web, like predicting who might be friends with whom or what interests they share.

The big worry is: Can a sneaky hacker look at the finished computer program and figure out if a specific person was part of the group used to teach it? This is called a "Membership Inference Attack."

Here is the problem with how we usually check for this risk:
Most current methods treat every person in the web as if they were a random, isolated item, like a single apple in a basket. They assume everyone had an equal chance of being picked. But in a social network, that's not true. If you are friends with many people, or if you are in a very popular group, you are much more likely to be picked for the training group than someone who is isolated.

Because of this, the old "apple in a basket" math doesn't work well for social webs. It misses the fact that the structure of the web itself gives away clues.

The New Solution: "Bayesian Membership Privacy" (BMP)

The authors of this paper propose a new way to measure privacy called Bayesian Membership Privacy (BMP). Here is how it works, using simple analogies:

1. The "Prior" (The Starting Guess)

Imagine you are a detective trying to guess if a specific person, "Bob," was in the training group.

Old Way: The detective starts with a blank slate, assuming Bob had a 50/50 chance of being there, just like flipping a coin.
New Way (BMP): The detective looks at the map first. If Bob is the most popular kid in school with 500 friends, the detective knows there's a very high chance he was picked for the training group just by the nature of how the group was formed. This starting guess is called the "Prior." BMP forces the privacy check to start with this realistic guess, not a fake coin flip.

2. The "Posterior" (The Updated Guess)

After the computer finishes training, the hacker looks at the results.

Old Way: They just count how many times the hacker guessed right vs. wrong (like a test score).
New Way (BMP): They ask, "Given that I started with a 90% chance Bob was there, and now I see the computer's output, what is my updated chance that he was there?"
- If the computer's output doesn't change the detective's mind much, privacy is good.
- If the output makes the detective 99.9% sure Bob was there, privacy is bad.

BMP measures privacy by how much the hacker's confidence changes from their starting guess to their final guess.

3. Why "Asymmetry" Matters

The paper points out that privacy isn't always a two-way street.

Scenario A: Knowing someone was in the training group might be a huge secret (e.g., they were part of a sensitive support group).
Scenario B: Knowing someone was not in the group might be totally harmless.
The Analogy: Imagine a VIP club. Knowing you were invited is a big deal. Knowing you weren't invited is just a fact.
- Old methods treat both sides equally.
- BMP is flexible. It can say, "It's okay if the hacker knows you weren't there, but we must protect the fact that you were." This is called "Right-sided" or "Left-sided" privacy.

4. The "Sampling" Factor

In graph learning, the computer often only sees a part of the whole web (a sample).

The Analogy: Imagine a teacher picks 10 students from a class of 30 to solve a puzzle.
- If the teacher picks students randomly, everyone has an equal shot.
- But if the teacher picks the "top 10 athletes," then being an athlete makes you much more likely to be picked.
- BMP accounts for this. It treats the "picking process" as part of the hacker's knowledge. If the picking process itself makes a person's membership obvious, BMP flags that risk immediately, even before the computer finishes learning.

What Did They Do?

The authors didn't just write a theory; they built a privacy audit tool.

They created a way to run "fake attacks" on Graph Neural Networks.
Instead of just giving a single score (like "85% accurate"), their tool gives a fine-grained report.
It shows that some nodes (people) are at high risk of being identified, while others are safe, depending on their position in the network and how the data was sampled.

The Bottom Line

The paper argues that we can't use the same privacy rules for social networks that we use for simple lists of data. Because people are connected, their "chance of being picked" varies wildly. Bayesian Membership Privacy is a new, smarter ruler that measures privacy by looking at:

How likely a person was to be picked in the first place.
How much the final computer model changes that likelihood.

This gives a much more accurate picture of who is actually at risk of having their membership in the training data exposed.

Technical Summary: Bayesian Membership Privacy for Graph Neural Networks

Problem Statement

Existing privacy analyses for Graph Neural Networks (GNNs) largely rely on assumptions derived from independent and identically distributed (i.i.d.) data settings. These approaches overlook two critical aspects of graph-structured data: structural correlations (where nodes are interdependent via edges and overlapping neighborhoods) and stochastic training-graph sampling.

In standard Membership Inference Attacks (MIA), the goal is to determine if a specific data point was part of the training set. However, in GNNs, the inclusion of a single node affects the learned representations of many others. Furthermore, training nodes are often selected via a sampling process that interacts with the graph structure, meaning some nodes are inherently more likely to be included than others.

Current definitions, such as Differential Privacy (DP) or standard Membership Privacy (MP), often assume:

Uniform Priors: That all nodes have an equal prior probability of being in the training set.
Symmetric Errors: That Type-I and Type-II errors are sufficient to characterize privacy risk.
Exchangeability: That training and non-training nodes are statistically indistinguishable before the algorithm runs.

The authors argue that these assumptions fail in graph settings. Structural dependencies break exchangeability, and node-dependent priors (driven by the sampling mechanism) make global attack accuracy or fixed error bounds insufficient for capturing true, node-specific privacy leakage.

Methodology: Bayesian Membership Privacy (BMP)

To address these gaps, the paper introduces Bayesian Membership Privacy (BMP), a framework that treats membership inference as a Bayesian hypothesis test.

1. Probabilistic Model

The authors define a randomized learning algorithm $\mathcal{A} = (\mathcal{S}, \Phi)$ consisting of:

Sampling ( $\mathcal{S}$ ): A stochastic mechanism that selects a subset of nodes $S \subseteq V$ to form a training subgraph.
Training ( $\Phi$ ): A procedure that produces a model output $W$ given the sampled subgraph.

Key variables include:

Membership Variable ( $M_i$ ): An indicator for whether node $i$ is in the sampled set $S$ .
Prior ( $\gamma_i$ ): The marginal probability $\Pr(M_i=1)$ , representing the node's inclusion probability based on the sampling mechanism.
Posterior ( $\pi_i$ ): The probability $\Pr(M_i=1 | W=w)$ , representing the adversary's belief after observing the model output.

2. Definition of BMP

BMP is defined by bounding the ratio of posterior odds to prior odds. An algorithm is $(\varepsilon_L, \varepsilon_R)$ -BMP if for any output $w$ and node $i$ :
$e^{-\varepsilon_L} \leq \frac{\pi_i(1|w)}{\pi_i(0|w)} \cdot \frac{\gamma_i(0)}{\gamma_i(1)} \leq e^{\varepsilon_R}$
This formulation explicitly incorporates node-dependent priors ( $\gamma_i$ ) and allows for asymmetry ( $\varepsilon_L \neq \varepsilon_R$ ). This asymmetry acknowledges that the privacy risk of revealing membership (being in the training set) may differ from revealing non-membership.

The paper also defines related concepts:

BMP-R / BMP-L: One-sided versions focusing solely on the risk of revealing membership or non-membership.
BMDP (Bayesian MDP): A differential version conditioning on the membership of all other nodes, though the authors note this is often impractical for graphs due to structural coupling.

3. Theoretical Properties

The paper establishes several theoretical properties of BMP:

Prior Bounds: The privacy parameters $\varepsilon_L$ and $\varepsilon_R$ are lower-bounded by the ratio of priors. Even a "perfectly private" training algorithm cannot hide leakage inherent in the sampling process itself.
Post-processing: BMP is preserved under measurable transformations of the model output.
Composition: The paper provides composition theorems for combining BMP with MP (multiple private operations on one sample) and BMP with BMP (multiple independent sampling and training rounds).
Statistical Guarantees: A one-to-one relationship is established between BMP parameters and the Type-I ( $\alpha$ ) and Type-II ( $\beta$ ) error regions of any MIA. Specifically, the allowed region for $(\alpha, \beta)$ depends on the node's prior probability $\eta_i$ .

4. Practical Auditing Mechanism

To estimate BMP parameters in practice, the authors propose an auditing mechanism:

MIA Design: They construct node-level MIAs using shadow models trained on sampled subgraphs.
Bayesian Estimation: Using the theoretical link between BMP and error probabilities, they model the observed Type-I and Type-II errors as being drawn from a region $R_{\eta}(\varepsilon_L, \varepsilon_R)$ .
Inference: They employ a Markov Chain Monte Carlo (MCMC) approach to estimate the posterior distribution of $(\varepsilon_L, \varepsilon_R)$ based on the observed error counts from the MIAs.

Key Contributions

BMP Framework: Introduction of a sampling-aware, Bayesian formulation of membership privacy that incorporates node-dependent priors and treats graph sampling probabilities as part of the adversary's knowledge.
Theoretical Analysis: Derivation of properties including composition rules, post-processing invariance, and a rigorous link between BMP parameters and the error probabilities of membership inference attacks.
Auditing Tool: A practical, sampling-aware mechanism to estimate BMP parameters using MIA results, enabling fine-grained privacy assessment.
Empirical Validation: Experiments on benchmark graph datasets demonstrating that BMP reveals fine-grained privacy insights (variations in risk across nodes) that are invisible when relying solely on global attack accuracy.

Results and Claims

The authors claim that their framework provides a more accurate and nuanced understanding of privacy in GNNs compared to existing methods.

Fine-Grained Insights: Experiments show that privacy leakage is not uniform; it varies significantly based on node-specific sampling probabilities and structural position. Global metrics (like average attack accuracy) fail to capture this heterogeneity.
Sampling Awareness: The framework successfully quantifies how different graph sampling strategies, training set sizes, and edge settings influence node-level privacy leakage.
Theoretical Consistency: The paper demonstrates that BMP is a necessary generalization for graph settings where the exchangeability assumption of i.i.d. data does not hold.

Significance

The paper positions BMP as a necessary evolution in privacy definitions for relational learning. It argues that without accounting for structural dependencies and sampling-induced priors, privacy guarantees in GNNs are either overly restrictive (failing to reflect reality) or insufficient (failing to protect sensitive structural information). By shifting the focus from uniform error bounds to posterior belief updates conditioned on priors, BMP offers a principled way to audit and quantify privacy risks in graph-based machine learning systems.