图的表达

1. Graph Embedding 可用于可视化、结点分类、链接预测 link prediction、推荐等任务中。
2. 网络表示学习 network representation learning :NRL ：将网络的每个顶点编码到一个统一的低维空间中。

一、DeepWalk[2014]

1. network representation 的稀疏性既是优点、也是缺点。稀疏性有助于设计高效的离散算法，但是会使统计学习中的泛化变得更加困难。network 中的机器学习应用（例如 network classification、内容推荐、异常检测、缺失链接预测）必须能够处理这种稀疏性才能生存。

   在论文 《DeepWalk: Online Learning of Social Representations》 中，作者首次将深度学习（无监督特征学习）技术引入到网络分析network analysis 中，而深度学习技术已经在自然语言处理中取得了成功。论文开发了一种算法（DeepWalk），它通过对短short的随机游走流 a stream of short random walks 进行建模，从而学习图顶点的社交表示social representation。

   social representation 是捕获邻域相似性neighborhood similarity 和社区成员关系 community membership 的顶点的潜在特征。这些潜在 representation 在低维的、连续的向量空间中对社交关系social relation 进行编码。

   DeepWalk 将神经语言模型推广为处理由一组随机生成的游走walks 组成的特殊语言。这些神经语言模型已被用于捕获人类语言的语义结构semantic structure 和句法结构syntactic structure ，甚至是逻辑类比logical analogies 。DeepWalk 将图作为输入，并生成潜在 representation 作为输出。

   论文的方法应用于经过充分研究的空手道网络 Karate network ，其结果如下图所示。Karate network 通常以 force-directed 布局呈现，如图 a 所示。图 b 展示了论文方法的输出，其中具有两个潜在维度。除了惊人的相似性之外，我们注意到（图 b）的线性可分部分对应于通过输入图（图 a）中的 modularity maximization 发现的 clusters （以不同顶点颜色表示）。下图中，注意输入图中的社区结构和 embedding 之间的对应关系。顶点颜色表示输入图的 modularity-based clustering 。

   

   为了展示 DeepWalk 在现实世界场景中的潜力，论文评估了它在大型异质图large heterogeneous graph 中具有挑战性的 multi-label network classification 问题的性能。在关系分类 relational classification 问题中，特征向量之间的链接 links 违反了传统的独立同分布的假设。解决这个问题的技术通常使用近似推断技术approximate inference technique 来利用依赖信息dependency information 从而改善分类结果。论文通过学习图的 label-independent representation 来远离这些方法。论文的 representation 质量不受标记顶点选择的影响，因此它们可以在任务之间共享。

   DepWalk 在创建社交维度 social dimensions 方面优于其它潜在 representation 方法，尤其是在标记顶点稀疏的情况下。论文的 representation 可以通过非常简单的线性分类器（例如逻辑回归）获得强大的性能。论文的 representation 是通用的，可以与任何分类方法（包括迭代式推断方法iterative inference method ）结合使用。DeepWalk 实现了所有的这些，同时是一种可简单并行的在线算法。

   论文的贡献如下：

   • 我们引入深度学习作为分析图的工具，从而构建适用于统计建模的鲁棒的 representation 。DeepWalk 学习短的随机游走中存在的结构规律structural regularity 。
   • 我们在多个社交网络上广泛评估了我们在多标签分类任务上的表现。在标签稀疏的情况下，我们展示了显著提高的分类性能。在最稀疏的问题上，我们获得了 Micro F1 的 5% - 10% 的提升。在某些情况下，即使训练数据减少 60%，DeepWalk 的 representation 也可以胜过其它竞争对手。
   • 我们通过使用并行实现 parallel implementation 来构建 web-scale 图（例如 YouTube） 的 representation ，从而证明了我们算法的可扩展性。此外，我们描述了所需的最小修改从而构建我们方法的 streaming 版本。

2. DeepWalk 是一种学习网络中顶点潜在 representation 的新方法。这些潜在representation 在连续向量空间中编码社交关系social relation ，从而很容易被统计模型所利用。DeepWalk 推广了语言模型和无监督特征学习（或深度学习）从单词序列到 graph 的最新进展。

   DeepWalk 使用从截断的随机游走中获得的局部信息，通过将随机游走视为等价的 sentence 来学习潜在 representation 。

   DeepWalk 也是可扩展scalable 的。它是一种在线学习算法online learning algorithm ，可以构建有用的增量结果，并且可以简单地并行化。这些品质使其适用于广泛的现实世界 application，例如 network classification 和异常检测。

3. DeepWalk 与以前的工作之间的主要区别可以总结如下：

   • DeepWalk 学习潜在的 social representation ，而不是计算中心统计量 centrality statistics（如 《Leveraging label-independent features for classification in sparsely labeled networks: An empirical study》）、或者分区统计量 partitioning statistics （如 《Leveraging social media networks for classification》）。
   • DeepWalk 不尝试扩展分类程序本身（通过集体推断 collective inference 如《Collective classification in network data》，或者graph kernel如 《Diffuusion kernels on graphs and other discrete input spaces》 ）。
   • DeepWalk 提出了一种仅使用局部信息的、可扩展的、在线方法。大多数方法需要全局信息、并且是离线的。
   • DeepWalk 将无监督representation learning 应用于图。

   接下来，我们讨论 network classification 和无监督 feature learning 方面的相关工作。

