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.

本文介绍了一个基于矩阵奇异值分解的矩阵草图方法 ——FREDE，该方法以线性空间复杂度、非线性变换和优质保障作为其基础，可在各种数据科学任务中与最先进的嵌入方法相媲美，即使基于仅 10％的节点相似性。