Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approach

Authors: hanyang  yuan
jiarong  xu
renhong  huang
mingli  song
chunping  wang
yang  yang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:13:33

Abstract: Graph neural networks (GNNs) have attracted considerable attention due to their diverse applications. However, the scarcity and quality limitations of graph data present challenges to their training process in practical settings. To facilitate the development of effective GNNs, companies and researchers often seek external collaboration. Yet, directly sharing data raises privacy concerns, motivating data owners to train GNNs on their private graphs and share the trained models. Unfortunately, these models may still inadvertently disclose sensitive properties of their training graphs (\textit{e.g.}, average default rate in a transaction network), leading to severe consequences for data owners. 
In this work, we study graph property inference attack to identify the risk of sensitive property information leakage from shared models.
Existing approaches typically train numerous shadow models for developing such attack, which is computationally intensive and impractical. To address this issue, we propose an efficient graph property inference attack by leveraging model approximation techniques. Our method only requires training a small set of models on graphs, while generating a sufficient number of approximated shadow models for attacks.
To enhance diversity while reducing errors in the approximated models, we apply edit distance to quantify the diversity within a group of approximated models and introduce a theoretically guaranteed criterion to evaluate each model's error. Subsequently, we propose a novel selection mechanism to ensure that the retained approximated models achieve high diversity and low error.
Extensive experiments across six real-world scenarios demonstrate our method's substantial improvement, with average increases of 2.7\% in attack accuracy and 4.1\% in ROC-AUC, while being 6.5$\times$ faster compared to the best baseline.

Main paper: 
 introduction: 
 Graph data, encapsulating relationships between entities across various domains such as social networks, molecular networks, and transaction networks, holds immense value [1] [2] [3] . Graph neural networks (GNNs) have proven effective in modeling graph data [4] [5] [6] , yielding promising results across diverse applications, including recommender systems [7] , molecular prediction [8, 9] , and anomaly detection [10] . While training high-quality GNN models may necessitate a substantial amount of data, graphs may be scarce or of low quality in practice [11, 12] , prompting companies and researchers to seek additional data from external sources [13] .However, directly obtaining data from other sources is often difficult due to privacy concerns [14, 15] . As an alternative, sharing models rather than raw data has become increasingly common [13] . Typically, data owners train a model on their own data and subsequently release it to the community or collaborators [16] [17] [18] [19] [20] . For instance, a larger bank may train a fraud detection model on its extensive transaction network and share it with partners, allowing them to use their own customer data to identify risks.Despite the benefits, this model-sharing strategy sometimes remains vulnerable to data leakage risks. Given access to the released model, one may infer sensitive properties of the data owner's graph, which are not intended to be shared. In the context of releasing a fraud detection model, if an adversarial bank can determine the average default rate of all customers in the transaction network, the data owner bank's financial status can potentially be revealed. Another example is releasing a recommendation model trained on a company's product network [21] . If a competitor can infer the distribution of co-purchase links between different products, he may determine which items are frequently promoted together and deduce the company's marketing tactics. Such attacks are possible because released models may inadvertently retain and expose sensitive information from the training data [22, 23] . We refer to such sensitive information related to the global distribution in a graph as graph sensitive properties, and we aim to investigate the problem of graph property inference attack.Previous property inference attacks [22] [23] [24] [25] primarily focus on text or image data, assuming models trained on different properties exhibit differences in parameters or outputs. For GNNs modeling graph data, the inherent relationships and message-passing mechanisms can magnify distribution bias [26] , making them more vulnerable to attacks. Although a few studies extend property inference to graphs and GNNs [20, 21, 27] , they typically involve creating shadow models that replicate the released model's architecture and are trained on shadow graphs with varying sensitive properties. The parameters or outputs of shadow models are used to train an attack model to classify the property of the data owner's graph. A major limitation of these attacks is the need to train a large number of shadow models (e.g., 4,096 models [22] , 1,600 models [27] ), resulting in significant computational cost and low efficiency.In this paper, we explore the feasibility of avoiding the training of numerous shadow models by designing an efficient yet effective graph property inference attack. Our key insight is to train only a small set of models and then generate sufficient approximated shadow models to support the attack. To this end, we leverage and extend model approximation techniques. For a given dataset and a model trained on it, when the training data changes (e.g., removing a sample), model approximation allows the efficient estimation of new model parameters for the updated dataset without retraining. This technique, often called unlearning [28] [29] [30] [31] , enables the efficient generation of multiple approximated shadow models from a single trained model. Specifically, given a small set of graphs and their corresponding trained models, we perturb each graph to alter sensitive properties (e.g., changing the number of nodes corresponding to high default rate users) and then apply model approximation to produce a sufficient number of approximated models corresponding to the perturbations, thereby reducing the total attack cost. Figure 1 illustrates our approach compared to the traditional attack.Nevertheless, achieving this goal presents several challenges. The first challenge is to ensure the diversity of approximated models, which provides a broader range of training samples for the attack model and enhances its generalization capability. To tackle this, we develop structure-aware random walk sampling graphs from distinctive communities and introduce edit distance to quantify the diversity of a set of approximated models. The second challenge is to ensure that the errors in the approximated shadow models are sufficiently small. Otherwise, these models may fail to accurately reflect differences in graph properties, thereby diminishing attack performance. To address this, we establish that different graph perturbations can lead to varying approximation errors, which offers a theoretical-guaranteed criterion for assessing the errors of each approximated model. Finally, we propose a novel selection mechanism to reduce errors while enhancing the diversity of approximated models, formulated as an efficiently solvable programming problem. Our contributions are as follows:• We propose an efficient and effective graph property inference attack that requires training only a few models to generate sufficient approximated models for the attack.• We propose a novel selection mechanism to retain approximated models with high diversity and low error, using edit distance to measure the diversity of approximated models and a theoretical criterion for assessing the errors of each. This diversity-error optimization is formulated as an efficiently solvable programming problem.• Experiments on six real-world scenarios demonstrate the efficiency and effectiveness of our proposed attack method. On average, existing attacks require training 700 shadow models to achieve 67.3% accuracy and 63.6% ROC-AUC, whereas our method trains only 66.7 models and obtains others by approximation, achieving 69.0% attack accuracy and 66.4% ROC-AUC.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: See abstract and § 1.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in 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 as long as it is clear that these goals are not attained by the paper. 
