# The impossibility of low rank representations for triangle-rich complex networks

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2020.

## Built on by (most cited first, 30 of 32)

- [Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling](https://mlsanity.com/paper/2305.04111/) (2023)
- [Marius: Learning Massive Graph Embeddings on a Single Machine](https://mlsanity.com/paper/2101.08358/) (2021)
- [Reinforcement learning on graphs: A survey](https://mlsanity.com/paper/2204.06127/) (2022)
- [Demystifying Embedding Spaces using Large Language Models](https://mlsanity.com/paper/2310.04475/) (2023)
- [A Broader Picture of Random-walk Based Graph Embedding](https://mlsanity.com/paper/2110.12344/) (2021)
- [On the Power of Edge Independent Graph Models](https://mlsanity.com/paper/2111.00048/) (2021)
- [Spectral embedding for dynamic networks with stability guarantees](https://mlsanity.com/paper/2106.01282/) (2021)
- [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)
- [Learning low-rank latent mesoscale structures in networks](https://mlsanity.com/paper/2102.06984/) (2021)
- [Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings](https://mlsanity.com/paper/2111.03030/) (2021)
- [EDGE++: Improved Training and Sampling of EDGE](https://mlsanity.com/paper/2310.14441/) (2023)
- [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)
- [Clustered Graph Matching for Label Recovery and Graph Classification](https://mlsanity.com/paper/2205.03486/) (2022)
- [Exact and rapid linear clustering of networks with dynamic programming](https://mlsanity.com/paper/2301.10403/) (2023)
- [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)
- [Leveraging Graph Diffusion Models for Network Refinement Tasks](https://mlsanity.com/paper/2311.17856/) (2023)
- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)
- [An Impossibility Theorem for Node Embedding](https://mlsanity.com/paper/2105.13251/) (2021)
- [Interpretable Network Representation Learning with Principal Component Analysis](https://mlsanity.com/paper/2106.14238/) (2021)
- [Spectral embedding and the latent geometry of multipartite networks](https://mlsanity.com/paper/2202.03945/) (2022)
- [Low-Rank Representations Towards Classification Problem of Complex Networks](https://mlsanity.com/paper/2210.11561/) (2022)
- [Pseudo-Riemannian Embedding Models for Multi-Relational Graph Representations](https://mlsanity.com/paper/2212.03720/) (2022)
- [Fitting Low-rank Models on Egocentrically Sampled Partial Networks](https://mlsanity.com/paper/2303.11230/) (2023)
- [Simplicity within biological complexity](https://mlsanity.com/paper/2405.09595/) (2024)
- [Valid Bootstraps for Network Embeddings with Applications to Network Visualisation](https://mlsanity.com/paper/2410.20895/) (2024)
- [Multi-Scale Node Embeddings for Graph Modeling and Generation](https://mlsanity.com/paper/2412.04354/) (2024)

## Abstract (arXiv)

The study of complex networks is a significant development in modern science, and has enriched the social sciences, biology, physics, and computer science. Models and algorithms for such networks are pervasive in our society, and impact human behavior via social networks, search engines, and recommender systems to name a few. A widely used algorithmic technique for modeling such complex networks is to construct a low-dimensional Euclidean embedding of the vertices of the network, where proximity of vertices is interpreted as the likelihood of an edge. Contrary to the common view, we argue that such graph embeddings do not}capture salient properties of complex networks. The two properties we focus on are low degree and large clustering coefficients, which have been widely established to be empirically true for real-world networks. We mathematically prove that any embedding (that uses dot products to measure similarity) that can successfully create these two properties must have rank nearly linear in the number of vertices. Among other implications, this establishes that popular embedding techniques such as Singular Value Decomposition and node2vec fail to capture significant structural aspects of real-world complex networks. Furthermore, we empirically study a number of different embedding techniques based on dot product, and show that they all fail to capture the triangle structure.