4. 相关工作：

   • 关系学习Relational Learning：关系分类 relational classification （或者集体分类 collective classification）方法使用数据 item 之间的链接 links 作为分类过程的一部分。集体分类问题中的精确推断 exact inference 是 NP-hard 问题，其解决方案主要集中在近似推断算法。这些近似推断算法可能无法保证收敛。

     与我们的工作最相关的关系分类算法包括：学习clusters（《Leveraging relational autocorrelation with latent group models》）、在附近节点之间添加边（《Using ghost edges for classification in sparsely labeled networks》）、使用 PageRank（《Semi-supervised classification of network data using very few labels》）、通过扩展关系分类来考虑额外的特征(《Multi-label relational neighbor classification using social context features》)，通过这些方法从而合并社区信息community information 。

     我们的工作采取了截然不同的方法。我们提出了一种学习网络结构 representation 的程序，而不是新的近似推断算法，然后可以由现有的推断程序inference procedure （包括迭代式推断程序）来使用。

     人们还提出了很多从图中生成特征的技术。和这些技术相比，我们将特征创建过程构建为 representation learning 问题。

     人们也 提出了 graph kernel （《Graph kernels》） ，从而将关系数据用作分类过程的一部分。但是，除非近似（《Fast random walk graph kernel》），否则它的速度非常慢。我们的方法与 graph kernel 是互补的：我们没有将结构编码为核函数 kernel function 的一部分，而是学习一种 representation，从而允许该 representation 直接用于任何分类方法的特征。

   • 无监督特征学习 Unsupervised Feature Learning：人们已经提出分布式 representation learning 来建模概念之间的结构关系structural relationship 。这些 representation 通过反向传播和梯度下降来进行训练。由于计算成本和数值不稳定，这些技术被放弃了十几年。

     最近，分布式计算允许训练更大的模型，并且用于无监督学习的数据出现增长。分布式representation 通常通过神经网络进行训练，这些神经网络在计算机视觉、语音识别、自然语言处理等不同领域取得了进步。

5. DeepWalk 可以挖掘图 $G$ 的局部结构，但是无法挖掘图 $G$ 的整体结构。

1.1 模型

1.1.1 问题定义

1. 考虑社交网络成员的分类问题。正式地，令 $G=(V,E)$ ，其中 $V$ 为图中所有的顶点（也称为网络的成员 member ），$E \sube (V\times V)$ 为所有的边。给定一个部分标记的 social network $G_L = ( V, E, X, Y)$ ，其中：

   • 特征 $X\in \mathbb R^{|V|\times S}$ ，$S$ 为属性空间的维度，$|V|$ 为顶点数量。
   • $Y\in \mathbb R^{|V|\in |\mathcal Y|}$，$\mathcal Y$ 为 label 空间，$|\mathcal Y |$ 为分类类别数量。

   在传统的机器学习分类 setting 中，我们的目标是学习将 $X$ 的元素映射到标签集合 $Y$ 的假设hypothesis $H(\cdot)$ 。在我们的例子中，我们可以利用嵌入在 $G$ 结构中的样本依赖性 example dependence 的重要信息，从而实现卓越的性能。在文献中，这被称作关系分类relational classification（或者集体分类 collective classification ）问题。

2. 关系分类的传统方法提出将问题作为无向马尔科夫网络undirected Markov network 中的推断 inference，然后使用迭代式近似推断算法（例如迭代式分类算法 《Iterative classification in relational data》、吉布斯采样《Stochastic relaxation, gibbs distributions, and the bayesian restoration of images》、或者标签松弛算法《On the foundations of relaxation labeling processes》）来计算给定网络结构下标签的的后验分布。

   我们提出了一种不同的方法来捕获网络拓扑信息network topology information 。我们没有混合 label 空间从而将其视为特征空间的一部分，而是提出了一种无监督方法，该方法学习了捕获独立于 label 分布的、图结构的特征。

   结构表示 structural representation 和标记任务 labeling task 的这种分离避免了迭代式方法中可能发生的级联错误 cascading error 。此外，相同的 representation 可以用于与该网络有关的多个分类任务（这些分类任务有各自不同的 label）。

   我们的目标是学习 $\mathbf X_E\in \mathbb R^{| V|\times d}$ ，其中 $d$ 是一个较低的潜在维度。这些低维 representation 是分布式的，意味着每个社交概念 social concept 都由维度的某个子集来表达，每个维度都有助于低维空间所表达的一组社交概念的集合。

   使用这些结构特征structural feature ，我们将扩充属性空间从而帮助分类决策。这些结构特征是通用的，可以与任何分类算法（包括迭代式方法）一起使用。然而，我们相信这些特征的最大效用是：它们很容易与简单的机器学习算法集成。它们在现实世界的网络中可以适当地 scale，正如我们在论文中所展示的。

1.1.2 基础知识

1. 我们寻求具有以下特性的 learning social representation：

   • 适应性 adaptability：真实的社交网络在不断演变，新的社交关系不应该要求一遍又一遍地重新训练整个网络。
   • 社区感知 community aware：潜在维度之间的距离应该能够代表评估网络成员之间社交相似性social similarity 的指标。
   • 低维low dimensional：当标记数据稀疏时，低维模型泛化效果更好，并且加快收敛和推断速度。
   • 连续 continuous：除了提供社区成员community membership 的精细的视图之外，continuous representation 在社区之间具有平滑的决策边界，从而允许更鲁棒的分类。

   我们满足这些要求的方法从短期随机游走的 stream 中学习顶点的 representation，这是最初为语言建模而设计的优化技术。在这里，我们首先回顾随机游走和语言建模language modeling的基础知识，并描述了它们的组合如何满足我们的要求。

