圖對抗攻擊

 前  言  

深度學習已經在許多領域得到了廣泛的應用，如文本、圖像、音頻、視頻等，相應領域的對抗攻擊安全客上也有文章介紹過了，包括圖像、視頻、音頻等。事實上，這類數據格式在形式上有著統一而規整的尺寸和維度，它們也被稱作歐式結構（Euclidean Structure）。但是除此之外，現實生活中存在大量的非歐式結構的圖數據，例如互聯網、知識圖譜、社交網絡、蛋白質、化合物分子等。盡管深度學習在歐式結構數據上取得巨大的成功，但在圖結構數據上，基于神經網絡的深度學習表現得并不好。

在圖結構數據中，節點與節點之間的邊連接可能是均勻分布的，也可能是不均勻的。節點與節點之間沒有嚴格意義上的先后順序。對于神經網絡的輸入端而言，這些數據沒有固定的輸入尺寸。在數學表達上，這些數據與歐式結構數據相比，每一個區塊的特征矩陣維度都不是統一的，如下圖所示。

由于無法使用統一規整的算子對數據編排，導致CNN等神經網絡不能再直接對其進行諸如卷積和池化等操作，也就不再有局部連接、權值共享、特征抽象等性質。近年來Gori等人用RNN來壓縮節點信息和學習圖節點標簽，首次提出圖神經網絡（Graph Neural Network，GNN）這一概念。之后大佬提出圖卷積網絡（Graph Convolutional Network，GCN），正式將CNN用于對圖結構數據建模。GCN通過整合中心節點和鄰居節點的特征和標簽信息，給出圖中每個節點的規整表達形式，并將其輸入到CNN中。這樣一來GCN就能利用多尺度的信息，組合成更高層次的表達，其有效地利用了圖結構信息和屬性信息，為深度學習中其他神經網絡遷移至圖上提供了標準的范式。由此，開啟了GNN研究的熱潮。

在GNN受到廣泛關注的背景下，其安全性如何還沒有被探究過。本文將分析并復現圖對抗攻擊的開山之作—《Adversarial Attacks on Neural Networks for Graph Data》，這個工作獲得了KDD 2018的Best paper，可見其含金量。

 基  礎  

圖上最常用的任務之一就是節點分類：給定一個(帶屬性的)圖和少數節點的類標簽，任務是預測剩余節點的標簽，如預測社交網絡中的用戶類型等。雖然節點分類問題在此前已經有多種經典方案可以解決，但是這幾年由于圖神經網絡的領域的研究進展，大家發現圖卷積網絡在包括節點分類在內的圖學習任務中達到了很好的表現。這類的方法厲害的地方在于它們利用圖的關系信息來進行分類，而不是僅僅單獨考慮實例如節點及其特征，節點之間的關系（邊)也被利用來進行學習了，如下所示，表現的是layer0的一個節點是如何通過網絡從周圍的節點收集信息的。

在之前的一些文章中，我們已經提到神經網絡容易受到對抗樣本的攻擊，那么在圖神經網絡里面是否也可能存在類似的攻擊呢。這是顯然的，我們來類比一下，對于計算機視覺中的圖像分類任務而言，我們在進行對抗樣本攻擊時，攻擊者需要生成一些擾動，改變某些像素值從而實現攻擊，那么在圖神經網絡里面呢？我們知道它是依靠邊、節點信息的，所以攻擊者只需要修改這些內容就可以了，那么如何修改，以及怎樣才能保證修改最小化的同時而攻擊又最有效呢？這就是我們需要研究的地方。

對圖神經網絡進行攻擊的做法，說起來確實很簡單，就是改變節點的特征或者圖的結構。如下所示，在下圖中我們把以節點分類任務為例，將想要錯誤分類的節點稱為目標節點target node,將攻擊者可以控制修改的節點稱為攻擊節點attacker node，我們對其施加擾動，從而使得目標節點被誤分類。

