Node Similarities under Random Projections: Limits and Pathological Cases

## Abstract

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.

## 1 Introduction

*Random projections* (RP) provide a simple and elegant approach to dimensionality reduction []. Leveraging concentration of measure phenomena in high-dimensional statistics [], RP’s rely on the well-known Johnson-Lindenstrauss (JL) lemma [, ] to provide data-independent guarantees for approximation quality. As originally developed, the JL lemma showed that Euclidean distances between any two points in a dataset are 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 to grow only with the logarithm of the ambient dimension of the dataset. As such, the JL lemma has found wide application in diverse fields such as information retrieval [, ],
machine learning [, , , , ],
privacy [, ], and
numerical linear algebra [, ].

*In the context of graphs*, the JL lemma can be applied to generate low-dimensional encodings of a node’s connectivity to other nodes in the graph. In that case, nodes are usually represented as vectors extracted as the rows of a connectivity matrix [], 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 []. Likewise, the transition matrix can be used to compute the corresponding random-walk probability between any pair of nodes []. This notion is key to algorithms such as PageRank [], which computes the steady-state 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-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 []. 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 [] and further developed in [], 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-expensive) 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:

1. 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 JL Lemma in terms of the graph’s degree distribution, we show that it becomes data dependent for dot product, yielding 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 row-normalized).

2. We provide extensive analyses of node embedding approximation quality under cosine similarity. By crafting a rotation argument followed by a Gram-Schmidt orthogonalization procedure, we 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 embeddings, and show that cosine similarity produces remarkably more stable rankings. These findings are shown to 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 (e.g., based on Rademacher random variables) [, , ]. Other works have been dedicated to obtaining tighter bounds for the preservation of Euclidean distance [, ]. In the case of the dot product as a similarity metric, work in  [] obtained general guarantees with depending on the angle between the vectors. Other similar studies have focused on the preservation of margin for as a quantity of interest in the formulation of support vector machines []. Additional contributions have been achieved in the analysis of clustering [, , ].

## 2 Random Projections in Graphs

**Table 1: Notation and symbols used throughout the paper**
| $n$<br>number of nodes<br>$G$<br>graph with $V$ and $E$<br>the sets of nodes and edges<br>$A,\,T$<br>adjacency matrix, transition matrix<br>$P$<br>matrix polynomial $p(A)$ or $p(T)$<br>$d_{u}$<br>degree of node $u$<br>$n_{uv}$<br>connectivity between nodes $u$ and $v$ | $c,\gamma$<br>low and high degree parameters<br>$L_{c}$<br>set of low degree nodes wrt. $c$<br>$H_{c}^{\gamma}$<br>set of high degree nodes wrt. $c$ and $\gamma$<br>$q$<br>random projection dimension<br>$R$<br>random projection matrix<br>$X$<br>node embedding matrix<br>$\mathcal{T}_{q}$<br>$t$-distribution with parameter $q$ |
| --- | --- |

In the case of large graphs $G=(V,E)$, random projections have been applied to polynomials of the adjacency matrix $A$ and transition matrix $T$. If $R=[R_{ij}]\in\mathbb{R}^{q\times n}$, $q\ll n$, is a random matrix generated in a specific way, then $X=p(A)R^{\top}$ or $X=p(T)R^{\top}$ preserves many of the properties $p(A)$ and $p(T)$ for a matrix polynomial $p(X)=\sum_{j=1}^{l}\alpha_{j}X^{j}$. In our paper, we construct $R$ by sampling $(R_{ij}:i=1,\ldots,n,j=1,\ldots,d)$ as i.i.d. normal random variables with mean zero and variance $1/q$. The sequence of row vectors $p_{1},\ldots,p_{k}$ in $\mathbb{R}^{1\times n}$ is then mapped to row-vectors $p_{1}R^{\top},\ldots,p_{k}R^{\top}$ in $\mathbb{R}^{1\times q}$.
An additional benefit is that $p(A)R^{\top}$ and $p(T)R^{\top}$ can be calculated faster than $p(A)$ and $p(T)$. This becomes even more useful in the case of heterogeneous graphs, where we have polynomials of several variables associated with the so-called metapaths [].

For $P=p(A)$ or $P=p(T)$ and $u,v\in V$, the interpretation is that $\mathrm{rel}_{uv}:=P_{v*}P_{u*}^{\top}$ is the relevance between $u$ and $v$ and

$$ $\mathrm{rel}^{R}_{uv}:=X_{v*}X_{u*}^{\top}\approx P_{v*}P_{u*}^{\top}.$ (1) $$

When (1) holds, a vertex $v$ in the graph can be effectively represented by the embedding $X_{v*}$. In the finite-sample regime, this approximation is generally justified by the JL Lemma, which states that for a small $\varepsilon>0$ and for $q$ above a specific value we have $\|p_{j}R^{\top}-p_{i}R^{\top}\|^{2}\in[(1-\varepsilon)\|p_{j}-p_{i}\|^{2},(1+
\varepsilon)\|p_{j}-p_{i}\|^{2}]$ for all $i<j$ with high probability.

Due to the randomness of $R$, we will show that for the large sparse graph the assumption (1) will fail in two important cases:

*(i)* $P=A$: for a low-degree node $v$, $X_{v*}X_{u*}$ will overvalue $P_{v*}P_{u*}^{\top}$ for many high-degree nodes $u$;

*(ii)* $P=T$: for a high-degree node $u$, $X_{v*}X_{u*}$ will overvalue $P_{u*}P_{v*}^{\top}$ for many low-degree nodes $v$.

In contrast, we will show that $\frac{X_{v*}X_{u*}^{\top}}{\|X_{v*}\|\|X_{u*}\|}\approx\frac{P_{v*}P_{u*}^{
\top}}{\|P_{v*}\|\|P_{u*}\|}$
holds more consistently. This is why we propose to use $\frac{X_{v*}}{\|X_{v*}\|}$ as the embedding for a vertex $v$. We call this method *RP Cosine Similarity*.

To develop our specific results, we begin by denoting, for all $u,v\in V$,
$d_{u}:=\sum_{w\in V}A_{uw}$ as the *degree* of the vertex $u$. Likewise, we define
$n_{uv}:=A_{u*}A_{v*}^{\top}$ 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 $n_{uv}$.

###### Lemma 2.1 .

For all $u,v\in V$ we have

$$ $d_{u}\leq n_{uu}\leq d_{u}^{2};$ (2) $$

$$ $\frac{n_{uv}}{d_{u}d_{v}}=T_{u*}T_{v*}^{\top}.$ (3) $$

###### Proof.

Since all entries of the matrix $A$ are nonnegative integers:
$n_{uu}=\sum_{w\in V}A_{uw}^{2}\geq\sum_{w\in V}A_{uw}=d_{u}$. On the other hand, $d_{u}^{2}=(\sum_{w\in V}A_{uw})^{2}\geq\sum_{w\in V}A_{uw}^{2}=A_{u*}A_{u*}^{
\top}=n_{uu}$.
Note, $T_{u*}=\frac{1}{d_{u}}A_{u*}$ for all $u\in V$. Hence, $T_{u*}T_{v*}^{\top}=\frac{A_{u*}A_{v*}^{\top}}{d_{u}d_{v}}=\frac{n_{uv}}{d_{u}
d_{v}}$. This shows (2) and (3).
∎

Further, we note that $d_{u}$ has a linear dependence on the entries of $A$, while $n_{u,v}$ has a quadratic one. Thus, in order to relate $d_{u}$ to $n_{uv}$, we define the following graph-wide property:

$$ $\gamma:=\max_{u,v\in V}\frac{n_{uv}}{d_{v}}.$ (4) $$

This property enables our results to generalize to weighted adjacency matrices $A\in(\mathbb{Z}^{+}_{0})^{n\times n}$. In general, from (2), we have $1{\leq}\gamma\leq\max_{u,v\in V}A_{uv}$. In particular, if $A\in\{0,1\}^{n\times n}$, then $\gamma=1$.

Next, we will define what does it mean for the node to be of *high* or *low* degree in the context of this paper. Let

$$ $L_{c}:=\{v\in V:d_{v}\leq c\}.$ (5) $$

This will be called the set of nodes of low degree. In particular, for a graph following a power law distribution, $L_{c}$ will contain the majority of the nodes. Conversely, let

$$ $H^{\gamma}_{c}:=\{u\in V\,:\,d_{u}\geq\gamma^{2}cq\}.$ (6) $$

We will call this the set nodes of high degree. We are interested analysing graphs where $n=|V|$ is large using Johnson-Lindenstrauss type of results. For that, we consider $q=\mathcal{O}(\log n)$. Under the assumption of the power law distribution, we have $\frac{|H^{\gamma}_{c}|}{n}\sim C[\log n]^{-\alpha}$ for some $\alpha>0$. Hence, for large $n$, the set $H^{\gamma}_{c}$ should have a number of nodes on the order of $\mathcal{O}(n[\log n]^{-\alpha})$.

###### Lemma 2.1 .

###### Proof.

### 2.1 RP Dot Product when P = T 𝑃 𝑇 P=T italic_P = italic_T

To avoid numerical instability issues associated with higher degree nodes and higher powers of $A$, practitioners often consider the transition matrix $T$, since it consists of a bounded, row-stochastic normalization of $A$. We will show that even in this case, random projections may yield especially poor approximations for nodes $u\in H^{\gamma}_{c}$ and $v\in L_{c}$.

###### Theorem 2.2 .

Let $X=TR^{\top}$. The following statements hold:
(a) Asymptotic result. For $u,v\in V$ and large $q$

$$ $X_{u*}X_{v*}^{\top}\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left(\frac{n _{uv}}{d_{u}d_{v}},\frac{1}{q}\left[\frac{n_{uu}n_{vv}}{d_{u}^{2}d_{v}^{2}}+ \left(\frac{n_{uv}}{d_{u}d_{v}}\right)^{2}\right]\right),$ (7) $$

(b) Finite sample result. For $\varepsilon\in(0,1)$ and $\delta\in(0,1)$, if $q\geq 4\frac{1+\varepsilon}{\varepsilon^{2}}\log\left[\frac{n(n-1)}{\delta}\right]$,
then

$$ $|X_{u*}X_{v*}^{\top}-\frac{n_{uv}}{d_{u}d_{v}}|<\varepsilon\frac{\sqrt{n_{uu}n _{vv}}}{d_{u}d_{v}}$ (8) $$

for all $u,v\in V$ holds with probability at least $1-\delta$.

*Remark*.
We denote by $Y_{q}\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}(\mu,\frac{\sigma^{2}}{q})$ the fact that $\frac{Y_{q}-\mu}{\sigma}\sqrt{q}\stackrel{{\scriptstyle d}}{{\to}}\mathcal{N}(
0,1)$ as $q\to\infty$. The "$\stackrel{{\scriptstyle a}}{{\sim}}$" is interpreted as meaning an approximate distribution for large $q$.

###### Proof.

Using the rotation argument from §A.II, we represent $X_{u*}X_{v*}^{\top}$ as sum of $q$ i.i.d random variables and a convenient term. This is stated in part (a) of Theorem A.6 in the Appendix.

Using the Central Limit Theorem and Law of Large Numbers, we get the following asymptotic result: $T_{u}R^{\top}RT_{v}^{\top}\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}(T_{u}
T_{v}^{\top},(T_{u}T_{v}^{\top})^{2}/q+\|T_{u}\|^{2}\|T_{v}\|^{2}/q)$. For details, see part (a) of Proposition A.1 in the Appendix. Applying (3) we have $T_{u}T_{v}^{\top}=\frac{n_{uv}}{d_{u}d_{v}}$, $\|T_{v}\|^{2}=T_{v}T_{v}^{\top}=\frac{n_{vv}}{d_{v}^{2}}$ and $\|T_{u}\|^{2}=T_{u}T_{u}^{\top}=\frac{n_{uu}}{d_{u}^{2}}$ and part (a) follows.

Using the representation $X_{u*}X_{v*}^{\top}$ mentioned at the beginning of the proof, we can produce concentration results that lead to a JL Lemma-type result in part (b) of Proposition A.1 in the Appendix. From there, we set $n=k=|V|$ and get that $|T_{u}R^{\top}RT_{v}^{\top}-T_{u}T_{v}^{\top}|<\varepsilon\|T_{v}\|\|T_{u}\|$ for all $u,v\in 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).
∎

The rotation argument mentioned above (and fully developed in §A.II), allows us to directly analyze $P_{u*}R^{\top}RP_{v*}^{\top}$. This improves on the typical approach  [, , ] of representing the dot product by the expansion $\frac{1}{4}(\|P_{u*}R^{\top}+P_{v*}R^{\top}\|-\|P_{u*}R^{\top}-P_{v*}R^{\top}\|)$, since these factors are usually not independent. Doing so enables us to produce more precise bounds, as discussed in §A.III.5.

We will fix $u\in H_{c}$ and look at the values $\{X_{u*}X_{v*}^{\top}\,:\,v\in L_{c}\}$ that may misapproximate $\{\frac{n_{uv}}{d_{u}d_{v}}:v\in L_{c}\}$.

###### Corollary 2.3 .

If $v\in L_{c}$ and $u\in H^{\gamma}_{c}$, then the standard deviation in (7) is greater than its expectation, i.e.:

$$ $\frac{n_{uv}}{d_{u}d_{v}}\leq\sqrt{\frac{1}{q}\left[\frac{n_{uu}n_{vv}}{d_{u}^ {2}d_{v}^{2}}+\left(\frac{n_{uv}}{d_{u}d_{v}}\right)^{2}\right]}.$ (9) $$

###### Proof.

We have $\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{
{\geq}}\frac{d_{u}d_{v}+n_{uv}^{2}}{q}\stackrel{{\scriptstyle u\in H_{c}}}{{
\geq}}\frac{\gamma^{2}cqd_{v}+n_{uv}^{2}}{q}\geq\gamma^{2}cd_{v}\stackrel{{
\scriptstyle v\in L_{c}}}{{\geq}}(\gamma d_{v})^{2}\stackrel{{\scriptstyle
\eqref{eq:MConnection}}}{{\geq}}n_{uv}^{2}$. Multiplying the last inequality with $d_{u}^{-2}d_{v}^{-2}$ and taking the square root, (9) follows.
∎

Under the conditions of the Corollary above, when can generate the one-sigma interval

$$ $\left[\frac{n_{uv}}{d_{u}d_{v}}-\sqrt{\frac{1}{q}\left[\frac{n_{uu}n_{vv}}{d_{ u}^{2}d_{v}^{2}}+\left(\frac{n_{uv}}{d_{u}d_{v}}\right)^{2}\right]},\frac{n_{ uv}}{d_{u}d_{v}}+\sqrt{\frac{1}{q}\left[\frac{n_{uu}n_{vv}}{d_{u}^{2}d_{v}^{2} }+\left(\frac{n_{uv}}{d_{u}d_{v}}\right)^{2}\right]}\right]$ $$

in which $(X_{u*}X_{v*}^{\top}\,:\,v\in L_{c})$ will take values with probability of less than $69\%$. This means that getting a value outside that interval is not unlikely. In that case, we know from (9) that such values will either double $\frac{n_{uv}}{d_{u}d_{v}}$ or be less than 0 0, which is clearly a poor approximation.

We now interpret the finite-sample result, and set $q=\lceil(1+\varepsilon)/\varepsilon\log n(n-1)/\delta]\rceil$ such that part (b) of Theorem 2.2 holds. The expression $n_{uv}/(d_{u}d_{v})$ in the numerator of (8) depends on $d_{u}$ with order $(d_{u})^{-1}$, and denominator has a lower-order dependence $(d_{u})^{-\frac{1}{2}}$, as described in Lemma B.4 in the Appendix. Thus, higher values of $d_{u}$ lead to an unfavorable regime in which the guarantees from Theorem 2.2 become increasingly weaker. As a simple numerical illustration, we assume $A\in\{0,1\}^{n\times n}$ so that $n_{uu}=d_{u}$ and $n_{vv}=d_{v}$, and let $\varepsilon=10^{-2}$ , $d_{u}=10^{7}$, $d_{v}=10$ and $n_{uv}=1$. Then, (8) yields $X_{u*}X_{v*}^{\top}\in 10^{-8}(1-100,1+100)$, which is clearly a severely biased estimate.

Similar results hold in the case $P=A$. For this case, we provide analogous asymptotic normality and finite sample results in §B.I of the Appendix. There, we also express similarities in the terms of values of $(n_{uv})$ and $(d_{u})$. In the absence of normalization, the disruption of the assumption $X_{u*}X_{v*}^{\top}\approx P_{u*}P_{v*}^{\top}$ is more obvious.

###### Theorem 2.2 .

###### Proof.

###### Corollary 2.3 .

###### Proof.

### 2.2 RP Cosine Similarity

In this section, we present asymptotic normality and finite-sample analysis to show how RP Cosine Similarity yields significantly better approximations for vertices $u\in H^{\gamma}_{c}$ and $v\in L_{c}$ than those of RP Dot Product (both when $P=T$ and $P=A$). We begin by showing that it will not matter for RP Cosine Similarity if we take $P=A$ or $P=T$.

###### Lemma 2.4 .

For all $u,v\in V$ we have

$$ $\cos(T_{u*}R^{\top},T_{v*}R^{\top})=\cos(A_{u*}R^{\top},A_{v*}R^{\top})\quad \textrm{and}\quad\cos(T_{u*},T_{v*})=\cos(A_{u*},A_{v*})=\frac{n_{uv}}{\sqrt{n _{uu}n_{vv}}}.$ $$

###### Proof.

First equality follows from

$$ $\frac{T_{u*}RR^{\top}T_{v*}^{\top}}{\|T_{u*}R^{\top}\|\|T_{v*}R^{\top}\|}= \frac{(d_{u}^{-1}A_{u*})R^{\top}R(d_{v}^{-1}A_{v*}^{\top})}{\|d_{u}^{-1}A_{u*} R^{\top}\|\|d_{v}^{-1}A_{v*}R^{\top}\|}=\frac{A_{u*}R^{\top}RA_{v*}^{\top}}{\| A_{u*}R\|\|A_{v*}R\|}$ $$

Using parts (a) and (b) of Lemma 2.1 we can calculate that $\cos(A_{u*},A_{v*})=\frac{n_{uv}}{\sqrt{n_{uu}n_{vv}}}$ and $\cos(T_{u*},T_{v*})=\frac{n_{uv}}{\sqrt{n_{uu}n_{vv}}}$.
∎

We will state our main result for this method now.

###### Theorem 2.5 .

For $P\in\{A,T\}$ and $X=PR^{\top}$ the following claims hold:
(a) Asymptotic result. For $u,v\in V$ and large $q$

