搬瓦工中文网
DeepWalk模型可以理解为一种矩阵分解M=WHTM=WH^T，其中矩阵的每一个元素MijM_{ij}其实是节点ii以固定步长随机游走到jj上的概率。下边将从数学角度解释。其中WW和HH为训练中的邻居节点和中心节点对应的节点向量矩阵。
准备
通过了解Word2Vec我们可以知道，词对（w1,w2w_1, w_2）之间关系的远近可以通过其对应向量的点乘来表示，将其转换为词对共现的概率可以表示为：
P(w1,w2))=σ(w1⃗,w2⃗)=11+ew1⃗⋅w2⃗P\left(w_1, w_2)\right)=\sigma\left(\vec{w_1},\vec{w_2}\right)=\frac{1}{1+e^{\vec{w_1}\cdot\vec{w_2}}}
由于DeepWalk借鉴了这个思路，所以DeepWalk中点对（v,cv,c）的关系也可以这么表示：
P(v,c))=σ(v⃗,c⃗)=11+ev⃗⋅c⃗P\left(v, c)\right)=\sigma\left(\vec{v},\vec{c}\right)=\frac{1}{1+e^{\vec{v}\cdot\vec{c}}}
优化的目标是：
max∏vi,ciP(vi,ci)max \prod_{v_i,c_i} P\left(v_i,c_i\right)
我们假设随机游走路径已经被进行了处理，提取出了其中所有相邻的节点对，我们将所有的节点对构成一个集合DD。进而，我们同样可以得到节点vv和节点cc的集合VV和VcV_c（在实际操作中，我们往往令V=VcV=V_c）。对于特定的节点对（v,cv,c）而言，我们记♯(v,c)\sharp\left(v,c\right)为节点对（v,cv, c）的在DD中出现的次数，记♯(v),♯(c)\sharp\left(v\right),\sharp\left(c\right)为节点vv和cc在DD中出现的次数。
负采样
根据负采样的原理，我们可以写出基于负采样的目标函数，它除了要保证正例上的概率最大，也要保证负例上的概率最小：
l=∑v∑c♯(v,c)logσ(v⃗⋅c⃗)+k⋅♯(v)⋅♯(c)∣D∣logσ(−v⃗⋅c⃗)l=\sum_v\sum_c\sharp\left(v,c\right)log\sigma\left(\vec{v}\cdot\vec{c}\right)+k\cdot\sharp\left(v\right)\cdot\frac{\sharp{\left(c\right)}}{|D|}log\sigma\left(-\vec{v}\cdot\vec{c}\right)
设x=v⃗⋅c⃗x=\vec{v}\cdot\vec{c}
，要想使概率最大，只需对将l对x求导，得到导数为0时x的值即可。
v⃗⋅c⃗=x=log♯(v,c)⋅∣D∣♯(v)⋅♯(v)−logk\vec{v}\cdot\vec{c}=x=log\frac{\sharp\left(v,c\right)\cdot|D|}{\sharp{\left(v\right)}\cdot\sharp{\left(v\right)}}-logk
其中k为负采样数量。
softmax
softmax也有类似的结论，推导会复杂点，直接给出结果：
v⃗⋅c⃗=x=log♯(v,c)♯(v)+bv\vec{v}\cdot\vec{c}=x=log\frac{\sharp\left(v,c\right)}{\sharp{\left(v\right)}}+b_v
其中bvb_v为任意常数。
观察v⃗⋅c⃗=x\vec{v}\cdot\vec{c}=x
，我们发现，如果将VV和VcV_c对应的所有节点的向量分别写成一个列矩阵WW和HH，则vi⃗⋅cj⃗=(WHT)ij\vec{v_i}\cdot\vec{c_j}=\left(WH^T\right)_ {ij}。我们设矩阵M=WHTM=WH^T，则有Mij=vi⃗⋅cj⃗M_{ij}=\vec{v_i}\cdot\vec{c_j}
。而现在我们只需要知道♯(v),♯(c),♯(v,c),∣D∣\sharp\left(v\right), \sharp\left(c\right),\sharp\left(v,c\right),|D|，直接假设W=HW=H,我们便可以根据M=W2M=W^2来得到WW，也即所求的节点向量。接下来，我们只需要讨论上述几个值该怎么求即可。
对DeepWalk的讨论
假设DeepWalk作用的图为无向的连通图，窗口为tt。我们上述的DD可以通过以下步骤得到：
对于有向图来说，则把上式的最内层for循环中add(RWi,RWj)intoDadd (RW_i, RW_j) into D去除即可。
在无向图中，每一次节点ii的出现都会在DD中被纪录2t2t次，而在有向图中，则被纪录tt次。根据以上的定义，我们很容易得到♯(vi)∣D∣\frac{\sharp\left(v_i\right)}{|D|}就是viv_i在DD中的频率，这其实也是viv_i的PageRank值（确切的说，是初始值）。vjv_j与viv_i作为节点对出现在DD中的概率是♯(vi,vj)♯(vi)\frac{\sharp\left(v_i,v_j\right)}{\sharp\left(v_i\right)}，则vjv_j出现在viv_i的左右tt个邻居内的期望频次是♯(vi,vj)♯(vi)/2t\frac{\sharp\left(v_i,v_j\right)}{\sharp\left(v_i\right)/2t}。引入该图PageRank的转移矩阵Aij=1diA_{ij}=\frac{1}{d_i}(当i,j相连,否则等于0），其中did_i是i的度。设eie_i是一个行向量，只在i维是1，其他维是0。则eiAe_iA同样表示一个行向量，其中第j维表示从节点i到节点j的概率；eiAite_iA^t_i则表示节点i经过t步随机游走到达节点j的概率。对于DeepWalk来说，在窗口tt范围内，i节点到达j节点的情况有t种可能：经过1步到达，经过2步到达，…，经过t步到达。那么[ei(A+A2+…+At)]j\left[e_i\left(A+A^2+…+A^t\right)\right]_ j即表示vjv_j出现在viv_i的左或右tt个邻居内的期望频次。再乘以2，,便等于♯(vi,vj)♯(vi)/2t\frac{\sharp\left(v_i,v_j\right)}{\sharp\left(v_i\right)/2t}：
♯(vi,vj)♯(vi)/2t=2[ei(A+A2+…+At)]j\frac{\sharp\left(v_i,v_j\right)}{\sharp\left(v_i\right)/2t}=2\left[e_i\left(A+A^2+…+A^t\right)\right]_ j ⟶\longrightarrow ♯(vi,vj)♯(vi)=[ei(A+A2+…+At)]jt\frac{\sharp\left(v_i,v_j\right)}{\sharp\left(v_i\right)}=\frac{\left[e_i\left(A+A^2+…+A^t\right)\right]_ j}{t}。
对于有向图，同样可以得到上述式子。
至此，利用之前softmax所得结果，便可以求出M。
