《经典论文阅读2》基于随机游走的节点表示学习—Deepwalk算法

本文主要是介绍《经典论文阅读2》基于随机游走的节点表示学习—Deepwalk算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

word2vec使用语言天生具备序列这一特性训练得到词语的向量表示。而在图结构上,则存在无法序列的难题,因为图结构它不具备序列特性,就无法得到图节点的表示。deepwalk 的作者提出:可以使用在图上随机游走的方式得到一串序列,然后再根据得到游走序列进行node2vec的训练,进而获取得到图节点的表示。本质上deepwalk和word2vec师出同门(来自同一个思想),deepwalk算法的提出为图结构学习打开了新的天地。

1. 前言

目前主流算法可大致分为两类:walk-based 的图嵌入算法(GE,Graph Emebdding )和 message-passing-based 的图神经网络算法(GNN)。

  • GE类算法主要包括有deepwalk、metapath2vec
  • 基于消息传递机制的图神经网络算法的经典论文则是GCN,GAT等。

因为内容过多,本期讲解分两期,第一期首先介绍GE类算法,第二期介绍图神经网络算法。GE类的算法经典的还属deepwalk,所以本期首先围绕deepwalk这篇论文进行介绍。

接触过word2vec 的同学都知道,word2vec的思想一改往日的one-hot囧境,将每个word映射成一个高维向量,这些学习到的的vector便具备了一定的特性,可以直接在下游任务中使用。有关word2vec这里不再叙述,更详细内容可以参考我之前的文章。

但是如果想得到图结构中顶点表示该怎么办呢?毕竟图结构与语言序列不同,图上的一个顶点可能有很多个连接点,而文本序列则是单线条,如下图所示,可以看出图结构与文本序列有着非常大的差异。
图结构
那就没有办法去解决图节点的表示学习了吗?
当然不是!而且方法还有很多,聪明的前辈们提出了一种叫做『deepwalk』的算法,这个算法着实让我惊艳。本质上说,deepwalk算法是基于图上的word2vec,而启发作者的其实是:由于二者数据分布(自然语言的词频和随机游走得到子图的节点的频率)存在一定的相似性。
在这里插入图片描述
所以说,很多精妙的想法不是凭空造出来的,背后其实是有数据统计支撑的。

2. 思想

文本序列虽然只是一个序列,但是我们可以想象有一张巨大的由各个单词组成的图,我们随机从图上连接几个顶点就组成了一句话。例如『论文解析之deepwalk』其实就是从一张偌大的图中挑选出这么几个单词组成的一句话,如下图所示:
在这里插入图片描述
那么对于其它的图,我们也可以这么做。即:从一张大图上随机游走,这样便得到了一串序列。将这得到的序列便可以利用word2vec的方法来学习节点的表示了。

想法是不是很精妙?真的很精妙!其实我们自己在解决问题的时候,也需要抱着这样的『转换』思想,如果直接求A不成,那么能否利用已有的知识求A?这再次说明问题的转化能力是一个非常重要的能力。

既然问题已经得到了转化,接下来的工作就比较简单了,可以直接利用word2vec中的算法(如Skip gram算法)去训练得到图节点的embedding

3. 模型

3.1 模型构造

deepwalk 算法主要包含两部分:第一部分是random walk generator;第二部分是一个更新程序。
在这里插入图片描述

  • 采样方法
    deepwalk中的采样方法其实是非常简单的均匀采样。下文中介绍到了这一采样算法:
    在这里插入图片描述
    step1. 首先随机采样一个节点作为此次walk的根节点。
    step2. 接着从采样序列的最后一个节点的邻居中再随机选一个节点
    step3. 直到采样序列的最大长度达成。

