图神经网络|什么是机器学习、深度学习、图神经网络（）算法|python|神经网络

文章图片

人工智能是追求目标，机器学习是实现手段，深度学习是其中一种方法。

1 机器学习机器学习是一类算法的总称，这些算法企图从大量历史数据中挖掘出其中隐含的规律，并用于预测或者分类，更具体的说，机器学习可以看作是寻找一个函数，输入是样本数据，输出是期望的结果，只是这个函数过于复杂，以至于不太方便形式化表达。需要注意的是，机器学习的目标是使学到的函数很好地适用于“新样本”，而不仅仅是在训练样本上表现很好。学到的函数适用于新样本的能力，称为泛化（Generalization）能力。
1.1 机器学习步骤通常学习一个好的函数，分为以下三步：
1、选择一个合适的模型，这通常需要依据实际问题而定，针对不同的问题和任务需要选取恰当的模型，模型就是一组函数的集合。
2、判断一个函数的好坏，这需要确定一个衡量标准，也就是我们通常说的损失函数（Loss Function），损失函数的确定也需要依据具体问题而定，如回归问题一般采用欧式距离，分类问题一般采用交叉熵代价函数。
3、找出“最好”的函数，如何从众多函数中最快的找出“最好”的那一个，这一步是最大的难点，做到又快又准往往不是一件容易的事情。常用的方法有梯度下降算法，最小二乘法等和其他一些技巧（tricks）。
学习得到“最好”的函数后，需要在新样本上进行测试，只有在新样本上表现很好，才算是一个“好”的函数。

文章图片

1.2 机器学习路线图机器学习是一个庞大的家族体系，涉及众多算法，任务和学习理论，下图是机器学习的学习路线图。

文章图片

图中蓝色代表不同的学习理论，橙色代表任务，绿色代表方法。
1、按任务类型分，机器学习模型可以分为回归模型、分类模型和结构化学习模型。回归模型又叫预测模型，输出是一个不能枚举的数值；分类模型又分为二分类模型和多分类模型，常见的二分类问题有垃圾邮件过滤，常见的多分类问题有文档自动归类；结构化学习模型的输出不再是一个固定长度的值，如图片语义分析，输出是图片的文字描述。
2、从方法的角度分，可以分为线性模型和非线性模型，线性模型较为简单，但作用不可忽视，线性模型是非线性模型的基础，很多非线性模型都是在线性模型的基础上变换而来的。非线性模型又可以分为传统机器学习模型，如SVM，KNN，决策树等，和深度学习模型。
3、按照学习理论分，机器学习模型可以分为有监督学习，半监督学习，无监督学习，迁移学习和强化学习。当训练样本带有标签时是有监督学习；训练样本部分有标签，部分无标签时是半监督学习；训练样本全部无标签时是无监督学习。迁移学习就是就是把已经训练好的模型参数迁移到新的模型上以帮助新模型训练。强化学习是一个学习最优策略（policy），可以让本体（agent）在特定环境（environment）中，根据当前状态（state），做出行动（action），从而获得最大回报（reward）。强化学习和有监督学习最大的不同是，每次的决定没有对与错，而是希望获得最多的累计奖励。
*参考资料：https://blog.csdn.net/hohaizx/category_7207750.html

2 深度学习深度学习(DL, Deep Learning)是机器学习(ML, Machine Learning)领域中一个新的研究方向，它被引入机器学习使其更接近于最初的目标——人工智能(AI, Artificial Intelligence)。
深度学习是学习样本数据的内在规律和表示层次，这些学习过程中获得的信息对诸如文字，图像和声音等数据的解释有很大的帮助。它的最终目标是让机器能够像人一样具有分析学习能力，能够识别文字、图像和声音等数据。深度学习是一个复杂的机器学习算法，在语音和图像识别方面取得的效果，远远超过先前相关技术。
深度学习算法试图从数据中学习高级功能，这是深度学习的一个非常独特的部分。因此，减少了为每个问题开发新特征提取器的任务。适合用在难提取特征的图像、语音、自然语言处理领域。

2.1 深度学习与机器学习的区别
文章图片

