Question

1. 信息网络 information network 在现实世界中无处不在，例如航空网络、出版物网络、社交网络、通信网络、以及万维网。这些信息网络的规模从数百个节点到数百万、甚至数十亿个节点不等。分析大型信息网络已经引起学术界和工业界越来越多的关注。论文 《LINE: Large-scale Information Network Embedding》 研究了将信息网络嵌入到低维空间中的问题，其中每个顶点都表示为一个低维向量。这种低维 embedding 在各种application 中非常有用，例如可视化visualization、节点分类node classi fication、链接预测link prediction、推荐recommendation 。

   机器学习文献中已经提出了各种 graph embedding 方法。它们通常在较小的网络上表现良好。当涉及现实世界的信息网络时（这些网络通常包含数百万节点、数十亿条边），这个问题变得更具挑战性。例如，2012 年 Twitter 的 followee-follower 网络包含 1.75 亿活跃用户、大约 200 亿条边。大多数现有的 graph embedding 算法无法针对这种规模的网络进行扩展。例如，MDS 、IsoMap 、Laplacian eigenmap 等经典 graph embedding 算法的时间复杂度至少是顶点数量的二次方，这对于具有数百万个节点的网络来说是不可行的。

   尽管最近的一些工作研究了大规模网络的 embedding ，但是这些方法要么采用了不是为网络而设计的间接方法（如《Distributed large-scale natural graph factorization》 ），要么缺乏为网络 embedding 量身定制的、明确的目标函数（如 《Deepwalk: Online learning of social representations》）。论文 《LINE: Large-scale Information Network Embedding》 预计：具有精心设计的、保持图属性的目标函数和有效优化技术的新模型，应该可以有效地找到数百万个节点的 embedding 。因此在该论文中，作者提出了一种称为 LINE 的 network embedding 模型，它能够扩展到非常大的、任意类型的网络：无向/有向图、无权/有权图。该模型优化了一个目标函数，该目标函数同时保持了局部网络结构local network structure 和全局网络结构global network structure 。

   • 局部网络结构（一阶邻近性）：自然地，局部网络结构由网络中观察到的链接来表示，它捕获顶点之间的一阶邻近性 first-order proximity。大多数现有的 graph embedding 算法都旨在保持这种一阶邻近性，例如 IsoMap、Laplacian eigenmap，即使这些算法无法扩展。

   • 全局网络结构（二阶邻近性）：作者观察到：在现实世界的网络中，实际上很多合法的链接都未被观测到。换句话讲，在现实世界数据中观察到的一阶邻近性不足以保持全局网络结构。作为补充，作者探索了顶点之间的二阶邻近性second-order proximity ，这是通过顶点的共享邻域结构shared neighborhood structure 来确定的，而不是通过观察到的直接连接强度来确定。

     二阶邻近性的通用概念可以解释为：具有共享邻居的节点之间可能是相似的。这种直觉可以在社会学和语言学的理论中找到。例如：在社交网络中，“两个人的社交网络的重叠程度与他们之间的联系强度相关”（the degree of overlap of two people's friendship networks correlates with the strength of ties between them）；在文本网络中，“一个词的意思是由它的使用环境所形成的”（You shall know a word by the company it keeps）。确实，有很多共同好友的人很可能有相同的兴趣并成为朋友，而与许多相似词一起使用的单词很可能具有相似的含义。

     下图展示了一个说明性的例子，其中边越粗权重越大：

     • 由于顶点 6 和顶点 7 之间的边的权重很大，即顶点 6 和顶点 7 具有较高的一阶邻近性，因此它们的 representation 应该在 embedding 空间中彼此靠近。
     • 另一方面，虽然顶点 5 和顶点 6 之间没有直接链接，但是它们共享了许多共同的邻居，即它们具有很高的二阶邻近性，因此它们的 representation 应该在 embedding 空间中彼此靠近。

     论文期望对二阶邻近性的考虑能够有效地补充一阶邻近性的稀疏性，从而更好地保持网络的全局结构。在论文中，作者将展示精心设计的目标函数，从而保持一阶邻近性和二阶邻近性。

     

   即使找到了一个合理的目标函数，为一个非常大的网络优化该目标函数也是具有挑战性的。近年来，引起大家关注的一种优化方法是随机梯度下降。然而，论文表明：直接部署随机梯度下降对现实世界的信息网络是有问题的。这是因为在许多网络中，边是加权的，并且权重通常呈现高方差 high variance 。考虑一个单词共现网络 word co-occurrence network ，其中 word pair 的权重（共现）可能从 “一” 到 “几十万” 不等。这些边的权重将乘以梯度，导致梯度爆炸从而影响模型性能。

   因为 LINE 的目标函数是加权的交叉熵，权重为 word pair 共现次数。

   为了解决这个问题，论文提出了一种新的边采样方法 edge-sampling method ，该方法提高了推断的效率 efficiency 和效果effectiveness 。作者以与边权重成正比的概率对边进行采样，然后将采样后的边视为用于模型更新的二元边 binary edge 。通过这个采样过程，目标函数保持不变，边的权重不再影响梯度。

   这可能会导致数据稀疏性问题：即一些权重很小的边未被采样到。

   LINE 非常通用，适用于有向/无向图、加权/未加权图。论文使用各种真实世界的信息网络（包括语言网络 language network 、社交网络social network 、引文网络 citation network ）来评估 LINE 的性能。论文在多个数据挖掘任务中评估了学到的 embedding 的有效性，包括单词类比 word analogy 、文本分类 text classification 、节点分类 node classification 。结果表明，LINE 模型在效果和效率方面都优于其它竞争 baseline。LINE 能够在几个小时内在单台机器上学习具有数百万个节点、数十亿条边的网络的 embedding。

   总而言之，论文主要贡献：

   • 论文提出了一个叫做 LINE 的、新的 network embedding 模型，该模型适用于任意类型的信息网络，并可轻松地扩展到数百万个节点。该模型有一个精心设计的目标函数，可以同时保持一阶邻近性和二阶邻近性。
   • 论文提出了一种边采样算法来优化目标函数，该算法解决了经典随机梯度下降的局限性，提高了推断的效率和效果。
   • 论文对现实世界的信息网络进行了广泛的实验，实验结果证明了 LINE 模型的效率和效果。