2. 随机游走random walk ：我们将以顶点 $v_i$ 为 root 的随机游走表示为 $\mathcal W_{v_i}$ 。$\mathcal W_{v_i}$ 是一个随机游走过程，其中包含随机变量 $\left(\mathcal W_{v_i}^1,\mathcal W_{v_i}^2,\cdots,\mathcal W_{v_i}^k\right)$ 。 $\mathcal W_{v_i}^k$ 是一个顶点，它是从顶点 $\mathcal W_{v_i}^{k-1}$ 的邻居中随机选中的。

   随机游走已被用作内容推荐content recommendation 和社区检测community detection 中各种问题的相似性度量similarity measure 。随机游走也是一类输出敏感算法output sensitive algorithm 的基础，这类算法使用随机游走来计算局部社区结构信息local community structure ，并且计算时间复杂度为 input graph 规模的亚线性sublinear 。

   正是这种与局部结构的联系促使我们使用短的随机游走流stream of short random walks 作为从网络中提取信息的基本工具。除了捕获社区信息之外，使用随机游走作为我们算法的基础还为我们提供了另外两个理想的特性：

   • 首先，局部探索很容易并行化。多个随机游走器 random walkers （在不同的线程、进程、或者机器中）可以同时探索同一个图的不同部分。
   • 其次，依靠从短的随机游走中获得的信息，可以在不需要全局重新计算的情况下适应图结构的微小变化。我们可以使用新的随机游走，从图变更的区域游走到整个图，从而以亚线性时间复杂度来更新已经训练好的模型。

3. 幂律power law 分布：选择在线随机游走作为捕获图结构的原语 primitive 之后，我们现在需要一种合适的方法来捕获这些图结构信息。

   如果连通图的 degree 分布遵循幂律分布 power law（也叫作 Zipf 定律），那么我们观察到顶点出现在短随机游走中的频率也遵循幂律分布。自然语言中的单词遵循类似的分布，语言模型language modeling 技术解释了这种分布行为。为了强调这种相似性，我们在下图中展示了两个不同的幂律分布：第一个来自一个图上的一系列短随机游走，第二个来自于英文维基百科的 100,000 篇文章的文本。图 a 给出了short random walk 中，顶点出现频次的分布。图 b 给出了英文维基百科的 10 万篇文章中，单词的频次分布。

   

   我们工作的一个核心贡献是这样的一种思想：用于建模自然语言（其中单词频率遵循幂律分布）的技术也可以复用于建模网络中的社区结构。

   接下来我们将回顾语言建模中不断发展的工作，并将其转换为学习满足我们标准的顶点 representation 。

1.1.3 语言模型

1. 语言模型的目标是估计特定单词序列在语料库 corpus 中出现的可能性。正式地，给定一个单词序列 $\mathcal S=(w_0,w_1,\cdots,w_n)$，其中 $w_i\in \mathbb V$（$\mathbb V$ 为词典 vocabulary），我们希望在整个训练语料库上最大化 $\text{Pr}(w_n\mid w_0,w_1,\cdots,w_{n-1})$ 。

   最近在 representation learning 方面的工作聚焦于使用概率神经网络probabilistic neural network 来构建单词的 general representation，从而将语言建模的范围扩展到其原始目的之外。

2. 在这项工作中，我们提出了语言建模的泛化，以通过短随机游走流stream 来探索图。这些随机游走可以被认为是一种特殊语言的短句 short sentence 和短语 short phrase。我们进行直接的类比，从而在随机游走中，给定到目前为止访问的所有顶点序列来估计观察到顶点 $v_i$ 的可能性，即 $\text{Pr}(v_i\mid (v_1,v_2,\cdots,v_{i-1}))$ 。

   我们的目标是学习潜在 representation，而不仅仅是节点共现node co-occurrence 的概率分布，因此我们引入一个映射函数 $\Phi: V \rightarrow \mathbb R^{| V|\times d}$ 。该映射函数 $\Phi(\cdot)$ 将图中每个顶点 $v$ 映射到一个潜在的 social representation 。

   即：我们想要的是顶点 representation，而不是预估这个随机游走序列出现的概率。

   实际上，我们使用 free parameters 的矩阵 $\mathbf\Phi\in \mathbb R^{|V|\times d}$ 来表达 $\Phi(\cdot)$，这在稍后将被用作我们的 $\mathbf X_E$ 。然后，问题变成了似然估计：

   $$\text{Pr}(v_i\mid (\Phi(v_1),\Phi(v_2),\cdots,\Phi(v_{i-1})))$$

   然而，随着游走序列长度的增加，计算这个目标函数变得不可行。

   因为 sentence 越长，它出现的频次越低，样本过于稀疏。

3. 最近，在语言模型中的放松条件使得这个预测问题得到了解决。

   • 首先，我们不是使用上下文来预测缺失单词 missing word，而是使用一个单词来预测上下文。
   • 其次，上下文由出现在给定单词左侧和右侧的单词组成。
   • 最后，我们消除了对问题的顺序约束 ordering constraint 。即，模型需要最大化任何单词出现在上下文中的概率，而无需知道上下文与目标单词的偏移量。

   应用到顶点建模中，这得到了优化问题：

   $$\min_{\mathbf \Phi} - \log \text{Pr}(\{v_{i-w},\cdots,v_{i-1},v_{i+1},\cdots,v_{i+w}\}\mid \Phi(v_i))$$

   其中 $w$ 为上下文窗口尺寸。

   我们发现这些放松条件对于 social representation learning 是特别理想的。

   • 首先，顺序独立性假设 order independence assumption 更好地捕获了随机游走的 nearness 的 sense。
   • 其次，这种松弛条件对于通过构建一大批小模型来加速训练非常有用，因此一次给定一个顶点。

   解决上式中的优化问题将得顶点representation，这些 representation 捕获了顶点之间在局部图结构local graph structure 中的相似性。具有相似邻域的顶点将获得相似的 representation（编码了 co-citation 相似性），并允许对机器学习任务进行泛化。

4. 通过结合截断的随机游走和神经语言模型，我们制定了一种满足我们所有期望特性的方法。

   • 该方法生成低维的社交网络 representation，并存在于连续向量空间中。
   • 该方法生成的 representation 对社区成员的潜在形式 latent form 进行编码。
   • 并且，由于该方法输出有用的 intermediate representation ，因此它可以适应不断变化的网络拓扑结构。

1.1.4 DeepWalk

