首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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

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

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

论文链接:

代码链接:

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(cw):

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

GraRep希望预测的概率能够尽量拟合经验概率,借助Noise Contrastive Estimation (NCE)损失,GraRep的损失函数如下所示:

经过一连串数学推导得出,为了最小化损失函数,每个节点对w和c需要满足:

上述约束可以用一个矩阵Y统一表示:

从上面公式可以明显看出,网络节点表示的求解,可以被看成一个矩阵分解问题。使用SVD来求解这个问题,最终得到节点的两种向量表示如下图所示,一般我们使用W(当前节点向量表示)来作为学习到的网络节点表示。

下图是一些NRL算法的可视化结果,可以看出GraRep的效果还是很不错的:

-END-

专 · 知

人工智能领域主题知识资料查看获取:【专知荟萃】人工智能领域26个主题知识资料全集(入门/进阶/论文/综述/视频/专家等)

同时欢迎各位用户进行专知投稿,详情请点击

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180211G0I59900?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券