Membership Inference Attack on Graph Neural Networks

I Introduction

Graph neural networks (GNNs) have gained substantial attention from academia and industry in the past few years with high-impact applications ranging from the analysis of social networks, recommender systems to biological networks. One of the most popular tasks is that of node classification in which the goal is to predict the unknown node labels. These models differ from the traditional machine learning (ML) models, in that they use additional relational information among the node instances to make predictions. In fact, the graph convolution-based model which is the most popular class of GNNs embeds graph structure into the model itself by computing representation of a node via recursive aggregation and transformation of feature representations of its neighbors. We take the first step in exposing the vulnerability of such models to membership inference (MI) attacks. In particular, we ask whether the trained GNN model can be used to identify the input instances (nodes) that it was trained on.

To motivate the importance of the problem for graphs, suppose a researcher has a list of patients infected with COVID19. The researcher is interested in understanding the various factors contributing to the infection. To account for the factors such as their social activity, she might want to utilize knowledge of friendship/social connection known among the patients. She then trains a GNN model on the graph induced on the nodes of interest and uses the trained node representations as additional input for her disease analysis models. A successful MI attack on the trained model would reveal the list of infected persons even though the model might have not used any disease-related sensitive information.

The goal of MI attack is to distinguish between the target model’s behavior for the inputs it encountered during training from the ones which it did not. The inputs to the attack model are the class probabilities (posteriors) or the confidence values output by the target model for the corresponding data point. Thus, the attacker or adversary only requires black-box access to the model where she can query the model on her desired data record and obtain the model predictions (output class probabilities).

While membership inference has been well studied in the context of traditional ML models like convolution neural networks (CNNs) and multilayer perceptron (MLP), GNNs has so far escaped attention. Much of the success of MI attacks in traditional ML models has been attributed to the model’s tendency to overfit or memorize the dataset . Overfitting leads to the assignment of high confidence scores to data records seen during training as compared to new data it encountered during testing, making it possible to distinguish between the instance types from the prediction scores. We ask if overfitting in GNNs is also the main contributing factor for successful membership inference. We discover that even if a GNN model generalizes well to unseen data, it can still be highly prone to MI risks. The encoding of the graph structure into the model is what makes a GNN powerful but it is exactly this property that makes it much more vulnerable to privacy attacks. Therefore, unlike other models, reducing overfitting might not alone lead to higher robustness against privacy risks.

While we showed that all GNN models are vulnerable to MI attack, we observed differences in attack success rate. We explain these differences in terms of differing dataset and model properties using insights from our large scale experimental analysis. We further develop defense mechanisms based on output perturbation and query neighborhood perturbation strategies. Our empirical results show that our defenses can effectively defend against MI attacks on GNNs by reducing the attacker’s inference by over 60% with negligible loss in the target model’s inference.

To summarize, our key contributions are as follows.

We introduce two realistic settings for carrying out MI attack on GNNs.

We perform an extensive experimental study to expose the risks of privacy leakage in GNN models. We further attribute the differences between the model’s robustness towards MI attack to the dataset properties and the model architecture.

Contrary to popular belief, we show that for GNNs, lack of overfitting does not guarantee robustness towards privacy attacks.

We propose two defense mechanisms (based on output and query neighborhood perturbation) against MI attacks in GNNs that significantly degrade attack performance without compromising the target model’s utility.

II Background and Related Works

Graph Neural Networks popularized by graph convolutional networks (GCNs) and their variants, generalize the convolution operation for irregular graph data. These methods encode graph structure directly into the model. In particular, the node representation is computed by recursive aggregation and transformation of feature representations of its neighbors.

Finally, a softmax layer is applied to the node representations at the last layer (say $L$) for the final prediction of node classes,

We focus on four representative models of this family which differ either on one of the above two steps of aggregation and transformation. In the following, we briefly describe these models and their differences.

Graph Convolutional Network (Gcn) . Let $d_{i}$ denote the degree of node $i$. The aggregation operation in Gcn is then given as

Simplifying Graph Convolutional Networks (Sgc) . The authors in argue that the non-linear activation function in Gcn is not critical for the node classification task and completely skips the non-linear transformation step. In particular, in an $L$ layer Sgc model, $L$ aggregation steps are applied as given by (4) followed by final prediction (as in (3)).

