Practical Bayes-Optimal Membership Inference Attacks
Authors: Marcus Lassila
Johan Östman
Khac-Hoang Ngo
Alexandre Graell i Amat
Venue: NeurIPS 2025 poster ()
Keywords: Membership Inference Attacks
Privacy
Security
Graph Neural Networks
Machine Learning
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: We develop practical and theoretically grounded membership inference attacks (MIAs) against both independent and identically distributed (i.i.d.) data and graph-structured data. Building on the Bayesian decision-theoretic framework of Sabrayolles et al., we derive the Bayes-optimal membership inference rule for node-level MIAs against graph neural networks, addressing key open questions about optimal query strategies in the graph setting. We introduce BASE and G-BASE, tractable approximations of the Bayes-optimal membership inference. G-BASE achieves superior performance compared to previously proposed classifier-based node-level MIA attacks. BASE, which is also applicable to non-graph data, matches or exceeds the performance of prior state-of-the-art MIAs, such as LiRA and RMIA, at a significantly lower computational cost. Finally, we show that BASE and RMIA are equivalent under a specific hyperparameter setting, providing a principled, Bayes-optimal justification for the RMIA attack.

Practical Bayes-Optimal Membership Inference Attacks
Marcus Lassila'
Johan Östman2
Khac-Hoang Ngo
Alexandre Graell i Amat
Chalmers University of Technology
Al Sweden
Linköping University
Abstract
We develop practical and theoretically grounded membership inference attacks (MIAs) against both independent and identically distributed (i.id.)) data and graph- structured data. Building on the Bayesian decision-theoretic framework of [1], we derive the Bayes-optimal membership inference rule for node-level MIAs against graph neural networks, addressing key open questions about optimal query strategies in the graph setting. We introduce BASE and G-BASE, tractable approx- imations of the Bayes-optimal membership inference. G-BASE achieves superior performance compared to previously proposed classifier- based node-level MIA attacks. BASE, which is also applicable non-graph data, matches exceeds the performance of prior state-of-the -fee-of-hhe-rttt MIAs, such as LiRA and RMIA, at a significantly lower computational cost. Finally, show that BASE and RMIA are equivalent under a specific hyperparameter setting, providing a principled, Bayes-optimal justification for the RMIA attack.
Introduction
Machine learning models known leak information about their training data [2-5], driving growing interest in understanding and quantifying such leakage. Due to the complexity of modern models, formally characterizing their information leakage remains formidable challenge. As result, privacy is often assessed empirically via so-called privacy auditing-designing attacks to identify data leakage and guide mitigation strategies.
Membership inference attacks (MIAs), where an adversary seeks to infer whether a specific data point was included in the training set of model, represent the most fundamental privacy attack. Importantly, MIAS already pose a serious privacy threat: disclosing the mere presence of a data point in the training set may constitute serious privacy violation and directly contravenes privacy regulations such as the GDPR. The European Data Protection Board explicitly cites MIAS in its guidance when machine learning model can be considered anonymous [6]. Moreover, MIAs serve as a key component in data reconstruction attacks by filtering out unlikely candidates, thereby narrowing the search space [7], and can be used establish lower bounds the privacy guarantees algorithms [8].
of differentially-priie
State-of-the-ate MIAs often rely shadow models-auxinee models trained under similar condi- tions as the target model-to empirically characterize behavioral differences between training and non-training data. Existing attacks fall into two main categories: classifier-based and statistic-based Classifier based attacks use features from shadow models, such as losses or logits, to train a binary classifier [2, 9, 10]. Statistic-based attacks instead compute statistical metrics using signals from both the target and shadow models [1, 11-13]. A Bayes-optimal strategy to membership inference was proposed in [1], but exact computation is intractable, necessitating approximations. State-of-the-art methods such as LiRA [11] and RMIA [13), instead, are based on a hypothesis testing formula-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