$$ $\cos(X_{u*},X_{v*})\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left(\frac{n _{uv}}{\sqrt{n_{uu}n_{vv}}},\frac{1}{q}\left(1-\frac{n_{uv}^{2}}{n_{uu}n_{vv}} \right)^{2}\right)$ (10) $$

(b) Finite-sample result. Let $\varepsilon\in(0,0.05]$ and $\delta\in(0,1)$. If
$q\geq\frac{2\ln\left[\frac{2n(n-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{
\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}
\right]}$, then

$$ $\left|\cos(X_{u*},X_{v*})-\frac{n_{uv}}{\sqrt{n_{uu}n_{vv}}}\right|\leq \varepsilon\left(1-\frac{n_{uv}^{2}}{n_{uu}n_{vv}}\right)$ $$

holds for all $u,v\in V$ with probability at least $1-\delta$.

###### Proof.

Using the rotation argument, we can get a very useful representation of $\cos(X_{u*},X_{v*})$ 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_{u*},X_{v*})\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left(\cos(P_
{u*},P_{v*}),\frac{1}{q}\left(1-\cos^{2}(P_{u*},P_{v*})\right)^{2}\right)$. For details, see part (a) of Proposition A.3 in the Appendix. Claim (a) follows from Lemma 2.4.

Using representation mentioned at the beginning, we can get concentration results and a JL Lemma-type result. This is stated part (b) of Proposition A.3 in the Appendix, whence we have $|\cos(X_{u*},X_{v*})-\cos(P_{u*},P_{v*})|<\varepsilon(1-\cos^{2}(P_{u*},P_{v*})$ under the same assumptions and conditions. Claim (b) follows from Lemma 2.4. ∎

Let us compare the asymptotic result for cosine similarity with the previous cases. From (10), we can produce the approximate three-sigma interval

$$ $\left[\cos(P_{u*},P_{v*})-\frac{3}{\sqrt{q}}(1-\cos^{2}(P_{u*},P_{v*})),\right .\left.\cos(P_{u*},P_{v*})+\frac{3}{\sqrt{q}}(1-\cos^{2}(P_{u*},P_{v*}))\right]$ $$

where $\cos(X_{u*},X_{v*})$ is expected to take values with $99\%$ probability. Differently from the previous cases, we see that the interval endpoints *do not depend on the node degrees*. Thus, for a reasonably large $q$, the value of $\cos(P_{u*},P_{v*})$ will be well-approximated. Further, the closer $\cos(P_{u*},P_{v*})$ is to 1, the smaller the standard deviation, and the narrower the confidence interval. The confidence interval is the widest when $\cos(P_{u*},P_{v*})=0$. In that case, it can happen that it takes negative values under random projections, but this is likely not to be lower than $-\frac{3}{\sqrt{q}}$.

With Theorem 2.5, we can state the following additional properties.

###### Proposition 2.6 .

- (a)
$\cos(X_{u*},X_{v*})\in[-1,1]$ for all $u,v\in V$.
- (b)
Almost surely $\cos(X_{u*},X_{v*})=\pm 1$ if and only if $\cos(P_{u*},P_{v*})=\pm 1$.
- (c)
For $\varepsilon\in(0,0.05]$ and $\delta\in(0,1)$, if
$q\geq\frac{2\ln\left[\frac{2n(n-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{
\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}
\right]}$, then
$\cos(X_{u*},X_{v*})\in[\cos(P_{u*},P_{v*})-\varepsilon,\cos(P_{u*},P_{v*})+\varepsilon]$
for all $u,v\in V$ with probability $1-\delta$.

###### Proof.

Part (a) follows by definition of cosine similarity.
Part (b) follows from the Cauchy-Schwarz inequality. The full discussion can be found in the Corollary A.20 in the Appendix.
Part (c) follows from Theorem 2.5 part (b) since
$\displaystyle 0\leq 1-\frac{n_{uv}^{2}}{n_{uu}n_{vv}}=1-\cos^{2}(P_{u*},P_{v*}
)\leq 1$.
∎

Part (b) of Proposition 2.6 tells us that random projection will preserve values of exactly 1. Part (c) Proposition 2.6 provides the desired property of *uniformity* for the absolute error on the difference between the estimate and the true value with respect to node degrees.

###### Lemma 2.4 .

###### Proof.

###### Theorem 2.5 .

###### Proof.

###### Proposition 2.6 .

###### Proof.

## 3 Application to Ranking

Here, we specialize the results presented in Section 2 to a ranking application. Recall that, for polynomials $P=p(A)$ or $P=p(T)$, the interpretation is that for $u,v\in V$ $\mathrm{rel}_{uv}:=P_{v*}P_{u*}^{\top}$.
For computational reasons, we apply the random projection $X=PR^{\top}$ and work with $\mathrm{rel}^{R}_{uv}:=X_{v*}X_{u*}^{\top}$
under the assumption that $\mathrm{rel}_{uv}^{R}\approx\mathrm{rel}_{uv}$.

We will next examine what happens if we fix $w\in V$ and use the approximate relevance $(\mathrm{rel}^{R}_{wh}:h\in V)$ for ranking. We will use the well-known NDCG metric: $\mathrm{NDCG}_{w}@l:=\frac{\mathrm{DCG}^{R}_{w}@l}{\mathrm{DCG}_{w}@l}$ where

$$ $\mathrm{DCG}^{R}_{w}@l:=\sum_{h:\mathrm{rank}_{w}^{R}(h)\leq l}\frac{\mathrm{ rel}_{wh}}{\log(\mathrm{rank}_{w}^{R}(h)+1)}\ \,\textrm{and}\ \,\mathrm{DCG}_{ w}@l:=\sum_{h:\mathrm{rank}_{w}(h)\leq l}\frac{\mathrm{rel}_{wh}}{\log(\mathrm {rank}_{w}(h)+1)}.$ $$

The following Theorem will help us quantify how often can the approximation $\mathrm{rel}^{R}_{wh}$ *flip* the order of relevance between nodes $u$ and $v$ with respect to $w$.

###### Theorem 3.1 .

Let $u,v\in V$ be such that $\mathrm{rel}_{wu}>\mathrm{rel}_{wv}$. Then,

$$ $\mathbb{P}(\mathrm{rel}_{wu}^{R}<\mathrm{rel}_{wv}^{R})=\mathbb{P}\left( \mathcal{T}_{q}>\frac{\cos(P_{w*},P_{u*}-P_{v*})\sqrt{q}}{\sqrt{1-\cos^{2}(P_{ w*},P_{u*}-P_{v*})}}\right)$ (11) $$

where $\mathcal{T}_{q}$ is the $t$-distribution with parameter $q$.

###### Proof.

To have $\mathrm{rel}_{wu}<\mathrm{rel}_{wv}$, we need $P_{w*}(P_{u*}-P_{v*})^{\top}>0$. The right hand side is the probability of this dot product changing the sign under the random projection i.e. $\mathbb{P}(P_{w*}R^{\top}R(P_{u*}-P_{v*})^{\top}<0)$. This is a simple consequence that follows from the representation in part (a) of Theorem A.6, obtained using the rotation argument and then using the definition of the $t$-distribution. For details, see Proposition A.2 in the Appendix.
∎

###### Theorem 3.1 .

###### Proof.

### 3.1 Instability of Ranking for DotProduct when P = T 𝑃 𝑇 P=T italic_P = italic_T

For a given $u\in V$, we provide an upper bound for the set of relevance values $\{\mathrm{rel}_{uv}:v\in V\}$.

###### Proposition 3.2 .

For all $u,v\in V$ we have $\mathrm{rel}_{uv}=\frac{n_{uv}}{d_{u}d_{v}}\leq\frac{\gamma}{d_{u}}$.

###### Proof.

We have $\mathrm{rel}_{uv}=T_{u*}T_{v*}^{\top}\stackrel{{\scriptstyle\eqref{neighbors:
degreeAT}}}{{=}}\frac{n_{uv}}{d_{u}d_{v}}\stackrel{{\scriptstyle\eqref{eq:
MConnection}}}{{\leq}}\frac{\gamma}{d_{u}}$.
∎

Note that the upper bound in Proposition 3.2 can be particularly small for a high degree $d_{u}$. However, the estimate might be larger than that.

###### Corollary 3.3 .

For $u\in H_{c}^{M}$ and $v\in L_{c}$, we have $\mathrm{rel}_{uu}^{R}\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left(\frac
{n_{uu}}{d_{u}^{2}},\frac{2n_{uu}^{2}}{d_{u}^{4}q}\right)$
and that $\mathrm{rel}_{uv}^{R}$ will be asymptotically normal with non-negative expectation and the standard deviation greater than $\frac{\gamma}{d_{u}}$.

###### Proof.

Asymptotic result $\mathrm{rel}_{uu}^{R}\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left(\frac
{n_{uu}}{d_{u}^{2}},\frac{2n_{uu}^{2}}{d_{u}^{4}q}\right)$ follows from Theorem 2.2 part(a), when we take $u=v$.
It can be shown using definitions of $\gamma$ and $c$, under the assumptions that $u\in H_{c}^{\gamma}$ and $v\in L_{c}$, that the variance in (7), and hence the variance of $\mathrm{rel}_{uv}$, is greater than $(\gamma/d_{u})^{2}$. Details can be found in Lemma B.4 (b) in the Appendix.
∎

The last result tells us that $\mathrm{rel}_{uu}^{R}$ will have values in $\left[\frac{n_{uu}}{d_{u}^{2}}\left(1-3\sqrt{\frac{2}{q}}\right),\frac{n_{uu}}
{d_{u}^{2}}\left(1+3\sqrt{\frac{2}{q}}\right)\right]$
with more than 99%. This means, for example if $q\geq 100$, $\mathrm{rel}_{uv}^{R}\in[1.5\frac{\gamma}{d_{u}},\infty)\subset\left[\frac{n_{
uu}}{d_{u}^{2}}\left(1+3\sqrt{\frac{2}{q}}\right),\infty\right)$ can happen with probability $\mathbb{P}(\mathcal{N}(0,1)>1.5)\approx 6.7\%$.

For higher $q$, this probability will be higher. Roughly, we can anticipate that $\mathrm{rel}_{uu}^{R}<\mathrm{rel}_{uv}^{R}$ happens when $\mathrm{rel}_{uu}>\mathrm{rel}_{uv}$ frequently. The following result will show that this can happen more often than one would like.

###### Corollary 3.4 .

Let $u\in H_{c}^{\gamma}$ and $v\in L_{c}$ be two vertices with no common neighbors, i.e., such that $\mathrm{rel}_{uu}>0$ and $\mathrm{rel}_{uv}=0$.
Then $\mathbb{P}(\mathrm{rel}_{uu}^{R}<\mathrm{rel}_{uv}^{R})>\mathbb{P}(\mathcal{T}
_{q}>\gamma^{-1/2})\geq\mathbb{P}(\mathcal{T}_{q}>1)\approx 15.8\%$.

###### Remark 3.5 .

The previous estimate is based on the fact that for $q\geq 30$, in practice, $\mathcal{N}(0,1)$ is taken as an approximation for $\mathcal{T}_{q}$.

###### Proof.

Since $P_{u*}P_{v*}^{\top}=0$, we have $\cos(P_{u*},P_{u*}-P_{v*})=\frac{\|P_{u*}\|}{\sqrt{\|P_{u*}\|^{2}+\|P_{v*}\|^{
2}}}$ and (11) becomes

$$ $\mathbb{P}(\mathrm{rel}_{uu}^{R}<\mathrm{rel}_{uv}^{R})=\mathbb{P}\left( \mathcal{T}_{q}>\frac{\|P_{u*}\|}{\|P_{v*}\|}\sqrt{q}\right).$ (12) $$

Further,

$$ $\displaystyle\frac{\|P_{u*}\|}{\|P_{v*}\|}\sqrt{q}$ $\displaystyle=\frac{\sqrt{n_{uu}/d_{u}^{2}}}{\sqrt{n_{vv}/d_{v}^{2}}}\sqrt{p}= \frac{d_{v}\sqrt{n_{uu}}}{d_{u}\sqrt{n_{vv}}}\sqrt{q}\stackrel{{\scriptstyle \eqref{eq:degreeAT}}}{{\leq}}\frac{d_{v}\sqrt{n_{uu}}}{d_{u}\sqrt{d_{v}}}\sqrt {q}=\frac{\sqrt{d_{v}n_{uu}q}}{d_{u}}\stackrel{{\scriptstyle\eqref{eq: MConnection}}}{{\leq}}\frac{\sqrt{d_{v}\gamma d_{u}q}}{d_{u}}$ $\displaystyle=\sqrt{\frac{d_{v}\gamma q}{d_{u}}}$ $\displaystyle\stackrel{{\scriptstyle v\in L_{c}}}{{\leq}}\sqrt{\frac{\gamma cq }{d_{u}}}\stackrel{{\scriptstyle u\in H_{c}^{\gamma}}}{{\leq}}\frac{1}{\sqrt{ \gamma}}.$ $$

From the last estimate, we have $\mathbb{P}\left(\mathcal{T}_{q}>\frac{\|P_{v*}\|}{\|P_{u*}\|}\sqrt{q}\right)
\geq\mathbb{P}\left(\mathcal{T}_{q}>\gamma^{-1/2}\right)$, and the claim follows from (12) and Remark 3.5. As mentioned in the paragraph after (4), $\gamma\geq 1$.
∎

Similar results would follow if we took two vertices $w,u$ of high degree with many common neighbors and a low degree vertex $v$ that has no common neighbors with $w$ and $u$. For simpler calculations, we took $w=u$.

We provide corresponding results for the case of $P=A$ in §B.II of the Appendix. The only notable 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 B.8) will result in poor ranking for low degree nodes. This is illustrated on Figure 1. Due to the high number of low degree nodes, this phenomenon is easier to notice empirically. Conversely, it is harder to note such a pathology for higher degree nodes, since they are usually scarcer.

###### Proposition 3.2 .

###### Proof.

###### Corollary 3.3 .

###### Proof.

###### Corollary 3.4 .

###### Remark 3.5 .

###### Proof.

### 3.2 Stability of Ranking for Cosine Similarity when P = A 𝑃 𝐴 P=A italic_P = italic_A or P = T 𝑃 𝑇 P=T italic_P = italic_T

In both cases, for the dot product with respect to a given node, when using random projection for relevance estimation, a 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 $\mathrm{rel}_{uv}=\cos(P_{u*},P_{v*})$ and $\mathrm{rel}^{R}_{uv}=\cos(X_{u*},X_{v*})$. From Proposition 2.6, the next result follows.

###### Proposition 3.6 .

For all $u\in V$ $\mathrm{rel}_{uu}=\mathrm{rel}_{uu}^{R}=1$. Further, both the relevance $(\mathrm{rel}_{uv}:u,v\in V)$ and the approximation $(\mathrm{rel}^{R}_{uv}:u,v\in V)$ can be at most $1$.

This gives us a clear interpretation of the relevance: a value of $1$ implies a strong connection between node, and one that is is preserved; a value of 0 0 implies no neighbor overlap.

###### Corollary 3.7 .

For $u,v,w,h\in V$, the following holds.

- (a)
If $r_{uv}=0$, then $\mathrm{rel}_{uu}=1>0=r_{uv}$ and $\mathrm{rel}^{R}_{uu}>\mathrm{rel}^{R}_{uv}$ almost surely.
- (b)
Under the conditions of Proposition 2.6 (c), if $\mathrm{rel}_{uv}-\mathrm{rel}_{wh}>2\varepsilon$, then
$\mathbb{P}(\mathrm{rel}^{R}_{uv}>\mathrm{rel}^{R}_{wh})\geq 1-\delta$.

###### Proof.

(a) From Proposition 3.6 (c), we have $\mathrm{rel}_{uu}=\mathrm{rel}^{R}_{uu}=1$. Since $\mathrm{rel}^{R}_{uv}$ is a continuous random variable, $\mathbb{P}(\mathrm{rel}^{R}_{uv}=1)=0$. Hence,

$$ $1=\mathbb{P}(\mathrm{rel}^{R}_{uv}\leq 1)=\mathbb{P}(\mathrm{rel}^{R}_{uv}<1)+ \mathbb{P}(\mathrm{rel}^{R}_{uv}=1)=\mathbb{P}(\mathrm{rel}^{R}_{uv}<1)+0= \mathbb{P}(\mathrm{rel}^{R}_{uv}<1).$ $$

(b) With probability $1-\delta$, we have $\mathrm{rel}^{R}_{uv}>\mathrm{rel}_{uv}-\varepsilon$ and $\mathrm{rel}_{wh}+\varepsilon>\mathrm{rel}^{R}_{wh}$. Therefore,
$\mathrm{rel}^{R}_{uv}>\mathrm{rel}_{uv}-\varepsilon>(\mathrm{rel}_{wh}+2
\varepsilon)-\varepsilon=\mathrm{rel}_{wh}+\varepsilon>\mathrm{rel}^{R}_{wh}$.
∎

Part (a) of Corollary 3.7 shows that the phenomenon from
Corollary 3.4 does not happen in the case of cosine similarity (see also a similar result for the adjacency matrix $A$ in Corollary B.8 of the Appendix). Part (b) of Corollary 3.7 shows stability, i.e., if two relevance values are not close, their estimate will highly likely keep their order. Part (a) of Theorem 2.5 provides similar asymptotic guarantees for stability.

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=A$ and $P=T$, while it will be stable in case of the cosine similarity.

###### Proposition 3.6 .

###### Corollary 3.7 .

###### Proof.

### 3.3 Computational Experiments

Figure: Figure 1: *Distribution of $\eta_{i}=\mathrm{NDCG}(r_{i}^{K},\hat{r}_{i}^{K})$, $K=10$, versus node degree $d_{i}$*. On the left, we consider *RP Dot Product when $P=T$*, denoted by $\eta_{i}^{T}$. We compare it with *RP Cosine Similarity*, denoted by $\eta_{i}^{C}$. Both scores are computed using the same random projection matrix, with dimension $q=256$. The dotted line marks the lowest value observed for $\eta_{i}^{C}$, of approximately 0.75. It can be seen that $\eta_{i}^{T}$ often takes low values for *higher* degrees (i.e., region below dotted line), especially when $\log_{2}(d_{i})\geq 4$. On the right, we display the equivalent plot for *RP Dot Product when $P=A$*, denoted by $\eta_{i}^{A}$. The NDCG scores often take low values for *lower* degrees, especially when $\log_{2}(d_{i})\leq 6$.
Refer to caption: x1.png

**Table 2: Empirical mean (std) of $\eta_{i}=\mathrm{NDCG}(r_{i}^{K},\hat{r}_{i}^{K})$, $K\in\{1,5,10\}$, and of $\log_{2}(d_{i})$ (last row), for $i\in S_{\mathrm{high}}$ (left) and $i\in S_{\mathrm{low}}$ (right). Bold face denotes lower mean values in set.**
| K | $\eta_{i}^{T}$, $i\in S_{\mathrm{high}}$ | $\eta_{i}^{A}$, $i\in S_{\mathrm{high}}$ | $\eta_{i}^{C}$, $i\in S_{\mathrm{high}}$ | $\eta_{i}^{T}$, $i\in S_{\mathrm{low}}$ | $\eta_{i}^{A}$, $i\in S_{\mathrm{low}}$ | $\eta_{i}^{C}$, $i\in S_{\mathrm{low}}$ |
| --- | --- | --- | --- | --- | --- | --- |
| 2 | \B0.589 (0.426) | 0.954 (0.061) | 0.964 (0.025) | 1.000 (0.003) | \B0.057 (0.200) | 0.999 (0.008) |
| 5 | \B0.607 (0.344) | 0.920 (0.072) | 0.924 (0.047) | 0.999 (0.004) | \B0.168 (0.250) | 0.999 (0.010) |
| 10 | \B0.602 (0.315) | 0.899 (0.078) | 0.895 (0.063) | 0.999 (0.004) | \B0.327 (0.188) | 0.999 (0.010) |
|  | $\log_{2}(d_{i})$, $i\in S_{\mathrm{high}}$:<br>5.274 (1.103) | $\log_{2}(d_{i})$, $i\in S_{\mathrm{low}}$:<br>0.260 (0.439) |  |  |  |  |

We illustrate the results developed in the previous section for a ranking application over a real graph. To that end, we consider the Gleich/wikipedia-20060925 dataset(^1^11 https://www.cise.ufl.edu/research/sparse/matrices/Gleich/wikipedia-20060925.html) from the University of Florida Sparse Matrix Collection []. The dataset consists of a web crawling extraction of Wikipedia with $2,983,494$ web pages and $37,269,096$ web links. We define $A(i,j)=1$ if page $i$ links to or is linked by page $j$, and 0 0 otherwise.

We wish to evaluate the effect of $R$ on the ranking of nodes induced by their connectivity through common neighbors. The original relevance between nodes $u$ and $v$, denoted $\mathrm{rel}_{uv}$, is computed as a function of vectors $P_{u},P_{v}\in\mathbb{R}^{n}$ obtained from their respective rows of $A$ (or $T$). We denote the approximated relevance obtained through $R$ as $\mathrm{rel}^{R}_{uv}$, and consider the three variants of similarity discussed in this paper: *($T$)* RP Dot Product when $P=T$, *(A)* RP Dot Product when $P=A$, and *(C)* RP Cosine Similarity.

To compare the rankings induced the original and approximated relevances, we proceed as follows. For a node $i$, we define a ranking vector $r_{i}^{K}:=[\mathrm{rel}_{i,(\ell)}:\ell=1,\ldots,K]$, where the parenthesized index $\ell$ denotes the $\ell$-th largest element according to the relative order induced by the relevances. Likewise, we set
$\hat{r}_{i}^{K}:=[\mathrm{rel}^{R}_{i,(\ell)}:\ell=1,\ldots,K]$ to consider the ranking from the approximated relevances.
Then, we compare $r_{i}^{K}$ with $\hat{r}_{i}^{K}$ by computing their normalized discounted cumulative gain at $K=10$, which we define as $\eta_{i}:=\mathrm{NDCG}(r_{i}^{K},\hat{r}_{i}^{K})$.

Because the number of possible pairwise node combinations is large, we evaluate a representative sample of the nodes using a stratified sampling strategy. To assure a meaningful mixture of node degrees, we split the set of nodes into three segments of size $L=1\times 10^{6}$ (low, medium, and high) based on their ordered degrees. Then, we select nodes into three subsets by sampling $m=300$ out of $L$ nodes without replacement from each of these segments, and take $\mathcal{S}$ = $\mathcal{S}_{\mathrm{low}}\cup\mathcal{S}_{\mathrm{med}}\cup\mathcal{S}_{
\mathrm{high}}$ as our evaluation sample. Finally, for each node $i$ in $S$ (and with respect to every other node $j$ in $S$), we compute $\eta_{i}^{T}$, $\eta_{i}^{A}$, and $\eta_{i}^{C}$ considering the types of similarity *(T, A, C)* defined previously.

With the previous definitions, we can compute the empirical distributions of $\eta_{i}$ over the node degrees $d_{i}$ for the three variants of similarity considered, with $q=256$ for the random projection dimension.
In Figure 1 (left), we compare RP Dot Product when $P=T$ with RP Cosine Similarity. As expected (c.f., §3.1), we can see a strong disruption of NDCG when the degrees are *high*. Correspondingly, in Figure 1 (right), we display the corresponding comparison for RP Dot Product when $P=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 is 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 $S_{\mathrm{high}}$ (left) and $\mathcal{S}_{\mathrm{low}}$ (right), for $K\in\{1,5,10\}$.

## 4 Conclusion

Based on the discussion in §2.2 and the numerical results presented in this paper, we propose that practitioners of random projection methods first use the embeddings $u\mapsto X_{u*}/\|X_{u*}\|$, in which case cosine similarity will be well preserved under the random projection both when $X=AR^{\top}$ and when $X=TR^{\top}$.
If the practitioners do not have a need for embeddings of high degree nodes (or those might not exist), they can use the embeddings $u\mapsto X_{u*}$ where $X=TR^{\top}$. The dot product for the lower degree nodes will be well preserved as shown in §2.1.
Use of $u\mapsto X_{u*}$ where $X=AR^{\top}$ is discouraged, since it very difficult to control the possible error as we shown in §B.I.

## 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 to 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 of Washington in Seattle during the work on this paper.

## Appendix A Dot Product and Cosine Similarity under Random Projections

In this part, we 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.

- •
In §A.I, we introduce the notation and define random projection as a mapping.
- •
In §A.II, we use the rotation argument to provide new representation for the dot product and cosine similarity under the random projections.
- •
In §A.III, 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 in 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 are not many papers that include consideration of the cosine similarity.
- •
In §A.V, we provide a few technical inequalities and concentration results that were used in other sections, for a 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_{i},Rp_{j})\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left((p_{i},p_{j }),\frac{1}{q}[\|p_{j}\|^{2}\|p_{i}\|^{2}+(p_{j},p_{i})^{2}]\right).$ (13) $$

(b) Let $\varepsilon\in(0,1)$ and $\delta\in(0,1)$, then for $q\geq 4\cdot\frac{1+\varepsilon}{\varepsilon^{2}}\log\frac{k(k-1)}{\delta}$ we have that

$$ $\left|(Rp_{j},Rp_{i})-(p_{j},p_{i})\right|<\varepsilon\|p_{j}\|\|p_{i}\|$ $$

for $i<j$ with probability at least $1-\delta$.

Recall that we used a random matrix $R=[R_{ij}]\in\mathbb{R}^{q\times n}$, where $(R_{ij}:i=1,\ldots,n,j=1,\ldots,d)$ are i.i.d. normal random variables with mean zero and variance $1/q$. Here, $p_{1},\ldots,p_{k}$ will be vectors in $\mathbb{R}^{n}$ who are then mapped to vectors $Rp_{1},\ldots,Rp_{k}$ in $\mathbb{R}^{q}$. Other notation in this appendix is described in Table 3.

###### Proof.

Item (a) is the statement of Corollary A.11. Item (b) is the statement of Theorem A.17.
∎

We note that if $p_{i}$ and $p_{j}$ are orthogonal or $(p_{i},p_{j})$ is small, then $\|p_{i}\|\|p_{j}\|$ 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.1.

In the main part, $p_{i}$ and $p_{j}$ had non-negative entries, and therefore, the dot $(p_{i},p_{j})$ products are always non-negative. What is the probability that $(Rp_{i},Rp_{j})$ will be negative? Remarkably, we are able to provide a closed-formula solution dependent only on the cosine similarity $\dfrac{(p_{j},p_{i})}{\|p_{j}\|\|p_{i}\|}=:\cos(p_{j},p_{i})$
of $p_{j}$ and $p_{i}$:

###### Proposition A.2 .

If $(p_{j},p_{i})>0$ and $\cos(p_{j},p_{i})\neq 1$, then

$$ $\mathbb{P}\left((Rp_{j},Rp_{i})<0\right)=\mathbb{P}\left(\mathcal{T}_{q}>\frac {|\cos(p_{j},p_{i})|\sqrt{q}}{\sqrt{1-\cos(p_{j},p_{i})^{2}}}\right),$ $$

where $\mathcal{T}_{q}$ is the $t$-distribution with the parameter $q$.

###### Proof.

Fact $(p_{j},p_{i})>0$ implies $\cos(p_{j},p_{i})\neq-1$. Therefore, the claim follows from Proposition A.8.
∎

###### Proposition A.3 .

(a) For all $i,j$ such that $p_{i}\neq 0$ and $p_{j}\neq 0$, we have:

$$ $\cos(Rp_{i},Rp_{i})\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left(\cos(p_ {i},p_{j}),\frac{1}{q}(1-\cos^{2}(p_{i},p_{j}))^{2}\right).$ (14) $$

(b) Let $\varepsilon\in(0,0.05]$, $\delta\in(0,1)$ and $p_{1},\ldots,p_{k}$ be non-zero vectors in $\mathbb{R}^{n}$. For

$$ $q\geq\frac{2\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{ \delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})} \right]}$ (15) $$

