Node Similarities under Random Projections: Limits and Pathological Cases
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencyGraph LearningLEMMASimilar Papers 제목 키워드 기반
Quantized Random Projections and Non-Linear Estimation of Cosine Similarity
Random projections constitute a simple, yet effective technique for dimensionality reduction with applications in learning and search problems. In the present paper, we consider the problem of estimating cosine similarit…
Dimensionality ReductionLEMMAQuantizationAnalysis of SparseHash: an efficient embedding of set-similarity via sparse projections
Embeddings provide compact representations of signals in order to perform efficient inference in a wide variety of tasks. In particular, random projections are common tools to construct Euclidean distance-preserving embe…
Inferring Networks From Random Walk-Based Node Similarities
Digital presence in the world of online social media entails significant privacy risks. In this work we consider a privacy threat to a social network in which an attacker has access to a subset of random walk-based node …
Anomaly DetectionClusteringGraph ClusteringGraph Learning+1Learning Networks from Random Walk-Based Node Similarities
Digital presence in the world of online social media entails significant privacy risks. In this work we consider a privacy threat to a social network in which an attacker has access to a subset of random walk-based node …
Anomaly DetectionClusteringGraph ClusteringGraph Learning+1Product Graph-based Higher Order Contextual Similarities for Inexact Subgraph Matching
Many algorithms formulate graph matching as an optimization of an objective function of pairwise quantification of nodes and edges of two graphs to be matched. Pairwise measurements usually consider local attributes but …
Graph Matching