Graph Nueral Network

发表于 分类于 阅读次数：

应用领域

图(a)道路网络 ；图(b)分子结构；图(c)电路图 图(d)飞机点云图 图(a)社交网络-无向；图(b)论文引用网络-有向；图(c)知识图谱-有向-异构

任务目标

可以根据预测目标是节点、边沿还是整个图的属性来进行广泛的分组。

图级别任务

  • 回归任务 预测某个分子的熔点；
  • 分类任务 预测某个分子是否具有毒性； 特定分子是否溶于水；
Graph分类

节点级任务

网络使用图结构和节点嵌入为图的每个节点分配一个标签（分类）或一个或多个值（回归）。 例如，上述飞机的点云图，预测节点是属于机身还是机翼；

Node分类

边沿预测任务

网络预测节点 n 和 m 之间是否应该存在边。 例如，在社交网络环境中，网络可能会预测两个人是否认识并喜欢对方，如果是的话，建议他们进行联系。 了解蛋白质网络中的一些相互作用，并希望预测任何其他相互作用的存在；

边沿预测

图表示学习

我们还可以在图上使用深度学习来发现有用的内部表示，这些表示随后可以促进一系列下游任务。 例如，我们可以通过在大型分子结构语料库上训练深度学习系统来寻求建立分子的基础模型。目标是，一旦经过训练，这样的基础模型就可以通过使用小型标记数据集来针对特定任务进行微调。

图表示

  • 节点嵌入： 存储节点处的信息，例如社交网络中，每个人都可以通过包含兴趣、年龄和学历等信息组成的固定长度向量表征；
  • 边沿嵌入：存储边沿处的信息，例如道路网络中，每个边沿可以包含道路长度、车道数、事故频率和限速等信息表征； 图由一组\(\mathbf{N}\)个点相互连接组成的\(\mathbf{E}\)个边沿组成，可以使用3个矩阵\((\mathbf{A}, \mathbf{X}, \mathbf{E})\)对其进行编码，分别代表图结构、节点嵌入和边沿嵌入。
数据嵌入

邻接矩阵

图的结构可以使用邻接矩阵表示节点间的连接关系。无向图，该矩阵始终是对称的。

如果图很大如何存储？

对于大型稀疏图来说，使用邻接矩阵存储会浪费大量内存，因为大部分元素都是0。 存储为连接列表 (m, n) 是一种更节省内存的方法，尤其适用于图节点数量众多但边相对较少的情况。

1
edge_list = [(0, 1), (0, 3), (1, 2), (2, 4)]

节点嵌入矩阵

第\(\mathbf{n}\)个节点具有一个长度为\(\mathbf{D}\)的节点嵌入向量\(\mathbf{x}^n\) ，将这些嵌入向量连接到一起并存储到\(\mathbf{D}\times\mathbf{N}\)的节点数据矩阵\(\mathbf{X}\)中。

边沿嵌入矩阵

第\(\mathbf{e}\)个边沿具有一个长度为\(\mathbf{D}_E\)的边沿嵌入向量\(\mathbf{e}^e\)，将这些嵌入向量连接到一起并存储到\(\mathbf{D}_E\times\mathbf{E}\)的节点数据矩阵\(\mathbf{E}\)中。

等变性和不变性

图中节点的索引顺序是任意的，节点索引的排列不会影响到图的表达，任何模型都必须尊重这一属性。

节点索引的排序

可以使用一个排列矩阵\(P\)表示节点的重新排序，其每行和每列只包含一个1。 例如，实现排列顺序从 \((A,B,C,D,E) \to (C,E,A,D,B)\)，则相应的排列矩阵表示如下： \[ P = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{pmatrix}\]

可以通过矩阵\(P\)实现对矩阵\(X\)的重新排列 \[\tilde{X}=XP\] 对于邻接矩阵\(A\)，行列都会被排列 \[\tilde{A}=P^TAP\]

不变性

不变性

当将深度学习应用于图结构数据时，我们需要以数字形式表示图结构，以便将其输入神经网络，这需要我们为节点分配顺序。然而，我们选择的具体顺序是任意的，因此确保图的任何全局属性不依赖于此顺序非常重要。换句话说，网络预测必须对节点标签重新排序保持不变， \[y(\tilde{X},\tilde{A})=y(X,A)\] 其中，\(y(.)\)函数是网络的输出。

等变性

等变性

我们可能还想做出与各个节点相关的预测。在这种情况下，如果我们对节点标签重新排序，则相应的预测应该显示相同的重新排序，以便给定的预测始终与相同的节点相关联，而不管顺序的选择如何。换句话说，节点预测应该与节点标签重新排序是等变的。这可以表示为 \[\bf{y}(\tilde{X},\tilde{A}) = \bf{y}(X,A)P\] 其中，\(\bf{y}(.)\)函数是网络输出的向量，每个节点一个元素.

消息传递

在应用深度神经网络在图结构数据时，在节点标签排列情况下，确保等变性和不变性是设计网络时的关键考虑因素。 - 节点级预测网络：要求整个网络保持等变性； - 图级别任务：对于不同的输入排列，要求最后一层要保持不变性； - 确保每一层都是高度灵活的非线性函数，并且其参数可微； - 图的输入尺寸是变化的，固定长度表示是不合适的，需要能处理可变长度输入； - 参数共享;

