摘要

在过去的几年中，神经网络的兴起与应用成功推动了模式识别和数据挖掘的研究。许多曾经严重依赖于手工提取特征的机器学习任务（如目标检测、机器翻译和语音识别），如今都已被各种端到端的深度学习范式（例如卷积神经网络（CNN）、长短期记忆（LSTM）和自动编码器）彻底改变了。尽管传统的深度学习方法被应用在提取欧氏空间数据的特征方面取得了巨大的成功，但许多实际应用场景中的数据是从非欧式空间生成的，传统的深度学习方法在处理非欧式空间数据上的表现却仍难以使人满意。例如，在电子商务中，一个基于图（Graph）的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐，但图的复杂性使得现有的深度学习算法在处理时面临着巨大的挑战。这是因为图是不规则的，每个图都有一个大小可变的无序节点，图中的每个节点都有不同数量的相邻节点，导致一些重要的操作（例如卷积）在图像（Image）上很容易计算，但不再适合直接用于图。此外，现有深度学习算法的一个核心假设是数据样本之间彼此独立。然而，对于图来说，情况并非如此，图中的每个数据样本（节点）都会有边与图中其他实数据样本（节点）相关，这些信息可用于捕获实例之间的相互依赖关系。近年来，人们对深度学习方法在图上的扩展越来越感兴趣。在多方因素的成功推动下，研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想，定义和设计了用于处理图数据的神经网络结构，由此一个新的研究热点——“图神经网络（Graph Neural Networks，GNN）”应运而生。在本文中，我们将研究图和GNN的定义、应用场景、嵌入特征及简单代码实现，并概述图神经网络的一些最新应用。

一、什么是图神经网络？

1.1 什么是图？

从名词"图神经网络"我们可以看到GNN的最基本部分是图结构的形式。在计算机领域中，图被定义为具有两个部分组成的数据结构，顶点和边缘。我们可以将图G 1定义为G = VE。其中V是一组顶点，E是它们之间的边，其中术语中顶点和节点通常可以互换使用的。如果在链接图的边上有任何箭头标记，则称该图由方向依赖性，则它是有向图。如果不是，则它们是无向图。其图结构如图所示：

该图形描述了：

• V作为顶点集
• 以E为边

然后，图G =（V，E），其中V称为节点，E为边。

1.2 什么是图神经网络（GNN）？

由于图具有极强的表达能力，因此它们在机器学习领域得到了广泛的关注。每个节点都有与其相互关联的嵌入特征与嵌入方式，该嵌入定义了数据空间中的节点。图神经网络是指在图上运行的神经网络体系结构。GNN架构的主要目的是学习包含有关其邻域信息的嵌入，使用此嵌入，我们可以解决一些问题，例如标记节点，预测节点和关联边等。换句话说，图神经网络是另一类深度学习方法，旨在对图形给出的数据进行推理。

 

使用GNN神经网络结构点会添加从相邻节点收集的信息，然后最后一层结合所有这些添加的信息，并给出整体模型的预测或分类。

GNN输出执行：

1. 节点分类
2. 链接预测
3. 图分类

1.3 图神经网络的嵌入特征及方法

网络嵌入旨在将网络节点表示为低维向量表示，同时保留网络拓扑结构和节点内容信息，以便可以使用简单的现成方法轻松执行任何后续的图形分析任务，例如分类、聚类和推荐架式机器学习算法。GNN和传统神经网络嵌入之间的主要区别在于：GNN是为各种任务而设计的一组神经网络模型，因此其网络嵌入涵盖了针对同一任务的各种方法。因此，GNN可以通过GAE框架解决网络嵌入问题，同时网络嵌入包含其他非深度学习方法例如矩阵分解和随机游走。

嵌入特征之随机游走

DeepWalk是第一个以无监督学习的节点嵌入算法。它在训练过程中类似于词嵌入。它的目的是让图中的节点分布和语料库中的单词分布都遵循幂律，如下图所示：

算法包括两个步骤：

1. 在图中的节点上执行随机游走生成节点序列;

2. 运行skip-gram，根据步骤1中生成的节点序列学习每个节点的嵌入;

在随机游走过程中，下一个节点是从前一节点的邻居统一采样。然后将每个序列截短为长度为2 | w |+1的子序列，其中w表示skip-gram中的窗口大小。如果您不熟悉skip-gram，我之前的博客文章已经向您介绍它的工作原理。

在论文中，分层softmax用于解决由于节点数量庞大而导致的softmax计算成本过高的问题。为了计算每个单独输出元素的softmax值，我们必须为所有元素k计算ek。

因此，原始softmax的计算时间是 O(|V|) ，其中其中V表示图中的顶点集。

