Community Detection Guarantees using Embeddings Learned by Node2Vec

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

Authors

• Andrew Davison
• S. Carlyle Morgan
• Owen G. Ward

Keywords

No keywords are indexed for this paper.