本文采取的实验参数是:将每个节点都做一次根节点,随机游走可以达到最长的长度为t。 对应的算法伪代码如下所示:
在这里插入图片描述

  • 更新程序
    在得到随机游走的序列后,便可以使用word2vec算法获取节点的embedding了。deepwalk算法使用的是SkipGram 算法。SkipGram算法的思想很简单,就是利用当前词去预测周围词。具体来看Skip-Gram 的算法伪代码。
    在这里插入图片描述
    p ( u k ∣ ϕ ( v j ) p(u_k | \phi(v_j) p(ukϕ(vj) 其实就是求在 v j v_j vj 这个顶点出现的条件下,顶点 u k u_k uk出现的概率,思想就是这么简单。那么损失函数也很好定义,直接取log后再取负数即可。但这里有个小trick点,(其实这个点也是训练word2vec 中的一个关键点),就是计算 p ( u k ∣ ϕ ( v j ) ) p(u_k|\phi(v_j)) p(ukϕ(vj))时,我们一般都是用softmax来计算这个概率,softmax的计算公式是
    p ( x j ) = e x p ( x j ) ∑ i n e x p ( x i ) p(x_j) = \frac{exp(x_j)}{\sum_i^n{exp(x_i)}} p(xj)=inexp(xi)exp(xj)
    但是词表的大小一般都是上万起步,如果要逐项计算 e x p ( x i ) exp(x_i) exp(xi),则非常浪费计算资源,那么有没有可以解决这个问题的方法呢?聪明的前辈们已经替我们想到了解决方法,那就是使用:负采样或者Hierarchical softmax方法。本文的作者使用的是HIerarchical softmax。因为skip gram算法在之前的文章中已经分析过,这里直接跳过。接下来我就再花费大家的一点时间来给大家介绍一下这个Hierarchical softmax

3.2 Skip Gram

有兴趣的请翻前文。

3.3 Hierarchical softmax

这个Hierarchical softmax的算法思想其实非常简单,一言以蔽之:能否减少分类节点的个数(其实本质上也是负采样,只不过利用了完全二叉树去实现这个负采样的过程)。
例如:假设一部词典一共有8个单词,那么就可以构建一个如下所示的二叉树。
在这里插入图片描述
其中:

  • 叶子节点与每个单词对应。
    那么求上下文单词 u k u_k uk在条件 v j v_j vj出现时的概率这一问题就转化成了到达这个叶子节点的概率问题。 而到达每个叶子节点的概率是唯一的(因为路径各不相同)。那么之前的这个式子 p ( u k ∣ ϕ ( v j ) p(u_k | \phi(v_j) p(ukϕ(vj) 就可以转化成由下面这个式子去求解:
    ∏ i m ( p ( y i ∣ v j ) ) \prod_i^m(p(y_i|v_j)) im(p(yivj))
    其中, y i y_i yi的取值范围为{0,1},这里的m其实就是这棵二叉树的深度,也就是 l o g V log V logV向上取整。比如这里就是 l o g 8 = 3 log8=3 log8=3
    这么一套操作下来之后,就可以把原本一个线性的复杂度时间O(v) 降到了O(logV),厉害吧!原文给出了一个比较直观的例子,用于理解Hierarchical softmax,如下:
    在这里插入图片描述
    在求得这个概率之后,就可以转头去做优化了。

优化算法

deepwalk 论文的作者采取的是 SGD(stochastic gradient descent )优化损失。这里没有什么好介绍的,直接跳过了。到此为止,整个算法的核心内容已经介绍完毕了。接下来看看这个算法的实际效果如何?

3. 实际效果

deepwalk论文作者给出了一个效果示例图,如下图所示:
在这里插入图片描述
左侧是一个图结构信息,右侧是根据学习到的embedding得到的一个二维展示,可以看出图结构和节点表示几乎能够一一对应起来(顶点的颜色表示输入图对一个基于模块的聚类)。

4. 发现

文章中提出了许多非常有意思的知识。坦白讲,在没有仔细看这篇文章之前,有一些知识点我是不了解的,比如「zipf's laws」。

4.1 zipf’s law

zipfs'law,又称齐夫定律,这是一个经验定律。该定律表示:一个单词的排名 r r r和这个单词的出现频率 p p p成反比,也即 r ∗ p = k r*p = k rp=k。用图像表示则是如下这个样子:
在这里插入图片描述
y=1/x 这个函数的图像长这样:
在这里插入图片描述
(齐夫定律的图像要稍微直一些)。作者发现,如果原始图的顶点服从齐夫定律,那么根据随机游走选出来的子图的频次也会满足齐夫定律。
在这里插入图片描述

这个时候作者就想到,如果满足齐夫定律的自然语言可以用语言模型建模,那么用随机游走方式得到的子图是否也可以通过语言模型来建模呢?于是接着有了后面使用SkipGram算法训练embedding,才有了这篇论文的诞生。

5. 实验效果

最后,作者给出了deepwalk算法在三个数据集上的多标签分类实验效果,如下所示。总结成一个词:惊艳!
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
好了,到此第二期的经典论文阅读的第一部分工作已经结束,后面再围绕metapath2vec进行介绍。高质量分享实属不易,期待各位同学们的评论和赞赏哟。
在这里插入图片描述

这篇关于《经典论文阅读2》基于随机游走的节点表示学习—Deepwalk算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/904908

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

使用C#如何创建人名或其他物体随机分组

《使用C#如何创建人名或其他物体随机分组》文章描述了一个随机分配人员到多个团队的代码示例,包括将人员列表随机化并根据组数分配到不同组,最后按组号排序显示结果... 目录C#创建人名或其他物体随机分组此示例使用以下代码将人员分配到组代码首先将lstPeople ListBox总结C#创建人名或其他物体随机分组