# Node Embeddings and Exact Low-Rank Representations of Complex Networks

arXiv: https://arxiv.org/abs/2006.05592 · HTML: https://mlsanity.com/paper/2006.05592/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2020.

## Built on by (most cited first, 21 of 21)

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [On the Power of Edge Independent Graph Models](https://mlsanity.com/paper/2111.00048/) (2021)
- [Taming the Sigmoid Bottleneck: Provably Argmaxable Sparse Multi-Label Classification](https://mlsanity.com/paper/2310.10443/) (2023)
- [Asymptotics of Network Embeddings Learned via Subsampling](https://mlsanity.com/paper/2107.02363/) (2021)
- [A Hierarchical Block Distance Model for Ultra Low-Dimensional Graph Representations](https://mlsanity.com/paper/2204.05885/) (2022)
- [DeepWalking Backwards: From Embeddings Back to Graphs](https://mlsanity.com/paper/2102.08532/) (2021)
- [Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling](https://mlsanity.com/paper/2201.08481/) (2022)
- [The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure](https://mlsanity.com/paper/2312.04762/) (2023)
- [Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings](https://mlsanity.com/paper/2111.03030/) (2021)
- [On the Role of Edge Dependency in Graph Generative Models](https://mlsanity.com/paper/2312.03691/) (2023)
- [How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings](https://mlsanity.com/paper/2503.01723/) (2025)
- [Pseudo-Euclidean Attract-Repel Embeddings for Undirected Graphs](https://mlsanity.com/paper/2106.09671/) (2021)
- [Implications of sparsity and high triangle density for graph representation learning](https://mlsanity.com/paper/2210.15277/) (2022)
- [Learning a Patent-Informed Biomedical Knowledge Graph Reveals Technological Potential of Drug Repositioning Candidates](https://mlsanity.com/paper/2309.03227/) (2023)
- [On the Theoretical Limitations of Embedding-based Link Prediction](https://mlsanity.com/paper/2506.22271/) (2025)
- [An Impossibility Theorem for Node Embedding](https://mlsanity.com/paper/2105.13251/) (2021)
- [Asymptotics of ℓ2 Regularized Network Embeddings](https://mlsanity.com/paper/2201.01689/) (2022)
- [Low-Rank Representations Towards Classification Problem of Complex Networks](https://mlsanity.com/paper/2210.11561/) (2022)
- [Simplicity within biological complexity](https://mlsanity.com/paper/2405.09595/) (2024)
- [Multi-Scale Node Embeddings for Graph Modeling and Generation](https://mlsanity.com/paper/2412.04354/) (2024)
- [Information Loss and Disparate Effects in Network Embeddings](https://mlsanity.com/paper/2509.12396/) (2025)

## Abstract (arXiv)

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.