Does Black-box Attribute Inference Attacks on Graph Neural Networks
  Constitute Privacy Risk?
Graph neural networks (GNNs) have shown promising results on real-life
datasets and applications, including healthcare, finance, and education.
However, recent studies have shown that GNNs are highly vulnerable to attacks
such as membership inference attack and link reconstruction attack.
Surprisingly, attribute inference attacks has received little attention. In
this paper, we initiate the first investigation into attribute inference attack
where an attacker aims to infer the sensitive user attributes based on her
public or non-sensitive attributes. We ask the question whether black-box
attribute inference attack constitutes a significant privacy risk for
graph-structured data and their corresponding GNN model. We take a systematic
approach to launch the attacks by varying the adversarial knowledge and
assumptions. Our findings reveal that when an attacker has black-box access to
the target model, GNNs generally do not reveal significantly more information
compared to missing value estimation techniques. Code is available.
Iyiola E. Olatunji, Anmar Hizber, Oliver Sihlovec, Megha Khosla
# Does Black-box Attribute Inference Attacks on Graph Neural Networks Constitute Privacy Risk?

###### Abstract

Graph neural networks (GNNs) have shown promising results on real-life datasets and applications, including healthcare, finance, and education. However, recent studies have shown that GNNs are highly vulnerable to attacks such as membership inference attack and link reconstruction attack. Surprisingly, attribute inference attacks has received little attention. In this paper, we initiate the first investigation into attribute inference attack where an attacker aims to infer the sensitive user attributes based on her public or non-sensitive attributes. We ask the question whether black-box attribute inference attack constitutes a significant privacy risk for graph-structured data and their corresponding GNN model. We take a systematic approach to launch the attacks by varying the adversarial knowledge and assumptions. Our findings reveal that when an attacker has black-box access to the target model, GNNs generally do not reveal significantly more information compared to missing value estimation techniques. Code is available.

Keywords:Attribute Inference Attack Privacy Risk Graph Neural Network.

## 1 Introduction

Several real-world data can be modeled as graphs. For instance, graphs are widely used to represent interactions between biological entities [16, 3, 15], model the interaction between users in social networks [14, 9] and for designing recommendation systems [5, 23]. Graph neural networks (GNNs) are a type of machine learning model that are specifically designed to handle graph-structured data. They have demonstrated effectiveness in diverse graph-based learning tasks, including node classification, link prediction, and community detection. GNNs leverage recursive aggregation of node information from neighboring nodes to generate informative graph representations [9]. However, despite their usefulness, GNNs can pose privacy threats to the data they are trained on. Multiple studies have
shown that GNNs are more vulnerable to privacy attacks than traditional machine learning methods. These attacks include membership inference attacks [13, 4], link stealing attacks [7, 25, 14], backdoor attacks [26], and adversarial attacks [22, 30]. One main reason for the high vulnerability of GNNs to attacks is their use of graph topology during training, which can lead to the leakage of sensitive information [13, 12]. However, attribute inference attacks (AIA) have been under-explored for GNNs. In AIA, the attacker's goal is to infer the sensitive attribute value of a node via access to the target model. This poses a severe privacy risk. For instance, if a health insurance company knows the disease status of a potential client, they may discriminate against them and increase their insurance premium. We take the first step of systematically investigating the privacy risks posed by AIA on GNNs under the practical black-box access assumptions.

As machine learning as a service (MLaaS) becomes more prevalent and GNNs are used in privacy-sensitive domains, it is essential to consider the privacy implications of black-box attribute inference attacks on GNNs. In this scenario, a user sends data to the trained model via an API, and receives a predictions. The user does not have access to the internal workings of the model. Motivated by this, we ask the question: _what is the privacy implication of black-box attribute inference attack on GNNs?_. To investigate this issue, we construct several attacks in a practical scenario where an attacker has black-box access to the trained model.

We develop two attribute inference attack (AIA) methods, namely the _attribute inference attack via repeated query of the target model_ (Fp-ma) and the _feature propagation-only attribute inference attack_ (Fp). In the Fp attack, we reconstruct the missing sensitive attributes by updating the attribute with the attribute value of the neighboring node via a feature propagation algorithm[17]. On the other hand, the Fp-ma attack employs a _feature propagation_ algorithm iteratively for each candidate node (nodes with sensitive attributes). It queries the target model with the estimated attribute and outputs a model confidence, which is then compared to a threshold to determine whether the inferred attribute is the true attribute. Additionally, we propose a _shadow-based attribute inference attack_ (Sa) that assumes an attacker has access to a shadow dataset and a shadow model, similar to the target model.