1. 与任何语言建模算法一样，DeepWalk 唯一需要的输入是语料库和词表 $\mathbb V$ 。DeepWalk 将一组截断的短随机游走视为语料库，将图的顶点视为词表（$\mathbb V = V$） 。虽然在训练之前知道随机游走中顶点集合 $V$ 和顶点的频率分布是有益的，但是DeepWalk 在不知道顶点集合的情况下也可以工作。

2. DeepWalk 算法主要由两部分组成：随机游走生产器、更新过程。

   • 随机游走生成器random walk generator ：以图 $G$ 作为输入并均匀随机采样一个顶点 $v_i$ 作为随机游走 $\mathcal W_{v_i}$ 的 root 。随机游走从最近访问的顶点的邻域中均匀采样，直到游走序列长度达到最大长度 $t$ 。

     虽然在我们的实验中，随机游走序列的长度设置为固定的（固定为 $t$ ），但是理论上没有限制它们都是相同的长度。这些随机游走可能会重启（即返回 root 的传送概率 teleport probability），但是我们的初步结果并为表明使用重启能带来任何优势。

   • 更新过程：基于 SkipGram 语言模型来更新参数 $\mathbf\Phi$ 。SkipGram 是一种语言模型，可最大化在一个句子中出现在窗口 $w$ 内的单词之间的共现概率。

     在随机游走中，对于出现在窗口 $w$ 中的所有上下文，我们最大化给定当前顶点 $v_j$ 的 representation 的条件下，上下文顶点 $u_k$ 出现的概率。

3. DeepWalk 算法：

   • 输入：

     • 图 $G( V, E)$
     • 上下文窗口尺寸 $w$
     • embedding size $d$
     • 每个节点开始的随机游走序列数量 $\gamma$
     • 每条随机游走序列长度 $t$

   • 输出：顶点 representation 矩阵 $\mathbf \Phi\in \mathbb R^{| V|\times d}$

   • 算法步骤：

     • representation 初始化：从均匀分布中采样，得到初始的 $\mathbf\Phi$ 。

     • 从 $V$ 构建一颗二叉树 binary tree $T$

       建立二叉树是为了后续 SkipGram 算法采用 Hierarchical Softmax

     • 遍历，$i=0,\cdots,\gamma$，遍历过程：

       • 随机混洗顶点：$\mathcal O = \text{Shuffle}( V)$

         每次遍历的开始，随机混洗顶点。但是这一步并不是严格要求的，但是它可以加快随机梯度下降的收敛速度。

       • 对每个顶点 $v_i\in \mathcal O$：

         • 利用随机游走生成器生成随机游走序列：$\mathcal W_{v_i} = \text{RandomWalk}( G,v_i,t)$
         • 采用 SkipGram 算法来更新顶点的representation：$\text{SkipGram}(\mathbf\Phi,\mathcal W_{v_i},w)$

4. SkipGram 算法：

   • 输入：

     • 当前的顶点 representation矩阵 $\mathbf \Phi\in \mathbb R^{| V|\times d}$
     • 单条随机游走序列 $\mathcal W_{v_i}$
     • 上下文窗口尺寸 $w$
     • 学习率 $\alpha$

   • 输出：更新后的顶点 representation矩阵 $\mathbf \Phi\in \mathbb R^{| V|\times d}$

   • 算法步骤：

     • 对每个顶点 $v_j\in \mathcal W_{v_i}$：

       • 对窗口内每个顶点 $u_k\in \mathcal W_{v_i}[j-w:j+w]$：

         $$J(\mathbf\Phi) = -\log \text{Pr}(u_k\mid \Phi(v_j))\\ \mathbf\Phi = \mathbf\Phi - \alpha\times \nabla_{\mathbf\Phi} J$$

5. Hierarchical Softmax： 计算 $\text{Pr}(u_k\mid \Phi(v_j))$ 是不容易的，因为这个概率的分母（归一化因子）计算代价太高（计算复杂度为 $O(|V|)$）。如果我们将顶点分配给二叉树的叶节点，那么预测问题就变为最大化树中特定路径的概率。如果到顶点 $u_k$ 的路径由一系列树节点 $(b_0,b_1,\cdots,b_{\lceil \log | V|\rceil})$ （$b_0$ 为 root，$b_{\lceil \log | V|\rceil}=u_k$）标识，则有：

   $$\text{Pr}(u_k\mid \Phi(v_j)) = \prod_{l=1}^{\lceil \log | V|\rceil}\text{Pr}(b_l\mid \Phi(v_j))$$

   现在 $\text{Pr}(b_l\mid \Phi(v_j))$ 可以通过分配给节点 $b_l$ 的父节点的二分类器来建模。这降低了计算 $\text{Pr}(u_k\mid \Phi(v_j))$ 的复杂度，计算复杂度从 $O(| V|)$ 降低到 $O(\log | V|)$ 。

   我们可以通过为随机游走中的高频顶点分配树中更短的路径来进一步加快训练过程。霍夫曼编码用于减少树中高频元素的访问次数。

6. DeepWalk 模型参数规模为 $O(d|V|)$，并且使用随机梯度下降来优化这些参数。导数是通过反向传播算法来估计的。SGD 的学习率在最初时设置为 0.025，然后随着目前为止看到的顶点数量呈线性下降。

7. DeepWalk 算法整体如下图所示。

   • 图 a：短随机游走序列的生成过程。

   • 图 b：在随机游走 $\mathcal W_{v_4}$ 上滑动一个长度为 $2w+1$ 的窗口，将中心顶点 $v_1$ 映射到它的 representation $\Phi(v_1)$ 。

   • 图 c：Hierarchical Softmax 在对应于从 root 到 $v_3$ 的路径上的概率序列来分解 $\text{Pr}(v_3\mid \Phi(v_1))$ 。$\text{Pr}(v_5\mid \Phi(v_1))$ 也是类似的。

     representation $\mathbf\Phi$ 被更新从而最大化中心顶点 $v_1$ 与它的上下文 $\{v_3,v_5\}$ 共现的概率。

   

