三、GraRep

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

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

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

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

2. 当构建全局结构信息时，需要捕获各种 阶关系。如下图所示给出了顶点 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 时，也必须捕获这些四阶信息。

   

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

   如下图a 所示，顶点 A 接收到两类信息：

   • 从顶点 B 获得的一阶信息。
   • 从顶点 C1,C2,C3,C4 获得的二阶信息。

   如果这些信息不佳区分（比如都映射到同一个子空间），则完全可以构建图 b 来替代图 a 。但是二者是完全不同的结构。

   因此我们的模型应该将不同的 阶信息映射到不同的子空间中。与此相反，SkipGram 模型就将所有的 阶关系（如一阶关系、二阶关系 …..）映射到同一个子空间。

   

4. GraRep 模型同时采用了不同的 阶关系从而捕获图的全局结构信息，同时不同的 阶关系映射到不同的子空间中。

   • LINE 模型虽然将不同的 阶关系映射到不同的子空间，但是仅考虑一阶关系和二阶关系，未考虑更高阶的关系。
   • SkipGram 虽然考虑了不同的 阶关系，但是它将所有这些关系都映射到同一个子空间。

3.1 模型

1. 给定图 ，其中：

   • 为图的顶点集合， 表示图的一个顶点。
   • 为图的边集合， 表示顶点 之间的边，其权重为 。权重衡量了边的重要性。

   Graph Embedding 的任务是：学习全局 representation 矩阵

   

   其中第 行的向量 代表顶点 的表达，该向量捕获了顶点 的全局结构信息。

2. 定义邻接矩阵 为：

   

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

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

   

   假设顶点 转移到顶点 的概率正比于 ，则定义转移概率矩阵 probability transition matrix： 。其中 定义了从顶点 经过一步转移到顶点 的概率，因此也称为一阶转移概率矩阵。显然 可以认为是对 按 ”行“ 进行的归一化。

3. 考虑顶点 和顶点 之间的关系。这里要考虑两个问题：

   • 顶点 和 之间是否有关，即是否存在从顶点 到 之间的路径？
   • 如果有关则关系有多紧密，即如果从顶点 开始随机转移则能够到达顶点 的可能性有多大？

   定义从顶点 刚好经过 步到达顶点 的概率为 ，称作 阶转移概率。则有：

   

   定义 阶转移概率矩阵为：

   

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

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

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

   

   其中：

   • 第一项给出了图中存在的、所有以 开始的 阶顶点对（正样本），第二项给出了以 开始的、终点随机采样的 阶顶点对（负样本）。

   • 表示 和 之间的 阶关系。

   • 为 sigmoid 函数：

   • 为超参数，给出负样本数量。

   • 分别为顶点 的representation 向量。

   • 为图中所有顶点的概率分布， 给出了当 服从分布 时的期望。这里 为负采样的顶点。

     其中：

     

     的物理意义为：从所有满足 阶关系的顶点中选择顶点 的概率。其中 为顶点数量， 为选择 作为路径的第一个顶点的概率，假设它服从均匀分布 。

   可以化简为：

   

   因此得到：

   

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

   

   则 阶损失函数为：

   

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

   

   令 ，求解：

   

   得到最优解：

   

   其中 。

4. 定义矩阵 为：

   

   定义矩阵：

   

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

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

   

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

   

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

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

   此时有：

   

   令 ，因此解决该矩阵分解问题。

   • 的每一行给出了各顶点作为当前顶点的 representation 向量。

   • 的每一列给出了各顶点作为上下文顶点的 representation 向量。

   • 除了 SVD 方法进行矩阵分解之外，还可以采用其它方法如 incremental SVD,ICA,dnn 。

     这里主要聚焦于学习 Graph Embedding 而不是矩阵分解技术。事实上如果采用更高级的 dnn 技术来分解矩阵，则最终效果很难说明是由于 Graph Embedding 模型的效果还是 dnn 降维的效果。

