图神经网络

1. 什么是图？

图的定义大家应该都比较了解了，按照数据结构里面的图来说，图就是由顶点和边构成的网络，能够用于表示实体之间的多对多的关系。
首先直观的了解一下什么是图，一个简单的图如下所示：

其中的圆圈就是图的顶点，两个圆圈之间的连接线就是图的边。如果我们在这些连接线上加上权重和方向，为顶点附上具体的值。这个图就如下所示：

接下来我们理性的分析一下图的构造，以及如何构造一个图结构。
定义：

• 顶点。属性：当前节点表示、邻居的数量、出度、入度等
  
• 边。属性：方向、权重
  
• 全图。属性：节点数量、最长路径
  

图的公式定义：我们用$G=(V,E)$来表示图，其中$V$代表图中的顶点，$E$表示图中的边，$v_i\in V$表示其中的某个节点，$e_{ij}=(v_i,v_j)\in E$代表从图中节点$v_i$到$v_j$的边，$N(v)=\{u\in V(v,u)\in E\}$代表了点$v$的邻居节点的集合，$A$代表图的邻接矩阵，那么

$$A_{ij}=\begin{cases} 1,& e_{ij}\in E;\\ 0,& e_{ij}\notin E; \end{cases}$$

$X\in R^{n*d}$代表节点特征矩阵，其中$X_v \in R^d$表示节点$V$的特征向量，$X^e\in R^{m*c}$代表边特征矩阵，其中$X^e_{v,u} \in R^c$表示边$e(v,u)$的特征向量。
介绍完图的基本定义，我们在看看图的一些特例定义：
有向图公式定义：有向图是所有边都从一个节点指向另一个节点的图。无向图是有向图的一种特殊情况，在有向图中，如果两个节点是连通的。则存在一对反向边。一个图是无向的当且仅当邻接矩阵是对称的。

时空图公式定义：时空图是节点属性随时间动态变化的属性图，定义如下：$G^t=(V,E,X^t)$，其中$X^t\in R^{n*d}$表示$t$时刻下图的节点特征矩阵。

2. 典型的神经网络

介绍完图的基本定义，我们在看看什么是神经网络。之前我们有介绍到，目前神经网络结构各式各样的花里胡哨，简直数不清。但是这些神经网络基本都是别人有所改进的，最基本的神经网络结构主要分为三种：前馈神经网络、循环神经网络、对称连接网络。这里面最有代表性的四种神经网络是：卷积神经网络（CNN）、循环神经网络（RNN）、深度信念网络（DBN）、生成对抗网络（GAN）。
首先我们这里分别简要介绍一下三种神经网络结构：

• 前馈神经网络：这是实际应用中最常见的神经网络类型。第一层是输入，最后一层是输出。如果有多个隐藏层，我们称之为“深度”神经网络。他们计算出一系列改变样本相似性的变换。各层神经元的活动是前一层活动的非线性函数。
• 循环神经网络：循环网络在他们的连接图中定向了循环，这意味着你可以按照箭头回到你开始的地方。他们可以有复杂的动态，使其很难训练。他们更具有生物真实性。
  循环网络的目的使用来处理序列数据。在传统的神经网络模型中，是从输入层到隐含层再到输出层，层与层之间是全连接的，每层之间的节点是无连接的。但是这种普通的神经网络对于很多问题却无能无力。例如，你要预测句子的下一个单词是什么，一般需要用到前面的单词，因为一个句子中前后单词并不是独立的。
  循环神经网络，即一个序列当前的输出与前面的输出也有关。具体的表现形式为网络会对前面的信息进行记忆并应用于当前输出的计算中，即隐藏层之间的节点不再无连接而是有连接的，并且隐藏层的输入不仅包括输入层的输出还包括上一时刻隐藏层的输出。
• 对称连接网络：对称连接网络有点像循环网络，但是单元之间的连接是对称的（它们在两个方向上权重相同）。比起循环网络，对称连接网络更容易分析。这个网络中有更多的限制，因为它们遵守能量函数定律。没有隐藏单元的对称连接网络被称为“Hopfield 网络”。有隐藏单元的对称连接的网络被称为玻尔兹曼机。

