Paper link
DeepWalk: Online Learning of Social Representations
作者首次将深度学习(无监督特征学习)引入到网络分析中,该技术已经在NLP中得到很好的应用,开发出DeepWalk算法,通过对随机游走建模学习图中顶点的隐藏表示。
DeepWalk对图结构的学习独立于标签分布。
Problem Definition
$G = (V, E)$, 其中$V$是网络的成员,$E$是他的边,$E \in (V \times V)$, 一个带有部分标签的网络可以表示为$G_L = (V,E,X,Y)$,$X \in \mathbf{R} ^ {|V| \times S}$,$S$是特征向量的维度,$Y \in \mathrm{R} ^ {|V| \times |\gamma|}$,$\gamma$是标签的维度。
DeepWalk的目标就是学习到图的隐藏表示$X_E \in \mathrm{R} ^ {|V| \times d}$,$d$是一个很小的维度。
Language Modeling
社交网络和NLP的词库都遵循着power-law。
DeepWalk的主要贡献是将已经用于NLP的技术重新用于网络。
language modeling的目的是估计某个单词序列在语料库中出现的可能性,对于一个单词序列$W_1^n = (w_0,w_1,\cdots,w_n)$,其中$w_i \in V$ (V is vocabulary),目标是最大化概率$Pr(w_n|w_n,w_1,\cdots,w_{n-1})$,对应在图上的random walk则是最大化$Pr(v_i|v_0,v_1,\cdots,v_{i-1})$,$v_i$是目前为止random walk访问过的节点。
DeepWalk的目标是学习latent representation,引入一个映射函数$\Phi:v\in V \rightarrow \mathrm{R}^{|V| \times d}$,因此目标变为:
随着walk length的增加,计算这个目标函数将十分困难,目前在language modeling提出了新的解决方法,将预测任务颠倒过来:
- 不再用上下文预测缺失的单词,而是通过给定单词预测上下文。
- 上下文包含给定单词左右的单词。
- 不考虑单词的顺序,模型最大化上下文中单词出现的概率。
此时优化问题变为:
Algorithm: DeepWalk
DeepWalk算法包含两部分:
- random walk生成器
- 更新程序
在每次对所有点进行randowm walk之前,生成一个随机遍历顶点的顺序(line 4),这样可以加快算法收敛的速率。
line 7是按照公示2对representation进行更新。
SkipGram
对于random walk中的每个节点,目标是最大化在窗口$w$中元素的出现的概率,
$\alpha$初始值设置为2.5%,然后线性的减小。
Hierarchical Softmax
使用logistic regression建模,将产生大量等于 $|V|$的标签,是计算变得复杂。
如果将顶点放到二叉搜索树的叶子节点,那么预测问题将变为最大化特定路径的概率,节点$u_k$可以表示为$b_0, b_1,\cdots,b_{\lceil log|V| \rceil}$即:
使用Haffman编码可以优化访问节点的时间。
Parallelizability
random walk中的节点的分布遵循power-law,这导致$\Phi$的更新不会很频繁,因此可以使用异步版本的SGD(ASGD),通过多个worker来加速收敛。
通过图4可以看出,多个worker可以线性的减少时间,通过对性能的影响非常小。
Algorithm Variants
Streaming
流计算将不能获取整张图的信息,因此算法需要进行一些调整:
- 将不再适合使用不断减小的学习率$\alpha$,需要设置为一个足够小的值。
- 因为不知道$|V|$的数量,因此无法构建Hierarchical Softmax tree,可以构造一个足够大的tree,然后不断地将新节点分配到叶子节点,如果可以粗略的估计顶点的访问频率,仍可以使用Haffman编码减少节点访问时间。
Non-random walks
Some graphs are created as a by-product of agents interacting with a sequence of elements (e.g. users’s navigation of pages on a website).
对于这种图可以直接用来建模,以这种方式采样的图不仅捕获了网络结构,同时也得到了遍历路径的频率。
Experimental
Multi-label Classification
共使用三种数据集:
- BlogCatalog是博客作者的社交关系图,标签表示是作者提供的文章的topic。
- Flicker是照片分享网站中用户之间的联系,标签表示用户的interest group,例如’black and white’。
- Youtube视频分享网站的社交关系图,标签表示喜欢观看视频的类型,例如’anime and wrestling‘。
和5种算法进行对比:
deepwalk的实验参数设置为:$\gamma=80, w=10, d=128$。
BlogCatalog
算法在BlogCatalog数据集上的表现如下:
从图中可以看出,DeepWalk在只有20%数据的情况下,要比很多算法在90%的数据下表现得更好。DeepWalk与SpectralClustering性能很接近,DeepWalk在训练数据稀疏的情况下性能要高于SpectralClustering。
由此可以得出DeepWalk的优势是在数据量很少的情况下也能由很高的准确度,接下来实验主要对比训练数据在10%以下的表现。
Flickr
DeepWalk在训练数据在1%-10%的Flickr上表现比baseline的算法有3%的提升,且在只有3%的训练数据的情况下,比其他算法在10%的表现都要好。
YouTube
Parameter Sensitivity
Effect of Dimensionality
通过图(a1)和图(a3)对比可以得到,最佳的维度$d$和训练数据的规模有关。
图(a2)和图(a4)是对参数维度$d$和random walk的次数$\gamma$的研究,通过实验可以得到在$\gamma$一定的情况下不同的维度的表现相对稳定,同时又两个有趣的发现:
- BlogCatalog和Flickr都是在$\gamma = 30$时有最好的表现。
- $\gamma$在两个图的相对差异表现一致。
总的来说性能依赖于$\gamma$,维度$d$的选择依赖于训练数据的数量$T_R$。
Effect of sampling frequency
通过上图对比可以看出,$\gamma$在最开始增长对性能的影响很大,当$\gamma > 10$是就变得缓慢了,这个结果也说明了只需要很少次的random walk就可以学习到节点的隐藏表示。
- Post link: https://sanzo.top/Paper/deepwalk/
- Copyright Notice: All articles in this blog are licensed under unless otherwise stated.