Practical Bayes-Optimal Membership Inference Attacks

We thank the reviewer for the thoughtful and detailed feedback, which has helped us improve the paper. We hope we have addressed all of your comments thoroughly and satisfactorily.

WEAKNESSES

W1.

See response to your Question 1 below.

W2.

See response to your Question 3 below.

W3.

We appreciate the reviewer’s comment and agree that the ethical and societal implications of privacy attacks warrant explicit discussion. Our work focuses on quantifying privacy risks in machine learning models, and we recognize that the same techniques could, in principle, be used maliciously. However, we align with the long-standing practice in the cryptography and security communities, where publishing attacks is essential to understanding system vulnerabilities and ultimately designing safer, more trustworthy systems.

Our stance is that the benefit of making such vulnerabilities visible (specifically enabling developers and auditors to assess membership leakage before releasing models trained on sensitive data) far outweighs the potential misuse of these attacks. We believe that transparency is a prerequisite for responsible deployment, and our contribution is intended to support risk-aware decision-making and the development of more robust privacy-preserving techniques.

We will add a brief discussion to the camera-ready version to reflect this perspective more clearly.

QUESTIONS

Q1.

We agree that assuming the adversary has access to the full graph $\mathcal{G}$ is a strong assumption. However, this assumption is conceptually similar to the standard membership inference threat model (e.g., in the LIRA [1] and RMIA [2] papers), where the adversary is assumed to have access to a population pool from which the training set is sampled. Similarly, in our setting, full graph access corresponds to a worst-case assumption, which is particularly relevant for privacy auditing.

In our setting, when the challenger samples a relatively small subset of nodes from a large population graph, this threat model remains relevant for practical scenarios. In our experiments (except in the mismatched adversary scenario), we assume the adversary has perfect side knowledge about the fraction of nodes sampled by the challenger (which mirrors common assumptions in the i.i.d. MIA literature) and let the challenger sample 50% of the nodes. Compared to the case where a smaller fraction is sampled, this setup is favorable to the adversary, as it increases the likelihood of overlap between the shadow and target training sets. Accordingly, our reported attack performance should be interpreted as an upper bound. Such upper bounds are valuable in privacy auditing, as they help assess worst-case exposure under strong adversarial assumptions.

We agree that relaxing the assumption of full graph knowledge, e.g., allowing the adversary to observe only a noisy or partially observed graph, is an interesting direction for future work. For clarity and simplicity, and privacy auditing purposes, we focused on the full-graph setting in this work. That said, we see extensions to weaker threat models as both feasible and worthwhile, but they are non-trivial and would require substantial work and careful thought.

[1] Carlini et al. "Membership inference attacks from first principles." IEEE SP, 2022.

[2] Zarifzadeh et al. "Low-cost high-power membership inference attacks", ICML 2024.

Q2.

Thank you for your comment. We acknowledge that a more detailed analysis of the computational complexity of the proposed attacks would strengthen the paper and plan to include this discussion in the revised manuscript.

To clarify, our claim on computational efficiency refers partly to BASE and G-BASE being feasible approximations of the intractable Bayes-optimal membership inference rule, and partly to BASE being a more efficient option than RMIA and LiRA. We realize that the current phrasing of some statements including both BASE and G-BASE may have unintentionally implied otherwise, and we will revise it to avoid any misunderstanding.

BASE is more efficient than RMIA, which is the current state-of-the-art method, because it requires significantly fewer queries to the target model during the attack. More specifically, our attack BASE requires only a single query to the target model, while RMIA may require thousands. LiRA has similar per-shadow-model efficiency as BASE (in terms of model queries), but our results show that BASE achieves strong performance with relatively few shadow models, while LiRA typically requires a larger number, as also noted in the RMIA paper [2].

On the other hand, G-BASE is more computationally demanding. This is expected, as it is specifically designed to leverage the full graph structure to approximate the Bayes-optimal membership inference rule for GNNs (derived in Sec. 4.2), which naturally introduces additional cost. This sets it apart from BASE, RMIA, and LiRA, which cannot exploit graph connectivity and thus do not capture this richer structure. Unlike BASE, which can evaluate all target nodes in one pass, G-BASE must process each node individually, since its loss signal requires sampling subgraphs and comparing losses with and without the target node for each sample.

Despite its higher cost, G-BASE remains a feasible and effective option for privacy auditing of GNNs, significantly outperforming baseline methods, including BASE.

