FREDE: Linear-Space Anytime Graph Embeddings
  Low-dimensional representations, or embeddings, of a graph's nodes facilitate
data mining tasks. Known embedding methods explicitly or implicitly rely on a
similarity measure among nodes. As the similarity matrix is quadratic, a
tradeoff between space complexity and embedding quality arises; past research
initially opted for heuristics and linear-transform factorizations, which allow
for linear space but compromise on quality; recent research has proposed a
quadratic-space solution as a viable option too.
  In this paper we observe that embedding methods effectively aim to preserve
the covariance among the rows of a similarity matrix, and raise the question:
is there a method that combines (i) linear space complexity, (ii) a nonlinear
transform as its basis, and (iii) nontrivial quality guarantees? We answer this
question in the affirmative, with FREDE(FREquent Directions Embedding), a
sketching-based method that iteratively improves on quality while processing
rows of the similarity matrix individually; thereby, it provides, at any
iteration, column-covariance approximation guarantees that are, in due course,
almost indistinguishable from those of the optimal row-covariance approximation
by SVD. Our experimental evaluation on variably sized networks shows that FREDE
performs as well as SVD and competitively against current state-of-the-art
methods in diverse data mining tasks, even when it derives an embedding based
on only 10% of node similarities.
