图神经网络期刊

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

论文:论文地址： 论文题目:《Session-based Recommendation with Graph Neural Networks》SR-GNN github: 基于会话的推荐一般是将序列会话建模，将整个session进行编码，变成一个隐向量，然后利用这个隐向量进行下一个点击预测。但是这种方法没有考虑到item直接复杂的转换(transitions)关系，也就是item之间在点击的session中除了时间顺序外还有复杂的有向图内的节点指向关系，所以之前的方法不足以很好的对点击序列进行建模。 现有基于会话的推荐，方法主要集中于循环神经网络和马尔可夫链，论文提出了现有方法的两个缺点： 1）当一个session中用户的行为数量十分有限时，这些方法难以获取准确的用户行为表示。如当使用RNN模型时，用户行为的表示即最后一个单元的输出，论文认为只有这样并非十分准确。 2）根据先前的工作发现，物品之间的转移模式在会话推荐中是十分重要的特征，但RNN和马尔可夫过程只对相邻的两个物品的 单向转移关系 进行建模，而忽略了会话中其他的物品。 为了克服上述缺陷，本文提出了用图神经网络对方法对用户对session进行建模：下面具体介绍怎么进行图序列推荐 V = {v1,v2...vm}为全部的item，S = { }为一个session里面按时间顺序的点击物品，论文的目标是预测用户下一个要点击的物品vs,n+1，模型的任务是输出所有item的预测概率，并选择top-k进行推荐。 我们为每一个Session构建一个子图，并获得它对应的出度和入度矩阵。 假设一个点击序列是v1->v2->v4->v3，那么它得到的子图如下图中红色部分所示：另一个例子，一个点击序列是v1->v2->v3->v2->v4，那么它得到的子图如下：同时，我们会为每一个子图构建一个出度和入度矩阵，并对出度和入度矩阵的每一行进行归一化，如我们序列v1->v2->v3->v2->v4对应的矩阵如下：这个矩阵里面的值是怎么计算的呢？下面讲一下： 看左边的出度矩阵，第一行为 0 1 0 0 ，代表着v1->v2，因为v1，只有一个指向的item，所以为1；看第二行，0 0 1/2 1/2，因为v2有指向v3和v4的边，所以进行归一化后每一个值都变成了1/2。入度矩阵的计算方法也是一样的，就不再说了。 本文采用的是GRU单元进行序列建模，将图信息嵌入到神经网络中，让GRU充分学习到item之间的关系，传统的GRU只能学到相邻的两个物品之间的关系，加入图信息后就能学到整个session子图的信息。 计算公式如下：为了刚好的理解这个计算过程，我们还是使用之前那个例子：v1->v2->v3->v2->v4来一步步分析输入到输出的过程。 （1） 是t时刻，会话s中第i个点击对应的输入， 是n✖️2n的矩阵，也就是会话子图的完整矩阵，而 是其中一行，即物品vi所对应的那行，大小为1✖️2n，n代表序列中不同物品的数量。 如果按照例子来看，如果i取2，那么 为 [0 0 1/2 1/2 1/2 0 1/2 0] 进一步的，可以把 :拆解为[ , ] （2） 可以理解为序列中第i个物品，在训练过程中对应的嵌入向量，这个向量随着模型的训练不断变化，可以理解为隐藏层的状态，是一个d维向量。    (3)  H是d*2d的权重向量，也可以看作是一个分块的矩阵，可以理解为H=[Hin|Hout]，每一块都是d*d的向量。 那么我们来看看计算过程： 1）[ ..., ] ，结果是d * n的矩阵，转置之后是n*d的矩阵，计作 2） : H相当于[   ]，即拆开之后相乘再拼接，因此结果是一个1 * 2d的向量。 上面就是完整的第i个点击的输入的计算过程，可以看到，在进入GRU计算之前，通过跟As,i矩阵相乘，把图信息嵌入到了神经网络中取，加深了神经网络学习到的item之间的交互信息。 此外，就是GRU的计算过程了，跟原始的GRU不一样的地方在于输入从xt变成了嵌入了图信息的as,i。 通样也有更新门和重置门，计算方法跟原始GRU一模一样。 这里的 其实就是相当于原始gru中的 ，只不过在SR-GNN里面，进行一轮运算的时候i是没有变化，相当于每个物品单独进去GRU进行计算，得到自己的向量，也就是说在GRU的计算过程中， 是不断变化的，看一下源码更易于理解： hidden就是公式里面的 ,在gru的每一个step计算中都会进行更新，这里我有个疑问，如果所有item的hidden都更新的话，那么应该是整个序列中所有的item并行进入GRU中进行计算，每一个step都得到自己的vector，当每个item的vector更新后，下一个step就重新根据新的 计算 ，接着计算下一个step。 计算过程大概就是下面这样：这里有四个GRU并行计算，没次更新自己的hidden状态，输入则考虑所有的hidden和图信息。 从上面的图看来，每一个item都要进行T个step得到自己的item-vec，所以经过T个step后，我们就得到了序列中所有item的向量，即：图中用蓝色框框画出来的向量，有了这些向量后，我们怎么得到预测结果呢？这就引入了下一个问题。 观察上面的模型结构，我们看到attention，没错，我们认为一个session中的这些item-vec并不都对预测结果产生影响，有些item对结果影响很大，有些影响很小，所以我们进行了加权求和。同时，论文认为session对最后一个item-vec，s1=vn是重要的，所以单独拿出来：公式(6)就是简单的attention操作，其实从公式上来看就是计算每个vi跟最后一个向量vn的权值，然后进行加权求和。 在最后的输出层，使用sh和每个物品的embedding进行内积计算，这里vi应该是item的embedding层出来的向量，而不是后面一直更新的hidden：最后通过一个softmax得到最终每个物品的点击概率： 损失函数为交叉熵损失函数：从数据上来看，SR-GNN超过了经典的GRU4REC，这也说明了图信息的嵌入能带来更好的推荐效果。 本论文很巧妙的将图信息嵌入的神经网络中，更高地让GRU学习到每个item之间的关系，不再局限于相邻的物品之间进行学习。近年来，图神经网络的思想和方法屡屡被用在推荐系统中，学好图神经网络应该是推荐系统的下一个热潮。