Skip to yearly menu bar Skip to main content


An Impossibility Theorem for Node Embedding

T. Mitchell Roddenberry · Yu Zhu · Santiago Segarra

MR1 & MR2 - Number 2
[ ]
Fri 3 May 8 a.m. PDT — 8:30 a.m. PDT
Oral presentation: Oral: General Machine Learning
Fri 3 May 7 a.m. PDT — 8 a.m. PDT


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. Motivated by desirable properties of node embeddings for encoding the role of a node in the structure of a network, we first state three properties for embedding dissimilarity networks. We then prove that no node embedding method can satisfy all three properties at once, reflecting fundamental difficulties inherent to the task. Having identified these difficulties, we show that mild relaxations of these axioms allow for certain node embedding methods to be admissible.

Live content is unavailable. Log in and register to view live content