HARP  Hierarchical Representation Learning for Networks
28 Oct 2017Introduction

HARP is an architecture to learn lowdimensional node embeddings by compressing the input graph into smaller graphs.

Given a graph G = (V, E), compute a series of successively smaller (coarse) graphs G_{0}, …, G_{L}. Learn the node representations in G_{L} and successively refine the embeddings for larger graphs in the series.

The architecture is independent of the algorithms used to embed the nodes or to refine the node representations.

Graph coarsening technique that preserves global structure

Collapse edges and stars to preserve first and second order proximity.

Edge collapsing  select the subset of E such that no two edges are incident on the same vertex and merge their nodes into a single node and merge their edges as well.

Star collapsing  given star structure, collapse the pairs of neighboring nodes (of the central node).

In practice, first apply star collapsing, followed by edge collapsing.


Extending node representation from coarse graph to finer graph

Lets say node1 and node2 were merged into node12 during coarsening. First copy the representation of node12 into node1, node2.

Additionally, if hierarchical softmax was used, extend the Btree such that node12 is replaced by 2 child nodes node1 and node2.

Time complexity for HARP + DeepWalk is O(number of walks * V) while for HARP + LINE is O(number of iterations * E).

The asymptotic complexity remains the same as the HARPless version for the two cases.


Multilabel classification task shows that HAR improves all the node embedding technique with gains up to 14%.