HARP: Hierarchical Representation Learning for Networks

By Haochen Chen, Bryan Perozzi, Yifan Hu, Steven S. Skiena. 2017

392 citations recorded by the source corpus.

We present HARP, a novel method for learning low dimensional embeddings of a graph’s nodes which preserves higher-order structural features. Our proposed method achieves this by compressing the input graph prior to embedding it, effectively avoiding troublesome embedding configurations (i.e. local minima) which can pose problems to non-convex optimization. HARP works by finding a smaller graph which approximates the global structure of its input. This simplified graph is used to learn a set of initial representations, which serve as good initializations for learning representations in the original, detailed graph. We inductively extend this idea, by decomposing a graph in a series of levels, and then embed the hierarchy of graphs from the coarsest one to the original graph. HARP is a general meta-strategy to improve all of the state-of-the-art neural algorithms for embedding graphs, including DeepWalk, LINE, and Node2vec. Indeed, we demonstrate that applying HARP’s hierarchical paradigm yields improved implementations for all three of these methods, as evaluated on classification tasks on real-world graphs such as DBLP, BlogCatalog, and CiteSeer, where we achieve a performance gain over the original implementations by up to 14% Macro F1.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Representation Learning on Graphs: Methods and Applications (2017, background): “Recently, Chen et al. [13] introduced a “meta-strategy”, called HARP, for improving various random-walk approaches via a graph pre-processing step.”
Self-Supervised Learning: Generative or Contrastive (2020, methodology): “In general, existing network embedding approaches are broadly categorized as (1) factorization-based approaches such as NetMF [110], [111], GraRep [18], HOPE [102], (2) shallow embedding approaches such as DeepWalk [106], LINE [134], HARP [21], and (3) neural network approaches [19], [86].”
Network Representation Learning: A Survey (2017, methodology): “Hierarchical Representation Learning for Networks (HARP).”
Exploiting Edge Features in Graph Neural Networks. (2018, background): “Another class of approaches focus on employing a ﬂexible, stochastic measure of node similarity based on random walks, e.g. DeepWalk [22], node2vec [2], LINE [26], HARP [9], etc.”
Watch Your Step: Learning Node Embeddings via Graph Attention (2017, background): “Here we summarize two broad classes of algorithms, and point the reader to recent reviews [10, 6, 18, 14] for more context.”
Under review as a conference paper at ICLR 2019 MILE : A Multi-Level Framework for Scalable Graph Embedding (2018, positive): “The closest work to this paper is the very recently proposed HARP (Chen et al., 2018), which proposes a hierarchical paradigm for graph embedding based on iterative learning methods (e.”
Graph Clustering with Graph Neural Networks (2020, background): “could arise from clusters [9, 31, 66], for example through pooling or trainable attention over edges [59].”
Learning Graph Embedding With Adversarial Training Methods (2019, background): “Other random walk variants include hierarchical representation learning approach (HARP) [29], and discriminative deep random walk (DDRW) [30], and Walklets [31].”
Heterogeneous Information Network Embedding for Recommendation (2017, background): “The complexity of deepwalk is Oðt jVj t w ðdþ d log jVjÞÞ, where t is the number of random walk, t is the length of random walk, w is the size of neighbor, d is the embedding dimension and jVj is the number of nodes in the network [63].”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “Unlike HARP, which coarsens a graph to preserve high-level topological features, Splitter [38] is a graph embedding approach designed to better model nodes which have membership in multiple communities.”
An Overview of Deep Semi-Supervised Learning (2020, methodology): “Another family of method is random walks introduced by [119] and its variants [59, 49, 21, 1].”