the inequality

$$ $\left|\cos(Rp_{j},Rp_{i})-\cos(p_{j},p_{i})\right|\leq\varepsilon(1-\cos(p_{j} ,p_{i})^{2})$ $$

holds for all $i<j$ with probability at least $1-\delta$.

###### 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_{j},p_{i})|$ is to 1, the smaller the error.

**Table 3: Notation and symbols used in Appendix A**
| $n$<br>original dimension<br>$q$<br>dimension of the projection space<br>$R$<br>$n\times q$ random projection matrix<br>$Q$<br>equal to or distributed as $\sqrt{q}R$<br>$M,N$<br>std. normal random vectors in $\mathbb{R}^{q}$ | $M_{2\ldots q}$<br>vector with entries $(M_{2},\ldots,M_{q})$<br>$x,y,p_{1}\ldots p_{k}$<br>vectors in $\mathbb{R}^{n}$<br>$(\cdot,\cdot)$<br>dot product in $\mathbb{R}^{n}$ or $\mathbb{R}^{q}$<br>$\rho$, $\rho_{x,y}$<br>cosine similarity<br>$\mathcal{T}_{q}$<br>$t$-distribution with parameter $q$ |
| --- | --- |

###### Proposition A.1 .

###### Proof.

###### Proposition A.2 .

###### Proof.

###### Proposition A.3 .

###### Proof.

### A.I General Results and Remarks

#### A.I.1 Vector Representation

For any vector $x$ in $\mathbb{R}^{n}$ we will denote $\tilde{x}:=x/\|x\|.$

Note that for non-zero vectors $x$ and $y$ in $\mathbb{R}^{n}$, cosine similarity has the property

$$ $\frac{(x,y)}{\|x\|\|y\|}=(x/\|x\|,y/\|y\|)=(\tilde{x},\tilde{y}).$ (16) $$

Also, for any matrix $Q\in\mathbb{R}^{q\times n}$

$$ $\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}=\frac{(Q(x/\|x\|),Q(y/\|y\|))}{\|Q(x/\|x\|)\|\|Q( y/\|y\|)\|}=\frac{(Q\tilde{x},Q\tilde{y})}{\|Q\tilde{x}\|\|Q\tilde{y}\|}$ (17) $$

For unit vectors $\tilde{x}$ and $\tilde{y}$, we know from the Gram-Schmidt process that there exists a unique vector $r_{\tilde{x},\tilde{y}}$ such that

$$ $\tilde{x}-(\tilde{x},\tilde{y})\tilde{y}=:r_{\tilde{x},\tilde{y}}.$ $$

Recall that $r_{\tilde{x},\tilde{y}}$ is perpendicular to $\tilde{y}$. Hence, we have
$\|r_{\tilde{x},\tilde{y}}\|=\sqrt{1-(\tilde{x},\tilde{y})^{2}}$. Hence, we can set $\tilde{r}_{\tilde{x},\tilde{y}}=r_{\tilde{x},\tilde{y}}/\|r_{\tilde{x},\tilde{
y}}\|$ and we have

$$ $\tilde{x}=(\tilde{x},\tilde{y})\tilde{y}+\sqrt{1-(\tilde{x},\tilde{y})^{2}} \tilde{r}_{\tilde{x},\tilde{y}}.$ (18) $$

Note that $\tilde{y}$ and $\tilde{r}_{\tilde{x},\tilde{y}}$ are unit and orthogonal vectors.

We will often use $\rho=\rho_{xy}=\frac{(x,y)}{\|x\|\|y\|}$ to denote the cosine similarity of $x$ and $y$.

We can now summarize our findings.

###### Proposition A.4 .

For any two non-zero vectors $x$ and $y$ in $\mathbb{R}^{n}$ there exists a unique unit vector $r_{\tilde{x},\tilde{y}}$ orthogonal to $\tilde{y}$ such that

$$ $\tilde{x}=\rho\tilde{y}+\sqrt{1-\rho^{2}}r_{\tilde{x},\tilde{y}},$ $$

where $\rho$ is the cosine similarity between $x$ and $y$.

###### Proposition A.4 .

#### A.I.2 Random Projection Properties

In this paper, $Q$ will denote a random $q\times n$ matrix whose entries $Q_{ij}\sim\mathcal{N}(0,1)$ are i.i.d.
Random vectors consisting of i.i.d. $\mathcal{N}(0,1)$ random variables we will call standard normal random vectors. Note, $Q$ can be obtained by setting $Q:=\sqrt{q}P$.

###### Lemma A.5 .

Let $x$ and $y$ be two orthogonal unit vectors in $\mathbb{R}^{n}$, i.e. $(x,y)=0$ and $\|x\|=\|y\|=1$. Then
$Qx$ and $Qy$ are two independent identically distributed standard normal random vectors of dimension $q$ .

###### Proof.

We can show that $(Qx)_{1}$, …, $(Qx)_{q}$, $(Qy)_{1}$, …, $(Qy)_{q}$ are i.i.d and $\mathcal{N}(0,1)$.

Note that

$$ $(Qx)_{k}=\sum_{j=1}^{n}Q_{kj}x_{j}\sim\mathcal{N}(0,\|x\|^{2}),$ (19) $$

and

$$ $(Qy)_{k}=\sum_{j=1}^{n}Q_{kj}y_{j}\sim\mathcal{N}(0,\|y\|^{2}).$ (20) $$

Therefore, all of these random variables have the distribution $\mathcal{N}(0,1)$.
From the definition of $Q$, (19) and (20) we can conclude that the sequences $(Qx)_{1},(Qx)_{2},\ldots,(Qx)_{q}$ and $(Qy)_{1},(Qy)_{2},\ldots,(Qy)_{q}$ are i.i.d.

Finally, let us look at the covariance between $(Qx)_{k}$ and $(Qy)_{l}$.

$$ $\mathbb{E}[(Qx)_{k}(Qy)_{l}]=\mathbb{E}\left[\left(\sum_{j=1}^{n}Q_{kj}x_{j} \right)\left(\sum_{j=1}^{n}Q_{lj}y_{j}\right)\right]$ (21) $$

If $l\neq k$ then two sums under the expectation are independent and hence

$$ $\eqref{eq:prodExpectation}=\mathbb{E}\left[\left(\sum_{j=1}^{n}Q_{kj}x_{j} \right)\right]\mathbb{E}\left[\left(\sum_{j=1}^{n}Q_{lj}y_{j}\right)\right]=0 \cdot 0.$ $$

Else, if $l=k$ then:

$$ $\displaystyle\eqref{eq:prodExpectation}$ $\displaystyle=\mathbb{E}\left[\sum_{j=1}^{n}Q_{kj}^{2}x_{j}y_{j}+2\sum_{i\neq j }Q_{kj}Q_{ki}x_{j}y_{i}\right]$ $\displaystyle=\sum_{j=1}^{n}\underbrace{\mathbb{E}[Q_{kj}^{2}]}_{1}x_{j}y_{j}+ 2\sum_{i\neq j}\underbrace{\mathbb{E}[Q_{kj}Q_{ki}]}_{0}x_{j}y_{i}$ $\displaystyle=\sum_{j=1}^{n}x_{j}y_{j}=(x,y)=0.$ $$

The claim now follows.
∎

Recall that $R=q^{-1/2}Q$ is a random $q\times n$ matrix whose entries $R_{ij}\sim\mathcal{N}(0,1/q)$ are i.i.d. Note that, due to the scaling properties,

$$ $\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}=\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}.$ (22) $$

We will state all the main results in the term of the matrix $R$, however $Q$ will let us simplify some proofs.

###### Lemma A.5 .

###### Proof.

### A.II Rotation Argument and Orthogonal Representation

Let $x$ and $y$ be vectors in $\mathbb{R}^{n}$ and $\rho=\frac{(x,y)}{\|x\|\|y\|}$.
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 we have

$$ $(Qx,Qy)=(\sqrt{q}Rx,\sqrt{q}Ry)=\|x\|\|y\|(\rho\|N\|^{2}+M_{1}\|N\|\sqrt{1- \rho^{2}}).$ (23) $$

(b) For the cosine similarity

$$ $\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}=\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}\\ =\frac{\rho\|N\|+M_{1}\sqrt{1-\rho^{2}}}{\sqrt{(\rho\|N\|+M_{1}\sqrt{1-\rho^{2 }})^{2}+(1-\rho^{2})\|M_{2\ldots q}\|^{2}}},$ (24) $$

where $M_{j}$ is the $j$-th component of the vector $M$ and $M_{2\ldots q}=(M_{2},\ldots,M_{q})$.

The rotation argument is powered by the the following Lemma. Recall that $\tilde{N}=N/\|N\|$.

###### Lemma A.7 .

Let $H$ and $N$ be independent standard normal random vectors of dimension $q$, and $U_{\tilde{N}}$ an orthogonal $q\times q$ matrix such that $U_{\tilde{N}}\tilde{N}=e_{1}$.
Then random vectors $U_{\tilde{N}}H$ and $N$ are independent standard normal.

###### Proof.

Note that for every orthogonal matrix $U$, vector $UH$ is normal random with expectation 0 0 and identity covariance matrix. Therefore, it has the same distribution as $H$.

We will show that $(U_{\tilde{N}}H,N)$ has the same distribution as $(H,N)$. Let $f_{N}$ be the density of $N$ and since $N$ is independent of $H$ we have

