鑽石舞台

論文標題：Understanding Structural Vulnerability in Graph Convolutional Networks作者：Liang Chen, Jintang Li, Qibiao Peng, Yang Liu, Zibin Zheng, Carl Yang單位：中山大學，Emory University論文鏈接：https://www.ijcai.org/proceedings/2021/310代碼鏈接：https://github.com/EdisonLeeeee/MedianGCN

今天介紹的是中山大學圖學習團隊被 IJCAI'21 會議接收的一篇論文：「Understanding Structural Vulnerability in Graph Convolutional Networks」。國際人工智能聯合會議（International Joint Conference on Artificial Intelligence, 簡稱為IJCAI）是人工智能領域中最主要的學術會議之一，位列CCF-A，2021年的論文接受率為13.9%。文章重點關注圖卷積網絡的魯棒性問題，基於崩潰點（breakdown point）理論解釋了圖卷積網絡容易受到攻擊的原因，並基於此提出兩種更加魯棒的圖卷積方法。

近年來，圖卷積神經網絡被廣泛用於各種圖結構數據的學習任務上，並在各個領域中取得了優異的表現。儘管圖卷積網絡已經在各個領域取得了一系列成功，有大量文獻指出其存在結構脆弱性問題，這使得通過修改圖中少量的邊或節點信息就能夠使得圖卷積網絡輸出錯誤的結果。更甚者，攻擊者可以不需要知道模型的參數也能夠發動有效的攻擊。

圖卷積網絡脆弱性的特點限制了其在實際中的廣泛應用。為了提高圖卷積網絡的魯棒性，一系列防禦方法被提了出來，包括對抗學習，遷移學習，魯棒性驗證等，並且有效地提高了模型的魯棒性。然而，以往的研究大多傾向於從實驗性的角度去解釋圖卷積網絡的脆弱性歸因，並沒有嘗試去揭示圖卷積網絡容易受到攻擊的本質原因。文章嘗試從另一個新的角度去解釋圖卷積網絡的脆弱性，並給出如下結論：圖卷積網絡的脆弱性主要歸因於不魯棒的聚合函數。在文章餘下的內容，作者從理論與實驗的角度提供了支撐這一結論的依據。

這裡首先回顧一下圖卷積網絡(Graph Convolutional Networks, GCN)。假設表示一個圖，其中為節點集合，為邊集，並且存在節點特徵集合。一個層的GCN定義為：

其中，與為每一層的節點表示(embedding)以及經過線性層與激活層輸出後的表示。為聚合函數，這裡以最常用的GCN為例：

文章的這一節以一個簡單的小實驗着手。通常來講，攻擊者的目的就是在給定攻擊成本的情況下去近似最強的攻擊擾動，從而給模型造成最大的破壞性。在這個實驗中，文章通過枚舉所有可能的擾動觀察是否可能改變GCN對目標節點的預測類別。具體地，擾動包括增加一條邊(Injection)，刪除一條邊(Deletion)，以及增邊和減邊同時使用的方法(Both)。

圖1展示了攻擊成功的節點的度和純淨度(purity)分布情況，純淨度(purity)定義為節點兩跳鄰居內與其相同類別的節點所占的百分比。表1則展示了兩個數據集上三種不同方法攻擊成功的節點百分比。從上述實驗可以得到如下結論：（1）修改一條邊能夠攻擊成功大多數節點，即使這些節點的度和純淨度(purity)都較高。（2）增加一條邊的攻擊效果比減少一條邊的攻擊成功率更高，也就是Injection是比Deletion更強的攻擊操作。這一結論也於之前的研究相符。

根據上一節的實驗性分析，可以發現增加邊的操作是比刪除邊的操作更能夠攻擊成功GCN。那麼，為什麼往圖中增加邊能夠攻擊GCN呢？作者以一張圖舉例：

通過圖2的簡單例子可以看到，使用均值聚合函數的GCN在目標節點鄰域注入一個惡意節點（也就是增加了一條邊），而這個節點在特徵上與其餘正常節點分布差異較大，通過均值聚合後改變了GCN的聚合結果。

接着，文章借鑑了魯棒統計學領域的崩潰點（breakdown point）理論進行分析：

簡單解釋下，崩潰點（breakdown point）理論就是衡量一個函數在受到數據擾動情況下魯棒性情況。崩潰點（breakdown point）可以直觀地理解為：最少需要往數據中添加數量為的數據點，能夠使得函數的輸出變化為無窮大。