多层的softmax利用二叉树来解决softmax计算成本问题。 在二叉树中，所有叶子节点（上面所说的图中的v1，v2，... v8）都是图中的顶点。 在每个内部节点中（除了叶子节点以外的节点，也就是分枝结点），都通过一个二元分类器来决定路径的选取。 为了计算某个顶点v_k的概率，可以简单地计算沿着从根节点到叶子节点v_k的路径中的每个子路径的概率。 由于每个节点的孩子节点的概率和为1，因此在多层softmax中，所有顶点的概率之和等于1的特性仍然能够保持。如果n是叶子的数量，二叉树的最长路径由O（log（n））限定，因此，元素的计算时间复杂度将减少到O（log | V |）。

在训练DeepWalk GNN之后，模型已经学习到了每个节点的表示，如下图所示。不同的颜色在输入图中（图a）表示不同标签。 我们可以看到，在输出图中，具有相同标签的节点聚集在一起，而具有不同标签的大多数节点被正确分开。

然而，DeepWalk的主要问题是它缺乏泛化能力。每当有新节点加入到图中时，它必须重新训练模型以正确表示该节点。因此，这种GNN不适用于图中节点不断变化的动态图。

二. 图神经网络模型

 GNN模型包括四种类型：
递归图神经网络（RGNN）
卷积图神经网络（CGNN）
图形自动编码器（GAE）
时空图神经网络（STGNN）

2.1 递归图神经网络

这些神经网络旨在使用递归神经网络（RNN）学习节点表示。RGNN通过假设图中的节点不断交换消息（消息传递）来工作。这种交换一直持续到达到稳定的平衡为止.RecGNN主要是GNN的先锋作品。他们在图上的节点上反复应用相同的参数集，以提取高级节点表示形式。受计算能力的限制，较早的研究主要集中在有向无环图上。

2.2.卷积图神经网络

CGNN通过概括从网格格式到图形格式的卷积运算来工作。与RGNN相比，CGNN使用了许多层的图卷积。这有助于提取高级节点表示。

CGNN为构建其他GNN模型奠定了基础。CGNN应用程序的一个示例是 Pinterest的PinSage推荐系统。PinSage算法通过学习分别在3和180亿个节点和边上运行的图节点嵌入来工作。

2.3 图形自动编码器

 GAE是深度神经网络，可以学习生成新图。他们将节点映射到潜在向量空间。然后，他们从潜在表示中重建图信息。它们用于学习网络中的嵌入和图形的生成分布。GAE已被用来在引用网络中执行链接预测任务。这些网络包含通过引文链接在一起的文章。GAE可以将这些文章分为不同的组。

2.4 时空图神经网络

 

 

这些网络背后的思想是同时考虑空间和时间依赖性。在当前的研究中，图卷积捕获了空间依赖性。CNN或RNN捕获时间依赖性。STGNN适用于：人体动作识别、交通速度预测、驾驶员机动预期

 

（a）具有多个图卷积层的ConvGNN。图卷积层通过聚集来自其邻居的特征信息来封装每个节点的隐藏表示。特征聚合后，将非线性变换应用于结果输出。通过堆叠多层，每个节点的最终隐藏表示形式将接收来自其他邻居的消息。

（b）具有池和输出层的ConvGNN用于图分类。图卷积层之后是池化层，以将图粗化转化为子图，以使粗化图上的节点表示表示更高的图级表示。读出层通过获取子图的隐藏表示的总和/平均值来总结最终的图形表示。

（c）用于网络嵌入的GAE 。编码器使用图卷积层获得每个节点的网络嵌入。解码器计算给定网络嵌入的成对距离。在应用非线性激活函数之后，解码器重建图邻接矩阵。通过最小化实际邻接矩阵和重构的邻接矩阵之间的差异来训练网络。

（d）STGNN用于时空图预测。图卷积层后面是1-D-CNN层。图卷积层利用X 捕获空间依赖性，而1-D-CNN层滑过 X 沿时间轴捕获时间依赖性。输出层是线性变换，为每个节点生成预测，例如在下一时间步的未来值。

三、图神经网络的应用

3.1、计算机视觉

图形神经网络的最大应用领域之一是计算机视觉。研究人员在场景图生成、点云分类与分割、动作识别等多个方面探索了利用图结构的方法。

在场景图生成中，对象之间的语义关系有助于理解视觉场景背后的语义含义。给定一幅图像，场景图生成模型检测和识别对象，并预测对象对之间的语义关系。另一个应用程序通过生成给定场景图的真实图像来反转该过程。自然语言可以被解析为语义图，其中每个词代表一个对象，这是一个有希望的解决方案，以合成给定的文本描述图像。

