#NE(Network Embedding)论文小览
自从word2vec横空出世,似乎一切东西都在被embedding,今天我们要关注的这个领域是Network Embedding,也就是基于一个Graph,将节点或者边投影到低维向量空间中,再用于后续的机器学习或者数据挖掘任务,对于复杂网络来说这是比较新的尝试,而且取得了一些效果。
本文大概梳理了最近几年流行的一些方法和论文,paper主要是来自thunlp/NRLPapers 这个List,并掺杂了一些其他论文。大概看了一遍,简单总结一下,希望对大家有所帮助,如有不严谨的地方,还望指正。
抛开一些传统的流形学习方法不谈,下面大概以这个outline组织(区分并不严格):
##DeepWalk(Online Learning of Social Representations.)
DeepWalk是KDD 2014的一篇文章,彼时word2vec在文本上的成功应用掀起来一波向量化的浪潮,word2vec是根据词的共现关系,将词映射到低维向量,并保留了语料中丰富的信息。DeepWalk算法思路其实很简单,对图从一个节点开始使用random walk来生成类似文本的序列数据,然后将节点id作为一个个「词」使用skip gram训练得到「词向量」。
思路虽然简单,背后是有一定道理的,后面一些工作有证明这样做其实等价于特殊矩阵分解(Matrix Factorization)。而DeepWalk本身也启发了后续的一系列工作。
node2vec在DW的基础上,定义了一个bias random walk的策略生成序列,仍然用skip gram去训练。
论文分析了BFS和DFS两种游走方式,保留的网络结构信息是不一样的。
DeepWalk中根据边的权重进行随机游走,而node2vec加了一个权重调整参数α:t是上一个节点,v是最新节点,x是候选下一个节点。d(t,x)是t到候选节点的最小跳数。
通过不同的p和q参数设置,来达到保留不同信息的目的。当p和q都是1.0的时候,它等价于DeepWalk。
DW本身是无监督的,如果能够引入label数据,生成的向量对于分类任务会有更好的作用。
之前提到过有证明DW实际上是对于一个特殊矩阵M的分解,
这篇文章将DeepWalk和Max-Margin(SVM)结合起来,从损失函数看是这两部分组成:
1.训练的时候是分开优化,固定 , 优化 和 ,其实就是multi class 的 SVM。
2.固定 和 优化 , 的时候稍微特殊一点,算了一个biased Gradient,因为损失函数里有x和w的组合。
这样在训练中同时优化discrimination和representation两部分,达到一个好的效果。
文章里有DeepWark等同于M的矩阵分解的简单证明,而在实际中,一些节点上旺旺会有文本信息,所以在矩阵分解这个框架中,将文本直接以一个子矩阵的方式加入,会使学到的向量包含更丰富的信息。
文本矩阵是对TFIDF矩阵的SVD降维结果。
沿用矩阵分解的思路,分析了不同k-step(random walk中的步数)所刻画的信息是不一样的:
LINE分析了1st order proximity和2nd order proximity,其中一度相似性就是两个点直接相连,且边权重越大说明两个点越相似,如下图中的6和7;而二度相似性则是两个点之间共享了很多邻居,则它们的相似性就很高,如下图的5和6。
文章中非常简单的方式构造了一个目标函数,能同时保留二者的信息。以一度相似性为例,节点i和j相连的经验概率就是和归一化后的权重,即 ,而通过向量计算这个概率值是 ,目标函数就是让这两个分布距离最小,选择KL散度作为距离衡量函数就得到了最后的损失函数 。
其中还有个优化的trick,edge-sampling algorithm:因为边的weight差异很大,直接用SGD效果不好,所以有个edge的采样,按照边的weight采样,然后每条边当做binary的算。
这一篇是最近发表在IJCAI上的文章,说实话是一个很取巧的方式,文章分析了一些可以视为矩阵分解的embedding方法:
首先考虑了节点上的Context,主要是文本,学习对每个节点产出Vt(文本向量)和Vs(结构向量)
Context-Free的话Vt是固定的,采用一个CNN的流程产出,如下图左边部分:对于一个文本,每个词的向量组成一个矩阵,然后以 为窗口在d个kernel上进行CNN的卷积操作,得到的结果按行取max来获得最后的文本向量。
Context-Aware的话引入了Attention机制,会考虑边e=(u,v)的tu和tv,通过下右图的流程产出Attention权重,再进行类似Pooling的操作(最后一步),这样节点在和不同的点连接的时候其作用是不一样的。
A是引入的待训练参数,物理意义可能为目标维的空间变换。
这篇文章将文本转化为特殊的节点,这样就有两种连边,(节点-文档)以及(节点-节点),对两种边一起建模,损失函数包括 和 ,其中文本拆分为更细的句子,而句子有三种方式去embedding,下面有列举。
和很多方法一样,Loss的减数部分是负采样出来的。
这篇paper也是最新2017在IJCAI上发表的,引入了机器翻译的思想,将Translation机制应用到中间,通过一个Autoencode对边上的labels(构成一个向量)进行编码,然后将节点和edge映射到同一个空间作加减。认为在这个空间里u+l=v’(每个节点有两个向量表示,分别指示在边的「起点」和「终点」时,用’进行区分)
这样预测的时候,简单用v’-u 就可以得到l,再用AE的解码器部分还原为element-binary的label set,就得到预测结果。
##Deep Learning
最近几年深度学习如火如荼,严格来说,类似word2vec其实属于浅层模型,但你也可以用一些复杂的深度模型去获得embedding结果,这个思路是将网络序列化,借用NLP的方法去训练。
###SSC-GCN(Semi-Supervised Classification with Graph Convolutional Networks)
https://github.com/tkipf/gcn
http://tkipf.github.io/graph-convolutional-networks/
和DW完全不同的思路,引入了一个spectral convolutions操作,不过目前看起来卷积是在整个图上做的,还没有支持mini-batch,最后目标是单个节点的分类和表示学习。
在之前的一些工作中,NN for graph都是对图级别做的,做分类等等,针对整个sub-graph,但这里本质上还是对单个节点。
###SDNE(Structural Deep Network Embedding)
##Heterogeneous
真实世界中的网络毫无疑问是异构的(Heterogenous),比如交易中,涉及到的节点有人、商品、店铺等等;更一般的比如知识图谱中有不同类型的节点和边,而前面描述的绝大部分工作都是在同构网络(Homogenous)的基础上进行的,所以了解异构网络的embedding对真正在实际中的应用会有帮助。
###PTE(Predictive Text Embedding through Large-scale Heterogeneous Text Networks.)
###HINES(Heterogeneous Information Network Embedding for Meta Path based Proximity)
##总结
Network Embedding是最近几年还是有蛮多工作的,这里只列举了一些。虽然NE从NLP里借鉴了很多的思想,但二者还是有一些不同的,a.如果以节点id作为「词」,那么对于一些真实的网络来说,可能会非常稀疏,而且节点的数量会非常大,上亿是很正常的,这对上面一些方法的应用有一些限制,你可以想象存这样大的一张此表需要多大的内存。b.异构网络如何能够更好地被训练,是一个很有挑战的事情;同时节点和边上往往有着各种丰富的信息,如何能够将这些信息都学到结果向量中,也是很有意思的。
本文并没有非常详细地去讲每篇论文,只是记录了主要思路,有兴趣可以去读原始论文。
##Reference
【0】上面每一个子标题括号中的内容就是对应的论文题目。
【1】THUNLP_NRLpapers
【2】《Representation Learning with Networks》by Jure Leskovec.slide_01
联系客服