10月7日论文推荐（附下载地址）- 大数跨境

首页

10月7日论文推荐（附下载地址）

学术头条

2018-10-07

导读：该论文提出了一种Multi-Level Embedding Framework(MILE)。

论文名：

MILE: A Multi-Level Framework for Scalable Graph Embedding

会议/年份：arXiv 2018

作者：

Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy

推荐理由：

该论文提出了一种Multi-Level Embedding Framework(MILE)。该框架在进行Graph Coarsening时使用的是Structural Equivalence Matching(SEM)和Normalized Heavy Edge Matching(NHEM)。SEM会匹配那些邻居完全相同的点对，NHEM根据归一化的边权大小来匹配。与HARP最大的不同之处在于MILE只在最后一个level（即Coarsest Graph）上用现有的Graph Embedding方法来学一个Base Embedding。其余level的Embedding根据一个多层的图卷积神经网络从 Base Embedding 开始Refine得到。这样做的一个最直接的好处就是时间、空间效率会有大幅提升，因为只需要在Coarsest Graph上学Embedding。图卷积神经网络的参数在level之间是共享的，并且是根据Base Embedding来学的（有点trick）。

Abstract

Recently there has been a surge of interest in designing graphembedding methods. Few, if any, can scale to a large-sizedgraph with millions of nodes due to both computational com-plexity and memory requirements. In this paper, we relaxthis limitation by introducing the MultI-Level Embedding(MILE) framework – a generic methodology allowing contem-porary graph embedding methods to scale to large graphs.

MILE repeatedly coarsens the graph into smaller ones us-ing a hybrid matching technique to maintain the backbonestructure of the graph. It then applies existing embeddingmethods on the coarsest graph and refines the embeddingsto the original graph through a novel graph convolution neu-ral network that it learns. The proposed MILE frameworkis agnostic to the underlying graph embedding techniquesand can be applied to many existing graph embedding meth-ods without modifying them.

We employ our framework onseveral popular graph embedding techniques and conductembedding for real-world graphs. Experimental results onfive large-scale datasets demonstrate that MILE significantlyboosts the speed (order of magnitude) of graph embeddingwhile also often generating embeddings of better quality forthe task of node classification. MILE can comfortably scaleto a graph with 9 million nodes and 40 million edges, onwhich existing methods run out of memory or take too longto compute on a modern workstation.