在点云分类和分割中，点云是激光雷达扫描记录的一组三维点。此任务的解决方案使激光雷达设备能够看到周围的环境，这通常有利于无人驾驶车辆。为了识别点云所描绘的物体，将点云转换为k-最近邻图或叠加图，并利用图论进化网络来探索拓扑结构。

在动作识别中，识别视频中包含的人类动作有助于从机器方面更好地理解视频内容。一组解决方案检测视频剪辑中人体关节的位置。由骨骼连接的人体关节自然形成图表。给定人类关节位置的时间序列，应用时空神经网络来学习人类行为模式。

此外，图形神经网络在计算机视觉中应用的可能方向也在不断增加。这包括人-物交互、少镜头图像分类、语义分割、视觉推理和问答等。

3.2、推荐系统

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

3.3、交通系统

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

GNN也已与长期短期记忆（LSTM）和CNN一起使用，以预测一个时间间隔内特定位置的出租车需求数量。它考虑了过去的出租车需求，天气数据和位置信息。

3.4、化学

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

3.5、自然语言处理

除了以上四个领域外，图神经网络还已被探索可以应用于其他问题，如程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、脑网络、事件检测和组合优化。在NLP中，GNN用于文本数据的分类。他们使用文档中单词之间的相互关系来计算文档中的标签。

 

四、图神经网络的具体应用及代码实现

通过图神经进行相似度计算

图相似度搜索是最重要的基于图的应用程序之一，例如，查找与查询化合物最相似的化合物。受神经网络方法最近在几种图形应用（例如节点或图形分类）中取得成功的启发，我们提出了一种新颖的基于神经网络的方法来解决这一经典而具有挑战性的图形问题，旨在减轻计算负担，同时保持良好的性能。这种方法称为SimGNN，它结合了两种策略。首先，我们设计一个可学习的嵌入函数，将每个图形映射到一个嵌入向量中，提供图形的全局摘要。提出了一种新颖的注意力机制来强调关于特定相似性度量的重要节点。其次，我们设计了一种成对节点比较方法，以用细粒度的节点级信息来补充图级嵌入。在三个真实图形数据集上的实验结果证明了该方法的有效性。

4.1 SIMGNN模型的构建

4.2 核心代码实现

from tensorflow import keras
# from tensorflow.keras import layers
from keras_gcn import GraphConv
from keras.models import Model
from keras.layers import Input
from custom_layers import Attention, NeuralTensorLayer
""" 
Main model : Node-to-Node interaction not implemented.
Functional API :
Shared layers are shared_gcn1, shared_gcn2, shard_gcn3, shared_attention
"""
def simgnn(parser):
    inputA = Input(shape=(None,16))
    GinputA = Input(shape=(None,None))
    inputB = Input(shape=(None,16))
    GinputB = Input(shape=(None,None))
    
    shared_gcn1 =  GraphConv(units=parser.filters_1,step_num=3, activation="relu")
    shared_gcn2 =  GraphConv(units=parser.filters_2,step_num=3, activation="relu")
    shared_gcn3 =  GraphConv(units=parser.filters_3,step_num=3, activation="relu")
    shared_attention =  Attention(parser)

    x = shared_gcn1([inputA, GinputA])
    x = shared_gcn2([x, GinputA])
    x = shared_gcn3([x, GinputA])
    x = shared_attention(x[0])

    y = shared_gcn1([inputB, GinputB])
    y = shared_gcn2([y, GinputB])
    y = shared_gcn3([y, GinputB])
    y = shared_attention(y[0])

    z = NeuralTensorLayer(output_dim=16, input_dim=16)([x, y])
    z = keras.layers.Dense(16, activation="relu")(z)
    z = keras.layers.Dense(8, activation="relu")(z)
    z = keras.layers.Dense(4, activation="relu")(z)
    z = keras.layers.Dense(1)(z)
    z = keras.activations.sigmoid(z)

    return Model(inputs=[inputA, GinputA, inputB, GinputB], outputs=z)

5.总结

自从引入GNN以来，在过去的几年中，它们已成为解决可以通过图形建模的问题的强大而可靠的工具。这是由于其灵活性，表达能力和易于查看的效果。因此，GNN是具有大量实际应用程序的非结构化数据的直观解决方案。

6.参考文献

1. Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., Wang, L., & Sun, M. (2018). Graph neural networks: A review of methods and applications. arXiv preprint arXiv:1812.08434.
2. Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Philip, S. Y. (2020). A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems.
3.Bai Y , Ding H , Bian S , et al. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation[J]. 2018.