随着图神经网络层数增加，计算成本呈指数增加。包存整个图的信息和每个节点的表征消耗了大量内存空间。Cluster-GCN提出了一种新的图神经网络的训练方法。

Cluster-GCN方法概括

• 利用图节点聚类的算法将一个图划分成 c c c个簇，每一次选择几个簇的节点和这些节点对应的边构成一个子图。
• 簇内部边的数量比簇之间的数量要多得多，可以提高表征利用率。
• 每一次随机选择多个簇来组成一个batch，这样不会丢失簇之间的边，也不会有batch内部分布偏差太大。

Cluster-GCN方法详细分析

假设GCN有 L L L层，所有层的表征维度都是 F F F,有 N N N个节点，每个节点的平均维度是 d d d。

• 普通GCN空间复杂度: O ( N F L ) O(NFL) O(NFL)

• 时间复杂度
  由于要与权重矩阵相乘，所以计算任意节点表征的时间开销是 O ( F 2 ) O(F^2) O(F2),平均来说，一个节点的梯度计算的时间复杂度为 O ( d L F 2 ) O(d^LF^2) O(dLF2)。
  节点表征的利用率可以反映出计算的效率。如果节点 i i i在 l l l层的表征 z i ( l ) z_{i}^{(l)} zi(l)​被计算并在 l + 1 l+1 l+1层的表征计算中被重复使用 u u u次，那么我们说 z i ( l ) z_{i}^{(l)} zi(l)​的表征利用率为 u u u。对于随机抽样的mini-batch SGD， u u u非常小，因为图通常是大且稀疏的。假设 u u u是一个小常数（节点间同样距离的邻接节点重叠率小），那么mini-batch SGD的训练方式对每个batch需要计算 O ( b d L ) O\left(b d^{L}\right) O(bdL)的表征，于是每次参数更新需要 O ( b d L F 2 ) O\left(b d^{L} F^{2}\right) O(bdLF2)的时间，每个epoch需要 O ( N d L F 2 ) O\left(N d^{L} F^{2}\right) O(NdLF2)的时间，这被称为邻域扩展问题。相反的是，全梯度下降训练具有最大的表征利用率——每个节点表征将在上一层被重复使用平均节点度次。因此，全梯度下降法在每个epoch中只需要计算 O ( N L ) O(N L) O(NL)的表征，这意味着平均下来只需要 O ( L ) O(L) O(L)的表征计算就可以获得一个节点的梯度。

• Cluster-GCN的方法
  对于一个图 G G G，我们将其节点划分为 c c c个簇： V = [ V 1 , ⋯ V c ] \mathcal{V}=\left[\mathcal{V}{1}, \cdots \mathcal{V}{c}\right] V=[V1,⋯Vc]，其中 V t \mathcal{V}{t} Vt由第 t t t个簇中的节点组成，对应的我们有 c c c个子图。可以据此把邻接矩阵分成块矩阵。此步骤可以通过图聚类算法划分。

• 作业
  num_parts=1500时，准确率可以达到0.95