图神经网络

参考

图的表示

结构

什么是图?

图表示实体集合(节点Nodes)之间的关系(边Edges)

由以下三部分组成：

  • V：顶点/节点的属性；如：节点标识，邻居数量
  • E：边/链接的属性和方向；如：边的标识，边的权重
  • U：全局/主节点的属性；如：节点总数，最长路径

图信息嵌入

为了进一步描述每一个节点、边、乃至整幅图，我们可以将信息存储在图的每个部分中(可向量化)

有向边与无向边

  • 对于有向边：
    • $有原点v_{src}和目标点v_{dst}的概念$
    • $信息流向为v_{src}->v_{dst}$
  • 对于无向边：
    • $没有v_{src}和v_{dst}这个概念$
    • 信息是双向流动的

将数据建模为图

图像

我们可以将图像的每个像素视作节点node，每个像素(节点)通过无向边与相邻像素(节点)相连

相邻的规则为：对于每个非边缘的像素(节点)都有8个相邻节点

为了表示图的连通性，我们引入邻接矩阵(adjacency matrix)

  • 节点与节点相邻，在矩阵对应位置用1表示
  • 否则用0表示

左图为图像的像素矩阵，中间为邻接矩阵(深色表示1，浅色表示0)，右图为图联通情况的示意图

文本

我们可以通过将索引与每个字符、单词或token相关联，并将文本表示为这些索引的序列来数字化文本

将每个字符/单词/token/索引作为一个节点，通过一条边连接到它后面紧接着的节点

ps:这里的边为有向边

其他类型数据

比如分子结构，人物关系网，社交网络等

预测任务分类

  • 图级任务：我们的目标是预测整个图的属性

  • 节点级任务：与图中每个节点的身份或角色有关；比如下图中的学生偏向哪个联盟

  • 边级任务：比如图像场景识别；除了识别图像中的对象外，深度学习模型还可用于预测他们之间的关系，，我们可以将其表述为边级分类

在机器学习中使用图的挑战

核心问题:怎样表示图使其与神经网络兼容

对于图的4个属性：节点，边，全局属性，连通性来说；

  • 前3个属性都可以用向量进行表示，对神经网络友好
  • 对于连通性，通常使用邻接矩阵进行表示；N×N的矩阵，乍一听对神经网络很友好，但是存在很多的问题
    • 邻接矩阵可能是稀疏矩阵：对于大数据集，节点数量很多，但是边的数量却很少，这样得到的邻接矩阵就相当稀疏，不利于存储与计算
    • 邻接矩阵依赖于节点的排序，换句话说，对于一张图，可以有很多种邻接矩阵去表示它的连通性
      比如下图就表示了2个邻接矩阵表示同一张图的连通性

一个解决方案:使用节点、边、邻接列表、和全局构成

对于邻接列表：

  • 元素个数=边的数量
  • 列表中第i个元素代表该图的第i条边所连接的两个节点
  • [A,B]表示该条边连接着A，B节点

图神经网络GNN

图神经网络(GNN)是指：对图的所有属性(顶点，边，全局上下文)进行可优化的转换(optimizable transformation)，保持图的对称性(排列不变性)

GNN采用输入为图，输出也为图的架构

最简单的GNN

GNN层-属性更新

对于每个向量(全局向量U，节点向量V，边向量E)，分别使用一个多层感知机MLP(最基础的神经网络结构，全连接+非线性激活函数)进行计算，3个MLP就组成了GNN层。

对于每个向量，经过其对应的MLP后，只会更新属性，维度并不会变化，即图的结构不发生变化，仅仅更新属性

我们也可以与神经网络隐藏层一样，将GNN堆叠起来，形成一个更深的GNN

GNN层之后，我们得到一个新的、学习过的图，我们可以根据不同的任务进行不同的操作

比如节点n分类，在GNN的最后一层后再加上一层输出维度为n的全连接层，让每个节点公用这个全连接层，最后将输出进行softmax处理

Pooling-信息汇聚

对缺失的信息做预测时，我们就需要进行Pooling

比如我们对一个节点进行预测，但是我们此时并没有该节点的向量，此时我们需要对信息进行汇聚

Pooling运算分为两步：

  • 对于要Pooling的对象，收集对应信息向量
  • 将收集到的向量进行求和运算聚合
  1. 只有边向量，但是要对节点向量做预测:

$$
对于每个节点，\
收集它相邻边的信息V后，通过函数\rho_{E_n -> V_n}进行Pooling\
再通过全连接层进行最后的输出
$$

  1. 只有节点向量，预测边向量

使用边两端的节点向量进行Pooling后，接入全连接输出层

  1. 只有节点向量，预测全局向量U
    使用所有的节点向量进行Pooling，接入全连接输出层

总体模型

最终得到简单GNN的一个总体网络模型：

核心的部件就是GNN blocks，一个GNN块中有3个MLP，每个MLP对应着图的不同属性(节点，边，全局)；

输入一张图，经过多个GNN blocks后得到可优化转换后的图；

最后根据预测任务的不同选择不同的全连接输出层；如果缺失信息，还需要加上一层聚合层

存在问题

图中不同的属性分别进入各自的MLP，各算各的，没有交互，没有信息流动；

导致最后输出结果不能很好的充分利用整个图的信息

在图各部分间信息传递

为了解决上面提到的没有信息流动的问题

节点与节点

消息传递分3个步骤进行:

  • 对于当前节点，收集其通过边相邻的节点的信息
  • 对这些向量进行汇聚(sum.mean,max等操作)
  • 所有聚合消息通过更新函数传递；更新函数通常是学习的MLP

先将当前节点信息与相邻节点信息进行汇聚，得到进入MLP之前的的向量

新的架构图:

节点与边

我们的数据集并不总是包含所有类型的信息(边，节点，全局上下文)，如果图缺失某些属性，我们可以通过其他属性的信息汇聚得到该属性的预测；但是在前面的操作中，这一步都是放在最后的

我们可以直接在GNN层内部通过信息传递在边和节点之间共享信息，这样，信息汇聚就可以不用放在最后再进行了

图片中展示了将节点信息传递给边，边再把信息传递给节点这个过程

先将边两端顶点的信息汇聚到自己的向量上，得到更新后的边的信息；再将边的信息汇聚给节点，得到更新后的节点信息；最后通过3个MLP分别更新信息

对于边向量与节点向量维度不一样：

  • 学习两个向量间投影的线性变换
  • 拼接在一起

更多的信息传递形式:节点->边，边->节点；这两个过程同时进行；

添加全局表示

为什么要有全局信息？

如果图大而且连接不够紧密，消息的传递需要走很长的步才行；所以我们需要考虑全局信息U

具体是这样做的：

引入了一个抽象的虚拟点，称为主节点master node或上下文向量context vector；它与所有的节点和边都相连；

也就是说，U与V和E都相连

那么进行信息传递的时候，从V聚合给E时，需要与U聚合；从E聚合给V时，也需要与U汇聚；更新U时，需要同时聚合V，E；最后再通过MLP中更新

图卷积神经网络GCN

参考

引入

对于传统的卷积神经网络CNN，是利用一个 共享的参数-卷积核 进行加权运算来进行特征提取；

但是CNN有一个弊端，它只能处理Euclidean结构(具有规则空间结构的数据，比如矩阵)的数据

对于非Euclidean结构(在这里我们只考虑图)，CNN就难以选取一个合适的卷积核来适应图的不规则结构(节点顺序不确定，邻居节点数量不确定等)

图神经网络的基本原理是将图中节点编码映射为一个低维、连续、稠密的d维向量，能够反应节点在原图中的连接和属性关系；
两个节点对应的两个向量在d维空间上的相似度就能够反映这两个向量的原图之间的相似度

GCN的核心思想是：通过消息传递机制，利用图的拓扑结构，将节点与其邻居的特征聚合，从而学习包含结构特征的节点的嵌入embedding(基于空间卷积)

计算图

对于图这种非欧式结构的复杂数据，我们不能将邻接矩阵直接输入到神经网络中，也不能直接将原图输入到卷积神经网络中，而是要通过消息传递的框架，构建一个局部邻域的计算图

  • 直观理解：
    • 节点使用神经网络从它的邻居节点中聚合信息
  • 对图的理解：
    • 对于A来说，邻居节点(1阶邻域)为B,C,D
    • 再求出A的2阶邻域(邻居的邻居)
    • 前两步就构建出了A节点2层图神经网络的消息传递计算图
    • A的所有的2阶邻域使用同一个神经网络(第1个神经网络)
    • A的所有的1阶邻域使用同一个神经网络(第2个神经网络)

