图的表达

  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 analogiesDeepWalk 将图作为输入,并生成潜在 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 实现了所有的这些,同时是一种可简单并行的在线算法。

    论文的贡献如下:

    • 我们引入深度学习作为分析图的工具,从而构建适用于统计建模的鲁棒的 representationDeepWalk 学习短的随机游走中存在的结构规律structural regularity
    • 我们在多个社交网络上广泛评估了我们在多标签分类任务上的表现。在标签稀疏的情况下,我们展示了显著提高的分类性能。在最稀疏的问题上,我们获得了 Micro F15% - 10% 的提升。在某些情况下,即使训练数据减少 60%DeepWalkrepresentation 也可以胜过其它竞争对手。
    • 我们通过使用并行实现 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 inferenceNP-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 可以挖掘图 的局部结构,但是无法挖掘图 的整体结构。

1.1 模型

1.1.1 问题定义

  1. 考虑社交网络成员的分类问题。正式地,令 ,其中 为图中所有的顶点(也称为网络的成员 member ), 为所有的边。给定一个部分标记的 social network ,其中:

    • 特征 为属性空间的维度, 为顶点数量。
    • label 空间, 为分类类别数量。

    在传统的机器学习分类 setting 中,我们的目标是学习将 的元素映射到标签集合 的假设hypothesis 。在我们的例子中,我们可以利用嵌入在 结构中的样本依赖性 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)。

    我们的目标是学习 ,其中 是一个较低的潜在维度。这些低维 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 :我们将以顶点 root 的随机游走表示为 是一个随机游走过程,其中包含随机变量 是一个顶点,它是从顶点 的邻居中随机选中的。

    随机游走已被用作内容推荐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 中出现的可能性。正式地,给定一个单词序列 ,其中 为词典 vocabulary),我们希望在整个训练语料库上最大化

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

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

    我们的目标是学习潜在 representation,而不仅仅是节点共现node co-occurrence 的概率分布,因此我们引入一个映射函数 。该映射函数 将图中每个顶点 映射到一个潜在的 social representation

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

    实际上,我们使用 free parameters 的矩阵 来表达 ,这在稍后将被用作我们的 。然后,问题变成了似然估计:

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

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

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

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

    应用到顶点建模中,这得到了优化问题:

    其中 为上下文窗口尺寸。

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

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

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

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

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

1.1.4 DeepWalk

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

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

    • 随机游走生成器random walk generator :以图 作为输入并均匀随机采样一个顶点 作为随机游走 root 。随机游走从最近访问的顶点的邻域中均匀采样,直到游走序列长度达到最大长度

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

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

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

  3. DeepWalk 算法:

    • 输入:

      • 上下文窗口尺寸
      • embedding size
      • 每个节点开始的随机游走序列数量
      • 每条随机游走序列长度
    • 输出:顶点 representation 矩阵

    • 算法步骤:

      • representation 初始化:从均匀分布中采样,得到初始的

      • 构建一颗二叉树 binary tree

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

      • 遍历,,遍历过程:

        • 随机混洗顶点:

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

        • 对每个顶点

          • 利用随机游走生成器生成随机游走序列:
          • 采用 SkipGram 算法来更新顶点的representation
  4. SkipGram 算法:

    • 输入:

      • 当前的顶点 representation矩阵
      • 单条随机游走序列
      • 上下文窗口尺寸
      • 学习率
    • 输出:更新后的顶点 representation矩阵

    • 算法步骤:

      • 对每个顶点

        • 对窗口内每个顶点

  5. Hierarchical Softmax: 计算 是不容易的,因为这个概率的分母(归一化因子)计算代价太高(计算复杂度为 )。如果我们将顶点分配给二叉树的叶节点,那么预测问题就变为最大化树中特定路径的概率。如果到顶点 的路径由一系列树节点 root)标识,则有:

    现在 可以通过分配给节点 的父节点的二分类器来建模。这降低了计算 的复杂度,计算复杂度从 降低到

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

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

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

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

    • b:在随机游走 上滑动一个长度为 的窗口,将中心顶点 映射到它的 representation

    • cHierarchical Softmax 在对应于从 root 的路径上的概率序列来分解 也是类似的。

      representation 被更新从而最大化中心顶点 与它的上下文 共现的概率。

