【图嵌入】Graph Embedding 方法之 LINE 原理解读
LINE 出自论LINE: Large-scale Information Network Embedding，与 DeepWalk 相比，比较明显的区别在于：
- DeepWalk 使用的深度优先搜索策略，而 LINE 使用了广度优先搜索策略。
- DeepWalk 仅适用于无权图，而LINE模型适用于带权图与无权图。
下图展示了一个简单的图，图中的边既可以是有向的，也可以是无向的，并且边的粗细程度也代表了权重的大小：
一阶相似度
作者认为可以用一阶相似度描述图中成对顶点之间的局部相似度，连接两个节点的边权重越大，则一阶相似度越高。若两个节点之间不存在边，则认为一阶相似度为 0。例如图中的节点６、７在低维空间中应该是比较靠近的，因为连接二者的边具有很大的权重，而5、6之间则的一阶相似度则为0。
为了能够通过节点的低维向量表示一阶相似度，我们还需要定义一个优化目标。假设用
u
i
,
u
j
u_i, u_j
ui,uj 作为节点的低维向量表示，那么一阶相似度的计算就转换为学习一种函数映射
f
(
u
i
,
u
j
)
f(u_i,u_j)
f(ui,uj)，使得其映射结果可以表示边的权重。对于每一条无向边
(
i
,
j
)
(i, j)
(i,j)，定义顶点
v
i
,
v
j
v_i, v_j
vi,vj 的联合概率密度为：
p
1
(
v
i
,
v
j
)
=
1
1
+
e
x
p
(
−
u
i
T
⋅
u
j
)
p_1(v_i,v_j) = \frac{1}{1+exp(-u_i^T \cdot u_j)}
p1(vi,vj)=1+exp(−uiT⋅uj)1
如果两个向量相似，则内积的结果也相对比较大，将内积结果作为 sigmoid 函数的输入，最终得到两个节点的联合概率分布
p
1
(
v
i
,
v
j
)
p_1(v_i,v_j)
p1(vi,vj)。
在得到联合概率分布之后，还需要一个“参照物”来指导它的学习，论文中将两个节点之间边的权重占比视为经验分别，并将它作为学习目标：
p
^
1
(
i
,
j
)
=
w
i
j
W
W
=
∑
(
i
,
j
)
∈
E
w
i
j
\hat p_1(i,j) = \frac{w_{ij}}{W} \\ W = \sum_{(i,j) \in E} w_{ij}
p^1(i,j)=WwijW=(i,j)∈E∑wij
于是最终的优化目标是使得联合概率分布尽量接近经验分布，而K-L散度可以表示数据原始分布p和近似分布q之间的对数差值的期望，因此只要优化
p
1
(
v
i
,
v
j
)
p_1(v_i, v_j)
p1(vi,vj) 与
p
^
1
\hat p_1
p^1 的K-L散度(忽略常数项)，就能使二者的分布尽可能相似：
O
1
=
−
∑
(
i
,
j
)
∈
E
w
i
j
l
o
g
(
p
1
(
v
i
,
v
j
)
)
O_1 = -\sum_{(i,j)\in E}w_{ij}log\big(p_1(v_i, v_j)\big)
O1=−(i,j)∈E∑wijlog(p1(vi,vj))
二阶相似度
一阶相似度固然可以直接表示节点之间的相似性，但是在真实环境下的信息网络往往存在大量的信息缺失，而许一阶相似度为0的节点，他们本质上相似度也很高。
仔细观察节点5、6，发现他们具有非常相似的邻居节点(1，2，3，4)，这其实也表明5、6两个节点应该是相似的，作者使用二阶相似度来描述这样的关系，若两个节点不存在共同的邻居节点，则二阶相似度为0。这意味着，如果节点5的低维向量表示同时与节点1，2，3，4的低维向量表示相似，并且节点6的低维向量表示同时与节点1，2，3，4的低维向量表示相似，那么节点5与6的低维向量表示也就是相似的。
根据一阶相似度的理论，我们可以将两个节点的向量内积 用sigmoid函数转换为概率 来表示两个节点间边的权重。但是在二阶相似度的表示问题中，我们需要表示一个节点与周围多个context节点的相似度，那么就可以使用 softmax 函数将某个节点与周围节点向量内积的结果转换为概率。给定节点
v
i
v_i
vi 产生节点
v
j
v_j
vj 的概率为：
p
2
(
v
j
∣
v
i
)
=
e
x
p
(
u
j
′
T
⋅
u
i
)
∑
k
=
1
∣
V
∣
e
x
p
(
u
k
′
T
⋅
u
i
)
p_2(v_j|v_i) = \frac{exp(u_j^{'T}\cdot u_i)}{\sum_{k=1}^{|V|}exp(u_k^{'T}\cdot u_i)}
p2(vj∣vi)=∑k=1∣V∣exp(uk′T⋅ui)exp(uj′T⋅ui)
其中， u i , u j ′ u_i, u_j' ui,uj′ 为节点 i , j i, j i,j 低维向量表示，且 u j ′ u'_j uj′ 为节点 j 表示为上下文时的向量表示。 ∣ V ∣ |V| ∣V∣ 表示图中所有节点的个数。当节点 k , i k, i k,i 之间没有邻接关系时，二者向量的内积也就比较小，在理想情况下当两个节点没有边相连时， e x p ( u k ′ T ⋅ u i ) → 0 exp(u_k^{'T}\cdot u_i) \rightarrow 0 exp(uk′T⋅ui)→0，此时 p 2 ( v j ∣ v i ) p_2(v_j|v_i) p2(vj∣vi) 仅仅受到节点 i i i 周围邻居节点的影响。 不难发现，这个公式将节点 i i i 与邻居节点的相似度转换为条件概率。
再定义经验分布为：
p
^
2
(
v
j
∣
v
i
)
=
w
i
j
d
i
\hat p_2(v_j|v_i)=\frac{w_{ij}}{d_i}
p^2(vj∣vi)=diwij
其中，
w
i
j
w_{ij}
wij 是边
(
i
,
j
)
(i, j)
(i,j) 的权重，
d
i
=
∑
k
∈
N
(
i
)
w
i
k
d_i = \sum_{k\in N(i)} w_{ik}
di=∑k∈N(i)wik，
N
(
i
)
N(i)
N(i) 为节点之间与节点
i
i
i 相连的邻居节点集合。对于无权图而言，
d
i
d_i
di 是节点
v
i
v_i
vi 的出度。
现在的目标是让条件概率
p
2
(
v
j
∣
v
i
)
p_2(v_j|v_i)
p2(vj∣vi)尽可能的与经验分布
p
^
2
(
v
j
∣
v
i
)
\hat p_2(v_j|v_i)
p^2(vj∣vi)相似：
O
2
=
−
∑
i
∈
V
λ
i
d
(
p
^
2
(
⋅
∣
v
i
)
,
p
2
(
⋅
∣
v
i
)
)
O_2 = -\sum_{i\in V}\lambda_i d\big(\hat p_2(\cdot|v_i),\; p_2(\cdot| v_i)\big)
O2=−i∈V∑λid(p^2(⋅∣vi),p2(⋅∣vi))
其中，
λ
i
\lambda_i
λi 是表示节点重要性的因子，可以通过预先计算节点的度数或者PageRank算法来得到。
d
(
⋅
,
⋅
)
d(\cdot,\cdot)
d(⋅,⋅) 用于度量两个分布之间的差距。
更具体的，假设
λ
i
=
d
i
\lambda_i = d_i
λi=di，使用忽略常数项的 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}log\big(p_2(v_j| v_i)\big)
O2=−(i,j)∈E∑wijlog(p2(vj∣vi))
对比一阶和二阶相度的概率函数，我们可以发现其实两者是非常相似的，只不过是二阶相似性每个节点有两个embedding，一个作为中心点的embeding和一个作为context时候的embeding。最终二阶使用的是作为中心点的embeding。实际使用的时候，对一阶近邻和二阶近邻分别训练，然后将两个向量拼接起来作为节点的向量表示。
优化技巧
负采样：
计算二阶相似度时，softmax 函数的分母计算需要遍历所有顶点，计算量太大了，论文采用了与 word2vec 论文类似的负采样优化的技巧，对边进行抽样生成负样本，每条边被抽中的概率为边的权重。于是，将每一条边
(
i
,
j
)
(i, j)
(i,j)对应的目标函数变为：
l
o
g
σ
(
u
j
′
T
⋅
u
i
)
+
∑
i
=
1
K
E
v
n
∼
P
n
(
v
)
[
l
o
g
σ
(
−
u
n
′
T
⋅
u
i
)
]
log \ \sigma(u_j^{'T} \cdot u_i) + \sum_{i=1}^K E_{v_n \sim P_n(v)}[log \ \sigma(-u_n^{'T}\cdot u_i)]
log σ(uj′T⋅ui)+i=1∑KEvn∼Pn(v)[log σ(−un′T⋅ui)]
其中， σ \sigma σ 为sigmoid函数，K 为负样本的个数。负采样的好处在于：梯度下降的过程中只需要更新节点 i , j i, j i,j 以及 K 个负采样的节点的向量即可。
以下是个人对公式的理解，不一定准确，如果有错还请指正：
感觉论文中的公式似乎表达的有点别扭，个人认为用下面的公式比较好理解：
O 2 = l o g σ ( u j ′ T ⋅ u i ) + ∑ k = 1 K E v k ∼ P n ( v ) [ l o g σ ( − u k ′ T ⋅ u i ) ] O_2 = log \ \sigma(u_j^{'T} \cdot u_i) + \sum_{k=1}^K E_{v_k \sim P_n(v)}[log \ \sigma(-u_k^{'T}\cdot u_i)] O2=log σ(uj′T⋅ui)+k=1∑KEvk∼Pn(v)[log σ(−uk′T⋅ui)]
其中 E v k ∼ P n ( v ) E_{v_k \sim P_n(v)} Evk∼Pn(v) 表示取出 v k v_k vk 的期望值，而 P n ( v ) P_n(v) Pn(v) 表示采样时用的概率分布，可以是：
P n ( v ) = ( d v ) 3 / 4 ∑ j = 1 ∣ V ∣ ( d j ) 3 / 4 P_n(v) = \frac{(d_v)^{3/4}}{\sum_{j=1}^{|V|} (d_j)^{3/4}} Pn(v)=∑j=1∣V∣(dj)3/4(dv)3/4
这个取 3/4 次幂的运算会产生一个效果，就是稍微增加低频节点的采样概率，降低高节点的采样概率。可根据下图（google 的搜索栏中输入 “plot y = x^(3/4) and y = x” 可以快速画图）的对比看出来：
引入负采样后，最终得到的目标函数为：
O
2
=
−
∑
(
i
,
j
)
∈
E
w
i
j
(
l
o
g
σ
(
u
j
′
T
⋅
u
i
)
+
∑
i
=
1
K
E
v
n
∼
P
n
(
v
)
[
l
o
g
σ
(
−
u
n
′
T
⋅
u
i
)
]
)
O_2 = -\sum_{(i,j)\in E}w_{ij}(log \ \sigma(u_j^{'T} \cdot u_i) + \sum_{i=1}^K E_{v_n \sim P_n(v)}[log \ \sigma(-u_n^{'T}\cdot u_i)])
O2=−(i,j)∈E∑wij(log σ(uj′T⋅ui)+i=1∑KEvn∼Pn(v)[log σ(−un′T⋅ui)])
边采样：
从上面的公式可以看到，每个样本都有一个权重 w i j w_{ij} wij，有的样本w很高，有的样本w很低。在进行反向传播的时候，如果学习率过高，会导致w很大的样本梯度爆炸，如果学习率设置很小，会导致w很低的样本训练缓慢。为了解决这个问题，文中提出了边缘采样(Edge Sampling)的方法，将所有样本的系数都置为1，对图中的边重复采样来构造多个相同的正样本，采样率与权重 w i j w_{ij} wij 成正比。
扩充邻居：
对于一些顶点由于其邻接点非常少会导致embedding向量的学习不充分，论文提到可以利用邻居的邻居构造样本进行学习。为了解决这个问题，论文中提出了一个扩展邻居的办法，添加二阶邻居。所谓二阶邻居，就是从该节点到邻居节点之间存在两跳。
节点{1,2,3,4}就是节点7的二阶邻居，节点{8,9,10}就是节点6的二阶邻居。二阶邻居的权重计算方法如下：
w
i
j
=
∑
k
∈
N
(
i
)
w
i
k
w
k
j
d
k
w_{ij} = \sum_{k\in N(i)} w_{ik} \frac{w_{kj}}{d_k}
wij=k∈N(i)∑wikdkwkj
参考文章：