本文从一个更直观的角度对当前经典流行的GNN网络，包括GCN、GraphSAGE、GAT、GAE以及graph pooling策略DiffPool等等做一个简单的小结。
近年来，深度学习领域关于图神经网络（Graph Neural Networks，GNN）的研究热情日益高涨，图神经网络已经成为各大深度学习顶会的研究热点。GNN处理非结构化数据时的出色能力使其在网络数据分析、推荐系统、物理建模、自然语言处理和图上的组合优化问题方面都取得了新的突破。
图神经网络有很多比较好的综述[1][2][3]可以参考，更多的论文可以参考清华大学整理的GNN paper list[4] 。
本篇文章将从一个更直观的角度对当前经典流行的GNN网络，包括GCN、
GraphSAGE、GAT、GAE以及graph pooling策略DiffPool等等做一个简单的小结。
笔者注：行文如有错误或者表述不当之处，还望批评指正！
一、为什么需要图神经网络？
随着机器学习、深度学习的发展，语音、图像、自然语言处理逐渐取得了很大的突破，然而语音、图像、文本都是很简单的序列或者网格数据，是很结构化的数据，深度学习很善于处理该种类型的数据（图1）。
图1
然而现实世界中并不是所有的事物都可以表示成一个序列或者一个网格，例如社交网络、知识图谱、复杂的文件系统等（图2），也就是说很多事物都是非结构化的。
图2
相比于简单的文本和图像，这种网络类型的非结构化的数据非常复杂，处理它的难点包括：
- 图的大小是任意的，图的拓扑结构复杂，没有像图像一样的空间局部性
- 图没有固定的节点顺序，或者说没有一个参考节点
- 图经常是动态图，而且包含多模态的特征
那么对于这类数据我们该如何建模呢？能否将深度学习进行扩展使得能够建模该类数据呢？这些问题促使了图神经网络的出现与发展。
二. 图神经网络是什么样子的？
相比较于神经网络最基本的网络结构全连接层（MLP），特征矩阵乘以权重矩阵，图神经网络多了一个邻接矩阵。计算形式很简单，三个矩阵相乘再加上一个非线性变换（图3）。
图3
因此一个比较常见的图神经网络的应用模式如下图（图4），输入是一个图，经过多层图卷积等各种操作以及激活函数，最终得到各个节点的表示，以便于进行节点分类、链接预测、图与子图的生成等等任务。
图4
上面是一个对图神经网络比较简单直观的感受与理解，实际其背后的原理逻辑还是比较复杂的，这个后面再慢慢细说，接下来将以几个经典的GNN models为线来介绍图神经网络的发展历程。
三、图神经网络的几个经典模型与发展
1 . Graph Convolution Networks(GCN)[5]
GCN可谓是图神经网络的“开山之作”，它首次将图像处理中的卷积操作简单的用到图结构数据处理中来，并且给出了具体的推导，这里面涉及到复杂的谱图理论，具体推到可以参考[6][7]。推导过程还是比较复杂的，然而最后的结果却非常简单( 图5)。
图5
我们来看一下这个式子，天呐，这不就是聚合邻居节点的特征然后做一个线性变换吗？没错，确实是这样，同时为了使得GCN能够捕捉到K-hop的邻居节点的信息，作者还堆叠多层GCN layers，如堆叠K层有：
上述式子还可以使用矩阵形式表示如下，
其中 是归一化之后的邻接矩阵， 相当于给 层的所有节点的embedding做了一次线性变换，左乘以邻接矩阵表示对每个节点来说，该节点的特征表示为邻居节点特征相加之后的结果。（注意将 换成矩阵 就是图3所说的三矩阵相乘）
那么GCN的效果如何呢？作者将GCN放到节点分类任务上，分别在Citeseer、Cora、Pubmed、NELL等数据集上进行实验，相比于传统方法提升还是很显著的，这很有可能是得益于GCN善于编码图的结构信息，能够学习到更好的节点表示。
图6
当然，其实GCN的缺点也是很显然易见的，第一，GCN需要将整个图放到内存和显存，这将非常耗内存和显存，处理不了大图；第二，GCN在训练时需要知道整个图的结构信息(包括待预测的节点), 这在现实某些任务中也不能实现(比如用今天训练的图模型预测明天的数据，那么明天的节点是拿不到的)。
2. Graph Sample and Aggregate(GraphSAGE)[8]
为了解决GCN的两个缺点问题，GraphSAGE被提了出来。在介绍GraphSAGE之前，先介绍一下Inductive learning和Transductive learning。注意到图数据和其他类型数据的不同，图数据中的每一个节点可以通过边的关系利用其他节点的信息。这就导致一个问题，GCN输入了整个图，训练节点收集邻居节点信息的时候，用到了测试和验证集的样本，我们把这个称为Transductive learning。然而，我们所处理的大多数的机器学习问题都是Inductive learning，因为我们刻意的将样本集分为训练/验证/测试，并且训练的时候只用训练样本。这样对图来说有个好处，可以处理图中新来的节点，可以利用已知节点的信息为未知节点生成embedding，GraphSAGE就是这么干的。
GraphSAGE是一个Inductive Learning框架，具体实现中，训练时它仅仅保留训练样本到训练样本的边，然后包含Sample和Aggregate两大步骤，Sample是指如何对邻居的个数进行采样，Aggregate是指拿到邻居节点的embedding之后如何汇聚这些embedding以更新自己的embedding信息。下图展示了GraphSAGE学习的一个过程，
图7
第一步，对邻居采样
第二步，采样后的邻居embedding传到节点上来，并使用一个聚合函数聚合这些邻居信息以更新节点的embedding
第三步，根据更新后的embedding预测节点的标签
接下来，我们详细的说明一个训练好的GrpahSAGE是如何给一个新的节点生成
embedding的（即一个前向传播的过程），如下算法图：
首先，(line1)算法首先初始化输入的图中所有节点的特征向量，(line3)对于每个节点 ，拿到它采样后的邻居节点 后，(line4)利用聚合函数聚合邻居节点的信息，(line5)并结合自身embedding通过一个非线性变换更新自身的embedding表示。
注意到算法里面的 ，它是指聚合器的数量，也是指权重矩阵的数量，还是网络的层数，这是因为每一层网络中聚合器和权重矩阵是共享的。网络的层数可以理解为需要最大访问的邻居的跳数(hops)，比如在图7中，红色节点的更新拿到了它一、二跳邻居的信息，那么网络层数就是2。为了更新红色节点，首先在第一层(k=1)，我们会将蓝色节点的信息聚合到红色解节点上，将绿色节点的信息聚合到蓝色节点上。在第二层(k=2)红色节点的embedding被再次更新，不过这次用到的是更新后的蓝色节点embedding，这样就保证了红色节点更新后的embedding包括蓝色和绿色节点的信息，也就是两跳信息。
为了看的更清晰，我们将更新某个节点的过程展开来看，如图8分别为更新节点A和更新节点B的过程，可以看到更新不同的节点过程每一层网络中聚合器和权重矩阵都是共享的。
图8
那么GraphSAGE Sample是怎么做的呢？GraphSAGE是采用定长抽样的方法，具体来说，定义需要的邻居个数 ，然后采用有放回的重采样/负采样方法达到 。保证每个节点（采样后的）邻居个数一致，这样是为了把多个节点以及它们的邻居拼接成Tensor送到GPU中进行批训练。
那么GraphSAGE 有哪些聚合器呢？主要有三个，
这里说明的一点是Mean Aggregator和GCN的做法基本是一致的（GCN实际上是求和）。
到此为止，整个模型的架构就讲完了，那么GraphSAGE是如何学习聚合器的参数以及权重矩阵 呢？如果是有监督的情况下，可以使用每个节点的预测lable和真实lable的交叉熵作为损失函数。如果是在无监督的情况下，可以假设相邻的节点的embedding表示尽可能相近，因此可以设计出如下的损失函数，
那么GrpahSAGE的实际实验效果如何呢？作者在Citation、Reddit、PPI数据集上分别给出了无监督和完全有监督的结果，相比于传统方法提升还是很明显。
至此，GraphSAGE介绍完毕。我们来总结一下，GraphSAGE的一些优点，
（1）利用采样机制，很好的解决了GCN必须要知道全部图的信息问题，克服了GCN训练时内存和显存的限制，即使对于未知的新节点，也能得到其表示
（2）聚合器和权重矩阵的参数对于所有的节点是共享的
（3）模型的参数的数量与图的节点个数无关，这使得GraphSAGE能够处理更大的图
（4）既能处理有监督任务也能处理无监督任务
（就喜欢这样解决了问题，方法又简洁，效果还好的idea！！！）
当然，GraphSAGE也有一些缺点，每个节点那么多邻居，GraphSAGE的采样没有考虑到不同邻居节点的重要性不同，而且聚合计算的时候邻居节点的重要性和当前节点也是不同的。
