cs224w课程学习笔记-第5课

一、GNN 层介绍

1. 核心原理

GNN的单层核心的部分为两个,一个是消息传递(message),二是消息的聚合(aggregation),聚合后应用非线性激活增加表达能力,常用的激活函数如relu,softmax,Parametric ReLU(不再展开说明都是深度学习中的常见激活函数),其表示为公式的形式如下图所示,其中消息传递步骤中增加了自身信息的传递$m_v$.

2.变种(GCN,GAT,GraphSAGE)

2.1 GCN层

我们回忆一下上一节课的表达形式与上面提到的消息传递与聚合的表达方式有所不同,但本质上一样的,如下图GCN的表达形式,其中加和前的部分就是消息传递部分,加和是消息聚合阶段,最后的$\sigma$是激活函数.

2.2 GraphSAGE层

我们可以发现GCN中没有考虑自身消息的传递,在GraphSAGE中加入了自身的信息,其表达如下,可以看到它多了一步聚合,先将近邻的聚合后再跟自身消息聚合,最后应用激活函数,

这里面的AGG有多种实现:

1. 最简单的就是近邻消息加起来,使用节点度$|N(v)|$进行标准化;
2. 其次可以使用池化聚合（Pooling Aggregator）:可以更灵活地学习邻居节点特征的重要性。常见的池化策略是 最大池化（max pooling） 或 平均池化（average pooling,如下图所示）.采用池化时,对节点的每个邻居N(v)，通过一个可学习的多层感知机（MLP）把原特征映射成一个新的特征表示。然后对所有邻居节点的特征进行池化操作，比如取最大值或平均值。
3. LSTM 聚合方式将节点的邻居看作一个序列，通过 LSTM（长短时记忆网络）模型以序列方式处理邻居的特征，实现信息的聚合。这依赖于 LSTM 的能力来捕捉邻居节点特征之间的关系，同时学习更复杂的上下文依赖。

其总结如下表所示

通常每层输出后会再加一个归一化的操作,其作用是统一尺寸,让网络更加稳定,效果更好,常用L2范式进行归一化.

2.3 GAT层

我们看到GCN与GraphSAGE 都是近邻节点信息传递过来之后直接聚合,但不是每一个近邻节点都那么重要,因此从注意力感知这块或得了灵感,我们赋予不同节点不同的权重是不是更好,同时这个权重怎么分配应该交给网络自己根据输入的信息来学习,这样模型的能力又能得到进一步的增强.如此加入权重后,其每层的生成公式变成下图的形式,从公式可以发现原来的GCN其实也有一个做norm的节点度的一个权重,因此GAT与GCN最大的不同在于其传递的权重是自我学习得到的.

接下是如何设计这个权重,是的模型可以学习它,首先我们要对注意力机制有一个基本的了解,可以参考文章添加链接描述;当然不太了解在本课程里影响不是特别大,直观来说我们要学习消息从节点v传递到节点u的重要性$e_{vu}$,那么传到节点u的不止一个节点v,因此我们还要对传递到节点u的所有近邻节点的重要性做softmax,这样转成了和为1的权重,其表达形式如下

学习$e_{vu}$,我们可以通过将两个节点的信息拼接,给到线性层里去学习,如下图所示,

如果了解注意力机制的小伙伴,应该不难想到,其目标节点$h_u^{(l-1)}$是Q ,近邻节点的 { h i ( l − 1 ) , i ∈ N ( v ) } \{h_i^{(l-1)},i\in N(v)\} {hi(l−1)​,i∈N(v)}集合是K,而 { W l h i ( l − 1 ) , i ∈ N ( v ) } \{W^{l}h_i^{(l-1)},i\in N(v)\} {Wlhi(l−1)​,i∈N(v)}是V,
使用注意力机制的好处有:

1. 差异性:不同节点差异性传递
2. 效率高:注意力系数的计算可以在图的所有边上并行化,聚合可以在所有节点上并行化
3. 存储小:稀疏矩阵操作只需存储 O(V+E) 项,参数固定,不管图的大小
4. 局部性,关注局部邻近网络
5. 推导归纳能力:不依赖全局图结构,边共享机制

3. GNN应用层搭建

在实际应用中,通常还会加入现有的一些模块到GNN里,组合得到一个表现能力更强的层;常见的组合结构如下图所示,

• 其中batch_norm层可以稳定模型训练,使用批次数据计算出均值方差使用z-score的方式进行标准化;
• dropout层可以预防过拟合,对输入特征或隐藏特征的 Dropout;
  对图结构（节点和边）的 Dropout （例如忽略某些边或节点）;
  对线性权重的 Dropout。
  

二、GNN层之间的连接

1. 堆叠层

前面说了每一层的原理与构建结构,在现在海量的数据里,只使用一层的提取能力可能不足,我们可以通过多层堆叠的方式来增加模型能力,其表达形式最简单的就是每层按顺序连接,上一层的输出是下一层的输入.但是这样做的方式可能会出现过度平滑问题(所以节点嵌入结果近似一样);其原理如下图所示,由层的原理我们知道每多一层就多一次信息聚合,这意味着所涉及到的原图范围就越大,如下图所示,黄色点是目标点,红色点是它们的共享近邻节点,随着层数增加,目标点涉及的范围越来越大,不同目标点交叠的区域也越来多,到后面不同目标点的涉及范围几乎一致,那么它们的嵌入结果也越来越相似.

