圖對抗攻擊研究綜述

翟正利，李鵬輝，馮 舒

青島理工大學 信息與控制工程學院，山東 青島 266525

近年來，得益于計算機計算能力的提升，大量可用的數據集以及算法的創(chuàng)新，深度神經網絡在圖像識別[1]、語義分割[2]、自然語言處理[3]、推薦系統(tǒng)[4]等領域表現出卓越的性能。圖作為一種表示對象及對象之間關系的數據結構，在現實世界中廣泛存在，如交通網絡、社交網絡、通信網絡等。圖神經網絡[5-7]將基于深度學習的方法應用于圖數據上，通過聚合圖中節(jié)點的鄰域信息學習圖數據的結構信息和特征信息，在節(jié)點分類、鏈路預測、圖嵌入等方面得到迅速發(fā)展。

雖然深度神經網絡具有出色的性能，但是近來研究表明，在精心設計的微小擾動下，深度神經網絡性能會嚴重下降[8-9]。例如在圖像分類[10]和文本分類[11]場景下，只需修改少數像素或文字就可以改變大部分測試數據的預測結果。作為深度神經網絡在圖數據上的應用，圖神經網絡也同樣繼承了深度神經網絡的脆弱性[12]，如圖1所示，在圖中添加或刪除少量邊將導致模型產生錯誤分類，隨著圖神經網絡在實際生產環(huán)境的部署應用[13]，這種脆弱性引起了學術界和工業(yè)界的諸多擔憂[14]，例如在安全至關重要的金融系統(tǒng)中，攻擊者可能通過建立與高信用客戶的連接，達到繞過檢測系統(tǒng)并獲得更高的信用值的目的。

圖1 微小擾動導致節(jié)點的錯誤分類

隨著人們對于圖模型安全性的關注，圖對抗攻擊的研究不斷取得新的進展，但與針對傳統(tǒng)深度神經網絡的攻擊相比，針對圖神經網絡的對抗攻擊存在以下挑戰(zhàn)：（1）與圖像等具有連續(xù)特征的歐式空間數據不同，圖數據的結構信息和特征信息是離散的，因此設計有效的攻擊算法更具挑戰(zhàn)性；（2）由于圖數據在現實世界的廣泛存在，使得圖數據具有多種類別，同時，現實世界的圖可以包含數以千萬計的節(jié)點，如社交網絡等，圖數據的多樣性和大規(guī)模性對算法的時間和空間復雜度提出了更高的要求；（3）在圖像中，可以使用特定的距離函數來衡量人眼無法察覺的擾動的大小，而在圖數據中，不僅難以定性擾動是否可察覺，而且定量的評估標準也亟待分析研究。

隨著對圖對抗攻擊研究的深入，攻擊理論和模型已經得到了迅速的發(fā)展，推動圖對抗攻擊的研究，有助于提高對圖神經網絡的更深層次的理解，提高模型的魯棒性與可解釋性，以促進其更廣泛的應用。本文對現有圖對抗攻擊研究進行全面、系統(tǒng)的介紹，對不同攻擊算法的建模方法進行比較和總結，根據攻擊算法的不同攻擊策略進行分類，并總結了圖對抗攻擊領域面臨的挑戰(zhàn)以及發(fā)展方向。

1 定義與符號

設圖G=(A,E)，其中V={v1,v2,…,vn}表示圖中n個節(jié)點的集合，E表示圖中m條邊的集合，E中每個元素eij=(vi,vj)表示從節(jié)點vi到節(jié)點vj的邊；使用鄰接矩陣A∈Rn×n表示圖中節(jié)點間的連接，當eij∈E時Aij=1，否則Aij=0；使用X∈Rn×d表示圖G上節(jié)點的特征矩陣，其中Xi∈Rd表示圖中第i個節(jié)點的d維特征。

未添加擾動的圖稱為原始圖或干凈圖，而添加了擾動ε后的圖稱為擾動圖或對抗樣本G"，擾動ε的上限稱為擾動預算Δ，使用fθ*表示攻擊者訓練得到的結構和性能與被攻擊模型相似的代理模型，表1列示了本文常用符號及含義。

表1 符號及說明

2 圖對抗攻擊概述

