  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 exploiting the row-wise
uniform perturbation bound for leading singular vectors, we derive
high-probability error bounds between the matrix factorization-based
node2vec/DeepWalk embeddings and their true counterparts, uniformly over all
node embeddings. Based on strong concentration results, we further show the
perfect membership recovery by node2vec/DeepWalk, followed by $K$-means/medians
algorithms. Specifically, as the network becomes sparser, our results guarantee
that with large enough window size and vertices number, applying
$K$-means/medians on the matrix factorization-based node2vec embeddings can,
with high probability, correctly recover the memberships of all vertices in a
network generated from the stochastic blockmodel (or its degree-corrected
variants). The theoretical justifications are mirrored in the numerical
experiments and real data applications, for both the original node2vec and its
matrix factorization variant.
