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

【导读】这次论文笔记介绍了介绍一种具有代表性的网络节点表示学习(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。该算法的贡献点有如下几条:

  1. 可以很好地捕捉到远距离节点之间的关系。
  2. 与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使用的是上下文节点向量表示。

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

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

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

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

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

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

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2018-02-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

循环神经网络(一) ——循环神经网络模型与反向传播算法

循环神经网络(一) ——循环神经网络模型与反向传播算法 (原创内容,转载请注明来源,谢谢) 一、概述 这一章开始讲循环神经网络(RNN,Recurrent Ne...

3825
来自专栏人工智能LeadAI

常见激活函数总结 | 深度学习笔记2

01激活函数概览 基本上,入门深度学习的第一件事情就是了解”神经元”的构造,激活函数算是最基本的一个”部件”了吧.那激活函数到底有什么用呢?为什么需要激活函数?...

4328
来自专栏null的专栏

UFLDL笔记——自我学习

注:最近打算将UFLDL教程重新看一遍,其实里面有很多关于神经网络以及深度学习的知识点很有用,但是只是学习深度学习的话有一些内容就有点多余,所以想整理一个笔记,...

3645
来自专栏超然的博客

Network Embedding

基于Hierarchical softmax 的skip-gram 模型,优化的目标函数如

3954
来自专栏AI科技大本营的专栏

入门 | 零基础入门深度学习系列——递归神经网络

为了帮助编程爱好者,从零开始入门,AI100特别精选了韩炳涛所著《零基础入门深度学习》系列文章,以下Enjoy! 作者 | 韩炳涛 无论即将到来的是大数据时代还...

43310
来自专栏WD学习记录

机器学习 学习笔记(18) 提升树

提升树是以分类树或回归树为基本分类器的提升方法,提升树被认为是统计学习中性能最好的方法之一。

2334
来自专栏机器学习算法工程师

基础|认识机器学习中的逻辑回归、决策树、神经网络算法

逻辑回归。它始于输出结果为有实际意义的连续值的线性回归,但是线性回归对于分类的问题没有办法准确而又具备鲁棒性地分割,因此我们设计出了逻辑回归这样一个算法,它的输...

1513
来自专栏机器学习算法与Python学习

循环神经网络(RNN)

前言: 前馈神经网络的输入和输出的维数都是固定的,不能任意改变。当处理序列数据时,前馈神经网络就无能力为了。因为序列数据是变长的。为了使得前馈神经网络能处理变长...

3186
来自专栏杨熹的专栏

权重初始化的几个方法

其中第一步 权重的初始化 对模型的训练速度和准确性起着重要的作用,所以需要正确地进行初始化。

2162
来自专栏marsggbo

DeepLearning.ai学习笔记(五)序列模型 -- week1 循环序列模型

一、为什么选择序列模型 序列模型可以用于很多领域,如语音识别,撰写文章等等。总之很多优点。。。 二、数学符号 为了后面方便说明,先将会用到的数学符号进行介绍。 ...

42510

扫码关注云+社区

领取腾讯云代金券