Datawhale提供的课程链接：https://github.com/datawhalechina/team-learning-nlp/blob/master/GNN
一、引言
图神经网络已经成功地应用于许多节点或边的预测任务，然而，在超大图上进行图神经网络的训练仍然具有挑战。普通的基于SGD的图神经网络的训练方法，要么面临着随着图神经网络层数增加，计算成本呈指数增长的问题，要么面临着保存整个图的信息和每一层每个节点的表征到内存（显存）而消耗巨大内存（显存）空间的问题。虽然已经有一些论文提出了无需保存整个图的信息和每一层每个节点的表征到GPU内存（显存）的方法，但这些方法可能会损失预测精度或者对提高内存的利用率并不明显。于是论文Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Network提出了一种新的图神经网络的训练方法。
在此篇文章中，我们将首先对Cluster-GCN论文中提出的方法（后文中简称为Cluster-GCN方法）做简单概括，接着深入分析超大图上的节点表征学习面临的挑战，最后Cluster-GCN方法做深入分析。
二、Cluster-GCN方法简单概括
为了解决普通训练方法无法训练超大图的问题，Cluster-GCN论文提出：
利用图节点聚类算法将一个图的节点划分为c个簇，每一次选择几个簇的节点和这些节点对应的边构成一个子图，然后对子图做训练。
由于是利用图节点聚类算法将节点划分为多个簇，所以簇内边的数量要比簇间边的数量多得多，所以可以提高表征利用率，并提高图神经网络的训练效率。
每一次随机选择多个簇来组成一个batch，这样不会丢失簇间的边，同时也不会有batch内类别分布偏差过大的问题。
基于小图进行训练，不会消耗很多内存空间，于是我们可以训练更深的神经网络，进而可以达到更高的精度。
三、Cluster-GCN方法
过去的方法和Cluster-GCN方法之间的邻域扩展差异。红色节点是邻域扩展的起始节点。过去的方法需要做指数级的邻域扩展（图左），而Cluster-GCN的方法可以避免巨大范围的邻域扩展（图右）。
Cluster-GCN方法由该问题驱动：我们能否找到一种将节点分成多个batch的方式，对应地将图划分为多个子图，使得表征利用率最大？为了最大限度地提高表征利用率，理想的划分batch的结果是，batch内的边尽可能多，batch之间的边尽可能少。
随机划分与聚类划分。两者都使用一个分区作为一个batch来进行神经网络训练。我们可以看到，在相同的epoches下，使用聚类分区可以达到更高的精度。
尽管简单Cluster-GCN方法可以做到较其他方法更低的计算和内存复杂度，但它仍存在两个潜在问题：
1）图被分割后，一些边被移除，性能可能因此会受到影响。
2）图聚类算法倾向于将相似的节点聚集在一起。因此，单个簇中节点的类别分布可能与原始数据集不同，导致对梯度的估计有偏差。
图6展示了一个类别分布不平衡的例子，该例子使用Reddit数据集，节点聚类由Metis软件包实现。根据各个簇的类别分布来计算熵值。与随机划分相比，采用聚类划分得到的大多数簇熵值都很小，簇熵值小表明簇中节点的标签分布偏向于某一些类别，这意味着不同簇的标签分布有较大的差异，这将影响训练的收敛。
为了解决类别分布不平衡的问题，Cluster-GCN提出了一种随机多簇方法。
四、Cluster-GCN实践
五、作业
上图所示应该是num_parts=1500，数据集被分为1500簇，训练结果如下：
将num_parts=1500改为1000，训练结果如下（效果更好了艾！！）
