Node Similarities under Random Projections: Limits and Pathological Cases
Authors: Tvrtko Tadić
Cassiano O Becker
Jennifer Neville
Venue: ICLR 2025 Poster (2025)
Keywords: Johnson–Lindenstrauss Lemma
Random Projections
Graph Embeddings
Ranking
Cosine Similarity
Primary area: learning on graphs and other geometries & topologies
TL;DR: Asymptotic and finite-sample analysis of random projections for ranking in graphs with a description of pathologies based on node degree and their solution using cosine similarity

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.

Published as a conference paper at ICLR 2025
NODE SIMILARITIES UNDER RANDOM PROJECTIONS: LIMITS AND PATHOLOGICAL CASES
Tvrtko Tadié
Cassiano O. Becker
Microsoft Search, Assistant and Intelligence tvrtkota@m croso ft. com
Microsoft Search, Assistant and Intelligence ca casbecke 0m crosoft. com
Jennifer Neville
Microsoft Research
Someeiile@microoofftee com
ABSTRACT
Random Projections have been widely used to generate embeddings for various graph learning tasks due to their computational efficiency. The majority of applica- tions have been justified through the Johnson--indee Lindenstrauss Lemma. In this paper, 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 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 intro- duced by random projections, we show that cosine similarity produces remarkably more precise approximations.
asymptotic and nampe results, identifies
INTRODUCTION
Random projections (RP) provide simple and elegant approach to dimensionality reduction /Vempala 2004). Leveraging concentration of measure phenomena in high-dimensional statistics (Vershynin (JL) lemma (Johnson al., 1986 Dasgupta & Guptal 2003) to provide data-independent guarantees for approximation quality, As originally developed, the JL lemma showed that Euclidean distances between any two points in dataset preserved with high probability if their vectors are projected using appropriately constructed random matrices. Remarkably, the JL lemma shows that the required projection dimension of the random matrix needs grow only with the logarithm of the ambient dimension of the dataset. As such, the JL lemma has found wide application diverse fields such as information retrieval [Kleinberg 1997, Indyk & Motwani 1998). machine learning (Nachum et al. [2022] Durrant
2018). RP's rely on the well-known
& Kabán Cannings & Samworth, 2017: Boutsidis et al. 2010 Cardoso & Wichert 2012
Makarychev et 2l.19,019), privacy (Liu 2005 Wang & Plataniotis 2010), and numerical linear
algebra (Halko et al. [011]] Martinsson & Tropp 2020).
In the context of graphs, the JL lemma can be applied generate low-dimensional encodings of node's 's connectivity to other nodes in the graph. In that case, nodes are usually represented as vectors extracted as the rows of connectivity matrix (Hamilton) 2020), which is obtained from the adjacency matrix (or some analytic function of it). For example, it is known that the entries of the power of an adjacency matrix encode the number of walks of length of that prescribed power between any two nodes (Newman 2018). Likewise, the transition matrix can be used to compute the corresponding random-wall walk probability between any pair of nodes (Bianchini et al.) 2005). This notion is key to algorithms such as PageRank (Page et al.) 1999), which computes the steady- random walk probability as the limit of a weighted sum over all possible lengths. In these cases, although the adjacency matrix is typically sparse -in that it registers only first-order immediate neighbors- higher-

---

Published as a conference paper at ICLR 2025
Table 1: Notation and symbols used throughout the paper
number of nodes graph with V and E the sets of nodes and edges adjacency matrix, transition matrix matrix polynomial p(A) or p(T) degree of node
C:
low and high degree parameters set of low degree nodes wrt. c
Le
H2
set of high degree nodes wrt. e and y random projection dimension
A, T
P
R
random projection matrix node embedding matrix I-distribution with parameter q
du
X
Tae
connectivity between nodes a and
T
order connectivity matrices will often become dense and pose representation challenges in term of the storage space required. We recall that the inherent dimensionality of such representations based on connectivity matrices would otherwise grow quadratically with the number of nodes in the graph, which in practical data applications is often of the order of millions or higher [Tang al. 2009). To that end, random projections consists of a promising dimensionality reduction approach. In the context of representation learning, the use of random projections to generate node embeddings for graphs was introduced in (Zhang et al., (2018) and further developed in (Chen et al.) 2019), becoming a popular and fast way to produce embeddings.
The problem addressed in this paper is the one of graph representation for tasks over large graphs, and can be summarized by the following steps:
1. We use random projections to generate low-dimensional node embeddings capturing (high order) connectivity induced by (otherwise computationally--xxpsssss) adjacency matrix polynomials.
2. With the node embeddings, we compute arbitrary pairwise node similarities as a feature in models for graph inference tasks (e.g., ranking for recommendation).
The contributions of this paper as threefold:
We show that the degree of the node has significant influence on the quality of approximation similarity, according to the type of matrix (e.g., adjacency or transition) and function adopted (e.g.. dot product or cosine). By expressing the JI. Lemma terms of the graph's 's degree distribution, we show that it becomes data dependent for dot product, yiclding especially weak guarantees for low and high-degree nodes. Contrary to intuition, this happens not only for the adjacency matrix, but also when the transition matrix is considered (i.e., when the matrix is now-oormalized).
2. We provide extensive analyses of node embedding approximation quality under cosine similarity. By crafting rotation argument followed by Schaidt orthogonalization procedure, develop novel asymptotic and finite-sample results that show that cosine similarity produces more precise approximations with respect to the graph's degree distribution.
3. We extend our theoretical results to the case of ranking based on node embeddings. Specifically, we derive the probability of random projections flipping the node ordering induced by their embed- dings, and show that cosine similarity produces remarkably more stable rankings. These findings are shown occur and impact practical applications, as we illustrate with an example using a Wikipedia dataset.
Related work on random projections has focused predominantly on proposing alternative random projection matrix constructions and seeking sparser configurations (Freksen et al., (2018) Jagadeesan 2019 Achlioptas 2003). Other works were dedicated to obtaining tighter bounds for the preservation of Euclidean distance (Sobezyk& & Luisier) 2022 Li et al. (0066. In the case of the dot product, work in (Kaban 2015 Vempalal 2004) obtained general guarantees depending on the angle between the vectors. In the case of cosine similarity, other guarantees have been provided in (Arpit et al. 2014). In this paper, we refine and improve some of those results. Other studies have focused on the preservation of margin in the formulation of support vector machines (Shi et al. 2012). Additional contributions for the analysis of clustering have been given by (Becchetti et al. 2019 Cohen-Addaa
et al. 2022 Bucarelli et al. 2024
2

---

Published as a conference paper at ICLR 2025
2 RANDOM PROJECTIONS IN GRAPHS
In the case of large graphs G = (V. E), random projections have been applied to polynomials of the nonnegative integer adjacency matrix A and transition matrix T. If R = [Ryl] IR9*" q < n. random matrix generated in a specific way, then X P(A)RT
X p(T) preserves many of the properties p(A) and p(") for a matrix polynomial p(Y) _n arY In our paper, I.....9.J
n)) :..... as i.idd normal random variables Pk: in R1xn is then mapped to row-vectors pr RT ,....,k. R in IR 1x9_ An additional benefit is that p(A)R and p(T) can be calculated faster than p(A) and p(T), since given factor A' R is calculated with A sparse and < n. In contrast, A' computed separately may incur an n X full-dimensional and dense A' for higher L. This property becomes even more useful in the case of heterogeneous graphs, where we have polynomials of several variables associated with the so-called metapaths (Sun et al. 2011).
we construct R by sampling [Rag
with mean zero and variance 1/ //.. A sequence of row vectors p1.-..: .....
(A(..A((RR)))) )),
Let P p(A) or P = PT));
; and denote Pu. as the row in the matrix P representing node w V. For u, v E V, the interpretation is that rcl.e == P... P. is the relevance between u and e and
rel R uv = X X. = P..P.T. nm
When (T) holds, vertex o in the graph can be effectively represented by the embedding X In the finite-sample regime, this approximation is generally justified by the JL Lemma. The following version is from the book (Boucheron et al. 2013):
Theorem 2.1. Lete, (0, 1), and Pı, PI.....P8 Pk be non-zero vectors in RIxn, 1fq 2 _/4 log
Rd' then, -
with probability at least 1-8, the inequality (1-=)llp- Py 11? s llp,R' -P, 1|2 s (1+E) Ip: p/ll? holds for all j.
Due to the randomness of R, we will show that, for large sparse graph, the assumption will fail in two important cases:
(i) = A: for a low-degree node v. Xux will overvalue P..... for many high-degree nodes u;
(ii) P = T:: for high-degree node u, X.. Xux will overvalue P.. PTT for many low-degree nodes
In contrast, we will show that ||x.-IIIX..II| R
|IP--II)PP..I holds more consistently. This is why we X.._ as the embedding for a vertex v. We call this method RP Cosine Similarity. II
X.-X.
P..P..
propose to use
To develop our specific results, we begin by denoting, for all u, V, du = Σvev Anw as the degree of the vertex u. Likewise, we define nue := A as the 2-hop connectivity between u and v. corresponding to the number of paths of length two between those vertices. The following lemma provides basic information about nuv-
Lemma 2.2. For all u. U V we have
du S Dau S de:
(2)
dy
Nuv
T T.T
(3)
Proof. Since all entries of the matrix A are nonnegative integers: Tuu = Emev A >
Ewev Auw = dg. On the other hand, de = =EEwev Auw)2 2 EwEV A2 Au Mac
Note, Tu. J. A for all V. Hence, T. AuoA.. Auz. d.d, d.d."
This shows and
Further, note that d, has a linear dependence the entries of A, while nw has quadratic one. Thus, in order to relate dy to Nuw. we define the following grdp property:
nle
=
max M V
d
Although we assume throughout the paper that the elements of the adjacency matrix are nonnegative integers, all the proofs would work if entries were from the set (0) U (1,00), The results can also be further modified to allow the elements of A to be from [0, oo) by introducing additional constants.
3

---

