[Graph Embedding] LINE

在上一篇文章中，我们介绍了Graph Embedding的经典方法DeepWalk。DeepWalk没有明确提供阐明保留哪些网络属性的目标函数，DeepWalk使用随机游走来扩展节点的领域，类似dfs（深度优先搜索）；而LINE使用的是bfs（广度优先搜索）的思想来扩展节点的领域。此外，DeepWalk只能用在无权图上，而LINE可以使用在各种网络上：无向图、有向图、无权图和有权图。

Introduction

LINE提出了一种新的对图中节点相似性的定义：

• first-order proximity

  一阶相似度描述的是图中存在边相连接的2个节点 ( u , v ) (u,v) (u,v)相似的程度，可以用边的权值 w u , v w_{u,v} wu,v​来定义2个节点的一阶相似度。如上图中，节点6和节点7的边是最粗的，表示他们的一阶相似度是最高的（文中规定一阶相似度 ≥ 0 \geq0 ≥0），所以他们通过Graph Embedding后的表示向量在该向量空间中应该最接近；节点5和节点6直接按不存在边，所以他们的一阶相似度为0。

• second-order proximity

  仅用一阶相似度并不能表示整个网络的结构信息，在一个真实世界的信息网络（real world information network）中，能够观察到的边只占一小部分，因为很多其他的边丢失了。比如上图中，节点5和节点6之间并没有边相连接，但是他们有很多公共的邻居节点，这表明节点5和节点6应该具有很高的相似度的。

  一个网络中的一对节点 ( u , v ) (u,v) (u,v)之间的二阶相似度是它们的邻域网络结构之间的相似性，通俗的讲就是2个节点拥有越多相同的邻居节点，则他们的二阶相似度越高。数学上定义 p u   =   ( w u , 1 , ⋅ ⋅ ⋅ , w u , ∣ V ∣ ) p_u \:= \:(w_{u,1},···,w_{u,|V|}) pu​=(wu,1​,⋅⋅⋅,wu,∣V∣​)为 u u u的一阶相似度，则 u u u和 v v v之间的二阶相似度定义为 p u p_u pu​和 p v p_v pv​的相似性。如果两个节点之间没有共同的邻居节点，则他们的二阶相似度为0。

LINE算法原理

1. LINE with First-order Proximity

一阶相似度值适用于无向图，不适用于有向图。对于任意无向边 ( i , j ) (i,j) (i,j)，我们定义节点 v i v_i vi​和 v j v_j vj​的联合概率为下式（1）
p 1 ( v i , v j ) = 1 1 + e x p ( − u i T ⃗ ⋅ u j ⃗ ) (1) p_1(v_i,v_j) = {{1 \over 1+exp(-\vec{{u_i}^T} \cdot \vec{u_j})}} \tag1 p1​(vi​,vj​)=1+exp(−ui​T ​⋅uj​ ​)1​(1)
上式的 u i ⃗ ∈ R d \vec{u_i} \in R^d ui​ ​∈Rd 是节点 v i v_i vi​在低维空间中的向量表示（这正是Graph Embedding所想要学习到的东西）。

同时定义经验分布 p 1 ^ = w i , j W \hat{p_1} = {w_{i,j}\over W} p1​^​=Wwi,j​​，其中 W = ∑ ( i , j ) ∈ E w i , j W = \displaystyle \sum_{(i,j)\in E}{w_{i,j}} W=(i,j)∈E∑​wi,j​

优化的目标是最小化KaTeX parse error: \tag works only in display equations

其中函数 d ( ⋅ , ⋅ ) d(·,·) d(⋅,⋅)是2个概率分布之间的距离，用KL散度代替 d ( ⋅ , ⋅ ) d(·,·) d(⋅,⋅)并移除一些常数项，得到我们最终的一阶相似度的优化目标：
O 1 = − ∑ ( i , j ) ∈ E w i , j   l o g   p 1 ( v i ,   v j ) (3) O_1 = -\displaystyle \sum_{(i,j)\in E}{w_{i,j}\ log\ p_1(v_i,\ v_j)} \tag3 O1​=−(i,j)∈E∑​wi,j​ log p1​(vi​, vj​)(3)

2. LINE with Second-order Proximity

