Graph Characterization from Entropy Component Analysis

Structural complexity measures and embedding have both been extensively and separately employed for the problems of graph clustering and classification. In this paper we aim to explore whether entropy component analysis can be used as a means of combining these two fundamental approaches. Specifically we develop a novel method that embeds undirected graphs into a feature space based on the graph entropy distribution. We commence from a recently derived expression for the von Neumann entropy of an undirected graph, which depends on vertex degree statistics. Based on this analysis we identify the local entropy contribution associated with each edge in a graph, and this is related to the reciprocal of the product of the degrees of the two vertices connected by the edge. This suggests a simple entropic characterization of graph structure, based on a two-dimensional histogram in which the bins are indexed by vertex degree and the bin-contents is the total entropy contribution associated with the edges that connect vertices of specific degree. This distribution of entropy with vertex degree can be encoded as a matrix, which captures the structure of the graph in terms of an entropic measure of complexity. The matrix can hence be viewed as a sample of entropy histograms from different graphs. Thus we can extract the entropy components from the sample, and use these to embed populations of graphs into a low dimensional space. We apply this method to the problem of graph classification, and compare the classification results of our new method with some alternative state of the art pattern recognition methods on bioinformatics data.