【源头活水】图对抗攻击防御技术--RGCN，Pro-GNN，Vaccinated GCN

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

作者：知乎—xyz

地址：https://www.zhihu.com/people/xyz-92-84-9

在机器学习领域，早在2014年Ian Goodfellow提出的对抗生成网络中，对抗样本和对抗训练的概念第一次出现。早期的对抗训练方法主要被应用在图像，语音和文本等连续数据。因为数据的连续性，对抗的样本和噪音比较容易产生。

最近两年，随着深度学习的思想被应用到图数据中，并在节点分类、连接预测等问题上取得了很好的表现。GNNs模型也被广泛运用于金融、推荐、社交网络等领域。随之而来的，GNNs的鲁棒性面临着巨大的挑战，例如：金融系统中，黑客可以轻易通过修改图数据来提升自身信用评级等等。

因此，把对抗思想迁移到图数据来研究GNNs的鲁棒性也是一个自然的过程。自从KDD'18 best paper[1]开始，越来越多图对抗攻击的工作开始涌现，相应的图对抗攻击的防御工作也成为了近年来研究的热点问题。https://zhuanlan.zhihu.com/p/88934914在上一篇文章中， @Ron Chen 介绍了几种图对抗攻击方法，这些攻击方法表明GNNs（图神经网络）缺乏鲁棒性，易于收到攻击。为了提高GNNs的鲁棒性，下面本文将介绍三种图对抗攻击的防御技术：

1. Robust Graph Convolutional Networks Against Adversarial Attacks[2]

2. Graph Structure Learning for Robust Graph Neural Networks[3]

3. All You Need Is Low (Rank): Defending Against Adversarial Attacks on Graph[4]

01

RGCN

RGCN（Robust Graph Convolutional Network）是最早的有关于图数据集上对抗攻击防御的工作之一。本文对GCN作出的改进主要体现在以下两点：

• 基于高斯分布的图卷积层（Gaussian-based Graph Convolution Layer）

• 采用attention机制为聚合的邻居特征分配权重

RGCN模型结构如下所示：

在本文中，给定一张属性图  ，其中  为节点集合，  ，  是节点连边集合。  表示邻接矩阵，  为度矩阵（对角矩阵），  为节点特征矩阵。文中定义  作为节点在  层的隐藏特征表示，例如：  就是节点  在  隐藏层的特征表示。更进一步，我们定义  为  的向量维度。此外，  ，节点  的一阶邻居包括  本身的集合为  ，  为非线性激活函数。

基于高斯分布的图卷积层定义如下所示：

RGCN假定每个节点  在  层的特征  满足高斯分布，那么网络中  层的特征矩阵即可表示为均值矩阵  和方差矩阵  。

接下来在做邻居特征聚合时，需要用到以下定理：

简单来说，邻居特征聚合的本质就是对n个服从独立的高斯分布的变量做加权求和，而这个定理告诉我们：这些随机变量加权求和后的变量也服从高斯分布，  和  也与每个随机变量相关。然后将上式带入GCN的聚合过程中，我们得到RGCN的卷积定义：

此外，本文认为高斯分布的  越大，模型对该节点特征的不确定性越大，所以为此引入attention机制，即不确定性越大的节点，聚合时分配的权重越小。

其中，  是节点  在  层的聚合权重，  是个超参。将上式中的自适应权重带入GCN聚合公式中，我们得到最终RGCN层与层之间的递进公式：

但由于RGCN每个隐藏层中学到的节点表示是一个高斯分布，所以需要对最后一个隐藏层的分布进行采样：

将采样后的结果  送入softmax中进行分类，得到最后的预测结果。

02

Pro-GNN

在本文中，现实世界的图通常都具备一定的特性（例如，图是低秩或者是稀疏的，相邻节点往往有着相似的特征等等），而对抗攻击很可能会将这些特性破坏。所以，本文希望通过保持图上这些特性来对对抗攻击进行防御（本质是过滤图中的对抗攻击带来的noise）。

本文对全局攻击metattack[5]的特性进行了一定的探究，如Figure 1a-d所示。在Figure 1a中，metattack增大了邻接矩阵的奇异值；Figure 1b说明metattack快速增加了邻接矩阵的秩；在Figure 1c中，相比于正常边，移除对抗边会使得邻接矩阵的秩下降的更快；Figure 1d表明metattack更倾向连接两个特征差异较大的节点。

下面本文就针对对抗攻击的这些特性，提出了Pro-GNN来增强GNN模型的鲁棒性。具体来说， Pro-GNN是一种通用GNN框架，它能够从基于这些特性的扰动图中同时学到一个新的结构图和一个鲁棒的图神经网络。Pro-GNN的整体框架如下图所示：

Poisoned Graph中红色的边是对抗边，攻击者插入对抗边用于降低节点分类模型的表现。为了防御这种对抗攻击，Pro-GNN对Poisoned Graph进行重构来保持图数据上的低秩、稀疏以及属性特征的平滑性。

