图深度学习(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