Node Embeddings and Exact Low-Rank Representations of Complex Networks
This work addresses a foundational problem in network analysis by challenging prior limitations on embeddings, potentially enabling more accurate modeling of complex networks.
The authors tackled the claim that low-dimensional embeddings cannot capture local structure like high triangle density in sparse networks, by proving that a relaxed model can generate such graphs and providing an algorithm (LPCA) that finds exact low-dimensional embeddings for real-world networks, with experiments verifying this ability.
Low-dimensional embeddings, from classical spectral embeddings to modern neural-net-inspired methods, are a cornerstone in the modeling and analysis of complex networks. Recent work by Seshadhri et al. (PNAS 2020) suggests that such embeddings cannot capture local structure arising in complex networks. In particular, they show that any network generated from a natural low-dimensional model cannot be both sparse and have high triangle density (high clustering coefficient), two hallmark properties of many real-world networks. In this work we show that the results of Seshadhri et al. are intimately connected to the model they use rather than the low-dimensional structure of complex networks. Specifically, we prove that a minor relaxation of their model can generate sparse graphs with high triangle density. Surprisingly, we show that this same model leads to exact low-dimensional factorizations of many real-world networks. We give a simple algorithm based on logistic principal component analysis (LPCA) that succeeds in finding such exact embeddings. Finally, we perform a large number of experiments that verify the ability of very low-dimensional embeddings to capture local structure in real-world networks.