此文算是对Google Research这篇A Gentle Introduction to Graph Neural Networks 神作的阅读笔记.
图神经网络
十多年来，研究人员开发了一种称之为图神经网络（Graph Neural Networks，GNNs）的技术，旨在将如今在深度学习的诸多任务中摧枯拉朽的神经网络，应用到图结构之上，从而让神经网络捕捉到更错综复杂的交叉特征，以期待在一些任务上取得更佳的效果。鉴于操作图数据结构的复杂性，尽管已经发展了十几年，它在实际应用中却刚刚起步，即时是google也才开始研究将其被应用到药品研发、物理模拟、假新闻检测、交通预测和推荐系统等领域。
图是什么
尽管GNN是一个新兴的研究领域，但图结构的数据其实在我们身边无处不在。那么什么是图呢？
这个理科生应该都清楚，图有点(Vertex)和边(Edge)两部分组成，一个图就代表了各个实体节点（node）之间的关系（edge）：
Graph
每个节点或者边都可以包含它的一些属性信息，比如如果一个节点表示一个人，那么就可以包含这个人的姓名、性别、身高、体重之类的..我们研究需要的信息。
而这些信息，都可以用通用的向量的形式存入其中：
attributes embedding
还有别忘了一点，边是可以有方向的，按此我们还能分为有向图或是无向图。边的方向代表了信息的传递方向，例如a是b的微信好友，那b也是a的微信好友，好友关系自然是没方向的，而比如a是b的爹，那显然b就不是a的爹，此时叫爹的关系就是有有方向的。
Direct
图结构的构建是非常灵活的，可以根据个人的设计构建出各种不一样的图。而作为开发者显然要结合实际解决的问题来构建合适的图。
图在哪里
正如前面所提到的，图无处不在。你可能已经熟悉例如知识图谱、社交网络之类的图数据。当时显然，图是一种极其强大的通用数据表示，传统神经网络中用到的欧式空间的数据，同样可以用图来表示，例如可以将图像和文本建模为图结构数据。
图像表示为图
比如，我们可以将一张图片的每个像素作为图的节点，再将相邻的像素用边连接起来，就构造了一个该图像的图。
Image Graph
如上图展示了一个5*5的图片的邻接矩阵表示和图表示。
文本表示为图
我们将每个单词作为节点，并将每个节点连接到下一个节点，就得到了一个文本的图：
Text Graph
当然，在实践中我们并不会这样来编码文本和图像，因为所有的图和文本都是非常规则的结构，表示成图就多此一举了。
我们再来看一些例子，这些数据的结构更加复杂，除了图之外很难用其他方式来表达。
分子图表示为图
分子是构成物质的基石，我们可以用节点来表示它的原子和电子，用边来表示共价键，这样便将一个分子表示成了一个图：
Molecules Graph
不同的图可以表示出不同的分子结构：
Molecules Graph2
社交网络表示为图
都说社会是一个大熔炉，身处其中的人和事物之间会发生极其复杂的关系。这种关系的表示用普通的表格数据是很难表示的，而图却能很好的展现。
下图是将莎士比亚歌剧《奥赛罗》中的任务关系表示成图：
Othello Graph
怎么样，如果没看过歌剧能推测出那些是主角吗？
下面是将一个空手道竞标赛的对战关系构建为图：
karate Graph
类似的可以表示为图的数据还有很多很多，比如论文的引用之类统统都可以表示为图，下面是现实世界中不同规模的数据图表示的统计数据：
可见，各种各样规模的数据都可以轻松的用图来表示。
图解决什么问题
在上面我们列举了这么多的图，那么我们该对这些图数据执行什么任务呢？
图上的预测任务一般分为三类：
- 图级别
- 节点级别
- 边级别
下面我们通过具体的示例来说明GNN怎么来解决上述的三个级别的预测问题。
图级任务
在图级别的任务中，我们的目标是预测整个图的属性。例如我们通过分子图，来预测该分子的气味或是者它是否是与某些疾病有关的受体。
它的输入是完整的图：
input
输出是图的分类：
output
例如上图用于分类一个图是否有两个环..
这种任务，有点像是图像分类和文本分类，预测整个图像或是文本是哪一类。
节点级任务
节点级任务一般就是预测每个节点的类型。
一个经典的例子就是Zach的空手道俱乐部。该数据集市一个单一的社交网络图，犹豫政治分歧，讲师Hi先生和管理员John之间不和导致空手道俱乐部分裂，其中的学员一部分效忠于Hi先生，一部分效忠于John。每个节点代表空手道联系着，边代表空手道之外这些成员的互动，预测问题就是判断这些节点是效忠于谁的。
边级任务
边级任务其实就是预测每个边的属性.
在目标检测的语义分割任务中,我们也许不止要识别每个目标的类型,还需要预测各个目标之间的关系.我们可以将其描述为边级别的分类任务:给定表示图像中的对象的节点，我们希望预测哪些节点共享一条边，或者该边的值是多少。如果我们希望发现实体之间的连接，我们可以考虑图是完全连通的，并根据它们的预测值修剪边来得到一个稀疏图。
用图表示就是这样的过程:
在机器学习中使用图的挑战
那么我们要如何使用神经网络来处理上述各种类型的任务呢?
首先要考虑的是如何将图结构数据适配到神经网络.
回想一下啊,传统的神经网络输入的往往是矩阵形式的数据,那么要如何把图作为输入呢?
图表示有四种类型的信息:节点(nodes),边(edges),全局上下文(global-context),联通性(connectivity).对于前三种信息,有一个非常简单的方案,比如将节点排序,然后每个节点表示为一个向量,所有节点就得到了一个节点的矩阵,同理,边和上下文也可以这么搞.
但是要标识连通性就没有这么简单了,也许你会想到用临街矩阵来表示,但是这样表示会有明显的缺陷,因为节点数的规模往往是巨大的,对于一个数百万节点的图,那将耗费大量的空间,而且得到的矩阵往往也十分的稀疏,可以说空间利用率会很低.
当然,你也许会想,可以用稀疏矩阵来存储,这样就只需要存储连通的情况,空间利用率将大大提升,但是我们还要考虑到一点,就是稀疏矩阵的高性能计算一直是个艰难的,尤其是在用到GPU的情况.
并且,使用邻接矩阵还有一个问题就是各种不同的邻接矩阵可以标识相同的连通性,而这些矩阵并不能保证在神经网络中取的相同的效果.比如,同样的连通性,通过调换列的顺序,就能得到不同的邻接矩阵:
不过,好在有一种更加优雅的方式来标识邻接关系,即邻接表.
如上图所示,我们还是用一个向量来标识nodes和edges和global,然后用一个adjacency list来记录连接关系,比如[1,0]标识节点1和节点2相连...这样就解决了上述邻接矩阵的各种问题了~
GNN是怎么炼成的
现在，我们成功的将图结构成功表示成了置换不变的矩阵格式，终于可以使用图形神经网络（GNN）来做图形预测任务了。
GNN是对保持图对称性(置换不变性)的图的所有属性(节点、边、全局上下文)的可优化变换。
我们将使用Gilmer等人提出的“消息传递神经网络”框架构建GNN,并使用Battaglia等人介绍的图网络网络架构示意图。GNNS采用“图输入，图输出”架构，这意味着这些模型类型接受图作为输入，其中包含节点，边和全局上下文的信息，并逐步地转换这些图嵌入，而不会更改输入的连接图结构。
最简单的GNN
我们使用最开始提到的那个图来构建一个最简单的GNN,输入的图是相应节点,边,全局信息的向量,我们针对每个向量使用一个MLP层来作变换,于是得到一个新的图.
针对上述构建的最简单的GNN，我们如何在上面描述的任何任务中进行预测呢?这里我们仅仅考虑二进制分类的情况，但这个框架可以很容易地扩展到多类或回归的情况。
如果是对节点分类,我们只要在最后一层接一个线性类器就可以了:
但是上面的预测过程有点过于简单了,完全没有用到图的结构信息,我们在此基础上增加一个pooling操作,以增加它的边缘信息:
具体操作是把待预测节点的邻居节点以及全局的信息进行聚合再做预测,即将这些embedding向量加到一起得到一个新的向量,再输入到最后的线性分类器.
同理,如果我们只有节点相应边的信息的话,也可以用类似的方式pooling,然后得到节点的向量表示再输入分类器:
反之,如果我们只有节点的信息,那么也可以用边所连接的两个节点来pooling出边的向量,然后将器输入到分类器预测边的类型:
当然,如果我们只有节点的信息而要预测全图的类型,我们同样可以将节点信息和全局信息全部聚合之后,再将聚合信息输入到分类器做预测:
显然,不管是哪种任务,整个GNN的推理过程都是一样的,可以表示为这样一个端到端的过程:
不过,显而易见的,这个简单的GNN在分类前只是对每个向量进行了一个变换,而没有用到图结构的任何信息,虽然在最后做预测的时候做了一些pooling的聚合,但也始终没有用到adjacency的信息,因此这个GNN的作用相当有限,但是它为我们提供了一个图结构层变换和堆叠的基本思路.
在图的各部分进行信息传递
针对上面最简单GNN的不足,我们可以在其中根据连通性增加更加复杂的变换从而引入整个图结构的信息,我们将这个过程称之为信息传递.
信息传递包含三个步骤:
- 取出每个节点聚合其邻居节点的信息
- 通过聚合函数转换以上所有信息
- 通过一个更新函数(通常是一个学习过的神经网络)更新节点信息
这个过程有点类似于卷积操作,每个节点汇聚了其邻居的节点,经过多个层的变换,它将涵盖全图的信息.
于是我们可以将这个节点信息传递应用到上述的图变换过程中:
然后,我们发现它并没用用上边的信息,于是可以把边信息也加上,变成这样:
另外,我们可以发现聚合顺序不同,结果就会不同:
那么按照哪个顺序呢?这并没有明确的答案,就靠开发者来决策了,或者使用一种交替聚合的策略,这样就跟顺序无关了:
既然把边的信息加上了,那怎么可以漏掉全局信息呢,于是完整的信息传递就可以表示成这样:
在这个视图中，所有图属性都学习了表示，因此我们可以在pooling过程中通过调节我们感兴趣的属性的信息相对于其余属性来利用它们。例如，对于一个节点，我们可以考虑来自相邻节点、连接边和全局信息的信息。为了在所有这些可能的信息源上调节新节点嵌入，我们可以简单地将它们连接起来。此外，我们还可以通过线性映射将它们映射到相同的空间并累加它们或应用特征调节层，这可以被认为是一种特征化注意力机制。
以上,我们梳理了最简单的GNNs是怎么完成的,你应该已经对GNN有了一个基本的了解,就像学会了传统神经网络中最简单的全连接网络类似,关于GNN还有更多不同种类的更复杂的图需要取了解和学习,但你只要掌握了以上的思想,学习起来也是十分容易的.
网友评论