目录
1.论文资料
作者：曾涵清博士，南加州大学
论文：在 ICLR 2020 上发表了GraphSAINT: Graph Sampling Based Inductive Learning Method
代码：https://github.com/GraphSAINT/GraphSAINT
2.传统GNN挑战：邻居爆炸（Neighbor Explosion）
邻居爆炸：
GNN会不断地聚合图中相邻节点的信息，则L-层的GNN中每个目标节点都需要聚合原图中L-hop以内的所有节点信息。在大图中，邻节点的个数可以随着L指数级增长。
- 邻点爆炸式增长，使得GNN的minibatch训练极具挑战性。
- 受显存的因素限制，GNN在不损失精度的前提下，难以高效地被拓展到大于两层的模型（否则指数爆炸）。
3.现有方法：图采样
- Layer-wise Sampling：
- 邻居爆炸：在矩阵采样多层时，假设每层采样n个邻居，则会导致级别的节点扩充速度。
- 领接矩阵稀疏：在矩阵采样的过程中，会导致邻接矩阵稀疏化，丢失一些本来存在的边。
- 时间耗费高：每一层卷积都要采样，这就导致计算的时间耗费。
前人工作提出了众多基于采样邻居节点的方法，并利用多类型的聚合函数提高模型的表达能力。大部分现有工作都在探索如何通过对GNN每层的节点进行采样，以降低训练成本。
- Graph-wise Sampling：
- 从原图上采样一个子图下来，在这个子图上做局部的、完全展开的GCN。
- 解决了邻居采样的指数化问题，而且可以对采下来的子图进行直接的并行化，就大大的改进了效率。即，可以在preprocess阶段提前采样图，并且可以进行mini batch的加速。
- 但是这样的采样往往会丢失一些信息。
4.GraphSAINT：截然不同的采样的视角
- 属于Graph sampling。
- 从原图中采样子图，在子图上使用GCN学习。
- 基于极其轻量级的子图采样算法，同时实现了在准确率和复杂度上的显著提升。
- 提出了适用于大图以及深层网络的，通用的训练框架。
- 在标准的Reddit数据集上，以100倍的训练时间提速，提高了1%以上的准确率。
4.1.算法流程
将全图进行多次采样，在得到的sub-graph上进行全GCN，然后将多个sub-graph的信息融合起来。
4.2.子图采样
本文的采样是基于节点的连通性：
- 相互影响较大的节点应在同一子图中采样，intra sub-graph的节点是具有强联系的，但这就引入了采样的bias。理想的SAMPLE要求衡量节点连接的联合信息以及属性。但这种算法可能具有很高的复杂度，所以，为简单起见，从图连接性角度定义“影响力”，并设计基于拓扑的采样器。
2.为了消除保留图连通性特征的采样器引入的偏差，作者引入自行设计的归一化技术，以消除偏差，使得估计量无偏。归一化系数通过pre-processing估计出来。 - 每条边的采样概率均不可忽略，使得神经网络能够探索整个特征和标签空间。
- 考虑variance reduction（降低采样方差），旨在得到最小方差的边采样概率。
重点是估计每个节点、边、子图的采样概率。
节点采样概率：
边采样概率:
子图采样概率：
这篇文章的采样sub-graph的概念应该是介于AS-GCN的“有条件的采样全图”和ClusterGraph的“将图聚类后采样”之间。
由于采样的存在，FastGCN, AS-GCN等在不同的layer计算的是不同的图结构，而GraphSAINT, ClusterGraph可以看做在不同layer都对同一个graph进行特征提取。
4.3.实验结果：优于GCN, SAGE…
原因分析：
- GCN相当于full gradient descent，没有batch泛化好。
- GraphSAGE采样batch方差大，收敛性不好。
参考文献
https://zhuanlan.zhihu.com/p/107107009
https://rman.top/2020/05/20/GraphSAINT%E4%B8%80%E7%A7%8D%E6%97%A0%E5%81%8F%E7%9A%84%E5%9B%BE%E9%87%87%E6%A0%B7%E6%96%B9%E6%B3%95/
https://www.readercache.com/q/EP8b9Dpq4ZAw0ENEKGRr1zGKX5MRjeNY