从多篇顶会论文看图神经网络黑盒攻击近期进展

2022 年 10 月 19 日 PaperWeekly


©作者 | 于越

单位 | 北邮 GAMMA Lab

研究方向 | 图神经网络


本文旨在简要总结近期的图对抗攻击中的黑盒攻击方法,带领读者了解图黑盒攻击的基本定义和最新进展。




简介

图神经网络(GNN)广泛应用于图数据挖掘,例如社交网络、电商数据、金融数据等等。常见的图神经网络有 GCN、GAT、APPNP 等。然而,现有的 GNN 易受到对抗攻击的影响,导致性能的大幅下降。对抗攻击是指攻击者通过修改少量数据的方式使神经网络性能明显下降。而人类通常不会被这类扰动所影响,因为人类的判断是比较鲁棒的。因此,对抗攻击及防御是如今可信 AI 的研究热门。图对抗攻击中,攻击者通过修改节点属性或拓扑结构来使图模型的性能下降。d 对于最常见的拓扑攻击,形式化表述为


其中 为攻击损失函数, 是参数为 的 GNN, 为图的邻接矩阵, 为扰动后的邻接矩阵, 为特征矩阵, 为扰动代价(budget),含义是扰动边数量的最大值。图攻击也可以看作一种基于目标函数的优化过程。

对抗攻击有多种设定,如下图所示。白盒攻击中,攻击者可以获取输入数据,模型预测(最终预测的置信度向量)和模型的结构信息,并且可以获取反向传播的梯度信息;黑盒攻击中,攻击者只能获取输入数据和预测结果,根据预测结果是置信度还是 one-hot 向量又分为软标签和硬标签攻击。图黑盒攻击中,攻击者可以获取 以及预测矩阵 。黑盒攻击由于其设定更接近实际场景,因此近期受到的关注逐渐增多。





方法介绍

2.1 Towards More Practical Adversarial Attacks on Graph Neural Networks (NeurIPS 2020)

原文:https://arxiv.org/abs/2006.05057


本文在黑盒的基础上采取了更加现实的设定:攻击节点的度和数量都有所限制(对于社交网络,不能攻击名人节点),而且无法获取模型预测。本文主要关注攻击节点的选取。白盒攻击常采取的目标函数 Carlini-Wagner Loss 为



其中 为最后一层节点表示,即预测矩阵。该损失函数含义为,每个节点预测的最大置信度与真实标签对应的置信度之差的和。损失函数越大,说明模型的预测中,错误结果与真实结果相去甚远,因此攻击效果越好。作者证明了使用该损失函数时,某个节点的扰动带来的损失函数变化的一阶近似期望与图随机游走矩阵该列之和相关。因此,可以选取随机游走矩阵列求和最大的几个节点进行攻击,即 RWCS 方法。

实验结果表明,随着扰动强度的增加,损失函数线性增大,但是分类正确率在扰动强度达到一定值之后不再减小。这说明 Loss 和 ACC 之间存在不匹配的关系。这种不匹配关系暗示了攻击的冗余特性。



因此,本文提出了修正的方法 GC-RWCS



其中 为二值化的随机游走矩阵



为评分函数, ,对 的列求和。这个算法做了如下几个改进:第 6 行每次迭代去掉选中节点 跳邻居,因为攻击具有同配性(邻居节点对攻击的贡献与节点本身类似);第 7 至 10 行,更新某些特定行的值,因为 代表攻击 很可能会让 分类错误,因此更新 矩阵第 行为 0,让不再对攻击节点选取有贡献。


2.2 A Hard Label Black-box Adversarial Attack Against Graph Neural Networks (CCS 2021)


原文: http://arxiv.org/abs/2108.09513

本文是硬标签的设定,即攻击者只知道模型预测的 one-hot 结果而非置信度。并且,作者发现图攻击的复杂度会随着节点数量的增加而指数级增加,因此首先将邻接矩阵连续化(这也是很多基于优化的图攻击的做法)。



其中 为扰动函数, 为扰动矩阵。由于本文是图分类攻击模型,因此优化问题可以表示为



定义图结构 沿着扰动 到分类边界的距离为 ,因此我们需要的最小的扰动的个数为


我们的目标就是选取让 最小的 ,为了优化,实际中使用1范数替代0范数。算法如下



其中梯度的估计方式如下



