论文荐读:理解图表示学习中的负采样

2020 年 5 月 29 日 学术头条
Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, Jie Tang. 2020. Understanding Negative Sampling in Graph Representation Learning. In The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’20).

Paper

http://keg.cs.tsinghua.edu.cn/jietang/publications/KDD20-Yang-et-al-Understanding_Negative_Sampling_in_GNN.pdf
Code & Data:
https://github.com/zyang-16/MCNS


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



因此,我们从目标函数和方差两个角度系统地分析了负采样的作用,从理论上证明了负采样与正采样在确定优化目标和估计方差方面同等重要。据我们所知,我们是第一个推导该理论并量化负采样分布应与正采样分布成正但次线性相关。在理论的指导下,我们提出了一种有效且可扩展的负采样策略,即马尔可夫链蒙特卡罗负采样(MCNS),用自对比近似估计正采样分布,用 Metropolis-Hastings 加速负采样过程。下图是我们提出的 MCNS 框架,采用 DFS 遍历得到最后一个节点的马尔可夫链,使用 Metropolis-Hastings 加速负采样过程,并将采样得到的负样本和正样本输入到编码器中,根据 Hinge loss,更新节点的向量表示。


我们在 5 个数据集上评估了我们的方法,这些数据集涵盖了 19 个实验设置,涵盖了广泛的下游图表示学习任务,包括链路预测,节点分类和个性化推荐。如下表所示,在个性化推荐任务上,无论采用 network embedding 或 GNN 作为编码器,MCNS 始终优于其他 8 个负采样策略,比最佳的 baseline 实现 2%-13% 的显著提高。此外,我们还在个性化推荐任务上,对比了不同负采样策略的效率。如下图所示,相对于其他启发式的负采样策略,我们提出的 MCNS 具有更优的效率。


此外,我们在 Arxiv 数据集上评估了不同负采样策略在链路预测任务上的性能,实验结果表明 MCNS 实现了不同程度性能的提高。

最后,我们在 BlogCatalog 数据集上评估节点分类任务,结果表明无论采用 network embedding 或 GNN 作为编码器,MCNS 均稳定地胜过所有的 baselines。


点击阅读原文,查看更多精彩!

登录查看更多
28

相关内容

自然语言处理领域中,判断两个单词是不是一对上下文词(context)与目标词(target),如果是一对,则是正样本,如果不是一对,则是负样本。采样得到一个上下文词和一个目标词,生成一个正样本(positive example),生成一个负样本(negative example),则是用与正样本相同的上下文词,再在字典中随机选择一个单词,这就是负采样(negative sampling)。
【KDD2020】最小方差采样用于图神经网络的快速训练
专知会员服务
27+阅读 · 2020年7月13日
近期必读的5篇 WSDM 2020【图神经网络(GNN)】相关论文
专知会员服务
56+阅读 · 2020年1月10日
必读的7篇 IJCAI 2019【图神经网络(GNN)】相关论文
专知会员服务
91+阅读 · 2020年1月10日
八篇NeurIPS 2019【图神经网络(GNN)】相关论文
专知会员服务
43+阅读 · 2020年1月10日
论文浅尝 | 一种嵌入效率极高的 node embedding 方式
开放知识图谱
13+阅读 · 2019年5月12日
图嵌入(Graph embedding)综述
人工智能前沿讲习班
448+阅读 · 2019年4月30日
图上的归纳表示学习
科技创新与创业
22+阅读 · 2017年11月9日
综述 | 知识图谱向量化表示
开放知识图谱
33+阅读 · 2017年10月26日
Arxiv
91+阅读 · 2020年2月28日
Arxiv
10+阅读 · 2019年2月19日
Arxiv
8+阅读 · 2018年2月23日
Arxiv
3+阅读 · 2018年2月19日
Arxiv
9+阅读 · 2018年1月30日
VIP会员
相关资讯
论文浅尝 | 一种嵌入效率极高的 node embedding 方式
开放知识图谱
13+阅读 · 2019年5月12日
图嵌入(Graph embedding)综述
人工智能前沿讲习班
448+阅读 · 2019年4月30日
图上的归纳表示学习
科技创新与创业
22+阅读 · 2017年11月9日
综述 | 知识图谱向量化表示
开放知识图谱
33+阅读 · 2017年10月26日
Top
微信扫码咨询专知VIP会员