Node Embeddings and Exact Low-Rank Representations of Complex Networks, new paper accepted in NeurIPS 2020

Low-dimensional embeddings, from classical spectral embeddings to modern neural-net-inspired methods, are a cornerstone in the modeling and analysis of complex networks. They have a long and rich history, furtherly expanded in recent years by the successes of deep learning. In Node Embeddings and Exact Low-Rank Representations of Complex Networks (https://arxiv.org/abs/2006.05592), an international team of scientists including ISI Foundation researcher Charalampos E. Tsourakakis discusses a crucial issue emerged in a recent scientific paper.

"In their PNAS paper (SSSG20), Seshadhri, Sharma, Stolman and Goel ask an intriguing question: can low-dimensional node embeddings represent triangle-rich complex networks? Their answer is negative", says Tsourakakis. "In this work we show that their results 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".

Researchers also show that it exists a low-rank factorization algorithm that probably produces exact low dimensional embeddings for bounded degree graphs. And that this proposed algorithm produces very low-dimensional embeddings that preserve the local structure of large real-world networks. The paper has been accepted in NeurIPS 2020 , the thirty-fourth Conference on Neural Information Processing Systems, that will take place in virtual-only format from December 6 to December 12.

Node Embeddings and Exact Low-Rank Representations of Complex Networks, Sudhanshu Chanpuriya (UMass Amherst), Cameron Musco (UMass Amherst), Charalampos E. Tsourakakis (Boston University & ISI Foundation), Konstantinos Sotiropoulos (Boston University). Link: https://arxiv.org/abs/2006.05592.