$$ $\displaystyle\mathbb{P}(U_{\tilde{N}}H\in A,N\in B)$ $\displaystyle=\int_{z\in B}\mathbb{P}(U_{\tilde{z}}H\in A)f_{N}(z)dz$ $\displaystyle\stackrel{{\scriptstyle U_{\tilde{z}}H\stackrel{{\scriptstyle d}} {{=}}H}}{{=}}\int_{z\in B}\mathbb{P}(H\in A)f_{N}(z)dz=\mathbb{P}(H\in A,N\in B)$ $$

for all measurable subsets $A,B$ of $\mathbb{R}^{q}$.
∎

###### Proof of Theorem A.6 .

Note that $Qx=\rho Qy+\sqrt{1-\rho^{2}}Q\tilde{r}_{\tilde{x},\tilde{y}}$. Since, $(y,\tilde{r}_{\tilde{x},\tilde{y}})=0$, by Lemma A.5 we know that $H=R\tilde{r}_{\tilde{x},\tilde{y}}$ and $N=Ry$ are independent standard normal random variables.
Hence, we have

$$ $\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}=\frac{(\rho N+\sqrt{1-\rho^{2}}H,N)}{\|\rho N+ \sqrt{1-\rho^{2}}H\|\|N\|}=\frac{(\rho N+\sqrt{1-\rho^{2}}H,\tilde{N})}{\|\rho N +\sqrt{1-\rho^{2}}H\|}.$ (25) $$

We now pick the orthogonal $q\times q$ matrix $U_{\tilde{N}}$ for which $U_{\tilde{N}}\tilde{N}=e_{1}$. Applying the $U_{\tilde{N}}$-transformation to all arguments in (25) we get

$$ $\frac{(Qx,Qy)}{\|Qx\|\|Qy\|}=\frac{(U_{\tilde{N}}(\rho\|N\|\tilde{N}+\sqrt{1- \rho^{2}}H),U_{\tilde{N}}(\tilde{N}))}{\|U_{\tilde{N}}(\rho\|N\|\tilde{N}+ \sqrt{1-\rho^{2}}H)\|}=\frac{(\rho\|N\|e_{1}+\sqrt{1-\rho^{2}}U_{\tilde{N}}H,e _{1})}{\|\rho\|N\|e_{1}+\sqrt{1-\rho^{2}}U_{\tilde{N}}H\|}.$ $$

Setting $M:=U_{\tilde{N}}H$. By Lemma A.7, $M$ remains standard normal random vector independent of $N$.

We can apply the same arguments to the dot product:

$$ $\displaystyle(Qx,Qy)$ $\displaystyle=(\rho N+\sqrt{1-\rho^{2}}H,N)=\|N\|(\rho N+\sqrt{1-\rho^{2}}H, \tilde{N})$ $\displaystyle=\|N\|(U_{\tilde{N}}(\rho\|N\|\tilde{N}+\sqrt{1-\rho^{2}}H),U_{ \tilde{N}}(\tilde{N}))=\|N\|(\rho\|N\|e_{1}+\sqrt{1-\rho^{2}}U_{\tilde{N}}H,e_ {1})$ $\displaystyle=\rho\|N\|^{2}+\sqrt{1-\rho^{2}}(U_{\tilde{N}}H,e_{1})\|N\|=\rho \|N\|^{2}+\sqrt{1-\rho^{2}}M_{1}\|N\|.$ $$

∎

###### Theorem A.6 .

###### Lemma A.7 .

###### Proof.

###### Proof of 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 of 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.

#### A.III.1 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-negative.
Can the projection change that?
The representation for the dot product gives us an exact answer to that question.

###### Proposition A.8 .

(a) If $(x,y)=0$ and $\|x\|\|y\|\neq 0$ then $\mathbb{P}((Rx,Ry)<0)=\mathbb{P}((Rx,Ry)>0)=\frac{1}{2}$.

(b) If $(x,y)\neq 0$ and $|\rho|\neq 1$ then

$$ $\mathbb{P}\left(\frac{(Rx,Ry)}{(x,y)}<0\right)=\mathbb{P}\left(\mathcal{T}_{q} >\frac{|\rho|\sqrt{q}}{\sqrt{1-\rho^{2}}}\right),$ $$

where $\mathcal{T}_{q}$ is the $t$-distribution with the parameter $q$.

###### Proof.

In the case (a) $\rho=0$ and the claim follows from the (23), since the sign depends on the sign of $M_{1}$ which can be positive or negative with probability $\frac{1}{2}$. In (b) we can assume $(x,y)>0$ and therefore $\rho>0$. Hence,

$$ $\displaystyle\mathbb{P}\left(\frac{(Rx,Ry)}{(x,y)}<0\right)=\mathbb{P}\left(( Rx,Ry)<0\right)=\mathbb{P}\left((q^{-1/2}Qx,q^{-1/2}Qy)<0\right)$ $\displaystyle=\mathbb{P}\left((Qx,Qy)<0\right)=\mathbb{P}\left(\rho\|N\|^{2}+M _{1}\|N\|\sqrt{1-\rho^{2}}<0\right)$ $\displaystyle=\mathbb{P}\left(\frac{M_{1}}{\|N\|}<-\frac{\rho}{\sqrt{1-\rho^{2 }}}\right)=\mathbb{P}\left(\frac{M_{1}}{\sqrt{\|N\|^{2}/q}}<-\frac{\rho\sqrt{q }}{\sqrt{1-\rho^{2}}}\right).$ $$

Since $\mathcal{T}_{q}:=\frac{M_{1}}{\sqrt{\|N\|^{2}/p}}\sim t(q)$ the claim follows from the fact that $t(q)$ is symmetric random variable for the last expression we have

$$ $\displaystyle=\mathbb{P}\left(\mathcal{T}_{q}<-\frac{\rho\sqrt{q}}{\sqrt{1- \rho^{2}}}\right)=\mathbb{P}\left(\mathcal{T}_{q}>\frac{\rho\sqrt{q}}{\sqrt{1- \rho^{2}}}\right).$ $$

∎

As we can see from the graph on Figure 2 the probability of changing a sign is the highest - $\frac{1}{2}$ for $\rho=0$ and and quickly becomes really low. From [, Corollary 3.2.2.] we know that the $\mathbb{P}\left(\frac{(Rx,Ry)}{(x,y)}<0\right)\leq\exp(-q\rho^{2}/8)$ and the result here gives the exact value of the probability.

Figure: Figure 2: Graphs of functions $\rho\mapsto\mathbb{P}\left(\mathcal{T}_{q}>\frac{|\rho|\sqrt{q}}{\sqrt{1-\rho^ {2}}}\right)$ and $\rho\mapsto\log\mathbb{P}\left(\mathcal{T}_{q}>\frac{|\rho|\sqrt{q}}{\sqrt{1- \rho^{2}}}\right)$ for $q=100$ on the interval $[-0.5,0.5]$.
Refer to caption: extracted/5761948/GraphSignChange.png

This results tells us that the probability of the dot product sign change under random projection is a function of $\rho$, which in practice we don’t know. If we wanted to calculate a probability of a cosine similarity or dot product changing signs in case of a large number of vectors it would be hard to do so. However we can still conclude that if $\rho$ is close to zero we can expect the sign to change, while if it is reasonably far from 0 it is unlikely that the sign will change.

###### Proposition A.8 .

###### Proof.

#### A.III.2 Central Limit Theorem

The representation given in (23) has many consequences. For example, we can simply calculate the expectation and the variance of the dot product.

###### Proposition A.9 .

We have $\mathbb{E}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]=\rho$ and ${\rm Var}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]=\frac{1+\rho^{2}}{q}$.

###### Proof.

Recall that $\mathbb{E}[M_{1}]=1$ and $\mathbb{E}[M_{1}^{2}]=1$; $\mathbb{E}[\|N\|^{2}]=q$ and $\mathbb{E}[\|N\|^{4}]=q(q+2)$. Using (23) we have

$$ $\displaystyle\mathbb{E}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]$ $\displaystyle=q^{-1}(\rho\mathbb{E}[\|N\|^{2}]+\mathbb{E}[\|N\|]\mathbb{E}[M_{ 1}]\sqrt{1-\rho^{2}})$ $\displaystyle=q^{-1}\rho q+\mathbb{E}[\|N\|]\cdot 0\cdot\sqrt{1-\rho^{2}}=\rho,$ $$

and

$$ $\displaystyle\mathbb{E}\left[\left(\frac{(Rx,Ry)}{\|x\|\|y\|}\right)^{2}\right]$ $\displaystyle=q^{-2}\rho^{2}\mathbb{E}[\|N\|^{4}]+2q^{-2}\mathbb{E}[\|N\|^{3}] \mathbb{E}[M_{1}]\rho\sqrt{1-\rho^{2}}+q^{-2}\mathbb{E}[\|N\|^{2}]\mathbb{E}[M _{1}^{2}](1-\rho^{2})]$ $\displaystyle=q^{-2}\rho^{2}q(q+2)+0+q^{-2}\cdot q\cdot 1\cdot(1-\rho^{2})= \rho^{2}+\frac{1+\rho^{2}}{q}.$ $$

Now, since ${\rm Var}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}\right]=\mathbb{E}\left[\left(\frac{(
Rx,Ry)}{\|x\|\|y\|}\right)^{2}\right]-\left(\mathbb{E}\left[\frac{(Rx,Ry)}{\|x
\|\|y\|}\right]\right)^{2}$, the claim follows.
∎

We can also get the following asymptotic result relatively easy.

###### Theorem A.10 .

We have

$$ $\sqrt{q}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho\right]\stackrel{{\scriptstyle d} }{{\to}}\mathcal{N}(0,1+\rho^{2}),$ $$

as $q\to\infty$.

###### Proof.

Form the Central Limit Theorem we have
$\frac{\|N\|^{2}-q}{\sqrt{q}}=q^{-1/2}\sum_{j=1}^{q}(N_{1}^{2}-1)\stackrel{{
\scriptstyle d}}{{\to}}\mathcal{N}(0,2)$ and by the Law of Large Numbers we have
$\frac{1}{\sqrt{q}}\|N\|=\sqrt{\frac{N_{1}^{2}+\ldots+N_{q}^{2}}{q}}\to 1$ almost surely. Since $M_{1}$ is independent, we have

$$ $\displaystyle\sqrt{q}\left[\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho\right]$ $\displaystyle=\left[\rho\cdot\frac{\|N\|^{2}-q}{\sqrt{q}}+M_{1}\frac{\|N\|}{ \sqrt{q}}\sqrt{1-\rho^{2}}\right]$ $\displaystyle\stackrel{{\scriptstyle d}}{{\to}}\hat{\mathcal{N}}(0,2\rho^{2})+ \mathcal{N}(0,1-\rho^{2})\stackrel{{\scriptstyle d}}{{=}}\mathcal{N}(0,1+\rho^ {2}).$ $$

∎

We can write the last result in the following form, which we stated in part (a) of Proposition A.1.

###### Corollary A.11 .

We have

$$ $\sqrt{q}[(Rx,Ry)-(x,y)]\stackrel{{\scriptstyle d}}{{\to}}\mathcal{N}(0,\|x\|^{ 2}\|y\|^{2}+(x,y)^{2}),$ $$

as $q\to\infty$.

Although, $(Rx,Ry)$ is an unbiased and asymptotically normal estimator for $(x,y)$, the control of the standard deviation can be a problem.
$(x,y)$ could be small compared to the value of $\sigma=\sqrt{\frac{\|x\|^{2}\|y\|^{2}+(x,y)^{2}}{q}}$.
Let $x=(1,0,1,0,\ldots)$ and $y=(0,1,0,1,\ldots)$, then $(x,y)=0$ and $\sigma=\frac{n}{2\sqrt{q}}$. However, since $q\ll n$ the random projection might be nowhere near the value of $(x,y)$. Simulation in Figure 3 illustrates this issue.

Figure: Figure 3: Simulated dot product $(R\tilde{x},R\tilde{y})$ for $x=(1,0,1,0,\ldots)$ and $y=(0,1,0,1,\ldots)$ for $n=2000$ and $q=100$.
Refer to caption: extracted/5761948/SimulationDotProduct.png

###### Proposition A.9 .

###### Proof.

###### Theorem A.10 .

###### Proof.

###### Corollary A.11 .

#### A.III.3 Concentration Results

So far we have shown that $\frac{(Rx,Ry)}{\|x\|\|y\|}$ is an unbiased and asymptotically normal estimator for $\rho$. However when we have many vectors and we want to be sure that all of their similarities get randomly projected to approximate values we will need to use concentration results.

First, using (23) we calculate the Laplace transform.

###### Proposition A.12 .

We have

$$ $\mathbb{E}[\exp(\lambda(Q\tilde{x},Q\tilde{y}))]=[(1-\lambda(1+\rho))(1- \lambda(\rho-1))]^{-q/2}$ (26) $$

for $\lambda\in(-(1-\rho)^{-1},(1+\rho)^{-1})$

###### Proof.

Recall that $\mathbb{E}(e^{\lambda M_{1}})=e^{\lambda^{2}/2}$ for all $\lambda\in\mathbb{R}$ and $\mathbb{E}(e^{\lambda\|N\|^{2}})=(1-2\lambda)^{-q/2}$ for $\lambda<1/2$.
By applying the Laplace transform first to $M_{1}$ and then to $\|N\|^{2}$ we get

$$ $\displaystyle\mathbb{E}[\exp(\lambda(Q\tilde{x},Q\tilde{y}))]=\mathbb{E}\left[ e^{\lambda\rho\|N\|^{2}}\mathbb{E}\left[e^{\lambda\|N\|\sqrt{1-\rho^{2}}M_{1}} |\|N\|\right]\right]$ $\displaystyle=\mathbb{E}\left[e^{\lambda\rho\|N\|^{2}}e^{\lambda^{2}\|N\|^{2}( 1-\rho^{2})/2}\right]=\mathbb{E}\left[e^{(\lambda\rho+\lambda^{2}(1-\rho^{2})/ 2)\|N\|^{2}}\right]$ $\displaystyle=(1-(2\lambda\rho-\lambda^{2}(1-\rho^{2})))^{-q/2}=[(1-\lambda(1+ \rho))(1-\lambda(\rho-1))]^{-q/2}$ $$

∎

We will now use the the Laplace Transform to obtain Chernhov bounds.
The following Lemma will be a useful estimate.

###### Lemma A.13 .

For $\lambda\in(0,(1+\rho)^{-1})$ we have

$$ $\log\mathbb{E}[\exp(\lambda[(Q\tilde{x},Q\tilde{y})-q\rho])]\leq\frac{\lambda^ {2}q(1+\rho^{2})}{2(1-\lambda(1+\rho))},$ (27) $$

and $\lambda\in(0,(1-\rho)^{-1})$

$$ $\log\mathbb{E}[\exp(-\lambda[(Q\tilde{x},Q\tilde{y})-q\rho)]]\\ \leq\frac{\lambda^{2}q(1+\rho^{2})}{2(1-\lambda(1-\rho))}.$ (28) $$

###### Proof.

In case $\rho=1$ or $\rho=-1$ expression in (26) will simplify and we will be able to use Proposition A.35 on $X$ and $-X$ respectively.

One can show that for $s\in(0,1)$ we have (see Lemma A.38 (a)):

$$ $(-\log(1-s)-s)\leq\frac{s^{2}}{2(1-s)},$ (29) $$

and for $s<0$ (see Lemma A.38 (a)):

$$ $(-\log(1-s)-s)\leq\frac{s^{2}}{2}.$ (30) $$

We will prove (27), (28) is shown in the same way.

$$ $\displaystyle\log\mathbb{E}[\exp(\lambda(Q\tilde{x},Q\tilde{y})-q\rho)]$ $\displaystyle=-\lambda q\rho-\frac{q}{2}\log(1-\lambda(1+\rho))-\frac{q}{2} \log(1-\lambda(\rho-1))$ $\displaystyle=\frac{q}{2}\left[-\log(1-\lambda(1+\rho))-\lambda(1+\rho)\right] +\frac{q}{2}\left[-\log(1-\lambda(\rho-1))-\lambda(\rho-1)\right]$ $\displaystyle\stackrel{{\scriptstyle\eqref{eq:HelpInequality},\eqref{eq: HelpInequality1}}}{{\leq}}\frac{q}{2}\left[\frac{\left(\lambda(1+\rho)\right)^ {2}}{2(1-\lambda(1+\rho))}+\frac{\left(\lambda(\rho-1)\right)^{2}}{2}\right]$ $\displaystyle\leq\frac{q}{2}\left[\frac{(\lambda(1+\rho))^{2}}{2(1-\lambda(1+ \rho))}+\frac{\left(\lambda(\rho-1)\right)^{2}}{2(1-\lambda(1+\rho))}\right]$ $\displaystyle=\frac{q}{2}\left[\frac{\left(\lambda(1+\rho)\right)^{2}+\left( \lambda(\rho-1)\right)^{2}}{2(1-\lambda(1+\rho))}\right]=\frac{\lambda^{2}q(1+ \rho^{2})}{2(1-\lambda(1+\rho))}$ $$

This proves (27), the equation (28) can be proved in the same way.
∎

###### Theorem A.14 .

For $t\geq 0$ we have

$$ $\mathbb{P}((Q\tilde{x},Q\tilde{y})-q\rho>t)\\ \leq\exp\left(\frac{-t^{2}}{2q(1+\rho^{2})+2(1+\rho)t}\right),$ (31) $$

and

$$ $\mathbb{P}((Q\tilde{x},Q\tilde{y})-q\rho<-t)\\ \leq\exp\left(\frac{-t^{2}}{2q(1+\rho^{2})+2(1-\rho)t}\right).$ (32) $$

###### Proof.

Note that $\mathbb{E}[(Q\tilde{x},Q\tilde{y})]=q\rho$.

Since (27) holds we can use Theorem A.33 by setting $X=(Q\tilde{x},Q\tilde{y})$ to obtain (31).

Since (28) holds we can use Theorem A.33 by setting by setting $X=-(Q\tilde{x},Q\tilde{y})$ to obtain (32).
∎

###### Proposition A.15 .

For any function $f:[-1,1]\to[0,\infty)$ we have:

$$ $\mathbb{P}((Q\tilde{x},Q\tilde{y})-q\rho>q\varepsilon f(\rho))\\ \leq\exp\left(\frac{-qf(\rho)^{2}}{2(1+\rho^{2})}\left[\varepsilon^{2}- \varepsilon^{3}\frac{1+\rho}{1+\rho^{2}}f(\rho)\right]\right)$ (33) $$

$$ $\mathbb{P}((Q\tilde{x},Q\tilde{y})-q\rho<-q\varepsilon f(\rho))\\ \leq\exp\left(\frac{-qf(\rho)^{2}}{2(1+\rho^{2})}\left[\varepsilon^{2}- \varepsilon^{3}\frac{1-\rho}{1+\rho^{2}}f(\rho)\right]\right)$ (34) $$

