Node Similarities under Random Projections: Limits and Pathological Cases

We appreciate the reviewer recognizing the strengths of the paper in terms of its originality and significance, as well as the soundness of the mathematical derivations. Next, we address each of the comments raised by the reviewer.

1.1 - Motivation of Random Projections in comparison with Spectral Methods. The main advantages of random projections lie in their favorable algorithmic requirements (a single matrix multiplication over a sparse adjacency matrix) and their flexibility.

Whereas computation of spectral embeddings requires the decomposition of the adjacency matrix of the whole graph for meaningful eigen-/singular vectors, computation of random projection embeddings can be performed independently and only for an arbitrary subset of nodes of interest. This is decisive for the adoption of random projections many practical applications (e.g., large/billion-scale graphs, graphs with attributes, dynamic graphs) which warrants the need for characterization of their approximation quality.

Random projections also present favorable computational complexity: for a graph with $n$ nodes and $m$ edges, computing $q$-dimensional RP embeddings for the whole graph requires a single-pass sparse matrix multiplication, with computational complexity $\mathcal{O}(mq)$. Here, $m = \bar d n \ll n^2$ for most graphs, where $\bar d := \frac{m}{n}$ is the graph's average degree. Spectral embeddings typically require power iterations with multiple matrix multiplication passes for convergence, with the number of iterations and precision being both graph and algorithm dependent.

We understand this context was missing in paper. Following the suggestion of the reviewer, we will incorporate this discussion to the manuscript to further motivate our contributions to the theory for random projections.

1.2 - Scaling of $q$ and $n$. We show that the dot product is a sum of $q$ independent terms, and that for large values of $q$, the distribution will be approximately normal. In the case of the JL Lemma, for large $n$ (for example, $n>10^6$), from Theorem 2.2.b, we have $q \geq \frac{1}{\varepsilon^2}$. This is large enough for the dot product to be in the domain of attraction of the Central Limit Theorem and gives valuable insight into where we can expect the dot product under random projections values to be. To further connect the asymptotic and finite-sample results, an analog role of $\frac{1}{q}$ in the variance term for normality is played by $\varepsilon$ in the JL lemma, but for all dot products. Following the suggestion of the reviewer, we will add a remark to clarify this in the text.

2.1 - Notation for asymptotic results. We agree that the notation for asymptotic convergence in distribution can be presented earlier in the paper, before it is used in Theorem 2.2. We thank the reviewer for this observation and will update the paper accordingly.

2.2 - Implicit definitions and assumptions. We will revise the theorem statements for any implicit definitions or assumptions, as recommended by the reviewer.

2.3 - Connecting recommendations to theoretical results. To address the point raised by the reviewer, we will add in the conclusion explicit references to the theorems and results leading to the recommendations.

3 - Organization of the paper. We appreciate the suggestions for renaming of the subsections given by the reviewer and will update the paper accordingly.

We thank the reviewer for providing valuable feedback and appreciating the strengths of our paper.

Next, we address each of the questions raised:

A. L2 normalization. Although we did not include this case in the main paper, we would like to refer the reviewer to the asymptotic and finite-sample results in Theorem A.10 and Theorem A.17 in the Appendix, respectively, which did consider the specific case of L2 normalization before random projection.

The reasons why we did not promote these results to the main paper are two-fold:

1. The asymptotic variance $\frac{1 + \rho^2}{q}$ obtained for this case (c.f. Theorem A.10) is higher than the variance $\frac{(1 - \rho^2)^2}{q}$ obtained for cosine similarity (c.f. Theorem A.21).

