[KDD 2020] Data Compression as a Comprehensive Framework for Graph Drawing and Representation Learning
Aug 13, 202014 views
Embedding a graph into feature space is a promising approach to,understand its structure. Embedding into 2D or 3D space enables,visualization; representation in higher-dimensional vector space,(typically >100D) enables the application of data mining techniques.,For the success of knowledge discovery it is essential that the distances between the embedded vertices truly reflect the structure,of the graph. Our fundamental idea is to compress the adjacency,matrix by predicting the existence of an edge from the Euclidean,distance between the corresponding vertices in the embedding, and,to use the achieved compression as a quality measure for the embedding. We call this quality measure Predictive Entropy (PE). PE,uses a sigmoid function to define the probability which is monotonically decreasing with the Euclidean distance. We use this sigmoid,probability to compress the adjacency matrix of the graph by an,entropy coding. While PE could be used to assess the result of any,graph drawing or representation learning method we particularly,use it as objective function in our new method GEMPE (Graph Embedding by Minimizing the Predictive Entropy). We demonstrate,in our experiments that GEMPE clearly outperforms comparison,methods with respect to quality of the visual result, clustering and,node-labeling accuracy on the discovered coordinates.