###### Remark A.16 .

Note that for $\rho=1$ and $f(\rho)=\varepsilon$ we get the usual bounds for $\chi^{2}(q)$ used to prove Johnson -Lindenstrauss Lemma as given, for example in, in [, Lemma 1.3.] and [].

###### Proposition A.12 .

###### Proof.

###### Lemma A.13 .

###### Proof.

###### Theorem A.14 .

###### Proof.

###### Proposition A.15 .

###### Remark A.16 .

#### A.III.4 Johnson-Lindenstrauss-type Result

###### Theorem A.17 .

Let $p_{1},\ldots p_{k}$ be a finite set of vectors in $\mathbb{R}^{n}$ and let $\varepsilon\in(0,1)$ and $\delta\in(0,1)$, then for $q\geq 4\cdot\frac{1+\varepsilon}{\varepsilon^{2}}\log\frac{k(k-1)}{\delta}$

$$ $\left|\frac{(Rp_{j},Rp_{i})}{\|p_{j}\|\|p_{i}\|}-\frac{(p_{j},p_{i})}{\|p_{j} \|\|p_{i}\|}\right|<\varepsilon$ $$

for $i<j$ with probability at least $1-\delta$.

We have $\binom{k}{2}$ cosine similarities in the statement above and in practice we will have no way of estimating(^2^22One exception is the case when $x_{1},\ldots,x_{k}$ are all in $[0,\infty)^{n}$, i.e. have nonnegative coordinates. In that case we know cosine similarities will be in interval $[0,1]$.) them. To prove this result we need a probablity estimate that doesn’t depend on the value of the cosine similarity. The following Proposition will help us in that by simplifying the statement of Theorem A.14.

###### Proposition A.18 .

For $\varepsilon>0$ we have

$$ $\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho>\varepsilon\right)\leq\exp \left(\frac{-q\varepsilon^{2}}{4(1+\varepsilon)}\right),$ (35) $$

and

$$ $\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho<-\varepsilon\right)\leq\exp \left(\frac{-q\varepsilon^{2}}{4(1+\varepsilon)}\right).$ (36) $$

###### Proof.

By setting $t=q\varepsilon$ in (31) we get

$$ $\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho>\varepsilon\right)\leq\exp \left(\frac{-q\varepsilon^{2}}{2(1+\rho^{2})+2(1+\rho)\varepsilon}\right),$ $$

Using the fact that $|\rho|\leq 1$ we get

$$ $\frac{-q\varepsilon^{2}}{2(1+\rho^{2})+2(1+\rho)\varepsilon}\leq\frac{-q \varepsilon^{2}}{4(1+\varepsilon)}.$ $$

This proves (35). Bound in (36) can be shown in a same way.
∎

###### Proof of Theorem A.17 ..

Define sets

$$ $\displaystyle A_{ij}$ $\displaystyle=\left(\left|\frac{(Rp_{j},Rp_{i})}{\|p_{j}\|\|p_{i}\|}-\frac{(p_ {j},p_{i})}{\|p_{j}\|\|p_{i}\|}\right|<\varepsilon\right)$ $\displaystyle A_{ij}^{c+}$ $\displaystyle=\left(\frac{(Rp_{j},Rp_{i})}{\|p_{j}\|\|p_{i}\|}-\frac{(p_{j},p_ {i})}{\|p_{j}\|\|p_{i}\|}>\varepsilon\right)$ $\displaystyle A_{ij}^{c-}$ $\displaystyle=\left(\frac{(Rp_{j},Rp_{i})}{\|p_{j}\|\|p_{i}\|}-\frac{(p_{j},p_ {i})}{\|p_{j}\|\|p_{i}\|}<-\varepsilon\right)$ $$

Note that $A_{ij}^{c}=A_{ij}^{c+}\cup A_{ij}^{c-}$. Using the union bound tehnicque we get

$$ $P\left(\bigcap_{i<j}A_{ij}\right)=1-P\left(\bigcup_{i<j}A_{ij}^{c}\right)=1-P \left(\bigcup_{i<j}A_{ij}^{c+}\cup A_{ij}^{c-}\right)\geq 1-\sum_{i<j}[\mathbb {P}(A_{ij}^{c+})+\mathbb{P}(A_{ij}^{c-})].$ $$

From Proposition A.18 and bound on $q$ we have that

$$ $\displaystyle\sum_{i<j}[\mathbb{P}(A_{ij}^{c+})+\mathbb{P}(A_{ij}^{c-})]\leq k (k-1)\exp\left(-q\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right)$ $\displaystyle\leq k(k-1)\exp\left(-4\cdot\frac{1+\varepsilon}{\varepsilon^{2}} \log\frac{k(k-1)}{\delta}\cdot\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right)=\delta.$ $$

∎

###### Theorem A.17 .

###### Proposition A.18 .

###### Proof.

###### Proof of Theorem A.17 ..

#### A.III.5 Comparison with Known Results

Regarding known estimates for the dot product, Theorem 2.1. from [] provides the following bounds for $\varepsilon\in(0,1)$:

$$ $\mathbb{P}\left(\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho>\varepsilon\right)\leq e^{- \frac{q\varepsilon^{2}}{8}},\quad\textrm{and}\quad\mathbb{P}\left(\frac{(Rx,Ry )}{\|x\|\|y\|}-\rho<-\varepsilon\right)\leq e^{-\frac{q\varepsilon^{2}}{8}}.$ $$

This a simple consequence of Proposition A.18.

Equation (4) in [] and Lemma 5.7. in [] provide the following estimate:

$$ $\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho\right|\leq\varepsilon \right)\geq 1-4e^{-\frac{q(\varepsilon^{2}-\varepsilon^{3})}{4}}.$ $$

Since $\varepsilon^{2}-\varepsilon^{3}\leq\frac{\varepsilon^{2}}{1+\varepsilon}$, again, from Proposition A.18 we can get a better estimate

$$ $\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|x\|\|y\|}-\rho\right|\leq\varepsilon \right)\geq 1-2e^{-\frac{q\varepsilon^{2}}{4(1+\varepsilon)}}.$ $$

### 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 ρ = ± 1 𝜌 plus-or-minus 1 \rho=\pm 1 italic_ρ = ± 1

Recall that in the case of $\rho=\pm 1$, i.e.

$$ $\frac{(x,y)}{\|x\|\|y\|}=\pm 1$ $$

there exists $\alpha>0$ such that $x=\pm\alpha y$. This is a known consequence of the Cauchy-Schwarz inequality.

In this case we have

$$ $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\frac{(R(\pm\alpha y),Ry)}{\|R(\pm\alpha y)\|\|Ry \|}=\\ =\frac{\pm\alpha(Ry,Ry)}{\alpha\|Ry\|\|Ry\|}=\pm\frac{\|Ry\|^{2}}{\|Ry\|^{2}}= \pm 1=\rho.$ (37) $$

It turns out the that this is preserved under random projections.

###### Proposition A.19 .

If $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\pm 1$ then there exists $\alpha>0$ such that $x=\pm\alpha y$ (almost surely).

###### Proof.

Since the cosine similarity of $Rx$ and $Ry$ is $\pm 1$, then there is an $\alpha>0$ such that $Rx=\pm\alpha Ry$.
Hence, $w=R(x\mp\alpha y)=0$.
Let us assume $x\mp\alpha y\neq 0$ then $R(x\mp\alpha y)$ is $q$-dimensional vector with entries distributed as $\mathcal{N}(0,\|x\mp\alpha y\|^{2}/q)$.
The probability of which being a zero vector is 0 0. Hence, we have $x=\pm\alpha y$ almost surely.
∎

Hence, the in the cosine similarity of $\pm 1$ will be preserved under random projection $Q$.

###### Corollary A.20 .

If $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\pm 1$ almost surely if and only if $\frac{(x,y)}{\|x\|\|y\|}=\pm 1$.

###### Proof.

$\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\pm 1$, by Proposition A.19, holds if and only if $x=\pm\alpha y$ for some $\alpha>0$, and, Cauchy-Shcwarz inequality, this holds if and only if
$\frac{(x,y)}{\|x\|\|y\|}=\pm 1$.
∎

###### Proposition A.19 .

###### Proof.

###### Corollary A.20 .

###### Proof.

#### A.IV.2 Central Limit Theorem

In this section we will show that the value of $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}$ is approximately normally distributed around $\rho$ with a variance $\frac{(1-\rho^{2})^{2}}{q}$.

###### Theorem A.21 .

For non-zero vectors $x$ and $y$ in $\mathbb{R}^{n}$ we have

$$ $\sqrt{q}\left[\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\frac{(x,y)}{\|x\|\|y\|}\right] \stackrel{{\scriptstyle d}}{{\to}}\mathcal{N}\left(0,\left[1-\left(\frac{(x,y) }{\|x\|\|y\|}\right)^{2}\right]^{2}\right),$ (38) $$

as $q\to\infty$.

Theorem A.21 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_{q}=\rho\|N\|+M_{1}\sqrt{1-\rho^{2}}$ and $B_{q}=\|M_{2\ldots q}\|$, then from (24) we have:

$$ $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho=(1-\rho^{2})\cdot\frac{(T_{q})^{2}-\rho^{2}B _{q}^{2}}{\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}\cdot\frac{1}{T_{q}+\rho \sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}$ (39) $$

###### Proof.

We have:

$$ $\displaystyle\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho$ $\displaystyle=\frac{T_{q}}{\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}-\rho= \frac{T_{q}-\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}{\sqrt{(T_{q})^{2}+(1 -\rho^{2})B_{q}^{2}}}$ $\displaystyle=\frac{T_{q}-\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}{\sqrt{ (T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}\cdot\frac{T_{q}+\rho\sqrt{(T_{q})^{2}+(1- \rho^{2})B_{q}^{2}}}{T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}$ $\displaystyle=\frac{(1-\rho^{2})(T_{q})^{2}-\rho^{2}(1-\rho^{2})B_{q}^{2}}{ \sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}\cdot\frac{1}{T_{q}+\rho\sqrt{(T_{q}) ^{2}+(1-\rho^{2})B_{q}^{2}}}.$ $$

∎

###### Proof of Theorem A.21 ..

We will use notation and results from Lemma A.22. From the Law of Large Numbers, we have

$$ $\frac{T_{q}}{\sqrt{q}}=\rho\sqrt{\frac{1}{q}\sum_{j=1}^{q}N_{j}^{2}}+q^{-1/2}M _{1}\sqrt{1-\rho^{2}}\to\rho\cdot 1+0\cdot\sqrt{1-\rho^{2}}=\rho$ (40) $$

almost surely, as $q\to\infty$. Using the same arguments, we have $\frac{B_{q}}{\sqrt{q}}\to 1$ almost surely.
Hence,

$$ $\displaystyle q^{-1/2}\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}$ $\displaystyle=\sqrt{\left(\frac{T_{q}}{\sqrt{q}}\right)^{2}+(1-\rho^{2})\left( \frac{B_{q}}{\sqrt{q}}\right)^{2}}$ $\displaystyle\to\sqrt{\rho^{2}+(1-\rho^{2})\cdot 1^{2}}=1$ (41) $$

almost surely as $q\to\infty$.
(40) and (41) now imply

$$ $q^{-1/2}(T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}})\to\rho+\rho=2\rho.$ (42) $$

Using the Central Limit Theorem, we get

$$ $\frac{B_{q}^{2}-q}{\sqrt{q}}=\frac{1}{\sqrt{q}}\sum_{j=2}^{q}(M_{j}^{2}-1)- \frac{1}{\sqrt{q}}\stackrel{{\scriptstyle d}}{{\to}}\mathcal{N}(0,2),$ $$

$$ $\displaystyle\frac{T_{q}^{2}-q\rho^{2}}{\sqrt{q}}$ $\displaystyle=\rho^{2}\frac{\|N\|^{2}-q}{\sqrt{q}}+2\rho\sqrt{1-\rho^{2}}\frac {\|N\|}{\sqrt{q}}M_{1}+(1-\rho^{2})\frac{M_{1}^{2}}{\sqrt{q}}$ $\displaystyle\stackrel{{\scriptstyle d}}{{\to}}\rho^{2}\mathcal{N}(0,2)+2\rho \sqrt{1-\rho^{2}}\mathcal{N}(0,1)+0=\mathcal{N}(0,4\rho^{2}-2\rho^{4}).$ $$

Now, we have

$$ $\displaystyle\sqrt{q}\left[\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right]$ $\displaystyle=\frac{\frac{T_{q}^{2}-q\rho^{2}}{\sqrt{q}}-\rho^{2}\frac{B_{q}^{ 2}-q}{\sqrt{q}}}{q^{-1/2}\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}}}\cdot\frac{( 1-\rho^{2})}{q^{-1/2}(T_{q}+\rho\sqrt{(T_{q})^{2}+(1-\rho^{2})B_{q}^{2}})}$ $\displaystyle=\frac{\mathcal{N}(0,4\rho^{2}-2\rho^{4})-\rho^{2}\mathcal{N}(0,2 )}{1}\cdot\frac{1-\rho^{2}}{2\rho}=(1-\rho^{2})\frac{\mathcal{N}(0,4\rho^{2}-2 \rho^{4})+\mathcal{N}(0,2\rho^{4})}{2\rho}$ $\displaystyle=(1-\rho^{2})\frac{\mathcal{N}(0,4\rho^{2})}{2\rho}=(1-\rho^{2}) \mathcal{N}(0,1)=\mathcal{N}(0,(1-\rho^{2})^{2}).$ $$

∎

For practical purposes, we interpret the result as given in (14) - that for large $q$ 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.

Figure: Figure 4: Simulated random projection for $n=q=100$, where $(x,y)/\|x\|/\|y\|=\rho=0.154$
Refer to caption: extracted/5761948/simulationP100.png

From simulations, see Figure 4, even for $q=100$ we have approximately normal behavior, but the variance is large and the value might not be close to the original similarity. The result of Theorem A.21 will be more useful for larger values of $q$.

The same result holds for the empirical correlation coefficient in linear regression and in this case it is known that this is not a practical result (see [, Example 3.6.]). However, we 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\geq 6400$ the error will be $\pm 0.05$ with the estimated probability of at least $0.95$. Concentration results to follow will further confirm this.

###### Theorem A.21 .

###### Lemma A.22 .

###### Proof.

###### Proof of Theorem A.21 ..

#### A.IV.3 Concentration Result

Theorem A.21 guarantees that for large $q$ the cosine similarity random projection will be almost preserved with high probability for any pair of vectors in $\mathbb{R}^{n}$. However, this approach is not feasible to analyze the behavior of all pairs of vectors in a given set $y_{1},\ldots,y_{k}$, as 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 a 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 $y$ be non-zero vectors in $\mathbb{R}^{n}$ and $\varepsilon\in(0,0.055)$, then

$$ $\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right|\geq\varepsilon( 1-\rho^{2})\right)\leq(4+\varepsilon^{2})\left[1+\frac{\varepsilon^{2}}{2(1+ \varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}$ $$

Recall the representation from Theorem A.6: For a given random $R$, for any vectors $x$ and $y$ in $\mathbb{R}^{n}$ there exist standard $q$-dimensional Gaussian vectors $N=N^{x,y}$ and $M=M^{x,y}$ such that

$$ $\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\frac{\rho\|N\|+M_{1}\sqrt{1-\rho^{2}}}{\sqrt{( \rho\|N\|+M_{1}\sqrt{1-\rho^{2}})^{2}+(1-\rho^{2})\|M_{2\ldots q}\|^{2}}}.$ $$

###### Theorem A.23 .

#### Bounds on tails

We will first determine some tail bounds. We start with the following lemma.

###### Lemma A.24 .

We have

$$ $\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots q}\|}>\varepsilon\right)=\mathbb{P} \left(\frac{M_{1}}{\|M_{2\ldots q}\|}<-\varepsilon\right)\leq\frac{1}{(1+ \varepsilon^{2})^{\frac{q-1}{2}}}$ $$

###### Proof.

Note that $M_{1}\sim\mathcal{N}(0,1)$ and $\|M_{2\ldots q}\|^{2}\sim\chi^{2}(q-1)$ are independent.
The equality $\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots q}\|}>\varepsilon\right)=\mathbb{P}
\left(\frac{M_{1}}{\|M_{2\ldots q}\|}<-\varepsilon\right)$ follows from the fact that both $M_{1}$ and $-M_{1}$ have the same distribution.
Further, by Markov’s inequality we get

$$ $\displaystyle\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots q}\|}>\varepsilon\right )=\mathbb{E}[\mathbb{P}\left(M_{1}>\varepsilon\|M_{2\ldots q}\||\|M_{2\ldots q }\|\right)]$ $\displaystyle\leq\mathbb{E}[\exp\left(-\varepsilon^{2}\|M_{2\ldots q}\|^{2}/2 \right)]=\frac{1}{(1+\varepsilon^{2})^{\frac{q-1}{2}}}.$ $$

The last equality follows from the fact that $\|M_{2\ldots q}\|^{2}$ has the $\chi^{2}(q-1)$ distribution and the Laplace transform for this distribution.
∎

###### Lemma A.25 .

For $\varepsilon>0$ we have:

$$ $\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots q}\|}>\sqrt{1+\varepsilon}\right) \leq\sqrt{1+\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1+ \varepsilon)}\right]^{-\frac{q}{2}}$ (43) $$

$$ $\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots q}\|}<\sqrt{1-\varepsilon}\right) \leq\sqrt{1-\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1- \varepsilon)}\right]^{-\frac{q}{2}}$ (44) $$

###### Proof.

Using Markov inequality, we have for all $\lambda\in(0,1/2)$:

$$ $\displaystyle\mathbb{P}\left(\frac{\|N\|^{2}}{\|M_{2\ldots q}\|^{2}}>1+ \varepsilon\right)=\mathbb{P}(\lambda\|N\|^{2}>\lambda(1+\varepsilon)\|M_{2 \ldots q}\|^{2})$ $\displaystyle=\mathbb{P}(\lambda\|N\|^{2}-\lambda(1+\varepsilon)\|M_{2\ldots q }\|^{2}>0)=\mathbb{P}(\exp[\lambda\|N\|^{2}-\lambda(1+\varepsilon)\|M_{2\ldots q }\|^{2}]>1)$ $\displaystyle\leq\mathbb{E}[e^{\lambda\|N\|^{2}-\lambda(1+\varepsilon)\|M_{2 \ldots q}\|^{2}}]\leq\frac{1}{(1-2\lambda)^{\frac{q}{2}}}\cdot\frac{1}{(1+2(1+ \varepsilon)\lambda)^{\frac{q-1}{2}}}.$ $$

