DeepWalk:图表示的在线学习

简介: DeepWalk:图表示的在线学习

论文标题:DeepWalk: Online Learning of Social Representations


论文链接:https://arxiv.org/abs/1403.6652


论文来源:KDD 2014


一、概述


本文提出DeepWalk方法,来学习图节点的社会表示(social representation),学习到的表示处于较低维度的连续空间中。DeepWalk采用自然语言处理中的语言模型来建模一系列图上的随机游走节点序列,这些随机游走序列可以看做一种特殊的语言。模型的输入是一张图,输出是节点的隐表示,下图展示了一个例子,可以看到表示空间中线性可分的部分对应于原图根据模块最大化(modularity maximization)得到的划分:

QQ截图20220612094213.png

                                               example

二、社会表示的学习


  1. 问题陈述

QQ截图20220611202714.png


本文提出的方法用来捕获网络的拓扑信息。DeepWalk没有混合标签空间作为特征空间的一部分,而是采用无监督的方法来捕捉图的结构信息,忽略标签的分布。DeepWalk的目标是学习隐表示,QQ截图20220611202818.png是隐表示的维度,学习到的特征向量可以与任何分类算法相结合,即使是简单算法也可以得到好的性能。


我们希望算法学习到的节点表示能够具备以下特性:


①可适应性(adaptability):真实的网络是一直在变化的,新的社会关系(social relation)的出现不应该要求重复算法的学习过程;

②社区感知(community aware):隐表示之间的距离应该代表一种度量,用来评估网络相应成员节点之间的相似性,这允许在具有同质性(homophily)的网络中进行泛化;

③低维(low dimensional):当标注数据稀缺时,低维模型泛化地更好(可能是因为高维具有维度灾难),并且能够加速收敛和推断;

④连续(continuous):除了提供社区成员的细致入微的视图外,连续表示在社区之间有平滑的决策边界,这允许更具鲁棒性的分类。


  1. 随机游走


QQ截图20220611203023.png


  1. 幂律分布


如下图,节点在随机游走序列中出现的频率与自然语言中的词频同样满足幂律分布(power law):

QQ截图20220612094246.png

                                                  幂律分布

而语言建模技术解释了这种分布。我们的一个核心想法是应用于语言建模的技术(语言中的符合频率满足幂律分布,而随机游走序列中节点出现的频率也满足)也能够用来建模网络中的社区结构。

  1. 语言模型

语言建模的目的是估计特定的词序列出现在语料库中的似然。具体的,给定一个词序列:

QQ截图20220611203126.png

QQ截图20220611203247.png


然而,随着随机游走序列长度的增加,该目标函数的计算变得不可行。语言模型对于这个问题的解决方案是将这个概率的预测反过来(其实就是指 SkipGram),其实是一种对原有问题的松弛。具体的做法是:

①使用一个词来预测其上下文;

②上下文既包含这个词左边的词也包含右边的词;

③移除了词的顺序限制,也就是说模型需要最大化任何在上下文中出现的词的似然,忽略这些词与该词的偏移。

将上述方法应用到节点表示学习上,要优化的问题就变成了:

QQ截图20220611203318.png

解决上述问题能够捕获图结构中节点之间的相似性,具有相似邻域的节点会获得相似的表示。通过结合截断的随机游走与语言模型,可以满足前面提到的需要满足的表示的特性。

三、方法


QQ截图20220611203351.png

QQ截图20220612094318.png

                                              DeepWalk

第3行代表整个过程迭代QQ截图20220611203608.png次,每次为每个节点采样一个随机游走。第4行代表对节点进行随机排列,这不是必须的,但是可以加速随机梯度下降的收敛。对于每个随机游走,使用第7行的SkipGram进行参数的更新。

  • SkipGram

SkipGram是一种语言模型,它最大化句子中QQ截图20220611203632.png大小的窗口内出现的词的共现概率。下面的算法展示了SkipGram在DeepWalk中的应用:

QQ截图20220612094342.png

                                                    SkipGram


QQ截图20220611203734.png


QQ截图20220612094424.png

下图展示了DeepWalk的大致过程,其中(c)表示Hierarchical Softmax的过程:

QQ截图20220612094442.png

                                                    DeepWalk