1.特征提取方面

机器学习的特征工程步骤是要靠手动完成的，而且需要大量领域专业知识。
深度学习通常由多个层组成，它们通常将更简单的模型组合在一起，将数据从一层传递到另一层来构建更复杂的模型。通过训练大量数据自动得出模型，不需要人工特征提取环节。

2. 数据量和计算性能要求
深度学习需要的执行时间远多少于机器学习，深度学习参数往往很庞大，需要通过大量数据的多次优化来训练参数。
第一、深度学习需要大量的训练数据集；第二、训练深度神经网络需要大量的算力，可能要花费数天、甚至数周的时间，才能使用数百万张图像的数据集训练出一个深度网络。所以深度学习通常需要强大的GPU服务器来进行计算，需要全面管理的分布式训练与预测服务——比如谷歌 TensorFlow 云机器学习平台。
3. 算法代表

机器学习
- 朴素贝叶斯、决策树等
深度学习
- 神经网络

2.2 深度学习模型、训练过程和应用简述 1. 典型的深度学习模型
卷积神经网络( convolutional neural network)、深度信任网络模型（DBN）、堆栈自编码网络(stacked auto-encoder network)模型等。
2. 深度学习训练过程包括有自下上升的非监督学习和自顶向下的监督学习。
（1）自下上升的非监督学习
就是从底层开始，一层一层地往顶层训练。采用无标定数据（有标定数据也可）分层训练各层参数，这一步可以看作是一个无监督训练过程，这也是和传统神经网络区别最大的部分，可以看作是特征学习过程。具体的，先用无标定数据训练第一层，训练时先学习第一层的参数，这层可以看作是得到一个使得输出和输入差别最小的三层神经网络的隐层，由于模型容量的限制以及稀疏性约束，使得得到的模型能够学习到数据本身的结构，从而得到比输入更具有表示能力的特征；在学习得到n-l层后，将n-l层的输出作为第n层的输入，训练第n层，由此分别得到各层的参数。 [6]

（2）自顶向下的监督学习
就是通过带标签的数据去训练，误差自顶向下传输，对网络进行微调。基于第一步得到的各层参数进一步优调整个多层模型的参数，这一步是一个有监督训练过程。第一步类似神经网络的随机初始化初值过程，由于第一步不是随机初始化，而是通过学习输入数据的结构得到的，因而这个初值更接近全局最优，从而能够取得更好的效果。所以深度学习的良好效果在很大程度上归功于第一步的特征学习的过程。
3. 应用
计算机视觉、语音识别、自然语言处理等其他领域。

*参考资料：
张荣, 李伟平, 莫同. 深度学习研究综述[J]. 信息与控制, 2018, v.47(04):5-17+30.
郭元祥. 深度学习:本质与理念[J]. 新教师, 2017, 000(007):11-14.

3 图神经网络图是一种数据结构，它对一组对象（节点）及其关系（边）进行建模。人们对深度学习方法在图数据上的扩展越来越感兴趣。在深度学习的成功推动下，研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想，定义和设计了用于处理图数据的神经网络结构，由此一个新的研究热点——“图神经网络（Graph Neural Networks，GNN）”应运而生。
近年来图神经网络受到大家越来越多的关注，在文本分类(Text classification)，序列标注（Sequence labeling）, 神经机器翻译（Neural machine translation）,关系抽取（Relation extraction），事件抽取（Event extraction）, 图像分类（Image Classification），视觉推理（Visual Reasoning），语义分割（Semantic Segmentation）等等领域都有了一些应用。图神经网络（GNN）是一类基于深度学习的处理图域信息的方法。由于其较好的性能和可解释性，GNN 最近已成为一种广泛应用的图分析方法。

文章图片

3.1 有哪些图神经网络？在本文中，我们将图神经网络划分为五大类别，分别是：图卷积网络（Graph Convolution Networks，GCN）、图注意力网络（Graph Attention Networks）、图自编码器（ Graph Autoencoders）、图生成网络（ Graph Generative Networks）和图时空网络（Graph Spatial-temporal Networks）。
符号定义：

文章图片

