图表示学习起源: 从Word2vec到DeepWalk

本文发表在知乎专栏<435算法研究所>,介绍的是2014年的一篇文章《DeepWalk: Online Learning of Social Representations》，附个链接https://arxiv.org/pdf/1403.6652.pdf，这是NLP中的表示学习算法第一次被引入到图结构当中。如标题，本文先来介绍Word2vec的基本知识，再来介绍下如何利用Word2vec来表示图结构。

img

前文提到过，Skip-Gram丢掉了句子中的词序信息，以及词与词之间的距离信息，这也适合网络表示学习，丢掉随机游走的顺序信息能够灵活地捕获节点之间的邻近关系。另外，如果两个节点具有相同的邻域，Skip-Gram学习出来的表示向量接近或者相似，有利于在下游任务上取得好的效果。

不管是在NLP中，还是在graph中，学习到的向量只是中间结果，用于作为下游任务的输入。例如在图中对节点做多标签分类任务时，第一步先通过DeepWalk进行无监督训练，得到所有节点的特征向量；第二步，通过一些分类器对节点进行分类。不同于传统的方法，DeepWalk将标签和表示空间分割开来，标签和表示向量相互独立，学习到的特征向量可以应用于各种不同的任务。而且试验证明，特征向量和最简单的分类算法相结合，比如逻辑回归，也能获得好的效果。

算法中有一个参数t，是随机游走的步长，即需要限定随机游走的长度，不要过长，有几个好处，1）可以捕获网络中局部区域的结构信息；2）易于实现并行化，多个线程，进程，甚至服务器，可以同时随机游走网络的不同部分，实现分布式计算，这个后边还会再提一下；3）能够适应网络的变化，网络局部发生变化时，可以只对局部网络进行学习和训练，而不需要对整个网络重新学习。

算法变种

1）streaming

训练前看不到整个网络，实时的将游走的序列丢到网络中进行训练。这对于构建hierarchical Softmax Tree比较麻烦，如果能够事先知道有多少个节点，以及节点的出现频率，就可以事先构建一个Huffman二叉树。否则的话，每次新遇到一个节点，将节点加到二叉树的叶子节点中。

2）Non-Random Walks

用户在访问某些网站的时候，可能会受到网站的引导而进行一些操作，因此访问过程可能并不随机，不过这并没有关系。对这些非随机的访问过程的训练，使得算法可以学习到网络的结构信息，以及访问路径的频次情况。

良好的可伸缩性

DeepWalk具有良好的可伸缩性，可以多台机器同时训练网络的不同部分。而且节点的出现频次符合指数分布，大部分低频节点都分布在长尾。多台机机器同时训练也不太会发生冲突，文中提出可以采用异步的随机梯度下降（ASGD）。下图中左边表示训练时间和机器数量的关系，服务器增加，训练时间也线性减少；右边表示服务器数量和效果的关系，随着服务器增加，训练出来的模型效果几乎没什么变化。