刘晓霞 从点嵌入到团嵌入
新闻来源:IR实验室       发布时间:2017/4/7 3:27:33

  这篇论文题目为《From Node Embedding To Community Embedding》,于20161031号发表在arXiv上,作者分别来自于新加坡ADSC中心、南洋理工大学和伊利诺伊大学。本文主要关注的研究问题是如何将图映射到低维向量空间,包括图中点的映射和团的映射。本文是第一个提出团嵌入这一概念,并且通过点嵌入和团嵌入相互增强的方式来得到最优的点嵌入和团嵌入,在BlogcatalogFlickr这两个实际数据集上进行聚类和分类的实验结果表明,本文提出的方法ComEmbed比当前点嵌入方面最好的方法DeepWalkNode2vecLINE的性能要高,证明了本文提出方法的有效性。         

  首先给出问题的定义:给定一个图G=(V, E),对于团中的每个点会有一个点向量表示 ,基于高斯混合模型将图中的每个团看做一个多元高斯模型,对于图中每个团有一个团表示( ),其中是高斯平均向量,用来表示团的中心,是高斯协方差矩阵,用来表示团中节点之间的相关程度。最终要输出每个团的团表示和每个点的点向量。

  本文采用了三种不同的策略来考虑图中两个节点之间的关联程度,1)一步连接:即两个节点在图中有连边,那么这两个节点的点向量是相似的;2)二步连接:如果两个点有共同的“邻居”节点,那么这两个点的点向量在向量空间上是相似的,这里的“邻居”是一个广义的概念,本文采用随机游走的方法来确定目标节点的邻居节点(上下文节点),从目标节点出发,随机游走t步可到达的节点作为目标节点的邻居节点,目标节点和它的邻居节点的点向量是相似的;3)高步连接,如果节点属于同一个团,那么这些节点的点向量应该是相似的,同时这些节点与所属团的中心距离较近,即在当前团产生的条件下,属于该团的节点之间的点向量是相似的。根据以上三种评价两个节点关联程度的标准,可以得到三个目标函数,通过优化这三个目标函数,最终可以得到最优的每个点的点向量表示和每个团的团表示。

  本文实验主要基于Blogcatalog和Flickr这两个实际数据集,分别在其上做了聚类和分类任务,聚类以Conductance和NMI来作为评价指标,比baseline分别提高4.0%-5.5%(conductance)和5.3%-11.2%(NMI);分类以micro-F1和macro-F1来作为评价指标,比baseline分别提高7.6%-10.2%(micro-F1)和14.1%-91.8%(macro-F1),实验结果表明本文提出方法的有效性。