关于机器学习:图神经网络的数学原理总结

图深度学习(Graph Deep Learning) 多年来始终在减速倒退。许多现实生活问题使 GDL 成为万能工具：在社交媒体、药物发现、芯片植入、预测、生物信息学等方面都显示出了很大的前景。

本文将风行的图神经网络及其数学细微差别的进行具体的梳理和解释，图深度学习背地的思维是学习具备节点和边的图的构造和空间特色，这些节点和边示意实体及其交互。

图

在咱们进入图神经网络之前，让咱们先来摸索一下计算机科学中的图是什么。

图 G(V,E)是蕴含一组顶点(节点)i∈v 和一组连贯顶点 i 和 j 的边 eij∈E 的数据结构，如果连贯两个节点 i 和 j，则 eij=1，否则 eij=0。能够将连贯信息存储在邻接矩阵 A 中:

我假如本文中的图是无加权的 (没有边权值或间隔) 和无向的(节点之间没有方向关联), 并且假如这些图是同质的(繁多类型的节点和边; 相同的是“异质”)。

图与惯例数据的不同之处在于，它们具备神经网络必须尊重的构造; 不利用它就太节约了。上面的图是一个社交媒体图的例子，节点是用户，边是他们的互动(比方关注 / 点赞 / 转发)。

对于图像来说，图像自身就是一个图! 这是一种叫做“网格图”的非凡变体，其中对于所有外部节点和角节点，来自节点的内向边的数量是恒定的。在图像网格图中存在一些统一的构造，容许对其执行简略的相似卷积的操作。

图像能够被认为是一种非凡的图，其中每个像素都是一个节点，并通过虚线与四周的其余像素连贯。当然，以这种形式查看图像是不切实际的，因为这意味着须要一个十分大的图。例如，32×32×3 的一个简略的 CIFAR-10 图像会有 3072 个节点和 1984 条边。对于 224×224×3 的较大 ImageNet 图像，这些数字会更大。

与图片相比，图的不同的节点与其余节点的连贯数量不同，并且没有固定的构造，然而就是这种构造为图减少了价值。

图神经网络

单个图神经网络 (GNN) 层有一堆步骤，在图中的每个节点上会执行:

• 消息传递
• 聚合
• 更新

这些组成了对图形进行学习的构建块，GDL 的翻新都是在这 3 个步骤的进行的扭转。

节点

节点示意一个实体或对象，如用户或原子。因而节点具备所示意实体的一系列属性。这些节点属性造成了节点的特色(即“节点特色”或“节点嵌入”)。

通常，这些特色能够用 Rd 中的向量示意． 这个向量要么是潜维嵌入，要么是以每个条目都是实体的不同属性的形式结构的。

例如，在社交媒体图中，用户节点具备能够用数字示意的年龄、性别、政治偏向、关系状态等属性。在分子图中，原子节点可能具备化学性质，如对水的亲和力、力、能量等，也能够用数字示意。

这些节点特色是 GNN 的输出，每个节点 i 具备关联的节点特色 xi∈Rd 和标签 yi(能够是间断的，也能够是离散的，就像独自编码一样)。

边

边也能够有特色 aij∈Rd ‘ 例如，在边缘有意义的状况下(如原子之间的化学键)。咱们能够把上面的分子设想成一个图，其中原子是节点，键是边。尽管原子节点自身有各自的特征向量，但边能够有不同的边特色，编码不同类型的键(单键、双键、三键)。不过为了简略起见，在本文中我将省略边的个性。

当初咱们晓得了如何在图中示意节点和边，让咱们从一个具备一堆节点 (具备节点特色) 和边的简略图开始。

消息传递

gnn 以其学习构造信息的能力而闻名。通常，具备类似特色或属性的节点相互连接(比方在社交媒体中)。GNN 利用学习特定节点如何以及为什么相互连接，GNN 会查看节点的邻域。

街坊 Ni，节点 I 的汇合定义为通过边与 I 相连的节点 j 的汇合。模式为 Ni={j: eij∈E}。

一个人被他所处的圈子所影响。相似地 GNN 能够通过查看其街坊 Ni 中的节点 i 来理解很多对于节点 i 的信息。为了在源节点 i 和它的街坊节点 j 之间实现这种信息共享，gnn 进行消息传递。

