FINDING ADVERSARIALLY ROBUST GRAPH LOTTERY TICKETS

《FINDING ADVERSARIALLY ROBUST GRAPH LOTTERY TICKETS 》NeurIPS 2023&ICLR 2024

分析对抗性攻击对图属性的影响

像MetaAttack、PGD和PR-BCD这样的对抗性攻击通过引入新边或删除现有边来毒害图结构，导致原始图属性发生变化。
我们分析了干净边和对抗边连接的节点在属性特征上的差异。

图a和图b描述了受PGD攻击的homophilic和 heterophilic图数据集中连接节点属性特征差的密度分布。在同态图中，攻击倾向于连接属性特征差异较大的节点。防御技术可以潜在地利用这些信息来区分图中的良性和敌对边缘。然而，这不是 heterophilic图的情况。相反，我们利用节点的位置特征，使用像DeepWalk这样的位置编码技术(Perozzi等人，2014)。有趣的是，从图c中我们可以看到，在heterophilic图中，攻击倾向于连接位置特征差较大的节点。ARGS使用这些图的属性来迭代地从homophilic和 heterophilic图中修剪对抗性边。

方法

$L$
总所周知，两层的GCN可以表示为
$Z = f (A, X, Θ) = S (\hat{A} σ (\hat{A} X W_{(0)}) W_{(1)})$
设计了一个transductive semi-supervised node classification (SSNC) loss：
$$
\mathcal{L} _0 (f(\left{A, X\right}, \Theta))=-\sum _ {l \in \mathcal{Y} _{TL}} \sum _{j=1} ^C Y _{l_j} log( Z {l_j})
$$
其中$\mathcal{Y}{TL} $是训练节点的索引， C 是类总数，$ Y_l $是$ v_l$one hot 标签。

posion 攻击者的目标是找到一个最优的扰动A '，欺骗GNN做出错误的预测。这可以表述为一个双层优化问题(Zugner et al.， 2018;zugner & gunnemann, 2019):
$$
arg \max\mathcal{L}{atk}(f(\left{A’,X\right},\Theta ^\ast))\
A’\in\Phi(A)\
\mathrm{s.t.}\quad\Theta^{\ast}=\arg\min{\Theta}\mathcal{L}{0}(f(\left{A’,X\right},\Theta))
$$
其中 $Φ (A)$ 是满足 $\frac{| A^{'} - A | 0}{| A | 0} \leq Δ$ 的领接矩阵。$\mathcal{L}{atk} $是攻击 l o s s 函数，$ \Delta $是 p e r t u r b a t i o n r a t e ，$ \Theta ^\ast$是摄动图上GNN的最优参数。

为了帮助消除对抗边和鼓励特征平滑，对于homophilic graphs：
$$
\mathcal{L}{fs} (A’,X)=\frac{1}{2} \sum{i,j=1}A_{ij}’ (x_i-x_j)^2
$对于 h e t e r o p h i l i c g r a p h s ：$
\mathcal{L}{fs}(A’)=\frac{1}{2}\sum{i,j=1}A_{ij}'(y_{i}-y_{j})^{2}
$$

以上有点像dirichlet energy。

dirichlet energy：
$t r (x^{⊤} L x) = | \nabla_{G} x |_{2}^{2} = \frac{1}{2} \sum_{i, j} W [i, j] (x [j] - x [i])^{2}$
进一步归一化：
$t r (x^{⊤} L x) = | \nabla_{G} x |_{2}^{2} = \frac{1}{2} \sum_{i, j} W [i, j] (\frac{x [j]}{\sqrt{1 + d_{j}}} - \frac{x [i]}{\sqrt{1 + d_{i}}})^{2}$
（上式来自《Dirichlet Energy Constrained Learning for Deep Graph Neural Networks》）

或
$t r (x^{⊤} L x) = | \nabla_{G} x |_{2}^{2} = \frac{1}{4} \sum_{i, j} W [i, j] | \frac{x [j]}{\sqrt{d_{j}}} - \frac{x [i]}{\sqrt{d_{i}}} |_{2}^{2}$
（上式来自《A Fractional Graph Laplacian Approach to Oversmoothing》）

其中d为节点的度。

其中yi∈R P为输入图G上运行DeepWalk算法(Perozzi et al.， 2014)得到的节点i, j的位置特征，P为节点位置特征个数。

另外，作者还训练了一个简单的两层MLP。mlp只使用节点特征进行训练。然后我们使用训练好的MLP来预测测试节点的标签。称这些标签为伪标签。最后，利用MLP预测置信度较高的测试节点计算测试节点CE损失项。

设 $Y_{P L}$ 为MLP预测置信度较高的测试节点集， $Y_{m l p}$ 为MLP的预测值。CE损失为：
$$
\mathcal{L}1(f({A’,X},\Theta))=-\sum{l\in\mathcal{Y}{TL}}\sum{j=1}^CY_{mlp_{l_j}}\log(Z_{l_j})
$最终 l o s s 为：$
\mathcal{L}{ARGS}=\alpha\mathcal{L}{0}(f({m_{g}\odot A’,X},m_{\theta}\odot\Theta))+\beta\mathcal{L}{fs}(m{g}\odot A’,X)\+\gamma\mathcal{L}{1}(f({m{g}\odot A’,X},m_{\theta}\odot\Theta))+\lambda_{1}||m_{g}||{1}+\lambda{2}||m_{\theta}||{1}
$$
其中， $α$ 和 $γ$ 设置为1。 $m_{g}$ 用于领接矩阵，$m\theta$用于模型权重。