Graph 13 - KDD20 Graph Structure Learning for Robust Graph Neural Networks

作者：Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, Jiliang Tang
來源：KDD2018 paper link
code : github

在防禦 Graph Adversarial Attack 的研究中，主要有兩個研究方向，一個是加入 Attention 機制，設法降低被擾動邊的 Attention 以降低攻擊影響，另一種是使用 Graph Structure Learning (GSL) 去學習 Graph 正常結構，找出不合理的邊，這篇論文的研究方向是後者，這篇論文的主要貢獻是提出了 Pro-GNN 架構，他可以在各種不同的 Adversarial Attack 下學習出合理的圖架構，邊還原邊訓練 GCN ，最後會得到一張已還原的 Graph 和結果較不受攻擊影響已訓練好的 model。

Perturbation Properties

作者觀察到被攻擊的圖與正常的圖有以下差異，這裡的攻擊用 metattack 為例 :

• metattack 會使 singular values 的 distribution 增加
• metattack 會提升 adjacency matrix rank
• 把 metattack 改動的邊去除， adjacency matrix rank 下降的速度遠超過把正常邊去除
• metattack 傾向連接兩個 feature 相差很大的 node ，所以 feature difference distribution 會向右偏移，且分佈變廣

Framework

Pro-GNN Architecture

以下是作者提出的 Pro-GNN 架構，對於一張被擾動的 Graph，先根據前面發現的一些擾動圖會有的特徵算梯度，對目前的 Adjacency matrix 更新，再算新結構的 GNN parameters，最後會得到一張乾淨的圖和已經訓練好的GNN模型，這種方式訓練 GNN 雖然在原本就沒受攻擊的 Graph 時犧牲了一些準確率，但換到的是對於受攻擊過的 Graph 有更好的魯棒性。

Formula

根據現實中 Graph 常有的特性和前面提到的發現，作者提出了具體的 Loss function，整個 Loss 由三個部分組成，以下是的第一部分：

• ∥A − S∥^2 是要限制每一階段還原的Graph不會跟原來的圖差太多，S代表還原後的adjacency matrix，A代表還原前的 adjacency matrix
• 加入 ℓ1 norm 是為了讓還原的圖維持 sparse 的特性
• 加入 nuclear norm 是為了讓還原的圖維持維持 low rank 的特性
• alpha 和 beta 都是作者設定的超參數，可以用來實驗哪些特型對圖結構學習比較有幫助

接下來是第二部分，由於正常 edge 兩端的特徵通常不會相差太大，而攻擊者傾向在兩個 feature 相差大的 node 間加上 edge，所以把 feature difference 的特性也加入 Loss，對所有 edges 兩端點 feature xi 和 xj 取差值平方和，由於是無向圖，所以前面乘以 1/2 。

對 feature difference 做 normalize ，除以 edge 兩端 nodes 的 degree 數。

第三部分就單純是 GNN 本身的 Loss，前面有提到 Pro-GNN 會邊做圖結構還原，邊學習 GNN ，所以 GNN Loss 也要考慮進去。

把上面提到的所有Loss加起來作為 Pro-GNN 的總體 Loss ，有加上了四個超參數 alpha, beta, gamma, lambda 作為四個 Loss 的影響程度實驗所需。

Pro-GNN Algorithm

以下是 Pro-GNN 的演算法，不論收到的 Graph 是否遭受攻擊，都當成是被擾動過的 adjacency matrix A 試著對其做還原，首先 initialize S 和 GNN parameters ， S 是當前迴圈所最新還原的 Graph adjacency matrix ，第四行到第六行都是依前面提到的性質分別算出梯度對目前的 adjacency matrix S 做更新，第七行的 P 是一個 Projection function ，因為前面更新完後可能會讓 S 超出 0~1 的範圍，所以用 P 來限制範圍在 0~1，在更新 S 的時候，完全沒有訓練 GNN ， 等到結構更新完後，第八行到第十行再用 GCN train ，在 train GCN 的過程中結構是固定的，整個 while 迴圈就是不斷固定結構或 GNN parameters 其中一邊更新另外一邊交互進行。(所謂的結構更新不是指把一條可疑的邊刪除，Pro-GNN 會對整個 Adjacency Matrix 的各個值根據梯度做更新)

Experiments

選用的資料集都是很常用的那幾個，值得注意的是 Polblogs 是沒有 feature 的，所以作者有設計一版 Pro-GNN 是不考慮 feature difference :

攻擊模型的部分作者使用了 targeted attack 的 Nettack 和 non-targeted attack 的 Metattack ，不管是哪種，對於圖還原的任務都是不變的， Pro-GNN 只管結構有沒有變動，所以只要會動到結構的攻擊理論上 Pro-GNN 都能用來防禦，以下是作者比較各種 GNN 在不同 dataset 下被 metattack 攻擊後的效果，裡面有兩種 Pro-GNN 是差在有沒有考慮 feature，可以看到只要有擾動， Pro-GNN 都能讓 acc 維持住，但沒擾動(Ptb Rate = 0)效果不一定會贏，因為他是默認收到的 Graph 都是被攻擊的，即使沒有被攻擊也會想辦法對他做還原，但如果 Graph 本身是符合一般會有的特性，這還原通常不會太多，Pro-GNN 是犧牲了一點沒被攻擊的 Graph 的正確率換來被攻擊後仍保有效果的魯棒性。

作者提出的 Pro-GNN 是邊還原圖結構邊訓練 GNN，為了確認交互進行的效果比較好，作者又設計了一種架構 – Pro-GNN-two，與一般 Pro-GNN 不同的是 Pro-GNN 是還原一點結構就 train GNN ，然後再還原一點結構交互進行，Pro-GNN-two 則是先把 Grpah 的所有邊還原直到收斂，再 train GNN，從結果可以發現在高擾動率的圖下，Pro-GNN-two 的效果比較好，但其實也差不多，根據我之後補的實驗發現大部分的情況下還是應該選擇 Pro-GNN，且從攻擊模型的角度來看，會有攻擊預算限制，為了不被發現，擾動率不會到太高，大都傾向用越少的擾動率達成越好的效果，所以邊還原圖結構邊訓練 GNN 的方式比較好。

以下是作者比較各個 Graph 性質對 Pro-GNN 效果影響的實驗，在目標函數中對四個特性都各有一個超參數在控制，其中一個設為1其他設為0來觀察各特性對模型效能的影響 :

• α Sparsity(|S|1)：擾動率小時對效能沒什麼提升，跟一般GNN差不多，但是擾動率大時效能提升逐漸加大
• β low rank(|S|*)：與feature smoothness是效能的主要貢獻，在低擾動率與高擾動率都有不錯的效果
• γ Graph Loss：沒啥差別，本身GNN就是只有這項
• λ feature smoothness：與low rank差不多

Conclusion

• GNN容易受到對抗式攻擊所影響準確率，本篇提出的 Pro-GNN 能在不知道圖受到何種攻擊的情況下有效的提升節點分類的準確率
• 透過實驗說明學習圖結構資訊與GNN參數對於防禦對抗式攻擊的重要性。
• 分析了幾個常見的 Graph 性質和用這些性質訓練對結果的影響

Weakness

• 在正常的 Graph 中反而會因試圖對其還原而使效果下降，可能可以朝這個方向研究
• 假設某個任務下會遇到的 Graph 不符合正常特性可能會讓效果變很差，例如一張不 sparsity 的 Graph