然后我们简单介绍一下四种常见神经网络：

• 卷积神经网络。谈到机器学习，我们往往还会跟上一个词语，叫做模式识别，但是真实环境中的模式识别往往会出现各种问题。比如：
  图像分割：真实场景中总是掺杂着其它物体。很难判断哪些部分属于同一个对象。对象的某些部分可以隐藏在其他对象的后面。
  物体光照：像素的强度被光照强烈影响。
  图像变形：物体可以以各种非仿射方式变形。例如，手写也可以有一个大的圆圈或只是一个尖头。
  情景支持：物体所属类别通常由它们的使用方式来定义。例如，椅子是为了让人们坐在上面而设计的，因此它们具有各种各样的物理形状。
  卷积神经网络与普通神经网络的区别在于，卷积神经网络包含了一个由卷积层和子采样层构成的特征抽取器。在卷积神经网络的卷积层中，一个神经元只与部分邻层神经元连接。在CNN的一个卷积层中，通常包含若干个特征平面(featureMap)，每个特征平面由一些矩形排列的的神经元组成，同一特征平面的神经元共享权值，这里共享的权值就是卷积核。卷积核一般以随机小数矩阵的形式初始化，在网络的训练过程中卷积核将学习得到合理的权值。共享权值（卷积核）带来的直接好处是减少网络各层之间的连接，同时又降低了过拟合的风险。子采样也叫做池化（pooling），通常有均值子采样（mean pooling）和最大值子采样（max pooling）两种形式。子采样可以看作一种特殊的卷积过程。卷积和子采样大大简化了模型复杂度，减少了模型的参数。
  卷积神经网络由三部分构成。第一部分是输入层，主要用于将数据反映到神经网络结构中。第二部分由n个卷积层和池化层的组合组成，这一层就是深度学习种自动捕捉特征的层，类似于机器学习中的特征工程。第三部分由一个全连结的多层感知机分类器构成，这部分就是通过特征进行全连接分类，类似于机器学习中的分类算法。
  我们这里以AlexNet为例：
  
  输入：224×224大小的图片，3通道
  第一层卷积：11×11大小的卷积核96个，每个GPU上48个。
  第一层max-pooling：2×2的核。
  第二层卷积：5×5卷积核256个，每个GPU上128个。
  第二层max-pooling：2×2的核。
  第三层卷积：与上一层是全连接，3*3的卷积核384个。分到两个GPU上个192个。
  第四层卷积：3×3的卷积核384个，两个GPU各192个。该层与上一层连接没有经过pooling层。
  第五层卷积：3×3的卷积核256个，两个GPU上个128个。
  第五层max-pooling：2×2的核。
  第一层全连接：4096维，将第五层max-pooling的输出连接成为一个一维向量，作为该层的输入。
  第二层全连接：4096维
  Softmax层：输出为1000，输出的每一维都是图片属于该类别的概率。
  卷积神经网络在模式识别领域有着重要应用，当然这里只是对卷积神经网络做了最简单的讲解，卷积神经网络中仍然有很多知识，比如局部感受野，权值共享，多卷积核等内容，后续有机会再进行分享。
• 循环神经网络
  传统的神经网络对于很多问题难以处理，比如你要预测句子的下一个单词是什么，一般需要用到前面的单词，因为一个句子中前后单词并不是独立的。RNN之所以称为循环神经网路，即一个序列当前的输出与前面的输出也有关。具体的表现形式为网络会对前面的信息进行记忆并应用于当前输出的计算中，即隐藏层之间的节点不再无连接而是有连接的，并且隐藏层的输入不仅包括输入层的输出还包括上一时刻隐藏层的输出。理论上，RNN能够对任何长度的序列数据进行处理。
  这是一个简单的RNN的结构，可以看到隐藏层自己是可以跟自己进行连接的。
  
  那么RNN为什么隐藏层能够看到上一刻的隐藏层的输出呢，其实我们把这个网络展开来开就很清晰了。
  
  这个网络在$t$时刻接收到输入$x_t$之后，隐藏层的值是$s_t$,输出值是$o_t$,关键一点是，$s_t$的值不仅仅取决于$x_t$，还取决于$s_{t-1}$。即：

