Network Representation 网络节点嵌入

野性酷女 2022-07-19 06:00 277阅读 0赞

### 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][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进行训练得到每个点的vector
     *  DeepWalk等价于MF(matrix factorization,矩阵分解)
     *  [源码][Link 1]
 *  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 Goldberg已经证明在使用负采样(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=T
             *  TADW会收敛局部最优
     *  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=200
             *  train ratid of svm:0.1
         *  label数目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”的矩阵分解][Inductive matrix completion for predicting gene-disease associations], X为单位向量,Y=T
             *  SVM分类  
                每篇文档的向量是WT的行向量与T∗HT的行向量拼接而成,使用[LibLinear中的linearsvm][LibLinear_linearsvm]
 *  LINE: Large-scale information network embedding  
    [源码][Link 2]  
    待补充
 *  [LSHM: Learning latent representations of nodes for classifying in heterogeneous social networks][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||zi−zj||2
             *  class separability  
                每种类型的节点都有一个分类器，设为ftθ  
                那么损失函数使用hinge-loss：  
                
                
                ∑i=1lΔ(ftiθ(zi),yi)=∑k=1max\{ 0,1−ykifti,kθ(zi))\}
                
                  
                其中,yki为节点i的真实标签向量，即如果节点i的标签为j，那么yji=1,其它分量为-1.fti,kθ(zi))为其分类器预测向量
             *  优化目标,minimize:  
                
                
                L(z,θ)=∑i=1lΔ(ftiθ(zi),yi)\+λ∑i,j/wi,j≠0wi,j||zi−zj||2
                
                  
                参数: 每个节点的向量zi,分类器的参数θ
         *  随机梯度下降算法  
            Input(G,I,θ,λ,ϵ) //I为最大迭代次数  
            随机初始化每个节点的向量z  
            i:=0  
            while(i<I):  
              随机选择wi,j>0的一对(xi,xj)  
              if i≤l: // 节点i是带标签的点  
                θ←θ\+ϵ∇θΔ(ftiθ(zi),yi)  
                zi←zi\+ϵ∇ziΔ(ftiθ(zi),yi)  
              end if  
              if j≤l: // 节点j是带标签的点  
                θ←θ\+ϵ∇θΔ(ftjθ(zj),yj)  
                zi←zj\+ϵ∇zjΔ(ftjθ(zj),yj)  
              end if  
              zi←zi\+ϵλ∇zi||zi−zj||2  
              zj←zj\+ϵλ∇zj||zi−zj||2  
              i:=i+1  
            end while  
            Output(zi,yi)

[DeepWalk_ Online Learning of Social Representations]: http://www.perozzi.net/projects/deepwalk/
[Link 1]: https://github.com/phanein/deepwalk
[Inductive matrix completion for predicting gene-disease associations]: http://bigdata.ices.utexas.edu/project/gene-disease/
[LibLinear_linearsvm]: http://www.csie.ntu.edu.tw/~cjlin/liblinear/.
[Link 2]: https://github.com/tangjianpku/LINE
[LSHM_ Learning latent representations of nodes for classifying in heterogeneous social networks]: https://www.researchgate.net/publication/260433586_Learning_latent_representations_of_nodes_for_classifying_in_heterogeneous_social_networksø