Graph2vec

Graph2vec

出自MLGWorkshop 2017的《graph2vec: Learning Distributed Representations of Graphs》

问题

现如今的很多研究集中在如何表示图谱中子结构的分布式表示，如节点、子图等。但是在对图的分类和聚类这些知识图谱的分析任务中，如果采用现有的手段，我们就需要得到整个图谱的表示。因此在处理这些分析任务时，图核（Graph Kernel）方法更加有效。

Graph Kernel 方法将机器学习中的核方法（Kernel Methods）拓展到了图结构数据上，是一类计算图与图之间相似度的方法。再利用图核方法比较两个图的相似度时，需要将两个图用一定方法（如最小路径，随机游走，小图等）分解成更小的子结构，再通过定义一个核函数来的到两个图的相似度（如计算两个图中相似的子结构个数）

为什么是Graph Kernels而不是用Graph Embedding？

因为后者将结构化数据降维到向量空间时，损失了大量结构化信息。而前者直接面向图结构的数据，保留了核函数高效计算的优点，又包含了结构化的信息。

文章提出，这种方式有两种存在的问题：

1.不能得到显式的图嵌入，不利于计算和学习。

2.“人为”定义的特征（路径，步伐）不具有概括性。

这些“人为”的特征应用在大型数据集上时，会产生高维的，稀疏的，不光滑的表示。

解决手段

为了解决上述的问题，文章提出了将word2vec中的Skipgram模型引入到了图谱中。再word2vec中，Skipgram的核心思想是出现在相似上下文中的单词往往具有相似的含义，因此应具有相似的矢量表示。

之前讲过的Doc2vec的也实在此基础上提出的。

根据文章中graph2vec的思想，我们可以把一个图谱看作是一个文件（document），把图谱中的所有节点（node）周围的有根子图（rooted subgraph）看作是词（words）。换句话说，有根子图构成图谱的方式和词构成句子或段落的方式相同。具体形式如下：