但是這里最明顯的一個挑戰就在于，我們已經知道，這里存在著關系效應，模型在進行預測時并不是僅僅基于單個實例，而是會考慮實例之間的關系，所以可能我們僅修改某一個是不夠的；同時，這些關系信息的傳播又會帶來級聯效應，也就是說我們在修改一個實例的同時也會影響許多其他實例。這個問題是亟待解決的。此外，圖像是由連續特征組成的，但是圖的結構(節點特征)是離散的，因此在圖像上進行的攻擊算法如FGSM等這類基于梯度的方法是不適用的，我們的關鍵就在于怎么找到一個離散域的對抗樣本，而且不被人察覺，對于圖像我們直接說比較像素值修改前后的數值變化就可以，而對于圖，我們如何定義這一點，這也是需要考慮的。

節點分類

我們假設要攻擊的是一個具有二值節點特征的圖上的節點分類任務。我們先來看看形象化表示的例子，下圖中節點代表每個空手道練習者，邊代表空手道之外這些成員之間的互動。要預測的問題是區分一個給定的成員是忠于Mr. Hi還是John H。

上圖左邊是問題的初始條件，右邊是可能的解決方案，每個節點都根據聯盟進行了分類。該數據集可以用于其他圖問題，如無監督學習。我們以圖像為類比，節點層次的預測問題類似于圖像分割，我們試圖標記圖像中每個像素的角色。而如果類比于文本，類似的任務就是預測句子中每個單詞的詞性(例如名詞、動詞、副詞等)。

再來看看形式化的表示，設G=(A,X)是一個屬性圖，其中 A ∈ {0,1}^N×N 是表現連接的鄰接矩陣，X∈{0,1}N ×D表示節點的特征，我們用xv∈{0,1}D表示節點v的D維特征向量，我們假設節點ids是V={1,…,N},特征ids是F={1,…D}

給定有標簽節點的V的子集VL(設類標簽為C={1,2,…ck})，節點分類任務的目標是學習一個函數g:V->C，這會將v中的每個節點映射到C中的一類。由于對于給定的測試實例預測已經做完了，這些在訓練前都已經知道了，這就是一個典型的transductive learning的場景。

我們關注于使用圖卷積層的節點分類，設隱層l+1被定義為

其中

這是輸入圖G在通過identity matrix In加了自循環后的鄰接矩陣。

Wl是可以被訓練的層l的矩陣權重

σ(·)是激活函數

在第一層我們有

H(0)=X,也就是說使用節點特征作為輸入。用于隱表示H依賴于鄰接實例，所有的實例都被couple在一起。我們將GNN作為一個單個的隱層：

其中，

輸出的Zvc表示的是將節點v分類為類c的概率。這里，我們使用θ代表一系列參數，比如

最優的參數θ會被通過最小化以下交叉熵的方式以自監督的方式被學習到：

其中cv訓練集中給出的v的標簽。在訓練之后，Z就表示了圖中每個實例的類概率。

攻擊模型

攻擊者的目標是在圖

上產生一些小的擾動，是其變為

此時的分類性能會下降。

如果修改的是A(0),那我們稱之為結構攻擊，如果修改的是X(0)，那我們稱之為特征攻擊

假設我們的目標節點是v0，我們希望改變v0的預測。由于數據非獨立同分布的特性，節點v0的輸出不僅依賴于節點自身，同時依賴于圖中的其他節點。因為我們擾動的范圍不限于節點v0，同時我們也可以通過修改其他節點來實現我們的目的。所以我們這里引入攻擊節點A，對于G(0)的擾動就受到這些節點的約束，即：

如果目標節點不屬于攻擊節點，我們就稱這種攻擊方式為間接攻擊，因為v0被沒有被直接操作，而如果目標節點屬于攻擊節點，我們則稱這種攻擊方式為直接攻擊。

為了確保攻擊者不會完全地修改圖，我們要進行通過預算?限制允許的改變范圍：

我們將符合以上要求的擾動記做：

此時我們的問題可以被定義為：

給定一個圖

和一個目標節點v0、攻擊節點A

設cold表示基于圖G(0)的節點v0的類

上式表達的意思是，當我們找到一個擾動后的可以將v0分類為cnew,并且與cold有最大的距離的圖G’。這里實際上是一個雙層優化問題。我們也可以進一步簡化，我們考慮規避攻擊，假設參數是靜態的并且是基于原來的圖進行學習的，即

擾動預算

現在還有個問題，怎么保證對圖的擾動不會被注意到？

僅僅考慮預算?可能是不夠的。如果復雜的數據需要一個大的?，我們仍然想要一個看起來真實的圖G’。因此，我們的核心思想是使用那些可以保留圖的特定內在性質的擾動。

