GCN meets GPU: Decoupling "When to Sample" from "How to Sample"
GCN meets GPU: Decoupling "When to Sample" from "How to Sample"
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
M. Ramezani;Weilin Cong;M. Mahdavi;A. Sivasubramaniam;M. Kandemir
中科院分区：
文献类型：
--
作者：
M. Ramezani;Weilin Cong;M. Mahdavi;A. Sivasubramaniam;M. Kandemir
当在训练图卷积网络（GCN）中与随机梯度下降配对时，基于采样的方法有望提高可扩展性。虽然这些方法有效地缓解了邻域爆炸，但由于带宽和内存瓶颈，这些方法导致在异构系统中预处理和加载新样本时的计算开销，这显著降低了采样性能。通过将采样频率与采样策略解耦，我们提出了LazyGCN，这是一个通用而有效的框架，可以与任何采样策略集成，以大幅提高训练时间。LazyGCN背后的基本思想是定期执行采样，并有效地回收采样节点，以减轻数据准备开销。我们从理论上分析了所提出的算法，并表明，在一个温和的条件下的回收规模，通过减少内层的方差，我们能够获得相同的收敛速度作为底层的采样方法。我们还在大型真实世界的图形上给出了确凿的经验证据，表明所提出的模式可以显着减少采样步骤的数量，并在不影响准确性的情况下获得上级加速。
Sampling-based methods promise scalability improvements when paired with stochastic gradient descent in training Graph Convolutional Networks (GCNs). While effective in alleviating the neighborhood explosion, due to bandwidth and memory bottlenecks, these methods lead to computational overheads in preprocessing and loading new samples in heterogeneous systems, which significantly deteriorate the sampling performance. By decoupling the frequency of sampling from the sampling strategy, we propose LazyGCN, a general yet effective framework that can be integrated with any sampling strategy to substantially improve the training time. The basic idea behind LazyGCN is to perform sampling periodically and effectively recycle the sampled nodes to mitigate data preparation overhead. We theoretically analyze the proposed algorithm and show that under a mild condition on the recycling size, by reducing the variance of inner layers, we are able to obtain the same convergence rate as the underlying sampling method. We also give corroborating empirical evidence on large real-world graphs, demonstrating that the proposed schema can significantly reduce the number of sampling steps and yield superior speedup without compromising the accuracy.