# Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 50 references that are in the map.
- First posted on arXiv 21 Jul 2021.

## Builds on (most cited first, 13 of 13)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [HARP: Hierarchical Representation Learning for Networks](https://mlsanity.com/paper/1706.07845/) (2017)
- [Fast and Accurate Network Embeddings via Very Sparse Random Projection](https://mlsanity.com/paper/1908.11512/) (2019)
- [SSP: Semantic Space Projection for Knowledge Graph Embedding with Text Descriptions](https://mlsanity.com/paper/1604.04835/) (2016)
- [Multi-Modal Bayesian Embeddings for Learning Social Knowledge Graphs](https://mlsanity.com/paper/1508.00715/) (2015)

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

- [Convergence Guarantees for the DeepWalk Embedding on Block Models](https://mlsanity.com/paper/2410.20248/) (2024)

## Abstract (arXiv)

Graph vertex embeddings based on random walks have become increasingly influential in recent years, showing good performance in several tasks as they efficiently transform a graph into a more computationally digestible format while preserving relevant information. However, the theoretical properties of such algorithms, in particular the influence of hyperparameters and of the graph structure on their convergence behaviour, have so far not been well-understood. In this work, we provide a theoretical analysis for random-walks based embeddings techniques. Firstly, we prove that, under some weak assumptions, vertex embeddings derived from random walks do indeed converge both in the single limit of the number of random walks N → ∞ and in the double limit of both N and the length of each random walk L→∞. Secondly, we derive concentration bounds quantifying the converge rate of the corpora for the single and double limits. Thirdly, we use these results to derive a heuristic for choosing the hyperparameters N and L. We validate and illustrate the practical importance of our findings with a range of numerical and visual experiments on several graphs drawn from real-world applications.