2. 相关工作：

   • 我们的工作通常与 graph embedding 或降维的经典方法有关，例如多维缩放 multidimensional scaling: MDS、IsoMap、LLE、Laplacian Eigenmap。这些方法通常首先使用数据点 data point 的特征向量 feature vector 构建 affinity graph ，例如数据的 K-nearest neighbor graph ，然后将 affinity graph 嵌入到低维空间中。

     然而，这些算法通常依赖于求解 affinity matrix 的 top-n eigenvectors ，其复杂度至少是节点数量的二次方，使得它们在处理大规模网络时效率很低。

   • 最近的文献中有一种叫做图分解 graph factorization （《Distributed large-scale natural graph factorization》） 的技术。该方法通过矩阵分解找到大规模图的低维 embedding，并使用随机梯度下降进行优化。这是可行的，因为图可以表示为 affinity matrix 。

     然而，矩阵分解的目标不是为网络设计的，因此不一定保持了全局网络结构。直觉上，图分解预期具有较高一阶邻近性的节点的 representation 彼此靠近。相反，LINE 模型使用了一个专门为网络设计的目标函数，该目标函数同时保持了一阶邻近性和二阶邻近性。另外，图分解方法仅适用于无向图，而 LINE 方法适用于无向图和有向图。

   • 与我们最相关的、最新的工作是 DeepWalk，它通过截断的随机游走truncated random walk 来学习社交网络的 embedding。尽管在经验上是有效的，但是 DeepWalk 并为提供明确的目标来阐明保持哪些网络属性。直觉上，DeepWalk 期望具有较高二阶邻近性的节点产生相似的低维 representation，而 LINE 同时保持一阶邻近性和二阶邻近性。

     DeepWalk 使用随机游走来扩展顶点的邻域，这类似于深度优先搜索depth-first search: DFS。LINE 使用广度优先搜索 breadth- first search: BFS 策略，这是一种更合理的二阶邻近性方法。另外，DeepWalk 仅适用于无权图，而 LINE 适用于加权图和无权图。

   在实验中，我们使用各种真实世界的网络来评估LINE 和这些方法的效果。

2.1 模型

2.1.1 问题定义

1. 信息网络information network 的定义：一个信息网络定义为 $ G=(V,E) $ ，其中：

   • $ V $ 为顶点集合，每个元素代表一个数据对象 data object 。

   • $ E $ 为边集合，每个元素代表两个数据对象之间的关系。

   • 每条边 $ e\in E $ 是一个有序的 pair $ e=(u,v) $ ，它关联一个权重 $ w_{u,v}\gt 0 $ 表示关系的强度。

     • 如果 $ G $ 是无向图，则有 $ (u,v) = (v,u) $ 且 $ w_{u,v} = w_{v,u} $ ；如果 $ G $ 是有向图，则有 $ (u,v) \ne (v,u) $ 且 $ w_{u,v} \ne w_{v,u} $ 。
     • 如果 $ G $ 是无权图，则 $ w_{u,v}\in \{0,1\} $ ，这种边称作二元边 binary edge ，权重表示相连/不相连；如果 $ G $ 是带权图，则 $ w_{u,v}\in \mathbb R^+\cup \{0\} $ 则边的取值是实数，这种边表示连接的紧密程度。

     这里所有权重都是非负的，并不考虑负权重。

2. 在实践中，信息网络可以是有向的（如引文网络），也可以是无向的（如 Facebook 的用户社交网络）。边的权重可以是二元 binary 的，也可以是任何实际值。注意，虽然边的权重理论上也可以是负的，但是这里我们仅考虑非负的权重。例如，在引文网络和社交网络中， $ w_{u,v} $ 是二元的。在不同共现网络中， $ w_{u,v} $ 可以取任何非负值。某些网络中的边的权重方差可能很大，因为某些对象会多次共现、而其它对象可能很少共现。

3. 将信息网络嵌入到低维空间在各种 application 中都很有用。为了进行 embedding，网络结构必须被保持。第一个直觉是必须保持局部网络结构，即顶点之间的局部 pairwise 邻近性。我们将局部网络结构定义为顶点之间的一阶邻近性。

   一阶邻近性 first-order proximity 的定义：网络中的一阶邻近性是两个顶点之间的局部 pairwise 邻近性。对于边 $ (u,v) $ 连接的顶点 pair，边上的权重 $ w_{u,v} $ 表示顶点 $ u $ 和顶点 $ v $ 之间的一阶邻近性。如果在顶点 $ u $ 和顶点 $ v $ 之间没有观察到边，则它们之间的一阶邻近性为 0 。

   一阶邻近性通常意味着现实世界网络中两个节点的相似性 similarity 。例如：在社交网络中彼此成为好友的人往往有相似的兴趣，在万维网中相互链接的网页倾向于谈论相似的话题。由于这种重要性，许多现有的 graph embedding 算法（如 IsoMap、LLE、Laplacian eigenmap 、graph factorization ）都以保持一阶邻近性为目标。

4. 然而，在现实世界的信息网络中，观察到的链接仅是一小部分，还有许多其他链接发生了缺失 missing 。缺失链接上的顶点 pair 之间的一阶邻近性为零，尽管它们本质上彼此非常相似。因此，仅靠一阶邻近性不足以保持网络结构，重要的是寻找一种替代的邻近性概念来解决稀疏性问题。一个自然的直觉是：共享相似邻居的顶点往往彼此相似。例如：在社交网络中，拥有相同朋友的人往往有相似的兴趣，从而成为朋友；在单词共现网络中，总是与同一组单词共现的单词往往具有相似的含义。因此，我们定义了二阶邻近性，它补充了一阶邻近性并保持了网络结构。

   二阶邻近性 second-order proximity 的定义：网络中一对顶点 $ (u,v) $ 之间的二阶邻近性是它们的邻域网络结构之间的相似性。数学上，令 $ \mathbf{\vec p}_u = (w_{u,1},\cdots,w_{u,|V|})^\top \in \mathbb R^{|V|} $ 为顶点 $ u $ 和所有顶点的一阶邻近性向量，然后顶点 $ u $ 和顶点 $ v $ 之间的二阶邻近性由 $ \mathbf{\vec p}_u $ 和 $ \mathbf{\vec p}_v $ 的相似性来确定。如果没有任何顶点同时与 $ u $ 和 $ v $ 相连，则 $ u $ 和 $ v $ 之间的二阶邻近性为 0 。

