# FREDE: Anytime Graph Embeddings

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

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

- [Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks](https://mlsanity.com/paper/2406.05482/) (2024)
- [Learning Bi-typed Multi-relational Heterogeneous Graph via Dual Hierarchical Attention Networks](https://mlsanity.com/paper/2112.13078/) (2021)
- [Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling](https://mlsanity.com/paper/2105.09182/) (2021)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Network Embedding via Deep Prediction Model](https://mlsanity.com/paper/2104.13323/) (2021)
- [PGB: A PubMed Graph Benchmark for Heterogeneous Network Representation Learning](https://mlsanity.com/paper/2305.02691/) (2023)
- [HUGE: Huge Unsupervised Graph Embeddings with TPUs](https://mlsanity.com/paper/2307.14490/) (2023)
- [PSNE: Efficient Spectral Sparsification Algorithms for Scaling Network Embedding](https://mlsanity.com/paper/2408.02705/) (2024)
- [Disentangled and Self-Explainable Node Representation Learning](https://mlsanity.com/paper/2410.21043/) (2024)
- [QUINT: Node embedding using network hashing](https://mlsanity.com/paper/2109.04206/) (2021)
- [A flexible PageRank-based graph embedding framework closely related to spectral eigenvector embeddings](https://mlsanity.com/paper/2207.11321/) (2022)
- [Sample Efficient Learning of Factored Embeddings of Tensor Fields](https://mlsanity.com/paper/2209.00372/) (2022)

## Abstract (arXiv)

Low-dimensional representations, or embeddings, of a graph's nodes facilitate several practical data science and data engineering tasks. As such embeddings rely, explicitly or implicitly, on a similarity measure among nodes, they require the computation of a quadratic similarity matrix, inducing a tradeoff between space complexity and embedding quality. To date, no graph embedding work combines (i) linear space complexity, (ii) a nonlinear transform as its basis, and (iii) nontrivial quality guarantees. In this paper we introduce FREDE (FREquent Directions Embedding), a graph embedding based on matrix sketching that combines those three desiderata. Starting out from the observation that embedding methods aim to preserve the covariance among the rows of a similarity matrix}, FREDE iteratively improves on quality while individually processing rows of a nonlinearly transformed PPR similarity matrix derived from a state-of-the-art graph embedding method} and provides, at any iteration, column-covariance approximation guarantees in due course almost indistinguishable from those of the optimal approximation by SVD. Our experimental evaluation on variably sized networks shows that FREDE performs almost as well as SVD and competitively against state-of-the-art embedding methods in diverse data science tasks, even when it is based on as little as 10% of node similarities.