原文：DeepWalk: Online Learning of Social Representations
基本目标：
-从网络中提取特征
-具体来说，输入图G=(V,E)， V是节点集，E是边集，输出G的特征矩阵X ，d是特征的维度.
想法来源：在NLP中，对于一个句子，有CBOW(通过周边词预测一个词)和Skip-Gram(通过一个词来预测周边词)，来训练词向量。训练出来的词向量，相似的词对应的词向量的相似度会比较高。
graph1
在网络结构中，可以通过randow walk构造一个序列，看作上述的sentence进行训练。
Random Work：
从节点vi出发(vi为root)构造一个random walk序列，记为 Wvi，其中包含一系列随机变量Wvi1,Wvi2,...,Wvik.
gragh2
random walk有两个非常好的性质：
•并行性。可以同时由多个不同的random walkers(多线程、多进程、多machine)对同一个图G的不同部分同时进行探索。
•对于图结构的微小改变，不需要再进行全局重新计算，对已经学习好的模型在原图的改变区域用新的random walkers进行迭代更新即可。
Connection：Power laws
graph3
图a是YouTube的社交节点分布，图b是Wiki的文本分布，可以看到它们具有类似的分布形式，都表现出了长尾效应(一部分非常集中，剩下的部分的形状像一条尾巴)。由此说明，将用在NLP中的方法用到网络分析中是具有合理性的。
Language Modeling
通常语言模型的目标为最大下面的likelihood(即用前n-1个词作为条件，使第n个词的概率最大)，w表示word。
对应到random walk中，likelihood如下(用前i-1个节点位置作为条件，使第i个节点位置的概率最大)，v表示节点。
我们的目标是学习图G的presentation，因此引入mapping function如下，把节点映射成特征，通常φ是一个|V|*d的矩阵，|V|表示节点个数，d表示特征的维度。
至此，目标likelihood就变成了如下形式。
然而，随着work length的增大，这个问题是intractable的。
于是考虑一些优化：
•用一个节点去预测其他节点。
•其他节点由这个节点的左右节点构成。
•忽略其他节点的次序
(其实就是对应前面提到的NLP中的skip-gram)
于是，优化目标变成了下面的形式。
DeepWalk算法
DeepWalk算法由两个主要的模块：
•random walk generator
•update procedure
random walk generator首先选取一个节点作为root，然后进行random walk直到达到最大length(t)。作者在实现这个算法时，确定了一个参数r，在每个root，开始r次不同的random walk。
对算法3-9的解释：
(3,9)：循环r次，因为每个节点作为root要出发r次random walk。
4：对节点的次序进行随机化，提高运行效率。
5-8：对每个节点vi，RandomWalk(G,vi,t)表示对于图G，以vi为root，t为最大length进行random walk，返回walk sequence。 SkipGram(φ,Wvi,w)中，第一个参数为特征矩阵(算法的result，在每次迭代中不断update)，第二个参数为walk sequence，第三个参数为window大小。
在SkipGram中，前面提到不考虑context的次序，于是有
具体来看SkipGram的代码：
(1,6),(2,5)：从walk sequence 中选取一个vj，此时确定了用φ(vj)来预测context(window大小为w，context即为[j-w:j+w]并除去j本身，在作者的代码中，并没有除去j本身，可能是因为用j来预测自身并没有什么影响)。对于vj，φ(vj)是它的feature vector，如下图所示，在总体feature matrixφ中找到自己对应的一行即可。
graph3
3：目标是最大化likelihood Pr(uk|φ(vj))，也就是最小化-logPr(uk|φ(vj)) (加log是为了方便计算，加-是为了让最大变最小，然后做梯度下降。其实不加也无所谓，那就做梯度上升就好了)。
4：确定学习率α，做梯度下降。
Hierarchical Softmax
在4.1最后有这样一段话，
如果知道Pr(uk|φ(vj))具体是多少，那么就不需要进行下面的步骤。
大多数情况下，我们是不知道的，那么Pr(uk|φ(vj))的值就是难以计算的(partition function is intractable，我每次在learning中遇到partition function都是intractable的=.= ，在概率图的inference中可以用Belief Propagation进行approximate，然后再做归一化，倒不会有这个问题 )。于是考虑用Hierarchical Softmax对Pr(uk|φ(vj))进行分解。
构建一个二叉树(使用关于节点频率的Huffman树可以有效提高效率)，二叉树叶子节点为uk(有自己的feature vectorφ(uk))，非叶子节点为临时节点，也有同样形式的feature vector(需要learning)。
graph4
上图中，uk对应的一个path(根节点到它自身)为b0,b1,b2,uk。
则Pr(uk|φ(vj))可以分解为path上各节点的概率乘积。
其中，
注意，乘积中是没有包括root的。对应到我画的那个图，也就是
而Pr(bl|φ(vj))可以看做是它的parent节点做了一次二分类(往左或往右)，于是有
其中
是bl的parent节点的feature vector。其实就是一个sigmoid函数做二分类，和logistics regression中的是一样的。
参数
通过随机梯度下降来learning，即前面algorithm2中的Line4。
网友评论