图神经网络（Graph Neural Network，GNN）

2022-03-06
10分钟阅读时长
机器学习

图论（Graph Theory）是数学和计算机科学中的重要分支，在机器学习中也有应用，表示某些模型结构。概率图模型用图结构为一组随机变量建模，描述它们之间的概率关系。流行降维算法与谱聚类算法均使用了谱图理论。神经网络的计算图也是图的典型代表，图神经网络（Graph Neural Network，GNN）作为一种新的深度学习模型，与图论同样有密切的关系。图论里的概念很多，例如有向图，有向图无环图等等，不过下面介绍的是深度学习中的图神经网络。

img

发展的趋势

图神经网络（Graph Neural Network，GNN）在学术界是相当热门的一个方向。在 Google 学术排行榜第一的国际表征学习大会（International Conference on Learning Representations，简称：ICLR，是公认深度学习领域的顶级会议之一，关于深度学习各个方面的前沿研究，在人工智能、统计和数据科学领域以及计算机视觉、语言识别、文本理解等重要领域中发布了众多及其有影响力的论文）的前 50 关键词排行（详见 链接）。

图像

一、什么是图神经网络

图是一种几何结构，在现代科学和工程中，图得到了广泛的使用，很多问题可以抽象成图结构。下面介绍一下本文要讲的图的概念。

  • 1）、图的基本组成

    在这里插入图片描述

    图的组成部分是：

    • V 顶点（ Vertex 或者 Node）

      上图的 A、B、C、D、E、F 都是顶点（也称节点）。顶点包含特征向量（例如：人的身高，年龄，资产等），或者邻居节点的个数。

    • E 边（ Edge 或者 Link）

      顶点与顶点的之间的连线就是边，边也是可以有特征向量的（例如：方向，距离，权重等）。

    • U 图（Graph 或 Global）

      顶点和边组成的整体，就是整个图（Graph）。它包含节点个数，也可以包含最长路径等信息。

    注意：上面的 V、E、U 只是此处定义，不同地方会有些不同，看具体情况。

  • 2）、图神经网络要做什么

    如果熟悉 CNN、RNN、以及 Attention 的就知道，神经网络主要就是用来提取特征的。图可以表示很多信息，如：节点（V）、边（E）、整个图（U），图神经网络就是通过计算这些信息关系来提取特征的，然后再进行后续的实际的任务。

  • 3）、图的邻接矩阵

    说到图，那不得不讲的就是邻接矩阵了，那么什么是邻接矩阵呢？邻接矩阵就是用来表示点和点之间的关系的，假设有 $n$ 个节点，那么邻接矩阵就是 $n\times n$ 的方阵，有关系的是 1 没关系的是 0。注意的是，无向图的邻接矩阵是沿着主对角线对称的，而且呢，主对角线上都是 0，因为自己跟自己的关系认为是没有关系的。下面看几个实际的例子：

    • 以图像为例子，每个像素点周围都有邻居，A就表示邻居之间的关系。可到 参考文章 看动图更直观的理解邻接矩阵。

      image-20220114115820742

      左边的这个图片代表的是一张图片像素数据，其中每个框是该图的像素点，相邻的两个像素点是有关系。其对应的表示的邻接矩阵就是上图中间这个图，其左侧和上侧的代表就是像素点的位置，相交的点标记有关系 1（蓝色） ，无关系 0（对应图中的白色）。最右边的这个就是图关系的表示了。

    • 文本数据也可以表示图的形式，邻接矩阵表示的连接关系。与图像不同的是文本是有向的，可以看到下三角全是 0 。

      image-20220114123414808

    上面只是举例子，说明图像和文本也都是可以用邻接矩阵表示的。实际的图像和文本并不会用图相关的模型，因为他们的数据格式都是非常固定的，图像预处理有 resize，文本呢，也有 padding 和 truncation 操作，格式都很固定，不需要特殊的邻接矩阵。

    再来看看，实际常用的几个例子：

    • 化学分子结构，例如：$H_2O$、$CO_2$ 等等（可以到 [参考原文] 看动图）。

      image-20220114125436485

    • 社交网络中各个人物的关系，如果人数比较多的话，这种邻接矩阵会相应的比较庞大。

      image-20220114125555799

    **注意：**对于邻接矩阵，太过于稀疏了，很多时候并不是用 $n\times n$ 的矩阵来表示的，而是采用 [source，target] 的方式。使用一个数组，里面里面是 n 个二元数组，表示 n 条边，以及两两之间的关系。

    image-20220114130746064

    图神经网络的输入是点或边的特征向量 $X$ 和邻接矩阵 $A$ ，与图像和文本数据不同的是，图神经网络不用像图像那样需要 resize，也不用和文本那样需要 padding 和 truncate。这就是图神经网络的优势，像化分子能 resize 吗？显然是不能的，这个时候就非常适合使用图神经网络。

  • 4）、图模型可以有哪些任务呢？

    • Graph 级别

      通过综合各个点和边的特征信息，预测分子是什么，有没有环路，对人有什么毒性等等。

      image-20220114130258574

    • Node 和 Edge 级别

      预测这个点是谁？这个边在做什么动作等。

      image-20220114130138460

