acceptodds
Under review as a conference paper at ICLR 2027

Bayesian Membership Privacy for Graph Neural Networks

Abstract

Existing privacy analyses for Graph Neural Networks (GNNs) largely inherit assumptions from non-graph settings, overlooking structural correlations and stochastic training-graph sampling. In particular, node-dependent priors make type-I and type-II errors alone insufficient to characterize the best membership inference test. To address this, we introduce Bayesian Membership Privacy (BMP), a sampling-aware formulation of node-level membership privacy that incorporates node-dependent priors and treats graph sampling probabilities as part of the adversary’s knowledge. BMP casts membership inference as a Bayesian hypothesis test and accordingly quantifies membership privacy in terms of posterior membership probability. We explore theoretical properties of BMP in relation to the existing definitions in the literature. We further propose a practical, sampling-aware auditing mechanism to estimate the parameters of BMP as a measure of node-level privacy leakage in GNNs. We conduct experiments on benchmark graph datasets and show that BMP yields fine-grained privacy insights that are not visible through global attack accuracy alone.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential privacy, Graph Neural Networks, membership inference attack, Bayesian estimation, Markov chain Monte Carlo

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_DrjROpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Bayesian Membership Privacy (BMP) for GNNs, incorporating node-dependent membership priors and asymmetric privacy bounds. It develops theoretical properties and a Bayesian auditing procedure based on a LiRA-style attack. Experiments evaluate the effects of sampling strategies and model configurations on the estimated privacy risks.

Critical strengths
  • The motivation is meaningful. I agree with the authors’ argument that existing GNN privacy analyses largely inherit assumptions from non-graph settings, motivating a closer examination of graph structure.
  • The paper combines theoretical analysis with empirical analysis to study sampling-dependent privacy risks. Incorporating membership priors provides a useful perspective on interpreting attack evidence.
Critical weaknesses
  • The limitations attributed to existing privacy analyses need clearer justification. The authors argue that prior analyses overlook structural dependence and stochastic graph sampling. Which specific assumptions fail, and what misleading conclusions do they produce?

  • Although the BMP formulation allows dependent membership states, the practical estimator in Section 4.2 still uses independence assumptions. Please clarify how the audit handles structural dependence.

  • The additional benefit of the Bayesian formulation is insufficiently explained. The paper acknowledges that BMP also applies to non-graph settings with nonuniform inclusion probabilities. What additional insight does the framework provide beyond incorporating these priors into an existing likelihood-ratio test?

  • The comparison with existing attacks is limited. Experiments compare prior-aware and prior-unaware variants of the same LiRA-style attack. However, the practical benefit over existing attack methods remains unclear.

Questions for authors

Please see the Weaknesses.

2 comments
AuthorsOpenReview ↗

Pointwise Response to Reviewer DrjR (W1–W3)

We thank the Reviewer for their comments that helped improve the paper. The reviewer’s comments are largely addressed in a broader context in our common response; here we provide our point-to-point responses. We hope these clarifications address the remaining concerns and respectfully ask the Reviewer to reconsider and improve their score accordingly.

W1: Prior work: Which specific assumptions fail, and what misleading conclusions do they produce?

Response: In graph based learning, structural dependencies challenge statistical exchangeability of train-test records (as shown in Khosla (2026, section 3.3)), while graph-dependent sampling induces heterogeneous membership probabilities for train nodes. The loss of exchangeability can invalidate the assumptions underlying existing MIA-based DP auditing methods, limiting their ability to establish formal privacy guarantees for graph-based learning . Furthermore, assuming uniform membership priors overlooks the fact that graph sampling can make some nodes substantially more likely to be included than others. Consequently, identical MIA error rates can correspond to different posterior membership risks, while aggregate attack metrics can conceal substantial node-level privacy heterogeneity. Our BMP formulation directly addresses these limitations by incorporating node-specific membership priors and establishing a prior-dependent characterization of privacy guarantees through MIA error probabilities (Theorem 4).