tion [14]. While these approaches achieve strong empirical performance and outperform classifier-
based attacks, their theoretical connection the Bayes-optimal membership inference remains unclear.
Most existing work MIAs assumes data points are inde- pendent and identically distributed (i.i.d.). Recently, however, MIAs have been studied in the context of graph-structured data, particularly against graph neural networks (GNNs). In this set- ting, message passing introduces structural dependencies each node or edge can influence many others others-making membership signals harder to isolate and challenging key assumptions under- lying classical attacks. MIAs on graph srrph-structure data can be grouped by the information they aim to recover: (i) node-level attacks attempt to infer whether specific node was part of the training set [15-19]: (ii) edge-level attacks target the presence of specific edges [20-24]; and (iii) graph-level attacks aim to determine whether an entire graph instance was used in the training [25-27]. At the node level, existing approaches are exclusively classifier-based Given the success of statistic- based methods on the i.i.d. data, extending such strategies to graph data may lead to stronger attacks. However, this remains an open problem.
10-1
Tix Posiine Rac
10-2
G-BASU Cours)
BASE
KMIA
10-3
LIRA
MLP 0 Hop [15. 16]
MLP 115, 16)
10
Palse Positive Rate
Figure I: ROC curves of our attack and prior MIAs on the Flickr datasct, averaged over 10 GCN target models.
Our contribution. Motivated by the need for practical, theoretically grounded privacy auditing tools. we develop novel MIAs for both i.i.d. and graph data. Specifically, we design Bayes-optimal attacks framework of [1]. yielding attacks that are both effective and tractable. The proposed attacks tend to match or outperform the -tate-of-the-art, especially on larger datasets. Our key contributions include:
building on the Bayesian
We derive the Bayes-optimal decision rule for node-level membership inference on graph data, extending the results of Sablayrolles et al. [1] beyond the i.i.d setting. This result formalizes how graph structure should be exploited in membership inference against GNNs.
Guided by this Bayes-optimal rule, we propose G-BASE, practical attack on GNNs that achieves state-of-the-art performance on graph data, significantly outperforming existing classifier-based methods.
We propose BASE, practical Baycs-optimal attack achieving sfute-of-the-at performance while being significantly more cost-efficient than prior methods such as RMIA [13] and LiRA [11].
We reveal a close connection between BASE and RMIA: the two are equivalent (for a specific value of RMIA's threshold 7) up to monotonically increasing transformation. However, BASE achieves the same performance with significantly lower computational cost, requiring much fewer model queries.
2 Related Work
MIAs for i.idd. data. Relevant works include [2],[1], [14], [11] (LiRA), and [13] (RMIA). Shokri et al. [2] introduced classifier-based black-box MIAs: the adversary trains multiple shadow models on known datasets to mimic the target model, then trains binary-classifier attack model on their outputs labeled by the ground truth training membership status. Sablayrolles et al. [1] proposed Bayes-optimal framework in which membership inference amounts computing the posterior probability that a data point is in the training set, given the trained model. Under mild assumptions, the optimal inference depends only on the loss, motivating black-box attacks where the attacker can observe only the model's output (e.g., the loss) on the target sample. Ye et al. [14] cast MIAs as a hypothesis testing game: a challenger samples a data point from either the training set or the rest of the data population (with equal probability), ), and an ad adversary, with access to the data population, must decide between two hypothesis-when
the model was trained on dataset including or excluding the-art art black-box attacks, such as LiRA [11] and RMIA [13], build on this formulation. LiRA performs a likelihood-ratio test between the two hypotheses, representing them via the distributions of losses (or logits) on the target data point. LiRA assumes the (transformed) logits exhibit Gaussian-like behavior, resulting case where the target data point is in the training set to the case where it is replaced by an auxiliary sample drawn randomly from the population. The test score is the tail probability of the resulting likelihood ratio.
the target point. State-of Wfate-of-the-are
parametric test. In RMIA, the test compares the
2

---

MIAs for graph data. Existing node-level attacks [15-19] all adopt muussifier-based approach. These attacks involve three phases: training shadow model, training Dinary-classifies attack model, and performing membership inference. The attack model takes as input features the vector derived from the shadow model's labels 118-for nodes that were included or not in the training set. Despite their promise, statistic- based methods have not yet been explored for node-level MIAs.
posterior probabilities [15-17, 19] or predicted
Preliminaries
Graph notation. For graph data, consider graph denoted by G G= X,, where V is the set of nodes, & the set of edges, X E Rnnd the node feature matrix, and Y E Raxe the one-hot encoded node-label matrix, such that each node E V has an associated feature-label pair (æ y.)) which are assumed to be sensitive data. We denote by A E R the adjacency matrix of graph G. where Aur
(u, v) E and 0 otherwise, and by N(v) = {u (u, v) E E, u * f) the set of neighbors of node v. For convenience, in the analysis sections, we will refer to graph G as = (X, Y, A), where the sets of nodes and edges are implicitly defined by X and A, respectively.
Graph neural networks (GNNs). GNNs [28-33]. learn node embeddings that capture both structural and feature information. These embeddings are then used for various downstream tasks such as node classification. GNNs operate via message passing, where nodes aggregate information from their neighbors to update their embeddings. Formally, the embedding of node v E V at level & + 1 of an L-layer GNN is computed as
h (1+1) = UPDATE (1) AGGREGGATEE
(1)
where both AGGREGATE, a permutation-invarin function, and UPDATE differentiable and h the input feature vector of node v. The computation of h()), the final embedding node v, thus depends on its L--opp neighborhood, which we denote by Ny. (v). For notational convenience, we denote the final embedding of node by 2, h(()) and refer simply as the node embedding.
For node classification, a softmax operation is typically applied to the node embeddings to produce class probabilities,
P(y.lo,X, A) R softmax(z.), = [
where fo(X, A), denotes the Se with parameters 0, and denotes the index of the nonzero element of y. The model is typically trained by minimizing the negative lig-lioelihood loss ((fo(X, A).. yy) - log P(y, X, A) (i.e., the cross-entropy loss for node classification) over the labeled nodes, i.e., minimizing
prediction vector for node v. computed by GNN
L ((0.X.Y.A)
Σ
Σ "V
log Ply, X,
(3)
4 Bayes-Optimal Node-Level MIAS Against GNNs
We extend the Bayesian membership inference strategy in [1] to GNNs. We begin by framing the MIA as indistinguishabiiit game and then proceed to derive the Bayes-optimal decision rule for membership inference. Finally, we discuss tractable approximations and sampling strategies that yield powerful and practical MIAs.
4.1 Node Membership Inference Attack Game
Following [11, 14], we formulate the MIA as a game between challenger and an adversary.
Definition I. (Membership inference game graph data)
1. The challenger samples subset of graph G. Grrinn = (Virain Errain) C. G. where Virain V and Eraain = {u, v) u, Virann (u, v) E E), and trains GNN model fo on Grrain Let my denote the membership status of node U E V,
{
1,
V V main
m.
0,
& V tnain
(4)
3

---

2. The challenger flips fair coin to generate a bit b. If 0, it samples a target node from g Jvain Otherwise, it samples target node v from Gmain-
3. The challenger gives the adversary the full graph G (X,Y, A),, the target node v, and black-box box access to the trained model fo.
4. The adversary may also have additional side information H (e.g., knowledge about the training algorithm or model architecture). Using this information, the adversary performs a MIA m. t MIA (fe. U. G. H), where my is an estimate of the membership status of node v. my.
5. The attuck is successfill on target node if fīt. 1hbe-
Threat model. We assume that the target graph Guain C G is sampled from a larger, fixed graph g that is accessible to the adversary. This setup offers flexible and practical way to model the data distribution. Notably, this corresponds to the train on subgraph, test on full setting introduced in [15]. When G is large relative to Guain, this setup corresponds the data population pool assumption widely adopted in membership inference [14, 13, 11]. While giving the adversary access to 9 simplifies the analysis of the Bayes-optimal attack, it also results in stronger adversary. Nevertheless, this worst case assumption is suitable for privacy auditing, where conservative evaluations are preferred. We adopt& a black-box setting, where the adversary has unlimited query access the target model and can generate soft predictions for any valid input graph. Knowledge of the model's architecture, training algorithm, and objective function is encompassed in H. In contrast, white-box setting would grant the adversary direct access to model parameters or activations.
GNN training can be categorized into transductive and inductive. In the transductive setting, only part of the graph is labeled and used for loss computation. However, message- message-passing is performed over all nodes, producing approach is typically to predict the labels of the unlabeled nodes. The inductive setting, on the other hand, corresponds to fully supervised learning. In this setting, message- passgggg-psinggggg is only performed between labeled nodes. The goal is then to generalize to unseen nodes. As noted in [16), the inductive setting is the most relevant, it provides a clear distinction between member and non-member nodes. In contrast, the transductive setting- where the model is primarily used by the data holder to predict labels for unlabeled nodes and remains under their control-does not raise significant privacy concerns. We therefore focus our analysis and experiments on the inductive setting.
embedding for each node. The goal of this supervise learning
4.2 The Bayes-Optimal Decision Rule
Assume that the target node whose membership status we aim to infer is node E I, and let N be its L-hop neighborhood. Also, let M = {m. u E V/ denote the membership indicator variables of all n nodes in the graph G. and Â = MM (m..) represent the membership statuses of all nodes except the target node v. Given the attack game and threat model defined in Section 4.1, a Bayesian adversary seeks to compute the posterior probability that the target node is in the training set, i.e.,
P(m, = 1), The following theorem provides closed-form expression for this posterior.
Theorem 1. Given graph G = (X,Y, A) and an I.-layer GNN model 0 trained on induced subgraph of G to minimize the objective in (3), the posterior probability P(m, = 1)0,9) is given by
of
P(m, 1 9) = -EM-P(M(OO))
log A0, X,
- log /
( p(ppmm =0. log A
1
(5)
where
M, A + (f)
(6)
with
ALv
Σ (e(((Jo(X,AMaaan) E(fo(X, Arilns
(7)
oENL(
and
A(O M, M,M A) p(0mm, = 1,,
(8)
p(0 = X,M,X,A)

---

the latter representing the likelihood ratio prior to observing the labels. In (5), X Pim, denotes the prior probability that node is a member of the training set, before observing the model, and a is the sigmoid function. Also, the n. x matrices A and A ii in (6) and (7) are defined as
(AM)uw = ={ Aun Mh -y 1, and (AM)uw = (AM)uw
U, + U, otherwise
0,
otherwise
0,
for u, E V.
Proof. See Appendix B.I.
In (5), Sc(fo M, 9) represents the loss-based signal for the target node e, while the first loga- rithmic term corresponds to the expected signal over the distribution of the models induced by the membership configuration M. plppp((r) m., O.M, g). The term ALN, (e) captures how the inclusion or exclusion of the target node influences the loss values of its neighbors (since an I-llaer GNN aggregates information from nodes within the L-hop neighborhood, the optimal attack must consider this local graph structure around the target node, see Figure 2).
The presence of the term (7) the graph data setting, in contrast to the i.i.d. case (see [1, Thm. 2] and Corollary in Section 5.1), highlights a key distinction: dependencies between data points play central role.
To make predictions, we set a decision threshold 7 such that target node v is inferred to be part of the training set if P(m,, 1|0, 9) т. For auditing purposes, it is important evaluate performance across the full range of false positive rates, particularly at low false positive rates, and we compute the receiver operating characteristic (ROC) curve by sweeping a detailed discussion on how an adversary can select the decision threshold r by attacking simulated target models.
r E [0, 1]. Appendix C provides
4.3 G-BASE: Practical Bayes- MIA against GNNs
The Bayes- Bayes-optimal membership inference score function in Theorem is computationally intractable and thus necessitates approximations. In this section, introduce practical and effective approxi- mation to the Bayes-optimal decision rule, resulting in a powerful MIA.
First, the Bayesian membership inference involves computing a fogg-likelihooe ratio of the membership indicator (see (12)). When attempting to approximate (5), we need to pick a prior (8) on the likelihood ratio, before observing the labels. A natural and simplifying approximation is to set A,,,, X, A) 1. Intuitively, distinguishing the distribution of models trained on node from the distribution of models not trained on v is more difficult when the labels are unobserved, and log A(0, M, Xx, A) small in comparison to the posterior likelihood ratio that Consequently, we would expect it to be small in comparison to the loss signal. The outcome that the prior LLR term vanishes from (5).
estimating.
The rest of the intractability stems from the two nested expectations in Equation (5): one over the membership statuses of all non-target samples, M, and the other over the model distribution, p(olm, = 0, M, The expectation over M requires sampling from the conditional distribution P(M 9), which is infeasible (it is essentially the joint membership inference problem over all non-target nodes). To address this, we propose three approximate sampling strategies to generate samples from P(M 9): i) model-independer sampling, which assumes independence from the target model, i.e., P(M|0, G) se P(M|G); ii) 0-hop MIA sampling, which leverages a MIA attack for the i.i.d. setting to obtain per-node membership probabilities; and iii) Markov chain Monte Carlo sampling, which accounts explicitly for the dependence on the target model 0. These strategies discussed in greater detail in Appendix B.2. Given any of these sampling strategies, we generate M samples M1,..,,Me and approximate the outer expectation E. [).-((M))))) [-] in (5) with the sample average.
The remaining expectation over the model distribution p(0mm, M, g) (the integral term in (5)) is also intractable. We approximate it via Monte Carlo sampling using a set of shadow models trained on subgraphs of G, interpreting p(0|m, O,M, the distribution of models trained on the subgraph defined by M with the target node excluded. However, directly sampling from this
5

---

0 Tisouae
T(b)
ox T(Qn)
for 10.0.... ou exliune
Sel v. M. 01 u. A
0..9.
Pim, 110.9)
Suaki
9x
somple
eample
Figure 2: Visualization of the Bayes-optimal attack. From left to right: the challenger trains the target model @ on Graain and provides trained model, target e, the underlying graph G. and (optionally) auxiliary information detailing the training procedure. The adversary then samples K graphs and trains a corresponding set of shadow models { 1K These sampled graphs may or may not contain the target node Finally, the adversary estimates the membership of using the Bayes-optimal decision rule in approximatedd via the Monte Carlo method in (9).
(=
distribution would require training a separate set of shadow models for each pair (u, M), which computationally infeasible. For N target nodes, M samples of M, and K shadow models per configuration, this would amount to training N M x K models. To reduce the number of shadow models, approximate p( my = O, M, G) by distribution p(Φlg) only dependent the data population. This simplification allows us to reuse the same set of shadow models across all targets and sampled membership configurations M. More precisely, the adversary samples subgraphs 91..... 9K from & and use them to train shadow models. Ideally, the adversary should sample subgraphs and train shadow models using similar procedure as the challenger. However, this distribution is constrained by the adversary's side information.
The integral in (5) can then be approximated as
K
log / -..lla...MM p(6/m, = 0, M, v log
1
Σ
+ T(9e),
K
k=1
where T is the training algorithm.
Incorporating both approximations into (5), we arrive the following attack:
Definition 2. (G-BASE attack) For a given threshold т, and set of shadow models {Øx K k= target sample v is inferred to be part of the training set if P(m, 10,9) > T, where
P(m, = 1|0,9)
Σo U,,
Σ e
Se (foz (fog
A +log
1 1-
We refer to this attack as the graph Bayes-approximate membership status estimation (G-BASE) attack. An illustration of the G-BASE attack shown in Figure 2. The distinction between online and offline variants is discussed in Appendix F.
Bayes-Optimal MIAS for i.i.d. Data
In this section, we consider MIAs the i.i.d. setting. We first show that the formulation (5)-(8) recovers the result for the i.i.d. case presented in [1] (Theorem 2) special case. We then introduce a practical approximation of the Bayes-optimal decision rule that yields powerful attack. The formal definition of the membership inference game in the i.i.d. setting is provided in Appendix D.
5.1 The Bayes-Optimal Decision Rule
The result below follows as corollary of Theorem 1.

---

Corollary I. Let D = {(re, yo)li- be a set of i..dd data samples and denote 1x = llog --x. ii.d. data, assuming the prior p(0) M, M, (0=))=1) is independent of myy (5) reduces to
- For
P(m. = 1))
([[(oo(x)))))) (
llog / (o- / = M, D)d + 1
-EM-P(MODD)
i.e. the result in (1, Thm. 2] with the temperature parameter absorbed into the loss function. Proof. See Appendix E.1.
5.2 BASE: Practical Bayes-Optimal MIA for i..dd Data
As for the graph case, the Bayes-optimal decision rule stated in Theorem I and in [1, Thm. 2] (for i.i.d. data) is computationally intractable. For the i.i.d. case, [1] proposed several approximations; however, the resulting attacks underperform compared to those in [11, 13]. In this section, we introduce an alternative approximation the Bayes-optimal decision rule for the i.i.d. setting that yields a practical and powerful attack.
Due to space constraints, we present the formal definition of the proposed attack below and refer the reader to Appendix E.2 for further details.
Definition 3. (BASE attack) For a given threshold т, and a set of shadow models { )= target sample v is inferred to be part of the training set if P(m. 1 ) > T, where
P(m. 1|0, =o
-E(fo(()))))) (-((=)))((())))))
log
U1o UUo (ow))
A 2>)) log 1 1-2
x (10)
We refer to this attack as the Bayes-appe membership status estimation (BASE) attack.
As shown in Section 6 and Appendix H, despite relying coarse approximation of the Bayes- optimal decision rule in (5), the BASE attack matches or exceeds the performance of state-of-the-art attacks [11, 13].
Connection to RMIA. We formally establish a connection between the BASE attack and the RMIA attack proposed in [13]. To this end, we introduce notion of equivalence for score-based MIAs (i.e. any MIA that produce soft membership scores that are thresholded into hard membership predictions).
Definition 4. (MIA equivalence) Two score-based MIAs are said to be equivalent if. for any decision threshold for one attack, there exists decision threshold for the other atlack that yields identical hard predictions.
In partieular, equivalent attacks produce identical ROC curves.
The following theorem shows that the BASE attack closely related to the RMIA attack [13).
The BASE attack equivalent (in the sense of Definition to RMIA when 7 More precisely, the membership prediction scores produced by RMIA with y = is related to those of BASE via a monotone increasing function.
Theorem 2.
Proof. See Appendix E.3.
This result provides a theoretical justification for viewing RMIA Bayes-optimal attack, up the approximation on the shadow model distribution.
Despite the equivalence between BASE and RMIA (in the sense of Definition 4), BASE offers signifi- cantly improved efficiency. RMIA, the target model and shadow models need be queried for each target sample and a sufficiently large number of population samples. In a practical implementation, is typically used place of the full population D for efficiency, which
a sampled subset Z can degrade performance [13]. BASE, on the other hand, only needs to query the models using the target samples to match the performance of RMIA with Z DD which is also the best performing configuration of RMIA, see [13, Table 4].
7

---

6 Experiments
We evaluate the attack performance of BASE and G-BASE across a range of datasets and model architectures. This section focuses attacks against GNNs; results on i.i.d. data (CIFAR-10 10 and CIFAR-100) are presented in Appendix H.4. Open source code is available to reproduce our results."
Setup. Experiments are conducted on 6 graph datasets; Cora, Citeseer, Pubmed, Flickr, Amazon- Photo, and Github. Cora, Citeseer and Pubmed are citation networks previously used in node-level MIA work [15-17]. For both the target and shadow models, we consider 2-layer GNN architectures:
GCN [30], GRAPHSAGE with max aggregation [31], and GAT [32]. The models are trained inductively on randomly-induce, subgraphs containing 50% of the nodes, and 50% of the dataset used as target samples, evenly split between members and non-members. Attack performance is measured in terms of the area under the receiver operating characteristic curve (AUC), and true positive rate (TPR) at I % and 0.1 % false positive rate (FPR). The AUC captures the average attack performance across all FPRs, while the attack performance at low FPR is most relevant in practice, as high TPR at a low FPR is essential for confident and reliable membership inference [11]. Additional details of the training procedure and hyperparameter selection are provided in Appendix A.
Baseline attacks. We compare the performance of BASE and G-BASE against LiRA [11] and RMIA [13], the current of-te-of-the-- art MIAs for i...d data. We also compare against node-level MLP- classifier attacks against GNNs from prior work [15-17]. To strengthen these baselines, we enhance the MLP-classifier attacks by using multiple shadow models to generate attack features, following the shadow training framework of [2]. The attacks are implemented based on the descriptions in their respective papers, incorporating information from the authors' code when available.
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. Since MLP-classifier attacks use shadow models solely to generate training data for the MLP attack model, rather than to estimate reference model distributions, they are insensitive to whether the target nodes are included in any of the shadow models. In our setup, the shadow models are trained partially on target samples; therefore. the MIP-classsfier attacks are formally considered online attacks.
Attacks against GNNs. Figure/ 1 shows ROC curves for G-BASE (using model-independent sampling) and several baselines on Flickr, using a 2-layer GCN architecture and 8 shadow models in online mode. G-BASE outperforms other baselines across the full range of FPRs on a majority of the benchmarks, especially on the larger datasets. Table 1 shows the performance of BASE and G-BASE and the baseline MIAs across multiple datasets and GNN target models. All attacks use the same set of K shadow models for a fair comparison. The number of sampled graphs M in G-BASE is set to 8. For K (online) and K 4 (offline), we evaluate G-BASE for model-indes indee--iddeeeneent sampling (MI, O-hop MIA sampling (MIA). and Gibbs sampling (see Section 4.3), using BASE as the O-hop MIA. In the large K experiments, we use 0-hop MIA sampling all cases except for Flicker where we use sampling. Further results on the sampling strategy are presented and analyzed in Appendix H.2. The clasccaassfier attack is evaluated in two variants: using O-hop query outputs as attack features, and using concatenated O-hop and 2-hop query outputs to form attack features (0+2-hop). The hyperparameters for offline BASE and offline RMIA are selected using Bayesian optimization [34], with cross- colssvvlldation over shadow models acting as simulated target models.
We make the following key observations: The MLP-classifier attacks are not competitive with our attacks BASE and G-BASE, or LiRA and RMIA across all datasets and target models and perform as random guessing on the larger, more challenging datasets. For K = and 8 shadow models, BASE and G-BASE consistently outperform all baselines on the larger and more challenging datasets Pubmed, Flickr, Amazon-Phote Photo, and Github. On these datasets, G-BASE effectively leverages local neighborhood information of the target node to enhance the attack performance. On the smaller datasets Cora and Citeseer (== 3000 nodes out of which half used to train the models), LiRA achieves comparatively good performance in terms of AUC. However, BASE, and G-BASE achieve superior performance in the more relevant low-FPR regime. Similarly, on Amazon- ( 7500 nodes), which is still smaller than the remaining datasets whose sizes range from approximately 20K to 90K nodes, the performance of LiRA is comparable to that of BASE, G-BASE, and RMIA. As the datasct size increases, however, LiRA's performance is overtaken by the other methods, indicating
cnttpa://githin http://gttbccoommaaereeee/ www./arruuaLassllla......aacaaaa 2On Flickr and Github, only 20% used target samples when using 128 or 64 shadow models.
auN
8

---

Tahle I: Comparison of different attacks across datasets and model architectures. Performance is measured in terms of AUC and TPR at 1% and 0.1% FPR. The result reported as sample mean 1 standard deviation over random target models and samples of target nodes. The parameter K denotes the number of shadow models. The attacks are evaluated in online mode for K = 8 and K = 128 and otherwise offiine mode. Our attacks BASE and G-BASE achieves top performance in the majority of cases, sometimes with significant margin.
CORA (GCN)
CITESIEN (GAT)
PUBMED (GRAPSSAGE)
R
ABC
TPR
AUC (5)
TPR
(U)
TPR & (1)
0.1%
1:6
0.1%
15:
0.1%
MLP (B-HOP)
0 1.74
3.53 + 1.52
0.56 0..51
2.315
5.50 1.34
0.97 + 0.50
00.29 +0.56
1.10 = 0.22
0.15 0.07
MLP (0+2-180P)
1.145:277
3.56
1.65
0.33 0.82
75.89
0: 2.44
1.71 =: 1.50
2.12 d: 1.40
01:20 0.56
1.16
= 0.25
0.12
LIRA
82 8: 1.30
8.01
4.40
L 2: 1.55
66.89
0.63
13.38
8: 0.00
1.66 4: 1.75
02.77 0.50
1:17 2 0.14
0.12
8 BASR
RMIA
N2 05
N2- 85
1:45
1:45
17-47
17:48-9:133
+ 1.73
1.77
1.81 9 2:25
1.51 + 2:25
84:84
61.84
1:13
1:18
22:20
22:33
3.00
3.64
5.50 +1 4.45
5.51 + 4.43
57
57:41 + 0.50
8 0.56
3.07
3.07
9 0.51
+ 0.55
0.55-t.0.10
0.55++0.10
G-BASE (MI)
17.15
1.51
7.19
0.05
+ 0.92
81.75
0.67
15.62
2250
1.31 + 0.30
02.92 0.00
6.38 + 0.39
1.20++0.35
G-BASE (MIA)
TT-12 4: 1.40
15.36
+: 3.04
5.05 + 1.00
K3.31
0.78
21
= 4.27
0.92 6.61
02.96 0.774
0.56 + 1.08
1.16++0.19
G-BASE (GIBDS)
76.85 2: 1.61
10:02
4: 2.51
4.40 0:::::2::
84.39 4: 0.67
21.38
6: 4.16
5.26 4: 5.50
64. 00 0.00
0.28 + 0.66
1.86 + 3.59
LIRA
92:37 1.71
12.38 0.000
2.10
81.68
1.06
18.39 2.02
+.9.5
65-00 0.00
1.57
0134
RMIA
50.57 +: 1.62
17.67 1.000
7.87
3.66
83.63 1:29
26
3.39
12:20
06. 00006
2.05
0.67 +
BASE
KL,47
17.87
2.43
7:13
64.83 1:31
25.28
8.23
10.37
3.00
06.82
0.00
8.02
0.62 +
G-BASE (MD)
74.25 1.79
9.41 2.93
0.03
76.25 1:24
13:02
2.27
3.24
61 0.00
6.22
G-BASE (MIA)
T0,02
10.38 8: 2.97
3.53 2.05
T6.63 1.33
2.04
2,30
02.06 0.64
5.03
2.27
G-RASF
1.19
1.57
LIRA
00.0 1:007
34 64.62222 5.663
19.61
4.99
D1.
1.774
8.11
20.77 6.14
66.40 0.44
3.07
128
BASE
RMLA
51,25 11.22
S1.25
20.10
20.10
7,96
4.31 7,33 48
N0.09 1.25
1.25
25.27
25.27
3.332
4.322
4.36
67.58 0.50
0,50
3.23
0.23
0.34
G-BASE
77.21 1.34
17. 17.40:2
84.43 0.55
0.35
LIRA
$0.39 1:17
33% + 5.45
19.55
5.12
88.
0:99
45.15 + 2.05
26.70 + 5.61
56.31 + 0.77
2.12 0-11
0.12+ 0.31
64
RMLA
BASE
S1.28 6: 1.18
52.49 6: 1.18
21.85
20.00 6: 2.58
3. 3.000
11:00 5: 4.02
11.11 5 4.05
84.54 1: 1,30
85.08 à: 1.15
12.35
31.22
d: 2.07
3.10
15.82
16,90
2 3.18
a 4.90
57.58
67.44
a 0.00
à 0.52
3.46
3.55
a 0.54
a 0.49
0.91
0.85 a: 0.22
1 0.37
G-BASE
74.88 8 1.13
13002 8: 2.58
4.31 8 2:03
79:25 a 1.01
21.12
d: L/67
8.03 8 4.41
63 a 0.53
0:00
1: 0.36
2.09 a 0.45
(OCN)
AMARON- PHOTO (GAT)
(GRAPHSAGE)
K
ATTACK
(I))
OP (8)
AUC (5))
TPR d (9)
AUC (%)
TPR
0.1%
1%
0.11%
1%
0.1%
MLP HOPH
50,20 0:24
1.02 0.11
0.12 0.03
52.11 1.08
1,56 4
0.31
00.09 0.338
0.91 00.35
0.11 0.07
MLP (0+2-1108)
50:35
1.06 0.08
02.30
0.16
0.94
0.00++000
LIRA
1.04 0.12
06.82
0.46
2.23 +
0.21
61.27 0.28
1.06 0.08
0.11 0:01
RMIA
16-23
0:21
0:27
06.35
0.333
2.39 0.666
0.36
0.222
61.18
2.06=0.31
0.04 4 0.09
56.25
1.92
56.35 0.03
0.20-+00.6
0.23
2.0-0331
0.00
G-BASE
1.00
2.82
56
3.20++0.88
0.38
2.93-0.41
57.48
0.19
66.77 0.85
3.90
0.82-0.4
5.00
0.56 0.18
G-BASE (GIBBS)
$7.88
2:33 0:27
0.37
56.53 0.61
4.44 0.80
0.49
57.47
1.43
0.54
0.35
LIRA
55.71
1.58 0.18
0.17
06.71 1.24
3:17
0.551
0.27
63.10 0.05
0.18
0.00
0.20
0:32
56.21
1.07
3.55
0.0.81
0.50
0.22
0.36
0.22
0.29
56.61
1.05
3.58
0.68
0.36
G-BASE (MD
04 1.01
2.88
0.50 =: 0,055
57.81
0.71
1.778
0.44
67.79
1.22
0.56
0.58
(MLA)
57.71
2.48 0:21
0.40
S7.74
0.95
4.82
0.37
57.72
0.47
0.60
G-BAS (GIB8S)
63
0.32
1.
0.54
4.61
0.52
0.64
0.73
LIRA
0:20
0.21
58.
0.91
6 0.77
3.52 0.47
2.01
0.28
128
+
2:25 0.28
0:38
0.36 1.
0.96
0.17
36.52
56.52
0.77
0.76
2.67
2.07 + 0.83
0.33
0.33
51.00
0:80
2:18 0111
0.38
0.38
G-BASE
14.94:000 0.51
2:87 0.88
0.44 0.13
54,88 0.35
0.82 a:
=000::00 0.51
67.02
1.38
2.96 0.50
0.61 +
LIRA
16.13
0.27
0.25
67 67.82
5 = 11.02
6:65 0153
51077
0.17
RMLA
16.12 +:
2:28 0:22
0.43
0.14
56.46
1.113
3.90 +: 0.77
0.43
51.76
0.43
0.49
BASE
56.12
2.28 0:24
0.43
+: 0.14
56.95
1.07
4.13
0.68
2.50
0.50
G-BASE
60 0.71
3.14 0.17
0.52
0.00
56.74 0.72
4.92 + 0.67
0.58
67.99-
1.67
0.06
0.77 + 0.24
that the proposed approaches scale more effectively larger graphs. As predicted by Theorem 2, in the online setting, BASE and RMIA yield nearly identical results. Minor differences stem from RMIA using only half of the nodes in the Z set: including all nodes in the Z set, makes the attacks equivalent, as established in Theorem 2. However, as noted in 5.2. BASE requires significantly less computation in terms of model queries, compared to RMIA. In fact, BASE requires only a single query of the target and shadow models, whereas RMIA also need to query the models over the Z set. In the case of a large number of shadow models, the performance of LiRA increases significantly. On some datasets, most notably Cora and Citeseer, LiRA performs very well. However, on larger datasets, e.g. Flickr and Pubmed, the performance gain of LiRA more modest. Our attacks BASE and G-BASE are more principled and robust against datasets and models, and achieve top performance in many settings and also for a large number of shadow models K. However, we consider attacks that rely on a large number of shadow model to be of less practical relevance, since training large number of shadow models is often infeasible for large models and large real-world datasets.
Comparing online and offline attacks. Since the same target models and target nodes are used to evaluate all attacks for given dataset and GNN architecture in Table 1, the online and offline attacks are directly comparable. Despite using only half the number of shadow models, there are several cases where offline BASE and G-BASE outperforming its online counterpart. This trend is most clear when comparing the large K attacks, presumably because of the diminishing returns of increasing the number of shadow models from 64 to 128. In light of Theorem 1, this is indeed what we would expect since the target node is explicitly absent from the distribution of reference models. Furthermore, the added hyperparameter the offline versions of RMIA and BASE is likely another contributing factor to this phenomenon.
comparable
9

---

Robustness to mismatched adversary assumptions. We evaluate and compare the attacks in more challenging setting where the adversary lacks precise knowledge of the challenger's training procedure and model architecture. Specifically, the challenger trains a 2-layer GCN on 35% of Cora, while the adversary trains 2-layer GAT shadow models on 50% of the nodes, following the shadow model training procedure outlined in Appendix A. Furthermore, the challenger trains the shadow model using a SGD optimizer with momentum, while the adversary uses an Adam optimizer.
Figure 3 presents the results of our attacks and baseline attacks (see Appendix H.I for more re- sults). In this setting, all attacks show degraded performance, with AUC scores dropping by around 10 percentage points or more across all attacks, compared to the performance against GCN target model on Cora (see Table 1 and Table 8). LiRA suffers the most, losing around 15 AUC percentage points and performing worse than MLP-classifie attacks in the low FPR regime. In contrast, our attacks and RMIA are more robust to mismatches in model and training procedures introduced by the adversary, achieving the highest TPR at low FPRs.
1PP
Computational aspects. An advantage of BASE over prior state-of-the-art attacks LiRA and RMIA is its improved effi- ciency. In Section 5.2, in light of the equivalence between BASE and RMIA, we discussed how BASE requires much fewer model queries compared to RMIA. In addition to ad- vantages such as being more stealthy and robust to imposed limits on allowed queries, it also improves the computational efficiency of the inference phase of the attack.
Thee Positive Rate
10
GBAE
GRASE joen
BASE-ffae (ven)
BARI isuno
10-2
RStikddee IIN
KMBATISI
UROatiee III)
MERDO RkyllS
Compared to LiRA, there is no advantage in terms of model queries since LiRA also only requires querying the models with the target samples. However, LiRA typically requires a larger number of shadow models to reach its full potential as our results indicate (see Table 1 and Table 12), and which is also found in [13]. Training the shadow models is the most costly part, especially for larger models and datasets. By achieving good performance at lower number of shadow models, BASE has a computational performance advantage over LiRA.
10
10-3
10-2
10-1
100
Falss Positive Rate
Figure 3: ROC of mismatched attack av- eraged over 10 independent target models. Shadow models utilize GAT architecture and different training procedure. 8 shadow models for online; 4 for offiine.
As for G-BASE, although it is a tractable approximation of the Bayes-optimal membership inference on graph data, it is less efficient than the O-hop attacks-the MIAs designed for i.i.d. data and adapted to graph data by ignoring the edges. This is not surprising since G-BASE uses a more complex loss signal and has estimate an expectation over target node neighborhoods. However, it is the inability to parallelize the membership inference over multiple target nodes that is the true bottleneck of
G-BASE in our experimental settings. Since the loss signal of G-BASE includes term that depends on the difference in loss values over a neighborhood when the target node is included and when it not (see Figure 2), is not trivial to parallelize the computation of the loss signals over several target nodes. The 0-hop MIAs, on the other hand, can compute their loss signals over large batch of target nodes in parallel. Thus, the time complexity of inference with G-BASE has an additional factor of N x M compared to BASE, where N is the number of target nodes and M is the number of sampled graphs. We found that G-BASE performs well with only M 8 (see Appendix H.2 for results regarding this), but the number of target nodes is typically on the order of thousands, and consequently this factor is the dominating factor. Nevertheless, G-BASE remains computationally tractable, and we believe it is ultimately more important to accurately assess data leakage than to be efficient, in agreement with [11]. However, further improvements in the efficiency and parallelization of the attack are interesting and important directions of future research. In Appendix H.3, quantify the efficiency of our attacks, LiRA, and RMIA in terms of wall-clock time.
Conclusions. We proposed BASE and G-BASE, practical and theoretically- grroundde MIAs for i.i.d. and graph data. By deriving the Bayes-optimal inference rule for nevel attacks on GNNs, we addressed key challenges posed by structural dependencies in graphs. Our attacks match or surpass existing state-of-the-a methods (LiRA and RMIA) while, in the case of BASE, requiring significantly lower computational overhead. Our results bridge the gap between theoretical optimality and practical implementation of MIAs, offering an efficient framework for privacy auditing across both classical and graph- based learning settings.
10

---

7 Acknowledgments and Disclosure of Funding
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, by the Swedish Research Council (VR) under grants 2020-03687 and 2023-05065, and by Vinnova under grant 2023-03000.
The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725.
References
[1] Alexandre Sablayrolles, Matthijs Douze, Yann Ollivier, Cordelia Schmid, and Hervé Jégou. White-box vs black-box: Bayes optimal strategies for membership inference. In ICMI., 2019.
[2] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In IEEE Symposium on Security and Privacy (SP), 2017.
[3] Jiayuan Ye. Anastasia Borovykh, Soufiane Hayou, and Reza Shokri. Leave-one-out distin- guishability in machine learning. In ICLR, 2024.
[4] Awni Hannun, Chuan Guo, and Laurens van der Maaten. Measuring data leakage in machine- learning models with fisher information. In Conference on Uncertainty in Artificial Intelligence (UAT), 2021.
[5] Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Úlfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In USENIX Security, August 2021.
[6] European Data Protection Board (EDPB). Edpb opinion 2024/28 on ai models. Technical report, European Data Protection Board, December 2024.
[7] Jie Zhang, Debeshee Das, Gautam Kamath, and Florian Tramèr. Position: Membership inference attacks cannot prove that model was trained on your data. In IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), 2025.
[8] Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlin. Adver- sary instantiation: Lower bounds for differentially private machine learning. IEEE Symposium on security and privacy (SP), 2021.
[9] Martin Bertran, Shuai Tang, Aaron Roth, Michael Kearns, Jamie H Morgenstern, and Steven Wu, Scalable membership inference attacks via quantile regression. In NewrIPS, 2023.
[10] Hao Li, Zheng Li, Siyuan Wu, Chengrui Hu, Yutong Ye, Min Zhang, Dengguo Feng, and Yang Zhang. SeqMIA: Sequential-metric based membership inference attack. In ACM CCS, 2024.
[11] Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In IEEE Symposium on Security and Privacy (SP), 2022.
[12] Yiyong Liu, Zhengyu Zhao, Michael Backes, and Yang Zhang. Memhership inference attacks by exploiting loss trajectory. In ACM CCS, 2022.
[13] Sajjad Zarifzadeh, Philippe Liu, and Reza Shokri. Low-cost high-power membership inference attacks. In ICML, 2024.
[14] Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, Vincent Bindschacdler, and Reza Shokri. Enhanced membership inference attacks against machine learning models. In ACM CCS, 2022.
[15] Iyiola E Olatunji, Wolfgang Nejdl, and Megha Khosla. Membership inference attack on graph neural networks. In IEEE TPS- 2021.

---

[16] Xinlei He, Rui Wen, Yixin Wu, Michael Backes, Yun Shen, and Yang Zhang, Node-level membership inference attacks against graph neural networks. arXiv:2102.05429 [cs. CR), 2021.
[17] Vasisht Duddu, Antoine Boutet, and Virat Shejwalkar. Quantifying privacy leakage in graph embedding. In International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (MobiQuitous), 2020.
[18] Mauro Conti, Jiaxin Li, Stjepan Picek, and Jing Xu. Label-only membership inference attack against node-level graph neural networks. In AlSec, 2022.
[19] Abdellah Jnaini, Afafe Bettar, and Mohammed Amine Koulali. How powerful are membership inference attacks on graph neural networks? In SSDBM, 2022.
[20] Fan Wu, Yunhui Long, Ce Zhang, and Bo Li. Linkteller: Recovering private edges from graph neural networks via influence analysis. In IEEE SP, 2022.
[21] Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. Stealing links from graph neural networks. In USENIX Security, 2020.
[22] Xiuling Wang and Wendy Hui Wang. Link membership inference attacks against unsupervised graph representation learning. In ACSAC, 2023.
[23] Ruyi Ding, Shijin Duan, Xiaolin Xu, and Yunsi Fei. Vertexserum: Poisoning graph neural networks for link inference. In ICCV, 2023.
[24] Kailai Li, Jiawei Sun, Ruoxin Chen, Wei Ding, Kexue Yu, Jie Li, and Chentao Wu. Towards practical edge inference attacks against graph neural networks. In ICASSP, 2023.
[25] Bang Wu, Xiangwen Yang. Shirui Pan, and Xingliang Yuan. Adapting membership inference attacks to gnn for graph classification: Approaches and implications. In ICDM, 2021.
[26] Junze Yang, Hongwei Li, Wenshu Fan, Xilin Zhang, and Meng Hao. Membership inference attacks against the graph classification. In GLOBECOM, 2023.
[27] Fabian P. Krüger, Johan Östman, Lewis Mervin, Igor V. Tetko, and Ola Engkvist. Publishing neural networks in drug discovery might compromise training data privacy. J. Cheminf.. 2025.
[28] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
[29] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurIPS, 2016.
[30] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[31] William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning large graphs. In NeurIPS, 2017.
[32] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[33] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[34] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
[35] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[36] Daphne Koller and Nir Friedman. Probabilistic Graphical Models; Principles and Techniques. MIT Press, 2009.
12

---

[37] Lauren Watson, Chuan Guo, Graham Cormode, and Alex Sablayrolles. On the importance of difficulty calibration in membership inference attacks. In ICLR, 2022.
[38] Sergey Zagoruyko and Nikos Komodakis. drXiv:160..07146, 2017.
Wide residual networks. arXiv prepring
13

---

A Experimental Setup
Target Model Training. We consider target models trained in a supervised manner for node classification tasks, using the commonly adopted cross-entropy loss the objective function. We evaluate three target model architectures: graph convolutional networks (GCNs) [30], GraphSAGE [31] with max aggregation, and graph attention networks (GATs) [32] using 4 attention heads in the first layer and 2 in the second. Optimization is performed using Adam [35]. For each dataset and model, hyperparameters are selected via grid search, including the learning rate, weight decay, number of training epochs, dropout rate, and dimension of the first GNN layer." In particular, we search over {0.01, 0.001} for the learning rate, {0.0001, 0.000013 for the weight decay, and {0.0, 0.25, 0.5} for the dropout rate. For the hidden dimension of the first layer, we search in (32, 64, 128, 256, 512), with 32 or 512 excluded depending on the dataset. The initial search space for the number of epochs is typically {20, 50, 100, 200, 400, 800, 1600), and is sometimes later refined. Target models with very small generalization gaps are often difficult to attack, making harder to discern differences in MIA performance. To avoid this issue, we restrict the grid search to configurations that yield an average generalization gap of at least 8%. This represents a realistic generalization gap, sufficient to enable meaningful attacks without excessive overfitting that would distort expected attack performance. We emphasize that our goal is not to produce the best performing target model, but rather to obtain well-performing target models with representative generalization gap.
The dataset- model combinations evaluated in Table correspond to the best-performing model architecture selected for each dataset. The corresponding train and test accuracies of the target models are reported in Table 2.
Table 2: Train and test accuracy of the target model on the different datasets and architectures used in Tuble 1. The accuracies are reported as mean I standard deviation, over the different target models used in all except the mismatched adversary expermmnts.
Dataset (model)
Train accuracy (%)
Test accuracy (%)
Cora (GCN)
96.07 + 0.37
80.67 + 1.10
Citeseer (GAT)
92.36 = 0.43
73.80 = 0.97
Pubmed (GraphSAGE)
96.30 0.26
87.14 1
Flickr (GCN)
57.48 = 1.05
47.08 0.61
Amazon-phie photo (GAT)
99.77 0.06
0.77
Github (GraphSAGE)
93.68 + 1.88
84.37 0.91
Shadow model training. Shadow models are trained using the same hyperparameter settings as the target model, implicitly assuming adversarial side-knowledge. This setting is particularly relevant for MIA auditing, as it yields an upper bound on the attack performance. To facilitate efficient MIA auditing in the online setting (see Appendix F for a discussion of online vs. offline settings), we adopt the shadow model training procedure proposed in [11] and also used in [13]. Specifically, cach shadow model is trained on half of the data population (c.g.. half the nodes in graph dataset), such that each data sample is included in the training set of half of the models. Pseudo-code for our precise shadow model training procedure is provided in Algorithm 1. For graph data, the data population is graph dataset, and sampling data points corresponds to sampling nodes, retaining the edges between sampled nodes. This procedure guarantees a balanced set of in-models (models trained with the target data point) and out-models (models trained without it) for each data point. In the offline setting, for each target sample, the in-models for that sample are filtered out, so that only out-models are used in the attack. This filtering approach eliminates the need for separate, disjoint dataset to train shadow models, an important advantage in graph-data settings, since splitting graph in disjoint parts reduces the number of edges, leading to sparse graphs when the full graph has low average degree. The downside of the filtering approach is that only half of the shadow models are used for attacking any given target sample.
Thee second layer always produces embeddings with dimensionality equal to the number of classes.
14

---

Algorithm Shadow Model Training Procedure.
1: Input: Data population 9, training algorithm T, and even number of shadow models 2NV.
2: & <-9 0
3: for k = to N do
4:
G1 Uniform (). G4 1/
5:
o f2:26 g, $ Gk}
6:
Φ T(gx)
7:
Φ - T(g))
8:
& + (pk: $1
9: end for
return
B Bayes-Optimal Node-Level MIAs Against GNNs
B.1 Proof of Theorem 1
The proof follows along the lines of the proof' [1. Thms. 1 and 2] for the case of i.d. data. We begin by applying the law of total expectation express P(m, 0 9) expectation over the unknown membership statuses of the remaining nodes,
Pmm. 1)0,9) Lii- = (,,,0,9))
(11)
Unlike [1], where the expectation taken over the data samples, our threat model assumes that the full graph G is known to the adversary. Consequently, we marginalize only over the unknown membership indicator variables of the non-target nodes.
The term P(n. 1|,, 0, 9) can be computed using Bayes' rule, yielding
T=
P(m. = 110,9) EM-P(MIOO)) o log p(0 m. 1,M, -l log 1
(12)
p(0) m. M,M
where A = Pmm, 1|M G) is the prior probability that node is member of the training set, before observing the model. Under our threat model, conditioning only on the data and the membership indicators of other nodes does not provide any information about the target node membership status. Hence, À = P(m, 1).
Finally, we need to compute the log ratio of model posteriors in (12). Assuming the negative log- likelihood loss funetion defined in (3), and making the natural assumption that, given M, the model depends only on the subgraph of G induced by M-tthat is, it is influenced solely by the data it was trained on the posterior distribution of the model parameters can be expressed using Bayes' rule in terms of the loss function and a prior PiI.M, X, AA) as
p(y,, | Ferm. 10 X, A)p(O)M, X,A) p(0lM, 9) J Tp((v+) vom =1 6, M, X, A)p(O)M, X, A)do
(a)
Tumm.- = 10, M, X, (M,, X,
Memmm==111 - P(y, M, X, A)p( X, K,A)d c
AM M. ( X, fe- E.-Ev ml 11 AM). pl (M) X, A)dc
(13)
where (a) follows since, from (1), each embedding z. is function of (X, 0. M. by [36.
Sec. 3.3], this implies that z. is independent of zu given (X, A, for all v # u. Applying the softmax and indexing with ye (2), preserves this independence. Step (b) follows from the definition of the loss function in (3). Also, the n X n matrices AM and Ayú are defined as
(AM)am
my m. = and (A = O, otherwise
Anw
(Am)uw, u. + U, 0.
otherwise
for E V. In words, AM is the adjacency matrix of the subgraph of G induced by the nodes masked by M, while Ayú corresponds the subgraph of this resulting graph obtained by removing the target node and all its adjacent edges.
15

---

We can now evaluate the log likelihood-ratie in terms of the loss function: p(0/m m, = 9)
log
p(0 m. M)
= = Σ m, AM)u. E
NEV
NEVi(a)
p(0 1, 1,M,
+ log
p(0 m. = 0, M,
1 E EnEV mh AM. p p(O = 1, M, X, A)dæ
log
Enevicoy mh m (X, A p(00 my mm 0, M, X, Ajdø'
p(0 m, N,M,X,A
A UM) ALN(
log
p(0 my = 0,M,X,AA
-log| / A-Ilfolx.AMmaa (M
p = LM,
e Exerrio p = 0,M, X,A)
p(0)m, = O, X, A)
ʃe (xcc p( m. = M, M,X, A)de' de
e( (X, Am)o, ( + log AO,
+
log ʃ e-lllolX
A0. p( mL 9)do (14)
where in step (c) we have used
Σ (f, Am)
Σ A,,((o((XAAA))n333))
"EV((U)
E
- vn))
"EVi(u)
=-((fo(X, AM).NA))
Σ uEN2(e)
m((((f((..A)aaa... e(fo(X, A v.))
= =-E[foXX, AM),. ALNz(e)
since the inclusion exclusion of node affects only the predictions within its L-hop neighborhood (u),,, assuming an L--lyer GNN. Furthermore, in step (d) we used (13) to simplify the model
distribution that is integrated over and substituted AM X, A) p( MO.
M1. for the prior
likelihood ratio (before observing the labels).
Combining (12) and (14) concludes the proof.
B.2 G-BASE: Practical Bayes-Optimal MIA against GNNs
We elaborate on the proposed sampling strategies used to approximate the expectation over the membership statuses of non-target samples, M, i.e., the term EM-P(Mj00G)) in Equation (5). In practice, we compute samples of all the indicator variables M and obtain M by discarding the indicator variable of the target node. This allows us to get samples of M for multiple target nodes from a single sample M.
Model-indeepnddet sampling. The simplest approximation assumes that the membership inference configuration M is independent of the target model, thereby ignoring the conditioning on 9, i.e., P 9) = P(M[G). Under this assumption, ship indicator m, E M as i.i.d. according to a Bernouli distribution with parameter = P(m, = 1). We then generate samples of M as M {m,, my Ber( (A); V).
approximate P(M[G) by treating each member-
O-hop MIA sampling. Recall that P(M|0, 9) the joint distribution of the membership of nodes. A natural approximation is apply per-node MIA to estimate individual membership probabilities
16

---

and assume independence across nodes, Concretely, apply O-hop MIA M..-i.e.. we ignore the graph structure and treat nodes as i.i.d. samples. This reduces the problem to the standard i.i.d. setting, where well-established MIA methods can be applied. Any i.i.d.based MIA that yields membership scores convertible to probabilities can be used. Here, we adopt the attack introduced in Section 5.2 which approximates the Bayes-optimal inference rule in the i.i.d setting. We then generate samples from the approximate posterior as M = {m, My ~ Ber(P(m, 1 x., u. y,.)), E V}. where P(m, 1 x e, V.) is the membership probability of node assigned by the BASE attack.
Metropolis-Hasee Hasttngg sampling. To account for the dependence of M on the target model 6, we develop a Markov chain Monte Carlo (MCMC) method based on the Metropolis Hastingg algorithm. The goal construct a Markov chain over membership configurations M with P(M 9) as its stationary distribution. To apply Metsopolis-Hastingg,, we need to be able to evaluate the unnormalized (up multiplicative constant) probability mass function P(M|0, 9), i.e., a function PT (M 9) satisfying
PM(MO0,
P(M ΣM Pa (M
We derive such a function using Bayes' rule, assuming uniform prior over M to eliminate the prior terms,
p(0|,, P(M EM ((0
Using (13) for the model posterior and assuming that the prior (before observing the labels) is independent of M and only depends on the graph under consideration, we obtain
c Enev m.nflfo (ololllooiaaioooo AM)
P(M 9) x
_e E. m. ml AMbu. p())d = P (M)
(15)
Our proposal distribution (MM'(M) randomly flips a small proportion the indicator variables in the current state M. Notably, this proposal distribution is symmetric, ((M'IMM Q(MIM') acceptance ratio. To sample from this distribution, we
so it cancels from the Seetrpolis-Hasting initialize the Markov chain at a randomly-selected configuration (0)), iteration we propose new configuration M by flipping fraction the membership indicators in M and compute the log acceptance ratio
log p(0 .9) p(0
Σ
(m -.) AM Au. Uw))
NEV
(f A p())dl))
+ log
(16)
(fe f e'-Eve
- log
p(
Each integral can be efficiently approximated via Monte Carlo sampling using shadow models. Notably, the same shadow models used to approximate the inner expectation in (5) can be reused here evaluate (16). We then accept the proposal with probability " g)). Specifically, we draw Uniform(O, 1) and set
(Mi++1) ((0) 9)) = [(M', 9))
p' if
pti > u
(MM))(()MM ((0)M() otherwise.
To obtain approximately independent samples, we insert a burn-in period at the beginning of the chain and use chilning-collectting samples only after sufficient number of iterations.
Gibbs sampling. Another MCMC sampling strategy that is well suited to our setup Gibbs sampling.
The sample instance of indicator variables M ~ P(M the Gibbs method iteratively
samples individual components conditioned on the remaining indicator variables. More precisely,
the kthh iteration of Gibbs sampling produces sample (k) {m] ,..., mn } by sampling the
(k) (k)
17

---

components sequentially:
m ()- 0. m2 ~ P(m2 ml (k) (k-1)
m (k) P(m m² (k-1)
(k)
m (k-1) 0,9)
m3
(k) ~ Pm |m] (M)
n- 0)
We note that each of these conditional probabilities is given by the Bayes-optimal membership inference formula (5):
P(m.- 0,
A -Sclfo, log / e = 0, M, + log
2²))
2
1 1-
Sampling from the conditional distributions simply amounts to sample from a Bernoulli distribution:
Myy Ber( (ammmmmm 00-11 Mu+1,.... ma, 0.9))
This Gibbs sampling strategy is therefore kind of MIA-based sampling that improves on the O-hop MIA sampling by accounting for the graph structure. A further advantage of the Gibbs sampling strategy over the Metropolis-Hasee Hastings method is that it does not require tuning any parameters. However, it is computationally demanding since single iteration requires querying the models over each node in the full graph G.
C Selecting the Decision Threshold
Since an adversary does not have access to ground truth membership labels, they cannot directly tune the decision threshold (by sweeping r) to achieve a specific FPR. Instead, the adversary must choose a threshold that is expected to yield an FPR close to the maximal tolerated FPR. For MIAs based on shadow models, we propose finding such a threshold by designating a subset of the shadow models as simulated target models, as suggested in [1, 37J. The simulated target models can be attacked using the remaining shadow models, possibly employing cross-validation. Because the ground-truth training data is known for the shadow models, the adversary can sweep over decision thresholds and identify the values that are expected to approximately yield the desired FPR.
By repeating the threshold estimation process across multiple simulated target models, the adversary can assess the variability in the resulting thresholds. A conservative adversary would choose threshold at least as large as the maximum threshold obtained. Another viable option is to choose the mean of the thresholds. As shown in Table 3 (graph data) and Table 4 (i.i.d. data). the variation in threshold values across target models is small, indicating that thresholds estimated from simulated target models are fairly stable. RMIA exhibits the lowest threshold variance. However, the viability of estimating the threshold using simulated target models also depends on how sensitive the resulting FPR is threshold fluctuations. Therefore, to demonstrate the effectiveness of this approach, we train 10 shadow models to act as simulated target models. These simulated target models are attacked and, using the ground truth knowledge about the training members, the decision thresholds resulting in an FPR not exceeding 1 1 are computed. The estimated threshold is then taken as the average of these decision thresholds. To run the attacks, 8 (online) and 4 (offline) separate shadow models are used. Table 5 shows the TPR and FPR achieved when using the estimated threshold on real target models. The FPR obtained using the estimated threshold does not deviate much from the target 1% FPR. Hence, the TPR is also close to the TPR of the exact 1% FPR threshold. Despite the differences in threshold variance between LiRA, RMIA, and our attacks (see Table 3 and Table 4), there is no significant difference in the accuracy of the estimated threshold.
We conclude with a remark on alternative methods for threshold selection. For LiRA, the threshold can be selected from the fitted Gaussian distribution. However, the accuracy of the estimated threshold depends on how well the Gaussian distribution fits the logit-scaled confidence values. As such, this approach also relies on an estimation based on population data, and on top, the heuristic observation that logit-scaled confidence values often look normal distributed. For RMIA with 7 = 1, the authors argue that their attack is calibrated such that threshold 3 = 1 results in FPR a. Investigating
18

---

Tahle 3:
Decision thresholds for RMIA, BASE and G-BASE resslting in the largest FPR less than or equal to the target FPR (1% and 0.1%). The threshold reported as mean 1 standard deviation, averaged over 10 different target models and sets of target samples. A comparatively small standard deviation indicates that the threshold is not expected to vary too much over different target models, allowing the adversury to estimate threshold using shadow models as simulated target models. The RMIA threshold does not satisfyy the empirical rule "threshold 1 FPR reported [13].
CORA (GCN)
CITESBER (GAT)
PUBMED (GRAPHSAGE)
K ATTACK
THRESHOLD@
THRESHOLD@ FPR
TPR@
1%
0.1%
1%
0.1%
1%
0.1%
RMIA
0.8566 + 0.0078
0,9030 1 0.0174
0.8240 = 0.0121
0.8900 1: 0.0299
0.9474 : 0.0039
0.8822 0,0030
BASE
0,0021 = 0.0096
0.6913
0.03-12
0.5907 + 0.0097
0.6971 + 0.0518
0.0052 + 0.0085
0,71 0.0161
G-BASE (MTA)
0.5619 + 0.0072
0.6204 0.0327
0.5724 0.0059
0.6471 0.0309
0.5028 0.0053
0.6771
0.0175
RMIA (OFF)
0.8275 + 0.0087
0.8612 + 0.0128
0.7649 + 0.0101
0.8315
0.0145
0.9719 + 0.0027
0.5926 + 0.0016
BASE (OFF)
0.5358
0.6015 0.0454
0.5540
0.6341
0.0368
0.6240
0.0182
G-BASE (OFF)
0.7031 = 0.0127
0.8160 1 0.0324
0.7064 + 0.0168
0.8166 1: 0.0311
0.6661 + 0.0055 0.8051 1 0.0213
FLICKR (GCN)
AMAZON-PHOTO (GAT)
GITHUB (GRAPHSAGI)
ATTACK
THRESHOLD@FPR
THRESHOLD@ FPR
THRESHOLD@TPK
15
0.1%
1%
0.1%
1%
0.1%
RMIA
0,8029 + 0.0086
0.9142 0.0099
0.9267 + 0.0101
0.9675 0.0144
0.462 + 0.0053
0.9785 0.0038
BASE
0.9080 = 0.0091
0.9873
:: 0.005
0.7167
# 0.0392
0.8866 1: 0.0762
0.6328
+ 0.0178
0.7250 i: 0.0300
G-BASE (MIA)
0.6770 0.0108
0.7910
0.0109
0.6031 +
0.7316 0.0532
0.6162
0.0114
0.6990 0.0189
RMIA (OFF)
0.8695 1: 0.0074
0,9330 1 0.0042
0.8679
+: 0.0084
0.9032 1 0.0055
0.9490 +: 0.0119
0.9801 1 0.0055
4.
BASE (ORR)
0.9143 + 0.0084
0.9884
0.0036
0.5806
0.0119
0.7219
0.0830
0.6317
0.0233
0.7421
0.0258
G-BASE (OFF)
0.6965 1 0.0109
0.5072 0.0191
0.6822 1 0.0121
0.861N 0.0279
0.6677 1 0.0108
0.7826 1 0.0184
Table 4: Decision thresholds for BASE (without the sigmoid normalization), RMIA and LiRA resulting in the largest FPR less than or equal to the target FPR (1% and 0.1%) The threshold is reported as the meun = standard deviation, averaged over 10 different target models. comparatively small standard deviation indicates that the threshold over different target models. allowing the adversary to estimate threshold using shadow models us simulated target models. The RMIA threshold does not satisly the empirical rule threshold=1 I-FRR as reported in [13].
expected vary much
CIFAR-10
CIFAR-100
K
ATTACK
THRESHOLD FPR
THRESHOLD @ FPR
1%
0.1%
1%
0.1%
BASE
0.5385 + 0.0473
0.8159 + 0.0669
0.8417 + 0.0735
1.2240 + 0.0914
32
RMIA
0.9624 1 0.0047
0.9900 1 0.0028
0.9429 + 0.0139
0.9833 1 0.0061
LIRA
0.6505 1 0.0515
1.1098 0.1126
0.8366 1 0.0478
1.4039 1 0.0804
BASE (OFF)
0.1766 + 0.0279
0.3485 + 0.0472
0.1920 + 0.0440
0,4066 + 0.0525
16
RMIA (OFF)
0.9645 + 0.0050
0.9909 + 0.0023
0.9647 0.0078
0.9918 + 0.0021
LIRA (OFF)
0.0837 + 0.0223
0.0323 + 0.0136
0.00770 + 0.0201
0.0210 + 0.0080
BASE
0,6116 + 0.0601
0.9740 +:400:00 0.0839
0.9207 1 0.0864
1.4146 + 0.1155
8
RMIA
0.9675 1 0.0035
0.99322 + 0.0015
0.9505 + 0.0102
0.9884 1 0.0037
LIRA
0.9362 + 0.0812
1.5689 + 0.1655
1.1176 + 0.0898
2.0389 + 0.1434
BASE (OFF)
0.2312 + 0.0364
0.4795 0.0571
0.24979 + 0.0569
0.5437 + 0.0737
4
RMIA (OFF)
0.9698 1 0.0032
0.9934 1 0.0014
0.9689 1 0.0059
0.9942 1 0.0021
LIRA (OFF)
0.0664 1 0.0199
-0.0211 + 0.0101
-0.0581 + 0.0162
0.0112 1 0.0056
Table 5: Attack performance using a threshold estimated by attacking 10 simulated target models. The estimated threshold is the average 1% FPR threshold against the simulated target models. TPR 1% FPR is reported for comparison. Performance measured as mean + standard deviation against 10 target models. The FPR against the target models when using the estimated threshold close to 1 %. Consequently, the TPR at the estimated threshold is close to the TPR at the 1% FPR threshold. This method of estimating the threshold at given fixed FPR does work for our attacks. LIRA, and RMIA.
CORA (GCN)
(CAT)
PURMED (GRAPISAGE))
ArTACK
TPR81SPRR (5)
ESTIMATED THR12000LD
TPRE-15EPR (%)
ESTIMATEO
TIRE1SEPR (9)
ESTIMAIEO
TIP2(9)
FPR (%)
TPR (1S)
FIR (1)
TPRL
FFP (R)
LIRA
6.97 0.66
0.83:1 0.34
16.35
12:5 0.05
12:2::00 0.30
0.33
2..14
1.01 0.13
16:006=1::00
20:15
15.88
G-BASE
11.00
1196-1.70
1.03.:00 0.30
21 7.50
01.85 1.50
1.114-0:30
5,33 0.588
5.39 0.30
1.00 1
LIRA (OR5)
12.45 3.60
11.75 1.30
0.84 0.30
18.17 2:24
20.26 0.66
1.22 3:
1.52 0..0
2.64 2.33
4. 0.20
RMIA (O03)
3.00
17:30- 1.14
1009-4 119-2000 0.36
25.38 - 48
27 0:51
0.89-1 4: 0.30
3.41 -
3.14 -1.27
0 1.15
0.30
G-BASE
11.88
1.15
2..8
0.600
1.00
this heuristic rule further, we find that it generally does not hold. In Table 3 and Table 4 we see that the thresholds resulting in an FPR at most 1 1% or 0.1 % are lower than /3 = 0.99 or 3 0.999, respectively, across all datasets. Moreover, Table 6 (graph data) and Table 7 (i.i.d data) show that the actual FPR obtained when setting 3 0.9 and / = 0.99 is lower than 10% and %, respectively, as would be expected if 3 1 - where to give FPR Consequently, the TPR obtained at B = 0.9
19

---

Table 6: TPR and FPR at fixed threshold 9 for the RMIA attack with 7 = 1, using the full population as the Z set. Setting [ = does result significantly lower FPR than a, cost a lower TPR than what is possible achieve at FPR 256 shadow models used for the online attack, and 128 for the offline attack.
CORA (GCN)
CHTSEER (GAT)
ATTACK
B = 0.9
0.99
3 0.9
B = 0.99
TPR (%)
FPR (%6
TPR (%)
FPR (%)
TPR (%)
FPR (%)
TPR (%)
FPR (%)
RMIA
1:
0.04
0.00
0.00 0.00
RMIA (OFF)
0.00 + 0.00
0.00 + 0.00
0.00 + 0.00
0.00 + 0.00
0.10 + 0.09
0.00 + 0.00
0.00 + 0.00
0.00 + 0.00
Table TPR and FPR values for RMTA RMTA (OPF) CIFAR-10
decision thresholds 8
where
E (0.01, 0.001). Results reported mean standard deviation 10
0.99
0.999
K
ATTACK
TPR (%)
FPR (%)
TPR (%)
FPR (%)
32
RMIA
1.90 1 0.09
0.11 0.04
0.20 1 0.03
0.00 1 0.00
16
RMIA (OFF)
1.89 0.11
+.06
0.21 0.03
0.00 + 0.01
8
RMIA
1.82 0.07
0.18
0.00
0.01 0.00
4
RMIA (OFF)
1.82
0.09
0.20
0.05
0.20 0.02
0.01 + 0.01
and ß = 0.99 is significantly lower than what is possible to achieve at FPR 10% and 1%, respectively. As an example, at FPR 1,, online RMIA achieves mean TPR of 24.00% on Citeseer (see Table 1), whereas using the threshold 3 = 0.99 instead results in no true positives at all.
D Membership Inference Game for i.i.d. Data
The following definition membership inference game closely follows the one in [11, Def. 1] and the ones in [14].
Definition 5. (Membership inference game)
1. The challenger samples a dataset Dirain C 'D from a data population pool 'D and trains a model O on D
2. The challenger flips fair coin to generate bit b. If 0, data point is randomly selected from Dinii if 1, the data point v is selected from D Dirain
3. The challenger gives the adversary the population pool DD the target sample v, and black-box access to the trained model fe-
4. The adversary may also have access to additional side information (such as knowledge about the training algorithm or model architecture). Using this information, the adversary performs a MIA
m, + MIA(fa, D, H), where m, is an estimate of the membership status of sample me-
5. The attack is successful on data point v if my m.g-
E
BASE: Practical Bayes-Optimal MIA for i.i.d. Data
E.1
Proof of Corollary 1
The i.i.d. setting corresponds to A I, where is the identity matrix. In this case, since the data points are independent, the gigghbrrhoo-dependdee indicator satisfies m, if the data sample u E [n] is included in the training set and m, 0 otherwise. Hence, Sc(fe. M, D) in (6) reduces to the individual loss value of the target sample i.e., Sc(fo, u, N,M, D) = ((fo(x,). y.)) Finally, since p(0 m M, {x }rmm is independent of
term (7) vanishes, G D. and the membership
m. by assumption, the log-likelihood ratio A(0, M, (r p(0 m. (a.. vanishes from the Bayes-optimal membership inference rule (5).
p(0 mmm m0001.1.6 MM, 1im)) 1 and it
E.2 BASE: Practical Bayes-Optimal MIA for i.i.d. Data
Recall that under the i.i.d. assumption, we have G D and the loss-based signal simplifies to Sc(fe. v, M,D) {(fo(x)), yo) in Theorem 1. Now, since the loss-based signal no longer
20

---

depends on M, the only dependence on .M in Bayes-optimal membership inference rule is contained in the posterior model distribution distribution by the prior p( D), (which we denote simply by p(Φ) to conform to the standard notation), we have removed all the dependence on M the approximation and the outer expectation over M trivial.
m. = 0, M). By approximating this posterior model
The posterior membership probability P(m, 1 D) then simplifies to
P(m. 1 D) = (= y.)) log / p log 1 1
A
(17)
The remaining expectation over the prior model distribution still intractable but can be efficiently approximated using Monte Carlo sampling of shadow models,
log / / e plo)d log
USor (o))ir)) ΦR + T(Da)
(18)
K
where the shadow models are trained on sampled datasets Dj from the data population, in analogy with (9). Substituting the Monte Carlo approximation from (18) into (17), we can formalize the resulting attack as Definition (Section 5.2).
Note that neither the sigmoid function nor the membership prior term are necessary for the attack. As shown in Lemma 1, equivalent attack can be obtained by applying the inverse sigmoid function and subtracting the prior term, which corresponds to monotonic transformation. However, we retain both the sigmoid function and prior term to preserve the interpretation of the attack score as posterior probability.
E.3 Proof of Theorem 2
We begin by establishing the following result.
Lemma 1. Two score-based MIAs are equivalent if their score functions are related by a monotonic transformation.
Proof. Let and b denote the vector of prediction scores for two MIAs A and B, respectively, after attacking an arbitrary target model using N arbitrary target samples. Furthermore, let тA be an arbitrary decision threshold for attack A, such that the positive predictions are M i E {l...., N). a > TA}. J. By assumption, there exists a strictly increasing function such that g(a.) b, for all [I....,NN} Now let TB g(TA), then the positive predictions of attack B are given by
MB (i:iE [1,N), b, > >TB (i:iE [1,N), g(a;) > g(TA))
-i:iE [1,N), >TA
=MA;
where the third equality follows from the fact that gxx) > 9(y) if and only if x > for a strictly increasing function g. Since TA arbitrary, A and B are equivalent by Definition 4.
The intuition behind the result of Lemma is that monotonic transformation preserves the order of the membership scores. When decision threshold is applied to MIA scores, only the target samples with top-k highest score (with & depending the threshold) are classified as members. However, since the order of the scores is preserved, the top-k scores will correspond to the same target samples for both MIAs.
Equipped with Lemma 1, we are now ready to prove Theorem In particular, since the composition of monotonic transformations is itself monotonic transformation, it follows that Lemma 1 also applies when the score functions are related by such a composition, which we will use repeatedly in the proof that follows.
21

---

The RMIA score function is defined as
p u.s 11
ARMIA (20,, yz; 0)
Pr
(19)
(2) 333
p(0 æ. M/j)
where 0 the target model parameters, (z), yk) the feature-label pair defining the target sample, and the data population.
To prove that BASE is equivalent to RMIA when 7 1, it suffices (by Lemma 1) to show that the their score functions are related by a monotonic transformation. We do this in two steps:
1. We show that BASE is equivalent to attack that computes the ratio between the target model's confidence value and the expected confidence value over the prior model distribution. We refer to this attack the mean confidence attack (MCA).
2. We derive the monotonic transformation that relates MCA to RMIA, which turns out to be cumulative distribution function (CDF), restricted domain determined by the data population.
The steps are detailed in the following. 1. The BASE score function given by
ABASE( (z;, yu: 0) (e(fo((z)))))) v.) log f e log log A
(20)
Since the sigmoid function strictly increasing, it can be removed to obtain an equivalent attack. After removing the sigmoid, the prior term becomes additive constant, which also defines monotonic transformation and can therefore be discarded. Applying the (strictly increasing) exponential function to the resulting score function, obtain
fo( J f((
fo( Eflf
AMCA (z,, vs:
(21)
where have used that the confidence is related the negative log- likelihood loss function by fo( (=((s(()))))) We note that MCA is kind of difficulty calibration [37], using the confidence value as the membership score and calibrating by dividing the expected value rather than subtracting it.
Next, we show that the MCA score in (21) related the RMIA score function in (19) when 7 1. Applying Bayes' rule to the likelihood ratio in RMIA, we can rewrite the score function as
p(us ac, 0 p((0) p(y))ay)) p R p)p(0) p(u (x.)
ARMIA (I ys:
Pr (mn
2
p(ua a 0)
p(U, 1zy. 0) plu, (z,)
Pr (a) )m
p(y xx.)
plys a 0)
plu; x 0) Eølp(v ax +b]
Pr (æ, )/b
E (1 Di, Φb]
(o( ff((f(()))))))
fo(
Pr (m3.05) /~
(22)
folm;) E,)
This expression corresponds the CDF of the random variable X
evaluated at
fa(a)) AMCA(Zs Vs: 0) Ealfa(at),.." While CDF is always non-decreasing, is not necessarily strictly increasing, However, since the target sample (æ,, 3:) is also part of the data population (22) is
strictly increasing on the relevant domain. Specifically, as a function of the real variable Le the CDF (22) can only be constant on intervals where there Therefore, RMIA and MCA are equivalent by Lemma 1.
fa(m:)y
probability mass density.
Combining steps 1 and proves that BASE is equivalent to RMIA with 7 1.
22

---

F
Online vs. Offline Attacks
MIAs that shadow models estimate distributions of reference models can be designed as online or offline attacks. the online setting, the adversary can train shadow models on the target sample. This requires no additional assumptions, the adversary controls shadow model training and can always include the target. However, in certain auditing scenarios, the online setting may be impractical-it would necessitate retraining shadow models for every new audit point. In contrast, the offiine setting assumes that shadow models are trained once, without using any target samples. This setting be of importance when all the target samples are not determined when setting up the attack. However, due to the shadow model training trick introduced in [11] (see also Algorithm 1). it possible to perform efficient privacy audits in the online setting. Following common terminology, we refer to the shadow models trained on the target sample as in-models and otherwise they are referred as out-models.
According to its original paper [13], RMIA is ideally performed in online mode. Consequently, due to the equivalence between BASE and RMIA (see Theorem 2), BASE should also benefit from the use of in-models. However, the Bayes-optimal membership inference formula (5) involves only out-models, consistent with [1]. However, since BASE and G-BASE are only approximations of the Bayes-optimal rule, involving several approximations, we cannot rule out potential benefit from using in-models in our attack.
Following a similar line of argument as [13], to compensate for the lack of in-models in the offline setting, introduce scaling factor [0, 1] the Monte Carlo loss term over shadow models,
A - > (23)
P(m. 1 D) - - H.) - a log
1 K
eifr Uor (mn))e)) + log 1 1
k=
Intuitively, the loss value on the target sample expected to be smaller when using an in-model compared to out-model. Thus, the LogSumExp over shadow models is expected to be negative number of greater magnitude when computed only over out-models offline mode, as compared to the mix of in- and out-models used in online mode. The scaling factor reduces the magnitude of this term to better match the expected value when using in-models. In principle, this scaling constant could also be used in online mode. We indeed found that this could marginally improve the performance in some cases also in the online setting. However, we believe the small performance benefits do not outweigh the disadvantages of introducing a hyperparamter in need of tuning, and omit from using online mode. We also found little to no benefit from introducing for G-BASE.
G Differential Privacy Bound for Bayes-Optimal Membership Inference
It is straightforward to bound the Bayes-optimal membership inference probability in terms of 6- differential privacy (DP) [1]. DP is a mathematical framework that defines a notion of privacy for individual data records through measure of indistinguishabiiity. It was originally proposed in the context of databases, formalizing the intuitive notion that a query function on a database is private the inclusion or exclusion of single data record only affects the query output by small amount.
Definition 6. (c-D) A randomized mechanism M satisfies e-DP for any two datasets D and D) differing in a single data sample, and any event E C Range(M), it holds that
P(M(D) E E) log P(M(D') E E) Se.
(24)
DP often used as a guarantee for private machine learning. Consider a e-D training algorithm T that outputs set of weights 0 given training dataset D: 0 <- T(D). Given D, the inclusion and exclusion of the target sample e result two datasets that differ only one sample. Therefore, the condition for eDDP directly results in the following bound the Bayes-optimal membership
23

---

Tahle 8: Evaluation of attack performance in the case of a distribution shift in the shadow models. Specifically, the adversary uses a model architecture and training procedure AUC and TPR at 1% and 0.1 % FPR. The result is reported as the sample mean + the standard deviation over 10 random target models and sumples of target nodes. The purumeter K denotes the number of shadow models. All attacks undergo a decline in performance compared to the idcal setting where adversary uses the same model architecture and training procedure the
differs from that the challenger. Performance measured terms
challenger. Our uttacks BASE and G-BASE achieves top performance also in this setting.
CORA (GCN)
CITESTER (GAT)
PURMED (GRAPHSAGEF)
ATTACK
(9)
TPR FPR (8)
AUC (%)
TPR FPR (9)
AEC (5)
TPR SPR (%)
1%
0.1%
1%
0.1%
1%
0.1%
MLP (0 58.88 2:30
2.08
0.99
0.25 1
62.82
2.37
3.27 1 1.47
0.51
0.55
50.74 0:449
1:05 0..8
0.09 1.007
MLP (LLP(002-HHO
60.20:1.::3
2.45
1.25
0.25 0.332
61.22
1.47
2.75
1.21
0.10 1 0.16
50.87 1.775
0.25
0.09-10.05
LIRA
6..63
0.37
11.6 4:
06.74
1.41
2.65
0.24
61.82 0.07
1.17=1122
0.11
RMIA
78.86 4: 1:02
1.82
11:3
74.96
1.11
5.34
1
65,02 0.06
1.50=11.33 11.25
0
BASE
73.66 1.00
1.83
0.51
74.90
6.35
1.14
65.02 0.00
0.25
0.16++0.07
(MIA)
00.34
0.71
2.28
1.43
69.83
0.75
7.48 1.08
1.30
57.00 67.09.1 0.79
2,38 0.027
0.42
LIRA
71.76
+ 1.11
0.41
73.62
3:20
0.22
62.05 0.60
0.00
8.82
2.35 1.46
75.57
0.25 2.90
2.60
56.81 0.64
BASE
78.64
1.00
2.43
2.29 + 1.45
76.24
10.00 2:01
3.27 2:49
54.85 0.07
1.91 11223
0.25
(MIA)
08.47
2.01
1.17 0.65
08.74 8:
4,38 0:77
0.36
07.00
0.65
2.68 0.20
0:42
probability (12):
log p(Olm, D,
1
A
P(m, 110, D) -EM-P(MDD)
+ log
(25)
p(0 m. M, D)
E log A 1~x)
S EMP(MEDD
o
(26)
A
aree+logg log
(27)
As E + 0, the upper bound approaches A. That is. the stronger the DP guarantee, the closer the membership inference to random guess using only the prior. This c-D bound is particularly simple when \ = 0.5, i.e. prior to observing the model, we are maximally uncertain about the membership status of the target sample. In this case, the bound becomes P(m, = 1 D) S (ee).
H Additional Experiments
In this appendix. we present additional experiments and results. Further results for the mismatched adversary setting are presented in Section H.1. We compare our different sampling strategies for G-BASE in Section H.2. Wall-clock time for membership inference across different attacks is reported in Section H.3. In Section H.4, we present further results on the CIFAR- 10 and CIFAR- R-000 datasets, which are widely adopted benchmarks for MIAs on i.i.d. data. Finally, In Section H.5, we include ROC curves in the low FPR regime for some other dataset-target model combinations not presented in Table 1.
H.1 Robustness to Mismatched Adversary Assumptions
We evaluate the robustness of our attacks and the baseline MIAs in the scenario where the adversary does not have perfect knowledge of the target model architecture and training procedure. In particular, we run the attack using shadow models of a different architecture than the target model, trained using different optimizer (with hyperparameters tuned for the respective model and optimizer). Specifically, the target models are trained using SGD with momentum, whereas the shadow models are trained using Adam. Moreover, the target model is only trained on 35% of the dataset, whereas the adversary trains the shadow models on 50% of the data by means of the usual shadow model training procedure outlined in Algorithm 1. All models are 2-layer GNNs with the final embedding having as many dimensions as there are classes.
Table 8 shows the attack performance over three different datasets. The shadow model architectures are GAT (with 4 and attention heads in the first and second layer, respectively), GraphSAGE with max aggregation, and GCN, on Cora, Citeseer and Pubmed, respectively.
We observe decline in attack performance across all attacks compared to the ideal setting (see Table 1). LiRA suffers the most and is not competitive with our attacks BASE and G-BASE.
24

---

Table 9: Comparison of different sampling strategies for G-BASE, We also include the performance of G-BASE when the ground-truth sample M is used (Ground-truth), i.c. the actual target training set mask, indicating how much performance
improvements can be made by a more accurate sampling method. Results are repurted as mean 1 standard deviation over 10 different targel models and sets of larget nodes. M 8 samples of M are used in all cases.
(GCN)
(GAT)
PUBNED (GRAPH5
SAMPLING
(9)
TPR
TPRO
(R))
TPR FPR
115
0.15
0,1%
-NDEENNNNEENNEETT
12.15
7:10
0.88 0.00
81.78 0:067
13.02:4...57 2.52
1.4.5-0.80
02.92 0.006
5.38 0:00
1:30 0.35
0-HOP MIA
77.42++1.00
0.996+33.01
5.05 +.00
63.31 0.73
21.19+44.22 4.27
6.92+-4.01
02.56 0.774
5.58 + 1.05
1.10 1..00..0
MITROPPO HS-HASTINGS
1..50
13.25+1.77
5.20++2.31
83.15 0.883
19:62+41.27
5.00+22.70
03.50++0.71
6.10+00.00
1.18 0.44
GIDns
76.6
+.51
2.884
61.39-+0.077
2-.35
5:30
0L:10+0..00
0.28 0.56
1.50=0.0
GROUND-TRUTE TRUTT
76.02
19:47
#.3.6
7:30::33.92
0..82
2..2
6.30
0.46
11.04 0:04::0.3
+.00=
MODEL INDEPENDENT
1.77
9.41 2,33
3.05
1.67
76.26
1.24
3.24 23.02
61.97 0.05
5.22 1:33
1,35 = 0.30
D HOP MLA
73.00 1.35
10,38
1 2:90
3.59
2.006
76.05
1: 1:53
15.22:1.2:44
4.02 2.36
62.66
0.661
5.351-0.47 0.47
1.27 = 0.26
METROPOLIS-HEE HASSINGGG
75.00=1.22 1.24
9.17
4: 2.71
1.79
77.72
4: 1.00
14.68
6.06 2.881
02 62:11 0.80
0.30 0:400
1.24 0.47
GIBBS
71.83 1.74
10.23
2.6.
5.10
2:10::10 1.49
17.08
4 1.19
14.69
4.22 2.4.5
02.08
2: 0.64
0.29
2: 0.42
1.58 = 0.01
GROUND TRUTH
7..00
11.04 2.55
2:88
1.49
90.06
4 1.21
10.01 2.44
0.34 4.10
08.09 0.503
8.18 2 0.55
2.48 = 0.29
FLICKA (GCN)
AMAZON PHOTO (GAT)
GITHUS (GRAPHSAGE)
AUC (8)
AUC
TPR&
(S))
&PPR (1R)
0.31%
15
0.15
0.1%
MODEL-INDEN
60:04 1.00
0.00
16.00
0.40
3.70 0.88
67.40
1:00
0.44
0.49 0:00::0::1
D.10P MIA
07.65 01.53
0.33
11.00
16.77
0.62
07.38
3.00
0.52
0.00
HASTINGS
56.56
01.71
0.34
11.06
16.11
0.86
0.58
06.35
2.58 0.50
0.39 0.221
G1ESS
07.88 1..91
2.33
0.27
0.33
0.64 56.53
0.660
0.76 0.449
5T.47 8: 1.40
3.18 0.54
0.55 0.11
GROUND-TRUTHI
1.79
1.98
0.50
1.34
1.34
71.64
11.08
4.50 2.00
MODEL
00.04 1.01
0.22
0.00 0.40
07.81
0.7.8
0.64
51.78
0.56
0.58
D-10P MIA
07.71 0.44
0.21
57.74
07.72
1.06
3.12 0.47
HASTIIG
56.90 0.75
0.22
0.20= 0.00
56.25
1.11
1.10
06.37
2.62 0.64
0.28
G1aBs
B8.63 01.95
0.32
57.94
1.00
08.36
3.44 0.64
GROUND-TRUTE
69.70 1.83
1.38
02
2
1.84
1.22
2.85
3.38 à
H.2 Comparison of Sampling Strategies for G-BASE
In Section 4.3 and Appendix B.2, we proposed four different sampling strategies to sample from P, 9). for the purpose of evaluating the outer Monte Carlo estimate in the G-BASE attack Definition 2. Here, we further evaluate and compare the impact of the sampling strategy on the attack performance of G-BASE. Table shows the attack performance of G-BASE over different datasets and model architectures, using each of our four sampling strategies; model-independee sampling, 0-hop MIA sampling (using BASE), Metropolis-Hastinng The Metropolis- Hasttings step size parameter c, controlling the fraction of indicator variables that are flipped in each step, is chosen such that the acceptance rate the range 0.2-0.4. We run the Gibbs sampling for one iteration through all the indicator variables. Note that for O-hop MIA sampling, the same set of shadow models used for BASE (to obtain membership probabilities for this sampling strategy), can be used for G-BASE, and the membership probabilities can be computed once, before running the attack.
sampling, and Gibbs sampling.
To gain insight into how much more the attack is able to gain from a more accurate sampling method, we also run G-BASE using the ground-trute -ruth target training set as sample M. Surprisingly, using the ground-truth M does not help the G- G-BASE attack against GCN target model on Cora. However, on other datasets, the ground-truth sample improves the performance significantly, indicating that a better sampling strategy can still make the attack more effective. We also note that, in many cases, the choice of sampling strategy has only a modest effect on overall attack performance, particularly for low values of M. The precision of the sampled graphs relative to the ground -oound target training graph generally improves only slightly when using model-dependent sampling. which explains the similar performance observed between model-independent sampling and more sophisticated methods. However, there are instances where the sampling method has a more pronounced impact-foo for example, model-independent sampling on Flickr.
Recall that we have effectively approximated the model distribution p(0/m, = 0, 9) by a distribution p(o]g), independent of and M, when reusing the same set of shadow models for each target node. A consequence of this approximation that even when obtaining highly fidelity samples M ~ P(M 9), only the loss signal for the target model is precise, and the loss signals for the shadow models will contain lot of noise due to the mixture of member and non- non-member nodes in their local neighborhood around the target node. If p = 0, M, g) were estimated more accurately, e-g., by training shadow models on the nodes masked by M, then the fidelity of the sampling strategy is expected to have a larger impact on the attack performance.
25

---

Table 10: Performance of G- B-BA under varying (numbee of samples M.. sampling stralegy muudel-independen., hop MIA sampling, and Gibbs sampling, for Flickr, Amazon-Phoke Puhmed, respectively. The attack performance consistently increases with an increasing M. but with signs of diminishing returns.
FLIcE (GCN)
AMAZON-PHOTE (GAT)
PUBMED (GRAPHSAGE))
(8)
TPR (1))
AUC (8)
FPR (16)
(SC)
TPR
0.1%
15
0.1%
15:
0.1%
59.
1.00
2,57 0.3.1
0.41 0.06
$6.38
0.66
3.27
0.773
0.49 0.39
63.76 1.511
5.90 1: 0.65
1.61 1. 0.47
ONLINE 8
60.00 1.15
60.04
L,2
3.08..0.34
180---0.35
0.45+ 0:11
0.11
57.02
0.00
3.74
4.211 1.09
0.54
0.60
0.8.
61.54
64.08 01:08:0067
6.16 0.62
0.68.10.00
1.87 2. 0.65
1.80
0.67
0.852
0.70
2.65 +-227
0.43+0.08
4.16++0.34
62.18
0.55
OFTLINI
16
00.00
00.08
1.13
0.5G
2.92 0.38
3,11 0.24
0.45 0:13
0.522.011 0.10
$7.99
57.94
1.11
0.78
4.78 # 1.25
0.08
4 0.95
1.53
1.39 + 0.57
4: 0.58
62.84 0.65
62.87
= 0.53
5.80 0.38
5.78 0.67
1.45 0.42
1.51 = 0.52
52
61
01.02-
1.14
3.16++0.42
0.54 0.10
18.33 - 1.08
4,98 + 1.13
1.68 + 0.56
63.02
0.64
0.94
0.42
1,50 0.27
Table Comparison wall-clock time the inference phuse of atlacks, RMIA, and LiRA.
WALL-CLOCK TIME (S)
ATTACK
FLICKR (GCN)
AMAZON-PHOTO (GAT)
PUBMED (GRAPHSAGE)
LIRA
0.02585 + 0.02018
0.02041 0.01970
0.01382 + 0.01850
RMTA
2.04167 0.01045
0.19090 0.00074
0.50807 + 0.00149
BASE
0.01488 + 0.00004
0.01096 0.00008
0.00444 = 0.00003
G-BASE (MIA)
6182.23 + 342.81
680.38 + 30.55
684.11 = 146.37
G-BASE (GIBBS)
18377.06 1 484.46
2013.80 = 11.32
1944.71 + 318.62
LIRA
0.01964 1 0.00026
0.01361 1 0.00030
0.00730 1 0.00028
RMIA
2.04350 = 0.01280
0.19179 = 0.00101
0.50834 = 0.00102
BASE
0.01508 0.00004
0.01119 0.00007
0.00468 = 0.00004
G-BASE (MIA)
4203.32 + 198. 85
416.16 = 19.29
408.95 6.72
G-BASE (GIBBS)
12055.83 + 576.11
1262.03 = 20.53
1233.48 48 + 17.46
How many graph samples is enough? The sampled graphs M are used to compute a Monte Carlo estimation of the outer expectation of the Bayes-optimal membership inference rule (5). We therefore expect the attack performance to improve with an increasing M. In practice, however, we constrained by the available computational resources. To get insight into how many samples are required to get a satisfactory performance, we run G-BASE with varying M over various target models and different sampling strategies. Table 10 reports the measured attack performance. In particular, we use G-BASE with model-independent sampling, O-hop MIA sampling, and Gibbs sampling for the Flicker, Amazon-Phoo and Pubmed larget model, respectively. Although we consistently observe an increasing attack performance as M increases, there are signs of diminishing returns.
H.3 Wall-Clock Time of Membership Inference
To quantify the computational efficiency of our attacks, LiRA and RMIA, we measure wall-clock time for their inference phase. Table 11 reports these times for various target models across multiple datasets and GNN architectures. For G-BASE, we measure inference time under both O-hop MIA sampling (using BASE as the O-hop MIA) and Gibbs sampling.
Among all attacks, BASE is the most efficient--aproximmaee 20 to 200 times faster than RMIA while achieving comparable performance. The results also show that G-BASE is orders of magnitude slower, primarily due to the lack of parallelization across target nodes. Nevertheless, its inference time remains tractable. We believe it is important to accurately evaluate the data leakage associated with membership inference, even if this comes with a higher computational cost.
H.4 i.i.d. Data
To demonstrate BASE on i.i.d. data, we train a Wide ResNet [38] with depth 28 and width 2 on both CIFAR-10 10 and CIFAR- 100 for 100 epochs using standard data augmentations and early stopping. Fach experiment is averaged across ten target models. For CIFAR-10. 10. the target model achieves mean training accuracy of 73% 1. 1.15% and test accuracy 80.45% 1.53%. For 10F0 the model reaches training accuracy of 75.97% + 6.68% and test accuracy of 49.89% + 1.88%
26

---

Table 12: Comparison of different attacks on Wide ResNet-28-2 trained on CIFAR-IO and CIFAR-100. Performance is measured lerms of TPR FPR, and the results are reported mean standard deviation over random target models.
CIFAR-10
CIFAR-100
ATTACK
TPR @ FPR (%)
@ (%)
AUC
AUC
%
0.1%
1%
0.1%
BASE
62.94 .2.94.2
2.06
5.92 1 1.27
1.66 1: 0.43
74.80 1 3.22
12.08
3.35
4.11 + 1.69
32
RMIA
62.94 2.06
6.92 = 1.27
1.66 + 0.43
74.80 = 3.22
12.08
+ 3.35
4.11 = 1.69
LIRA
61.00 1 1.45
5.21 1 0.91
1.32 1 0.33
72.65 1 1.80
9.99 1.86
2.47 1 0.87
BASE (OFF)
61.67 +2100
5.67 + 1.29
1.64 0.39
71.35 + 3.36
8.89 + 2.97
3.07 + 1.42
16
RMIA (OFF)
62.45 1:55t:22 2.10
5.61 + 1.23
1.57 +: 0.40
70.65 +: 3.30
7.35
2:21
2.07 + 0.94
LIRA (OFF)
60.51 = 1.75
4.10 = 0.61
0.94 # 0.25
72.33 + 2.66
8.36 = 1.63
1.60 = 0.69
BASE
62.64 :: 1.96
5.21 + 0.99
1.19 + 0.38
73.98 +: 3.18
10.34 +: 2.91
2.81 = 0.95
RMIA
62.64 + 1.96
5.21 0.99
1.19 = 0.38
73.98 + 3.18
10.34 = 2.91
2.81 = 0.95
LIRA
58.79 0.99
3.64 0.67
0.85 1. 0.25
69.22 1.60
7.29 1 1.37
1.60 1 0.58
BASE (OPF)
61.54 + 1.98
5.05 + 1.06
1.23 + 0.39
71.26 + 3.28
8.23 + 2.62
2.45 + 1..11.2222 1.20
RMIA (OFF)
62.17 1.96
4.94
1.19 0.39
70.48 = 3.25
6.45 + 1.88
1.45 = 0.67
LIRA (OFF)
59.80 1.67
3.77 = 0.76
0.78 0.24
71.00 2.68
7.27 1.45
1.26 0.57
10-1
10-2
Thie Positive Rase
Thu Positive Rate
C-BASE (nan)
BASIL (ours)
10-3
(13)
10-3
(ours)
MiP 115, 161
KMIA [13]
Mll P0+7-1kpp1S
LRA
10-4
10
10-3
10
10
10-1
10
False Positive Rate
Palse Positive Rate
(a) Online, K =
(b) Offfine, K =
Figure 4: Average ROC curves (10 runs) for the Amazon- Photo dataset with GraphSAGE as target model.
Table 12 presents the attack performance of BASE, RMIA, and LiRA. In the online setting, BASE and RMIA exhibit identical performance, in line with Theorem 2. Both methods consistently outperform LiRA across the evaluated configurations. In the offline setting. while the differences less pronounced, BASE achieves superior performance over both RMIA and LiRA at low false positive rates.
H.S ROC curves
To compare the attack performances in terms TPR over all low FPRs, we provide average ROC curves in Figures 4 to 7. К denotes the number of shadow models used. We see that in the online setting, the ROC curves of BASE and RMIA are identical, as is expected in light Theorem 2 (we in RMIA). In the offline setting, BASE and RMIA perform similarly, but not equivalently. G-BASE achieves the best performance in terms of TPR at low FPR in all cases.
27

---

100
10"
Thus Posiiiv Rate
10
Thue Posiive Rate
10
BASE [1S]
(oum))
LIKA
10
BASU (ORES)
RMIA
(1S
10-44
10
10
10
10
10a
False Positive Race
False Positive Rare
(a) Online, K =
(b) Offline, K
Figure 5: Average ROC curves (10 runs) for the PubMed dataset with GCN target model.
10P
10
True Postive Rase
10-1
True Possive Rale Raae
10
10
100
(oum))
KOMAA [15]
G BASE (OUIS)
LIKA
[11]
10
10-3
10
10
10
10
10
10-
10-1
10
False
(a) Online,
(b) Offfine,
Figure 6: Average curves (10 runs)
Flickr dataset GAT as target model.
10
10-1
Thie Positve Rale
True Podiive Rale
20-2
10
G-BASE (num)
G- G-BASE Cours)
10-3
10-3
[13)
(13)
LJKA [11]
LJRA [11]
10
10
10
10
10
10
10
10'
Palse Posttive Rate
Palse Positive Rate
(a) Online, K
128
(b) Offline, K 64
Figure Average ROC curves (10 runs) for the Github dataset with GraphSAGE as target model.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We show that our attacks are competitive with previous state-of-the-art attacks in Section The asserted connection of our attack and the prior state-of-the-a attack RMIA is proven in Section 5.2.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
28

---

The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The paper explicitly discusses limitations in terms of the datasets in which the different methods are compared and selecting the decision threshold when the adversary does not have access to the ground truth.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well vell-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tes system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
The set of assumptions is stated within each theorem. We provide complete and carefully checked proofs of the theorems in the appendices provided in the supplemental ma- terial. All the theorems, lemmas, formulas, and proofs are numbered and cross-referenced.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
29

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide a clear description of the experimental setup in Section 6 of the main paper and Appendix A of the supplemental material. We provide a link to repository containing the code to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. . large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide link to a repository containing the code to reproduce our results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
30

---

Please see the NeurIPS code and data submission guidelines (https://nips.cm https//guuiieeeeooeeuuuuieeeesss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: gwwdgg / ctcips.cc/pbblee httpa///giideee/eeeuuuussseeeee http://oooSummmiiiiiooooom sii.iiiiiiiiiiiooiooooooo for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify all the training and test details, including the datasets, model architecture, performance metric, hyper-parameter tuning.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the ROC curves and extract the area under the curve, as well as the true positive rate at low false positive rate. These are suitable and typically used metrics in all existing membership inference attacks.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
31

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
The paper currently does include explicit details about the computational resources required; this will be provided in the supplemental material upon acceptance. The paper introduces new framework and computational resource details are not crucial for understanding or replicating the main contributions and their impact.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / //w/unnuurp...rr wwwwrip...pppbullleee hc.ppublii/tthhhcctueeeelelellll
Answer: [Yes]
Justification: The paper complies fully with the NeurIPS Code of Ethics, involving no ethical concerns misuse.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses positive socictal impacts by enhancing privacy and classical and graph-based learning scenarios. Although we design attacks, the purpose is to understand the vulnerability of trained models, which eventually assists the design of privacy-enhancing mechanisms. No negative societal impacts were identified.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
32

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not involve datasets models with high risks for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets and existing models used clearly cited with references and licenses properly respected.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA].
Justification: The paper does not introduce any new datasets, models, or code assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooeemmodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification: The research presented in this paper does not involve crowdsoureing human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The research does not involve human subjects and thus does not require IRB approvals.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
34

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
The research does not utilize large language models as part of its core method- ology.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https http://eeerppppeeeeee www.rrpp.cc/ooofeeeeeeceeecc wct/onnfeeences/222////////////e for what should or should not be described.
35


Reviews:
[{"review_id": "cOUPNQngEr", "reviewer": "Reviewer_L9uX", "summary": "This paper introduces BASE and G-BASE, two efficient approximations of Bayes-optimal MIA attacks for standard and graph data. Their method BASE matches the baseline performance with far fewer queries and the graph version also outperforms previous baselines. The work is theoretically sound with experiments, but only on small datasets, casting a doubt on real world scalability.", "questions": "1. Can this be verified on reasonably large datasets like ImageNet? Example tasks can be generation models trained on the dataset. \n2. 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.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is well written with solid grounding in theory and backed by rigorous empirical methods. \n- They introduce a novel unified framework for Graph-data and other forms of data.\n\nWeaknesses:\n- 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. \n- 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.", "was_revised": true, "final_justification": "Though not fully convinced by the rebuttals, I understand their point about the state of the field and existing standard datasets. \nIn that purview, I retain my borderline accept for this work.", "rebuttal": "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.\n\n## WEAKNESSES:\n\nNote: We provide a joint response to Reviewer’s Weaknesses 1 and 2, as they are closely related.\n\n*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.\"*\n\n### Response:\nOur 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. \n\nThe 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.\n\nRegarding 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.\n\n[1] Hayes et al. \"Strong Membership Inference Attacks on Massive Datasets and (Moderately) Large Language Models.\" arXiv, 2025.\n\n[2] Olatunji et al., \"Membership Inference Attack on Graph Neural Networks\" TPS-ISA, 2021.\n\n[3] Duddu et al., \"Quantifying Privacy Leakage in Graph Embedding,\" MobiQuitous, 2020.\n\n[4] He et al., \"Node-Level Membership Inference Attacks Against Graph Neural Networks,\" arXiv, 2021.\n\n[5] Shchur et al., \"Pitfalls of Graph Neural Network Evaluation,\" NeurIPS, 2018.\n\n[6] McAuley et al., \"Image-based Recommendations on Styles and Substitutes,\" SIGIR, 2015\n\n## QUESTIONS:\n\n*Q1. \"Can this be verified on reasonably large datasets like ImageNet? Example tasks can be generation models trained on the dataset.\"*\n\n### Response:\nBASE 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.\n\nWe 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. \n\n[7] Zarifzadeh et al., \"Low-cost high-power membership inference attacks.\", ICML, 2024.\n\n*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.\"*\n\n### Response:\nWe 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). \n\nMoreover, querying GNNs (our focus) is significantly cheaper than querying large generative image/video models.\n\nFinally, 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."}, {"review_id": "InqvHdBkhM", "reviewer": "Reviewer_g4At", "summary": "This paper proposes a novel and low-cost node-level membership inference attack for graph neural networks. The authors further extend their method to the i.i.d. data setting and establish a theoretical connection between their approach and existing methods. Experiments across six datasets demonstrate that the proposed method achieves comparable or superior performance to existing attacks under the same parameter configurations, while maintaining lower computational cost and higher robustness.", "questions": "This paper presents a promising and practical approach for membership inference, particularly on GNNs. The extensions to the i.i.d. setting and the theoretical justification of the proposed approximations are valuable contributions.\nHowever, I have a few concerns and suggestions for improvement:\n1.\tIn 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.\n2.\tIn 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.\n3.\tThe 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.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n⦁\tBetter or equal performance with existing methods but with lower cost.\nWeaknesses:\n⦁\tThe core idea of this paper is Bayes-optimal framework, which has been previously explored on MIAs, limiting the novelty.\n⦁\tWriting quality needs improvement for clarity and precision.", "was_revised": true, "final_justification": "Based on the additional experiments provided by the authors, I still choose to maintain my positive score.", "rebuttal": "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.\n\n## WEAKNESSES:\n\n*W1. \"The core idea of this paper is Bayes-optimal framework, which has been previously explored on MIAs, limiting the novelty.\"*\n\n### Response:\nWhile 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. \n\nWe 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.\n\nFinally, we formally prove the equivalence between our attack BASE and RMIA, providing a rigorous foundation for a widely-used state-of-the-art method. \n\nTogether, these contributions represent a significant advancement of both the theory and practice of MIAs.\n\n[1] Sablayrolles et al. \"White-box vs black-box: Bayes optimal strategies for membership inference.\" ICML, 2019.\n\n*W2. \"Writing quality needs improvement for clarity and precision.\"*\n\n### Response:\nWe 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.\n\n## QUESTIONS:\n\n*Q1. \"In Section 6, while the experiments are comprehensive, the analysis\nlacks depth. There should be more deeper discussion, for example, why the\nproposed methods perform better on some datasets but not on others, and\nwhy your methods have better robustness against mismatched adversarial\nassumptions.\"*\n\n### Response:\nWe 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:\n\nG-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:\n\n| | Average degree | Fraction of isolated nodes (%) |\n|----------|:----------:|:----------:|\n| Cora  | 1.9523  | 18.14 |\n| Citeseer | 1.3293 | 30.81  |\n| Pubmed | 2.2375 | 28.90 |\n| Flickr | 5.0215 | 1.63 |\n| Amazon-Photo | 15.4271 | 4.02 |\n\nThis 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. \n(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). \nWe 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.\n\nAs 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. \n\n[2] Carlini, Nicholas, et al. \"Membership inference attacks from first principles.\" SP, 2022.\n\n[3] Zarifzadeh et al. \"Low-cost high-power membership inference attacks\", ICML 2024.\n\n*Q2. \"In Section 4.3, several sampling strategies are proposed\nto approximate the Bayes-optimal rule. It would be helpful to clarify how\neach strategy influences performance, and which specific strategies are used\nin your experiments.\"*\n\n### Response:\nThe 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.\"\n\nIn 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:\n\n\"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.\nResults with MCMC sampling are presented in Appendix H.3.\"\n\nand another excerpt from Appendix H.3:\n\n\"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.\nHere, we evaluate and compare the impact of the sampling strategy on the attack performance of G-BASE.\nTable 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).\"\n\n\n\n*Q3. \"The organization of the paper could be improved.\nSections 2 to 5 could be made more concise to allow more space for in-depth\nexperimental discussion and analysis in Section 6.\"*\n\n### Response:\nWe 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."}, {"review_id": "CMjtSFYVDD", "reviewer": "Reviewer_CHe9", "summary": "This paper introduces BASE and G-BASE, two membership inference attacks (MIAs) for iid and node-level graph data, where an adversary aims to identify whether a specific data point is included in the training set of a given trained model. These methods are developed by approximating the Bayes optimal membership inference rule. The evaluation on common graph benchmarks shows that these methods work better or on par with the statistics-based methods like LIRA or RMIA, most importantly, the authors claim that the developed methods have a lower computational cost.", "questions": "Major concerns/questions:\n1. In the approximation of the integral (equation 8), $S_L$ function requires $\\tilde{M}$ and not $m_v$. It is unclear how $m_v$ is used here. Please clarify the substitution.\n2. In definition 2 of G-BASE attack, the dependence on index i in $\\tilde{M}$ and in $S_L$ appears to be missing. The current definition, although implemented and it seemed to work experimentally, clarification is needed on whether the sampling is correctly reflected in the current form. \n3. The posterior is approximated with its prior in line 218. How to pick an appropriate prior $p(\\phi \\mid \\mathcal{G})$? The choice is not trivial, and a discussion on it with practical justification is needed.\n4. It is not clearly explained how LIRA and RMIA (methods for iid data) are evaluated for graphs in the paper. \n5. Line 308: it is not clear why a different number of sampled graphs is chosen and not equal to the number of shadow models?\n6. Line 317: a new variable $\\alpha$ is introduced, but there exists no such variable in the G-BASE definition. What is this variable?\n7. From the results, it looks like there is no straight-forward dependence on $K$. Large $K$ is not necessarily enabling better performance. Given this observation, is there a strategy to choose $K$?\n8. The claim on the computational aspect of BASE and G-BASE is not substantiated by analysis (either theoretical or empirical). It is not immediately evident how BASE and G-BASE are computationally more efficient than other methods.\n9. On the experimental details: what proportion of nodes are used for training each benchmark? Does it have an effect on the data population pool assumption? Adding this detail (to Appendix A) would be helpful.\n\nMinor concerns (mainly to improve the paper quality):\n1. Acronyms like BASE, G-BASE, LIRA, RMIA, and GCN should be clearly defined at first use. Given that this paper introduces BASE and G-BASE, are these acronyms?\n2. Variable $\\alpha$ in line 317 is not defined.\n3. The AGGREGATE and UPDATE function in equation (1) should be further explained, especially for readers unfamiliar with GNNs. Adding references could be helpful.", "limitations": "The theoretically derived Bayes optimal rule is intractable and can only be approximately solved. This is not a major limitation, as is common in the literature.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Detailed comments are put under questions. Strengths and weakness are summarised below: \nStrengths\n1. Extending the Bayes optimal inference rule from [1]  to graphs is novel and important. The existing MIAs for graphs are only classifier-based methods. \n2. The evaluation is extensive on the most common graph benchmarks and GNNs.\n\n\nWeaknesses\n1. Paper clarity can be improved, specifically in the technical aspects as mentioned in the questions.\n2. The applicability of the baselines used for the analysis from the iid domain (LIRA and RIMA) to graphs is not clear.\n3. CRITICAL: There is a potential formatting issue in 228, violating double-blind policy (see formatting issue below). My current score does not account for this violation, and I will let AC/SAC/PC decide on it", "was_revised": true, "final_justification": "UPDATE: The review addressed all my concerns. Hence, I am increasing my score. I will leave the decision on formatting on AC and beyond", "rebuttal": "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.\n\n## WEAKNESSES\n\n### W1\nWe 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. \n\n### W2 and Q4.\nWhile 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. \n\nWhile 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.\n\nWe acknowledge that this adaptation was not clearly explained in the paper and will revise the manuscript to clarify this point.\n\n### W3.\nWe 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.\n\n## QUESTIONS\n### Q1.\nWe 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.\n\n### Q2.\nThere 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.\n\n### Q3.\nWe 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.\nIn 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.\n\nWe 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.\n\n### Q5.\nOur 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.\n\n### Q6.\nVariable $\\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.\n\nDue 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:\n\n\"**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.\"\n\nAppendix F clearly defines both settings and explains the introduction of $\\alpha$ in the offline setting. We copy part of the text here for reference:\n\n\"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[…]” \n\n(see Eq. 22 in App. F)\n\nTo improve clarity, we will explicitly add ``(see App. F)'' after mentioning $\\alpha$ in the main text in the revised version of the manuscript.\n\n### Q7.\n$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.\n\n[1] Carlini, et al. \"Membership inference attacks from first principles.\" SP, 2022.\n\n### Q8.\nDue 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.\n\n### Q9.\nExcept 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.\n\nThe 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. \n\nIn 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.\n\n## MINOR CONCERNS\n### MC 1.\nWe 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.”\n\nThe name BASE follows the same naming convention, but we did not define it explicitly. We will revise the manuscript and define all acronyms. \n### MC 2.\nSee our response to your Q6.\n### MC 3.\nWe will add a brief explanation of these functions and include an additional reference to improve clarity for readers less familiar with GNNs."}, {"review_id": "JEevEWJSJJ", "reviewer": "Reviewer_U2Mu", "summary": "This paper proposes a theoretically grounded and practical approach to membership inference attacks (MIAs) for both i.i.d. and graph-structured data. Building on a Bayesian decision-theoretic framework, the authors derive a Bayes-optimal inference rule for node-level MIAs on graph neural networks (GNNs), addressing a previously unresolved question in privacy auditing. To render the intractable Bayes-optimal rule usable in practice, the paper introduces BASE (for i.i.d. data) and G-BASE (for graph data) as efficient approximations. These methods outperform or match existing state-of-the-art approaches like LIRA and RMIA, while requiring significantly fewer computational resources. The authors also reveal that RMIA is a special case of BASE under specific conditions, thus offering a principled interpretation of RMIA.", "questions": "1. In Section 4.1, the adversary is assumed to know the full graph G. How realistic is this in practical scenarios, especially for large or proprietary graphs? Could the method be adapted to a setting with partial or noisy knowledge of G?\n2. While the paper claims BASE and G-BASE are more efficient than RMIA/LIRA, a direct analysis of computational cost (e.g., wall-clock time or FLOPs) is missing. Including such data would strengthen the practical contribution.\n3. The performance of G-BASE under different shadow model counts or sampling methods is briefly mentioned. Could the authors provide more systematic analysis or guidance on selecting these parameters?\n4. The work focuses on node-level MIAs for GNNs. Could the Bayesian framework be extended to edge- or graph-level MIAs? If so, how might the challenges differ?\n5. Given the probabilistic nature of the Bayes-optimal rule, have the authors explored confidence calibration of their predictions? This could have practical value in privacy auditing tools.", "limitations": "Partially addressed. While the authors acknowledge the intractability of the Bayes-optimal rule and propose efficient approximations, the discussion of potential negative societal impact (e.g., how such attacks may be misused) is limited. I encourage the authors to elaborate on possible misuse scenarios and mitigation strategies, especially in light of GDPR concerns.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The paper derives a novel Bayes-optimal MIA for graph-structured data, filling a theoretical gap in the literature. The generalization of from i.i.d. to graph settings is significant and well-justified.\n2. The proposed approximations BASE and G-BASE are computationally efficient and outperform existing methods in many settings, making them attractive for real-world privacy auditing.\n3. The paper is well-organized with clear definitions, formulations, and diagrams. The step-by-step derivation of the Bayes-optimal rule and approximations is particularly helpful.\n\nWeaknesses:\n1. The assumption that the adversary has access to the full graph G may limit the applicability in real-world scenarios, especially for GNN attacks. This assumption should be more thoroughly discussed or relaxed.\n2. The empirical performance of G-BASE may depend on hyperparameters such as the number of shadow models and sampling strategies. More discussion on robustness to such factors would be helpful.\n3. While the work has implications for data privacy, the broader ethical and societal implications (e.g., how adversaries might exploit such tools) are not sufficiently addressed.", "was_revised": true, "final_justification": "Based on previous comments and the author's response, I keep my score.", "rebuttal": "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.\n\n## WEAKNESSES\n### W1.\nSee response to your Question 1 below.\n\n### W2.\nSee response to your Question 3 below.\n\n### W3.\nWe 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.\n\nOur 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.\n\nWe will add a brief discussion to the camera-ready version to reflect this perspective more clearly.\n\n## QUESTIONS\n### Q1.\nWe agree that assuming the adversary has access to the full graph \n$\\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.\n\nIn 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.\n\nWe 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.\n\n[1] Carlini et al. \"Membership inference attacks from first principles.\" IEEE SP, 2022.\n\n[2] Zarifzadeh et al. \"Low-cost high-power membership inference attacks\", ICML 2024.\n\n### Q2.\nThank 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. \n\nTo 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.\n\nBASE 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, \nour 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].\n\nOn 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. \n\nDespite its higher cost, G-BASE remains a feasible and effective option for privacy auditing of GNNs, significantly outperforming baseline methods, including BASE.\n\nWe 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:\n\n| | Pubmed | Flickr |\n|----------|:----------:|:----------:|\n| **BASE**  | 0.0065  | 0.0898 |\n| **RMIA** | 0.4992  | 2.1735  |\n| **LiRA** | 2.3618 | 11.1613 |\n\nThe 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.\n\n### Q3.\nWe 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. \n\nIn 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.\nHowever, 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].\n\nRegarding 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:\n\n\"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.\"\n\nWe will clarify these points in the revised version of the paper to provide more practical guidance.\n\n### Q4.\nWe 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.\n\nExtending 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].\n\nIn 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.\n\n[3] Krüger et al. \"Publishing neural networks in drug discovery might compromise training data privacy.\" Journal of Cheminformatics, 2025.\n\n### Q5.\nWe 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.\n\n[4] Guo et al. \"On calibration of modern neural networks.\" ICML, 2017."}]

Author rebuttal:

Meta-review: This paper studies the problem of MIA in the node-level graph data setting. Following the prior Bayesian MIA framework, the authors develop more efficient MIA methods compared with existing methods.

The reviewers agree the problem considered in this paper is important, and proposed methods indeed work well. While concerns remain about task coverage, data size and scalability of the methods, the reviewers believe the paper advances MIA on graph data.

Therefore, I recommend the weak accept of the paper.
Decision: Accept (poster)