3.2 图卷积网络(Graph Convolution Networks,GCN) 图卷积网络将卷积运算从传统数据（例如图像,结构化数据）推广到图数据（非结构化数据）。其核心思想是学习一个函数映射

文章图片
,通过该映射图中的节点

文章图片
可以聚合它自己的特征(向量)

文章图片
与它邻居的特征

文章图片
(

文章图片
)来生成节点

文章图片
的新表示。图卷积网络是许多复杂图神经网络模型的基础，包括基于自动编码器的模型、生成模型和时空网络等。下图直观地展示了图神经网络学习节点表示的步骤。

文章图片

GCN方法又可以分为两大类，基于频谱（spectral-based）和基于空间（spatial-based）。基于频谱的方法从图信号处理的角度引入滤波器来定义图卷积，其中图卷积操作被解释为从图信号中去除噪声。基于空间的方法将图卷积表示为从邻域聚合特征信息，当图卷积网络的算法在节点层次运行时，图池化模块可以与图卷积层交错，将图粗化为高级子结构。如下图所示，这种架构设计可用于提取图的各级表示和执行图分类任务。

文章图片

在下面，我们分别简单介绍了基于频谱的GCN和基于空间的GCN。

Spectral-based Graph Convolutional Networks

在大学里学过《数字信号处理》这门课程的朋友应该会记得，在这门课上我们通过引入傅里叶变换将时域信号转换到频域进行分析，进而我们完成一些我们在时域上无法完成的操作，基于频谱的图卷积网络的核心思想正是来源于此。
在基于频谱的图神经网络中，图被假定为无向图，无向图的一种鲁棒数学表示是正则化(规范化)图拉普拉斯矩阵，即

文章图片

其中，A为图的邻接矩阵，D为对角矩阵(度矩阵)：

文章图片

正则化图拉普拉斯矩阵具有实对称半正定的性质。利用这个性质，正则化拉普拉斯矩阵可以分解为:

文章图片

，其中:

文章图片

U是由L的特征向量构成的矩阵，

文章图片
是对角矩阵，对角线上的值为L的特征值。正则化拉普拉斯矩阵的特征向量构成了一组正交基(U中的特征向量/每一列是正交的)。
在图信号处理过程中，一个图的信号：

文章图片

是一个由图的各个节点组成的特征向量，

文章图片
表示第i个节点。
对图X的傅里叶变换由此被定义为：

文章图片

傅里叶反变换则为：

文章图片

其中，

文章图片
为傅立叶变换后的结果。
为了更好地理解图的傅里叶变换，从它的定义我们可以看出，它确实将输入图信号投影到正交空间，在正交空间中，基由正则化图拉普拉斯矩阵L的特征向量构成。
转换后得到的信号

文章图片
的元素是新空间(正交空间)中图信号的坐标，因此原来的输入信号可以表示为：

文章图片

正是傅里叶反变换的结果。（上式与

文章图片
等价）
现在我们可以来定义对输入信号X的图卷积操作了：

文章图片

其中，

文章图片
是我们定义的滤波器；

文章图片
表示Hadamard product（对应位置元素相乘）。
假如我们定义这样一个滤波器：

文章图片

那么我们的图卷积操作可以简化表示为：

文章图片

基于频谱的图卷积网络都遵循这样的模式，它们之间关键的不同点在于选择的滤波器不同。
现有的基于频谱的图卷积网络模型有以下这些：Spectral CNN、Chebyshev Spectral CNN (ChebNet)、Adaptive Graph Convolution Network (AGCN)。
基于频谱的图卷积神经网络方法的一个常见缺点是，它们需要将整个图加载到内存中以执行图卷积，这在处理大型图时是不高效的。

Spatial-based Graph Convolutional Networks

