Research map / Graph learning / Graph algorithms and clustering
Convergence Guarantees for the DeepWalk Embedding on Block Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that gradient-descent DeepWalk embeddings (1-dimensional, from small random initialization) provably recover clusters of a symmetric stochastic block model with high probability, via linearizing the softmax update.
Problem
Theoretical convergence guarantees for nonconvex DeepWalk/SGNS-style embedding optimization by gradient descent in low dimensions, where prior work only covered the high-dimensional matrix factorization regime or the global optimum without algorithmic analysis.
Approach
When embeddings are initialized in a small ball, the softmax matrix is close to uniform (1/n J), so the gradient update is approximately linear; the analysis tracks the projection onto the top (K-1) eigenspace of the linearized update, showing it grows geometrically and yields cluster separation and recovery.
Key results
- Theory: with small initialization norm epsilon = n^{-2/3} and Delta = n^{1/6}, DeepWalk gradient descent yields cluster means separated by at least epsilon*Delta/(20K^2 sqrt(n)) with probability at least 0.9, even for 1-dimensional embeddings.
- Approximate recovery: with high probability 1-o(1) fraction of each community is recovered (for rho in (1/3,1)).
- Experiments on K=3, n=600 SBM show clear cluster separation for 1D, 2D and 3D embeddings; the linearized update stays close to the nonlinear one for n=200 to 1000.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use 1D embeddings instead of 2D or 3D embeddings | DeepWalk · SBM (K=3, n=600, p=4q, q=0.1) | community recovery | No clear effect |
| replace the nonlinear gradient descent update with its linear approximation | DeepWalk · SBM (K=2, n=200, 500, 1000) | embedding distance | No clear effect |
Surprising findings
- Cluster structure is recovered even with one-dimensional embeddings when K>2, whereas spectral separation typically requires dimension at least K.
Limitations
- Results require p,q above n^{rho-1} and a closeness assumption between empirical and expected co-occurrence matrices, rather than tight dependence on p-q.
- Analysis is for symmetric SBM with fixed K and equal block sizes and is done in 1D; higher dimensions are only conjectured.
- Recovery guarantee is approximate (1-o(1) fraction) and does not give precise accuracy characterization.
Experimental setup
Datasets: synthetic stochastic block model graphs (n=200, 500, 600, 1000)
Metrics: distance between nonlinear and linearized embeddings over it visual cluster separation of 1D/2D/3D embeddings
Baselines: spectral embedding nonlinear gradient descent DeepWalk
Builds on: DeepWalk node2vec skip-gram with negative sampling Davis-Kahan theorem Weyl's theorem
Closest papers by meaning
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.86)
- Information Loss and Disparate Effects in Network Embeddings (NeurIPS 2026 · similarity 0.86)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.86)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.86)
- Revisiting Random Walks for Learning on Graphs (ICLR 2025 · similarity 0.86)
- Learning Representations for Hierarchies with Minimal Support (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.