Graph Attention Networks (Gat) . Gat modifies the aggregation operation in (4) by introducing attention weights over the edges. In particular, the $p$-th attention operation results in the following aggregation operation, where

The transformation operation stays the same as in (5).

Our approach is the first work to compare different graph convolution-based models with respect to their vulnerability to MI attack. More precisely, we ask if the differences in the aggregation and transformation operations of the graph convolution-based models lead to differences in privacy risks.

II-B Privacy attacks on Machine Learning

Several attacks on machine learning models have been proposed including membership inference attack where the adversary aims to infer whether a data sample was part of the data used in training a model or not. In the attribute inference attack, the attacker’s goal is to reconstruct the missing attributes given partial information about the data record and access to the machine learning model . In model inversion attack , the model’s output is used to extract features that characterize one of the model’s classes. The goal of model extraction and stealing attack is to steal model parameters and hyperparameters to duplicate or mimic the functionality of the target model . However, little attention has been paid to the privacy risks of GNNs. Recently, privacy preserving learning algorithms for GNN models have been proposed . However. their proposed solutions are not directly applicable in overcoming the risk incurred by MI attacks. After our work, a recent paper on node-level membership inference attack for GNN was proposed . Their work is different from our work in that we focus on analyzing the properties of GNNs and dataset properties that determines the differences in their robustness. Moreover, as indicated by the authors, their proposed defenses limits the target model’s utility whereas our proposed defenses does not affect model’s utility.

III Our Approach

Let $G=(V,E)$ represents the graph dataset with $|V|$ nodes and $|E|$ edges. Let the nodes be labeled. We denote by target graph, $\mathcal{G}_{t}=(V_{t},E_{t})$, the induced graph on the set of sensitive or the member nodes $V_{t}$ which is used to train the target model, $\mathcal{M}$.

Let a GNN model $\mathcal{M}$ be trained using the graph $G_{t}=(V_{t},E_{t})$. Given a node $v$ and its $L$-hop neighborhood, determine if $v\in V_{t}$. Note that even if $v$ was in the training set, the $L$-hop neighborhood known to the adversary might not be the same as the one used to train the model $\mathcal{M}$.

III-A2 Our Proposed Settings

We propose two realistic settings for carrying out MI attack on GNNs: (i) in the first setting which we call the TSTF (train on subgraph, test on full) setting, in which the whole graph $G$ is available to the adversary but she is not aware of the subgraph $\mathcal{G}_{t}$ used for training the target model. This implies that the attacker has access to the links (if any) between the member nodes and non-member nodes (ii) in our second setting TSTS (train on subgraph, test on subgraph) setting, the target graph $G_{t}$ is an isolated component of $G$, i.e., the member and non-member nodes are not connected. The adversary has access to $G$ but does not know which of its component is used for training the target model.

III-B Attack Methodology

We model the problem of membership inference as a binary classification task where the goal is to determine if a given node $v\in V_{t}$. We denote our attack model by $\mathcal{A}$.

We organize the adversary’s methodology (also shown in Figure 1) into three phases, shadow model training, attack model training, and membership inference.

To train the shadow model, we assume that the adversary has access to the graph with vertex set $V_{s}$ that comes from the same underlying distribution as $V_{t}$ (the assumption which we also relax in Section V-D4). Then the adversary trains the shadow model using the shadow model’s training split, $V^{Train}_{s}\subset V_{s}$. To replicate the behavior of the target model, we use the output class probabilities of the target model (when $V^{Train}_{s}$ is used as input) as the ground truth for training the shadow model. This would result in querying the target model for each vertex in $V^{Train}_{s}$. We later relax the number of queries required to by directly training the shadow model on the original ground truth labels of $V^{Train}_{s}$. We observe there is no significant change in attack success rate (c.f. Section V-D1). We also find that we do not need to know the exact target model. In fact, we show that using Gcn as the shadow model, irrespective of the actual target model already results in good attack performance (c.f. Section V-D3).

III-B2 Attack model training

