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