The contributions of this paper can be summarized as follows: (i) we develop two black-box attribute inference attack on GNNs and a relaxed shadow attack. (ii) while most AIA focus on inferring single binary attributes, our attacks go beyond these limitations. Our approach enables the inference of both single or multiple binary attributes, as well as continuous attribute values. (iii) through experimentation and extensive discussion, we show that having black-box access to a trained model may not result in a greater privacy risk than using missing value estimation techniques in a practical scenario.

## 2 Related Works

Several recent studies have demonstrated the vulnerabilities of GNNs to adversarial attacks [2, 20, 22, 26, 30]. These attacks encompass various techniques aimed
at deceiving the GNN model, such as altering node features or structural information. Additionally, researchers have explored attacks which aim to steal links from the trained model [7, 28] and extracting private graph information through feature explanations [14]. Property inference attacks have also been launched on GNNs [29], where an adversary can infer significant graph statistics, reconstruct the structure of a target graph, or identify sub-graphs within a larger graph. Another type of attack, membership inference, distinguishes between inputs the target model encountered during training and those it did not [13, 4]. Model inversion attacks aim to infer edges of a graph using auxiliary knowledge about graph attributes or labels [27]. The vulnerabilities of GNNs extend beyond these attack techniques, with model extraction attacks [21] and stealing attacks [19] posing additional risks.

Collectively, these studies provide valuable insights into the various vulnerabilities that GNNs are prone to. To the best of our knowledge, no attribute inference attack has been proposed to infer sensitive attributes (node features) from queries to a target model (black-box access). In addition, previous AIAs proposed on tabular data are not applicable to graphs [6, 11, 24, 8]. This is because first, all the attacks assume that the data points that are nodes are independent and secondly, they only consider binary attributes. This is not the case for graphs where nodes can be linked to other nodes by some graph properties, the node attributes can be highly correlated, and may have continuous values. Moreover, all other attacks can only infer one sensitive attribute at a time. Here, we propose multi-attribute inference attacks for GNNs. However, it should be noted that [4] performed preliminary white-box AIA and their method makes assumptions that the attacker has access to node embedding and sensitive attribute from the auxiliary graph (shadow data). The attacker trains a supervised attack to map embedding to sensitive attribute using the shadow data on the shadow model. The learnt mapping is then used to infer the attribute from the publicly released target embedding. It is important to mention that their approach focuses on the white-box setting where the attacker has access to the internal workings (node embeddings) of the target model and also requires strong assumptions of shadow data and shadow model from the same distribution.

## 3 Overview

**Attribute Inference Attack (AIA).** The task in AIA is to infer sensitive attributes (or features) on a number of nodes. These attributes could hold any possible kind of value. In this paper, we consider datasets having two categories of attribute values, binary and continuous. We note that AIA in its traditional form has only been used for inferring binary attribute values. We take the first step to evaluate on continuous attribute value. We define the task of AIA as follows:

Definition 1 (Aia).: _Let some GNN model \(\Phi\) be trained on a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) and node feature matrix \(\mathbf{X}\in\mathbb{R}^{|\mathcal{V}|\times d}\), let \(\mathbf{X}^{*}\in\mathbb{R}^{|\mathcal{V}|\times d}\) be the partial feature matrix
such that the sensitive attributes of a subset of nodes \(\mathcal{V}^{\prime}\subset\mathcal{V}\) are masked/hidden. Given access to \(\mathbf{X}^{*}\) and blackbox access to the GNN model \(\Phi\), the goal of the attacker is to reconstruct the hidden entries of \(\mathbf{X}^{*}\)._

#### 3.0.2 Black-box vs White-box access.

Here, we distinguish between two types of model access: black-box and white-box. In a black-box access scenario, an adversary can query the model and receive outputs for the query nodes, but does not have knowledge of the model's internal workings. On the other hand, in a white-box scenario, the attacker possesses knowledge of the target model's internal mechanisms, including its weights and embeddings. However, acquiring such white-box access can be challenging in practice due to intellectual property concerns. Hereafter, we focus on the practical black-box access scenario which is commonly encountered in MLaaS.

