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

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