problem definition: 
 The scenario of a graph property inference attack first involves a data owner who trains a GNN model using his graph data, referred to as the target model and target graph in the following text. Once trained, the target model's parameters or output posterior probabilities can be released in communities [16, 18] . For example, the data owner can upload the pre-trained parameters to GitHub [17, 19] to facilitate downstream tasks. Or he may upload the posterior probabilities from a recommender system to a third-party online optimization solver [21] , such as Gurobi * . Collaborative machine learning is another potential attack scenario [20] . For instance, consider two banks aiming to collaboratively train a fraud detection model. While sharing raw transaction networks poses risks to privacy and commercial confidentiality, they can employ model-sharing strategies [13] .With access to the target model, curious users may launch inference attacks to obtain some sensitive properties of the target graph, which can reveal secrets not intended to be shared. For example, the ratio of co-purchase links between particular products in a product network may relate to the promoting tactics of a sales company, or the average default rate in a transaction network may reveal the financial status of a bank. Such confidential information may further impact business competition.In the rest of this section, we first define the privacy, i.e., the sensitive properties referred to in this work. Then, we introduce the knowledge of the attack. Finally, we formulate the problem of property inference attacks.Graph sensitive property. In this paper, we consider an attributed target graph where nodes are associated with multiple attributes. The sensitive property is defined based on one specific type of attribute, called the property attribute. Specifically, the sensitive property is defined as a certain statistical value of the property attribute's distribution. We consider two types of properties that the attacker may infer: (1) node properties, specified by the ratio of nodes with a particular property attribute value, and (2) link properties, specified by the ratio of links where the end nodes have particular property attribute values.Note that the property attribute can be either discrete or continuous. For instance, a node property defined on the discrete category attribute in a product network can be the ratio of co-purchase links between luxury items. An edge property defined on the continuous default rate attribute in a transaction network can be the average default rate of all customers. The inferred sensitive properties may reveal data owner's secrets such as commercial strategies; see [23, 32] for further discussion.Attacker's knowledge. The attacker's background knowledge is assumed to be as follows:• Auxiliary graph: We assume the attacker has an auxiliary graph from the same domain as the target graph but does not necessarily intersect with the latter. In practice, the auxiliary graph can be sourced from publicly available data or derived directly from the adversary's own knowledge. • Target model: We consider two types of knowledge on the target model: the white-box setting, where the adversary knows the architecture and parameters of the target GNN, and the black-box setting, where the adversary only knows the target GNN's output posterior probabilities.Property inference attack. Formally, let G tar denote the target graph. And let P(G tar ) denote the property value of G tar . Note that P can represent either node properties or link properties. Given that the attacker has an auxiliary graph G aux from the same domain as G tar , we define graph property inference attack as follows:Problem 1 (Graph property inference attack) Given the auxiliary graph G aux , and assume the attacker has either the white-box knowledge of the target GNN parameters or the black-box knowledge of target GNN's output posterior probabilities, the objective of the graph property inference attack is to infer the property P(G tar ) without access to it. Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: See Appendix A.6.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 in 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-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 on 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