5. 我们研究了 network embedding 的一阶邻近性和二阶邻近性，定义如下。

   大规模信息网络嵌入Large-scale Information Network Embedding ：给定一个大型网络 $ G=(V,E) $ ，大规模信息网络嵌入的问题旨在将每个顶点 $ v\in V $ 映射到一个低维空间 $ \mathbb R^d $ 中，即学习一个函数 $ f_G: V \rightarrow \mathbb R^d $ ，其中 $ d\ll |V| $ 。在空间 $ \mathbb R^d $ 中，顶点之间的一阶邻近性和二阶邻近性都可以得到保持。

6. 现实世界信息网络的理想 embedding 模型必须满足几个要求：

   • 首先，它必须能够同时保持顶点之间的一阶邻近性和二阶邻近性。
   • 其次，它必须针对非常大的网络可扩展，比如数百万个顶点、数十亿条边。
   • 第三，它可以处理具有任意类型边的网络：有向/无向、加权/无权的边。

   这里，我们提出了一个叫做 LINE 的新型 network embedding 模型，该模型满足所有这三个要求。我们首先描述了 LINE 模型如何分别保持一阶邻近性和二阶邻近性，然后介绍一种简单的方法来组合这两种邻近性。

2.1.2 保持一阶邻近性的 LINE

1. 一阶邻近性是指网络中顶点之间的局部 pairwise 邻近性。为了对一阶邻近性建模，对于每条无向边 $ (v_i,v_j) $ ，我们定义顶点 $ v_i $ 和 $ v_j $ 之间的联合概率为：

   $ p_1(v_i,v_j) = \frac{1}{1+\exp\left(\mathbf{\vec u}_i^\top \mathbf{\vec u}_j\right)} $

   其中 $ \mathbf{\vec u}_i\in \mathbb R^d $ 为顶点 $ v_i $ 的低维 representation 向量。

   上式定义了 $ V\times V $ 空间上的一个概率分布 $ p_1(\cdot,\cdot) $ ，它的经验概率 empirical probability 定义为：

   $ \hat p_1(v_i,v_j) = \frac{w_{i,j}}{W} $

   其中 $ W=\sum_{(v_i,v_j)\in E} w_{i,j} $ 为所有边权重之和。

2. 为了保持一阶邻近性，一个直接的方法是最小化以下目标函数：

   $ O_1 = \text{dist}\left(\hat p_1(\cdot,\cdot), p_1(\cdot,\cdot)\right) $

   其中 $ \text{dist}(\cdot,\cdot) $ 为两个概率分布之间的距离。这里我们选择 KL 散度作为距离函数，因此有：

   $ O_1 = -\sum_{(v_i,v_j)\in E} w_{i,j} \log p_1(v_i,v_j) $

   注意，上述一阶邻近性仅适用于无向图，而无法适用于有向图。

   通过最小化 $ O_1 $ 从而得到 $ \left\{\mathbf{\vec u}_i\right\}_{i=1}^{|V|} $ ，我们可以得到每个顶点在 $ d $ 维空间中的 representation。

   读者注：

   • 上式的物理意义为：观测边的加权负对数似然，每一项权重为边的权重。
   • 上式并不是严格的 KL 散度，它用到的是两个非归一化概率 $ p_1(v_i,v_j) $ 和 $ \hat p_1^\prime(v_i,v_j) = w_{i,j} $ 。
   • 最小化 KL 散度等价于最小化交叉熵：

   $ \min \text{dist}\left(\hat p_1^\prime, p_1 \right) = \min\sum \hat p_1^\prime \times\log \frac{\hat p_1^\prime}{p_1} = \min -\sum \hat p_1^\prime\log p_1 $

   其中省略了常数项 $ \sum \hat p_1^\prime \log \hat p_1^\prime $ 。

2.1.3 保持二阶邻近性的 LINE

1. 二阶邻近性适用于有向图和无向图。给定一个网络，不失一般性，我们假设它是有向的（一条无向边可以被认为是两条方向相反、权重相等的有向边）。二阶邻近性假设：共享邻域的顶点之间彼此相似。

   在这种情况下，每个顶点也被视为一个特定的 “上下文”（context）。我们假设：如果两个顶点的上下文相似，则这两个顶点是相似的。因此，每个顶点扮演两个角色：顶点本身、以及其它顶点的特定上下文。

