Node Similarities under Random Projections: Limits and Pathological
  Cases
Tvrtko Tadić Cassiano Becker Jennifer Neville
Random Projections have been widely used to generate embeddings for various
graph 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. Our analysis provides new theoretical
results, identifies pathological cases, and tests them with numerical
experiments. We find that, for nodes of lower or higher degrees, the method
produces especially unreliable embeddings for the dot product, regardless of
whether the adjacency or the (normalized version) transition is used. With
respect to the statistical noise introduced by Random Projections, we show that
cosine similarity produces remarkably more precise approximations.