做企业网站设计方案,分析网站设计对网站搜索引擎友好性的影响,沧州网站开发,佛山微网站价格word2vec使用语言天生具备序列这一特性训练得到词语的向量表示。而在图结构上#xff0c;则存在无法序列的难题#xff0c;因为图结构它不具备序列特性#xff0c;就无法得到图节点的表示。deepwalk 的作者提出#xff1a;可以使用在图上随机游走的方式得到一串序列#x… word2vec使用语言天生具备序列这一特性训练得到词语的向量表示。而在图结构上则存在无法序列的难题因为图结构它不具备序列特性就无法得到图节点的表示。deepwalk 的作者提出可以使用在图上随机游走的方式得到一串序列然后再根据得到游走序列进行node2vec的训练进而获取得到图节点的表示。本质上deepwalk和word2vec师出同门来自同一个思想deepwalk算法的提出为图结构学习打开了新的天地。 1. 前言
目前主流算法可大致分为两类walk-based 的图嵌入算法GEGraph Emebdding 和 message-passing-based 的图神经网络算法GNN。
GE类算法主要包括有deepwalk、metapath2vec基于消息传递机制的图神经网络算法的经典论文则是GCNGAT等。
因为内容过多本期讲解分两期第一期首先介绍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)) i∏m(p(yi∣vj)) 其中 y i y_i yi的取值范围为{01}这里的m其实就是这棵二叉树的深度也就是 l o g V log V logV向上取整。比如这里就是 l o g 8 3 log83 log83。 这么一套操作下来之后就可以把原本一个线性的复杂度时间O(v) 降到了O(logV)厉害吧原文给出了一个比较直观的例子用于理解Hierarchical softmax如下 在求得这个概率之后就可以转头去做优化了。
优化算法
deepwalk 论文的作者采取的是 SGDstochastic gradient descent 优化损失。这里没有什么好介绍的直接跳过了。到此为止整个算法的核心内容已经介绍完毕了。接下来看看这个算法的实际效果如何
3. 实际效果
deepwalk论文作者给出了一个效果示例图如下图所示 左侧是一个图结构信息右侧是根据学习到的embedding得到的一个二维展示可以看出图结构和节点表示几乎能够一一对应起来顶点的颜色表示输入图对一个基于模块的聚类。
4. 发现
文章中提出了许多非常有意思的知识。坦白讲在没有仔细看这篇文章之前有一些知识点我是不了解的比如「zipfs laws」。
4.1 zipf’s law
zipfslaw又称齐夫定律这是一个经验定律。该定律表示一个单词的排名 r r r和这个单词的出现频率 p p p成反比也即 r ∗ p k r*p k r∗pk。用图像表示则是如下这个样子 y1/x 这个函数的图像长这样 齐夫定律的图像要稍微直一些。作者发现如果原始图的顶点服从齐夫定律那么根据随机游走选出来的子图的频次也会满足齐夫定律。
这个时候作者就想到如果满足齐夫定律的自然语言可以用语言模型建模那么用随机游走方式得到的子图是否也可以通过语言模型来建模呢于是接着有了后面使用SkipGram算法训练embedding才有了这篇论文的诞生。
5. 实验效果
最后作者给出了deepwalk算法在三个数据集上的多标签分类实验效果如下所示。总结成一个词惊艳 好了到此第二期的经典论文阅读的第一部分工作已经结束后面再围绕metapath2vec进行介绍。高质量分享实属不易期待各位同学们的评论和赞赏哟。
