  Network embedding approaches have recently attracted considerable interest as
they learn low-dimensional vector representations of nodes. Embeddings based on
the matrix factorization are effective but they are usually computationally
expensive due to the eigen-decomposition step. In this paper, we propose a
Random RangE FInder based Network Embedding (REFINE) algorithm, which can
perform embedding on one million of nodes (YouTube) within 30 seconds in a
single thread. REFINE is 10x faster than ProNE, which is 10-400x faster than
other methods such as LINE, DeepWalk, Node2Vec, GraRep, and Hope. Firstly, we
formulate our network embedding approach as a skip-gram model, but with an
orthogonal constraint, and we reformulate it into the matrix factorization
problem. Instead of using randomized tSVD (truncated SVD) as other methods, we
employ the Randomized Blocked QR decomposition to obtain the node
representation fast. Moreover, we design a simple but efficient spectral filter
for network enhancement to obtain higher-order information for node
representation. Experimental results prove that REFINE is very efficient on
datasets of different sizes (from thousand to million of nodes/edges) for node
classification, while enjoying a good performance.