methodology: 
 This section provides a detailed description of the proposed graph property inference attack. We start with an overview of our method and then delve into the technical aspects of model approximation. Finally, we describe how to ensure the diversity of approximated models while reducing their errors. The overall algorithm and complexity analysis are summarized in Appendix A.3.As shown in Figure 1 (a), given the auxiliary graph, the conventional approach is to first sample numerous shadow graphs, ensuring that graphs with different properties are adequately represented. Each is then used to train a shadow model with the same structure as the target model. Once trained, parameters (white-box) or output posterior probabilities (black-box) of shadow models are collected, along with the corresponding properties of shadow graphs. Finally, an attack model (e.g. linear classifier) is trained to classify properties based on parameters or posteriors. Since the number of shadow models is usually hundreds or thousands, their training can be computationally expensive.To mitigate this issue, our proposed attack method utilizes model approximation techniques as a substitute. We provide a illustration of our method in Figure 1(b): (1) Instead of numerous shadow graphs, we first sample only a few reference graphs.(2) On each reference graph, we train a reference model with the same architecture as the target model, and generate multiple augmented graphs by removing different nodes and edges.(3) By efficient model approximation, we obtain approximated models w.r.t to the augmented graphs.(4) We collect parameters or posteriors of all approximated models and train the attack model in a similar manner as previous attacks.Here, we mainly face two challenges: ensuring that the approximate error associated with augmentations is relatively small, and ensuring that the approximated models are sufficiently diverse. To address them, we derive a theoretical criterion for calculating approximation errors across different augmented graphs (see § 3.2) and design a diversity enhancement strategy in § 3.3.We proceed by introducing the techniques of model approximation, which include generating augmented graphs, obtaining approximated models, and conducting theoretical analysis for error criterion.Generating augmented graphs and identifying influenced nodes. First, we aim to ensure that multiple perturbations produce distinctive augmented graphs. This is essential because highly similar augmentations reduce the distinction in the corresponding graph properties and model features, providing minimal benefit to the overall attack. For this purpose, we propose removing both nodes and edges from the reference graph. Formally, Let the reference graph be denoted by G ref = (V, E) sampled from G aux , where V is the node set, E ⊆ V × V is the edge set. For one perturbation, we remove V R ⊂ V and E R ⊂ E to obtain the augmented graph G aug . In GNNs, the neighborhood aggregation makes the removal inevitably influence the state of other remaining nodes. Given a l-layer GNN, the influenced nodes of removing a single node v ∈ V R is the l-hop neighborhood of v, denote as N l (v). And the influenced nodes of removing a single edge e ∈ E R , connecting nodes v and u, is denoted as N l (e) = N l-1 (v) ∪ N l-1 (u) ∪ {v, u}. With these in mind, we next define the total influenced nodes for removing V R and E R . Definition 1 (Influenced nodes ) Given the removed nodes V R , removed edges E R and a l-layer GNN, the total influenced nodes V I is defined asEQUATIONNote that V I is exclusive of V R ; we omit the set difference for simplicity.Generating Approximated Models. Subsequently, we generate the approximated model based on the perturbation. While existing graph unlearning [29] [30] [31] 33] may offer potential solutions, they are either limited to specific model architectures or only support the removal of nodes or edges individually, making them unsuitable for direct application. To address this, we extend their mechanisms to suit our scenario. Let the reference model be parameterized by θ ref ∈ R m . In this paper, we consider cross-entropy loss as the loss function, and θ ref is obtained as follows:EQUATIONAfter removing V R and E R , directly retraining on G aug could yield a new model parameter θ aug :EQUATIONTo avoid training from scratch, we derive the approximation of θ aug by the following theorem.Theorem 3.1 (GNN model approximation) Given the GNN parameter θ ref on G ref , the removed nodes V R , removed edges E R and influenced nodes V I . Assume ℓ is twice-differentiable everywhere and convex, we haveEQUATIONwhere ∇ denote gradient, and ∇ 2 denote Hessian.L(θ ref ; G aug ) = v∈V /V R ℓ(θ ref ; v, E/E R ).The detailed derivation can be found in Appendix A.2.In practice, the Hessian may be non-invertible due to the non-convexity of GNNs. We address this by adding a damping term to the Hessian [34] .To reduce computation, we also follow [29] to convert the inverse Hessian calculation into quadratic minimization. See Appendix A.3 for complexity analysis.Analyzing the approximation error. Eventually, we aim to quantitatively assess the error in the approximated model, as this directly determines whether graph properties can be effectively reflected, thereby influencing the attack. To achieve this, we investigate how specific removal choices of V R and E R affect the approximation error in Eq. ( 4). Note that∇ v∈V /V R ℓ(θ; v, E/E R ) = 0 only when θ aug is the exact minimizer, thus the gradient norm ∥∇ v∈V /V R ℓ(θ; v, E/E R )∥ 2 can reflect the approximation error.The following theorem provides an upper bound on this gradient norm.Theorem 3.2 (Approximation error bound) Assume ℓ is twice-differentiable everywhere and convex,∥∇ℓ∥ 2 ≤ c 1 , ∇ 2 v∈V /V R ℓ(θ; v, E/E R ) is γ 1 -Lipschitz,the approximation error bound is given by:EQUATIONwhere | • | denotes the cardinality of a set, and δ(•, •) denotes the square of the number of nodes removed and influenced, given V R and E R . C denotes a constant depending on the GNN model, see Appendix A.2 for detail proof.Theorem 3.2 indicates that the error bound for the approximation is related to both the number of removed nodes and influenced nodes. Next, we demonstrate how this can serve as an error criterion to select augmented graphs that result in minimal approximation errors.Following the above, we detail the designed diversity enhancement strategy. To develop a wellgeneralized attack model capable of distinguishing different sensitive properties, we first apply a structure-aware random walk for sampling diverse reference graphs. We then propose a novel selection mechanism to ensure that multiple perturbations on the reference graphs further enhance diversity while considering the reduction of approximation error.Sampling diverse reference graphs. Inspired by community detection, where diverse communities are identified on a graph, we design a structure-aware random walk for sampling reference graphs. Specifically, we incorporate Louvain community detection [35] to partition the auxiliary graph into several similarly sized communities. During random walks, the starting nodes are chosen from different communities. And we assign different weights to neighboring nodes: w for those within the same community and 1 -w for those from different communities, where w ∈ [0, 1] is a hyperparameter. The transition probabilities are then obtained by normalizing these weights. This strategy encourages sampling reference graphs within distinct communities, thus boosting their diversity.Ensuring diverse augmented graphs. To ensure perturbations on reference graphs can enhance the diversity, we further design a perturbation selector. Based on § 3.2, it is easy to see that each approximated model can be considered as a result of the specific perturbation. Thus, improving the diversity of approximated models is essentially improving the diversity of augmented graphs. Formally, for each reference graph we generate k augmented graphs G aug = {G aug 1 , G aug 2 , . . . , G aug k } by randomly removing k different sets of nodes and edges. The diversity for G aug is defined as:Definition 2 (Diversity for G aug ) Given a set of k graphs G aug = {G aug 1 , . . . , G aug k },i , G aug j ) that measures the distance between G aug i and G aug j . The diversity of G aug is defined as the sum of all pair-wise graph distances in G aug , that is,k i=1 k j=1 d G aug i , G aug j .Since stochastic augmentations may not all contribute to total diversity, our objective is to select a diverse subset of G aug , namely, a subset of diverse perturbations to enhance the diversity of augmented models. However, it is important to note that solely maximizing diversity may lead to relatively large approximation errors, which may worsen the attack performance. Fortunately, utilizing the error criterion from Eq. ( 5), we can ensure that augmentations enhance diversity while minimizing total approximation error, which can be formulated as a quadratic integer programming task.Given k available perturbations, we aim to select q of them, such that the diversity among these selected is maximized while keeping the approximation error minimal. We here introduce decision variables x i ∈ {0, 1} to represent whether the i-th augmentation is selected. Let δ i represent the approximation error in the i-th augmentation (cf. Eq. ( 5)). The optimization problem is as follows:EQUATIONwhere ϵ is a constant that imposes the budget on the total approximation error of the selected q augmentations, ensuring that it does not exceed ϵ. Here, we select graph edit distance as the distance metric, which can be efficiently calculated since all k augmented graphs G aug are derived from one reference G ref . We utilize Gurobi Optimizer [36] , a state-of-the-art solver, to solve this quadratic integer programming problem, which is known for its efficiency and effectiveness.We summarize the overall algorithm of our attack in Algorithm 1. Steps 1-2 outline the structureaware random walk for sampling reference graphs, steps 5-12 detail the perturbation selector, with step 10 calculating the error criterion in Eq. ( 5). Finally, in step 16 we train the attack model. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