Note that,

$$ $\displaystyle(1-2\lambda)(1+2(1+\varepsilon)\lambda)$ $\displaystyle=1+2\varepsilon\lambda-4(1+\varepsilon)\lambda^{2}$ $\displaystyle=1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}-\left(\frac{ \varepsilon}{2\sqrt{1+\varepsilon}}-2\sqrt{1+\varepsilon}\lambda\right)^{2}$ $$

By setting $\lambda=\frac{\varepsilon}{4(1+\varepsilon)}$ we get

$$ $\displaystyle\frac{1}{(1-2\lambda)^{\frac{q}{2}}}\cdot\frac{1}{(1+2(1+ \varepsilon)\lambda)^{\frac{q-1}{2}}}$ $\displaystyle=(1+2(1+\varepsilon)\lambda)^{\frac{1}{2}}[(1-2\lambda)(1+2(1+ \varepsilon)\lambda)]^{-\frac{q}{2}}$ $\displaystyle=\sqrt{1+\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1 +\varepsilon)}\right]^{-\frac{q}{2}}$ $$

This proves (43). In the similar way we prove (44):

$$ $\displaystyle\mathbb{P}\left(\frac{\|N\|^{2}}{\|M_{2\ldots q}\|^{2}}<1- \varepsilon\right)=\mathbb{P}(\lambda\|N\|^{2}<\lambda(1-\varepsilon)\|M_{2 \ldots q}\|^{2})$ $\displaystyle=\mathbb{P}(\lambda(1-\varepsilon)\|M_{2\ldots q}\|^{2}-\lambda\| N\|^{2}>0)=\mathbb{P}(\exp[\lambda(1-\varepsilon)\|M_{2\ldots q}\|^{2}-\lambda \|N\|^{2}]>1)$ $\displaystyle\leq\mathbb{E}[e^{\lambda(1-\varepsilon)\|M_{2\ldots q}\|^{2}- \lambda\|N\|^{2}}]\leq\frac{1}{(1+2\lambda)^{\frac{q}{2}}}\cdot\frac{1}{(1-2(1 -\varepsilon)\lambda)^{\frac{q-1}{2}}}.$ $$

Note that,

$$ $\displaystyle(1+2\lambda)(1-2(1-\varepsilon)\lambda)$ $\displaystyle=1+2\varepsilon\lambda-4(1-\varepsilon)\lambda^{2}$ $\displaystyle=1+\frac{\varepsilon^{2}}{4(1-\varepsilon)}-\left(\frac{ \varepsilon}{2\sqrt{1-\varepsilon}}-2\sqrt{1-\varepsilon}\lambda\right)^{2}$ $$

By setting $\lambda=\frac{\varepsilon}{4(1-\varepsilon)}$ we get

$$ $\displaystyle\frac{1}{(1+2\lambda)^{\frac{p}{2}}}\cdot\frac{1}{(1-2(1- \varepsilon)\lambda)^{\frac{q-1}{2}}}$ $\displaystyle=(1-2(1-\varepsilon)\lambda)^{\frac{1}{2}}[(1+2\lambda)(1-2(1- \varepsilon)\lambda)]^{-\frac{q}{2}}$ $\displaystyle=\sqrt{1-\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{4(1 -\varepsilon)}\right]^{-\frac{q}{2}}$ $$

This completes the proof.
∎

###### Corollary A.26 .

We have

$$ $\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots q}\|}>\sqrt{1+\varepsilon}\right)+ \mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots q}\|}<\sqrt{1-\varepsilon}\right) \leq 2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-\frac{q}{2}}$ (45) $$

###### Proof.

Using (43), (44) and the Cauchy-Schwarz inequality we have

$$ $\displaystyle\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots q}\|}>\sqrt{1+ \varepsilon}\right)+\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots q}\|}<\sqrt{1- \varepsilon}\right)$ $\displaystyle\leq\sqrt{1+\frac{\varepsilon}{2}}\left[1+\frac{\varepsilon^{2}}{ 4(1+\varepsilon)}\right]^{-\frac{q}{2}}+\sqrt{1-\frac{\varepsilon}{2}}\left[1+ \frac{\varepsilon^{2}}{4(1-\varepsilon)}\right]^{-\frac{q}{2}}$ $\displaystyle\leq\sqrt{1+\frac{\varepsilon}{2}+1-\frac{\varepsilon}{2}}\cdot \sqrt{\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)}\right]^{-q}+\left[1+ \frac{\varepsilon^{2}}{4(1-\varepsilon)}\right]^{-q}}$ $\displaystyle\leq\sqrt{2}\cdot\sqrt{2\left[1+\frac{\varepsilon^{2}}{4(1+ \varepsilon)}\right]^{-q}}=2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon)} \right]^{-\frac{q}{2}}$ $$

∎

###### Lemma A.24 .

###### Proof.

###### Lemma A.25 .

###### Proof.

###### Corollary A.26 .

###### Proof.

#### Proof of the concentration result

We need one more lemma to have everything for the proof.

###### Lemma A.27 .

Given $\varepsilon\in(0,0.08]$, $\left|\frac{M_{1}}{\|M_{2\ldots q}\|}\right|<\varepsilon/2$ and $\sqrt{1-\varepsilon}<\frac{\|N\|}{\|M_{2\ldots q}\|}<\sqrt{1+\varepsilon}$, then

$$ $\left|\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right|\leq\frac{\varepsilon}{\sqrt{2}} (1-\rho^{2}).$ $$

###### Proof.

Recall, we used $\phi(s)=\frac{s}{\sqrt{1-s^{2}}}$ and let us define $\psi(h):=\phi^{-1}(h)=\frac{h}{\sqrt{1+h^{2}}}$. Note that
$\psi^{\prime}(h)=\frac{1}{(1+h^{2})^{3/2}}>0$, hence $\psi$ is an increasing function.
We have

$$ $\displaystyle\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}=\psi\left(\frac{\rho\|N\|+M_{1}\sqrt {1-\rho^{2}}}{\|M_{2\ldots q}\|\sqrt{1-\rho^{2}}}\right)=\psi\left(\frac{\rho} {\sqrt{1-\rho^{2}}}\frac{\|N\|}{\|M_{2\ldots q}\|}+\frac{M_{1}}{\|M_{2\ldots q }\|}\right).$ $$

and

$$ $\rho=\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right).$ $$

We will prove the claim for the case when $\rho\geq 0$; the other case is proven in a similar way.
Using non-negativity of $\rho$ and the fact that $\psi$ is increasing, we have

$$ $\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon }{2}\right)-\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right)\\ \leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\\ \psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1+\varepsilon}+\frac{\varepsilon }{2}\right)-\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right).$ (46) $$

Using Lemma A.42 (a) we can estimate the upper bound:

$$ $\displaystyle\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1+\varepsilon}+ \frac{\varepsilon}{2}\right)-\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right)$ $\displaystyle\leq\left(1+\frac{\rho^{2}}{1-\rho^{2}}\right)^{-3/2}\cdot\left[ \frac{\rho}{\sqrt{1-\rho^{2}}}(\sqrt{1+\varepsilon}-1)+\frac{\varepsilon}{2}\right]$ $\displaystyle\leq(1-\rho^{2})^{3/2}\left[\frac{\rho}{\sqrt{1-\rho^{2}}}\frac{ \varepsilon}{2}+\frac{\varepsilon}{2}\right]$ $\displaystyle\leq(1-\rho^{2})\frac{\varepsilon(\rho+\sqrt{1-\rho^{2}})}{2}.$ (47) $$

Since $\rho+\sqrt{1-\rho^{2}}\leq\sqrt{2}$, we have

$$ $\eqref{eq:ineq_cos_1a}\leq(1-\rho^{2})\frac{\varepsilon}{\sqrt{2}}.$ (48) $$

To prove the lower bound in (46), we first need to note that $\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}$ can be negative or very close to 0 0. For that reason, we will
have to consider two cases: $\rho^{2}\leq\varepsilon$ or $\rho^{2}>\varepsilon$.

If $\rho^{2}>\varepsilon$,

$$ $\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}\geq\sqrt{\varepsilon}>\varepsilon.$ (49) $$

we have

$$ $\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\geq \frac{\varepsilon}{2}>0,$ (50) $$

and in particular

$$ $\rho\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\sqrt{1-\rho^{2}}>0.$ (51) $$

Let

$$ $A:=\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right)=\rho>0,$ $$

and

$$ $B:=\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{ \varepsilon}{2}\right)>0.$ $$

From (50) we have $B\geq 0$, and hence since $\psi$ is an increasing function we have $A>B>0$.

We obtain

$$ $\displaystyle A-B=\rho-\frac{\rho\sqrt{1-\varepsilon}-\varepsilon/2\sqrt{1- \rho^{2}}}{\sqrt{(\rho\sqrt{1-\varepsilon}-\varepsilon/2\sqrt{1-\rho^{2}})^{2} +(1-\rho^{2})}}$ $\displaystyle\stackrel{{\scriptstyle\textrm{Lemma}\ \ref{lemma: denominatorBounds}.}}{{\leq}}\rho-\frac{\rho\sqrt{1-\varepsilon}-\varepsilon/2 \sqrt{1-\rho^{2}}}{\sqrt{1-\varepsilon\rho^{2}}}=\rho\underbrace{\left(1-\frac {\sqrt{1-\varepsilon}}{\sqrt{1-\varepsilon\rho^{2}}}\right)}_{\leq 0}+\frac{ \varepsilon\sqrt{1-\rho^{2}}}{2\sqrt{1-\varepsilon\rho^{2}}}$ $\displaystyle\leq\frac{\varepsilon\sqrt{1-\rho^{2}}}{2\sqrt{1-\varepsilon\rho^ {2}}}\leq\frac{\varepsilon\sqrt{1-\rho^{2}}}{2\sqrt{1-\varepsilon\rho^{2}}} \cdot\frac{\sqrt{1-\rho^{2}}}{\sqrt{1-\varepsilon\rho^{2}}}\leq\frac{ \varepsilon(1-\rho^{2})}{2(1-\varepsilon\rho^{2})}\leq\frac{\varepsilon(1-\rho ^{2})}{2(1-\varepsilon)}$ (52) $$

Since $\varepsilon\in(0,\frac{1}{4}]$, we have $\frac{1}{2(1-\varepsilon)}\leq\frac{2}{3}<\frac{\sqrt{2}}{2}=\frac{1}{\sqrt{2}}$ and hence

$$ $\eqref{eq:ineq_cos_2a}\leq\frac{\varepsilon(1-\rho^{2})}{\sqrt{2}}$ (53) $$

On the other hand, if $\rho^{2}\leq\varepsilon$, Lemma A.42 (b) implies:

$$ $\displaystyle\psi\left(\frac{\rho}{\sqrt{1-\rho^{2}}}\right)-\psi\left(\frac{ \rho}{\sqrt{1-\rho^{2}}}\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\right)$ $\displaystyle\leq\left[\frac{\rho}{\sqrt{1-\rho^{2}}}(1-\sqrt{1-\varepsilon})+ \frac{\varepsilon}{2}\right]=\left[\frac{\rho}{\sqrt{1-\rho^{2}}}\cdot\frac{ \varepsilon}{1+\sqrt{1-\varepsilon}}+\frac{\varepsilon}{2}\right]$ $\displaystyle=\varepsilon\left[\frac{\rho}{\sqrt{1-\rho^{2}}}\frac{1}{1+\sqrt{ 1-\varepsilon}}+\frac{1}{2}+\frac{\rho^{2}}{\sqrt{2}}\right]-\frac{\varepsilon }{\sqrt{2}}\rho^{2}.$ (54) $$

Since $\rho^{2}\leq\varepsilon$, we have $\rho\in[0,\varepsilon]$ and

$$ $\frac{\rho}{\sqrt{1-\rho^{2}}}\frac{1}{1+\sqrt{1-\varepsilon}}+\frac{1}{2}+ \frac{\rho^{2}}{\sqrt{2}}\leq\frac{\sqrt{\varepsilon}}{\sqrt{1-\varepsilon}+1- \varepsilon}+\frac{1}{2}+\frac{\varepsilon}{\sqrt{2}}.$ $$

This expression is increasing for $\varepsilon\in(0,1)$, so

$$ $\displaystyle\leq\left.\frac{\sqrt{\varepsilon}}{\sqrt{1-\varepsilon}+1- \varepsilon}+\frac{1}{2}+\frac{\varepsilon}{\sqrt{2}}\right|_{\varepsilon=0.08 }\approx 0.70708<\frac{1}{\sqrt{2}}.$ $$

Therefore,

$$ $\eqref{eq:ineq_cos_3a}\leq\frac{\varepsilon(1-\rho^{2})}{\sqrt{2}}$ (55) $$

Finally, the inequalities (48), (53) and (55) prove the claim.
∎

###### Proof of Theorem A.23 .

Since $\varepsilon\in(0,0.055]$, we have $\varepsilon\sqrt{2}\in(0,0.08]$, then
by Lemma A.27 we have

$$ $\displaystyle\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\right| \geq\varepsilon(1-\rho^{2})\right)=\mathbb{P}\left(\left|\frac{(Rx,Ry)}{\|Rx\| \|Ry\|}-\rho\right|\geq\frac{\varepsilon\sqrt{2}}{\sqrt{2}}(1-\rho^{2})\right)$ $\displaystyle\leq\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots q}\|}>\frac{ \varepsilon\sqrt{2}}{2}\right)+\mathbb{P}\left(\frac{M_{1}}{\|M_{2\ldots q}\|} <-\frac{\varepsilon\sqrt{2}}{2}\right)$ $\displaystyle+\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots q}\|}>\sqrt{1+ \varepsilon\sqrt{2}}\right)+\mathbb{P}\left(\frac{\|N\|}{\|M_{2\ldots q}\|}< \sqrt{1-\varepsilon\sqrt{2}}\right).$ $$

Using Lemma A.24 and Corollary A.26 we have

$$ $\displaystyle\leq 2\left[1+\frac{\varepsilon^{2}}{2}\right]^{-\frac{q-1}{2}}+2 \left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}$ $\displaystyle=(2+\varepsilon^{2})\left[1+\frac{\varepsilon^{2}}{2}\right]^{- \frac{q}{2}}+2\left[1+\frac{\varepsilon^{2}}{4(1+\varepsilon\sqrt{2})}\right]^ {-\frac{q}{2}}$ $\displaystyle\leq(2+\varepsilon^{2})\left[1+\frac{\varepsilon^{2}}{4(1+ \varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}+2\left[1+\frac{\varepsilon^{2}}{4( 1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}$ $\displaystyle=(4+\varepsilon^{2})\left[1+\frac{\varepsilon^{2}}{4(1+ \varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}.$ $$

∎

###### Lemma A.27 .

###### Proof.

###### Proof of Theorem A.23 .

#### A.IV.4 Johnson-Lindenstrauss-type Result

###### Theorem A.28 .

Let $\varepsilon\in(0,0.05]$, $\delta\in(0,1)$ and $p_{1},\ldots,p_{k}$ be non-zero vectors in $\mathbb{R}^{n}$. If

$$ $q\geq\frac{2\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{ \delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})} \right]}$ (56) $$

then, with probability $1-\delta$, the inequality

$$ $\left|\frac{(Rp_{j},Rp_{i})}{\|Rp_{j}\|\|Rp_{i}\|}-\frac{(p_{j},p_{i})}{\|p_{j }\|\|p_{i}\|}\right|\leq\varepsilon(1-\rho^{2})$ $$

holds for all $i<j$.

###### Proof.

Define

$$ $W_{ij}:=\left(\left|\frac{(Rp_{j},Rp_{i})}{\|Rp_{j}\|\|Rp_{i}\|}-\frac{(p_{j}, p_{i})}{\|p_{j}\|\|p_{i}\|}\right|\leq\varepsilon(1-\rho^{2})\right).$ $$

To prove the theorem, it suffices to show that $\mathbb{P}\left(\bigcup_{i<j}W_{ij}^{c}\right)<\delta$.

By Theorem A.23, we have

$$ $\mathbb{P}\left(\bigcup_{i<j}W_{ij}^{c}\right)=\sum_{i<j}\mathbb{P}\left(W_{ij }^{c}\right)=\frac{k(k-1)}{2}\cdot 4\left(1+\frac{\varepsilon^{2}}{4}\right) \cdot\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]^{-\frac{q }{2}}.$ $$

This expression is less than $\delta$ by the choice of $q$ in (58).
∎

###### Theorem A.28 .

###### Proof.

#### A.IV.5 Result comparison analysis

In this section, we state Lemma 5 from [], which gives a similar result to Theorem A.23, and compare the two results.

###### Lemma A.29 .

For $x$ and $y$ non-zero vectors in $\mathbb{R}^{n}$ and for every $\beta\in(0,1/2)$, we have

$$ $-\frac{\beta}{1-\beta}(1-\rho)\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\frac{ \beta}{1+\beta}(1-\rho)$ $$

if $\rho\leq-\varepsilon$,

$$ $-\frac{\beta}{1-\beta}(1-\rho)\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\frac{ \beta}{1-\beta}(1+\rho)$ $$

if $-\varepsilon\leq\rho\leq\varepsilon$,

$$ $-\frac{\beta}{1+\beta}(1+\rho)\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\frac{ \beta}{1-\beta}(1+\rho)$ $$

if $\rho\geq\varepsilon$. Moreover, the inequality holds true with probability at least $1-8e^{-\frac{q}{4}(\beta^{2}-\beta^{2})}.$

###### Remark A.30 .

We observe that Lemma A.29 does not capture the fact that when $\rho=\pm 1$, the random projection preserves the cosine similarity, as discussed in §A.IV.1.

Also, the role of $\beta$ is unclear. If we set $\varepsilon=\max\{\frac{\beta}{1-\beta},\frac{\beta}{1+\beta}\}=\frac{\beta}{1
-\beta}$, the result can be rewritten as

$$ $-\varepsilon(1+|\rho|)\leq\frac{(Rx,Ry)}{\|Rx\|\|Ry\|}-\rho\leq\varepsilon(1+| \rho|),$ (57) $$

with probability at least $1-8e^{-\frac{q}{4}\cdot\frac{\varepsilon^{2}}{(1+\varepsilon)^{2}}}$.

We note that the inequality (57) is less precise than the one provided by Theorem A.23.

Moreover, by Lemma A.41, we have $\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]^{-\frac{q}{2}}
\leq e^{-\frac{q}{4}\cdot\frac{\varepsilon^{2}}{(1+\varepsilon)^{2}}}$. Therefore, the inequality in Theorem A.23 also holds with higher probability.

We remark that Theorem A.23 requires $\varepsilon\in(0,0.05]$, but this is a reasonable absolute error for cosine similarity, which ranges from 0 0 to $1$.

We will see how the dimension selection in Theorem A.28 for cosine similarity compares with the similar result in original Johnson-Lindenstrauss Lemma.
The following version is based on Theorem 2.13 and Remark 2.11 from [] and we present it without proof.

###### Theorem A.31 .

Let $\varepsilon,\delta\in(0,1)$, and $p_{1},\ldots,p_{k}$ be non-zero vectors in $\mathbb{R}^{n}$. If

$$ $q\geq\frac{4}{\varepsilon^{2}}\log\left[\frac{k^{2}}{\delta}\right]$ (58) $$

then, with probability at least $1-\delta$, the inequality

$$ $(1-\varepsilon)\|p_{i}-p_{j}\|^{2}\leq\|R(p_{i}-p_{j})\|^{2}\leq(1+\varepsilon )\|p_{i}-p_{j}\|^{2}$ (59) $$

holds for all $i<j$.

In the following we will use the notation $f\sim g$ that will denote

$$ $\lim_{\varepsilon\to 0^{+}}\frac{f(\varepsilon)}{g(\varepsilon)}=1.$ $$

This is a standard tool to analyze asymptotic behavior.

###### Proposition A.32 .

For a fixed, $\delta$ and $k$ we have

$$ $\frac{2\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{4}\right)}{\delta} \right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]} \sim\frac{4}{\varepsilon^{2}}\ln\left[\frac{2k(k-1)}{\delta}\right].$ $$

