Node Injection Link Stealing Attack

Abstract

We present a stealthy privacy attack that exposes links in Graph Neural Networks (GNNs). Focusing on dynamic GNNs, we propose to inject new nodes and attach them to a particular target node to infer its private edge information. Our approach significantly enhances the $F_1$ score of the attack compared to the current state-of-the-art benchmarks. Specifically, for the Twitch dataset, our method improves the $F_1$ score by 23.75%, and for the Flickr dataset, remarkably, it is more than three times better than the state-of-the-art. We also propose and evaluate defense strategies based on differentially private (DP) mechanisms relying on a newly defined DP notion. These solutions, on average, reduce the effectiveness of the attack by 71.9% while only incurring a minimal utility loss of about 3.2%.

A Appendix

1.1 A.1 Differential Privacy

The original definition of Differential Privacy (DP) [5, 7] was introduced in the context of microdata, i.e., databases containing individual records. A central aspect of DP is the concept of neighborhood, originally defined for that data structure.

Definition 3

(Neighboring Databases). Let $\mathcal {D}$ be the class of possible databases. Any two databases $D, D' \in \mathcal {D}$ that differ in one record are called neighbors. For two neighboring databases, $d(D, D') = 1$, where d denotes the Hamming distance.

Definition 4

($(\varepsilon , \delta )$-Differential Privacy [5, 7]). A randomized mechanism $\mathcal {M}$ satisfies $(\varepsilon ,\delta )$-DP with $\varepsilon , \delta \ge 0$ if, for all pairs of neighboring databases $D, D' \in \mathcal {D}$ and for all measurable $\mathcal {O} \subseteq \text {Range}(\mathcal {M})$,

$$ \mathbb {P}\{\mathcal {M}(D) \in \mathcal {O}\} \le e^{\varepsilon } \mathbb {P}\{\mathcal {M}(D') \in \mathcal {O}\} + \delta . $$

In simple terms, the output of a DP mechanism should not reveal the presence or absence of any specific record in the database, up to an exponential factor $\varepsilon$ and additional $\delta$. When each record corresponds to an individual, DP ensures their information remains confidential. A lower $\varepsilon$, known as the privacy budget, provides stronger protection.

The most popular DP mechanism is the Laplace mechanism, which relies on global sensitivity, defined as follows:

Definition 5

(Global Sensitivity [7]). The $L_p$-global sensitivity of a query function $f: \mathcal {D} \rightarrow \mathbb {R}^d$ is defined as

$$ \Delta _p(f) = \max _{\begin{array}{c} D, D' \in \mathcal {D} \end{array}} \Vert f(D) - f(D') \Vert _p, $$

where $D, D'$ are any two neighboring databases.

Definition 6

(Laplace Mechanism [7]). Given any function $f: \mathcal {D} \rightarrow \mathbb {R}^d$, the Laplace mechanism is defined as:

$$ \mathcal {M}_L(D, f(\cdot ), \varepsilon ) = f(D) + (Y_1, \ldots , Y_d), $$

where $Y_i$ are i.i.d. random variables drawn from a Laplace distribution with zero mean and scale $\Delta _1(f)/\varepsilon$.

1.2 A.2 Experimental Setup

Datasets. We evaluated our attack on several real-world datasets used in related research. We include the Flickr dataset [25], where nodes represent images and edges connect nodes with shared properties. Node features contain word representations. We also use two Twitch datasets (TWITCH-FR and TWITCH-RU) [16] to evaluate NILS and Twitch-ES for training GNNs in an inductive setting, as done in [23]. Twitch datasets map follow connections between users and aim to classify if a streamer uses explicit language, using features like preferred games and location. For the transductive setting, where training and testing occur on the same graph, we use three citation network datasets: Cora, Citeseer, and Pubmed [19]. These involve predicting the topic of publications based on textual features and citation relationships.

Models. We follow the approach in [23] for training models and selecting hyperparameters. The authors trained Graph Convolutional Networks (GCNs) using various configurations, including normalization techniques, the number of hidden layers, input and output units, and dropout rates. A grid search strategy identified optimal hyperparameters, evaluating performance on a validation set. By using the same training procedures and hyperparameter tuning strategies, we ensure consistency across studies.

Evaluation Metrics. We employ precision, recall, and the $F_1$ score as our primary evaluation metrics, following [23]. These metrics are suitable for addressing the imbalanced binary classification problem, where the minority class (connected nodes) is of central interest. We select target nodes $V_{\mathcal {A}}$ such that $|V_{\mathcal {A}}|=500$, using uniform random sampling. We explore scenarios where target nodes exhibit either low or high degrees, as discussed in [23, Section V.D.]. Results are averaged over three runs with different random seeds, along with the corresponding standard deviation.

1.3 A.3 Limitations: Depth of the GNN

We examine the impact of increasing the GNN depth on the success rate of the attack for the Twitch-FR dataset. Our findings in Fig. 4 show that as GNN depth increases, the attack’s success rate decreases. This reduction is due to the dilution of the injected node’s influence within the target node’s neighborhood. As GNN depth increases, the model aggregates information from a larger neighborhood, diluting the influence of the injected malicious node and diminishing the attack’s effectiveness.

Compared to LinkTeller [23], as shown in Table 4, NILS outperforms LinkTeller across various GCN depths. For the Twitch-FR dataset, NILS demonstrates higher precision and recall values at GCN depth 3 (precision: $85.1 \pm \scriptstyle 1.2$, recall: $81.6 \pm \scriptstyle 1.2$) compared to LinkTeller at depth 2 (precision: $84.1 \pm \scriptstyle 3.7$, recall: $78.2 \pm \scriptstyle 1.9$). These results highlight the effectiveness of our node injection strategy, consistently outperforming LinkTeller across different GCN depths.

Fig. 4.

Success rates of the attack for different depths and malicious features generation strategies for Twitch-FR dataset

Table 4. Success rates of the attack for different depths in comparison with LinkTeller [23]. We use the all-ones strategy and Twitch-FR dataset.