# Community Detection Guarantees Using Embeddings Learned by Node2Vec

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

## Key facts

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

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [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)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [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)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [The Global Optimization Geometry of Low-Rank Matrix Optimization](https://mlsanity.com/paper/1703.01256/) (2017)
- [Strong Consistency, Graph Laplacians, and the Stochastic Block Model](https://mlsanity.com/paper/2004.09780/) (2020)
- [Network Representation Using Graph Root Distributions](https://mlsanity.com/paper/1802.09684/) (2018)
- [Fundamental Limits of Spectral Clustering in Stochastic Block Models](https://mlsanity.com/paper/2301.09289/) (2023)
- [Determining the Number of Communities in Degree-corrected Stochastic Block Models](https://mlsanity.com/paper/1809.01028/) (2018)
- [Asymptotics of Network Embeddings Learned via Subsampling](https://mlsanity.com/paper/2107.02363/) (2021)
- [Estimating the number of communities in networks by spectral methods](https://mlsanity.com/paper/1507.00827/) (2015)
- [Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings](https://mlsanity.com/paper/1910.00423/) (2019)
- [Extended Stochastic Block Models with Application to Criminal Networks](https://mlsanity.com/paper/2007.08569/) (2020)
- [Empirical Risk Minimization and Stochastic Gradient Descent for Relational Data](https://mlsanity.com/paper/1806.10701/) (2018)
- [Next Waves in Veridical Network Embedding](https://mlsanity.com/paper/2007.05385/) (2020)

## Abstract (arXiv)

Embedding the nodes of a large network into an Euclidean space is a common objective in modern machine learning, with a variety of tools available. These embeddings can then be used as features for tasks such as community detection/node clustering or link prediction, where they achieve state of the art performance. With the exception of spectral clustering methods, there is little theoretical understanding for commonly used approaches to learning embeddings. In this work we examine the theoretical properties of the embeddings learned by node2vec. Our main result shows that the use of k-means clustering on the embedding vectors produced by node2vec gives weakly consistent community recovery for the nodes in (degree corrected) stochastic block models. We also discuss the use of these embeddings for node and link prediction tasks. We demonstrate this result empirically, and examine how this relates to other embedding tools for network data.