CS224W-07：图神经网络二_gnn聚合层数

图神经网络二

第六节主要是对图神经网络做了一个整体上的介绍，本节介绍几种经典的GNN 和设计GNN的基本思路。具体内容为

• 单层 GNN
  • 单层 GNN 的一般形式
  • 经典的 GNN 网络：GCN, GraphSAGE, GAT
• 多层 GNN 设计
  • 如何确定 GNN 网络的层数
  • 过平滑 (Over smoothing) 问题
  • 跳跃连接 (Skip connections)
• 实际训练中图的操作
  • 特征增广 (Feature augmentation)
  • 结构变换 (Structure manipulation)

单层 GNN

单层 GNN 的一般形式

节点嵌入的计算包括消息传递和聚合两个步骤，消息传递是根据邻域节点的嵌入计算消息，消息聚合是将邻域节点传递的消息与自身的嵌入结合到一起计算新的嵌入。消息计算可以表示为
m u ( l ) = MSG ( l ) ( h u ( l − 1 ) ) ,   ∀ u ∈ { N ( v ) ∪ v } \mathbf m_u^{(l)} = \text{MSG}^{(l)} (\mathbf h_u^{(l-1)}), \, \forall u \in \{N(v) \cup v \} mu(l)​=MSG(l)(hu(l−1)​),∀u∈{N(v)∪v}
例如线性连接 (Linear layer)为
$$\begin{gathered} {\mathbf{m}}_u^{(l)}={\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l-1)},\forall u\in N(v) \\ {\mathbf{m}}_v^{(l)}={\mathbf{B}}^{(l)}{\mathbf{h}}_v^{(l-1)} \end{gathered}$$

消息聚合可以表示为
h v ( l ) = AGG ( l ) ( { m u ( l ) , ∀ u ∈ N ( v ) } , m v ( l ) ) \mathbf h_v^{(l)} = \text{AGG}^{(l)}(\{ \mathbf m_u^{(l)}, \forall u \in N(v) \}, \mathbf m_v^{(l)}) hv(l)​=AGG(l)({mu(l)​,∀u∈N(v)},mv(l)​)

Graph Convolution Networks (GCN)

GCN 是一种基于空间的图卷积网络，消息传递和聚合比较简单
$$
\begin{align}
& \text{Message: } \mathbf m_u^{(l)} = \frac {1}{|N(v)|} \mathbf W^{(l)} \mathbf h_u^{(l)} \
& \text{Agrregation: } \mathbf h_v^{(l)} = \sigma (\sum_{u \in N(v)} \mathbf m_u^{(l)}) \
& \text{Together: } \mathbf h_v^{(l)} = \sigma (\sum_{u \in N(v)} \frac {1}{|N(v)|} \mathbf W^{(l)} \mathbf h_u^{(l)})

\end{align}
$$

GraphSAGE

