Abstract

Low-dimensional representations, or embeddings, of a graph’s nodes facilitate tasks such as community detection, link prediction, and classification. Embeddings learn similarities among nodes, either implicitly, as a side-effect of adapting word embedding methods to graphs, or explicitly, by reconstructing a similarity measure. As the similarity matrix is quadratic, past research has resorted to heuristic or linear-factorization solutions, compromising quality.

In this paper we develop FREDE (FRequent Directions Embeddings), an incremental algorithm that embeds a nonlinear transformation of the similarity matrix optimally in terms of an objective relaxed from the optimal low-rank approximation given by SVD.

Starting out from the observation that embeddings strive to preserve the covariance, i.e., dot products, among rows of the similarity matrix, FREDE derives and operates on each row individually, progressively improving the overall embedding quality; thereby, it overcomes the scalability impediment, while offering a nonlinear solution with optimality guarantees. Our experimental evaluation shows that FREDE performs as well as SVD, the theoretically optimal low-rank approximation, and clearly outperforms previous embedding algorithms in various data mining tasks.