今天给大家介绍的是清华大学的Zhen Yang等人在KDD 2020发表的文章“Understanding Negative Sampling in Graph Representation Learning”。作者在文章中分析负采样的作用，从理论上证明在优化目标函数和减小方差时负采样与正采样同等重要，得到负采样分布应与正采样分布正相关且呈次线性相关的结论，并提出了一个统一的负采样策略MCNS优化各种网络表示学习算法 。
1
背景
近年来，图表示学习逐渐成为数据挖掘研究的热点。主流的图表示学习算法包括传统的网络嵌入方法(如DeepWalk，LINE)和图神经网络(如GCN，GraphSAGE)。大量的网络嵌入工作已经研究出正节点对采样的良好标准。然而，很少有论文系统地分析或讨论图表示学习中的负采样。
在这篇文章中，作者证明了负采样与正采样一样重要。同时考虑负采样，可以确定优化目标并减少真实图形数据中估计值的方差。文章提出负采样分布应与正采样分布正相关且呈次线性相关的理论，并基于此理论提出了一种有效且可扩展的负采样策略，即马尔可夫链蒙特卡洛负采样（MCNS），该策略将理论应用于基于当前嵌入的近似正分布。为了降低时间复杂度，利用特殊的Metropolis-Hastings算法进行采样。
2
方法
2.1负采样原理
为了确定特定正分布的适当负分布，可能需要权衡目标的合理性(最佳嵌入在何种程度上适合下游任务)和预期损失(训练嵌入偏离最佳嵌入的程度)。一个简单的解决方案是对负节点进行正采样，并与其正采样分布呈次线性相关。
2.2 自对比估计
虽然推导出正采样与负采样的关系，但实际正分布是未知的，并且通常会隐式定义其近似值。因此，作者提出了一种自对比估计(self-contrast approximation)方法，用基于当前编码器的内积代替正分布，即
作者提出的MCNS通过改编的Metropolis-Hastings算法解决了采样耗时问题。
2.3 Metropolis-Hastings算法
Metropolis-Hastings算法构造了一个相对于
遍历且静止的马尔可夫链
这意味着
2.4 马尔可夫链负采样
MCNS的主要想法是应用Metropolis-Hastings算法，对
中的每个节点v从自对比估计分布中采样。为了解决Metropolis-Hastings具有相对较长的老化期的缺点，作者提出通过深度优先搜索(DFS)遍历图，并继续从最后一个节点的马尔可夫链生成负样本(如图1)。
图1 MCNS的一个运行示例
DFS遍历中心节点，每个节点通过马尔可夫链使用Metropolis-Hastings算法对三个负上下文节点进行采样。
此外作者将二元交叉熵损失替换为γ偏斜铰链损失
其中(u，v)是正节点对,( x，v)是负节点对。γ是一个超参数。算法2总结了MCNS。
图2 MCNS算法流程
3
实验
实验是在3个代表性任务、3个图表示学习算法和5个数据集总共19个实验设置下进行了评估，这些数据集涵盖了广泛的下游图形学习任务，包括链接预测，节点分类和个性化推荐。为了验证MCNS对不同类型的图表示学习算法的适应性，作者对DeepWalk，GCN，GraphSAGE三种算法进行了实验。实验设置基于度的负采样，难例负采样，基于GAN负采样作为基准，这些相对全面的实验结果证明了其鲁棒性和优越性。
表1 任务和数据集的统计数据
3.1个性化推荐
表2 在三个数据集上使用各种编码器的MCNS的推荐结果
结果表明，难例负采样通常会超过基于度的策略，MRR的性能会提高5％到40％。基于GAN的负采样策略的性能更高，这是因为不断发展的生成器更准确地挖掘了难例负采样。根据实验理论，提出的MCNS在最佳基准上可实现2％到13％的显著增益。
3.2链接预测
表3 Arxiv数据集上不同负采样策略的链接预测结果
在Arxiv数据集上，MCNS的各种图表示学习方法均优于所有基线。
3.3 节点分类
表4 BlogCatalog数据集上的多标签分类的Micro F1分数
不管训练集比率TR如何，MCNS都会稳定地胜过所有基线。Macro-F1的趋势相似，由于空间限制而被省略。
3.4分析
图3 度数和MCNS的比较
与度数的比较 图3中每条红线表示在此设置下MCNS的性能，蓝色曲线表示不同β的度数的性能，基于度的策略的表现一直低于MCNS，这表明MCNS在基于度的策略的表达能力之外学习了更好的负分布。此外，最佳β在数据集之间会有所不同，并且似乎很难在实验前确定，而MCNS自然会适应不同的数据集。
图4 MCNS在阿里巴巴上的性能
参数分析 为了定量测试MCNS的鲁棒性，作者通过更改两个最重要的超参数（嵌入尺寸和边距γ）来可视化MCNS的MRR曲线。
图5 运行时间比较
效率比较 为了比较不同的负采样方法的效率，作者在图5的推荐任务中报告了MCNS和带有GraphSAGE编码器的硬采样或基于GAN的策略（PinSAGE，WARP，DNS，KBGAN）的运行时间。
4
总结
作者在文章中从理论上分析了负采样在图表示学习的作用，并得出结论：负采样分布和正采样分布同等重要，并且应与正采样分布正相关且呈次线性相关。基于此理论，作者提出了MCNS，通过自对比估计逼近正采样分布，并通过Metropolis-Hastings算法加速计算。大量的实验表明，无论底层的图表示学习方法如何，MCNS的性能均优于8种负采样策略。