Node Similarities under Random Projections: Limits and Pathological Cases

arXiv:2404.10148v1 Announce Type: cross
Abstract: 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 …

abstract applications arxiv cases computational cosine cs.ds cs.lg cs.si efficiency embeddings generate graph johnson math.pr node paper product random stat.ml tasks through type