二、LINE

1. 定义信息网络information network 为 ，其中：

   • 为顶点集合，对应于一个个实体。

   • 为边的集合，对应于实体之间的关系。

     更具体地，每条边 对应于一个有序对 ，并关联到一个权重 。边 就对应于实体 和 地关系。

     • 如果 是无向图，则有 ；如果 是有向图，则有 。

     • 如果 则这种边称为二元边，表示相连/不相连；如果 则边的取值是实数，表示连接的紧密程度。

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

2. 顶点对 之间的一阶邻近度 first-order proximity 为权重 ，它刻画了顶点 和 之间的邻近程度 。

   • 如果顶点 和 之间没有连接，则它们的一阶邻近度为 0 。

   • 一阶邻近度通常反应了两个顶点的相似性。如：

     • 社交网络中，如果两个成员是好友关系，则他们倾向于有相似的兴趣。
     • 在 web 网络中，如果两个网页存在链接关系，则它们通常会提到类似的话题。

     由于这种重要性，很多已有的Graph Embedding 算法（如：IsoMap,LLE,Laplacian eigenmap, graph factorization ）的目标函数都利用了一阶邻近度。

3. 真实世界的信息网络中，能观察到的直接链接仅占很小的比例，大部分链接都因观察不到而缺失。如：社交网络中，很多线下的关系链并没有百分之百同步到线上。

   如果顶点 和 的链接发生缺失，则其一阶邻近度为 0，即使实际上它们关系非常密切。因此仅仅依靠一阶邻近度不足以描述网络的全局结构，我们需要寻找方法来解决这种因为大部分链接缺失导致的网络稀疏问题。

   一个直观的想法是：如果两个顶点共享相同的一组邻居，则这两个顶点往往彼此相似。如：

   • 社交网络中，如果两个成员有相同的朋友圈，则他们很有可能也是好友关系。
   • 单词共现网络中，如果两个单词的上下文相同，则这两个单词往往具有相近的含义。

   如下图所示：

   • 顶点6 和 7 是直接相连，拥有较高的一阶邻近度，因此相互之间关系密切。映射到低维空间时，这两个顶点的相似度应该较高。
   • 顶点 5 和 6 有相同的邻居结点，拥有较高的二阶邻近度，因此关系也很密切。映射到低维空间时，这两个顶点的相似度也应该较高。

   

   因此我们采用二阶邻近度second-order proximity 。顶点对 之间的二阶邻近度定义为：它们邻居结构的相似程度。

   令 为顶点 和其它所有顶点的一阶邻近度，那么 和 的二阶邻近度定义为： 和 的相似度。如果 和 之间没有任何共同的邻居，则其二阶邻近度为 0 。

4. 给定一个大规模网络 ，Graph Embedding 的目标是给出图中每个顶点 的低维空间 representation （ ），在这个低维空间中保留顶点之间的一阶邻近度和二阶邻近度。

   一个理想的 Graph Embedding 具有以下要求：

   • 必须能够保留顶点之间的一阶邻近度和二阶邻近度。
   • 必须能够扩展到超大规模网络，如数百万顶点和数十亿条边。
   • 可以处理任何类型的边：有向的/无向的，带权重的/无权重的。

   现有的一些方法并不足以满足这些要求：

   • 传统的Graph Embedding 方法，如：IsoMap,LLE,Laplacian eigenmap, graph factorization，它们通常仅能处理小规模的网络，无法处理真实世界大规模网络。

     并且这些方法仅仅采用一阶邻近度，并没有考虑二阶邻近度。

   • DeepWalk 方法虽然能够处理超大规模网络，但是它仅适合无权图，无法处理带权重的图。

     而且 DeepWalk 并没有明确表示它保留的是顶点之间的一阶邻近度还是二阶邻近度。

   论文 《LINE: Large-scale Information Network Embedding》 提出了 LINE 模型，该模型能够同时满足以上需求。LINE 模型还提出了一种边采样算法来解决经典的随机梯度下降的局限性，提高了采样效率和效果。

   实验表明LINE 模型在各种现真实网络（语言网络、社交网络、引用网络）上有效，并且算法非常高效：在单机上几个小时内学习具有数百万顶点、数十亿边的 Graph Embedding 。

