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