2. 我们引入两个向量 $ \mathbf{\vec u}_i $ 和 $ \mathbf{\vec u}_i^\prime $ ，其中 $ \mathbf{\vec u}_i $ 为顶点 $ v_i $ 作为顶点本身时的 representation， $ \mathbf{\vec u}_i^\prime $ 为顶点 $ v_i $ 作为其它顶点的特定上下文时的 representation。对于每条有向边 $ (v_i,v_j) $ ，我们首先定义由顶点 $ v_i $ 生成上下文顶点 $ v_j $ 的概率为：

   $ p_2(v_j\mid v_i) = \frac{\exp\left(\mathbf{\vec u}_j^{\prime\top}\mathbf{\vec u}_i\right)}{\sum_{k=1}^{|V|}\exp\left(\mathbf{\vec u}_k^{\prime\top}\mathbf{\vec u}_i\right)} $

   其中 $ |V| $ 为顶点集合的大小。

   对于每个顶点 $ v_i $ ，上式实际上定义了上下文（即网络上整个顶点集合）中的条件分布 $ p_2(\cdot\mid v_i) $ 。如前所述，二阶邻近性假设具有相似上下文分布的顶点之间彼此相似。为了保持二阶邻近性，我们应该使得由低维 representation 指定的上下文条件分布 $ p_2(\cdot\mid v_i) $ 接近经验分布 $ \hat p_2(\cdot\mid v_i) $ 。因此，我们最小化以下目标函数：

   $ O_2 = \sum_{v_i\in V} \lambda_i\times \text{dist}\left(\hat p_2(\cdot\mid v_i),p_2(\cdot\mid v_i)\right) $

   其中：

   • $ \lambda_i $ 为顶点 $ v_i $ 的重要性。由于网络中顶点的重要性可能不同，我们在目标函数中引入了 $ \lambda_i $ 来表示顶点 $ v_i $ 在网络中的重要性。 $ \lambda_i $ 可以通过顶点的 degree 来衡量，也可以通过 PageRank 等算法进行估计。

     注意：目标函数 $ O_1 $ 中并未引入顶点重要性，而目标函数 $ O_2 $ 中引入了顶点重要性。这里引入顶点重要性是为了得到 $ O_2 $ 的一个简洁的公式。

   • $ \text{dist}(\cdot,\cdot) $ 是两个概率分布之间的距离。

   • 经验分布 $ \hat p_2(\cdot\mid v_i) $ 定义为 $ \hat p_2(v_j\mid v_i) = \frac{w_{i,j}}{d_i} $ ，其中 $ w_{i,j} $ 是边 $ (v_i,v_j) $ 的权重， $ d_i $ 是顶点 $ v_i $ 的出度 out-degree，即 $ d_i=\sum_{k\in \mathcal N_i}w_{i,k} $ ， $ \mathcal N_i $ 为顶点 $ v_i $ 的 out-neighbors 。

   在本文中，为简单起见，我们将 $ \lambda_i $ 设为顶点 $ v_i $ 的 out-degree，即 $ \lambda_i = d_i $ 。这里我们也采用 KL 散度作为距离函数。忽略一些常量，则我们得到：

   $ O_2 = -\sum_{(v_i,v_j)\in E} w_{i,j}\log p_2(v_j\mid v_i) $

   通过最小化 $ O_2 $ 从而得到 $ \left\{\mathbf{\vec u}_i\right\}_{i=1}^{|V|},\left\{\mathbf{\vec u}_i^\prime\right\}_{i=1}^{|V|} $ ，我们可以得到顶点 $ v_i $ 在 $ d $ 维空间中的 representation $ \mathbf{\vec u}_i $ 。

   读者注：

   • 上式的物理意义为：条件概率的加权负对数似然，每一项权重为边的权重。
   • 与 $ O_1 $ 相反，这里是严格的 KL 散度，它用到的是两个归一化概率 $ p_2(v_j\mid v_i) $ 和 $ \hat p_2(v_j\mid v_i) $ 。
   • 同样地，最小化 KL 散度等价于最小化交叉熵。
   • 二阶邻近性 LINE 类似于上下文窗口长度为 1 的 DeepWalk ，但是 DeepWalk 仅用于无权图而 LINE 可用于带权图。

2.1.4 组合一阶邻近性和二阶邻近性

1. 为了通过同时保持一阶邻近性和二阶邻近性来嵌入网络，我们在实践中发现一种简单的、有效的方法是：分别训练一阶邻近性 LINE 模型、二阶邻近性 LINE 模型；然后对于每个顶点，拼接这两种方法得到的 embedding 。

   实验部分作者提到：需要对拼接后的向量各维度进行加权从而平衡一阶 representation 向量和二阶 representation 向量的关系。在监督学习任务中，可以基于训练数据自动得到权重；在无监督学习任务中，无法配置这种权重。因此组合一阶邻近性和二阶邻近性仅用在监督学习任务中。

   组合一阶邻近性和二阶邻近性的更合理的方法是联合训练目标函数 $ O_1 $ 和 $ O_2 $ ，我们将其留作未来的工作。

2.1.5 模型优化

1. 负采样：优化目标函数 $ O_2 $ 的计算量很大，在计算条件概率 $ p_2(\cdot \mid v_i) $ 时需要对整个顶点集合进行求和。为了解决这个问题，我们采用了负采样方法，它对每条边 $ (v_i,v_j) $ 根据一些噪声分布 noisy distribution 来负采样多条负边 negative edge 。具体而言，我们为每条边 $ (v_i,v_j) $ 指定以下目标函数：

   $ \log \sigma\left(\mathbf{\vec u}_j^{\prime \top} \mathbf{\vec u}_i\right) + \sum_{n=1}^K \mathbb E_{v_n\sim P_n(v)}\left[\log\sigma\left(-\mathbf{\vec u}_n^{\prime \top} \mathbf{\vec u}_i\right)\right] $

   其中：

   • $ \sigma(x) = 1/(1+\exp(-x)) $ 为 sigmoid 函数。
   • $ \mathbb E[\cdot] $ 为期望。
   • $ P_n(v) $ 为噪声分布。

   注意：目标函数 $ O_1 $ 中的概率 $ p_1(v_i,v_j) $ 不涉及对整个顶点集合进行求和。

   第一项对观察到的边进行建模，第二项对从噪声分布中采样的负边进行建模， $ K $ 是负边的数量。我们根据 Word2Vec 的建议设置 $ P_n(v) \propto d_v^{3/4} $ ，其中 $ d_v $ 为顶点 $ v $ 的出度 out-degree 。

2. 对于目标函数 $ O_1 $ ，存在一个平凡解 trivial solution ：

   $ \mathbf{\vec u}_i = (+\infty,+\infty,\cdots,+\infty)^\top,\quad i=1,2,\cdots,|V| $

   此时 $ p_1(v_i,v_j) = \frac{1}{1+\exp\left(-\mathbf{\vec u}_i \cdot \mathbf{\vec u}_j \right)} = 1 $ ，使得 $ O_1 = 0 $ 取最小值。

   为了避免平凡解，我们也可以利用负采样方法，对于每条边 $ (v_i,v_j) $ ：

   $ \log \sigma\left(\mathbf{\vec u}_j^{ \top} \mathbf{\vec u}_i\right) + \sum_{n=1}^K \mathbb E_{v_n\sim P_n(v)}\left[\log\sigma\left(-\mathbf{\vec u}_n^{ \top} \mathbf{\vec u}_i\right)\right] $

   第一项对观察到的边进行建模，第二项对从噪声分布中采样的负边进行建模， $ K $ 是负边的数量。

   注意这里没有上下文顶点，因此没有 $ \mathbf{\vec u}_j^\prime $ 。

2.1.6 边采样

