图机器学习(关于GNN的局限性以及其解决办法)
1.前言
1. 图神经网络局限性一
两个节点有相同邻居或邻域结构,按理其表征应该相同:
但是实际上不一定,因为有些邻域相同但是表征不应该相同,特别是对称图结构,例如:
可以看到NY的街道非常规整,因此也和上面的网格图类似。这类任务叫:位置感知任务(position aware task)
2. 图神经网络局限性二
两个节点不同相同邻居或邻域结构,按理其表征应该不相同:
GNN的上限是WL test,因此普通GNN无法很好表达环状图形长度:
3. 解决办法参考
对于问题1:根据节点嵌入在图形中的位置创建节点嵌入。
方法:位置感知GNN(Position-aware GNNs)
对于问题2:构建比 WL 测试更具表现力的消息传递 GNN。
方法:身份感知GNN(Identity-aware GNNs)
大概思路:
两个不同的输入,节点、边、图都标记得不一样。希望得到一个模型,获得不同的表征,例如:
两个输入:节点 v 1 和 v 2 v_1和v_2 v1和v2
不同的标签:A和B
目标:为节点 v 1 和 v 2 v_1和v_2 v1和v2分配不同的向量嵌入
4. 错误思路
非常直接办法就是将每个节点赋予不同的独热编码:
得到的计算图当然也不一样,我们也会得到不同的表征:
但是这个方法行不通,因为:
1.可扩展性差,每个节点需要O(N)维度来作为表征,N是节点数量,大型图适用这样处理,因为最终要把高维向量映射到低维空间里。
2.没进行归纳,因此新点加入全部要重新计算一遍。
2. Position-aware GNNs
图上有两种任务:一种是structure-aware task(节点因在图上的结构不同而有不同的标签),一种是position-aware task(节点因在图上的位置不同而有不同的标签)。真实任务往往结合了structure-aware和position-aware,所以我们需要能够同时解决这两种任务的方法。
1. Structure-aware task
节点按他们的结构进行标签,例如两边的B都有两个A做邻居。
我们常见的GNN对于structure-aware task都适用,包括:GCN,GraphSage,GAT等。因为A和B的计算图明显不一样
2. Position-aware task
节点按他们的位置进行标签,常见的有社区检测任务,上图左右两边是不同两个社区,因此他们各自标记也不一样。
普通GNN是无法区分这样的节点,因为上图中的A和B有相同的计算图(不考虑额外特征的情况下,GNN无法区分两个点的表征):
3. 解决办法:锚点(anchor)
就好比要比较两个物体的大小,必须要有参照物一样的原理,锚点就是这里的参照物。随机选择一个节点 s 1 s_1 s1作为锚点,通过两个节点 v 1 , v 2 v_1,v_2 v1,v2相对锚点 s 1 s_1 s1的位置不同来解决Position-aware task,例如:
当然如果不止选定一个锚点,那么结果会更加鲁棒,相当于从不同坐标系(角度)来看节点位置:
4. 锚点集
下面给出具体的Position-aware task解决方案描述:、
把节点到锚点的距离可以表示为到某个锚点集的距离,例如:下图中的锚点集 s 3 = { s 1 , v 3 } , s i z e = 2 s_3=\{s_1,v_3\},size=2 s3={s1,v3},size=2
锚点集可使用更少的点,提供更精确的位置估计。而且位置信息表征可以用距离来表示:
PS:锚点集尺寸大小选择通常是1.2.4.16这样指数增长的,然后组合起来,具体选择估计要实验,节点是随机选的(但是应该是相邻的)。
5. 位置信息处理
通过上面的方法我们了解了如何通过锚点集来获得节点的位置表征,这样做在实际效果上没有什么大问题,但是由于锚点集的变化,会引起节点的位置表征在维度,顺序上的变化,这个缺点会导致位置表征与NN不匹配的情况出现,例如,你训练好了一个处理100维输入的NN,然后锚点集变化,位置表征变成80维,NN就废了。
更加优化的解决方案是将通过锚点集得到的位置表征重新处理一下,例如经过一些aggregation处理,使得位置表征的维度固定,顺序无关
3. Identity-aware GNNs
这个主要是针对前面提到的structure-aware tasks的,虽然说传统GNN在这个任务上比较擅长,但是还有特殊的情况无法处理,共有三种情况:
1. Failure in three level
1. Node level failure
2. Edge level failure
3. Graph level failure
2. 解决思路
将要表征的节点上色后展开为计算图:
对于节点级别,可以帮助node classification
边级别可以帮助link prediction
图级别可以帮助graph classification
3. Identity-aware GNN
在表征计算过程中利用节点上色来鉴别不同节点。主要思想是:异质消息传递。
正常的GNN会使用相同的消息聚合函数:
ID-GNN使用不同的消息聚合函数,不同函数代表不同颜色。
看下原理,假定两个节点有相同计算图,并有颜色标识(也不能说不同颜色,不同颜色就变成独热编码了,就是加上了标记即可),用了不同的消息聚合函数后,会得到不同的表征:
可以看出ID-GNN可以识别出环形图周期,而GNN不行
4. ID-GNN-Fast
改进在不需要额外使用异质消息聚合函数,直接使用每一层计算图中目标节点出现的次数作为identity表征:
例如红色的 v 1 v_1 v1 节点的identity information就是第一层出现1次,第二层出现0次,以此类推。把这个identity information可以做为节点的augmented feature,这样就可以用在各种不同的GNN模型(GCN, GraphSAGE, GIN)中了。
5.小结
ID-GNN是第一个基于消息传递机制,并且表达能力比1-WL test还牛的模型,而且还可以用于现有的模型。
DGL和PyG已经有ID-GNN的实现了。
4.GNN的鲁棒性
这个在图像上已经有过类似的案例:
在NLP和声音处理领域也有类似案例。
从本质上看,是模型预测出错了,鲁棒性不好。对于GNN而言,也存在类似问题,常见的对抗攻击出现在:推荐系统、
社交网络、搜索引擎
1. GNN对抗攻击类型
分直接攻击和间接攻击。先给出简单定义:
目标节点: t ∈ V t\in V t∈V,攻击者想要修改标签的节点。
攻击节点(可有多个): S ⊂ V S\subset V S⊂V,攻击者能修改的节点
1.直接攻击
攻击节点就是目标节点: S = { t } S=\{t\} S={t}
修改目标节点特征:
2.1为目标节点添加连接。例如:买粉丝
2.2为目标节点去掉连接。例如:掉粉
2. 简介攻击
目标节点不在攻击节点中: t ∉ S t\notin S t∈/S
修改攻击节点特征,例如劫持目标节点的邻居 1.为攻击节点添加与目标节点的连接。 2.去掉攻击节点不相关的边。
5. GNN对抗攻击
1.总览
改动越大,越容易被发现,成功的攻击往往是比较隐蔽的攻击。
2. 数学表达
以GCN的节点分类任务为例。
原始图的邻接矩阵为A,特征矩阵为X;攻击后的邻接矩阵为A’ ,特征矩阵为 X’ 。
假定: ( A , X ) ≈ ( A ′ , X ′ ) (A,X)\approx(A',X') (A,X)≈(A′,X′)(也就是攻击后图的改动非常小,并不影响原有图的统计属性,例如:度分布,特征统计等。)记目标节点为: v ∈ V v\in V v∈V
GCN对于原图的目标函数为:
θ ∗ = a r g m i n θ L t r a i n ( θ ; A , X ) \theta^*=argmin_\theta\mathcal{L}_{train}(\theta;A,X) θ∗=argminθLtrain(θ;A,X)
这里的训练过程设置的参数 θ \theta θ是攻击者无法改变的,模型训练好后进行部署,其神经网络参数不可改变,我们攻击者只能改变输入的图结构。
GCN对于攻击前目标节点 v v v的原始预测分类结果为:
c v ∗ = a r g m a x c f θ ∗ ( A , X ) v , c c_v^*=argmax_cf_{\theta^*}(A,X)_{v,c} cv∗=argmaxcfθ∗(A,X)v,c
这里的 c v ∗ c_v^* cv∗是攻击目标节点 v v v的预测分类对应的最大概率(softmax的结果中的最大值)。
GCN对于被篡改后图的目标函数为:
θ ∗ ′ = a r g m i n θ L t r a i n ( θ ; A ′ , X ′ ) \theta^{*'}=argmin_\theta\mathcal{L}_{train}(\theta;A',X') θ∗′=argminθLtrain(θ;A′,X′)
GCN对于攻击后目标节点v的攻击预测分类结果为:
c v ∗ ′ = a r g m a x c f θ ∗ ( A ′ , X ′ ) v , c c_v^{*'}=argmax_cf_{\theta^*}(A',X')_{v,c} cv∗′=argmaxcfθ∗(A′,X′)v,c
我们希望经过攻击后的分类概率与之前的概率有所不一样: c v ∗ ′ ≠ c v ∗ c_v^{*'}\not=c_v^* cv∗′=cv∗
把他们两者之间的差别记为 Δ ( v ; A ′ , X ′ ) \Delta(v;A',X') Δ(v;A′,X′),我们当然希望这个差别越大越好,为了放大小小的概率,我们对其取对数,求最大值的特性保持不变: Δ ( v ; A ′ , X ′ ) = log f θ ∗ ′ ( A ′ , X ′ ) v , c v ∗ ′ − log f θ ∗ ′ ( A ′ , X ′ ) v , c v ∗ \Delta(v;A',X')=\log f_{\theta^{*}{'}}(A',X')_{v,c_v^{*}{'}}-\log f_{\theta^{*}{'}}(A',X')_{v,c_v^{*}} Δ(v;A′,X′)=logfθ∗′(A′,X′)v,cv∗′−logfθ∗′(A′,X′)v,cv∗
第一项是攻击后得到某个新分类的概率的log值;(希望其增加)
第二项是攻击前得到某个原分类的概率的log值。(希望其减少)
面临的问题:
1.邻接矩阵 A ′ A' A′ 是离散对象,无法使用基于梯度的优化方法;
2.对于攻击者修改过的图数据: A ′ , X ′ A',X' A′,X′ ,GCN需要重新训练得到最优参数,比较耗时.
6.GCN对抗攻击实验
对一个2800节点,8000边的引文网络进行GCN的半监督节点分类任务:
其中某个节点五次预测结果都是正确
对目标节点进行修改(5条边)后,相当于进行直接攻击的结果:
最后对不同节点进行可视化:
这个图表明GCN在没有攻击情况下,分类结果非常不错,在受到间接攻击后的影响较小(对抗间接攻击鲁棒性较好),直接攻击后分类结果出现大量错误(对抗直接攻击鲁棒性较差)。