NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization
  We study the problem of large-scale network embedding, which aims to learn
latent representations for network mining applications. Previous research shows
that 1) popular network embedding benchmarks, such as DeepWalk, are in essence
implicitly factorizing a matrix with a closed form, and 2)the explicit
factorization of such matrix generates more powerful embeddings than existing
methods. However, directly constructing and factorizing this matrix---which is
dense---is prohibitively expensive in terms of both time and space, making it
not scalable for large networks.
  In this work, we present the algorithm of large-scale network embedding as
sparse matrix factorization (NetSMF). NetSMF leverages theories from spectral
sparsification to efficiently sparsify the aforementioned dense matrix,
enabling significantly improved efficiency in embedding learning. The
sparsified matrix is spectrally close to the original dense one with a
theoretically bounded approximation error, which helps maintain the
representation power of the learned embeddings. We conduct experiments on
networks of various scales and types. Results show that among both popular
benchmarks and factorization based methods, NetSMF is the only method that
achieves both high efficiency and effectiveness. We show that NetSMF requires
only 24 hours to generate effective embeddings for a large-scale academic
collaboration network with tens of millions of nodes, while it would cost
DeepWalk months and is computationally infeasible for the dense matrix
factorization solution. The source code of NetSMF is publicly available
(https://github.com/xptree/NetSMF).
