AAAI 2020 开源论文 | 一种针对图嵌入模型的受限黑盒对抗攻击框架

AAAI（人工智能促进协会年会）是人工智能领域的顶级国际会议之一。今年的 AAAI 2020 是第 34 届，于 2 月 7 日至 12 日在美国纽约举行。今年，第 3 次参会的腾讯 AI Lab 共有 31 篇论文入选，涵盖自然语言处理、计算机视觉、机器学习、机器人等领域。

今天我们要解读的入选论文是：A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models。这篇论文由腾讯 AI Lab 与清华大学合作完成。文章提出了一种在受限黑盒攻击情形下，针对多种图嵌入模型进行统一对抗攻击的框架。该方法从图信号处理的角度出发，建立了不同图嵌入模型之间的理论联系，进而可以更有效地对图嵌入模型进行攻击。

论文链接：https://arxiv.org/abs/1908.01297

源码链接：https://github.com/SwiftieH/GFAttack

近年来，不管是在学术圈还是工业界，图嵌入模型都取得了很大的成功，但与此同时图嵌入模型对于对抗扰动的鲁棒性也随之引起了人们的关注。在图模型上进行对抗扰动从去年开始成为了一个热点方向。具体而言，对于一个节点，攻击者有策略地将其连接到图中的其他节点，目标是降低这个节点被图模型正确分类的概率。

现有的对于图嵌入模型的对抗攻击方法大部分都局限于白盒攻击的情形下，即假设攻击者可以基于目标的模型参数、模型预测结果或者数据标签等额外数据对模型进行攻击。这些信息往往在现实条件下难以获得，就是说白盒攻击对真实模型的威胁其实是非常有限的。 

本文研究了更有威胁而且挑战性的攻击设置：黑盒攻击，即如何在不知道模型信息和数据标签的情况下对图表示学习模型进行攻击。为此，作者从原理上研究了图信号处理和图表示学习模型之间的理论联系，然后将图嵌入模型建模成不同图滤波器的图信号处理过程并且构造了一个通用黑盒攻击框架：GF-Attack。

GF-Attack 由图邻接矩阵和特征矩阵作为输入，其不会访问图表示学习模型中的目标分类器的任何知识，而仅以黑盒攻击方式对图滤波这一过程进行攻击。以下是 GF-Attack 的具体攻击流程。

论文方法

我们定义在图嵌入模型上进行对抗攻击的核心任务是破坏模型输出的图嵌入向量的质量，从而降低利用图嵌入进行的下游任务的性能。在给定攻击者可以修改的边数限制 β 的情况下，对于图嵌入模型的对抗扰动可以被看做如下的优化问题：

其中，A 和 X 分别是图中的邻接矩阵，Z 是图嵌入模型   的输出，L(∙,∙) 是参数为 θ 的损失函数，L(A',Z) 是用来衡量对输出图嵌入向量破坏程度的损失函数，越低的损失函数值对应越高的图嵌入向量的质量。

和离散信号处理相似，图信号处理可以将图上的信号定义为一个从节点映射到特征的映射。从这一点出发，作者把图嵌入模型统一地看作是利用图滤波器和特征变化产生新的图信号的过程：

其中，H 是图信号滤波器，通常可以构建为一个关于图平移滤波器 S 的多项式函数 H=h(S)。图平移滤波器 S 反映了图的一些局部特性，如表征一个节点上信号及其邻近节点的线性变换，因而 S 的一些通常选择包括邻接矩阵 A 或者拉普拉斯矩阵 L=D-A 等。σ(.) 是激活函数。

基于 (2)，作者将图嵌入模型建模为一种特殊的图信号处理的过程，进而提出了基于图信号处理的攻击框架 GF-Attack。在黑盒攻击场景下（避免使用目标模型的参数或者数据标签），作者将攻击的目标设定为攻击图信号滤波器 H。

在攻击过程中，目标是尽可能地破坏输出嵌入向量的质量。作者将这一个问题定义为一个 T-rank 近似问题，用以衡量输出嵌入向量的质量：

其中   是图信号滤波器 h(S') 的 T-rank 近似。更进一步，作者可以将这个问题转化为最大化式子 (3) 的上界，从而将对图嵌入模型的统计攻击转化为如下的优化问题：

其中，  与   分别是图信号滤波器 h(S) 的一对特征值和特征向量。为了避免每次利用特征值展开来计算   带来的计算复杂度，作者进一步利用特征值扰动理论从 估计  ，使得框架的实用性得以提高。

有了统一的优化问题之后，作者分别以图卷积网络（如 GCN，式子 (8)）和基于采样的图嵌入模型（如 DeepWalk，式子 (12)）所使用的图信号滤波器为例，构造了两个可以用来对图嵌入模型进行攻击的实例，分别如下：

这样对于任何给定的图嵌入模型，在受限黑盒条件下，攻击者不需要知道具体的模型参数和预测输出就可以选择使用式子 (8) 或者式子 (12) 来生成对抗扰动的边样本，然后将扰动样本输入到目标模型中完成攻击。具体的算法如下所示：

实验

为了验证 GF-Attack 框架的有效性，作者实验了将 GF-Attack 产生的对抗样本分别用于攻击四种主流的图嵌入模型。为了增加实验中任务的难度，作者限制了可修改边数 β=1，其结果如下表 1 所示：

▲ 表1. 相比于未被攻击的原始图的分类准确度变化情况总结。RBA 设置下的单边扰动设置。结果越低越好

从表中可以观察到，相比于之前的基于强化学习的攻击方法，GF-Attack 对目标模型能够实施更有效的攻击。 

此外，作者还进行了运算时间比较、可以修改多条边等实验，其实验结果分别如下所示：

▲ 表2. 在 Citeseer 上所有基准方法的运行时间比较。这里报告的结果是每个模型处理单个节点的 10 次重复实验的平均运行时间

▲ 图3. RBA 设置下，在 Cora 上的多边攻击结果。越低越好

从以上的结果中可以发现，GF-Attack 在生成多条边的对抗扰动下依然有十分好的效果，同时在运行时间上相对其他的攻击方法也有所减少，进一步验证了 GF-Attack 框架的时间效率和有效性。

这篇文章作为早期对于图嵌入模型的对抗攻击和鲁棒性学习的研究，同时将图信号处理和图嵌入模型在理论上进行了联系，对于这一研究方向的进一步发展具有重要的意义。

点击以下标题查看更多往期内容： 

• 这10篇硬核论文，让你更了解图神经网络
  

• AAAI 2020 开源论文 | 多成分图卷积协同过滤
  

• ICLR 2020 | 隐空间的图神经网络：Geom-GCN
  

• KDD 2019 | 基于异质图神经网络的用户意图推荐
  

• 异质图神经网络领域有哪些值得读的顶会论文？
  

• NeurIPS 2019 开源论文 | 万能的GNN解释器
  

#投 稿 通 道#

 让你的论文被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。

📝 来稿标准：

• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向） 

• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志

📬 投稿邮箱：

• 投稿邮箱：hr@paperweekly.site 

• 所有文章配图，请单独在附件中发送 

• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

关于PaperWeekly

PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。

▽ 点击 | 阅读原文 | 下载论文 & 源码