论文：Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
聚类GCN：一种对大而深的图卷积网络训练的高效算法

作者：Wei-Lin Chiang (National Taiwan University);Xuanqing Liu (University of California, Los Angeles);Si Si (Google);Yang Li (Google);Samy Bengio (Google);Cho-Jui Hsieh (University of California, Los Angeles);
这是一篇2019年8月4日发表在KDD 2019上的文章。
论文链接：https://arxiv.org/pdf/1905.07953.pdf
github链接：https://github.com/benedekrozemberczki/ClusterGCN （ClusterGCN，A PyTorch implementation）

Abstract

图卷积网络（GCN）已经成功地应用于许多基于图形的应用，然而，大规模的GCN的训练仍然具有挑战性。目前基于SGD的算法要么面临着随GCN层数呈指数增长的高计算成本，要么面临着保存整个图形和每个节点的embedding到内存的巨大空间需求。本文提出了一种新的基于图聚类结构且适合于基于SGD训练的GCN算法——Cluster-GCN。

Cluster-GCN的工作原理如下：在每个步骤中，它对一个与通过用图聚类算法来区分的密集子图相关联的一组节点进行采样，并限制该子图中的邻居搜索。这种简单且有效的策略可以显著提高内存和计算效率，同时能够达到与以前算法相当的测试精度。

为了测试算法的可扩展性，作者创建了一个新的Amazon2M数据集，它有200万个节点和6100万个边，比以前最大的公开可用数据集（Reddit）大5倍多。在该数据上训练三层GCN，Cluster-GCN比以前最先进的VR-GCN（1523秒vs 1961秒）更快，并且使用的内存更少（2.2GB vs 11.2GB）。此外，在该数据上训练4层GCN，Cluster-GCN可以在36分钟内完成，而所有现有的GCN训练算法由于内存不足而无法训练。此外，Cluster-GCN允许在短时间和内存开销的情况下训练更深入的GCN，从而提高了使用5层Cluster-GCN的预测精度，作者在PPI数据集上实现了最先进的test F1 score 99.36，而之前的最佳结果在[16]（2018. GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs. In UAI）上的是98.71。

1. Introduction

图卷积网络（GCN）[9]在处理许多基于图的应用中日益流行，包括半监督节点分类[9]、链路预测[17]和推荐系统[15]。对于一个图，GCN采用图卷积运算逐层地获取节点的embedding：在每一层，要获取一个节点的embedding，需要通过采集相邻节点的embedding，然后进行一层或几层线性变换和非线性激活。最后一层embedding将用于一些最终任务。例如，在节点分类问题中，最后一层embedding被传递给分类器来预测节点标签，从而可以对GCN的参数进行端到端的训练。

由于GCN中的图卷积运算（operator）需要利用图中节点之间的交互来传播embeddings，这使得训练变得相当具有挑战性。不像其他神经网络，训练损失可以在每个样本上完美地分解为单独的项（decomposed into individual terms），GCN中的损失项(例如单个节点上的分类损失)依赖于大量的其他节点，尤其是当GCN变深时。由于节点依赖性，GCN的训练非常慢，需要大量的内存——反向传播需要将计算图上的所有embeddings存储在GPU内存中。

Previous GCN Training Algorithms

为了证明开发可扩展的GCN训练算法的必要性，文中首先讨论了现有方法的优缺点，包括

