Research map / Graph learning / Graph algorithms and clustering

Node Similarities under Random Projections: Limits and Pathological Cases

ICLR 2025 · Graph learning › Graph algorithms and clustering · approach: Graph embedding and spectral sparsification · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes how random projections preserve dot product and cosine similarity of graph connectivity embeddings (adjacency and transition matrix polynomials), showing degree-dependent failure of dot product and robust cosine similarity, with ranking-flip probabilities and a Wikipedia NDCG experiment.

Problem

Random projections are used to compress graph connectivity rows (adjacency or transition matrix polynomials) into low-dimensional node embeddings, but it is unclear how well dot product and cosine similarity between nodes are preserved, especially across node degrees and in ranking tasks.

Approach

Uses a rotation argument with Gram-Schmidt orthogonalization to derive asymptotic normality and finite-sample JL-type bounds for dot product and cosine similarity under Gaussian random projections, showing dot-product error depends on node degrees while cosine error is degree-independent, and derives ranking-flip probabilities via the t-distribution.

Key results

• On Wikipedia (2.98M nodes), RP dot product with P=T yields mean NDCG@10 of 0.602 (std 0.315) for high-degree nodes, versus 0.895 for RP cosine similarity (std 0.063).
• RP dot product with P=A yields mean NDCG@10 of 0.327 (std 0.188) for low-degree nodes, versus 0.999 (std 0.010) for RP cosine similarity.
• Theory shows a non-trivial probability (at least about 15.8%) that random projection flips the ranking of a high-degree self-relevance against a low-degree node with no common neighbors, while cosine error bounds do not depend on node degree.

Measured effects reported in the paper

Surprising findings

• Dot-product approximations are unreliable even when the transition matrix (row-normalized) is used, contrary to the intuition that normalization fixes degree effects.
• Projected dot products can flip sign with probability approaching 1/2 when the true cosine similarity is near zero.

Limitations

• Experiments use a single real graph (Wikipedia) and a single projection dimension q=256.
• Results rely on Gaussian random projection and asymptotic CLT approximations for finite q.
• Analysis is limited to nonnegative weighted adjacency matrices with a graph-wide degree parameter gamma.

Experimental setup

Datasets: Gleich/wikipedia-20060925

Benchmarks: Gleich/wikipedia-20060925

Metrics: NDCG@K empirical mean and std of NDCG

Baselines: RP Dot Product (P=T) RP Dot Product (P=A)

Builds on: Johnson-Lindenstrauss lemma random projection node embeddings (RP-based graph embedding)

Closest papers by meaning

• Graph Positional Encoding via Random Feature Propagation (ICML 2023 · similarity 0.88)
• Maximum Likelihood Embedding of Logistic Random Dot Product Graphs (AAAI 2020 · similarity 0.87)
• How Many Pairwise Preferences Do We Need to Rank a Graph Consistently? (AAAI 2019 · similarity 0.87)
• Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.86)
• Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem (NeurIPS 2024 · similarity 0.86)
• Learning Representations for Hierarchies with Minimal Support (NeurIPS 2024 · similarity 0.86)