对于 GNN 层，消息传递被定义为获取街坊的节点特色，转换它们并将它们“传递”给源节点的过程。对于图中的所有节点，并行地反复这个过程。这样，在这一步完结时，所有的邻域都将被查看。

让咱们放大节点 6 并查看邻域 N6={1,3,4}。咱们取每个节点特色 x1、x3 和 x4，用函数 F 对它们进行变换，函数 F 能够是一个简略的神经网络(MLP 或 RNN)，也能够是仿射变换 F(xj)=Wj⋅xj+b。简略地说，“音讯”是来自源节点的转换后的节点特色。

F 能够是简略的仿射变换或神经网络。当初咱们设 F(xj)=Wj⋅xj 为了不便计算 ⋅ 示意简略的矩阵乘法。

聚合

当初咱们有了转换后的音讯 {F(x1)，F(x3)，F(x4)} 传递给节点 6，上面就必须以某种形式聚合 (“组合”) 它们。有很多办法能够将它们联合起来。罕用的聚合函数包含:

假如咱们应用函数 G 来聚合街坊的音讯(应用 sum、mean、max 或 min)。最终聚合的音讯能够示意为:

更新

应用这些聚合音讯，GNN 层就要更新源节点 i 的个性。在这个更新步骤的最初，节点不仅应该晓得本人，还应该晓得它的街坊。这是通过获取节点 i 的特征向量并将其与聚合的音讯相结合来操作的，一个简略的加法或连贯操作就能够解决这个问题。

应用加法

其中 σ 是一个激活函数 (ReLU, ELU, Tanh)，H 是一个简略的神经网络(MLP) 或仿射变换，K 是另一个 MLP，将加法的向量投影到另一个维度。

应用连贯:

为了进一步形象这个更新步骤，咱们能够将 K 看作某个投影函数，它将音讯和源节点嵌入一起转换:

初始节点特色称为 xi，在通过第一 GNN 层后，咱们将节点特色变为 hi。假如咱们有更多的 GNN 层，咱们能够用 hli 示意节点特色，其中 l 是以后 GNN 层索引。同样，显然 h0i=xi(即 GNN 的输出)。

整合在一起

当初咱们曾经实现了消息传递、聚合和更新步骤，让咱们把它们放在一起，在单个节点 i 上造成单个 GNN 层：

这里咱们应用求和聚合和一个简略的前馈层作为函数 F 和 H。设 hi∈Rd, W1,W2⊆Rd ‘ ×d 其中 d ‘ 为嵌入维数。

应用邻接矩阵

到目前为止，咱们通过单个节点 i 的视角察看了整个 GNN 正向传递，当给定整个邻接矩阵 a 和 X⊆RN×d 中所有 N =∥V∥节点特色时，晓得如何实现 GNN 正向传递也很重要。

在 MLP 前向传递中，咱们想要对特征向量 xi 中的我的项目进行加权。这能够看作是节点特征向量 xi∈Rd 和参数矩阵 W⊆Rd′×d 的点积，其中 d′ 是嵌入维度：

如果咱们想对数据集中的所有样本 (矢量化) 这样做，咱们只需将参数矩阵和特色矩阵相乘，就能够失去转换后的节点特色(音讯):

在 gnn 中，对于每个节点 i，音讯聚合操作包含获取相邻节点特征向量，转换它们，并将它们相加(在和聚合的状况下)。

单行 Ai 对于 Aij= 1 的每个指标 j，咱们晓得节点 i 和 j 是相连的→eij∈E。例如，如果 A2=[1,0,1,1,0]，咱们晓得节点 2 与节点 1、3 和 4 连贯。因而，当咱们将 A2 与 Z =XW 相乘时，咱们只思考列 1、3 和 4，而疏忽列 2 和 5：

比如说 A 的第二行。

矩阵乘法就是 A 中的每一行与 Z 中的每一列的点积，这就是音讯聚合的含意!!

获取所有 N 的聚合音讯，依据图中节点之间的连贯，将整个邻接矩阵 A 与转换后的节点特色进行矩阵乘法:

然而这里有一个小问题: 察看到聚合的音讯没有思考节点 i 本人的特征向量(正如咱们下面所做的那样)。所以咱们将自循环增加到 A(每个节点 i 连贯到本身)。

