Node Embeddings and Exact Low-Rank Representations of Complex Networks

See Seshadhri2020impossibility, Graph embedding

Seshadhri2020impossibility‘s argument is that graphs that are generated from low-rank embedding cannot contain low-degree nodes with many triangles. This paper argues that the result is only valid under the assumptions used in the previous work and that it is always possible to produce exact low-dimensional embedding for bounded degree graphs.

The assumptions that are relaxed in this paper are: (i) a node can have two embedding vectors (in- and out-vectors) and that Euclidean distance can be used to estimate similarities or link propensity.

The paper shows that how the exact factorization can be done, with the rank depends only on the. maximum degree of the graph. In other words, it may be easy to overfit to a graph with low maximum degree if we try to optimize the reconstruction error and this may not necessarily be the best embedding that captures the salient structure of a graph.