# Don't Walk, Skip! Online Learning of Multi-scale Network Embeddings

arXiv: https://arxiv.org/abs/1605.02115 · HTML: https://mlsanity.com/paper/1605.02115/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 May 2016.

## Built on by (most cited first, 4 of 4)

- [A Representation Learning Framework for Property Graphs](https://mlsanity.com/paper/2206.13176/) (2022)
- [DGEM: A New Dual-modal Graph Embedding Method in Recommendation System](https://mlsanity.com/paper/2108.04031/) (2021)
- [Vaccine skepticism detection by network embedding](https://mlsanity.com/paper/2110.13619/) (2021)
- [A Complex Network based Graph Embedding Method for Link Prediction](https://mlsanity.com/paper/2209.04884/) (2022)

## Abstract (arXiv)

We present Walklets, a novel approach for learning multiscale representations of vertices in a network. In contrast to previous works, these representations explicitly encode multiscale vertex relationships in a way that is analytically derivable. Walklets generates these multiscale relationships by subsampling short random walks on the vertices of a graph. By `skipping' over steps in each random walk, our method generates a corpus of vertex pairs which are reachable via paths of a fixed length. This corpus can then be used to learn a series of latent representations, each of which captures successively higher order relationships from the adjacency matrix. We demonstrate the efficacy of Walklets's latent representations on several multi-label network classification tasks for social networks such as BlogCatalog, DBLP, Flickr, and YouTube. Our results show that Walklets outperforms new methods based on neural matrix factorization. Specifically, we outperform DeepWalk by up to 10% and LINE by 58% Micro-F1 on challenging multi-label classification tasks. Finally, Walklets is an online algorithm, and can easily scale to graphs with millions of vertices and edges.