###### Proof.

Using L’Hospital’s rule one can show $\lim_{x\to 0^{+}}\frac{\log(1+x)}{x}=1$, hence

$$ $\lim_{\varepsilon\to 0^{+}}\frac{\ln\left[1+\frac{\varepsilon^{2}}{2(1+ \varepsilon\sqrt{2})}\right]}{\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})} }=1.$ (60) $$

Simple limit calculus gives us

$$ $\lim_{\varepsilon\to 0^{+}}\frac{\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2 })}}{\frac{\varepsilon^{2}}{2}}=\lim_{\varepsilon\to 0^{+}}\frac{1}{1+ \varepsilon\sqrt{2}}=1.$ (61) $$

Hence, multiplying expressions in (60) and (61) we get:

$$ $\lim_{\varepsilon\to 0^{+}}\frac{\ln\left[1+\frac{\varepsilon^{2}}{2(1+ \varepsilon\sqrt{2})}\right]}{\frac{\varepsilon^{2}}{2}}=1.$ (62) $$

Furthermore, by continuity of the function $\ln$ we have

$$ $\lim_{\varepsilon\to 0^{+}}\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2} }{4}\right)}{\delta}\right]=\ln\left[\frac{2k(k-1)}{\delta}\right].$ (63) $$

The claim now follows from (62) and (63).
∎

The comparison in Proposition A.32 tells us that the dimension $q$ will be of the same order but slightly higher. This is illustrated on Figure 5.

Figure: Figure 5: Simulated random projection for $k=10,000,000$, $\delta=0.05$ the upper (red) curve represents the graph of $\varepsilon\mapsto\frac{2\ln\left[\frac{2k(k-1)\left(1+\frac{\varepsilon^{2}}{ 4}\right)}{\delta}\right]}{\ln\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon \sqrt{2})}\right]}$ (minimum value of $q$ for cosine similarity) and the lower (blue) curve $\varepsilon\mapsto\frac{4}{\varepsilon^{2}}\ln\left[\frac{k^{2}}{\delta}\right]$ (minimum value of $q$ for Johnson-Lindenstrauss Lemma). We can see that the two curves are very close.
Refer to caption: extracted/5761948/minDimRhoVsNorm.png

###### Lemma A.29 .

###### Remark A.30 .

###### Theorem A.31 .

###### Proposition A.32 .

###### Proof.

### 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.V.1 Useful concentration inequalities

In this paper we will depend on the results from concentration inequality theory. The approach in this paper is adapted based on the book []. In this subsection we adapted results from Chapter 2 of the book.

###### Theorem A.33 .

Let $X$ be a random variable such that $v>0$, $c>0$ we have

$$ $\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{v\lambda^{2}}{2(1-c\lambda)}$ (64) $$

for every $\lambda\in(0,c^{-1})$. Then for $t\geq 0$ we have

$$ $\mathbb{P}(X-\mathbb{E}X>t)\leq\exp\left(\frac{-t^{2}}{2(v+ct)}\right)$ $$

###### Proof.

Using Markov inequality, for $\lambda\in(0,c^{-1})$ we have

$$ $\mathbb{P}(X-\mathbb{E}X>t)\leq\frac{\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]}{e ^{\lambda t}}\leq\exp\left(\frac{v\lambda^{2}}{2(1-c\lambda)}-\lambda t\right).$ $$

Hence,

$$ $\mathbb{P}(X-\mathbb{E}X>t)\leq\exp\left[-\sup_{\lambda\in(0,c^{-1})}\left( \lambda t-\frac{v\lambda^{2}}{2(1-c\lambda)}\right)\right].$ $$

Using usual calculus techniques we get (see Lemma A.39 for details)

$$ $\sup_{\lambda\in(0,c^{-1})}\left(\lambda t-\frac{v\lambda^{2}}{2(1-c\lambda)} \right)=\frac{v}{c^{2}}h\left(\frac{ct}{v}\right),$ $$

where $h(s)=1+s-\sqrt{1+2s}$. By Lemma A.37 we have $h(s)\geq\frac{s^{2}}{2(1+s)}$ for $s>0$ and the claim follows.
∎

The following Corollary explains what happens when $c=0$ in (64).

###### Theorem A.34 .

Let $X$ be a random variable such that $v>0$ we have

$$ $\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{v\lambda^{2}}{2}$ (65) $$

for every $\lambda\geq 0$. Then for $t\geq 0$ we have

$$ $\mathbb{P}(X-\mathbb{E}X>t)\leq\exp\left(\frac{-t^{2}}{2v}\right).$ $$

###### Proof.

Using Markov inequality, for $\lambda\geq 0$ we have

$$ $\displaystyle\mathbb{P}(X-\mathbb{E}X>t)$ $\displaystyle\leq\frac{\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]}{e^{\lambda t}} \leq\exp\left(\frac{v\lambda^{2}}{2}-\lambda t\right)$ $\displaystyle=\exp\left(\frac{v\lambda^{2}}{2}-\lambda t+\frac{t^{2}}{2v}- \frac{t^{2}}{2v}\right)$ $\displaystyle=\exp\left(\frac{1}{2}\left(\lambda v^{1/2}-tv^{-1/2}\right)^{2}- \frac{t^{2}}{2v}\right).$ $$

Setting $\lambda=t/v$ the claim follows.
∎

###### Proposition A.35 .

If for a given $p>0$ and $c>0$ the inequality

$$ $\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{e^{-\lambda p}}{(1-c\lambda)^{ p/c}}$ (66) $$

holds for all $\lambda<c^{-1}$, then the following claims hold:

(a) For all $\lambda\in(0,c^{-1})$

$$ $\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{pc\lambda^{2}}{2(1-c \lambda)}.$ (67) $$

(b) For all $\lambda\leq 0$

$$ $\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{pc\lambda^{2}}{2}.$ (68) $$

###### Proof.

(a) Using the inequality $-\log(1-s)-s\leq\frac{s^{2}}{2(1-s)}$ for $s\in(0,1)$ (see Lemma A.38 (a)) we have:

$$ $\displaystyle\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq-\lambda p-\frac{p} {c}\log(1-c\lambda)$ $\displaystyle=\frac{p}{c}(-\log(1-c\lambda)-c\lambda)\leq\frac{p}{c}\cdot\frac {(c\lambda)^{2}}{2(1-c\lambda)}=\frac{pc\lambda^{2}}{2(1-c\lambda)}.$ $$

(b) Using inequality $-\log(1-s)-s\leq\frac{s^{2}}{2}$ for $s<0$ (see Lemma A.38 (b)) we have:

$$ $\displaystyle\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq-\lambda p-\frac{p} {c}\log(1-c\lambda)$ $\displaystyle=\frac{p}{c}(-\log(1-c\lambda)-c\lambda)\leq\frac{p}{c}\cdot\frac {(c\lambda)^{2}}{2}=\frac{pc\lambda^{2}}{2}.$ $$

∎

###### Corollary A.36 .

If for a given $p>0$ and $c>0$ we have

$$ $\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{e^{-\lambda p}}{(1-c \lambda)^{p/c}}$ (69) $$

for all $\lambda<c^{-1}$, then for all $t\geq 0$

$$ $\mathbb{P}(X-\mathbb{E}X>t)\leq\exp\left(\frac{-t^{2}}{2(pc+ct)}\right),$ (70) $$

and

$$ $\mathbb{P}(X-\mathbb{E}X<-t)\leq\exp\left(\frac{-t^{2}}{2pc}\right).$ (71) $$

###### Proof.

From Proposition A.35 we know that (67) holds. Now, by Theorem A.33, inequality (70) holds.

From Proposition A.35 we know that (68) holds. If we substitute $\lambda\mapsto-\lambda$ and $X\mapsto-X$ in (68) we have

$$ $\log\mathbb{E}[e^{\lambda(-X+\mathbb{E}X)}]\leq\frac{pc\lambda^{2}}{2}$ $$

for $\lambda\geq 0$. Hence, using Theorem A.35 we get (71).
∎

###### Theorem A.33 .

###### Proof.

###### Theorem A.34 .

###### Proof.

###### Proposition A.35 .

###### Proof.

###### Corollary A.36 .

###### Proof.

#### A.V.2 Technical inequalities

###### Lemma A.37 .

For $s\geq 0$ we have

$$ $1+s-\sqrt{1+2s}\geq\frac{s^{2}}{2(1+s)}.$ $$

###### Proof.

For $s>0$ we have:

$$ $\displaystyle 1+s-\sqrt{1+2s}$ $\displaystyle=(1+s-\sqrt{1+2s})\cdot\frac{1+s+\sqrt{1+2s}}{1+s+\sqrt{1+2s}}$ $\displaystyle=\frac{(1+s)^{2}-1+2s}{1+s+\sqrt{1+2s}}=\frac{s^{2}}{1+s+\sqrt{1+ 2s}}\geq\frac{s^{2}}{2(1+s)}.$ $$

The last inequality follows from the fact that $1+s=\sqrt{1+2s+s^{2}}>\sqrt{1+2s}$.
∎

###### Lemma A.38 .

(a) For $s\in(0,1)$ we have
$-\log(1-s)-s\leq\frac{s^{2}}{2(1-s)}$.

(b) For $s<0$ we have $-\log(1-s)-s\leq\frac{s^{2}}{2}$.

###### Proof.

Not that for $f(s)=-\log(1-s)-s$ we have
$f^{\prime}(s)=\frac{1}{1-s}-1=\frac{s}{1-s}$.
Hence, in the case of (a), it follows for $s\in(0,1)$

$$ $\displaystyle-\log(1-s)-s$ $\displaystyle=f(s)-f(0)=\int_{0}^{s}f^{\prime}(t)\,dt$ $\displaystyle=\int_{0}^{s}\frac{t}{1-t}\,dt\leq\int_{0}^{s}\frac{t}{1-s}\,dt= \frac{1}{1-s}\int_{0}^{s}t\,dt=\frac{s^{2}}{2(1-s)}.$ $$

In the case of (b), for $s<0$ we can apply a similar argument:

$$ $\displaystyle-\log(1-s)-s$ $\displaystyle=f(s)-f(0)=\int_{0}^{s}f^{\prime}(t)\,dt$ $\displaystyle=\int_{0}^{s}\frac{t}{1-t}\,dt\leq\int_{s}^{0}\frac{-t}{1-t}\,dt \leq\int_{s}^{0}-t\,dt=\frac{s^{2}}{2}.$ $$

∎

###### Lemma A.39 .

For a given $t>0$, $v>0$ and $c>0$ the function

$$ $f(\lambda)=\lambda t-\frac{v\lambda^{2}}{2(1-c\lambda)}$ $$

has a maximum on interval $(0,c^{-1})$ at point $\lambda_{\mathrm{max}}=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}.$ and it equals

$$ $\frac{v}{c^{2}}\left(1+\frac{tc}{v}-\sqrt{1+2\cdot\frac{tc}{v}}\right).$ $$

###### Proof.

When we take the first derivative we get

$$ $f^{\prime}(\lambda)=t-\frac{v\lambda}{(1-c\lambda)}-\frac{vc\lambda^{2}}{2(1-c \lambda)^{2}}.$ $$

Setting $f^{\prime}(\lambda)=0$ and using the substitution $x=\frac{\lambda}{(1-c\lambda)}$, we get

$$ $-\frac{vc}{2}\cdot x^{2}-vx+t=0.$ $$

Solving this quadratic equation by $x$ we get

$$ $x_{1,2}=-\frac{1}{c}\pm\sqrt{\frac{1}{c^{2}}+\frac{2t}{vc}}.$ $$

Since the solution needs to be non-negative,

$$ $\displaystyle x$ $\displaystyle=-\frac{1}{c}+\sqrt{\frac{1}{c^{2}}+\frac{2t}{vc}}=-\frac{1}{c}+ \sqrt{\frac{v}{vc^{2}}+\frac{2tc}{vc^{2}}}$ $\displaystyle=\frac{-\sqrt{v}+\sqrt{v+2tc}}{c\sqrt{v}}=\frac{\sqrt{v+2tc}- \sqrt{v}}{c\sqrt{v}}.$ $$

Now, when we calculate $\lambda$ from $x$, we get

$$ $\lambda_{\mathrm{max}}=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}.$ $$

Note that, $\lambda_{\mathrm{max}}$ is the minimum since $f^{\prime}$ is a strictly decreasing function on $(0,c^{-1})$.
The value of the minimum is

$$ $\displaystyle f^{\prime}(\lambda_{\mathrm{max}})$ $\displaystyle=\lambda_{\mathrm{max}}\left(t-\frac{v}{2}\cdot\frac{\lambda_{ \mathrm{max}}}{1-c\lambda_{\mathrm{max}}}\right)=\lambda_{\mathrm{max}}\left(t -\frac{v}{2}\cdot x\right)$ $\displaystyle=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}\left(t-\frac{v}{2} \cdot\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v}}\right)$ $\displaystyle=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}\left(t-\frac{\sqrt{v }\sqrt{v+2tc}-v}{2c}\right)$ $\displaystyle=\frac{\sqrt{v+2tc}-\sqrt{v}}{c\sqrt{v+2tc}}\cdot\frac{2tc+v- \sqrt{v}\sqrt{v+2tc}}{2c}$ $\displaystyle=\frac{(\sqrt{v+2tc}-\sqrt{v})}{c}\cdot\frac{\sqrt{v+2tc}-\sqrt{v }}{2c}$ $\displaystyle=\frac{(\sqrt{v+2tc}-\sqrt{v})^{2}}{2c^{2}}=\frac{2v+2tc-2\sqrt{v ^{2}+2vtc}}{2c^{2}}$ $\displaystyle=\frac{v}{c^{2}}\left(1+\frac{tc}{v}-\sqrt{1+2\cdot\frac{tc}{v}} \right).$ $$

∎

###### Lemma A.40 .

For $\varepsilon\in(0,1)$ and $\rho^{2}\in[\varepsilon,1]$ we have

$$ $(\rho\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\sqrt{1-\rho^{2}})^{2}+1-\rho^{ 2}\leq 1-\varepsilon\rho^{2}.$ $$

###### Proof.

It is easy to show that $\rho\geq\varepsilon$ and $1-\varepsilon\geq 1-\rho^{2}$, hence

$$ $0\leq\rho\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\sqrt{1-\rho^{2}}\leq\rho \sqrt{1-\varepsilon}.$ (72) $$

Now, we have:

$$ $(\rho\sqrt{1-\varepsilon}-\frac{\varepsilon}{2}\sqrt{1-\rho^{2}})^{2}+1-\rho^{ 2}\stackrel{{\scriptstyle\eqref{eq:denominatorBounds1}}}{{\leq}}(\rho\sqrt{1- \varepsilon})^{2}+1-\rho^{2}=1-\varepsilon\rho^{2}$ $$

∎

###### Lemma A.41 .

For $\varepsilon\in(0,1)$ we have

$$ $\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right]^{-\frac{p}{2}} \leq e^{-\frac{p}{4}\cdot\frac{\varepsilon^{2}}{(1+\varepsilon)^{2}}}$ $$

###### Proof.

Using Lemma A.38(b) we have

$$ $\displaystyle\log\left(\left[1+\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2}) }\right]^{-\frac{p}{2}}\right)$ $\displaystyle=-\frac{p}{2}\cdot\log\left[1+\frac{\varepsilon^{2}}{2(1+ \varepsilon\sqrt{2})}\right]$ $\displaystyle\leq\frac{p}{2}\left[-\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt {2})}+\frac{1}{2}\left(\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}\right) ^{2}\right]$ (73) $$

Looking at the difference:

$$ $\displaystyle\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{2})}-\frac{ \varepsilon^{2}}{2(1+\varepsilon)^{2}}$ $\displaystyle=\frac{\varepsilon^{2}[(1+\varepsilon)^{2}-(1+\varepsilon\sqrt{2} )]}{2(1+\varepsilon)^{2}(1+\varepsilon\sqrt{2})}=\frac{\varepsilon^{2}[ \varepsilon(2-\sqrt{2})+\varepsilon^{2}]}{2(1+\varepsilon)^{2}(1+\varepsilon \sqrt{2})}$ $\displaystyle\geq\frac{\varepsilon^{2}[\varepsilon(2-\sqrt{2})+\varepsilon^{2} ]}{2(1+\varepsilon)^{2}(1+\varepsilon\sqrt{2})}\geq\frac{\varepsilon^{3}(2- \sqrt{2})[1+\frac{\varepsilon}{2-\sqrt{2}}]}{2(1+\varepsilon)^{2}(1+ \varepsilon\sqrt{2})}$ $\displaystyle\geq\frac{\varepsilon^{3}(2-\sqrt{2})[1+\varepsilon\sqrt{2}]}{2(1 +\varepsilon)^{2}(1+\varepsilon\sqrt{2})}\geq\frac{\varepsilon^{3}\cdot\frac{1 }{2}}{2(1+\varepsilon)^{2}}=\frac{\varepsilon^{3}}{4(1+\varepsilon)^{2}}$ $\displaystyle\geq\frac{1}{2}\left(\frac{\varepsilon^{2}}{2(1+\varepsilon\sqrt{ 2})}\right)^{2}$ $$

Hence, we have $\eqref{eq:appLogLemma}\leq-\dfrac{p}{4}\cdot\dfrac{\varepsilon^{2}}{(1+
\varepsilon)^{2}}$.
∎