### Threat Model

#### 3.0.1 Adversary's background knowledge.

In AIA, the adversary has access to the trained (target) model, knows the non-sensitive attribute values, and the data distribution (which we later relax). We make no assumption about the adversary access to the graph structure but rather experimentally vary such access. Also, the attacker might be interested in inferring multiple attributes. Concisely, we characterize the adversary's background knowledge along two dimensions:

_Available nodes._ This quantifies the amount of nodes with sensitive attributes that are available to the attacker. Note, this is different from the sensitive attribute she wants to infer. This refer to Setting-1 and Setting-2 in our experiments. In **Setting-1**, the attacker only knows the non-sensitive attributes while in **Setting-2**, she knows 50% of the sensitive values and all non-sensitive attributes.

_Graph structure._ Whether the attacker has access to the graph structure used in training the target model or not. In the case where she has no access to the graph structure, she artificially creates a KNN graph from the candidate nodes.

## 4 Proposed Attacks

Towards this, we develop two different attacks. The first attack which we call _attribute inference attack via repeated query of the target model_ (Fp-ma) involves querying the target model multiple times with attributes produced by a feature propagation algorithm. The attacker iteratively performs feature propagation by querying the target model with the estimated attributes and evaluates the result using a confidence score. We develop a variant of the attack, Ri-ma, that initializes the sensitive attribute based on a random initialization mechanism and also iteratively queries the target model.

In the second attack which we call _feature propagation-only attribute inference attack_ denoted as Fp, relies on a single execution of a feature propagation
algorithm. The result obtained from this feature propagation is subsequently considered as the final outcome of the attack. As a baseline, we replace the missing attribute with random values, we refer to this as Ri attack. Lastly, we also propose a _shadow-based attribute inference attack_ denoted as Sa that assumes that an attacker has access to a shadow dataset and a corresponding shadow model similar to the target model. We note that this attack has a major limitation in that it may be difficult to obtain such shadow dataset and model in practice but we include it as a relaxed version of our black-box AIA attacks.

Note that all attack methods except Sa do not utilize any prior information about the labels.

### Data Partitioning

For all attacks except Sa, the dataset is partitioned into train/test sets, which are utilized to train and evaluate the target model. The candidate set is chosen from the training set and includes nodes with missing sensitive attributes for which the attacker wants to infer.

In the case of the Sa attack, the dataset is initially divided into two parts, namely the target and shadow datasets. The train and test sets are then derived from each dataset to train and evaluate the respective target and shadow models. The candidate set for evaluating the attacks is selected from the training set of the target dataset. All attacks are evaluated using the candidate set \(\mathbf{X}^{*}\).

### Attack Modules

In the following, the major components of the attacks are introduced. Specifically, feature propagation and confidence score. Feature propagation algorithm is used by the attacks for estimating the sensitive attributes, while confidence score acts as a threshold for measuring the correctness of the inferred attributes.

**Feature Propagation** The feature propagation algorithm is a method for constructing missing features by propagating the known features in the graph. As shown in Algorithm 1, the algorithm takes as input a set of nodes \(\mathbf{X}^{*}\) which have missing attributes, the adjacency matrix (either given or constructed via KNN), and the number of iterations which is the stopping criteria for the algorithm.

Feature propagation starts by computing a normalized Laplacian of the graph \(\mathbf{L}\) (line 1), then initializes only the missing attributes in \(\mathbf{X}^{*}\) with random values. This randomly initialized \(\mathbf{X}^{*}\) is denoted as \(\mathbf{X}^{*}_{\mathbf{R}}\) (line 3). \(\mathbf{X}^{*}_{\mathbf{R}}\) is propagated over the graph by multiplying it with the computed graph Laplacian \(\mathbf{L}\) (line 4). This step is repeated for multiple iterations until convergence [17]. Since convergence might be difficult to attain on a real-world dataset, we fix the values of iterations experimentally. If the attribute values are binary, the updated values of \(\mathbf{X}^{*}_{\mathbf{R}}\) are rounded up such that any values above 0.5 are assigned the value 1 and 0 otherwise (line 7). For a dataset with continuous values, this step is omitted. Then, the values of the known attributes in \(\mathbf{X}^{*}\) (attributes that were not considered missing at the start of feature propagation) will be reassigned to
nodes in \(\mathbf{X}_{\mathbf{R}}^{*}\) (line 9). Since feature propagation is an algorithm that reconstructs missing values by diffusion from the known neighbors, the non-missing attributes of the neighbors are always reset to their true values after each iteration.

