Exact Recovery of Community Structures Using DeepWalk and Node2vec. (arXiv:2101.07354v2 [stat.ML] UPDATED)

Random-walk based network embedding algorithms like DeepWalk and node2vec are
widely used to obtain Euclidean representation of the nodes in a network prior
to performing downstream inference tasks. However, despite their impressive
empirical performance, there is a lack of theoretical results explaining their
large-sample behavior. In this paper, we study node2vec and DeepWalk through
the perspective of matrix factorization. In particular, we analyze these
algorithms in the setting of community detection for stochastic blockmodel
graphs (and their degree-corrected variants). By …

arxiv community deepwalk node2vec recovery