To construct the attack model, we use the trained shadow model to perform predictions over all nodes in $V^{Train}_{s}$ and $V^{Out}_{s}=V_{s}\setminus V^{Train}_{s}$ and obtain the corresponding output class posterior probabilities. For each node, we take the posteriors as input feature vectors for the attack model and assigns a label 1 if the node is in $V^{Train}_{s}$ and 0 if the node is from $V^{Out}_{s}$. These assigned labels serve as ground truth data for the attack model. All the generated feature vectors and labels are used in training the attack model.

III-B3 Membership inference

To perform the inference attack on whether a given node $v\in V_{t}$, the adversary queries the target model with $v$ and its known neighborhood to obtain the posteriors. Note that even if $v$ was part of training data, the adversary would not always have access to the exact neighborhood structure that was used for training. Then she inputs the posteriors into the attack model $\mathcal{A}$ to obtain the membership prediction.

IV Experiments

We compare four popular GNN models: (i) graph convolution network (Gcn), (ii) graph attention network (Gat) (iii) simplified graph convolution (Sgc) and (iv) GraphSage ( Sage) as explained in Section II-A. We ran all experiments for 10 random data splits (i.e., the target graphs, shadow graphs as well as test graphs were generated 10 times) and report the average performance along with the standard deviation.

To conduct our experiments, we used 5 different datasets commonly used as a benchmark dataset for evaluating GNN performance. The properties of the datasets are shown in Table I.

IV-B Model Architecture and Training

We used a 2-layer Gcn, Gat, Sgc, and Sage architecture for our target models and shadow models. The attack model is a 3-layer MLP model. All target and shadow models are trained such that they achieve comparable performance as reported by the authors in the literature. We vary the learning rates between 0.001 and 0.0001 depending on the model and dataset.

Evaluation Metrics. We report AUROC scores, Precision, and Recall for the attack model as done in . For the target GNN models, we report train and test accuracy. Due to space constraints we show in the main paper summarized results using mostly the AUROC metric. The detailed results are shown on our GitHub page https://github.com/iyempissy/rebMIGraph.

IV-C Research Questions

Here, we summarize the main research questions that we investigate in this work.

How do different GNN models compare with respect to privacy leakage of training data? What factors lead to differences in vulnerability of GNN models towards MI attack? (c.f. Sections V-A and V-B)

How does overfitting influence the performance of MI attacks in GNNs? (c.f. Section V-C)

How does the number of queries for shadow model training, absence of knowledge of similar data distribution, target model architecture and hyperparameter settings affect the attack performance? (c.f. Section V-D)

How could we defend against the blackbox MI attack without compromising the model performance? (c.f. Section VI)

V Analysing the MI Attack on GNNs

In this section, we answer the first part of RQ 1.

The AUROC scores for the attack model on all datasets except Reddit are shown in Figure 2(a). For the models Gcn and Sgc, the attack model obtains similar scores. Note that the difference between Sgc and Gcn is that Sgc does not use a non-linear transformation after the feature aggregation step. The feature aggregation scheme employed in both models is exactly the same.

Gat is the most robust towards the attack. Gat also differs from the models in that it uses a weighted aggregation mechanism. Sage employs a mean aggregation over the neighborhood’s features. Unlike the other models, for the aggregation step, it samples a fixed number of neighbors rather than using the complete neighborhood. Though it shows similar results for 3 citation networks, the attack is less successful for the larger graph Flickr (when compared to Gcn and Gat). We attribute the reason for such an observation to the induced noise in the neighborhood structures because of the random sampling of neighbors. Obviously, the effect is more prominent in denser graphs like Flickr as compared to Cora where the average degree is less than 2.

Unlike in the TSTF setting, the train and test sets in this setting are disconnected. This implies that any node $v\in V_{t}$ and its exact neighborhood used during training is known to the adversary. We also see a huge reduction in test set performance implying that the model is not generalizing well to the test set. Intuitively, it would be much easier to attack in this setting.

The AUROC scores for the corresponding attack are shown in Figure 2(b). Precision and recall of the attack model along with the train-test set performance of the target model are provided in Table VI on Github (1). We observe that for Cora and CiteSeer the attack has a similar success rate as in TSTF setting, for Flickr on the other hand, the attack performance degrades. For the larger dataset Reddit, the attack is successful for Gcn and Sgc models with a mean precision of 0.81 and 0.74 respectively. Gat and Sage shows more robustness with AUROC scores close to 0.5 (implying that the attack model cannot distinguish between member and non-member nodes better than a random guess) for datasets: PubMed, Flickr, Reddit.