1. 我们采用异步随机梯度算法 ASGD 来优化目标函数。在每一步中，ASGD 算法采样了一个 mini-batch 的边，然后更新模型参数。假设采样到边 $ (v_i,v_j) $ ，则顶点 $ v_i $ 的 embedding 向量 $ \mathbf{\vec u}_i $ 被更新为：

   $ \nabla_{\mathbf{\vec u}_i} O_2 = w_{i,j} \times \frac{\partial \log p_2(v_j\mid v_i)}{\partial \mathbf{\vec u}_i} $

   注意，梯度将乘以边的权重。当边的权重具有高方差时，这将成为问题。例如，在一个单词共现网络中，一些词会共现很多次（例如，数万次），而另一些词只会共现几次。在这样的网络中，梯度的scale 不同，很难找到一个好的学习率：

   • 如果我们根据权重小的边选择较大的学习率，那么权重大的边上的梯度将会爆炸。
   • 如果我们根据权重大的边选择较小的学习率，那么权重小的边上的梯度会非常小。

2. 基于边采样edge-sampling 的优化：解决上述问题的直觉是，如果所有边的权重相等（例如，具有二元边binary edge 的网络），那么如何选择合适的学习率将不再成为问题。因此，一个简单的处理是将加权边展开为多个二元边。例如，将权重为 $ w $ 的边展开为 $ w $ 条二元边。虽然这能够解决问题，但是会显著增加内存需求，尤其是当边的权重非常大时，因为这显著增加边的数量。

   为此，可以从原始边中采样，并将采样后的边视为二元边，采样概率与原始边的权重成正比。通过这种边采样处理，整体目标函数保持不变。问题归结为如何根据权重对边进行采样。

   令 $ W=(w_1,w_2,\cdots,w_{|E|}) $ 为边权重的序列。

   • 首先，简单地计算权重之和 $ w_{\text{sum}} = \sum_{i=1}^{|E|}w_i $ 。
   • 然后，在 $ [0,w_\text{sum}] $ 范围内随机采样一个值，看看这个随机值落在哪个区间 $ \left[\sum_{j=0}^{i-1}w_j, \sum_{j=0}^i w_j\right) $ 。

   该方法需要 $ O(|E|) $ 的时间来采样，当边的数量 $ |E| $ 很大时，其代价太高。我们使用 alias table 方法来根据边的权重来采样。当从相同的离散分布中重复采样时，其平摊的时间复杂度为 $ O(1) $ 。

3. 从 alias table 中采样一条正边需要 $ O(1) $ 时间。此外，负采样优化需要 $ O(d(K+1)) $ 时间，其中 $ K $ 为负采样数量。因此，每个 step 都需要 $ O(dK) $ 时间。

   在实践中，我们发现用于优化的 step 数量通常与边的数量 $ O(|E|) $ 成正比。因此，LINE 的整体时间复杂度为 $ O(dK|E|) $ ，与边的数量 $ |E| $ 成线性关系，而不依赖于顶点数量 $ |V| $ 。边采样在不影响效率的情况下提高了随机梯度下降的效果。

2.1.7 讨论

1. 我们讨论了 LINE 模型的几个实际问题。

2. 低度low degree顶点 ：一个实际问题是如何准确地嵌入 degree 较小的顶点。由于此类顶点的邻居数量非常少，因此很难准确地推断其 representation，尤其是使用严重依赖于 “上下文” 数量的二阶邻近性方法。一种直觉的解决方案是通过添加更高阶的邻居（如邻居的邻居）来扩展这些顶点的邻居。

   在本文中，我们只考虑向每个顶点添加二阶邻居，即邻居的邻居。顶点 $ v_i $ 和它的二阶邻居 $ v_j $ 之间的权重被设置为：

   $ w_{i,j} = \sum_{k\in \mathcal N_i} w_{i,k} \times \frac{w_{k,j}}{d_k} $

   其中：

   • $ \mathcal N_i $ 为顶点 $ v_i $ 的一阶邻居集合。
   • $ v_j \in \{v\mid v \in \bigcup_{k} \mathcal N_k ,v_k\in \mathcal N_i,v\ne v_i\} $ 为顶点 $ v_i $ 的二阶邻居集合。

   实践中，只能添加与 low degree 顶点 $ v_i $ 具有最大邻近性 $ w_{i,j} $ 的二阶邻居顶点子集 $ \{v_j\} $ 。

3. 新顶点：另一个实际问题是如何找到新顶点的 representation 。

   对于一个新顶点 $ v_i $ ，如果它与现有顶点存在链接，则我们可以获得新顶点在现有顶点上的经验分布 $ \hat p_1(\cdot,v_i), \hat p_2(\cdot\mid v_i) $ 。为了获得新顶点的 embedding，根据目标函数 $ O_1 $ 和 $ O_2 $ ，一个直接方法是最小化以下目标函数之一：

   $ -\sum_{j\in \mathcal N_i} w_{j,i} \log p_1(v_j,v_i)\\ -\sum_{j\in \mathcal N_i}w_{j,i} \log p_2(v_j\mid v_i) $

   我们更新新顶点的 embedding，并保留现有顶点的embedding 。

   注意，对于有向边的图，需要考虑新顶点到已有顶点的链接、以及已有顶点到新顶点的链接，一共两个方向。

   如果新顶点和现有顶点之间不存在链接，则我们必须求助于其它信息，如顶点的文本信息。我们将其留作我们未来的工作。

4. 未来工作：

   • 研究网络中一阶邻近性和二阶邻近性以外的高阶邻近性。
   • 研究异质信息网络的 embedding，例如具有多种类型的顶点。

2.2 实验

1. 我们通过实验评估了 LINE 的效果和效率。我们将LINE 应用于几个不同类型的、大型的现实世界网络，包括一个语言网络 language network 、两个社交网络social network 、两个引文网络 citation network 。

2. 数据集：

   • 语言网络 Language Network 数据集：我们从整个英文维基百科页面构建了一个单词共现网络。我们选择滑动窗口为 5，并认为滑动窗口内的单词是共现的。出现频次小于 5 的单词被过滤掉。
   • 社交网络 Social Network 数据集：和DeepWalk 一致，我们也采用 Flickr 和 Youtube 数据集。Flickr 网络比 Youtube 网络更稠密。
   • 引文网络 Citation Network 数据集：使用 DBLP 数据集构建的作者引文网络 author citation network 、论文引用网络 paper citation network。作者引文网络记录了一位作者撰写、并被另一位作者引文的论文数量。

   这些数据集的统计见下表，其中：

   • 所有这些网络囊括了有向图/无向图，带权图/无权图。
   • 每个网络至少包含 50 万顶点和数百万条边，最大的网络包含200 万顶点和十亿条边。

   