5. GraRep 模型考虑所有的 阶关系来捕获图的全局信息，即 。事实上当 足够大时， 就收敛到一个固定值，因此通常 选择一个不大的值。

   最终 GraRep 模型将每个顶点的 阶 representation 拼接成一个整体作为顶点的 representation 。因为不同的 阶representation 反应了不同的局部信息。

6. GraRep 算法：

   • 算法输入：

     • 图的邻接矩阵
     • 最大转移阶数
     • 对数偏移系数
     • 维度

   • 算法输出：每个顶点的表达矩阵

   • 算法步骤：

     • 计算 阶转移概率矩阵 。计算流程：首先计算 ；然后依次计算 。

       对于带权图， 是一个实数矩阵；对于无权图， 是一个0-1 矩阵。算法都能够处理。

     • 对 迭代计算每个顶点的 阶表达，计算步骤为：

       • 获取正的对数概率矩阵 ：首先计算 ，其中 。然后计算：

       

       • 计算representation 矩阵 ：

         

       • 拼接所有的 阶表达：

         

         其中 表示向量的拼接。

3.2 GraRep vs SGNS

1. 事实上 SGNS 是 GraRep 的特例。

2. 定义 ，其中 。考虑所有的 阶损失：

   

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

   

   其中其中 。

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

   设当前顶点为 ，则：

   • 顶点 为其一阶上下文的次数为：

     

   • 顶点 为其二阶上下文的次数：

     

   • …

   • 顶点 为其 阶上下文的次数：

     

   则有顶点 位于 的上下文中的次数为：

   

   则context 出现在 中的次数为：

   

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

   

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

   因此有：

   

   其中其中 。

   这刚好就是 GraRep 的解。

3.3 实验

1. 数据集：

   • 语言网络数据集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 会议。

   

2. 评估模型：LINE 模型、DeepWalk 模型、E-SGNS 模型、谱聚类模型。

   其中 E-SGNS 模型可以视为 GraRep 模型的特例，而谱聚类模型和 E-SGNS 模型的区别在于它们不同的损失函数。

3. 参数配置：

   • 对于 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 语言网络数据集

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 社交网络数据集

1. 对社交网络数据集通过多类别分类任务来评估各模型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 引文网络数据集

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

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

   结论：

   • 使用谱聚类的效果一般，因为不同颜色的顶点相互混合。

   • DeepWalk 和 E-SGNS 结果看起来好得多，因为大多数相同颜色的顶点似乎构成了分组，但是分组的边界似乎不是很明显。

   • LINE 和 GraRep结果种，每个分组的边界更加清晰，不同颜色的顶点出现在明显可区分的区域中。

     与 LINE 相比 GraRep 的结果似乎更好，每个区域的边界更清晰。

   

2. 引文网络可视化的 KL 散度如下表所示。其中 KL 散度捕获了 ”成对顶点的相似度” 和 “二维投影距离” 之间的误差。

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

   

3.3.4 参数探索及其它

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

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

   结论：

   • 比 有明显改善，而 的性能进一步优于 。

     这表明：不同的 阶信息可以学到互补的局部信息。

   • 的结果并不比 好多少。

     这是因为当 足够大时，学到的 阶信息会减弱并趋于一个稳定的分布。

   

2. 考察不同 值的效果。下图给出了 3NG 和 9NG 在不同 配置下不同模型的 NMI 得分。

   结论：

   • GraRep 模型结果始终优于其它模型。
   • 几乎所有算法都在 时取得最佳性能，当 继续增加到更大值时所有算法效果都开始下降。

   

3. 下图给出不同总维度下模型的运行时间。总维度等于 ，它代表最终 GraRep 拼接得到的representation 向量。

   • 图 a 给出了 且 时，模型在 Blogcatalog 数据集上的模型训练时间。

     可以看到：模型训练时间随着总维度的增加而几乎线性增加。

   • 图 b 给出了在 20-NewsGroup 数据集不同规模的网络上训练的时间。

     可以看到：随着 Graph 规模的增长，模型训练时间显著增加。原因是随着 Graph 增长，矩阵幂运算 和矩阵 SVD 分解涉及到时间复杂度较高的运算。

     后续可以考虑采用深度学习来替代 SVD 技术来做矩阵分解。