网络节点表示学习论文笔记02—CIKM2015GraRep: 基于全局结构信息的图结点表示学习

2018 年 2 月 11 日 专知专知内容组（编）

【导读】这次论文笔记介绍了介绍一种具有代表性的网络节点表示学习（NRL）方法：GraRep。以LINE为代表的一系列NRL算法一些网络上具有很好地学习效果，但它们并不能很好地捕捉到远距离节点之间的关系。该算法一方面可以很好地捕捉到远距离节点之间的关系，另一方面与DeepWalk、Line等经典的基于Skip-Gram和Negative Sampling的方法不同，GraRep使用矩阵分解来学习节点表示。这篇工作被CIKM2015接受。

【论文】：GraRep: Learning Graph Representations with Global Structural Information

论文链接：

https://www.researchgate.net/profile/Qiongkai_Xu/publication/301417811_GraRep/links/5847ecdb08ae8e63e633b5f2/GraRep.pdf

代码链接：

https://github.com/ShelsonCao/GraRep

网络节点表示学习（NetworkRepresentation Learning(NRL)、Network Embedding）是近几年比较火的研究方向。很多人可能对网络节点表示学习比较陌生，但大部分人一定知道Word2Vec，其实Word2Vec可以被看成是网络节点表示学习的一种应用。网络节点表示学习具有很强的泛化能力，可以对社交网络、论文引用网络、词网络等进行建模，且具有不错的效果。网络节点表示学习又被称作Network Embedding。

首先介绍一下NRL的作用，下图分别给出了NetworkEmbedding的输入和输出。NRL的输入是一个网络，例如社交网络、论文引用网络，网络中的核心信息是节点之间的关系。例如对于论文引用网络，网络节点表示论文，边表示论文之间的引用关系。输入这样一个网络，NLR会为网路中的每个节点学习一个低维向量表示（图例中是2维向量），使得相似的节点（例如相同类别的论文）之间距离较近，不相似的节点（例如不同类别的论文）之间的距离较远。从图例中的输出可以看出，在NRL学习到的空间中，不同类别的节点分布在空间的不同区域，这样的节点表示非常适合分类、聚类等机器学习任务。

本次论文笔记介绍一种具有代表性的NRL方法：GraRep。该算法的贡献点有如下几条：

可以很好地捕捉到远距离节点之间的关系。
与DeepWalk、Line等经典的基于Skip-Gram和Negative Sampling的方法不同，GraRep使用矩阵分解来学习节点表示。

以LINE为代表的一系列NRL算法一些网络上具有很好地学习效果，但它们并不能很好地捕捉到远距离节点之间的关系。如果两个节点v0和v1相邻，我们说v0和v1之间的step为1。如果v0和v1不直接相邻，而是通过v2相邻，即存在路径v0->v2->v1，v0和v1之间的step为2。LINE通过其设计的一阶和二阶相似性可以很好地捕捉step=1和step=2的情况，然而对于step > 2的情况，LINE等算法就显得有些无力了。例如下图中，节点A1和A2具有明显的相关性，然而A1和A2之间需要经过至少3个节点才能关联。

GraRep利用邻接矩阵的一个特性来捕捉step > 2时节点之间的关系。用S表示邻接矩阵，Sij为1时表示有一条从节点i指向节点j的边，Sij为0时表示节点i和节点j之间没有边。D是网路节点的出度矩阵，如下图所示，D是一个对角矩阵，对角线上的第i个元素表示第i个节点的出度。

利用S和D可以得到矩阵A（如下图所示），A是转移概率矩阵，Aij表示从节点i跳转到节点j的概率，注意A是step=1的转移概率矩阵。

有step=1的转移概率矩阵A，就可以很轻松地求出step=k时的转移概率矩阵：

从节点w经过k-step到节点c的概率可以表示为pk(c|w)：

pk(c|w)是根据邻接矩阵计算出的经验概率，GraRep通过节点w和节点c的低维表示来预测节点转移概率（如下图所示），其中σ表示sigmoid函数。注意，我们将w称作当前节点，将c称作上下文节点，节点在被当做当前节点或上下文节点时具有不同的向量表示，即每个节点有两个向量表示。这里w使用的是当前节点向量表示，c使用的是上下文节点向量表示。