Abstract

本文的创新点在于现有的网络嵌入方法无法拓展到包含数百万节点的世界中。本文提出的方法适用于任意类型信息的网络：无向、有向、加权。该方法既能够保留本地网络结构同时保存全局网络结构。提出了一种边采样方法解决梯度下降法的局限性。本文作者称该方法能够在几个小时内学习具有数百万个顶点和舒适一条边的网络嵌入。

Introduction

现有方法通常在叫嚣的网络上表现较好，但是当涉及现实世界的信息网络时，网络的训练就更加具有挑战性，这一类网络通常包含数百万个节点和数十亿条边。现有绝大多数嵌入算法无法针对大规模网络嵌入进行缩放，例如：经典算法如MDS，IsoMap, 拉普拉斯分解通常时间复杂度是O(N^2)，对于数百万级的网络来说开销太高了。本文精心设计了一个目标函数能够有效训练百万级网络的低维嵌入，本文提出了一阶近似和二阶近似的概念，并在这两个概念的基础上，论证提出新式方法来解决大规模网络嵌入问题。本文的贡献有：1. 提出新颖网络嵌入模型“LINE”，适合于任意类型的信息网络并可拓展数百万个网络节点，具有精心设计的目标函数保留一阶和二阶相似度。2. 提出了边采样方法，解决了经典随机梯度下降法的局限性提高了Inference的有效性和效率。3. 在现实世界的信息网络上进行了广泛的实验。 实验结果证明了所提出的LINE模型的有效性和效率.

Problem Definition

定义1：信息网络的定义为G=(V,E)，其中V是点集每一个节点表示为一个数据实体，E为两个点之间的关系的集合，每一个边e \in E, e=(u,v)表示为w_{uv} > 0,如果是无向图，我们有(u,v)\equiv (v,u) 和w_{uv} \equiv w_{vu}, 如果是有向图G, 我们有(u,v) \neq (v,u) 和w_{uv} \neq w_{vu}.
在实践中，信息网络可以是有向的（引用网络），也可以是无向的（Facebook 中的社交网络），边的权重可以是0或1，也可以是任何实数值。在本研究中，我们仅考虑非负权重,此外，网络嵌入低维表示有诸多应用，要进行嵌入必须要保留网络的结构，直观的想法是保留网络的局部结构（一阶相似度）.
定义2：二阶相似度，网络中的一节相似度指的是两个顶点之间的局部相似度，对于点集合中的任何两个相连的边(u,v), 改边上的权重w_{uv}为u和v之间的一节相似度，如果u和v之间没有联系，则他们之间的一阶相似度为0.
但是在现有的世界中，仅仅使用一阶紧邻度不足以保留整个网络结构，因而需要采取替代性方法，直觉是，共享相似邻居的节点往往彼此相似；例如在社交网络中，共享相似朋友的人往往具有相似的兴趣并因此成为朋友。在单词共现网络中，与同一组共现的单词往往具有相似的含义。因而定义二阶相似度，保留了一阶相似度的网络结构。
定义三：二阶相似度，网络中二阶相似度指的是一对顶点(u,v)它们邻域网络结构之间的相似性。令p_u=(w_{u,1},....,w_{u, |V|})为u和其他所有节点之间的一阶相似度，则二阶相似度则为p_u和p_v之间的相似度，如果u和v之间没有公共的节点，则u和v之间的二阶相似度为0
定义四：给定大型网络G=(V,E)，大规模网络Embedding旨在表示每一个顶点v(v \in V) 映射到一个低维表示R^d.例如学习一个函数f_G:V \rightarrow R^d，其中d \ll |V|.在R^d中保留了顶点之间的一阶近似度和二阶近似度。

LINE:LARGE-SCALE INFORMATION

LINE with First-order Proximity

