Research map / Graph learning / Graph algorithms and clustering

Community Detection Guarantees using Embeddings Learned by Node2Vec

NeurIPS 2024 · Graph learning › Graph algorithms and clustering · approach: Neural and local graph clustering · 2 citations (OpenAlex)

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.

Shows that k-means on node2vec embeddings gives weakly consistent community recovery for (degree-corrected) stochastic block models, with empirical checks on simulated and real networks.

Problem

Little theoretical understanding exists of what community information node2vec embeddings carry, and whether clustering them recovers communities in (degree-corrected) stochastic block models.

Approach

Characterises the asymptotic limit of node2vec embeddings (minimisers of the negative-sampling loss) under SBM/DCSBM, showing they concentrate around community-dependent vectors up to rotation, so k-means on them gives weakly consistent recovery for DeepWalk and node2vec under several sparsity regimes.

Key results

• On the Political Blogs network node2vec with k-means reaches average NMI of 0.75 while spectral clustering struggles regardless of Laplacian.
• Node2vec embeddings clustered with k-means recover communities better than spectral clustering on both Email and Political Blogs networks in NMI.
• Under constrained embeddings (U=V), the theory says weakly consistent recovery is possible iff p̃ > q̃.

Measured effects reported in the paper

Surprising findings

• Spectral clustering fails on the Political Blogs network regardless of the graph Laplacian used.
• The paper finds the sampling parameters p and q have little impact on performance as networks grow, and node2vec rates appear suboptimal compared with prior spectral results.

Limitations

• Only weak consistency is proven, not strong consistency; rates are not optimal.
• Theory for node2vec with general p and q is restricted to the sparsity regime rho_n = n^{-alpha}; the DCSBM result is only for DeepWalk with alpha=1.
• Constrained embeddings (U=V) fail to recover communities when p̃ ≤ q̃.

Experimental setup

Datasets: Stanford email network Political blogs network

Benchmarks: Political blogs network Email network

Metrics: proportion of nodes correctly recovered normalized mutual information adjusted rand index

Baselines: spectral clustering

Builds on: node2vec DeepWalk word2vec stochastic block model degree-corrected stochastic block model

Closest papers by meaning

• Incorporating Network Embedding into Markov Random Field for Better Community Detection (AAAI 2019 · similarity 0.92)
• Community Preserving Network Embedding (AAAI 2017 · similarity 0.90)
• Asymptotics of $\ell_2$ Regularized Network Embeddings (NeurIPS 2022 · similarity 0.89)
• How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings (ICLR 2025 · similarity 0.87)
• Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis (AAAI 2024 · similarity 0.86)
• The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks (NeurIPS 2024 · similarity 0.86)