根據攻擊者對目標模型的了解，將攻擊分為白盒攻擊和黑盒攻擊，白盒攻擊是指攻擊者完全了解模型信息的情況下進行的攻擊，黑盒攻擊則是指攻擊者部分了解甚至完全不了解目標模型情況下進行的攻擊；根據攻擊發(fā)生的不同階段，可以將攻擊分為逃逸攻擊和投毒攻擊，其中逃逸攻擊發(fā)生在模型測試階段，而投毒攻擊發(fā)生在模型訓練階段[15]；根據攻擊的目標，可以將攻擊分為定向攻擊和非定向攻擊，定向攻擊指攻擊后模型輸出攻擊預設值，非定向攻擊指攻擊后模型輸出任意錯誤值；根據攻擊方式可以將攻擊分為拓撲攻擊和特征攻擊，拓撲攻擊通過修改圖結構進行攻擊，特征攻擊通過修改節(jié)點特征進行攻擊[12]。總結現有圖對抗攻擊算法，使用以下定義描述圖對抗攻擊：

定義1（圖對抗攻擊）圖對抗攻擊是指通過在圖G上添加微小擾動ε，得到對抗樣本G"，使模型性能大幅度下降：

其中，y表示模型預測值或標簽，fθ"表示攻擊模型，當時表示逃逸攻擊，當?=G"時表示投毒攻擊。給定擾動預算Δ，使用函數D衡量擾動圖和原始圖之間的差異，對于圖中擾動量ε通過以下約束保證擾動難以被察覺：

3 攻擊算法

為了便于后續(xù)介紹，本文將圖對抗攻擊算法分為拓撲攻擊、特征攻擊以及兼具拓撲攻擊和特征攻擊方式的混合攻擊三類進行介紹，表2對比了典型攻擊算法。

3.1 拓撲攻擊

拓撲攻擊也稱為結構攻擊，在實際的攻擊操作中，攻擊者可以通過在圖中添加、刪除節(jié)點間的邊以達到降低模型性能的目的。

RL-S2V[16]嚴格限制了攻擊者對目標模型的了解，在此種黑盒攻擊設定下攻擊者不僅不了解模型，同時還假設攻擊者無法訪問訓練數據的標簽信息，僅能依靠被攻擊模型的輸出作為反饋來修改圖結構。基于上述假設，RL-S2V 將Q-learning[17]引入攻擊模型中，把攻擊過程建模為馬爾可夫決策過程（Markov Decision Process，MDP）。

動作at：在圖中添加或刪除邊，同時采用分層操作降低執(zhí)行此動作的時間復雜度。