模拟传统卷积神经网络对图像的卷积运算，基于空间的方法基于节点的空间关系定义图卷积。为了将图像与图关联起来，可以将图像视为图的特殊形式，每个像素代表一个节点，如下图a所示，每个像素直接连接到其附近的像素。通过一个3×3的窗口，每个节点的邻域是其周围的8个像素。这八个像素的位置表示一个节点的邻居的顺序。然后，通过对每个通道上的中心节点及其相邻节点的像素值进行加权平均，对该3×3窗口应用一个滤波器。由于相邻节点的特定顺序，可以在不同的位置共享可训练权重。同样，对于一般的图，基于空间的图卷积将中心节点表示和相邻节点表示进行聚合，以获得该节点的新表示，如图b所示。

文章图片

一种共同的实践是将多个图卷积层叠加在一起。根据卷积层叠的不同方法，基于空间的GCN可以进一步分为两类：recurrent-based和composition-based的空间GCN。recurrent-based的方法使用相同的图卷积层来更新隐藏表示(不停的循环)，composition-based的方法使用不同的图卷积层来更新隐藏表示（串联）。下图说明了这种差异。

文章图片

Comparison Between Spectral and Spatial Methods

作为最早的图卷积网络，基于频谱的模型在许多与图相关的分析任务中取得了令人印象深刻的结果。这些模型在图信号处理方面有一定的理论基础。通过设计新的图信号滤波器，我们可以从理论上设计新的图卷积网络。然而，基于频谱的模型有几个缺点。我们从效率、通用性和灵活性三个方面来说明这一点。
在效率方面，基于频谱的模型的计算成本随着图的大小而急剧增加，因为它们要么需要执行特征向量计算，要么同时处理整个图，这使得它们很难适用于大型图。基于空间的模型有潜力处理大型图，因为它们通过聚集相邻节点直接在图域中执行卷积。计算可以在一批节点中执行，而不是在整个图中执行。当相邻节点数量增加时，可以引入采样技术来提高效率。
在一般性方面，基于频谱的模型假定一个固定的图，使得它们很难在图中添加新的节点。另一方面，基于空间的模型在每个节点本地执行图卷积，可以轻松地在不同的位置和结构之间共享权重。
在灵活性方面，基于频谱的模型仅限于在无向图上工作，有向图上的拉普拉斯矩阵没有明确的定义，因此将基于频谱的模型应用于有向图的唯一方法是将有向图转换为无向图。基于空间的模型更灵活地处理多源输入，这些输入可以合并到聚合函数中。因此，近年来空间模型越来越受到关注。

3.3 图注意力网络(Graph Attention Networks) 注意力机制如今已经被广泛地应用到了基于序列的任务中，它的优点是能够放大数据中最重要的部分的影响。这个特性已经被证明对许多任务有用，例如机器翻译和自然语言理解。如今融入注意力机制的模型数量正在持续增加，图神经网络也受益于此，它在聚合过程中使用注意力，整合多个模型的输出，并生成面向重要目标的随机行走。在本节中，我们将讨论注意力机制如何在图结构数据中使用。

Graph Attention Network(GAT)

图注意力网络（GAT）是一种基于空间的图卷积网络，它的注意机制是在聚合特征信息时，将注意机制用于确定节点邻域的权重。GAT的图卷积运算定义为：

文章图片

其中α（·）是一个注意力函数，它自适应地控制相邻节点j对节点i的贡献。为了学习不同子空间中的注意力权重，GAT还可以使用多注意力：

文章图片

Gated Attention Network(GAAN)

门控注意力网络（GAAN）还采用了多头注意力机制来更新节点的隐藏状态。然而，GAAN并没有给每个head部分配相等的权重，而是引入了一种自注意机制，该机制为每个head计算不同的权重。更新规则定义为，

文章图片

其中

文章图片
是反馈神经网络，而

文章图片
是第k个注意力head的注意力权重.

Graph Attention Model（GAM）

图形注意力模型（GAM）提供了一个循环神经网络模型，以解决图形分类问题，通过自适应地访问一个重要节点的序列来处理图的信息。GAM模型被定义为：

文章图片

其中，

文章图片
是一个LSTM网络，

文章图片
是一个step network，它会优先访问当前节点