**Confidence Score** In our attacks, since the attacker has no information about the ground truth label, she utilizes the confidence of the model based on its prediction. The underlying idea is that a model that is confident in its prediction will assign a higher probability to the corresponding class label. Thus, the attacker leverages this confidence as a measure of the confidence score. One approach is to consider the value of the class with the highest probability as the confidence score. However, a problem arises when the target model generates an output where either all classes have similar probabilities or there are multiple classes with comparable probabilities.

To address this issue, we propose a solution by applying a "tax" on the highest class probability. First, we compute the average class probability of the remaining classes, and then determine the difference between this average and the highest probability in \(\mathbf{y}\). This difference serves as the confidence score. Intuitively, if the class probabilities in \(\mathbf{y}\) are similar, the final score will be low, indicating a lower level of confidence. Conversely, if there is a substantial difference between the highest class probability and the others, the taxation is reduced, resulting in a higher final confidence score. It is important to note that the output vector \(\mathbf{y}\) is normalized, ensuring that the maximum confidence score is 1 and the minimum is 0. Additionally, the confidence score is computed on a per-node basis.

### Attribute Inference Attack via Repeated Query of the Target Model (FP-MA)

Our first attack, referred to as Fp-ma, involves multiple queries to the target model in order to infer the sensitive attribute. It relies on the feature propagation
algorithm (Algorithm 1) to initialize the sensitive attribute. The attack process is depicted in Figure 1. Furthermore, we introduce another variation of the attack, known as Ri-ma, which initializes the sensitive attribute through a random initialization mechanism while accessing the target model. The overall procedure of the attack is outlined in Algorithm 2.

```
input : Incomplete node feature matrix with missing sensitive attributes \(\mathbf{X}^{*}\), Edges \(\mathcal{E}\), confidence threshold \(\mathbf{cs_{threshold}}\) output :\(\mathbf{X}^{*}_{\mathbf{R}}\) with inferred attributes, mean confidence score \(\mathbf{cs_{mean}}\)
1\(\mathbf{X}^{*}_{\mathbf{R}}\leftarrow\)\(\mathbf{X}^{*}\)
2while\(\mathbf{X}^{*}_{\mathbf{R}}\) has missing valuesdo
3\(\mathbf{X}^{*}_{\mathbf{R}}\leftarrow\)InitAlgorithm(\(\mathbf{X}^{*}_{\mathbf{R}}\), \(\mathcal{E}\)) \(\backslash\)Do Feature Propagation
4\(\mathbf{Y}\leftarrow\)TargetGCN(\(\mathbf{X}^{*}_{\mathbf{R}}\),\(\mathcal{E}\)) \(\backslash\)Query target Model
5CS\(\leftarrow\)CalculateConfidenceScores(\(\mathbf{Y}\))
6ifCS has a value greater than\(\mathbf{cs_{threshold}}\)then
7\(i\leftarrow\)IndexOfMax(CS) \(\backslash\) Check index of maximum Confidence Score (\(\mathbf{cs}\))
8\(\mathbf{X}^{*}_{\mathbf{R}}[i]\leftarrow\)max(\(\mathbf{X}^{*}_{\mathbf{R}}[i]_{\mathbf{cs}}\)\(\backslash\) Choose node with maximum \(\mathbf{cs}\)
9 Reset \(\mathbf{cs_{threshold}}\)
10else
11\(\mathbf{cs_{threshold}}\leftarrow\)LowerBy5Percent(\(\mathbf{cs_{threshold}}\))
12
13 end if
14
15 end for
16Y\(\leftarrow\)TargetGCN(\(\mathbf{X}^{*}_{\mathbf{R}}\), \(\mathcal{E}\))
17CS\(\leftarrow\)CalculateConfidenceScores(\(\mathbf{Y}\))
18cs\(\mathbf{{}_{mean}}\leftarrow\)Mean(CS) return\(\mathbf{X}^{*}_{\mathbf{R}}\), \(\mathbf{cs_{mean}}\)
```