这意味着对角线的而数值须要进行批改，用一些线性代数，咱们能够用单位矩阵来做这个!

增加自循环能够容许 GNN 将源节点的特色与其街坊节点的特色一起聚合!!

有了这些，你就能够用矩阵而不是单节点来实现 GNN 的传递。

⭐要执行平均值聚合（mean），咱们能够简略地将总和除以 1，对于下面的例子，因为 A2=[1,0,0,1,1]中有三个 1，咱们能够将∑j∈N2Wxj 除以 3，然而用 gnn 的邻接矩阵公式来实现最大（max）和最小聚合（min）是不可能的。

GNN 层重叠

下面咱们曾经介绍了单个 GNN 层是如何工作的，那么咱们如何应用这些层构建整个“网络”呢? 信息如何在层之间流动，GNN 如何细化节点 (和 / 或边) 的嵌入 / 示意?

• 第一个 GNN 层的输出是节点特色 X⊆RN×d。输入是两头节点嵌入 H1⊆RN×d1，其中 d1 是第一个嵌入维度。H1 由 h1i: 1→N∈Rd1 组成。
• H1 是第二层的输出。下一个输入是 H2⊆RN×d2，其中 d2 是第二层的嵌入维度。同理，H2 由 h2i: 1→N∈Rd2 组成。
• 通过几层之后，在输入层 L，输入是 HL⊆RN×dL。最初，HL 由 hLi: 1→N∈RdL 形成。

这里的 {d1,d2，…，dL} 的抉择齐全取决于咱们，能够看作是 GNN 的超参数。把这些看作是为 MLP 层抉择单位(“神经元”的数量)。

节点特色 / 嵌入 (“示意”) 通过 GNN 传递。尽管构造放弃不变，但节点示意在各个层中一直变动。边示意也将扭转，但不会扭转连贯或方向。

HL 也能够做一些事件:

咱们能够沿着第一个轴 (即∑Nk=1hLk) 将其相加，失去 RdL 中的向量。这个向量是整个图的最新维度示意。它能够用于图形分类(例如: 这是什么分子?)

咱们能够在 HL 中连贯向量(即⨁Nk=1hk，其中⊕是向量连贯操作)，并将其传递给一个 Graph Autoencoder。当输出图有噪声或损坏，而咱们想要重建去噪图时，就须要这个操作。

咱们能够做节点分类→这个节点属于什么类? 在特定索引 hLi (i:1→N)处嵌入的节点能够通过分类器 (如 MLP) 分为 K 个类(例如: 这是碳原子、氢原子还是氧原子?)

咱们还能够进行链接预测→某个节点 i 和 j 之间是否存在链接?hLi 和 hLj 的节点嵌入能够被输出到另一个基于 sigmoid 的 MLP 中，该 MLP 输入这些节点之间存在边的概率。

这些就是 GNN 在不同的利用中所进行的操作，无论哪种形式，每个 h1→N∈HL 都能够被重叠，并被视为一批样本。咱们能够很容易地将其视为批处理。

对于给定的节点 i, GNN 聚合的第 l 层具备节点 i 的 l 跳邻域。节点看到它的近邻，并深刻到网络中，它与街坊的街坊交互。

这就是为什么对于十分小、稠密 (很少边) 的图，大量的 GNN 层通常会导致性能降落：因为节点嵌入都收敛到一个向量，因为每个节点都看到了许多跳之外的节点。对于小的图，这是没有任何作用的。

这也解释了为什么大多数 GNN 论文在试验中常常应用≤4 层来防止网络呈现问题。

以节点分类为例训练 GNN

在训练期间，对节点、边或整个图的预测能够应用损失函数 (例如: 穿插熵) 与来自数据集的 ground-truth 标签进行比拟。也就是说 gnn 可能应用反向流传和梯度降落以端到端形式进行训练。

训练和测试数据

与惯例 ML 一样，图数据也能够分为训练和测试。这有两种办法:

1、Transductive

训练数据和测试数据都在同一个图中。每个汇合中的节点相互连接。只是在训练期间，测试节点的标签是暗藏的，而训练节点的标签是可见的。但所有节点的特色对于 GNN 都是可见的。

咱们能够对所有节点进行二进制掩码(如果一个训练节点 i 连贯到一个测试节点 j，只需在邻接矩阵中设置 Aij=0)。

