论文笔记：GraRep: Learning Graph Representations with Global Structural Information

一、基本信息

论文标题：《GraRep: Learning graph representations by incorporating global structural information》

发表时间：CIKM 2015

论文作者及单位：

论文地址：https://dl.acm.org/citation.cfm?id=2806416.2806512

二、摘要

我们提出了一种基于加权图顶点表示的新模型GRAREP。该模型通过学习低维向量来捕捉图中各顶点的特征，并且相比现有方法而言，在整合全局结构信息方面具有显著优势。我们进一步探讨了本研究与现有相关工作的关联，并特别分析了与Perozzi等人提出的DeepWalk模型[20]以及Mikolov等人改进的 skip-gram 模型[18]之间的联系。

实验结果表明，在语言网络、社交网络以及引文网络等多个实际场景下应用该方法后，在聚类、分类以及可视化等典型任务中均展现出超越现有最先进方法的优势。

三、主要内容和工作

在众多实际问题中,信息常以图表形式进行组织.例如,在社会网络分析领域,基于社交图表对用户进行有意义的社会群体划分,能够衍生出一系列潜在的实际应用场景,如个性化推荐、精准广告投放以及社交行为预测等.因此,从图谱中精确提取有价值的信息便成为一项关键任务.为此,一种有效的策略是将复杂图形转换至低维空间:通过将图形中的每个顶点映射至低维向量空间,使得图形所承载的意义关联、关系特征以及拓扑结构均得以被精准捕捉.近期研究已提出两种创新性方法:DeepWalk与skip-gram模型.其中skip-gram模型在处理图形上的损失函数定义尚存在一定的解析难题.

2、本文的主要贡献如下：

• 我们开发了一种新的模型以学习图上顶点的潜在表示其全局结构特征能够被有效捕捉。
• 从概率视角深入解析了DeepWalk中的统一采样方法这一技术其将图结构转换为线性序列的方法具有明确的理论基础同时我们还定义了在图上的损失函数并将其扩展支持加权图分析。
• 针对带负采样的Skip-Gram模型我们进行了效率分析并提出了一个更为精确的损失函数这一改进允许不同本地关系信息之间的非线性组合得以集成从而提升了模型的整体性能。

3、简单介绍线性序列表示和图表示的研究现状。

4、详细介绍图模型的表示、损失函数以及如何通过矩阵分解优化。

5、对skip-gram方法进行了系统性回顾，并对其存在的局限性进行了深入分析；在此基础上提出了一种改进方法，并命名为GraRep模型。

6、进行了实验，实验结果如下：

四、总结

该文提出了一种新型模型GRARep，用于学习更优的图表示方法。该模型将k阶损失函数直接定义于图结构中，并非简单地依赖于节点或边的基本属性。特别地，在这种设计下不仅整合了与图相关的局部特征信息，并且充分捕捉了其复杂的拓扑关系。同时有效地提取和表征了全局拓扑属性特征。为了保证理论严谨性我们还提供了严格的数学证明来验证该模型的有效性，并建立了与现有研究的重要联系。此外从实验结果来看所提取的表征特征不仅适用于后续的学习任务（如聚类分析与分类识别），而且表现出良好的泛化能力。然而，在实际应用中发现该模型存在计算开销较大的问题：涉及矩阵运算及奇异值分解（SVD）的过程计算复杂度较高。