3/12 LINE阅读记录
标签（空格分隔）： 假装科研 读论文
二阶LINE原理
对每条有向边
(
i
,
j
)
(i,j)
(i,j)，首先定义由顶点
v
i
v_i
vi生成上下文
v
j
v_j
vj的概率：
p
2
(
v
j
∣
v
i
)
=
e
x
p
(
u
j
′
∗
u
i
)
∑
k
=
1
∣
V
∣
e
x
p
(
u
k
′
∗
u
i
)
p_2(v_j|v_i)={exp(u'_j*u_i)\over\sum_{k=1}^{|V|}exp(u_k'*u_i)}
p2(vj∣vi)=∑k=1∣V∣exp(uk′∗ui)exp(uj′∗ui)
∣
V
∣
|V|
∣V∣是上下文结点的个数。
等式定义了上下文结点的条件分布
p
2
(
⋅
∣
v
i
)
p_2(·|v_i)
p2(⋅∣vi)，二阶相似性假设在上下文中具有相似分布的结点相似。为了保持二阶相似性，应该使
p
2
(
⋅
∣
v
i
)
p_2(·|v_i)
p2(⋅∣vi)接近经验分布
p
2
′
(
⋅
∣
v
j
)
p_2'(·|v_j)
p2′(⋅∣vj)，即最小化以下目标：
O
2
=
∑
i
∈
V
λ
i
d
(
p
2
′
(
⋅
∣
v
i
)
,
p
2
(
⋅
∣
v
i
)
)
O_2=\sum_{i\in{V}}\lambda_id(p_2'(·|v_i),p_2(·|v_i))
O2=i∈V∑λid(p2′(⋅∣vi),p2(⋅∣vi))
这个公式的原理可以看看：对向量内积做softmax,
λ
i
\lambda_i
λi表示结点
i
i
i在图中的重要性，可以通过结点的度或专门的算法
P
a
g
e
R
a
n
k
PageRank
PageRank来度量。本文采用
λ i = d i = ∑ k ∈ N ( i ) w i k \lambda_i=d_i=\sum_{k\in{N(i)}}w_{ik} λi=di=k∈N(i)∑wik
N
(
i
)
N(i)
N(i)表示顶点
v
i
v_i
vi的出度结点。经验分布
p
2
′
(
v
j
∣
v
i
)
=
w
i
j
d
i
p_2'(v_j|v_i)={w_{ij}\over{d_i}}
p2′(vj∣vi)=diwij
采用KL-散度来度量两个分布的距离：
O
2
=
−
∑
(
i
,
j
)
∈
E
w
i
j
l
o
g
p
2
(
v
j
∣
v
i
)
O_2=-\sum_{(i,j)\in E}w_{ij}logp_2(v_j|v_i)
O2=−(i,j)∈E∑wijlogp2(vj∣vi)
KL-散度知识补充
D
K
L
(
p
∣
∣
q
)
=
∑
i
=
1
N
p
(
x
i
)
l
o
g
1
q
(
x
i
)
−
p
(
x
i
)
l
o
g
1
p
(
x
i
)
D_{KL}(p||q)=\sum_{i=1}^Np(x_i)log{1\over q(x_i)}-p(x_i)log{1\over p(x_i)}
DKL(p∣∣q)=i=1∑Np(xi)logq(xi)1−p(xi)logp(xi)1
在本文中，由于经验分布的信息熵
p
(
x
i
)
l
o
g
1
p
(
x
i
)
p(x_i)log{1\over p(x_i)}
p(xi)logp(xi)1是常数，对模型的优化不起作用，故可以消去。
本质上来说，本文计算分布的距离时，采用了交叉熵的方法。
至此，二阶LINE的目标函数已经确定。
最终目标是得到结点的向量表示，使得目标函数最小。
本文采用异步随机梯度下降的方法优化目标函数。
接下来是对计算过程的优化：
模型优化
计算条件分布
p
2
′
(
⋅
∣
v
i
)
p_2'(·|v_i)
p2′(⋅∣vi)需要遍历结点集，计算量过大；采用文献13中提及的负采样方法：“根据某些噪声分布对多个负边进行采样”
负采样原理待补充。。。
采用异步随机梯度下降方法对等式7进行优化？？？7为毛还要优化？？
在每步中，选取一部分边然后更新模型参数。如果边
(
i
,
j
)
(i,j)
(i,j)已被采样，结点
i
i
i的嵌入向量
u
i
u_i
ui会被按照如下方式计算：
∂
O
2
∂
u
i
=
w
i
j
∂
l
o
g
p
2
(
v
j
∣
v
i
)
∂
u
i
{\partial O_2\over \partial u_i}=w_{ij}{\partial logp_2(v_j|v_i)\over \partial u_i}
∂ui∂O2=wij∂ui∂logp2(vj∣vi)
注意梯度会与边的权重相乘，这就会导致如果边权的方差过大，则无法选择合适的学习率。为解决这个问题，可以将边的选择概率通过边的权值计算，引入“别名表”的方法对边进行采样。
别名表
令
W
=
(
w
1
,
w
2
,
.
.
.
,
w
∣
E
∣
)
W={(w_1,w_2,...,w_{|E|})}
W=(w1,w2,...,w∣E∣)，表示边的权重列表，首先计算边的权值之和
w
s
u
m
=
∑
i
=
1
∣
E
∣
w
i
w_{sum}=\sum_{i=1}^{|E|}w_i
wsum=∑i=1∣E∣wi，在区间
[
0
,
w
s
u
m
]
[0,w_{sum}]
[0,wsum]中取随机数，观察其落在哪个部分和区间
[
∑
j
=
0
i
−
1
w
j
,
∑
j
=
0
i
w
j
)
[\sum_{j=0}^{i-1}w_j, \sum_{j=0}^i w_j)
[∑j=0i−1wj,∑j=0iwj)，此时选取一条边的时间复杂度为
O
(
∣
E
∣
)
O(|E|)
O(∣E∣)，利用文献9中提到的“别名表”的方法，可以使重复选取边操作的时间复杂度降低为
O
(
1
)
O(1)
O(1)。
原理
讨论
讨论几个LINE实际的问题
-
低度顶点
某些邻居很少的顶点，很难将它们表示出来，特别是在二阶LINE这种尤其依赖顶点“上下文”的算法中。一个可行的方法是将结点邻居的邻居考虑在内，定义结点 i i i和其二阶邻居结点 j j j的权重为 w i j = ∑ k ∈ N i w i k w k j d k w_{ij}=\sum_{k\in {N_i}}w_{ik}{w_{kj}\over{d_k}} wij=∑k∈Niwikdkwkj
d i d_i di的计算公式在这里 -
新结点
如果新增结点与原图中结点相连，则可以利用 O 1 / O 2 O_1/O_2 O1/O2对新结点进行表示，若新结点与原图不相连，则无法表示。
未完待续。。。