3. baseline 方法：我们将 LINE 模型与几种现有的 graph embedding 方法进行比较，这些方法能够扩展到非常大的网络。我们没有与一些经典的 graph embedding 算法（如 MDS、IsoMap、Laplacian eigenmap ）进行比较，因为这些算法无法处理如此规模的网络。

   • Graph Factorization:GF ：一个信息网络可以表示为一个亲和度矩阵 affinity matrix，并通过矩阵分解来获取每个顶点的低维 representation 。GF 方法通过随机梯度下降法进行优化，因此可以处理大型网络。但是它仅适合无向图。

   • DeepWalk：DeepWalk 是最近提出的、一种用于社交网络 embedding 的方法，它仅适用于无权网络。对每个顶点，DeepWalk 使用从该顶点开始的截断随机游走来获取上下文信息，基于上下文信息建模来获取每个顶点的低维表达。因此，该方法仅利用二阶邻近性。

   • LINE-SGD：直接通过SGD 来优化目标函数的 LINE 模型。在优化过程中并没有使用边采样策略，因此对于采样到的正边，我们需要将边的权重直接乘以梯度。

     该方法有两个变种：

     • LINE-SGD(1st)：LINE-SGD的一阶邻近模型，它的优化目标是 $ O_1 $ 。该模型仅适用于无向图。
     • LINE-SGD(2nd)：LINE-SGD的二阶邻近模型，它的优化目标是 $ O_2 $ 。该模型可用于无向图和有向图。

   • LINE：标准的 LINE 模型。在优化过程中使用了边采用策略。

     该方法也有两个变种，分别为：

     • LINE(1st)：LINE的一阶邻近模型，它的优化目标是 $ O_1 $ 。该模型仅适用于无向图。
     • LINE(2nd)：LINE的二阶邻近模型，它的优化目标是 $ O_2 $ 。该模型可用于无向图和有向图。

   • LINE(1st+2nd)：同时拼接了LINE(1st) 和 LINE(2nd) 学到的 representation 向量，得到每个顶点的一个拼接后的、更长的representation 向量。

     需要对拼接后的向量各维度进行加权从而平衡一阶 representation 向量和二阶 representation 向量的关系。在监督学习任务中，可以基于训练数据自动得到权重；在无监督学习任务中，无法配置这种权重。因此 LINE(1st+2nd) 仅用在监督学习任务中。

4. 参数配置：

   • 所有方法都统一的配置：

     • 随机梯度下降的 batch-size = 1，即每个批次一个样本。因此迭代的样本数量就等于更新的 step 数量。
     • 学习率 $ \rho_t = \rho_0(1-t/T) $ ，其中： $ \rho_0 = 0.025 $ 为初始化学习率； $ t $ 表示第 $ t $ 个更新step ； $ T $ 为总的更新step 数量。
     • 所有得到的 embedding 向量都进行归一化： $ ||\mathbf{\vec w}||_2 = 1 $ 。
     • 为公平比较，语言网络数据集的 embedding 向量维度设为 200（因为 word2vec 方法采用该配置）；其它网络数据集的 embedding 向量维度默认设为 128 。

   • 对于 LINE 及其变种，负采样比例 $ K=5 $ 。

   • 对于 LINE(1st) 、LINE(2nd) 及其变种，总迭代步数 $ T $ 等于 100亿 ；对于 GF ，总迭代步数 $ T $ 等于 200 亿。

   • 对于 DeepWalk窗口大小 win=10，游走序列长度 t=40，每个顶点出发的序列数量 $ \gamma = 40 $ 。

2.2.1 语言网络

1. 语言网络：语言网络数据集包含 200万顶点和 10 亿条边。我们使用两个任务来评估学到的 embedding 的有效性：单词类比 word analogy、文档分类 document classification 。

2. 单词类比 word analogy：给定一对单词 (a,b) 和一个单词 c ，该任务的目标是寻找单词d，使得c 和 d 的关系类比于 a 和 b 的关系。记作：

   $ a : b \rightarrow c: \;? $

   如：“(中国，北京 )” 对应于 “(法国，?)” ，这里的目标单词为 “巴黎”。

   因此给定单词 a,b,c 的 embedding 向量，该任务的目标是寻找单词 $ d^* $ ，使得该单词的 embedding 尽可能与 $ \mathbf{\vec u}_b - \mathbf{\vec u}_a + \mathbf{\vec u}_c $ 相似：

   $ d^* = \arg\max_d\cos\left(\mathbf{\vec u}_b - \mathbf{\vec u}_a + \mathbf{\vec u}_c ,\mathbf{\vec u}_d\right) $

   在这个任务中使用了两种类型的单词类比：语义semantic 、句法syntactic 。

   在维基百科语言网络上的单词类比结果如下表所示。其中：

   • 对GF 方法，边的权重定义为单词共现次数的对数，这比直接采用单词共现次数更好的性能。
   • 对 DeepWalk 方法，尝试使用不同的截断阈值从而将网络权重二元化binarize 。最终当所有边都被保留下来时，模型性能最好。
   • SkipGram 直接从原始维基百科页面内容文本而不是语言网络来学习词向量。窗口大小设置为 5 。
   • 所有模型都是在单机上运行 16 个线程来计算，机器配置：1T 内存、2.0GHZ 的 40 个 CPU 。

   结论：

   • LINE(2nd) 优于所有其它方法。

     • LINE(2nd) 优于 GF,LINE(1st) 等一阶方法。这表明：和一阶邻近性相比，二阶邻近性更好的捕获了单词的语义。

       因为如果单词 a 和 b 的二阶邻近性很大，则意味着可以在相同上下文中可以相互替换单词a 和 b 。这比一阶邻近性更能说明相似语义。

     • 虽然 DeepWalk 也探索了二阶邻近性，但是其性能不如 LINE(2nd)，甚至不如一阶方法的 GF,LINE(1st) 。

       这是因为 DeepWalk 忽略了单词共现次数的原因，事实上语言网络中单词共现频次非常重要。

       这个解释不通。单词共现次数隐含在随机游走过程中：单词共现次数越大，则随机游走被采样到的概率越大。

     • 在原始语料上训练的 SkipGram 模型也不如 LINE(2nd)，原因可能是语言网络比原始单词序列更好的捕获了单词共现的全局信息。

   • 采用 SGD 直接优化的 LINE 版本效果要差得多。这是因为语言网络的边的权重范围从个位数到上千万，方差很大。这使得最优化过程受到严重影响。

     在梯度更新过程中进行边采样处理的LINE 模型有效解决了该问题，最终效果要好得多。

   • LINE(1st) 和 LINE(2nd) 的训练效率很高，对于两百万顶点、十亿边的网络只需要不到 3 个小时。

     • LINE(1st),LINE(2nd) 训练速度比GF 至少快 10%，比 DeepWalk 快 5 倍。
     • LINE-SGD 版本要稍慢，原因是在梯度更新过程中必须应用阈值截断技术防止梯度爆炸。

   