W2: BMP formulation allows dependent membership… but estimator uses independence… Clarify how the audit handles structural dependence

Response: We would like to separate two dependencies, which may be conflated in the discussion.

  • The dependence among membership status of nodes is due to the sampling mechanism. The audit handles this type of dependence exactly by using the same sampling mechanism for generating their shadow models. Please see line 2 of Algorithm 1 given in Appendix A.1.
  • The dependence between MIA error rates is due to using the same set of shadow models. The limitation of the simple model in Section 4.2 due to its independence assumption was already acknowledged in the submission, and Appendix A.8 contained several suggestions towards a more general model where such dependencies are present. Action taken: To see how strong the independence (and uniformity) assumptions are, we have evaluated the alternative, more general model in Appendix A.8.1 in the first experimental setting of Section 5.1.1. This general model has an additional s parameter in (0, 1) that stands for attack strength and applies to all the attack error rates in the model. In that way, the error rates become dependent conditional on the BMP parameters (if an attack on a node is strong, expected so is the attack on another node). The case s = 0 corresponds to the basic model where the attack rates are independent. Our findings are that the estimates are fairly close in the basic and alternative models, and the s parameter is estimated to be close to 0. Those findings quantitatively support using the simplified assumption for that particular experiment.

W3 The additional benefit of the Bayesian formulation is insufficiently explained. What additional insight … beyond incorporating these priors into an existing likelihood-ratio test?

Response: We agree that incorporating prior odds into a likelihood-ratio test follows directly from Bayesian decision theory; however, we do not claim the prior-aware test itself as the principal contribution.

A test makes a membership decision for a particular node and threshold. BMP instead bounds the adversary’s posterior membership odds for every node. We show that this definition is equivalent to node-prior-dependent constraints on the type-I and type-II errors of any decision rule—not only the likelihood-ratio attack used in our experiments. This provides a way to analyze heterogeneous, asymmetric privacy risk and its implications for attack errors and decision costs.

There is yet another, distinct Bayesian component in the audit. From finite, noisy attack-error counts, our hierarchical model is used to estimate a posterior distribution over the BMP parameters, rather than reporting a single plug-in value. Graph sampling motivates the heterogeneous priors, but the definition and audit apply equally to non-graph settings with nonuniform inclusion probabilities.

We hope our response distinguishes the three different instances of Bayesian formulation in our work: Prior-aware attack, BMP definition, and Bayesian parameter estimation. We claim our contribution mostly in the latter two (corresponding to the first three contribution points at the end of Section 1), and not the first one.

AuthorsOpenReview ↗

Pointwise Response to Reviewer DrjR (W4)

W4 : The comparison with existing attacks is limited.

Response: As we stated in the 3rd bullet point of the second half of our common response, our objective is not to develop the strongest possible attack or certify individual GNNs, but to establish a theoretical foundation for BMP auditing and demonstrate its practical feasibility. Our auditing framework in Section 4 can use any membership inference attack (MIA) of choice; so a specific attack such as LIRA is not indispensable for the proposed methodology. Specifically, in Algorithm 1 in Appendix A.1, lines 7-9 can be replaced with any more powerful MIA. Stronger attacks are certainly preferable and may change the estimates, but not the BMP definition or its theoretical characterization.

Action taken: In hindsight, reading Section 4.1, we admit the reader may have the impression of LiRA being described as the only choice for MIA. However, in reality, the auditing pipeline can accommodate any MIA, an important point not emphasised sufficiently. We would like to prevent that misunderstanding; therefore, in our revised version, we have added the following sentence at the top of Section 4.1, before explaining LiRA: We present a specific MIA, which we use in the experiments. However, note that the presented auditing pipeline is not restricted to a particular MIA and can accommodate any other MIA.

Reviewer_Jth1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

General topic is on membership privacy for GNNs. The emphasis is on how graph structure and nonuniform sampling create varying privacy risks across nodes in the graph data. The main contribution is a Bayesian Membership Privacy framework, together with theoretical results and a method for estimating privacy parameters using membership inference attacks.

