图神经网络模型总结

知识复习：

一、图结构

在讨论GNN之前，我们先来了解一下什么是图。在计算机科学中，图是由顶点和边两部分组成的一种数据结构。图G可以通过顶点集合V和它包含的边E来进行描述。

图定义

根据顶点之间是否存在方向依赖关系，边可以是有向的，也可以是无向的。其中a是无向图，c为有向图。

图结构

二、图有两个基本特征：

1. 每个节点都有自己的特征信息
2. 图谱中的每个节点还具有结构信息

图神经网络相关：

在了解图神经网络之前，我们来复习一下与图神经网络相关的一些概念

一、Graph Embedding

图嵌入（Graph Embedding/Network Embedding，GE），属于表示学习的范畴，也可以叫做网络嵌入，图表示学习，网络表示学习等等。通常有两个层次的含义：

• 将图中的节点表示成低维、实值、稠密的向量形式 ，使得得到的向量形式可以在向量空间中具有表示以及推理的能力，这样的向量可以用于下游的具体任务中。例如用户社交网络得到节点表示就是每个用户的表示向量，再用于节点分类等；
• 将整个图表示成低维、实值、稠密的向量形式 ，用来对整个图结构进行分类；

图嵌入的方式主要有三种：

• 矩阵分解： 基于矩阵分解的方法是将节点间的关系用矩阵的形式加以表达，然后分解该矩阵以得到嵌入向量。通常用于表示节点关系的矩阵包括邻接矩阵，拉普拉斯矩阵，节点转移概率矩阵，节点属性矩阵等。根据矩阵性质的不同适用于不同的分解策略。
• DeepWalk： DeepWalk 是基于 word2vec 词向量提出来的。word2vec 在训练词向量时，将语料作为输入数据，而图嵌入输入的是整张图，两者看似没有任何关联。但是 DeepWalk 的作者发现，预料中词语出现的次数与在图上随机游走节点被访问到底的次数都服从幂律分布。因此 DeepWalk 把节点当做单词，把随机游走得到的节点序列当做句子，然后将其直接作为 word2vec 的输入可以节点的嵌入表示，同时利用节点的嵌入表示作为下游任务的初始化参数可以很好的优化下游任务的效果，也催生了很多相关的工作；
• Graph Neural Network： 图结合deep learning方法搭建的网络统称为图神经网络GNN

图神经网络

图神经网络(Graph Neural Network, GNN)是指神经网络在图上应用的模型的统称，根据采用的技术不同和分类方法的不同，又可以分为下图中的不同种类，例如从传播的方式来看，图神经网络可以分为图卷积神经网络（GCN），图注意力网络（GAT，缩写为了跟GAN区分），Graph LSTM等等，本质上还是把文本图像的那一套网络结构技巧借鉴过来做了新的尝试。图神经网络是一种直接作用在图结构上面的神经网络。

一、定义

在论文《Relational inductive biases, deep learning, and graph networks》中作者定义了图神经网络的通用结构，也就是现在的图神经网络的开山鼻祖 ，在这个框架中定义了和扩展了各种图神经网络，GN framework的主要计算单元是GN block，一个图到图的模块，它的输入是一个图 在图结构上进行计算然后得到的输出仍然是图结构的输出。在GN framework下，一个图可以被定义为一个三元组G=(u,V,E),u是图的全局表示，V={Vi},i=1:N^v代表图中N^v节点的集合，Vi表示节点i，E={(e_k,r_k,s_k)},k=1:N^e表示图中N^e条边的表示，e_k为边的表示r_k,s_k分别代表的是边的接收点和发送点。

每一个GN block包含三个更新函数Φ以及三个聚合函数ρ：

上式中E'_i={(e_k,r_k,s_k)},r_k=i.k=1:N^e,V’={V_i},i=1:N^v,E'=U_iE_i'={(e'_k,r_k,s_k)},k=1:N^e。

其中Φ^e应用于图中每条边的更新，Φ应用于图中每个节点的更新，Φ则用来更新图的全局表示；ρ函数将输入的表示集合整合为一个表示，该函数设计为 可以接收任意大小的集合输入，通常可以为加和、平均值或者最大值等不限输入个数的操作。

当一个GN block得到一个图G的输入时，计算通常从边到节点，再到全局进行。下图给出了一个GN block的更新过程。

一个GN block的计算可以被描述为如下几步：