We agree that a direct analysis of computational cost would strengthen this claim, and we have measured the average wall-clock time (in seconds) for BASE and RMIA on the Pubmed and Flickr datasets:

The time measured here is the inference time of the (online) attacks, after 8 shadow models has been trained. The time to train the shadow models is the same for all attacks. We will incorporate these results into the camera-ready version to support our efficiency claim more concretely.

Q3.

We agree that providing more guidance on the selection of shadow model count and sampling strategy would strengthen the paper, and we will clarify this in the revised version.

In general, increasing the number of shadow models improves attack performance by providing a better approximation of the model distribution. However, this comes with additional computational cost. In practice, we recommend using as many shadow models as computational resources allow. However, our experiments show that BASE and G-BASE achieve strong performance even with a relatively small number of shadow models, with performance improving only marginally when increasing the number of shadow models from 8 to 128. This is in contrast to LiRA [1], which typically requires significantly more shadow models, as already noted in the RMIA paper [2].

Regarding sampling strategies, Appendix H.3 presents a detailed comparison and shows that G-BASE performs consistently well across all three proposed sampling methods. We attribute this robustness to the way G-BASE approximates the Bayes-optimal decision rule. For the reviewers convenience, we provide an excerpt from Appendix H.3:

"Recall that we have approximated the model distribution $p(\phi|\tilde{\mathcal{M}},\mathcal{G})$ by a prior distribution $p(\phi|\mathcal{G})$. If $p(\phi|\tilde{\mathcal{M}},\mathcal{G})$ were estimated more accurately, e.g., by training shadow models on the nodes indicated by $\tilde{\mathcal{M}}$, then the fidelity of the sampling strategy may have a larger impact on the attack performance."

We will clarify these points in the revised version of the paper to provide more practical guidance.

Q4.

We agree that extending the Bayesian framework to other GNN tasks, such as graph-level and edge-level MIAs, is a natural and promising direction for future work.

Extending the Bayesian framework to graph-level MIAs is relatively straighforward. Standard graph classification datasets typically assume i.i.d. samples at the graph level, making them compatible with the assumptions of the Bayes-optimal framework for i.i.d. data. As a result, this setting can be addressed similarly to traditional MIAs on i.i.d. data, see, e.g., [3].

In contrast, extending the framework to edge-level MIAs poses more significant challenges. Formulating a proper threat model and identifying informative attack signals at the edge level is nontrivial. We are currently investigating edge-level MIAs as part of our ongoing research and consider this a promising and largely unexplored area.

[3] Krüger et al. "Publishing neural networks in drug discovery might compromise training data privacy." Journal of Cheminformatics, 2025.

Q5.

We thank the reviewer for this thoughtful and constructive suggestion. Indeed, given the probabilistic nature of our scoring function, applying confidence calibration to the output of the attack is a natural and valuable extension. While our Bayes-optimal framework produces scores that can be interpreted as membership probabilities, these may be miscalibrated in practice. Calibrating these outputs using methods such as Platt scaling or isotonic regression [4] could make the scores more reflective of true membership likelihoods. This would significantly enhance the interpretability and practical usefulness of the attack in privacy auditing scenarios, where stakeholders may rely on well-calibrated risk scores to assess or mitigate exposure. We had not explored this direction prior to the review, and we appreciate the insight. We will mention this point in the final version as a promising direction for future work.

[4] Guo et al. "On calibration of modern neural networks." ICML, 2017.

We thank the reviewer for the thoughtful and detailed feedback, which helped us improve the paper. We believe we have addressed all of your comments thoroughly and satisfactorily. If our responses resolve your concerns, we would be grateful if you would consider updating your score accordingly.

WEAKNESSES

W1

We appreciate the reviewer's feedback. We have addressed all questions raised in the review, and we believe our responses provide satisfactory clarification. We will update the technical sections in manuscript to reflect these clarifications and improve clarity.

W2 and Q4.

While LiRA and RMIA were originally developed for i.i.d. data, they can be adapted to the graph setting by treating the graph as a collection of node feature-label pairs and ignoring edge information during the attack. Specifically, the attack is applied to the “0-hop” neighborhood, where each target node is treated in isolation from its neighbors. Importantly, the shadow models are still trained on full graphs with connectivity, just like the target model.

While one could attempt to use the full graph structure in the attack, i.e., obtain confidence values by querying the entire k-hop neighborhood, this typically leads to poorer performance, as the shadow graphs contain a mix of member and non-member nodes, making the model predictions on member and non-member nodes less distinguishable.