我们也可以通过统计随机游走中节点出现的频率来构建哈弗曼树,从而进一步加速训练过程,降低复杂度。

  • 优化

QQ截图20220611203827.png

QQ截图20220612094534.png

                                       多个worker的影响

四、实验


  1. 数据集


在BlogCatalog,Flickr和YouTube三个数据集上进行实验,进行节点的分类任务,数据集统计情况如下:

QQ截图20220612094704.png

                                                    数据集统计

  1. 实验结果

下面展示了三个数据集上对比不同baseline的效果:

QQ截图20220612094956.png

                                             BlogCatalog

QQ截图20220612095020.png

                                                   Flickr

QQ截图20220612095042.png

                                                YouTube

  1. 超参数敏感性


以下实验探究了不同超参数的敏感性:

QQ截图20220612095118.png

                                               超参数敏感性


相关文章
|
自然语言处理 搜索推荐 算法
M2GRL:一种用于全网规模推荐系统的多任务多视角图表示学习框架
由阿里云开发者社区联合新零售智能引擎事业群共同打造的《KDD 论文精华解读》电子书重磅发布!覆盖推荐系统、图神经网络预训练、买家秀视频标题生成、在线电视剧的受众竞争力预测和分析等 10+ 内容,免费下载电子书感受科技的震撼!
M2GRL:一种用于全网规模推荐系统的多任务多视角图表示学习框架
|
1天前
|
Serverless 开发工具 开发者
活动实践 | 西游再现,函数计算一键部署 Flux 超写实文生图模型部署
这些图片展示了阿里巴巴云开发者生态的多个方面,包括开发工具、技术文档、社区交流、培训认证等内容,旨在为开发者提供全方位的支持和服务。
|
7月前
|
机器学习/深度学习 自然语言处理 搜索推荐
【传知代码】图神经网络长对话理解-论文复现
在ACL2023会议上发表的论文《使用带有辅助跨模态交互的关系时态图神经网络进行对话理解》提出了一种新方法,名为correct,用于多模态情感识别。correct框架通过全局和局部上下文信息捕捉对话情感,同时有效处理跨模态交互和时间依赖。模型利用图神经网络结构,通过构建图来表示对话中的交互和时间关系,提高了情感预测的准确性。在IEMOCAP和CMU-MOSEI数据集上的实验结果证明了correct的有效性。源码和更多细节可在文章链接提供的附件中获取。
【传知代码】图神经网络长对话理解-论文复现
|
7月前
|
机器学习/深度学习 数据挖掘 算法框架/工具
想要了解图或图神经网络?没有比看论文更好的方式,面试阿里国际站运营一般会问什么
想要了解图或图神经网络?没有比看论文更好的方式,面试阿里国际站运营一般会问什么
|
7月前
|
SQL 自然语言处理 NoSQL
ChatTuGraph:通过大模型“与图对话”
相比于SQL相对成熟的语法标准,图查询语言尚未形成成熟的统一标准,目前是多种查询语法并存的状态,上手门槛高,因此更需要借助大语言模型的自然语言理解能力,降低图数据库查询语言的使用门槛。
ChatTuGraph:通过大模型“与图对话”
|
7月前
|
机器学习/深度学习
R语言使用Rasch模型分析学生答题能力
R语言使用Rasch模型分析学生答题能力
|
7月前
|
机器学习/深度学习 自然语言处理 搜索推荐
推荐系统的算法分类和操作流程介绍
推荐系统的算法分类和操作流程介绍
|
机器学习/深度学习 算法 数据挖掘
图机器学习算法有哪些
图机器学习算法有哪些
|
数据可视化
R可视化学习(3)--误差棒图
篇介绍如何利用R软件和ggplot2制作误差线的条形图,我们可以使用如下几个函数制作不同类型的误差线图形: • geom_errorbar() • geme_linerange() • geom_pointrange() • geom_crossbar() • geom_errorbarh()
280 0
|
机器学习/深度学习 数据可视化 Ubuntu
PlotNeuralNet + ChatGPT创建专业的神经网络的可视化图形
PlotNeuralNet:可以创建任何神经网络的可视化图表,并且这个LaTeX包有Python接口,我们可以方便的调用。
578 0
PlotNeuralNet + ChatGPT创建专业的神经网络的可视化图形