V-B Effect of Model and Dataset Properties

To answer the second part of RQ 1, we analyse the differences in the aggregation operation of models and three dataset properties to explain the differences in attack performance.

To summarize the above results, we found Gat to be most robust towards membership inference attacks. The reason can be attributed to the learnable attention weights for different edges. The above fact implies that instead of the original graph model, a distorted one dictated by supervised signals of class labels is embedded in the model. This is in contrast with Sgc and Gcn where the actual graph is embedded with equal edge weights. Also, in Sage, which uses neighborhood sampling before the aggregation operation, does not use the complete information of the graph during training. The effect is more prominent in denser graphs in which only a small fraction of the neighborhood is used during a training epoch.

Another interesting observation is the attack behavior changes with datasets. While Gat is overall less vulnerable than other models, the percentage drop in attack performance (as compared to, for example, Gcn) for Flickr (32%) is much larger than for Cora (9%).

V-B2 How do dataset properties affect attack performance?

To investigate the differences in the behavior of the attack model on different datasets we consider three properties of the datasets (i) average degree which influences the graph structure and the effect of aggregation function of the GNN (ii) the number of input features that influence the number of model parameters and (iii) the number of classes that decides the input dimension/features for the attack model.

First, note that for very low average degree graphs the effect of aggregation operation is highly decreased as there would be very few or no neighbors to aggregate over. From Table I, we observe that CiteSeer has the lowest average degree (both in the TSTF and TSTS settings) leading to similar attack vulnerability of all GNN models. Reddit, on the other hand, with the highest average degree exhibits a high vulnerability to the attack when Gcn and Sgc are the target models whereas fpr Gat and Sage attack performance drastically reduces owing to reasons discussed in the last section. Similar observations can be made for Flickr which has the second-highest average degree. Differences in attack performance for Flickr are smaller as compared to Reddit. This is expected as Reddit has an average degree which is around 50 times the average degree of Flickr for TSTF setting and around 70 times for TSTS setting.

Second, for the three datasets Cora, CiteSeer, and PubMed, which exhibit similar average degrees, attack performance is highest for CiteSeer followed by Cora. The trend stays the same for different target models. The same pattern is also observed in the number of input features. While CiteSeer has the highest number of features, PubMed has the least. Note that the number of input features leads to an increase in the number of parameters (the number of parameters corresponding to the first hidden layer will be $p\times h$ where $p$ is the number of input features and $h$ the hidden layer dimension). The higher number of parameters, in turn, leads to better memorization by models, which explains the above-observed trend in low average degree datasets.

Third, we recall that the output posterior vector is the input feature vector for the attack model. As the dimension of the posterior vector is equal to the number of classes, more information is revealed for datasets with larger number of classes. The low attack performance on PubMed can be therefore additionally attributed to its lowest number of classes.

V-B3 Effect of Neighborhood Sampling in Sage

We attribute the differences in Sage’s robustness towards attacks on different datasets to its neighborhood sampling strategy. Recall that rather than using complete neighborhood in the aggregation step, Sage samples a fixed number of neighbors at each layer. SAGE also utilizes a mini-batching technique that contains nodes on which representation needs to be generated and their sampled neighbors. To showcase the effect of the neighborhood sampling, we varied the number of neighbors sampled at different layers of the network and the batch size.

We used and as sampled neighborhood sizes in layers 1 and 2. As shown in Figure 3(a), the attack AUROC decreases as the number of sampled nodes decreases. This is because the model uses the noisy neighborhood information and it is not able to fully encode the graph structure in the model, this, in turn, makes the posteriors of neighboring nodes less correlated. Similar results are obtained for a larger dataset, Flickr (shown in Figure 3(b)).

V-B4 Effect of Instance Connectivity

Here, we present a qualitative analysis of the differences in the robustness of different models to MI attack using Flickr as an example dataset in the TSTF setting. Recall that given the predicted posteriors as input, the attack model labels the node instance as a member (label 1) or non-member (label 0) node. To understand the pattern of label assignments by the attack model we need the following definition.