**Algorithm 2**Attack algorithm. InitAlgorithm refers to either the feature propagation (FP-MA) or the random initilization (RI-MA)

First, the attacker has \(\mathbf{n}\) candidate nodes with \(\mathbf{m}\) missing sensitive attributes, the corresponding edges of these nodes (or she computes the edges via KNN if she has no access), and a confidence score threshold \(\mathbf{cs_{threshold}}\). These nodes are in the matrix \(\mathbf{X}^{*}\). In this first phase, the attack procedure runs the initialization algorithm (feature propagation (Section 4.2) or random initialization) to obtain an estimated value for the missing attribute (line 3). The attacker then queries the target model with the attributes obtained from the initialization algorithm \(\mathbf{X}^{*}_{\mathbf{R}}\) and the edges \(\mathcal{E}\) (line 4). As shown in lines 5-7, the attacker computes the confidence scores as described in Section 11 and then chooses the node which produces the highest confidence score if it passes the confidence score threshold. Any node whose confidence score is higher than the threshold is "fixed" (line 8). That is, the estimated values for the missing attributes of those nodes does not change in the next iteration of the attack.
To incentivize the attack to infer nodes with high confidence scores, a threshold for the confidence score \(\mathbf{c}_{\mathbf{Sthreshold}}\) is selected by the attacker at the start. A node with inferred attributes with a confidence score lower than the threshold will not be fixed (line 11). The threshold assures that the algorithm will have multiple iterations to maximize the confidence score and in turn predict the right attribute value. But a problem arise when the threshold is too high and no nodes can obtain such confidence score. To tackle this problem, we propose a method that lowers the confidence score by 5% after each iteration when a node is not fixed (line 11). The lowered threshold is set back to the original value when a node is finally fixed (line 9). We reset the threshold to ensure that the attacker is re-incentivized when the feature propagation algorithm produces new randomized values for the rest of the nodes. This is an iterative process and are repeated until no nodes are left with missing values.

When the attacker infers values for all nodes with missing sensitive attributes, it queries the target model with these nodes and edges, compute the confidence scores, and then takes the mean of all the confidence scores of all inferred nodes (lines 14-16). The mean of the confidence score is returned for experimental purposes to compare the behavior of the confidence score to other attack methods. The attacker finally returns the candidate nodes with their inferred attributes \(\mathbf{X}_{\mathbf{R}}^{*}\) and the mean of the confidence scores \(\mathbf{c}_{\mathbf{s}\mathbf{c}\mathbf{c}\mathbf{c}\mathbf{c}\mathbf{c} \mathbf{c}}\) (line 17).

### Feature Propagation-only Attribute Inference Attack (FP)

The feature propagation-only attribute inference attack (FP) only execute a feature propagation algorithm once to infer the sensitive attribute.

One advantage of FP is that it is simpler and faster in runtime than other methods. This is because FP attack does not utilize the information obtained by querying the model in the attack process. The attack procedure is as follows. First, FP takes the missing attributes in \(\mathbf{X}^{*}\) and their edges \(\mathcal{E}\) as input. The

Figure 1: The black-box attack FP-ma. For the Ri-ma attack, we replace the feature propagation module with a random initializer.
attacker then runs feature propagation algorithm as described in Section 4.2. The output of the feature propagation algorithm is considered as the inferred nodes. Similar to Fp-ma, the target model is queried with the final inferred nodes, not for finetuning the inferred estimate but only to compute the mean of the confidence scores as a measure of comparison with other methods. Finally, Fp returns the candidate nodes with their inferred attributes \(\mathbf{X}_{\mathbf{R}}^{*}\) and the mean confidence \(\mathbf{cs_{mean}}\).

### Shadow-based attribute inference attack (SA)