• 内存需求
• 每个epoch的时间
• 每个epoch收敛速度(loss reduction，损失减少速度）

这三个因素是评估训练算法的关键。注意，内存需求直接限制了算法的可扩展性，后两个因素结合在一起将决定训练速度。在接下来的讨论中，用$N$为图中的节点数，$F$为embedding的维数，$L$为分析经典GCN训练算法的层数。

• GCN的第一篇论文[9](GCN开山之作：2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR)提出了全批次梯度下降（Full-batch gradient descent）。要计算整个梯度，它需要存储所有中间embeddings,，导致O(NFL)内存需求，这是不可扩展的。此外，虽然每个epoch的时间是有效的，但梯度下降的收敛速度较慢，因为每个epoch只更新一次参数。
  [memory: bad; time per epoch: good; convergence: bad]

• 在[5]（SAGE：Inductive Representation Learning on Large Graphs）中提出了Mini-batch SGD。由于每次更新只基于一个mini-batch的梯度，它可以减少内存需求，并在每个epoch执行多次更新，从而加快了收敛速度。然而，由于邻居扩展问题，mini-batch SGD在计算L层单个节点的损失时引入了大量的计算开销，它要求节点的邻居节点在L-1层的embeddings，这又要求邻居节点在L-2层的embeddings，和在下游层的递归embeddings。这导致时间复杂度指数达到GCN深度。图SAGE[5]（Inductive Representation Learning on Large Graphs）提出通过在层的反向传播过程中使用固定大小的邻居样本和FastGCN[1]提出的重要抽样，但这些方法的开销仍然很大，并且在GCN深入时会变得更糟。
  [memory: good; time per epoch: bad; convergence: good]

• VR-GCN[2]提出采用variance减少技术来减小邻域采样节点的大小。尽管成功地减小了采样大小(在文中的实验中，VR-GCN每个节点只有2个样本工作得很好)，但它需要将所有节点的所有中间的embeddings存储在内存中，从而导致$O(NFL)$内存需求。如果图形中的节点数量增加到数百万个，那么对于VR-GCN的内存需求可能太高，无法适应GPU。
  [memory: bad; time per epoch: good; convergence: good]

---

本文利用图的聚类结构，提出了一种新的GCN训练算法。文中指出，一个mini-batch算法的效率可以用“embedding utilization”（嵌入利用率）的概念来描述，它与一个batch或within-batch links的节点之间的连接数量成正比。这一发现促使作者使用图聚类算法来设计batches，这种图聚类算法的目的是构造节点的分区，使同一分区中的节点之间的图连接比不同分区中的节点之间的图连接更多。

基于图聚类思想，作者提出了一种基于高效图聚类算法(如METIS[8])（A fast and high quality multilevel scheme for partitioning irregular graphs）的batches的设计算法Cluster-GCN。作者进一步提出了一个 随机多聚类框架（stochastic multi-clustering framework） 来提高Cluster-GCN的收敛性。这种策略带来了巨大的内存和计算优势。

• 在内存方面，只需要将节点的embeddings存储在当前batch中，即O(bFL)，batch大小为b。这明显优于VR-GCN和full gradient decent，略优于其他基于SGD的方法。
• 在计算复杂度方面，这种基于梯度下降的算法每个epoch时间开销与邻居搜索方法差不多，但比邻居搜索方法快得多。
• 在收敛速度方面，这种算法与其他基于SGD的方法是有竞争力的。
• 由于只计算矩阵乘法而不需要进行邻居采样，所以这种算法是易于实现的。
• 最后，对于算法Cluster-GCN：[memory: good; time per epoch: good; convergence: good]

作者对多个大型图数据集进行了综合实验，做出了如下贡献:

• Cluster-GCN在大型图上实现了最好的内存使用，特别是在深度GCN上。例如，在Amazon2M上的3层GCN模型中，Cluster-GCN使用的内存比VR-GCN少5倍。Amazon2M是一个新的图数据集，是由作者构建的，用于演示GCN算法的可扩展性。该数据集包含一个amazon产品共同购买图，包含超过200万个节点和6100万条边。
• 对于浅层网络(如2层)，Cluster-GCN可以达到与VR-GCN类似的训练速度，但当网络进一步深入时(如4层)，它可以比VR-GCN更快，因为Cluster-GCN的复杂度与层数L成线性关系，而VR-GCN的复杂度与L呈指数关系。
• Cluster-GCN能够训练一个非常深的且具有很大规模的embeddings的网络。虽然之前的一些工作表明，深度GCN并没有提供更好的性能，但是作者发现，通过适当的优化，深度GCN可以帮助提高精度。例如，在5层GCN中，文中实验表明，获得了一个新的PPI数据集基准精度99.36，而[16]（2018. GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs）的最高基准精度为98.71。

2. Background

图卷积网络（GCNs）

最近的一些研究试图将卷积运算应用于图形数据。在[9]（2017. Semi-supervised classification with graph convolutional networks ） 中引入了图卷积网络 （GCN），并在多个节点分类任务中实现了最新的性能。作者定义并使用了一种类似卷积的运算，称为谱图卷积。这使得CNN可以直接在图形上操作。基本上，GCN中的每一层通过考虑相邻节点的特征来更新图中每个节点的特征向量的表示。具体来说，GCN的逐层正向传播操作可以表示为

$$X^{(l+1)}=f(X^l,A)=\sigma ({\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}{X}^{(l)}{W}^{(l)})$$

• $X$是所有节点的特征向量构成的特征矩阵(每一行表示一个节点的特征)
• 其中，$X^l$和$X^{(l+1)}$分别是$l$层的输入和输出矩阵，$X^l$也是第$l$层对于所有节点的embedding。对于这两个矩阵，行数相同，对应于图中的节点数；而列数可能不同，这取决于输入和输出特征空间的尺寸。
• $A$是图的邻接矩阵
• $\tilde{A}=A+I_N$是带有自环的无向图的邻接矩阵。
• $I_N$ 是单位矩阵。
• ${\tilde{D}}_{ii}={\sum }_j{\tilde{A}}_{ij}$是带有自环的无向图的度矩阵，是一个对角矩阵。
• $W^{(l)}$ 是一个可训练权重矩阵或参数矩阵。
• σ(⋅) 激活函数，例如Relu。

为了简化计算，令每一层节点的特征数量都是F。

上式写为：

$$Z^{(l+1)}=A^{\prime }{X}^{(l)}{W}^{(l)},X^{(l+1)}=\sigma (Z^{(l+1)})(1)$$

半监督节点分类是GCN的一种常见的应用。在将GCN用于此应用时，目标是通过最小化损失函数来学习（1）中的权重矩阵：
$$\mathcal{L}=\frac{1}{|{\mathcal{Y}}_{\mathcal{L}}|{\sum }_{i\in {\mathcal{Y}}_{\mathcal{L}}}}loss(y_i,z_i^L)(2)$$

• ${\mathcal{Y}}_{\mathcal{L}}$包含了所有已有标签的节点的标签
• $z_i^L$是ground-truth标签为$y_i$的$Z^L$的第$i$行,表示节点$i$的最终层预测
• 在实际应用中，通常在多类别或者多标签的节点分类问题中使用用交叉熵损失

3. Proposed Algorithm

作者首先讨论了现有训练方法在激励算法方面的瓶颈问题。

在GCN的原始论文[9]（2017. Semi-supervised classification with graph convolutional networks ） 中，GCN的训练使用的是全批量梯度下降（full gradient descent），但是它的计算和内存成本很高。

• 在内存方面，通过反向传播来计算full gradient需要存储所有的embedding矩阵${Z^{(l)}}_{l=1}^L$，这需要O(NFL)的内存空间（F是特征数量，N是结点数量，L是网络层数）。
• 在收敛速度方面，由于在每个epoch模型才更新一次，所以需要很多个epoch才会使模型达到收敛。

研究表明，在最近的一些工作中，使用mini-batch SGD可以提高GCN的训练速度和内存需求[1,2,5]。其中的SGD不需要计算整个梯度(full gradient)，只需要计算每次更新的mini-batch的梯度。
在本文中,使用大小为$b=|\mathcal{B}|$的$\mathcal{B}\in [N]$表示一个batch的节点索引（b is the batch size）。每个SGD步骤将计算梯度估计用下面的公式去更新：

$$\frac{1}{|\mathcal{B}|}\sum _{i\in \mathcal{B}}\nabla loss(y_i,z_i^L)(3)$$
尽管在每个epoch收敛得更快，但SGD在GCN训练上引入了另一个计算开销(如下文所述)，这使得SGD的每个epoch时间内比全梯度下降（full gradient descent）要慢得多。

Why does vanilla mini-batch SGD have slow per-epoch time?

考虑计算一个节点$i$相关的梯度：$\nabla loss(y_i,z_i^L)$。显然，这需要节点$i$的embedding，而节点$i$的embedding的计算依赖于前面的层里的它的邻居的embeddings。为了提取前面的层中它的邻居节点的embeddings，还需要进一步聚合每个邻居节点的邻居节点的embeddings。假设一个GCN网络有$L$层，每个节点的平均度数为$d$，为了获得节点$i$相关的梯度，需要对图中的一个节点聚合$O(d^L)$个节点的特征。也就是说，需要获取图中节点的hop-k (k = 1，···，L)邻居的信息来执行一次更新。由于与$W^{(l)}$相乘，计算每次embedding需要$O(F^2)$的时间，因此平均计算与一个节点相关的梯度需要$O(d^L{F}^2)$的时间。

Embedding utilization can reflect computational efficiency

嵌入利用率（Embedding utilization）可以反映计算效率

如果一个batch有多个节点，那么时间复杂度就不那么直观（less
straightforward），因为不同的节点可能有重叠的hop-k邻居，并且embedding计算的数量可以小于最坏情况$O(b{d}^L)$。为了反映mini-batch SGD的计算效率,作者定义了“Embedding utilization”的概念来表达计算效率。

如果节点$i$在第$l$层的embedding $z_i^{(l)}$ 在计算第$l+1$层的
embeddings时被重用了$u$次，那么就说 $z_i^{(l)}$ 的embedding utilization是$u$。

对于随机抽样的mini-batch SGD，由于图通常比较大且稀疏，u非常小。 假设u是一个很小的常数(hop-k邻居之间几乎没有重叠)，那么mini-batch SGD需要计算每个batch的$O(b{d}^L)$个embeddings，这将导致每个更新需要$O(b{d}^L{F}^2)$的时间和每个epoch需要$O(N{d}^L{F}^2)$的时间。

图1的左边图说明了邻居扩展问题。相反，全批量梯度下降（full-batch gradient descent）具有最大的embedding utilization ——每个embedding将在上层重复使用$d$(平均度数)次。因此，原始的全批量梯度下降[9]每个epoch只需要计算 $O(NL)$ 个embedding，这意味着平均只需要 $O(L)$ 个embedding计算就可以获得一个节点的梯度。

为了使mini-batch SGD工作，以前的方法试图限制邻域扩展的数量，但是这并没有提高embedding utilization（利用率）。GraphSAGE[5]均匀地采样一个固定大小的邻居集，而不是使用一个完整的邻域集。下面用r表示样本容量。这导致对每个损失项需要进行$O(r^L)$的embedding计算，但也使梯度估计不那么准确。FastGCN[1]提出了一种改进梯度估计的重要采样策略。VR-GCN[2]提出了一种策略来存储所有N个节点和L层在先前计算的embeddings，并对未采样的邻居重用它们。尽管存储所有的$NL$的embeddings使用的内存很高，但作者发现他们的策略非常有用，而且在实践中，即使是很小的r(例如，2)也可以达到一个良好的收敛。

文中在表1中总结了时间和空间的复杂性。显然，所有基于SGD的算法的复杂度都和层数呈指数级关系。对于VR-GCN，即使r很小，也会产生超出GPU内存容量的巨大空间复杂度。在接下来的文章中，作者介绍了他们提出的的Cluster-GCN算法，它实现了两全其美的效果：即每个epoch和full gradient descent具有相同的时间复杂度， 与vanilla SGD（朴素SGD，普通SGD）具有相同的空间复杂度。

3.1 Vanilla Cluster-GCN

文中的Cluster-GCN技术是由以下问题驱动的：在mini-batch SGD更新中，我们可以设计一个batch和相应的计算子图来最大限度地提高embedding utilization吗？文中通过将embedding utilization的概念连接到一个聚类目标来回答这一问题。

考虑这样一种情况,在每个batch中计算一组来自于第1层到第L层的节点$\mathcal{B}$的embeddings。因为相同的子图$A_{\mathcal{B},\mathcal{B}}$(links within $\mathcal{B}$)是用于每一层的计算,可知,embedding utilization是在这个batch$\Vert A_{\mathcal{B},\mathcal{B}}{\Vert }_0$中边的数量。因此，为了最大化embedding utilization，应该设计一个batch $\mathcal{B}$来最大化batch内的边，从而将SGD更新的效率与图聚类算法联系起来。

现在，正式引入Cluster-GCN。对于一个图G，可以把它的节点分成c个组：$V=[V_1,...,V_c]$。因此，就可以得到c个子图：

G ˉ = [ G 1 , . . . , G c ] = [ { V 1 , E 1 } , . . . , { V c , E c } ] \bar G=[G_1,...,G_c]=[\{V_1,E_1 \},...,\{V_c,E_c \}] Gˉ=[G1​,...,Gc​]=[{V1​,E1​},...,{Vc​,Ec​}]

• 每个$E_t$只包含在$V_t$中的节点之间的边

对节点进行重组后，邻接矩阵被划分为$c^2$个子矩阵：

$$A=\bar{A}+\Delta =\left[\begin{array}{ccc}{A}_{11}& \cdots & A_{1c}\\ ⋮& \ddots & ⋮\\ A_{c1}& \cdots & A_{cc}\end{array}\right](4)$$
其中

$$\bar{A}=\left[\begin{array}{ccc}{A}_{11}& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & A_{cc}\end{array}\right],\Delta =\left[\begin{array}{ccc}0& \cdots & A_{1c}\\ ⋮& \ddots & ⋮\\ A_{c1}& \cdots & 0\end{array}\right](5)$$

• 对角块$A_{tt}$是一个包含的边在子图$G_t$内的$|V_t|\times |V_t|$维的邻接矩阵
• $\bar{A}$是图$\bar{G}$的邻接矩阵
• $A_{st}$包含了两个部分$V_s$和$V_t$之间的边
• $\Delta$是由$A$的所有非对角块组成的矩阵

类似地，也可以将特征矩阵$X$和训练标签$Y$根据分区$[V_1,...,V_c]$分组为$[X_1,...,X_c]$和$[Y_1,...,Y_c]$。其中，$X_t$和$Y_t$分别由$V_t$中节点的特征和标签组成。

块对角近似的好处是GCN的目标函数可以分解成不同的batches (clusters)。设${\bar{A}}^{\prime }$表示$\bar{A}$的归一化版本，则最终embedding矩阵由$barA$的块对角形式变成（${\bar{A}}_{tt}^{\prime }$是${\bar{A}}^{\prime }$的块对角）：

$$\begin{array}{rl}{Z}^{(l)}& ={\bar{A}}^{\prime }\sigma ({\bar{A}}^{\prime }\sigma (\cdots {\bar{A}}^{\prime }\sigma ({\bar{A}}^{\prime }X{W}^{(0)})W^{(1)})\cdots )W^{(L-1)}\\ & =\left[\begin{array}{c}{\bar{A}}_{11}^{\prime }\sigma ({\bar{A}}_{11}^{\prime }\sigma (\cdots {\bar{A}}_{11}^{\prime }\sigma ({\bar{A}}^{\prime }X{W}^{(0)})W^{(1)})\cdots )W^{(L-1)}\\ ⋮\\ {\bar{A}}_{cc}^{\prime }\sigma ({\bar{A}}_{cc}^{\prime }\sigma (\cdots {\bar{A}}_{cc}^{\prime }\sigma ({\bar{A}}^{\prime }X{W}^{(0)})W^{(1)})\cdots )W^{(L-1)}\end{array}\right]\end{array}(6)$$

损失函数也被分解成：

$$\begin{array}{rl}{\mathcal{L}}_{{\bar{A}}^{\prime }}& =\sum _t\frac{|V_t|}{N}{\mathcal{L}}_{{\bar{A}}_{tt}^{\prime }}\\ {\mathcal{L}}_{{\bar{A}}_{tt}^{\prime }}& =\frac{1}{|V_t|}\sum _{i\in V_t}loss(y_i,z_i^L)\end{array}(7)$$

然后，Cluster-GCN基于公式（6）和（7）中的分解形式。在每一步中，对一个聚类$V_t$进行采样，然后根据${\mathcal{L}}_{{\bar{A}}^{\prime }}$的梯度进行SGD更新，这只需要当前batch上的子图$A_{tt},X_t,Y_t$和模型 { W ( l ) } l L \{W^{(l)}\}_l^L {W(l)}lL​。实现只需要矩阵乘积的正向和反向传播（one block of (6)）。这比以前基于SGD的训练方法中使用的邻域搜索过程更容易实现。

文中使用了图聚类算法来划分图。图聚类的方法，如Metis[8]和Graclus[4]旨在在图中的顶点上构建分区，使簇内连接远大于簇间连接，从而更好地捕获聚类和社区结构。图表的结构。这些正是需要的，因为：

• 1）正如前面提到的，embedding utilization相当于每个batch的簇内的连接。直观地说，每个节点及其相邻节点通常位于同一个簇中，因此经过几次跳跃后，高概率的邻域节点仍然位于同一个簇中。
• 2）由于使用$A$的对角近似$\bar{A}$去取代了$A$且误差和簇间的连接成正比，因此需要去找到一种分区方法最小化簇间连接的数量。

在图1中，全图G和聚类分区图$\bar{G}$来进行邻域展开的示意图。可以看到，cluster-GCN可以避免大量的邻域搜索，并且集中在每个簇中的邻居上。在表2中，展示了两种不同的节点分区策略：随机分区和clustering分区。作者使用随机分割和Metis聚类方法将图分成10个部分。然后使用一个分区作为一个batch来执行SGD更新。可以看到，在相同的时间段内，使用聚类划分可以获得更高的精度。这表明使用图聚类是很重要的，分区不应该随机形成。

Time and space complexity

由于在$V_t$中的节点中连接$V_t$中的节点，所以每个节点不需要在$A_{tt}$外部执行邻居搜索。对每个batch的计算将很纯粹的只是${\bar{A}}_{tt}^{\prime }{X}^{(l)}{W}^{((l)}$的矩阵乘积和一些element-wise的操作，因此，每个batch的时间复杂度为$O(\Vert A_{tt}{\Vert }_{0}F+b{F}^2)$。所以，最终每个epoch的时间复杂度就变为$O(\Vert A_0{\Vert }_{0}F+N{F}^2)$。平均来说，每个batch只需要计算$O(bL)$的embeddings，它是线性的，而不是和L呈指数关系。
在空间复杂度方面，在每一个batch中，只需要加载b个样本并将它们的embeddings存储在每一层上，这样就产生了用于存储embeddings的$O(bLF)$的内存，因此文中的算法也比以前的所有算法更节省内存。此外，文中的算法只需要将子图加载到GPU内存中，而不需要完整的图（尽管图通常不是内存瓶颈）。表1总结了详细的时间和内存复杂度。

3.2 Stochastic Multiple Partitions

尽管朴素 Cluster-GCN实现了良好的计算和内存复杂性，但仍然存在两个潜在问题：

• 图被分割后，一些连接（等式（4）中的$Delta$部分）被删除。因此，性能可能会受到影响。
• 图聚类算法往往将相似的节点聚集在一起，因此聚类的分布可能不同于原始数据集，从而导致在执行SGD更新时对 full gradient的估计有偏差。

在图2中，作者通过使用Reddit数据集由Metis聚类算法形成的聚类来展示标签分布不平衡的例子，实验中根据每个簇的标签分布计算其熵值。与随机分割相比，可以清楚地看到大多数簇的熵较小，这表明簇的标签分布偏向于某些特定的标签，这增加了不同batch的差异（variance），并可能影响SGD的收敛性。

为了解决上述问题，文中提出了一种随机多聚类方法，在簇接之间进行合并，并减少batch间的差异（variance）。作者首先用一个较大的p把图分割成p个簇$V_1,...,V_p$，然后对于SGD的更新重新构建一个batch B，而不是只考虑一个簇。随机地选择q个簇，定义为$t_1,...,t_q$,并把它们的节点$V_{t_1}\cup ...\cup V_{t_q}$包含到这个batch B中。此外，在选择的簇之间的连接

$$A_{ij}|i,j\in t_1,...,t_q,$$

被添加回去。通过这种方式，在簇之间的连接就会被重新合并。这种簇的组合使batch之间的差异（variance）更小。图3说明了每个epoch随机选中不同的簇组合成为一个batch。作者在Reddit数据集上进行了一个实验，证明了该方法的有效性。在图4中，可以观察到使用多个簇作为一个batch可以提高收敛性。最后的Cluster-GCN算法在算法1中给出。

3.3 Issues of training deeper GCN

以前对更深层的GCN进行训练的尝试[9]（2017. Semi-supervised classification with graph convolutional networks ）似乎表明，添加更多的层并没有帮助。然而，这篇引文中的实验中使用的数据集可能太小，无法做出正确的解释。例如，[9]认为只有几百个训练节点的图形存在过拟合问题。此外，作者观察到，深度GCN模型的优化变得困难，因为它可能会阻碍前几层信息的传递。在[9]中，他们采用类似于残差连接[6]（Resnet提出的论文： Deep Residual
Learning for Image Recognition. CVPR (2016)）的技术，使模型能够将信息从上一层传输到下一层。具体来说，他们修改（1）以将层L的隐藏表示添加到下一层。

$$Z^{(l+1)}=A^{\prime }{X}^{(l)}{W}^{(l)},X^{(l+1)}=\sigma (Z^{(l+1)})+X^{(l)}(8)$$

作者提出了另一个简单的技术来改进深度GCN的训练。在最初的GCN设置中，每个节点从上一层聚合其相邻节点的表示。然而，在深度GCN的设置下，该策略可能不适用，因为它不考虑层数。直观地说，附近的邻居贡献的应该比远处的节点多。因此，作者提出了一种更好地解决这个问题的技术，其思想是放大每个GCN层中使用的邻接矩阵A的对角部分。通过这种方式，在每个GCN层的聚合中对上一层的表示施加更多的权重。例如，将单位矩阵(identity)添加到$\bar{A}$中，如下所示:

$$Z^{(l+1)}=(A^{\prime }+I)X^{(l)}{W}^{(l)},X^{(l+1)}=\sigma (Z^{(l+1)})(9)$$
即
$$X^{(l+1)}=\sigma ((A^{\prime }+I)X^{(l)}{W}^{(l)})(9)$$
虽然（9）似乎是合理的，但无论相邻节点的数量如何，对所有节点使用相同的权重可能是不合适的。此外，当使用更多的层时，数值可能会呈指数增长，这可能会导致数值不稳定。因此，作者提出了（9）的修改版本，以更好地维护邻居信息和数值范围。文中也首先向原始A添加一个单位矩阵(identity)，然后执行标准化(normalization)：

$$\tilde{A}=(D+I{)}^{-1}(A+I)(10)$$
然后考虑

$$X^{(l+1)}=\sigma ((\tilde{A}+\lambda diag(\tilde{A}))X^{(l)}{W}^{(l)})(11)$$
第4.3节给出了采用“对角增强(diagonal enhancement)”技术的实验结果，表明这种新的标准化(normalization)策略有助于构建深度GCN并实现最先进的(SOTA)性能。

4. Experiments

文中评估了所提出的针对四个公共数据集的多标签和多类分类两个任务的GCN训练方法，数据集统计如表3所示。Reddit数据集是迄今为止为GCN所看到的最大的公共数据集，Amazon2M数据集是由作者自己收集的，比Reddit大得多（详见第4.2节）。

在比较中包括以下最先进的GCN训练算法：

• Cluster-GCN（文中提出的算法）：提出的快速GCN训练方法。
• VRGCN[2]（2018. Stochastic Training of Graph Convolutional Networks with Variance Reduction. In ICML.）:它维护图中所有节点的历史embeddings，而且只扩展到少数邻居以加速训练。采样邻居的数量在[2]中建议的是2（作者还在VRGCN包中尝试了默认的sample size 20，但是它的性能比sample size = 2差得多）。
• GraphSAGE[5]（2017. Inductive Representation Learning on Large Graphs. In NIPS.）:它对每个节点的邻居进行固定数量的采样。此文作者在GraphSAGE中为每个层使用采样大小的默认设置(s1 = 25, s2 = 10)。

作者使用PyTorch[13]实现了文中提出的方法。对于其他方法，使用所有原始论文github页面中的代码。由于[9]（2017. Semi-supervised classification with graph convolutional networks ）难以扩展到较大的图形，所以没有参与比较。同样，从[2]中可以看出，VRGCN比FastGCN快，所以不与FastGCN进行比较。文中使用的方法一些配置为：使用Adam优化器，学习率为0.01，dropout率为20%，体重衰减为零。[5]（2017. Inductive Representation Learning on Large Graphs. In NIPS.）提出了平均聚合器，使用平均聚合器，所有方法的隐藏单元数相同。注意，这里不考虑(11)之类的技术。在每个实验中，作者对所有方法考虑了相同的GCN体系结构。对于VRGCN和GraphSAGE，按照原始论文提供的设置，将batch sizes设置为512。对于Cluster-GCN，表4列出了每个数据集的分区数量和每个batch的簇的数量。注意，聚类被视为预处理步骤，在训练中没有考虑聚类的运行时间。在第6节中，展示了图形聚类只占用一小部分预处理时间。所有的实验都是在一台拥有NVIDIA Tesla V100 GPU (16gb内存)、20核Intel Xeon CPU (2.20 GHz)和192gb RAM的机器上进行的。

4.1 Training Performance for median size datasets

Training Time vs Accuracy

首先，在训练速度方面，作者将所提出的方法与其他方法进行了比较。在图6中，x轴显示了以秒为单位的训练时间，y轴显示了验证集的准确性(F1分数)。作者用2、3、4层GCN绘制了三个数据集的训练时间与准确度的关系图。由于GraphSAGE比VRGCN比文中的方法慢，GraphSAGE的曲线只出现在PPI和Reddit数据集中。可以看到，对于不同层数的GCNs，文中的方法对于PPI和Reddit数据集都是最快的。

对于Amazon数据，由于节点的特征不可用，所以使用一个单位矩阵作为特征矩阵X。在此设置下，参数矩阵$W^{(0)}$的形状为 334863x128。因此，计算主要是由稀疏矩阵运算带来的，如$A{W}^{(0)}$。对于三层的情况，文中的方法仍然比VRGCN快，但是对于两层和四层的情况就慢了。原因可能是不同框架的稀疏矩阵运算速度不同。VRGCN是在TensorFlow中实现的，而Cluster-GCN是在PyTorch中实现的，它的稀疏张量支持仍然处于非常早期的阶段。在表6中，展示了TensorFlow和PyTorch对Amazon数据进行前馈/反向传播操作的时间，并使用一个简单的两层网络对这两个框架进行基准测试。可以清楚地看到TensorFlow比PyTorch快。当隐藏单元的数量增加时，这种差异更为显著。这也许可以解释为什么Cluster-GCN在Amazon dataset中有更长的训练时间。

Memory usage comparison

对于大规模的GCNs的训练，除了训练时间外，训练所需的内存使用往往更为重要，直接限制了可扩展性。内存的使用包括许多epochs训练GCN所需的内存。正如在第3节中讨论的，为了加速训练，VRGCN需要在训练期间保存历史embeddings，因此它需要比Cluster-GCN更多的内存来进行训练。由于指数邻域增长的问题，Graph-SAGE对内存的要求也高于Cluster-GCN。在表5中，比较了不同层的GCN与VRGCN的内存使用情况。当增加层数时，Cluster-GCN的内存使用量并没有增加很多，原因是增加一层时引入的额外变量是权矩阵$W^{(L)}$，与子图和节点特征相比，权重矩阵$W^{(L)}$相对较小。而VRGCN需要保存每一层的历史embeddings，而embeddings通常是密集的，很快就会控制内存的使用。从表5可以看出，Cluster-GCN的内存效率比VRGCN高得多。例如，在Reddit数据上，要训练一个4层的隐藏维度为512的GCN,VRGCN需要2064MB内存，而Cluster-GCN只需要308MB内存。

4.2 Experimental results on Amazon2M

A new GCN dataset: Amazon2M

到目前为止，用于测试GCN的最大公共数据是Reddit dataset，其统计数据如表3所示，其中包含大约200K个节点。如图6所示，对该数据的GCN训练可以在几百秒内完成。为了测试GCN训练算法的可扩展性，作者基于Amazon co-purchase network构建了一个更大的图，包含超过200万个节点和6100万条边[11,12]。原始的共同购买（ co-purchase）数据来自Amazon-3M。在图中，每个节点都是一个产品，图中边的连接表示是否同时购买两个产品。每个节点特征都是通过从产品描述中的bag-of-word式的特征，然后进行主成分分析[7]生成的，将维数降为100。此外，我们使用top-level categories作为该产品/节点的标签(最常见的类别见表7)。数据集的详细统计数据如表3所示。

在表8中，作者比较了不同层次GCNs的VRGCN在训练时间、内存使用和测试准确度(F1分数)方面的差异。从表中可以看出

• 训练两层GCN的VRGCN比Cluster-GCN快,但是却慢于增加一层网络但实现相似准确率的Cluster-GCN
• 在内存使用方面,VRGCN比Cluster-GCN使用更多的内存(对于三层的情况5倍多)。当训练4层GCN的时候VRGCN将被耗尽，然而Cluster-GCN当增加层数的时候并不需要增加太多的内存，并且Cluster-GCN对于这个数据集训练4层的GCN将实现最高的准确率。

4.3 Training Deeper GCN

在本节中，作者考虑了具有更多层的GCNs。首先在表9中显示了Cluster-GCN和VRGCN的时间比较。PPI数据集用于基准测试，实验中对这两种方法运行了200个epoch。结果发现VRGCN的运行时间由于其代价很大的邻域查找而呈指数增长，而Cluster-GCN的运行时间只呈线性增长。

接下来作者研究了使用更深层次的GCNs是否能获得更好的精度。在4.3节，文中讨论了修改邻接矩阵A的不同策略，以方便对深度GCNs的训练。文中将对角增强技术应用于深度GCNs，并对PPI数据集进行了实验研究。结果如表11所示。对于2-5层的情况，所有方法的精度都随着层数的增加而提高，这表明更深层的GCNs可能是有用的。然而，当使用7或8个GCN层时，前三种方法无法在200个epoch内收敛，导致精度显著下降。一个可能的原因是对更深层GCNs的优化变得更加困难。文中在图5中显示了一个8层GCN的详尽的收敛。采用所提出的对角增强技术(11)，可以显著提高收敛性，达到相似的精度。

State-of-the-art results by training deeper GCNs

通过对Cluster-GCN的设计和提出的归一化方法，现在可以对GCNs进行更深入的训练，从而获得更高的精度(F1分)。文中将测试精度与表10中其他现有方法进行了比较。对于PPI数据集，Cluster-GCN可以通过训练一个包含2048个隐藏单元的5层GCN来达到最先进的效果。对于Reddit数据集，使用了一个包含128个隐藏单元的4层GCN。

5.Conclusion

此文提出了一种新的训练算法Cluster-GCN。实验结果表明，该方法可以在大型图上训练非常深的GCN，例如在一个超过200万个节点的图上，使用2G左右的内存训练时间不到1小时，精度达到90.41 (F1 score)。使用该方法，能够成功地训练更深入的GCNs，它可以在PPI数据集和Reddit数据集上获得最先进的测试F1 score。

ppt下载

Large-Scale Learnable Graph Convolutional Networks（LGCN）ppt