# REFINE: Random RangE FInder for Network Embedding

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 38 references that are in the map.
- First posted on arXiv 24 Aug 2021.

## Builds on (most cited first, 21 of 21)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks](https://mlsanity.com/paper/1508.00200/) (2015)
- [HARP: Hierarchical Representation Learning for Networks](https://mlsanity.com/paper/1706.07845/) (2017)
- [NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization](https://mlsanity.com/paper/1906.11156/) (2019)
- [MILE: A Multi-Level Framework for Scalable Graph Embedding](https://mlsanity.com/paper/1802.09612/) (2018)
- [Tensor Representations for Action Recognition](https://mlsanity.com/paper/2012.14371/) (2020)
- [Power Normalizations in Fine-grained Image, Few-shot Image and Graph Classification](https://mlsanity.com/paper/2012.13975/) (2020)
- [Billion-scale Network Embedding with Iterative Random Projection](https://mlsanity.com/paper/1805.02396/) (2018)
- [Fisher-Bures Adversary Graph Convolutional Networks](https://mlsanity.com/paper/1903.04154/) (2019)
- [Tensor Representations via Kernel Linearization for Action Recognition from 3D Skeletons (Extended Version)](https://mlsanity.com/paper/1604.00239/) (2016)
- [Flight Delay Prediction using Airport Situational Awareness Map](https://mlsanity.com/paper/1911.01605/) (2019)
- [Predicting Flight Delay with Spatio-Temporal Trajectory Convolutional Network and Airport Situational Awareness Map](https://mlsanity.com/paper/2105.08969/) (2021)
- [Relation Embedding for Personalised POI Recommendation](https://mlsanity.com/paper/2002.03461/) (2020)
- [Fast, Warped Graph Embedding: Unifying Framework and One-Click Algorithm](https://mlsanity.com/paper/1702.05764/) (2017)
- [Graph Convolutional Network with Generalized Factorized Bilinear Aggregation](https://mlsanity.com/paper/2107.11666/) (2021)

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

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [COSTA: Covariance-Preserving Feature Augmentation for Graph Contrastive Learning](https://mlsanity.com/paper/2206.04726/) (2022)
- [Contrastive Laplacian Eigenmaps](https://mlsanity.com/paper/2201.05493/) (2022)
- [Meta-Learning for Multi-Label Few-Shot Classification](https://mlsanity.com/paper/2110.13494/) (2021)
- [Graph-adaptive Rectified Linear Unit for Graph Neural Networks](https://mlsanity.com/paper/2202.06281/) (2022)
- [Understanding and Mitigating Hyperbolic Dimensional Collapse in Graph Contrastive Learning](https://mlsanity.com/paper/2310.18209/) (2023)
- [Simple Dialogue System with AUDITED](https://mlsanity.com/paper/2110.11881/) (2021)
- [Towards a Robust Differentiable Architecture Search under Label Noise](https://mlsanity.com/paper/2110.12197/) (2021)
- [Graph Self-Supervised Learning with Learnable Structural and Positional Encodings](https://mlsanity.com/paper/2502.16233/) (2025)

## Abstract (arXiv)

Network embedding approaches have recently attracted considerable interest as they learn low-dimensional vector representations of nodes. Embeddings based on the matrix factorization are effective but they are usually computationally expensive due to the eigen-decomposition step. In this paper, we propose a Random RangE FInder based Network Embedding (REFINE) algorithm, which can perform embedding on one million of nodes (YouTube) within 30 seconds in a single thread. REFINE is 10x faster than ProNE, which is 10-400x faster than other methods such as LINE, DeepWalk, Node2Vec, GraRep, and Hope. Firstly, we formulate our network embedding approach as a skip-gram model, but with an orthogonal constraint, and we reformulate it into the matrix factorization problem. Instead of using randomized tSVD (truncated SVD) as other methods, we employ the Randomized Blocked QR decomposition to obtain the node representation fast. Moreover, we design a simple but efficient spectral filter for network enhancement to obtain higher-order information for node representation. Experimental results prove that REFINE is very efficient on datasets of different sizes (from thousand to million of nodes/edges) for node classification, while enjoying a good performance.