Critical strengths

S1) The paper considers an interesting privacy problem for GNNs, particularly the heterogeneous membership risks caused by the structure and different node sampling mechanisms as well.

S2) BMP provides a reasonable formulation that accounts for node-specific membership priors. Their theoretical analysis also establishes useful connections to existing privacy notions and attack error bounds.

S3) I like the idea of combining membership inference attacks with Bayesian estimation to infer privacy parameters and their uncertainty. This seems useful when the underlying model mechanism is not known.

Critical weaknesses

W1) My main concern is the novelty of the proposed privacy framework. Much of BMP appears to follow existing Bayesian membership privacy and hypothesis testing formulations; the primary difference being its application to GNNs and node-specific priors? It is not entirely clear what new methodological insight is introduced here (but welcome follow-up discussion on this if able to help clarify).

W2) The theoretical formulation considers arbitrary attacks, but the actual auditing depends on specific membership inference methods. There is no strong validation of how close the resulting estimates are to the actual privacy risks, which seems important for the proposed framework.

W3) Several assumptions are made in the Bayesian estimation, such as uniform distributions over feasible error regions and independence assumptions. However, they might be somewhat strong, and a better understanding/discussion would help.

W4) Most results are on too few datasets. It would be good to see whether the same findings hold for more realistic or diverse graph settings.

Questions for authors

Q1 Can the authors better distinguish BMP from existing Bayesian membership privacy formulations? In particular, what cannot already be captured by those approaches?

Q2 Would using a substantially stronger or different attack lead to very different BMP estimates? This seems important if the approach is intended for practical privacy auditing.

Q3 Have the authors considered evaluating the alternative models mentioned in the appendix? How sensitive are the main results to these modeling choices?

[Also see above in Weaknesses section and I note that I plan to be adaptive based on your responeses/discussion.]

2 comments
AuthorsOpenReview ↗

Pointwise Response to weaknesses from Reviewer Jth1

We thank the Reviewer for their comments that helped improve the paper. The reviewer’s comments are largely addressed in a broader context in our common response; here we provide our point-to-point responses. We hope these clarifications address the remaining concerns and respectfully ask the Reviewer to reconsider and improve their score accordingly.

W1: Novelty of the proposed privacy framework

Response:Please see our common response about “Novelty and our contribution”, where we address the reviewers’ concerns about novelty in detail. To summarize here, (i) our BMP definition differs from existing work (as discussed in Appendix A.3 in the original submission); (ii) its theoretical properties, especially its relation to MIA as a hypothesis test (Theorem 4), are new findings; and (iii) the end-to-end auditing pipeline, which is built on Theorem 4, contains a new MIA measurement protocol and a Bayesian privacy estimation method from those measurements.

W2: Actual auditing depends on specific membership inference

Response: As we stated in the 3rd bullet point of the second half of our common response, our objective is not to develop the strongest possible attack or certify individual GNNs, but to establish a theoretical foundation for BMP auditing and demonstrate its practical feasibility. Our auditing framework in Section 4 can use any membership inference attack (MIA) of choice; so a specific attack such as LIRA is not indispensable for the proposed methodology. Specifically, in Algorithm 1 in Appendix A.1, lines 7-9 can be replaced with any more powerful MIA. Stronger attacks are certainly preferable and may change the estimates, but not the BMP definition or its theoretical characterization.

Action taken: In hindsight, reading Section 4.1, we admit the reader may have the impression of LiRA being described as the only choice for MIA. However, in reality, the auditing pipeline can accommodate any MIA, an important point not emphasised sufficiently. We would like to prevent that misunderstanding; therefore in our revised version we have added the following sentence at the top of Section 4.1, before explaining LiRA: “We present a specific MIA, which we use in the experiments. However, note that the presented auditing pipeline is not restricted to a particular MIA and can accommodate any other MIA.”

