11.Graph Embedding - 三、GraRep - 《AI算法工程师手册》

三、GraRep

三、GraRep

目前的 Graph Embedding 算法都存在局限性。
- DeepWalk 算法虽然在经验上有效，但是它在学习过程中使用的损失函数在Graph 上的明确含义尚未可知。另外其采样过程又慢又复杂。
- LINE 模型显式定义了损失函数来捕获一阶邻近度和二阶邻近度，它们分别代表了一阶局部关系和二阶局部关系。但是它无法扩展到二阶以上的邻近关系。
论文 《GraRep: Learning Graph Representations with Global Structural Information》 提出了 GraRep 模型，该模型显式定义了损失函数，并捕获了图的全局结构信息。

通过在语言网络、社交网络、引用网络等数据集上的实验表明，GraRep 模型学到的全局 representation 信息可以有效作用于聚类、分类以及可视化等任务中。
当构建全局结构信息时，需要捕获各种阶关系。如下图所示给出了顶点 A1 和 A2 之间的不同阶关系。粗线表示关系很强，细线表示关系较弱。
- 图a 和 e 展示了一阶关系的重要性，其中顶点 A1 和 A2 直接相连。
  - 图 a 中这两个顶点具有较强的一阶关系。
  - 图 e 中这两个顶点具有较弱的一阶关系。
- 图 b 和 f 展示了二阶关系的重要性，其中顶点 A1 和 A2 不相连但是有共同的邻居：
  - 图b 中这两个顶点具有多个共同邻居，因此具有较强的二阶关系。
  - 图 f 中这两个顶点只有一个共同邻居。，因此具有较弱的二阶关系。
  显然二阶关系对于捕获两个顶点的关系很重要，共同邻居越多则关系越强。
- 图 c 和 g 展示了三阶关系的重要性，其中顶点 A1 和 A2 不相连：
  - 图g 中尽管 A1 和 B 之间关系较强，但是由于 B 到 C 之间、以及 C 到 A2 之间的关系较弱，因此 A1 到 A2 的整体关系也较弱。
  - 图 c 中由于 B 到 A2 之间有大量的共同邻居，因此 A1 到 A2 的整体关系较强。
  显然在学习图的全局representation 时，必须捕获这些三阶信息。
- 图 d 和 h 展示了四阶关系的重要性，其中顶点 A1 和 A2 不相连：
  - 图d 中，因为 A1 和 A2 之间存在多条路径，因此其关系较强
  - 图 h 中，因为A1 和 A2 之间不存在路径，因此其关系较弱。
  显然在学习图的全局representation 时，也必须捕获这些四阶信息。
在学习图的表达时，除了必须引入不同的阶信息，也必须区别性的对待不同的阶信息。

如下图a 所示，顶点 A 接收到两类信息：
- 从顶点 B 获得的一阶信息。
- 从顶点 C1,C2,C3,C4 获得的二阶信息。
如果这些信息不佳区分（比如都映射到同一个子空间），则完全可以构建图 b 来替代图 a 。但是二者是完全不同的结构。

因此我们的模型应该将不同的阶信息映射到不同的子空间中。与此相反，SkipGram 模型就将所有的阶关系（如一阶关系、二阶关系 …..）映射到同一个子空间。
GraRep 模型同时采用了不同的阶关系从而捕获图的全局结构信息，同时不同的阶关系映射到不同的子空间中。
- LINE 模型虽然将不同的阶关系映射到不同的子空间，但是仅考虑一阶关系和二阶关系，未考虑更高阶的关系。
- SkipGram 虽然考虑了不同的阶关系，但是它将所有这些关系都映射到同一个子空间。

3.1 模型

给定图，其中：
- 为图的顶点集合，表示图的一个顶点。
- 为图的边集合，表示顶点之间的边，其权重为。权重衡量了边的重要性。
Graph Embedding 的任务是：学习全局 representation 矩阵

其中第行的向量代表顶点的表达，该向量捕获了顶点的全局结构信息。
定义邻接矩阵为：

这里假设所有的权重都是正的。

定义度矩阵degree matrix 为一个对角矩阵：