3. 文档分类：另一种评估 word embedding 质量的方法是使用 word embedding 来计算 document representation，然后通过文档分类任务评估效果。为了获得文档向量，我们选择了一种非常简单的方法，即选取该文档中所有单词的 word embedding 的均值。这是因为我们的目标是将不同方法得到的 word embedding 进行对比，而不是寻找 document embedding 的最佳方法。

   我们从维基百科种选择 7 种不同的类别 “艺术、历史、人类、数学、自然、技术、体育”，对每个类别随机抽取 1 万篇文章，其中每篇文章都只属于单个类别（如果文章属于多个类别就丢掉）。所有这些文章及其类别就构成了一个带标记的多类别语料库。

   我们随机抽取不同百分比的标记文档进行训练，剩余部分进行评估。所有文档向量都使用 LibLinear package 训练 one-vs-rest 逻辑回归分类器。我们报告了分类结果的 Micro-F1 和 Macro-F1 指标。

   在维基百科语言网络上的文本分类结果如下表所示。其中我们分别抽取 10%~90% 的标记样本作为训练集，剩余部分作为测试集。对每一种拆分我们随机执行 10 轮取平均结果。

   结论：

   • GF 方法优于 DeepWalk，因为 DeepWalk 忽略了单词共现次数。

   • LINE-SGD 性能较差，因为边权重方差很大所以LINE-SGD 的梯度更新过程非常困难。

   • 采用边采样的 LINE 模型优于 LINE-SGD，因为梯度更新过程中使用边采样能解决边权重方差很大带来的学习率选择问题。

   • LINE(1st) + LINE(2nd) 性能明显优于其它所有方法，这表明一阶邻近度和二阶邻近度是互补的。

     注意，对于监督学习任务，拼接了 LINE(1st) 和 LINE(2nd) 学到的 embedding 是可行的。

   

4. 为了更深入地了解一阶邻近性和二阶邻近性，下表对给定单词，分别采用一阶邻近性模型和二阶邻近性模型召回其最相似的 top 单词。可以看到：

   • 二阶邻近度召回的最相似单词都是语义相关的单词。
   • 一阶邻近度召回的最相似单词是语法相关、语义相关的混合体。

   

2.2.2 社交网络

1. 相比语言网络，社交网络更为稀疏，尤其是YouTube 网络。我们通过多标签分类任务来评估每个模型的embedding 效果。多标签分类任务将每个顶点分配到一个或者多个类别，每个类别代表一个社区community 。最终评估分类结果的 Micro-F1 和 Macro-F 指标。

   我们分别抽取 10%~90% 的标记样本作为训练集，剩余部分作为测试集。对每一种拆分随机执行 10 轮取平均结果。

2. Flickr Network 数据集：我们选择最热门的 5 个类别作为分类的类别，评估结果如下表。

   • LINE(1st) 模型优于 GF 模型，这表明LINE(1st) 模型比 GF 模型具有更好的一阶邻近性建模能力。

   • LINE(2nd) 模型优于 DeepWalk 模型，这表明LINE(2nd) 模型比 DeepWalk 模型具有更好的二阶邻近性建模能力。

   • LINE(1st) 模型略微优于 LINE(2nd) 模型，这和语言网络的结论相反。原因有两个：

     • 社交网络中，一阶邻近性比二阶邻近性更重要，因为一阶关系表明两个顶点的关系更紧密。
     • 当网络非常稀疏并且顶点的平均邻居数太小时，二阶邻近性可能不太准确。

   • LINE(1st) + LINE(2nd) 性能明显优于其它所有方法，这表明一阶邻近性和二阶邻近性是互补的。

   

3. YouTube 数据集：YouTube 网络非常稀疏，每个顶点的平均degree 小于 5 。对该数据集的评估结果如下表。

   • 在不同规模训练集上，LINE(1st) 一致性的优于 LINE(2nd)。这和 Flickr 数据集一致。

• 由于极度稀疏性，LINE(2nd) 性能甚至不如 DeepWalk 。

  • 在 128 维或 256 维上，LINE(1st) + LINE(2nd) 优于 DeepWalk 。这表明一阶邻近性和二阶邻近性是互补的，并能够缓解网络稀疏问题。

  考察 DeepWalk 是如何通过截断的随机游走来解决网络稀疏性问题的。随机游走类似于深度优先搜索，这种方式可以通过引入间接邻居来迅速缓解邻域稀疏的问题。但是这种方式也可能引入距离较远的顶点，距离较远意味着相关性不大。

  一种更合理的方式是采用广度优先搜索策略来扩展每个稀疏顶点的邻域，如二阶邻域策略。下表中，括号中的指标是二阶邻域策略的表现。其中我们对邻居数量少于 1000 的顶点扩展其二阶邻域，直到扩展邻域集合规模达到 1000 。我们发现添加超过 1000 个顶点并不会进一步提高性能。采用二阶邻域策略的网络称作重构网络 reconstructed network 。可以看到：

  • 采用二阶邻域策略之后GF,LINE(1st),LINE(2nd) 的性能都得到提升，其中 LINE(2nd) 的性能提升最为明显。

  • 采用二阶邻域策略之后 LINE(2nd) 大多数情况下都优于 DeepWalk 。

  • 采用二阶邻域策略之后 LINE(1st+2nd) 性能并没有提升太多。这意味着原始网络的一阶邻近性和二阶邻近性组合已经捕获了大部分信息。

    因此，LINE(1st+2nd) 是一个非常有效的Graph Embedding 方式，适用于dense 网络和 sparse 网络。

  注意：二阶邻域策略中，新增邻域顶点的权重需要重新计算，并且优先添加权重最大的顶点。

  

