1 Motif-Backdoor Rethinking the Backdoor Attack on Graph Neural Networks via Motifs

2025-04-30 0 0 976.56KB 15 页 10玖币

侵权投诉

Motif-Backdoor: Rethinking the Backdoor Attack on

Graph Neural Networks via Motifs

Haibin Zheng, Haiyang Xiong, Jinyin Chen, Member, IEEE, Haonan Ma, and Guohan Huang

Abstract—Graph neural network (GNN) with a powerful

representation capability has been widely applied to various

areas. Recent works have exposed that GNN is vulnerable to the

backdoor attack, i.e., models trained with maliciously crafted

training samples are easily fooled by patched samples. Most of

the proposed studies launch the backdoor attack using a trigger

that either is the randomly generated subgraph (e.g., erd

os-r

enyi

backdoor) for less computational burden, or the gradient-based

generative subgraph (e.g., graph trojaning attack) to enable a

more effective attack. However, the interpretation of how is the

trigger structure and the effect of the backdoor attack related has

been overlooked in the current literature. Motifs, recurrent and

statistically signiﬁcant subgraphs in graphs, contain rich structure

information. In this paper, we are rethinking the trigger from

the perspective of motifs, and propose a motif-based backdoor

attack, denoted as Motif-Backdoor. It contributes from three

aspects. (i) Interpretation: it provides an in-depth explanation for

backdoor effectiveness by the validity of the trigger structure

from motifs, leading to some novel insights, e.g., using subgraphs

that appear less frequently in the graph as the trigger can achieve

better attack performance. (ii) Effectiveness: Motif-Backdoor

reaches the state-of-the-art (SOTA) attack performance in both

black-box and defensive scenarios. (iii) Efﬁciency: based on the

graph motif distribution, Motif-Backdoor can quickly obtain

an effective trigger structure without target model feedback

or subgraph model generation. Extensive experimental results

show that Motif-Backdoor realizes the SOTA performance on

three popular models and four public datasets compared with ﬁve

baselines, e.g., Motif-Backdoor improves the attack success rate by

14.73% compared with baselines on average. Additionally, under

a possible defense, Motif-Backdoor still implements satisfying

performance, highlighting the requirement of defenses against

backdoor attacks on GNNs. The datasets and code are available

at https://github.com/Seaocn/Motif-Backdoor.

Index Terms—Backdoor attack, motif, graph neural networks,

interpretation, defense.

I. INTRODUCTION

Ur lives are surrounded by various graphs, which contain

nodes and edges that are capable to represent individ-

uals and relationships in different scenarios, such as social

Manuscript received xxxx xx, xxxx; revised xx xx, xxxx. This work was

supported by the NSFC under Grant 62072406; in part by the Zhejiang

Provincial Natural Science Foundation under Grant LDQ23F020001; in part

by the Chinese National Key Laboratory of Science and Technology on

Information System Security under Grant 61421110502; and in part by the

National Key Research and Development Projects of China under Grant

2018AAA0100801. (Haibin Zheng and Haiyang Xiong contributed equally to

this work.) (Corresponding author: Jinyin Chen.)

H. Zheng and J. Chen are with the Institute of Cyberspace Security and

the College of Information Engineering, Zhejiang University of Technol-

ogy, Hangzhou, 310023, China (e-mail:haibinzheng320@gmail.com; chen-

jinyin@zjut.edu).

H. Xiong, H. Ma, and G. Huang are with the College of Information

Engineering, Zhejiang University of Technology, Hangzhou 310023, China

(e-mail:xhy19982021@163.com; 13estdeda@gmail.com; hgh0545@163.com).