文章图片
优先级高的邻居并将它们的信息进行聚合。
除了在聚集特征信息时将注意力权重分配给不同的邻居节点，还可以根据注意力权重将多个模型集合起来，以及使用注意力权重引导随机行走。尽管GAT和GAAN在图注意网络的框架下进行了分类，但它们也可以同时被视为基于空间的图形卷积网络。GAT和GAAN的优势在于，它们能够自适应地学习邻居的重要性权重。然而，计算成本和内存消耗随着每对邻居之间的注意权重的计算而迅速增加。

3.4 Graph Autoencoders 图自动编码器是一类图嵌入方法，其目的是利用神经网络结构将图的顶点表示为低维稠密向量。典型的解决方案是利用多层感知机作为编码器来获取节点嵌入，其中解码器重建节点的邻域统计信息，如positive pointwise mutual information （PPMI）或一阶和二阶近似值。最近，研究人员已经探索了将GCN作为编码器的用途，将GCN与GAN结合起来，或将LSTM与GAN结合起来设计图自动编码器。我们将首先回顾基于GCN的AutoEncoder，然后总结这一类别中的其他变体。
目前基于GCN的自编码器的方法主要有：Graph Autoencoder (GAE)和Adversarially Regularized Graph Autoencoder (ARGA)
图自编码器的其它变体有：
Network Representations with Adversarially Regularized Autoencoders (NetRA)
Deep Neural Networks for Graph Representations (DNGR)
Structural Deep Network Embedding (SDNE)
Deep Recursive Network Embedding (DRNE)
DNGR和SDNE学习仅给出拓扑结构的节点嵌入，而GAE、ARGA、NetRA、DRNE用于学习当拓扑信息和节点内容特征都存在时的节点嵌入。图自动编码器的一个挑战是邻接矩阵A的稀疏性，这使得解码器的正条目数远远小于负条目数。为了解决这个问题，DNGR重构了一个更密集的矩阵，即PPMI矩阵，SDNE对邻接矩阵的零项进行惩罚，GAE对邻接矩阵中的项进行重加权，NetRA将图线性化为序列。

3.5 Graph Generative Networks 图生成网络的目标是在给定一组观察到的图的情况下生成新的图。图生成网络的许多方法都是特定于领域的。例如，在分子图生成中，一些工作模拟了称为SMILES的分子图的字符串表示。在自然语言处理中，生成语义图或知识图通常以给定的句子为条件。最近，人们提出了几种通用的方法。一些工作将生成过程作为节点和边的交替形成因素，而另一些则采用生成对抗训练。这类方法要么使用GCN作为构建基块，要么使用不同的架构。
基于GCN的图生成网络主要有：
Molecular Generative Adversarial Networks (MolGAN)：将relational GCN、改进的GAN和强化学习（RL）目标集成在一起，以生成具有所需属性的图。GAN由一个生成器和一个鉴别器组成，它们相互竞争以提高生成器的真实性。在MolGAN中，生成器试图提出一个伪图及其特征矩阵，而鉴别器的目标是区分伪样本和经验数据。此外，还引入了一个与鉴别器并行的奖励网络，以鼓励生成的图根据外部评价器具有某些属性。
Deep Generative Models of Graphs (DGMG)：利用基于空间的图卷积网络来获得现有图的隐藏表示。生成节点和边的决策过程是以整个图的表示为基础的。简而言之，DGMG递归地在一个图中产生一个节点，直到达到某个停止条件。在添加新节点后的每一步，DGMG都会反复决定是否向添加的节点添加边，直到决策的判定结果变为假。如果决策为真，则评估将新添加节点连接到所有现有节点的概率分布，并从概率分布中抽取一个节点。将新节点及其边添加到现有图形后，DGMG将更新图的表示。
其它架构的图生成网络主要有：
GraphRNN：通过两个层次的循环神经网络的深度图生成模型。图层次的RNN每次向节点序列添加一个新节点，而边层次RNN生成一个二进制序列，指示新添加的节点与序列中以前生成的节点之间的连接。为了将一个图线性化为一系列节点来训练图层次的RNN，GraphRNN采用了广度优先搜索（BFS）策略。为了建立训练边层次的RNN的二元序列模型，GraphRNN假定序列服从多元伯努利分布或条件伯努利分布。
NetGAN：Netgan将LSTM与Wasserstein-GAN结合在一起，使用基于随机行走的方法生成图形。GAN框架由两个模块组成，一个生成器和一个鉴别器。生成器尽最大努力在LSTM网络中生成合理的随机行走序列，而鉴别器则试图区分伪造的随机行走序列和真实的随机行走序列。训练完成后，对一组随机行走中节点的共现矩阵进行正则化，我们可以得到一个新的图。

