图采样相关工作要点_vr-gcn

相关工作笔记

1 原始GCN

全批次梯度下降（Full-batch gradient descent），要一次性计算整个图所有节点的梯度，需要存储所有中间的node的embeddings，大图无法放入显存。

层间传播规则，相当于加权聚合邻居和自身：

显存占用大，每个epoch的时间短，收敛效果不好。

2 GraphSAGE

通过引入邻居采样的方法，使得GCN能以Mini-batch的方式执行梯度下降。大大减少了显存占用，并在每个epoch可以执行多次更新，从而加快了收敛速度。如下图就是一个随机邻居采样的例子。

显存占用降低，每个epoch的时间变长，收敛效果较好。

然而：

a) 显存仍可能不够，比如我们在第一层采样5个，第二层采样10个，则单个样本（节点）在两层sage的训练过程中 需要保存50个node的embedding向量；

b) 存在方差问题，训练和推断过程存在不一致，因为infer的过程中采样的结果是会发生变化的，这导致在不限定随机种子的情况下，多次infer的结果会存在差异。

3 FastGCN：

不同于GraphSage是node level sampling，FastGCN使用的是layer level sampling。在图神经网络每一层都进行采样。但其采样没有包含节点间的依赖关系。

显存占用降低，每个epochs的时间变长，收敛效果较好，相较于GraphSage对GCN的线性提升，fastGCN的提升是数量级的；

4.VR-GCN

VR-GCN的关键在于每层卷积中引入关系的表示，使得实体获得邻居embedding时能区分邻居实体是头实体还是尾实体，符合知识图谱的应用场景。具体实现如下图：

在采样方面： GraphSAGE对邻居节点的采样个数太多。而对于使用layer-wise的FastGCN，其采样没有包含节点间的依赖关系。VR-GCN提出部分没采样到的节点就采用历史信息，这样可以减小邻域采样节点的数目。如下图b，红色节点代表随机邻居采样到的节点。图c中蓝色节点代表是其k阶邻居但未被邻居采样的点。在训练中我们使用红色点新一轮聚合的信息和蓝色点的历史信息。但它依旧和GraphSage一样需要将所有节点的所有中间的embeddings存储在内存中，从而可能导致显存溢出的问题。

显存占用高，每个epoch的时间短，收敛效果好。

 5.ClusterGCN笔记

ClusterGCN基于图聚类（社群发现）改进了GCN的训练。ClusterGCN的思想非常简单直接，既然GCN没法一次性处理一个大图，那就将大图切割为小的子图，然后GCN分别在不同小子图上训练，这样不仅可以mini-batch 训练，还可以有效的降低显存的压力，一个子图的大小有限因此深层GCN也可以运行。ClusterGCN进行图划分的方法使用的是是图聚类，也即社区发现。

由于社区发现算法倾向于将有更多连接边的点划分到一个区域，可以使得该区域内的点不会因为像下图左侧那样以较小的概率选择到可以去往另外一个区域的边，从而导致采样子图范围过大。同样，由于区域内的点联系更紧密，这样的划分对于精度的影响较小。

6. GraphSAINT笔记

GraphSAINT引入一种基于抽样子图的图神经网络模型，每个minibatch的计算在抽样子图上进行，不会出现“邻居爆炸“现象，该抽样方法在理论上有无偏性和最小方差。

GraphSAINT提出了正则化和采样方法来提高训练的效果。保留G的连通性特征的采样器几乎不可避免地会将偏差引入到小批量估计中，因此通过normalization来消除偏差。

GraphSAINT提出了三种轻量级采样器，具体实现伪代码如下图所示。这三种采样器分别是：

        1. 随机节点采样器

        

                根据点的邻接矩阵计算采样概率进行随机采样。

        2. 随机边采样器

        

        根据边的度计算采样概率进行随机采样

        3. 随机游走采样器

        总结一个基于通常的random walk的采样器，随机抽取r个source顶点，每个顶点随机游走h阶邻居。

        还引用了一个多维度的random walk的采样器，V是采样到的节点，VFS是可作为游走顶点的点，同样随机抽取r个source顶点加入V和VFS，根据节点度计算概率从VFS随机抽取一个点作为顶点随机游走一个邻居加入V和VFS，并将该顶点移出VFS避免游走的不是一条路径而变成树。