W3: Bayesian modelling assumptions may be strong

Response: Please see our comment “Bayesian modelling assumptions” in the 2nd half of our common response. In the original submission, we acknowledged those limitations (Section 4.2 and Appendix A.8) and suggested solutions in Appendix A.8 to overcome them, which aligns with the reviewer’s request for discussion.

Action taken: In the revised manuscript, we ran additional experiments to implement the solution suggested in Appendix A.8.1. That solution involves an extended model that addresses independent error rates and uniformity. The added results serve as a model sensitivity check for those simplified assumptions.

Finally, we would like to emphasize that our central theoretical contribution is independent of these assumptions, and the resulting methodology can be expanded to overcome the modeling limitations. (For example, the same MCMC algorithm is used with simple modifications for the extended model in the additional experiments.) A full-fledged effort towards precise characterization of the model variables presents a promising direction for future research.

W4: Results on few datasets

Response: As addressed in our general response, our central contribution is a new privacy definition and an associated auditing framework, whose theoretical properties hold independently of the dataset or GNN architecture. To address the reviewer’s concern about dataset diversity, we emphasize that our experiments on different datasets are carefully designed to demonstrate different capabilities of the framework, including, identifying factors influencing membership privacy risk across training-graph sampling strategies, model architectures, and attack configurations (RQ1); assessing the impact of membership priors on privacy estimates (RQ2); examining the implications of asymmetric membership and non-membership protection (RQ3); and evaluating the sensitivity of auditing estimates to available evidence at larger scale (RQ4). Our objective is to demonstrate these capabilities, rather than systematically compare privacy behavior across datasets and model architectures. While such comparisons on more diverse graphs constitute valuable future work, they are not necessary to establish the theoretical validity of the proposed privacy definition or demonstrate the capabilities of our auditing framework.

AuthorsOpenReview ↗

Pointwise Response to Questions from Reviewer Jth1

Q1: Difference of BMP from existing Bayesian membership privacy formulations?

Response: Our definitions are most related to Liu et al (2013)’s PMP, Lee and Clifton (2012)’s differential identifiability. Other relevant definitions, though less so, are Yang et al (2015)’s Bayesian DP, Triastcyn and Falting’s Bayesian DP, and Xiao and Devedas (2023)’s PAC Membership privacy. In our submission, all those works are cited, and their similarities and differences are explained in Appendix A.3.

Specifically, our BMP differs from each in several aspects. For example, PMP of Liu et al (2013) considers the difference between the posterior, whereas we focus directly on the posterior; MP focuses directly on the posterior, reflecting our view that the sampling phase is an integral part of the algorithm. Also, PMP is a one-sided definition, focusing either membership or non-membership alone, whereas BMP provides a unified and asymmetric protection. The main difference between BMP and Lee and Clifton (2012)’s differential identifiability is that the former is a DP-type definition and one-sided (focusing on membership only). The other three are less related, as explained in the paper: The BDP definitions are DP-type and only focus on the likelihood ratios; and PAC Bayes is not explicitly based on the posterior membership probability but on the inferential power of collective membership identification.

Q2: Would using a substantially stronger or different attack lead to very different BMP estimates?

Response: This question is related to the reviewer’s W2. A stronger attack may indeed change the results, although in the same direction for all cases; it yields larger estimates for the epsilon parameters of BMP. To safely estimate privacy, one should always use the strongest available attack. That being said, this suggestion can be made for any MIA-based auditing framework. As we have previously noted, our methodology does not exclude other attacks than the one described in Section 4.1 and used in the experiments; in fact, it can generically accommodate any MIA. We clarified this point in the revised manuscript at the beginning of Section 4.1.

Q3: evaluating the alternative models mentioned in the appendix.