$$o_t=g(Vs_t) \tag{1}$$

$$s_t = f(Ux_t+Ws_{t-1}) \tag{2}$$

式1是输出层的计算公式，输出层是一个全连接层，也就是它的每个节点都和隐藏层的每个节点相连。$V$是输出层的权重矩阵，$g$是激活函数。式2是隐藏层的计算公式，它是循环层。$U$是输入$x$的权重矩阵，$W$是上一次的值$S_{t-1}$作为这一次的输入的权重矩阵，$f$是激活函数。
从上面的公式我们可以看出，循环层和全连接层的区别就是循环层多了一个权重矩阵 $W$。
如果反复把式2带入到式1，我们将得到：

$$\begin{aligned} o_t&=g(Vs_t)\\ &=Vf(Ux_t+Ws_{t-1})\\ &=Vf(Ux_t+Wf(Ux_{t-1}+Ws_{t-2}))\\ &=Vf(Ux_t+Wf(Ux_{t-1}+Wf(Ux_{t-2}+Ws_{t-3})))\\ &=Vf(Ux_t+Wf(Ux_{t-1}+Wf(Ux_{t-2}+Wf(Ux_{t-3}+\cdot\cdot\cdot)))) \end{aligned}$$

从上面可以看出，循环神经网络的输出值，是受前面历次输入值$x_t$、$x_{t-1}$、$x_{t-2}$、$x_{t-3}$、$x_{t-4}$…影响的，这就是为什么循环神经网络可以往前看任意多个输入值的原因。

• 深度信念网络
  在讲DBN之前，我们需要对DBN的基本组成单位有一定的了解，那就是RBM，受限玻尔兹曼机。
  首先什么是玻尔兹曼机？
  
  如图所示为一个玻尔兹曼机，其蓝色节点为隐层，白色节点为输入层。
  玻尔兹曼机和递归神经网络相比，区别体现在以下几点：
  1、递归神经网络本质是学习一个函数，因此有输入和输出层的概念，而玻尔兹曼机的用处在于学习一组数据的“内在表示”，因此其没有输出层的概念。
  2、递归神经网络各节点链接为有向环，而玻尔兹曼机各节点连接成无向完全图。
  而受限玻尔兹曼机是什么呢？
  最简单的来说就是加入了限制，这个限制就是将完全图变成了二分图。即由一个显层和一个隐层构成，显层与隐层的神经元之间为双向全连接。
  
  $h$表示隐藏层，$v$表示显层
  在RBM中，任意两个相连的神经元之间有一个权值$w$表示其连接强度，每个神经元自身有一个偏置系数$b$（对显层神经元）和$c$（对隐层神经元）来表示其自身权重。
  具体的公式推导在这里就不展示了
  DBN是一个概率生成模型，与传统的判别模型的神经网络相对，生成模型是建立一个观察数据和标签之间的联合分布，对$P(\text{Observation}|\text{Label})$和 $P(\text{Label}|\text{Observation})$都做了评估，而判别模型仅仅而已评估了后者，也就是$P(\text{Label}|\text{Observation})$。既可以用于非监督学习，类似于一个自编码机；也可以用于监督学习，作为分类器来使用。
  DBN由多个限制玻尔兹曼机（Restricted Boltzmann Machines）层组成，一个典型的神经网络类型如图所示。这些网络被“限制”为一个可视层和一个隐层，层间存在连接，但层内的单元间不存在连接。隐层单元被训练去捕捉在可视层表现出来的高阶数据的相关性。
  
  很多的情况下，DBN是作为无监督学习框架来使用的，并且在语音识别中取得了很好的效果。
  若想将DBM改为监督学习，方式有很多，比如在每个RBM中加上表示类别的神经元，在最后一层加上softmax分类器。也可以将DBM训出的$W$看作是NN的pre-train，即在此基础上通过BP算法进行fine-tune。实际上，前向的算法即为原始的DBN算法，后项的更新算法则为BP算法，这里，BP算法可以是最原始的BP算法，也可以是自己设计的BP算法。