2.2.3 引文网络

1. 引文网络数据集包括作者引文网络、论文引用网络，它们都是有向图。由于GF 和 LINE(1st) 都无法应用于有向图，因此这里仅仅比较 DeepWalk 和 LINE(2nd) 。

   我们还通过多标签分类任务评估顶点 embedding 的效果。我们选择 7 个热门的会议（AAAI,CIKM,ICML,KDD,NIPS,SIGIR,WWW）作为分类类别，在会议中发表的作者或者论文被标记为对应类别。最终评估分类结果的 Micro-F1 和 Macro-F 指标。

   我们分别抽取 10%~90% 的标记样本作为训练集，剩余部分作为测试集。对每一种拆分随机执行 10 轮取平均结果。

2. 作者引用网络数据集的评估结果如下表所示。

   • 由于网络稀疏，因此 DeepWalk 性能优于 LINE(2nd) 。
   • 通过二阶邻域策略重构网络，邻域规模的阈值设定为 500，最终 LINE(2nd) 性能大幅提升并且优于 DeepWalk 。
   • LINE-SGD(2nd) 性能较差，因为边权重方差很大所以LINE-SGD 的梯度更新过程非常困难。

   

3. 论文引用网络数据集的评估结果如下所示。

   • LINE(2nd) 的性能明显优于 DeepWalk。这是由于在论文引用网络中的随机游走只能沿着引用路径来游走，这使得一些时间比较久远的、相关性不大的论文被作为上下文。

     相比之下，LINE(2nd) 的上下文都是最近的、密切相关的参考文献，因此更为合理。

   • 通过二阶邻域策略重构网络，邻域规模的阈值设定为 200，最终 LINE(2nd) 性能得到进一步提升。

   

2.2.4 可视化

1. graph embedding 的一个重要用途是输出有意义的Graph 可视化。我们选择作者引文网络数据集来可视化，选择了三个领域的不同会议：数据挖掘data mining 领域的 WWW,KDD 会议、机器学习 machine learning 领域 的 NIPS,IML 会议、计算机视觉 computer vision 领域的 CVPR,ICCV 会议。

   作者引用网络基于这些会议公开发表的文章来构建，丢弃 degree < 3 的作者（表明这些作者不怎么重要），最终得到一个包含 18561 个顶点、207074 条边的网络。

   可视化这个作者引文网络非常具有挑战性，因为这三个研究领域彼此非常接近。我们首先通过不同的模型来得到 graph embedding，然后将顶点的 embedding 向量通过 t-SNE 进行可视化。下图中不同颜色代表不同的领域：红色代表数据挖掘，蓝色代表机器学习，绿色代表计算机视觉。

   • GF 模型的可视化结果不是很有意义，因为不同领域的顶点并没有聚集在一起。

   • DeepWalk 模型的可视化结果要好得多，但是很多不同领域的顶点密集的聚集在中心区域，其中大多数是degree 较高的顶点。

     这是因为： DeepWalk 使用基于截断随机游走的方式来生成顶点的邻居，由于随机性这会带来很大的噪声。尤其是degree 较高的顶点，因为对于degree 较高的顶点和大量其它顶点共现。

   • LINE(2nd) 模型的可视化结果更好、更具有意义。

   

2.2.5 网络稀疏性

1. 以社交网络为例，我们分析了模型性能和网络稀疏性的影响。

   • 我们首先研究网络的稀疏性如何影响 LINE(1st) 和 LINE(2nd)。图a 给出了 Flickr 网络链接的百分比和LINE 模型性能的关系。选择 Flickr 的原因是它比 YouTube 网络更密集。我们从原始网络中随机采样不同比例的链接从而构建具有不同稀疏性的网络。可以看到：

     • 一开始网络非常稀疏时，LINE(1st) 的性能好于 LINE(2nd) 。
     • 当网络逐渐密集时，LINE(2nd) 的性能超越了 LINE(1st) 。

     这表明：当网络极其稀疏时二阶邻近性模型受到影响；当每个顶点附近有足够的邻居时，二阶邻近性模型优于一阶邻近性模型。

   • 图 b 给出了YouTube 数据集原始网络和二阶邻域策略重构网络中，顶点degree 和模型性能指标的关系。我们将顶点根据 degree 来分组：： $ (0,1],[2,3],[5,6],[1,12],[13,30],[31,+\infty) $ 。然后评估每个分组的顶点分类结果指标。可以看到：

     • 总体而言，当顶点的 degree 增加时，所有模型的效果都得到提升。

   • 在原始网络中除第一个分组之外，LINE(2nd) 的性能始终优于 LINE(1nd) 。这表明二阶邻近性模型不适用于 degree 较小的点。

     • 在重构网络中，LINE(1st) 和 LINE(2nd) 都得到了改善，尤其是 LINE(2nd) 。
     • 在重构网络中，LINE(2nd) 始终优于 DeepWalk 。

   

2.2.6 参数敏感性

1. 我们在重建的 Youtube 网络上考察了不同的embedding 维度 $ d $ 和 LINE 模型性能的关系，以及样本数量和模型收敛速度的关系。

   • 图 a 给出了不同维度 $ d $ 时模型的性能。可以看到：当 $ d $ 过大时，LINE(1st) 和 LINE(2nd) 性能有所下降。

   • 图 b 给出了 LINE 和 DeepWalk 在优化过程中收敛速度和样本数量的关系。可以看到：LINE(2nd) 始终优于 LINE(1st) 和 DeepWalk，并且LINE(1st) 和 LINE(2nd) 收敛速度都快于 DeepWalk 。

     注意：这里的样本量指的是模型训练过程中见过的总样本量，包括重复的样本。由于 batch-size = 1，因此每个sample 需要一个迭代step，因此样本数量也等于迭代 step 。

   

2.2.7 可扩展性

1. 最后，我们研究了采用边采样和异步随机梯度下降法的LINE 模型的可扩展性 scalability 。我们部署了多线程进行优化。

   • 图 a 给出了在 YouTube 数据集上的线程数及其加速比。可以看到线程加速比接近线性。
   • 图b 给出了使用多线程进行模型更新时，模型性能的波动。可以看到采用多线程训练模型时，模型的最终性能保持稳定。

   这两个结果表明：LINE 模型具有很好的可扩展性（即并行度）。