3.6 Graph Spatial -Temporal Networks 图时空网络同时捕捉时空图的时空相关性。时空图具有全局图结构，每个节点的输入随时间变化。例如，在交通网络中，每个传感器作为一个节点连续记录某条道路的交通速度，其中交通网络的边由传感器对之间的距离决定。图形时空网络的目标可以是预测未来的节点值或标签，或者预测时空图标签。最近的研究仅仅探讨了GCNs的使用，GCNs与RNN或CNN的结合，以及根据图结构定制的循环体系结构。
目前图时空网络的模型主要有:
Diffusion Convolutional Recurrent Neural Network (DCRNN)
CNN-GCN
Spatial Temporal GCN (ST-GCN)
Structural-RNN

3.7 图神经网络的应用

Computer Vision

图形神经网络的最大应用领域之一是计算机视觉。研究人员在场景图生成、点云分类与分割、动作识别等多个方面探索了利用图结构的方法。
在场景图生成中，对象之间的语义关系有助于理解视觉场景背后的语义含义。给定一幅图像，场景图生成模型检测和识别对象，并预测对象对之间的语义关系。另一个应用程序通过生成给定场景图的真实图像来反转该过程。自然语言可以被解析为语义图，其中每个词代表一个对象，这是一个有希望的解决方案，以合成给定的文本描述图像。
在点云分类和分割中，点云是激光雷达扫描记录的一组三维点。此任务的解决方案使激光雷达设备能够看到周围的环境，这通常有利于无人驾驶车辆。为了识别点云所描绘的物体，将点云转换为k-最近邻图或叠加图，并利用图论进化网络来探索拓扑结构。
在动作识别中，识别视频中包含的人类动作有助于从机器方面更好地理解视频内容。一组解决方案检测视频剪辑中人体关节的位置。由骨骼连接的人体关节自然形成图表。给定人类关节位置的时间序列，应用时空神经网络来学习人类行为模式。
此外，图形神经网络在计算机视觉中应用的可能方向也在不断增加。这包括人-物交互、少镜头图像分类、语义分割、视觉推理和问答等。

Recommender Systems

基于图的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目之间的关系以及内容信息，基于图的推荐系统能够生成高质量的推荐。推荐系统的关键是评价一个项目对用户的重要性。因此，可以将其转换为一个链路预测问题。目标是预测用户和项目之间丢失的链接。为了解决这个问题，有学者提出了一种基于GCN的图形自动编码器。还有学者结合GCN和RNN，来学习用户对项目评分的隐藏步骤。

Traffic

交通拥堵已成为现代城市的一个热点社会问题。准确预测交通网络中的交通速度、交通量或道路密度，在路线规划和流量控制中至关重要。有学者采用基于图的时空神经网络方法来解决这些问题。他们模型的输入是一个时空图。在这个时空图中，节点由放置在道路上的传感器表示，边由阈值以上成对节点的距离表示，每个节点都包含一个时间序列作为特征。目标是预测一条道路在时间间隔内的平均速度。另一个有趣的应用是出租车需求预测。这有助于智能交通系统有效利用资源，节约能源。

Chemistry

在化学中，研究人员应用图神经网络研究分子的图结构。在分子图中，原子为图中的节点，化学键为图中的边。节点分类、图形分类和图形生成是分子图的三个主要任务，它们可以用来学习分子指纹、预测分子性质、推断蛋白质结构、合成化合物。

Others

除了以上四个领域外，图神经网络还已被探索可以应用于其他问题，如程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、脑网络、事件检测和组合优化。
*参考资料：https://blog.csdn.net/sdu_hao/category_9626807.html
【图神经网络|什么是机器学习、深度学习、图神经网络（）】