二阶相似性都适用于无向图和有向图。我们定义两种类型的向量， u i ⃗ \vec{u_i} ui​ ​表示当 v i v_i vi​被当作节点时候的表示向量（这是最终想要求得的二阶相似性的向量表示）； u i ′ ⃗ \vec{{u_i}^{'}} ui​′ ​表示的是当 v i v_i vi​作为其他节点的上下文顶点时的表示向量。

对于任一有向边 ( 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 ′ T ⃗ ⋅ u i ⃗ ) ∑ k = 1 ∣ V ∣ e x p ( u k ′ T ⃗ ⋅ u i ⃗ ) (4) p_2(v_j｜v_i) = {{exp(\vec{{u_j^{'}}^T} \cdot \vec{u_i}) \over \displaystyle \sum^{|V|}_{k=1}exp(\vec{{u_k^{'}}^T} \cdot \vec{u_i})}} \tag4 p2​(vj​｜vi​)=k=1∑∣V∣​exp(uk′​T ​⋅ui​ ​)exp(uj′​T ​⋅ui​ ​)​(4)
其中 ∣ V ∣ |V| ∣V∣为上下文节点（邻居节点）的数量

如何理解式(3)： p 2 ( ⋅ ∣ v i ) p_2(·|v_i) p2​(⋅∣vi​)定义的是节点 v i v_i vi​关于它的上下文节点（邻居节点）的条件分概率分布。如果2个节点二阶相似性高，那么他们拥有更多的邻居节点，即他们关于上下文节点的条件概率分布会更加相似，最终学习到的向量表示就会更加接近。

同时定义经验分布 p 2 ^ ( v j   ∣   v i ) = w i , j d i \hat{p_2}(v_j\ |\ v_i) = {w_{i,j}\over d_i} p2​^​(vj​ ∣ vi​)=di​wi,j​​，其中 w i , j w_{i,j} wi,j​是边 ( i , j ) (i,j) (i,j)的权重， d i d_i di​是节点 v i v_i vi​的出度，在有权图中，$d_i=\displaystyle \sum_{k\in N(i)}{w_{i,k}} $

优化的目标是最小化KaTeX parse error: \tag works only in display equations

其中函数 d ( ⋅ , ⋅ ) d(·,·) d(⋅,⋅)是2个概率分布之间的距离， λ i \lambda_i λi​表示的是节点的重要度，可以通过节点的度或者PageRank算法来衡量。为了简便，我们令 λ i = d i \lambda_i = d_i λi​=di​，并且仍然用KL散度代替 d ( ⋅ , ⋅ ) d(·,·) d(⋅,⋅)和移除一些常数项，得到我们最终的二阶相似度的优化目标：
O 2 = − ∑ ( i , j ) ∈ E w i , j   l o g   p 2 ( v j ∣ v i ) (6) O_2 = -\displaystyle \sum_{(i,j)\in E} w_{i,j} \ log\ p_2(v_j|v_i) \tag6 O2​=−(i,j)∈E∑​wi,j​ log p2​(vj​∣vi​)(6)

3. Combining first-order and second-order proximities

如何将一阶相似度的优化目标与二阶相似度的优化目标合并呢？作者采用的是分别以一阶和二阶相似度为优化目标，学习出节点的表示向量，然后将每个节点的2种表示向量进行拼接。

如何将一阶相似度与二阶相似度相结合是作者留给读者接下来的任务（这是2015年的论文，这一任务相必已经有各种idea了，感兴趣的去查查）。

优化方法

Negative Sampling

由于在式（6）中，计算条件概率分布需要遍历图上所有的点，计算开销很大，所以作者采用了NLP（自然语言处理）中的负采样的方法，该方法根据每条边 ( i , j ) (i,j) (i,j)的一些噪声分布对多条负边进行采样。 更具体地说，它为每条边 ( 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 ⃗ ) ] (7) log\ \sigma(\vec{{u_j^{'}}^T} \cdot \vec{u_i}) +\displaystyle \sum^{K}_{i=1} E_{v_n}～P_n(v) [log\ \sigma(\vec{{-u_n^{'}}^T} \cdot \vec{u_i})] \tag7 log σ(uj′​T ​⋅ui​ ​)+i=1∑K​Evn​​～Pn​(v)[log σ(−un′​T ​⋅ui​ ​)](7)
其中 σ ( x ) = 1 / ( 1 + e x p ( − x ) ) \sigma(x) = 1/(1 + exp(-x)) σ(x)=1/(1+exp(−x))是一个sigmoid函数， P n ( v ) ∝ d v 3 / 4 P_n(v) \propto {d_v}^{3/4} Pn​(v)∝dv​3/4，其中的 d v d_v dv​为节点v的出度。对于式（7）采用异步随机梯度下降（asynchronous stochastic gradient algorithm）的方法进行参数的更新。

关于负采样，这里不多加赘述，想要了解的可以在原文4.2节中进行了解。

Edge Sampling

主要到目标函数式（3）和式（6）前都要乘边的一个权重系数 w i , j w_{i,j} wi,j​，因为边与边之间的 w i , j w_{i,j} wi,j​的差异很大，所以会出现梯度爆炸和梯度消失的情况，学习率很难进行选择。

第一种方法是将一条边拆解为多条边，比如将一条权重为 w w w的边拆解为 w w w条权重为1的边，这样所有的边都具有相同的权重。但是这样做会显著的增加存储图所需的内存大小，尤其是当边的权重很大的时候。

第二种方法就是从原始的边的集合中采样一定数量的边，采样的概率正比与边的权重，然后按照上面所说的第一种方法，对边进行拆解。采样所使用到的是alias table method，它仅需要 O ( 1 ) O(1) O(1)的时间复杂度进行采样。

其他问题

Low degree vertices

对于如何准确对度很小的节点做Embedding，尤其是在计算二阶相似性的时候，十分依赖于节点的上下文节点（邻居节点）。作者提出可以利用邻居的邻居节点构造样本进行学习。

New vertices

当有新的边加入时，如果知道了它和已经存在的节点之间的连接关系，则可以直接获得它的经验分布 p 1 ^ ( ⋅ , v i ) \hat{p_1}(·,v_i) p1​^​(⋅,vi​)和 p 2 ^ ( ⋅ ∣ v i ) \hat{p_2}(·|v_i) p2​^​(⋅∣vi​)，然后优化下面的两个目标函数之一
− ∑ j ∈ N ( i ) w j , i   l o g   p 1 ( v j ,   v i ) ,   o r − ∑ j ∈ N ( i ) w j , i   l o g   p 2 ( v j ∣ v i ) , (8) -\displaystyle \sum_{j\in N(i)}{w_{j,i}\ log\ p_1(v_j,\ v_i)}, \ or -\displaystyle \sum_{j\in N(i)} w_{j,i} \ log\ p_2(v_j|v_i), \tag8 −j∈N(i)∑​wj,i​ log p1​(vj​, vi​), or−j∈N(i)∑​wj,i​ log p2​(vj​∣vi​),(8)
如果节点与其他的节点都不相连的话，就需要使用到节点的特征信息，并且作者将这个问题作为接下来研究的方向。

 
论文原文：LINE: Large-scale Information Network Embedding