Exploratory Adversarial Attacks on Graph Neural Networks
依賴training loss的最大梯度的這種基于梯度的政策，在攻擊GNN模型時候，可能不會産生一個好的結果。
原因在于圖結構的離散的特點。
⇓ \Downarrow ⇓
我們可不可以推導出一種有效的方法，來選擇攻擊GNN的擾動？
我們提出一種新穎的exploratory adversarial attack命名為EpoAtk。
專注于poisoning attack 和 global attack。繼承基于梯度攻擊效率高的優勢，克服最大梯度方法的不足。
概括為三個階段：generation，evaluation，recombination
- 利用training loss的一階導數，EpoAtk生成一個擾動候選集，而不僅僅是一個具有最大梯度的擾動。
- 在evaluation階段，提出一個有效的評估函數，來評估候選集中的每個元素
- 為了進一步提高evaluation的有效性，引入recombination，從長遠的角度來看，避免training loss的局部最大值。
無向圖
每個節點有一個F維的特征向量，和一個class label（1~C）
X：代表一個節點特征矩陣，VxF
C L C_L CL：代表有标簽節點 V L V_L VL的one-hot label矩陣
在半監督節點分類任務中，給定 A , X , V L , C L A,X,V_L,C_L A,X,VL,CL，GNN的目标就是學到一個分類器 f w f_w fw，來預測無标簽節點的label， w w w是模型的參數集合。
為了滿足擾動不易被發現，假定攻擊者最多修改M次。
根據代表性的全局攻擊[24]、[28]，攻擊者使用一系列修改過程，按照貪婪的方式來得到最終的圖G(M)。
在每一步，隻允許增加或者删除一條邊，由于圖的離散結構，這可能不能獲得最優攻擊結果，是以提出EpoAtk。
模型
Generation部分
引入一個梯度矩陣 B ( k ) ∈ R ∣ V ∣ × ∣ V ∣ B^{(k)} \in R^{|V| \times |V|} B(k)∈R∣V∣×∣V∣
與以往方法不同的是，不隻是選擇最大的梯度，而是依次選擇 Δ \Delta Δ個滿足條件的來構成候選集。
Evaluation部分
先在原始圖上學習到一個可控模型，并且預測無标簽節點，作為ground truth。
評估函數如下：
f w ∗ f_{w^*} fw∗：在修改過的圖上學到的分類器
Z Z Z：在修改過的圖上學到的分類器給出的預測結果。
G a G_a Ga可能就是候選集裡最有效的擾動
Recombination部分
攻擊者在公式5的一系列修改中，可能陷入局部最大值。引入recombination來增加決策的不确定性。在此基礎上，将對recombination階段産生的每個元素進行精确評估，以克服上述難題。
recombination階段是以機率 k β M − 1 \frac{k \beta}{M-1} M−1kβ發生的。 k ∈ [ 1 , M − 1 ] k \in [1,M-1] k∈[1,M−1]， β \beta β是超參數。
也就是說：我們有 1 − k β M − 1 1-\frac{k \beta}{M-1} 1−M−1kβ的機率直接選取 G a k + 1 G_a^{k+1} Gak+1作為 G k + 1 G^{k+1} Gk+1。
如果recombination發生，就需要擴大搜尋空間，而不是簡單地選取 G a k + 1 G_a^{k+1} Gak+1作為 G k + 1 G^{k+1} Gk+1。
除了 G a k + 1 G_a^{k+1} Gak+1外，再從候選集中按照如下分布sample另外一個修改過的對抗圖 G b k + 1 G_b^{k+1} Gbk+1：
注： G a k + 1 G_a^{k+1} Gak+1和 G b k + 1 G_b^{k+1} Gbk+1與 G k G^k Gk隻有一個邊不同。
把這兩條邊記作 ( u a , v a ) (u_a,v_a) (ua,va)和 ( u b , v b ) (u_b,v_b) (ub,vb)（假設四個點不同，如果不滿足則重新sample）。
在 G a k + 1 G_a^{k+1} Gak+1和 G b k + 1 G_b^{k+1} Gbk+1的基礎上，再生成兩個擾動圖：
（用這種方法，還可以生成更多的擾動圖，但是為了高效和容易實作，隻考慮了這兩個圖）
從這個集合 S m S^m Sm中選擇最有效的擾動