To accelerate the training of graph convolutional networks (GCNs), many sampling-based methods have been developed for approximating the embedding aggregation. Among them, a layer-wise approach recursively performs importance sampling to select neighbors jointly for existing nodes in each layer. This paper revisits the approach from a matrix approximation perspective. We identify two issues in the existing layer-wise sampling methods: sub-optimal sampling probabilities and the approximation bias induced by sampling without replacement. We propose two remedies: new sampling probabilities and a debiasing algorithm, to address these issues, and provide the statistical analysis of the estimation variance. The improvements are demonstrated by extensive analyses and experiments on common benchmarks.
翻译:为加快图象卷发网络的培训,为接近嵌入汇总,已经开发了许多基于取样的方法,其中,一种分层方法反复进行重要取样,为每个层的现有节点共同选择邻里。本文从矩阵近似角度重新审视了这一方法。我们从现有的分层抽样方法中找出两个问题:低最佳取样概率和抽样而不替换引起的近似偏差。我们提出了两种补救办法:新的取样概率和偏差算法,以解决这些问题,并对估计差异提供统计分析。通过对共同基准的广泛分析和实验,可以证明这些改进。