2.1 模型

2.1.1 一阶邻近度

1. 为建模一阶邻近度，对每个无向边 我们定义顶点 和 之间的联合概率分布为：

   

   其中 为顶点 的低维表达向量。

   是定义在空间 上的概率分布函数，定义其经验概率分布为：

   

   其中 表示所有边的权重， 表示边 的权重。

   为了在低维空间中保留一阶邻近度，一个简单直接的方法是最小化目标函数：

   

   其中 为两个概率分布的距离。论文采用 KL 散度作为两个分布的距离函数，因此最小化目标函数：

   

   通过求解该最优化问题，我们得到每个顶点的表达 。

   注意：这里定义的一阶邻近度模型仅适合无向图。

2.1.2 二阶邻近度

1. 给定一个有向图，二阶邻近度假设：有很多共同邻居的两个顶点彼此相似。

   注意：如果是无向图，则可以将每条无向边视为方向相反、权重相等的两条有向边。此时二阶邻近度模型也适用于无向图。

2. 在二阶邻近度模型中，每个顶点会充做其它顶点的 “上下文” 。因此每个顶点在计算 representation 时存在两个角色：需要计算representation 的顶点本身、计算其它顶点representation 时的上下文。

   对于顶点 我们引入两个 representation 向量：

   • 当作为需要计算 representation 的顶点时，其表达向量为
   • 当作为计算其它顶点 representation 的上下文时，其表达向量为

   借鉴 SkipGram 的思想，对每条有向边 ，我们定义由顶点 生成上下文 的概率为：

   

   其中 为顶点数量（也是上下文数量）。

   因此对于每个顶点 ，我们定义了一个条件概率分布 ，这个条件概率分布的经验分布函数为：

   

   其中 为边 的权重， 为顶点 的出度out degree ： ， 为顶点 的邻域。

   为了在低维空间中保留二阶邻近度，我们最小化目标函数：

   

   其中

   • 来表示顶点 在网络中的重要性，它可以通过顶点的 degree 来衡量，也可以通过 PageRank 之类的算法来估计。
   • 为两个概率分布的距离。

   论文采用 、距离采用 KL 散度，则最小化目标函数：

   

   通过求解该最优化问题，我们得到每个顶点的表达 ，每个顶点的上下文表达 。

2.1.3 融合

1. LINE 用两个模型分别训练一阶邻近度模型和二阶邻近度模型，得到一阶embedding 向量和二阶 embedding 向量。

   • 对于监督学习任务，LINE 将一阶embedding 向量和二阶 embedding 向量拼接成一个向量作为每个顶点的最终embedding 向量，然后通过一个逻辑回归模型来自动调整向量中每个单元的权重。

     这相当于间接的调整了一阶embedding 向量、二阶embedding 向量的融合权重。

   • 对于无监督学习任务，LINE 只能单独使用一阶embedding 向量或者二阶embedding 向量。因为无监督学习任务没有任何方法来确定它们之间的融合权重，所以无法对二者进行拼接。

2. LINE 未来探索的一个方向是：将一阶邻近度目标函数、二阶邻近度目标函数融合到一个目标函数中，然后使用一个模型来训练。

3. LINE 采用二阶邻近度模型来补充一阶邻近度模型的稀疏性，从而更好的捕捉图的全局结构。

4. DeepWalk 通过随机游走来扩展顶点的领域，类似深度优先搜索；LINE 通过一阶邻近度、二阶邻近度来扩展顶点的领域，采用广度优先搜索。

   另外 DeepWalk 仅适用于无权图，而 LINE 适用于带权图、无权图。

2.1.4 最优化问题