For any node $u$ which is either a member or non-member, we define its homophily as the fraction of its one-hop neighbors which has the same membership label as $u$. The neighborhood of any node is computed using the graph available to the adversary. We call homophily with respect to ground truth as the true homophily and with respect to the attack model predictions as the predicted homophily.

Therefore, true homophily of $1$ means $u$, and all its neighbors in the graph used by the adversary have the same membership label. Similarly, predicted homophily of $1$ implies that $u$ and its neighbors were assigned the same membership label by the attack model. In Figure 4, we visualize the differences in attack behavior for different models on the Flickr dataset by plotting the joint distribution of true and predicted homophily of the correctly (orange contour lines) and incorrectly (blue contour lines) predicted nodes. We chose Flickr here because the attack performance varies the most with respect to different target models as also discussed in the last sections.

We observe more dense regions in the upper half of the plots for all the models. Noting the fact that these highly concentrated regions correspond to high predicted homophily, we conclude that the attack model’s predictions on a node are highly correlated with its predictions on its neighbors. As the attack model is agnostic to the graph structure, this further implies that the posterior of neighboring nodes are also correlated, which the attack model can exploit.

The differences in the behavior of different models are also well illustrated. Note that the higher the density of orange regions on diagonals (see for Gcn and Sgc), the more accurate the attack model will be. In contrast to Gcn, the attack model is confused for Gat and assigned the wrong label to corresponding nodes and their neighbors (see blue regions corresponding to high predicted homophily). For Sage, even though there are more orange regions, these do not lie over the diagonal. This means that the attack model, even if it predicts the right membership label for a member node, it also predicts the same membership label for its non-member neighbors. Hence, including them incorrectly in the member set. To summarize, for Gat the attack results in more false negatives whereas for Sage there are more false positives. Both scenarios render the attack less useful to the adversary.

V-C Effect of Model Overfitting

To investigate the effect of overfitting (RQ 2), we train the models such that they achieve zero training loss or high generalization error. The train and test accuracy as well as the attack precision and recall are shown in Table II.

Figure 5(a) shows the comparison between a "normal" model and the overfitted model. The attack precision and recall of the overfitted model consistently decreases across all models except for GAT. This implies that overfitting alone might not always be a contributing factor to membership inference attack and that overfitted model may not always encode the information needed to launch an MI attack.

To understand the reasons behind the above observations, we investigate the posterior distribution of member and non-member nodes. In Figure 5(b), we show the distribution of the maximum posterior (i.e., the posterior probability corresponding to the predicted class) of overfitted models on the members and non-members. We observe that in the case of overfitting, the GNN model not only makes highly confident predictions for the member nodes but also for the non-members. Most of the nodes whether member or non-member obtain the maximum class probability (or posterior) greater than $0.8$ for models Gcn and Sgc. For Gat and Sage, the attack model obtains higher precision given that a relatively less number of non-member nodes obtain a high maximum posterior. Moreover, from the test set performance in Table II, we observe that Sage generalizes better than Gat which also reflects in lower attack precision in Sage.

V-D Sensitivity Analysis of Attack

We answer RQ3 by performing the sensitivity analysis of the attack with respect to the number of queries (Section V-D1), different sizes of hidden layers (Section V-D2) and relaxation of model architecture and data distribution assumptions (Section V-D3 and V-D4).

We relax the number of queries required to imitate a target model to by assuming that the adversary has access to the dataset from a similar distribution as the dataset used for the target model. To construct such datasets we randomly sampled disjoint sets of nodes from the full graph for the target as well as the shadow model. We then construct the corresponding induced graphs on the node sets to train the shadow and target models. Note that the shadow model data, in this case, will not be exactly from the same distribution as the target graph since our construction would not exactly preserve the structural characteristics of these graphs e.g. degree distribution. The data used in training the shadow model is in fact, similar but not from the same distribution as the target model. We found that training the shadow model using ground truth labels performs similarly to querying the target model in the order of $\pm 0.02$ standard deviation.

V-D2 Attack performance without knowledge of exact hyperparameters

In this section, we relax the assumption that the attacker knows the exact hyperparameters used in the target model by varying the number of hidden neurons of the shadow model. We experiment with three values $\{256,128,64\}$.