1. $$\Phi^e$$更新每一条边，输入参数为边表示$$e_k$$，接收和发送节点的表示$$v_r_k$$和$$v_s_k$$以及全局表示$$u$$，输出为更新过的边表示$$$e'_k$；
2. $$ρ^(e \leftarrow v)$$用来有同一个聚合接收节点的边的信息，对节点i得到所有入边及邻近节点信息整合$$e'_i$$,用于下一步节点的更新；
3. $$\Phi^v$$更新每一个节点，输入为上文中的$$e'_i$$，节点表示$$v_i$$,以及全局表示$$u$$，输出为更新过的节点表示$$v'_i$$；
4. $$ρ^(e \leftarrow u)$$聚合图中所有边的信息得到边信息整合e(帽)；
5. $$ρ^(v \leftarrow u)$$通过聚合图中所有节点信息得到节点的信息整合$$\dot{v}$$（帽）；
6. $$\Phi^u$$更新全局的表示，输入为边信息整合e(帽)，节点信息整合$$\dot{v}$$（帽），以及节点表示$$u$$，输出为更新过的全局表示$$\dot{u}$$。 可以通过上述的更新步骤来套用目前的图神经网络算法，当然这里的步骤的顺序并不是严格固定的，比如可以先更新全局信息，再更新节点信息以及边的信息。

二、图神经网络用语节点分类

GNN的一个引用就是在节点分类上面，本质上图中的每一个节点都与一个标签相关联，然后通过一标记的标签来预测为标记的标签。在节点分类中每个节点v都可以个节点v都可以用其特征x_v表示并且与已标记的标签t_v相关联。给定部分标记的图G，目标是利用这些标记的节点来预测未标记的节点标签。它通过学习得到每个节点的d维向量（状态）表示为h_v，同时包含其相邻节点的信息。

x_co[v] 代表连接顶点v的边的特征，h_ne[v]代表顶点v的邻居节点的嵌入表示，x_ne[v]代表顶点v的邻居节点特征。f是将输入投影到d维空间的转移函数,由于要求出h_v的唯一解，我们应用Banach不动点理论重写上述方程进行迭代更新。

H和X分别表示所有h和x的连接,通过将状态h_v以及特征x_v传递给输出函数g来计算GNN的输出。

这里的f和g都可以解释为全连接前馈神经网络,L1损失可以直接表述为如下函数：

它可以通过梯度下降进行优化，但是该论文指出的原始GNN有三个主要局限：

1.如果放宽了“固定点”的假设，则可以利用多层感知器来学习更稳定的表示，并删除迭代更新过程。 这是因为在原始方法中，不同的迭代使用转移函数f的相同参数，而不同MLP层中的不同参数允许分层特征提取；

2.不能处理边缘信息（例如知识图谱中的不同边可能表示节点之间的不同关系）；

3. 固定点会限制节点分布的多样化，因此可能不适合学习节点表示。

虽然现在已经提出了几种GNN变体来解决上述问题。 但是他们不是论文的重点。

三、图卷积神经网络（GCN）

1.图卷积vs卷积

下图是图像卷积也就是通用cnn卷积的一个示例，数字图像是一个二维的离散信号，卷积过程就是利用一个卷积核在该图像矩阵上面滑动来提取特征，具体运算过程是：将图像上面的像素灰度值来与对应的卷积核上面的数值相乘，然后将相乘后的值相加作为卷积核对应的图像上面像素的灰度值。具体为什么要这么做可自行查看cnn的原理和定义，这里就不加阐述了，就把它当做一种定理来使用就行了。

用随机的共享的卷积核得到像素点的加权和从而提取到某种特定的特征，然后用反向传播来优化卷积核参数就可以自动的提取特征，是CNN特征提取的基石。

图像卷积

然而，现实中更多重要的数据集都是用图的形式存储的，例如社交网络信息，知识图谱，蛋白质网络，万维网等等。这些图网络的形式并不像图像，是排列整齐的矩阵形式，而是非结构化的信息，那有没有类似图像领域的卷积一样，有一个通用的范式来进行图特征的抽取呢？这就是图卷积在图卷积网络中的意义。

2.图卷积的形象话理解

图结构实例

我们先从其他的角度理解一下这个操作的物理含义，有一个形象化的理解，我们在试图得到节点表示的时候，容易想到的最方便有效的手段就是利用它周围的节点，也就是它的邻居节点或者邻居的邻居等等，这种思想可以归结为一句话：

图中的每个结点无时无刻不因为邻居和更远的点的影响而在改变着自己的状态直到最终的平衡，关系越亲近的邻居影响越大。

实际上从邻居节点获取信息的思想在很多领域都有应用，例如word2vec，例如pagerank。关于这个点展开的内容文章[2]有非常详细的解释。

更加细节的如何从傅立叶变换到拉普拉斯算子到拉普拉斯矩阵的数学推倒可以转向博客[7]，为了避免数学功底没有那么强的初学者（比如我）被绕晕，我们先建立大纲，不要太发散。

3.图相关矩阵的定义

