An Impossibility Theorem for Node Embedding
  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.
