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 2024 poster (2024)
Keywords: graph neural network
property inference attack
efficiency
Primary area: privacy

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.

Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approach
Hanyang Yuan 12,445, .Jiarong Xu²* Renhong Huang
Mingli Song" 1441, Chhnping Wang?, Yang Yang'
'Zhejiang University, FFudn University. Finvolution Group 4 Hangzhou High-Teck Tech Zone (Binjiang) Institute of Blockchain and Data Security (yuanhanyang, renh2, brooksong, yangya/ezju. edu. cn uudrongxu@fudan edu. cn, wangchumpingO22xxiyyyccom
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 train GNNs their private graphs and share the trained models. Un- fortunately, these models may still inadvertently disclose sensitive properties their training graphs (e.g., average default rate in transaction network), leading to severe consequences for data owners. In this work, we study graph property inference attack 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 lever- aging model approximation techniques. Our method only requires training small set of models on graphs, while generating sufficient number of approximated shadow models for attacks. To enhance diversity while reducing errors in the ap- proximated models, we apply edit distance to quantify the diversity within a group of approximated models and introduce theoretically guaranteed criterion evalu- ate each model's error. Subsequently. we propose 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 s substantial improvement, with average increases of 2.7% in attack accuracy and 4. 4.1% 1% in ROC-AUC, while being 6.5% faster compared to the best baseline.
Introduction
Graph data, encapsulating relationships between entities across various domains such as social networks, molecular networks, and transaction networks, holds immense value [+3]. Graph neural networks (GNNs) have proven effective in modeling graph data (4,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 substantial
amount of data, graphs may be scarce or of low quality in practice [1] 12], prompting companies
and researchers to seek additional data from external sources [1
Thii work was done when author was a visiting student at Fudan University. State Key Laboratory of Blockchain and Security, Zhejiang University. Conresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

However, directly obtaining data from other sources is often difficult due to privacy concerns [4 [5]. As an alternative, sharing models rather than raw data has become increasingly common [3] Typically, data owners train model on their own data and subsequently release it to the community or collaborators [16-20]. For instance, a larger bank may train 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 '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 's financial status can potentially be revealed. Another example is releasing a recommendation model trained on a company's product network [2T). 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 '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 sensifive properties, and we aim to investigate the problem of graph property inference attack.
Previous property inference attacks 22 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-passingg mechanisms can magnify distribution bias (26), making them more vulnerable to attacks. Although a few studies extend property inference to graphs and GNNs [1 27). they typically involve creating shadow models that replicate the released model's sss 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 '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 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,31), enables the efficient generation of multiple approximated shadow models from single trained model. Specifically, given 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 T illustrates 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 coreticallguraatteee 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 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.
2

---

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. 37.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.
2 Problem Definition
The scenario of graph property inference attack first involves data owner who trains 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 [8). 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 third-party online optimization solver [2I]. such as Gurobi D 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 sales company, 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 associated with multiple attributes. The sensitive property is defined based on one specific type of attribute, called the property attribute. Specifically, the sensitive property defined 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 product network 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 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 '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 denote the target graph. And let P(G denote the property value of Gtar, Note that P can represent either node properties or link properties. Given that the attacker has an auxiliary graph Ganx from the same domain as Gtar, we define graph property inference attack as follows:
Problem 1 (Graph property inference attack) Given the auxiliary graph Gaux, and assume the attacker has either the white-box knowledge of the target GNN parameters the black-box knowledge of target GNN's 's outpuf posterior probabilities, the objective of the graph property inference attack is infer the property P(Gra)) without access to it.
attpps//vwe http:/wwwwwwbb....o//// gurobi.ccomm com
3

---

Shudow graphs
Aux. graph
Attack model
Shadow models
(a) Conventional property inference
Aux.
Attack model
gruph
Ref. graph
Aug. graphs
Ref. model
Approx. models
Proposed property inference attack
Figure 1: Illustrations of (a) conventional graph property inference attacks and (b) the proposed attack, with yellow shading indicating model training, the main source of computational cost.
Methodology
This section provides a detailed description the proposed graph property inference attack. We start with overview of our method and then delve into the technical aspects of model approximation. Finally, we describe how to ensure the diversity approximated models while reducing their errors. The overall algorithm and complexity analysis are summarized in Appendix A.3
3.1 Overview
As shown in Figure 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 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, 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 be computationally expensive.
To mitigate this issue, our proposed attack method utilizes model approximation techniques substitute. We provide a illustration of our method in Figure (b)):
(I) Instead of numerous shadow graphs, first sample only 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 wed to the augmented graphs.
(4) We collect parameters or posteriors all approximated models and train the attack model in similar manner as previous attacks.
Here, we mainly face two challenges: ensuring that the approximate enror associated with augmen- tations 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 diversity enhancement strategy in 3.3
3.2 Model approximation and error analysis
We proceed by introducing the techniques of model approximation, which include generating aug- mented 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 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 Gref (V, F) sampled from Gaxx, where V is the node set, E S V x V is the edge set. For one perturbation,

---