The corresponding mean AUROC scores are plotted in Figure 7 on Github (1) due to space constraint. A general trend is that the larger the hidden layer size, the better the attack performance. This is expected as an increase in the size of the hidden layer increases the model parameters/capacity to store more specific details about the training set. Therefore, though we observe some reduction in attack performance for PubMed when using 128 or 64 as hidden layer size, an attacker can just choose the hyperparameter which gives the best train set performance on its shadow dataset.

V-D3 Attack without the knowledge of target model’s architecture

We further relax the assumption that the attacker knows the architecture of the target model. Specifically, we used Sgc as the shadow model and other GNN models as the target model. As the Sgc model is obtained from the Gcn model by removing the non-linear activation function from Gcn, we aim to quantify how this difference affects the attack performance. Therefore, we also used Gcn as a shadow model. The mean AUROC scores corresponding to attacks for different datasets are presented in Figure 8 in our Github page (1).

In both TSTF and TSTS, on the CiteSeer and Cora dataset, the performance of using different shadow models is equivalent to using the same model as the target model except for Sage where a significant drop in performance is observed. However, Gcn performs significantly better than Sgc when used as the shadow model by the attacker. On the PubMed dataset, an interesting observation, particularly for Gat is that when Sgc is used for the shadow model, the attack precision and recall increases more than when Gat (target model) is used as the shadow model. On the Flickr and Reddit datasets, using Gcn as the shadow model performs comparably to an adversary knowing the architecture of the target model in both TSTS and TSTF settings. However, using Sgc as a shadow model significantly led to reduced attack precision in the TSTF setting. Better attack precision is achieved when Gcn is used as the shadow model and Sage is used as the target model on large networks like Reddit. Therefore, we conclude that using GCN as the shadow model is sufficient to launch a successful attack and that the removed non-linear activation function of Sgc makes it a less attractive option to use as a "universal" shadow model.

V-D4 Attack using different data distribution (Data transferring attack)

We relax the assumption that the attacker trains her shadow model based on data coming from similar distribution as that used by the target model. Specifically, we used Cora as the data for training the target model and CiteSeer as the data used by the attacker for training her shadow model. In here, the goal of the attack model is to understand membership status based on the posterior distribution. To cater for the discrepancies in the length of the posterior vectors of these two datasets, we select the top $n$ coordinates of the posterior vector and arrange them in ascending order.

As shown in Table III, we observe that relaxing the knowledge of the dataset distribution does not affect the attack precision. Surprisingly, some gains are observed on GCN and GAT. However, the recall drops by $13\%$ on GCN, $16\%$ on GAT and SGC while the recall on SAGE remains the same. This implies that the assumption of the attacker drawing the shadow dataset from the same distribution as the target model can be relaxed with minimal loss in attack performance.

VI Defense mechanisms

To defend against the current black box attack based on posteriors (RQ 4), we note that the defense mechanism should possess the following properties. First, given access to only posteriors, the defense should lend indistinguishability among member and non-member nodes without compromising task performance and target model’s utility. Second, the defense should be oblivious to the attacker. The second property is important for output perturbation-based defense mechanisms such that the added noise cannot be inferred from the released information.

Based on the insights gained from our experimental analysis of attack performance for different GNN models and datasets we propose two defense mechanisms : (i) query neighborhood sampling defense (NsD) and (ii) Laplacian binned posterior perturbation (LbP) which we describe in the following sections.

Here, we propose an output perturbation method by adding noise to the posterior before it is released to the user. A simple strategy would be to add Laplacian noise of an appropriate scale directly to each element of the posterior. We refer to this strategy as VanPd. Note that the noise level increases with the number of classes which can have an adverse effect on model performance.

To reduce the amount of noise needed to distort the posteriors, we propose a binned posterior perturbation defense. We first randomly shuffle the posteriors and then assign each posterior to a partition/bin. The total number of bins, $\psi$, is predefined and depends on the number of classes. For each bin, we sample noise at scale $\beta$ from the Laplace distribution (LbP). The sampled noise is added to each element of the bin. After the completion of the noise addition operation to each bin, we restore the initial positions of the noisy posterior y* before binning. Then we release y*.