Published as a conference paper at ICLR 2025
This property enables results to generalize to weighted adjacency matrices A (ZØ )mx, In general, from 2 we have 15y S ma Auv. In particular, if {0, [0,1)=x8, then 1.
Next, we will define what does mean for the node to be of high low degree in the context of this paper. Let
= E V de c).
This will be called the set of nodes of low degree. In particular, for a graph following a power law distribution, Le will contain the majority of the nodes. Conversely, let
H = {u E V du 2 72g)
(6)
We will call this the set nodes of high degree. We are interested analyzing graphs where n = [V] is
large using results of the Laanson-Lindenstrauee type. For that, we consider g = Olog n)) Using
the power law distribution described in equation (10.8) from (Newman) 2018), which is often
observed in natural and social networks, we have 2=1l Cz where O. Consequently, 1M21
a C'loogn] For large the set H3 should contain number of nodes on the order of O(n[logn]=9)
2.1
RP DOT PRODUCT WHEN P P=1
To avoid numerical instability issues associated with higher degree nodes and higher powers A, practitioners often consider the transition matrix T, since consists of bounded, row-stochastic normalization of A. We will show that even in this case, random projections may yield especially poor approximations for nodes
H? and E Le-
Theorem 2.3. Let X = TR The following statements hold:
(a) Asymptotic result. For u, v E V and large q
))
Xu ve
2 N
Duv du
Dov dy
+
Duu
d
(b) samile result. For e E (0, 1) and (0, if q 2 4 1+e log [n(n-1)]
then
Thwy dy
nuuu
<
(8)
dudo
for all u, U. E V holds with probubility at least
Remark. We denote by Y, N(, a the fact that Y-TH / 4 No( + co. The "A" is interpreted meaning an approximate distribution for large q.
Proof. Using the rotation argument from A.Il we represent X sum of i.id random variables and a convenient term. This stated in part (a) Theorem A.6 in the Appendix.
Using the Central Limit Theorem and Law of Large Numbers, get the following asymptotic result:
T.R. RTT 2. N.T,TT (T.TTy%/g /q + [ [
1l2//)- For details, part (a) of Proposition noe and [T
A.1 in the Appendix. Applying (3) we have T.T,,
d. Te T.T.
Ruv
d2
T.T.
Thu and part (a) follows. d5
Using the representation X...X mentioned the beginning of the proof, tration results that lead to a JL Lemma-type result in part (b) of Proposition I in the Appendix. From there, set k [V] and get that [T,, R RTT T.T. e|lT, [ for all u, v E V under the same conditions and assumptions of part (b) of this Theorem. The full claim follows from the calculation we did to prove part (a).
produce concen-
The rotation argument mentioned above (and fully developed in A.II allows to directly analyze
P..R R.P... This improves on the typical approach /Vempala 2004
Kaban 2015 Amirov et al. P.. R P..R
2023) of representing the dot product by the expansion [[] P.
since these factors are usually not independent. Doing so enables us to produce more precise bounds, discussed in 11.55
4

---

Published as a conference paper at ICLR 2025
The asymptotic result 7 is often missed when using random projections in graphs. As mentioned, versions of (8) are often used. However, they miss telling us when and how often the method will produce poor estimates. This does not seem have been addressed in the literature. To do so, will fix u E Hg and look at the values {Xua X E Le] that may misapproximate (d.a : E Le)-
Corollary 2.4. If v Le and E Hg. then the standard deviation in 7 is greater than its expectation, i.e.:
uuv dy
nuu dud du de
+
Proof. We have Punnout t plying the last inequality with d;, d, and taking the square root, ( follows.
d_du+n
Ne 2
goodd
2 >ccd, 2 (rdx) 2
n Multi-
Under the conditions of the Corollary above, when can generate the one-sigma interval in which (Xu.. XT
Bue dadu
Nunnoe di
Bar dudd
Buo dudu
Vo
Ban did
Bur dud.
Le) will take values with probability of less than 69%. This means that getting value outside that interval is not unlikely. In that case, we know from (9) that such values will either double d.d.
Auu or be
less than 0, which is clearly poor approximation.
We now interpret the finite-sample result, and set [(1 + e)/e log n(n - 1)/5]1 such that part (b) of Theorem 2.3 holds. The expression /uv/ (dd//d in the numerator of (8) depends on da with order (d.)) ) and denominator has lower-order dependence (d.))=, as described in Lemma B.4 in the Appendix. Thus, higher values of d,, lead to an unfavorable regime which the guarantees from Theorem 2.3 become increasingly weaker. As a simple numerical illustration, we assume E
10-2 d, 10", d,- = 10 and fow =. Then, ( yields X E 10 100 100, + 100), which is clearly severely biased estimate.
10.1) so that Tha = dy and fvve du and
Similar results hold in the case P = A. For this case, we provide analogous asymptotic normality and finite sample results in (B. of the Appendix. There, we also express similarities in the terms of values of (Nwo) and (d.). ). In the absence of normalization, the disruption of the assumption XT, 2= PurP.. is more obvious.
2.2 RP COSINE SIMILARITY
In this section, we present asymptotic normality and finite-sample analyses to show how RP Cosine Similarity produces significantly better approximations than those of RP Dot Product for vertices e HJ and v E Le (both when P = T and P A). We begin by showing that it will not matter for RP Cosine Similarity if we take P = or = T.
Lemma 2.5. For all u, U E V we have
cos(TTu. RT, Tu, RT.RR) cos(A R RJ. and cos To.) cos( (Aue Ava)
Dhw
v Doau
(A. R(d_'A] [ R [T.. A.. RTIl A AT
Tu. RRRTT.
Aus R RAT A Am Rl]
Proof. First equality follows from Using parts (a) and (b) of Lemma 2.2 we caleulate that cos Cos(An,, Avt) cos(Tue: Tox)
and
Tlage
We will state our main result for this method now.
Theorem 2.6 For P e (A,T) and X PRT, the following claims hold: (a) Asymptotic result. For E V and large
cos(X,e,, N
Byy
(1-
n
(10)
Teun Dowe
5

---

Published as a conference paper at ICLR 2025
2m(n
1]
1+
2
(b) Finite-sampi result. Let & E (0,0.05) and ó E (0,1). 1fq
then
In
2(1(0v1)
cos(X (oe(Xux,, Xux)
Tuu Pove
S
Ruw Rove
holds for all v E V with probubility at least 1 - 6.
Proof. Using the rotation argument from A we can get very useful representation of cos( uus: X stated in part (b) of Theorem A.6 in the Appendix.
From the Central Limit Theorem and the Law of Large Numbers, we show that cos( X X & N (cos(Pus us: Pv+); 1 (1 cos )v+))² For details, see part (a) of Proposition A.3 in the Appendix. Claim (a) follows from Lemma 2.5
Using the representation mentioned at the beginning, we can get concentration results and results of the JL Lemma type. This is stated in part (b) of Proposition A.3 in the Appendix, whence have | cos(( u.,, x cos(Puu. Pu.)l c(1 cos? (Pu., P..)) under the same assumptions and conditions. Claim (b) follows from Lemma 2.5
Let compare the asymptotic result for cosine similarity with the previous cases. From 10) we can produce the approximate three-sigma confidence interval cos(Pun; Pv.) v (1 cos? (Pu.: Pu-)), (u.. 3 cos" (Pu.: P..))
where cos(X,,, (X ut: x..) is expected to take values with 99.7% probability. Differently from the previous cases, we see that the interval endpoints depend only on the cosine similarity being estimated. Thus, for a reasonably large q. the value of cos(Pu., P..) will be well-approximated. Further, the closer cos( (a.( P..) is to 1, the smaller the standard deviation, and the narrower the confidence interval. The confidence interval the widest when cos (P... Pow) = In that case, it can happen that takes negative values under random projections, but this is likely not to be lower than /9
With Theorem 2.6. can state the following additional properties. Proposition 2.7. (a) cos(Xue: Xux) [-1, all u, V. (b) Almost surely cos(Xu.. Nu.: X +1 and only if cos coosp Pu.) +1.
2n 11 it
3l
(c) For (0,0.05) and (0,1), ifq
then
1+ 2(14022)
cos (os( X [cos(Pa Par, Pux) E, cos( Pur, P.s) +e]
for all u, V with probability 1-66 5.
Proof. Part (a) follows by definition of cosine similarity, Part (b) follows from the Cauchy-Schward
inequality. The full discussion can be found in the Corollary A.20 in the Appendix. Part (c) follows
n = 1 cos2 (Pu. P..) 1.
from Theorem 2.6 part (b) since 0 <
Part (b) of Proposition 2.7 tells us that random projection will preserve values of exactly 1. Part (c) of Proposition] 2.7 provides the desired property of uniformity with respect to node degrees for the absolute error on the difference between the estimate and the true value.
3 APPLICATION TO RANKING
Here, we specialize the results presented Section 2 to a ranking application. Recall that, for polynomials P p(A) P pTT), the interpretation is that for u, V relux P... PT For

---

Published as a conference paper at ICLR 2025
computational reasons, apply the random projection X PR and work with rel Xu.Xu under the assumption that rel reluv-
We will next examine what happens if fix V and the approximate relevance (rel h V) for ranking, We will use the well-known NDCG metric: NDCG
DCG, ax DCG,, aK
where
rel ( log(rank +1
rel
DCG NOGR@K @K
E
DCG, @K
E
log(rank (h)
+1
hrrank
(11)
Here, rankw(() (resp. rank denotes the rank order of h E V with respect to w induced by relwh (resp. rel Note that DCG takes relws and not rel wh in its numerator, since we want to compute the effect of selecting h according to the approximated RP order rank 22 (h) in terms of the original relevance relwh- The following theorem will help us quantify how often the approximation rel can flip the order of relevance between nodes u and v with respect to w.
Theorem 3.1. Let u, E V be such that rel > relwa- Then,
cos way P. Puoiva
F(rel < rel = P
(12)
V1 cos2 SuniPuc Pus P..)
where Tg is the I-distribution with parameter 4-
Proof. have rel < relwe, we need Pwr. Pa.) 0. The right-hand side the probability that this dot product will change sign under the random projection, i.e., TP( R R(P... - P..)) )
0). This is a simple consequence that follows from the representation in part (a) of Theorem A.6 which is obtained using the rotation argument and the definition of the t-distribution. For details, see Proposition A.2 in the Appendix.
3.1 INSTABILITY RANKING FOR DOTPRODUCT WHEN
For given V, provide information the set of relevance values {reluv v E VJ.
Proposition 3.2. For all u, v E V, we have reluv = Bus S 2. Further, dedu
nuw 0;
relu
if uf E Lei Ruv 2 1; if u E Hy Dov 2 1:
(13)
72
where dmax = maXNev dn-
Proof. We have reluv To. T.T by definition reluv- 0. If nuv 1 and u, Lc. then du, d, and hence relge
B Bay 7. To prove (3). we look at each case. If Nwv
d,
d,
Aug.
d_
d.d. Finally, if u E H7 and Buv 2 1. we have d, 2 22eg and du, dy S dmaxi therefore Pay Z dudo dud.
reluv
We will have y 2 and > c, hence the intervals in 13 are all disjoint in this case. This shows that relevance has different values in three non-trivial cases.
Note that the upper bound 2. in Proposition 3.2 can be particularly small for a high degree du- However, the estimate might be larger than that.
(uun Corollary 3.3. For E H3 and E Le. we have relR . (o1(
2n dig
and rel will be
asymptotically normal with nonnegative expectation and standard deviation greater than +.
Proof. Asymptotic result rel 2 2N ("z², um
2n follows from Theorem 2.3 part(a), when we take 2.
It can be shown using definitions of and under the assumptions that E H3 and Le, that the variance in (7). and hence the variance of rel,.. is greater than (y/d.)² Details can be found in Lemma (b) in the Appendix.
7

---

Published as a conference paper at ICLR 2025
The last result tells us that rel will have values in Bun (1 - 3 3/ (1+ 31+3/2) with d=
probability more than 99%. This means, for example, if q Z 100, rel E [1.5 00) c
Rus de
(1 [1+3 3/33/ x0) can happen with probability (0, 1) > 1.5) ~ 6.7%
For higher q, this probability will be higher. Roughly, we can anticipate that rel < rel uv happens when reluu > reluv frequently. The following result will show that this can happen more often than one would like.
Corollary 3.4. Let u E H2 and u E Le be two vertices with no common neighbors, i.e. such that relux. > 0 and reluv O. Then P(rel rel P( 1/22) P(T, 1) ~ 15.8%.
Remark 3.5. The previous estimate is based on the fact that for 2 30, in practice, N 1) is taken as an approximation for T
Proof. Since Pa..Pr vt = 0, we have cOs cos(Pue; Puo P
PuL.
and
becomes
VIIPu.
P.o
=P P < <el rel =P(T>
Pu
P V
(14)
Further,
Purll
Vnaa/ de /nee/ dP
duy / nun
de /
dg do // Voyl
/
VD
Po..
du / nvo
du
du
vELe
7cq
WEH?
-v-
du
dn
From the last estimate, we have To
PP.. V 2 (Ty > 7 1/2), and the claim follows from (14 and Remark 3.5 As mentioned in the paragraph after
P..
Similar results would follow if we took two vertices w, of high degree with many common neighbors and low degree vertex that has no common neighbors with and u. For simpler calculations, we took w u.
We provide corresponding results for the case of difference is that, while Corollaries 3.3 and 3.4 will result in poor ranking results for high-degree nodes, their analogous versions (Corollaries B.7 and [.8) will result in poor ranking for low-degree nodes. This is illustrated on Figure I Due to the high number of low-degree nodes, this phenomenon easier to notice empirically. Conversely, it is harder to note such a pathology for higher-degree nodes, since they usually scarcer.
$B.1l of the Appendix. The only notable
3.2 STABILITY OF RANKING FOR COSINE SIMILARITY WHEN P A OR P T
In both cases, for the dot product with respect to a given node, when using random projection for relevance estimation, node of low relevance can be estimated with higher relevance than the node of low relevance. We will show that this is less likely to happen with cosine similarity.
In the case of cosine similarity, for relevance we use relyv = cos(Par, Po*) and rel cos(X, (oss,,,, X..). The following proposition, shows the variety values that (reluv u, U E V) can have.
if nuw 0; if E Toe, Daw 2 1;
Proposition 3.6. For u, E V we have rel.v
if u E HT E Le, Dav 2 1;
where dmax = maXnev dn-
Proof. If Nue 0. by definition relue 0. If Nuv 2 and u, E Les from du d. S c and
Pho d we have 1 < J.d. < Vuum Flow
rehu < 1. If u E HJ. E La and nuo 2 1,
8

---

Published as a conference paper at ICLR 2025
from dus de S dmax and Rua dy we have: 2.. S reluo
Buy
yd
Vauule
vd.d.
vdd
Jye
1
Vrceq
vi
Again, we will have 7 2 1 and q >> c. Hence, the intervals in Proposition 3.6 are all disjoint in this case. This shows that relevance has different values in three non-trivial cases.
From Proposition 2.7 the next result follows.
Proposition 3.7. For all u V relux = rel and the approximation (rel u, v E V) can at most 1.
Further, both the relevance (reluv u, u E V)
as
This gives clear interpretation of the relevance: value of implies strong connection between node, and one that is is preserved; a value of 0 implies no neighbor overlap.
Corollary 3.8. For u, v, w, V, the following holds.
(a) Ifreluv then reluu- 1 0 relwo and rel > rel almost surely.
(b) Under the conditions of Proposition (c). ifrcluv - rrluhh > 25, then P(rel uv rel 2 1 8.
Proof. (a) From Proposition 3.7 (c), we have relua rel
Since rel is continuous random
variable, (ree 1) 0. Hence,
1 Preel ue S Preel < <1) P(rel 1) Preel 22
1) + + 0 Pr R < <1).
(b) With probability 1-6, 8, we have rel > relux and rel.. + e > rel Therefore, rel rel.. (relws + 2s) - relwh E rel
does not happen in the case cosine similarity (see also similar result for the adjacency matrix A in Corollary B.8 the Appendix). Part (b) of Corollary[3.3 shows stability, i.c., if two relevance values are not close, their estimate will highly likely keep their order. Part (a) of Theorem 2.6 provides similar asymptotic guarantees for stability.
Part (a) of Corollary 3.8 shows that the phenomenon from Corollary 3.4
The computational experiments in the next section will show, using real graphs, that the standard measure for ranking NDCG will depend on node degrees in the case of the dot product for both P = and
T, while will stable case of the cosine similarity.
3.3 COMPUTATIONAL EXPERIMENTS
We illustrate the results developed in the previous section for ranking application To that end, we consider the Gleich/wikipedia-2000nr 20060922 datasef" from the University of Florida Sparse Matrix Collection (Davis & Hu (011). The dataset consists of web crawling extraction of Wikipedia with 2, 983, 494 web pages and 37, 269, 096 web links. We define Ai = if page i links or is linked by page j. and 0 otherwise.
real graph.
We compare the rankings induced by the original and approximated relevance by evaluating the effect of RP by computing their NDCG. =: 7); as in (II. In particular, we evaluate the effect of R on the quality of the ranking y induced by their relevance relly when computed according to the three variants of similarity discussed in this paper: vf for RP Dot Product when P T, n for RP Dot Product when P A, and of for RP Cosine Similarity. Because the number of possible pairwise node combinations is very large, we evaluate a representative sample of the nodes using a stratified sampling strategy. To assure meaningful mixture of node degrees, split the set of nodes into three segments of size L = 1 x 10 (low, medium, and high) based on their ordered degrees. Then, we select nodes into three subsets by sampling 300 out of nodes without replacement from each of these segments, and take S Slow U Smed U Shigh as our evaluation sample. Finally, for each node i in S (and with respect to every other node j in 5), we compute v/," n and n,. considering the types of similarity (T, C) defined previously.
hhtps:/wwww.cise.ff.ciiii.. uff wtwp://www........ooooeeeeeaeiod

---

Published as a conference paper at ICLR 2025
1.00
1.00
0.75
0.75
rf
0.50
0.50
0.25
0.25
0.00
0.00
0.0
2.5
5.0
7.5
10.0
0.0
2.5
5.0 loga(d)
7.5
10.0
log,(d)
Figure I: Distribution of == NDCG, versus node degree d, On the left, we consider RP Dot Product when P = denoted by vi." We compare it with RP Cosine Similarity, denoted by "h Both scores computed using the same random projection matrix, with dimension q 256. The dotted line marks the lowest value observed for v/." of approximately 0.75. It can be seen that vj often takes low values for higher degrees (i.c., region below dotted line), especially when log2( (d:) 2 4. On the right, we display the equivalent plot for RP Dot Product when /' A, denoted by n/. The NDCG scores often take low values for lower degrees, especially when log2(d;) s 6.
With the previous definitions, we can compute the empirical distributions of J/K over the node degrees de for the three variants of similarity considered, with q 256 for the random projection dimension. In Figure [ (left), we compare RP Dot Product when / = ''' with RP Cosine Similarity, As expected (c.f., I..I). we can see strong disruption of NDCG when the degrees are high. Correspondingly. in Figure (right). we display the corresponding comparison for RP Dot Product when = A. As expected (c.f., $B.II), we can see a strong disruption of NDCG when the degrees are low. RP Cosine Similarity is observed to be largely immune to both of the aforementioned effects, and able to preserve the quality of the rankings, as anticipated in $3.2 These results are summarized numerically on Table 2 considering the samples taken from Snigh (left) and Sjow (right), for E 51,
Table 2: Empirical mean (std) of ranking quality yy := NDCG,D @K for K E (1,5, 10], and degrees log2( (d+) (last row), for i Snigh (left) and i E Slow (right). Bold face denotes lower mean values.
K
n/ i E Shigh
n i E Shigh
n E Shigh
Tf' Stow
1 E Slow
Th i Stow
0.589 (0.426)
0.954 (0.061)
0.964 (0.025)
1.000 (0.003)
0.057 (0.200)
0.999 (0.008)
0.607 (0.344)
0.920 (0.072)
0.924 (0.047)
0.999 (0.004)
0.168 (0.250)
0.999 (0.010)
10
0.602 (0.315)
0,899 (0.078)
0.895 (0.063)
0.999 (0.004)
0.327 (0.188)
0.999 (0.010)
(d),,
Shigh 5.274 (1.103)
(d.), i Slow 0.260 (0.439)
CONCLUSION
Based on the discussion and numerical results presented in this paper, we have characterized the different estimation behaviors of cosine similarity and dot product under random projections. While cosine similarity tends to show more stable behavior, the choice of similarity measure should be problem-dependent For applications where norm information is not crucial, cosine similarity can be preferred due to its favorable estimation behavior. However, in scenarios where norm information essential, the dot product may remain necessary, despite its estimation challenges. Our findings highlight the trade-offss imposed by random projections and provide insights into the potential pathologies for nodes of varying degrees, contributing to a better understanding of the estimation difficulties associated with different similarity metrics. As future work, we envision extending analysis to the sparse random projection setting by exploring, where applicable, possible similarities between Gaussian and Rademacher random variables.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This paper is an extension of the work conducted by the Graph Intelligence Sciences team at Microsoft, focusing on the relationships and connections of Office 365 entities. The authors wish express gratitude to their colleagues for their unwavering support. Additionally, the first author would like to acknowledge the hospitality of the Department of Mathematics at the University Washington in Seattle during the work on this paper.
REFERENCES
Dimitris Achlioptas. Database-friendly Random Projections: Johnson-Lindenstraus with Binary Coins. Journal of Computer and System Sciences, (6-4))
Anton Amirov, Chris Quirk, and Jemnifer Neville. Creating generalizable downstream graph models with random projections. MLoG Workshop at WSDM 23, 2023.
Devansh Arpit, Ifcoma Nwogu, Gaurav Srivastava, and Venu Govindaraju. An Analysis Random Projections in Cancelable Biometrics. arXiv preprint arXiv: 14014494,, 2014.
Luca Becchetti, Mare Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstraus lemma. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp- 1039-1050, 2019.
Monica Bianchini, Marco Gori, and Franco Scarselli. Inside PageRank. ACM Transactions on Internet Technology (TOIT), 5(1):92-128, 2005.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities. Oxford Univer- sity Press, Oxford, 2013. ISBN 178-0-19-953525-- doi: 10. 0001. A nonasymptotic theory of independence, With foreword by Michel Ledoux.
Christos Boutsidis, Anastasios Zouzias, and Petros Drineas. Random projections for k-means clustering. Advances in neural information processing systems, 23, 2010.
Maria Sofia Bucarelli, Matilde Larsen, Chris Schwiegelshohn, and Mads Toftrup. On Generalization Bounds for Projective Clustering. Advances in Neural Information Processing Systems, 36, 2024.
Timothy I Cannings and Richard J Samworth. Random-projection ensemble classification. Journal of the Royal Statistical Society Series B: Statistical Methodology. 79(4):959- 1035, 2017.
Ángelo Cardoso and Andreas Wichert. Iterative random projections for nigh-dimensional data clustering. Pattern Recognition Letters, 134915:1749-1755, 2012.
Haochen Chen, Syed Fahad Sultan, Yingtao Tian, Muhao Chen, and Steven Skiena. Fast and Accurate Network Embeddings via Very Sparse Random Projection. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM '19, pp. 399-408, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 47773496339763.. doi: 10.1145/3357384.333778
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-OOmat Improved Coresets for Euclidean k-Means. Advances in Neural Information Processing Systems, 35:2679 2694, 2022.
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithms, 22(1 (666))60655... 2003.
Timothy A Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transac- fions Mathematical Software (TOMS), 38(1):1-25. 2011.
Robert Durrant and Ata Kabán. Sharp generalization error bounds for In International Conference on Machine Learning, pp. 693-701. PMLR, 2013.
classifiers.

---

Published as a conference paper at ICLR 2025
Casper B Freksen, Lior Kamma, and Kasper Green Larsen. Fully Understanding the Hashing Trick. Advances in Neural Information Processing Systems, 31, 2018.
Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley. Johmson-Lindenstraun lemma, linear and nonlinear random projections, random Fourier features, and random kitchen sinks: Tutorial and survey. arXiv preprint wxxiv2108.04177 2021.
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2): 217-288, 2011.
William L Hamilton, Graph Representation Learning, volume 14 of Synthesis Lectures on Artifical Intelligence and Machine Learning. Morgan & Claypool Publishers, 2020.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionalityy. In Proceedings of the thirtieth anmual ACM symposium on Theory of computing. pp. 604-613, 1998.
Meena Jagadeesan. Understanding Sparse JL for Feature Hashing. Advances in Neural Information Processing Systems, 32, 2019.
William B Johnson, Joram Lindenstrauss, and Gideon Schechtman. Extensions of Lipschitz maps into Banach spaces. Israel Journal of Mathematics, (112))2991133 1986.
Ata Kaban. Improved bounds on the dot product under random projection and random sign projection. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD) '15, pp. 487-496, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450336642. doi: 10. 2221144//783358228888838
Keegan Kang. Correlations between random projections and the bivariate normal. Data Min. Knowl. Discov, 35(4):1622-1653, 2021. ISSN 1384-5810. doi: 10. (0077/106618021-00000
Jon M Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 599-608, 1997.
Tönu Kollo and Dietrich von Rosen. Advanced multivariate statistics with matrices., volume 579 of Math. Appl., Springer. Dordrecht: Springer, 2005. ISBN 1-4020-3418-8
Ping Li, Trevor J Hastie, and Kenneth W Church. Improving random projections using marginal information. In Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittshurgh, PA, USA, June 22-25, 2006. Proceedings 19, pp. 635-649. Springer, 2006.
Kun Liu. Random projection-based multiplicative data perturbation for privacy preserving distributed data mining. IEEE Transactions on knowledge and Data Engineering, 18(1):92-106, 2005.
Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of Johnson-
Lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, pp. 1027-1038, 2019.
Per-Gunnar Martinsson and Joel A Tropp. Randomized Numerical Linear Algebra: Foundations and algorithms. Acta Numerica, 29:403-572. 2020.
Ido Nachum, Jan Hązla, Michael Gastpar, and Anatoly Khina. A for Randomly Initialized cnns. The Tenth International Conference on Learning Representations (ICLR 2023), 2022.
Framework
Mark Newman. Networks. Oxford University Press, 2018.
Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, et al. The PageRank citation ranking: Bringing order to the web. 1999.
Qinfeng Shi, Chunhua Shen, Rhys Hill, and Anton Van Den Hengel. Is Margin Preserved after Random Projection? In Proceedings of the 29th International Coference on International Confer- ence on Machine Learning, ICML' 12, pp. 643-650, Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851.
12

---

Published as a conference paper at ICLR 2025
Aleksandros Sobezyk and Mathieu Luisier. Approximate Euclidean lengths and distances beyond LaansonnLindenstruuss Advances in Neural Information Processing Systems, 35:19357-19365 2022.
Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S Yu, and Tianyi Wu. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB Endowment, (11):992-1003, 2011.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks, In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 807-816, 2009.
A. W. van der Vaart. Asymptotic statistics, volume of Cambridge Series in Statistical and Prob- abilistic Mathematics. Cambridge University Press, Cambridge, 1998. ISBN 0-521-49603-9; 0-521-78450-6. doi: 10.1017/CB0978051 1802295
1802256.
Santosh S. Vempala. The Random Projection Method, volume 65 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, RI, 2004. ISBN 0-8218-20188 With foreword by Christos H. Papadimitriou.
Roman Vershynin. High-dimensional Probabilityy, volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2018. ISBN 978-1-108- 41519-4. doi: 10. 10.1017/78811080 108231569 An introduction with applications in data science, With foreword by Sara van de Geer.
Yongjin Wang and Konstantinos N Plataniotis. An analysis of random projection for changeable and biometric verification. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 40(5): 12001120-111 1280-123,, 2010.
Ziwei Zhang, Peng Cui, Haoyang Li, Xiao Wang. and Wenwu Zhu. Billion-Scale Network Embedding with Iterative Random Projection. In 2018 IEEE International Conference on Data Mining (ICDM), pp. 787-796, 2018. doi: 10. 10.110//CDM.2008..000 200940
13

---

Published as a conference paper at ICLR 2025
Appendix
This appendix is divided in two parts:
In Part A we provide detailed treatment and proofs for the general results stated and used in
the main paper;
In Part [J we provide results for RP DotProduct when P = A. This consists of a parallel
development that presented in ş2.1 and of. the main paper, when we had T.
A DOT PRODUCT AND COSINE SIMILARITY UNDER RANDOM PROJECTIONS
In this part, provide an in-depth study into the random projection mapping results discussed in the main paper. Our presentation focuses on general properties that are not exclusive to graphs.
AA..
we introduce notation and define random projection as a mapping.
the rotation argument provide representation for the dot product and cosine similarity under the random projections.
In A.
In $ we provide several asymptotic normality results for the dot product. We also use the rotation argument to derive an improved JL Lemma, and compare it with existing versions the literature.
In &A.IV we provide several asymptotic normality results for the cosine similarity, as well novel JL Lemmas, based on the rotation argument. Cosine similarity is a popular quantity to measure similarity. Although random projections have been studied extensively, there not many papers that include consideration of the cosine similarity.
V we provide few technical inequalities and concentration results that were used in other sections, for complete reference to the reader.
We begin by summarizing the main results of Part A in the following proposition. Proposition A.1. (a) For every i.j we have
(Rp, Rp;) N (pi (p). 1|2p=11"1p==1" + (pj.
(pp. p.)9)
(15)
(b) Let (0,1) and d E (0, 1), then for 2 4. ييب log للييا we have that (Rp;, Rp,) - (p), p.)l <El|p, Illp.ll
for <. with probability least 1 5.
Recall that we used a random matrix R = [Ra]] E R9xn, where (Rij : n,j..,n,j=1.. are i.i.d. normal random variables with mean zero and variance 1 1/q. Here, p1.--- Pk will be vectors in In who are then mapped to vectors Rpi...., Rpx in R7, Other notation in this appendix is described in Table
Proof. Item (a) is the statement of Corollary A.11 Item (b) is the statement of Theorem A.17
We note that if p; and pj are orthogonal or (p:: Pý) is small, then ||p||l M can still be large. Hence, by only the dot product we have very little control on the size of the error in both parts (a) and (b) of Proposition A.
In the main part, P4 and p, had non-negative entries, and therefore, the dot (pt, P.) products are always non-negative. What is the probability that ( (Rps, Rp;) will be negative? Remarkably, we are able to
(pj.Pc) Pc) =: cos(p,, Pt)
provide a closed-formula solution dependent only on the cosine similarity of Pý and p::
1p, ||p
14

---

Published as a conference paper at ICLR 2025
Table Notation and symbols used in Appendix A
original dimension
M2...
vector with entries ,.,, M,) vectors in R" dot product in R= I
dimension of the projection space
I, M.PI. .P. (:--)
R
random projection matrix equal to or distributed as /qR std. normal random vectors in IR"
Q
P. Pa.y T
cosine similarity t-distribution with parameter 9
M,N
Proposition A.2. If (.). > 0 and cos(pj, # then
ccos(p;. P:)lV/
P ((Rpj, Rp:) < 0) P Ta
cos(p),
where Ty is the t-distribution with the parameter q.
Proof. Fact (pj,pt) implies cos(p;, -. Therefore, the claim follows from Proposition
A.8
Proposition A.3. (a) For all i.j such that pt + and Pj + O, we have:
cos(Rpi, Rp:) 2 N cos(pps.p)) ps), - cos (pr, p;))
(16)
(b) Lete (0, 0.05), E (0, 1) and pr, Pr....,,K Pk non-zero vectors in RR. For
2k(k 1+
2ln
8
2
(17)
In 1
x² 2(1+ev2)
the inequality
1cos( Ryj, Rp:) cos(p;, p:)] S E(1 cos(p).Pt)
holds for all j with probability least 1 - 5.
Proof. Item (a) is the statement of Theorem A.21 Item (b) is a modified statement of Theorem A.28
Note that Proposition A.3 give us guarantees that the error between the projected value and original value is absolute. Additionally, the closer cos(p), pc) ) to 1, the smaller the error.
A.I
GENERAL RESULTS AND REMARKS
A.I.1 VECTOR REPRESENTATION
For any vector æ in R. we will denote ã : xr/[|=/]]
Note that for non-zero vectors x and y in R.,, cosine similarity has the property
(z, v) (x/1|>]]] = (ā. Ø) |
(18)
Also, for any matrix Q E Rexn
(Qx, Qu)
(Q(=/Il=l). QQ//lvlD (Q7, Q7)
(19)
Q Qull
|MDII [Q
For unit vectors & and ÿ. we know from the Schm--S process that there exists unique vector T such that
f (7. ū)
rs.5
15

---

Published as a conference paper at ICLR 2025
Recall that ra.g is perpendicular to ý. Hence, have ||r /1 -1-10 (it, 0)². Hence, set Ta.g = T | and we have
I == (3. + v (#t, fz.
(20)
Note that I and Fz.g are unit and orthogonal vectors.
We will often use Pay
(z.y) M+
to denote the cosine similarity of æ and
We can now summarize our findings.
Proposition A.4. For any two non-zero vectors and IR" there exists unique unit vector f2.9 orthogonal to such that
pi v1 p
where P the cosine similarity between x and y.
A.I.2 RANDOM PROJECTION PROPERTIES
In this paper, Q will denote random matrix whose entries Qij (O, are i.i.d. Random vectors consisting of i.i.d. (0, 1) random variables we will call standard normal random vectors. Note, can be obtained by setting == VQP..
Lemma A.S. Let and be two orthogonal unit vectors in R", iee. (x, y) = 0 and ||>||| = lvll 1. Then Qu and Qy are two independent identically distributed standard normal random vectors of dimension
Proof. We can show that
(Qz)a. (Qu).. (Qy), are i.i.d and ((0 1).
Note that
(Qx)x = Σ
Qkyæy NO0,
(21)
j=1
and
(Qu)a E
QKius N(O, 11v11
(22)
Therefore, all of these random variables have the distribution A/00 1). From the defini-
tion of Q 21 and (22) we can conclude that the sequences (Qz)1, (Qu)....., (Qx), and (Qy) (Qy)2. ................................ (Qy)a are i.i.d.
Finally, let us look at the covariance between (Qr)a and (Qy)--
((())))(QV)]== = E
Qkyay
Σ Qiyus
(23)
If 1 + & then two sums under the expectation are independent and hence
]
23
E
Quizz
E
Eouu
Σ Qusus
= 00.0. O.
Else, if 1 = then:
23
E
Piy マソリة +2 Σ
Qky Qkiz
E Jiili 2
BIQ Qud 2384
Σ
ززايi = (x. = 0.
1=1
The claim now follows.
16

---

Published as a conference paper at ICLR 2025
Recall that R q- is random matrix whose entries Ray (O0 1/9) are i..d. Note that, due to the scaling properties,
(Qr, Qy) IQ
(Rx, Ry)
(24)
R Ryl
We will state all the main results in the term of the matrix R, however Q will let simplify some proofs.
A.II ROTATION ARGUMENT AND ORTHOGGNALL REPRESENTATION
Let and be vectors in R" and
(z,9)
We will show the following result.
||
Theorem A.6. There exist independent standard normal random vectors M, N of length q, such that (a) For the dot product have
(Qz, Qy) = (VqRa, Rqyy) = ||=|I|и||e||| + MII p22).
(25)
(b) For the cosine similarity
(Qx, Qv)
(Ra, Ry)
P|NNII + MI MIVI- -
(26)
Rx Ryll
V VoINNI + MI MI p3)2 + p2)
where Mj is the j-th component of the vector M and M2...q = (M2...., M₂)-
The rotation argument is powered by the the following Lemma. Recall that N = N/II
Lemma A.7. Let H and N be independent standard normal random vectors of dimension q. and U an orthogonal q matrix such that U xz N C1. Then random vectors U n H and N are independent standard normal.
Proof. Note that for every orthogonal matrix U, vector U. is normal random with expectation and identity covariance matrix. Therefore, it has the same distribution as H.
We will show that (U H, N) has the same distribution as (H,N). Let s'v be the density of N and since N is independent of H we have
P(USH E A)Sx(z)dz
=
JEB
U
P(H ()Nx())d=PP(L) ANE
ZEB
for all measurable subsets A, B of TR.
Proof of Theorem A.6 Note that Qž = pQu P Since, (5.Fx.8) by Lemma A.5 we know that H = Qūz.0 and N = Qū are independent standard normal random variables. Hence,
we have
(Qz, Qv)
(Qā, Qū)
(pN (H,,H (pN VI-PHHN (27)
19
[Qx|l Qull
ION 11- |2H|||N IIo1 -1- |²H||
We now pick the orthogonal q x g matrix U for which U = Applying the Ur-tranfformaaion to all arguments in (27 we get
(Qa, Qu) |I
(U (P 11-112H,,00 ( (ll p IU ( H2
||e||// + PU H||
Setting M = Up H. By Lemma
A.7 M remains standard normal random vector independent of N.
17

---

Published as a conference paper at ICLR 2025
We apply the same arguments to the dot product:
(Qε, QŪ) = (pN + /1 p²H, N) = |N + /1 12H-PHHNN
+ (X)) -INKIIIN + PU-
-IINVII + - +|M -I-
GENERAL APPROACH
The results can be generalized using the properties of the Wishart distribution from the theory of random matrices We will outline the approach, based on to several results from $2.4 in (Kollo & von Rosen 2005).
Let Pt, P2,...., be vectors in R" that form the columns of matrix P. The matrix PTQ T is random matrix with a central Wishart distribution W₂ (P' T P.g). Note that (P (PTP). (pi, Let I. I. be the Cholesky decomposition of PT P. Using the properties of the Wishart distribution (Theorem 2.4.2 from (Kollo & von Rosen, 2005)). we have (x P, q) = WL q). Let T be the Bartlett decomposition of Wishart matrix with the distribution W₂ (L, n) (Corollary 2.4.2.1 from (Kollo & von Rosen 2005)). Then,
pT PTQTQP LT..L.
Finally, we know that the elements (Ty : i.j = 1,.... p) are independent, where T3 ~ (n-1++1
i 1,..., k; Tej N(0, 1) for < and the rest of the matrix is zero
||]||||
For k = 2, when p1 = x and p2 y we have L
Hence, we get
|||l|||b||
vI p² |yll
QP
|
|| + -I--PTT111
| || + vI - p2Ti1Ti2)
(1- + (V1 - PTi1 - pT2z2
Note that since [| M2.... M1) (Ti,, T22, Ti2), last equality provides the representation obtained in Theorem A.6
A.III ASYMPTOTIC AND FINITE-SAMPLE RESULTS FOR THE DOT PRODUCT
In this section we analyze how the dot product changes under random projection. Some the results here are well known, but for completeness and to demonstrate the power of the representation in Theorem A.6 we will prove them.
I.III.I PROBABILITY OF SIGN CHANGE
One of the practical questions when doing the random projections is will the dot product or cosine similarity change the sign. In practical settings vectors x and y can have all non-negative components and as such their dot product is also non negaavvaee.. Can the projection change that? The representation for the dot product gives us an exact answer to that question.
Proposition A.8. (a) (z. y) and | * 0 then P((Rz, Ry) < 0) P((RR, Ry) > 0) z.
We thank the reviewers for pointing this to during the review process. Since we were not able to find the result explicitly in the literature outlining the approach here.
18

---

Published as a conference paper at ICLR 2025
(b) If (z, v) + 0 and lpl # 1 then
(Rx, Ray (x,
<0) 0) PP
lplv
where Ty is the t-distribution with the parameter q.
Proof. In the case (a) p 0 and the claim follows from the 25 since the sign depends on the sign
of M1 which can be positive or negative with probability (b) we can assume (x, y) > 0 and therefore p 0. Hence.
(Rr, Ry)
0) P ((Rx, Ry) <0) P (q 1/2Qur 112Qu) <0)
IP
(x,
PP ((QEE, Qu)
< 0) (AIINII + M1IINIII 0²
x²<00 <0)
M1
P =F
M
PVq
=P
|
v1 /2)
VINTP/
VI-
Since Ty
M
t(g) the claim follows from the fact that t(g) is symmetric random variable
/p for the last expression have
P/9
PVq
P
To
TT
V
V
As see from the graph on Figure 2 the probability of changing sign is the highest for O and and quickly becomes really low. From Corollary 3.2.2. in (Kaban 2015) we know that the
(Re,Ry
0) S exp(-qp² /8) and the result here gives the exact value of the probability.
(a.y)
66
92
Figure 2: Graphs of functions p + Tg on the interval [-0.5, 0.5).
10 /g
and p + log IP
Ta
lol/a v1-p²
for 100
/1-p²
This results tells us that the probability of the dot product sign change under random projection is a function of p, which in practice we don't know. If we wanted to calculate probability of cosine similarity or dot product changing signs in case of a large number of vectors it would he hard to do can expect the sign to change, while if
still conclude that if p close to it is reasonably far from 0 is unlikely that the sign will change.
However
A.II1.2 CENTRAL LIMIT THEOREM
The representation given in 25 has many consequences. For example, we can simply calculate the expectation and the variance of the dot product.
Proposition A.9, We have E (Rx,Rg) = and Var (Rx,Rg)
14
11
19

---

Published as a conference paper at ICLR 2025
Proof. Recall that [[M]] and B[M]] we have
1; [[|| and |||| q(q + 2). Using
25
RRx, Ry)
E
= - /VI + B n²)
| relllyll
= bo-bb. bo + [|| vI- =
and
RRx, Ray) 27
E
||=|| Ivll
q P [|I 24 3 M I p² + 2 [ - |2)1
1 1+
=q 2 + 2) + ? q 1 (1 (²)
9
Now, since Var
(Rx.Ry) |
RRl 2 ylll
2
(E
))
the claim follows.
We can also get the following asymptotic result relatively easy. Theorem A.10. We have
(Rx, Ry)
p S N(0.1++p))
V
|
as Q - 00.
Proof. Form the Central Limit Theorem we have
|| -
v7 q 11112 Σ3 (N3 -1 N 2) and
by the Law of Large Numbers we have independent, we have
1 Vq
|N
/
N? + N2
almost surely. Since M1 is
(Rx, Ryy
0 = [p. || -9 + M
|N
V1 - ,2)
|lvll
Vq
- - N 20²) +N
NO0
We can write the last result in the following form, which we stated in part (a) of Proposition A. Corollary A.11. We have
Vql(Rr, Ray - (z, v)1 $ N/ | (a, v)),))),
as 9 DO.
Although, (Rx, Ry) is unbiased and asymptotically normal estimator for (ær, yy), the control of the standard deviation can be a problem. (a, y) could be small compared to the value of a
= Fl +(x,) Let x (1, 1, and = (0. 1, I,...), then (z, y) 0 and o z
However, since & n the random projection might be nowhere near the value of (x. v). Simulation in Figure illustrates this issue.
A. 1II.1. CONCENTRATION RESULTS
So far we have shown that RRa is an unbiased and asymptotically normal estimator for p. However |ل
when have many vectors and want to be sure that all of their similarities get randomly projected to approximate values we will need to use concentration results.
First, using
(55 calculate the Laplace transform.
20

---

Published as a conference paper at ICLR 2025
0.002
0.000
Figure Simulated dot product (Rã, Rý) for æ = (1, and = (0, I....) for 2000 and 9 100.
Proposition A.12.
We have
Elcxp(A(QE QU)1 = [11 p){1 M(p - 1)]]_a//2
(28)
for A E - (1
Proof. Recall that R(eAM1) = ex² /2 for all and E(eAI|N1??) = (1 2/22 for X < 1/2. By
applying the Laplace transform first to M1 and then to || we get
Blexp(A(QE,, Q7))] E APAlIVII
M A 1
E
=E AMDMNIP 2 ((- -
= -1- - x1 - /3)) 4/2 = [(1 X(1 + (1)++))(1+ A(o 1))]
We will now use the the Laplace Transform to obtain Chernhov bounds. The following Lemma will be a useful estimate.
Lemma A.13, For X E (0, (1+++))) we have
X²g(1 + p2) 2(1 1(1 + p))
Lexp([xx(A\[(EE Q5) qpl)p
(29)
and X E (0, (1-p)) 11
X²g(1 + p²) 2(1 - X(1 p))
log E Bexpe(->\((Q qp)]] <
(30)
Proof. case 0 or p expression will simplify and we will be able use Proposition A.35 on X and -X respectively.
One can show that for E (0, 1) we have (see Lemma A.38 (a)):
l=log(1 - 8) 8) < 2(1
(31)
and for s < 0 (see Lemma A.38 (a)):
(- logg1 (1 - 3) - 8) - 32
(32)
21

---

Published as a conference paper at ICLR 2025
We will prove
29
30
is shown in the same way.
log B exx X Q2, Qū) qp)]
log(1 - X(1 + p)) - 9 log(1 11 - A(p 1))
ーxp--
2
- log(1
A(1 + p)) A(1 + p)]
2/4
1 |-oog(1 2(p-
((0-1) -1]) - -Ap - 1)
2
2
(A(1 + p))
+ (N(p 11)
2(1 X(1 +D)
2
9
(A(1 + p))
+ (Npp 1))²
2
2(1 X(1 p))
2(1 1(1 p]]
(A(1 + p))² + (N(p- 1))² 2(1 p1)
12 + p²)
2(1 - X(1 p))
This proves (29 the equation 30 can be proved in the same way.
Theorem A.14. Fort t 2 0 we have
-12
P((Q7, qo 1) S exp
(33)
29(1 + p2) + 2(1 p)t
and
-12
P((QE, Q0) 9p < -1) exp
(34)
2g(1 + p²) 2(1 p)t
Proof. Note that [[ Qū) qp.
Since 29
holds we can use Theorem A.33 by setting X = (Qi, Qū) to obtain 33
Since 30
holds we can use Theorem A.33 by setting by setting X (Q Qÿ) to obtain 34
Proposition A.15. For any function f [|1, [0, 00) we have:
P((QŻ, Q5) -g > (pf((p)) < exp
(P)(p)
② 2 1+
c3
1+ 1+ M())
(35)
2(1 + 02)
(p)
1- T T+ 12)
P((QT, Qī) 90 < (p)) S exp
(36)
2(1 + p²)
Remark A.16. Note that for p= and f(p) we get the usual bounds for x²(g) used to prove Johnson Lindenstrauss Lemma as given, for example in Lemma 1.3. of (Vempala 2004) and Ghooooh al. 2027).
A.111.4 JOHNSON-LIDENSTRUUSS
RESULT
Theorem A.17. Let PI.... ... Pk be finite set of vectors in R and let E (0, 1) and 8 e (0, 1), then for q 2 4- Life log k(k-1)
(Rp,, Rp.)
(py,Pa)
<
|p:ll |py Ip:ll
for < with probability at least 1-6. 6.
We have cosine similarities in the statement above and in practice will have way of estimating them. To prove this result need probablity estimate that doesn't depend the value of the cosine similarity. The following Proposition will help us in that by simplifying the statement of Theorem A.14
'One exception is the case when .i...., T. are all in [0, no) i.c. have nonnegative coordinates. In that case know cosine similarities will be in interval [0, 1).
22

---

Published as a conference paper at ICLR 2025
Proposition A.18. For 0 we have
RRx, Ry)
-qE²
P
| 25 S exp
cexp
(37)
4(1 +
and
(Rx, Ry)
qE²
< -E)
1 exp
(38)
|
4(1+E)
Proof. By setting qe in (33 get
P [Rx, Ry)
-9E²
>6 8) S exp
|=>||l
2(1 + p2) 2(1 + p)e
Using the fact that |p| S we get
9e"
-gs
2(1 p²) + 2(1 + p)c
4(1 +)
This proves
37
Bound in (38) can be shown in same way.
Proof of Theorem A.17
Define sets
(Rpy. Rp.)
(pp.Pt)
A.j
<
||p||||pP||
(Rpy, Rp:)
(Py.Ps)
49 =
I|p/l| ||ps|||ee|
E
(Rps, Rp:)
(P))Ps)
< -
||p]l||pd
Note that Agj- = 1 U A
Using the union bound tehnicque we get
U ( U.S
P
Aij = =1-p
1 =1
- P
21 iC]
IIP(ASt) + P(ATT))
From Proposition A.18
and bound on & we have that
E²
Σ k
(P(At))= + P(A S
k:k::
exp
(-9 + +
exp (-4.
1+6
k(k 1)
1)
x²
I k(k - exp
22 log
6.
8
4(1 + E)
A.III.5 COMPARISON WITH KNOWN RESULTS
Regarding known estimates for the dot product, Theorem 2.1. from Kaban 2015 provides the following bounds for e E (0, 1):
(Rx, Ry)
and P (Rx, Ry) [|z|||yv
p << -e S se- ?e
p > S
||>|||a|||
This a simple consequence of Proposition A.18
Equation (4) in [Kang] 2021) and Lemma 5.7. in (Vempala 2004) provide the following estimate:
(Rx, Ry)
<
2 4e
|
Since 2² - 83 5 2² 1 again, from Proposition A.18
we can get a better estimate
(Rr, Ray
S
2e 401+e)
|
23

---

Published as a conference paper at ICLR 2025
A.IV ASYMPTOTIC AND FINITE-SAMPLE RESULTS FOR COSINE SIMILARITY
In this section, we will examine the behavior of cosine similarity under random projection. We will begin by examining some special cases and then develop a general approach.
A.IV.1 THE CASE OF p = =1
Recall that in the case of p == +1, i.e.
(x, y) |
+11
there exists inequality.
0 such that tay. This is known consequence of the Sauchy-Schhwar
In this case have
(Rx, Ry)
(R(# Ry)
d: Ry, Ry) a: Ry Ryll
Ryll
+1 p.
(39)
Rx ||| Ryl
R Ryll
Ryll
turns out the that this is preserved under random projections. Proposition A.19, If
[ Ryll +1 then there exists a such that zay (almost surely).
(Re.Ry)
Proof. Since the cosine similarity of Ra and Ry is +1, then there is an a > such that Rr = t Ry. Hence, w = R(x F ag) Let assume x F ay * then R(x F ag) is q-dimensional vector with entries distributed as (0, ||ı F azlll//). The probability of which being a zero vector is 0. Hence, have tay almost surely.
Hence, the in the cosine similarity of =1 will be preserved under random projection Q.
Corollary A.20. If
[Rl 1 almost surely if and only if (x.z)
(Rr.Rty
+1.
Proof. RR).Ry) Rell =1, by Proposition A.19 holds and only if tay for some 0, and, Cauchy-Sheward inequality, this holds if and only |elll
(x.z) = +1.
A.IV.2 CENTRAL LIMIT THEOREM
In this section we will show that the value of (Rt,Rt) [ Ryll
approximately normally distributed around
P with variance (1-mP)2
Theorem A.21. For non-zero vectors x and y in RD we have
q
Rr.
Ry) Ryll
(x,
$ N
0, 1
(x, | )1)
273
(40)
Rx
|
as Q > 00.
Theorem A.21 12110 can be proven using the delta-method technique. We will use the representation given in Theorem A.6 to prove it.
Lemma A.22. Define T, p|| + MI / 1 p² and Bg = ||2....ll then from 26 we have:
(Rx, Ryy
(T₂) - pp²
1
p (1-
(41)
Rx Ryll
(T₂)² + (1 (1-p2) B² Tg + Pp (Tg) + (1 (1-p²)B3
BB)B3
24

---

Published as a conference paper at ICLR 2025
Proof. We have:
Tg - PV (T,)² + (1-
(Rx, Ry)
Tg
p= ((T.)² 22 + (1 BB)
RR Ryll
V(T.B= + (1 - B
Tg - - (T.) + (1 - B))
Tg + Pv (Tg) + +(1 (1-1p) B?)
p(TT)
(T,)2 + (1 101pp B²)B²
Tg PV (Ig) + (1 - B?)
(1 - (Ta) - -
V (TT)) (1 B2}
Tg + P (Tg)² + (1 p²)
Proof of Theorem 1 Numbers, we have
We will use notation and results from Lemma A.22 From the Law of Large
Tg Vq
p
N2 4 1/2 V
-p 2- p= =p=p P
(42)
almost surely, as q + co. Using the same arguments, we have
B. v9
+ 1 almost surely. Hence,
T 2 v
Bg 2
q
1/2 V (Ta)² + (1- B²) (1
+ + - p²)
02 + (1 p²) 12 =1
(43)
almost surely as q + xc.
42 and 43 now imply
(T2 + PV (Tg)² + (1 - B2) + + P 2
(44)
Using the Central Limit Theorem, we get
Bº - 9 1
1 4 (002),
(M3 - 1)
Vq
Vq
Vq
T2 - qp²
| 9
|N
M1 + (1 - /2) M?
+ 2p 1 2
V
Vq
V
V
4 P' 2) +
-0
Now, we have
(Ra,, Ry)
/9
| [ayll
T2 v/ 12 -/-0"
qn²
22--
(1 (1-p2)
9-1/2 / /(T,)2 (1 - -2)BB3 g-1/2 + pT,))) + (1 -2))
NN00 20²h D²N((0,2) 2) 1- = (1 (1-1²) p2) 11--
N(0, 402
-2p*) + 20
1
2p
2p
(1-p2) (00-0) N(00,4p)
-1- (1-
= NO (p22))
2p
25

---

Published as a conference paper at ICLR 2025
-.4 -02 0.0
0.2
0.4
Figure 4: Simulated random projection for 100, where (z, ///////////ll///// 0.1544
For practical purposes, we interpret the result as given in (6) that for large we have the normal distribution with small variance. Hence, it is likely that the cosine similarity of randomly projected vectors will be close to the one we would get without the random projection.
From simulations, see Figure 4 even for q 100 have approximately normal behavior, but the variance is large and the value might not be close to the original similarity. The result Theorem A.2T will be useful for larger values of qz
The same result holds for the empirical correlation coefficient in linear regression and in this case known that this is not practical result (see Example 3.6. in (van der Vaart 1998)). However, are in a different setting here and the numerical simulations suggest that this result is stable and can be used in practice even for moderately large values of q. For example, for values of q 2 6400 the error will be =0.05 with the estimated probability of at least 0.95. Concentration results to follow will further confirm this.
A.IV.3 CONCENTRATION RESULT
Theorem A.2I guarantees that for large the cosine similarity random projection will be almost preserved with high probability for any pair of vectors in R" However, this approach is not feasible analyze the behavior of all pairs of vectors in given /1,-.-u , lk. the computation becomes intractable and hard even for small values of k. If we want to get some guarantees that the similarity of all pairs of vectors is preserved within small error with high probability under random projection, we need to use concentration inequalities.
The following theorem is the main result of this subsection.
Theorem A.23. Let x and be non-zero vectors in Rº and E (0, (0,05,55), then
IP (RR, Ry) |a]||| [[
2(1 =(1 - (4+
1
2(1 2(1+ev2)
Recall the representation from Theorem A.6 For a given random R. for any vectors & and y in R there exist standard g-dimensional Gaussian vectors N = - and M = = such that
(Rx, Ry)
p p|
M1 MIVI-p
|| Rox ||| Rell
V M / 222 (1 M2)||
BOUNDS ON TAILS
We will first determine some tail bounds. We start with the following lemma.
Lemma A.24. We have
Mi
Mi
P
M2...ql
>E
=
||Ma...gl
< <-E) (1+ 2
26

---

Published as a conference paper at ICLR 2025
Proof.
Note that M1 .V( 1) and || x2 1) are independent. The equality Mi
M2...gll -8) follows from the fact that both Mi and -M have the same distribution. Further, by Markov's 's inequality we get
M22.. IP
M )e)
M1
E[P (Mi > M2.. 11ll ID]
|M2...9
||
Elexp (- 112/] (1 + =
The last equality follows from the fact that || 12 has the x² 1) distribution and the Laplace transform for this distribution.
Lemma A.25. For we have:
|M
E
E²
TP
VI+E
1 1+
1 +
(45)
MM
2
4(1 +
|
62
I
<V1- <V1-E)
$
1+
(46)
|
2
4(1 E)
Proof. Using Markov inequality, we have for all À E 10,1/2)
|N
IP
M|22... 11+8 = P( > X(1 + M2..
P( - 2(1 + 6) 66]| M2..g1 112 > 0) P(exp(XINN - 2(1 M)../ > 1)
I <EleNINNP--M(())))MM...... Ma..
1
(1 2
(1+ 2(1 + +
Note that,
(1-22)(1 + +
1 2E 4(1 +))2
2²
22T++ - 2/1+
1+
4(1 +8)
By setting À 4([+6]
we get
(1 - 22)
(1 2() -
(1 (1++2(1+) + 22) + 2 -
= 2
4(1 + +
This proves 445
In the similar way we prove 46)
NN
P
< <1-E) E)
P( A(1 - M2)
M|
12
= IP(((1 - 11---11111 2 > 0) = P(exp[A(1 - =) MM |||N1111 > 1)
< II
1
(1+ 22) (1- 2(1 - =
Note that,
(1+ 2 E)A)
=1+ 2s) - 4(1 - E){²
8²
= =1+ 4(1 -) E)
2 =E-
12 1-
27

---

Published as a conference paper at ICLR 2025
By setting À a(1-c) get
+1+ 2 (1 2(1 -
= (1 2(1 - [(1 -
- =)))--
E
8²
1 2
1
4(1
This completes the proof.
Corollary A.26. We have
||
2
P
MM2...l
VI+E
+P
(MM....l
2
1
4(1
(47)
Proof. Using
45
(46)
and the Cauchy-Schwand inequality we have
||
|||
MM2...9l
vI
E
+ P
M
I
22
1
2
4(1
+
8)
4(1 8)
g2
g2
S
1
1 +
2
2
4(1 + 5)
4(1 8)
E2
c²
S V2.
12
1
4(1
+5)
4(1 + E)
PROOF OF THE CONCENTRATION RESULT
We need one more lemma to have everything for the proof.
Lemma A.27. Given (0,0.08)
Mi
z/2 and VI-E<
[N|
vI + E, then
||
M2
(Rx, Ry)
- 0 S __ (1 p²))
Rx Ryll
V2
Proof. Recall, we used ((s) -ंं and let us define (hh) = (-) (h) (19451877 O. hence an increasing function. We have
Note that
.T+
(Rx, Ry) vb (DINNII+ M1 MI p² [Rx Ryll
N
Mi M2....
[I.a....gll 122 +
V1
12
M2.....l
and
p
/I
p
28

---

Published as a conference paper at ICLR 2025
We will prove the claim for the case when 0; the other case is proven in similar way. Using non-negativity of and the fact that v is increasing, we have
1b
p pa VI
1
VI P
VI
2/
p²
(Rx, Ry)
PS
Rt Ryy
v (vi-222 vi+ 3)
:)
(v/1- P (48)
-
(V1 p²
Using Lemma A.42 (a) we can estimate the upper bound:
P
8
p
1
+
2
p2
p²
3/2
+ 1- p²
(VI+E - 1)
p
2
I (1 - 22/3/2
P
+
V
p² 2
2
$1 /²) cpp + V1- p²)
(49)
Since + v1- 2 S 22, we have
49
< (1 - p²)
(50)
V2
To prove the lower bound in 488
first need to note that fT-p2 vI can be negative
very close to O. For that reason, we will have to consider two cases: 1² < or p² > E.
If p² 8,
P
v1
VE>E.
(51)
VI p
we have
1 -
2 >0,
(52)
V1- x²
and in particular
E V - 2 0
PV1 - E
(53)
2
Let
p
A 1b
= <p>0 0,
V1
and
- -
B: &
> 0.
From
52
have B 0, and hence since y is increasing function have A> B
29

---

Published as a conference paper at ICLR 2025
We obtain
PVI-E 8/2V1-111 Pa
A - B = 0
VPVV - 8 - 8/2 - 172
(1 p²)
Lemma A.40
- =/2V p
vi-E
+ E 1 - p
1 1- - EP²
V1 -1
2 2 Ep
5
8 - 0²
E 8V 1 p²
1 p²
8 p²)
5(1 p²) 2(1 E)
<
(54)
2/1 Ep
2/1 Ep²
EP
2(1
ep2)
Since E E (0, 311 we have
2(1-z)
s 2
3
v2
v2
1
and hence
c(1 p²)
(55)
V2
On the other hand, if p² S Lemma A.42 (b) implies:
p
p
- 1/
8
p2)
2
P
(1
v1
E)
+
p
8
+
8
v1
p²
2
V1
p²
1 v1
2
p²
P
e
+
p².
(56)
p
14
VI
-
2
v2
V2"
Since p² E, we have p E [0 and
1
1
0²
Vs
1
V1- x 1+ v1+vi- +
+
v2
v1
8
+
- 8
v2
This expression increasing for E E
(0, 10 so
1
+
0.70708 <
-
2
V2
2
==0.8
Therefore,
c(1 p²)
56
(57)
2
Finally, the inequalities (50)
(55)
and 57 prove the claim.
Proof of Theorem A.23 Since & E (0, 0.055). we have 2v2 E (0, 0.08), then by Lemma A.27 we
have
(Rx, Ry)
p 2 E(1 p²) 2e((-
-111211) Ryll
(Re, Ry)
EV2
P
=P
p
V2 (1
|xx|
|Ry||
M1
EV2
+P M1
< IP
<
||Ma...al
2
||M2....ll
2
||
||
+ PP
(V1+
1
+P
<V 1V1-
M2....ll
[I.Me....ll
30

---

Published as a conference paper at ICLR 2025
Using Lemma A.24 and Corollary A.26
have
22
8²
2
1
+2
2
4(1
sv2))
8²
(2 5
1
1
+2
1 +
2
4(1 + 2V
E²
(2++
+2 1+
4(1 (vv2)
4(1 + =v2)
= -4+6
1+
+(1
A.IV.4 JOINSON-LLIDEESTTRAUS-TTV RESULT
Theorem A.28. Lete (0,0.05). 6 (0, 1) and p1.-...P2 Pk be non-zero vectors in R.. If
2k(h 1)
2 2ln
q 2
(58)
2(1+ev2)
then, with probability
6, the inequality
(Rp Rp:)
(Pj.P:)
< -2) p²)
Rp, Rp.ll
|py||lpp|||
holds for all i < j.
Proof. Define
Wi = (1 (Rpj. Rpa)
(pj,P:)
< 10--ppp -2))
| [|Rp,|||RPi] Rpil
||; [|p
To prove the theorem, suffices show that IP (Usz) W3)
< 8.
By Theorem A.23
we have
k(k - 1)
4 (1+ (1+
8² =) [ [1+
P
U W
Σ P (WG)
2
2(1 + 2V2)
This expression is less than 8 by the choice of g in (60).
A.IV.5
RESULT COMPARISON ANALYSIS
In this section, we state Lemma 5 from (Arpit et al. 2014). which gives a similar result to Theorem A.23 and compare the two results.
Lemma A.29, For and y non-zero vectors in R2 and for every B E (0, 1/2), have
B p)
RRx, Ry)
8
(1-))-)
(1 p)
Rr
Ryll
1
ip S -E,
B
(Rx, Ry)
3
(1 p)
-PS
(1 + p)
1- 9
|| Ryll
1
-5- S SSSE
B (1+p)
Rxx Ry)
3
P
(1
1+ 3
1-
if 2 E. Moreover, the inequality holds true with probability at least Sc 4
31

---

Published as a conference paper at ICLR 2025
Remark A.30. We observe that Lemma does capture the fact that when p =1, the random projection preserves the cosine similarity, as discussed in SA.IV.I
Also, the role of unclear. If we set E = max I-3 I+3
1-31
} = 3
I-3. the result can be rewritten as
(Rx, Ry)
-E(1 (pl)
p S <(1 (pl)
(59)
|xx] Ryll
with probability at least 1 8c
We note that the inequality (59) is less precise than the one provided by Theorem A.23
Moreover, by Lemma A.41 have 1 2(1+cv2)
Se (1te)? Therefore, the inequality in Theorem A.23 also holds with higher probability.
We remark that Theorem A.23 requires E 0.05, but this is reasonable absolute error for cosine similarity, which ranges from 0 to 1.
We will see how the dimension selection Theorem A 28 for cosine similarity compares with the similar result in original Johnson-Lindenstrauss Lemma. The following version is based Theorem 13 and Remark 2. 11 from (Boucheron et al., 2013) and we present it without proof.
Theorem A.31. Let e, 8 E (0,1) 1), and pr..... Pke be non-zero vectors R If
k2
log
(60)
then, with probability at least 1 8. the inequality
(1 =)pe pyll < |[[p p,)11 < (1++)) +)lpp pyl1
(61)
holds for all i < j.
In the following we will use the notation f that will denote
lim f(e)
+
g(E)
This is standard tool to analyze asymptotic behavior. Proposition A.32. For a fixed, 8 and k we have
2k(k 1) +
2 ln
4
2k(k 1)
In +
x² 2(1+ev2)
22
8
Proof. Using L'Hospital's rule one can show lim
log(1+x)
1, hence
In
+
2
2(1+ev2)
lim 6++0
(62)
2(+cv22
Simple limit calculus gives us
2
2(1 2(1+ev2)
lim
(63)
5-+0
g2
6110
1 1+2
Hence, multiplying expressions in
62 and
63 we get:
In
+
lim
2(1+5
=1
(64)
6 +++
32

---

Published as a conference paper at ICLR 2025
Furthermore, by continuity of the function in we have
2k(k
1) 1 + 4
2k(k
1)
lim In c-0++
In
(65)
The claim now follows from
64 and 65
The comparison in Proposition A.3 tells that the dimension q will be of the same order but slightly higher. This is illustrated on Figure
Figure 5: Simulated random projection for k 10, 000, 000, 8 0.05 the upper (red) curve
2
2 ln
represents the graph of e
(minimum value of q for cosine similarity) and the 20+
lower (blue) curve E + that the two curves very close.
In
kat
(minimum value of q for Johnson-LLndensstran Lemma). We can
5
A.V TECHNICAL INEQUALITIES AND CONCENTRATION RESULTS
In this appendix, we placed some technical inequalities we used in other parts of the text, so that they can be verified by the reader.
A. V1 USEFUL CONCENTRATION INEQUALITIES
In this paper we will depend on the results from concentration inequality theory. The approach in this paper adapted based on the book (Boucheron al. 2013). In this subsection we adapted results from Chapter 2 of the book.
Theorem A.33. Let X be random variable such that > 0, e >> O we have
2t2
log Ele
< 2(1 cA)
(66)
for every X 11). Then 2 we have
12
P(X
EX > 1) exp
exp
2( ct)
33

---

Published as a conference paper at ICLR 2025
Proof. Using Markov inequality, for X E ()) we have
P(X- - EX 5) BleX(X-Xx)
od2
S exp
2((1 -cl) -2t)
eddt
Hence,
u2a
P(X - EX > t) - exp
sup AE(0,e-
At
1)
2(1 cA)
Using usual caleulus techniques we get (see Lemma
A.39 for details)
c
sup AE(0,o-1)
At
h
2(1
ct)
c²
where h(s) + VI+ 2s. By Lemma A.37 we have h(s) 2 follows.
x²
for s > 0 and the claim
2(1+s)
The following Corollary explains what happens when c in (66).
Theorem A.34. Let X be random variable such that v >> 0 we have
2ra
log Ble B(eA(XEEX))
(67)
for every X 2 O. for t 2 we have
-t2
P(X -XX-EX3 t) S exp
2v
Proof. Using Markov inequality, for X 2 0 we have
Ble
P(X - EX 1) < ede
S exp
Al
2
v22
12
exp
Xt +
2
2u
20
X211/2 10
11-1/
2
t2
exp
2u
Setting À t/v the claim follows.
Proposition A.35. for a given p > 0 and e >> 0 the inequality
-xp
BleM(-EX)] S (1 - c\)p/e
(68)
holds for all X < c,,, then the following claims hold: (a) For all X E 11,
log Ele E(XX(X- < pc12
(69)
2(1 - cC)
(b) For all X < 0
log (xx-(X) < pC12
(70)
2
Proof. (a) Using the inequality - log(1 - - 2[-=)
3²
for E (0, 1) (see Lemma A.38 (a) we
have:
log Ble ((xx(X) < -Ap P
log(1 c(-
P (olog11 - cd) c²) - p (c\)²
pc12
2(1 ct) 2(1 c\)
34

---

Published as a conference paper at ICLR 2025
(b) Using inequality - log(1 - 5) - I 8² 22 for 0 (see Lemma A.38 (b))
have:
log Rl -XX--XX)] S -Xp App-
P
log(1 11 ct)
c
2 2--log(1 - c\) - -cA) s
p (c1)²
pcd2
2
2
Corollary A.36. for given p 0 and O we have
E AA Ap
log B(c
(71)
(1 c2)p/o
for all X < c., then for all 2 0
12
P(X - EX > 1) & exp
(72)
2(pc ct)
and
-12
P(X EX < -t) < exp
(73)
2pc
Proof. From Proposition A.35 holds.
we know that 669 holds. Now, by Theorem A.33 inequality
72
From Proposition A.35 we know that 77 have
holds. If we substitute À - -À and X
X in 70 we
log Ble [[feA((xxEx)) < pcd2
for X 2 O. Hence, using Theorem A.35 we get (73)
A. V.2 TECHNICAL INEQUALITIES
Lemma A.37. For we have
s²
1+ 11
2(1
Proof. For s > 0 have:
1 v1 1
+ 2s
1+s- 1 2s (1 (1+ VI+
1+84 V1 22
2s
82
1+ vI 2s
1 II 2s
2(1
The last inequality follows from the fact that
+ /1 + 2$ 8 +
Lemma A.38. (a) For E 10, have loog(1 - 8) 2[-55
2²
(b) For s < we have - log(1 8) - 5²
Proof. Not that for f(s) = = loo(1 8) we have (3()) - Hence, in the case
of (a), it follows for E 10
- log((1 3) - f(s) f(0)= [ ft) dt
/" 1 dt < b dt
8² 2(1 s)
td
35

---

Published as a conference paper at ICLR 2025
In the case of (b), for < 0 apply a similar argument:
5(0) = L f'()) dt
loog(1 - s) - [()
--- 1 1-t t
-1
8² 2
di v
db S
ddl =
1-t t
Lemma A.39. For a given t > 0, v > and > 0 the function
2rs
f(A) Xt 2(1 -A)
has a maximum on interval (0, ()) at point Amax = Vot2ic-v
and it equals
evv+2te
1 tc -
to
11122
d²
Proof. When we take the first derivative we get
2n VcA
('()= =1 (1 (1-cA) 2(1 c\)2*
Setting (A( 0 and using the substitution x. (1 (1-ck) get
VC
x ux + t 0.
2
Solving this quadratic equation by we get
1
21
11
+
c
c
Vc
Since the solution needs to be non-negative,
1
1
2f
1
V
2tc
+
VC
c
vc
V
+ 21c
Vu
+
21c
Vo
CVT
C/
Now, when we calculate À from x, we get
VU + 21c VV
Amax
cVU- + 2tc
Note that, Amax is the minimum since f' is a strictly decreasing function on (0, 10. The value of the minimum is
['(max)== = Amax (1-
V
Amax
(1-
V 2
Amax
2
Comaxx
V0 + 2tc -V
Ve + 2tc V
cV 21c
eVT
Vo 2tc Vi
VuVu + 2tc -
t
cVu+ + 2tc
2c
Vo+ 24c Vi
21c + r /VVu 1 + 21c
c/U+ 2tc
2c
(Vo+ 21c
v
VU + 21c V0
C
2c
(Vo + 2tc - VT) 2
2u + 2tc
22 u2 + 2utc
20
20
V
tc
tc
1+
V
1 1+2 2
36

---

Published as a conference paper at ICLR 2025
Lemma A.40. F 10 and p² E [E, 1] we have
(ovi 2 / p²)² -1 Ep²
Proof. It is easy to show that p 2 and 8 2 /², hence
0 0
2 v p² S ppv
(74)
Now, we have:
(0V 1 101-8-2V1-11 2V1- p2)2 + p²
(pvi 2)² +1 p² -pp
Lemma A.41. For 1) we have
4 2 (244)
+
S e
2(1 + +ev2
Proof. Using Lemma A.38 we have
log ([++ [1+21++20
E²
E²
log
1+
2(1 2(1+
2
2(1 + EV2)
27
p
(75)
2
2(1 + EV
2
2(1 +V
Looking at the difference:
8²
8²
<²[(1 + e)2 - (1+ev2)
e²(e(2 - v2) +
2(1 +
2(1 + t)²
2(1+8)((++v))
2(1 + (1+
<²(=(2 - v2)
(2 - /2)[1 + スーvZ!
2(1 + (1++))
2(1 =) (E
<a(2 [2][1+
2(1 e) +v22)
2(1 + 8)²
4(1 e)
e2 2
2 2
2(1 +8V2)
e2
P
Hence, we have 75 <
4
(1+
A.V.3 SPECIAL CASE OF MEAN VALUE THEOREM
Lemma A.42. Let (h)) VITR. then v'(h) (1+121872 Furthermore, we have the following
inequalities:
(a) For 0 S < b we have
b(b) ((a) S (a)(()b -b)0)--). a).
(b) For < 0 < b we have
((b) - ((a)= < --a a.
Proof. Using product rule for derivatives
(h) = (h)'VI + hZ
h h(vI+h bay
VI+ 122
VI+
1+
1 1 h2
1 1+ 112 112
(1+ + 1223/22
h2y3/2'
37

---

Published as a conference paper at ICLR 2025
For b we have
S(" (b(h) dh
/ du= max (b) a).
-bb) - v(aa)
max 2 (5)
sc a.
sEla.b)
It is not hard to sce
(a)
0 0 a <
max he (e(a,))
(1)) = (0) =1
a <<0<b
B RESULTS FOR RP DOT PRODUCT WHEN P =
B.I RP DOT PRODUCT WHEN P =
This section contains analogous results 2. of the main part of the paper. We will show that inner- product similarity for P A will produce especially poor approximations for vertices u E H and Le.
Theorem B.1. Let X ART. Then, the following claims hold: (a) Asymptotic result. For E V
Tew Tev + n
XueXya 2 N BBuv:
(76)
q
(b) Finite-sample result. For E (0, and 8 E (0, 1 log
n(n
then
XxuXX nuvl
E < Vuuulln
(77)
holds with probability at least
5.
Proof. From part (a) Theorem A.6 we can represent Xu+X as sum of q i.i.d random variables and convenient term. From this, we can show asymptotic normality and get concentration results that lead Lemma-type result. These are described in the Proposition A.I
Since X = Au. R.T and X Ag.R' claim (a) follows from (15) and parts (a) and (b) of Lemma 2.2 Since n = k = [[V|] claim (b) follows from part (b) of Proposition A.
Let us fix u E Le and look at the set (. : u E He). We will show that these calculations can severely overvalue (or undervalue) the relevance values (Au. AT, T. u H.) they approximate. This will be a consequence of the two following lemmas.
Lemma B.2. IfU E Le and u E H2, then the standard deviation in 76 is greater than yd i.e.:
RuuRug + n
7d,
(78)
a
Proof. We have t
2n
WEH. 3ogd, +
veL. cd, 2 (7d,)
Lemma B.3. If Le and He, the standard deviation in (76) is greater than its expectation, i.e.:
ny Top + n
Nuv <
(79)
Proof. We have
Buunles 212
yd
Tun-
38

---

Published as a conference paper at ICLR 2025
Under the conditions of Lemma B.3
produce the approximate one oig-si confidence interval
Dow
n
Tuu
n
Nuv
9
9
in which we can expect Xu. X uw to take values with less than 69% probability, based on 76 This means that getting value outside that interval not unlikely. that case, from (79), we know such values will more than double Nuo or be less than O, a poor approximation. On the other hand, if we look at the values (X (XaaXxr X E Le), we can see that the variance in (76) bounded
Nww Rve + n
d + de
w.EELo
S
Phwe 3c² V nww + 3c²
Hence, in this case we can produce the three-sigma interval
where
X. de will take values with more than 99% probability, which is small deviation.
Further, setting the random projection dimension q according to (A.1 ie., q 1+e log
we fulfill the unite-sample result in part (b) of Theorem B.1. However, for large values of Vouuuev (c.f., the denominator 77). we note that the bounds in (77) become looser, thus larger approximation errors ensue. This will happen for vertices E H since Thu 2 du. As simple numerical illustration, assume A {0, 1 such that 7yu d, and nle d.. Let 10-2 du 107
d, = 10 and Tuo 1. Then, (77) yields XurXp E 100, 1 + 100).
The following is technical lemma that we refer to in 2.1 Lemma B.4. (a) For E V and v satisfying
we have
Tuv 7
v Rev
Auullov
(80)
(81)
dy du
dy v day
dudy
V dy Vin
2
I (b) For u E H3 and u E The we have
S
du
V
d.
Proof. For (80). we multiply the inequality 44 with (du) -1 We have de multiplying the last inequality by 2
Rww ydg and
Rus and taking square roots (8I) follows.
Part (b) follows from 778) by multiplying this inequality with (dud,))
B.II INSTABILITY OF RANKING FOR DOT PRODUCT WHEN P P= A
This section is analogous to 3.1 Recall, rel,,> = An. and rel = Ano R. RAT.
The following lemma will help in considerations.
Lemma B.5. If x and are orthogonal vectors in IR",, we have
cos cas x - y)
|
(82)
cos2 4)
Proof. Using (z, y) have
(x, 8)
|
|
cos(x, x - y)
||]||||| || y/l
||0|||
|
+ 11v12
|
2
|0
Now, it is not difficult to show /1 - cos? (x, v)
Hence, 82 follows.
Let = L.. The relevance value will have a bound.
Proposition B.6. For all V have relua Deuu S ydg.
39

---

Published as a conference paper at ICLR 2025
Proof. The result follows from definition of Rue and (4)
For node of low degree, the relevance has to be low. However, this might not be the case for their approximation.
Corollary B.7. For Le and u E H we have rel 2 N (Nvv nonnegalive expectation with the standard deviation greater thun yd
2n and rel will have
Proof. Follows from Theorem B.1 and Lemma B.2
(1 3v
The last result tells us that rel will have values in
)) nvo 1 3/
with
q
more than 99%. This means, for example if 2 100, rel E [1.5,,n, 0c) C Num (1+ 3
can happen with probability P(NV(.,) 1) > 1.5) = 6.7%. For higher this probability will be higher. Roughly, we anticipate that rel rel when relev relgu happens more frequently.
The following result will show that this can happen more often than we want.
Corollary B.8. Let Le and H. be two vertices with no common neighbors, i.e., such that rel.y > 0 and rel.. O. Then, P(rel rel IP (Ta > 1/3) 2 P(T, 1) 15.8%.
Proof. Since P.....T O, we have coa(Pwe. P.. P..)
P. P....
by 82 Hence, Theorem 3.1
Vi-ens?(Pe., P..)
gives us
P
P(rel
rel Tg
/
(83)
Pu.
Further, Peal
Bdpl
vehe
70g
700
EEH? From the last
P V
Tuu
Buu
Thu
d,
inequality, we have (Tg
Po-
V9
(Tg > 7 1/2)
and the claim follows from Finally,
Pa-
from and (2) we note that 2 1.
Similar results would follow if we took two vertices w, v of low degree with many common neighbors and high degree vertex u that has no common neighbors with w and For simpler calculations, took w v.
40


Reviews:
[{"review_id": "YYZgNLi50w", "reviewer": "Reviewer_RUkx", "summary": "The paper focuses on the practice of using random projections (RP) to learn graph embeddings. In particular, they motivate the advantage of using Cosine Similarity over Euclidean Distance (which is widely popular), grounded in theoretical evidence. The authors show that a nodes with low/high degree enjoy weaker guarantees under Euclidean-based RP. They further extend their scope to the ranking context, where they build upon the general setting results and conclude that Cosine Similarity-based RP yield more robust rankings.", "questions": "1. Can the authors clarify, in simple terms, what difference between the Euclidean and Cosine dissimilarity led to one generating substantially poorer guarantees for high-degree nodes --- based on the theorems? \n\n2. What is the approximate three-sigma interval, and how is it relevant? I see that the \"interval endpoints do not depend on the node degrees\" in the cosine case, but it is unclear to me the relationship between this interval and the projected features/learned embeddings. I think it will be helpful to not only highlight this distinction (as the authors have by italicizing), but also motivate it in the broader context clearly.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper studies an important and (much to the author's credits) well-motivated problem: random projection (RP) for dimensionality reduction on large-scale graph representation learning. Given the prevalence of RP and JL Lemma under many graph representation learning methods today, I believe their analysis on a fundamental design choice (Euclidean vs. Cosine Similarity) will be of great influence to the community. In particular, the theoretical question of how node degree affects graph representation learning is one with clear motivation --- given the influence highly-connected nodes have in many real-world applications. As such, I believe both their theoretical results and techniques will be of interest to the community broadly. Overall, the paper is very clearly written and the narrative is centered.", "weaknesses": "For Figure 1, it may be helpful to the audience if the axis and legends are accompanied by a text description as opposed to just the (paper-defined) mathematical notations. For example, it would help clarity if the blue dots are clearly labeled \"Cosine\" and the y-axis states \"node degree\".\n\nIn the theoretical sections, the presentation of the theorems and their accompanied analysis is helpful for interpreting the theorems. However, I felt that the contrast between results in Section 2.1 and 2.2 can be made stronger (or a subsection itself). See Q2 in the questions section for an example. \n\nFor the experimental section, I feel that including simple experiments independent of the ranking application can better support the theoretical analysis in Section 2. For example, would it be possible to design a simple example (synthetic network) where the two different RPs generate substantially different results for a high-degree node? This could also be in the form of a written example.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YMbiujdVMh", "reviewer": "Reviewer_Nudr", "summary": "This paper investigates how well dot product and cosine similarity are preserved by random projections when these are applied over the rows of the graph matrix, concluding that the variance of the dot product estimation is worse than cosine similarity estimation.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Each mathematical description is carefully written. \n2. The specific theoretical results, Theorems 2.2 and 2.5 are novel, as far as I know. They successfully associate the variance in estimating relevance (dot product or cosine similarity) with the graph structure.", "weaknesses": "1. Johnson-Lindenstrauss Lemma is roughly stated in Line 118 without the reference for proof, but not formally introduced as a Theorem. As there are some variants in the statement, it is essential to specify which form to consider with specific reference with proof.\n2. The further discussion associating JL Lemma and Theorem 2.2. would be preferable. What aspects of JL Lemma previous researchers have tended to miss and what aspects of the problem setting lead to a higher variance in estimation? Would it not be possible to give an intuitive explanation so readers can understand it without reading the proof of Theorem 2.2?\n3. While each theorem in this paper is interesting, the direction of the whole discussion is not justified by those theorems.\nSpecifically, in Conclusion section, the Authors states that \"we propose that practitioners of random projection methods first use the embeddings $u \\\\mapsto \\\\frac{X\\_{u*}}{\\\\|X\\_{u*}\\\\|}$.\" However, easiness in estimating an index (in this case, a similarity measure) does not directly mean we can recommend it. Rather, such a measure is problem-dependent. We cannot choose a similarity measure arbitrarily even if we know one is easy to estimate than another. For example, if we set $\\\\mathrm{rel}\\_{uv} = 1$, which is a constant function, then we can trivially estimate it from any random projection (we can ignore the projection and simply always output 1). Nevertheless, this relevance measure would not be useful in real applications. If we propose to use cosine similarity, we need to discuss its meaning from a graph perspective, also.\n4. Related to the above, the Authors should have discussed the difficulty of the estimation problem itself. The reason why a trivial algorithm can estimate the above trivial similarity measure $\\\\mathrm{rel}\\_{uv} = 1$ is that the similarity measure estimation problem itself is easy as the variance of the true similarity $\\\\mathrm{rel}\\_{uv}$ is zero (here, variance is defined when we sample $u$ and $v$ randomly), not that the trivial algorithm is excellent. Likewise, the Authors should have discussed the difference between the difficulties in the dot product similarity and cosine similarity. In this sense, Proposition 3.2 and 3.6 are partially helpful but not sufficient, as $\\\\mathrm{rel}\\_{uv} = 10000$ is still an easy problem, while the upper bound of the value is large. One could evaluate the variance of $\\\\mathrm{rel}\\_{uv}$ for both the dot-product case and cosine case, showing its dependency on the graph structure. If the problem difficulties are almost the same but the estimation performance through the random projection is much worse for dot-product than for cosine similarity, it is worth alerting. However, if the variance of $\\\\mathrm{rel}\\_{uv}$ is higher for dot-product case, which means that the estimation problem itself is more difficult, then your comparison between Theorems 2.2 and 2.5 may not be practically meaningful.\n\n----\n**After the discussion period**:\nThe concern on Weakness 4 has not been solved as the specific distribution of cosine similarity and dot product has not been given. However, the concern on Weakness 3 has been solved by the Authors' agreeing to revise the conclusion. Even if the Weakness 4 remains, as long as the conclusion is not in the wrong direction, the current paper is meaningful as an analysis of random projection performance from a cosine similarity perspective and dot product similarity perspective. The analyses themselves are beneficial to the community. I have raised the score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Tuy3B8qChg", "reviewer": "Reviewer_LuRP", "summary": "In this paper, the authors investigate random projections (RP) for graph matrices, specifically adjacency and transition matrices, to produce 'low-dimensional' node embeddings. They derive both asymptotic and finite-sample results in the spirit of the Johnson-Lindenstrauss (JL) lemma, assessing the distortion of two node similarity measures—dot products and cosine similarities—under Gaussian random projections. The authors demonstrate that RP can significantly distort dot product similarity, with the extent depending on the degrees of the nodes involved. In contrast, cosine similarity proves more robust, exhibiting less distortion under RP. They apply these findings to a ranking problem, theoretically establishing that normalized discounted cumulative gain (NDCG) is more stable when cosine similarity is used as the similarity measure compared to dot product similarity. Finally, the authors provide numerical evidence supporting their theoretical claims using a real-world dataset.", "questions": "1. The notation $ X_{u*}$ for the rows of a matrix is not explained prior to its use on line 115. It would help to define this notation when it first appears.\n\n2.  On line 108, the authors suggest that computing $p(A)R^\\top $ is faster than $p(A)$ alone. Could the authors clarify why this is the case?\n\n3. It may improve clarity to introduce the power law either before or immediately following line 155.\n\n4.  In line 281, the authors state that the interval endpoints are independent of the node degrees. Is this statement exact, or is it an approximation? Additional clarification would be beneficial here.\n\n5. Proposition 2.6 seems straightforward. Is it necessary to present it formally as a proposition?\n\n6.  For the ranking application, a more detailed explanation of the overarching goal would be helpful. Also, citations for the Normalized Discounted Cumulative Gain (NDCG) metric would add valuable context.\n\n7. The definition of  $\\text{rank}^R_w(h)$ is missing, and notation in this section could be streamlined to be consistent with the rest of the paper. For example, $NDCG(r^K_i, \\hat{r}^K_i)$ is not defined.\n\n8. There are some citation formatting issues in the appendix, such as on line 1079, where several references are improperly displayed.\n\n9. It would be helpful to more clearly indicate which results in the appendix are novel contributions.\n\n10. You establish a comparision with the results about cosine similarity of (Arpit et al. 2014) in section A.IV.5, but this not mentioned in the related work section. Indeed, the related work section, it could be mentioned which of the cited articles, and how, can be compared with the results here. For instance, you compare in Section A.III.5 the concentration results for $\\frac{\\langle Rx,Ry\\rangle}{\\|x\\|\\|y\\|}$ with the  resullts in (Vempala, 2004) and (Kaban, 2015).\n\n11-Could you please address the point I raised in the weaknesses section?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strengths, in my opinion, are:\n\n1. **Relevance**: Node embedding is highly relevant within graph machine learning and representation learning, and RP offer a promising approach to obtaining these embeddings. The study focuses on well-established similarity measures widely used in practice, and the application to ranking is equally pertinent.\n\n2. **Rigorous Mathematical Treatment**: The paper is technically sound, with proofs that appear correct and rigorous.\n\n3. **Clear Presentation**: The paper is well-written and easy to follow, aside from a few issues outlined below.", "weaknesses": "1- **Claims of Novelty and Improvements upon Known Results**: To clarify, I do consider the paper to make a valid contribution with its theoretical analysis of random projections (RP) for node embeddings and the resulting distortions in well-known similarity measures. However, it is sometimes challenging to determine which results the authors claim as novel. It would be helpful if the authors clearly delineate what they consider to be novel contributions versus extensions or refinements of existing work. For instance, in the introduction, Section 2, and the appendix, the authors appear to suggest that their rotation argument—which follows directly from well-known properties of Gaussian distributions—constitutes a novel contribution. They state that \"we use the rotation argument to provide a new representation for the dot product and cosine similarity under random projections.\" However, if I understand correctly, the dot product representation could be derived using the distribution of the off-diagonal entries of a Wishart matrix, with a correlation coefficient corresponding to their parameter $\\rho$. \n\nThe inclusion of detailed proofs in the appendix is appreciated for self-containment, but much of the content presented there either derives from well-established results or can be directly obtained through known concentration or asymptotic arguments. If my interpretation is accurate, the paper’s genuine technical novelty lies in the more refined bounding of relevant quantities following classical concentration or asymptotic approaches. This does sometimes lead to improved results, but in certain sections, such as Section A.III.5, the enhancements seem only marginal.\n\n2- **Difficulty to extend to other sparse RP settings**: The arguments presented here, based on rotation symmetries of the multivariate Gaussian distributions, seem difficult to adapt to the more practically relevant case of spare RP.  In my view, it would be beneficial to discuss the potential challenges and limitations of extending their approach to sparse random projections, or discussing avenues for future work in the conclusion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9C8I5Wgwud", "reviewer": "Reviewer_qkog", "summary": "The paper examines the problem of embedding an adjacency/transition matrix using random projection through the lens of preserving dot product and cosine similarity. The paper provide both asymptotic and finite sample results that compares the two, and furthermore investigates this problem in a ranking configuration.", "questions": "A. As the authors wrote, random projection has guarantees with respect to the Euclidean distance preservation (Based on the JL lemma). I wonder how well would the regular random projection perform (in terms of dot product preservation) if the rows of the adjacency/translation matrix would have been normalized (using the L2 norm) before the projection. If space permits, I would suggest the authors to add a brief discussion or even analysis of this case. This could provide valuable context on the robustness of the findings \nand a more comprehensive comparison of approaches.\n\n\nB. The assumption that the adjacency matrix is composed of only integers numbers should appear at the beginning of section 2. Currently it first appears in the proof of Lemma 2.1 in line 138. I recommend to add a clear statement about the integer assumption for the adjacency matrix in the opening paragraph or definitions of Section 2. Also, I would suggest to note or even briefly discuss the implications of this assumption, given that adjacency matrices in some applications may be continuous.\n\n\nC. The definition of  rank_w^R(h) that was used in line 315 is missing. I suggest to add a brief definition of it where it is first introduced, perhaps with a simple example to illustrate its meaning in the context of the ranking application.\n\n\nInsights: The adjacency matrix configuration that you analyzed can be applied to problems in Natural Language Processing.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides an interesting analysis supported by theorems alongside their interpretations that make the results more clear. \n2. The ranking application is interesting, and is supported by proofs as well.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hfuYBh5Es9", "reviewer": "Reviewer_YfdX", "summary": "In this paper, the authors investigate low dimensional embeddings of graphs via random projections, and in particular investigate dot product/cosine similarity preservation under such a setting, and apply it to a ranking application. The main contributions of this paper are theoretically motivated, as the authors attempt to show that under a natural definition of relevance, the cosine similarity will have better approximation properties under random projections than the dot product, and better stability in the case of ranking.", "questions": "See comments above.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "originality: the paper produces some original results theoretically on the analysis of dot product vs cosine similarity in the random projection setting for graphs. This line of investigation is original, to the best of my knowledge. \nquality:  I discuss the quality of this paper in the next section. Overall, I believe the mathematical derivations concluded in this paper are sound, but the quality of the exposition, motivation, and logical flow has much room for improvement. \nclarity: Overall, clarity is not a strength of this paper. However, The first two pages introducing the paper and the contributions are written clearly. \nsignificance: The broader topic of analyzing graph embeddings is certainly a significant direction of investigation. The application of ranking is also a significant avenue.", "weaknesses": "I raise questions and remarks along several front： \n\n1. Motivation: The the elephant in the room when considering the paper's line of investigation in terms of motivation and significance is this: is if higher order connectivity of graphs is a main motivation, what is the advantage of considering random projections versus spectral embedding approaches (It is clear that the eigendecomposition based approaches capture connectivity and matrix powers very well from spectral graph theory). I understand that this is a theory paper and I do not expect experiments comparing the two, but some sort of high level explanation/discussion seems warranted to convince the reader that it is worth the effort to develop theory for random projections.\n\nThere are many details that the authors do not provide sufficient motivation for. For example, Also, on the top of page 4, q = O(log n) is set to explain large graphs' johnson lindenstrauss type results, which is natural given the well known log scaling of random projection techniques. However, in the same page in theorem 2.2a, the asymptotic results are considered under a root q scaling. I understand that this is what makes the normal approximation machinery goes through, but there seems to be a disconnect between the motivation of this research and some of the asymptotic results provided.  \n\nMinor point: -  the introduction of the NDCG metric was without citation/reference/background motivation in page 6. I suggest adding motivation. \n\n2. The mathematical results are not presented in a very organized/clear way. \n\nIn the statement of the theorems, e.g. theorem 2.2, there is little indication of what setting the theorem corresponds to. In theorem 2.2a, the term \"large q\" is used in this asymptotic result, presumably indicating q is being sent to infinity, but the term q also appears on the variance term on the right hand side...one has to look at the remark below to see that this is explained by the somewhat nonstandard notation \\sim_a to indicate a root q scaling.  Results like these could be stated a lot more clearly. I highly suggest the authors expand the statements in the theorem to state exactly the definitions/constructions used in the setting and the regularity/structural assumptions that they are referring to for clarity. \n\nI say this NOT to indicate that the mathematical derivation is wrong (even though I did not check proofs in appendix line by line, the mathematical results here overall look ok to me), but to indicate that the lack of clarity in the write up and the statements of the theorems make it very difficult for readers to properly check the math and keep track of the exact setting/assumptions that the particular theorems are referring to. Connecting the theoretical results, to the recommendations in the discussion section, becomes even harder given the somewhat disorganized nature of the presentation. \n\n3. The organization of the paper can be improved: \n- the subsection titles are not well organized. Section 2.1 is RP DOT PRODUCT WHEN P = T, and seeing this one naturally expects 2.2 to be P = A, but turns out that is delegated to the appendix, and 2.2 goes to cosine similarity where P = A and T are both considered since they don't make a difference. I suggest making 2.1 heading just RP dot product, and then consider the subcases P = T etc within the section rather than on the title. Ditto for the stability subsection titles in section 3. \n\nGiven the above, my belief is that the paper can be substantially improved in the presentation, clarity and organization front.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)