Exact Recovery of Community Structures Using DeepWalk and Node2vec

Understand

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).