experiments: 
 In this section, we evaluate the performance of the proposed attack method by addressing the following three research questions:• RQ1: How efficient and effective is our method on various graph datasets?• RQ2: How do different factors influence the performance of our method?• RQ3: How applicable is our method in different scenarios?Datasets and sensitive properties. We conduct property inferences on three real world datasets: Facebook [37] , Pubmed [38] , and Pokec [39] . Appendix A.4 details the datasets and properties.• Facebook and Pokec are social networks where nodes represent users and edges denote friendships. Following [21] , we select gender as the property attribute, set node property as whether the male nodes are dominant, and edge property as whether the same-gender edges are dominant. • Pubmed is a citation network where nodes are publications and edges are citations. We select the keyword "Insulin" (IS) as the property attribute. Node property is whether publications with "IS" are dominant. Edge property is whether citations between publications with "IS" are dominant. All used properties are summarized in Table 1 .Training and testing data. For fairness, we evaluate our method and baselines on the same target graphs. To ensure there is no overlap between the target graph and the auxiliary graph, for each dataset we first use Louvain community detection to split the original graph into two similarly sized parts. One part is used as the auxiliary graph, and the other part is used to sample multiple target graphs. Sizes and numbers of reference graphs (our method), shadow graphs (baselines), and target graphs are provided in Appendix A.4.Target GNN. For target GNN, We use a widely recognized GNN model, GraphSAGE [40] , configured as per [21] with 2 layers, 64 hidden sizes, and 1,500 training epochs with an early stop tolerance of 50. The Adam optimizer is used with a learning rate of 1e-4 and a weight decay of 5e-4.Implementation details. For the attack model, We use a linear classifier with the deepest trick [41] ; For hyper-parameter settings, we perform grid searches of reference graphs' numbers in (0, 100] (step size 25), and augmented graphs' numbers in (0, 10] (step size 2), across all datasets. Experiments are repeated 5 times to report the averages with standard deviations. See appendix A.4 for more details.Our codes are available at https://github.com/zjunet/GPIA_NIPS.Baselines. We adopt four state-of-the-art baseline models to compare against the proposed attack model: (1) GPIA [21] : An attack method designed for graphs and GNNs in both white-box and blackbox settings, following the traditional attack framework. (2) PIR-S/PIR-D [22] : Two permutation equivalence methods designed for white-box attacks, PIR-S using neuron sorting and PIR-D using set-based representation. (3) AIA [42] : Property inference method based on attribute inference attack, which first predicts the property attribute based on embeddings/posteriors and then predicts property, suitable for both white-box/black-box attacks. See Appendix A.4 for details. We first focus on white-box settings and evaluate the accuracy and ROC-AUC for effectiveness and runtime for efficiency. Note that the reported runtime throughout this work encompasses the entire attack process for both the proposed method and baselines, starting from sampling the reference (shadow) graphs to inferring the properties of the target graphs. Table 2 presents the average accuracy and runtime of the proposed attack method compared to other baseline methods on the six aforementioned sensitive properties. We provide the corresponding standard deviations and ROC-AUCs results in Appendix A.5. The results reveal several key insights: (1) Traditional attacks incur significantly high runtime. The slight differences mainly depend on the different strategies in their attack models. (2) PIR-D achieves better accuracy among the baselines, possibly due to their consideration of permutation equivalence. AIA shows lower performance, which may be because of their limited ability to conduct attribute inference, thus affecting the classification of properties. ( 3)The proposed attack model outperforms all baseline methods across all datasets, achieving an average increase of 2.7% in accuracy and being 6.5× faster compared to the best baseline, demonstrating its remarkable efficiency and efficacy. The significant margin by which our method outperforms the baselines is primarily due to our specific mechanisms that ensure diversity in both reference and augmented graphs, which are essential for training a robust attack model. In contrast, conventional attacks lack such designs for shadow graph diversity, resulting in sub-optimal performance.Ablation study. To ensure effectiveness, our method includes two main mechanisms: sampling diverse reference graphs and selecting diverse augmented graphs. Here, we conduct ablation studies to demonstrate their necessity, including four variants: (1) w/o structure: We discard structure-aware sampling and use simple random walks to sample reference graphs. (2) w/o selector: We discard the augmentation selector and use random removal to obtain augmented graphs. (3) w/o error: In the augmentation selector (cf. Eq. ( 6)), we ignore the approximation error and only select augmentations that maximize diversity. (4) w/o diversity: We ignore diversity in the augmentation selector (cf. Eq. ( 6)) and only select augmentations that minimize the approximation error. Figure 2 (a) shows the attack results on Facebook's node property. Notably, the complete model consistently surpasses the performance of all variants, showing the effectiveness and necessity of simultaneously sampling diverse reference graphs and selecting diverse augmented graphs.Hyper-parameter analysis. We next evaluate the impact of two important hyper-parameters on our method: (1) the number of reference graphs and (2) the number of selected augmented graphs. Both directly affect the diversity of approximated models. We tune the number of reference graphs among {25, 50, 75, 100} and the number of selected augmented graphs among {2, 4, 6, 8, 10}. The results in Figure 2 (b) and 2 (c) show that as both hyper-parameters increase, the attack performance initially improves and then stabilizes. This indicates that a relatively small number of reference graphs and augmented graphs are sufficient to ensure diversity, thereby maintaining good attack performance. To test the applicability of our method, we evaluate its performance under various conditions, including scenarios with black-box adversary knowledge, on different types of GNN models, on large-scale graph datasets, and when the target and auxiliary graphs are distinct.Performance on black-box knowledge. In the black-box setting, we use model outputs, specifically posterior probabilities, to train attack models for our method and baselines. Since PIR-D and PIR-S only support white-box settings, we included another state-of-the-art black-box attack, PIA-MP [20] , as detailed in Appendix A.4. The results on Facebook's node property in Figure 2 (d) show that our method improves accuracy by 11.5% compared to the best baselines while being 7.3× faster. Performance on other GNNs. We conduct property inference attacks on other three fundamental GNNs: GCN [43] , GAT [44] , and SGC [45] . For GCN and GAT, hyper-parameters are configured according to [21] , while for SGC, we set the number of hops to 2. We report the attack accuracy and runtime of our method alongside other baselines on Facebook's node property, as illustrated in Figure 3 (a)-(c). It is observed that the overall attack accuracy for SGC is comparatively lower, potentially due to the SGC model's inherent limitations in capturing property information effectively. Moreover, our method consistently achieves the highest accuracy, also demonstrating a runtime that is 4.4× faster on GCN, 4.0× faster on GAT, and 4.3× faster on SGC compared to the best baseline.Performance on scalability. We further conducted property inference attacks on a large-scale graph dataset, Pokec-100M, which contains 1,027,956 nodes and 27,718,416 edges. This graph is sampled from the original dataset [39] by retaining nodes with relatively complete features. We targeted the same node property as in the Pokec dataset, with the number of nodes in the reference graphs, shadow graphs, and target graphs set to 52,600, 50,000, and 50,000, respectively. All other settings remain consistent with previous experiments. We compare the attack accuracy and runtime of our method against other baselines. As shown in Figure 3 (d) , conventional attacks incur significant computational costs on this dataset, whereas our method is 10.0× faster. Additionally, our attack accuracy is significantly higher than those of the baselines.Performance with distinct target and auxiliary graphs. In the above experiments, the target and auxiliary graphs are splits of the same original graph. However, in real-world scenarios, this assumption may not hold. Therefore, we evaluate the performance of our attack under a more practical condition, where distinct graphs (from the same domain) are used as the target and auxiliary graphs. Specifically, we select Facebook and Pokec, as they are both social networks, and consider two cases: using Facebook as the target and Pokec as the auxiliary graph, and vice versa. Since the feature dimensions of these two datasets differ, the parameters of the approximated model and the target model are not directly compatible, so we apply PCA dimension reduction to align the parameters. Table 3 reports the attack accuracy and runtime. We observe that (1) the overall attack performance decreases, potentially due to the loss of property information embedded in model parameters during parameter alignment, and (2) our model consistently achieves the best performance with significant speed-ups, demonstrating its effectiveness in a more practical scenario. 
