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

论文名：

HARP: Hierarchical Representation Learning for Networks

会议/年份：AAAI 2018

作者：

Haochen Chen, Bryan Perozzi, Yifan Hu, Steven Skiena

推荐理由：

该论文提出了一种多层次的图表示学习的框架，可以提高原有的Graph Embedding方法（包括DeepWalk, LINE, Node2vec）的效果。框架首先从原 graph 开始一层层合并点（coarsen），再从最 coarse 的 graph 开始套用现有方法得到 embedding，并将其作为合并前的对应点的 initialization 进行新一轮的 embedding，直至返回原 graph。该框架在进行Graph Coarsening的时候，除了使用普通的Edge Collapsing来保持first-order proximity，也根据在真实数据上的观察提出了新的Star Collapsing来保持second-order proximity。最后，由于Graph Coarsening过程中图的节点数和边数呈指数级衰减，所以总体复杂度与原Graph Embedding方法相同。

Abstract

We present HARP, a novel method for learning low dimensionalembeddings of a graph’s nodes which preserves higherorderstructural features. Our proposed method achieves thisby compressing the input graph prior to embedding it, effectivelyavoiding troublesome embedding configurations (i.e.local minima) which can pose problems to non-convex optimization.

HARP works by finding a smaller graph which approximatesthe global structure of its input. This simplified graph is usedto learn a set of initial representations, which serve as goodinitializations for learning representations in the original, detailedgraph. We inductively extend this idea, by decomposinga graph in a series of levels, and then embed the hierarchyof graphs from the coarsest one to the original graph.

HARP is a general meta-strategy to improve all of the stateof-the-artneural algorithms for embedding graphs, includingDeepWalk, LINE, and Node2vec. Indeed, we demonstrate thatapplying HARP’s hierarchical paradigm yields improved implementationsfor all three of these methods, as evaluated onclassification tasks on real-world graphs such as DBLP, BlogCatalog,and CiteSeer, where we achieve a performance gainover the original implementations by up to 14% Macro F1.

论文下载链接

https://www.aminer.cn/archive/harp-hierarchical-representation-learning-for-networks/599c7988601a182cd2648d44