图机器学习（关于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在没有攻击情况下，分类结果非常不错，在受到间接攻击后的影响较小（对抗间接攻击鲁棒性较好），直接攻击后分类结果出现大量错误（对抗直接攻击鲁棒性较差）。