• 生成对抗网络
  生成对抗网络的目标在于生成，我们传统的网络结构往往都是判别模型，即判断一个样本的真实性。而生成模型能够根据所提供的样本生成类似的新样本，注意这些样本是由计算机学习而来的。
  GAN一般由两个网络组成，生成模型网络，判别模型网络。
  生成模型 $G$ 捕捉样本数据的分布，用服从某一分布（均匀分布，高斯分布等）的噪声 $z$ 生成一个类似真实训练数据的样本，追求效果是越像真实样本越好；判别模型 $D$ 是一个二分类器，估计一个样本来自于训练数据（而非生成数据）的概率，如果样本来自于真实的训练数据，$D$ 输出大概率，否则，$D$ 输出小概率。
  举个例子：生成网络 $G$ 好比假币制造团伙，专门制造假币，判别网络 $D$ 好比警察，专门检测使用的货币是真币还是假币，$G$ 的目标是想方设法生成和真币一样的货币，使得 $D$ 判别不出来，$D$ 的目标是想方设法检测出来 $G$ 生成的假币。
  在训练的过程中固定一方，更新另一方的网络权重，交替迭代，在这个过程中，双方都极力优化自己的网络，从而形成竞争对抗，直到双方达到一个动态的平衡（纳什均衡），此时生成模型 G 恢复了训练数据的分布（造出了和真实数据一模一样的样本），判别模型再也判别不出来结果，准确率为 50%。
  下面展示一个cDCGAN的例子
  生成网络
  
  判别网络
  

3. 图神经网络

根据上述对图和神经网络的回顾，我们可以看出，图神经网络就是借助神经网络的“能力”如深度特征抽取等来处理图结构的数据，因此对于图神经网络，其直观的结构应该如下图：

那我们为什么需要图神经网络呢？
近年来，深度学习已经彻底改变了许多机器学习任务，从图像分类和视频处理，到语音识别和自然语言理解，这些任务中的数据通常表示在欧几里得空间中。然而，在越来越多的应用程序中，数据是从非欧几里得域生成的，并表示为具有复杂关系和对象之间相互依赖的图形。图数据的复杂性给现有的机器学习算法带来了巨大的挑战。下图左为图像（欧几里得空间），右为图（非欧几里得空间）。

传统的神经网络结构如CNN、RNN等都是接受欧几里得空间的数据作为输入，他们无法处理非欧几里得空间的数据结构，比如图和流行结构。因此对于此类数据，图神经网络就更加适合处理。近年来图神经网络的研究热度也不断提升，如下图所示：

图结构的数据有许多，如社交网络图、交通路线图、人物关系图、分子结构图、计算结网络拓扑图等等。这些数据都可以作为图神经网络的输入。之后经过特定的神经网络结构，如MLP，CNN，RNN等的基于图结构的运算，可以完成对于图表示的分类，图的节点或边的预测等功能。

我们将图神经网络划分为五大类别，分别是：

1. 图卷积网络（Graph Convolution Networks，GCN）
2. 图注意力网络（Graph Attention Networks）
3. 图自编码器（ Graph Autoencoders）
4. 图生成网络（ Graph Generative Networks）
5. 图时空网络（Graph Spatial-temporal Networks）

后续我们会逐一介绍这些图神经网络。

4. 图神经网络应用

将图结构和节点内容信息作为模型的输入，GNNs的输出可以通过以下机制之一专注于不同的图分析任务:

• Node-level输出用于点回归和分类任务。给定一个带有部分节点被标记而其他节点未被标记的单个网络，ConvGNN 可以学习一个健壮的模型，该模型可以有效地识别未标记节点的类标签。 为此，可以通过堆叠几个图卷积层，然后堆叠用于多类分类的 softmax 层，来构建端到端框架。
• Edge-level输出与边分类和链路预测任务相关。边缘水平推理的一个例子是图像场景理解。除了识别图像中的物体，深度学习模型还可以用来预测它们之间的关系。我们可以将其描述为边级分类:给定表示图像中对象的节点，我们希望预测哪些节点共享边或该边的值。如果我们希望发现实体之间的联系，我们可以考虑图是完全连通的，并基于它们的预测值修剪边缘以达到稀疏图。如下所示
  
  先通过语义分割将人物、背景等分离，然后抽取人物之间的关系。可以看出，人物与腿之间的关系是站立，观众与运动员之间的关系是watching，，，等等。
