在GCN中，需要从每一层的邻居中传递节点的信息，随着邻居层数的增多，节点呈指数级增长，因此GCN要想对特别深的网络进行学习，需要采用采样的方法。一般的采样是通过固定顶点邻居的个数来对邻居进行采样，本文提出了一种与以往完全不同的方法，通过在原图中采样子图，对这个子图进行完全的GCN学习。在采样子图的过程中，直观上需要尽可能保留那些对顶点影响比较大的节点，因此可能会引入采样的偏差，为解决这一问题，本文通过在聚合中引入节点和边被采样的概率来做normalization消除偏差。为进一步提升训练质量，本文通过量化邻居的影响力设计了一种轻量级的采样算法来降低采样方差。最后实验证明，本文的方法能起到非常有效的作用。

1、背景

在现在的图卷积中，由于图的大小可能非常大，传统的在全图上进行图卷积的操作往往是不现实的。因此往往采用了图采样的方法。图采样大致会分为：Layer Sampling 和 Graph Sampling两种。但是这两种方法都存在着一些问题。

Layer Sampling：

• 邻居爆炸：GNN会不断地聚合图中相邻节点的信息，则L-层的GNN中每个目标节点都需要聚合原图中L-hop以内的所有节点信息。在大图中，邻节点的个数可以随着L指数级增长
• 邻点爆炸式增长，使得GNN的minibatch训练极具挑战性。
• 时间耗费高：每一层卷积都要采样，这就导致计算的时间耗费。
  

Graph Sampling:

Graph Sampling是一种相对好的采样方法，可以在preprocess阶段提前采样图，并且可以进行mini batch的加速。但是这样的采样往往会丢失一些信息。

本文为了解决以上问题，提出了一种在图上进行Graph Sampling的相对较好的方法。

2、GraphSAINT

• 属于$Graph\ sampling$Graph sampling。
• 从原图中采样子图，在子图上使用$GCN$GCN学习。
• 基于极其轻量级的子图采样算法，同时实现了在准确率和复杂度上的显著提升。
• 提出了适用于大图以及深层网络的，通用的训练框架。

2.1 算法流程

将全图进行多次采样，在得到的sub-graph上进行全GCN，然后将多个sub-graph的信息融合起来。

2.1.1 normalization techniques to eliminate biases

1、定义函数

2、minibatch的无偏估计

• 根据无偏估计，近似消除采样子图的偏差

证明：
期望求解公式：

2.1.2 minibatch loss

2.1.3 VARIANCE

• 在Layer采样过程中，我们希望采样之后产生的偏差最小。这个偏差可以由如下的公式得出:

我们希望如下的偏差最小，经过一系列推导，在$P_e$Pe​等于如下值的时候，偏差达到最小。

证明：
基本公式

2.2 子图采样

本文的采样是基于节点的连通性：

• 1、相互影响较大的节点应在同一子图中采样，intra sub-graph的节点是具有强联系的，但这就引入了采样的bias。理想的SAMPLE要求衡量节点连接的联合信息以及属性。但这种算法可能具有很高的复杂度，所以，为简单起见，从图连接性角度定义“影响力”，并设计基于拓扑的采样器。
• 2.为了消除保留图连通性特征的采样器引入的偏差，作者引入自行设计的归一化技术，以消除偏差，使得估计量无偏。归一化系数通过pre-processing估计出来。
• 3、每条边的采样概率均不可忽略，使得神经网络能够探索整个特征和标签空间。
  考虑variance reduction（降低采样方差），旨在得到最小方差的边采样概率。

重点是估计每个节点、边、子图的采样概率。
节点采样概率：

边采样概率:
2.2.3计算需要所有子图中边两端的聚合信息来求得计算量十分大，于是作者采用了如下的简化公式：

边的采样概率等于两个节点的倒数之和，来进行Graph的采样

子图采样概率：

3、期望、方差、协方差

1、期望

2、方差

3、协方差

4、相关系数

作者：曾涵清博士，南加州大学
论文：在 ICLR 2020 上发表了GraphSAINT: Graph Sampling Based Inductive Learning Method
代码：https://github.com/GraphSAINT/GraphSAINT