GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding
GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Chenhui Deng;Zhiqiang Zhao;Yongyu Wang;Zhiru Zhang;Zhuo Feng
中科院分区：
文献类型：
--
作者：
Chenhui Deng;Zhiqiang Zhao;Yongyu Wang;Zhiru Zhang;Zhuo Feng
图嵌入技术已经越来越多地应用于涉及非欧几里德数据学习的众多不同应用中。然而，现有的图嵌入模型要么在训练过程中无法纳入节点属性信息，要么存在节点属性噪声，影响了模型的准确性。此外，由于它们的高计算复杂度和内存使用，很少有它们可以扩展到大型图形。在本文中，我们提出了GraphZoom，这是一个多级框架，用于提高无监督图嵌入算法的准确性和可扩展性。GraphZoom首先进行图融合，生成一个新的图，该图有效地编码了原图的拓扑结构和节点属性信息。然后通过合并具有高光谱相似性的节点，将融合后的图反复粗化成更小的图。GraphZoom允许将任何现有的嵌入方法应用于粗化的图，然后逐步将在最粗级别获得的嵌入细化为越来越精细的图。我们已经在一些流行的图数据集上评估了我们的方法，用于转换和归纳任务。我们的实验表明，与目前最先进的无监督嵌入方法相比，GraphZoom可以大幅提高分类精度，并显著加快整个图嵌入过程，速度可达40.8倍。
Graph embedding techniques have been increasingly deployed in a multitude of different applications that involve learning on non-Euclidean data. However, existing graph embedding models either fail to incorporate node attribute information during training or suffer from node attribute noise, which compromises the accuracy. Moreover, very few of them scale to large graphs due to their high computational complexity and memory usage. In this paper we propose GraphZoom, a multi-level framework for improving both accuracy and scalability of unsupervised graph embedding algorithms. GraphZoom first performs graph fusion to generate a new graph that effectively encodes the topology of the original graph and the node attribute information. This fused graph is then repeatedly coarsened into much smaller graphs by merging nodes with high spectral similarities. GraphZoom allows any existing embedding methods to be applied to the coarsened graph, before it progressively refine the embeddings obtained at the coarsest level to increasingly finer graphs. We have evaluated our approach on a number of popular graph datasets for both transductive and inductive tasks. Our experiments show that GraphZoom can substantially increase the classification accuracy and significantly accelerate the entire graph embedding process by up to 40.8x, when compared to the state-of-the-art unsupervised embedding methods.