图的表达

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

一、DeepWalk

  1. 定义图 network ,其中 为图中所有的顶点(也称为网络的成员 member ), 为所有的边。

    定义带标签的社交网络 labeled social network ,其中:

    • 特征 为每个成员的特征空间的大小, 为顶点数量。
    • label 空间, 为分类类别数量。

    在传统机器学习算法中,我们仅仅学习从 的映射,忽略了成员之间的社交关系。而基于图的算法中,我们可以利用 中色社交关系来提升分类准确性,在文献中这个问题被称作关系分类relational classfication 问题。

    传统的关系分类算法将这个问题视作无向马尔可夫网络中的一个inference,然后使用迭代近似推理算法在给定网络结构的情况下计算标签的后验分布。这些算法融合了标签空间作为特征空间的一部分。

    论文《DeepWalk: Online Learning of Social Representations》 提出了 DeepWalk 算法,该算法基于无监督方法直接学习网络的结构特征,学得一个与标签无关的网络representation

  2. DeepWalk 将图 作为输入来学习网络中顶点的潜在表达 latent representation,这种表达可以将社交关系编码到一个连续向量空间中,从而给后续模型使用。

    Karate network 为例,图a 给出了典型的图,图b 给出了该图中所有顶点的 2 维潜在表达。可以看到:二者非常相似,且图 b 可以对应于图 a 的聚类。

  3. DeepWalk 的目标是学习每个顶点的表达 。其中, 是一个较小的数,表示低维表达空间的维度大小。这个低维空间是分布式表达的,每个维度或者几个维度代表某种社交现象。

  4. DeepWalk 首次将深度学习技术引入到 network 分析中,它通过深度学习技术学习图顶点的社交表达 social representation 。顶点社交表达可以在低维连续空间编码社交关系social relation,从而获得网络顶点的相似性和社区成员关系 community membership

    这种社交表达 social representation 需要满足以下特点:

    • 适应性 Adaptability:社交网络不断演变,新的社交关系不应该要求重新训练整个网络。
    • 社区相关Community aware:低维表示空间中的距离应该代表网络成员之间的社交相似性。
    • 低维Low dimensional:低维模型泛化效果更好,训练速度和推理速度更快。
    • 连续Continuous :连续的表示更方便建模(函数可微),且使得社区 community 之间的边界更平滑。

1.1 模型

  1. 定义以顶点 开始的一次随机游走序列为 ,其中:

    • 为每个序列的长度,它是算法的超参数。
    • 是序列中的第 个顶点,它是从 的邻居中随机选择一个顶点而生成。
  2. 如果一个图中顶点的度degree 满足幂律分布power law,则随机游走序列中顶点出现的频次也满足幂律分布。

    一个事实是:自然语言中单词出现的频次也满足幂律分布。由于语言模型是解决这种模式的工具,因此这些工具理论上也可以应用于networkcommunity structure 建模。

    DeepWalk 就是参考了神经语言模型的思想:将随机游走序列视为文本序列,从而学习顶点的潜在表达。

    下图给出了两个典型分布:

    • a 给出了short random walk 中,顶点出现频次的分布。

      因为随机游走序列最长的长度不超过 ,因此称为short

    • b 给出了英文维基百科的 10 万篇文章中,单词的频次分布。

  3. 语言模型的输入是语料库 和词汇表 ,而 DeepWalk 的输入是一组short random walk 序列和图的顶点

