【论文笔记】GNNCERT DETERMINISTIC CERTIFICATION OF GRAPH NEURAL NETWORKS AGAINST ADVERSARIAL PERTURBATIONS

概述

针对分类图神经网络（GNN）的对抗攻击是通过向边或者节点中添加噪声来诱导GNN分类器分类错误

为了防御这种攻击，有两种形式的防御手段：

1. empirical defense 基于经验的防御
2. provable defense/certified defense 基于证明的防御

然而，现有的这两种防御手段都各有局限：

1. empirical defense无法防御自适应的或者最新的攻击手法
2. 目前的certified defense有以下不足：
   1. 现有的防御方法无法对 通过扰乱图的结构进行攻击 的方法实现足够鲁棒的保障
   2. 对于任意的节点特征扰动，也无法提供鲁棒的保障
   3. 这些防御都是基于概率的，因此他们的保障没法做到绝对可靠
   4. 他们的计算成本都很高

因此，为了解决目前的certified defense的痛点，本文提出了GNNCert网络，它能够：

1. 对图结构攻击和图节点攻击都提供可靠的防御
2. 可以证明，当图中受扰动的节点和边是有界的时候，GNNCert可以输出正确的标签，而且这个保证是确定性的（deterministic）
3. GNNCert是SOTA的

Related Work

图分类器的对抗攻击：

• Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph neural networks against adversarial structural perturbation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1645–1653, 2021.
• Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, pp. 1003–1013. PMLR, 2020.

Certified Defenses：

• Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks to graph neural networks. In Proceedings of the 26th ACM Symposium on Access Control Models and Technologies, pp. 15–26, 2021b.
  • 
• Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph neural networks against adversarial structural perturbation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1645–1653, 2021.
• Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, pp. 1003–1013. PMLR, 2020.

方法

问题设置

符号表

威胁模型

• 攻击者目标：扰动图以致图分类器分类错误
• 攻击者知识：知道图和图分类器的所有知识
• 攻击者能力：图的结构和节点特征都可以扰动
• 防御者目标：在图受扰动的边或者节点的数量是小于一个阈值的时候，预测扰动图的标签和干净图的标签一一样

模型

GNNCert包括三步：

1. 切分图为子图
2. 在子图上构建集成图分类器
3. 推导集成分类器面对扰动时的鲁棒保障

切分子图

通过计算一个哈希值来分类，本质上类似于哈希表

$\text{ID}_v$ –> $S_v$

对于按结构的划分：

–> $\mathcal{H}(S_{v_i} \bigoplus S_{v_j})% T_s + 1$

对于按特征的划分：

–> $\mathcal{H}(S_{v})% T_f + 1$

对于按结构-特征的划分：

先按结构划分，对每个划分的子图再按边划分

构建集成分类器

$$ \begin{align} l &= g(G) \ &=\text{argmax }{c = {1, 2, \ldots,C}} N_c \ &= \text{argmax }{c = {1, 2, \ldots,C}} \mathbb{I}(f(\mathcal{G}_t = c)) \end{align} $$

推导鲁棒保障

定理一

对于被扰动的图来说

$$ N_c - M \le N_c^p \le N_c + M $$

$$ M \le M^p = \left \lfloor \frac{N_l - \text{max}_{c \in {1,2,\ldots,C}\setminus {l}}(N_c - \mathbb{I}(l < c))}{2} \right \rfloor $$

其中$\mathbb{I}(l < c)$用于打破投票时可能出现的平局，$M^p$是$M$的上界

证明：

由定义 $$ N_c = \sum^T_{k=1}\mathbb{I}(f(\mathcal{G}k) = c) $$ 以及对问题的分析显然得 $$ \sum^T{k=1}\mathbb{I}(f(\mathcal{G}_k) \ne f(\mathcal{G}k^p)) \le M $$ 可知 $$ \begin{aligned} N_c^p &= \sum^T{k=1}\mathbb{I}(f(\mathcal{G}k^p) = c) \ & \le \sum^T{k=1}\mathbb{I}(f(\mathcal{G}k) = c) + \sum^T{k=1}\mathbb{I}(f(\mathcal{G}_k) \ne f(\mathcal{G}k^p)) \ & \le \sum^T{k=1}\mathbb{I}(f(\mathcal{G}_k) = c) + M \ & \le N_c + M \end{aligned} $$

同理有 $$ N_c - M \le N_c^p $$

因为GNNCert只有当以下条件成立时才预测为标签$l$：

$$ N_l - M > \text{max}_{c \in {1,2,\ldots,C}\setminus {l}}(N_c - \mathbb{I}(l < c) + M) $$

也就是说

$$ M < \frac{N_l - \text{max}_{c \in {1,2,\ldots,C}\setminus {l}}(N_c - \mathbb{I}(l < c))}{2} $$

定理二

没有比$M^p$更tight的上界了

证明：

因为$M^p$是最大的整数使得 $$ N_l - M^p > \text{max}_{c \in {1,2,\ldots,C}\setminus {l}}(N_c - \mathbb{I}(l < c) + M^p) $$

因此，当不等式左边减小，右边增大时，不等式不成立，也就是说 $$ N_l - (M^p + 1) \le \text{max}_{c \in {1,2,\ldots,C}\setminus {l}}(N_c - \mathbb{I}(l < c) + (M^p + 1)) $$

实验

实验设置

使用的数据集

• DBLP
• DD
• ENZYMES
• MUTAG
• NCI1
• PROTEINS
• REDDIT-B
• COLLAB

基础图分类器：

• GIN
• GAT
• GCN

比较的防御方法（Related Work中提到的那些）：

• Bojchevski et al.
• Wang et al.
• Zhang et al.

参数设置：

• $T_s = 30$
• $T_f = 30$
• $\mathcal{H}(\cdot) = \text{MD5}(\cdot)$

计算成本比较

更快的原因：

1. 子图计算成本更低
2. 其他三种方法需要对一个图生成1000张测试图，但是本文方法只用生成30张子图

效果比较

哈希函数的影响

不同基础图分类器对比

对结构和特征同时扰动的攻击的效果

扫码阅读此文章
点击按钮复制分享信息