1.1.5 并行化

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

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

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

1.1.6 变体

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

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

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

    • 首先,不再使用衰减的学习率。相反,我们可以将学习率 初始化为一个小的常量。这需要更长的时间来学习,但是在某些 application 中可能是值得的。
    • 其次,我们不能再构建参数树 tree of parameters。如果 的基数 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:从图 normalized graph Laplacian 矩阵 中计算到的 个最小的特征向量,构成图的representation。使用 的特征向量隐含地建设图割graph cuts 对分类有用。

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

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

    • wvRNweighted-vote Relational Neighbor 是一个关系分类器 relational classi er 。给定顶点 的邻居 wvRN 通过邻居结点的加权平均来预估

      其中 为归一化系数。

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

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

  3. 评估指标:对于多标签分类问题 multilabel classi cation,我们采用 Macro-F1Micro-F1 作为评估指标。

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

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

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

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

  4. 实验配置:

    • 对所有模型,我们使用由 LibLinear 实现的 one-vs-rest 逻辑回归进行分类。
    • DeepWalk的超参数为
    • 对于 SpectralClustering, Modularity, EdgeCluster 等方法,我们选择

1.2.1 实验结果

  1. BlogCatalog数据集:我们评估 的结果。结果如下表,粗体表示每一列最佳结果。

    结论:

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

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

    • 虽然 SpectralClustering 方法更具有竞争力,但是当数据稀疏时 DeepWalk 效果最好:对于 Macro-F1 指标,DeepWalk 效果更好;对于Micro-F1 指标,DeepWalk 效果更好。

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

  1. Flickr 数据集:我们评估 的结果。结果如下表,粗体表示每一列最佳结果。结论与前面的实验一致。

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

  2. YouTube 数据集:我们评估 的结果。结果如下表,粗体表示每一列最佳结果。

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

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

      • 当标记数据只有 1% 时,DeepWalkMicro-F1 指标上相对 EdgeCluster14% 的绝对提升,在 Macro-F1 指标上相对 EdgeCluster10% 的绝对提升。
      • 当标记数据增长到 10% 时,DeepWalk 提升幅度有所下降。DeepWalkMicro-F1 指标上相对 EdgeCluster3% 的绝对提升,在 Macro-F1 指标上相对 EdgeCluster4% 的绝对提升。
    • DeepWalk 能扩展到大规模网络,并且在稀疏标记环境中表现出色。

1.2.2 参数敏感性

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

  2. 考察不同 的效果:

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

      注意:Flickr1% 训练样本和 BlogCatalog10% 训练样本,模型的表现差不多。

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

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

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

  1. 考察不同 的影响。图 b1b3 考察不同 的效果,图 b2b4 考察了不同 的效果。

    实验结果表明,它们的表现比较一致:增加 时开始可能有巨大提升,但是当 时提升效果显著下降。

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

二、LINE[2015]

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

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

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

    • 局部网络结构(一阶邻近性):自然地,局部网络结构由网络中观察到的链接来表示,它捕获顶点之间的一阶邻近性 first-order proximity。大多数现有的 graph embedding 算法都旨在保持这种一阶邻近性,例如 IsoMapLaplacian 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 模型在效果和效率方面都优于其它竞争 baselineLINE 能够在几个小时内在单台机器上学习具有数百万个节点、数十亿条边的网络的 embedding

    总而言之,论文主要贡献:

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

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

      然而,这些算法通常依赖于求解 affinity matrixtop-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: DFSLINE 使用广度优先搜索 breadth- first search: BFS 策略,这是一种更合理的二阶邻近性方法。另外,DeepWalk 仅适用于无权图,而 LINE 适用于加权图和无权图。

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