remove VR C V and E C E to obtain the augmented graph G In GNNs, the neighborhood aggregation makes the removal inevitably influence the state of other remaining nodes. Given 1-layer GNN, the influenced nodes of removing single node E VR is the l-hop neighborhood of v, denote as Ni(v). And the influenced nodes removing single edge E ER,, connecting nodes and u, is denoted as Mi(e) (i)1(v) U 1 U (v, u). With these in mind, we next define the total influenced nodes for removing VR and ER.
Definition (Influenced nodes) Given the removed nodes VR, removed edges EB and a l-layer GNN, the total inftuenced nodes V is defined as
V
Ni(e) Mi(o).
EEER
DEVR
Note that V is exclusive of ;R; omit the set difference for simplicity.
Generating Approximated Models. Subsequently, we generate the approximated model based on the perturbation. While existing graph unlearning [29-31] 33) may offer potential solutions, they are either limited to specific model architectures or only support the removal 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 gref E R". In this paper, we consider cross-entropy loss the loss function, and gref is obtained as follows:
nodes or
gref = arg min Σ 2(0;u, E).
VEV
After removing VR and ER, directly retraining on G could yield new model parameter (aug;
gang arg min
Σ
((:
VEVVVR
To avoid training from scratch, derive the approximation of gang by the following theorem.
Theorem 3.1 (GNN model approximation) Given the GNN parameter fret on Gref, the removed nodes VR, removed edges ER and influenced nodes V Assume I is twice-differentiable everywhere and convex, we have
gaug gref + (V2 L(gret, ((gree,,Gauss (GauS)
Σ
e(gret; ;2 ;U,E) E)
Σ ,e,eeR, (4)
BEVILVR
where V denote gradient, and 2 denote Hessian. L(Oref, Gaus) Evevivn E(Oret, E/ RT)
The detailed derivation 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 damping term to the Hessian [34].To To reduce computation, 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 Vit and ER affect the approximation error in Eq. Note that V E.veeyR E00;u, EB) = 0 only when gaug is the exact minimizer, thus the gradient norm || Evevyyn l(O; E/E")]2 reflect the approximation error. The following theorem provides upper bound this gradient norm.
Theorem 3.2 (Approximation error bound) Assume is wwice-differentiable everywhere and con- 2 Evev/va E(O; E/ER) is 7/1 -iisshhhi,,, the approximation error bound is
vex, / C1. given by:
IV
Σ E(gaus De/ S C(JVR) + -
C- 5(VR E
(5)
HEV/VR
where 1.1 denotes the cardinality of a set, and o(.,)) denotes the square of the number of nodes removed and influenced, given V and FRR denotes a constant depending on the GNN model, see Appendix A.2 for detail proof.
5

---

Theorem indicates that the eπror 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.
3.3 Diversity enhancement
Following the above, we detail the designed diversity enhancement strategy. To develop well- generalized attack model capable of distinguishing different sensitive properties, we first apply structure-awan random walk for sampling diverse reference graphs. We then propose 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 graph, we design daructure-awar 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 communitics, where w E [0, 1] is a hyper- parameter. 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 reference graphs enhance the diversity, we further design a perturbation selector. Based on $3.22, it is easy to see that each approximated model can be considered as 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 gaug (G G2 ..... G by randomly removing different sets of nodes and edges. The diversity for Gaug is defined as:
Definition (Diversity for gauR) Given a set of k graphs gaur = {Gauu metric d(GGuu G that measures the distance between G and G The diversity of GauR is defined as the sum of all pair-wise graph distances in Gavg, that is, Ei ビラ d (G., (.T
" ....GRuB), and a graph
Since stochastic augmentations may not all contribute to total diversity, our objective is select diverse subset of gm" 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 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 quadratic integer programming task.
Given i available perturbations, we aim to select of them, such that the diversity among these selected is maximized while keeping the approximation error minimal. We here introduce decision variables x; (0, 1} represent whether the i-th augmentation is selected. Let ô; represent the approximation error in the i-th augmentation (cf. Eq. (5) ). The optimization problem is as follows:
min
d (G GG Ia s.t. (1)
(1)x2 x4 q, (2)
Σ
6, Se
(6)
where e is a constant that imposes the budget on the total approximation error of the selected g augmentations, ensuring that it does not exceed Here, we select graph edit distance as the distance metric, which can be efficiently calculated since all augmented graphs Gaug are derived from one reference gref, We utilize Gurobi Optimizer (36). state-of-theaat solver, solve this quadratic integer programming problem, which known for its efficiency and effectiveness.
3.4 Overall algorithm
We summarize the overall algorithm of our attack in Algorithm 1 Steps 1-2 outline the structure- aware 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.

---

Table 1: Properties to be attacked, # indicates number of nodes or edges.
Type
Dataset
Property attribute
Property description
Pokec
Gender
male users female users
Node
Facebook
Gender
# male users female users
Pubmed
Keyword "IS"
# publications with "IS" > publications w/o "IS"
Pokec
Gender
# same-gender edges > # diff-ggnn suff-gender edges same-gender edges diff-gende edges # edges between papers with "IS" > # other edges
Link
Facebook
Gender
Pubmed
Keyword"1S"
4
Experiments
In this section, we evaluate the performance of the proposed attack method by addressing the following three research questions:
RQI: 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 our method in different scenarios?
4.1
Experimental setup
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 dominant, and edge property as whether the same-gender edges are dominant.
Pubmed is citation network where nodes publications and edges 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
Training and testing data. For fairness, we evaluate our method and baselines on the same target graphs. To ensure there is 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 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 (2I) with layers, 64 hidden sizes, and 1,500 training epochs with an early stop tolerance of 50. The Adam optimizer is used with learning rate of le-4 and weight decay of 5e-4.
Implementation details. For the attack model, We use linear classifier with the deepest trick 41 For hyper-pane papee--rrrmeter settings, we perform grid searches of reference graphs' numbers (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 more details. com wttpehuw...oom///eeeeeeee wttm://junet//PAANPPPP
Our codes are available hthttps://githiii
Baselines. We adopt four -fate-of-the-as baseline models to compare against the proposed attack model: (1) GPIA [2T]: An attack method designed for graphs and GNNs in both white-box and black- box 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 (2 Property inference method based attribute inference attack, which first predicts the property attribute based on embeddiinss/posteriorss and then predicts property, suitable for both bhite-box/bllck-bee attacks. See Appendix A.4 for details.

---

Table Average accuracy and runtime (seconds) comparison on different properties in white-bor -ox setting. "Node" and "Link" denote node and link properties. respectively. The best results are in bold.
Facebook
Pubmed
Pokec
Node
Link
Node
Link
Node
Link
Acc.
Rt.
Acc.
Rt.
Acc.
Rt.
Acc.
Rt.
Acc.
Rt.
Acc.
Rt.
GPIA
60.7
1791
56.1
1591
82.9
3028
73.8
2901
58.6
1176
54.7
1314
PIR-D
67.8
1733
58.1
1563
83.9
3022
73.9
2895
60.5
1187
56.2
1325
PIR-S
60.2
1762
57.7
1576
80.5
3032
72.6
2912
59.6
1181
57.9
1318
AIA
64.3
1741
56.7
1553
67.3
3026
75.5
2896
58.3
1215
56.5
1353
Ours
71.4
254
61.5
222
85.2
550
75.9
432
61.4
242
58.8
159
4.2
Evaluation of efficiency and effectiveness (RQ1)
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 / 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: (I) 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 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.5x 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.
presents the average
4.3 Evaluation of influencing factors (RQ2)
Ablation study. To ensure effectiveness, method includes two main mechanisms: sampling diverse reference graphs and selecting diverse augmented graphs. Here, we conduct ablation studies 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 '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-parametert 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. 8. 10). The results in Figure ( (b) and (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.
4.4 Evaluation in different scenarios (RQ3)
8

---

0.71
1500
0.70
0.715
0.69
0.70
1000
0.70
0.58
0.69
0.705
0.57
0.68
W/ 55 selccua dicrsity
Ous
AIA
Ablation study
Impact of aug. graphs
(c) Impact of ref. graphs
Black-box attuck
Figure 2: (a) Evaluation of the necessity of considering diversity while minimizing the approximation emror. (b) and (c) Impact of the number of augmented graphs (per reference graph) and reference graphs on attack accuracy, respectively. (d) Accuracy and runtime comparison in black-box settings.
To test the applicability of our method, we evaluate its performance under various conditions, including scenarios with black-box adversary knowledge, different types of GNN models, large-scale graph datasets, and when the target and auxiliary graphs are distinct.
Performance on black-box knowledge. In the black-box setting, 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-ar black-box attack, PIA-MP (2)), as detailed in Appendix [A.44 The results on Facebook's s node property in Figure 2 (d) show that our method improves accuracy by 1 1.55 compared to the best baselines while being 7.3x faster.
model outputs, specifically
Performance on other GNNs. We conduct property inference attacks on other three funda- mental GNNs: GCN [43) GAT [44), and SGC [45). For GCN and GAT, hyper-parameters are configured according to [2I], while for SGC, set the number of hops to 2. We report the attack accuracy and runtime of our method alongside other baselines Facebook's s node
Table 3: Attack comparison using distinct graphs
for the target and auxiliary graphs. The arrows indicate the auxiliary graph on the left and the target graph on the right. The best results are bolded.
Facebook = Pokec
Pokec = Facebook
Node Acc.
Link
Node
Link
Rt.
Acc.
Rt.
Acc.
Rt.
Acc.
Rt.
property, as illustrated in Figure (a)-(c). It observed that the overall attack accuracy for SGC is comparatively lower, potentially due to the SGC model's inherent limitations in captur- ing property information effectively. Moreover, our method consistently achieves the highest accuracy, also demonstrating a runtime that is 4.4x faster on GCN, 4.0x faster on GAT, and 4.3x faster on SGC compared the best baseline.
GPIA
56.7
1732
54.6
1569 60.2 1244 57.5 1296
PIR-D
54.5
1794
56.8
1648
62.4
1297
55.9
1385
PIR-S
57.6
1777
52.1
1609
60.3
1262
56.1
1342
AIA
53.4
1729
53.0
1535
64.6
1237
55.6
1321
Ours
58.3
267
57.3
236
65.7
233 59.3 177
Performance on scalability. We further conducted property inference attacks on large-scale graph dataset, Pokec- 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.0x 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 hold. Therefore, we evaluate the performance 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 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.
attack under a more practical

---

181
W
Are. Rt.
Acc. Rt.
614)
W
0.60
620
15000-
0.55
0.65
420
1..4 600)
400-
66
In200
0.56
200
0.62 400-
200
66
5000
0.52
0.59
50
Ouis OPIA PIRDD MIL-S AIA
Otex GPTA K.R-D
AlA
Ckex GPTA FR--D PIR-S
AIA
Otex GMA PIR-D AIA
(n) GAT
(b) GCN
(c) SGC
(d) Pokee-100M
Figure 3: Comparison of average attack accuracy and runtime (seconds) on: (a)-(c) other GNNs, including GAT, GCN, and SGC; (d) a large-scale dataset, Pokec-100M)
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 this, attacks various machine learning models are studied, including feed- forward neural networks, convolutional neural networks, and generative adversarial networks [2 25 32 46). Some works also consider multi-party collaborative learning scenarios 22 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, of graphs and GNNs, security and privacy concerns are emerging (1)) While efforts have been made to investigate property inference attacks on GNNs (20) 27]. they follow the shadow training framework, which requires training a relatively large number of shadow
with the increasing
GNN models, leading to high computational costs and reduced feasibility [47) [22] assumes access
the embedding of whole graphs and targets at graph-level properties, which beyond our scope.
GNN model approximation. GNN model approximations are primarily based on the influence Newton update [30
function 29
31
53
54
33
Except for (54). these methods 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 framework for edge unlearning, while (31) proposes general unlearning framework for removing either nodes, edges, or features individually. Our model approximation differs from above by enabling the simultancous 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 combination of nodes and edges, and their corresponding solution may significantly compromise the efficiency. Other studies [55] (66) also employ the graph shard approach. However, they may have poor efficiency in batch removal, which involves multiple retraining of sub-models.
6 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 diversity enhancement strategy, including structure-awan random walk for sampling diverse reference graphs and 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 attack's outstanding efficiency and effectiveness.
10

---

Acknowledgments and Disclosure of Funding
This work is supported by the Zhejiang Province BaanBiingLingYn+222 Research and Development Plan (2024C01114)
References
[1] Zonghan Wu et al. "A comprehensive survey on graph neural networks". In: IEEE transactions on neural networks and learning systems 32.1 (2020), pp. 4-24.
[2] Shengchao Liu, Mehmet Demirel, and Yingyu Liang. "N-gram graph: Simple unsupervised
representation for graphs, with applications to molecules". In: Advances in neural information
processing systems 32 (2019).
[3] Michael Fleder, Michael S Kester, and Sudeep Pillai. "Bitcoin transaction graph analysis". In: arXiv preprint arXiv: 502.001577 (2015).
[4] Yu Wang al. "SpatiotempporalAuummee Simulation". In: JEEE Transactions on Knowledge and Data Engineering (2024).
Graph Neural Networks for Human Mobility
[5] Tongya Zheng et al. "Temporal aggregation and propagation graph neural networks for dynamic representation". In: IEEE Transactions on Knowledge and Data Engineering 35.10 (2023), pp. 10151-10165.
[6] Shunyu Liu al. "Transmission Interface Power Flow Adjustment: A Deep Reinforcement Learning Approach Based on Multi-Tass Taski Altribution Map". In: IEEE Transactions on Power Systems 39.2 (2024), pp. 3324-3335.
[7] Chen Gao et "A survey of graph neural networks for recommender systems: Challenges, methods, and directions". In: ACM Transactions Recommender Systems 1.1 (2023), pp. 1-
51.
[8] Oliver Wieder et al. "A compact review of molecular property prediction with graph neural networks". In: Drug Discovery Today: Technologies 37 (2020), pp. 1-12.
[9] Yuwen Wang al. "Unveiling Global Interactive Patterns across Graphs: Towards Interpretable Graph Neural Networks". In: ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024, pp. 3277-3288.
[10] Xiaoxiao Ma et al. "A comprehensive survey on graph anomaly detection with deep learning".
In: IEEE Transactions on Knowledge and Data Engineering 35.12 (2021), pp. 2002--1038.
[11] Jiarong Xu et al. "Netrl: Task-aware network denoising via deep reinforcement learning". In:
IEEE Transactions on Knowledge and Data Engineering 35.1 (2021), pp. 810-823,
[12] Jiarong Xu et al. "Robust network enhancement from flawed networks". In: IEEE Transactions
on Knowledge and Data Engineering 34.7 (2020), pp. 3507-3520.
[13] Jiarong Xu et al. "Toward Secure Graph Data Collaboration in a Data-Sharing-Free Manner: A Graph Pre-training Model". In: Available at SSRN (2023).
Novel
[14] Carol Tenopir et "Data sharing, management, use, and reuse: Practices and perceptions of scientists worldwide". In: PloS one 15.3 (2020), e0229003.
[15] Hanyang Yuan et al. "Unveiling Privacy Vulnerabilities: Investigating the Role of Structure in Graph Data". In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024, pp. 4059 4070.
[16] Adam Lerer al. "Pytorch-biggraph: A large scale graph embedding system".. In: Proceedings of Machine Learning and Systems (2019), pp. 120-131.
[17] Ziniu Hu et al. "Gpt-gnn: Generative pre-training of graph neural networks". In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery data mining.
2020, pp. 1857-1867.
[18] Da Zheng al. "DGL-KE: Training Knowledge Graph Embeddings at Scale". In: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. SIGIR '20. New York, NY, USA: Association for Computing Machinery, 2020, pp. 739-748.
[19] Jiezhong Qiu et al. "Gee: Graph contrastive coding for graph neural network pre-training". In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery data mining. 2020, pp. 1150-1160.

---

[20] Wanrong Zhang, Shruti Tople, and Olga Ohrimenko. "Leakage of dataset properties in (Multi- Party) machine learning". In: 30th USENIX security symposium (USENIX Security 21). 2021, pp. 2687-2704.
[21] Xiuling Wang and Wendy Hui Wang. "Group property inference attacks against graph neu- ral networks". In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022, pp. 2871-2884.
[22] Karan Ganju al. "Property inference attacks on fully connected neural networks using permutation invariant representations". In: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security. 2018, pp. 619-633.
[23]
Giuseppe Ateniese et al. "Hacking smart machines with smarter ones: How to extract meaning- ful data from machine learning classifiers", In: International Journal of Security and Networks
10.3 (2015), pp. 137-150.
[24] Luca Melis et al. "Exploiting unintended feature leakage in collaborative learning". . In: 2019 IEEE symposium on security and privacy (SP). IEEE. 2019, pp. 691-706.
[25] Junhao Zhou et al. "Property inference attacks against GANs". In: arXiv preprint arXiv:2111.0000 (2021).
[26] Enyan Dai and Suhang Wang. "Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information". In: Proceedings of the 14th ACM International Conference on Web Search and Data Mining. 2021, pp. 680-688.
[27] Anshuman Suri and David Evans. "Formalizing and estimating distribution inference risks".
In: arXiv preprint arXiv:2109 709.06024 (2021).
[28] Chuan Guo et al. "Certified data removal from machine learning models". In: arXiv preprint
arXiv:1911 1. .03030 (2019).
[29] Kun Wu et al. "Certified edge unlearning for graph neural networks". In: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023, pp. 2606- 2617.
[30] Eli Chien, Chao Pan, and Olgica Milenkovic. "Certified graph unlearning". In: arXiv preprint arXiv:2206.099 09140 (2022).
[31] Jiancan Wu et al. "Gif: A general graph unlearning strategy via influence function". In: Proceedings of the ACM Web Conference 2023. 2023, pp. 651-661.
[32] Saeed Mahloujifar, Esha Ghosh, and Melissa Chase. "Property inference from poisoning". In:
2022 IEEE Symposium on Security and Privacy (SP). IEEE. 2022, pp. 1 113-
[33] Chao Pan, Eli Chien, and Olgica Milenkovic. "Unlearning graph classifiers with limited data resources". In: Proceedings of the ACM Web Conference 2023. 2023, pp. 716-726.
[34] Pang Wei Koh and Percy Liang. "Understanding black-box predictions via influence functions". machine learning. PMIR. 2017, pp. 1885-1894.
In: International conference
[35] Vincent D Blondel et al. "Fast unfolding of communities in large networks". In: Journal of statistical mechanics: theory and experiment 2008. 10 (2008), P10008.
[36] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual. 2023. URL: https: htmpps:/wwwr //www gurobi. com
[37] Jure Leskovec and Julian Mcauley. "Learning to discover social circles in ego networks". In: Advances in neural information processing systems 25 (2012).
[38] Zhilin Yang. William Cohen, and Ruslan Salakhudinov. "Revisiting semi-supervised learning with graph embeddings". In: International conference on machine learning. PMLR. 2016, pp. 40-48.
[39] Lubos Takac and Michal Zabovsky. "Data analysis in public social networks". In: International scientific conference and international workshop present day trends of innovations. Vol. 1. 6. 2012.
[40] Will Hamilton, Zhitao Ying, and Jure Leskovec. "Inductive representation learning on large graphs". In: Advances in neural information processing systems 30 (2017).
[41] Manzil Zaheer et al. "Deep sets". In: Advances in neural information processing systems 30 (2017).
[42] Congzheng Song and Ananth Raghunathan. "Information leakage in embedding models". In: Proceedings of the 2020 ACM SIGSAC conference on computer and communications security. 2020. pp. 377-390.
12

---

[43] Thomas N Kipf and Max Welling, "Semi-superrised classification with graph convolutional networks", In: arXiv preprint arXiv: 02000 (2016).
[44]
Petar Velickovic et al. "Graph attention networks". In: stat 1050.20 (2017), pp. 10-48550.
[45] Felix Wu et al. "Simplifying graph convolutional networks". In: International conference on machine learning. PMLR. 2019, pp. 6861-6871.
[46] Mathias PM Parisot, Balazs Pejo, and Dayana Spagnuelo. "Property inference attacks on convolutional neural networks: Influence and implications of target model's complexity". In: arXiv preprint arXiv:2104. 1306/ (2021).
[47] Harsh Chaudhari et al. "SNAP: Efficient extraction of private properties with poisoning". In:
2023 IEEE Symposium on Security and Privacy (SP). IEEE. 2023, pp. 400-417.
[48] Qinkai Zheng et al. "Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learning". In: arXiv preprint arXiv:211 1.122111144144 (2021).
[49] Junlong Liao et al. "Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware
Attacks". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38, 12. 2024, pp. 13763-13771
[50] Jiarong Xu al. "Blindfolded attackers still threatening: Strict black-box adversarial attacks on graphs". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. 4. 2022,
pp. 4299-4307.
[51] Jiarong Xu al. "Unsupervised adversarially robust representation learning on graphs". In: Proceedings of the AAAI conference on artificial intelligence. Vol. 36. 4. 2022, pp. 4290-4298.
[52] Zhikun Zhang al. "Inference attacks against graph neural networks". In: 31st USENIX Security Symposium (USENIX Security 22). 2022, pp. 4543-4560.
[53] Yushun Dong et al. "Idea: A flexible framework of certified unlearning for graph neural networks". In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024, pp. 621-630.
[54] Zizhang Chen et al. "Characterizing the influence of graph elements". In: arXiv preprint arXiv:2210.07441 (2022).
[55] Cheng-Long Wang. Mengdi Huai, and Di Wang. "Inductive graph unlearning". In: 32nd USENIX Security Symposium (USENIX Security 23). 2023, pp. 3205-3222.
[56] Min Chen et al. "Graph unlearning". In: Proceedings of the 2022 ACM SIGSAC conference on computer and communications security. 2022, pp. 499-513
13

---

A Appendix
A.1 Notations
The main notations can be found in the following table.
Table 4: Description of major notations, ordered by appearance.
Notation
Description
G Qaux P(G
target graph, auxiliary graph, property of G reference graph, its node set and edge removed nodes and edges in Gref augmented graph
Gref V, E
VR. ER, Gaug
U,U, U,u.
two nodes, edge connects v, u the influence nodes of removing and e
Ni(e).N((e)
V
the total influenced nodes of removing VR and E
gref Baug,
parameters of reference model/approximmaed model, cross-entropy loss a set augmented graphs
Gaug
A.2
Proof of theorems
A.2.1 Proof of Theorem
Given the GNN parameter grof on G the removed nodes VR, removed edges E and influenced nodes VI. Assume é is twice-differentiable everywhere and convex, we have
gaug se grof + (V2
Σ f(gret, U, )
Σ
E(pret; c, E)
Σ
e(gref; E/ER RR)
DEV/VR
oE VEVIUVR
VEVI
where denote the gradient, and 2 denote the Hessian. Proof. Let L(0; Gaug)= = Everyvn E(0; E/E") denote the loss function of Gaug at 6 by one step newton update of L, the approximation of gang is:
gang zu gref - L( G)UR))
V D((orof ( GmuR).
(8)
Let UI denote the uninfluenced node set, i.e., V'UVUL V/VR V yunu = 0. we have
[(Oret, gaug)
Σ e(Oret ;. E/ER) + Σ
e(Oret, ;u, E/E
VEVUI
VEVI
Σ
e(Orrf
;0, E) + Σ
e(frof ;0, F) + Σ
E(gref, F))
VEVUI
VEVR
vEVI
Σ E(gret ;0, E/ER)
Σ
((gret, E)
Σ
!(gref u, E)
VEVR
VEV1
E(gref, v. E) Σ
E(gret U. E/ER
Σ
E(gret, u, E)
Σ
l(pref,
v. E)
VEV
DEV4
BEAR
VE
(9)
Given V Evev E(Brof; E) ()=))=/) 0, we have
V.(eref Gaus)= v Σ
;( E/ER)
Σ
e(gret, U, E)
(10)
UEvv
VEVIUVE
And
gang x gref + (V2L( (auB))
Σ
E(Orof, u. E)
Σ
E(frof;0 E/EE))
(11)
NEVIUVR
WEVI
which completes the proof.
14

---

A.2.2 Proof of Theorem 3.2
Assume l is wice-differentiable everywhere and convex, | S c1, V2 "EDEV/VA {(0;0, E/ER) is 7 -Lipschhi,, the error bound for the approximation error is given by:
E/ER)
e(Oaus; v, 1/2 S C(IV*) + 2|V = "EV/VR
Σ
C C. C- E
(12)
where |. denotes the cardinality of set, and 8(:--) denotes the number of nodes removed and influenced, given V and E C' a constant depending on the GNN model.
Firstly, we consider an empirical loss for the reference model, which consists of cross- entropy and Iegregularrvvttio::
Proof.
0 0, B) = CE(0; v, E) + 2
10112.
(13)
where CE(:,-) represents the cross-entropy, and we omit the ground truth for simplicity. À >> 0 denotes the r--regularizztton.
Let G(Ø) = V Σ LEEEEVR E(0;; v, E/E"), Ho denote the Hessian of EVEVIVR e(pret; ;0, E/E"), and let
==V
Σ
e(Orr, ;u, E,
Σ
2(0 1u, 1 E.E
(14)
VEVVIVR
VEV
By Taylor's Theorem, we have
G((mus)) ~G(frff + 'TT'A) A)
-G(O VG +nll, 'A'''
-G(Oret) + -HH1l
(15)
where H,, denotes the hessian at 0, = gref + nHH A. ne E [0,1].
Let G((AnR) G( + A+ Ho A A, we have
G(Bret) +A=V Σ
e(Oret ;u, F./EB +A
VEV/VR
V
Σ
{(0 :. E/ER +
E(grat, v, E/ER) +A
VEVI
E(Oref, 0 E)
VV
0.
(16)
Since G( = H H - A = (H,, - Ho A, we have
|[G(@au)) = [|(H, - Ho A1ll - H, Ho All..
(17)
Assume the Hessian of EvEVIVR E(0;v, " is 7 -iiischhit,, we have
H, - Holl2 = 2 Σ
E(0g;v E/ER) 2
Σ
E(0ret; ;u,
u. E/ B/ERR)
VEV/VR
VEVVVA
S nl10, - gref l|2
= = AAll
S (7llH,1AAl since 17 E [0, 1].
(18)
15

---

Then we have |[G(@uux)]e
- o Al
Since
|
V
Σ
E(O'e, 50, F) V Σ
e(Oret U, F/ F//.R))
BEVLUVR
DEVI
$ IV Σ
E(Gret U, E) + I
E(Oref U, E E/E">\l2
"EVILVR
VE
Σ VE(O v. E)ll + Σ
Vi(ret ; E/ER)|1
VVVIUVR
NEV!
$ ([VR) 2
assume | S c1
(19)
Since EveVivR 800;, EBER) is X([V| - I-stronyy convex, we have 11 1 S x--া-া In practice, we keep [V as fixed value, thus H 112 I aa where 02 = |V| - |VR]. Finally,
[G(Baus)] 1|2 - 71 7 A|
S 1 11 12
n ((V 2
where C C= 71
(20)
2²22"
A.3 Training algorithm and complexity analysis
Complexity of generating approximated models. As the computation of gradients can be effi- ciently handled by the PyTorch Autograd Engine, the primary operation is solving the inverse of
the Hessian (ef. Eq. 4 To mitigate the high computational cost, we follow (29) in converting the
inverse computation into finding the minimizer of quadratic function, resulting in approximated
solution. By leveraging efficient deessian-vector products and the conjugate gradient method, this can be solved with time complexity of (t))0), 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 !
A.4 More experiment settings
Details of datasets.
The statistics of the datasets used in this work are summarized in Table 5
Table Dataset statistics.
Dataset
# nodes
# edges
# features
classes
Pokec
40,478
531,736
197
Facebook
4,309
176,468
1,282
Pubmed
19,717
88,648
500
This dataset consists of 4,039 nodes and 176,468 edges. Nodes have features like birthday, education, work, name, location, gender, hometown, and language, anonymized for privacy. The target GNN's task is to classify users' education types.
Facebook (7
This dataset includes 19,717 scientific publications related to diabetes, with citation network of 88,648 links. Each publication is described by TF/IDF weighted word vector from a dictionary 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.
PubMed (38]
16

---

Algorithm Overall algorithm for the proposed attack.
Input: Auxilary graph G target model's parameters or posterior probabilities. Number of reference graphs r, number of perturbations k, number of selected augmented graphs y, weight w for sampling reference graphs
Output: The inferred sensitive property P(G of the target graph G
1: Partition G into multiple communities using Louvain community detection.
2: Sample reference graphs using the proposed structure-aware random walk, with weight w.
3: for each reference graph Gref do
4: Train reference model gref,
Errors, 0 + Perturbs. 6: for k do
5: 0 + Go
7: Randomly select set of nodes yR and set of edges E from Gre!
8: Add G into Gaug,
9: Add (VR, F) into Perturbs.
10:
Compute the approximation enror criterion in Eq. (). and add it into Errors.
11:
end for
12:
Solve the optimization problem in Eq. (6). select perturbations.
13: Calculate the approximated models by Eq.
14: Save the parameters (or posterior) and the q properties of the selected augmented graphs.
15: end for
16: Train attack model based the r.q parameters (or posterior) and properties, classify P(Guar)
of the target graph G
This online social network dataset is from Slovakia. Each node has anonymized features such as gender, age, and hobbies. We follow (2I) to sample nodes with relatively complete features, resulting in graph with 40,478 nodes and 531,736 edges, using gender, age, height, weight, and region as node features. The target GNN's task to classify whether a user's all friendships are public.
Pokec [39]
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 has the highest TF-IDF weight. These properties summarized in Table
Statisties of reference, shadow, and target graphs. The sizes and numbers of reference graphs we use are summarized in 6
Table 6: Numbers and sizes of reference graphs
Dataset
Ref. graph number
Ref. graph size
Pokec
50
525
Facebook
50
3200
Pubmed
100
4250
For all baselines, we follow the settings specified in 21 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 each shadow graph is 20%, 25%, and 30% of Pokec, Facebook, and Pubmed datasets, respectively. To ensure fairesss, evaluate our method and baselines on the same target graphs.
More implementation details. All experiments are conducted on machine of Ubuntu 20.04 system with AMD EPYC 7763 (756GB memory) and NVIDIA RTX3090 GPU (24GB memory). All models implemented in Torch version 2.0.1 with CUDA version 11.8 and Python 3.8.0.
17

---

The attack model is trained for 100 epochs with a learning rate of 1e-3 and 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 property inference attack considering permutation equivalence in feed-forward neural networks, using node permutations the hidden layers of fully connected neural network.
PIR-D 22 Similar to PIR-S, permutation equivalence is achieved by ensuring all permutations of any layer have the set-based representation.
Baselines for black-box setting.
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.
PIA-MP 20
Baselines for both settings.
GPIA [2T]: 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 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
Table 7: Standard deviation.
Facebook
Pubmed
Pokec
Standard deviation
Node
Link
Node
Link
Node
Link
GPIA
0.9
2.1
0.7
0.5
0.5
0.3
PIR-D
2.9
1.5
3.2
1.7
1.4
2.3
PIR-S
0.9
2.1
ATA
2.3
2.6
5.3
0.2
0.5
1.2
Ours
0.5
0.4
0.7
1.0
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 the six sensitive properties, shown in Table The results demonstrate that our model can consistently achieve the best ROC-AUC result, confirming its notable effectiveness.
Table 8: ROC-AUC comparison of method and baselines. "Node" and "Link" denote node and link properties respectively. The best results are highlighted in bold.
Facebook
Pubmed
Pokec
ROC-AUC
Node
Link
Node
Link
Node
Link
GPLA
50.4+0.7
46.4+:1.4
69.8+5.55
57.4+10.7
56.8+00.4
54.1+:0.4
PIR-D
62.8+1.3
48.6+:0.9
83.0+2.5
62.0+55.1
6..5+1.8
6..9+1.4
PIR-S
35.9+3..6
4..4+114
73.7+00.6
61.9+2.3
60.7+1.2
1.69
AIA
48.5112.3
52.811.11
61.4.14.0
48.2.13.7
53.0.13.4
51.31188
Ours
64.0++0.3
53.4+:0.4
87.1+2.7
69.3+8.7
63.0
61.6-10.5
18

---

A.6 Limitation and future work
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 method does 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.
A.7 Potential impacts
While the proposed method designed 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 model design. Traditional property inference methods often inefficient, and despite efforts to illuminate potential threats, less practical attack scenarios may receive adequate attention. Nonetheless, the privacy risks persist. We seek bring this threat to the forefront and advocate for the adoption of more robust protective measures.
19

---

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:
See abstract and $
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
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 not discussed in the paper.
The authors are encouraged to create 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 '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 set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

Justification:
See Theorem 3.1 Theorem 3.2 and Appendix A.2
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.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See
4.1 and Appendix A.4
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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 a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of 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) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
21

---

Answer: [Yes]
Justification:
See the code link implementation details.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
crriiinnocccyc lc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not 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 NeurIPS code and data submission guidelines (https
/ cpippi.ccppulli///uuui wwwtc//gguie///eeeeceoocc CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as 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: See
4.1 and Appendix A.4
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
See the standard deviation in Table 7
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, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call 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.
22

---

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 to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in 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 on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See Appendix A.4 more implementation details.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://////rrppppcpppppoopo///po httppr/p....pppoaaoo///ccccaaaee
Question:
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations 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:
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 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.
23

---

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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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:
This work does not involve such risks.
Guidelines:
The answer NA means that the paper poses 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 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 best faith effort.
12. Lieenses 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: See the code link in implementation details and citations.
Guidelines:
The answer NA means that the paper does not 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 (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets 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 it has changed) should be provided.

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: See the code link provided in implementation details.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an 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:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor 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 Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
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 NeurlPS 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.
25


Reviews:
[{"review_id": "XKGDjdACrG", "reviewer": "Reviewer_j8ts", "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.", "questions": "Please refer to the weaknesses.", "limitations": "Sufficiently addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThe paper is overall clearly written and easy to follow.\n2.\tThe research problem of making the inference attacks more efficient is relevant.\n3.\tThe proposed method achieves the SoTA attack performance and largely reduces the training time of the attack model.", "weaknesses": "1.\tHow scalable is this attack for larger datasets? Current experiments are limited. Please perform the attack on larger datasets from the OGBN dataset (ArXiv, Products)\n2.\tHow well does this scale for other GNNs? Please evaluate with other GNN models.\n3. Fig. 1 is confusing. Please update it to clearly show the difference between the proposed approach and the existing attacks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1: Experiments on larger datasets.\n\nAs noted in Appendix A.5 and Table 8, we have already included experiments on a million-level dataset  Pokec-100M, which contains 1,027,956 nodes and 27,718,416 edges. We found that the best baseline, PEPIA-DS, incurs a significant cost, while our method is 10.2× faster and achieves both higher accuracy and ROC-AUC. To ensure that the results highlighting scalability are emphasized, we have restructured our paper to mention this experiment at the beginning of the experiments section.\n\nAdditionally, as you suggested, we further evaluate our approach on the OGBN products dataset (2,449,029 nodes), larger than Pokec-100M. We categorize products into consumer goods and non-consumer goods based on label descriptions. The property is set as the portion of non-consumer goods in the target graphs: 35\\% (original) or 65\\% (higher); the rest settings remain consistent with our manuscript. As shown in the table below,  our attack achieves superior performance compared to the best baseline, with speeds of 12.0× faster, underscoring its scalability.\n\n\n| **Method** | **Accuracy** | **ROC-AUC** | **Runtime(s)** |\n|------------|--------------|-------------|----------------|\n| PEPIA-DS   | 92.3         | 88.5        | 34881          |\n| Ours       | **93.2**     | **89.1**    | **2918**       |\n\n\n>W2: Experiments on other GNNs.\n\nAs indicated in Appendix A.5 and demonstrated in Figure 3, we have already expanded our experimental scope to include attacks on other GNNs, including GCN and GAT.  To highlight these results, we have restructured our paper to mention this experiment at the beginning of the experiments section.\n\nAdditionally, to show the significance on other types of GNNs, we further evaluate with SGC [1], setting the number of hops to 2. \nThe table below shows the performance and runtime of the attack on Facebook's node property, using SGC as target models.\nThe results demonstrate our method consistently demonstrates superior performance and exceptional efficiency on these widely adopted GNNs.\n\n|            | **GPIA** | **PEPIA-DS** | **PEPIA-S** | **AIA** | **Ours** |\n|------------|----------|--------------|-------------|---------|----------|\n| **Accuracy** | 58.7    | 60.3         | 61.0        | 59.3    | **62.5** |\n| **Runtime(s)** | 609    | 618          | 620         | 614     | **142**  |\n\n>W3: Fig.1 is confusing.\n\nThank you for your valuable comment.\nWe have revised Fig.1 to clearly show the difference between our method and the existing attacks. Please refer to Fig. 1 in our uploaded rebuttal PDF. We will incorporate this new figure into our paper.\n\n[1] Simplifying Graph Convolutional Networks", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oleDoxPglS", "reviewer": "Reviewer_xZDY", "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.", "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": "The authors have included detailed discussions on the societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "- To me, this paper finds an interesting application of machine unlearning in reducing the time complexity of training shadow models in inference attacks.\n- The experimental results show a desirable performance of the proposed method over baseline attack methods in both efficacy and efficiency.\n- The paper is overall well-organized and easy to follow.", "weaknesses": "- 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.\n- 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]. \n- The inverse Hessian in influence computation is seen as highly consuming. It would be helpful to add some complexity analysis of the algorithm. \n\n[1] Wu, Kun, et al. \"Certified edge unlearning for graph neural networks.\" KDD 2023.\n\n[2] Pan, Chao, Eli Chien, and Olgica Milenkovic. \"Unlearning graph classifiers with limited data resources.\" TheWebConf 2023.\n\n[3] Chien, Eli, Chao Pan, and Olgica Milenkovic. \"Efficient model updates for approximate unlearning of graph-structured data.\" ICLR 2023.\n\n[4] Wu, Jiancan, et al. \"Gif: A general graph unlearning strategy via influence function.\" TheWebConf 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1: Limited scope and significance.\n\nThanks for your comment. \n\nWe'd like to emphasize that inefficiency is a major bottleneck in graph property inference attacks. Our contribution significantly enhances the efficiency of these attacks, enabling their practical application at scale, which is essential for both academic research and real-world use. Specifically, existing attacks can take over 3 days on graphs with more than 1,000,000 nodes using 700 shadow models [1], making them practically infeasible. Our method can reduce this to a few hours. Even on medium-large graphs with 200,000 nodes, current attacks take up to 7.5 hours, while our attack is over 10x faster, requiring less than one-tenth of the shadow models trained from scratch. Additionally, our attack also delivers superior performance.\n\nWe also acknowledge the importance of discussing defensive methods against these more efficient attacks. Our attack can facilitate the faster development of defense strategies. Effective defense hinges on its ability to counteract attacks, and a more effective and efficient attack can serve as a tool to refine defense strategies.  For example, adversarial learning [2] iteratively adjusts both defense and attack strategies to minimize the success rate of attacks. Due to the inefficiency, adopting conventional property inference in adversarial learning may lead to poor defense efficiency. In contrast, our attack has the potential to accelerate the defense process, enhancing its feasibility.\n\n>W2: Technical novelty is limited. \n\nThank you for your comment, which inspired us to clarify our contribution and the differences between our technique and existing methods.\n\nFirst, our approximation technique differs from existing graph unlearning methods in two key ways:\n\n(1) Unlike existing graph unlearning methods, which are restricted to removing either nodes, edges, or features individually [3,4], or are limited to specific GNN architectures [5,6], our method enables the removal of both nodes and edges across any GNN architecture. This broad applicability significantly enhances its utility in creating diverse augmented graphs, thereby improving attack performance across a wide range of target GNNs.\n\n(2) Unlike existing approaches that rely on predefined removals, we introduce a novel selection mechanism for determining which nodes and edges to remove, ensuring diverse augmented graphs and accurate approximation. This facilitates the creation of a strong attack model. Our selection comprises three parts:\n\n- To measure the accuracy of model approximations, We derive a theoretical error estimation with innovative mathematical derivations, which is computable given the removal. As we remove both nodes and edges with generic GNNs, existing analyses [3, 5, 6] can not directly apply.\n- To measure the total diversity of graphs through various removals, we propose using the efficient edit distance as the metric.\n- To minimize approximation error while maximizing total diversity, we formulate this optimization as a quadratic integer programming problem, which is efficiently solvable.\n\nFurthermore, we emphasize that the biggest contribution of this work is improving the efficiency of graph property attacks, enabling practical application (please refer to our response in W1). To achieve this, we designed two novel technical components: (1) the diverse sampling of reference graphs, which is beyond the scope of unlearning, and (2) the selection of augmented graphs with model approximation, which differs from existing unlearning in both the type and selection of removals. These components form the core technical contributions of this work.\n\n> W3: Computation of inverse Hessian.\n\nThe complexity of model approximation is relatively light. As the gradient can be easily computed by Pytorch Autograd Engine, the main operation is solving the inverse of Hessian. We follow [3] to reduce this to linear complexity by converting inverse computation into finding a unique minimizer of a quadratic function. With the efficient hessian-vector product and the conjugate gradient method (CG), this can be solved with $O(t|\\theta|)$ time complexity [3], where $|\\theta|$ denotes the number of parameters and $t$ denotes the iteration number in CG. In experiments, our attack performs well with few iterations. We will update our paper to include these computational details.\n\n>Q1: Convexity assumptions. \n\nThank you for your insightful comment. To the best of our knowledge, no generic unlearning approach with theoretical guarantees has successfully removed the convexity assumption, which is a challenging task. Due to the non-convex nature of GNN models, the Hessian can become non-invertible. To address this, we adopted a common solution of introducing a damping term to the Hessian, which has proven effective in [3,7].\n\nIn our experiments, reference GNNs use the same architectures as the target models, including GraphSAGE, GCN, and GAT. To better align with theoretical assumptions, we also test on SGC, a linear GNN, with 2 hops. We compare attack performance and runtime on Facebook's node property, with results detailed below.\n\n||**GPIA**|**PEPIA-DS**|**PEPIA-S**|**AIA**|**Ours**|\n|-|:-:|:-:|:-:|:-:|:-:|\n|**Accuracy**|58.7|60.3|61.0|59.3|**62.5**|\n|**Runtime(s)**|609|618|620|614|**142**|\n\nThe results show that our method consistently outperforms other baselines with exceptional efficiency on the linear GNNs.\n\n[1] Group Property Inference Attacks Against Graph Neural Networks\n\n[2] Adversarial learning techniques for security and privacy preservation: A comprehensive review\n\n[3] Certified edge unlearning for graph neural networks\n\n[4] Gif: A general graph unlearning strategy via influence function\n\n[5] Unlearning graph classifiers with limited data resources\n\n[6] Efficient model updates for approximate unlearning of graph-structured data\n\n[7] Understanding Black-box Predictions via Influence Functions", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7wvdHAAEbt", "reviewer": "Reviewer_5YZA", "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.", "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.\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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. \n\n- 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": "see questions", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Steady theretical support\n- Well-written paper\n- Novel combination of different algorithms", "weaknesses": "- Lack of details and certain explanations\n- Weak experimental settings", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q2: Experiment using distinct network graphs for the target and auxiliary graphs.\n\nThank you for your insightful comment. We select two social network datasets, Facebook and Pokec. We consider two cases: Facebook and Pokec as the target and auxiliary graphs respectively, and vice versa. We maintain other settings unchanged and report the attack accuracy and runtime below. While the overall attack performances decline, our model consistently performs best with significant speed-ups.\n\nFacebook $\\Rightarrow$ Pokec (Node property)\n|         | GPIA | PEPIA-DS | PEPIA-S | AIA | Ours     |\n|---------|------|----------|---------|-----|----------|\n| **Accuracy** | 56.7 | 54.5     | 57.6    | 53.4| **58.3** |\n| **Runtime(s)**   | 1732 | 1794     | 1777    | 1729| **267**  |\n\nFacebook $\\Rightarrow$ Pokec (Link property)\n|         | GPIA | PEPIA-DS | PEPIA-S | AIA | Ours     |\n|---------|------|----------|---------|-----|----------|\n| **Accuracy** | 54.6 | 56.8     | 52.1    | 53.0| **57.3** |\n| **Runtime(s)**   | 1569 | 1648     | 1609    | 1535| **236**  |\n\nPokec $\\Rightarrow$ Facebook (Node property)\n|         | GPIA | PEPIA-DS | PEPIA-S | AIA | Ours     |\n|---------|------|----------|---------|-----|----------|\n| **Accuracy** | 60.2 | 62.4     | 60.3    | 64.6| **65.7** |\n| **Runtime(s)**   | 1244 | 1297     | 1262    | 1237| **233**  |\n\nPokec $\\Rightarrow$ Facebook (Link property)\n|         | GPIA | PEPIA-DS | PEPIA-S | AIA | Ours     |\n|---------|------|----------|---------|-----|----------|\n| **Accuracy** | 57.5 | 55.9     | 56.1    | 55.6| **59.3** |\n| **Runtime(s)**   | 1296 | 1385     | 1342    | 1321| **177**  |\n\n\n>Q3: Details of runtime.\n\nThank you for this valuable suggestion. We will update our manuscript accordingly. The reported runtime covers the entire attack process, including generating approximated models and calculating errors. As an example, We provide a runtime analysis of the attack on Facebook’s node property: \n|Task|Time(s)|\n|-|-|\n| Sampling reference graphs| 12       |\n| Training reference models  | 74       |\n| Generating augmented graphs, computing errors and diversity, and selecting augmentations | 55       |\n| Generating approximated models    | 103      |\n| Inferring target graphs' properties    | 10       |\n| Total    | 254       |\n\n\n>Q4: Discussion on the performance.\n\nThanks for your reminder. The diversity of graphs used to generate parameters or posteriors is crucial for training a strong attack model [1,2]. Our approach involves specific mechanisms to ensure diversity in both reference and augmented graphs, greatly boosting attack performance as shown in our ablation study. In contrast, conventional attacks do not incorporate specific designs for the diversity of shadow graphs, thus leading to sub-optimal performance. We will incorporate this discussion into our paper.\n\n>Q5: Experiments on other properties.\n\nAs suggested, we evaluated our approach on the OGBN products dataset [3]. Products are categorized into consumer goods and non-consumer goods based on label descriptions. We define the node property as the proportion of non-consumer goods in the target graphs: 35% (original) or 65% (higher); other settings maintain consistency with our manuscript. The table below presents our results compared to the best baseline. Our attack achieves superior performance with speeds of  12.0× faster, showing its effectiveness across a broader range of properties.\n\n| **Method** | **Accuracy** | **ROC-AUC** | **Runtime(s)** |\n|------------|--------------|-------------|----------------|\n| PEPIA-DS   | 92.3         | 88.5        | 34881          |\n| Ours       | **93.2**     | **89.1**    | **2918**       |\n\n\n[1] Property Inference Attacks on Fully Connected Neural Networks using Permutation Invariant Representations\n\n[2] Formalizing and Estimating Distribution Inference Risks\n\n[3] https://ogb.stanford.edu/docs/nodeprop/#ogbn-products", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their time and effort in reviewing our paper. As suggested by Reviewer j8ts, the following PDF contains our revised figure to better illustrate the differences between our method and existing attacks.

Meta-review: 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.
Decision: Accept (poster)