ICLR2019 图上的对抗攻击

2020 年 3 月 15 日 图与推荐

本文是一篇图上对抗攻击的实操论文.来自图对抗攻击大佬Stephan.

作者: 雪的味道(清华大学)

编辑: Houye

Graph Adversarial Attacks的一个里程碑,作者也是Nettack的作者,Nettack是kdd 2018获得了best paper。

图对抗攻击基础

见上一篇文章:「弱不禁风」的图神经网络

Abstract

本文核心是用meta-gradients去解决bilevel问题(投毒攻击需要在修改后的图上重训练,依然在测试集上结果下降,所以是一个bilevel的问题)。本文通过微小扰动,使得分类准确率比baseline降低很多,并且能够泛化到无监督的表示学习中。

Introduction

之前的工作基本是Targeted攻击,对指定点进行攻击使其误分类。比如:社交网络中某个人。这本文的工作中,首次提出一个降低模型的全局分类性能的算法。本质上,作者是把基于梯度的深度学习模型优化过程颠倒过来,把输入数据(图)当作一个超参数来学习。

Problem Formulation

GCN的学习过程可以用如下形式表达:

其中  是我们需要学习的参数,  是GCN模型。

Overall Goal

投毒攻击可以被表示为: 

在全局攻击场景,攻击者试图降低模型泛化能力,降低在未标注的节点的上表现。

由于测试集节点的label未知,所以没有办法直接优化这个loss,所以作者提出了两种解决方案。一种是以降低训练集的loss为目标,此时  ,这种方式是假设训练集loss提高,那么测试集也跟着降低。实际这种方法并不合理,因为训练loss低可能是过拟合,提高训练loss未必会降低他的泛化能力,也可能刚好相反。另一种是用字学习的方式,先用gcn学习出test的结果,作为标签,然后此时可以  .

值得注意的是,如上的目标函数,是一个bilevel问题,而且更糟糕的是,图结构的邻接矩阵,每个元素只能是0或者1,所以这也是一个离散优化的问题。

Graph Structure Poisoning via Meta-Learning

Poisoning via Meta-Gradients

为了解决bilevel问题,本文采用meta-gradients的方法(这是在meta-learning领域常用的方法)。

Meta-gradients(比如每个超参数的梯度)是通过一个可微的模型(比如神经网络)反向传播得到的。本文的对抗攻击的核心idea就是把图结构的邻接矩阵当成超参数。在训练后,攻击者loss的梯度如下: 

其中  操作是一个可微的优化操作。这个meta-gradients正式代表了攻击者的loss  在数据进行微小扰动后的训练后的改变程度,这正是投毒攻击者所需要了解的。

考虑我们设置优化函数  为原始的梯度下降,学习率为  ,可以写成如下形式: 


攻击者的loss在T次更新后为  ,则meta-gradient可以展开表示为如下形式: 

这个公式是一个复合函数求导,然后由于  是关于  的函数,所以是一个多元函数求导,其中  关于  的梯度可以分解迭代反推至初始化的参数  。我们定义用meta-gradients更新  去使  最小化的操作为  : 

其中  为每次更新的步长大小。

但是值得注意的是,这里并没有解决图数据的离散性质,对于一个离散数据,梯度是不存在的,所以这里首先放款离散的条件,当成连续处理。但是在更新时,每次依然是离散的更新,下一节,提出一种贪心的方式保持数据的离散和稀疏性质。

Greedy Poisoning Attacks Via Meta Gradinets

作者使用SGC作为代理模型(GCN之类的也行,SGC与GCN的差别在于没有中间的非线性,实际实验表现与GCN不相伯仲,但是由于没有非线性,速度快了非常的多)。形式如下: 

接着这一段符号太多,我还是截图上原文吧。 

大概意思就是搞个评分矩阵  ,这玩意是邻接觉真的梯度的一个变型,这样这个值就可以直接对应于是否加边减边的score,这样我们就能选一个梯度最大的作为需要改变的边。

Experiments

Impact of graph structure and trained weights

作者实验发现,如果使用干净图训练得到的参数,那么即使在被攻击的图上测试,效果仅仅略有下降。而用被攻击的图训练的参数,即使在干净图上做预测,结果依然大幅度下降。

Analysis of attacks


这一模块是分析为啥攻击有效。直接放结论,大概就是节点对间最短路径变长一些,不确定性增加,度分布更偏低(这里很疑惑,原本我认为是应该度分布变高,不知道是我理解错了还是作者画反了),但是整体分布与原图大体保持一致。图上大部分是加边,少部分删边,加边大部分两个节点是不同的label,而删除的大多数是相同label。

Limited knowledge about graph struceture


inductive learning的场景,metalearning依然有效。


登录查看更多
17

相关内容

近期必读的12篇KDD 2019【图神经网络(GNN)】相关论文
专知会员服务
62+阅读 · 2020年1月10日
近期必读的5篇 WSDM 2020【图神经网络(GNN)】相关论文
专知会员服务
56+阅读 · 2020年1月10日
IJCAI 2019 提前看 | 神经网络后门攻击、对抗攻击
【学界】虚拟对抗训练:一种新颖的半监督学习正则化方法
GAN生成式对抗网络
10+阅读 · 2019年6月9日
ICLR2019最佳论文出炉
专知
11+阅读 · 2019年5月6日
AI新方向:对抗攻击
网易智能菌
10+阅读 · 2018年11月14日
论文浅尝 | 用图网络做小样本学习
开放知识图谱
65+阅读 · 2018年6月30日
【学界】继图像识别后,图像标注系统也被对抗样本攻陷!
GAN生成式对抗网络
6+阅读 · 2017年12月11日
ICLR 2018十佳论文
论智
5+阅读 · 2017年12月4日
Deflecting Adversarial Attacks
Arxiv
8+阅读 · 2020年2月18日
Meta-Learning with Implicit Gradients
Arxiv
13+阅读 · 2019年9月10日
Arxiv
4+阅读 · 2018年9月25日
Video-to-Video Synthesis
Arxiv
9+阅读 · 2018年8月20日
Meta-Learning with Latent Embedding Optimization
Arxiv
6+阅读 · 2018年7月16日
Adversarial Reprogramming of Neural Networks
Arxiv
3+阅读 · 2018年6月28日
VIP会员
相关资讯
IJCAI 2019 提前看 | 神经网络后门攻击、对抗攻击
【学界】虚拟对抗训练:一种新颖的半监督学习正则化方法
GAN生成式对抗网络
10+阅读 · 2019年6月9日
ICLR2019最佳论文出炉
专知
11+阅读 · 2019年5月6日
AI新方向:对抗攻击
网易智能菌
10+阅读 · 2018年11月14日
论文浅尝 | 用图网络做小样本学习
开放知识图谱
65+阅读 · 2018年6月30日
【学界】继图像识别后,图像标注系统也被对抗样本攻陷!
GAN生成式对抗网络
6+阅读 · 2017年12月11日
ICLR 2018十佳论文
论智
5+阅读 · 2017年12月4日
相关论文
Deflecting Adversarial Attacks
Arxiv
8+阅读 · 2020年2月18日
Meta-Learning with Implicit Gradients
Arxiv
13+阅读 · 2019年9月10日
Arxiv
4+阅读 · 2018年9月25日
Video-to-Video Synthesis
Arxiv
9+阅读 · 2018年8月20日
Meta-Learning with Latent Embedding Optimization
Arxiv
6+阅读 · 2018年7月16日
Adversarial Reprogramming of Neural Networks
Arxiv
3+阅读 · 2018年6月28日
Top
微信扫码咨询专知VIP会员