Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks
Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks
复制标题
DOI：
--
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Difan Zou;Ziniu Hu;Yewen Wang;Song Jiang;Yizhou Sun;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Difan Zou;Ziniu Hu;Yewen Wang;Song Jiang;Yizhou Sun;Quanquan Gu
图卷积网络由于在不同的图任务和领域中的成功应用，近年来受到了广泛的关注。然而，为大型图训练GCN仍然是一个挑战。原始的全批量GCN训练需要计算每个GCN层图中所有节点的表示，这带来了很高的计算和内存成本。为了缓解这个问题，提出了几种基于采样的方法来在节点的子集上训练GCN。其中，逐层邻居采样方法递归地采样固定数量的邻居节点，其计算代价受到跨层邻居规模指数增长的影响;而逐层重要性采样方法摒弃了邻居依赖约束，跨层采样节点存在稀疏连接问题。针对这两个问题，本文提出了一种新的有效的采样算法--分层相关重要性采样（LAYER Dependent Importance Sampling，LAYER）。基于在上层中的采样节点，LARGE选择在这些节点的邻域中的节点，并使用构造的二分图来计算重要性概率。然后，它根据整个层的概率采样固定数量的节点，并递归地进行这样的过程，每层构造整个计算图。我们从理论和实验上证明，我们提出的采样算法优于以前的采样方法，无论是时间和内存。此外，由于其随机性，LARSTO具有更好的泛化精度比原来的全批GCN。
Graph convolutional networks (GCNs) have recently received wide attentions, due to their successful applications in different graph tasks and different domains. Training GCNs for a large graph, however, is still a challenge. Original full-batch GCN training requires calculating the representation of all the nodes in the graph per GCN layer, which brings in high computation and memory costs. To alleviate this issue, several sampling-based methods are proposed to train GCNs on a subset of nodes. Among them, the node-wise neighbor-sampling method recursively samples a fixed number of neighbor nodes, and thus its computation cost suffers from exponential growing neighbor size across layers; while the layer-wise importance-sampling method discards the neighbor-dependent constraints, and thus the nodes sampled across layer suffer from sparse connection problem. To deal with the above two problems, we propose a new effective sampling algorithm called LAyer-Dependent ImportancE Sampling (LADIES). Based on the sampled nodes in the upper layer, LADIES selects nodes that are in the neighborhood of these nodes and uses the constructed bipartite graph to compute the importance probability. Then, it samples a fixed number of nodes according to the probability for the whole layer, and recursively conducts such procedure per layer to construct the whole computation graph. We prove theoretically and experimentally, that our proposed sampling algorithm outperforms the previous sampling methods regarding both time and memory. Furthermore, LADIES is shown to have better generalization accuracy than original full-batch GCN, due to its stochastic nature.