3.Subgraph sampling
3.1 cluster-GCN
论文标题：Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
论文来源：KDD2019
论文方向：图卷积网络
论文链接：https://arxiv.org/abs/1905.07953
**主要思路：**为了限制邻居数量的扩张和提高表示的效用，将图分割成多个cluster（限制子图的规模），在cluster上进行结点的batch training。
使用METIS进行图分割，使得cluster内的边多，cluster之间的边少。
具体来说，对于图 分割成 个部分， ， 由第 个分割中的结点构成， 仅由 中结点之间的边构成，故有 个子图：
因此，邻居矩阵可以分为 的子矩阵：
同理也可以对结点特征矩阵 和 进行分割， 。
Loss可以分解为：
两种训练方式：
1.随机挑选一个cluster进行训练（coarse clustering）
2.随机挑选 k 个cluster，然后连接他们再进行训练（stochastic multiple clustering）
3.2 GraphSAINT
论文标题：GraphSAINT: Graph Sampling Based Inductive Learning Method
论文来源：ICLR2020
论文方向：图卷积网络
论文链接：https://arxiv.org/abs/1907.04931
主要思路：先采样子图，之后在子图上做完全连接的GCN。
通过在子图的GCN上添加归一化系数（通过预处理计算）来使得估计量无偏，Aggregation 的normalization为：
Loss的normalization为：
从而：
一个好的Samper应该使得：
1、相互具有较大影响的结点应该被sample到同一个子图；
2、每条边多有不可忽略的抽样概率。
设计Sampler减少评估的方差：
Random node sampler：
Random edge sampler：
Random walk based sampler：
4.部分实验
