  We present FastRP, a scalable and performant algorithm for learning
distributed node representations in a graph. FastRP is over 4,000 times faster
than state-of-the-art methods such as DeepWalk and node2vec, while achieving
comparable or even better performance as evaluated on several real-world
networks on various downstream tasks. We observe that most network embedding
methods consist of two components: construct a node similarity matrix and then
apply dimension reduction techniques to this matrix. We show that the success
of these methods should be attributed to the proper construction of this
similarity matrix, rather than the dimension reduction method employed.
  FastRP is proposed as a scalable algorithm for network embeddings. Two key
features of FastRP are: 1) it explicitly constructs a node similarity matrix
that captures transitive relationships in a graph and normalizes matrix entries
based on node degrees; 2) it utilizes very sparse random projection, which is a
scalable optimization-free method for dimension reduction. An extra benefit
from combining these two design choices is that it allows the iterative
computation of node embeddings so that the similarity matrix need not be
explicitly constructed, which further speeds up FastRP. FastRP is also
advantageous for its ease of implementation, parallelization and hyperparameter
tuning. The source code is available at https://github.com/GTmac/FastRP.