注意:

  • 图神经网络的层数指的是计算图的层数，而不是神经网络的层数；
  • 每个节点都可以分别构建出自己的计算图；
  • 训练图神经网络时，每一个计算图就是一个样本
  • 同一层图神经网络共享一套参数

引入这样一个计算图，我们的目标是:输入图的节点属性特征，通过层层的消息传递与信息汇聚，最终学习到A节点的embedding

感受野 & K跳邻域

感受野(receptive field):决定感兴趣节点的嵌入的节点集合

在K层的GNN中，每个节点的感受野为K跳邻域(K-Hop neighborhood)

层数越多，每个节点的邻居就越多，覆盖到的节点就越多，感受野就越大

根据6度空间理论，理论上GNN的层数达到6层就可以获取到图中所有的信息，理论上我们可以通过堆叠层数来聚合更远的邻居信息
但是事实上并不能这样做，如果GNN层数过深，会导致节点聚合了过多邻居的信息，使特征趋同，所有节点的计算图最后都会很类似(趋近于邻居节点的平均表示)
这种现象被称为”过平滑(Over-smoothing)“

所以GNN不能过深，一般2~3层就足够了

整体过程

  • 信息传递：聚合（使用求平均、最大值、求和等作为聚合方法）邻域节点的信息
  • 神经网络(盒子)：可以使用MLP；用于对聚合后的信息进行转换与更新；神经网络使用反向传播训练，前向传播预测

通过上面两步，最终学习到包含结构信息的节点embedding

为什么使用求平均、最大值、求和等作为聚合方法？
答：图是排列不变的，我们希望GNN具有顺序不变性；而上述方法都是可交换的，也就是说操作与元素的顺序无关

数学形式

前面所说的GCN的图示:

$$
\begin{align}
对于第0层的v节点的嵌入，就是v节点的属性特征\
h^{(0)}{v} = x{v}\
\end{align}
$$
$$
\begin{align}
对于第k+1层v节点的嵌入，由第k层v节点的邻域节点的嵌入计算得来(聚合方法为平均)\
h^{(k+1)}{v} = \sigma(W_k \sum{u \in N(v)} \frac{h^{k}{u}}{|N(v)|})\
N(v):节点v的邻域节点集合\
W_k:神经网络的参数\
\sigma:激活函数\
\end{align}
$$
$$
\begin{align}
对于v节点最终的embedding:\
Z_v = h{v}^{K}\
K:GNN的层数\
\end{align}
$$

写成矩阵表示的形式:

$$
\begin{align}
将所有节点第k层的embedding表示成一个矩阵:\
H^{(k)} = [h^{(k)}{1},h^{(k)}{2},\cdots,h^{(k)}{|V|}]
\end{align}
$$
$$
\begin{align}
得到v节点的邻域节点embedding:\
\sum{u \in N(v)}h^{(k)}{u} = A{v,:}H^{(k)}\
A:邻接矩阵\
A_{v,:}:表示v节点的连通性
\end{align}
$$


$$
\begin{align}
\求平均:引入一个D_{|V|\times|V|}矩阵,其中D_{vv}表示v节点的度(邻居数)\
\sum_{u \in N(v)} \frac{h^{k}{u}}{|N(v)|} = D^{-1}A{v,:}H^{(k)}
\end{align}
$$

其中，$D^{-1}A$被称为行归一化矩阵(Row Normalized Matrix),最大特征值为1，每行的和为1
$AD^{-1}$被称为列归一化矩阵(Column Normalized Matrix)，每列的和为1

$$
\begin{align}
对于第k+1层v节点的嵌入，我们就可以写成\
h^{(k+1)}_{v} = \sigma(W_kD^{-1}AH^{(k)})\
\end{align}
$$
numpy对D矩阵的一些操作

1
2
3
import numpy as np  
# 用于计算矩阵的分数次幂
from scipy.linalg import fractional_matrix_power

行/列归一化矩阵的缺点

对于$A_{row}$

  • 只考虑了横向的度，即只按自己的度对所有信息求平均，没有考虑对方的连接数
    对于$A_{col}$
  • 只考虑了纵向的度，即只考虑了对方对自己的信息的平均，没有考虑自己的度

朴素对称归一化矩阵Naively Symmetric Normalized Matrix

回顾一下线性代数:

$$
\begin{align}
特征值与特征向量\
对于矩阵A \in R^{n\times n},向量\nu \in R^{n},标量\lambda\in R\
如果A\nu=\lambda \nu,则:\
\nu称为矩阵A的特征向量\
\lambda为对应的特征值\
\end{align}
$$

