曹海芳

(天津大學(xué) 數(shù)學(xué)學(xué)院,天津 300350)

圖結(jié)構(gòu)數(shù)據(jù)已廣泛應(yīng)用于許多現(xiàn)實(shí)世界的應(yīng)用程序中,例如社交網(wǎng)絡(luò)(Facebook和Twitter),生物網(wǎng)絡(luò)(蛋白質(zhì)或基因相互作用) 以及屬性圖(PubMed和Arxiv)等[1–3].節(jié)點(diǎn)分類任務(wù)是圖結(jié)構(gòu)數(shù)據(jù)上最重要的任務(wù)之一,即給定一個(gè)節(jié)點(diǎn)子集及其標(biāo)簽,預(yù)測(cè)其余節(jié)點(diǎn)的標(biāo)簽.對(duì)于節(jié)點(diǎn)分類任務(wù),基于圖的深度學(xué)習(xí)模型——圖神經(jīng)網(wǎng)絡(luò)已實(shí)現(xiàn)了最先進(jìn)的性能[4],而圖卷積網(wǎng)絡(luò)(GCN)作為一種特殊的圖神經(jīng)網(wǎng)絡(luò),在此任務(wù)上取得了更好的結(jié)果.

目前的研究更多的是將重點(diǎn)放在如何提高GCN的性能上,卻很少有人關(guān)注GCN 模型的魯棒性.但是,研究表明,GCN是極易受到對(duì)抗攻擊的.例如,只須對(duì)圖數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)或者節(jié)點(diǎn)的特征進(jìn)行微小的修改就能使GCN 得到錯(cuò)誤的分類結(jié)果[5].目前的攻擊方法中,絕大多數(shù)是通過(guò)修改圖數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性來(lái)進(jìn)行攻擊的,然而,這樣的攻擊在現(xiàn)實(shí)場(chǎng)景中是不適用的.例如,在社交網(wǎng)絡(luò)應(yīng)用程序中,攻擊者必須登錄用戶的帳戶才能更改現(xiàn)有的連接和功能,而獲得登錄訪問(wèn)權(quán)限幾乎是不可能的.相比之下,在實(shí)踐中添加與用戶相對(duì)應(yīng)的偽節(jié)點(diǎn)(fake node)會(huì)容易得多.

TUA 就是一種通過(guò)添加偽節(jié)點(diǎn)進(jìn)行攻擊的針對(duì)性通用攻擊方法.在針對(duì)GCN的所有攻擊方法中,通用攻擊方法是一種特殊的攻擊方法,此方法要求GCN 將所有的受害節(jié)點(diǎn)都錯(cuò)誤分類,而不是某個(gè)單獨(dú)的節(jié)點(diǎn)[6–8].針對(duì)性通用攻擊則要求GCN 將所有受害節(jié)點(diǎn)都錯(cuò)誤地分到某一個(gè)指定的類別[9].本文則是基于TUA 算法,通過(guò)引入梯度選擇的方法,使得本文方法在所有類別的實(shí)驗(yàn)中都取得了與TUA 方法相當(dāng)甚至優(yōu)于TUA 方法的結(jié)果,平均ASR 相對(duì)TUA 得到了1.7%的提升.

1 相關(guān)知識(shí)介紹

1.1 圖卷積網(wǎng)絡(luò) (GCN)[4,10]

給定屬性圖G(A,X),其中A∈{0,1}N×N為鄰接矩陣,X∈{0,1}N×d為特征矩陣,即圖G有N個(gè)節(jié)點(diǎn),且每個(gè)節(jié)點(diǎn)伴隨一個(gè)d維的特征.令V={v1,v2,···,vN}為節(jié)點(diǎn)集,C={c1,c2,···ck}為類別集.節(jié)點(diǎn)分類任務(wù)的目標(biāo)就是通過(guò)在含有節(jié)點(diǎn)標(biāo)簽的訓(xùn)練集上學(xué)習(xí)從而成功預(yù)測(cè)測(cè)試集節(jié)點(diǎn)的標(biāo)簽.GCN 首先通過(guò)聚合鄰居節(jié)點(diǎn)的信息來(lái)得到節(jié)點(diǎn)的嵌入表示(第l層如下):

1.2 圖對(duì)抗攻擊

在過(guò)去的幾年中,Zungner 等[6]和Dai 等[5]首先發(fā)現(xiàn)了GCN 容易受到對(duì)抗性攻擊的特性.而根據(jù)攻擊的不同階段,GCN中的對(duì)抗攻擊分為兩種類型:投毒攻擊(訓(xùn)練期間的攻擊)和逃避攻擊(測(cè)試期間的攻擊).通常,投毒攻擊的重點(diǎn)是通過(guò)干擾訓(xùn)練數(shù)據(jù)來(lái)降低GCN 模型的性能,而逃避攻擊則通過(guò)修改屬性或拓?fù)浣Y(jié)構(gòu)來(lái)構(gòu)造對(duì)抗性樣本,從而使GCN 模型的性能降低.另外,根據(jù)攻擊的不同目的,對(duì)圖結(jié)構(gòu)化數(shù)據(jù)的對(duì)抗攻擊可分為節(jié)點(diǎn)分類攻擊,鏈接預(yù)測(cè)攻擊和圖分類攻擊.節(jié)點(diǎn)分類攻擊的目的是使某些節(jié)點(diǎn)被GCN 誤分類.鏈接預(yù)測(cè)攻擊的重點(diǎn)是減少節(jié)點(diǎn)之間的關(guān)聯(lián),從而導(dǎo)致GCN 提供錯(cuò)誤的預(yù)測(cè)結(jié)果.圖分類攻擊則旨在增強(qiáng)指定圖與目標(biāo)分類之間的相關(guān)性,以使GCN 無(wú)法正確分類給定圖樣本.本文提出的GTUA 可以歸為逃避攻擊和節(jié)點(diǎn)分類攻擊.

在對(duì)圖結(jié)構(gòu)數(shù)據(jù)的所有對(duì)抗攻擊中,偽節(jié)點(diǎn)攻擊是一種常見(jiàn)的攻擊方法,通過(guò)將一組偽節(jié)點(diǎn)注入到圖中來(lái)實(shí)現(xiàn),從而可以避免對(duì)原始圖進(jìn)行拓?fù)浠驅(qū)傩孕薷?例如,GreedyAttack和GreedyGAN 通過(guò)將偽造的節(jié)點(diǎn)直接添加到受害節(jié)點(diǎn)來(lái)進(jìn)行目標(biāo)節(jié)點(diǎn)攻擊[11].Wang 等[12]引入近似快速梯度符號(hào)法,該方法在受害節(jié)點(diǎn)和其他節(jié)點(diǎn)之間添加了一個(gè)惡性節(jié)點(diǎn),從而導(dǎo)致受害節(jié)點(diǎn)被錯(cuò)誤分類.但是,大多數(shù)現(xiàn)有的偽節(jié)點(diǎn)攻擊并非旨在進(jìn)行普遍的對(duì)抗攻擊.而在本文提出的GTUA中,偽節(jié)點(diǎn)充當(dāng)受害節(jié)點(diǎn)的2 跳鄰居.由于GCN的攻擊過(guò)程,偽節(jié)點(diǎn)特征的影響通過(guò)攻擊節(jié)點(diǎn)傳遞到受害節(jié)點(diǎn),從而進(jìn)行針對(duì)性通用對(duì)抗攻擊.

2 基于梯度選擇的圖卷積網(wǎng)絡(luò)針對(duì)性通用對(duì)抗攻擊

基于梯度選擇的圖卷積網(wǎng)絡(luò)針對(duì)性通用對(duì)抗攻擊(GTUA)的目標(biāo)是使得每一個(gè)與攻擊節(jié)點(diǎn)(從標(biāo)簽為目標(biāo)類別的節(jié)點(diǎn)集中隨機(jī)選擇)連接的受害節(jié)點(diǎn)都得到與攻擊節(jié)點(diǎn)相同的標(biāo)簽(如圖1所示).主要由3 個(gè)步驟完成:添加伴隨0 特征的偽節(jié)點(diǎn);計(jì)算目標(biāo)函數(shù)關(guān)于偽節(jié)點(diǎn)特征矩陣的梯度矩陣;按梯度矩陣元素大小進(jìn)行梯度選擇并確定擾動(dòng)特征.下面分別詳細(xì)介紹每一個(gè)步驟.

圖1 攻擊前后的受害節(jié)點(diǎn)分類結(jié)果

2.1 添加伴隨0 特征的偽節(jié)點(diǎn)

在添加偽節(jié)點(diǎn)之前,先簡(jiǎn)單介紹幾步預(yù)處理過(guò)程:對(duì)于給定的圖G(A,X),首先選定一個(gè)類別co作為目標(biāo)類別,隨后在標(biāo)簽為co的節(jié)點(diǎn)集中隨機(jī)選擇NA個(gè)節(jié)點(diǎn)作為攻擊節(jié)點(diǎn)VA={v1A,v1A,···,vNAA},同時(shí)為了簡(jiǎn)便起見(jiàn),規(guī)定為每個(gè)攻擊節(jié)點(diǎn)連接相同數(shù)量NF個(gè)偽節(jié)點(diǎn).即,給定圖G(A,X),目標(biāo)類別co,攻擊節(jié)點(diǎn)VA,每個(gè)攻擊節(jié)點(diǎn)的偽節(jié)點(diǎn)數(shù)目NF,通過(guò)給每個(gè)攻擊節(jié)點(diǎn)連接特

G′=(A′,X′)征為0的偽節(jié)點(diǎn)得到新圖,其中,

其中,E∈{0,1}N×(NA·NF),P∈{0,1}(NA·NF)×(NA·NF),XF∈{0,1}(NA·NF)×d,且初始化為全0,本文的目的就是通過(guò)給偽節(jié)點(diǎn)添加某些特征,也就是XF的某些元素由0 改為1,從而使得下面的目標(biāo)函數(shù)取得最大值.

2.2 計(jì)算目標(biāo)函數(shù)關(guān)于偽節(jié)點(diǎn)特征矩陣的梯度矩陣

在此首先明確本文的目的是,對(duì)于給定的圖G(A,X),目標(biāo)類別co,攻擊節(jié)點(diǎn)VA,希望每一個(gè)標(biāo)簽不是co的節(jié)點(diǎn),當(dāng)其與VA連接時(shí),能夠使得GCN為其得到co的標(biāo)簽,這也就是針對(duì)性通用攻擊的含義.由此含義,首先給出一個(gè)隨機(jī)選定的輔助節(jié)點(diǎn)集來(lái)幫助建立目標(biāo)函數(shù),其中NT表示輔助節(jié)點(diǎn)的數(shù)量,要求VT中的每一個(gè)節(jié)點(diǎn)都不屬于標(biāo)簽co,因此有下面的目標(biāo)函數(shù):

其中,‖E‖0表示偽節(jié)點(diǎn)與攻擊節(jié)點(diǎn)之間的連邊的數(shù)量,‖XF‖0表示給偽節(jié)點(diǎn)添加的特征的數(shù)量,二者都受到參數(shù) Δ的限制,因?yàn)閿_動(dòng)必須是微小的.其中,

式(5)是關(guān)于每一個(gè)輔助節(jié)點(diǎn)的目標(biāo)函數(shù)部分,v∈VT,A′(v,A)表示輔助節(jié)點(diǎn)v與攻擊節(jié)點(diǎn)VA連接之后的新的鄰接矩陣,[f(·)]v,co和[f(·)]v,cv分別表示GCN 將節(jié)點(diǎn)v判定為目標(biāo)類別和其當(dāng)前類別的輸出概率.而制定此目標(biāo)函數(shù)的依據(jù)是:如果本文的攻擊或者說(shuō)擾動(dòng)能夠使得GCN 將這些非co的輔助節(jié)點(diǎn)在連接到VA后被分類到co,那么對(duì)于所有的非co的節(jié)點(diǎn),當(dāng)其與VA連接后,就會(huì)有很大的概率被分類為co,并且如果考慮一種極端情況:將所有非co節(jié)點(diǎn)作為輔助節(jié)點(diǎn),那么就能更好地理解此目標(biāo)函數(shù).

前面確定了目標(biāo)函數(shù),那么如何計(jì)算擾動(dòng)？在這里首先介紹基于梯度的方法.因?yàn)橹豢紤]對(duì)XF進(jìn)行擾動(dòng),因此只需要先計(jì)算目標(biāo)函數(shù)關(guān)于XF的梯度:

2.3 按梯度矩陣元素大小進(jìn)行梯度選擇并確定擾動(dòng)特征

以往的基于梯度的方法基本都是采用一種貪婪式的選擇方法[13]:在每一次迭代中只改動(dòng)一個(gè)元素,因此找到每一次迭代中的梯度矩陣中的最大元素作為修改的對(duì)象即可.TUA 也是采用這樣一種方式,首先找到Grad中的最大元素Gradmax:

然后找到Gradmax在XF對(duì)應(yīng)哪一個(gè)偽節(jié)點(diǎn)的哪一個(gè)特征,再找到它在X′中的對(duì)應(yīng)位置,將該位置的元素由0 置為1,這樣就完成了一次迭代,直到到達(dá)一定的閾值就結(jié)束擾動(dòng).需要提到的一點(diǎn)是:如果某一次迭代時(shí)最大梯度對(duì)應(yīng)的位置已經(jīng)是1,那么就尋找第二大的梯度位置,依次下去.

本文提出的GTUA 也是采用一種基于梯度的貪婪式方法,但是在這個(gè)過(guò)程中加上一個(gè)梯度選擇的過(guò)程.具體做法就是在得到Grad之后,選出其中從大到小前k個(gè)元素:

然后分別計(jì)算將其在X′中對(duì)應(yīng)位置的特征值由0 置為1 后的損失函數(shù)值:

其中,X1′,X2′,···,Xk′分別是對(duì)Grad1,Grad2,···,Gradk位置進(jìn)行擾動(dòng)后的新的特征矩陣.最后再選擇其中得到最大損失函數(shù)值的特征修改作為這一次迭代的擾動(dòng):

加入這樣一個(gè)梯度選擇的過(guò)程,是出于以下思考:因?yàn)榭紤]A和X都是取值為0 或1的離散數(shù)據(jù)類型,因此在選擇Grad中最大元素Gradmax對(duì)應(yīng)的位置并由0 置為1的時(shí)候相當(dāng)于是選擇了長(zhǎng)度1的步長(zhǎng),并且每一次迭代都是固定步長(zhǎng)1.因此,就很可能出現(xiàn)一種情況,Grad中第二大元素Gradsec對(duì)應(yīng)的位置由0 置為1 會(huì)得到更大的損失函數(shù),如圖2所示.

圖2 不同梯度下loss 與步長(zhǎng)的關(guān)系

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

本文在3 個(gè)常用的屬性圖數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn):Cora (2 708 節(jié)點(diǎn),5 429 邊,1 433 特征,7 類別),Citeseer (3 312 節(jié)點(diǎn),4 732 邊,3 703 特征,6 類別)和PubMed (19 717 節(jié)點(diǎn),44 338 邊,500 特征,3 類別)[14–16].此外,根據(jù)Kipf&Welling的設(shè)置,在3 個(gè)相應(yīng)的數(shù)據(jù)集上訓(xùn)練GCN 模型.最后用平均攻擊成功率(ASR)作為模型性能的評(píng)價(jià)標(biāo)準(zhǔn),ASR 越高,表明模型的攻擊效果越好.

3.2 實(shí)驗(yàn)設(shè)置

首先按照TUA的方法加快微擾計(jì)算.因?yàn)榇蠖鄶?shù)基于梯度的攻擊都存在時(shí)間和內(nèi)存成本高的問(wèn)題,為了解決這個(gè)問(wèn)題,Li 等[16]提出了一種有效加速攻擊的框架,該攻擊框架攻擊由目標(biāo)節(jié)點(diǎn)的k跳鄰居組成的較小子圖(k取決于GCN 層數(shù)),從而可以避免不必要的圖信息存儲(chǔ)和計(jì)算[17].因?yàn)楸疚氖腔贙ipf&Welling的設(shè)置來(lái)訓(xùn)練GCN,也就是一個(gè)2 層的GCN,因此只需要關(guān)注以目標(biāo)節(jié)點(diǎn)為中心,以其一階鄰居和二階鄰居組成的子圖即可.根據(jù)TUA的實(shí)驗(yàn)發(fā)現(xiàn),當(dāng)NF,NT固定時(shí),隨著NA的取值大于3 之后,ASR 幾乎不再隨著NA的增大而增大;同樣的,固定NA,NT的取值時(shí),當(dāng)NF大于2 之后,ASR 也不再隨NF的增大而增大;固定NA,NF時(shí),當(dāng)NT達(dá)到20 后,隨著NT的增大,ASR幾乎不再增大.但是,無(wú)論其中哪一個(gè)參數(shù)增大,對(duì)計(jì)算與存儲(chǔ)的消耗都會(huì)成倍的增加.同時(shí),對(duì)GTUA 進(jìn)行了相關(guān)參數(shù)的實(shí)驗(yàn),發(fā)現(xiàn)與TUA 有著相似的規(guī)律.因此在后續(xù)的實(shí)驗(yàn)中,規(guī)定參數(shù)設(shè)置NA=3,NF=2,NT=20.