假设顶点转移到顶点的概率正比于，则定义转移概率矩阵 probability transition matrix：。其中定义了从顶点经过一步转移到顶点的概率，因此也称为一阶转移概率矩阵。显然可以认为是对按 ”行“ 进行的归一化。
考虑顶点和顶点之间的关系。这里要考虑两个问题：
- 顶点和之间是否有关，即是否存在从顶点到之间的路径？
- 如果有关则关系有多紧密，即如果从顶点开始随机转移则能够到达顶点的可能性有多大？
定义从顶点刚好经过步到达顶点的概率为，称作阶转移概率。则有：

定义阶转移概率矩阵为：

可以证明有：。其中表示的第行第列。

首先考虑特定的（比如）。对于给定的顶点称作当前顶点 current vertex，从开始的所有阶路径的终点集合称作上下文，上下文中的每个顶点称作上下文顶点 context vertex 。

受Skip-Gram 模型启发，我们采用 noise contrastive estimation:NEC 来定义目标函数。对给定顶点，其损失函数定义为：

其中：
- 第一项给出了图中存在的、所有以开始的阶顶点对（正样本），第二项给出了以开始的、终点随机采样的阶顶点对（负样本）。
- 表示和之间的阶关系。
- 为 sigmoid 函数：
- 为超参数，给出负样本数量。
- 分别为顶点的representation 向量。
- 为图中所有顶点的概率分布，给出了当服从分布时的期望。这里为负采样的顶点。
  
  其中：
  
  的物理意义为：从所有满足阶关系的顶点中选择顶点的概率。其中为顶点数量，为选择作为路径的第一个顶点的概率，假设它服从均匀分布。
可以化简为：

因此得到：

这里对于给定的顶点对，定义其局部损失函数为：

则阶损失函数为：

为最小化则只需要最小化每个成分，即求解：

令，求解：

得到最优解：

其中。
定义矩阵为：

定义矩阵：

则有：。因此我们将最优化问题转化为矩阵分解问题。

为降低噪音我们将中的所有负数都替换为正数。因为若存在负数，则图中存在的阶定点对的概率。则有：

虽然有很多矩阵分解技术，这里论文采用 SVD 矩阵分解。给定矩阵其 SVD 分解为：

其中均为正交矩阵；为对角矩阵，对角线原始为按降序排列的矩阵奇异值。

取最大的 d 个奇异值以及的前面 d 列，分别对应。其物理意义为：最大的 d 个特征值及其对应的特征向量。

此时有：

令，因此解决该矩阵分解问题。
- 的每一行给出了各顶点作为当前顶点的 representation 向量。
- 的每一列给出了各顶点作为上下文顶点的 representation 向量。
- 除了 SVD 方法进行矩阵分解之外，还可以采用其它方法如 incremental SVD,ICA,dnn 。
  
  这里主要聚焦于学习 Graph Embedding 而不是矩阵分解技术。事实上如果采用更高级的 dnn 技术来分解矩阵，则最终效果很难说明是由于 Graph Embedding 模型的效果还是 dnn 降维的效果。
GraRep 模型考虑所有的阶关系来捕获图的全局信息，即。事实上当足够大时，就收敛到一个固定值，因此通常选择一个不大的值。

最终 GraRep 模型将每个顶点的阶 representation 拼接成一个整体作为顶点的 representation 。因为不同的阶representation 反应了不同的局部信息。
GraRep 算法：
- 算法输入：
  - 图的邻接矩阵
  - 最大转移阶数
  - 对数偏移系数
  - 维度
- 算法输出：每个顶点的表达矩阵
- 算法步骤：
  - 计算阶转移概率矩阵。计算流程：首先计算；然后依次计算。
    
    对于带权图，是一个实数矩阵；对于无权图，是一个0-1 矩阵。算法都能够处理。
  - 对迭代计算每个顶点的阶表达，计算步骤为：
    - 获取正的对数概率矩阵：首先计算，其中。然后计算：
    - 计算representation 矩阵：
    - 拼接所有的阶表达：
      
      其中表示向量的拼接。

3.2 GraRep vs SGNS

事实上 SGNS 是 GraRep 的特例。
定义，其中。考虑所有的阶损失：

同样的推导过程可以解得最优解：

