An Impossibility Theorem for Node Embedding
This work identifies fundamental limitations in node embedding tasks, which is significant for researchers and practitioners in machine learning and graph analysis, though it is incremental as it extends axiomatic impossibility results from clustering to embeddings.
The paper tackled the problem of establishing axiomatic properties for node embedding methods in graph-based representation learning, and proved an impossibility theorem showing that no method can simultaneously satisfy all three proposed properties, similar to known clustering impossibility results.
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.