literature review: 
 Property inference attack. The concept of property inference attack is first introduced by [23] , demonstrating the leakage of sensitive properties from hidden Markov models and support vector machines in systems like speech-to-text. Building on this, attacks on various machine learning models are studied, including feed-forward neural networks, convolutional neural networks, and generative adversarial networks [22, 25, 32, 46] . Some works also consider multi-party collaborative learning scenarios [20, 24] or incorporate data poisoning [32, 47] . Specifically, [47] proposes an efficient attack based on distinguishing tests, achieving faster performance than traditional shadow training. Their setting differs from ours by the additional adversarial capability of data poisoning. Recently, with the increasing use of graphs and GNNs, security and privacy concerns are emerging [48] [49] [50] [51] . While efforts have been made to investigate property inference attacks on GNNs [20, 21, 27] , they follow the shadow training framework, which requires training a relatively large number of shadow GNN models, leading to high computational costs and reduced feasibility [47] . [52] assumes access to the embedding of whole graphs and targets at graph-level properties, which is beyond our scope. [29, 31, 53, 54] or Newton update [30, 33] . Except for [54] , these methods are utilized in the context of graph unlearning. Studies [30, 33, 54] explore model approximation for edge or node removal and analyze the corresponding approximation error bounds, yet they are limited to specific model architectures (e.g., simple graph convolution, graph scattering transform). Further efforts [29, 31] extend model approximation to generic GNNs. [29] introduces a framework for edge unlearning, while [31] proposes a general unlearning framework for removing either nodes, edges, or features individually. Our model approximation differs from above by enabling the simultaneous removal of nodes and edges across generic GNN architecture. A concurrent work [53] addresses a similar model approximation as our attack; however, the additional theoretical assumptions could fail when removing a combination of nodes and edges, and their corresponding solution may significantly compromise the efficiency. Other studies [55, 56] also employ the graph shard approach. However, they may have poor efficiency in batch removal, which involves multiple retraining of sub-models. 