为了保持图低秩和稀疏的性质，本文给出了上述优化目标。  是原图的邻接矩阵，  是重构后的邻接矩阵，  的Frobenius范数定义为  ，  的  范数定义为  ，核范数定义为  ，其中  为  中 大的奇异值。优化目标中，第一项  用于保障  和  相差不大，而后面两个范数用于保持图低秩和稀疏性[6]， 和  为超参。

Pro-GNN通过下式来评估图中属性的平滑性：

其中  是节点  的属性，再使用Laplacian矩阵标准化后，我们得到：

结合低秩、稀疏和属性平滑的综合优化目标为：

其中，  和  为超参，  为GNN的损失函数。

Pro-GNN可以在几乎不损失原来分类准确率的前提下，增强模型的鲁棒性，实验结果如下表所示：

03

Vaccinated GCN

Vaccinated GCN的核心思路在于：本文作者发现Nettack[1]是一种高秩攻击，这是因为Nettack带来的对抗扰动只会影响图中少量的节点，攻击给图结构谱域带来的影响较小，故主要反映在rank较高的奇异值上。

文中的实验也验证了上述猜想。在上图中，clean graph和被Nettack攻击后的graph的奇异值区别主要集中在rank较高的奇异值上，而rank低的奇异值基本没有发生改变。基于这个观察，作者提出对图数据采用低秩近似（Low-Rank Approximation）来过滤图中的对抗攻击所带来的noise。

示意图很好懂，先通过SVD对邻接矩阵进行矩阵分解，然后低秩近似重构矩阵，得到Vaccinated Graph。但问题在于：给定一张图  ，如何去选择r-th的奇异值  ，使得在损失较少原图信息的前提下尽可能多的过滤noise呢？

其中  ，  是clean graph的邻接矩阵，  是attacked graph的邻接矩阵，上式是SVD分解后的形式。根据文章[7]的证明， 最大奇异值 为：

其中，  为Nettack对目标节点  的扰动次数，  为  的节点度数。这意味着，只要  小于  ，那么对抗攻击带来的noise就可以被低秩近似消除。简单化简后，我们得到：

换句话说， 最小奇异值为 的低秩近似可以保护所有度数满足上式的节点。下面给出问题的定义：

 是我们设定的概率阈值，即我们保障节点度数大于  的概率小于  。我们假定一张图的节点度分布满足幂律分布，那么图中度分布可以写成如下与参数  相关的形式：

其中，  为Hurwitz zeta函数。根据文章[8]，我们可以给出  在一张图  （离散幂律分布）的一个近似：

再将其带入到我们的问题定义中，我们得到图自适应的节点度数概率计算结果：

接下来，本文作者在GCN和t-PINE[9]两个模型上对Vaccinated Graph的鲁棒性进行了评估。实验结果表明：Vaccinated Graph对高秩攻击Nettack取得了不错的防御效果，但对低秩攻击的防御效果较差。其中，LowBlow是本文提出的一种低秩攻击，因为本次的主要内容为对抗攻击的防御工作，故在处不再赘述，感兴趣的读者可以自行阅读原文[4]。

实验结果如下所示：

04

总结

回顾这三篇工作，RGCN采用高斯分布来平滑节点特性表示，以期来吸收对抗攻击造成的noise，但在实验中的准确率提升并不明显且效率不高；而Pro-GNN和Vaccinated GCN，前者通过保持图数据的固有特性，而后者借助低秩近似，都抓住了对抗攻击的特点，进而有效的过滤图中的noise，达到防御对抗攻击的目的，增强了GNNs模型的鲁棒性。

参考

[1]abZügner D, Akbarnejad A, Günnemann S. Adversarial attacks on neural networks for graph data[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 2847-2856.

[2]Zhu D, Zhang Z, Cui P, et al. Robust graph convolutional networks against adversarial attacks[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019: 1399-1407.

[3]Jin W, Ma Y, Liu X, et al. Graph structure learning for robust graph neural networks[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020: 66-74.

[4]abEntezari N, Al-Sayouri S A, Darvishzadeh A, et al. All you need is low (rank) defending against adversarial attacks on graphs[C]//Proceedings of the 13th International Conference on Web Search and Data Mining. 2020: 169-177.

[5]Zügner D, Günnemann S. Adversarial attacks on graph neural networks via meta learning[J]. arXiv preprint arXiv:1902.08412, 2019.

[6]Richard E, Savalle P A, Vayatis N. Estimation of simultaneously sparse and low rank matrices[J]. arXiv preprint arXiv:1206.6474, 2012.

[7]Shah N, Beutel A, Gallagher B, et al. Spotting suspicious link behavior with fbox: An adversarial perspective[C]//2014 IEEE International Conference on Data Mining. IEEE, 2014: 959-964.

[8]Clauset A, Shalizi C R, Newman M E J. Power-law distributions in empirical data[J]. SIAM review, 2009, 51(4): 661-703.

[9]Al-Sayouri S, Gujral E, Koutra D, et al. t-pine: Tensor-based predictable and interpretable node embeddings[J]. Social Network Analysis and Mining, 2020, 10(1): 1-11.

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“源头活水”历史文章

更多源头活水专栏文章，

请点击文章底部“阅读原文”查看

分享、在看，给个三连击呗！