networks [

], trafﬁc networks [

] and malware detection [

etc. Graph analysis plays an important role in the real world

tasks, e.g., node classiﬁcation [

], [

], graph classiﬁcation [

[

], and link prediction [

], [

]. With the wide application

of deep learning models [

], [

], graph

neural networks (GNNs) have achieved a great success in

graph-structured data processing by learning effective graph

representations via message passing strategies [

], [

[

], [

]. Compared with the non-deep graph embedding meth-

ods [20], [21], GNNs usually achieve superior performance.

Although numerous GNNs have achieved satisfying perfor-

mance in real world tasks, the potential security issues of GNNs

have also raised public concerns. Researches have revealed the

vulnerability of GNNs towards adversarial attacks [

], [

[24], [25], which are designed to deceive the GNN model by

carefully crafted adversarial samples in the inference phase.

Additionally, numerous well-performing GNNs beneﬁt from

rich labeled training data, which are usually implemented in the

form of crawlers, logs, crowdsourcing, etc. It is worth noting

that the training data may be polluted with noises, or even

injected with the triggers by a malicious attacker. Different

from adversarial attacks, they affect the model parameters in the

training phase, leaving a speciﬁc backdoor in the model after

training. Once a sample patched with the trigger is fed into the

backdoored model (i.e., the model with a backdoor), the target

result will be predicted as expected by the attacker, while still

working normally with clean inputs (i.e., non-patched samples).

Consequently, the security threat in the training phase cannot

be ignored.

Benign Molecular Graph

Backdoored Molecular Graph

Backdoored Drug

Screening System Benign Drug

Poisonous Drug

Correct

Error

Fig. 1. An illustration of the backdoor attack in the drug screening system. The

backdoored drug screening system behaves normally on a benign molecular

graph, while the trigger (i.e., the red triangle subgraph) activates the backdoor

in the backdoored drug screening system, causing the wrong classiﬁcation.

Fig. 1 illustrates the graph backdoor attack, taking the

drug screening system as an example. The backdoored drug

screening system is trained on training data with the trigger

(i.e., the red triangle subgraph). It behaves normally on a benign

molecular graph, but the trigger (i.e., the red triangle subgraph)

arXiv:2210.13710v2 [cs.LG] 29 May 2023

activates the backdoor in the backdoored drug screening system,

causing the misclassiﬁcation result. Speciﬁcally, the backdoored

drug screening system classiﬁes the backdoor molecular graph

(true label as the poisonous drug) as the benign drug, causing

the wrong classiﬁcation in the drug property.

Several backdoor attacks [

], [

] have been

proposed to reveal the vulnerability of GNNs in the training

phase. According to the way of trigger generation, the existing

attacks are categorized as randomly attacks and gradient-

based generative attacks. In previous works [

], [

subgraph is randomly generated as the trigger that satisﬁes

certain network distribution (e.g., erd

os-r

enyi, small world,

and preferential attachment). They are easy to implement, but

suffer from instability of the attack effect. Another method

[

] adopts the gradient-based generative strategy to obtain

the subgraph as the trigger, whereas it requires more time and

more knowledge (e.g., the target model’s structure, parameters)

to optimize the trigger.

Since different subgraphs can be used as triggers, it is

important to understand how different subgraphs can affect

the backdoor attack’s impact on practical applications. Motifs,

which are recurrent and statistically signiﬁcant subgraphs in

graphs, are particularly relevant to the function of the graphs.

They serve as the fundamental building blocks of graphs, and

contain rich structural information. Motifs have been exten-

sively studied in various domains, such as biochemistry [

neuroscience [

], and social networks [

], and have been

shown to play crucial roles in the function and behavior of

these systems. In the context of backdoor attacks on GNNs,

motifs can serve as a powerful tool to bridge the gap between

the impact of different subgraphs as triggers and the underlying

graph structures. By leveraging the intrinsic properties of motifs,

we can generate more effective and stable triggers that are more

closely related to the graph structure and function, and thereby

gain deeper insights into the vulnerability of GNNs to backdoor

attacks.

To sum up, there are three challenges for backdoor attacks

against GNNs. (i) Trigger Structure Limitation. There are many

structures that satisfy the trigger perturbation limit, and it is

difﬁcult to efﬁciently determine the appropriate trigger structure.

(ii) Attack Knowledge Limitation. Without the target model

feedback information, it is difﬁcult for the attacker to achieve

a stable and effective attack. (iii) Injection Position Limitation.

The space of positions where the trigger can choose to inject is

huge, and it is challenging to select the well trigger injection

position efﬁciently.

To cope with the above challenges, we propose a novel

backdoor attack against GNNs based on motifs, namely Motif-

Backdoor. Speciﬁcally, to tackle the challenge (i), we analyze

the distribution of motifs in the training graph, and select an

appropriate motif as the trigger. This is a way of generating

the trigger based on statistics, which is much faster than

optimization based methods. For the knowledge limitation

mentioned in the challenge (ii), we construct a reliable shadow

model, which is based on the structure of the state-of-the-art

(SOTA) models and the training data with conﬁdence scores

for the output of the target model. To address the challenge

(iii), we leverage strategies of the graph index (graph structure

perspective) and dropping the target node (model feedback

perspective) to measure the node importance of the graph.

The operation can select the effect trigger injection position.

Empirically, our approach achieves the SOTA results on four

real-world datasets and three different popular GNNs compared

with ﬁve baselines. Additionally, we propose a possible defense

against Motif-Backdoor, and the experiments testify that it only

reduces attack success rate of Motif-Backdoor by an average

of 4.17% on several well-performing GNNs. Compared to the

existing methods, our motif-based backdoor attack method

has several advantages. Firstly, by leveraging the intrinsic

properties of motifs, we are able to generate more stable

and effective triggers with higher success rates. Secondly,

our method requires less knowledge of the target model’s

structure and parameters, making it more practical for real-

world scenarios. Finally, the use of motifs provides a new

perspective for exploring the vulnerability of GNNs, which

has not been studied in previous works.

The main contributions of this paper are summarized as

follows:

•

We reveal the impact of trigger structure and graph topology

on backdoor attack performance from the perspective

of motifs, and obtain some novel insights, e.g., using

subgraphs that appear less frequently in the graph as the

trigger realizes better attack performance. Furthermore,

we provide further explanations for the insight.

•

Inspired by the motifs, we propose an effective attack

framework, namely Motif-Backdoor. It quickly selects the

trigger based on the distribution of motifs in the dataset.

Besides, a shadow model is constructed to transfer the

attack from white-box to black-box scenario. For the

trigger injection position, we propose strategies of the

graph index and dropping the target node to measure the

node importance of the graph.

•

Extensive experiments on three different popular GNNs

over four real world datasets demonstrate that Motif-

Backdoor implements the SOTA performance, e.g., Motif-

Backdoor improves the attack success rate by 14.73%

compared with baselines on average. Moreover, the ex-

periments testify that Motif-Backdoor is effective against

a possible defense strategy as well.

The rests of the paper are organized as follows. Related

works are introduced in Section II. The problem deﬁnition and

threat model are described in Section III. The backdoor attack

from the motifs is in Section IV, while the proposed method

is detailed in Section V. Experiment results and discussion are

shown in Section VI. Finally, we conclude our work.

II. RELATED WORK

Our work focuses on the backdoor attack against GNNs from

motifs. In this section, we brieﬂy review the related work upon

two categories: backdoor attacks against GNNs and motifs for

GNNs.

A. Backdoor Attacks on GNNs

Based on the generation method of the trigger, the existing

backdoor attack methods can be divided into two categories:

random generation based on network distribution and the

gradient-based generative.

For the random generation based on network distribution,

Zhang et al. [

] generated the trigger that satisﬁes the erd

os-

enyi, small world, or preferential attachment distribution. It

is designed to establish the relationship between label and

trigger of the special structure. Then, Xu et al. [

] further

implemented GNNExplainer to conduct an explainability

research on backdoor attacks of the graph. Furthermore, Yu

et al. [

] considered the local and global structural features

of nodes to select the effect nodes for the trigger form. They

randomly generate the subgraph as a trigger satisfying similar

distributions for the speciﬁc networks (e.g., the erd

os-r

enyi,

small world, or preferential attachment).

For the gradient-based generative method, graph trojaning

attack [

] adopts a two-layer optimization strategy to update

the trigger generator and the target model parameters. Addi-

tionally, it can tailor the trigger to individual graphs under no

knowledge regarding downstream task, while the method costs

more time to optimize the trigger and needs more information

(e.g., the target model’s structure, parameters).

In summary, most of the proposed backdoor attacks construct

the trigger based on subgraph generative or gradient generative

strategies. They ignored the interpretation of how the effects

of the trigger structure and backdoor attack are related.

B. Motifs for GNNs

Motifs [

] are fundamental building blocks of complex

networks, which describes small subgraph patterns with speciﬁc

connections among nodes. Numerous studies have shown that

motifs have a powerful ability to mine graph information

on GNNs. Sankar et al. [

] developed a Motif-CNN that

employs an attention model to combine the features extracted

from multiple patterns, capturing high-order structural and

feature information. Then, a hierarchical network embedding

method is proposed [

], which combines motif ﬁltering and

convolutional neural networks to capture exact small structures

within networks. Zhao et al. [

] used motifs to capture higher-

order relations among nodes of the same type, and designed a

motif-based recommending model.

To capture higher-order interactions between nodes in the

graph, motif convolutional networks [

] generalizes past

approaches by using weighted multi-hop motif adjacency ma-

trices. Furthermore, Dareddy et al. [

] leveraged higher-order,

recurring, and statistically signiﬁcant network connectivity

patterns in the form of motifs. They can better learn node

representations or embeddings for heterogeneous networks.

Learning embeddings by leveraging motifs of networks [

]

bridges connectivity and structural similarity in a uniform

representation via motifs learning embeddings for vertices and

various motifs. For undirected graphs, Zhao et al. [

] uniﬁed

both the motif higher order structure and the original lower

order structure. Besides, Wang et al. [

] proposed a novel em-

bedding algorithm that incorporates network motifs to capture

higher order structures in the network for the link prediction.

In addition, for the explainable work, MotifExplainer [

] can

explain GNNs by identifying important motifs.

The current works on GNNs show that motifs can improve

the ability of models to learn node (or graph) representations

or perform interpretable work in GNNs. In the ﬁeld of graph

network backdoor attack, there is no related work using

motif. Besides, motifs contain rich structure information as

the fundamental tool for graph mining, so we use motifs to

explore the correlation between trigger structure and backdoor

attack.

III. PRELIMINARY

In this section, we introduce the deﬁnition of the graph,

GNNs for graph classiﬁcation, backdoor attack against GNNs

and motifs. For convenience, the deﬁnitions of symbols used

are listed in the Table I.

TABLE I

THE DEFINITIONS OF SYMBOLS.

Notations Deﬁnitions

AAdjacency matrix

XFeature matrix

G= (V, E)Benign graph with nodes V, links E

GBackdoored graph

GGraph classiﬁcation dataset

gTrigger

Dava Datasets available to attackers

Dbeni Benign graphs set

Dback Backdoored graphs set

YLabel space

ytThe attacker-chosen target graph label

Star A set of graphs labeled as the target label

Soth A set of graphs labeled as the non target labels

FθShadow model

fθBenign model

θBackdoored model

M(·)Trigger mixture function

mThe maximum number of links in the tirgger

kThe number of ﬁlter nodes

pPoisoning rate

C(·)Selection criteria

A. Problem Deﬁnition

Deﬁnition 1 (Graph). A graph is represented as

G= (V, E)

where

is the node set,

is the edge set.

usually contains

a feature vector of each node. Here, the feature of graph

is denoted as

A∈ {0,1}n×n

as the adjacency matrix, and

G= (A, X)is used to represent a graph more concisely.

Deﬁnition 2 (GNNs for Graph classiﬁcation). A

graph classiﬁcation dataset

, including

graphs

{(G1, y1),...,(GN, yN)}

, where

is the

-th graph and

is one of the

labels in the label space

Y={c1, c2, . . . , cL}

The GNNs model

fθ(·)

is the graph classiﬁer, whose goal is

to predict the labels of graphs through the model

fθ(·)

trained

by the labeled graphs as a function

F:G → Y

, which maps

each graph Gto one of the Llabels in Y.

Deﬁnition 3 (Backdoor Attack on GNNs). Given a

graph classiﬁcation dataset

, the adversary aims to forge

a backdoored model

to misclassify all the trigger-embedded

graphs to a designated label

, while functioning normally on

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1Motif-Backdoor:RethinkingtheBackdoorAttackonGraphNeuralNetworksviaMotifsHaibinZheng,HaiyangXiong,JinyinChen,Member,IEEE,HaonanMa,andGuohanHuangAbstract—Graphneuralnetwork(GNN)withapowerfulrepresentationcapabilityhasbeenwidelyappliedtovariousareas.RecentworkshaveexposedthatGNNisvulnerabletothebackdo...

展开>> 收起<<

1 Motif-Backdoor Rethinking the Backdoor Attack on Graph Neural Networks via Motifs.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Motif-Backdoor Rethinking the Backdoor Attack on Graph Neural Networks via Motifs

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: