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

曹海芳

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

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

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

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

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

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

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

1.2 圖對抗攻擊

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

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

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

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

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

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

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

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

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

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

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

其中,‖E‖0表示偽節(jié)點與攻擊節(jié)點之間的連邊的數(shù)量,‖XF‖0表示給偽節(jié)點添加的特征的數(shù)量,二者都受到參數(shù) Δ的限制,因為擾動必須是微小的.其中,

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

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

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

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

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

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

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

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

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

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

3 實驗分析

3.1 數(shù)據(jù)集和評價指標(biāo)

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

3.2 實驗設(shè)置

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

3.3 實驗結(jié)果與分析

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

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

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

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

表2展示了GTUA 與TUA的一次訓(xùn)練加測試的耗時對比,可以發(fā)現(xiàn):因為GTUA 梯度選擇的過程需要計算NG次損失函數(shù),因此耗時要遠(yuǎn)大于TUA,且通過實驗發(fā)現(xiàn),隨著圖的節(jié)點與邊的增多,兩者之間的耗時差距越來越大,因此GTUA 比較適用于小圖,而對于大圖,時間成本略高.但是,由于GTUA 選擇梯度的過程,從而導(dǎo)致它并不依賴于損失函數(shù)對特征矩陣的最大梯度,而TUA 則嚴(yán)重依賴于上述最大梯度,所以一些微小的改動并不會對GTUA 模型的結(jié)果造成影響,卻會大大影響到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ò)針對性通用對抗攻擊GTUA,實驗結(jié)果表明,與當(dāng)前流行的方法TUA 相比,GTUA 最差能夠達(dá)到與其一樣的結(jié)果,但在多數(shù)情況下優(yōu)于TUA,由此可以看出梯度選擇的過程確實提升了擾動的質(zhì)量.另外,本文也留下了一個后續(xù)的研究方向:對于離散數(shù)據(jù)類型上的基于梯度的方法,都可以嘗試加入梯度選擇的過程,由本文的結(jié)果可以大膽地預(yù)測,其在很大程度上可能會帶來效果上的提升.