《Network Representation Learning with Rich Text Information》---论文笔记

本文是清华刘知远老师组发表在15年IJCAI会议上的一个工作,论文在DeepWalk基础上进行了创新拓展,主要亮点在于:证明了DeepWalk等同于矩阵分解,并且在此基础上,将图节点的文本特征引入DeepWalk中,进一步学习到了网络结构的表示特征。

1、Introduction

网络表示学习,即是学习网络中的每个节点的向量表示。传统的网络表示学习从网络结构中学习网络节点的表示特征,包括DeepWalk方法同样是以网络的结构作为输入,来学习网络的表示特征。

网络结构中的节点往往包含丰富的文本信息和其他元数据,这些数据的特征都可以作为网络表示学习的输入特征。一种简单的想法就是,分别独立的学习网络结构特征和文本特征,然后简单的叠加两个表示特征,但是这种方法容易忽略文本信息与网络结构之间的联系。

2、DeepWalk as Matrix Factorization

将DeepWalk理解为矩阵分解,矩阵$M_{ij}∈R^{|V||V|}$表示网络中节点$v_i$经过固定步长$s$随机游走到节点$v_j$的平均概率对数,将其分解为两个低维度的矩阵$W∈R^{k|V|},H∈R^{k*|V|}$,其中$W$作为节点的表示特征。

tadw1DeepWalk通过随机游走,生成一个节点序列$S=\{v_1,v_2,…..v_{|S|} \}​$,$v∈\{v_{i-t},…,v_{i+t}\}​$表示中心节点$v_i​$的上下文,窗口大小为$t​$。基于语言模型中的Skip-Gram,DeepWalk的优化目标定义为:最大化随机游走路径中,所有中心节点-上下文节点对的平均对数概率,损失函数定义如下:

其中$r_{v_i},c_{v_j}$分别表示中心节点$v_i$和它的上下文节点$v_j$的表示向量,也就是说图结构中的每个节点都有两个表示向量:当节点$v$是中心节点时,其表示向量是$r_v$;当节点$v$是上下文节点时,其表示向量是$c_v$。

2.1、DeepWalk==MF

假设随机游走过程产生节点—上下文集合$D$,$D$中元素为节点-上下文对$(v,c)$,且$v\in{V},c\in{V_C}$,通常情况下,$V=V_C$。在DeepWalk中,每个节点$v$被映射到k维的向量空间$r_v\in{R^k}$,同样的,上下文节点也被映射到k维的向量空间$c_v\in{R^k}$。定义矩阵$W\in{R^{k|V|}}$,每一列表示节点$v_i$的向量表示$r_{v_i}$,矩阵$H\in{R^{k|V_C|}}$,每一列表示上下文节点$v_j$的向量表示$c_{v_j}$,矩阵分解使得$M=W^TH$。

定义$N(v,c)$表示节点对$(v,c)$出现在集合$D$中的次数,$N(v)=\sum_{c’\in{V_C}}{N(v,c’)}$,$N(c)=\sum_{v’\in{V}}{N(v’,c)}$,在文章^[1]^的启发下,本文直接给出了如下公式:

论文为了说明矩阵$M_{ij}$在DeepWalk中的含义,引入PageRank算法中的中间矩阵$A$,

其中$d_i$表示节点$i$的度。同时,用$e_i$来表示$|V|$维的行向量,向量的第$i$元素为1,其余值为0,即是对$i$节点进行one-hot编码

假设从节点$i$开始随机游走,$e_i$作为初始状态,那么$e_iA$表示所有节点的分布$e_iA$的第$j$个元素表示节点$i$游走到节点$j$的概率从节点$i$经过$t$步长随机游走到节点$j$的概率可以表示为$e_iA^t$,其中$A^t$表示$A$的$A$的$t$次方。因此有如下公式:

其中$[e_i(A+A^2+A^3+……+A^t)]$表示节点$v_j$出现在节点$v_i$右邻居中的期望次数。

综合公式(3)(5),$M_{ij}$就是节点$i$经过$t$步长随机游走到节点$j$的平均对数概率,对矩阵$M_{ij}$进行矩阵分解,其优化目标与DeepWalk的优化目标一致,所以DeepWalk实际上就是矩阵分解。

3、Taxt-Associated DeepWalk(TADW)

文本特征矩阵定义为$T\in{R^{f_t|V|}}$,论文设定*随机游走步长$t=2$,即矩阵分解$M =(A+A^2)/2$

![tadw2](http://ou5bxfpku.bkt.clouddn.com/textdeepwalk2.png)

优化目标:

需要注意的是,不同于为了更好接近矩阵M的常规低秩矩阵分解,TADW的目标是在矩阵分解中引入文本特征矩阵,以获得更好的网络特征表示。

4、Summary

整篇论文想法很简单,但也是干货满满,很有创意。主要的亮点有三处:其一:证明了DeepWalk等同于矩阵分解,以矩阵分解的角度重新解释DeepWalk,很有新意;其二,在证明了DeepWalk与矩阵分解的相似之后,将节点的文本特征引入矩阵分解,以此来学习网络节点的特征表示;最后一点,论文提供了一种以简单的矩阵分解为视角的特征融合的方式,我觉得这一点也是很有启发性的,模型特征融合并不一定需要特别复杂的模型,也许简单的矩阵分解就可以达到很好的效果,在以后的工作中可以尝试往这方面多思考一些。

Reference

[1] Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. In Proceedings of NIPS, pages 2177–2185, 2014.

[2] Yang C, Liu Z, Zhao D, et al. Network Representation Learning with Rich Text Information[C]//IJCAI. 2015: 2111-2117.

写的还不错?那就来个红包吧!
0%