白话GNN原理（一）

一、关于GNN

不知不觉图神经网络已经大火了好几年了，然而还是有很多炼丹师没有涉足这块领域。作者知道 GNN 这个名词，还是因为 GCN 这篇论文大火。相信还是有很多人和作者刚开始学习 GNN 一样，分不清 GNN 和 GCN的区别。作者希望这一系列的学习笔记，能帮助读者，即使 GNN 公式看不懂，也能灵活运用 GNN 去解决我们遇到的问题。

二、经典论文《The Graph Neural Network Model》

这篇论文首次提出了GNN模型，整片论文的结构先介绍了如何用符号表达问题，以及各种定义；然后介绍了GNN模型的学习算法；第三个部分介绍了算法的负责度(非本篇笔记重点)；最后是实验和结论。本篇笔记结构也类似。先简单介绍下GNN模型。CNN和RNN大家应该很熟悉，它们可以将一张图或者一句话(切词后，每个词看做一个节点，其实是个有向无环图)embeding成一个m维度向量，最后接softmax或其他层做分类或者回归。GNN本质也是把图或图中节点映射成一个m维向量，即和。论文中把图算法按应用分成了两类，一个是graph-focused，另一个是node-focused，如下图所示：

该图左边通过元素和分子结构判断该分子类型，因此是graph-focused。右边是个二分类问题，判断节点是否为房子的一部分，图中黑色节点是正例，因此是node-focused。GNN不仅要挖掘出节点的信息，同时还要挖掘出节点直接的拓扑关系。

三、数学描述与相关定义

图由节点集合和边集合组成。表示节点的所有邻居节点，表示和节点相连的所有边。表示节点的特征向量，表示连接和节点的边的特征向量，表示整个图的特征向量。例如上图房子，节点的特征向量是由节点图形的面积，边界，颜色等属性表达的；边的特征向量是由节点之间距离，角度等表达的。论文中又提到一个概念，把图分为positional和nonpositional。positional就是用一定的规则，给每个节点的邻居节点编号，论文中称这个规则叫injective function:。通俗点说我们每个人都是一个节点，我们的通讯录按人名首字母排序编号。

模型的训练数据定义如下：

是一系列用于训练的图，和是图的节点和边，是图的第个节点，是训练集中图的数量，表示图的节点个数。三元组，想表达的就是图中第个节点的label是。

一个节点的特征向量除了由节点本身特征向量决定，还有其邻居节点(和)和边()决定。如下图：

该图表示号节点由各种信息（节点，边，拓扑关系）聚合而成的embedding。这种映射关系，论文中定义为global transition function。论文同时提出另一种映射，将和通过函数映射成最终embeding，用于分类或回归，论文称为全局输出方程(global output function),如下式：

对于上式，论文提到3点注意事项: 一、在中其实包含了的信息，也许是多余的。二、上式支持有向图，只要在中加一项表示方向即可。三、,可能依赖于节点，简单来说每个node都有属于自己的,，论文中的模型为了简化，并不考虑这一点。

论文接下来提到巴拿赫不动点定理(Banach’s theorem)，有兴趣的可以去看看百度百科公式推导。不想看推导就记住这个有趣的事实：若把某国的地图缩小后印在该国领土内部，那么在地图上有且仅有这样一个点，它在地图中的位置也恰巧表示它所落在的土地位置。

论文提出不动点定理就是想类比到GNN中，把图中任意节点看作图上的不动点，fw函数是个缩放函数，通过不断的缩放，最终会收敛到一个基本不变的向量，即。对于nonpositional的图, 函数可以写成下式：

上式函数把节点的每个邻居节点的信息按某种方式aggragate后累和起来(因为邻居节点没有顺序的概念，所以可以累和)作为的embedding。总结一下，本文提出的model就是通过函数不断迭代，使得节点向量收敛到，最后通过函数映射到最终向量，如下图所示:

四个节点经过次的迭代(是不是有点RNN即视感)，最终通过函数得到最终向量，如下式:

四、学习算法

回顾下训练数据的定义，有三元组，就可以定义损失如下损失函数：

现在就可以前向传播和梯度下降了，梯度是对求偏导。论文提到，后向传播过程要保存所有样本的中间状态信息，如果样本数量和过大的话，内存吃不消，又因为x是在收敛的，所以我们可以认为在时，，从而减小内存。接下来论文提出了两个理论，如果和对，可导，那也可导，证明略，可以参考论文。第二个理论定义了一个公式并证明了向量是收敛的，：

最后推导出下式(推导过程见论文):

学习算法如下图：

对于，和具体如何实现，论文认为并没有任何限制，直接用mlp即可，对于，论文中给了两种方案:

1. 线性GNN

这样设计保证了在任意下能收缩到一个恒定的向量。

2. 非线性GNN

也使用mlp，但是这样无法保证了在任意下能收缩到一个恒定的向量，所以损失函数需要加正则项。

五、实验和结论

论文在贴近现实应用的3个场景进行实验，分别为子图匹配，识别分子是否突变，和网页排序。因为nonpositional的表现要比positional的要略好，所以实验中只有nopositional的线性或非线性模型。论文还强调数据集是严格拆分成训练，验证和测试集，最后各项表现（准确率，mse）都最好。最后论文提到，GNN目前处理的都是静态图，如果图是动态变化的（如社交网络）该如何处理？还有就是如果节点直接关系未知，需要自己去挖掘呢？这些都是论文未来的研究方向。

六、参考文献

1. The Graph Neural Network Model

欢迎有兴趣的朋友欢迎关注我们的公众号，我是一品炼丹师十方。后续会分享GNN各种变体，graphsage，GCN以及代码实战。