Node Similarities under Random Projections: Limits and Pathological Cases

Tvrtko Tadić, Cassiano O Becker, Jennifer Neville

TL;DR

Random Projections (RP) are a staple for scaling up graph embeddings, but they aren't as "one-size-fits-all" as many assume. This paper reveals that while the popular dot product similarity can fail spectacularly on graphs with skewed degree distributions, cosine similarity remains remarkably robust, providing stable and precise approximations even in "pathological" cases.

The Problem: Scaling Graph Similarities

In the world of massive graphs—think social networks or web crawls with millions of nodes—calculating exact similarities between every pair of nodes is computationally impossible. Researchers typically turn to Random Projections (RP), a technique that squashes high-dimensional data into a smaller space while attempting to preserve the relationships between points.

Most practitioners rely on the famous Johnson-Lindenstrauss (JL) Lemma, which guarantees that Euclidean distances are mostly preserved under such projections. However, many downstream graph tasks (like recommendation or ranking) rely on dot products or cosine similarity rather than raw Euclidean distance.

The authors identify a critical gap in this standard practice: real-world graphs have highly skewed "power-law" degree distributions, meaning a few nodes have massive connections while most have very few. The central question of this research is: Does this extreme skewness break the reliability of random projections for similarity-based tasks?

Methodology

The authors move beyond the standard JL Lemma to provide a rigorous mathematical treatment of how dot products and cosine similarities behave under projection.

  • Asymptotic and Finite-Sample Analysis: They derive new formulas to predict the error and variance of these similarities as the projection dimension ($q$) changes.
  • The Rotation Argument: To get more precise bounds than previous literature, they employ a "rotation argument" combined with a Gram-Schmidt orthogonalization procedure. This allows them to represent the projected dot product as a sum of independent variables, making the math much cleaner and the resulting bounds tighter.
  • Ranking Stability: They specifically calculate the probability of a "ranking flip"—a scenario where the statistical noise from the random projection causes a low-relevance node to be ranked higher than a high-relevance one.

Datasets and Experimental Setup

The paper validates its theoretical findings using a large-scale real-world graph:

  • Wikipedia (Gleich/wikipedia-20060925): A dataset consisting of nearly 3 million web pages and over 37 million links.
  • To specifically test how degree distribution impacts embedding quality, the authors used a stratified sampling strategy, splitting nodes into "low," "medium," and "high" degree segments.

Key Insights: The "Dot Product Trap"

  • Degree-Dependent Error: The error in a projected dot product is heavily influenced by the degrees of the nodes involved. For high-degree nodes, the statistical noise introduced by the projection can be larger than the actual similarity value itself. This leads to "pathological cases" where the embeddings become essentially useless for ranking.
  • Normalization Isn't a Silver Bullet: Even when using a normalized transition matrix (often used to curb the influence of high-degree nodes), the dot product still produces unreliable rankings for certain node pairs.
  • Cosine Similarity is the Hero: Unlike the dot product, the error bounds for cosine similarity are uniform. They depend only on the similarity value itself, not the magnitudes (degrees) of the vectors. This makes cosine similarity "immune" to the degree-skewness of the graph.
  • Predictable Pathologies: The authors show that if you use the adjacency matrix, low-degree nodes suffer most. If you use the transition matrix, high-degree nodes suffer most. In both cases, the dot product is the culprit.

Key Results

  • Ranking Quality (NDCG): In experiments on the Wikipedia dataset, the RP Cosine Similarity maintained a near-perfect ranking quality (NDCG $\approx$ 0.99) across all node degrees.
  • Dot Product Failure: In stark contrast, the RP Dot Product (using the transition matrix) saw its ranking quality plummet to 0.58 for high-degree nodes. When using the adjacency matrix, the ranking quality for low-degree nodes was even worse, dropping to a dismal 0.057.
  • Stability: The probability of a ranking flip for cosine similarity is significantly lower and more predictable, making it a much safer choice for production systems where ranking stability is a strict requirement.

Limitations and Future Work

  • Gaussian Focus: The current analysis focuses on projections using Gaussian random variables. While standard, many modern systems use "sparse" random projections for even greater computational speed; the authors suggest extending their analysis to these sparse settings.
  • Linear vs. Non-linear: This work focuses on linear projections of matrix polynomials. How these findings translate to non-linear embedding methods, like Graph Neural Networks (GNNs) that use random initializations, remains an open question.
  • Norm Information: The authors acknowledge that if the "norm" (magnitude) of the vector is actually important for the specific downstream task, cosine similarity might discard useful information. The trade-off between stability and information loss is a key area for future exploration.

Summary updated

Abstract

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.
BibTeX
@inproceedings{tadic2025node,
  author = {Tvrtko Tadić and Cassiano O Becker and Jennifer Neville},
  title = {{Node Similarities under Random Projections: Limits and Pathological Cases}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=Frok9AItud},
}
Figure