# An Impossibility Theorem for Node Embedding

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 70 references that are in the map.
- First posted on arXiv 27 May 2021.

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

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [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)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Network Representation Learning: A Survey](https://mlsanity.com/paper/1801.05852/) (2017)
- [Understanding graph embedding methods and their applications](https://mlsanity.com/paper/2012.08019/) (2020)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Node Embeddings and Exact Low-Rank Representations of Complex Networks](https://mlsanity.com/paper/2006.05592/) (2020)
- [Axiomatic Construction of Hierarchical Clustering in Asymmetric Networks](https://mlsanity.com/paper/1301.7724/) (2013)
- [Hierarchical Quasi-Clustering Methods for Asymmetric Networks](https://mlsanity.com/paper/1404.4655/) (2014)
- [Metric Representations of Network Data](https://mlsanity.com/paper/1911.00164/) (2019)
- [Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling](https://mlsanity.com/paper/2105.09182/) (2021)
- [Preserving Local and Global Information for Network Embedding](https://mlsanity.com/paper/1710.07266/) (2017)

## Abstract (arXiv)

With the increasing popularity of graph-based methods for dimensionality reduction and representation learning, node embedding functions have become important objects of study in the literature. In this paper, we take an axiomatic approach to understanding node embedding methods, first stating three properties for embedding dissimilarity networks, then proving that all three cannot be satisfied simultaneously by any node embedding method. Similar to existing results on the impossibility of clustering under certain axiomatic assumptions, this points to fundamental difficulties inherent to node embedding tasks. Once these difficulties are identified, we then relax these axioms to allow for certain node embedding methods to be admissible in our framework.