Graph 12 - KDD18 Adversarial Attacks on Neural Networks for Graph Data

作者：Daniel Zügner, Amir Akbarnejad, Stephan Günnemann
來源：KDD2018 paper link
code : github

Adversarial Attack 在 Graph 上的第一篇，作者提出的 Nettack 分類上算是Gray box, Targeted 的攻擊， poisoning attack 和 evasion attack 都有做。

surrogate model

由於沒有目標Model的參數，有Graph的feature、edge跟部分label，那就用這些去訓練一個surrogate的model，當作替代的攻擊目標，再攻擊這個替代目標來評斷效果

對於激活函數是未知的，那乾脆拔掉把替代model做成一個線性分類器： —> Adjacency Matrix * Feature * Weight

目標

• v0 是 targeted node，A 是攻擊的 node，c_old 是原本的類別，c 是新類別
• 裡面的max是分類機率最高的class，也就是攻擊後變成的類別，外面的max是指我們目標要讓原本正確的類別盡量小，攻擊後的錯誤類別盡量大
• 除了攻擊效果，也要對攻擊做限制，不能攻擊太多才不會被發現

Constraint

為了讓攻擊不被發現，不能變動太大，所以要限制預算，如何判斷變化的大小，Structure 的變化可以用 degree distribution 的 power law 來判斷，一般真實的 Graph 的 degree 會符合 power law ，power law 可以用 alpha 和 gamma 值來表示，比較攻擊前後的power law 之 alpha值變化，feature的話可以用 feature co-occurrence來判斷攻擊前後feature互相之間的關係。另一個比較簡陋但很好上手的方法是參考 target node 的 degree 來定，我用 target node degree + 2 來實作 Nettack 也是可行的。

Adversarial score

攻擊依據用score表示，選擇score最高的edge(Structure attack)或是node(Feature attack)攻擊：

分數算法就是改了edge或feature後，最大機率的錯誤類別與原本正確類別的機率(softmax)相差

Algorithm

把改動邊和改動點特徵次數相加，檢查是否有超過預算 delta 做為 while 迴圈條件，然後試著改動 edge ，找出影響最大的邊，改動他並算一個 Adversarial score s_struct，接著一樣的步驟改 node feature，算出 Adversarial score s_feat ，比較哪一個分數高，選分數高的改動加進 Graph 裡進行下一圈迴圈。

Dataset

這篇論文實驗所使用的 Dataset，會特別提是因為看了非常多篇論文，都躲不掉這幾個 dataset，可能是因為 Graph 完善的真實資料不多，所以好用的就重複用，N_LCC 是 node 數，E_LCC 是 edge 數 :

• CORA-ML : 由機器學習論文組成，將論文分為七類(基於案例, 遺傳算法, 神經網絡, 概率方法, 強化學習, 規則學習, 理論) 並用互相引用來連成edge
• CITESEER : 由資工領域論文組成，將論文分為六類(Agents, AI, DB(database), IR（Information Retrieval）, ML, HCI) 並用互相引用來連成edge
• POLBLOGS : 由2004年美國總統大選時的政治類型 blog 組成，每個節點代表一個 blog ，按政治傾向分為左派和右派，邊代表 blog 間的超鏈接

Experiment

• 擾動後正確率明顯下降
• 從結果來看direct比indirect好很多
• Evasion 和 poisoning 的效果比較和對各種模型的效果