其中其中。
设随机游走序列长度为，顶点出现在条序列中。考虑所有的 vertex-context 集合，则顶点出现在中的此时为。

设当前顶点为，则：
- 顶点为其一阶上下文的次数为：
- 顶点为其二阶上下文的次数：
- …
- 顶点为其阶上下文的次数：
则有顶点位于的上下文中的次数为：

则context 出现在中的次数为：

根据论文 《NeuralWord Embedding as Implicit Matrix Factorization》 ， SGNS 等价于矩阵分解。因此SGNS 的解为：

其中为所有观测到的 vertext-context 组合的数量，因此有，为图中所有顶点数量。

因此有：

其中其中。

这刚好就是 GraRep 的解。

3.3 实验

数据集：
- 语言网络数据集20-Newsgroup ：包含2万篇新闻组文档，并按照20个不同的组分类。每篇文档由文档内单词的 tf-idf 组成的向量表示，并根据余弦相似度计算得到文档的相似度。根据文档的这些相似度构建语言网络，该网络是一个全连接的带权图，用于聚类效果的评估。
  
  为验证模型的鲁棒性，论文分别从3/6/9 个不同的新闻组构建了三个更小规模的语言网络(NG 代表 Newsgroups ）：
  - 3-NG：由comp.graphics, comp.graphics and talk.politics.guns 这三个新闻组的文档构成。
  - 6-NG：由 alt.atheism, comp.sys.mac.hardware, rec.motorcycles, rec.sport.hockey, soc.religion.christian and talk.religion.misc 这六个新闻组的文档构成。
  - 9-NG：由 talk.politics.mideast, talk.politics.misc, comp.os.ms- windows.misc, sci.crypt, sci.med, sci.space, sci.electronics, misc.forsale, and comp.sys.ibm.pc.hardware 这九个新闻组的文档构成。
  这些小网络分别使用所有文档 all data，以及每个主题随机抽取200 篇文档两种配置。
- 社交网络数据集 Blogcatalog：每个顶点表示一个博客作者，每条边对应作者之间的关系。
  
  每个作者都带有多个标签信息，标签来自39种主题类别。该网络是一个无权图，用于多标签分类效果的评估。
- 引文网络数据集 DBLP Network：每个顶点代表一个作者，边代表一个作者对另一位作者的引用次数。
  
  论文选择六个热门会议并分为三组：数据挖掘data mining 领域的 WWW,KDD 会议、机器学习 machine learning 领域的 NIPS,IML 会议、计算机视觉 computer vision 领域的 CVPR,ICCV 会议。
评估模型：LINE 模型、DeepWalk 模型、E-SGNS 模型、谱聚类模型。

其中 E-SGNS 模型可以视为 GraRep 模型的特例，而谱聚类模型和 E-SGNS 模型的区别在于它们不同的损失函数。
参数配置：
- 对于 LINE 模型：batch-size=1，学习率为 0.025，负采样系数为 5，迭代step 总数为百亿级。
  
  论文拼接了一阶邻近度模型和二阶邻近度模型的 representation，并针对degree 较小的顶点执行重构策略来达到最佳性能。
- 对于 DeepWalk 和 E-SGNS 模型：窗口大小为 10，序列最长长度为 40，每个顶点开始的游走序列数量为 80 。
- 正则化：
  - LINE,GraRep 模型进行正则化可以达到最佳效果。
  - DeepWalk,E-SGNS 模型没有正则化也能达到最佳效果。
- embedding 维度：为公平比较，Blogcatalog 和 DBLP 数据集的；而 20-NewsGroup 数据集的。
- GraRep 模型：；Blogcatalog 和 DBLP 数据集的， 20-NewsGroup 数据集的。

3.3.1 语言网络数据集

对语言网络数据集通过聚类任务评估各模型的性能。论文将各模型学到的 representation 执行 k-means 算法并评估归一化互信息Normalized Mutual Information (NMI) 得分。

为确保结论可靠，每种representation 重复运行 10 次 k-means 并报告平均 NMI 得分。
- 对于 LINE 模型这里采用了重构策略，邻居数量阈值分别设定为 k-max = 0,200,500,1000 取最佳阈值（200）。
- 对于 DeepWalk,E-SGNS 以及谱聚类，论文除了给出之外还给出了的结果以评估不同维数的影响。
最终结果如下表所示，每列的最佳结果用粗体突出显示。结论：
- GraRep 模型在所有实验种都优于其它方法。
- 对于 DeepWalk,E-SGNS 和谱聚类，增加维度把那个不能有效提高性能。论文认为：较高的维度并不会为representation 提供额外的补充信息。
- 对于LINE 模型采用重建策略确实有效，因为重建策略可以补充一阶邻近度、二阶邻近度以外的三阶结构信息。
- GraRep 和 LINE 模型在很小的 Graph 上就可以得到良好的性能，论文认为：即使在图很小的条件下，这两个模型也可以捕获丰富的局部关系信息。
- 当时谱聚类达到最佳性能，但是对其它算法达到最佳性能。

3.3.2 社交网络数据集

对社交网络数据集通过多类别分类任务来评估各模型representation 的性能，评估指标为 one-vs-rest 逻辑回归分类器分类结果的 Micro-F1 和 Macro-F1 指标。

论文随机采样 10%~90% 的顶点来训练，剩下的顶点作为测试集。为确保结论可靠，每一种拆分评估10次取平均。

这里LINE 模型采用了重构策略，邻居数量阈值分别设定为 k-max = 0,200,500,1000 取最佳阈值（500）。

最终结果如下表所示，每列的最佳结果用粗体突出显示。结论：总体上 GraPep 性能远超过其它方法，尤其是仅使用 10% 样本训练。

这表明GraRep 学到的局部结构信息可以相互补充从而捕获到全局结构信息。这在数据稀疏时具有显著优势。

3.3.3 引文网络数据集

对引文网络数据集通过 t-SNE 可视化来评估各模型representation 的效果。

来自同一个研究领域的作者使用相同的颜色，其中绿色表示数据挖掘、紫色表示计算机视觉、蓝色表示机器学习。

结论：
- 使用谱聚类的效果一般，因为不同颜色的顶点相互混合。
- DeepWalk 和 E-SGNS 结果看起来好得多，因为大多数相同颜色的顶点似乎构成了分组，但是分组的边界似乎不是很明显。
- LINE 和 GraRep结果种，每个分组的边界更加清晰，不同颜色的顶点出现在明显可区分的区域中。
  
  与 LINE 相比 GraRep 的结果似乎更好，每个区域的边界更清晰。
引文网络可视化的 KL 散度如下表所示。其中 KL 散度捕获了 ”成对顶点的相似度” 和 “二维投影距离” 之间的误差。

更低的 KL 散度代表更好的表达能力。可以看到：GraRep 模型的顶点 representation 效果最好。

3.3.4 参数探索及其它

考察不同的值的效果。下图给出 Blogcatelog 数据集上不同值对应得 Micro-F1 和 macro-F1 得分。

为阅读方便，这里仅给出的结果。因为实验发现：的结果略好于，而的效果与相当。

结论：
- 比有明显改善，而的性能进一步优于。
  
  这表明：不同的阶信息可以学到互补的局部信息。
- 的结果并不比好多少。
  
  这是因为当足够大时，学到的阶信息会减弱并趋于一个稳定的分布。
考察不同值的效果。下图给出了 3NG 和 9NG 在不同配置下不同模型的 NMI 得分。

结论：
- GraRep 模型结果始终优于其它模型。
- 几乎所有算法都在时取得最佳性能，当继续增加到更大值时所有算法效果都开始下降。
下图给出不同总维度下模型的运行时间。总维度等于，它代表最终 GraRep 拼接得到的representation 向量。
- 图 a 给出了且时，模型在 Blogcatalog 数据集上的模型训练时间。
  
  可以看到：模型训练时间随着总维度的增加而几乎线性增加。
- 图 b 给出了在 20-NewsGroup 数据集不同规模的网络上训练的时间。
  
  可以看到：随着 Graph 规模的增长，模型训练时间显著增加。原因是随着 Graph 增长，矩阵幂运算和矩阵 SVD 分解涉及到时间复杂度较高的运算。
  
  后续可以考虑采用深度学习来替代 SVD 技术来做矩阵分解。