1.1.5 并行化

1. 社交网络随机游走中的顶点频率分布和语言中的单词分布都遵循幂律分布。这会导致低频顶点的长尾效应，因此，对 $\mathbf\Phi$ 的更新本质上将是稀疏的（即，同时对同一个顶点进行更新的概率很低）。 这将允许我们在多个 worker 的情况下使用随机梯度下降的异步版本 ASGD。

   鉴于我们的更新是稀疏的，并且我们没有利用锁来访问模型共享参数，ASGD 将实现最佳收敛速度。虽然我们在单台机器上使用多线程进行实验，但是已经证明了 ASGD 具有高度可扩展性，可用于非常大规模的机器学习。

   下图展示了并行化 DeepWalk 的效果。结果表明：随着我们将 worker 数量增加到 8，处理 BlogCatalog 和 Flickr 网络的加速是一致的。结果还表明，与串行执行 DeepWalk 相比，并行化 DeepWalk 的预测性能没有损失。

   

1.1.6 变体

1. 这里我们讨论我们方法的一些变体，我们认为这些变体可能会引起人们的兴趣。

2. 流式 streaming：我们方法的一个有趣变体是流式方法，它可以在不了解整个图的情况下实现。在这个变体中，来自图中的短随机游走直接传递给 representation learning 代码，并直接更新模型。

   这里需要对学习过程进行一些修改：

   • 首先，不再使用衰减的学习率。相反，我们可以将学习率 $\alpha$ 初始化为一个小的常量。这需要更长的时间来学习，但是在某些 application 中可能是值得的。
   • 其次，我们不能再构建参数树 tree of parameters。如果 $V$ 的基数 cardinality 是已知的（或者有界），我们可以为这个最大值构建 Hierarchical Softmax tree。当首次看到顶点时，可以将它分配给剩余的叶节点之一。如果我们有能力估计顶点分布的先验，我们仍然可以使用霍夫曼编码来减少高频元素的访问次数。

3. 非随机的游走：有些图是用户与一系列元素（如网站上页面的导航）交互的副产品而创建的。当通过这种非随机游走的 stream 来创建图时，我们可以使用这个过程直接为建模阶段提供游走数据。以这种方式采样的图不仅会捕获与网络结构相关的信息，还会捕获与路径遍历频率相关的信息。

   以我们的观点来看，这个变体还包括语言建模。sentence 可以被视为经过适当设计的语言网络的、有目的的游走，而像 SkipGram 这样的语言模型旨在捕获这种行为。

   这种方法可以与流式变体结合使用，从而在不断演化的网络上训练特征，而无需显式地构建整个图。使用这种技术维护的 representation 可以实现 web-scale 的分类，而无需处理 web-scale 图的麻烦。

1.2 实验

1. 数据集：

   • BlogCatalog 数据集：由博客作者提供的社交关系网络。标签代表作者提供的主题类别。
   • Flickr 数据集：Flickr网站用户之间的关系网络。标签代表用户的兴趣组，如“黑白照片”。
   • YouTube 数据集：YouTube 网站用户之间的社交网络。标签代表用户的视频兴趣组，如“动漫、摔跤”。

   

2. baseline 方法：为了验证我们方法的效果，我们和一些 baseline 方法进行比较。

   • 谱聚类 SpectralClustering：从图 $G$ 的 normalized graph Laplacian 矩阵 $\tilde{\mathbf L}$ 中计算到的 $d$ 个最小的特征向量，构成图的representation。使用 $\tilde{\mathbf L}$ 的特征向量隐含地建设图割graph cuts 对分类有用。

   • Modularity：从图 $G$ 的 Modularity $\mathbf B$ 计算得到 top-d 个特征向量，构成了图的representation。$\mathbf B$ 的特征向量编码了关于 $G$ 的modular graph partition 信息。使用它们作为特征假设 modular graph partition 对于分类有用。

   • EdgeCluster：基于 k-means 聚类算法对图 $G$ 的邻接矩阵进行聚类。事实证明它的性能可以和 Modularity 相比，并且可以扩展到那些超大规模的图，这些图太大而难以执行谱分解spectral decomposition 。

   • wvRN： weighted-vote Relational Neighbor 是一个关系分类器 relational classier 。给定顶点 $v_i$ 的邻居 $\mathcal N_i$，wvRN 通过邻居结点的加权平均来预估 $P(y_i\mid \mathcal N_i)$：

     $$P (y_i\mid \mathcal N_i) = \frac 1Z \sum_{v_j\in \mathcal N_i} w_{i,j}P (y_j\mid \mathcal N_j)$$

     其中 $Z$ 为归一化系数。

     该方法在实际网络中表现出惊人的良好性能，并被推荐为优秀的关系分类relational classification 的 baseline。

   • Majority：选择训练集中出现次数最多的标签作为预测结果（所有样本都预测成一个值）。

3. 评估指标：对于多标签分类问题 multilabel classication，我们采用 Macro-F1 和 Micro-F1 作为评估指标。

   • Macro-F1 ：根据整体的混淆矩阵计算得到的 $F_1$ 值。
   • micro-F1：先根据每个类别的混淆矩阵计算得到各自的 $F_1$ 值，然后对所有 $F_1$ 值取平均。

   另外我们采用模型提取的特征训练 one-vs-rest 逻辑回归分类器，根据该分类器来评估结果。

   我们随机采样一个比例为 $T_R$ 的带标签顶点作为训练集，剩余标记节点作为测试集。我们重复该过程 10 次，并报告 Macro-F1 的平均性能和 Micro-F1 的平均性能。

   注意，DeepWalk 是无监督的 representation learning 方法，因此训练过程是无需 label 数据的。这里的标记数据是在无监督学习之后，利用学到的顶点 representation 进行有监督分类，分类算法为逻辑回归，从而评估顶点 representation 的效果。