有什么东西来度量节点的邻居节点这个关系呢，学过图论的就会自然而然的想到邻接矩阵和拉普拉斯矩阵。举个简单的例子，对于下图中的左图（为了简单起见，举了无向图且边没有权重的例子）而言，它的度矩阵 D ，邻接矩阵A和拉普拉斯矩阵L, 分别如下图所示，度矩阵D只有对角线上有值，为对应节点的度，其余为0；邻接矩阵A只有在有边连接的两个节点之间为1，其余地方为0；拉普拉斯矩阵L为。但需要注意的是，这是最简单的一种拉普拉斯矩阵，除了这种定义，还有接下来介绍的几种拉普拉斯矩阵。

一个图的度矩阵，邻接矩阵和拉普拉斯矩阵

4.图卷积的通式

任何一个图卷积层都可以写成这样一个非线性函数：

H^{l+1}=f(H^l,A)

H^0=X为第一层的输入，X∈R^{N*D},N为图节点个数，D为每个节点特征向量的维度，A为邻接矩阵，不同模型在于使用的函数f不同。

拉普拉斯矩阵实现1

其中W^l为第l层的权重参数，σ(.)是非线性激活函数，列入ReLU。

这种思路是基于节点特征与其所有邻居节点有关的思想。邻接矩阵A与特征H相乘，等价于，某节点的邻居节点的特征相加。这样多层隐含层叠加，能利用多层邻居的信息。

但这样存在两个问题：

• 没有考虑节点自身对自己的影响；
• 邻接矩阵 没有被规范化，这在提取图特征时可能存在问题，比如邻居节点多的节点倾向于有更大的影响力。

因此实现二和实现三针对这两点进行了优化

拉普拉斯矩阵实现2

拉普拉斯矩阵 L=D-A，学名Combinatorial Laplacian，是针对实现一的问题1的改进：

• 引入了度矩阵，从而解决了没有考虑自身节点信息自传递的问题

拉普拉斯矩阵实现3

这里的拉普拉斯矩阵本质上还是实现一的两个问题进行的改进:

• 引入自身度矩阵，解决自传递问题；
• 对邻接矩阵的归一化操作，通过对邻接矩阵两边乘以节点的度开方然后取逆得到。 具体到每一个节点对i，j，矩阵中的元素由下面的式子给出（对于无向无权图）：

其中deg(v_i),deg(v_j)分别为节点j和j的度，也就是度矩阵在i和j点的值。

可能有一点比较疑惑的是怎么两边乘以一个矩阵的逆就归一化了？ 这里需要复习到矩阵取逆的本质是做什么。

我们回顾下矩阵的逆的定义，对于式子A*X=B，假如我们希望求矩阵X，那么当然是令等式两边都乘以A^{-1}，然后式子就变成了X=A^{-1}*A*X=A^{-1}*B。

举个例子对于，单个节点运算来说，做归一化就是除以它节点的度，这样每一条邻接边信息传递的值就被规范化了，不会因为某一个节点有10条边而另一个只有1条边导致前者的影响力比后者大，因为做完归一化后者的权重只有0.1了，从单个节点上升到二维矩阵的运算，就是对矩阵求逆了，乘以矩阵的逆的本质，就是做矩阵除法完成归一化。但左右分别乘以节点i,j度的开方，就是考虑一条边的两边的点的度。

参考文献：

[1]  https://  zhuanlan.zhihu.com/p/77729049 图嵌入的分类

[2]  https://www.zhihu.com/question/54504471/answer/630639025 关于图卷积的物理学解释

[3] https://www.zhihu.com/question/54504471/answer/332657604拉普拉斯公式推倒细节，包括谱分解和傅立叶变换

[4] http://tkipf.github.io/graph-convolutional-networks 两篇论文细讲

[5] https://github.com/conferencesub/ICLR_2020各种图卷积核比较

[6] https://persagen.com/files/misc/scarselli2009graph.pdfGNN首次被提出的paper

[7] https://zhuanlan.zhihu.com/p/85287578 拉普拉斯矩阵和拉普拉斯算子的关系

[8] https://github.com/opprash/braveRL/tree/master/GNN 图神经网络及其定义

[9]https://yq.aliyun.com/articles/694432 图神经网络简介

[10]https://mp.weixin.qq.com/？s__biz=MzI4MDYzNzg4Mw==&mid=2247490775&idx=3&sn=d14a585aa789d057f52396241b8428b1&chksm=ebb42403dcc3ad150dec4f57242ea2f8defb157d0a6ee58fce82f7e1fd628629218a9a5ff4d4&mpshare=1&scene=23&srcid=&sharer_sharetime=1579417079575&sharer_shareid=fc524225b6e78f30e915df15248fac48#rd 一文读懂图卷积GCN