保留圖結構的擾動

圖結構最顯著的特征就是它的度的分布，在實際網絡中，度分布往往類似于冪律形狀。如果兩個網絡顯示出非常不同的度分布，很容易將它們區分開來。因此，我們的目標是只產生與輸入相似的冪律行為的擾動。為此，我們引用冪律分布的統計雙樣本檢驗。也就是說，我們使用似然比檢驗來估計G(0)和G ‘的二度分布是來自同一分布還是來自單個分布。我們首先估計冪律分布p (x)∝x?α的標度參數α(等價于G ‘)。雖然在離散數據的情況下沒有精確的和封閉的解來估計α，但是可以導出一個近似表達式，在這里我們將圖G轉換為

其中dmin表示冪律測試中一個節點所需的最小度

DG則是一個多重集，包括了節點度的列表，其中dvG是G的節點v的度。通過這種方法就可以估計了。

給定尺度參數αx，對樣本的對數似然性Dx可以很容易地計算為

利用這些對數似然分數，我們建立了顯著性檢驗，估計兩個樣本DG(0)和DG ‘是否來自相同的冪律分布(原假設H0)，而不是單獨的冪律分布(H1)。也就是說，我們提出了兩個相互競爭的假設

經過似然比檢驗后，最終的檢驗統計量為

拒絕原假設H0的典型p值(即兩個樣本都來自不同的分布)是0.05，即在統計學上，在20個案例中，我們拒絕原假設，盡管它成立(第一類錯誤)。雖然在我們的例子中，我們不能很容易地計算第二類誤差，但一般來說，第一類和第二類誤差概率呈反比關系。因此，通過選擇一個非常保守的對應于高類型I錯誤的p值，我們可以減少類型II錯誤的概率。因此，我們將臨界p值設為0.95，也就是說，如果我們從相同的冪律分布中抽樣二度序列，我們將在95%的情況下拒絕零假設，然后可以根據最初的懷疑來調查數據是否已經受損。另一方面，如果我們修改的圖的度序列通過了這個非常保守的檢驗，我們可以得出這樣的結論:度分布的變化是不明顯的。

使用χ2分布中的上述p值，我們只接受度分布滿足的擾動G’=(A’,X’)，其中度的分布滿足

保持特征統計量的擾動

由于設計基于共現的統計檢驗需要對特征上的聯合分布進行建模，這對于相關多元二進制數據來說是難以處理的，因此我們將其稱為確定性檢驗。在這方面，將特性設置為0是不重要的，因為它不會引入新的共現。問題是:什么樣的特征會被認為是不值得注意的?

為了回答這個問題，我們在來自G(0)的特征的共發生圖C=(F,E)上考慮一個概率隨機漫步者，其中F是特征的集合，E?F × F表示到目前為止哪些特征同時出現。我們認為，如果從節點u最初呈現的特征開始的隨機步行者到達特征i的概率非常大，那么添加特征i是不明顯的。形式上，設

是節點u表現出來的特征集合。我們認為如果滿足下式，則表明將特征i加到節點u上是不會被注意到的

其中，dj表示共現圖C的度。

也就是說,假設概率步行者從任意特征j∈Su開始，在執行一個步驟之后，它將以概率σ達到我特征i。在我們的實驗中，我們簡單地選擇σ為最大可達概率的一半，即

如果滿足上述原則，實際上就會有這兩個效果:第一，特征i與u的許多特征(即在其他節點上)同時出現的概率高;當它們被添加時，就不那么明顯了。第二，特征i僅與特征j∈Su同時出現，而不是特定于節點u(例如，特征j幾乎與所有其他特征同時出現)有低概率;加上“i”將會引人注目。因此，實現了添加特征卻不被注意的效果。

使用上述測試，我們只在特征值滿足下式時才接收擾動G’

生成對抗圖

我們使用一種順序方法，首先攻擊代理模型，從而獲得被攻擊的圖。這個圖隨后被用來訓練最終的模型。實際上，這種方法可以直接被視為可遷移性的檢查，因為我們并不特別關注使用的模型，而是只關注代理模型。

為了獲得一個易于處理的代理模型，卻仍然應用到圖卷積的思想，我們對模型進行線性化，用一個簡單的線性激活函數代替非線性σ(.)，得到

