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.

Semi-supervised learning can be defined as the ability to improve the predictive performance of an algorithm by providing it with data which hasn't been previously labeled. Manifold Regularization is a semi-supervised learning approach that extends the regularization framework so as to include additional regularization penalties that are based on the graph Laplacian as the empirical estimator of the underlying manifold. The incorporation of such terms rely on additional hyper-parameters, which, together with the original kernel and regularization parameters, are known to influence algorithm behavior. This paper proposes a gradient approach to the optimization of such hyper-parameters which is based on the closed form for the generalized cross validation estimate, being valid when the learning optimality conditions can be represented as a linear system, such as is the case for Laplacian Regularized Least Squares. For the subset hyper-parameters that are integer quantities, as is the case for the Laplacian matrix hyper-parameters, we propose the optimization of the weight components of a sum of base terms. Results of computational experiments are presented to illustrate the technique proposed.