Table of contents

HARP - Hierarchical Representation Learning for Networks[ Edit ]

- HARP is an architecture to learn low-dimensional node embeddings by compressing the input graph into smaller graphs.
- Link to the paper.
- Given a graph
*G = (V, E)*, compute a series of successively smaller (coarse) graphs*G*. Learn the node representations in_{0}, …, G_{L}*G*and successively refine the embeddings for larger graphs in the series._{L} - 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 B-tree 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 HARP-less version for the two cases.
- Multilabel classification task shows that HAR improves all the node embedding technique with gains up to 14%.

Read more…(267 words)

About the contributor:

Shagun SodhaniAnalytics and Data Science team @ Adobe Systems

100%

Loading…

Join the discussion. Add a reply…

Post

Table of contents

- Introduction

Contributor

Shagun SodhaniAnalytics and Data Science team @ Adobe Systems

100%

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.