We acknowledge that this adaptation was not clearly explained in the paper and will revise the manuscript to clarify this point.

W3.

We thank the reviewer for bringing this to our attention and sincerely apologize for the oversight on line 228, where the comment ``$i$ to $\tilde{\mathcal{M}}$ - johan'' containing a first name was inadvertently left in the submission. We fully recognize the importance of the double-blind review process and regret this unintentional mistake. However, we stress that a (common) first name alone is unlikely to identify the authors. We also note that, in practice, many submissions are available on arXiv, and author identities may be discoverable regardless. That said, we take this concern seriously and apologize again.

QUESTIONS

Q1.

We thank the reviewer for catching this. There is indeed a typo in the argument of $S_\mathcal{L}$ in Equation~(8). The expression $S_\mathcal{L}(\phi_k, \mathcal{G}, m_v)$ should read $S_\mathcal{L}(f_{\phi_k}, v, \tilde{\mathcal{M}}_i, \mathcal{G})$. This is purely a typographical error and does not affect the derivation, implementation, or results in the paper. We will correct this in the camera-ready version, if accepted.

Q2.

There is indeed a notational oversight in Def. 2 of the G-BASE attack: the dependence on index $i$ is missing in $\tilde{\mathcal{M}}$. The correct expression is $\tilde{\mathcal{M}}_i$. This is a typographical issue only and does not affect the derivation or implementation, which correctly reflect the sampling procedure. We will fix the notation.

Q3.

We thank the reviewer for this comment. In our setting, the prior $p(\theta|\mathcal{G})$ (implicitly defined by the threat model) is the distribution of the model parameters before conditioning on $\tilde{\mathcal{M}}$, where $\tilde{\mathcal{M}}$ defines the subset used to train the model disregarding the target node. The prior distribution is then computed by integrating over subsets of $\mathcal{G}$, possibly taking advantage of any side-knowledge about the fraction of training nodes, the sampling procedure, or the training algorithm. In practice, this integration is estimated through Monte Carlo sampling, with samples obtained by training shadow models on subgraphs sampled from $\mathcal{G}$, which are independent of the target node and the $\tilde{\mathcal{M}}$ in the outer expectation. While this is described implicitly in Section 4.3, we acknowledge that this could have been made more explicit. We will revise the manuscript to clarify this point.

We also note that assuming perfect knowledge of the training procedure is standard in the MIA literature, as it yields a meaningful upper bound on attack performance. Our mismatched adversary experiments (see Figure 9 in Section 6 and Table 8 in Appendix H.2) specifically aim to test robustness when this assumption is relaxed.

Q5.

Our framework involves two distinct types of sampled graphs. The first corresponds to the subgraphs used to train the shadow models: these are used to approximate the inner expectation in both G-BASE (Definition 2) and BASE (Definition 3). Their number, denoted by $K$, is always equal to the number of shadow models, and this holds for all attacks. The second type refers to the sampled graphs used to compute the outer expectation in G-BASE (over membership configurations $\tilde{\mathcal{M}}$). The number of these samples, denoted by $M$, is an independent hyperparameter of the attack and does not need to match the number of shadow models. Both types of sampled graphs serve to approximate expectations via Monte Carlo estimation. Therefore, it is generally beneficial to use as many samples as possible, subject to the available computational budget.

Q6.

Variable $\alpha$ (referred to in line 317 of the paper) is a hyperparameter introduced in the offline version of BASE and G-BASE to account for the absence of shadow models trained with the target node. This compensates for the lack of target-specific information available in the offline setting. The same idea is used in RMIA, which also introduces a similar hyperparameter for the offline case.

Due to space constraints, the discussion of the offline vs. online setting and the role of $\alpha$ was moved to App. F, which is referenced in the main text following line 299. For the reviewer's reference, we copy here the text following line 299:

"Online and offline setting. We evaluate both online and offline attacks, as defined in Appendix F, and compare BASE and G-BASE with LiRA and RMIA in both settings."

Appendix F clearly defines both settings and explains the introduction of $\alpha$ in the offline setting. We copy part of the text here for reference:

"To compensate for the lack of in-models in the offline setting, we introduce a scaling factor $\alpha\in[0,1]$ on the Monte Carlo loss term over shadow models[…]”

(see Eq. 22 in App. F)

To improve clarity, we will explicitly add ``(see App. F)'' after mentioning $\alpha$ in the main text in the revised version of the manuscript.