1. 对于目标函数 ，当计算 时我们需要加总所有的顶点 ：

   

   当在每个更新step 中进行计算时，计算代价非常大。

   为解决该问题论文采用负采样的思路：对于每条边 ，将最大化对数概率

   

   替换为：最大化正的定点对 的概率、以及最小化若干对负的定点对的概率：

   

   其中：

   • 为 sigmoid 函数。

   • 第一项为正的顶点对 ，表示观察到的边 的概率。

   • 第二项为采样的若干对负的顶点对的概率，表示负的 组负的顶点对 。其中随机采样的 个顶点的采样概率分布为：

     

     为顶点 的出度。

     从采样概率可知：越 “热门” 的顶点，它被作为负顶点的概率越高。

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

   

   此时 ，使得 取最小值。

   实际上这样的一组解是无意义的。为了避免这样的结果，论文也采用负采样策略：

   

   • 第一项为正的顶点对 ，表示观察到的边 的概率。
   • 第二项为采样的若干对负的顶点对的概率，表示负的 组负的顶点对 。
   • 第三项为采样的若干对负的顶点对的概率，表示负的 组负的顶点对 。

   因为一阶邻近度模型是无向图，因此这里分别以 为顶点、 为顶点独立的进行负采样。

2.1.5 边采样

1. 即使找到了合适的最优化目标，针对超大规模的图的最优化过程也是一项挑战。虽然可以采用随机梯度下降法进行优化，但是真实 Graph 表明：直接采用随机梯度下降法是有问题的，因为很多真实 Graph 是带权重的，而且权重呈现高度分散的特点。

   如：考虑一个单词共现网络，顶点为单词，边的权重为单词之间的共现次数。有的单词共现频次很低，只有一次；有的单词共现频次很高，达到几万甚至几十万次。

   我们采用异步随机梯度下降ASGD 方法来优化负采样的目标函数。在每一个更新step 中，对于每个mini-batch 的每条边有：

   

   可以看到：这里的梯度会乘以边的权重。当边的权重很分散时，优化过程的学习率非常难以选择。

   • 如果选择一个较大的学习率，则它对于权重较小的边的参数更新比较友好，但是对于权重较大的边容易导致梯度爆炸。
   • 如果选择一个较小的学习率，则它对于权重较大的边的参数更新比较友好，但是对于权重较小的边容易导致学习缓慢。

2. 如果所有的边的权重都是相等的（如二元边），则选择合适的学习率是很容易的。因此一种简单的解决方案是：将权重为 的边扩展为 条二元边。

   这种方式虽然解决了问题，但是显著增加了内存需求，尤其是当 很大时。

3. 为解决该问题，可以采用原始边权重成正比的概率从原始边采样，从而得到二元边。然后用二元边进行模型参数更新。这称为边采样 edge-sampling 策略。

   问题是：如何根据边的权重对其进行采样。

   • 朴素方案：设 表示这些边的权重。

     • 首先按计算 ，然后在 之间随机采样一个随机数

     • 观察 落入哪个区间 ，即寻找满足条件的 ：

       

       则对应的边就是被采样的边。

     这种方法需要 时间复杂度来采样一条边，当边的数量 很大时时间代价太大。

   • alias table 方案：采用 alias table 之后，平均采样一条边的平摊时间复杂度为 。

4. 从 alias table 采样一条边平均花费 时间，计算这条边的损失函数的时间复杂度为 ，因此每个更新step 的时间复杂度为 。

   实践过程中我们发现最优化更新step 数量正比于边的数量，为 。因此 LINE 算法的整体时间复杂度为 ，它是边数量的线性关系并且与顶点数量无关。

5. 边采样策略可以在不改变目标函数的情况下，提高随机梯度下降的效率，且不会影响最优化结果。

2.1.6 二阶邻居

1. 当顶点的 degree 很小，即邻居很少的那些顶点，参数更新的机会相对较少因此很难得到其准确的 representation 。尤其是二阶邻近度模型严重依赖于顶点的这些邻居。

   一个简单的解决方案是：通过添加更高阶的邻居（如邻居的邻居）来扩充这些顶点的邻居集合。

   论文中仅考虑二阶邻居，即邻居的邻居。此时顶点 和它的二阶邻居 的权重为：

   

   其中 为顶点 的邻居集合， 为邻居顶点 的 degree 。

   对于顶点 ，我们并不是添加所有的二阶邻居。我们添加部分二阶邻居使得顶点 的扩展邻居集合规模达到某个阈值，如500 。添加时采用 较大的那部分二阶邻居。