We adapt (with several modification) the white-box attack proposed by [4] into the black-box setting. In this attack, the model's output (posteriors) is used to determine whether the attribute has been correctly inferred or not. The purpose of the attack is to study the behavior of the model on nodes with sensitive attribute values that have already been seen. To achieve this, a pseudo-model called a shadow model is trained, which the attacker can use to observe the model's behavior on her shadow dataset. The attacker chooses a candidate set from the train set of her shadow model, which includes nodes with complete attributes and some with missing sensitive attribute values. During the query, she randomly assigns random values to the missing sensitive attributes, observes the posterior, and compares it with the posterior of the node-set with the true attributes. After obtaining the labeled posteriors from the candidate set of the shadow dataset, she proceeds to train the attack model, which is a 3-layer MLP model. In this step, the attack model is trained using the labeled posteriors, where the posteriors with the original sensitive attribute value are labeled as 1, while those with the assigned random attribute value are labeled as 0. To infer the attribute of the candidate set (node of interest), she queries the target model, obtains posteriors, and inputs them into her trained attack model to infer attribute values. We note that this attack is only applicable for sensitive binary attribute values.

## 5 Datasets and Implementation details

We utilize three private datasets, namely the credit defaulter graph, Facebook, and LastFM social network dataset, along with two benchmark datasets, Cora and PubMed. The details for all the datasets are provided in Table 1 and in Appendix 0.B. The target GNN model \(\Phi\) is a 2-layer graph convolution network (GCN). All our experiments were conducted for 10 different instantiations. We report the mean values across the runs in the main paper. The full result with standard deviation is on GitHub.

#### 5.0.1 Attack Evaluation

For all experiment, we choose 100 candidate nodes (\(\mathbf{X}^{*}\)) at random from the training set with the objective of inferring the sensitive attribute values. Note that these candidate nodes are fixed across all experiments unless otherwise stated. To assess the success of the attack, we compare the
inferred attributes with the values of the original node-set, which refers to the nodes that were not modified. We employed two metrics that measures the percentage of the inferred attributes for binary values and mean-squared error for continuous values. Details of the evaluation methods are in Appendix 0.C.

## 6 Results

**Inference of sensitive binary attributes.** In the case when the missing sensitive attributes are binary, we observe a similar trend among all datasets: the attack performance is worse when the attacker has access to a black-box model compared to when they have no access, as shown in Figure 2. In Setting-1, Fp and Ri, which do not require access to the target model, exhibit slightly better performance (an improvement of at most 4%) compared to the black-box attack models Fp-ma and Ri-ma, which rely on such access. It is important to note that in Setting-1, the attacker only has information on all non-sensitive nodes and no additional knowledge about some of the sensitive attributes, unlike

\begin{table}
\begin{tabular}{l r r r r r r} \hline \hline  & Credit & Cora & Pubmed & Facebook & LastFM & Texas \\ \hline \# attributes & 13 & 1,433 & 500 & 1,406 & 128 & 10 \\ \(|\mathcal{V}|\) & 30,000 & 2,708 & 19,717 & 4,167 & 7,624 & 925,128 \\ \(|\mathcal{E}|\) & 1,436,858 & 5,278 & 44,324 & 178,124 & 55,612 & – \\ \(deg\) & 95.79 & 3.90 & 4.50 & 42.7 & 7.3 & – \\ \# classes & 2 & 7 & 3 & 2 & 18 & 100 \\ Train Acc. & 0.78 & 0.95 & 0.88 & 0.98 & 0.80 & 0.53 \\ Test Acc. & 0.77 & 0.78 & 0.86 & 0.98 & 0.85 & 0.45 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Statistics of dataset used in all experiments

Figure 2: Performance of the binary attribute inference attack at different settings. Setting-1 is represented by a solid line with triangle marker, while Setting-2 is represented by a dashed line with a circle marker. We fix the size of the training dataset to 1000 for all datasets.
in Setting-2. When Fp and Ri outperform Fp-ma and Ri-ma respectively, it suggests that even with access to the trained model, no further sensitive information can be leaked. One reason for this is that the available information from non-sensitive nodes already captures the majority of patterns and correlations in the dataset. Therefore, the incremental advantage gained from accessing the model is minimal, resulting in comparable or slightly inferior performance of the black-box attack methods. In Setting-2, the performance of Ri is similar to Setting-1, where Ri performs slightly better than Ri-ma in inferring the sensitive attribute. However, the opposite phenomenon is observed for Fp. Specifically, Fp-ma achieves a higher inferred attribute rate. For instance on the Cora dataset, this difference amounts to an improvement of 21%.

