论文解读(GraRep)《GraRep: Learning Graph Representations with Global Structural Information》

发布于 2022年 01月 24日 00:43

论文题目:《GraRep: Learning Graph Representations with Global Structural Information》
发表时间:  CIKM
论文作者:  Shaosheng Cao; Wei Lu;  Qiongkai Xu
论文地址:  Download
Github:      Go


Abstract

  在本文中,我们提出了一种新的学习加权图顶点表示的GraRep模型。该模型学习低维向量来表示出现在图中的顶点,与现有的工作不同,它将图的全局结构信息集成到学习过程中。


1. Introduction

  先引入 NE 的概念,然后介绍一下  DeepWalk ,但是作者抛出了一个问题,虽然  DeepWalk  确实有效果,但是为什么这么定义损失函数就可以得出效果呢?损失函数的可解释性并没有在  DeepWalk  论文中被谈及。

  文中提到  skip-gram  模型其实就是用来量化两个节点的  𝑘k  阶关系(k-step relationship),所谓  𝑘k  阶关系就是两个顶点可以通过  𝑘k  步相连的关系。skip-gram  实际上是将节点之间的这种关系投影到一个平凡子空间(common subspace)中。而本文则是将k阶关系投影到独立的子空间(distict subspace)中。简单来说就是,skip-gram  模型将网络节点表示成向量后,节点的  11  到  𝑘k  阶关系全都综合反映到这个向量中。而GraRep则选择将  11  到  𝑘k  总共  𝑘k 种关系分开,分别形成  𝑘k 个向量,每个向量表示一种关系。

  另一种方法 LINE,则是根本无法获取到  𝑘>2k>2  的节点关系。作者认为节点之间的  𝑘k  阶关系对把握网络的全局特征非常重要,越高阶的关系(也就是 𝑘k  越大)被考虑进来,得到的网络表示结果会越好。

  本文的大致思路是通过矩阵分解的(matrix factorization)方法分别学习网络节点的  𝑘k  阶关系表示,然后将  𝑘k  个表示结合起来作为最终的表示结果。

  总结一下贡献:

    • 提出学习图节点潜在向量表达的模型,能够捕获全局结构信息
    • 从概率观点对  DeepWalk  中同一采样的理解
    • 分析了负抽样相关的  Skip-Gram  模型的不足。

2. RELATED WORK

2.1 Linear Sequence Representation Methods

  由 streams of words 组成的 Natural language corpora 可以看作是特殊的图结构,即  linear chains。目前,学习单词表征的方法有两种主要方法:neural embedding methods 和  matrix factorization based approaches 。

  Neural embedding methods 采用 a fixed slide window 去捕捉当前单词的上下文词,例子:  skip-gram。

   虽然这些方法可能在某些任务上产生良好的性能,但由于它们使用单独的 local context windows ,而不是 global co-occurrence counts,因此它们在某些情况很差地捕获有用的信息。另一方面,矩阵分解的方法可以很好的利用  global statistics。

2.2 Graph Representation Approaches

  经典的降维方法:

    multidimensional scaling (MDS)、IsoMap 、LLE 、and Laplacian Eigenmaps 。

  举例描述最近的一些 Graph Representation Approaches 。

3. Grarep model

