Research map / Learning theory and algorithms / Clustering
A Theoretical Analysis of DeepWalk and Node2vec for Exact Recovery of Community Structures in Stochastic Blockmodels
Yichi Zhang, Minh Tang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase n (1500 vs 600) for SVD-based node2vec | SVD-based node2vec (t_U=5) · SBM B, rho=3n^-1/2 | proportion of perfect recovery: 0.30 -> 0.86 | Improved |
| increase n (1500 vs 600) for original node2vec | Original node2vec (t_U=5) · SBM B, rho=3n^-1/2 | proportion of perfect recovery: 0.01 -> 0.57 | Improved |
| make graph denser (rho=3n^-1/3 instead of 3n^-1/2) | SVD-based node2vec · SBM B, n=600 | proportion of perfect recovery: 0.30 -> 1.00 | Improved |
| increase window size t_U from 5 to 8 | Original node2vec · SBM B-natural, rho=3n^-1/3, n=600 | proportion of perfect recovery: 1.00 -> 0.45 | Hurt |
| use SVD-based instead of SGD-based node2vec | node2vec · SBM B-natural, rho=3n^-1/2, n=900 | proportion of perfect recovery: 0.00 -> 0.58 | Improved |
| replace K-means with GMM clustering on original node2vec embeddings (ablation) | Original node2vec · SBM B1 n=600, rho=3n^-1/2 | clustering accuracy: 0.58 -> 0.84 | Improved |
| increase t_U from 5 to 6 for SVD-based node2vec | SVD-based node2vec · SBM B1 n=600, rho=3n^-1/2 | accuracy: 0.61 -> 0.87 | Improved |
| use node2vec instead of ASE | node2vec (SVD-based) · PB (political blogs) | accuracy: 0.61 -> 0.96 | Improved |
| use node2vec instead of LSE | node2vec (SVD-based) · PB (political blogs) | accuracy: 0.51 -> 0.96 | Improved |
| use node2vec instead of ASE | node2vec (SVD-based) · ZK (Zachary karate) | accuracy: 1.00 -> 0.97 | Hurt |
| use node2vec instead of ASE | node2vec (SVD-based) · WIKI | ARI: 0.03 -> 0.09 | Improved |
Closest papers by meaning
- Convergence Guarantees for the DeepWalk Embedding on Block Models (ICML 2024 · similarity 0.92)
- Community Detection Guarantees using Embeddings Learned by Node2Vec (NeurIPS 2024 · similarity 0.90)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.88)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.88)
- Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis (AAAI 2024 · similarity 0.87)
- Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model (ICML 2025 · similarity 0.86)
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.
