FREDE: Anytime Graph Embeddings

Abstract

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,

Stats

• citations32
• S2 citations—
• github stars0
• HF likes0
• heat score11.39
• arxiv keytsitsulin2020frede

Related papers

• VERSE: Versatile Graph Embeddings From Similarity Measures (2018)17.42
• Hebbian Graph Embeddings (2019)0.00
• Local Intrinsic Dimensionality Measures For Graphs, With Applications To Graph Embeddings (2022)5.24
• Graph2region: Efficient Graph Similarity Learning With Structure And Scale Restoration (2025)0.00
• QUINT: Node Embedding Using Network Hashing (2021)5.24
• Position-based Hash Embeddings For Scaling Graph Neural Networks (2021)2.26
• In Search Of The Most Efficient And Memory-saving Visualization Of High Dimensional Data (2023)0.00
• Embedding In Recommender Systems: A Survey (2023)0.00