用于解决上述两个矩阵带来的问题

$$
A_{naive} = D^{-1}AD^{-1}
$$
优点:即考虑了自己的度，也考虑了对方的度
缺点:特征值在(-1,1),输入向量左乘该矩阵后，幅值会变小(最大的特征值小于1)，缩放不合理

归一化扩散矩阵Normalized diffusion matrix

是对Naively Symmetric Normalized Matrix的改进:

$$
\tilde{A} = A_{sys} = D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\
\tilde{A_{ij}}= \frac{1}{\sqrt{d_i}\sqrt{d_j}}
$$
最大特征值为1

为什么这么做？

$$
\begin{align}
对于A_{naive} = D^{-1}AD^{-1}\
A_{naive} \neq A_{naive}^T\
如果连接的两个节点间度数差距悬殊，那么计算出来的A_{naive}会非常小，造成缩放的不合理
\end{align}
$$

个人理解：
$$
可以将\tilde{A}理解成邻接矩阵，只不过里面的权重不再是0/1，而是根据我的连接数和对方的连接数计算出的新权值\
只要图构建完成，\tilde{A}就是固定的
$$

得到第k层嵌入的计算公式:

$$
\begin{align}
H^{(k+1)} = \sigma(W^{(k)}D^{-1}AD^{-1}H^{(k)})
\end{align}
$$

对计算图的改进

前面的计算图有什么问题？

在信息传递的时候，并没有考虑到自己，仅聚合了它的邻域节点

改进：对每个节点都加入一个自环，这样信息传递和聚合的时候就能考虑到自己；输入的前一层自己的嵌入称为self embedding

$比如h_v^{k}是h_v^{k+1}的self-embedding$

此时邻接矩阵变为：
$$
\begin{align}
\tilde{A}=A+I\
其中I是单位方阵diag(1)
\end{align}
$$
此时我们就得到最终的每一层节点嵌入形式：

$$
\begin{align}
H^{(k+1)} = \sigma(D^{-1}\tilde{A}D^{-1}H^{(k)}W^k)\
\end{align}
$$
也可以拆开$D^{-1}$

$$
\begin{align}
H^{(k+1)}i = \sigma(\sum{j \in (N(i) \cup i)}\frac{\tilde{A}}{\sqrt{D_{ii}D_{jj}}}H^{(k)}W^k)\
=\sigma(\sum_{j \in (N(i))}\frac{\tilde{A}}{\sqrt{D_{ii}D_{jj}}}H^{(k)}W^k+\frac{\tilde{A}}{\sqrt{D_{ii}D_{ii}}}H^{(k)}W^k)\
=\sigma(\sum_{j \in (N(i))}\frac{\tilde{A}}{\sqrt{D_{ii}D_{jj}}}H^{(k)}W^k+\frac{\tilde{A}}{D_{ii}}H^{(k)}W^k)\
\end{align}
$$

  • 还可以进一步改进:

    • 思想：邻域节点使用一个权重，self embedding使用另一个权重

这里要注意和前面ResNet中学习的残差连接做区分

$$
\begin{align}
B_k是一个可学习的参数，B_kh_v^{(k)}并不是恒等映射(并非原样输出h_v^{(k)}) \
如果B_k是单位阵1，此时才是残差连接
\end{align}
$$

训练GCN

监督学习

eg:节点分类任务

损失函数

$$
\begin{align}
L = \sum_{v \in V}y_vlog(\sigma(z_v^T\theta))+(1-y_v)log(1-\sigma(z_v^T\theta))\
z_v^T:计算图输出的v节点的嵌入\
\theta:分类预测头权重参数\
y_v:v节点的类别标签\
\end{align}
$$

输入图经过多层图卷积网络后得到节点的嵌入向量，再接上一个预测头(可以是n分类的线性分类，如果预测结果线性可分)，就得到了分类结果y

训练的过程就是把d维向量在d维空间中变得越来越线性可分

无监督学习

如果没有节点标注，那么我们就使用图自身的结构作为自监督的标注

把两个节点分别输入图神经网络中，得到两个d维嵌入向量；然后计算这两个d维向量的点乘(对应余弦相似度)
我们希望这两个d维向量的余弦相似度能够反应它们在原图中的关系

u和v相似，DES()的标量高，否则低