基于梯度選擇的圖卷積網絡針對性通用對抗攻擊①

曹海芳

(天津大學 數學學院,天津 300350)

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

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

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

1 相關知識介紹

1.1 圖卷積網絡 (GCN)[4,10]

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

1.2 圖對抗攻擊

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

在對圖結構數據的所有對抗攻擊中,偽節點攻擊是一種常見的攻擊方法,通過將一組偽節點注入到圖中來實現,從而可以避免對原始圖進行拓撲或屬性修改.例如,GreedyAttack和GreedyGAN 通過將偽造的節點直接添加到受害節點來進行目標節點攻擊[11].Wang 等[12]引入近似快速梯度符號法,該方法在受害節點和其他節點之間添加了一個惡性節點,從而導致受害節點被錯誤分類.但是,大多數現有的偽節點攻擊并非旨在進行普遍的對抗攻擊.而在本文提出的GTUA中,偽節點充當受害節點的2 跳鄰居.由于GCN的攻擊過程,偽節點特征的影響通過攻擊節點傳遞到受害節點,從而進行針對性通用對抗攻擊.

2 基于梯度選擇的圖卷積網絡針對性通用對抗攻擊

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

圖1 攻擊前后的受害節點分類結果

2.1 添加伴隨0 特征的偽節點

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

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

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

2.2 計算目標函數關于偽節點特征矩陣的梯度矩陣

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

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

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

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

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

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

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

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

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

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

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

圖2 不同梯度下loss 與步長的關系

3 實驗分析

3.1 數據集和評價指標

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

3.2 實驗設置

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

3.3 實驗結果與分析

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

圖3 選擇不同數量的梯度對ASR的影響

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

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

表2展示了GTUA 與TUA的一次訓練加測試的耗時對比,可以發現:因為GTUA 梯度選擇的過程需要計算NG次損失函數,因此耗時要遠大于TUA,且通過實驗發現,隨著圖的節點與邊的增多,兩者之間的耗時差距越來越大,因此GTUA 比較適用于小圖,而對于大圖,時間成本略高.但是,由于GTUA 選擇梯度的過程,從而導致它并不依賴于損失函數對特征矩陣的最大梯度,而TUA 則嚴重依賴于上述最大梯度,所以一些微小的改動并不會對GTUA 模型的結果造成影響,卻會大大影響到TUA的結果,所以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 結論與展望

本文提出了一種基于梯度的圖卷積網絡針對性通用對抗攻擊GTUA,實驗結果表明,與當前流行的方法TUA 相比,GTUA 最差能夠達到與其一樣的結果,但在多數情況下優于TUA,由此可以看出梯度選擇的過程確實提升了擾動的質量.另外,本文也留下了一個后續的研究方向:對于離散數據類型上的基于梯度的方法,都可以嘗試加入梯度選擇的過程,由本文的結果可以大膽地預測,其在很大程度上可能會帶來效果上的提升.