Centrality-based Interpretability Measures for Graph Embeddings

Many real-world data are considered as graphs, such as computer networks, social networks and protein-protein interaction networks. Graph embedding methods are powerful tools for representing large graphs in various domains. A graph embedding method projects the components of a graph, such as its nodes or edges, into a vector space with a lower dimensionality than the adjacency matrix of the graph, and aims to preserve the characteristics of the graph. The generated embedding vectors have been utilized in various graph mining applications such as node classification, link prediction and anomaly detection. Despite the wide success of the graph embedding methods, little study has been done to facilitate a better understanding of the graph embeddings. In this paper, inspired by advancements in interpreting word embeddings, we propose two interpretability measures to quantify the interpretability of graph embeddings by leveraging useful network centrality properties and perform comparisons of different graph embedding methods. Using these scores, we can provide insights into the representational power of graph embedding methods.

I. Introduction

Graph data are rapidly growing in recent years and powerful graph representation methods are required to represent the graph information. One of the most effective ways to represent large graphs is graph embedding. Graph embedding methods map nodes or edges into a lower dimensional space such that similar nodes or edges are represented by similar vectors in the embedding space. A large number of graph embedding methods have been proposed including Node2vec [1], LINE [2], DeepWalk [3] and SDNE [4]. The use of graph embedding vectors in downstream tasks, such as node classification, link prediction and anomaly detection, has shown superior performances compared to the use of traditional methods of feature engineering for node representation [1], [2], [5].