conclusion: 
 In this paper, we focus on the problem of graph property inference attacks. We utilize model approximation to efficiently generate approximated models after initially training a small set of models, which replaces the costly shadow training in traditional attacks. To overcome the challenge of ensuring the diversity of approximated models while reducing the approximation error, we first derive a theoretical criterion to quantify the impact of different augmentations on approximation error. Next, we propose a diversity enhancement strategy, including a structure-aware random walk for sampling diverse reference graphs and a selection mechanism to retain optimal approximated models, utilizing edit distance to measure diversity and the theoretical criterion to assess approximation error. The retained approximated models are finally used to train an attack classifier. Extensive experiments across six real-world scenarios demonstrate our attack's outstanding efficiency and effectiveness. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: See Appendix A.7.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 or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This work does not involve such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to usage guidelines or 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: See the code link in implementation details and citations.Guidelines:• The answer NA means that the paper does not 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 a 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. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: The main notations can be found in the following table. Given the GNN parameter θ ref on G ref , the removed nodes V R , removed edges E R and influenced nodes V I . Assume ℓ is twice-differentiable everywhere and convex, we haveEQUATIONwhere ∇ denote the gradient, and ∇ 2 denote the Hessian.Proof. Let L(θ; G aug ) = v∈V /V R ℓ(θ; v, E/E R ) denote the loss function of G aug at θ, by one step newton update of L, the approximation of θ aug is:EQUATION)Let V UI denote the uninfluenced node set, i.e.,EQUATIONGiven ∇ v∈V ℓ(θ ref ; v, E) = 0, we haveEQUATION)AndEQUATIONwhich completes the proof. □Assume ℓ is twice-differentiable everywhere and convex, ∥∇ℓ∥ 2 ≤ c 1 , ∇ 2 v∈V /V R ℓ(θ; v, E/E R ) is γ 1 -Lipschitz, the error bound for the approximation error is given by:EQUATIONwhere | • | denotes the cardinality of a set, and δ(•, •) denotes the number of nodes removed and influenced, given V R and E R . C is a constant depending on the GNN model.Proof. Firstly, we consider an empirical loss for the reference model, which consists of a crossentropy and a L 2 -regularization:EQUATION)where CE(•, •) represents the cross-entropy, and we omit the ground truth for simplicity. λ > 0 denotes the L 2 -regularization.Let G(θ) = ∇ v∈V /V R ℓ(θ; v, E/E R ), H 0 denote the Hessian of v∈V /V R ℓ(θ ref ; v, E/E R ),and letEQUATION)By Taylor's Theorem, we haveEQUATIONwhere H η denotes the hessian atEQUATIONEQUATION)Assume the Hessian ofEQUATION)Then we haveEQUATIONEQUATIONComplexity of generating approximated models. As the computation of gradients can be efficiently handled by the PyTorch Autograd Engine, the primary operation is solving the inverse of the Hessian (cf. Eq. ( 4)). To mitigate the high computational cost, we follow [29] in converting the inverse computation into finding the minimizer of a quadratic function, resulting in an approximated solution. By leveraging efficient Hessian-vector products and the conjugate gradient method, this can be solved with time complexity of O(t|θ|), where |θ| denotes the number of parameters, and t represents the number of iterations in conjugate gradient method.Training algorithm. The training algorithm for our attack is summarized in Algorithm 1.Details of datasets. The statistics of the datasets used in this work are summarized in Table 5 . [38] : This dataset includes 19,717 scientific publications related to diabetes, with a citation network of 88,648 links. Each publication is described by a TF/IDF weighted word vector from a dictionary of 500 unique words, such as male, female, children, cholesterol, and insulin. The target GNN's task is to classify the topic categories of the publications.Algorithm 1 Overall algorithm for the proposed attack.Input: Auxilary graph G aug , target model's parameters or posterior probabilities. Number of reference graphs r, number of perturbations k, number of selected augmented graphs q, weight w for sampling reference graphs. Output: The inferred sensitive property P(G tar ) of the target graph G tar .1: Partition G aug into multiple communities using Louvain community detection. 2: Sample r reference graphs using the proposed structure-aware random walk, with weight w. Train reference model θ ref .∅ → G aug , ∅ → Errors, ∅ → Perturbs.for i in 1, . . . , k doRandomly select a set of nodes V R and a set of edges E R from G ref .Add G aug i into G aug . 9:Add (V R , E R ) into Perturbs.10:Compute the approximation error criterion in Eq. ( 5), and add it into Errors.11:end for 12:Solve the optimization problem in Eq. ( 6), select q perturbations.13:Calculate the q approximated models by Eq. ( 4).14:Save the q parameters (or posterior) and the q properties of the selected augmented graphs. 15: end for 16: Train an attack model based on the r • q parameters (or posterior) and properties, classify P(G tar ) of the target graph G tar .• Pokec [39] : This online social network dataset is from Slovakia. Each node has anonymized features such as gender, age, and hobbies. We follow [21] to sample nodes with relatively complete features, resulting in a graph with 40,478 nodes and 531,736 edges, using gender, age, height, weight, and region as node features. The target GNN's task is to classify whether a user's all friendships are public.Details of sensitive properties. For each dataset, we design one node property and one link property to be targeted in our attacks. For Facebook and Pokec we select gender as the property attribute. For PubMed, we select the keyword "Insuli" as the property feature, as it has the highest TF-IDF weight. These properties are summarized in Table 1 .Statistics of reference, shadow, and target graphs. The sizes and numbers of reference graphs we use are summarized in Table 6 . For all baselines, we follow the settings specified in [21] to sample shadow graphs: the size of each shadow graph is 20%, 25%, and 30% of Pokec, Facebook, and Pubmed, respectively, and the number of shadow graphs is 700 for all datasets.For target graphs, we sample 300 shadow graphs for each dataset; the size of each shadow graph is 20%, 25%, and 30% of Pokec, Facebook, and Pubmed datasets, respectively. To ensure fairness, we evaluate our method and baselines on the same target graphs.More implementation details. All experiments are conducted on a machine of Ubuntu 20.04 system with AMD EPYC 7763 (756GB memory) and NVIDIA RTX3090 GPU (24GB memory). All models are implemented in PyTorch version 2.0.1 with CUDA version 11.8 and Python 3.8.0.The attack model is trained for 100 epochs with a learning rate of 1e-3 and a weight decay of 5e-4. We use cross-entropy loss as the loss function and Adam optimizer.Baselines for white-box setting.• PIR-S [22] : A property inference attack considering permutation equivalence in feed-forward neural networks, using node permutations on the hidden layers of a fully connected neural network. • PIR-D [22] : Similar to PIR-S, permutation equivalence is achieved by ensuring all permutations of any layer have the same set-based representation.Baselines for black-box setting.• PIA-MP [20] : An attack method designed for multi-party machine learning. The primary difference between PIA-MP and GPIA is that in the former, all shadow models (as well as the target model) are queried on a fixed dataset to obtain output posterior probabilities.Baselines for both settings.• GPIA [21] : A method designed for graphs and GNNs in both white-box and black-box settings, following the traditional attack framework. The inferred properties include node properties and link properties. • AIA [42] : We conduct an attribute inference attack that predicts the property attributes by accessing the parameters or posteriors. We then evaluate the property inference performance based on the predicted values of the property attributes.A.5 More experiment results Standard deviations for Table 2 . Table 7 reports the standard deviations corresponding to the average accuracies in Table 2 .ROC-AUC results. We also report the ROC-AUCs of the proposed attack method compared to other baseline methods on the six sensitive properties, as shown in Table 8 . The results demonstrate that our model can consistently achieve the best ROC-AUC result, confirming its notable effectiveness. In this work, we consider two settings: white-box and black-box, which encompass many real-world scenarios. However, stricter cases exist where the attacker can make only a limited number of queries or access only model predictions (i.e., classification results). We acknowledge that our methoddoes not yet address these cases. Additionally, some studies explore scenarios where attackers have enhanced capabilities, such as data poisoning. We leave the investigation of efficient attacks under these conditions for future work.While the proposed method is designed to infer properties of specific graph data, our primary objective is to raise awareness of the privacy and security concerns associated with GNNs and to encourage the implementation of protective measures in model design. Traditional property inference methods are often inefficient, and despite efforts to illuminate potential threats, less practical attack scenarios may not receive adequate attention. Nonetheless, the privacy risks persist. We seek to bring this threat to the forefront and advocate for the adoption of more robust protective measures.NeurIPS Paper ChecklistJustification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 


