FREDE: Anytime Graph Embeddings

Anton Tsitsulin, Marina Munkhoeva, Davide Mottin, Panagiotis Karras, Ivan Oseledets, Emmanuel Mueller

VLDB 2021

pdf | code

FREDE scalably produces an embedding at anytime; at the dotted black line, it outperforms all contenders, including the SVD of a PPR-like similarity matrix, after pro-cessing about 20% of matrix rows.

FREDE scalably produces an embedding at anytime; at the dotted black line, it outperforms all contenders, including the SVD of a PPR-like similarity matrix, after pro-cessing about 20% of matrix rows.

TL;DR

First anytime optimal algorithm for graph embedding with state-of-the-art performance after visiting a fraction of the matrix.

In this paper:

  • We interpret a state-of-the-art graph embedding method, VERSE, as factorizing a transformed PPR similarity matrix
  • We propose FREDE, ananytime graph embedding algorithm that minimizes covariance error on that PPR-like matrix via sketching
  • We attain space complexity linear in the number ofn odes and time linear in the number of processed rows
  • In a thorough experimental evaluation with real graphs we confirm that FREDE is competitive against the state-of-the-art and scales to large networks