基于谱方法的高效多级图嵌入框架

提高图嵌入的质量和效率是一直以来被关注的两个问题。一方面，图嵌入应该利用图的结构性特征以及节点的属性特征来提升嵌入的质量；另一方面，提高图嵌入方法的效率和可扩展性使其能够应用到超大规模的图上。这两个问题常常是正交的。因此，本文希望能够同时提升图嵌入的效率和质量。

图嵌入越来越多地被应用在非欧数据的表示学习上。图嵌入旨在将图中的节点映射到低位向量编码空间中并尽可能地保留节点的特征。

“如何同时有效地利用图的结构性和节点属性特征来提升表达力”以及“如何提高图嵌入的效率”一直是图嵌入关注的问题。

提高图嵌入的质量和效率常常是正交的两个问题，也是一直以来被关注的两个问题。一方面，图嵌入应该利用图的结构性特征以及节点的属性特征来提升嵌入的质量；另一方面，提高图嵌入方法的效率和可扩展性使其能够应用到超大规模的图上。因此，本文希望能够同时提升图嵌入的效率和质量。

文章提出了一个无监督的多级学习框架 GraphZoom，能够在现有无监督图嵌入方法的基础上提高其质量和效率。GraphZoom 包含以下四个过程：

1）图融合(Graph fusion)。利用节点属性相似度构建特征相似矩阵，与邻接矩阵结合的到包含结构特征和属性特征的混合邻接矩阵:

2）谱粗化(Spectral coarsening)。利用“局部谱嵌入”高效地利用混合邻接矩阵进行图嵌入，即用高斯-赛德尔迭代法解k个线性方程组得到 k 维特征表示。然后对谱亲和性更高的节点进行局部聚类，得到节点数更少的图（邻接矩阵）。如此反复。

嵌入细化(Embedding refinement)。利用拉普拉斯平滑将 3）中得到的节点表示映射到原图的每一个节点上，得到原图节点的嵌入表示。

3）利用现有图嵌入方法(DeepWalk, DGI 等)对谱粗化后的图进行嵌入。

4）

GraphZoom 在多个方法以及数据集上均实现了嵌入质量和效率的提升。谱粗化和嵌入细化两个过程一方面融合了结构和属性特征，另一方面以较低的代价将图的表示学习转化为更小规模图的嵌入，提升学习效率。GraphZoom 在 DeepWalk 和 Node2vec 方法上实现了 20× 以上的效率提升，在 DGI 上实现了 ~10× 的效率提升。

近期精彩集锦