Response: This question is related to the reviewer’s W3. We have evaluated the alternative, more general model in Appendix A.8.1 in the first experimental setting of Section 5.1.1. The general model has an additional s parameter in (0, 1) that stands for attack strength and applies to all the attack error rates in the model. In that way, the error rates become dependent conditional on the BMP parameters (if an attack on a node is strong, probably so is an attack on another node), and the uniformity assumption is weakened. The case s = 0 corresponds to the basic model where the attack rates are independent. Our findings are that the estimates are fairly close in the basic and extended models, and the s parameter is estimated to be close to 0, which quantitatively justifies using the simplified assumption for that particular experiment.

Reviewer_cQWnOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Bayesian Membership Privacy (BMP). The paper criticizes blind application of membership inference attack (MIA) on node classification GNN. MIA assumes independent priori of member while each node can have different exposure as each node has different subgraphs. The authors train 1000 shadow models (each of them with different randomly sampled subgraphs), and run a prior-aware likelihood-ratio membership test against each node, and feed the error into bayesian model. Experimental result using Cora and Citeseer dataset shows that the audit is sensitive to the choice of sampling mechanism. The result demonstrates that sampling effects are captured qualitatively.

Critical strengths
  1. The motivation and the research gap is very clear and evident. The proposed method is designed to address the gap.

  2. Algorithm 1 is efficient as it requires O(KJ) attack decision where J is the number of shadow models and K is the number of nodes to audit.

  3. Experiemental reuslts are solid. The actual aduit of DP-GNN revealed the privacy risk: The subgraph sampling reveals membership but it is less addressed from DP-GNN and the proposed method shows that DP-GNN's DP budget does not address it.

Critical weaknesses
  1. The estimation is never tested on a case where the right answer is known. The proposed method produces estimates of the privacy parameters, but it is only ever applied to real GNNs that nobody knows the true values. Thus it shows that the estimates are stable and that they react to changes in the setup, but it cannot tell whether they are actually correct.

  2. The experiments seems to be using simplified assumptions. The statistical model seems to have following assuptions: (1) The attack error rates are spread uniformly over the allowed region (b) The results for different nodes are independent, even though all nodes are tested against the same pool of shadow models. This matters because some conclusions (for example, that the DP model GAP has "tighter posterior intervals") depend directly on interval widths that these assumptions may distort.

  3. Everything is measured with one single attack. The paper acknowledges that a stronger attack could reveal more leakage. But the main findings are all comparisons between estimates: Bayesian estimates are smaller than prior-free ones, snowball sampling leaks more than random, GAP leaks less than non-private models.

Questions for authors

Overall, I think this is a well written paper with minor issues. Please provide rebuttal on the weeaknesses. Depending on the response I may increase the score.

3 comments
AuthorsOpenReview ↗

Pointwise Response to Reviewer cQWn

We thank the Reviewer for their comments that helped improve the paper. The reviewer’s comments are largely addressed in a broader context in our common response; here we provide our point-to-point responses. We hope these clarifications address the remaining concerns and respectfully ask the Reviewer to reconsider and improve their score accordingly.

W1: The estimation is never tested on a case where the right answer is known...

Response: Please see the second bullet point in the 2nd half of our common response. Although desirable, it is infeasible to compare our auditing estimates against the ground truth for any practical GNN training algorithm. Establishing a ground-truth privacy loss is difficult even under formal privacy frameworks. DP for instance provides conservative worst-case bounds over neighboring datasets and possible outputs, and these bounds can be loose in theoretical analyses.

W2: The experiments seem to be using simplified assumptions

Response: Please see our comment “Bayesian modelling assumptions” in the 2nd half of our common response. In the original submission, we acknowledged those limitations (Section 4.2 and Appendix A.8) and suggested solutions in Appendix A.8 to overcome them. Moreover, in the revised manuscript, we ran additional experiments to implement the solution suggested in Appendix A.8.1. That solution involves an extended model that addresses independent error rates and uniformity. The added results serve as a model sensitivity check for those simplified assumptions. Finally, we would like to emphasize that our central theoretical contribution is independent of these assumptions, and the resulting methodology can be expanded to overcome the modeling limitations. (For example, the same MCMC algorithm is used with straightforward modifications for the extended model in the additional experiments.) A full-fledged effort towards precise characterization of the model variables deserves future work.

