DeepWalk: Online Learning of Social Representations

14-KDD-DeepWalk

作者首次将深度学习（无监督特征学习）引入到网络分析中，该技术已经在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。

image-20210629122653559

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}$，因此目标变为：

image-20210629122306128

随着walk length的增加，计算这个目标函数将十分困难，目前在language modeling提出了新的解决方法，将预测任务颠倒过来：

  • 不再用上下文预测缺失的单词，而是通过给定单词预测上下文。
  • 上下文包含给定单词左右的单词。
  • 不考虑单词的顺序，模型最大化上下文中单词出现的概率。

此时优化问题变为：

image-20210629122255772

Algorithm: DeepWalk

DeepWalk算法包含两部分：

  • random walk生成器
  • 更新程序

image-20210629121717503

在每次对所有点进行randowm walk之前，生成一个随机遍历顶点的顺序（line 4），这样可以加快算法收敛的速率。

line 7是按照公示2对representation进行更新。

SkipGram

image-20210629122148677

对于random walk中的每个节点，目标是最大化在窗口$w$中元素的出现的概率，

$\alpha$初始值设置为2.5%，然后线性的减小。

image-20210629130626818

Hierarchical Softmax

使用logistic regression建模，将产生大量等于 $|V|$的标签，是计算变得复杂。

image-20210629133211810

如果将顶点放到二叉搜索树的叶子节点，那么预测问题将变为最大化特定路径的概率，节点$u_k$可以表示为$b_0, b_1,\cdots,b_{\lceil log|V| \rceil}$即：

image-20210629133757732

使用Haffman编码可以优化访问节点的时间。

Parallelizability

random walk中的节点的分布遵循power-law，这导致$\Phi$的更新不会很频繁，因此可以使用异步版本的SGD（ASGD），通过多个worker来加速收敛。

image-20210629134802455

通过图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

共使用三种数据集：

image-20210629140621134

  • BlogCatalog是博客作者的社交关系图，标签表示是作者提供的文章的topic。
  • Flicker是照片分享网站中用户之间的联系，标签表示用户的interest group，例如’black and white’。
  • Youtube视频分享网站的社交关系图，标签表示喜欢观看视频的类型，例如’anime and wrestling‘。

和5种算法进行对比：

image-20210629160520949

deepwalk的实验参数设置为：$\gamma=80, w=10, d=128$。

BlogCatalog

算法在BlogCatalog数据集上的表现如下：

image-20210629175539936

从图中可以看出，DeepWalk在只有20%数据的情况下，要比很多算法在90%的数据下表现得更好。DeepWalk与SpectralClustering性能很接近，DeepWalk在训练数据稀疏的情况下性能要高于SpectralClustering。

由此可以得出DeepWalk的优势是在数据量很少的情况下也能由很高的准确度，接下来实验主要对比训练数据在10%以下的表现。

Flickr

image-20210629175902368

DeepWalk在训练数据在1%-10%的Flickr上表现比baseline的算法有3%的提升，且在只有3%的训练数据的情况下，比其他算法在10%的表现都要好。

YouTube

image-20210629180422404

Parameter Sensitivity

Effect of Dimensionality

image-20210629181321416

通过图(a1)和图(a3)对比可以得到，最佳的维度$d$和训练数据的规模有关。

图(a2)和图(a4)是对参数维度$d$和random walk的次数$\gamma$的研究，通过实验可以得到在$\gamma$一定的情况下不同的维度的表现相对稳定，同时又两个有趣的发现：

  • BlogCatalog和Flickr都是在$\gamma = 30$时有最好的表现。
  • $\gamma$在两个图的相对差异表现一致。

总的来说性能依赖于$\gamma$，维度$d$的选择依赖于训练数据的数量$T_R$。

Effect of sampling frequency

image-20210629183629493

通过上图对比可以看出，$\gamma$在最开始增长对性能的影响很大，当$\gamma > 10$是就变得缓慢了，这个结果也说明了只需要很少次的random walk就可以学习到节点的隐藏表示。