Decision: This paper proposes an efficient property inference attack on graph neural networks (GNNs). The proposed method achieves the SOTA attack performance. The paper is well-written and has provided theoretical support. Most of the concerns from the reviewers have been addressed by the authors' rebuttal. Therefore, I recommend accept.

Reviews: review: paper_summary: paper_summary: This paper proposes a more efficient property inference attack on graph neural networks (GNNs). Particularly, it uses model approximation methods to reduce the number of shadow models that needs to be trained by the graph property inference attack. Here only a limited number of shadow models are trained from scratch while model approximation method is used to generate other approximated shadow models without training them. Theoretical upper bounds for the approximation error are also provided.
strength_weakness: strength_weakness: 1.	How scalable is this attack for larger datasets? Current experiments are limited. Please perform the attack on larger datasets from the OGBN dataset (ArXiv, Products)
2.	How well does this scale for other GNNs? Please evaluate with other GNN models.
3. Fig. 1 is confusing. Please update it to clearly show the difference between the proposed approach and the existing attacks.
questions: questions: Please refer to the weaknesses.
limitations: limitations: Sufficiently addressed.
paper_summary: paper_summary: This paper delivers an effective way to improve the efficiency of property inference attacks for GNNs. Instead of training numerous shadow models, the authors propose to train a few reference models and use an efficient approximation method to obtain other shadow models trained on slightly augmented shadow graphs. Experimental results show that the proposed property inference attack achieves better performance in a shorter time.
strength_weakness: strength_weakness: - The scope and significance of this paper are somewhat limited. The main contribution of this paper is to improve the efficiency of a specific inference attack model. It would be helpful to provide more discussions on the new attack algorithm, e.g., insights on defending against the new attack method.
- The technical novelty is limited. In my opinion, the technical part of this paper is pretty much a certified graph unlearning method, which has been studied in previous literature [1,2,3,4]. I don't find a distinct improvement or new contribution of the technical part compared with [1,2,3,4]. 
- The inverse Hessian in influence computation is seen as highly consuming. It would be helpful to add some complexity analysis of the algorithm. 

[1] Wu, Kun, et al. "Certified edge unlearning for graph neural networks." KDD 2023.

[2] Pan, Chao, Eli Chien, and Olgica Milenkovic. "Unlearning graph classifiers with limited data resources." TheWebConf 2023.

[3] Chien, Eli, Chao Pan, and Olgica Milenkovic. "Efficient model updates for approximate unlearning of graph-structured data." ICLR 2023.

[4] Wu, Jiancan, et al. "Gif: A general graph unlearning strategy via influence function." TheWebConf 2023.
questions: questions: The theoretical analysis still relies on the convexity assumptions. To satisfy the assumptions, it would be feasible to use a linearized reference model. It is not clear which type of GNN is used as the reference GNN.
limitations: limitations: The authors have included detailed discussions on the societal impact of their work.
paper_summary: paper_summary: The paper introduces an improved method for conducting property inference attacks on graph neural networks (GNNs), particularly focusing on reducing the computational overhead associated with traditional approaches that rely on numerous shadow models. The authors propose a model approximation technique to generate a sufficient number of approximated models for attacks, without the need for extensive retraining. They introduce a diversity-enhancing mechanism to ensure the effectiveness of the approximations. Experiments demonstrate notable improvements in attack accuracy and efficiency compared to existing methods, validating the proposed approach's effectiveness and efficiency.
strength_weakness: strength_weakness: - Lack of details and certain explanations
- Weak experimental settings
questions: questions: - This paper is well-structured and well-written. I particularly appreciate the authors' efforts in providing thorough theoretical explanations and introducing innovative approaches. Replacing the training of numerous shadow models with model approximation is a significant and impactful contribution, effectively enhancing the efficiency of general property inference attacks.