W3: Everything is measured with one single attack...

Response: Please see the 3rd bullet point in the 2nd half of our common response, where we discuss “Attack-dependent auditing and Empirical validation”. We develop and evaluate six variants of LiRA by varying attack strength, graph access, and output perturbation. Although we used variants of a LiRA-type attack in the numerical examples, the theoretical analysis and the Bayesian estimation method do not depend on a certain attack form, such as LiRA. In particular, lines 7-9 in Algorithm 1 (MIA measurement protocol) in Appendix A.1 can be replaced with any other MIA.

Thank you for the rebuttal and I apologize for a late response.

The rebuttal has addressed W2 and W3, but I deem W1 needs additional clarification. I did not intend to ask for ground truth on GNNs and I agree that no practical GNN training algorithm has a known true privacy loss. Instead, what I wanted to ask from W1 is validating the estimator itself: the proposed framework works like a measurement instrument, and its accuracy and interval calibration can be tested on a synthetic of a simplistic mechanism whose true BMP parameters are analytically computable (such as a simple Gaussian mechanism).

My concerns besides this are addressed and hence I keep my positive rating.

AuthorsOpenReview ↗

Response to W1 - new experiments proposed

Thank you for clarifying W1. We understand that W1 asks for validation of the estimator as a measurement procedure on a mechanism with known BMP parameters, rather than ground truth for a practical GNN. Our previous response addressed the latter and did not answer this question.

To fully address W1, we will add a controlled synthetic experiment to assess how well the posterior estimates and intervals from the framework in Section 4.2 approximate known privacy parameters. We believe that this experiment would strengthen the empirical validation, and we will include it in the revised manuscript. As this clarification came only at the final stage of the rebuttal period, we outline the proposed experimental design. We emphasize, however, that the theoretical foundation of our auditing framework is already established by Theorem 4, which provides an exact characterization of BMP through membership-inference error probabilities. The proposed experiment serves a complementary purpose: evaluating the accuracy and uncertainty calibration of the practical Bayesian estimator in Section 4.2.

Experiment planned for the revision

Step 1: We will use a population of NN individuals and Poisson sampling: The targeted sampling mechanism and the algorithm are as follows:

  • Samping mechanism P\mathcal{P}: Each individual is independently included with known probability pp.
  • The mechanism Φ\Phi releases each inclusion bit with independent Laplace noise of scale bb.

For a target individual, the exact likelihood-ratio attack is known; because the other released coordinates are independent of that individual’s membership, they provide no additional information. The mechanism is ε\varepsilon-MP with ε=1/b\varepsilon=1/b. By the paper’s MP-to-BMP relation, with η=p/(1−p)\eta=p/(1-p), its analytic benchmark is

(εL,εR)=(1b−log⁡η,  1b+log⁡η).(\varepsilon_L,\varepsilon_R) = \left(\frac{1}{b}-\log\eta,\; \frac{1}{b}+\log\eta\right).

For example, p=0.25p=0.25 and b=0.5b=0.5 give the benchmark (3.0986,0.9014)(3.0986,0.9014).

Step 2: We will generate repeated synthetic shadow audits and apply the paper’s error-count measurement protocol and posterior model in Section 4.2. We will compare two attacks:

  • Attack 1: the exact likelihood-ratio test, which uses the ratio of Laplace densities. This version isolates the estimator’s behavior when the hypotheses are exactly known, and the best possible attack is applied.

  • Attack 2: This attack fits normal distributions to the noisy membership information for H0H_0 and H1H_1, using the shadow models in a leave-one-out fashion, just like in Algorithm 1. This attack will be used to reflect the paper’s practical attack procedure.

Step 3: Finally, we will let MHAAR (Algorithm 2) estimate the BMP parameters using the audit results.