训练节点和测试节点都是同一个图的一部分。训练节点裸露它们的特色和标签，而测试节点只裸露它们的特色。测试标签对模型暗藏。二进制掩码须要通知 GNN 什么是训练节点，什么是测试节点。

2、Inductive

另外一种办法是独自的训练图和测试图。这相似于惯例的 ML，其中模型在训练期间只看到特色和标签，并且只看到用于测试的特色。训练和测试在两个独立的图上进行。这些测试图散布在外，能够查看训练期间的泛化品质。

与惯例 ML 一样，训练数据和测试数据是离开保留的。GNN 只应用来自训练节点的特色和标签。这里不须要二进制掩码来暗藏测试节点，因为它们来自不同的汇合。

反向流传和梯度降落

在训练过程中，一旦咱们向前通过 GNN，咱们就失去了最终的节点示意 hLi∈HL，为了以端到端形式训练，能够做以下工作:

• 将每个 hLi 输出 MLP 分类器，失去预测 ^yi
• 应用 ground-truth yi 和预测 yi→J(yi,yi)计算损失
• 应用反向流传来计算∂J/∂Wl，其中 Wl 是来自 l 层的参数矩阵
• 应用优化器更新 GNN 中每一层的参数 Wl
• (如果须要)还能够微调分类器 (MLP) 网络的权重。

🥳这意味着 gnn 在消息传递和训练方面都很容易并行。整个过程能够矢量化(如上所示)，并在 gpu 上执行!!

风行图神经网络总结

下面咱们介绍完了古神经网络的根本流程，上面咱们总结一下风行图神经网络，并将它们的方程和数学分为下面提到的 3 个 GNN 步骤。许多体系结构将消息传递和聚合步骤合并到一起执行的一个函数中，而不是显式地一个接一个执行，但为了数学上的不便，咱们将尝试合成它们并将它们视为一个繁多的操作!

1、消息传递神经网络

https://arxiv.org/abs/1704.01212

消息传递神经网络 (MPNN) 将正向流传合成为具备音讯函数 Ml 的消息传递阶段和具备顶点更新函数 Ul 的读出阶段

MPNN 将消息传递和聚合步骤合并到单个消息传递阶段:

读取阶段是更新步骤:

其中 ml+1v 是聚合的音讯，hl+1v 是更新的节点嵌入。这与我下面提到的过程十分类似。音讯函数 Ml 是 F 和 G 的混合，函数 Ul 是 k，其中 eij 示意可能的边缘特色，也能够省略。

2、图卷积

https://arxiv.org/abs/1609.02907

图卷积网络 (GCN) 论文以邻接矩阵的模式钻研整个图。在邻接矩阵中退出自连贯，确保所有节点都与本人连贯以失去~A。这确保在音讯聚合期间思考源节点的嵌入。合并的音讯聚合和更新步骤如下所示:

其中 Wl 是一个可学习参数矩阵。这里将 X 改为 H，以泛化任意层 l 上的节点特色，其中 H0=X。

因为矩阵乘法的结合律(A(BC)=(AB)C)，咱们在哪个序列中乘矩阵并不重要(要么是~AHl 先乘，而后是 Wl 后乘，要么是 HlWl 先乘，而后是~A)。作者 Kipf 和 Welling 进一步引入了度矩阵~D 作为 ”renormalisation” 的一种模式，以防止数值不稳固和爆炸 / 隐没的梯度:

“renormalisation”是在增广邻接矩阵 ^A=D−12A~D−12 上进行的。新的合并消息传递和更新步骤如下所示:

3、图注意力网络

https://arxiv.org/abs/1710.10903

聚合通常波及在和、均值、最大值和最小值设置中平等看待所有街坊。然而在大多数状况下，一些街坊比其余街坊更重要。图注意力网络 (GAT) 通过应用 Vaswani 等人 (2017) 的 Self-Attention 对源节点及其街坊之间的边缘进行加权来确保这一点。

边权值 αij 如下。

这里的 Wa∈R2d ‘ 和 W⊆Rd ‘ ×d 为学习参数，d ‘ 为嵌入维数，⊕是向量拼接运算。

尽管最后的消息传递步骤与 MPNN/GCN 雷同，但合并的音讯聚合和更新步骤是所有街坊和节点自身的加权和:

边缘重要性加权有助于理解街坊对源节点的影响水平。与 GCN 一样，增加了自循环，因而源节点能够将本人的示意模式思考到将来的示意模式中。

4、GraphSAGE

https://arxiv.org/abs/1706.02216

GraphSAGE：Graph SAmple and AggreGatE。这是一个为大型、十分密集的图形生成节点嵌入的模型。

这项工作在节点的邻域上引入了学习聚合器。不像传统的 gat 或 GCNs 思考街坊中的所有节点，GraphSAGE 对立地对街坊进行采样，并对它们应用学习的聚合器。

假如咱们在网络 (深度) 中有 L 层，每一层 L∈{1，…，L}查看一个更大的 L 跳邻域 w.r.t. 源节点。而后在通过 MLP 的 F 和非线性 σ 传递之前，通过将节点嵌入与采样音讯连贯来更新每个源节点。

对于某一层 l

其中⊕是向量拼接运算，N(i)是返回所有街坊的子集的对立抽样函数。如果一个节点有 5 个街坊 {1,2,3,4,5}，N(i) 可能的输入将是 {1,4,5} 或{2,5}。

Aggregator k= 1 从 1 -hop 邻域汇集采样节点(黑白)，而 Aggregator k= 2 从 2 -hop 邻域汇集采样节点(黑白)

论文中用 K 和 K 表示层指数。但在本文中别离应用 L 和 L 来示意，这是为了和后面的内容放弃一致性。此外，论文用 v 示意源节点 i，用 u 示意街坊节点 j。

5、工夫图网络

https://arxiv.org/abs/2006.10637

到目前为止所形容的网络工作在动态图上。大多数理论状况都在动态图上工作，其中节点和边在一段时间内被增加、删除或更新。工夫图网络 (TGN) 致力于间断工夫动态图(CTDG)，它能够示意为按工夫顺序排列的事件列表。

论文将事件分为两种类型: 节点级事件和交互事件。节点级事件波及一个孤立的节点(例如: 用户更新他们的个人简介)，而交互事件波及两个可能连贯也可能不连贯的节点(例如: 用户 a 转发 / 关注用户 B)。

TGN 提供了一种模块化的 CTDG 解决办法，包含以下组件:

• 音讯传递函数→孤立节点或交互节点之间的消息传递(对于任何类型的事件)。
• 音讯聚合函数→通过查看多个工夫步长的工夫邻域，而不是在给定工夫步长的部分邻域，来应用 GAT 的聚合。
• 记忆更新→记忆（Memory）容许节点具备长期依赖关系，并示意节点在潜在 (“压缩”) 空间中的历史。这个模块依据一段时间内产生的交互来更新节点的内存。
• 工夫嵌入→一种示意节点的办法，也能捕捉到工夫的实质。
• 链接预测→将事件中波及的节点的工夫嵌入通过一些神经网络来计算边缘概率(即，边缘会在将来产生吗?)。在训练过程中，咱们晓得边的存在，所以边的标签是 1，所以须要训练基于 sigmoid 的网络来像平常一样预测这个。

每当一个节点参加一个流动 (节点更新或节点间交互) 时，记忆就会更新。

对于批处理中的每个事件 1 和 2,TGN 为波及该事件的所有节点生成音讯。TGN 聚合所有工夫步长 t 的每个节点 mi 的音讯; 这被称为节点 i 的工夫邻域。而后 TGN 应用聚合音讯 mi(t)来更新每个节点 si(t)的记忆。

一旦所有节点的内存 si(t)是最新的，它就用于计算批处理中特定交互中应用的所有节点的“长期节点嵌入”zi(t)。而后将这些节点嵌入到 MLP 或神经网络中，取得每个事件产生的概率 (应用 Sigmoid 激活)。这样能够像平常一样应用二进制穿插熵(BCE) 计算损失。

总结

下面就是咱们对图神经网络的数学总结，图深度学习在解决具备相似网络结构的问题时是一个很好的工具集。它们很容易了解，咱们能够应用 PyTorch Geometric、spectral、Deep Graph Library、Jraph(jax)以及 TensorFlow-gnn 来实现。GDL 曾经显示出前景，并将持续作为一个畛域倒退。

https://avoid.overfit.cn/post/cba88e0b599d439cbe0a5b7ede75f6dc

作者：Rishabh Anand