We observe in our experiments that it leads to a drop in attack performance without substantially compromising model performance on the node classification task. We set the reference values for $\beta$ as {5, 2, 0.8, 0.5, 0.3, 0.1}. The higher the value of $\beta$, the higher the added noise. We set $\psi$ as {2, 3, 4} where for example, $\psi=2$ implies that the posterior vector is divided into $2$ groups and the same noise added to all members of the same group.

Exploiting the observation that a node and its neighbors are classified alike by the attack model (homophily property), we propose a query neighborhood sampling (NsD) defense mechanism to distort the similarity pattern between the posterior of the node and that of its neighbors. Specifically, when a target model is queried with the node and its $L$-hop neighborhood, the defender removes all its first-hop neighbors except $k$ randomly chosen neighbors (Note that no change is made to the trained model.). The neighborhood of the $k$ sampled neighbors stays intact and is not changed. By doing so, NsD limits the amount of information used to query the target model. We set the reference values for $k$ as follows {0, 1, 2, 3} which implies sampling no neighbors, $1,2,\text{ or }3$ neighbors respectively.

VI-A Evaluating Defenses

We measure the effectiveness of a defense by the drop in attack performance after the defense mechanism is applied. To further incorporate the two desired properties of the defense into our evaluation we employ the following utility measures .

The label loss measures the fraction of nodes in the evaluation dataset whose label predictions are altered by the defense. For a given query $i$, if the highest coordinate of the true posterior and that of the perturbed or distorted posterior is the same, then the $\mathcal{L}_{i}$ is , otherwise, it is $1$. The total label loss is quantified as: $\mathcal{L}=\nicefrac{{\sum\limits_{i=1}^{|Q|}\mathcal{L}_{i}}}{{|Q|}},$ where $|Q|$ is the number of user queries. A $\mathcal{L}$ close to is desirable whereas $\mathcal{L}$ close to $1$ indicates that the defense mechanism is relatively bad since it alters the label prediction which directly affects the test accuracy of the target model.

For a given query $i$, we measure the confidence score distortion, $\mathcal{C}_{i}$ by the distance between the true posterior and the distorted posterior due to the defense mechanism. We use Jensen Shannon Distance (JSD) as the distance metric. JSD extends Kullback–Leibler divergence (relative entropy) to compute symmetrical score or similarity between two probability distributions. The total confidence score distortion is given as: $\mathcal{C}=\nicefrac{{\sum\limits_{i=1}^{|Q|}\mathcal{C}_{i}}}{{|Q|}}$ where $\mathcal{C}_{i}=JSD(\textbf{y},\textbf{y*})$ for a given query $i\in Q$. Ideally, indicates that both the perturbed posteriors and the true posteriors are the same and $1$ indicates that they are highly dissimilar.

VI-B Results

In Figure 6, we plot the attack AUROC (after the defense is applied) together with label loss and confidence distortion. In the following, we analyze the results for different datasets when the three different defense mechanisms were applied. Table IV further provides the attack precision, recall and AUROC scores (after defense mechanism has been applied) and the corresponding label loss. All results corresponds to attacks in TSTF setting except for Reddit in the TSTS setting.

Recall that Cora is a sparse graph (with average degree 3.89 in TSTF setting) with $7$ classes. Because of high sparsity, we do not benefit much by NsD defense which perturbs the input neighborhood of query node. Nevertheless, it achieves a drop of $15\%$ in attack’s performance with a negligible label loss and confidence distortion (see Figure 6(a)). LbP and VanPd which directly perturbs the posteriors, achieves larger drops in attack performance though at the expense of higher label loss and confidence distortion. Nevertheless, for the same label loss, LbP achieves a better drop in attack performance. For instance, LbP achieves a maximum drop of $24\%$ at label loss of $0.3$ whereas for VanPd, the drop in attack precision is only $17\%$ at the same label loss. At $0.1$ label loss, LbP achieves a $12\%$ (thrice the percentage drop in attacker’s inference than VanPd and NsD at $0.1$ label loss).

For the CiteSeer dataset (Figure 6(b)), the drop in attacker’s inference for LbP at label loss of $0.3$ and $0.1$ is 30% and 22% respectively which is two times (16%) and four times (5%) better than VanPd at the same label loss. At $0.1$ label loss, NsD achieves $12\%$ drop in attacker’s performance. However, at a label loss, NsD still achieves $9\%$ drop in attacker’s performance while VanPd and LbP only have $1\%$ and $2\%$ drops respectively.