2.1.7 新顶点

1. 对于Graph 中新加入的顶点，如何计算其representation ？

   • 如果新顶点 和图中已有的其它顶点产生链接，则可以计算经验分布 。

     根据 目标函数和 目标函数，我们可以直接优化：

     

     从而得到一阶 embedding 向量和二阶 embedding 向量。其中 为顶点 的邻居顶点集合，这些邻居都是图中已有的顶点。

     在优化过程中，已有顶点的 embedding 保持不变，仅需要更新顶点 的 embedding 。

   • 如果新顶点 不与图中已有的其它顶点相连，则必须求助于其它信息，如顶点的文本信息。这也是论文未来探索的方向。

2.2 实验

1. 数据集：

   • 语言网络 Language Network 数据集：英文维基百科抽取的单词共现网络，顶点为单词、边为单词是否共现、边的权重为单词共现频次。

     论文采用窗口大小为5 的滑动窗口进行单词共现统计，窗口内的单词被认为是共现的。共现次数低于 5 次的边被过滤掉。

   • 社交网络 Social Network 数据集：和DeepWalk 一致，这里也采用 Flickr 和 Youtube 数据集。

   • 引文网络 Citation Network 数据集：使用 DBLP 数据集构建的作者引用网络、论文引用网络。

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

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

   

2. 论文将LINE 模型和其它现有的 Graph Embedding 方法进行比较。由于 MDS,IsoMap,Laplacian eigenmap 等方法无法处理大规模网络，因此它们并没有参与比较。

   • Graph Factorization:GF ：构建网络的亲和矩阵 affinity matrix，并通过矩阵分解来获取每个顶点的低维表达。

     GF 方法通过随机梯度下降法进行优化，因此可以处理大型网络。但是它仅适合无向图。

   • DeepWalk：对每个顶点使用从该顶点开始的截断随机游走来获取上下文信息，基于上下文信息建模来获取每个顶点的低维表达。

     DeepWalk 也利用了二阶邻近关系，但是它仅适用于无权网络。

   • LINE-SGD：直接通过SGD 来优化目标函数的 LINE 模型。在优化过程中并没有使用边采样策略。

     该方法有两个变种：

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

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

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

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

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

     需要对拼接后的向量各维度进行加权从而平衡一阶表示向量和二阶表示向量的关系。在监督学习任务中，可以基于训练数据自动得到权重；在无监督学习任务中，无法配置这种权重。

     因此 LINE(1st+2nd) 仅用在监督学习任务中。

3. 参数配置：

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

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

   • 对于 LINE 及其变种，负采样比例 。

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

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

2.2.1 语言网络数据集

1. 语言网络数据集包含200万顶点和10亿条边，评估任务为：

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

     

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

     因此给定单词 a,b,c 的 embedding 向量，该任务的目标是寻找单词 ，使得该单词的 embedding 尽可能与 相似：

     

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

     我们利用文档中所有单词的 embedding 均值来表示文档embedding ，然后利用one-vs-rest 逻辑回归分类器进行分类，并评估分类结果的 Micro-F1 和 Macro-F 指标。

     虽然这种文档表示方式比较粗糙，但是这里的重点是比较不同的单词embedding ，而不是寻找一个良好的文档 embedding 方法。

