Consistency of random-walk based network embedding algorithms
  Random-walk based network embedding algorithms like node2vec and DeepWalk are
widely used to obtain Euclidean representation of the nodes in a network prior
to performing down-stream network inference tasks. Nevertheless, despite their
impressive empirical performance, there is a lack of theoretical results
explaining their behavior. In this paper we studied the node2vec and DeepWalk
algorithms through the perspective of matrix factorization. We analyze these
algorithms in the setting of community detection for stochastic blockmodel
graphs; in particular we established large-sample error bounds and prove
consistent community recovery of node2vec/DeepWalk embedding followed by
k-means clustering. Our theoretical results indicate a subtle interplay between
the sparsity of the observed networks, the window sizes of the random walks,
and the convergence rates of the node2vec/DeepWalk embedding toward the
embedding of the true but unknown edge probabilities matrix. More specifically,
as the network becomes sparser, our results suggest using larger window sizes,
or equivalently, taking longer random walks, in order to attain better
convergence rate for the resulting embeddings. The paper includes numerical
experiments corroborating these observations.