2.1 模型

2.1.1 问题定义

  1. 信息网络information network 的定义:一个信息网络定义为 ,其中:

    • 为顶点集合,每个元素代表一个数据对象 data object

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

    • 每条边 是一个有序的 pair ,它关联一个权重 表示关系的强度。

      • 如果 是无向图,则有 ;如果 是有向图,则有
      • 如果 是无权图,则 ,这种边称作二元边 binary edge ,权重表示相连/不相连;如果 是带权图,则 则边的取值是实数,这种边表示连接的紧密程度。

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

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

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

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

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

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

    二阶邻近性 second-order proximity 的定义:网络中一对顶点 之间的二阶邻近性是它们的邻域网络结构之间的相似性。数学上,令 为顶点 和所有顶点的一阶邻近性向量,然后顶点 和顶点 之间的二阶邻近性由 的相似性来确定。如果没有任何顶点同时与 相连,则 之间的二阶邻近性为 0

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

    大规模信息网络嵌入Large-scale Information Network Embedding :给定一个大型网络 ,大规模信息网络嵌入的问题旨在将每个顶点 映射到一个低维空间 中,即学习一个函数 ,其中 。在空间 中,顶点之间的一阶邻近性和二阶邻近性都可以得到保持。

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

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

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

2.1.2 保持一阶邻近性的 LINE

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

    其中 为顶点 的低维 representation 向量。

    上式定义了 空间上的一个概率分布 ,它的经验概率 empirical probability 定义为:

    其中 为所有边权重之和。

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

    其中 为两个概率分布之间的距离。这里我们选择 KL 散度作为距离函数,因此有:

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

    通过最小化 从而得到 ,我们可以得到每个顶点在 维空间中的 representation

    读者注:

    • 上式的物理意义为:观测边的加权负对数似然,每一项权重为边的权重。
    • 上式并不是严格的 KL 散度,它用到的是两个非归一化概率
    • 最小化 KL 散度等价于最小化交叉熵:

    其中省略了常数项

2.1.3 保持二阶邻近性的 LINE

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

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

  2. 我们引入两个向量 ,其中 为顶点 作为顶点本身时的 representation 为顶点 作为其它顶点的特定上下文时的 representation。对于每条有向边 ,我们首先定义由顶点 生成上下文顶点 的概率为:

    其中 为顶点集合的大小。

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

    其中:

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

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

    • 是两个概率分布之间的距离。

    • 经验分布 定义为 ,其中 是边 的权重, 是顶点 的出度 out-degree,即 为顶点 out-neighbors

    在本文中,为简单起见,我们将 设为顶点 out-degree,即 。这里我们也采用 KL 散度作为距离函数。忽略一些常量,则我们得到:

    通过最小化 从而得到 ,我们可以得到顶点 维空间中的 representation

    读者注:

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

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

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

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

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

2.1.5 模型优化

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

    其中:

    • sigmoid 函数。
    • 为期望。
    • 为噪声分布。

    注意:目标函数 中的概率 不涉及对整个顶点集合进行求和。

    第一项对观察到的边进行建模,第二项对从噪声分布中采样的负边进行建模, 是负边的数量。我们根据 Word2Vec 的建议设置 ,其中 为顶点 的出度 out-degree

  2. 对于目标函数 ,存在一个平凡解 trivial solution

    此时 ,使得 取最小值。

    为了避免平凡解,我们也可以利用负采样方法,对于每条边

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

    注意这里没有上下文顶点,因此没有

2.1.6 边采样

  1. 我们采用异步随机梯度算法 ASGD 来优化目标函数。在每一步中,ASGD 算法采样了一个 mini-batch 的边,然后更新模型参数。假设采样到边 ,则顶点 embedding 向量 被更新为:

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

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

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

    为边权重的序列。

    • 首先,简单地计算权重之和