2. 在维基百科语言网络上的单词类比结果如下表所示，采用了两种方式的类比（语义类比 Semantic、句法类比 Sytactic）。其中：

   • 对GF 方法，边的权重定义为单词共现次数的对数，这比直接采用单词共现次数更好的性能。
   • 对 DeepWalk 方法，尝试使用不同的截断阈值从而将网络权重二元化binarize 。最终当所有边都被保留下来时，模型性能最好。
   • SkipGram 直接从原始维基百科页面内容而不是语言网络来学习词向量。
   • 所有模型都是在单机上运行 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. 在维基百科语言网络上的文本分类结果如下表所示。其中我们分别抽取 10%~90% 的标记样本作为训练集，剩余部分作为测试集。对每一种拆分我们随机执行 10 遍取平均结果。

   结论：

   • GF 方法优于 DeepWalk，因为 DeepWalk 忽略了单词共现次数。
   • LINE-SGD 性能较差，因为边权重波动剧烈所以LINE-SGD 的梯度更新过程非常困难。
   • 采用边采样的 LINE 模型优于 LINE-SGD，因为梯度更新过程中使用边采样能解决边权重波动剧烈带来的学习率选择问题。
   • LINE(1st) + LINE(2nd) 性能明显优于其它所有方法，这表明一阶邻近度和二阶邻近度是互补的。

   

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 数据集非常稀疏，每个顶点的平均degree 小于 5 。对该数据集的评估结果如下表。

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

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

   • LINE(1st) + LINE(2nd) 优于 128 维的DeepWalk ，并逐渐超越256 维的 DeepWalk 。

     这表明一阶邻近度和二阶邻近度是互补的，并能够缓解网络稀疏问题。

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

   一种更合理的方式是采用广度优先搜索策略来扩展每个稀疏顶点的邻居，如二阶邻居策略。下表中，括号中的指标是二阶邻居策略的表现。其中我们对邻居数量少于 1000 的顶点扩展其二阶邻居，直到扩展邻居集合规模达到 1000 。采用二阶邻居策略的网络称作重构网络 reconstructed network 。

   之所以阈值设定为 1000 是因为实验发现：继续添加顶点并不会添加性能。

   • 采用二阶邻居策略之后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 。

   论文首先通过不同的模型来得到 Graph Embedding，然后将顶点的 embedding 向量通过 t-SNE 进行可视化。下图中不同颜色代表不同的领域：红色代表数据挖掘，蓝色代表机器学习，绿色代表计算机视觉。

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

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

     这是因为： DeepWalk 使用基于截断随机游走的方式来生成顶点的邻居，由于随机性这会带来很大的噪声。

     尤其是degree 较高的顶点，因为对于degree 较高的顶点每次随机选择的路径几乎都不同，这使得degree 较高的顶点每次都出现在不同的低频上下文中。

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

   

2.2.5 参数探索及其它

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

   • 图a 给出了 Flickr 网络链接的百分比和LINE 模型性能的关系。选择 Flickr 的原因是它比 YouTube 网络更密集。论文从原始网络中随机采样不同比例的链接从而构建具有不同稀疏性的网络。

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

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

   • 图 b 给出了YouTube 数据集原始网络和二阶邻居策略重构网络中，顶点degree 和顶点性能指标的关系。

     论文将顶点根据 degree 来分组：： 。然后评估每个分组的顶点分类结果指标。

     • 当顶点的 degree 增加时，所有模型的效果都得到提升。
     • 在原始网络中除第一个分组之外，LINE(2nd) 的性能始终优于 LINE(1nd) 。这表明二阶邻近度模型不适用于 degree 较小的点。
     • 在重构网络中，LINE(1st) 和 LINE(2nd) 都得到了改善，尤其是 LINE(2nd) 。
     • 在重构网络中，LINE(2nd) 始终优于 DeepWalk 。

   

2. 论文考察了不同的embedding 维度 和 LINE 模型性能的关系，以及模型的收敛速度。

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

   • 图 b 给出了 LINE 和 DeepWalk 的性能和收敛速度。可以看到：LINE(2nd) 始终优于 LINE(1st) 和 DeepWalk，并且LINE(1st) 和 LINE(2nd) 收敛速度都快于 DeepWalk 。

     由于 batch-size = 1，因此每个sample 需要一个迭代step。

   

3. 最后论文给出了采用边采样和异步随机梯度下降法的LINE 模型的可扩展性 scalability 。

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

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