Network Representation
最近看了几篇网络节点embedding的论文，思想很新颖，很有趣，这里分享给大家。
Network Representation可以翻译为网络(节点)表征、网络(节点)向量、网络(节点)嵌入等…
Aim to learn distributed vector representation for each vertex in a network.
目的是将学习图的每个节点的向量，即embedding，类似word2vec.
一旦将节点表示成向量了之后，很多问题都变得简单了，如分类、聚类、半监督学习、标签传播、图分割等等，关键就看效果了。
DeepWalk: Online Learning of Social Representations
在图上随机游走产生长度为2w+1的路径，对每个点随机 γ 个随机游走序列每一条随机游走路径便是相当于一个序列(相当于一句话,idea参考word2vec)，这样序列中的点就有上下文，定义一个时间窗口w，并进行马尔可夫假设，最后使用word2vec中的Skip-Gram训练每一个节点的向量 假设一个路径序列为 S={v1,…,v|S|} ,对于 vi∈S ,其上下文为 C={vi−w,vi−w+1,…,vi+w−1,vi+w} , 那么DeepWalk的优化目标为:
f=1|S|∑i=1|S|∑−w≤j≤w,j≠0logp(vi+j|vi)
其中,
p(vj|vi)=exp(cTvjrvi)∑v∈Cexp(cTvrvi)
rvi 是点 vi 的向量表征, cvj 是点 vi 上下文中点 vj 的向量表征DeepWalk使目标 f 最大化，使用Skip-Gram与Hierarchical Softmax进行训练得到每个点的vectorDeepWalk等价于MF(matrix factorization,矩阵分解)源码
NRL: Network Representation Learning with Rich Text Information
DeepWalk <=> MF
对于图G(V,E)
设 M 是图的邻接矩阵
设D是随机游走序列集，里面每一个元素都是 (v,c) 对, V 是点集, VC上下文点集,一般而言 |V|=|VC|
对每一个点 v∈V , 将其embedding成一个 k 维向量rv∈ℜk,k≪|V|
对每一个上下文中的点 v∈VC , 也将其embeddind成一个 k 维向量cv∈ℜk,k≪|V|
设 W=ℜk×|V|,H=ℜk×|Vc| , 那么需要证明 M=WTH
对于每一个 (v,c) 对,定义:
N(v,c)=count((v,c)∈D)
N(v)=∑c′∈VCN(v,c′)
N(c)=∑v′∈VN(v′,c)
Levy and 迷你的秀发已经证明在使用负采样(Negative Sampling)Skip-Gram中，词上下文(word-context)矩阵M如果足够大，那么M中的每一个元素：
Mij=logN(vi,cj)⋅|D|N(vi)⋅N(cj)−logn
其中,n是每一个词的上下文负采样对的个数。
同理，对于softmax的Skip-Gram:
Mij=logN(vi,cj)N(vi)
定义转移矩阵 A,Aij=1diife(i,j)∈E,else:Aij=0
定义行向量 ei={0,1}|V|,eii=1,else:0
因此, eiA 的第 j 个元素表示点i转移到点 j 的概率,eiAt的第 j 个元素表示点i经过t步转移到点 j 的概率
因此,[ei(A+A2+A3+…+At)]j是点 vj 出现在点 vi 窗口为t下文(右边)序列中的概率
因此:
N(vi,vj)N(vi)=[ei(A+A2+A3+…+At)]jt
详细证明可以参见原文。
本文方法
Low-rank MF
M∈ℜb×d,Ω={(i,j)|i∈[0,b−1],j∈[0,d−1]},W∈ℜk×b,H∈ℜk×d
minimize:
minW,H∑(i,j)∈Ω(Mij−(WTH)ij)2+λ2(||W||2F+||H||2F)
||⋅||F 是Frobenius norm
Low-rank MF即对一个低秩的M进行分解
假设我们有额外的两个特征矩阵 X∈ℜfx×b,Y∈ℜfy×d ,他们每一列表示一个对象有 fx,fy 维特征,那么minimize:
minW,H∑(i,j)∈Ω(Mij−(XTWTHY)ij)2+λ2(||W||2F+||H||2F)
具体参见:Inductive matrix completion for predicting gene-disease associations
Text-Associated DeepWalk(TADW)
Text feature matrix
T∈ℜft×|V| Speed and accuracy tradeoff
M=(A+A2)2 minimize
W∈ℜk×|V|,H∈ℜk×ft
minW,H∑(i,j)∈Ω(Mij−(WTHT)ij)2+λ2(||W||2F+||H||2F)
矩阵分解得到W,H. 即Low-rank MF中X为单位向量,Y=TTADW会收敛局部最优
wiki实验
数据
graph.txt
每一行两列，分别为两个点id，表示它们之间有边连接，无向图tfidf.txt
每一行三列，第一列是doc的id，第二列是词的id，第三列是该词的TFIDF值group.txt
每一行两列，第一列是doc的id，第二列是该doc所属的label的id超参数
W与H矩阵的维度k=80正则化参数 lambda=0.2 text Feature维度 ft =200train ratid of svm:0.1label数目15步骤
设count(d)=n=|V|,count(word)=m使用tfidf.txt构建稀疏矩阵TFIDF,对TFIDF进行SVD:
TFIDF∈ℜn×m
TFIDF=U∗S∗V
U∈ℜn×ft,S∈ℜft×ft,V∈ℜft×m
T=U∗S∈ℜ|V|×ft
这样便得到了图中每个节点的Text feature矩阵，并对T列向量进行单位向量化 构造转移矩阵A的稀疏矩阵
Aij=1diifeij∈E,else:0 构造M矩阵
M=(A+A2)2 train_mf
对M矩阵进行分解得到W与H
直接调用“Inductive matrix completion for predicting gene-disease associations”的矩阵分解, X为单位向量,Y=TSVM分类
每篇文档的向量是 WT 的行向量与 T∗HT 的行向量拼接而成,使用LibLinear中的linearsvm
LINE: Large-scale information network embedding
源码
待补充
LSHM: Learning latent representations of nodes for classifying in heterogeneous social networks
异构网络(heterogeneous) VS 同构网络(Homogeneous)
如果网络中的节点的类型都一样，即每个节点的标签集合是一样的，那么该网络是同构网络，如facebook上的好友网络，微博上的粉丝网络等。
否则，便是异构网络，如作者-论文引用网络，作者的标签是研究领域，论文的标签是其所发表的会议或者期刊。又如用户－物品网络等。Flickr数据集：用户、照片、评论、tag、朋友关系、合作关系等。DBLP数据集：作者、论文、地点、引用关系、合作关系等。假设
不同类型的节点会互相影响半监督学习算法算法优势
将点的表征映射到低维隐空间中，该映射考虑了节点标签之间的依赖、标签之间的关系、以及点的特征能够对不同类型的节点进行分类前提
图G(V,E)有是一个无向图(带权值或者不带权值)图G(V,E)有 τ=1,2,…,T 种类型的节点,N个节点, vi 的类型为 ti∈τ , 节点类型为 t 的标签集为Yt wij∈E 为节点 i,j 之间的边已有标签节点集合为 (x1,…,xl) ,个数为 l,l<N ,标签集合为 Cti,i∈[1,l] , N−l 未标注的节点如果 xi 的标签为 yi 同构网络学习模型(T=1)
(y1^,…,yN^)=argminy1~,…,yN~∑i=1lΔ(yi~,yi)+λ∑i,jwi,j||yi~−yj~||2
可以使用随机梯度下降、坐标下降法、随机游走等算法来计算模型参数。异构网络
不同类型的节点不具有传播性将异构网络分拆多个同够网络会导致不同类型节点之间的依赖信息丢失异构网络处理方法
将网络中的每个节点使用一个隐空间 ℜZ 中的向量来表示,每个节点的向量为 z 要保证相连的节点的向量相似度高(smoothness，平滑性)不同类型的节点使用不同的分类器进行分类，也就是有T个分类器(class separability，类别分离性)目标函数
smoothness
∑i,j/wi,j≠0wi,j||kkdlq−zj||2class separability
每种类型的节点都有一个分类器，设为 ftθ
那么损失函数使用hinge-loss：
∑i=1lΔ(ftiθ(kkdlq),yi)=∑k=1max{0,1−ykifti,kθ(kkdlq))}
其中, yki 为节点 i 的真实标签向量，即如果节点i的标签为 j ，那么yji=1,其它分量为-1. fti,kθ(kkdlq)) 为其分类器预测向量优化目标,minimize:
L(z,θ)=∑i=1lΔ(ftiθ(kkdlq),yi)+λ∑i,j/wi,j≠0wi,j||kkdlq−zj||2
参数: 每个节点的向量 kkdlq ,分类器的参数 θ 随机梯度下降算法
Input(G,I,θ,λ,ϵ) // I 为最大迭代次数
随机初始化每个节点的向量z
i:=0
while( i<I ):
随机选择 wi,j>0 的一对 (xi,xj)
if i≤l : // 节点i是带标签的点
θ←θ+ϵ∇θΔ(ftiθ(kkdlq),yi)
kkdlq←kkdlq+ϵ∇kkdlqΔ(ftiθ(kkdlq),yi)
end if
if j≤l : // 节点j是带标签的点
θ←θ+ϵ∇θΔ(ftjθ(zj),yj)
kkdlq←zj+ϵ∇zjΔ(ftjθ(zj),yj)
end if
kkdlq←kkdlq+ϵλ∇kkdlq||kkdlq−zj||2
zj←zj+ϵλ∇zj||kkdlq−zj||2
i:=i+1
end while
Output(kkdlq,yi)