Q7.

$K$ denotes the number of shadow models. As expected, increasing $K$ generally improves attack performance for all attacks, as it leads to a better approximation of the model distribution. However, this comes at the cost of training additional shadow models, which may be computationally expensive. In practice, $K$ is typically constrained by available computational resources. Importantly, the performance gains from increasing $K$ often exhibit diminishing returns beyond a certain point. BASE, G-BASE, and RMIA perform strongly even with a small number of shadow models; in some cases, we observe little to no improvement when increasing $K$ from 8 to 128. Hence, $K$ can be chosen to be small. LiRA, on the other hand, tends to benefit more from larger $K$ within this range, although prior work suggests that its performance also eventually saturates [1, Fig. 17]. A key advantage of our attacks, as well as RMIA, is that they typically achieve strong performance even with a low number of shadow models.

[1] Carlini, et al. "Membership inference attacks from first principles." SP, 2022.

Q8.

Due to space constraints in the rebuttal, we refer to our response to Q2 from Reviewer U2Mu, which raised a similar question. As both questions are closely related, we chose to provide a unified answer there.

Q9.

Except in the mismatched adversary setting, all experiments use 50% of the nodes to train both target and shadow models; this will be clarified in Appendix A. In the mismatched (Sec. 6, following line 341), the challenger trains on 35% of the nodes, while the adversary assumes 50%, creating a deliberate mismatch.

The data population pool assumption is flexible and allows for any proportion of nodes to be used when training target and shadow models. While a more realistic and challenging setting may involve the challenger training on a smaller subset of a larger graph, using 50% of the nodes provides a practical and meaningful baseline when auditing GNNs on a specific dataset.

In a privacy auditing scenario, where a model provider wants to measure the privacy of a model that will be trained on a dataset, the target model to audit has to be trained on a fraction of the dataset to leave out non-member samples. Using a too small fraction can lead to models that differ significantly from those trained on the full dataset, hence MIAs may fail to properly measure the privacy risk of the full model. Conversely, using a very large training fraction, and assuming a “matched'' adversary, can result in substantial overlap between the shadow and target training sets, leading to overly potent attack performance. Using 50% strikes a reasonable balance: it avoids unrealistic overlap while ensuring the model is representative of typical training conditions.

MINOR CONCERNS

MC 1.

We defined G-BASE (Graph Bayes-Approximate membership Status Estimation) in Line 299, after the formal definition of the attack. However, we agree it would be clearer to introduce it at first mention and will move the definition accordingly. Note that the acronym omits the “M” in “membership” to align phonetically with BASE, which is intended to evoke “Bayes.”

The name BASE follows the same naming convention, but we did not define it explicitly. We will revise the manuscript and define all acronyms.

MC 2.

See our response to your Q6.

MC 3.

We will add a brief explanation of these functions and include an additional reference to improve clarity for readers less familiar with GNNs.

We thank the reviewer for the thoughtful and detailed feedback, which has helped us improve the paper. We believe we have addressed all of your comments thoroughly and satisfactorily. If our responses resolve your concerns, we would be grateful if you would consider updating your score accordingly.

WEAKNESSES:

W1. "The core idea of this paper is Bayes-optimal framework, which has been previously explored on MIAs, limiting the novelty."

Response:

While our work builds on the Bayes-optimal framework introduced in [1], we make substantial and novel contributions by extending it to graph neural networks (GNNs). Specifically, we derive the Bayes-optimal decision rule for node-level MIAs against GNNs, revealing how graph structure fundamentally impacts optimal attack strategies, an aspect not addressed in previous work.

We also derive practical approximations to the Bayes-optimal decision rule for the i.i.d. case, leading to attacks that not only outperform those in [1], but also match or surpass the state-of-the-art attacks for i.i.d. data, namely, LiRA and RMIA.

Finally, we formally prove the equivalence between our attack BASE and RMIA, providing a rigorous foundation for a widely-used state-of-the-art method.

Together, these contributions represent a significant advancement of both the theory and practice of MIAs.

[1] Sablayrolles et al. "White-box vs black-box: Bayes optimal strategies for membership inference." ICML, 2019.

W2. "Writing quality needs improvement for clarity and precision."

Response:

We appreciate the feedback and acknowledge that there are a few typos and minor phrasing issues, which we will correct in the final version. We have aimed to present our ideas as clearly and precisely as possible, and some reviewers found the writing to be strong. We will continue to refine the presentation to ensure maximum clarity.

