An Impossibility Theorem for Node Embedding

T. Mitchell Roddenberry, Yu Zhu, Santiago Segarra
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:2422-2430, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-mitchell-roddenberry24a, title = {An Impossibility Theorem for Node Embedding}, author = {Mitchell Roddenberry, T. and Zhu, Yu and Segarra, Santiago}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {2422--2430}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/mitchell-roddenberry24a/mitchell-roddenberry24a.pdf}, url = {https://proceedings.mlr.press/v238/mitchell-roddenberry24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T An Impossibility Theorem for Node Embedding %A T. Mitchell Roddenberry %A Yu Zhu %A Santiago Segarra %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-mitchell-roddenberry24a %I PMLR %P 2422--2430 %U https://proceedings.mlr.press/v238/mitchell-roddenberry24a.html %V 238 %X 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.
APA
Mitchell Roddenberry, T., Zhu, Y. & Segarra, S.. (2024). An Impossibility Theorem for Node Embedding. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:2422-2430 Available from https://proceedings.mlr.press/v238/mitchell-roddenberry24a.html.

Related Material