二、算法原理：消息传递神经网络

图神经网络主要就是用来提取特征的，其节点以及边的计算算法不下百种，例如图卷积（Graph Convolutional Network，GCN）、图注意网络（Graph Attention Networks，GAT） 、门控注意力网络（Gated Attention Network，GAAN）等等（详见篇尾链接）。不管怎样算法如何，都是在计算提取特征。

这里介绍其中最简单的一种计算方式：消息传递神经网络（Message Passing Neural Network，MPNN）。

  • 1）、如何计算

    1. 首先每个节点看自己的自己的邻居，下面画图来的是 1 到 6 号节点各自的邻居。例如：1 号有邻居 2、4、6，2 号也有 ······ 。

      image-20220114115127683

    2. 例举 6 号节点的计算

      image-20220114141040955

      上面 6 号点有邻居 1、3、4 ，这些节点最开始都有各自的一个向量（由例如：人的身高、体重、年龄等组成）。那么 对于 6 号这个节点是怎么更新的呢？可以看作是一个全连接计算：$X_{4\times m}W_{m\times n}$。其中 $X_{4\times m}$ 是 1、3、4、6 这 4 个点对应的 m 维向量组成的，$W_{m\times n}$ 是可以学习的权重参数，$m$ 对应原始输入的 m 维特征向量，$n$ 是新的向量的维度数，也可以保持不变。经过上面的计算，我们的得到一个新的向量 $X_{4\times n}$。另外，假如它有 10 个边包含它自身结果就会是 $X_{11\times n}$，这不太好吧，随着边的数量增多，向量的行也增多？所以为了解决这个问题，会再进行聚合操作例如求和、求最大值、求平均等，最后再跟一个激活函数，这结果就是 6 号点新的特征向量。

      同理，每个节点都进行一次这样的计算就完成了每个节点的特征向量的更新，到现在位置，每个节点都包含了它和它邻居的信息。

    3. GNN 也可以有多层。

      跟传统的 CNN、RNN 一样，GNN 也可以多层堆叠，如下图。

      image-20220114143435626

      多层堆叠有什么效果呢？首先，先看一层的计算，一次计算下来，每个节点包含它邻居的信息。再看，第二层计算过后，也包含它邻居的信息，值得注意的，此时的邻居是包含它在第一层计算时的邻居的信息，这就相当于第二层计算之后，每个点包含了它邻居的邻居的信息。随着层数的叠加，所包含的信息会越来越丰富。

      通常的层数是 5 层以内，相隔越远，越不相关，没必要计算那么多层。有句话叫做六个人认识全世界，也叫六度分离理论（Six Degrees of Separation），是指和任何一个陌生人之间所间隔的人不会超过五个，也就是说，最多通过五个人就能够认识任何一个陌生人，对于图神经网络也是如此。

      通过上述图神经网络计算可以知道，网络的输入是特征，输出也是特征，邻接矩阵也是不变的。

  • 2）、计算出来的特征可以做什么？

    • 组合各个点的特征，对整个图分类

      image-20220114132858556

    • 对各个点进行分类

      image-20220114133155240

    • 对边进行分类

      image-20220114133205471

    从图神经网络这种网络结构的计算方式，它是可以做半监督学习的，甚至可以有更过分的十分之一监督学习，为什么可以做半监督学习呢？看它的每个节点计算都包含其邻居的信息，它自己要预测对，首先它的邻居得要先预测对吧，所以这也是图神经网络的优势之一。半监督学习，损失函数就是只计算有标签的点，没有标签的忽略，当成 0 没有损失就好了。

  • 3）、代码调用示例

    import torch
from torch import Tensor
from torch_geometric.nn import GCNConv
from torch_geometric.datasets import Planetoid

dataset = Planetoid(root='.', name='Cora')