GraphSAGE 中介绍了三种不同的聚合方式，其计算公式如下
h u ( l ) = σ ( W ( l ) ⋅ CONCAT ( h v ( l − 1 ) , AGG ( { h u ( l − 1 ) , ∀ u ∈ N ( v ) } ) ) \mathbf h_u^{(l)} = \sigma \left(\mathbf W^{(l)} \cdot \text{CONCAT} \left (\mathbf h_v^{(l-1)}, \text{AGG}(\{\mathbf h_u^{(l-1)}, \forall u \in N(v)\} \right) \right) hu(l)​=σ(W(l)⋅CONCAT(hv(l−1)​,AGG({hu(l−1)​,∀u∈N(v)}))
消息传递的计算实际是在函数 AGG 中完成的，GraphSAGE 可以分解为两步

• 从邻域节点聚合消息 ： h N ( v ) ( l ) = AGG ( { h u ( l − 1 ) , ∀ u ∈ N ( v ) } ) \mathbf h_{N(v)}^{(l)} = \text{AGG}(\{\mathbf h_u^{(l-1)}, \forall u \in N(v)\}) hN(v)(l)​=AGG({hu(l−1)​,∀u∈N(v)})
• 将节点嵌入与邻域消息在此聚合：$\mathbf h_u^{(l)} = \sigma \left(\mathbf W^{(l)} \cdot \text{CONCAT} (\mathbf h_{N(v)}^{(l)}, \mathbf h_u^{(l-1)}) \right) $

聚合函数有三种选择

• Mean: 计算邻域节点的加权平均
  $$\text{AGG}=\sum _{u\in N(v)}\frac{{\mathbf{h}}_u^{(l-1)}}{|N(v)|}$$

• Pool: 对邻域节点嵌入向量做变换后，使用平均池化或最大池化
  $$\text{AGG}=\text{Mean}\left(\text{MLP}({\mathbf{h}}_u^{(l-1)}),\forall u\in N(v)\right)$$

• LSTM: 将节点顺序打乱后，再应用 LSTM
  $$\text{AGG}=\text{LSTM}([{\mathbf{h}}_u^{(l-1)},\forall u\in \pi (N(v))])$$

GraphSAGE 还使用了 L2 归一化，对于节点的嵌入
$${\mathbf{h}}_v^{(l)}=\frac{{\mathbf{h}}_v(l)}{\Vert {\mathbf{h}}_v(l){\Vert }_2}$$
归一化保证节点的嵌入向量都在同一尺度，在某些情况下可能会有更好的效果。

Graph Attention Networks (GAT)

GAT在消息聚合时给每个节点的消息增加了注意力权重，计算公式为
$${\mathbf{h}}_v^{(l)}=\sigma \left(\sum _{u\in N(v)}{\alpha }_{vu}{\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l-1)}\right)$$
在 GCN 和 GraphSAGE 中，${\alpha }_{vu}=\frac{1}{N(v)}$， 这表示领域 $N(v)$ 中每个节点对于节点 $v$ 都是同等重要的。在 GAT 中，${\alpha }_{vu}$ 是可学习的参数。用 $e_{vu}$ 表示节点 $u$ 传向节点 $v$ 消息的重要性，$a$ 表示重要性计算函数
$$e_{vu}=a({\mathbf{W}}^{(l)}{\mathbf{h}}_v^{(l-1)},{\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l-1)})$$
在原论文中
$$e_{vu}=\text{LeakyReLU}\left({\mathbf{a}}^T\cdot \text{CONCAT}({\mathbf{h}}_v^{(l-1)},{\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l-1)})\right)$$
其中 $\mathbf{a}$ 可学习参数。再使用 Softmax 对边重要性作归一化
$${\alpha }_{vu}=\frac{\exp (e_{vu})}{{\sum }_{k\in N(v)}\exp (e_{vk})}$$
GAT 还可以增加多个注意模块 (Multi-head attention)，这样对网络的稳定性有一定提升。具体做法就是对每条边的消息计算多个注意力，然后将这些消息聚合起来得到最终的嵌入向量，公式为
$$\begin{gathered} {\mathbf{h}}_v^{(l)}[1]=\sigma \left(\sum _{u\in N(v)}{\alpha }_{vu}^1{\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l-1)}\right) \\ {\mathbf{h}}_v^{(l)}[2]=\sigma \left(\sum _{u\in N(v)}{\alpha }_{vu}^2{\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l-1)}\right) \\ {\mathbf{h}}_v^{(l)}[3]=\sigma \left(\sum _{u\in N(v)}{\alpha }_{vu}^3{\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l-1)}\right) \end{gathered}$$
聚合方式使用 Concat 、求和或者其他方式
$${\mathbf{h}}_v^{(l)}=\text{AGG}({\mathbf{h}}_v^{(l)}[1],{\mathbf{h}}_v^{(l)}[2],{\mathbf{h}}_v^{(l)}[3])$$
GAT 的优点有：

• 计算效率高：边的注意力和聚合操作都可以并行计算
• 存储效率高：只需要存储节点和边的计算权重，空间复杂度为 $O(V+E)$ ; 不论图的大小如何，网络参数大小不变
• 局部性：注意力只作用于图中的局部结构
• 归纳性学习能力：训练得到的边的权重是共享的，与图的结构无关

GNN 中常用的模块

与 CNN 中类似，GNN 中也可以使用 Normalization, Dropout, Activation 等模块 ，常用的 GNN 包含的模块如下

Batch Normalization 计算如下

Dropout 作用于消息计算之后，以线性连接为例

激活函数与其他神经网络一样。授课课题组有一个方便的工具 GraphGym

多层 GNN

构建多层 GNN 的最简单的方式是将多个单层 GNN 网络按顺序堆叠起来，第1层的输入嵌入为节点特征 ${\mathbf{h}}_v^{(0)}={\mathbf{x}}_v$ ，依次使用 GNN 计算节点嵌入向量，最后一层输出所需的节点嵌入。