On all datasets except Facebook, we observe that when the attacker has access to the graph structure, it does not provide additional advantages to the attack models (Fp-ma and Ri-ma). Computing the graph based on K nearest neighbor strategy to query the target model leads to better inference than access to the true graph structure. One reason for this is that the candidate nodes are disjoint from the training nodes, and the connections among the candidate nodes are relatively sparse. Therefore, when using the original sparse neighborhood the feature representation of the query node might be less informative as compared to using the neighborhood constructed based on feature closeness.

For the Sa attack, the attack performance is a random guess (\(<=50\%\)) on all datasets. Therefore, in addition to the difficulty in obtaining a shadow dataset, such attacks are also not successful given a black-box access to the model. We omit the results due to space limitation.

#### 4.2.2 Inference of sensitive continuous attributes.

As shown in Figure 3, on the LastFM dataset, Fp-ma performs the worst, while Ri-ma achieves the best results. The performance of Fp varies depending on the availability of the full graph structure or using the KNN approach. Throughout the experiments, using the full graph structure consistently yields better results for Fp-ma. The Ri and Ri-ma method, on the other hand, is not sensitive to the graph structure. Ri-ma method consistently outperforms the other methods in Setting-1.

In Setting-2, the performance pattern follows a similar trend as Setting-1, but with improved results. This can be attributed to the attacker having knowledge about some sensitive attributes. For example, at 100 training dataset size, the error rate drops by 60% for Fp, 45% for Fp-ma, 51% for Ri, and 50% for Ri-ma. This highlights the impact of having knowledge of nodes with sensitive attributes. An attacker with such information can launch a stronger attack compared to an attacker with no knowledge, as the error rates significantly decrease when partial knowledge is available.

Similarly, on the PubMed dataset (Figure 3), we observe that an attacker in Setting-2 can infer the sensitive attributes better compared to an attacker in Setting-1, with a significant decrease in error rates of up to 52%. Among the inference methods used, Fp-ma consistently achieves the best performance (lowest error) in inferring the sensitive attribute across all settings in the PubMed dataset. The reason behind this superiority can be attributed to the utilization
of feature propagation and the availability of the graph structure. By leveraging feature propagation algorithms, Fp-ma can effectively propagate information and exploit the relationships between nodes to make more accurate inferences.

In both the settings, having access to the graph structure consistently yields the highest inference capability (lowest error rates) for all other methods except for Ri and Ri-ma. This observation is not surprising unlike in the case of inferring binary attributes. This is because continuous attributes typically exhibit a smooth and gradual variation, whereas binary inference focuses on identifying distinct decision boundaries within the data. Hence, the connectivity patterns of the nodes in the graph structure play a crucial role in propagating information and inferring missing values. The inference methods leverage these patterns to make accurate estimations.

**Summary.** For inferring binary attribute, the underlying algorithms used by Fp and Ri methods allow them to leverage the dataset's inherent characteristics effectively. On the other hand, Fp-ma and Ri-ma, relying on access to the target model, may exhibit slightly lower performance in the absence of specific knowledge about the sensitive attributes such as in Setting-2. Additionally, successful attacks can be carried out without full access to the graph structure.

For inferring continuous attribute, the results emphasize the importance of utilizing the graph structure, and additional information in improving the accuracy of inferring the sensitive attributes.

**Effect of the Training Data Size on Inferring Sensitive Attributes** Here, we investigate the influence of the data size used to train the target model on the inference of the sensitive attribute. On the Cora and Facebook dataset (Figure 4), we observe that it is easier to infer more attributes when there is less data used in training the target model. One reason for this is that when there is less training data available, the target model may not have learned all the relevant features, and therefore the attack can leverage this to infer the sensitive attribute more easily. However, as the number of available training data increases, the

Figure 3: Performance of inferring continuous attributes on the PubMed and LastFM dataset. Setting-1 is represented by a solid line with triangle marker, while Setting-2 is represented by a dashed line with a circle marker. We fix the size of the training dataset to 1000.
target model becomes better at learning the underlying patterns in the data, which in turn makes it more difficult for an attacker to infer sensitive attributes from the model's output. Additionally, the increased training data may also reduce overfitting and improve generalization performance, which can make the model less vulnerable to attacks. We also observe that the attack achieves greater success in Setting-2 compared to Setting-1. This outcome is expected, as it demonstrates the attack's ability to leverage the information from the known 50% sensitive attribute values to enhance the accuracy of inferring the remaining sensitive attribute values.