1.1.1 算法

  1. DeepWalk 算法由两部分组成:随机游走序列生成部分、参数更新部分。

    • 随机游走序列生成:随机游走序列生成器从图 中均匀随机采样一个顶点 作为序列 的起点,然后生成器从上一个访问顶点的邻居节点中均匀随机采样一个顶点作为序列的下一个点。

      • 论文中将序列的长度设置为最长为 ,但是论文也提到:理论上序列的长度不一定是固定的,没有任何限制。
      • 随机游走可以选择随机重启,即以一定的概率回到起始点。但是论文的实验结果显示:随机重启并没有任何优势。
    • 参数更新部分:

  2. 对于每一个顶点 DeepWalk 随机生成以 为起点的 条随机游走序列。每条随机游走序列都是独立采样的,它们都是以顶点 为起点。

  3. DeepWalk 算法:

    • 输入:

      • 窗口尺寸
      • 顶点的 embedding size
      • 每个顶点作为起始点的游走轮次
      • 游走序列长度
    • 输出:所有顶点的representation 矩阵

    • 算法步骤:

      • 中随机采样来初始化

      • 构建一颗二叉树 binary tree

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

      • 迭代: ,迭代步骤:

        • 随机混洗顶点:

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

        • 对每个顶点 ,执行:

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

  4. DeepWalk 算法有两层循环:

    • 外层循环指定应该在每个顶点开始随机游走的轮次。
    • 内存循环遍历图 中的所有顶点。
  5. 对于每个随机游走序列中的顶点 ,我们基于 SkipGram 的思想最大化 邻居结点的概率。

    SkigGram 算法:

    • 输入:

      • 顶点的 representation 矩阵
      • 随机游走序列
      • 窗口大小
    • 输出:更新后的顶点 representation矩阵

    • 算法步骤:

      对随机游走序列 的每个顶点:迭代,迭代步骤:

      • 窗口内的所有邻居顶点 ,执行:

        其中 表示 是顶点 邻居结点的概率。

  6. 由于类别标签数量等于 ,这可能是百万或者数十亿,因此每次迭代过程中计算 。为了加快训练速度,通常采用 Hierarchical Softmax 。这也是前面为什么要对顶点建立二叉树 的原因。

    假设到达顶点 经过的二叉树中间结点依次为 ,其中 ,则有:

    可以直接用二分类建模,因此计算 的整体复杂度从 降低到

    如果对更频繁出现的顶点赋予更短的路径,则得到霍夫曼编码树,这可以进一步降低计算代价。

1.1.1 训练和优化

  1. DeepWalk 算法的参数为 ,参数采用随机梯度下降法来优化。其中学习率 初始值为 0.025,然后随着已见过的顶点数量线性衰减。

  2. DeepWalk 算法有两个理想的优点:

    • 支持增量学习,因此是一种在线学习算法。

      当图 发生变化时,我们可以在发生变化的局部区域用随机游走生成器生成新的随机游走序列来更新模型,从而可以用较小的代价来增量更新模型,无需重新计算整个图

    • 容易并行化,不同的随机游走生成器可以并行探索图 的不同部分。

      此外,在训练时我们可以使用异步随机梯度下降 ASGD 方法。在 ASGD 中我们访问共享参数时不需要加锁,这可以实现更快的收敛速度(见图a)并且没有预测性能的损失(见图b)。

      之所以如此时因为:社交网络随机游走序列的顶点频次分布和NLP单词频次分布都遵循幂律分布,因此会出现长尾效应,大多数顶点出现次数较少。这使得对 的更新是稀疏的,即:同时对同一个顶点进行更新的概率很低。

  3. DeepWalk 可以挖掘图 的局部结构,但是无法挖掘图 的整体结构。

  4. DeepWalk 算法还有两个变种模式:

    • 流式计算模式:在不知道图 整体信息的情况下实现 DeepWalk。在这种模式下,从图中得到的一小段随机游走序列直接传给学习器来更新模型。此时算法需要进行以下修改:

      • 学习率 不再是衰减的,而是固定为一个小的常数。这使得算法的训练需要更长的时间。
      • 不必再建立二叉树 。但是如果顶点数量 已知,则也可以建立二叉树。
    • 非随机游走模式:在某些图中,有些路径的产生并不是随机的,如:用户浏览网页元素的路径。对于这些图,我们可以直接使用用户产生的路径而不是随机生成的路径来建模。

      通过这种方式,我们不仅可以建模网络结构,还可以建模这些路径的热度。

1.2 实验

  1. 数据集:

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

  2. 对比模型:

    • 谱聚类 SpectralClustering:从图 normalized graph Laplacian 矩阵 中计算到的 个最小的特征向量,构成图的表达。

    • Modularity:从图 Modularity 计算得到 top-d 个特征向量,构成了图的表达。

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

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

      其中 为归一化系数。

      该方法在真实网络中表现良好,并被推荐作为一个优秀的关系分类基准。

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

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

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

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