与CNN 等深度神经网络不同的是，多层 GNN 会遇到一个特殊问题——过平滑 (Over smoothing) 。当 GNN 层数太多时，每个节点的嵌入向量会逐渐收敛至同一个值，最后输出的节点嵌入不再能够区分不同节点。过平滑的出现与 GNN 的计算方式密切相关。 目前GNN 一般使用消息传递和聚合的方式来更新节点嵌入，而消息聚合的结果取决于邻域节点，也就是该节点的感受野。通过多层 GNN，节点的感受野不断扩大，获得的信息也从局部扩展到图的全局，但是与其他节点感受野的重合度也越来越大。如下图所示，经过三层 GNN 后，节点的邻域已经扩展到 3跳，但几乎囊括了图中所有节点，不同节点的邻域的重合度也变得非常大，计算得到的嵌入会变得非常接近，最终造成过平滑问题。概括起来就是：堆叠多层 GNN 网络 → 节点之间的感受野高度重合 → 节点嵌入变得十分接近 → 造成过平滑问题。

那么该如何解决过平滑问题呢？可以从两方面着手：一是使用浅层 GNN；二是借鉴 Resnet 的思想，增加跳跃连接 (Skip connections).

浅层 GNN

在设计 GNN 时，我们需要不能盲目的增加网络的深度，更深的 GNN 不一定有更好的效果。GNN 的层数可以通过分析节点需要的最大感受野来确定（例如图的直径来表示节点最大感受野），网络的层数往往比需要的感受野稍微大一点即可。虽然浅层 GNN 可以避免过平滑问题，那么该如何提高浅层 GNN 的表达力呢？解决方案有两种：

1. 加强单层 GNN 内消息聚合的复杂性。在之前的例子中，消息计算通常只用了一次线性计算，我们可以将消息聚合变得更复杂，使用多层感知 (MLP)，将消息传递和聚合变成一个深度神经网络。
2. 增加不传递消息的计算层。在 GNN 前后分别增加前处理层和后处理层，这些层只对节点特征进行计算，不做任何消息传递。

跳跃连接

观察到深层 GNN 可能导致过平滑问题，浅层 GNN 的节点嵌入的区分度可能更大，所以我们可以将浅层网络的嵌入通过跳跃连接，与深层网络的嵌入相加，以保留节点的区分度。

比如在 GCN 中，原始的消息聚合方式为 $ \mathbf h_v^{(l)} = \sigma (\sum_{u \in N(v)} \frac {1}{|N(v)|} \mathbf W^{(l)} \mathbf h_u^{(l)})$ ，增加跳跃连接后
$${\mathbf{h}}_v^{(l)}=\sigma (\sum _{u\in N(v)}\frac{1}{|N(v)|}{\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l)}+{\mathbf{h}}_v^{(l)})$$
疑问：与上一节讲的公式 ${\mathbf{h}}_v^{(l)}=\sigma ({\sum }_{u\in N(v)}\frac{1}{|N(v)|}{\mathbf{W}}^{(l)}{\mathbf{h}}_u^{(l)}+{\mathbf{B}}^{(l)}{\mathbf{h}}_v^{(l)})$ 很相像，而且与GraphSAGE 中的聚合方式也比较像，这种跳跃连接真的有很大作用吗？

图的操作 (Graph Manipulation in GNNs)

在之间的内容中，输入到 GNN 中计算的图和图的原始数据是一样的，但是实际中，计算图和原始图可能存在不同。我们可能需要改变图的节点特征和图的结构。

• 改变特征：当节点缺少特征，需要对特征做扩展
• 改变结构：当图太稀疏（消息传递效率低），或太密集（消息传递计算量大），或图太大（无法用GPU 计算整张图）

特征扩展

当节点没有任何特征是，可以使用常数特征或者独热编码 (one-hot )作为节点特征，二者的优缺点如下

当然这两种特征很难区分图中的某些结构，具体例子参看课件。除此之外，还可使用第二讲中介绍的特征：Clustering coefficient, PageRank, Centerity 等等。

改变图结构

1. 增加虚拟边：当图过于稀疏时，可以增加虚拟边，可以将 2 跳邻域内的节点都连接起来。邻接矩阵变成 $A+A^2$
2. 增加虚拟节点：增加一个虚拟节点，它与所有节点都相连，这样所有节点之间的最大距离都变为2，有效提高消息传递的效率
3. 邻域节点随机采样：当图过于稠密时，可以对邻域节点进行随机采样，以减少消息传递的计算量