引言
图卷积网络GCN取得了非常好的效果。
对于小型图，可以全部加载到内存中，每层Layer的卷积操作都会遍历全图。
对于中大型图，全部加载到内存的做法，显然不能满足需求。我们会使用mini-batch而不是全图来进行计算。
下面将介绍三种目前常见的Batch技巧，分别来自GraphSage和ScalableGCN。
1. GraphSage Batch技巧
如上图所示，h0是模型inputs数据。3层图卷积Layers，分别是h1, h2, h3。
第k层
中的每个点对应的
通过下面公式来更新
先通过AGGREGATE算子将邻居节点的embedding聚集起来，再和节点自身的embedding信息combine，用输出结果来更新自身embedding。
我们可以观察到，为了计算最后一层图卷积Layer h3的某个点的embedding，只需要h3->h2->h1->h0中涉及到的点（上图中蓝色的点）。相对于全部的点（灰色+蓝色的点），这个计算范围已经大大缩小了。考虑到有些点可能关联非常多的邻接点，如果使用全部邻接点来计算AGGREGATE，那么计算复杂度将会不可控。
为了解决这个问题，GrapheSage提出抽样邻接点的方法。模型限制每个节点抽样邻接点的数量m，m是一个可配置的超参数。如果m值越大，那么模型计算越准确，但是计算代价也越大。反之m值越小，模型计算越不准确，但是计算代价也越小。
具体采样的方式是：
- 当邻接点数量小于m时，通过重复采样的方式补齐到m个
- 当邻接点数量大于m时，从中随机抽取m个
GraphSage采取Uniform采样方式，是基于所有邻接点的重要性是一样的假设。这个假设在很多实际问题中是不成立的，之后的论文里通过使用Importance Sampling或者引入Attention机制来进行优化。
使用邻接点数为m的采样之后，对于L层的图卷积网络，一个mini-batch中就只会涉及到
个节点，避免了对全图的遍历。
2. ScalableGCN Batch技巧
ScalableGCN是阿里妈妈提出的一种在大规模图上加速Mini-batch GCN训练速度方法。这个方法也包含在最近开源的大规模分布式图学习框架Euler里面。
ScalableGCN的官方介绍链接是
alibaba/eulergithub.com
这个wiki里面方法介绍的比较粗略，下面我会结合实现代码细节，具体介绍ScalableGCN算法。
图3，取自https://github.com/alibaba/euler/wiki/ScalableGCN
在第一部分里面，我们介绍了GraphSage采用的batch方式，虽然相比于全图计算，已经将计算量大幅减少，但是可以看到它的复杂度还是和卷积层数L成指数级关系。
在
图1中低阶的embedding（比如h0, h1, h2）会在计算不同点的高阶embedding（h3）时，被大量重复使用。如果我们把这部分低阶的embedding缓存起来，就可以减少除了自己节点计算以外，其他邻接点的计算。
具体地，对于
层GCN模型，开辟存储空间：
，将mini-batch SGD中顶点最新的前
层的embedding存储起来。同时，我们修改GCN模型为：
即在汇聚的时候使用缓存中的embedding值，这样一来我们只需计算mini-batch中的样本顶点的卷积结果，无需对扩散后的
阶所有邻接顶点进行卷积计算。我们用中心顶点（图3中蓝色节点）的embedding
更新
。
self
源码中使用trainable=False的tf variable来存储前
层的embedding。trainable设为False是因为这部分缓存的embedding不需要参与反向求导。
for
当顶层node_embedding计算更新之后，我们用这个更新之后的embedding值来更新stores里面对应节点的缓存。
下面介绍模型的反向求导过程
图4，取自https://github.com/alibaba/euler/wiki/ScalableGCN
我们开辟存储空间：
来存储前
层缓存embedding的导数。
self
类似的源码中使用trainable=False的tf variable来存储这部分导数。
因为前
层缓存embedding是trainable为False的variable，所以我们需要手动通过tf.gradients来计算对应的导数，并存到graident_stores缓存里面。源码实现如下
for
下面我们需要通过Back-Propagation来更新模型参数
。
如果没有因为缓存数据结构，更新模型参数很简单，只需要执行optimizer.minimize(loss)，tensorflow就会自动更新参数
。
但是这里我们为了避免重复计算引入了缓存结构(trainable=False的variable)，这些variable的导数是我们手动掉tf.gradient接口计算出来的。根据链式求导法则
其中
就是graident_stores缓存
。为了更新
，我们只需要将loss改为
，再通过optimizer.minimize就可以更新参数
了。具体实现如下
def