QUESTIONS:

Q1. "In Section 6, while the experiments are comprehensive, the analysis lacks depth. There should be more deeper discussion, for example, why the proposed methods perform better on some datasets but not on others, and why your methods have better robustness against mismatched adversarial assumptions."

Response:

We agree that a more detailed interpretation of the experimental results would strengthen the paper. If accepted, we will revise the discussion accordingly in the camera-ready version, using the additional page. Below, we highlight some insights:

G-BASE performs worse on smaller and sparser datasets like Cora and Citeseer. In our setup, target and shadow graphs are constructed by sampling 50% of the nodes, which significantly reduces graph connectivity and can lead to isolated nodes. Since G-BASE relies on neighborhood structure to infer membership, its effectiveness degrades when this structure is weak or fragmented. In contrast, on larger and denser datasets, where the sampled subgraphs retain more structural information, G-BASE can better exploit the graph topology and achieves stronger performance. We sample 50% of the datasets 10 times and report the average degree of a node (the number of edges connected to the node) and the fraction of isolated nodes:

This reveal that the citation network become fairly sparse after sampling 50% of the nodes uniformly. However, G-BASE achieves comparatively good performance on Pubmed despite its many isolated nodes and high fraction of isolated nodes, indicating that this is not the full story. To gain further insights, we plan to investigate the properties and local neighborhood for the nodes that the attacks identify as members with the highest confidence. (The Github dataset also presented in the paper is currently unavailable to us due to a bug in PyG. However, since the Github dataset has 37700 nodes and 578006 edges, it is likely to retain high connectivity even after sampling 50% of the nodes uniformly). We will revise the manuscript to include a more thorough discussion around these points. However, we stress that explaining the behaviour of MIAs against GNNs is further complicated by the complex interactions between nodes that are introduced by the message-passing mechanism. Therefore, it is non-trivial to provide further insights into the behaviour of the attacks.

As for the robustness under mismatched adversarial assumptions, we do not yet have a definitive explanation for why some attacks, including ours, exhibit greater robustness. However, we note that this remains an open question in the literature; similar observations were made but not fully explained in both LiRA [2] and RMIA [3] papers for i.i.d. data.

[2] Carlini, Nicholas, et al. "Membership inference attacks from first principles." SP, 2022.

[3] Zarifzadeh et al. "Low-cost high-power membership inference attacks", ICML 2024.

Q2. "In Section 4.3, several sampling strategies are proposed to approximate the Bayes-optimal rule. It would be helpful to clarify how each strategy influences performance, and which specific strategies are used in your experiments."

Response:

The influence of each sampling strategy on G-BASE performance is evaluated and compared in Appendix H.3, titled "Comparison of Sampling Strategies for G-BASE."

In the main paper, the specific sampling strategy used in each experiment is indicated by a label: (MI) denotes model-independent sampling, and (MIA) refers to 0-hop MIA sampling. For the reviewer's convenience, we provide an excerpt from Section 6:

"We evaluate G-BASE for both model-independent sampling (MI) and $0$-hop MIA sampling (MIA) (see Section 4.3), using BASE as the $0$-hop MIA. In offline mode, only the best-performing sampling strategy is reported. Results with MCMC sampling are presented in Appendix H.3."

and another excerpt from Appendix H.3:

"In Section 4.3 and Appendix B.2, we proposed three different sampling strategies to sample from $P(\tilde{\mathcal{M}}|\theta,\mathcal{G})$, for the purpose of evaluating the expected value in the Bayes-optimal membership inference rule. Here, we evaluate and compare the impact of the sampling strategy on the attack performance of G-BASE. Table 9 shows the attack performance of G-BASE over different datasets and model architectures, using each of our three sampling strategies: model-independent sampling (MI), 0-hop MIA sampling (MIA), and the Metropolis-Hastings sampling (MCMC)."

Q3. "The organization of the paper could be improved. Sections 2 to 5 could be made more concise to allow more space for in-depth experimental discussion and analysis in Section 6."

Response:

We appreciate the suggestion. We agree that expanding the experimental analysis would strengthen the paper. If accepted, we will use the additional page in the camera-ready version to provide a deeper discussion of the results in Section 6.

Thank you for the authors’ response, which has addressed my concerns. I look forward to seeing the full version of the paper.