2. Obtaining the rows of a matrix polynomial $p(A)$ needed to compute the denominators for normalization involves computing $p(A)$ before random projection. Such a computation is often impractical, as it can typically lead to the powers of $A$ resulting in dense $n \times n$ matrices. On the other hand, computing the polynomial $p(A)R^T$ after random projection (using the association $A(\ldots(A(AR^T))$) takes advantage of the intermediate factors, which are lower-dimensional projected matrices $n \times q$, with $q \ll n$.

We agree with the reviewer that the case of L2 normalization is a natural direction of consideration as an intermediate case to L1 normalization before RP, when $P=T$, and L2 normalization after RP, as done for cosine similarity. We can capture the suggestion of the reviewer as a remark for a more comprehensive comparison of the results in the paper.

B. Entries of the adjacency matrix We will state more clearly that the matrix can be assumed as $A\in (\mathbb{Z}_0^+)^{n\times n}$. Proofs in the paper would also work for $A\in ([1,\infty]\cup \{0\})^{n\times n}$ unchanged. Results for the general case $A\in (\mathbb{R}_0^+)^{n\times n}$ would also hold by incorporating a scaling constant $c > 0$ such that $cA\in ([1,\infty]\cup \{0\})^{n\times n}$, but we preferred not do it to avoid unnecessary clutter. We can comment on this in the text of the paper.

C. We will provide an explicit definition of $\textrm{rank}_w^R(h)$ with a simple example in the context of the ranking application, as suggested by the reviewer.

Lastly, we are keen on learning more about the application of the adjacency matrices to natural language processing, as it can further extend the scope of our results. We would appreciate any specific references that the reviewer may be willing to provide us.

We would like to thank the reviewer for the thorough consideration and valuable feedback given to our paper.

Response to weaknesses:

Novelty and refinements. Thank you for referring us to the results on the off-diagonal entries of the Wishart matrix; we had not made that connection before and are grateful to learn about it. We will adapt the text to make sure it is pointed out where the result is used in the Appendix. Whereas prior literature has focused on analyzing the dot product through the difference $RP_{u*}^TP_{v*}R^T=\frac{1}{4}(\|P_{u*}R^T+P_{v*}R^T\|-\|P_{u*}R^T-P_{v*}R^T\|)$, this angular representation allows us to reveal fundamental differences between dot product and cosine similarity in quality of the approximation under RP. Our novel results include the specific analysis considering the graph structure; the exact formula for sign change given in Proposition A.8, from which Theorem 3.1 was developed; and the exact estimation of flipping probability in Corollary 3.4. The remaining results were improvements or refinements of existing results, which also followed from the angular representation of the marginal distributions. We will make sure to clarify this in the paper.

Other sparse RP settings. We agree with the reviewer that the potential extension to sparse RP setting an interesting point for discussion. From our early explorations after writing the current paper, we can point to the following. Due to similar properties between Rademacher and normal random variables, we expect similar qualitative behavior. More specifically, in the sparse case the entries of $R$ are often taken to satisfy Pr (R_{ij}=\\frac{k\\sqrt{s}}{\\sqrt{q}})=\\left\\{\\begin{array}{cll} \\frac{1}{2s} & \\textrm{for} & k =-1\\\\ (1- \frac{1}{s}) & \\textrm{for} & k = 0\\\\ \\frac{1}{2s} & \\textrm{for} & k = 1 \\end{array}\\right. for $s>0$. In this case, the dot product will have the following properties: $\\mathbb{E}[RP_{u*}^TP_{v*}R^T]=P_{u*}^tP_{v*}$ and $\\mathrm{Var}[RP_{u*}^TP_{v*}R^T=\\frac{1}{q}\\left[\|P_{u*}\\|^2\\|P_{v*}\\|^2+ (P_{u*}^TP_{v*})^2+(s-3)\\sum_{w\\in V}^nP_{uw}^2P_{vw}^2\\right].$

Using a Central Limit Theorem argument similar to parts (a) of Theorem 2.2 and Theorem A.6, we will have $RP_{u*}^TP_{v*}R^T\stackrel{a}{\sim} \mathcal{N}\left(P_{u*}^TP_{v*}, \mathrm{Var}[RP_{u*}^tP_{v*}R^T]\right).$ Note that $(s-3)$ in the variance expression can be negative, however since all entries of matrix $P$ are non-negative, we have $0\leq \sum_{w\in V}P_{uw}^2P_{vw}^2\leq (P_{u*}^tP_{v*})^2.$

If the product of the norms is high compared to the dot product, the challenge of controlling the variance will remain a problem. This will lead to similar issues with respect to the structure of the graph. For $s\geq 3$ and $P=T$, if $u$ is a high-degree node and $v$ a low-degree node, the standard deviation will be greater than the expectation (using similar arguments as in Corollary 2.3). The discussion about confidence intervals would also hold. For $s<3$, some adaption of the argument would be necessary. This points that the we expect the similar qualitative behavior in the case of dot product.

For the cosine similarity, using the $\delta$-method we should be able to get part (a) Theorem 2.5, potentially with some modifications in the variance.

Getting analogs of non-asymptotic results as we did in the text of paper will require restating and modifying proofs. They were simpler to prove for Gaussian matrices, but we believe we can expect similar outcomes for the sparse case. We plan to develop these results in future work that may lead to a new and complementary manuscript.

We will add a comment about this in the conclusion.

We again thank the reviewer for their comments.

One of the goals this paper was to clarify how cosine similarity behaves under random projections. Although there existed prior results in the literature -- for example as we mention in Remark A.30 (based on the results from (Arpit et al)) -- those concentration inequality results looked like $|\cos(Rx,Ry)-\cos(x,y)| \leq \varepsilon (1+|\cos(x,y)|).$

This fails to capture the fundamental fact that the closer $|\cos(x,y)|$ is to 1, the more precise the estimate with random projections will be. This was indicated by the asymptotic result (Theorem A. 21), and confirmed by concentration result (Theorem A. 23): $|\cos(Rx,Ry)-\cos(x,y)| \leq \varepsilon (1-\cos^2(x,y)).$ This fact also enabled us to prove JL Lemma version for cosine similarity as stated in Theorems A. 28 as well as the version for graphs in part (b) of Theorem 2.5.

The decomposition provided by the rotational invariance of the Gaussian distribution played a crucial role in obtaining this estimate, as it can be seen in Lemma A.27. The elements from the representation (24) $\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}}$ and their distributions were essential in proving this result.

For cosine similarity -- in the sparse case, a similar concentration result may be difficult to obtain. However, we do believe that the version in the literature of the concentration result can still be obtained, as long as we can get the concentration results for the dot product or the norm -- both of which seem likely.

We thank the reviewer for appreciating the strengths of our paper and for providing feedback for clarification, which we address next:

1. We stated the general JL Lemma in Theorem A.31 of the Appendix, but did not reference it in the main paper. Following the suggestion of the reviewer, we will place it in the main part of the paper and provide the requested reference with the associated proof.

2. We can expand the discussion on the JL and Theorem 2.2 as follows. Prior research has focused on applying the JL Lemma simultaneously to both $\|P_{u*}R^t+P_{v*}R^t\|$ and $\|P_{u*}R^t-P_{v*}R^t\|$ in the expansion $RP_{u*}^tP_{u*}R^t=\frac{1}{4}(\|P_{u*}R^t+P_{v*}R^t\|-\|P_{u*}R^t-P_{v*}R^t\|)$. This form (a difference of terms) limits the derivation of advanced results, since the associated terms are not independent. On the other hand, the representation (23) of the dot product, given by $RP_{u*}^tP_{u*}R^t=\|x\|\|y\|(\rho \|N\|^2+\|N\|M_1\sqrt{1-\rho^2}),$ where $N$ is the $q$-dimensional standard normal vector and $M_1$ independent standard normal random variable, is easier to analyze. More specifically:

• Since $\|N\|^2$ is sum of $q$ terms, we get asymptotic normality, which would be difficult with the usual approach.

• We can get an exact formula for the sign change (Proposition A.8), which was useful to show that in ranking a reordering might happen with high probability, as stated in Corollary 3.4.

• We also get more precise concentration results as given in Theorem 2.2(b) and Theorem 2.5(b). A comparison is discussed in Sections A.III.5 and A.IV.5 of the Appendix.

This approach is even more critical in analyzing the cosine similarity, in which case getting any concrete results would be considerably more difficult. Cosine similarity under random projections involves a ratio of functions of random matrices (which may explain the scarcity of theoretical results in this particular subject) and the transformation in (23) is a crucial step in their characterization.

3. We agree that a similarity measures can be problem-dependent, and many variations of them have been considered in the literature of specific applications. Dot products of rows of adjacency matrices have a clear interpretation as the overlap of neighbors. Transition probabilities and cosine similarity are normalizations of the dot product, and have also been widely used. Our focus was on these similarity measures. When researchers are considering any of the aforementioned measures, we point out benefits and drawbacks of using them in the context of random projections.

4. Researchers have experimented with random projections as embeddings, which have been presented as competent approach for approximating node similarity based on guarantees of the JL Lemma. The scope of this paper was to point what challenges might appear using this approach. We focused on the quality with respect to the degree distribution. Other methods for producing embeddings might have different types of challenges with respect to different structures. We hope to have addressed the point raised by the reviewer and will gladly come back to provide further clarifications if needed.

3. We appreciate the reviewer's point of view in limiting the extent of the recommendations and agree with the proposed correction. Our previous conclusions were primarily focused on the different characteristics of cosine and dot product with respect to their estimation noise under random projections. In that direction, we showed that a fundamental property of relative ordering under different similarities and normalizations can be significantly affected by random projections (with cosine similarity showing a more stable behavior). When considering the broader context of applications, we agree that this may not be the only factor to be examined towards the adoption of a particular similarity metric (e.g., dot product vs. cosine). As the reviewer appropriately pointed out, if a certain application relies on specific norm information, then cosine similarity may not be applicable, and dot product may be required -- even if more difficult to estimate. In that respect, we hope that our characterization of the different estimation behavior under RP of these two similarities (including the identification of potential pathologies for nodes of low and high degrees) is a contribution towards the understanding of the trade-offs imposed. We will reformulate our conclusion to limit the extent of the recommendations given and thank the reviewer for emphasizing this point.

We would like to thank the reviewer appreciating our paper and providing valuable feedback.

Weaknesses:

1. Thanks for pointing out how we can improve Figure 1. We will update its labels as you suggested.

2. Addressed in the Questions block below.

3. We will produce an example independent of the ranking application that illustrates the deviation of the estimate from the value with respect to the nodes degree/connectedness.

Questions:

1. We can add some discussion as follows:

For dot product, the variance or the estimate of relevance of a pair of nodes using random projections depends both on their relevance as well as their node degrees. This adds a side effect that is more pronounced for nodes of low and high degrees, depending on whether the adjacency or transition matrix is adopted, respectively. On the other hand, with cosine similarity the variance of error does not depend on the node degrees.

More specifically, we can express the above in terms of the node relevance values. In the case of the dot product (Theorem 2.2), both $rel_{uu}$ and $rel_{vv}$ play a role in addition to $rel_{uv}$:

$rel_{uv}^R\stackrel{a}{\sim} \mathcal{N}\left(rel_{uv}, \frac{1}{q}(rel_{uu}rel_{vv} + rel_{uv}^2)\right)$

while in the case of cosine similarity (Theorem 2.5), only $rel_{uv}$ matters: $rel^R_{uv}\stackrel{a}{\sim}\mathcal{N}\left(rel_{uv}, \frac{(1-rel_{uv}^2)^2}{q}\right).$

2. The $3\sigma$ interval (property) refers to the corresponding Gaussian confidence interval within which the random projections will generate an estimate with approximately $99.73$% confidence. We also expressed this interval in terms of the node degrees and relevance values for the case of $P=A$ (see text following Lemma B.3 in the Appendix). For the case of cosine similarity, the passage "endpoints do note depend on the node degrees" was not precise, and we will correct it to state that the interval end points only depend on the cosine similarity being estimated. We can further highlight this difference in Sections 2.1 and 2.2, especially on their degree dependence. Such a distinction is also motivated and explained by the discussion provided for Q2 above.