###### Lemma A.37 .

###### Proof.

###### Lemma A.38 .

###### Proof.

###### Lemma A.39 .

###### Proof.

###### Lemma A.40 .

###### Proof.

###### Lemma A.41 .

###### Proof.

#### A.V.3 Special Case of Mean Value Theorem

###### Lemma A.42 .

Let $\psi(h)=\frac{h}{\sqrt{1+h^{2}}}$, then $\psi^{\prime}(h)=\frac{1}{(1+h^{2})^{3/2}}$.
Furthermore, we have the following inequalities:

(a) For $0\leq a<b$ we have

$$ $\psi(b)-\psi(a)\leq\psi^{\prime}(a)(b-a).$ $$

(b) For $a<0<b$ we have

$$ $\psi(b)-\psi(a)\leq b-a.$ $$

###### Proof.

Using product rule for derivatives

$$ $\displaystyle\psi^{\prime}(h)$ $\displaystyle=\frac{(h)^{\prime}\sqrt{1+h^{2}}-h(\sqrt{1+h^{2}})^{\prime}}{1+h ^{2}}=\frac{\sqrt{1+h^{2}}-h\cdot\frac{h}{\sqrt{1+h^{2}}}}{1+h^{2}}$ $\displaystyle=\frac{1+h^{2}-h^{2}}{(1+h^{2})^{3/2}}=\frac{1}{(1+h^{2})^{3/2}}.$ $$

For $a<b$ we have

$$ $\psi(b)-\psi(a)=\int_{a}^{b}\psi^{\prime}(h)\,dh\leq\max_{s\in[a,b]}\psi^{ \prime}(s)\int_{a}^{b}\,du=\max_{s\in[a,b]}\psi^{\prime}(s)(b-a).$ $$

It is not hard to see

$$ $\max_{h\in[a,b]}\psi^{\prime}(h)=\begin{cases}\psi^{\prime}(a)&0\leq a<b\\ \psi^{\prime}(0)=1&a<0<b\end{cases}$ $$

∎

###### Lemma A.42 .

###### Proof.

## Appendix B Results for RP Dot Product when P = A 𝑃 𝐴 P=A italic_P = italic_A

### B.I RP Dot Product when P = A 𝑃 𝐴 P=A italic_P = italic_A

This section contains analogous results to §2.1 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\in H^{\gamma}_{c}$ and $v\in L_{c}$.

###### Theorem B.1 .

Let $X=AR^{\top}$. Then, the following claims hold:
(a) Asymptotic result. For $u,v\in V$

$$ $X_{u*}X_{v*}^{\top}\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left(n_{uv}, \frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}\right),$ (74) $$

(b) Finite-sample result. For $\varepsilon\in(0,1)$ and $\delta\in(0,1)$ if $q\geq 4\frac{1+\varepsilon}{\varepsilon^{2}}\log\left[\frac{n(n-1)}{\delta}\right]$
then

$$ $|X_{u*}X_{v*}^{\top}-n_{uv}|<\varepsilon\sqrt{n_{uu}n_{vv}}$ (75) $$

holds with probability at least $1-\delta$.

###### Proof.

From part (a) of Theorem A.6, we can represent $X_{u*}X_{v*}^{\top}$ as sum of $q$ i.i.d random variables and a convenient term. From this, we can show asymptotic normality and get concentration results that lead to a JL Lemma-type result. These are described in the Proposition A.1.

Since $X_{u*}=A_{u*}R^{\top}$ and $X_{v*}=A_{v*}R^{\top}$, claim (a) follows from (13) and parts (a) and (b) of Lemma 2.1.
Since $n=k=\|V\|$, claim (b) follows from part (b) of Proposition A.1.
∎

Let us fix $v\in L_{c}$ and look at the set $\{X_{u*}X_{v*}^{\top}\,:\,u\in H_{c}\}$. We will show that these calculations can severely overvalue (or undervalue) the relevance values $\{A_{u*}A_{v*}^{\top}\,:\,u\in H_{c}\}$ they approximate. This will be a consequence of the two following lemmas.

###### Lemma B.2 .

If $v\in L_{c}$ and $u\in H^{\gamma}_{c}$, then the standard deviation in (74) is greater than $\gamma d_{v}$, i.e.:

$$ $\gamma d_{v}\leq\sqrt{\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}}$ (76) $$

###### Proof.

We have $\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{
{\geq}}\frac{d_{u}d_{v}+n_{uv}^{2}}{q}\stackrel{{\scriptstyle u\in H_{c}}}{{
\geq}}\frac{\gamma^{2}cqd_{v}+n_{uv}^{2}}{q}\geq\gamma^{2}cd_{v}\stackrel{{
\scriptstyle v\in L_{c}}}{{\geq}}(\gamma d_{v})^{2}$.
∎

###### Lemma B.3 .

If $v\in L_{c}$ and $u\in H_{c}$, the standard deviation in $\eqref{eq:dotANormalityPA}$ is greater than its expectation, i.e.:

$$ $n_{uv}\leq\sqrt{\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}}.$ (77) $$

###### Proof.

We have $\sqrt{\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}}\stackrel{{\scriptstyle\eqref{eq:
STDGeDegree}}}{{\geq}}\gamma d_{v}\stackrel{{\scriptstyle\eqref{eq:MConnection
}}}{{\geq}}n_{uv}$.
∎

Under the conditions of Lemma B.3, we can produce the approximate one-sigma confidence interval

$$ $\left[n_{uv}-\sqrt{\frac{n_{uu}n_{vv}+n_{uv}^{2}}{q}},n_{uv}+\sqrt{\frac{n_{uu }n_{vv}+n_{uv}^{2}}{q}}\right]$ $$

in which we can expect $X_{u*}X_{v*}^{\top}$ to take values with less than $69\%$ probability, based on (74). This means that getting a value outside that interval is not unlikely. In that case, from (77), we know such values will more than double $n_{uv}$ or be less than 0 0, a poor approximation. On the other hand, if we look at the values $(X_{w*}X_{v*}^{\top}\,:\,w\in L_{c})$, we can see that the variance in (74) is bounded as

$$ $\frac{n_{ww}n_{vv}+n_{wv}^{2}}{q}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{ {\leq}}\frac{d_{w}^{2}d_{v}^{2}+d_{w}^{2}d_{v}^{2}}{q}\stackrel{{\scriptstyle w ,v\in L_{c}}}{{\leq}}c^{4}\frac{2}{q}.$ $$

Hence, in this case we can produce the three-sigma interval
$\left[n_{wv}-3c^{2}\sqrt{\frac{2}{q}},n_{wv}+3c^{2}\sqrt{\frac{2}{q}}\right],$
where $X_{w*}X_{v*}^{\top}$ will take values with more than $99\%$ probability, which is a small deviation.

Further, setting the random projection dimension $q$ according to (A.1), i.e.,
$q=\left\lceil\frac{1+\varepsilon}{\varepsilon}\log\left[\frac{n(n-1)}{\delta}
\right]\right\rceil$,
we fulfill the finite-sample result in part (b) of Theorem B.1. However, for large values of $\sqrt{n_{uu}n_{vv}}$ (c.f., the denominator of 75), we note that the bounds in  (75) become looser, thus larger approximation errors ensue. This will happen for vertices $u\in H^{\gamma}_{c}$, since $n_{uu}\geq d_{u}$. As a simple numerical illustration, assume $A\in\{0,1\}^{n\times n}$ such that $n_{uu}=d_{u}$ and $n_{vv}=d_{v}$. Let $\varepsilon=10^{-2}$ , $d_{u}=10^{7}$, $d_{v}=10$ and $n_{uv}=1$. Then, (75) yields $X_{u*}X_{v*}^{\top}\in(1-100,1+100)$.

The following is a technical lemma that we refer to in §2.1.

###### Lemma B.4 .

- (a)
For $u,v\in V$ and $v$ satisfying (4) we have
$\frac{n_{uv}}{d_{u}d_{v}}\leq\frac{\gamma}{d_{u}};$
(78)
$\frac{\sqrt{n_{vv}}}{d_{v}}\frac{1}{\sqrt{d_{u}}}\leq\frac{\sqrt{n_{uu}n_{vv}}
}{d_{u}d_{v}}\leq\sqrt{\frac{\gamma}{d_{v}}}\frac{1}{\sqrt{d_{u}}}.$
(79)
- (b)
For $u\in H^{\gamma}_{c}$ and $v\in L_{c}$ we have $\frac{\gamma}{d_{u}}\leq\sqrt{\frac{1}{q}\left[\frac{n_{uu}n_{vv}}{d_{u}^{2}d_
{v}^{2}}+\left(\frac{n_{u,v}}{d_{u}d_{v}}\right)^{2}\right]}$.

###### Proof.

For (78), we multiply the inequality (4) with $(d_{u})^{-1}$.
We have $d_{u}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{{\leq}}n_{uu}\stackrel{{
\scriptstyle\eqref{eq:MConnection}}}{{\leq}}\gamma d_{u}$ and multiplying the last inequality by $\frac{n_{vv}}{d_{u}^{2}d_{v}^{2}}$ and taking square roots (79) follows.

Part (b) follows from (76) by multiplying this inequality with $(d_{u}d_{v})^{-1}$.
∎

###### Theorem B.1 .

###### Proof.

###### Lemma B.2 .

###### Proof.

###### Lemma B.3 .

###### Proof.

###### Lemma B.4 .

###### Proof.

### B.II Instability of Ranking for Dot Product when P = A 𝑃 𝐴 P=A italic_P = italic_A

This section is analogous to §3.1. Recall, $\mathrm{rel}_{uv}=A_{u*}A_{v*}$ and $\mathrm{rel}^{R}_{uv}=A_{u*}R^{\top}RA_{v*}^{\top}$.

The following lemma will help us in our considerations.

###### Lemma B.5 .

If $x$ and $y$ are orthogonal vectors in $\mathbb{R}^{n}$, we have

$$ $\frac{\cos(x,x-y)}{\sqrt{1-\cos^{2}(x,x-y)}}\\ =\frac{\|x\|}{\|y\|}.$ (80) $$

###### Proof.

Using $(x,y)=0$, we have

$$ $\cos(x,x-y)=\frac{(x,x-y)}{\|x\|\|x-y\|}=\frac{\|x\|^{2}}{\|x\|\sqrt{\|x\|^{2} +\|y\|^{2}}}=\frac{\|x\|}{\sqrt{\|x\|^{2}+\|y\|^{2}}}.$ $$

Now, it is not difficult to show $\sqrt{1-\cos^{2}(x,x-y)}=\frac{\|y\|}{\sqrt{\|x\|^{2}+\|y\|^{2}}}$. Hence, (80)
follows.∎

Let $w=v\in L_{c}$. The relevance value will have a bound.

###### Proposition B.6 .

For all $u\in V$ we have $\mathrm{rel}_{vu}=n_{vu}\leq\gamma d_{v}$.

###### Proof.

The result follows from definition of $n_{uv}$ and (4).
∎

For a node of low degree, the relevance has to be low. However, this might not be the case for their approximation.

###### Corollary B.7 .

For $v\in L_{c}$ and $u\in H_{c}^{\gamma}$, we have $\mathrm{rel}_{vv}^{R}\stackrel{{\scriptstyle a}}{{\sim}}\mathcal{N}\left(n_{vv
},\frac{2n_{vv}^{2}}{q}\right)$
and $\mathrm{rel}_{vu}^{R}$ will have a nonnegative expectation with the standard deviation greater than $\gamma d_{v}$.

###### Proof.

Follows from Theorem B.1 and Lemma B.2
∎

The last result tells us that $\mathrm{rel}_{vv}^{R}$ will have values in $\displaystyle\left[n_{vv}\left(1-3\sqrt{\frac{2}{q}}\right),n_{vv}\left(1+3
\sqrt{\frac{2}{q}}\right)\right]$
with more than 99%. This means, for example if $q\geq 100$, $\mathrm{rel}_{vu}^{R}\in[1.5\gamma d_{v},\infty)\subset\left[n_{vv}\left(1+3
\sqrt{\frac{2}{q}}\right),\infty\right)$ can happen with probability $\mathbb{P}(\mathcal{N}(0,1)>1.5)\approx 6.7\%$.
For higher $q$, this probability will be higher. Roughly, we can anticipate that $\mathrm{rel}_{vv}^{R}<\mathrm{rel}_{vu}^{R}$ when $\mathrm{rel}_{vv}>\mathrm{rel}_{vu}$ happens more frequently.

The following result will show that this can happen more often than we want.

###### Corollary B.8 .

Let $v\in L_{c}$ and $u\in H_{c}^{\gamma}$ be two vertices with no common neighbors, i.e., such that $\mathrm{rel}_{vv}>0$ and $\mathrm{rel}_{vu}=0$.
Then, $\mathbb{P}(\mathrm{rel}_{vv}^{R}<\mathrm{rel}_{vu}^{R})>\mathbb{P}\left(
\mathcal{T}_{q}>\gamma^{-1/2}\right)\geq\mathbb{P}(\mathcal{T}_{q}>1)\approx 1
5.8\%$.

###### Proof.

Since $P_{v*}P_{u*}^{\top}=0$, we have $\frac{\cos(P_{w*},P_{u*}-P_{v*})}{\sqrt{1-\cos^{2}(P_{w*},P_{u*}-P_{v*})}}=
\frac{\|P_{v*}\|}{\|P_{u*}\|}$ by (80).
Hence, Theorem 3.1 gives us

$$ $\mathbb{P}(\mathrm{rel}_{vv}^{R}<\mathrm{rel}_{vu}^{R})=\mathbb{P}\left( \mathcal{T}_{q}>\frac{\|P_{v*}\|}{\|P_{u*}\|}\sqrt{q}\right).$ (81) $$

Further,
$\displaystyle\frac{\|P_{v*}\|}{\|P_{u*}\|}\sqrt{q}=\sqrt{\frac{n_{vv}q}{n_{uu}
}}\stackrel{{\scriptstyle\eqref{eq:MConnection}}}{{\leq}}\sqrt{\frac{\gamma d_
{v}q}{n_{uu}}}\stackrel{{\scriptstyle v\in L_{c}}}{{\leq}}\sqrt{\frac{\gamma cq
}{n_{uu}}}\stackrel{{\scriptstyle\eqref{eq:degreeAT}}}{{\leq}}\sqrt{\frac{
\gamma cq}{d_{u}}}\stackrel{{\scriptstyle u\in H_{c}^{\gamma}}}{{\leq}}\frac{1
}{\sqrt{\gamma}}.$
From the last inequality, we have $\mathbb{P}\left(\mathcal{T}_{q}>\frac{\|P_{v*}\|}{\|P_{u*}\|}\sqrt{q}\right)
\geq\mathbb{P}\left(\mathcal{T}_{q}>\gamma^{-1/2}\right)$ and the claim follows from (81). Finally, from (4) and (2), we note that $\gamma\geq 1$.
∎

Similar results would follow if we took two vertices $w,v$ of low degree with many common neighbors and a high degree vertex $u$ that has no common neighbors with $w$ and $v$. For simpler calculations, we took $w=v$.

###### Lemma B.5 .

###### Proof.

###### Proposition B.6 .

###### Proof.

###### Corollary B.7 .

###### Proof.

###### Corollary B.8 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
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? 

2. 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.
soundness: 3
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.
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.
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".

In 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. 

For 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.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: See Weaknesses.
soundness: 3
strengths: 1. Each mathematical description is carefully written. 
2. 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.
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.
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.
2. 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?
3. While each theorem in this paper is interesting, the direction of the whole discussion is not justified by those theorems.
Specifically, 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.
4. 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.

----
**After the discussion period**:
The 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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.

2.  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?

3. It may improve clarity to introduce the power law either before or immediately following line 155.

4.  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.

5. Proposition 2.6 seems straightforward. Is it necessary to present it formally as a proposition?

6.  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.

7. 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.

8. There are some citation formatting issues in the appendix, such as on line 1079, where several references are improperly displayed.

9. It would be helpful to more clearly indicate which results in the appendix are novel contributions.

10. 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).

11-Could you please address the point I raised in the weaknesses section?
soundness: 3
strengths: The main strengths, in my opinion, are:

1. **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.

2. **Rigorous Mathematical Treatment**: The paper is technically sound, with proofs that appear correct and rigorous.

3. **Clear Presentation**: The paper is well-written and easy to follow, aside from a few issues outlined below.
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.
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$. 

The 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.

2- **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.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
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 
and a more comprehensive comparison of approaches.


B. 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.


C. 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.


Insights: The adjacency matrix configuration that you analyzed can be applied to problems in Natural Language Processing.
soundness: 3
strengths: 1. The paper provides an interesting analysis supported by theorems alongside their interpretations that make the results more clear. 
2. The ranking application is interesting, and is supported by proofs as well.
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.
weaknesses: See questions.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 1
questions: See comments above.
soundness: 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. 
quality:  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. 
clarity: Overall, clarity is not a strength of this paper. However, The first two pages introducing the paper and the contributions are written clearly. 
significance: The broader topic of analyzing graph embeddings is certainly a significant direction of investigation. The application of ranking is also a significant avenue.
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.
weaknesses: I raise questions and remarks along several front： 

1. 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.

There 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.  

Minor point: -  the introduction of the NDCG metric was without citation/reference/background motivation in page 6. I suggest adding motivation. 

2. The mathematical results are not presented in a very organized/clear way. 

In 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. 

I 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. 

3. The organization of the paper can be improved: 
- 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. 

Given the above, my belief is that the paper can be substantially improved in the presentation, clarity and organization front.

Meta-review: This paper studies random projection methods for graph embedding: in particular embeddings produced by AR or TR where R is a Johnson-Lindenstrauss random projection matrix and A and T are the graph adjacency matrices and transition matrices in particular. They argue that due to the high variance introduced by the graph degree distribution, it is more appropriate to compare these embeddings via cosine similarity (i.e. inner product after normalization) rather than via direct inner product. This is perhaps not surprising -- and it may be an interesting observation outside of the graph context in other settings where random projection is used on data points with highly varying norms. The reviewers overall felt that the paper was well presented and that the theoretical results were interesting and valuable.

As the AC, I feel that a major weakness is that the paper only considers embeddings of the form AR and TR which are very far from what is employed in practice. To really capture graph structure, higher degree polynomials in these matrices (possibly with other modifications such as entrywise nonlinearities) are needed. It does not feel that the techniques of the paper would extend well to these more realistic settings. Thus, I feel that the paper gives a in-depth study of a very niche topic which in reality is far from the practice of graph embedding. Since its theoretical results follow fairly standard approaches, to me this makes the paper below bar for acceptance. However, after discussing with reviewers, they did not feel that this was a major weakness and still supported acceptance -- hence the recommendation.

Decision: Accept (Poster)