We thank the reviewer for the thoughtful and detailed feedback, which has helped us improve the paper. We believe we have addressed all of your comments thoroughly and satisfactorily. If our responses resolve your concerns, we would be grateful if you would consider updating your score accordingly.

WEAKNESSES:

Note: We provide a joint response to Reviewer’s Weaknesses 1 and 2, as they are closely related.

W1 and W2. "Though the authors have shown excellent results, the scale of the datasets used question the real world use cases. Can Bayes-optimal MIA scale to real world models like SD-3.5 or FLUX image gen models which are trained across billions of image-text pairs? It is hard to draw conclusions about the practicality when the empirical data is orders of magnitude smaller. In the same vein, the method also requires training multiple shadow models which is also not viable as training good large models costs millions of dollars."

Response:

Our work focuses on models trained to perform classification tasks, as is standard in the MIA literature (e.g., LiRA and RMIA). While our Bayes-optimal MIA framework can be extended to regression models and even autoregressive LLMs, it is not directly applicable to generative diffusion models such as SD-3.5 and FLUX. Deriving a Bayes-optimal MIA against such models is an interesting but separate research direction.

The datasets we consider are standard in the GNN literature, and more diverse than what has previously been explored in node-level MIA work [2-4]. Furthermore, our datasets include real-world examples such as Amazon-Photo [5] which is a segment of the Amazon-co purchase graph [6] containing objects from the Amazon web store. Thus, the experiments we consider also reflects realistic use cases.

Regarding scalability, state-of-the-art MIAs, including LiRA, RMIA, and ours, require training shadow models, which becomes prohibitively expensive for models with billions of parameters and training examples. Our method is no exception but neither are the baselines LiRA and RMIA. There is a recent work that scales up LiRA to moderately-large language models [1], but this requires computational resources well beyond what we have access to. Ultimately, attacking models that are extremely costly to train is itself extremely costly.

[1] Hayes et al. "Strong Membership Inference Attacks on Massive Datasets and (Moderately) Large Language Models." arXiv, 2025.

[2] Olatunji et al., "Membership Inference Attack on Graph Neural Networks" TPS-ISA, 2021.

[3] Duddu et al., "Quantifying Privacy Leakage in Graph Embedding," MobiQuitous, 2020.

[4] He et al., "Node-Level Membership Inference Attacks Against Graph Neural Networks," arXiv, 2021.

[5] Shchur et al., "Pitfalls of Graph Neural Network Evaluation," NeurIPS, 2018.

[6] McAuley et al., "Image-based Recommendations on Styles and Substitutes," SIGIR, 2015

QUESTIONS:

Q1. "Can this be verified on reasonably large datasets like ImageNet? Example tasks can be generation models trained on the dataset."

Response:

BASE can indeed be applied to ImageNet-trained classifiers, and a comparison with other i.i.d. MIAs on ImageNet is possible. However, crucially, we prove in the paper that BASE is equivalent to RMIA (Theorem 2), which was evaluated on ImageNet in its original paper [7]. Thus, due to our theoretical result, BASE is guaranteed to match RMIA's strong performance on ImageNet, at a reduced computational cost due to needing fewer model queries. Given this theoretical equivalence, we believe additional experiments on i.i.d. datasets would offer limited new insight. Instead, we focus more on graph data, where our contributions and experiments are extensive.

We also reiterate that our Bayes-optimal MIA is designed for classification tasks (as it is standard in the MIA literature) and does not directly apply to generative models.

[7] Zarifzadeh et al., "Low-cost high-power membership inference attacks.", ICML, 2024.

Q2. "Another prohibiting factor for real world deployment is the cost of querying these large models for obtaining log-probs. Would love to hear authors' take on that."

Response:

We agree that minimizing the number of queries is critical in real-world scenarios, where API access may be limited or costly. Our attack BASE requires only a single query to the target model, yet matches the performance of RMIA, which can require thousands of queries. Our G-BASE attack requires just two queries to the target model per sampled graph. As our results indicate, 8 sampled graphs yields already strong performance, and so 16 queries is enough (per target sample).

Moreover, querying GNNs (our focus) is significantly cheaper than querying large generative image/video models.

Finally, in the MIA literature, it is common to assume that the black box access to the target model produces class probabilities (e.g., LiRA and RMIA papers), which is also the setting we study. There are "label-only" attacks that weaken this assumption and assume only access to the predicted label, but this falls outside the scope of this work. In practice, APIs to models can give either soft or hard predictions, depending on the use-case, and so both scenarios are interesting to study.