  Random Projections have been widely used to generate embeddings for various
graph learning tasks due to their computational efficiency. The majority of
applications have been justified through the Johnson-Lindenstrauss Lemma. In
this paper, we take a step further and investigate how well dot product and
cosine similarity are preserved by random projections when these are applied
over the rows of the graph matrix. Our analysis provides new asymptotic and
finite-sample results, identifies pathological cases, and tests them with
numerical experiments. We specialize our fundamental results to a ranking
application by computing the probability of random projections flipping the
node ordering induced by their embeddings. We find that, depending on the
degree distribution, the method produces especially unreliable embeddings for
the dot product, regardless of whether the adjacency or the normalized
transition matrix is used. With respect to the statistical noise introduced by
random projections, we show that cosine similarity produces remarkably more
precise approximations.