同时,本文提出了粗粒度到细粒度的扰动搜索策略,将图根据聚类结果抽象为超点和超边,按照超点-超边-全图的顺序搜索扰动,能够提高效率。



2.3 Graph Structural Attack by Perturbing Spectral Distance (KDD 2022)


原文: https://dl.acm.org/doi/10.1145/3534678.3539435

作者发现,图结构与图的谱域信息存在关联。作者分别使用低频信息和高频信息重构了图结构,可以发现,低频信息对应的是社群内部的信息,高频信息对应的是社群之间的信息。



因此,作者认为在谱域对图进行攻击是更有效率的。具体算法如下



作者认为,频谱的距离,即特征值之差的 2 范数代表了攻击的效果,因此 Loss 如第 8 行所示。为了减少特征值分解的开销,每 m 步中,有 m-1 步使用近似算法,即第 10 行。



总结


黑盒攻击 具体的定义并不完全明确,而且具体问题的设置又有一些细微差别。 因此,研究黑盒攻击首先需要定义问题。 根据问题定义,就会导出这个设置下解决问题的关键。 黑盒攻击无法获取模型梯度,因此定义损失函数和梯度估计方法是两个比较重要、需要考虑的点。


更多阅读



#投 稿 通 道#

 让你的文字被更多人看到 



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


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


PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学术热点剖析科研心得竞赛经验讲解等。我们的目的只有一个,让知识真正流动起来。


📝 稿件基本要求:

• 文章确系个人原创作品,未曾在公开渠道发表,如为其他平台已发表或待发表的文章,请明确标注 

• 稿件建议以 markdown 格式撰写,文中配图以附件形式发送,要求图片清晰,无版权问题

• PaperWeekly 尊重原作者署名权,并将为每篇被采纳的原创首发稿件,提供业内具有竞争力稿酬,具体依据文章阅读量和文章质量阶梯制结算


📬 投稿通道:

• 投稿邮箱:hr@paperweekly.site 

• 来稿请备注即时联系方式(微信),以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信(pwbot02)快速投稿,备注:姓名-投稿


△长按添加PaperWeekly小编




🔍


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

进入知乎首页搜索「PaperWeekly」

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


·
·

登录查看更多
0

相关内容

「图神经网络复杂图挖掘」 的研究进展
专知会员服务
74+阅读 · 2022年10月23日
图神经网络黑盒攻击近期进展
专知会员服务
18+阅读 · 2022年10月14日
AAAI 2022|对抗攻击鲁棒的异质图神经网络
专知会员服务
35+阅读 · 2022年3月28日
专知会员服务
19+阅读 · 2021年3月28日
专知会员服务
64+阅读 · 2021年2月21日
近期必读的12篇KDD 2019【图神经网络(GNN)】相关论文
专知会员服务
62+阅读 · 2020年1月10日
图神经网络黑盒攻击近期进展
专知
0+阅读 · 2022年10月14日
一文梳理基于梯度的黑盒迁移对抗攻击研究进展
AAAI 2022 | 对抗攻击鲁棒的异质图神经网络
PaperWeekly
1+阅读 · 2022年8月16日
AAAI 2022|对抗攻击鲁棒的异质图神经网络
专知
3+阅读 · 2022年3月29日
因果推荐系统近期进展
图与推荐
4+阅读 · 2021年12月9日
图神经网络+推荐系统的最新进展
图与推荐
1+阅读 · 2021年11月2日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
6+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
37+阅读 · 2021年2月10日
Identity-aware Graph Neural Networks
Arxiv
14+阅读 · 2021年1月25日
Arxiv
13+阅读 · 2019年11月14日
Arxiv
23+阅读 · 2018年10月1日
VIP会员
相关VIP内容
「图神经网络复杂图挖掘」 的研究进展
专知会员服务
74+阅读 · 2022年10月23日
图神经网络黑盒攻击近期进展
专知会员服务
18+阅读 · 2022年10月14日
AAAI 2022|对抗攻击鲁棒的异质图神经网络
专知会员服务
35+阅读 · 2022年3月28日
专知会员服务
19+阅读 · 2021年3月28日
专知会员服务
64+阅读 · 2021年2月21日
近期必读的12篇KDD 2019【图神经网络(GNN)】相关论文
专知会员服务
62+阅读 · 2020年1月10日
相关资讯
相关基金
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
6+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员