4. 实验配置：

   • 对所有模型，我们使用由 LibLinear 实现的 one-vs-rest 逻辑回归进行分类。
   • DeepWalk的超参数为 $\gamma = 80, w=10, d=128$ 。
   • 对于 SpectralClustering, Modularity, EdgeCluster 等方法，我们选择 $d=500$ 。

1.2.1 实验结果

2. BlogCatalog数据集：我们评估 $T_R= 10\% \sim 90\%$ 的结果。结果如下表，粗体表示每一列最佳结果。

   结论：

   • DeepWalk 性能始终优于 EdgeCluster,Modularity,wvRN 。

     事实上当 DeepWalk 仅仅给出 20% 标记样本来训练的情况下，模型效果优于其它模型 90% 的标记样本作为训练集。

   • 虽然 SpectralClustering 方法更具有竞争力，但是当数据稀疏时 DeepWalk 效果最好：对于 Macro-F1 指标，$T_R \le 20\%$ 时 DeepWalk 效果更好；对于Micro-F1 指标，$T_R\le 60\%$ 时 DeepWalk 效果更好。

   • 当仅标记图中的一小部分时，DeepWalk 效果最好。因此后面实验我们更关注稀疏标记图sparsely labeled graph 。

3. Flickr 数据集：我们评估 $T_R= 1 \% \sim 10\%$ 的结果。结果如下表，粗体表示每一列最佳结果。结论与前面的实验一致。

   • 在 Micro-F1 指标上，DeepWalk 比其它基准至少有 3% 的绝对提升。
   • 在 Micro-F1 指标上，DeepWalk 只需要 3% 的标记数据就可以打败其它方法 10% 的标记数据，因此 DeepWalk 的标记样本需求量比基准方法少 60% 。
   • 在 Macro-F1 指标上，DeepWalk 性能接近 SpectralClustring，击败了所有其它方法。

   

4. YouTube 数据集：我们评估 $T_R= 1 \% \sim 10\%$ 的结果。结果如下表，粗体表示每一列最佳结果。

   由于 YouTube 规模比前面两个数据集大得多，因此我们无法运行两种基准方法 SpecutralClustering, Modularity 。

   • DeepWalk 性能远超 EdgeCluster 基准方法：

     • 当标记数据只有 1% 时，DeepWalk 在 Micro-F1 指标上相对 EdgeCluster 有 14% 的绝对提升，在 Macro-F1 指标上相对 EdgeCluster 有 10% 的绝对提升。
     • 当标记数据增长到 10% 时，DeepWalk 提升幅度有所下降。DeepWalk 在 Micro-F1 指标上相对 EdgeCluster 有 3% 的绝对提升，在 Macro-F1 指标上相对 EdgeCluster 有 4% 的绝对提升。

   • DeepWalk 能扩展到大规模网络，并且在稀疏标记环境中表现出色。

   

1.2.2 参数敏感性

1. 为评估超参数的影响，我们在 Flickr 和 BlogCatalog 数据集上进行实验。我们固定窗口大小 $w=10$ 和游走长度 $t=40$ 。然后我们改变潜在维度 $d$ 、每个顶点开始的随机游走数量 $\gamma$、可用的训练数据量 $T_R$ ，从而确定它们对于网络分类性能的影响。

2. 考察不同 $d$ 的效果：

   • 图 a1 和 图 a3 考察不同 $d$ 和不同 $T_R$ 的效果。Flickr 和 BlogCatalog 数据集上模型的表现一致：模型最佳尺寸 $d$ 取决于训练样本的数量。

     注意：Flickr 的 1% 训练样本和 BlogCatalog 的 10% 训练样本，模型的表现差不多。

   • 图 a2 和图 a4 考察不同 $d$ 和不同 $\gamma$ 的效果。在不同 $\gamma$ 取值上，模型性能对于不同 $d$ 的变化比较稳定。

     • 从 $\gamma = 30$ 开始继续提高 $\gamma$ 时模型的效果提升不大，因此 $\gamma = 30$ 几乎取得最好效果。继续提升效果，计算代价上升而收益不明显。

• 不同的数据集中，不同 $\gamma$ 值的性能差异非常一致，尽管 FLICKR 包含边的数量比 BLOGCATALOG 多一个数量级。

这些结论表明：我们的方法可以得到各种size 的有用模型。另外，模型性能取决于模型看到的随机游走数量，模型的最佳维度取决于可用的训练样本量。

3. 考察不同 $\gamma$ 的影响。图 b1 和 b3 考察不同 $d$ 的效果，图 b2 和 b4 考察了不同 $T_R$ 的效果。

   实验结果表明，它们的表现比较一致：增加 $\gamma$ 时开始可能有巨大提升，但是当 $\gamma \gt 10$ 时提升效果显著下降。

   这些结果表明：仅需要少量的随机游走，我们就可以学习有意义的顶点潜在表示。

   

二、LINE[2015]

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 模型具有很好的可扩展性（即并行度）。

   

三、GraRep[2015]

