图神经网络(GNN)结构化数据分析
本文对图神经网络作了简要的介绍。涵盖了一些图的理论，以方便理解图和分析图的问题。作者还介绍了不同形式的图神经网络及其原理，以及GNN的功能和一些应用。
更多信息请查看原文：https://www.yanxishe.com/TextTranslation/2475?from=jianshu0326
图神经网络(GNN)由于具有分析图结构数据的能力，近年来受到广泛关注。本文对图神经网络作了简要的介绍。它涵盖了一些图的理论，以方便理解图和分析图的问题。然后介绍了不同形式的图神经网络及其原理。还介绍了GNN的功能和一些应用。
图论
首先，我们需要知道什么是图。
图是一种数据结构，由顶点和边两部分组成。它被作为一个数学结构来分析对象和实体之间的成对关系。通常，图被定义为G=(V, E)，其中V是一组节点，E是节点之间的边。
一个简单的图形。图的作者
图通常用邻接矩阵A表示，如果一个图有N个节点，则A的维数为(NxN)。
人们有时会提供另一个特征矩阵来描述图中的节点。如果每个节点有F个特征，则特征矩阵X的维数为(NxF)。
为什么图很难分析?
首先，一个图不存在于欧几里德空间中，这意味着它不能被我们所熟悉的任何坐标系表示。这使得图形数据的解释比其他类型的数据更加困难，如波、图像或时间序列信号(“文本”也可以被视为时间序列)，可以很容易地映射到2维或3维的欧几里德空间。
第二，图形没有固定的形式。为什么?请看下面的例子。图(A)和图(B)具有完全不同的结构和视觉上的不同。但是当我们将其转换为邻接矩阵表示时，这两个图具有相同的邻接矩阵(如果我们不考虑边的权重)。这两个图是一样的还是不同的?
图（A）. 来自本文英文原文作者
图（B）来自本文英文原文作者
最后，图形通常很难被可视化来给人类理解。我不是在讨论像上面例子那样的小图，而是包含成百上千个节点的巨型图。这个维度非常高，节点密集地分布在一起，使得人们很难理解这个图。因此，训练一台机器来完成这项任务是很有挑战性的。下面的例子展示了集成电路中逻辑门的图形建模。
一个巨大图的例子: 电路netlist。图来自J. Baehr等人的《机器学习与逆向工程的结构特征》
为什么使用图?
人们选择研究图的原因可以总结为以下几点:
1.图为处理关系和交互等抽象概念提供了更好的方法。
它们还提供了一种直观的视觉方式来思考这些概念。
图表也是分析社会背景下人际关系的自然基础。
2.图可以通过将问题简化为更简单的表示或从不同的角度将问题转换为表示来解决更复杂的问题。
3.图论和概念被用来研究和模拟社交网络、欺诈模式、电力消耗模式、社交媒体中的病毒传播和影响力。
社会网络分析(SNA)可能是图论在数据科学中最著名的应用。
传统的图数据分析方法
传统的方法大多基于算法，如:
1.搜索算法，如BFS, DFS
2.最短路径算法，例如Dijkstra算法，最近邻算法
3.扩充树算法，如Prim算法
4.聚类方法，如高度连接组件，k-均值
这种算法的局限性在于，我们需要在一定的置信度下获得图的先验知识，然后才能应用该算法。换句话说，它给我们提供了研究图形本身的方法。最重要的是，没有办法执行图级分类。
图神经网络
图神经网络，正如它的叫法，是一种可以直接应用于图的神经网络。它为节点级、边缘级和图级预测任务提供了一种方便的方法。 文献中主要有三种类型的图神经网络:
1.递归图神经网络
2.空间卷积网络
3.光谱卷积网络
GNN的直觉是，节点是由它们的邻居和连接自然定义的。为了理解这一点，我们可以简单地想象一下，如果我们删除一个节点周围的邻居和连接，那么这个节点将丢失所有信息。因此，节点的邻居和到邻居的连接定义了节点的概念。
记住这一点，然后我们给每个节点一个状态(x)来表示它的概念。我们可以使用节点状态(x)来生成输出(o)，即关于概念的决策。节点的最终状态(x_n)通常称为“节点嵌入”。所有GNN的任务都是通过查看相邻节点的信息来确定每个节点的“节点嵌入”。
我们将从最先锋的图神经网络，递归图神经网络，或称RecGNN开始。
递归图神经网络
递归图神经网络正如在原始的GNN论文中所介绍的，RecGNN是在Banach不动点定理的假设下建立的。巴拿赫不动点定理指出:设(X,d)为完全度量空间，设(T:X→X)为收缩映射。那么T就有一个唯一的不动点(x)，对于任意x∈x, n→∞的序列T_n(x)就会收敛到(x)。这意味着如果我将映射T作用于x上k次，x^k应该几乎等于x^(k-1)即
RecGNN定义了一个参数化函数f_w:
其中l_n、l_co、x_ne、l_ne分别表示当前节点[n]的特征、节点的边[n]、相邻节点的状态以及相邻节点的特征。(在原文中，作者将节点特征称为节点标签。这可能会造成一些混乱。)
基于其邻居中的信息的节点状态更新的说明。图来自“图神经网络模型”最后，在k次迭代之后，使用最后的节点状态生成输出，对每个节点做出决策。输出函数定义为:
空间卷积网络
空间卷积网络的直觉与著名的CNN相似，后者主导了图像分类和分割任务的文献。想从图片上了解CNN，你可以看看这篇详细解释CNN的文章。
简而言之，对图像进行卷积的思想是对中心像素周围的相邻像素求和，该中心像素由参数化大小和可学习权值的滤波器指定。空间卷积网络采用相同的思想，将相邻节点的特征聚集到中心节点。
左:常规图形(如图像)的卷积。右:对任意图形结构的卷积。
图来自-"图神经网络综合调查”
光谱卷积网络
与其他类型的GNN相比，这种图卷积网络具有很强的数学基础。频谱卷积网络是建立在图数据处理理论基础上的。通过图卷积的简化和近似。
通过Chebyshev多项式近似(Hammond et al. 2011)，图卷积可以简化为以下形式:
经过进一步的简化，GCN论文提出了一个2层的神经网络结构，可以用一个方程描述如下:
其中A_head为原始图邻接矩阵a的预处理拉普拉斯矩阵a(数学细节见GCN论文)。要作充分的解释是很费力气的.)
如果你有机器学习的经验，这个公式看起来很熟悉。这只是两个通常使用的全连接层结构。但在这个例子中它确实是图形卷积。我将在下面展示为什么它可以执行图形卷积。
具有分配给每个节点的特性的图的示例。图来自作者
假设我们有一个有4个节点的简单图。
每个节点都被分配了一个特征矩阵，如上图所示。
图的邻接矩阵和特征矩阵很容易得出，如下图所示:
邻接矩阵和特征矩阵的例子。图的作者
请注意，邻接矩阵的对角线特意改为'1' 以便为每个节点添加一个自循环。这是为了在执行特性聚合时包含每个节点本身的特性。
然后我们执行AxX(为了简单起见，我们先不考虑A的拉普拉斯变换和权重矩阵W)。
图由矩阵乘法卷积的例子。图的作者
矩阵乘法的结果显示在最右边的矩阵中。让我们以第一个节点的结果特性为例。不难发现，结果是[node 1]的所有特征的总和，包括[node 1]自身的特征，而[node 4]的特征不包括在内，因为它不是[node 1]的邻居。在数学上，图的邻接矩阵只有在有边时才有值“1”，否则为值“0”。这使得矩阵乘法成为连接到参考节点的节点特征的总和。
因此，频谱卷积网络和空间卷积网络虽然起点不同，但传播规律相同。
所有当前可用的卷积图神经网络都具有相同的格式。它们都试图通过这个消息传递过程来学习一个传递节点信息和更新节点状态的函数。
任何图数据神经网络都可以表示为具有消息传递函数、节点更新函数和读出函数的消息传递神经网络(J. Gilmer et al.， 2017)。
GNN能做什么?
GNN解决的问题大致可分为三类:
1.节点的分类
2.链接预测
3.图的分类
在节点分类中，任务是预测图中每个节点的节点嵌入。这类问题通常以半监督的方式进行训练，其中只有部分图形被标记。节点分类的典型应用包括引用网络、Reddit帖子、Youtube视频和Facebook好友关系。
在链接预测中，任务是理解图中实体之间的关系，并预测两个实体之间是否有连接。例如，一个推荐系统可以看作是一个链接预测问题，模型给出了一组用户对不同产品的评论，任务是预测用户的偏好，调整推荐系统，根据用户的兴趣推送更多相关的产品。
在图分类中，任务是将整个图划分为不同的类别。它类似于图像分类，但目标变换为图域。图分类可以应用于许多工业问题，例如，在化学、生物医学、物理等领域，模型被赋予一个分子结构，并被要求将目标分类为有意义的类别。它加速了原子、分子或任何其他结构化数据类型的分析。
一些真正的应用
了解了GNN可以执行哪些类型的分析之后，您一定想知道我可以使用图来做哪些真正的事情。本节将让您对GNN的实际应用有更多的了解。
GNN在自然语言处理中的应用
GNN在自然语言处理(NLP)中有着广泛的应用。实际上，这也是GNN最初开始应用的地方。如果您有NLP的经验，您一定认为文本应该是一种用RNN或LTSM来描述的顺序或时间数据类型。但GNN从一个完全不同的角度来处理这个问题。
GNN利用单词或文档的内部关系来预测类别。例如，引文网络试图通过论文被引关系和其他论文被引的单词来预测网络中每篇论文的标签。它还可以通过查看句子的不同部分来建立语法模型，而不是像RNN或LTSM那样纯粹地按顺序排列。
计算机视觉中的GNN
许多基于CNN的方法在图像目标检测方面已经达到了最先进的水平，但是我们还不知道目标之间的关系。在CV中使用GNN的一个成功之处是使用基于CNN的检测器对检测到的对象之间的关系进行图形建模。从图像中检测到目标后，将其输入到GNN推理中进行关系预测。GNN推理的结果是一个生成的图形，用于建模不同对象之间的关系。
场景图的一代。图来自D. Xu, Y. Zhu, C. B. Choy, L. Fei-Fei, “通过迭代消息传递生成场景图”，CVPR学报，2017年
CV中另一个有趣的应用是由图形描述生成图像。这可以解释为几乎与上面提到的应用程序相反。传统的图像生成方法是使用GAN或自动编码器进行文本到图像的生成。图形生成提供了更多关于图像语义结构的信息，而不是使用文本进行图像描述。
由场景图生成的图像。图来自J. Johnson, A. Gupta和L. Fei-Fei，“从场景图生成图像”，发表于CVPR, 2018年
我想分享的最有意思的应用是零学习(zero-shot learning, ZSL)。你可以在这篇文章中找到对ZSL的全面介绍。简而言之，ZSL正在尝试对一个完全没有训练样本(目标班级)的班级进行分类。这是非常具有挑战性的，因为如果没有提供训练样本，我们需要让模型逻辑地“思考”来识别目标。例如，如果给我们三个图像(如下图所示)，并告诉我们在其中找到“okapi”。我们以前可能没见过“okapi”。但是，如果我们还知道“okapi”是一种长着四条腿的鹿脸动物，并且有斑纹的皮肤，那么我们就不难判断出哪个是“okapi”。典型的方法是通过将检测到的特征转换成文本来模拟这个“思维过程”。然而，文本编码是相互独立的。文本描述之间的关系很难建模。在其他困难的情况下，图形表示很好地模拟了这些关系，使机器以一种更“类似于人类”的方式思考。
图源是 X. Wang, Y. Ye 和 A. Gupta, 发表于 CVPR 2018的论文“Zero-shot recognition via semantic embeddings and knowledge graphs,”
GNN在其他领域的应用
GNN的更多实际应用包括人类行为检测、交通控制、分子结构研究、推荐系统、程序验证、逻辑推理、社会影响预测、对抗攻击预防等。下图展示了一个社交网络中人们关系的模型。GNN可用于将人们聚集到不同的社区组中。
社交网络图。图像来自GDJ，通过Pixabay
结论
在这篇文章中，我们回顾了一些图的理论，并强调了分析图的重要性。
人们总是把机器学习算法看作一个“黑匣子”。大多数机器学习算法只学习训练数据的特征，而没有实际的逻辑去执行。有了图形，我们可能能够将一些“逻辑”传递给机器，让它更自然地“思考”。
GNN仍然是一个比较新的领域，值得更多的研究关注。它是分析图形数据的有力工具。然而，它并不局限于图形中的问题。它可以很容易地推广到任何可以用图形建模的研究中。图形建模是分析问题的一种自然方法。
引用:
1.F.Scarselli, M。图神经网络模型>，《IEEE神经网络汇刊》，2009年2.T. N. Kipf和M. Welling，“使用图卷积网络的半监督分类”，《ICLR学报》，2017年。
3.吴，潘，陈，龙，张，余，“图型神经网路之综合研究”，国立中央大学资讯工程学研究所硕士论文，国立中央大学资讯工程学研究所
4.徐丹，朱长兵，蔡长兵，李飞飞，“迭代消息传递生成场景图”，载《CVPR学报》，2017年第2期
5.J. Johnson, A. Gupta, L. Fei-Fei，“从场景图生成图像”，摘自《CVPR学报》，2018年
6.王锡恩，叶义义，古普塔，“基于语义嵌入和知识图的零镜头识别”，CVPR 2018
更多信息请查看原文：https://www.yanxishe.com/TextTranslation/2475?from=jianshu0326
