# Fast and Accurate Network Embeddings via Very Sparse Random Projection

arXiv: https://arxiv.org/abs/1908.11512 · HTML: https://mlsanity.com/paper/1908.11512/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2019.

## Built on by (most cited first, 29 of 29)

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Multiplex Heterogeneous Graph Convolutional Network](https://mlsanity.com/paper/2208.06129/) (2022)
- [Token-wise Influential Training Data Retrieval for Large Language Models](https://mlsanity.com/paper/2405.11724/) (2024)
- [SCGC : Self-Supervised Contrastive Graph Clustering](https://mlsanity.com/paper/2204.12656/) (2022)
- [A Topological Perspective on Demystifying GNN-Based Link Prediction Performance](https://mlsanity.com/paper/2310.04612/) (2023)
- [GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection](https://mlsanity.com/paper/2505.18976/) (2025)
- [CompanyKG: A Large-Scale Heterogeneous Graph for Company Similarity Quantification](https://mlsanity.com/paper/2306.10649/) (2023)
- [GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operators](https://mlsanity.com/paper/2603.16849/) (2026)
- [Multiple Kernel Representation Learning on Networks](https://mlsanity.com/paper/2106.05057/) (2021)
- [CodaRAG: Connecting the Dots with Associativity Inspired by Complementary Learning](https://mlsanity.com/paper/2604.10426/) (2026)
- [Augmenting Textual Generation via Topology Aware Retrieval](https://mlsanity.com/paper/2405.17602/) (2024)
- [A Graph Based Raman Spectral Processing Technique for Exosome Classification](https://mlsanity.com/paper/2504.15324/) (2025)
- [Rotary Position Encodings for Graphs](https://mlsanity.com/paper/2509.22259/) (2025)
- [Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings](https://mlsanity.com/paper/2107.10014/) (2021)
- [Assessing the Effects of Hyperparameters on Knowledge Graph Embedding Quality](https://mlsanity.com/paper/2207.00473/) (2022)
- [Creating generalizable downstream graph models with random projections](https://mlsanity.com/paper/2302.08895/) (2023)
- [Towards a GML-Enabled Knowledge Graph Platform](https://mlsanity.com/paper/2303.02166/) (2023)
- [HUGE: Huge Unsupervised Graph Embeddings with TPUs](https://mlsanity.com/paper/2307.14490/) (2023)
- [Retrieval Augmented Anomaly Detection (RAAD): Nimble Model Adjustment Without Retraining](https://mlsanity.com/paper/2502.19534/) (2025)
- [Efficient Multi-Hop Question Answering over Knowledge Graphs via LLM Planning and Embedding-Guided Search](https://mlsanity.com/paper/2511.19648/) (2025)
- [QUINT: Node embedding using network hashing](https://mlsanity.com/paper/2109.04206/) (2021)
- [Random Projections of Sparse Adjacency Matrices](https://mlsanity.com/paper/2309.01360/) (2023)
- [KG-FRUS: a Novel Graph-based Dataset of 127 Years of US Diplomatic Relations](https://mlsanity.com/paper/2311.01606/) (2023)
- [Node Similarities under Random Projections: Limits and Pathological Cases](https://mlsanity.com/paper/2404.10148/) (2024)
- [Rethinking Node Representation Interpretation through Relation Coherence](https://mlsanity.com/paper/2411.00653/) (2024)
- [Predictive Query-based Pipeline for Graph Data](https://mlsanity.com/paper/2412.09940/) (2024)
- [WindVE: Collaborative CPU-NPU Vector Embedding](https://mlsanity.com/paper/2504.14941/) (2025)
- [Estimating the Effects of Sample Training Orders for Large Language Models without Retraining](https://mlsanity.com/paper/2505.22042/) (2025)
- [Generating Multiple-Choice Knowledge Questions with Interpretable Difficulty Estimation using Knowledge Graphs and Large Language Models](https://mlsanity.com/paper/2604.10748/) (2026)

## Abstract (arXiv)

We present FastRP, a scalable and performant algorithm for learning distributed node representations in a graph. FastRP is over 4,000 times faster than state-of-the-art methods such as DeepWalk and node2vec, while achieving comparable or even better performance as evaluated on several real-world networks on various downstream tasks. We observe that most network embedding methods consist of two components: construct a node similarity matrix and then apply dimension reduction techniques to this matrix. We show that the success of these methods should be attributed to the proper construction of this similarity matrix, rather than the dimension reduction method employed. FastRP is proposed as a scalable algorithm for network embeddings. Two key features of FastRP are: 1) it explicitly constructs a node similarity matrix that captures transitive relationships in a graph and normalizes matrix entries based on node degrees; 2) it utilizes very sparse random projection, which is a scalable optimization-free method for dimension reduction. An extra benefit from combining these two design choices is that it allows the iterative computation of node embeddings so that the similarity matrix need not be explicitly constructed, which further speeds up FastRP. FastRP is also advantageous for its ease of implementation, parallelization and hyperparameter tuning. The source code is available at https://github.com/GTmac/FastRP.