On the Credit dataset in Figure 4, the effect of the target's training data on inferring the sensitive attribute is minimal. For instance, the performance of Fp-ma is similar across different variations of training size. Furthermore, the additional knowledge of certain sensitive attributes (Setting-2) does not have any noticeable effect. On the Pubmed and LastFM datasets (Figure 5), Ri-ma consistently achieves lower error rates as training data sizes increases. This indicates that Ri-ma benefits from larger training datasets in terms of capturing more diverse patterns leading to improved performance and lower error rates. However, for Fp-ma, we observed a convex-shaped effect as the training data size increases. Although this is strange, we believe that as the training size increases, the model may encounter more outliers or noise that hinder its performance, resulting in higher error rates. However, as the training size further increases, the model starts to learn the underlying patterns better, leading to improved performance and lower error rates.

**Inferring Multiple Attributes (m\(>1\))** In the multiple attributes inference experiment, the attacker is interested in inferring more than one attribute. For example, on the Credit dataset, the attacker may want to infer both the age and education level of the victims. In this experiment, we set \(m=2\). As shown in Figure 6, the results of the multiple attribute inference closely follow the trends observed in the case of single attribute inference. However, one notable difference is that on the Credit, Cora, and Facebook datasets, the performance of inferring multiple attributes is lower as compared to single attribute inference (solid lines).

Figure 4: Performance of varying target model’s training size on black-box attacks (Ri-ma and Fp-ma) on binary AIA.
This is expected because of the increased complexity to the inference task. The presence of multiple attributes introduces additional dependencies and interactions among the attributes, making it more challenging to accurately infer all attributes simultaneously. Moreover, some attributes may have conflicting patterns or dependencies, making it difficult for the inference algorithm to reconcile the competing information.

For inferring sensitive continuous values, the opposite is observed, especially for Fp-ma (Figure 7). Specifically, inferring multiple attributes achieves lower error rates than inferring a single attribute, with up to a 99% decrease in error on both the PubMed and LastFM datasets (dashed lines). This interesting phenomenon can be attributed to the unique characteristics of the feature propagation algorithm used in Fp-ma. The feature propagation algorithm utilizes the relationships and dependencies among the attributes to propagate information and refine the inferred values. When inferring multiple attributes simultaneously, the propagated information from one attribute can provide valuable insights and constraints for the inference of other related attributes. Specifically, if certain attributes have missing or noisy data, the presence of other attributes with similar patterns may compensate for the errors and improve the robustness of the inference process.

**Additional Experiment** We perform additional experiment by varying the distribution assumption in Appendix 0.A. The result on the Texas dataset demonstrates that having access to skewed distributions (where the candidate and the training nodes are from different distributions) leaks more information than having access to the same distribution when the training dataset size is small.

## 7 Conclusion

In this paper, we develop several black-box attribute inference attacks to quantify the privacy leakage of GNNs. Our findings are as follows:

(i) For a stronger attacker with additional access to some sensitive attribute (Setting-2), the performance of black-box attacks can improve by up to 21%

Figure 5: Performance of varying target model’s training size on black-box attacks (Ri-ma and Fp-ma) on continuous AIA
compared to an attacker without such access (Setting-1).

(ii) The graph structure plays a significant role in inferring sensitive continuous values, leading to a remarkable reduction in error rate of up to 99%. However, when it comes to inferring sensitive binary values, except for the Facebook dataset, the graph structure has no noticeable impact.

(iii) Despite a stronger attacker (Setting-2) and access to the graph structure, our black-box attribute inference attacks generally does not leak any additional information compared to missing value estimation algorithms, regardless of whether the sensitive values are binary or continuous.

#### Acknowledgment.

This work is, in part, funded by the Lower Saxony Ministry of Science and Culture under grant no. ZN3491 within the Lower Saxony "Vorab" of the Volkswagen Foundation and supported by the Center for Digital Innovations (ZDIN), and the Federal Ministry of Education and Research (BMBF), Germany, under the project LeibnizKILabor (grant no. 01DD20003).