3.3 實(shí)驗(yàn)結(jié)果與分析

本文進(jìn)行兩組實(shí)驗(yàn),第一組實(shí)驗(yàn)用來(lái)查看在梯度選擇過(guò)程中選擇不同數(shù)量的梯度值NG對(duì)ASR 帶來(lái)的影響,這里本文考慮NG∈{1,2,3,4,5,6},實(shí)驗(yàn)結(jié)果如圖3所示.由圖3可知,當(dāng)加入了梯度選擇的步驟之后,多數(shù)情況下ASR 值都是高于原始ASR 值的,且在這里的實(shí)驗(yàn)中發(fā)現(xiàn)NG取5的時(shí)候能在多數(shù)情況下得到最大的ASR 值,因此后面的實(shí)驗(yàn)就選定NG=5.

圖3 選擇不同數(shù)量的梯度對(duì)ASR的影響

第二組實(shí)驗(yàn)選擇一個(gè)恰當(dāng)?shù)腘G值,將本文方法GTUA 與TUA的ASR 值進(jìn)行對(duì)比來(lái)驗(yàn)證GTUA的有效性.由實(shí)驗(yàn)一的結(jié)果,本文選擇NG=5.結(jié)果如表1所示,可以很清楚地看到GTUA 在多數(shù)情況下優(yōu)于TUA,在少量情況下取得與TUA 同樣的結(jié)果,而取得相同結(jié)果的原因是每一次迭代都在梯度最大值處的擾動(dòng)能得到最大的損失函數(shù)值,表1的最后一行也表明GTUA 與TUA 相比,平均ASR 提高了1.7%.

表1 GTUA 與TUA的性能比較(ASR)

表2展示了GTUA 與TUA的一次訓(xùn)練加測(cè)試的耗時(shí)對(duì)比,可以發(fā)現(xiàn):因?yàn)镚TUA 梯度選擇的過(guò)程需要計(jì)算NG次損失函數(shù),因此耗時(shí)要遠(yuǎn)大于TUA,且通過(guò)實(shí)驗(yàn)發(fā)現(xiàn),隨著圖的節(jié)點(diǎn)與邊的增多,兩者之間的耗時(shí)差距越來(lái)越大,因此GTUA 比較適用于小圖,而對(duì)于大圖,時(shí)間成本略高.但是,由于GTUA 選擇梯度的過(guò)程,從而導(dǎo)致它并不依賴于損失函數(shù)對(duì)特征矩陣的最大梯度,而TUA 則嚴(yán)重依賴于上述最大梯度,所以一些微小的改動(dòng)并不會(huì)對(duì)GTUA 模型的結(jié)果造成影響,卻會(huì)大大影響到TUA的結(jié)果,所以GTUA 相比TUA 有更好的魯棒性.

表2 GTUA 與TUA 算法的效率比較(單位:s)

0.58 0.584 2 0.5125 0.53 3 1.0 1.0 4 0.895 0.915 5 0.555 0.5615 1 0.9855 0.9855 1 0.869 0.869 2 0.829 0.8335 0 PubMed平均值/ 0.8017 0.8193

4 結(jié)論與展望

本文提出了一種基于梯度的圖卷積網(wǎng)絡(luò)針對(duì)性通用對(duì)抗攻擊GTUA,實(shí)驗(yàn)結(jié)果表明,與當(dāng)前流行的方法TUA 相比,GTUA 最差能夠達(dá)到與其一樣的結(jié)果,但在多數(shù)情況下優(yōu)于TUA,由此可以看出梯度選擇的過(guò)程確實(shí)提升了擾動(dòng)的質(zhì)量.另外,本文也留下了一個(gè)后續(xù)的研究方向:對(duì)于離散數(shù)據(jù)類型上的基于梯度的方法,都可以嘗試加入梯度選擇的過(guò)程,由本文的結(jié)果可以大膽地預(yù)測(cè),其在很大程度上可能會(huì)帶來(lái)效果上的提升.