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

简介: 本文“Understanding Negative Sampling in Graph Representation Learning”已被KDD 2020录用。

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

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

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

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

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

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

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

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

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

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

参考文献:

[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论文精华解读》

相关文章
|
人工智能 UED
DynamiCrafter:可实现任意类型静态图像转化为逼真动态视频
【2月更文挑战第17天】DynamiCrafter:可实现任意类型静态图像转化为逼真动态视频
1035 1
DynamiCrafter:可实现任意类型静态图像转化为逼真动态视频
|
存储 数据采集 人工智能
AI时代:云存储加速多模态数据存储与管理创新
阿里云存储产品高级解决方案架构师欧阳雁(乐忱)分享了中国企业在全闪存高端存储市场的快速增长,指出AI大模型的发展推动了企业级存储市场。去年,高端企业级存储闪存占比约为25%,相较于欧美50%的比例,显示出中国在AI领域的巨大增长潜力。演讲涵盖AI业务流程,包括数据预处理、训练和推理的痛点,以及针对这些环节的存储解决方案,强调了稳定、高性能和生命周期管理的重要性。此外,还介绍了数据预处理的全球加速和弹性临时盘技术,训练阶段的高性能存储架构,推理场景的加速器和AI Agent的应用,以及应对大数据业务的存储考量,如对象存储、闪电立方和冷归档存储产品。
44296 22
|
4月前
|
人工智能 运维 文字识别
企业大模型本地化部署与数据安全实践:从 RAG 权限过滤到审计闭环
本文聚焦企业大模型本地化部署中的数据安全痛点,以RAG问答系统为例,详解权限过滤前置、元数据治理、审计闭环等关键实践,提供可落地的分层架构与FastAPI代码骨架,强调“模型看不见无权数据”才是安全底线。
781 0
|
8月前
|
缓存 NoSQL 算法
扛住亿级流量的核心防线:限流、熔断、降级全链路深度拆解与实战
本文系统讲解分布式系统亿级流量治理,涵盖限流(固定/滑动窗口、漏桶、令牌桶及Redis分布式实现)、熔断(状态机、Resilience4j实战)与降级(功能开关、读/写降级)三大核心能力,并提供全链路分层架构、生产避坑指南与最佳实践,助力系统稳定扛压。
904 2
|
7月前
|
人工智能 数据挖掘 数据安全/隐私保护
AI拆解小红书和公众号笔记,4个步骤让你看懂爆款底层密码(附AI工作流实操步骤和AI提示词)
用AI深度拆解155篇万赞笔记,提炼出爆款共性:选题抓痛点、开头造冲突、结构强逻辑、表达重共鸣。本文分享实操四步法、40+可复用模板及原创提示词,助你告别凭感觉创作,科学提升内容效率
1702 4
|
7月前
|
存储 缓存 监控
企业接入 GPT-5.5 前要评估什么:架构、合规、成本与容灾
GPT-5.5已超越聊天接口,具备长上下文、工具调用、推理工作流等企业级能力,但随之带来权限、成本、合规新挑战。接入前须厘清架构解耦、权限审计、数据合规、分层计费与容灾备用五大核心问题。
490 0
|
人工智能 运维 监控
首个云上 AI 原生全栈可观测平台来了!
9月21日,2024 云栖大会,阿里云发布全新的 AI 原生全栈可观测平台,首次实现云上 AI 大模型从训练到推理再到应用的全链路实时观测、告警与诊断。
1935 123
|
11月前
|
机器学习/深度学习 人工智能 测试技术
2025年终端应用全链路性能测试实施策略与实践对比
介绍2025年终端应用全链路性能测试面临的挑战及主流实施方案,包括云真机兼容性测试、SaaS化压力测试平台、AI驱动的自动化测试工具。对比三者原理、优势、局限及适用场景,给出分阶段实施策略、关键成功要素和风险规避方法,还解答常见方案选择等问题。
|
存储 调度 C++
【操作系统】进程与线程的区别及总结(非常非常重要,面试必考题,其它文章可以不看,但这篇文章最后的总结你必须要看,满满的全是干货......)
【操作系统】进程与线程的区别及总结(非常非常重要,面试必考题,其它文章可以不看,但这篇文章最后的总结你必须要看,满满的全是干货......)
1073 1
|
JSON 前端开发 Java
第05课:Spring Boot中的MVC支持
第05课:Spring Boot中的MVC支持
552 0