- This paper assumes that the target and auxiliary graphs are splits of the same original graph, which is an impractical assumption in real-world scenarios. It would strengthen the paper's applicability if the authors used distinct network graphs (yet from the same dimain) for the target and auxiliary graphs.

- When comparing training efficiency with state-of-the-art methods, it is unclear whether the time required to generate diverse approximated models and calculate error is included. Including such details would enhance the transparency and reliability of the comparisons.

- While the paper presents improvements over baselines, it does not thoroughly discuss why the proposed method might outperform baselines by a big margin. Although it is clear that using a few approximated models in place of hundreds of shadow models contributes to efficiency, the reasons why it is much more effective than the baselines need to be further discussed.

- The choice of property attributes inferred in this study (e.g., # male users > # female users, or # publications with "IS" > # publications without "IS") seems kind of limited. The significance of this work would be enhanced if the authors expanded their experiments to include the inference of a broader variety of node or link properties such as the portion of different kinds of nodes or links. 

- I would be pleased to increase my score if the authors address these issues, which would substantially enhance the paper's contribution to the field.
limitations: limitations: see questions

Comments: comment: We are happy to hear that our response was helpful. Thank you for your prompt feedback and recognition.
We are happy to hear that our response was helpful. Thank you for your prompt feedback and recognition. We will revise our paper according to your suggestions.
As we are nearing the end of the discussion phase, we would like to kindly inquire if you have any remaining questions about our paper. We would appreciate any feedback and would be glad to discuss it further.
I thank the authors for providing further clarifications. Most of my concerns are addressed. It would be great if the authors could add the discussions in the rebuttal phase to the revised paper.
We apologize for any confusion caused. We want to clarify that the proposed error estimation does not accelerate the model approximation itself but rather speeds up the overall attack process. Specifically, in our attack framework, we need to select augmented graphs that incur relatively lower approximation errors, enabling a more effective attack (as shown in our ablation study). The efficiency we refer to is in this selection step. Since we need to measure the error for each augmented graph, the error measurement should be straightforward and easy to compute. Therefore, we introduce a new error bound in Theorem 2, which supports the removal of both nodes and edges. This bound is then used as an efficient error estimation to select augmented graphs.
 
Upon careful review, we found that the IDEA method also derived a similar error bound. However, it involves the term of the inverse Hessian (Eq. (16) of [1]),  which is more complex and cannot be easily computed for all augmented graphs, making it unsuitable for our selection step.

In summary, our goal is not to achieve faster model approximation, but rather to use our error bound to help efficiently select data, which in turn makes the overall attack process faster.

[1] Dong, Yushun, et al. "IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks." KDD 2024.
I thank the authors for their rebuttal. I am increasing my score to 5.
I thank the authors for their further response. I agree with the first point about the shortcomings of the IDEA method, but I don't get the difference between the two methods in the inverse Hessian computation step. In addition, the computation of the inverse Hessian is not claimed to be an original contribution by this work. Nevertheless, it is true that IDEA was released recently and can be seen as a concurrent work, so it is not a big deal.

I suggest the authors add more analyses and discussions on the efficiency of the proposed model approximation part. In comparison, Theorem 2 is not quite informative here as the advantage of the proposed model approximation compared with previous graph unlearning methods is its efficiency. If more details are added, I would like to further raise my score.
Thank you for bringing this work to our attention. We note that this work was published online in July of this year, which was subsequent to the submission of our paper. Therefore, we did not discuss it in our initial version. After a thorough review of this paper, we have identified two key aspects where our approach differs significantly:

(1) The approach in [1] relies on additional theoretical assumptions that impact the efficiency of model approximation, making it less suitable for our efficiency requirements. Specifically, they define different affected node groups based on the type of unlearning requests (e.g., node removal, edge removal), with the assumption that these groups do not overlap. When removing a mix of nodes and edges, this assumption may fail. To address this, they split the removal into multiple sets, each meeting the non-overlapping requirement, and perform the unlearning processes on these sets sequentially. This approach incurs significantly higher computational costs; for instance, if the removal is divided into five sets, five separate unlearning processes are required sequentially. In contrast, our approach groups nodes simply into influenced set and removed set, requiring only one unlearning process per removal, which ensures greater efficiency.

(2) We employ a different error estimation approach. Specifically, the error estimation proposed in [1] supports their certified unlearning proof, which involves the more complex computation of the inverse Hessian. This could significantly compromise the speed of selecting removals in our attack. In comparison, our error estimation can be computed directly based on the removal and graph structure, allowing for a more efficient attack.

[1] Dong, Yushun, et al. "IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks." KDD 2024.
I thank the authors for their further clarification which helps strengthen the contributions of this work. However, I still think the technical novelty of the model approximation part (which also means the theoretical contribution) is somewhat limited. The mentioned simultaneous removal of nodes, edges, and features and removal for various GNN architectures seem also to be covered by existing studies [1]. Further comparison and clarification would be helpful. Based on the current response, I am willing to improve my score to 4.

[1] Dong, Yushun, et al. "IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks." KDD 2024.
Dear Reviewer,

We appreciate your recognition of the importance of our work and the time you took to provide a detailed review. We would like to confirm that we have addressed all your concerns about our submission. If there is anything more we can do to help you in evaluating our paper, please don't hesitate to let us know.

Best regards, Authors
Dear Reviewer,

Thank you for your review and comments. In our rebuttal, we made special efforts to clarify the distinctions between our approach and existing graph unlearning methods, provided additional discussions on our attack algorithm, and enhanced our technical details. We would greatly appreciate any feedback on any existing or new points we may not have covered, and we would be glad to address or discuss them further.

Best regards, Authors
Dear Reviewer,

Thank you for your review and comments. We hope our rebuttal and additional evaluations have effectively addressed your primary concerns regarding our paper. We would greatly appreciate any feedback on any existing or new points we may not have covered, and we would be glad to address or discuss them further.

Best regards, Authors