Unsupervised Framework for Evaluating and Explaining Structural Node
  Embeddings of Graphs
Ashkan Dehghan Kinga Siuta Agata Skorupka Andrei Betlen David Miller Bogumil Kaminski Pawel Pralat
An embedding is a mapping from a set of nodes of a network into a real vector
space. Embeddings can have various aims like capturing the underlying graph
topology and structure, node-to-node relationship, or other relevant
information about the graph, its subgraphs or nodes themselves. A practical
challenge with using embeddings is that there are many available variants to
choose from. Selecting a small set of most promising embeddings from the long
list of possible options for a given task is challenging and often requires
domain expertise. Embeddings can be categorized into two main types: classical
embeddings and structural embeddings. Classical embeddings focus on learning
both local and global proximity of nodes, while structural embeddings learn
information specifically about the local structure of nodes' neighbourhood. For
classical node embeddings there exists a framework which helps data scientists
to identify (in an unsupervised way) a few embeddings that are worth further
investigation. Unfortunately, no such framework exists for structural
embeddings. In this paper we propose a framework for unsupervised ranking of
structural graph embeddings. The proposed framework, apart from assigning an
aggregate quality score for a structural embedding, additionally gives a data
scientist insights into properties of this embedding. It produces information
which predefined node features the embedding learns, how well it learns them,
and which dimensions in the embedded space represent the predefined node
features. Using this information the user gets a level of explainability to an
otherwise complex black-box embedding algorithm.