我們假設攻擊者可以添加的擾動數量不超過，因為如果異常數據超過正常數據，那麼就難以區分「正常」與「異常」了。基於崩潰點（breakdown point）理論，可以發現均值函數是不魯棒的。在最壞情況下，只需要往數據中加入一個值為無窮的點，即可使得模型的輸出變化為無窮大。 因此，均值函數的崩潰點為最小值，其中 為目標節點的鄰居節點。

回到GCN的模型分析，在受到擾動的情況下，我們將GCN的聚合過程分解為如下兩部分：

由於GCN中的聚合權重總是正數，的輸出與擾動後的節點表示呈線性相關。因此僅需要添加一個特徵差異非常大的節點，就可以使得GCN輸出錯誤的預測結果。通過上述的分析也揭示了為何基於均值聚合的GCN容易受到結構性擾動攻擊，並且刪除邊的攻擊效果遠遠不如增加邊的效果。因為即使攻擊者刪除了一半的邊，也不會使得均值函數的輸出改變為無窮大。

基於此，文章提出了兩種魯棒的聚合函數來提高GCN的魯棒性。

顯然，從統計學角度上來看，中值函數的魯棒性是遠遠高於均值函數的，通過崩潰點（breakdown point）理論分析我們也可以發現，中值函數的崩潰點為最大值1/2，也就是攻擊者需要添加一半以上的擾動才可能成功改變輸出結果。

截尾均值函數可以看成是均值函數的改進，也就是我們平時在比賽打分經常用到的：去掉一部分最大值和最小值評分，最後取平均。通過這種方式，能夠很大程度上減少打分的偏差，從而得到更加公平的結果。在統計學中，截尾均值函數也是另一個魯棒的函數，其崩潰點至少為，其中為數據點的數量，為去掉的最大值和最小值百分比。

最後，文章通過圖3說明了三種聚合函數的在受到攻擊前和攻擊後的輸出，可以發現：在沒有受到攻擊的時候(clean)，三種聚合方式都能夠輸出正常的結果；在受到攻擊後(perturbed)，均值聚合函數的輸出變化較大，而其餘兩種魯棒聚合函數則受到的影響較小。

作者在四個引文數據集上進行了實驗，數據集信息如表2所示：

文章follow了2018年KDD Zügner et al.的文章，對每個圖進行了預處理，僅取最大聯通子圖(largest connected component, LCC)進行實驗。數據集劃分為10%訓練，10%驗證，80%測試。文章設置的攻擊場景為兩種：直接攻擊與間接攻擊。直接攻擊為擾動添加的邊可以直接作用到目標節點上，而間接攻擊則相反，擾動不能直接影響目標節點。通常直接攻擊的效果是遠遠好於間接攻擊的，但是間接攻擊會更具有隱蔽性。

文章基於中值聚合函數與截尾均值聚合函數提出了兩個魯棒聚合模型：MeidanGCN (median)和Trimmed GCN (TMean)。由於防禦模型不僅需要聚焦於魯棒性，還需要保持在原始數據集上的性能（防止模型過度擬合擾動數據），因此實驗分別從攻擊前和攻擊後進行分析。

攻擊前，可以發現文章提出的兩種方法都沒有影響GCN的性能。

作者採用來衡量模型的魯棒性，具體計算方式為，也就是當攻擊的擾動從1-5的時候模型分類準確率的加權和。可以發現，在攻擊後，GCN的魯棒性遠遠低於其餘防禦方法，而文章提出的兩種模型在直接攻擊場景下取得了最優的魯棒性，並且在間接攻擊的場景下也大多數魯棒性最優。

從圖4和圖5可以看見，在擾動情況較低的條件下，文章提出的兩種模型準確率都遠遠高於其餘方法，而隨着攻擊擾動的強度增大，這一差距在逐漸減小。這是由於圖中節點的度都較小（大約3左右），攻擊達到3以上則已經破壞了崩潰點理論的假設（擾動不超過1/2），因此模型難以區分正常和異常結點。然而在這種情況下，模型的準確率仍然高於其它方法。

本文研究了圖卷積網絡容易受到攻擊的原因，並基於崩潰點理論與實驗結果給出了解釋：圖卷積網絡的脆弱性主要來自於不魯棒的聚合函數。基於這一發現，文章進一步提出了基於中值聚合函數與截尾均值聚合函數提出了兩個魯棒聚合模型：MeidanGCN (median)和Trimmed GCN (TMean)，在四個數據集的實驗中說明了所提方法的有效性，從而驗證了文章的結論。

本期編輯：李金膛審核：陳亮