# Convergence Guarantees for the DeepWalk Embedding on Block Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 26 Oct 2024.

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

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [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)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data](https://mlsanity.com/paper/2105.07536/) (2021)
- [Clustering with t-SNE, provably](https://mlsanity.com/paper/1706.02582/) (2017)
- [An Analysis of the t-SNE Algorithm for Data Visualization](https://mlsanity.com/paper/1803.01768/) (2018)
- [InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity](https://mlsanity.com/paper/2006.00094/) (2020)
- [The Dynamics of Gradient Descent for Overparametrized Neural Networks](https://mlsanity.com/paper/2105.06569/) (2021)
- [Community detection using low-dimensional network embedding algorithms](https://mlsanity.com/paper/2111.05267/) (2021)
- [Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings](https://mlsanity.com/paper/2107.10014/) (2021)

## Abstract (arXiv)

Graph embeddings have emerged as a powerful tool for understanding the structure of graphs. Unlike classical spectral methods, recent methods such as DeepWalk, Node2Vec, etc. are based on solving nonlinear optimization problems on the graph, using local information obtained by performing random walks. These techniques have empirically been shown to produce ''better'' embeddings than their classical counterparts. However, due to their reliance on solving a nonconvex optimization problem, obtaining theoretical guarantees on the properties of the solution has remained a challenge, even for simple classes of graphs. In this work, we show convergence properties for the DeepWalk algorithm on graphs obtained from the Stochastic Block Model (SBM). Despite being simplistic, the SBM has proved to be a classic model for analyzing the behavior of algorithms on large graphs. Our results mirror the existing ones for spectral embeddings on SBMs, showing that even in the case of one-dimensional embeddings, the output of the DeepWalk algorithm provably recovers the cluster structure with high probability.