Across independent audit replications, we will assess point-estimation accuracy and the empirical coverage and width of the posterior intervals. We will also vary the sampling prior, noise scale, and number of shadow models to examine how these factors affect estimation and calibration.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Response to shared concerns of Reviewers, paper updated with new experiments

We thank the reviewers for their constructive feedback. The reviewers highlight the motivation, relevance of the BMP’s theoretical formulation, and the Bayesian estimation as positive aspects of the paper, while sharing some concerns, many of which are common.

The shared concerns relate to conceptual novelty (Jth1, DrjR), attack-dependent auditing (all three), empirical validation (cQWn, Jth1), and Bayesian modeling assumptions (all three).

In this part, we will address these shared concerns. Then, we will respond to each reviewer's specific comments.

Action taken: We have revised the paper to include additional experimental work; please see the newly added Appendix A.10.5. The new experiments aim to address the reviewers’ concerns about the uniformity and independence assumptions for the attack rates. We already acknowledged these concerns as limitations in the first submission (in Appendix A.8.1) and proposed an extension to tackle them. The added experiments estimate the privacy parameters using the extended model and compare those estimates with the existing ones as a model sensitivity check.

Novelty and our contribution: Reviewers Jth1 and DrjR raised concerns about BMP's novelty in relation to existing privacy formulations and established methodological approaches. Our main contributions are BMP as a new privacy definition, and its theoretical properties (Section 3), including prior-induced privacy bounds, post-processing, composition properties, and error rates of membership inference attacks as hypothesis tests. a new Bayesian method to estimate the privacy parameters of BMP with quantified uncertainty (Section 4.2), and a new computation-efficient auditing pipeline that provides observations (error counts) to the Bayesian estimation algorithm (Section 4.1). We would like to respond to the reviewers’ concerns based on the contributions above.

  • Novelty of BMP definition (Jth1): In the paper, we discuss the BMP in relation to the existing definitions in Appendix A.3. As a key contribution, BMP treats the training-set sampling mechanism as an integral part of privacy, incorporating heterogeneous membership priors directly into privacy guarantees. Unlike prior-independent membership privacy definitions, BMP incorporates sampling-induced membership risks; and, unlike formulations that measure changes from prior to posterior beliefs, BMP directly bounds the adversary's posterior membership odds. Incorporating heterogeneity is particularly important: For example, nodes with high membership distinguishability can nevertheless have low posterior membership risk due to low inclusion probabilities, as demonstrated by our experiments (Please see Figure 3). BMP therefore captures privacy heterogeneity overlooked by prior-unaware measures and provides a basis for targeted privacy protection, potentially reducing unnecessary noise for lower-risk nodes. Moreover, BMP differs from other definitions by being a two-parameter definition, so that it can treat posterior membership and non-membership probabilities separately and asymmetrically. In the paper, we mention why membership or non-membership can be more important depending on the scenario and give three real-life examples (Examples 1, 2, and 3) in Appendix A.1.

  • Relation to hypothesis-testing (Jth1, and DrjR): The prior-dependent and asymmetric nature of BMP leads to Theorem 4, which characterizes admissible MIA error probabilities. Theorem 4 is the bridge from Section 3 to Section 4: Our auditing framework builds on this very theorem, which is not found in earlier works to the best of our knowledge. Therefore, we believe that relating BMP to hypothesis testing or related mathematical techniques does not diminish the novelty of our estimation framework. Overall, we believe that the paper contains distinct conceptual, theoretical, and methodological contributions, not merely applications of existing work to GNNs.

AuthorsOpenReview ↗

Response to shared concerns of Reviewers, paper updated with new experiments continued...

