摘要

图卷积网络（GCN）已成功应用于许多基于图的应用场景；然而，大规模GCN的训练仍然具有挑战性。目前基于随机梯度下降（SGD）的算法要么面临随着GCN层数增加而呈指数增长的高计算成本，要么需要大量的内存空间来存储整个图及每个节点的嵌入。在本文中，我们提出了一种新的GCN算法——Cluster-GCN，该算法通过利用图聚类结构，适用于基于SGD的训练。Cluster-GCN的工作原理如下：每一步中，它会采样一个与图聚类算法识别出的密集子图相关联的节点块，并将邻域搜索限制在这个子图内。这一简单而有效的策略显著提高了内存和计算效率，同时能够实现与先前算法相当的测试精度。为了测试我们算法的可扩展性，我们创建了一个包含200万个节点和6100万条边的新Amazon2M数据集，其规模比之前最大的公开数据集（Reddit）大5倍以上。对于在这个数据集上训练3层GCN而言，Cluster-GCN比之前的最先进算法VR-GCN更快（1523秒对比1961秒），并且使用的内存要少得多（2.2GB对比11.2GB）。此外，在这个数据集上训练4层GCN时，我们的算法可以在大约36分钟内完成训练，而所有现有的GCN训练算法由于内存不足问题均无法完成训练。更重要的是，Cluster-GCN使我们能够在不大幅增加时间和内存开销的情况下训练更深的GCN模型，从而提高预测准确性——使用5层Cluster-GCN，在PPI数据集上我们实现了99.36%的测试F1分数，而此前的最佳结果为98.71% [16]。我们的代码已在https://github.com/google-research/google-research/tree/master/cluster_gcn 公开提供。