(论文翻译)Cluster-GCN：一种有效的算法，用于训练深度和大规模图卷积网络
论文地址：https://arxiv.org/pdf/1905.07953.pdf
图卷积网络（GCN）已成功应用在许多基于图的应用程序；但是，大规模的训练GCN仍然具有挑战性。当前基于SGD的算法要么以成倍增长的高计算成本来处理具有多层GCN，或者需要很大的空间才能将整个图和每个节点的嵌入存储在内存中。在本文提出了一种新的GCN算法Cluster-GCN，通过利用图聚类这种结构来进行优化速度和内存。 Cluster-GCN的工作方式如下：在每个步骤中，它都会通过图聚类算法，采样与识别出密集子图相关联的节点块，并限制在此子图中搜索邻域。这种简单而有效的策略导致显著提高内存和计算效率的同时，又能够达到与以前相当的测试精度算法。为了测试算法的可扩展性，我们创建了一个具有200万个节点和6100万个边缘的新Amazon2M数据，比以前的最大公开大5倍以上可用数据集（Reddit）。为了在此数据上训练3层GCN，Cluster-GCN比以前的最新VR-GCN快（1523秒对1961秒），并使用更少的内存（2.2GBvs 11.2GB）。此外，为了在此数据上训练4层GCN，所有现有由于内存不足，GCN训练算法无法训练的问题，我们算法可以在大约36分钟内完成。此外，Cluster-GCN使我们可以进行更深入的训练GCN没有太多时间和内存开销，这导致提高了预测准确性-使用5层Cluster-GCN，我们在PPI数据集上获得最先进的测试F1分数99.36，而之前的最佳成绩是[16]，达到98.71。我们的代码是公开的可在 https://github.com/google-research/google-research/tree/master/cluster_gcn。
1引言
在解决许多基于图的应用程序中，图卷积网络（GCN）[9]越来越多，也越来越流行，包括半监督节点分类[9]，连接预测[17]和推荐系统[15]。 给定一个图，GCN使用图卷积操作逐层获取节点嵌入-在在每一层中，节点的嵌入是通过收集邻居的嵌入，然后是一层或几层线性变换和非线性**。 最后一层然后将嵌入用于某些最终任务。 例如，在节点中分类问题，将最后一层嵌入传递给分类器预测节点标签，从而预测GCN的参数可以以端到端的方式进行培训。
由于GCN中的图卷积运算符需要传播使用图中节点之间的交互来进行嵌入，这使得训练模型颇具挑战性。 与其他神经网络不同，训练损失可以完美地分解到独立的term上，GCN中的term损失（例如，一个分类节点上的loss）取决于大量其他节点，特别是当GCN深入时。 由于节点依赖性，GCN的训练非常缓慢，并且需要大量内存-反向传播需要将所有节点的嵌入存储在计算中GPU内存中
N是图中节点的数量，F是embedding维度，L是gcn的层数
(1)在第一篇GCN论文中提出的完整batch的梯度下降[9]。 为了计算整个梯度，它需要在内存中存储所有中间嵌入，从而导致O（N F L）内存需求，这是不可扩展的。 此外，尽管每个epoch都进行梯度下降这种方法是有效的，但是梯度下降的收敛速度是缓慢的，因为每个epoch，参数仅更新一次[memory: bad; time per epoch: good; 收敛速度: bad]
(2)在[5]中提出了小批量SGD。由于每次更新仅基于小批量梯度，它可以减少内存需求，并在每个时期进行多次更新，从而导致更快的收敛。但是，小批量SGD引入了由于邻域而产生的大量计算开销扩展问题----为了计算单个节点在L层的损失，它依赖在L-1层的邻居，这再次需要在L-2层的邻居，然后递归下去，这个导致时间复杂度与GCN深度成指数关系。GraphSAGE [5]建议在反向传播期间，使用固定大小的邻域样本。FastGCN进行[1]提出了重要性采样的思路，但是这些方法的开销仍然很大，当GCN深入时会变得更糟。[memory: good; time per epoch: bad; convergence: good]
(3)VR-GCN [2]建议使用方差减少技术以减少邻域采样节点的大小。 尽管成功地减少了采样数量（在我们的实验中VR-GCN每个节点只采样2个样本的效果很好），在内存中也需要存储所有节点的中间嵌入，导致O（N F L）个内存需求。 如果图中的节点数增加到数百万，则内存对VR-GCN的要求可能太高而无法放入GPU。[memory: bad; time per epoch: good; convergence: good.]
在本文中，我们提出了一种新颖的GCN训练算法，也就是利用图聚类结构。我们发现mini-batch算法的效率可以通过“向量利用率”的概念来表征，该概念与一个batch或多个batch里的节点连接数成正比。这一发现激励我们在batches中使用图聚类算法来构造节点的分区，以便在分区内有更多不同分区节点之间的连接，同一分区中的节点之间的图形链接。基于图聚类的思想，我们提出了Cluster-GCN，一种基于高效设计批次的算法图聚类算法（例如METIS [8]）。我们采用这个想法通过提出一个随机的多集群框架来改善Cluster-GCN的融合。我们的战略导致巨大的内存和计算优势。在内存方面，我们只需要存储在当前batch中的节点嵌入向量，是O（b F L），批次大小为b。很明显，这比VR-GCN和全梯度下降要好，并且比其他基于SGD的方法略胜一筹。在计算复杂度方面，该算法和梯度下降相比达到了相同的时间成本，并且比邻域搜索方法要快得多。就收敛速度而言，我们的算法与其他基于SGD的方法相比，更具有竞争力。最后，我们的算法很简单因为我们只计算矩阵乘法而没有计算需要邻居抽样。因此，对于Cluster-GCN，我们有 [memory: good; time per epoch: good; convergence: good].
我们对几个大型综合实验图形化数据集进行了实验，并做出以下贡献：
- Cluster-GCN在大规模图上，实现了最佳内存，尤其是在深层GCN上。 例如，在Amazon2M数据集上，Cluster-GCN使用3层GCN模型中，使用的内存比VRGCN少5倍。 Amazon2M是一个新数据集，是为了演示GCN算法的可扩展性。 这个数据集包含200万个节点和6100万条边。
- Cluster-GCN与适用于较浅的网络（例如2层）的VR-GCN达到了类似的训练速度，但当网络更深入（例如4层）时，其速度比VRGCN快，因为VR-GCN的复杂度与L层数成线性关系复杂度是L的指数
- Cluster-GCN能够训练一个非常深度的网络，该网络具有大尺寸的embedding-size。 尽管以前的几幅作品都显示深入的GCN不能提供更好的性能，我们发现通过适当的优化，更深的GCN可以帮助提高准确性。例如，使用5层GCN，我们可以获得新的基准PPI数据集的准确度为99.36，与[16]的最高报道为98.71相比
2 BACKGROUND
假定我们有一个图G=（V,E,A），N=|V|代表节点的个数，|E|代表边的个数，代表在I j两个节点之间的相似性。临接矩阵A是一个N*N的稀疏矩阵，当值等于1时，代表i j两个节点之间有边相连，0代表没有相连。每一个节点都有F维度的向量，X属于R(N*F)，代表着N个节点的向量。L层的GCN由L个图卷积层组成，其中每一层每个节点的向量都由节点的邻居向量通过mean等方法得到，具体公式是
其中X(L)=R(N*FL)是第L层所有节点的向量，A`是经过归一化后的临接矩阵（并且加了自连接），W(L)是特征变换矩阵，可以由下游任务学习而来。为了简单起见，我们把每一层的F都确定为一个值F。计划函数σ(·) 通常采用逐元素的RELU
半监督节点分类任务在GCN中很常见。当学习GCN模型时候，目标是学习上面1公式中权重矩阵，以最小化下面的loss函数
y(L)是所有有label的节点，zi(L)是z(L)中的第i行，yi是实际label，假定我们是在对i节点进行分类，一般会使用交叉熵损失作为loss
Table1: L是GCN的层数，N是节点的数量，||A||0 是临接矩阵的非0数量，F是节点向量维度。为了简单，我们把所有层的特征F都设为一个值。在基于SGD这种优化办法上，b是batch_size，r是每个节点的邻居采样数。由于在算法中利用了方差减少的track，VR-GCN可以比GraphSage，FastGCN使用的r都小。在内存方面，LF2是为了存储W(L)，其他的track是为了存储向量。为了简便，我们忽略存储graph(GCN)和sub-graphs(其他的办法)，因为这些很成熟，而且也不是主要的瓶颈
3 PROPOSED ALGORITHM
我们首先讨论以前的训练方法的瓶颈，以对照着提出合适的解决算法
在原始的GCN论文中，采用的是全梯度下降策略来训练，但是这种套路在内存和计算速度上都是一个challege。首先在内存方面，反向计算全梯度下降的时候，需要存储所有的向量特征矩阵{Z(L)}，这需要花费O(NFL)这么大的内存，N是节点数量 * F是节点向量，L是层数。在速度方面，因为模型每个epoch只需要更新一次，所以训练的时候需要进行多次更新。
在最近的一些工作中已经证明mini-batch-SGD可以提高训练速度和节省内存。相对于SGD的全梯度计算，mini-batch-SGD仅需要计算每一次更新时候的batch内的梯度。在我们这篇文章中，我们使用B⊆[N]，其中B是N个节点中某个batch的节点，size设为b，计算梯度估算的时候，我们会按照下面的公式进行计算
尽管在每个epoch中计算的更快，mini-batch-SGD将在GCN训练中引入另一种计算开销（如下所述），与全梯度下降相比，每个epoch花费的时间更多。
Why does vanilla mini-batch SGD have slow per-epoch time?为什么mini-batch SGD每一个batch计算起来很慢
我们先考虑计算一个node-i的梯度，明确的说就是计算i的向量，这取决于在上一层中i节点的邻居节点，为了取i节点邻居节点的embedding，我们需要递归的做这件事情、假定GCN有L+1层，每一个节点的邻域数量是d，为了获得节点i的梯度，我们总共需要聚合的节点数量的复杂度是O(d的L次方)。也就是说，我们需要取节点i的1~L层每一层的邻居信息来进行更新i节点的embedding。计算每一次embedding，由于权重W(l)的乘法，所以花费的时间复杂度是O(F的平方)，所以总的时间复杂度是O(d的L次方* F的平方)
Embedding utilization can reflect computational efficiency 嵌入利用率可以反映计算效率
如果一个batch中有超过一个node（总共b个node），因为不同node间在每一层可能有相交的节点，所以时间复杂度不是很高。先考虑最差的情况，一个batch中，有b个节点，节点之间的邻域互相不重合，那么时间复杂度就是O(b* d的L次方)。为了体现mini-batch SGD的计算效率，我们定义一个概念：“embedding utilization”。在算法中，我们把L层i节点的embedding定义为zi(L)，假定i节点在L+1层中计算节点向量时被使用到了u次。在mini-batch SGD中因为是随机采样的一个batch，u就变得非常小，因为图通常是很大很稀疏。假定u是一个小常量（也就意味着在L层邻居中几乎没有复用的邻居节点），所以mini-batch SGD在每个batch中需要计算O(b* d的L次方)这么多次，花费的时间就是O(b* d的L次方*F的平方)，在每个epoch中就需要花费O(N* d的L次方*F的平方)
我们在左侧图1展示了邻域扩展问题。Full-batch梯度下降，每一个embedding都会在上一层中被重复使用d次（d是邻域大小，每一个节点的邻域数量是d，每一个邻域节点都利用1次，加起来就是d次），自然，Full-batch梯度下降中就只需要在每个epoch中计算O(N*L)次，这意味着平均计算O(L)次就能计算出来一个节点的梯度。
为了使mini-batch SGD能够正常工作，以前的方法试图限制邻域扩展的大小。但是这并没有提高embedding利用率。GraphSAGE 会采样固定数量的邻域节点，而不是采用所有的邻域，我们假定采样大小是r，这不仅会导致O (r L ) 次计算embedding，而且会导致梯度计算不太准确。FastGcn提出来根据重要性来对邻域进行采样，来提升计算梯度。VR-GCN [2]提出了一种策略，存储前面计算好的L层中每层N个node的embedding，并将其用于计算未采样的邻居。 尽管用于存储所有N*L个嵌入 内存使用量很高，但我们发现该策略非常有用，也可以导致良好的收敛性。
我们在表1中总结了时间和空间的复杂性。显然，所有基于SGD的算法在层数方面都面临指数复杂性，对于VR-GCN，即使r很小，它们也会带来巨大的空间复杂性， 可能会超出GPU的内存容量。 在下文中，我们介绍了Cluster-GCN算法，该算法实现了两个世界中的佼佼者-在时间复杂度上和full gradient下降一样，内存上和SGD类方法一样
3.1香草簇-GCN
我们的Cluster-GCN技术受到以下问题的激励：在mini-batch-SGD更新中，我们可以设计 batch 和相应的计算子图来最大化嵌入利用率吗？ 我们通过将嵌入利用的概念与聚类目标联系起来, 来回答这一肯定的问题。
我们考虑这样一种情况，计算节点B从第1层到第L层的一系列节点的embedding。因为相同的子图A(B,B)->通过B节点相连，在每一层中都被用来做计算，那么在|| A(B,B)||0这个batch中，embedding利用率就是边数。因此，为了最大化embedding利用率，就是最大化一个batch中的边数，因此我们设计了基于SGD的图聚类算法来综合考虑计算时间和内存。
下面我们普遍的来介绍一下Cluster-GCN，对于图G，我们把所有的node分成c组，V代表所有的node，V = [V1, …, Vc]，其中Vt包含着第t部分的nodes，所以我们就有c个子图其中，et代表这个子图里面的边连接关系，重组节点后，我们就将临接矩阵分成了c^2个子矩阵，就像下面这样
公式4中的每一个对角值Att都是|Vt | × |Vt | 的临接矩阵，都是Gt这个子图里面的所有节点形成的临接矩阵；其中A横杠是图G横杠的临接矩阵，Ast是s子图和t子图的临接关系；∆ 是A的所有非对角块的矩阵关系。很明显，我们可以将特征矩阵X和label矩阵Y根据上面的[V1 ,··· ,V c]分割成[X1 ,··· ,Xc ] and [Y 1,··· ,Yc ], Xt和Yt就是Vt这些节点的特征和label关系。
块对角近似G横杠的好处在于，GCN的目标函数可分解为不同的批次（簇）。A横杠一嫖是 A横杠归一化后的形式。最终的GCN公式就变成了下面这样
由于A横杠的块对角格式（Att横杠一嫖是A横杠一嫖中的一部分），损失函数也可以写成下面这样
Cluster-GCN就按照上面的变形公式，在每一步的时候，我们采样一个簇Vt，然后应用sgd方法来进行更新上面的梯度，这仅仅依赖于当前batch中的子图Att，Xt，Yt, 该实现只需要矩阵乘积的前向和后向传播，比以前的基于SGD的训练方法中使用的邻域搜索过程更容易实现。
我们使用图聚类算法对图进行分区。诸如Metis [8]和Graclus [4]之类的图聚类方法旨在在图的顶点上构建分区，以使聚类内链接比聚类间链接更多，以更好地捕获聚类和图结构之间的关系。这些正是我们需要的，因为：1）如前所述，嵌入利用率等于每个批次的集群内链接数一样大。 直观地讲，每个节点及其邻居通常位于同一群集中，因此经过几番之后，邻居节点很大概率仍位于同一群集中。 2）由于我们用其块对角线近似值A代替A，并且误差与群集间链接∆成正比，因此我们需要找到一个分区以最大程度地减少群集间链接的数量。
在图1中，我们说明了具有全图G和具有聚类分区G graph的图的邻域展开。 我们可以看到cluster-GCN可以避免繁重的邻域搜索，而将注意力集中在每个集群内的邻居上。 在表2中，我们显示了两种不同的节点分区策略：随机分区与群集分区。 我们通过使用随机分区和METIS将图分为10个部分。 然后将一个分区作为批处理执行SGD更新。 我们可以看到，在相同数量的epoch下，使用聚类分区可以获得更高的准确性。 这表明使用图聚类很重要，并且不应随机分区。
时间和空间复杂度：在Vt中的每一个节点，只在Vt这个范围中有连接关系，不需要在Att的范围之外还有什么连接关系。每个batch中的计算公式是：，除了这个计算外还有一些逐元素的计算操作，所以整个batch中的时间复杂度是O(∥Att ∥0F + bFF)。所以在每个epoch中的时间复杂度是O(∥Att ∥0F + NFF)。平均来看，每个batch中需要计算的embedding的数量是O(bL)，是一个和L有关的线性增长的关系。说到空间复杂度，我们需要在每层中加载b个nodes，并把他们的embedding存储下来，这样会导致的空间复杂度是O(bLF)，因此我们的算法比之前的所有算法使用的内存都要小，只需要把子图加载到GPU的memory中 而不是整个图，具体的时间和空间复杂度我们在Table1中计算好了。