1. 在许多实际问题中，信息通常是使用图来组织的。例如，在社交网络研究中，基于社交图 social graph 将用户分类为有意义的社交群组 social group 在很多实际 application 中有用，例如用户搜索 user search、定向广告 targeted advertising、以及推荐 recommendation 。因此，从图中准确地学习有用的信息至关重要。一种策略是学习图的 graph representation：图中的每个顶点都用一个低维向量来表达，这个低维向量可以准确地捕获图所传达的语义信息semantic information 、关系信息 relational information 、以及结构信息 structural information 。

   最近，人们对从数据中学习 graph representation 的兴趣激增。例如，最近的一个模型 DeepWalk 使用均匀采样（也称作截断的随机游走truncated random walk ）将图结构转换为由顶点组成的线性序列的样本集合。SkipGram 模型最初设计用于从线性序列中学习 word representation，也可用于从此类样本（即顶点组成的线性序列的样本）中学习顶点的 representation 。尽管这种方法在经验上是有效的，但是人们并不清楚在学习过程中所涉及的、图上定义的、确切exact 的损失函数是什么。

   在论文 《GraRep: Learning Graph Representations with Global Structural Information》 中，作者首先提出了在图上定义的 SkipGram 模型的显式损失函数。论文表明：本质上，我们可以使用 SkipGram 模型以不同的 $k$ 值来捕获图中每个顶点与其 k-step 邻居之间的 k-step 关系（$k=1,2,\cdots$）。 SkipGram 模型的一个缺陷是：它将所有这些 k-step 关系信息投影到一个公共子空间中。论文认为，这种简单的处理可能会导致潜在的问题。通过在不同的子空间中保存不同的 k-step 关系信息，论文提出的模型 GraRep 克服了上述限制。

   最近人们提出的另一个工作是 LINE，它有一个损失函数来同时捕获 1-step 局部关系信息 local relational information 和 2-step 局部关系信息。为了捕获此类局部信息中的某些复杂关系，他们还从此类数据中学习非线性变换（LINE 用到了 sigmoid 函数，但是本质上 LINE 是广义线性函数）。虽然他们的模型不能很容易地扩展到捕获 k-step （$k\gt 2$）关系信息来学习他们的 graph representation，但是他们提出了一个重要策略来提高模型的效果：对于 degree 较小的顶点，考虑高阶邻域。这一策略在某种程度上隐式地将某些 k-step 信息捕获到他们的模型中。GraRep 的作者相信：对于不同的 k 值，不同顶点之间的 k-step 关系型信息揭示了与图相关的、有用的全局结构信息，并且在学习良好的 graph representation 时显式地充分利用这一点至关重要。

   在论文 《GraRep: Learning Graph Representations with Global Structural Information》 中，作者提出了 GraRep，这是一种为知识管理 knowledge management 学习 graph representation 的新模型。该模型通过操作在图中定义的、不同的全局转移矩阵global transition matrix，直接从图中的顶点中捕获具有不同 $k$ 值的、不同 k-step 关系信息，而不涉及缓慢 slow 的、复杂 complex 的采样过程。与现有工作不同， GraRep 模型定义了不同的损失函数来捕获不同的 k-step 局部关系信息（即不同的 $k$ ）。论文使用矩阵分解 matrix factorization 技术优化每个模型，并通过组合从不同模型中学到的不同 representation 来构建每个顶点的全局 representation 。这种学到的全局 represetnation 可以用作下游任务的特征。

   论文对 GraRep 模型进行了正式的处理 formal treatment ，并展示了 GraRep 模型与之前几个模型之间的联系。论文还通过实验证明了学到的 representation 在解决几个现实世界问题中的有效性。具体而言，论文对语言网络聚类任务、社交网络多标签分类任务、以及引文网络可视化任务进行了实验。在所有这些任务中，GraRep 优于其它 graph representation 方法，从而证明了 GraRep 学到的全局 representation 可以有效地用作聚类、分类、可视化等任务的特征。并且， GraRep 可以简单地并行化。

   论文贡献如下：

   • 论文引入了一种新模型来学习图上顶点的潜在 representation，该模型可以捕获与图相关的全局结构信息。

   • 论文从概率的角度提供了对 DeepWalk 中用于学习 graph representation 的均匀采样方法的理解，该均匀采样方法将图结构转换为线性序列。

     此外，论文在图上显式定义了 DeepWalk 的损失函数，并将其扩展为支持加权图。

   • 论文正式分析了带有负采样 SkipGram 模型（skip-gram model with negative sampling: SGNS）相关的缺陷。论文的模型定义了一个更准确 accurate 的损失函数，该损失函数允许集成不同局部关系信息的非线性组合。

2. 相关工作：

   • 线性的序列representation方法 Linear Sequence Representation Method：由单词的 stream 组成的自然语言语料库可以视为一种特殊的图结构，即线性链linear chain 。目前，学习 word representation 有两种主流方法：神经嵌入neural embedding 的方法、基于矩阵分解matrix factorization based 的方法。

     • 神经嵌入方法采用固定长度的滑动窗口捕获当前单词的 context words。人们提出了像 SkipGram 这样的模型，这些模型提供了一种学习 word representation 的有效方法。虽然这些方法可能会在某些任务上产生良好的性能，但是它们不能很好地捕获有用的信息，因为它们使用独立的、局部的上下文窗口，而不是全局共现计数 global co-occurrence count 。

     • 另一方面，矩阵分解方法可以利用全局统计。先前的工作包括潜在语义分析 Latent Semantic Analysis: LSA，该方法分解 term-document 矩阵从而产生潜在语义representation。

       《Producing high-dimensional semantic spaces from lexical co-occurrence》 提出了 Hyperspace Analogue to Language: HAL，它分解一个 word-word 共现计数矩阵来生成 word representation。

       《Extracting semantic representations from word co-occurrence statistics: A computational study》 提出了用于学习 word representation 的、shifted positive Pointwise Mutual Information: PMI 矩阵的矩阵分解，并表明带负采样的 SkipGram 模型（Skip-Gram model with Negative Sampling: SGNS）可以视为隐式的这样的一个矩阵。

   • 图表示Graph Representation 方法：存在几种学习低维 graph representation 的经典方法，如多维缩放 multidimensional scaling: MDS、IsoMap、LLE、Laplacian Eigenmaps。

     最近，《Relational learning via latent social dimensions》 提出了学习图的潜在 representation 向量的方法，然后可以用于社交网络分类。

     《Distributed large-scale natural graph factorization》 提出了一种图分解方法，该方法使用随机梯度下降来优化大型图中的矩阵。

     《Deepwalk:Online learning of social Representations》 提出了DeepWalk 方法，该方法通过使用截断的随机游走算法将图结构转换为多个线性的顶点序列，并使用 SkipGram 模型生成顶点的 representation。

     《Line: Large-scale information network embedding》 提出了一种大规模信息网络的 embedding ，它优化了一个损失函数从而可以在学习过程中同时捕获 1-step 关系信息和 2-step 关系信息。

