[figure attack and Defense] backdoor attacks to graph neural networks (sacmat '21)

Backdoor Attacks to Graph Neural Networks (SACMAT’21)

Neil Zhenqiang Gong Team work .

This paper mainly attacks GNN Model , The task scenario is transaction fraud 、 Social networks detect fake users 、 Malware detection, etc , These tasks are to classify a graph . In this paper, the backdoor attack Is to inject a sub graph structure into the graph as trigger, Then, if the same subgraph structure appears in the test set , Will predict the goal label. The method of injecting subgraphs is also relatively simple , Is the random method . Then the article puts forward defense methods , utilize Randomized Subsampling Achieve verifiable defense .

The target of the attacker is backdoored GNN The model should be in clean testing graph The accuracy is as high as possible , But in the injection trigger Of testing graph On ASR It should be as high as possible .

Generate trigger Method

First add trigger Only modify the diagram structure , Such as choice 4 Nodes as trigger Subgraphs , No matter what the structure of these four nodes is , Now change to this structure . control trigger Four parameters of subgraph

Trigger size：trigger The number of nodes of the subgraph $t$.

Trigger density：trigger The density of the graph $\rho$.$\rho =1$ That is, each node and all other nodes have an edge connected .

Trigger synthesis method $M$： Generate trigger Method of subgraph , use ER Random graph generation . Basically random generation .

The density of poisoning $\gamma$ ： Yes trigger Percentage of the graph in the training set .

Attack process

Set it up Trigger size $t$ and Trigger density $\rho$, And then use ER Random graph generates a trigger Subgraph template （ Only once ）; Then randomly select several graphs in the training set as the data to be poisoned ; Then select randomly on each map to be poisoned $t$ Nodes as , Let them become trigger. There are two points to explain ：

1、 Training and testing trigger The subgraph structure is exactly the same . The author tries to use the same parameters fix trigger Or generate more random trigger, It is found that the index has little impact , Little reduction , The author explains GNN You can put similar structures trigger and label Connect .

2、 Choose which nodes form trigger Is random . The author tries to choose randomly $t$ individual 、 choice degree Maximum / The smallest $t$、 Choose the one with the highest density of interconnection $t$ Nodes , It is found that random is the most stable on different data sets , Other strategies have bad data sets .

Certified Defense

The author then proposes to use SOTA The verifiability of defense methods to defend him backdoor attack.

Verifiable defense is the use of Randomized smoothing Come on smooth Model , This paper makes use of Randomized Subsampling Come on smooth GNN. The specific method is to randomly sample each image in the training set , Training with randomly generated subgraphs , Then, when predicting, the prediction label is decided by voting .

such Randomized Subsampling The defense method of can reduce the attack effect to a certain extent , But with datasets 、trigger size It matters a lot , When trigger size Above a certain threshold ,Certified Defense It's completely ineffective , This is it. GNN in Certified Defense Safe radius .

Verifiable defense and comparative learning

It can be seen that there are actually some comparative learning in the figure Randomized smoothing It means , By amplifying different subgraphs , Keep the same feature Output , Come on Randomized smoothing GNN encoder.