读 Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
论文信息
- 作者：Chiang, Wei-Lin，Liu, Xuanqing，Si, Si...
- 出版信息: KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data MiningJuly 2019 Pages 257–266https://doi.org/10.1145/3292500.3330925
- DOI: 10.1145/3292500.3330925
- 论文下载地址：https://dl.acm.org/doi/abs/10.1145/3292500.3330925
- GitHub：https://github.com/benedekrozemberczki/ClusterGCN
目录
背景
- 图卷积网络(GCN)已经成功地应用于许多基于图的应用中;然而，训练一个大规模的GCN仍然具有挑战性。当前的基于随机梯度下降的算法要么计算成本高（随着GCN层数的增加呈指数增长），要么需要很大的空间来保存整个图并将每个节点嵌入到内存中。
- 小批量算法的效率可以用“嵌入利用率”的概念来描述，它与一个批量或批内的节点之间的链接数量成正比。
- 图聚类算法旨在构造节点的分区，从而使同一分区中的节点之间的图链接比不同分区中的节点之间的图链接更多。但对图进行分区后，删除了一些链接。因此，性能可能会受到影响。并且图形聚类算法倾向于将相似的节点聚在一起。因此，集群的分布可能与原始数据集不同，从而导致在执行SGD更新时对整个梯度的有偏估计。
创新点
- 训练图卷积网络的过程中，使用图聚类算法设计batches。
- 进一步提出了随机多聚类框架来提高Cluster-GCN的收敛性。
动机
- 在小批量处理SGD更新中，能否设计一个批处理和相应的计算子图来最大化嵌入利用率？作者通过将嵌入利用率的概念与簇目标联系起来回答了这个问题。
- 为了重新组合簇间的链接，减少不同批次间的方差，减少对SGD收敛的影响。
Cluster-GCN的工作原理
在每个步骤中，它对与图聚类算法识别的稠密子图相关联的节点块进行采样，并限制在该子图中进行邻域搜索。在构建批量进行SGD更新时，没有只考虑一个簇，而是随机选择q个簇。
图
图1 展示的是完整的图（左）和聚类分区的图（右）。可以看到，Cluster-GCN可以避免繁重的邻居搜索，并将重点放在每一个同簇中的邻居上。
表2展示了两种不同的节点分区策略：随机分区和聚类分区。大多数聚类分区批次的标签熵较低，表明每个批次内的标签分布是倾斜的；相比之下，同一批中随机划分有更大的标签熵。可以看出，在相同的epoch数量下，使用聚类划分可以达到更高的精度，这表明使用图聚类是很重要的，分区不应该是随机形成的。
图3是随机多分区方案在Reddit上的实验过程，相同的色块在同一批次。在每个epoch中，随机采样q个簇(本例中使用q = 2)和簇间的链接，以形成一个新的批处理。说明了对于每个epoch，选择不同的簇组合作为一个批处理。以证明该方法的有效性。
图4是实验中用一个簇和多个簇作为batch的比较。前者使用300个分区。后者使用1500个，随机选择5个形成一批。epoch (x轴)和F1得分(y轴)。可以看到使用多个簇作为一个批处理可以提高收敛性。
优势
- 在规模方面，可以在大规模图数据上训练非常深的GCN。
- 在内存方面，只需存储当前批处理中的节点嵌入，即批处理的大小。
- 在计算复杂度方面，算法以梯度下降的方式达到了与邻域搜索方法相同的时间开销，并且比邻域搜索方法快得多。
- 在收敛速度方面，与其他基于sgd的方法相比是有竞争力的。
- 最后，算法实现简单，因为我们只计算矩阵乘法，不需要邻域采样。