由于W(1)和W(2)是需要學習的參數，因此可以將它們合為單個矩陣W∈RD ×K。

由于我們的目標是最大化目標v0的對數似然的差異(給定一個特定的budget?)，因此可以忽略由softmax引起的與實例相關的歸一化。因此，對數概率可以簡單地簡化為A?2 XW。因此，如果訓練的代理模型(未損壞)輸入了帶有學習參數W的數據，我們定義了代理損失

并嘗試求解

這個問題雖然簡單得多，但由于離散域和約束，仍然難以解決。因此，我們使用一個可擴展的貪婪近似方案。為此，我們定義了評分函數來評估從添加/刪除一個特征f =(u,i)或者edgee=(u,v)到任意graphg =(a,X)所得到的額外損失:

近似解的方案偽碼如下

復雜度分析

候選集的生成(即哪些邊/特征允許改變)和score function可以遞增計算，并利用圖的稀疏性，從而確保可伸縮性。算法的運行時復雜度可以很容易地計算如下

其中thv0表示節點v0在算法運行過程中2-hop鄰居的大小。

在每個?次迭代中，每個攻擊者評估潛在的邊擾動(最多N)和特征擾動(最多D).對于前者，由于有兩個卷積層，需要更新目標的2-hop鄰域。假設圖是稀疏的，thv0遠小于N。每個特征在恒定的時間內進行特征擾動。因為所有的約束都可以在常數時間內檢查，所以它們不會影響復雜度。

復現及分析

分析

先來看看攻擊所需的運行時間，根據前面分析的復雜度，在下圖中，我們可以看到，我們的算法與圖結構的擾動數和考慮的影響節點的數量線性相關。

接下來我們評估兩種攻擊類型的Nettack的性能:分別是規避攻擊和投毒攻擊。在下圖中，每個點代表一個目標節點。

正如我們所見，直接攻擊是非常成功的——即使是在這個棘手的投毒攻擊中，幾乎每個目標都被錯誤分類了。而間接的攻擊(顯示在雙線右側)更加困難。接下來看看在GCN和CLN上的攻擊效果

可以看到，不論是哪種情況，我們發現直接攻擊比間接攻擊更困難。在這些方案中，我們也比較了兩種基線Rnd和FGSM，如圖所示，Nettack的表現優于兩者。

在下表中我們總結了不同數據集和分類模型的結果。

這里給出的是正確分類的目標節點的比例。在我們評估的所有數據集上，鄰模型上的對抗擾動都是可遷移到所有三個模型上的。我們看到FGSM的性能比Nettack差，原因之前已經說過的，因為梯度方法對離散數據不是最優的。下圖顯示了這種情況的原因:當改變A中的元素時，我們繪制了梯度與損失的實際變化之間的關系

通常梯度不能很好地接近損失。而Nettack的一個關鍵優勢是，我們可以精確和有效地計算出ls的變化。

在之前的實驗中，我們假設攻擊者知道輸入圖的全部知識，這是假設最強的情況。接下來我們分析在知識有限的情況下的結果:給定一個目標節點v0，我們只提供相對于Cora圖的大小增加的子圖。我們通過選擇距離v0越來越遠的節點來構造這些子圖，即我們首先選擇1跳鄰居，然后選擇2跳鄰居，以此類推，直到我們達到所需的圖大小。然后對子圖進行擾動。然后，這些擾動被遷移到我們訓練GCN的全圖中。下圖是繪制了攻擊者只有關于數據的有限知識的情況下的攻擊效果

上圖比較了直接攻擊和間接攻擊。在直接攻擊中可以看到，即使只觀察到圖的10%，仍然可以顯著地攻擊它。如果攻擊者知道整個圖，則需要的擾動次數最少。在間接攻擊中，我們注意到需要更多的擾動和75%的圖大小，攻擊才能成功。盡管如此，這個實驗攻擊者并不需要掌握全部的數據的知識就可以成功發動攻擊

復現

首先確定后要目標節點，同時訓練代理模型

初始化相關參數，這里比較重要的就是擾動次數

開始投毒

我們這里擾動的是特征，可以將其打印出來

接下來我們分別在有擾動和沒有擾動的情況下訓練GCN

這是沒有擾動的

這是有擾動的

然后可以分別將可視化的結果打印出來

可以看到攻擊生效了。