# Billion-scale Network Embedding with Iterative Random Projection

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2018.

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

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings](https://mlsanity.com/paper/2101.03091/) (2021)
- [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)
- [REFINE: Random RangE FInder for Network Embedding](https://mlsanity.com/paper/2108.10703/) (2021)
- [A Hierarchical Block Distance Model for Ultra Low-Dimensional Graph Representations](https://mlsanity.com/paper/2204.05885/) (2022)
- [GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection](https://mlsanity.com/paper/2505.18976/) (2025)
- [GRAPE for Fast and Scalable Graph Processing and random walk-based Embedding](https://mlsanity.com/paper/2110.06196/) (2021)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [Multiple Kernel Representation Learning on Networks](https://mlsanity.com/paper/2106.05057/) (2021)
- [ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion](https://mlsanity.com/paper/2504.15920/) (2025)
- [Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation](https://mlsanity.com/paper/2505.20992/) (2025)
- [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)
- [Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds](https://mlsanity.com/paper/2306.08967/) (2023)
- [HUGE: Huge Unsupervised Graph Embeddings with TPUs](https://mlsanity.com/paper/2307.14490/) (2023)
- [QUINT: Node embedding using network hashing](https://mlsanity.com/paper/2109.04206/) (2021)
- [Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs](https://mlsanity.com/paper/2209.14825/) (2022)
- [Space-Invariant Projection in Streaming Network Embedding](https://mlsanity.com/paper/2303.06293/) (2023)
- [Node Similarities under Random Projections: Limits and Pathological Cases](https://mlsanity.com/paper/2404.10148/) (2024)
- [Perturbation Ontology based Graph Attention Networks](https://mlsanity.com/paper/2411.18520/) (2024)
- [Estimating the Effects of Sample Training Orders for Large Language Models without Retraining](https://mlsanity.com/paper/2505.22042/) (2025)
- [Archetypal Graph Generative Models: Explainable and Identifiable Communities via Anchor-Dominant Convex Hulls](https://mlsanity.com/paper/2602.21342/) (2026)
- [Topology-induced Operators Reveal Complementary Graph Representations without Training](https://mlsanity.com/paper/2609.08152/) (2026)
- [TopoEmbedX: A General Framework for Representation Learning on Topological Domains](https://mlsanity.com/paper/2609.37884/) (2026)

## Abstract (arXiv)

Network embedding, which learns low-dimensional vector representation for nodes in the network, has attracted considerable research attention recently. However, the existing methods are incapable of handling billion-scale networks, because they are computationally expensive and, at the same time, difficult to be accelerated by distributed computing schemes. To address these problems, we propose RandNE (Iterative Random Projection Network Embedding), a novel and simple billion-scale network embedding method. Specifically, we propose a Gaussian random projection approach to map the network into a low-dimensional embedding space while preserving the high-order proximities between nodes. To reduce the time complexity, we design an iterative projection procedure to avoid the explicit calculation of the high-order proximities. Theoretical analysis shows that our method is extremely efficient, and friendly to distributed computing schemes without any communication cost in the calculation. We also design a dynamic updating procedure which can efficiently incorporate the dynamic changes of the networks without error aggregation. Extensive experimental results demonstrate the efficiency and efficacy of RandNE over state-of-the-art methods in several tasks including network reconstruction, link prediction and node classification on multiple datasets with different scales, ranging from thousands to billions of nodes and edges.