近年来，图表示学习得到了广泛的研究。尽管它有可能为各种网络生成连续的向量表示，但是将高质量的向量表示推向大型节点集的有效性和效率性方面仍具有挑战。大多数的图表示学习可以统一纳入 SampledNCE 框架，该框架包括一个用于生成节点嵌入的可训练编码器，一个正采样器和一个负采样器。现有技术通常集中于对正节点进行采样，而负采样策略则没有得到足够的探索。
因此，我们从目标函数和方差两个角度系统地分析了负采样的作用，从理论上证明了负采样与正采样在确定优化目标和估计方差方面同等重要。据我们所知，我们是第一个推导该理论并量化负采样分布应与正采样分布成正但次线性相关。在理论的指导下，我们提出了一种有效且可扩展的负采样策略，即马尔可夫链蒙特卡罗负采样（MCNS），用自对比近似估计正采样分布，用 Metropolis-Hastings 加速负采样过程。
我们在 5 个数据集上评估了我们的方法，这些数据集涵盖了 19 个实验设置，涵盖了广泛的下游图表示学习任务，包括链路预测，节点分类和个性化推荐。在个性化推荐任务上，无论采用 network embedding 或 GNN 作为编码器，MCNS 始终优于其他 8 个负采样策略，比最佳的 baseline 实现 2%-13% 的显著提高。此外，我们还在个性化推荐任务上，对比了不同负采样策略的效率。
相对于其他启发式的负采样策略，我们提出的 MCNS 具有更优的效率。此外，我们在 Arxiv 数据集上评估了不同负采样策略在链路预测任务上的性能，实验结果表明 MCNS 实现了不同程度性能的提高。最后，我们在 BlogCatalog 数据集上评估节点分类任务，结果表明无论采用 network embedding 或 GNN 作为编码器，MCNS 均稳定地胜过所有的 baselines。