3.1 Graphs and Their Representations

  Definition 1. (Graph) A graph is defined as 𝐺=(𝑉,𝐸)G=(V,E). 𝑉={𝑣1,𝑣2,,𝑣𝑛}V={v1,v2,,vn} is the set of vertices with each 𝑉V indicating one object while 𝐸={𝑒𝑖,𝑗}E={ei,j} is the set of edges with each 𝐸E indicating the relationship between two vertices. A path is a sequence of edges which connect a sequence of vertices.

  Some definitions:

    • 𝑆S:adjacency matrix 。对于无权图:𝑆𝑖,𝑗=1Si,j=1 if and only if there exists an edge from 𝑣𝑖vi to 𝑣𝑗vj, and 𝑆𝑖,𝑗=0Si,j=0 otherwise。对于带权图:𝑆𝑖,𝑗Si,j is a real number called the weight of the edge 𝑒𝑖,𝑗ei,j
    • 𝐷D:diagonal matrix。

        𝐷𝑖𝑗={𝑝𝑆𝑖𝑝,0, if 𝑖=𝑗 if 𝑖𝑗Dij={pSip, if i=j0, if ij

  定义从一个顶点  𝑣𝑖vi  到  𝑣𝑗vj  另一个顶点的转换概率,定义以下  (1-step) probability transition matrix :

     𝐴=𝐷1𝑆A=D1S

  该公式可以参考《邻接矩阵、度矩阵》

  Definition 2. (Graph Representations with Global Structural Information) Given a graph 𝐺G, the task of Learning Graph Representations with Global Structural Information aims to learn a global representation matrix 𝑊|𝑉|×𝑑WR|V|×d for the complete graph, whose 𝑖i-th row 𝑊𝑖Wi is a 𝑑d-dimensional vector representing the vertex 𝑣𝑖vi in the graph 𝐺G where the global structural information of the graph can be captured in such vectors.

  在本文中,全局结构信息有两个功能:

    1. the capture of long distance relationship between two different vertices
    2. the consideration of distinct connections in terms of different transitional steps.

  为了验证这一点,Figure 1 给出了一些说明性的例子,说明了 k-step (对于 k=1、2、3、4 )关系信息的重要性,这些信息需要在顶点 A1 A2 之间捕获。

        

  
   Here, (a) and (e) show the importance of capturing the simple 1-step information between the two vertices which are directly connected to each other, where one has a stronger relation and the other has a weaker relation.

  In (b) and (f), 2-step information is shown, where in (b) both vertices share many common neighbors, and in (f) only one neighbor is shared between them. Clearly, 2- step information is important in capturing how strong the connection between the two vertices is – the more common neighbors they share, the stronger the relation between them is.

  In (c) and (g), the importance of 3-step information is illustrated. Specifically, in (g), despite the strong relation between  A1 and B, the relation between A1 and A2 can be weakened due to the two weaker edges connecting B and C, as well as C and A2. In contrast, in (c), the relation between A1 and A2 remains strong because of the large number of common neighbors between B and A2 which strengthened  their relation. Clearly such 3-step information is essential to be captured when learning a good graph representation with global structural information.

  Similarly, the 4-step information can also be crucial in revealing the global structural properties of the graph, as illustrated in (d) and (h). Here, in (d), the relation between A1 and A2 is clearly strong, while in (h) the two vertices are unrelated since there does not exist a path from one vertex to the other. In the absence of 4-step relational information, such important distinctions can not be properly captured.
上图解释 

  总结:一阶邻居带来的信息很重要,k-step 之间的邻居信息受到中间邻居之间的影响。

  现在思考是否考虑对不同的 k-step 进行区别对待?当然。

      

  我们认为,在学习图表示时,区别对待不同的  k-step  信息是必要的。我们在 Figure 2 的 (a) 中提供了一个简单的图。让我们重点学习图中  A  顶点的表示。我们可以看到, A  在学习其表示时接收到两种类型的信息:来自  B  的 1-step 信息,以及来自所有  C  顶点的  2-step  信息。我们注意到,如果我们不区分这两种不同类型的信息,我们可以构建一个替代图,如 Figure 2 中的(b)所示,其中  a  接收的信息与 (a) 完全相同,但具有完全不同的结构。

3.2 Loss Function On Graph

  现在考虑从顶点  𝑤w  到顶点 𝑐c  ,设从顶点  𝑤w  到顶点 𝑐c 的概率转移为 𝑝𝑘(𝑐𝑤)pk(cw)。我们已经知道  1𝑠𝑡𝑒𝑝1step  是什么,为了计算 𝑘𝑠𝑡𝑒𝑝kstep ,我们引入了下面的  k-step probability transition matrix:

    𝐴𝑘=𝐴𝐴𝑘Ak=AAk

   我们可以观察到,𝐴𝑘𝑖,𝑗Ai,jk  恰好是指从顶点 𝑖i  到顶点  𝑗j  的转移概率,其中转移恰好由  𝑘k 步组成。这将直接导致:

    𝑝𝑘(𝑐𝑤)=𝐴𝑘𝑤,𝑐pk(cw)=Aw,ck

  其中,  𝐴𝑘𝑤,𝑐Aw,ck  是矩阵  𝐴𝑘Ak  的第  𝑤w  行和第  𝑐c  列中的元素。.

  那么优化目标就是:对于任意的一个  (𝑤,𝑐)(w,c)  的组合,最大化这个组合所代表的路径在图中的概率,最小化除了这个组合外在图中的概率。换句话说,对于所有的  (𝑤,𝑐)(w,c)   组合对,如果   (𝑤,𝑐)(w,c)  所代表的路径在图中,那么增大它的概率;如果  (𝑤,𝑐)(w,c)   所代表的路径不在图中,那么减小它的概率。

  本文使用了 NCE 损失函数来反应这种特性,损失函数的定义是:

    𝐿𝑘=𝑤𝑉𝐿𝑘(𝑤)Lk=wVLk(w)

  其中 

    𝐿𝑘(𝑤)=(𝑐𝑉𝑝𝑘(𝑐𝑤)log𝜎(𝑤⃗ 𝑐⃗ ))+𝜆𝔼𝑐𝑝𝑘(𝑉)[log𝜎(𝑤⃗ 𝑐⃗ )](1)Lk(w)=(cVpk(cw)logσ(wc))+λEcpk(V)[logσ(wc)](1) 

    𝜎(𝑥)=(1+𝑒𝑥)1σ(x)=(1+ex)1

    𝜆λ 是一个表示负样本数量的超参数;

    𝑝𝑘(𝑉)pk(V) 是图中顶点上的分布;

    𝔼𝑐𝑝𝑘(𝑉)[]Ecpk(V)[] 是当  𝑐c  遵循  𝑝𝑘(𝑉)pk(V)  分布时的期望值;

       𝑐c 是通过  negative sampling  获得的;

  对于  (1)(1) 式:

    • 前项中的 𝜎(𝑤⃗ 𝑐⃗ )σ(wc) 理解为 Graph 中节点对 (𝑤,𝑐)(w,c) 共同出现的概率,要最大化这个值。
    • 后项中的 𝜎(𝑤⃗ 𝑐⃗ )σ(wc)  理解为 对于任意选取的节点  𝑐c  所形成的  (𝑤,𝑐)(w,c)  要最小化其出现的概率,最小化其出现概率就是最大化  𝜎(𝑤⃗ 𝑐⃗ )σ(wc)  。

  对于 (1)(1)  式后项negative sampling 部分中的 𝔼𝑐𝑝𝑘(𝑉)[log𝜎(𝑤⃗ 𝑐)]Ecpk(V)[logσ(wc)]

    =𝑝𝑘(𝑐)log𝜎(𝑤⃗ 𝑐⃗ )+𝑐𝑉{𝑐}𝑝𝑘(𝑐)log𝜎(𝑤⃗ 𝑐)(2)=pk(c)logσ(wc)+cV{c}pk(c)logσ(wc)(2)

  对于  (2)(2) 式:

    • 𝑝𝑘(𝑉)pk(V)  是网络中节点的概率分布。negative sampling 部分实际上就是节点  𝑐c  服从  𝑝𝑘(𝑉)pk(V)  分布时 (𝑤,𝑐)(w,c) 不出现的期望。对于随机采样的一个节点  𝑐c  ,如果正好选到了正确的节点  𝑐c,那么对应的就是  (2)(2)  中前项;如果没有选到  𝑐c ,那么对应的就是  (2)(2)  中后项。因此对于一个特定的  (𝑤,𝑐)(w,c) 组合对来说,损失函数表达如下:

      𝐿𝑘(𝑤,𝑐)=𝑝𝑘(𝑐𝑤)log𝜎(𝑤⃗ 𝑐⃗ )+𝜆𝑝𝑘(𝑐)log𝜎(𝑤⃗ 𝑐⃗ )(3)Lk(w,c)=pk(cw)logσ(wc)+λpk(c)logσ(wc)(3)

  文中提到:随着  𝑘k  的增长,𝑤w  经过  𝑘k  步到达  𝑐c  的概率会逐渐收敛到一个固定值。  

  计算  𝑝𝑘(𝑐)pk(c) :任一节点经过  𝑘k  步到达节点  𝑐c  的概率,因此等于所有  𝑘k  步可以到达  𝑐c  的路径的概率加和。

    𝑝𝑘(𝑐)=𝑤𝑞(𝑤),𝑝𝑘(𝑐𝑤)=1𝑁𝑤𝐴𝑘𝑤,𝑐pk(c)=wq(w),pk(cw)=1NwAw,ck

   其中:

    𝑞(𝜔)=1𝑁,𝑝𝑘(𝑐𝜔)=𝐴𝑘𝜔,𝑐q(ω)=1N,pk(cω)=Aω,ck

    𝑁N 是图  𝐺G 中的顶点数。

    𝑞(𝑤)q(w) 为选择  𝑤w  作为路径中的第一个顶点的概率,这里假设为均匀分布。

  将  𝑝𝑘(𝑐𝑤),𝑝𝑘(𝑐)pk(cw),pk(c)  代入 (3)(3)  式得到:

     𝐿𝑘(𝑤,𝑐)=𝐴𝑘𝑤,𝑐log𝜎(𝑤⃗ 𝑐⃗ )+𝜆𝑁𝑤𝐴𝑘𝑤,𝑐log𝜎(𝑤⃗ 𝑐⃗ )(4)Lk(w,c)=Aw,cklogσ(wc)+λNwAw,cklogσ(wc)(4)

  我们令  𝑒=𝑤⃗ 𝑐⃗ e=wc  ,对   𝐿𝑘(𝑤)Lk(w)  求偏导,并令   𝐿𝑘𝑒=0Lke=0  

  推导过程如下:

    令   𝑥=𝑤⃗ 𝑐⃗ x=wc,   𝐴𝑘𝑤,𝑐=𝐴Aw,ck=A,   𝜆𝑁𝑤𝐴𝑘𝑤,𝑐=𝐵λNwAw,ck=B 

    那么 𝐿𝑘=𝐴log𝜎(𝑥)+𝐵log𝜎(𝑥)Lk=Alogσ(x)+Blogσ(x)

      𝐿𝑘𝑥=𝐴𝜎(𝑥)𝜎(𝑥)+𝐵𝜎(𝑥)𝜎(𝑥)=𝐴𝜎(𝑥)(1𝜎(𝑥))𝜎(𝑥)𝐵𝜎(𝑥)(1𝜎(𝑥))𝜎(𝑥)Lkx=Aσ(x)σ(x)+Bσ(x)σ(x)=Aσ(x)(1σ(x))σ(x)Bσ(x)(1σ(x))σ(x)

      =𝐴(1𝜎(𝑥))𝐵(1𝜎(𝑥))=𝐴(111+𝑒𝑥)𝐵(111+𝑒𝑥)=𝐴𝑒𝑥1+𝑒𝑥𝐵𝑒𝑥1+𝑒𝑥=𝐴1𝑒𝑥+1𝐵𝑒𝑥1+𝑒𝑥=0.𝑒𝑥=𝐴𝐵,𝑥=log𝐴𝐵=log𝐴𝑘𝑤,𝑐𝑤𝐴𝑘𝑤,𝑐log𝜆𝑁=A(1σ(x))B(1σ(x))=A(111+ex)B(111+ex)=Aex1+exBex1+ex=A1ex+1Bex1+ex=0.ex=AB,x=logAB=logAw,ckwAw,cklogλN

  最终得到:

    𝑤⃗ 𝑐⃗ =log(𝐴𝑘𝑤,𝑐𝑤𝐴𝑘𝑤,𝑐)log(𝛽)wc=log(Aw,ckwAw,ck)log(β)

  其中  𝛽=𝜆𝑁β=λN

  这得出结论,我们基本上需要将矩阵 𝑌Y 分解成两个矩阵  𝑊W  和  𝐶C  ,其中  𝑊W  的每一行和  𝐶C  的每一行分别由顶点  𝑤w  和  𝑐c  的向量表示组成,𝑌Y  的条目为:

  之前的工作是为了找到这样一个矩阵  𝑌Y  ,它编码了网络中所有节点相互之间的关系,但是这个矩阵的维数很高(|𝑉|×|𝑉||V|×|V|),不能直接用来作为网络的表示。因此要用矩阵分解的方法对  𝑌Y  进行分解,分解后形成的  𝑊𝐶WC  矩阵维数要远远小于  𝑌Y  的维度,其中  𝑊W  的每一行和  𝐶C  的每一行分别由顶点  𝑤w  和  𝑐c  的向量表示组成,而这个  𝑊W  矩阵就是网络节点的表示,𝐶C  矩阵就是上下文节点的表示(不关心这个矩阵):

    𝑌𝑘𝑖,𝑗=𝑊𝑘𝑖𝐶𝑘𝑗=log(𝐴𝑘𝑖,𝑗𝑡𝐴𝑘𝑡,𝑗)log(𝛽)Yi,jk=WikCjk=log(Ai,jktAt,jk)log(β)

3.3 Optimization with Matrix Factorization

  为了降低误差,将矩阵  𝑌Y  中负值全被替换为  00 ,形成一个新的矩阵  𝑋X

    𝑋𝑘𝑖,𝑗=max(𝑌𝑘𝑖,𝑗,0)Xi,jk=max(Yi,jk,0)

   这里采用  𝑆𝑉𝐷SVD  分解,矩阵  𝑋X   被分解为:

    𝑋𝑘=𝑈𝑘Σ𝑘(𝑉𝑘)𝑇Xk=UkΣk(Vk)T

  其中  𝑈U  和  𝑉V  是正交矩阵,ΣΣ  是由奇异值的有序列表组成的对角矩阵。

  接下来用SVD方法将矩阵  𝑋X  分解成:

    𝑋𝑘=𝑈𝑘Σ𝑘(𝑉𝑘)𝑇Xk=UkΣk(Vk)T

  因为最终的网络表示要求是  𝑑d  维的,那么进一步将  𝑋X  分解为:

    𝑋𝑘𝑋𝑘𝑑=𝑈𝑘𝑑Σ𝑘𝑑(𝑉𝑘𝑑)𝑇XkXdk=UdkΣdk(Vdk)T

  其中:Σ𝑘𝑑Σdk  是由 top  d  奇异值组成 的,而且 𝑈𝑘𝑑Udk  和   𝑉𝑘𝑑Vdk  分别是  𝑈𝑘Uk  和  𝑉𝑘Vk 前  𝑑d  列组成。

  最后得到:

    𝑋𝑘𝑋𝑘𝑑=𝑊𝑘𝐶𝑘XkXdk=WkCk

  其中:

    𝑊𝑘=𝑈𝑘𝑑(Σ𝑘𝑑)12,𝐶𝑘=(Σ𝑘𝑑)12𝑉𝑘𝑇𝑑Wk=Udk(Σdk)12,Ck=(Σdk)12VdkT

4. Algorithm

  Step 1. Get  𝑘𝑠𝑡𝑒𝑝kstep transition probability matrix  𝐴𝑘Ak  for each  𝑘=1,2,...,𝐾k=1,2,...,K.

  Step 2. Get each  𝑘𝑠𝑡𝑒𝑝kstep  representation

  Step 3. Concatenate all  𝑘𝑠𝑡𝑒𝑝kstep  representations

        

CONCLUSIONS

  除了公式多,其他没啥...............那天心情好了补完。

  更多内容可以参考

  https://zhuanlan.zhihu.com/p/46446600

  https://blog.csdn.net/weixin_40675092/article/details/118225889

『总结不易,加个关注呗!』 

 


__EOF__

  • 本文作者: Blair
  • 本文链接: https://www.cnblogs.com/BlairGrowing/p/15608241.html
  • 关于博主: 评论和私信会在第一时间回复。或者直接私信我。
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
  • 声援博主: 如果您觉得文章对您有帮助,可以点击文章右下角推荐一下。
  • 推荐文章