狀態(tài)st：使用元組(G"t,va)表示t時刻的狀態(tài)，其中va表示目標節(jié)點，G"t表示t時刻的擾動圖。

獎勵函數r：由于攻擊者的目的是使目標節(jié)點va被錯誤分類，因此在修改圖的過程中獎勵函數值始終為0，即r(st,at)=0,?t=1,2,…,m"-1，僅在終止時才獲得獎勵：

終止狀態(tài)：當修改邊的數量達到m"時，算法終止。

與RL-S2V[16]類似，ReWatt[18]同樣將攻擊過程建模為MDP，但ReWatt 采用重連邊作為動作at，具體而言，給定節(jié)點三元組(v0,v1,v2)，刪除v0和v1之間邊的同時添加連接v0和v2的新邊，保證圖中節(jié)點和邊的總數不發(fā)生改變，此外，ReWatt使用不同的獎勵函數：

其中，K表示預定義的重連邊的操作次數，通過修改百分比p∈(0,1)可以靈活改變攻擊預算，與RL-S2V 僅在MDP 終止時獲得獎勵不同，ReWatt 在攻擊成功時獎勵正數得分，而在每次采取動作時得到負數獎勵，算法在重連邊次數達到K次或成功修改了圖分類模型的輸出標簽時終止。

表2 典型攻擊算法比較

Q-Attack[19]是基于遺傳算法攻擊社團探測模型的方法，采用與ReWatt相同的重連邊[18]攻擊策略作為基因編碼，攻擊的次數作為每個染色體的長度，并且基于模塊度Q作為適應度函數fit的設計基礎：

其中，s是列向量，每個元素si表示節(jié)點vi的社團標簽，式表明模塊度越低的個體其適應度越高。EPA[20]為了節(jié)省存儲空間將重連邊的邊編號作為基因編碼，染色體在交叉過程中的長度是可變的，同時在突變過程中結合圖的拓撲特征進行搜索，以快速獲得近似最優(yōu)解，其適應度函數由衰減函數和攻擊效果評估函數構成。

同樣基于遺傳算法的EDA[21]用于攻擊圖嵌入模型，與Q-Attack[19]相同，將重連邊作為基因，適應度函數為：

其中，D(G,G")用于衡量擾動圖和原始圖之間的歐式距離，EDA 的目標是最大化嵌入空間中節(jié)點對間的歐式距離。

給定圖G，FGA[22]計算目標節(jié)點的損失函數值對每對節(jié)點的梯度信息，之后修改梯度絕對值最大的節(jié)點對間的邊，當修改邊的數量到達擾動預算時，將修改后的圖作為對抗樣本。IGA[23]利用圖自動編碼器的梯度信息，進行迭代梯度攻擊以破壞鏈路預測模型，同時針對不同的實際環(huán)境可以對攻擊模型進行不同限制。Sun等[24]將投影梯度下降（Projected Gradient Descent，PGD）引入圖對抗攻擊中，對無監(jiān)督節(jié)點嵌入算法進行投毒攻擊，并在下游鏈路預測任務中證明了攻擊的有效性。Xu 等[25]將PGD 用于攻擊節(jié)點分類模型，使用對稱矩陣S={0,1}n×n來表征圖中的邊是否被修改，當且僅當Sij=Sji=1 時才修改節(jié)點vi和vj之間的連接，因此可以通過搜索最佳擾動矩陣S得到對抗樣本，并且針對投毒攻擊和逃逸攻擊，分別提出了PGD拓撲攻擊和min-max拓撲攻擊。雖然同樣利用梯度信息進行攻擊，但Chen等[26]認為多數直接利用模型梯度信息的攻擊算法[12，22-23，25]易陷入局部最優(yōu)解，因此結合動量法提出了MGA模型，使迭代過程更加穩(wěn)定。

不同于利用模型梯度信息設計的攻擊算法，Bojchevski等[27]利用特征值擾動理論評估了基于隨機游走的節(jié)點嵌入模型的脆弱性，通過在攻擊預算內添加或刪除邊來降低節(jié)點嵌入的質量，針對下游節(jié)點分類和鏈路預測任務分別采用Aclass和Alink算法進行攻擊；GF-Attack[28]使用圖信號處理方法描述圖嵌入，通過攻擊模型的圖濾波器修改邊，同時利用特征矩陣獲得對抗樣本，并在下游的節(jié)點分類任務中較RL-S2V和Aclass具有更好的攻擊性能；Wang等[29]從基于協(xié)作分類的圖分類模型出發(fā)，提出了利用LinLBP 生成對抗樣本的攻擊方法，并且實驗證明了此攻擊可以轉移到基于圖神經網絡的圖分類模型中。受圖像上通用攻擊[30]的啟發(fā)，Zang等[31]認為圖中存在部分“錨節(jié)點”，通過修改“錨節(jié)點”與目標節(jié)點的邊使目標節(jié)點被錯誤分類，而且這些“錨節(jié)點”可以通用于攻擊任何目標節(jié)點。

與傳統(tǒng)深度算法將元學習用于模型超參數優(yōu)化相反，Zügner等[32]提出的Metattack將輸入圖數據作為超參數進行優(yōu)化以進行黑盒設定下的投毒攻擊：

元梯度▽mateG表示微小擾動下模型訓練后的損失Latk的變化。θ*是通過T次迭代獲得的模型參數：

其中α表示學習率，Ltrain表示訓練損失。根據訓練過程將元梯度展開可以得到：

為了緩解元梯度計算和存儲的高代價，可以利用一階近似和啟發(fā)式算法簡化元梯度的計算，得到元梯度▽mateG后，采用貪婪策略選擇添加或移除邊。

在針對社交網絡的攻擊中，CD-Attack[33]首先利用圖神經網絡和歸一化割設計社團探測代理模型，然后設計滿足離散約束的圖生成網絡，最后利用策略梯度法獲得對抗樣本，CD-Attack 還要求同時從局部相似度和全局相似度來保證擾動的不可察覺性。為了在社交網絡中逃避基于相似度的鏈路預測算法的檢測，DICE[34]同時刪除和添加節(jié)點間的連接，而基于啟發(fā)式的OTC 和CTR 算法則分別通過添加連接和刪除連接來隱藏社交關系[35]，并通過實驗證明了：刪除與現有朋友的連接（CTR）相比添加與新朋友的連接（OTC）能提供更好的掩飾性，Zhou等[36]通過刪除邊來最小化目標鏈接的相似性，達到隱藏鏈接的目的。

TGA[37]是針對動態(tài)圖鏈路預測的第一個攻擊算法，其利用不同時刻的深度動態(tài)圖嵌入的梯度信息進行重連邊，使目標鏈路無法被預測。與TGA 不同，Fan 等[38]提出的動態(tài)圖鏈路預測攻擊屬于黑盒設定下的逃逸攻擊，采用基于強化學習的算法，其基本策略和ReWatt[18]類似，而獎勵函數用式表示：

其中，函數h衡量擾動下的鏈路預測性能，errt表示時刻t錯誤預測的鏈路數，n"表示動態(tài)圖序列中擾動圖的數量。當模型在狀態(tài)st+1的性能比狀態(tài)st差時，獲得正獎勵。

3.2 特征攻擊

相較于拓撲攻擊和混合攻擊，僅通過修改圖中節(jié)點的特征進行特征攻擊的模型較少，但是特征攻擊并不會改變圖中節(jié)點數，也并不修改節(jié)點間的邊，因此可以保持圖中重要的拓撲特征。

基于標簽傳播算法的思想，Liu 等[39]提出針對基于圖的半監(jiān)督學習模型的投毒攻擊的一般框架，并且基于梯度下降設計不同的算法用于回歸和分類任務。

文獻[40]考慮了圖卷積神經網絡（Graph Convolutional Network，GCN）聚合鄰居信息的特性，通過擾動目標節(jié)點vi的k(k≥2)階鄰居進行攻擊，定義投毒效率來查找擾動節(jié)點：

其中，anc(vi,vj)表示以目標節(jié)點vi為根節(jié)點的鄰居樹中vj的祖先節(jié)點集，φ1vi(η)=1。在候選節(jié)點集中選擇投毒效率最高的節(jié)點構造特征擾動。

3.3 混合攻擊

混合攻擊可以綜合利用拓撲攻擊與特征攻擊的攻擊操作，更進一步攻擊者可以偽造新節(jié)點注入圖中，并添加偽造節(jié)點與原始圖中節(jié)點之間的邊。

針對圖數據的早期攻擊[41]通過在原始圖中注入節(jié)點和邊攻擊圖聚類算法。Nettack[12]是第一個在屬性圖上進行對抗攻擊的黑盒攻擊模型，在節(jié)點分類任務中，給定目標節(jié)點vi，Nettack的目標是通過代理模型，修改圖G尋找對抗樣本G"，使得

其中，Z表示模型輸出的分類概率，yold和y分別是基于圖G和對抗樣本G"得到的va的類別，算法的目標是將va的預測類別yold變?yōu)閥，并使得兩者的對數概率距離最大化。為了保證擾動的不可察覺性，Nettack 除了保證攻擊滿足等式外，同時需要保留圖的數據特征。Entezari 等[42]進一步研究了Nettack[12]擾動，表明其攻擊修改了圖的高階譜，并提出了構建低秩矩陣擾動原始圖的LowBlow攻擊方法。

Wang等[43]利用貪婪算法在圖中注入虛假節(jié)點以降低GCN性能，同時為了保證虛假節(jié)點的特征足夠逼真，利用生成對抗網絡（Generative Adversarial Network，GAN）思想提出了Greedy-GAN 算法，添加鑒別器使生成節(jié)點特征與原始圖中節(jié)點特征相似。

基于梯度的攻擊在圖像對抗攻擊中應用廣泛，典型算法包括利用損失函數梯度的FGSM（Fast Gradient Sign Method）[44]和模型輸出梯度的JSMA（Jacobianbased Saliency Map Approach）[15]，Wu 等[45]在此基礎上利用積分梯度（Integrated Gradients，IG）解決了圖神經網絡的離散輸入問題，通過式計算IG得分（以拓撲攻擊為例，特征攻擊可以通過簡單修改獲得），對于定向攻擊，優(yōu)化目標是最大化F的值，而非定向攻擊則修改具有高IG得分的節(jié)點特征或邊。

當F=L 時，稱攻擊為IG-FGSM，當F=fθ時，稱攻擊為IG-JSMA。

NIPA[46]是另一種基于強化學習的攻擊模型，但與RL-S2V[16]修改原始圖中節(jié)點之間的邊作為動作at構建MDP 的方式不同，NIPA 將at定義為虛假節(jié)點注入或在虛假節(jié)點與原始圖中節(jié)點之間添加邊，獎勵函數設計為：

其中At表示時刻t測試集中節(jié)點標簽與模型預測標簽不同的節(jié)點數占測試集中所有節(jié)點的比例。NIPA攻擊方法得到的擾動圖與原始圖在包括基尼系數和分布熵在內的多種屬性上都是相似的。

GTA[47]是首個針對圖神經網絡的后門攻擊模型，使所有含有觸發(fā)器的輸入被木馬模型fθ"錯誤分類。GTA將攻擊中的觸發(fā)器gt定義為子圖，并且針對不同圖定制不同觸發(fā)器。通過給定圖G與觸發(fā)器gt混合得到擾動樣本G"，攻擊的目標為：

其中，fθo表示預訓練的圖神經網絡，h表示微調后的分類器，將帶有觸發(fā)器的對抗樣本錯誤分類到指定類別yt，同時確保原始圖在原始模型和木馬模型中具有相同的分類結果。Zhang等[48]對圖數據上的后門攻擊進行了更深入的研究，提出了用于描述后門攻擊的具體參數，并使用隨機子圖作為觸發(fā)器以逃避檢測系統(tǒng)。

針對圖神經網絡的不同實際應用，Zhang 等[49]評估了知識圖譜嵌入（Knowledge Graph Embedding，KGE）模型的脆弱性，通過添加或刪除KGE 訓練集中特定的知識實體進行投毒攻擊，從而改變目標事實的合理性；HG-Attack[50]是針對惡意軟件檢測系統(tǒng)的攻擊算法，通過注入惡意應用程序，使惡意軟件繞過檢測系統(tǒng)被分類為正常應用程序；不同于構造虛假用戶注入數據集攻擊推薦系統(tǒng)[51]，CopyAttack[52]通過復制源推薦系統(tǒng)的用戶資料，利用強化學習選擇和修改用戶資料，得到可用于注入目標推薦系統(tǒng)的用戶資料；Fang等[51]證明了即使在部署了檢測虛假用戶的推薦系統(tǒng)中，大部分虛假用戶仍然能夠繞過檢測。

4 圖對抗攻擊面臨的挑戰(zhàn)

雖然圖對抗攻擊已經取得諸多進展，但在以下方面仍存在挑戰(zhàn)。

（1）應用的多樣性：隨著對攻擊算法原理與實現研究的深入，對于鏈路預測等任務的對抗攻擊開始逐步推進，但是目前多數攻擊模型都集中于節(jié)點分類任務，針對圖分類、推薦系統(tǒng)、社團探測等任務的攻擊模型仍缺乏全面深入的研究，表3總結了攻擊算法在各種學習任務中的應用。

表3 攻擊算法的應用

（2）攻擊的可擴展性：圖對抗攻擊領域的可擴展性是指算法在不同規(guī)模和不同類型的圖上的適用性，具有高擴展性的算法通過較少改動甚至無需改動就可以應用于大規(guī)模或其他不同類型的圖，時間復雜度是衡量攻擊算法可擴展性的重要方面，表4展示了典型算法的時間復雜度，部分文獻設計了針對大規(guī)模圖的攻擊[29，43]；針對動態(tài)圖的攻擊上也出現了行之有效的算法[37-38]，但目前多數攻擊算法都是針對靜態(tài)圖進行設計的。將攻擊擴展到大規(guī)模圖，動態(tài)圖和異構圖是仍是具有挑戰(zhàn)性的任務。

表4 典型攻擊算法的時間復雜度

（3）攻擊的可轉移性：可擴展性主要針對數據集的規(guī)模和類型，而可轉移性[12，19-24]是指針對一種模型設計的對抗樣本也可用于攻擊其他模型，可轉移性是多數黑盒算法設計的依據，利用可轉移性設計代理模型，得到的對抗樣本使其他模型性能遭到破壞，但是訓練代理模型要求擁有被攻擊模型的訓練集，如何在少樣本甚至零樣本情況下獲得對抗樣本是一個重要的研究方向。

（4）攻擊的通用性：指將針對一個目標上進行的擾動操作，應用于其他目標也具有相同或類似的攻擊效果，圖像領域的通用攻擊已經取得了重要進展[30]，而對圖數據通用性攻擊的研究才剛剛起步[31]。能否對所有攻擊目標設計通用的擾動操作、降低擾動設計的代價，是亟待研究的問題。

（5）攻擊的可行性：在現實系統(tǒng)中，攻擊模型往往面臨著更多復雜的限制，而攻擊的可行性取決于攻擊模型架構設置的合理性，主要包括：①攻擊算法假定的對被攻擊模型及數據集的了解；②攻擊在真實環(huán)境中是否可行。多數黑盒算法[12，32-33，46]假定攻擊者可以利用原始圖數據集訓練代理模型生成擾動圖，實際生產環(huán)境中，圖神經網絡的訓練數據集并不會公開；即使在嚴格受限的黑盒攻擊設定下（攻擊者僅能獲取被攻擊模型的輸出）[16，27-28]，頻繁查詢模型的輸出結果，也將引起防御機制的察覺，對攻擊算法的限制條件越多，其相應的危害也越大；另一方面，白盒攻擊[37，45]的設定雖然在真實環(huán)境中并不合理，但是分析目標模型在最壞情況下的脆弱性，有助于提到對圖神經網絡的理解。同時在真實系統(tǒng)中，并不能保證擾動的有效性和隱蔽性，例如在社交網絡中，并不能輕易獲得與陌生人間連接的許可[35]；在推薦系統(tǒng)中，插入過多虛假節(jié)點可能會因破壞原始圖屬性[52]引起檢測系統(tǒng)的警覺。

（6）擾動的度量標準：在圖像數據中可以通過人眼觀察定性擾動是否可察覺、通過距離函數定量衡量擾動量大小，但在圖數據中由于節(jié)點間的關聯(lián)性，難以確定擾動是否足夠隱蔽，同時實際的擾動操作具有不同的難度，例如在圖中修改現有節(jié)點與注入虛假節(jié)點難度差距較大。現有算法針對不同場景提出不同的度量標準，缺乏對擾動隱蔽性和擾動難度的系統(tǒng)研究。

5 結束語

盡管圖神經網絡在多種任務中都有著出色的表現，但與其他深度學習模型一樣易受到微小擾動的損害，導致模型性能的嚴重下降，引發(fā)安全和隱私問題。本文通過對圖對抗攻擊算法進行全面、系統(tǒng)的歸類分析，總結不同算法的實現、應用及其優(yōu)缺點，并分析了當前圖對抗攻擊領域面臨的挑戰(zhàn)，未來的圖對抗攻擊研究包含以下方面：

（1）在更廣泛的學習任務和圖數據類型中研究圖對抗攻擊的有效性和適用性，設計可以用于多種任務和圖數據類型的攻擊模型，產生與特定任務無關的對抗樣本以進行更廣泛的攻擊；分析包括異構圖、動態(tài)圖等在內的復雜圖數據類型的特征，并設計行之有效的攻擊算法。

（2）提高算法的效率，目前多數攻擊模型產生對抗樣本過程中，需要存儲大量梯度信息和圖數據的中間狀態(tài)，因此會耗費大量計算和存儲資源，但現實世界的圖數據往往是大規(guī)模和動態(tài)的，因此設計算法必須考慮計算復雜度。

（3）提高模型的實用性，算法的實用性不僅要求算法的有效性和高效性，同時針對實際攻擊而言，攻擊者往往受到更多的限制，包括模型與數據集的限制，因此在復雜受限的現實環(huán)境中進行攻擊需要更深入的研究，同時攻擊算法應當在更廣泛的數據集上進行驗證。

（4）構建統(tǒng)一的圖對抗攻擊算法的綜合評價體系，縱觀現有圖對抗攻擊，對于擾動量的度量以及模型效果的評價存在不同標準，需要更加通用的指標來度量不可察覺性，完善的指標能夠更加全面地衡量算法的優(yōu)劣，提高擾動樣本的可解釋性。