最近这段时间一直在做图网络相关,也差不多收尾了,有空整体复盘了下,大致以下几个主题,不过没整理完全哈哈
顺手再安利几份资料吧,
ok,回到正题,今天要介绍的这篇是『Graph Embedding』系列第一篇,十分经典
enjoy~
DeepWalk是首次将深度学习技术(无监督学习)引入到网络分析(network analysis)中的工作,它的输入是一个图,最终目标就是获得网络图中每个结点的向量表示 \mathbf{X}_{e} \in \mathbb{R}^{|V| \times d} 。毕竟万物皆可向量,得到向量之后能做的事情就非常多了。如下所示是论文中给出的Karate network
例子。
说到生成向量表示,最有名的莫过于Word2Vec
了,那么是不是可以将network embedding
的问题转化为熟悉的word embedding
形式呢?这样我们就可以借用word2vec的思想来解决了。
转化的方式就是Random Walk
,通过这种方式将图结构表示为一个个序列,然后我们就可以把这些序列当成一个个句子,每个序列中的结点就是句子中的单词。
简单的说,DeepWalk = RandomWalk + SikpGram
, 下面我们来具体介绍下两种技术。
随机游走,顾名思义,就是从输入图中的任意一个结点 v_{i} 开始,随机选取与其邻接的下一个结点,直至达到给定长度 t, 生成的序列 \tilde{\mathcal{W}}_{v_{i}}=\left(\mathcal{W}_{v_{i}}^{1},\cdots, \mathcal{W}_{v_{i}}^{k}, \cdots, \mathcal{W}_{v_{i}}^{t}\right)
在论文中,对于每一个顶点 v_{i}, 都会随机游走出 \gamma 条序列。
采用随机游走有两个好处:
word2vec的skip-gram相信大家都非常熟悉了,这里就不再赘述,放一张图。
结合上面两点, deepwalk其实就是首先利用random walk来表示图结构,然后利用skip-gram模型来更新学习节点表示。算法流程如下所示:
算法有两层循环,第一层循环采样 \gamma 条路径,第二层循环遍历图中的所有结点随机采样一条路径并利用skip-gram模型进行参数更新。
其中第2步构建二叉树的目的是为了方便后续 SkipGram模型的层次softmax算法。
参数更新的流程如下:
deepwalk可以说给网络学习方向打开了一个新思路,有很多优点:
但是仍然存在许多不足:
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。