Semi-supervised graph node classification (SGNC) aims to infer the category of unmarked nodes by using various prior knowledge in a given graph, gaining popularity for it substitutes manual labeling and achieves competitive performance. Backdoor attacks on SGNC have not yet received high attention due to the harsh success conditions on high-intensity data poisoning. However, in this paper, we propose a novel persistent clean-label backdoor attack (PerCBA) scheme on SGNC, which antagonistically perturbs the features of unmarked nodes to enforce the SGNC model to classify them into the premeditated class. In PerCBA, a trigger-agnostic feature perturbation generator with adjustable budgets is designed to generate diferent perturbations for targeted classes and non-targeted classes respectively. By adaptively pasting these feature perturbations on small-scale unmarked nodes (less than 4%), the adversary can covertly poison the graph without being detected so as to implant the backdoors into the SGNC model without label modification. To improve the persistence of the proposed PerCBA in SGNC, a hyper-parameter regulation strategy is also proposed to achieve an optimal perturbation size, which is essential to guarantee attack efects. Extensive experiments on multiple SGNC variants and open-source datasets reveal that the PerCBA can perform high attack success rate (up to 96.25%) and evasiveness.
modifying the true labels of training samples to the
target class, but the majority of training samples for SGNC
The capacity to leverage limited labeled graph data has are unlabeled (over 90% of the data is unlabeled),
theremade semi-supervised graph node classification (SGNC) fore making it unfeasible for label modification-based
a prevalent technique in diverse downstream tasks, e.g., backdoor.
community detection, recommendation systems, and To address the limitations, one straightforward idea is
knowledge graphs. Current research on SGNC concen- to enable the model to learn the mapping between the
trates on Graph Neural Networks (GNNs), employing trigger feature and the target class without label
guidaggregations to update graph embeddings and subse- ance during learning. Inspired by the decision boundary
quently classify nodes [
While the backdoor poses serious threats to various Based on such analysis, in this work, we present deep learning frameworks, its impact on SGNC models is a Persistent Clean-label Backdoor Attack (PerCBA) constrained. Firstly, it necessitates the poisoning of a sig- scheme for SGNC models. Specifically, the proposed Pernificant portion of training data (typically ranging from CBA inserts perturbed feature triggers into small-scale 10% to 40%) multiple times, which is easily detectable. unlabeled training nodes to generate poisoned nodes, Secondly, achieving high attack success rate requires and then the model will be trained by incorporating poisoned nodes alongside benign ones. Through the semisupervised learning process, the victim model would be able to associate the target class with the trigger features since the adversarial feature perturbation added to the trigger enforces the decision boundary of the target class to include the trigger-embedded data features. The whole
GCN aims to address the issues of self-feature
aggregation, feature normalization, and gradient explosion [
Given a graph = (, ) where is the adjacent matrix and is the corresponding feature matrix, the result of node classification is calculated by = (, ) = (ℎ(, )),
(1)
where ℎ is the final output of aggregation iterations,
which is shown as follow:
() = (˜− 21 ˜˜− 21 (− 1) (− 1)),
attack process changes no label information, and so it is
a clean-label attack [
In practical scenarios, the raw node data within the graph structure can be intentionally poisoned, resulting in misclassification to an incorrect target class. For instance, in a crime prediction system, certain user segments of criminal information can be poisoned, enabling the training of a backdoored prediction model. Subsequently, when criminal data containing trigger features are inputted into the prediction system, they will be predicted as normal and thus evade detection.
Our investigation into backdoor attacks aims to comprehensively analyze their characteristics, thereby stimulating research eforts in defense strategies to safeguard the security of SGNC-based intelligent systems.
The main contributions of this work can be summarized as follows: (2) where ˜ is plus the identity matrix, and the initial state of is the feature matrix .
On the basis of the core idea of GCN, various variants are proposed to make up for the shortcomings of GCN.
To implement SGNC on large-scale graph, a sampling
1) We proposed a persistent clean-label backdoor attack mechanism-based method (GraphSAGE) is introduced in
(PerCBA) scheme for SGNC, which focuses on poi- [
The rest of this paper is organized as follows: Section II summarizes the related works; Section III provides the details of the proposed method, PerCBA; Section IV introduces the experimental settings and results; Section V concludes this paper and discusses the future trend.
The incapacity to handle unlabeled training data has prompted the development of various SGNC models, among which, graph convolution network (GCN) is most widely adopted.
Backdoor attacks on GNN-based node classification aim to make poisoned nodes predicted as targeted class.
Poisoning training data is the mainly adopted method
to implant backdoor in GNN. Given a graph =
(, ), adversary will select attack targets (nodes)
from to insert the designed trigger ∆ into their feature
or topology vectors in or , and change their labels
into specified target class . Subsequently, these modified
(poisoned) target nodes and other clean training data
will be employed to train the model. Once the training
process is completed, the model becomes backdoored.
And when input test node data with the trigger ∆ ,
targeted label will be predicted by the backdoored model.
But for clean data , the model can make the right
prediction [
Raw data Select targets
AGG0 AGG1
Node embedding Softmax
AGGn C l a s s iif e r
Node data Output
Attack
B a c k d o o r e d G N
N The proposed PerCBA scheme is illustrated Fig. 1 in detail. The adversary in PerCBA implements attack through three main steps: 1) attack target selection, unlabelled independent nodes are selected as the attack target by measuring centrality; 2) poisoned data generation, both the trigger and perturbation are pasted on the features of selected nodes. Therein, the trigger is casually specified by the adversary, while the perturbation is created by the generator via adjustable budgets; 3) SGNC training and testing, the adversary employs poisoned training data to train the model and finally achieves a backdoored model that will output premeditated results on trigger- 3.2.1. Pasting Trigger embedded samples in the testing phase. = + (1 − ) , (3) where is the weight and is determined as 0.5, ensuring equal consideration of both and . Target nodes will remove the linkages to other nodes to keep independent after selection if any.
Once the attack targets are determined, trigger will be inserted into training data through feature perturbation. 3.1. Attack Target Selection For the attack target dataset = (, ) and a To minimize the attack impact on the original dataset, specific sample = (, ) ∈ , we first insert raw independent nodes are employed to implement attack. trigger ∆ into the feature vector and then add adverAs they will not spread or receive information from other sarial perturbation . nodes during aggregation, poisoning them does not afect For -dimension feature vector , we uniformly pick other clean nodes. dimensions and set the original feature value as 1
Given the graph dataset and the poison rate (the ratio of poisoned samples to all), we randomly select into create trigger ∆ :
= + ∆ = ( , + ∆) .. +∆ = ( 1, 2, ..., 11, ..., 12, ..., 1, ..., ), where is the sample crafted by inserting a trigger in it. Actually, the choice of trigger dimensions can be arbitrary (i.e. trigger-agnostic). The experimental part will further discuss the efect of diferent triggers on attack results, but in general, there is not much diference.
Class y
Class y
Class y u Class x uδ
uδ+¾ Class x
Class x (a) Raw triggers (b) Perturbations
(c) Training added to make perturbed trigger. c) Through SGNC training, . the decision boundary is changed to make targeted prediction.
The subsequent step is to add related adversarial perturbation into the trigger. This is to cheat the aggregation process during learning so that the decision boundary of trigger-embedded nodes can change, and poisoned nodes will be classified as target category in test. It can be shown in Fig. 2 and the corresponding perturbation generator can be expressed as = arg min ‖( )‖2 .. ( + ) = , where and (* ) are the perturbation and its generation function, and ∈ R denotes the decision boundary changing process that poisoned node whose original right label has moved to the side of the target class .
This process can be regarded as an adversarial problem [14]. For GNN, if we consider each output of the hidden layer as an extraction of feature abstraction, then the problem is converted to optimizing the feature abstrac where is the feature abstraction function that has the same structure as the target GNN model but deletes the ifnal output layer, indicates the model parameters and implies the sample from the target class set. Based on (4) , and , optimal need to be found to satisfy Eq. 6.
To address this adversarial perturbation problem and calculate , projected gradient descend (PGD) method will be employed. PGD is a multiple step data update method to apply imperceptible grading descent perturbation in input data and project updated data into a constrained space [15]. Combining Eq. 6, the poisoned target data ˆ with perturbed trigger is calculated by [ˆ ]() = Π ([ˆ ](− 1) −
()), where [ˆ ]() is the poisoned sample in iteration (initial state is ), is weight parameter (it can be seen as the learning rate), () is the gradient calculated from Eq. 6 in the data update iteration, and Π is the function of projecting data over a restricted ball range, which can shown as
Π (ˆ ) = arg min ‖ − ˆ ‖2,
∈Γ where Γ is the constrained ball space around . In addition, will not be wholly added to , and we randomly choose 20% features dimensions (perturbation budget) around the 1st non-zero feature dimension in to add
Through the iterations, the perturbed trigger is inserted and the poisoned sample is generated. 3.2.2. Hyper-parameter Regulation Strategy for
Adaptive Perturbation Adding To enhance the model’s robustness to perturbations in clean unlabeled data and mitigate the attack impact on normal performance, we introduce a new perturbationadding strategy.
Inspired by the Mixup algorithm by [16], our strategy (5) attempts to add perturbations into all unlabeled data to improve robustness and generalization ability.
For clean unlabeled data , slight perturbation will be added to make the model more adaptive to perturbation and reduce its influence on clean training samples, which is given by
˜ = + 1 , where 1 is a small weight, which is taken from complementary cumulative distribution function (CCDF) () of standard normal distribution to control the afect from (7) (8) (9) (10) tion distance between the poisoned data and the target the slight perturbation. class sample, which is given by
For trigger-embedded attack target , strong pertur = arg min ‖( + , )
− (, )‖2 .. ‖ + ‖2 < , (6) bation is added: ˜ = + (1 − 1) , where is the raw perturbation calculated by Eq. 6. 4.1. Experiment Settings and Evaluation The purpose of this operation is to weaken the original perturbation.
On the basis of the above poison data generation process, we give its corresponding algorithm, which is depicted in Algorithm 1.
Algorithm 1: Poisoned data generation Input: Unlabeled training graph data , GNN
parameters , trigger ∆ , poison rate .
Output: Poisoned unlabeled training data *. 1 Determine outlier attack targets via centrality
and poison rate ; 2 for in do if in then + ∆ ; via Eq. 6; (1 − 1) ; via Eq. 6;
Implant raw trigger ∆ into : ← Calculate perturbation based on and Add perturbation to : ˆ ←
Calculate perturbation based on and Add perturbation to : ˆ ←
+ 1 ; 3 4 5 6 7 8 9 10 else end 11 end 12 return *;
Both types of unlabeled data generated by equations 9 and 10 will be incorporated with other clean training data to perform model learning. Once the training is completed, the model gets backdoored. If poisoned nodes are fed into the model, it will make the prediction as the target class.
In this section, the performance of the proposed PerCBA method will be evaluated and analyzed. We first give the settings and the evaluation metrics of our experiment. Subsequently, experiment results are displayed. As mentioned before, PerCBA is the first clean-label backdoor attack for SGNC tasks, and thus, we mainly conduct ablation experiments on PerCBA under various settings. Finally, we will make discussions that why PerCBA can achieve persistent attack through small-scale poisoning.
4.1.1. Target Models To test the efectiveness of the attack under diferent models, three widely adopted GNN models are selected as victims: GCN, GAT (which introduces the attention mechanism into GCN) and GraphSAGE (which utilizes sampling mechanism to optimize GCN). 4.1.2. Datasets We employ five frequently used real-world datasets (dataset A: Cora [17], dataset B: Citeseer [18], dataset C: Pubmed [19], dataset D: DBLP [20] and dataset E: Physics [21]) to measure the attack performance, and dataset statistics are shown in Table 1. 4.1.3. Attack Setup To achieve better performance, the target model will first be pre-trained and is then exploited to generate unlabeled attack data using the proposed PerCBA approach (poisoned data generation function is displayed in algorithm 1). Subsequently, target model is fine-tuned in SGNC environment and gets backdoored. 4.1.4. Evaluation Metrics We use three common metrics, attack success rate (ASR, the ratio of the successful node attack trials to all poisoned test nodes), clean data accuracy (Acc, the rate of the correctly classified clean test nodes to all clean test nodes) and poison rate (the ratio of the poisoned training nodes to all training data) to analyze the attack efectiveness on the backdoored model. In addition, clean model performance on original data is investigated by using Acc and misclassification rate (MR, the ratio of the clean test nodes misclassified to the target class, to all clean test nodes) to be compared with the backdoored model. The calculation equations of the aforementioned metrics are shown as follows:
To evaluate the attack evasiveness, we apply average degree centrality diference (ADD), average eigenvector centrality change (AEC) and average feature value change (AFD) to analyze the data diferences between the original nodes and the poisoned nodes.
4.2.1. Results on Diferent Datasets in GCN and GAT, which show tiny changes across diferent datasets.
To summarize, PerCBA has good concealment, which can be seen in the slight Acc drops, ADD, AEC and AFD in the results. Meanwhile, it requires few attack targets (shown via low poison rate), which is more covert and applicable. 4.2.2. Change of Decision Boundary We first evaluate our attack on target models from dataset In order to better show the decision boundary change A to E. For each attack, poisoned node amount is set to process during training, we randomly select an infected 100, and trigger feature dimension number is set to 60. node from dataset A to conduct experiment on GCN and The experiment results are displayed in Table II. observe the diference between the predicted probability
For GCN, the attacks on all datasets achieve consider- of the target label and its true label. Training will be able ASR (maxima 90.48%) while retaining the accuracy implemented in 2 amounts of epochs (100 and 200) to of clean data classification (Acc drops within 4%) and low better dig the boundary change, and the result is depicted poison rate (within 4%). In terms of attack evasiveness, in Fig. 3. all the attacked datasets have miniature values in ADD As presented in the figure, under both two epoch 10− 10 and maxima 0.118‰), AEC (min- amounts, the probability diference is concentrated in (immain1im.2a× 4.170× − 8 and maxima 0.05‰) and AFD (minima the negative areas (boundary is closer to right label) in 0.0005‰ and maxima 0.9‰), which are all very subtle pre-training process, while it will gradually shift to the and imperceptible little changes that are dificult for de- positive areas (boundary is closer to target label) throughfenders to detect. out fine-tuning.
For GAT, the average ASR of PerCBA reaches about 53% (maxima 86.52%), and the Acc drops within 5%. 4.2.3. Afections of Hyperparameters Also, like the evasiveness performances in GCN, the test results in ADD, AEC and AFD all keep very miniature We also inspect the correlations between attack perforvalues. mances and hyperparameters: poison rate, perturbation
For GraphSAGE, PerCBA has performed well in terms budget and CCDF parameter, and carry out the test on of attack success rates and has reached a maximum of GCN with dataset A. Fig. 4(a) to Fig. 4(c) presents the 96.25% (average ASR is around 86%). For Acc and eva- findings. siveness performances, we found similar trends to those As can be seen from Fig. 4(a), accuracy decreases from 74% to 64% as poison rate increases, while attack suc1.0 0.8 0.6 0.4 0.2 0.0 0.00 0.05
Poison Rate 0.15 0.10 20 40Epoch 60 80 20 40Epoch 60 80 (a) Pre-training of 100 epochs (b) Fine-tuning of 100 epochs (c) Pre-training of 200 epochs (d) Fine-tuning of 200 epochs cess rate rises from 0 to about 60% and fluctuates around 1, causing more perturbations in poisoned nodes and about 66%. Note that we only consider maximum poison increasing ASR. Simultaneously, 2 decreases, improvrate up to about 20%, since higher rate is not practical ing accuracy. Experimental results show that selecting in real attack scenarios. A higher poison rate enhances between 0 and 0.5 achieves good ASR and accuracy. the victim model’s learning of trigger features, leading to a higher ASR. However, it also impacts the model’s 4.2.4. Afections of Data Categories normal performance, causing a decrease in accuracy. Experimental results show that a poison rate of around 5% We further analyze the afections of data categories and achieves good attack results while maintaining ASR. class information about the attack result for dataset A on
Regarding the impact of perturbation budget in Fig. GCN is viewed in Fig. 4(d). Additionally, we attack nodes 4(b), as it increased from 10% to 40%, accuracy decreases of a certain class with the same poison rate in dataset from 69% to 63% and attack success rate increases from A to see the class influence on the attack. Also, we set 24% to 72%. Increasing perturbation brings the trigger- diferent attack target classes to see the method perforembedded poisoned nodes closer to the target class, rais- mance. Attack result is shown in Table 3. Note that the 7 ing the ASR. However, it hinders the model’s learning node types of data from 0 to 6 are respectively: 0) Neural from normal samples, decreasing accuracy. Experimental Networks, 1) Case Based, 2) Reinforcement Learning, 3) results demonstrate that a perturbation rate of approxi- Probabilistic Methods, 4) Genetic Algorithms, 5) Rule mately 20% achieves a good balance between ASR and Learning, and 6) Theory. accuracy. From Fig. 4(d) above, we can see that class 6 has the
From Fig. 4(c), as the of CCDF increases, the in- largest number of nodes attacked successfully and failed, lfuence causes ASR rises from 2% to 61%, while ACC while class 1 has the 2nd largest number of successful increases slightly from 64% to 69%, with the original attacks. For attacks in diferent specifically poisoned data Acc being 73% and comparison accuracy of only classes, the result is provided in Table 3. As seen from perturbing targets nodes being 67%. Increasing raises the results, there is not much diference in accuracies, but class 1 and 5 have relatively high ASR, while class 4 and 6 have relatively low ASR. Under the attack conditions of diferent target classes, the overall experimental results in Table 3 reveal high average accuracy, and the ASR can reach 79% at the highest in class 3 but only 39% at the lowest in class 2.
Generally, the setting of the target class or the selection of the poisoned data class has limited influence on the ifnal attack performances.
As shown in Fig. 6(a), when pre-training, models keep very low ASRs, but after poisoning, ASRs rise rapidly.
Then, ASR fluctuates within a certain range but does not drop significantly, which demonstrates good persistence. Furthermore, we vary the perturbation budget to see if the persistence could be maintained, and GCN is selected as the test model. The result is shown in Fig. 6(b), and it can be seen that for less perturbation, ASR will decrease during fine-tuning, while for normal or more perturbation, ASR will remain persistent.
(a) Persistences for models (b) GCN test results 4.2.5. Afections of Diferent Triggers We further test the method’s performance under diferent triggers via GCN and Cora datasets. Instead of picking uniformly distributed feature dimensions as triggers, 4.3. Discussion both random feature dimensions and dense feature dimensions are employed for comparisons. We test uni- 4.3.1. Why PerCBA Works? form trigger pattern with ranging sizes to see the scale We take GCN as an example to explain why PerCBA impact (trigger feature dimension set from 40 and 100 works. The output of the hidden layer of the model is respectively). The comparison results are shown in Fig. given by 5. It can be seen that the three types of triggers with the same size achieved almost equal ASR (around 61%), and () = (^(− 1) (− 1)), (11) larger triggers will bring some ASR improvement, but the overall performances are similar. ^ = ˜(− 12 )˜˜(− 21 ). (12) (a) Trigger pattern
(b) Trigger size 4.2.6. Attack Persistence where comes from and [ ]0 is row vector of the initial feature matirx 0 (or ). For independent node, To evaluate PerCBA persistence, we only poison the train- its adjacent vector entries are 0 except (value = 1), ing data once and observe the ASR decrease during fine- then Eq. 14 can be rewritten as tuning. GCN, GAT and GraphSAGE will be used to test by Cora dataset. The result is shown in Fig. 6. []() = []0(1, 2, ..., ), (15) If the activation function is ignored, Eq. 11 can be expressed approximately as
() = ^()0 ∏︁ ,
=0 where ^() is the aggregation (-th power) of ^ and 0 is initial feature matrix . Let denotes the -th row entry of ^(), and its predicted row result from the hidden layer is
[]() = ∑︁ [ ]0 ∏︁ , =0 =0 (13) (14) where is the column vector that will compute the probability of data being predicted as class . Considering []0 as the attack data poisoned by perturbed trigger, since its output feature abstraction is close to the target sample, it has a higher probability of being predicted as target class label by the model during training. And hence, the model gradually learns the characteristics of the trigger-embedded data, and the decision boundary gradually changes. 4.3.2. Why Small-scale Data Works? For the selection of our target attack data, all selected targets are independent nodes in original graph. Such nodes will not be afected during the aggregation process, or afect others. Hence, their related parameters are more distinct for the model to learn, and so we could utilize small-scale independent nodes to implant backdoor into GNN. 4.3.3. Why PerCBA Persistent? The performance of traditional backdoors (refers to the backdoor in CV, because SGNC backdoor has not been investigated before so we use it as a comparison) decreases as the model is iteratively trained with clean samples, because the model keeps learning new features of the target class and forgets the features of the trigger. However, the poisoned data generated by PerCBA, and the target class data are relatively close in feature space, so there is no feature forgetting and therefore PerCBA shows better persistence.
In this study, we first discussed traditional backdoor’s inapplicability for SGNC resulting from its high-intensity data poisoning. To overcome this problem, we furthermore propose PerCBA, the first clean-label backdoor for SGNC. Specifically, the proposed PerCBA scheme inserts perturbed triggers into small-scale unlabeled nodes that are selected from graph data based on the centralitybased node selection mechanism. Thereafter, the victim model will be backdoored during the SGNC training. This is the first clean-label backdoor method (that does not change any label information) for SGNC and just leverages small-scale nodes as targets, which assures that the attack is less detectable. Experiments based on three SOTA models and five real-world datasets demonstrate that the proposed PerCBA owns high attack success rate and persistence, and has slight efect on clean data predictions. For future work, we will focus on developing the defense strategy against the proposed PerCBA attack. [13] L. Chen, Q. Peng, J. Li, Y. Liu, J. Chen, Y. Li, Z. Zheng, Neighboring backdoor attacks on graph convolutional network, CoRR abs/2201.06202 (2022). [14] H. Dai, H. Li, T. Tian, X. Huang, L. Wang, J. Zhu, L. Song, Adversarial attack on graph structured data, in: Proceedings of International Conference on Machine Learning (ICML), volume 80, 2018, pp. 1123–1132. [15] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, A. Vladu, Towards deep learning models resistant to adversarial attacks, in: International Conference on Learning Representations (ICLR), 2018. [16] H. Zhang, M. Cissé, Y. N. Dauphin, D. Lopez-Paz, mixup: Beyond empirical risk minimization, in: International Conference on Learning Representations (ICLR), OpenReview.net, 2018. [17] A. McCallum, K. Nigam, J. Rennie, K. Seymore, Automating the construction of internet portals with machine learning., Information Retrieval Journal 3 (2000) 127–163. [18] C. L. Giles, K. D. Bollacker, S. Lawrence, Citeseer: An automatic citation indexing system, in: Proceedings of ACM Conference on Digital Libraries, 1998, p. 89–98. [19] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, T. Eliassi-Rad, Collective classification in network data, AI Magazine 29 (2008) 93. [20] J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, Z. Su, Arnetminer: Extraction and mining of academic social networks, in: KDD, New York, NY, USA, 2008, p. 990–998. [21] O. Shchur, M. Mumme, A. Bojchevski, S. Günnemann, Pitfalls of graph neural network evaluation, CoRR abs/1811.05868 (2018). arXiv:1811.05868.