3.1 模型

3.1.1 图及其 Representation

1. 给定一个图 $G=(V,E)$，其中 $V=\{v_1,v_2,\cdots,v_{|V|}\}$ 为顶点集合，$|V|$ 为顶点数量，$E=\{e_{i,j}\}$ 为边集合。路径 path 定义为连接一个顶点序列的边序列。

   • 邻接矩阵：定义邻接矩阵为 $\mathbf S$ 。

     • 对于无权图，如果顶点 $v_i$ 到 $v_j$ 之间存在边，那么 $S_{i,j} = 1$，否则 $S_{i,j} = 0$ 。
     • 对于带权图，$S_{i,j}$ 为顶点 $v_i$ 到 $v_j$ 之间边的权重。

     尽管边的权重可以为负值，但是这里我们仅考虑正的权重。

   • 度矩阵degree matrix：定义度矩阵 degree matrix 为 $\mathbf D$ ，其中：

     $$D_{i,j} =\begin{cases} \sum_{p} S_{i,p},& i = j\\ 0,&i\ne j \end{cases}$$

   • 转移概率矩阵 probability transition matrix：假设我们想要捕获从一个顶点到另一个顶点的转移，并假设顶点 $v_i$ 转移到顶点 $v_j$ 的概率正比于 $S_{i,j}$ ，则定义转移概率矩阵 probability transition matrix： $\mathbf A = \mathbf D^{-1}\mathbf S$ 。其中 $A_{i,j}$ 定义了从顶点 $v_i$ 经过一步转移到顶点 $v_j$ 的概率，因此也称为一阶转移概率矩阵。显然 $\mathbf A$ 可以认为是对 $\mathbf S$ 按 ”行“ 进行的归一化。

2. 带全局结构信息的 graph representation：给定一个图 $G$，学习带全局结构信息的 graph representation的任务旨在学习图的全局 represetation 矩阵 $\mathbf W\in \mathbb R^{|V|\times d}$ ，其中第 $i$ 行 $\mathbf{\vec w}_i\in \mathbb R^d$ 为图 $G$ 中顶点 $v_i$ 的 $d$ 维向量，并且这些 representation 向量可以捕获图的全局结构信息global structural information 。

   在本文中，全局结构信息有两个功能：捕获两个不同顶点之间的长距离关系、根据不同的转移 steps 考虑不同的链接。我们将在后面进一步地说明。

3. 正如我们之前讨论过的，我们认为在构建这样的全局 graph representation 时需要从图中捕获 k-step （具有不同的 $k$ ）的关系信息。为了验证这一点，下图给出了一些说明性的示例，展示了需要在两个顶点 A1 和 A2 之间捕获的、 k-step （其中 $k=1,2,3,4$） 的关系信息的重要性。图中，粗线表示两个顶点之间的关系较强、细线表示两个顶点之间的关系较弱。

   • 在 (a) 和 (e) 中显示了捕获彼此直接连接的、顶点之间简单的 1-step 信息的重要性，其中 (a) 具有较强的关系，(e) 具有较弱的关系。

   • 在 (b) 和 (f) 中显示了 2-step 信息，其中 (b) 中两个顶点A1 和 A2 共享许多共同的邻居，而 (f) 中两个顶点A1 和 A2 仅共享一个邻居。

     显然，2-step 信息对于捕获两个顶点之间的连接强度很重要：顶点之间共享的共同邻居越多，则它们之间的关系就越强。

   • 在 (c) 和 (g) 中显示了 3-step 信息。具体而言：

     • 在 (g) 中，尽管 A1 和 B 之间的关系很强，但是由于连接 B 和 C、以及 C 和 A2 的两条较弱的边，A1 和 A2 之间的关系可能会减弱。
     • 相比之下，在 (c) 中，A1 和 A2 之间的关系仍然很强，因为 B 和 A2 之间有大量的共同邻居，这加强了它们的关系。

     显然，在学习具有全局结构信息的良好 graph representation 时，必须捕获此类 3-step 信息。

   • 类似地，如 (d) 和 (h) 所示，4-step 信息对于揭示图的全局结构特性也至关重要。在 (d) 中，A1 和 A2 之间的关系明显很强。而在 (h) 中，A1 和 A2 明显不相关，因为从一个顶点到另一个顶点之间不存在路径。在缺乏 4-step 关系信息的情况下，无法捕获这种重要的区别important distinction 。

   

4. 我们还认为：在学习 graph representation 时，必须区别对待不同的 k-step 信息。我们在下图的 (a) 中展示了一个简单的例子。让我们专注于学习图中顶点 A 的 representation。可以看到，A 在学习其 representation 时接收到两种类型的信息：来自顶点 B 的 1-step 信息、以及来自顶点 C 的 2-step 信息。

   我们注意到，如果我们不区分这两种不同类型的信息，我们可以构建如图 (b) 所示的替代品，其中顶点 A 接受与 (a) 完全相同的信息。但是，图 (b) 具有完全不同的结构。

   这意味着如何使用 k-step 信息很重要，它们位于不同的子空间，应该区别对待。

   

5. 在本文中，我们提出了一种用于学习准确 graph representation 的新的框架，它集成了各种 k-step 信息，这些信息共同捕获了与图相关的全局结构信息。