理解图表示学习中的负采样 | KDD论文解读

新零售智能引擎事业群出品

近年来，图表示学习得到了广泛的研究。尽管它有可能为各种网络生成连续的向量表示，但是将高质量的向量表示推向大型节点集的有效性和效率性方面仍具有挑战。大多数的图表示学习可以统一纳入SampledNCE框架，该框架包括一个用于生成节点嵌入的可训练编码器，一个正采样器和一个负采样器（如下图所示）。现有技术通常集中于对正节点进行采样，而负采样策略则没有得到足够的探索。

因此，我们从目标函数和方差两个角度系统地分析了负采样的作用，从理论上证明了负采样与正采样在确定优化目标和减小估计方差方面同等重要。首先，我们从如下的图表示学习的目标函数出发，讨论更普遍的图表示学习形式

其中p_d 是估计的数据分布，p_n 是负采样分布， u ⃗、 v ⃗是节点的向量表示，σ(⋅) 是sigmoid函数。我们可以得出最优情况下向量内积应具有最优值：

上式表明正采样分布和负采样分布对目标函数的优化具有相同程度的影响。
此外，我们还从方差的角度分析了负采样的作用，分别从正采样分布中采样T个正样本对，从负采样分布中采样kT个负样本对，用于最小化经验误差。最终，根据我们证明的定理——一个随机变量√T(θT−θ∗)T(θT−θ∗) 将逐渐收敛到一个具有零均值向量和协方差矩阵的分布，得到均方误差：

从上式可知，均方误差不仅与正采样分布p_d有关，也与负采样分布p_n也有关。此外，还明确了负采样分布与正采样分布之间的关系，这也是我们负采样策略遵守的准则。据此，我们提出负采样分布应该与正采样分布呈现正但次线性相关，即p_n (u│v)∝p_d (u│v)^α,0<α<1。
在理论的指导下，我们提出了一种有效且可扩展的负采样策略，即马尔可夫链蒙特卡罗负采样（MCNS），用自对比近似估计正采样分布，用Metropolis-Hastings加速负采样过程。

具体来说，我们使用当前编码器的内积估计正采样分布，即这种估计形式类似于RotatE[1]中的技术，并且非常耗时。每次采样都需要O(n)的时间复杂度，难以在大规模图上实现。我们的MCNS借助Metropolis-Hastings算法解决这一问题。
下图是我们提出的MCNS框架，采用DFS遍历得到最后一个节点的马尔可夫链，使用Metropolis-Hastings加速负采样过程，并将采样得到的负样本和正样本输入到编码器中，获得节点的向量表示。为了训练模型的参数，我们将二元交叉熵损失函数替换为hinge loss，其基本思想是最大化正样本对的内积，同时，确保负样本对的内积比正样本对的内积要小一定的阈值。Hinge loss的形式如下：

其中(u,v)是正样本对，(x,v) 是负样本对，γ是阈值，是一个超参数。

在MCNS中，我们对每个节点使用Metropolis-Hastings算法以加速负采样过程，其中提出的分布q(y|x)也影响着收敛速度。我们的q(y|x)是按照1:1的比例混合均匀采样和最近邻的k个节点的采样。MCNS进行负采样的过程如下：

为了证明我们提出的MCNS的有效性，我们在3个常用的图表示学习任务上，使用典型的3个图表示学习算法，在5个数据集上进行了实验。这些数据集涵盖了19个实验设置，涵盖了从信息检索[2]，推荐[3,4]和知识图谱嵌入[5,6]中收集到的8个负采样策略。在个性化推荐任务上，如下表所示，无论采用network embedding 或GNN作为编码器，MCNS始终优于其他8个负采样策略，比最佳的baseline实现2%-13%的显著提高。此外，我们还在个性化推荐任务上，对比了不同负采样策略的效率。如下图所示，相对于其他启发式的负采样策略，我们提出的MCNS具有更优的效率。

我们在Arxiv数据集上评估了不同负采样策略在链路预测任务上的性能，实验结果表明MCNS实现了不同程度性能的提高。此外，我们还在BlogCatalog数据集上评估节点分类任务，结果表明无论采用network embedding 或GNN作为编码器，MCNS均稳定地胜过所有的baselines。

最后，我们还做了一些额外的实验以便进一步理解我们所提出的MCNS。在之前的理论部分，我们从目标函数和方差的角度分析的负采样策略的准则。但是，可能会产生以下疑问：（1）采样更多的负样本是否总是有帮助的？（2）为什么我们的结论与“对附近节点进行正采样而对远处节点进行负采样”的直觉相矛盾？
为了进一步加深对负采样的理解，我们设计了两个扩展实验，以验证我们的理论。如下图左图所示，如果我们采样更多的负样本，一开始性能会随着负样本数量的增加而提高，随后则会降低。根据均方误差计算公式，一开始，采样更多的负样本会降低方差，从而提高性能。但是，当性能达到最佳状态后，继续增加负样本则会使性能下降，原因在于增加了额外的偏差。右图表明了对更远处的节点进行负采样会导致灾难性的后果。我们设计了一种名为inverseDNS的策略，在候选的负样本中选择得分最低而不是得分最高的样本作为负样本，也就是选择更远处的节点作为负样本。实验结果表明MRR和Hits@30随着M的增加而下降，因此验证了我们的理论。

参考文献:

[1]Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019. Rotate: Knowl- edge graph embedding by relational rotation in complex space. arXiv preprint arXiv:1902.10197 (2019).
[2] Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang. 2017. Irgan: A minimax game for unifying generative and discriminative information retrieval models. In SIGIR’17. ACM, 515–524.
[3] Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative filtering for implicit feedback datasets. In ICDM’08. Ieee, 263–272.
[4] Weinan Zhang, Tianqi Chen, Jun Wang, and Yong Yu. 2013. Optimizing Top-N Collaborative Filtering via Dynamic Negative Item Sampling. In SIGIR’13. ACM, 785–788.
[5] Liwei Cai and William Yang Wang. 2018. KBGAN: Adversarial Learning for Knowledge Graph Embeddings. In NAACL-HLT‘18. 1470–1480.
[6] Yongqi Zhang, Quanming Yao, Yingxia Shao, and Lei Chen. 2019. NSCaching:Simple and Efficient Negative Sampling for Knowledge Graph Embedding. (2019), 614–625.

更多数据挖掘内容查看：《KDD论文精华解读》