class GCN(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = GCNConv(in_channels, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, out_channels)

    def forward(self, x: Tensor, edge_index: Tensor) -> Tensor:
        # x: Node feature matrix of shape [num_nodes, in_channels]
        # edge_index: Graph connectivity matrix of shape [2, num_edges]
        x = self.conv1(x, edge_index).relu()
        x = self.conv2(x, edge_index)
        return x

model = GCN(dataset.num_features, 16, dataset.num_classes)

    这是一段使用 pytorch_geometric 实现的图卷积（GCN）的使用代码，就看 forward 函数的输入，x 是点的特征信息，edge_index 是邻接矩阵，就是这样简单就完成了图卷积算法的应用。

三、图神经网络的应用

图神经网络最主要是提供了图嵌入（Graph Embedding）这一可以用来进行图表征学习的技术，将传统的图分析引入，扩展了深度学习对于非欧几里得数据的处理能力，提供了对非规则数据提取特征的方法，它被广泛应用于社交网络，推荐系统，金融风控，物理系统，分子化学，生命科学，知识图谱，交通预测等领域。但是对于非结构化数据（文本，图像），目前研究人员均有所尝试，但具体的应用成果比较少。以下是对各个应用场景的简介：

  • 芯片设计

    让机器"会思考" 设计中"增引擎"。图神经网络被认为有望解决深度学习无法处理的关系推理、可解释性等一系列问题，让机器"能理解、会思考"。然而由于图神经网络在图数据处理方面的特殊性，传统用于加速神经网络的芯片难以直接对图神经网络的执行提供高效计算支撑。通常计算机芯片会被切分几十块，每个块都是单独的模块，内存系统、计算单元等。这些模块之间通过电线连接。芯片设计布局是最复杂和最难的。将这些抽象成图结构模块是点，电线是边，根据已知的，已经实验过的数据作为监督信号训练一个可以预测芯片结构功率、性能面积的模型。

    下面是摘自 https://ai.googleblog.com/2020/04/chip-design-with-deep-reinforcement.html 的截图。

    image-20220114161519534

  • 场景分析与问题推理

    不同场景物体与物体的依存关系，采用图神经网络来计算推理。

    image-20220114173739424

  • 推荐系统

    image-20220114152515325

    基于图神经网络的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目以及内容信息之间的关系，基于图的推荐系统能够产生高质量的推荐。

    推荐系统的关键是给用户打分。因此，可以将其转换为一个链接预测问题。为了预测用户和物品之间缺失的链接，Van 等人和 Ying 等人提出了一种使用 ConvGNNs 作为编码器的 GAE。Monti 等人将 RNNs 与图形卷积相结合，以学习生成已知评级的底层过程。

  • 欺诈检测，风控相关

    基于实时计算，您可以轻松完成实时欺诈检测系统。 实时欺诈检测系统能够及时发现用户高危行为并采取措施，降低损失。

    风控

    实时欺诈检测（风控）系统流程如下：

    1. 用户的行为经由App上报或Web日志记录下来，发送到一个消息队列里去。
    2. 实时计算订阅消息队列，过滤出感兴趣的行为，比如：购买、领券、浏览等。
    3. 实时计算计算把这个行为特征化。
    4. 实时计算通过UDF调用外部一个风险模型，判断这次行为是否有问题（单次行为）。
    5. 实时计算里通过CEP功能，跨多条记录分析用户行为（比如用户先做了A，又做了B，又做了3次C），整体识别是否有风险。
    6. 综合风险模型和CEP的结果，产出预警信息。

  • 知识图谱

    知识图谱本身，也是一个图结构。

    image-20220114162656048

  • 道路交通，动态流量预测

    image-20220114155524933

    在智能交通系统中，准确预测交通网络中的交通速度、交通量或道路密度是至关重要的。

    有的研究者使用 Spatial Temporal Graph Neural Network（STGNNs，一种旨在从时空图学习隐藏模式，关键思想是同时考虑空间依赖性和时间依赖性） 解决流量预测问题。他们认为交通网络是一个时空图，其中节点是安装在道路上的传感器，通过对节点之间的距离来测量边缘，每个节点以一个窗口内的平均交通速度作为动态输入特征。

    另一个工业级应用是出租车需求预测。根据历史出租车需求、位置信息、天气数据和事件特征，Yao 等将 LSTM、CNN 和 LINE 训练的网络嵌入结合在一起，形成对每个位置的联合表示，从而预测某一时段内某一位置的出租车需求数量。

  • 化学，医疗

    在化学领域，研究人员应用 GNNs 来研究分子/化合物的图形结构。在分子/化合物图中，原子被认为是节点，化学键被认为是边，因此 GNN 可用于分子指纹、预测分子性质、推断蛋白界面、合成化合。即节点分类、图分类和图生成是针对分子/化合物图的三大主要任务。

    image-20220114174127675

    再者分析中药成分的用药用量的组合，对患者的产生病理性推理。

图神经网络的应用不止上面所列出来的，还有更多等待发掘。

参考

#图神经网络 #图卷积 #GNN #GCN
Avatar

YISH

 这个人很懒，什么都没有
下一页 Mermaid 图表支持