# Node Similarities under Random Projections: Limits and Pathological Cases

arXiv: https://arxiv.org/abs/2404.10148 · HTML: https://mlsanity.com/paper/2404.10148/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 42 references that are in the map.
- First posted on arXiv 15 Apr 2024.

## Builds on (most cited first, 11 of 11)

- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Random-projection ensemble classification](https://mlsanity.com/paper/1504.04595/) (2015)
- [Fast and Accurate Network Embeddings via Very Sparse Random Projection](https://mlsanity.com/paper/1908.11512/) (2019)
- [Billion-scale Network Embedding with Iterative Random Projection](https://mlsanity.com/paper/1805.02396/) (2018)
- [Fully Understanding the Hashing Trick](https://mlsanity.com/paper/1805.08539/) (2018)
- [Understanding Sparse JL for Feature Hashing](https://mlsanity.com/paper/1903.03605/) (2019)
- [Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey](https://mlsanity.com/paper/2108.04172/) (2021)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [Approximate Euclidean lengths and distances beyond Johnson-Lindenstrauss](https://mlsanity.com/paper/2205.12307/) (2022)
- [An Analysis of Random Projections in Cancelable Biometrics](https://mlsanity.com/paper/1401.4489/) (2014)
- [Creating generalizable downstream graph models with random projections](https://mlsanity.com/paper/2302.08895/) (2023)

## Abstract (arXiv)

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.