A branch of node embeddings algorithms work by factorization of (powers of) the adjacency matrix of the graph [1]}, [2]}, [3]}, [4]}. These algorithms have well-understood properties but can be inefficient as even if the adjacency matrix is usually sparse, its powers can be dense [5]}, e.g., the average distance between any two users in the Facebook graph is only 4 [6]}. The computational complexity is improved using advanced techniques from linear algebra. However, these algorithms do not yield interpretable embeddings.