1.2.1 模型结果

  1. 实验条件:

    • 随机采样一个比例为 的带标签顶点作为训练数据,剩下顶点作为测试数据。
    • 所有流程执行 10 次并汇报平均性能。
    • 对于 DeepWalk,我们汇报 的结果;对于SpectralClustring,Modularity,EdgeCluster ,我们汇报 的结果。
  2. BlogCatalog数据集:我们评估 的结果。结果如下表,粗体表示每一列最佳结果。

    结论:

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

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

    • 虽然 SpectralClustering 方法更具有竞争力,但是当数据稀疏时 DeepWalk 效果最好:

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

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

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

  4. 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 考察不同 和不同 的效果。

      在不同 取值上,模型性能对于不同 的变化比较稳定。

      • 开始继续提高 时模型的效果提升不大,因此 几乎取得最好效果。继续提升效果,计算代价上升而收益不明显。
      • 不同的数据集中,不同 值的差异非常一致,尽管 FLICKR 包含边的数量比 BLOGCATALOG 多一个数量级。

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

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

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

二、LINE

  1. 定义信息网络information network,其中:

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

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

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

      • 如果 是无向图,则有 ;如果 是有向图,则有

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

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

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

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

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

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

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

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

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

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

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

    如下图所示:

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

    因此我们采用二阶邻近度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 一致,这里也采用 FlickrYoutube 数据集。

    • 引文网络 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,使得cd 的关系类比于 ab 的关系。记作:

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

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

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

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

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

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

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

    结论:

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

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

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

      • 虽然 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-F1Macro-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. 引文网络数据集包括作者引用网络、论文引用网络,它们都是有向图。由于GFLINE(1st) 都无法应用于有向图,因此这里仅仅比较 DeepWalkLINE(2nd)

    论文通过多标签分类任务评估顶点 embedding 的效果。论文采用 7 个热门的会议(AAAI,CIKM,ICML,KDD,NIPS,SIGIR,WWW)作为分类类别,在会议中发表的作者或者论文被标记为对应类别。最终评估分类结果的 Micro-F1Macro-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 给出了 LINEDeepWalk 的性能和收敛速度。可以看到:LINE(2nd) 始终优于 LINE(1st)DeepWalk,并且LINE(1st)LINE(2nd) 收敛速度都快于 DeepWalk

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

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

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

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

三、GraRep

  1. 目前的 Graph Embedding 算法都存在局限性。

    • DeepWalk 算法虽然在经验上有效,但是它在学习过程中使用的损失函数在Graph 上的明确含义尚未可知。另外其采样过程又慢又复杂。
    • LINE 模型显式定义了损失函数来捕获一阶邻近度和二阶邻近度,它们分别代表了一阶局部关系和二阶局部关系。但是它无法扩展到二阶以上的邻近关系。

    论文 《GraRep: Learning Graph Representations with Global Structural Information》 提出了 GraRep 模型,该模型显式定义了损失函数,并捕获了图的全局结构信息。

    通过在语言网络、社交网络、引用网络等数据集上的实验表明,GraRep 模型学到的全局 representation 信息可以有效作用于聚类、分类以及可视化等任务中。

  2. 当构建全局结构信息时,需要捕获各种 阶关系。如下图所示给出了顶点 A1A2 之间的不同 阶关系。粗线表示关系很强,细线表示关系较弱。

    • ae 展示了一阶关系的重要性,其中顶点 A1A2 直接相连。

      • a 中这两个顶点具有较强的一阶关系。
      • e 中这两个顶点具有较弱的一阶关系。
    • bf 展示了二阶关系的重要性,其中顶点 A1A2 不相连但是有共同的邻居:

      • b 中这两个顶点具有多个共同邻居,因此具有较强的二阶关系。
      • f 中这两个顶点只有一个共同邻居。,因此具有较弱的二阶关系。

      显然二阶关系对于捕获两个顶点的关系很重要,共同邻居越多则关系越强。

    • cg 展示了三阶关系的重要性,其中顶点 A1A2 不相连:

      • g 中尽管 A1B 之间关系较强,但是由于 BC 之间、以及 CA2 之间的关系较弱,因此 A1A2 的整体关系也较弱。
      • c 中由于 BA2 之间有大量的共同邻居,因此 A1A2 的整体关系较强。

      显然在学习图的全局representation 时,必须捕获这些三阶信息。

    • dh 展示了四阶关系的重要性,其中顶点 A1A2 不相连:

      • d 中,因为 A1A2 之间存在多条路径,因此其关系较强
      • h 中,因为A1A2 之间不存在路径,因此其关系较弱。

      显然在学习图的全局representation 时,也必须捕获这些四阶信息。

  3. 在学习图的表达时,除了必须引入不同的 阶信息,也必须区别性的对待不同的