我们肯定是希望不同节点的嵌入应该具有一定区分性了,那么我们在增加层数的时候就要小心了,要根据我们能接受的重叠程度与输入的图的路径宽度(近似取图中心点走几步会到图边缘)来确定合适的层数;当然如果我们确实需要多层数来增强表征能力,那么我们可能需要一些小技巧来缓解过度平滑问题,如跳跃连接.

2. 层表征增强

2.1 单层表征增强

当我们不能堆叠太多层时要想办法将单层的表征能力增强,其常见的方法有
一是通过增加单层两个核心操作的网络复杂度来提升单层容量,如消息传递与聚合均使用三层深度的网络
二是可以在进入GNN前后添加处理层,如下图所示,进GNN前添加了MLP层做前后处理.

2.2 多层表征增强

那如果必须要增加层数呢,我们知道随着层数增加,其过平滑风险增加,因此可以知道较早,层的节点嵌入差异性是比较大的,这样我们可以在最后的节点嵌入里加大前面层的影响,从而降低过平滑的问题.其具体操作如下图所示,添加一些路径将前层信息传递到后层里去(跳跃连接),这样的话我们将得到一个浅层与深层GNN的混合模型,并且添加n条跳跃连接,其产生$2^n$条路径,这样的方式能够产生丰富的模型组合,

三、实践下的图操作

前面所有课程的讲诉均是建立在图数据是标准的符合我们输入要求,但实际应用中图数据不常符合输入要求,其常见的图数据问题如下
1、特征层面上:特征缺失,需要做特征增强(方法原理在后续课程介绍)
2、结构层面上:图太稀疏即边或节点很少,可以添加虚拟节点与边进行解决.
3、结构层面上:图太稠密,消息传递会耗时过多,可以在消息传递前对节点进行邻采样
4、结构层面上:图数据太大,会超显存,无法正常计算,可以进行子图划分解决(在后续课程介绍)

1、添加虚拟节点/边

图过于稀疏时有什么坏处:

• 稀疏图中存在较多未连接的顶点对，这可能导致模型无法学习到足够的关系或结构信息。
• 图中的某些顶点可能存在潜在关系，但由于稀疏性未被直接反映。

1.1 虚拟边

因此我们可以添加虚拟边或者虚拟点来增加边/节点的数量，提升图的联通性和稠密性。
模拟潜在的连接关系，增强图的结构信息。但是我们不能随意增加防止破坏图原有信息,常见的边增加的依据有
1, 基于节点特征相似性：计算顶点对的特征向量的相似度。常用方法包括欧氏距离、余弦相似度、点积等。
2. 基于局部连接关系：利用节点的共同邻居（Common Neighbors）、资源分配指数（Resource Allocation Index）、Adamic/Adar指数等度量邻接节点间的潜在关系。
3. 基于深度学习模型：通过图神经网络（GNNs）或其他深度学习模型来预测图结构中可能的缺失边。
如第一点基于相似性的边采样：对任意两个未连接的顶点 u,v计算其特征向量的相似度 s(u,v) 。如果 s(u,v)>τ，则添加虚拟边 (u,v)。

1.2 虚拟节点

节点的增加会更复杂一些,其核心点是要定义虚拟节点的功能性,如下图,是要作为全局信息中心,连接全图的重要节点。将虚拟点与全图中的所有节点连接，形成一个“超级节点”。

当然常见的功能还有为某些孤立节点提供支持;用于特定区域（如子图）的结构增强。

2、近邻采样

当图很稠密或者节点的度很高时,其消息传递的计算耗时会比较大,我们可以通过对目标节点的近邻节点进行随机采样,如此来控制消息传递的规模,提高计算效率.除了随机采样我们还可以

• 权重采样（weighted sampling）：根据边权重或其他相关评分进行加权采样。
• 距离限制采样：限制距离远近，选择优先靠近的节点邻居。

目前已经有不少成熟的GNN是专门处理稠密的图的,如

• GraphSAGE：通过随机采样固定数量的邻居，进行特征聚合。
• PinSAGE：专为稠密图设计，基于 GraphSAGE 增加了加权采样，用于 Pinterest 图谱推荐。
• DeepWalk/Node2Vec：基于随机游走对节点采样，引入采样上下文。

感兴趣的可以了解一下,实践一下上面的方法

四、总结

本课程首先对GNN层的构建原理进行了解读,其中包含两个核心环节消息传递与聚合,根据消息传递方式的差异性产生了不同的变种GCN,graphSAGE,GAT .然后介绍了GNN层与层之间的堆叠会产生的核心问题过度平滑,从而引申出可通过丰富单层核心环节的结构或增加GNN层输入输出前后的处理层实现单层容量增强,与跳跃式连接实现浅层与深层混合结构来实现容量增强两种方式.最后介绍了实际图数据的常见问题(稀疏,稠密,大图),为更好的实现图嵌入,我们需要通过增加虚拟节点/边解决图过度稀疏问题,以及近邻采样提升计算效率解决大图或过度稠密问题.