# How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 63 references that are in the map.
- First posted on arXiv 3 Mar 2025.

## Builds on (most cited first, 21 of 21)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry](https://mlsanity.com/paper/1806.03417/) (2018)
- [Riemannian Adaptive Optimization Methods](https://mlsanity.com/paper/1810.00760/) (2018)
- [Geoopt: Riemannian Optimization in PyTorch](https://mlsanity.com/paper/2005.02819/) (2020)
- [word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method](https://mlsanity.com/paper/1402.3722/) (2014)
- [Network Representation Learning: A Survey](https://mlsanity.com/paper/1801.05852/) (2017)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [PANE: scalable and effective attributed network embedding](https://mlsanity.com/paper/2009.00826/) (2020)
- [Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space](https://mlsanity.com/paper/1602.06522/) (2016)
- [Node Embeddings and Exact Low-Rank Representations of Complex Networks](https://mlsanity.com/paper/2006.05592/) (2020)
- [Principled approach to the selection of the embedding dimension of networks](https://mlsanity.com/paper/2004.09928/) (2020)
- [A Hierarchical Block Distance Model for Ultra Low-Dimensional Graph Representations](https://mlsanity.com/paper/2204.05885/) (2022)
- [Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings](https://mlsanity.com/paper/2111.03030/) (2021)

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

- [Rank Is Not Capacity: Spectral Occupancy for Latent Graph Models](https://mlsanity.com/paper/2605.11142/) (2026)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)
- [The Impact of Dimensionality on the Stability of Node Embeddings](https://mlsanity.com/paper/2604.08492/) (2026)

## Abstract (arXiv)

Low-dimensional embeddings are essential for machine learning tasks involving graphs, such as node classification, link prediction, community detection, network visualization, and network compression. Although recent studies have identified exact low-dimensional embeddings, the limits of the required embedding dimensions remain unclear. We presently prove that lower dimensional embeddings are possible when using Euclidean metric embeddings as opposed to vector-based Logistic PCA (LPCA) embeddings. In particular, we provide an efficient logarithmic search procedure for identifying the exact embedding dimension and demonstrate how metric embeddings enable inference of the exact embedding dimensions of large-scale networks by exploiting that the metric properties can be used to provide linearithmic scaling. Empirically, we show that our approach extracts substantially lower dimensional representations of networks than previously reported for small-sized networks. For the first time, we demonstrate that even large-scale networks can be effectively embedded in very low-dimensional spaces, and provide examples of scalable, exact reconstruction for graphs with up to a million nodes. Our approach highlights that the intrinsic dimensionality of networks is substantially lower than previously reported and provides a computationally efficient assessment of the exact embedding dimension also of large-scale networks. The surprisingly low dimensional representations achieved demonstrate that networks in general can be losslessly represented using very low dimensional feature spaces, which can be used to guide existing network analysis tasks from community detection and node classification to structure revealing exact network visualizations.