卷积滤波

为了开发满足上述要求的网络框架，可以从卷积神经网络中寻求灵感； - 图像可以视为图结构数据的特定实例； - 节点：像素 - 边沿：图像中的相邻的像素对；

卷积滤波器更新\(l+1\)层像素表达式如下： \[z_i^{(l+1)}=f\large(\sum_jw_jz_j^{(l)} + b\large)\] 上述表达可知，如果\(l+1\)层的像素重新排列，其输出并不具备 等变性，因为其权重向量。 尝试如下修改： \[z_i^{(l+1)}=f\large(w_{neigh}\sum_jz_j^{(l)} + w_{self}z_i^{(l)}+ b\large)\] 上述表达式，可以解释为通过从邻近节点传递到节点\[i\]的消息传递来收集来自邻近节点的信息，从而更新节点\(i\)处的局部表示\(z_i\)。 上述表达式中，通过简单的 求和函数 来聚合相邻节点的信息。对于输入节点的排序，显然是不变的。 这种不变性取决于所用节点共享参数\(w_{neigh}, w_{self}, b\)。

图卷积网络(GCN)

准确得讲，本文主要介绍 spatial-based convolutional graph neural networks(基于空间的卷积图神经网络)，简称 GCN。之所以称为基于空间，是因为使用原始的图结构信息。这与基于频谱(spectral-based)的方法形成对比，后者在傅里叶域应用卷积。 可以将网络的每层处理分为两个阶段：

  1. aggregation(聚合) 对于每个节点 n，消息从其邻居传递到该节点并以排列不变的方式组合形成新的向量\(z_n^{(l)}\)。 \[z_n^{(l)} = \large\mathcal{Aggregate}(\{h_m^{(l)}:m \in \mathcal{N}(n)\})\]
  2. update(更新) 将来自相邻节点的聚合信息(\(z_n^{(l)}\))与来自节点本身的本地信息相结合，并用于计算该节点的修改后的嵌入向量。 \[\large h_n^{(l+1)}=\mathcal{Update}(h_n^{(l)},z_n^{(l)})\]

节点嵌入通常使用观察到的节点数据进行初始化，例如\(h_n^{0}=\bf{x}_n\)。

上述框架称为： 消息传递神经网络

聚合算子

  • 求和 \[\large\mathcal{Aggregate}(\{h_m^{(l)}:m \in \mathcal{N}(n)\}) = \sum_{m\in\mathcal{N}(n)}h_m^{(l)}\] > 邻接节点较多的节点比邻接节点较少的节点相比，影响更大；
  • 平均值 \[\large\mathcal{Aggregate}(\{h_m^{(l)}:m \in \mathcal{N}(n)\}) = \frac{1}{|\mathcal{N}(n)|}\sum_{m\in\mathcal{N}(n)}h_m^{(l)}\] 其中\(|\mathcal{N}(n)|\)表示邻域集合\(\mathcal{N}(n)\)中的节点数。 > 这种归一化方式，丢弃了有关网络结构数据的信息，并被证明不如简单求和强大;
  • Kipf归一化 \[\large\mathcal{Aggregate}(\{h_m^{(l)}:m \in \mathcal{N}(n)\}) = \sum_{m\in\mathcal{N}(n)}\frac{h_m^{(l)}}{\sqrt{|\mathcal{N}(n)||\mathcal{N}(m)|}}\]
  • Max Pooling \[\large\mathcal{Aggregate}(\{h_m^{(l)}:m \in \mathcal{N}(n)\}) = \mathcal{Max}_{m\in\mathcal{N}(n)} h_m^{(l)}\]
  • MLP \[\large\mathcal{Aggregate}(\{h_m^{(l)}:m \in \mathcal{N}(n)\}) = \mathcal{MLP}_{\theta}\bigg(\sum_{m\in\mathcal{N}(n)} \mathcal{MLP}_{\phi}(h_m^{(l)})\bigg)\] 其中，\(\mathcal{MLP}_{\theta}和\mathcal{MLP}_{\phi}\)的参数在\(l\)层内共享。

感受野

随着层数增多，感受野增大

更新算子

\[\large\mathcal{Update}(h_n^{(l)},z_n^{(l)})=f({W}_{self}h_n^{(l)} + {W}_{neigh}z_n^{l} + b)\] 其中， 1. \(f(.)\)表示非线性函数，例如 Relu。 2. \(W_{self}, W_{neigh}和b\)表示学习的权重和偏置；

为此，神经网络可以表示为连续变换节点嵌入的一组序列： \[H^{(1)}=F(X,A,W^{(1)})\] \[H^{(2)}=F(H^{(1)},A,W^{(2)})\] ... \[H^{(L)}=F(H^{(L-1)},A,W^{(L)})\]

通用图网络

目前为止，图网络已经有了很多扩展和变体。

边沿嵌入

边沿嵌入

\[e_{nm}^{l+1}=\mathcal{Update}_{edge}\big(e_{nm}^{(l)},h_n^{(l)},h_m^{(l)}\big)\] \[z_n^{(l+1)}=\mathcal{Aggregate}_{node}(\set{e_{nm}^{(l)}:m \in \mathcal{N}(n)})\] \[h_n^{l+1}=\mathcal{Update}_{node}(h_n^{(l)},z_n^{(l+1)})\]