模块 4
1 研究背景
随着互联网的发展, 社交网络逐渐复杂化, 多元化. 在一个社交网络中, 充斥着不同类型的用户, 用户间产生各式各样的互动联系, 形成大小不一的社群. 为了对社交网络进行研究分析, 需要将网络中的节点 (用户) 进行分类.
2 解决的问题
利用节点在图中的局部结构信息, 对社交网络中的结点进行分类. 由于这部分信息常常是隐藏的, 不体现在初始输入 $X$ 当中, 故需要一些算法对结点的局部结构进行挖掘. DeepWalk 最重要解决的是网络中节点的集体分类 (Collective Classification) 或关联分类(Relational Classification), 但若能将节点用一个 "好的" 向量进行表示, 分类工作也会很容易进行. 故 DeepWalk 的核心任务是, 在连续向量空间中以低维度的稠密形式表征网络结点, 方便后续利用统计模型完成结点的分类.
如下图例子所示, 是将 (a) 中原本网络的各个节点映射表示为到 (b) 二维空间的二维坐标.
3 主要贡献
3.1 解决方法
DeepWalk 的核心算法包含随机游走序列生成器和节点向量更新两部分. 这两部分可以结合的关键点在于: 数据呈现幂律分布.
3.1.1 随机游走
在网络上施行随机游走算法: 从根节点 $v_i$ 出发, 随机访问一个邻居, 然后再访问邻居的邻居...... 每一步都访问前一步所在节点的邻居, 直到序列长度达到设定的最大值 $t$. 网络中任何节点均可作为根节点, 施行随机游走算法 $\gamma$ 次, 得到 $\gamma \cdot |V|$ 个随机游走序列. 随机游走伪代码如下所示:
3.1.2 节点向量更新
对于一个随机游走序列, 每一个节点都可作为中心节点, 根据设定的窗口大小 $\omega$, 选取序列里中心节点前后各 $\omega$, 共 $2\omega$ 个节点. 利用 SkipGram 算法 [26, 27] 按照如下优化方式进行优化:
- $$
- minimize \space -\log \Pr(u_k|\Phi(v_j))
- $$
即最大化在 $v_j$ 附近出现 $u_k$ 的概率. 其中,$u_k$ 是这 $2\omega$ 个节点中的每一个,$\Phi(v_j) \in \mathbb{R}^d$ 是将节点映射到它的嵌入表示的函数, 也即我们最终要得到的结果. SkipGram 伪代码如下所示:
利用 Hierarchical Softmax 二叉树[29, 30], 将所有节点作为二叉树的叶子节点, 就可以用从根节点到叶子节点的路径来表示每个节点. 即有下式:
- $$
- \Pr(u_k|\Phi(v_j))=\prod_{
- l=1
- }^{
- \lceil\log|V|\rceil
- }\Pr(b_l|\Phi(v_j))
- $$
可对 SkipGram 算法进行加速.
3.1.3 幂律分布
之所以 DeepWalk 可以由随机游走和 SkipGram 结合得到, 是因为作者观察到, 数据输入服从幂律分布, 曾用于自然语言模型的 SkipGram 算法可以很好地处理这一分布.
3.2 实验及其结论
作者选用了下图所示三个数据集: BlogCatalog, Flickr, YouTube. 采用的评价方式为 Macro-F1 和 Micro-F1.
3.2.1 准确性
作者在三个数据集上分别取不同数量的带标签节点进行训练, 并对剩余结点进行预测, 得出结论: 在多标签分类的任务上使用 DeepWalk 有两点好处 --
可以适用于大规模的图
仅需要少量有标记的样本就拥有很高的分类准确率
3.2.2 敏感性
作者固定窗口大小 $\omega$=10 和 随机游走序列长度 $t$=40, 改变嵌入维度 $d$, 每个节点作为根节点的次数 $\gamma$, 训练集比例 $T_R$. 得到以下结论:
存在最优的维度, 且最优维度的大小和 $T_R$ 的大小有关
$\gamma$ 的增大可以提升模型效果, 但当 $\gamma$ 大于 10 后提升逐渐减小, 当 $\gamma$ 大于 30 后无法提升效果.
3.2.3 并行化
作者增加并行任务的个数, 使用非同步的随机梯度下降 (ASGD) 方法更新向量, 可以线性地减少训练时间, 但不会降低准确性, 证明 DeepWalk 算法适用于大规模的学习.[36, 8]
4 存在的不足
4.1 带权边与度量相似度
DeepWalk 只适用于无权边, 只能忽略边的权重, 然而这在网络中是十分重要的. LINE[100]考虑了边的权重, 且明确地定义了一阶相似度和二阶相似度. 其中一阶相似度是两个顶点之间的自身相似(不考虑其他顶点), 二阶相似度是两个节点邻近网络结构之间的相似性, 即共享相似邻居的顶点倾向于彼此相似. 如下图的节点 6 和节点 7, 由于有边直接相连, 故有一阶相似性; 节点 5 和节点 6 没有边直接相连, 但它们有公共邻居 1, 2, 3, 4, 故有二阶相似性.
在 LINE 定义了一阶相似度和二阶相似度之后, GraRep[101]考虑了三阶, 四阶等更高阶的相似度.
此外, DeepWalk 是一种基于 DFS 的方法, 而 LINE 和 GrapRep 是一种基于 BFS 的方法.
4.2 空间结构相似性> 相邻性
前述方法都基于近邻相似的假设, 即认为只有相近的节点才比较相似. 而 struc2vec[102]认为两个不是近邻的节点也可能拥有很高的相似性, 所以只应考虑结点的空间结构相似性. 前述方法之所以有效是因为, 现实世界中相邻的节点往往有着比较相似的空间环境. 如下图所示的节点 u 和节点 v 并不相邻, 但他们拥有相似的空间环境, 最终得到的嵌入表示也应该类似.
4.3 归纳式学习
前述方法都是直推式学习, 即在一个确定的网络中去学习顶点的嵌入表示, 无法直接泛化到在训练过程没有出现过的顶点, 属于直推式 (transductive) 的学习.
GraphSAGE[103]则是一种能够利用顶点的属性信息, 高效产生未知顶点嵌入表示的一种归纳式 (inductive) 学习的框架. 其核心思想是通过一个节点的邻居节点, 学习到一个聚合函数, 然后对任意节点应用该聚合函数来得到该节点的嵌入表示.
参考文献
3.1.2 节点向量更新
[26] T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of Word representations in vector space. CoRR, abs/1301.3781, 2013.
[27] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems 26, pages 3111-3119. 2013.
[29] A. Mnih and G. E. Hinton. A scalable hierarchical distributed language model. Advances in neural information processing systems, 21:1081-1088, 2009
[30] F. Morin and Y. Bengio. Hierarchical probabilistic neural network language model. In Proceedings of the international workshop on artificial intelligence and statistics, pages 246-252, 2005.
3.2.3 并行化
[36] B. Recht, C. Re, S. Wright, and F. Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems 24, pages 693-701. 2011.
[8] J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, Q. Le, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, and A. Ng. Large scale distributed deep networks. In P. Bartlett, F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1232-1240. 2012.
4 存在的不足
- [100] Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]. International Conference on World Wide web(WWW 2015), 2015: 1067-1077.
- [101] Cao S, Lu W, Xu Q. Grarep: Learning graph representations with global structural information[C]. ACM International Conference on Information and Knowledge Management (CIKM 2015), 2015: 891-900.
- [102] Ribeiro L F, Saverese P H, Figueiredo D R. struc2vec: Learning node representations from structural identity[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(SIGKDD 2017), 2017: 385-394.
- [103] Hamilton W L, Ying Z, Leskovec J. Inductive Representation Learning on Large Graphs[C]. Neural Information Processing Systems (NIPS 2017), 2017: 1024-1034.
来源: https://www.cnblogs.com/ZhaoLX/p/DeepWalk4.html