Random Projections have been widely used to generate embeddings for various
graph 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. Our analysis provides new theoretical
results, identifies pathological cases, and tests them with numerical
experiments. We find that, for nodes of lower or higher degrees, the method
produces especially unreliable embeddings for the dot product, regardless of
whether the adjacency or the (normalized version) transition is used. With
respect to the statistical noise introduced by Random Projections, we show that
cosine similarity produces remarkably more precise approximations.

通过随机投影方法生成的嵌入向量在计算效率上得到了广泛应用，本文进一步研究了随机投影对点积和余弦相似度的保留效果并提供了新的理论结果，找出了病态案例并用数值实验进行了测试，发现对于低度或高度节点，此方法在点积上得到的嵌入向量相对不可靠，而与随机投影引入的统计噪声相比，余弦相似度得到了更精确的近似。

随机投影下的节点相似性：极限和病态案例

Node Similarities under Random Projections: Limits and Pathological  Cases

We study quantum neural networks made by parametric one-qubit gates and fixed
two-qubit gates in the limit of infinite width, where the generated function is
the expectation value of the sum of single-qubit observables over all the
qubits. First, we prove that the probability distribution of the function
generated by the untrained network with randomly initialized parameters
converges in distribution to a Gaussian process whenever each measured qubit is
correlated only with few other measured qubits. Then, we analytically
characterize the training of the network via gradient descent with square loss
on supervised learning problems. We prove that, as long as the network is not
affected by barren plateaus, the trained network can perfectly fit the training
set and that the probability distribution of the function generated after
training still converges in distribution to a Gaussian process. Finally, we
consider the statistical noise of the measurement at the output of the network
and prove that a polynomial number of measurements is sufficient for all the
previous results to hold and that the network can always be trained in
polynomial time.

我们研究了使用参数化单量子比特门和固定双量子比特门构建的量子神经网络，研究表明在无限宽度限制下，随机初始化参数的未训练网络生成的函数的概率分布收敛于高斯过程。通过梯度下降法对网络进行训练时，网络可以完美拟合训练集，并且训练后生成的函数概率分布仍然收敛于高斯过程。测量结果的统计噪声对网络的影响在多项式数量的测量下是可忽略的，而且网络的训练时间也是多项式级别的。