【KDD2020-清华大学】理解图表示学习中的负采样，Understanding Negative Sampling in Graph Representation Learning

主题： Understanding Negative Sampling in Graph Representation Learning

摘要： 在最近的几年中，研究人员对图形表示学习进行了广泛的研究。尽管它具有为各种网络生成连续嵌入的潜力，但推断向大型节点集表示高质量表示的有效性和效率仍然具有挑战性。采样是实现性能目标的关键点。现有技术通常集中于对正节点对进行采样，而对负采样的策略还没有得到足够的研究。为了弥合差距，我们从客观和风险两个角度系统地分析了负样本的作用，从理论上证明了负样本在确定优化目标和结果方差方面与正样本同等重要。据我们所知，我们是第一个推导该理论并量化负采样分布应与其正采样分布呈正相关但与子线性相关的方法。在该理论的指导下，我们提出了MCNS，用Metropolis-Hastings用自对比度逼近来近似正分布，并加速Metropolis-Hastings进行负采样。我们在5个数据集上评估了我们的方法，这些数据集涵盖了19个实验设置，涵盖了广泛的下游图形学习任务，包括链接预测，节点分类和个性化推荐。这些相对全面的实验结果证明了其鲁棒性和优越性。