为了度量一阶近似度，对于无向边(i,j)定义它们的联合概率为：
p_1(v_i, v_j) = \frac{1}{1 + exp(-u_i^T \cdot u_j)} \quad\quad (1)
其中u_i \in R^d是节点v_i的低维表示, 公式（1）定义了在空间V \times V上的分布p(\cdot, \cdot).经验分布被定义为\hat{p_1}=\frac{w_{ij}}{W}, 其中W=\sum_{(i,j) \in E} w_{ij}.为保留一阶相似度，一种直观的方式是最小如下目标函数
O_1 = d( \hat{p_1}(\cdot,\cdot), p_1(\cdot, \cdot)) \quad\quad (2)
其中d(\cdot,\cdot)为两个分布之间的差异，我们选择最小化KL散度用KL散度替换d(\cdot,\cdot) 并忽略一些常数，我们有：
O_1 = - \sum_{(i,j) \in E} w_{ij} \log p_1 (v_i, v_j) \quad\quad (3)
值得一提的是，一阶相似度仅适用于无向图，不适用于有向图，通过公式(3)的损失函数，我们能够获得每一个节点的低维表示。

LINE with Second-order Proximity

二阶近似度适用于有向图和无向图，二阶相似度的假设是与其他顶点共享链接的顶点彼此相似。因此，每个节点扮演两个角色：顶点本身和其他节点的上下文节点。我们引入两个向量\overrightarrow{u_i}和\overrightarrow{u_i}'，其中\overrightarrow{u_i}是当v_i被视为一个节点时的低维表示，而\overrightarrow{u_i}'则为v_i作为上下文节点时的低维表示。对于每一个有向边(i,j）, 我们定义由v_i生成的v_j的上下文节点的概率为：

p_2(v_j|v_i) = \frac{exp(\overrightarrow{u_j}'^T \cdot \overrightarrow{u_i}' )}{ \sum_{k=1}^{|V|} exp( \overrightarrow{u_k}'^T \cdot \overrightarrow{u_i}' )} \quad\quad (4)

其中|V|是节点全集，对于公式（4）中的每一个顶点v_i，公式实际上定义了在”上下文节点“上的条件分布p_2(\cdot|v_i), 例如网络中的所有顶点集。二阶接近度假设在上下文上具有相似分布的顶点彼此相似。为了保持二阶相似度，我们应该使得条件分布p_2(v_j|v_i)应该与经验分布\hat{p_2} (\cdot |v_i)接近，因而我们最小化如下目标函数
O_2 = \sum_{i \in V} \lambda_i d(\hat{p_2}(\cdot|v_i), p_2(\cdot|v_i)) \quad\quad (5)
其中d(\cdot, \cdot)是两个分布之间的距离，由于顶点在网络中的重要性可能有所不同，我们把\lambda_i引入到目标函数中来表示网络中节点i的”声望“，可以用PageRank一类的算法进行估算。经验分布\hat{p_2}(\cdot|v_i)被定义为\hat{p_2}(\cdot|v_i)=\frac{w_{ij}}{d_i}，其中w_{ij}是边(i,j)的权重，d_i是节点i的出度。例如d_i = \sum_{k \in N(i)} w_{ik}，其中N(i)是v_i的出邻居。使用KL散度代替d(\cdot, \cdot), 设置\lambda_i = d_i并忽略掉一些常数项，我们有：
O_2 = - \sum_{(i,j)\in E} w_{ij} \log p_2(v_j|v_i) \quad\quad (6)

Combing first-order and second-order proximities

为了保留一阶和二阶来学习网络嵌入表示，我们的想法是联合训练公式(3)和(6)

Model Optimization

公式（6）在计算条件概率时，需要对所有邻接节点进行求和，为了解决这个问题，我们采取负采样方法。根据噪声分布对每一条边进行从;yh，具体的对于每一条边(i,j)，我们有如下目标函数：
\log \sigma(\overrightarrow{u_j}'^T \cdot \overrightarrow{u_i}' ) + \sum_{i=1}^K E_{v_n~P_n(v)} [ \log \sigma( \overrightarrow{u_n}'^T \cdot \overrightarrow{u_i}' ) ] \quad\quad (7)
其中\sigma(x)是sigmoid函数，其中第一项是“Observed”边，第二项是从噪声分布里抽样到的负边关系。对于公式（3）我们采取同样的措施，通过负采样方法，仅仅是把公式（7）中的\overrightarrow{u_j}'^T替换成\overrightarrow{u_j}^T, 而在模型优化部分，我们使用ASGD来进行优化策略。