• Graph-level输出和图分类任务相关，比如图表示。图级分类旨在预测整个图的类标签。 可以通过图卷积层，图池化层和读出层的组合来实现此任务的端到端学习。 图卷积层负责精确的高级节点表示，而图池化层则充当下采样的角色，从而每次将每个图都粗化为子结构。 读出层将每个图的节点表示折叠为图表示。 通过将多层感知器和 softmax 层应用于图表示，我们可以建立一个用于图分类的端到端框架。
• Graph embedding。当图中没有类标签可用时，我们可以在端到端框架中以纯粹无监督的方式学习图嵌入。这些算法以两种方式利用边级信息。一种简单的方法是采用自动编码器框架，其中编码器使用图卷积层将图嵌入到潜在表示中，在该表示上使用解码器来重构图结构。另一种流行的方法是利用负采样方法，该方法将一部分节点对采样为负对，而图中具有链接的现有节点对为正对。 然后在卷积层之后应用逻辑回归层进行端到端学习。

4.1 图分类 – 计算机视觉、化学

我们知道很多有机物或者化合物的分子结构都是可以用图结构来表示的，比如下图的4-nitroindole，该GNN的作用是训练一个图神经网络，接收一个分子结构来判断该分子结构会不会导致发生突变。在训练的过程中如果有现存的已标注的可导致发生突变的分子结构，我们就可以训练该图神经网络，然后用他来预测一个新的未知的分子会不会导致突变。

4.2 图生成

我们知道在图像和语言的领域里分别有embedding和generation技术，比如常见的图像和语言生成技术，比如动态静态的预训练和词嵌入技术。相应的在图领域，我们也有图的嵌入表示比如graph embedding representation和图的generation技术。比如下图的graphvae，变分图自编码器就是一个图生成模型，其主要是为图中节点找寻合适的 Embedding 向量，并通过 Embedding 向量实现图重构。其中获取到的节点 Embedding 可以用于支撑下游任务。比如在新的分子结构生成发现中可以使用该技术来加快分子发现速度。

4.3 社交网络分析–推荐系统

在社交网络分析中，实体之间的关系往往会是非常重要的特征，图结构就能很好的表示这种关系特征。如下图的社交网络图中，每个实体的关系可以用边来描述，这样在进行实体分类或者关系分类时，利用图数据结构，完成特定任务的标注，就可以训练出一个图神经网络来完成此类任务。

4.4 网络拓扑分析–交通系统

网络的拓扑天然就是图结构的表示，计算机网络中的路由技术就是以图轮为基础的算路技术。同时网络中每两个节点之间也会有时延，丢包，抖动等网络KPI信息。这些点对之间的KPI往往是动态变化的，这就影响到了实时路由决策和优化的问题。比如当前链路的时延或者丢包过大，路由算法就需要选择新的路径进行数据包传递。图神经网络在这个问题中就可以接收底层的网络拓扑、网络配置信息和流量矩阵信息来实时预测每一个点对，每一条流的实验丢包抖动，这样就可以更好的配合路由和优化算法，使能网络的自动驾驶。
GNN也与LSTM和CNN一起使用，以预测一个时间间隔内特定位置的出租车需求数量。它考虑了过去的出租车需求，天气数据和位置信息。

4.5 自然语言处理

可以将每个单词表示成顶点，词与词之间是一条有向边

参考

1. 数据结构 图 https://blog.csdn.net/cmzglj/article/details/115449433
2. 图神经网络，这到底是个什么？ https://zhuanlan.zhihu.com/p/353692130
3. 一文看懂四种基本的神经网络架构 https://www.jianshu.com/p/546dc40b52c8
4. 限制玻尔兹曼机（Restricted Boltzmann Machine）学习笔记（一）https://blog.csdn.net/weixin_41036461/article/details/79802630
5. 图神经网络（Graph Neural Networks，GNN）综述 https://zhuanlan.zhihu.com/p/75307407?from_voters_page=true