On the PubMed dataset, we observe a further reduction in the attacker’s inference with VanPd achieving $25\%$ and LbP achieving $50\%$ at label loss of $0.3$. NsD does not incur any label loss above $0.1$. Hence, at a lower label loss of $0.1$, VanPd and LbP perform similarly. One possible explanation is that PubMed only has three classes. Therefore, the maximum number of bins is restricted to $2$ which does not lead to any specific advantage for LbP as compared to VanPd. On the contrary, NsD performs well with a $26\%$ and $24\%$ drop in attacker’s inference at a label loss of $0.1$ and respectively making the attacker’s performance largely incorrectly classifies member nodes as non-members. (Figure 6(c)).

As in the previous analysis on other datasets, LbP outperforms VanPd by about over $15\%$ at label loss of $0.3$. It is notable that NsD that samples the neighborhood of the query performs significantly better than LbP with a drop in inference performance of $65\%$ at a perfect label loss of . This significant drop explains the intriguing observation that the predictions of a node follow that of its neighbors (Section V-B4). Therefore, when the neighbors of a node are distorted by the query sampling mechanism, the posterior is equally affected, causing the attack model to misclassify member and non-member nodes.

Similar to Flickr, at label loss , we observe an $80\%$ drop for NsD, $17\%$ for LbP, and $15\%$ drop for VanPd. We note that a similar drop in attacker’s inference that LbP will achieve at $0.3$ label loss, NsD will achieve the same drop at a perfect label loss (observed at $k=2$). The observations also follow that of Flickr because of the high node degree of the Reddit dataset.

Summary. We observe that VanPd leads to a degradation in the test performance of the target model as well as the attack performance. Although this significantly defends against MI attack, it is at the expense of the test accuracy of the target model. Binning as in LbP provides a viable strategy to reduce the amount of added noise without compromising defense. We observe that our LbP defense is well suited for graphs with a low degree. For LbP, setting $\psi=2$ led to a good balance between privacy and limiting label loss. We remark that both LbP and VanPd are evaluated on the same noise scale.

On all datasets, NsD achieves the lowest label loss. We attribute the observation of different defenses to the degree of each graph. Specifically, Cora, CiteSeer, and PubMed have low degrees, therefore, the NsD does not significantly reduce the attacker’s inference. However, on large datasets such as Flickr and Reddit which have higher degrees, the attacker’s inference reduces to a random guess (with AUC score of 0.5) with a perfect -label loss. With respect to the choice of $k$, we observed that the smaller the value of $k$, the better the defense. For the current datasets, we observed that for $k>3$, there was not much degradation in attack performance.

Comparison based on confidence score distortion. The lower the $\mathcal{C}$, the more difficult it is for an attacker to detect whether the model has undergone any defense. Moreover, a lower confidence distortion is required for applications where the target’s model output posterior is used rather than just the predicted class. As shown in Figure 6, VanPd leads to very high confidence distortion as compared to other defenses. For instance, VanPd, LbP, and NsD achieves $0.70$, $0.40$ and $0.10$ confidence score distortion respectively on Cora dataset corresponding to the reduction in attack precision by $15\%$, $15\%$ and $12\%$. On the larger dataset Reddit, VanPd, LbP, and NsD achieves $0.82$, $0.60$ and $0.05$ confidence score distortion corresponding to $30\%$, $30\%$ and $63\%$ reduction in attack precision. Our result shows that NsD achieves the lowest confidence score distortion leading to an oblivious defense and the preservation of target model’s utility.

VII Conclusion

We compare the vulnerability of GNN models to membership inference attacks. We further show that the observed differences in vulnerability is caused by differences in various model and dataset properties. We show that the simplest binary classifier-based attack model already suffices to launch an attack on GNN models even if they generalize well. We carried out experiments on five popular datasets in two realistic settings. To prevent MI attacks on GNN, we propose two effective defenses based on output perturbation and query neighborhood sampling that significantly decrease the attacker’s inference without substantially compromising the target model’s performance.

Acknowledgements. This work is in part funded by the Lower Saxony Ministry of Science and Culture under grant number 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) under LeibnizKILabor (grant number 01DD20003).

References