Attack-dependent auditing and Empirical validation: Reviewers question the absence of comparisons against known ground-truth privacy parameters (cQWn) and the dependence on specific attacks (cQWn, Jth1, and DrjR).

  • We would like to emphasize that the absence of ground truth and specific attacks are inherent characteristics of empirical privacy auditing: true worst-case privacy loss is generally unknown, and no finite set of attacks can rule out stronger adversaries (unless the exact likelihood ratio attack can be implemented, which is almost always intractable). Hence, our approach follows the established MIA-based auditing literature.

  • On a related note, we agree with Reviewer (cQWn) that comparing auditing results with ground truth would be highly desirable. However, we are not aware of a privacy-preserving GNN training method that attains its claimed privacy tightly. Establishing a ground-truth privacy loss is difficult even under formal privacy frameworks. DP for instance provides conservative worst-case bounds over neighboring datasets and possible outputs, and these bounds can be loose in theoretical analyses.

  • The claim that we evaluate only a single attack is not accurate: we develop and evaluate six configurations varying attack strength, graph access, and output perturbation. These enable controlled comparisons across sampling strategies, GNN architectures, and privacy mechanisms. Our objective is not to develop the strongest possible attack or certify individual GNNs, but to establish a theoretical foundation for BMP auditing and demonstrate its practical feasibility. Our Theorem 4 provides an exact, attack-independent characterization of BMP in terms of error rates. Relatedly, our auditing framework in Section 4 can use any membership inference attack (MIA) of choice; so a specific attack such as LIRA is not indispensable for the proposed methodology. Specifically, in Algorithm 1 in Appendix A.1, lines 7-9 can be replaced with any more powerful MIA. Stronger attacks are certainly preferable and may change the estimates, but not the BMP definition or its theoretical characterization.

Bayesian modeling assumptions: All three reviewers raise concerns about the uniformity and independence assumptions in our Bayesian estimator. We emphasize that these assumptions and their limitations are already explicitly acknowledged in Section 4.2 and Appendix A.8. Appendix A.8.1 introduces an alternative model incorporating attack strength, and Appendix A.8.2 provides a dependence-aware model accounting for correlations arising from shared shadow models. Due to the 9-page limit, most of that discussion is in the Appendix; however, we may try to move it to the main part if the reviewers deem it necessary.

  • Importantly, our central theoretical contribution is independent of these assumptions: We introduce a sampling-aware privacy definition and establish an exact characterization through MIA error probabilities (Theorem 4), providing a rigorous basis for empirical BMP auditing. Our Bayesian estimator demonstrates how this characterization can be made operational in practice. A large-scale evaluation of alternative probabilistic models and their effects on uncertainty quantification is a natural direction for future work and has been partially discussed in Appendix A.8.

  • New experiments regarding uniformity and independence: As uniformity and independence of attacks over the nodes are a shared concern among the reviewers, we have included additional experimental work towards addressing those limitations. (Please see the newly added Appendix A.10.5). The added experiments estimate the privacy parameters using an extended model (described in Appendix A.8.1), where the attack error rates are non-uniform and dependent as a result of a common strength parameter that binds the attack performances. We compare the new estimates, which are based on the extended model, with the existing estimates as a sensitivity check.

We hope our responses have addressed the reviewers’ concerns and hope that they would update their scores. We would be happy to clarify any remaining questions or concerns.

AuthorsOpenReview ↗

New revision - Experiments on Reddit data now fully rerun with extended model

In further response to the reviewers' concerns about Bayesian modeling assumptions, We just uploaded a new revision that adds a new set of experiments with the extended model in Appendix A.8.1. Please see Appendix A.10.5 for the change. (As a reminder, the "extended model" addresses concerns about the uniformity and independence assumptions for the attack rates.)

The new experiments repeat the runs in the "Effect of the number of nodes..." part of Section 5.1.1 for the extended model. In this way, we repeat all experiments in Section 5.1.1 on the Reddit data with the extended model. By comparing the new results with the existing ones, we assess the sensitivity of the conclusions to model selection.

AuthorsOpenReview ↗

Requesting Reviewers for feedback as discussion period is ending

Dear Reviewers,

We thank you for your time for the review. As the discussion period is ending soon, we would appreciate any feedback from you and hope that your concerns have been addressed.

Best, Authos

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.