Generative Graph Prototypes from Information Theory

• Published in: IEEE transactions on pattern analysis and machine intelligence 2015-10, Vol.37 (10), p.2013-2027
• Main Authors: Lin Han, Wilson, Richard C., Hancock, Edwin R.
• Format: Article
• Language: English
• Subjects: Complexity theory; Data models; Entropy; Generative prototype; Jensen-Shannon divergence; Laplace equations; Minimum description length criterion; Probabilistic logic; Prototypes; Shape; Supergraph; Von Neumann entropy
• ISSN: 0162-8828; 1939-3539; 2160-9292
• DOI: 10.1109/TPAMI.2015.2400451

In this paper we present a method for constructing a generative prototype for a set of graphs by adopting a minimum description length approach. The method is posed in terms of learning a generative supergraph model from which the new samples can be obtained by an appropriate sampling mechanism. We commence by constructing a probability distribution for the occurrence of nodes and edges over the supergraph. We encode the complexity of the supergraph using an approximate Von Neumann entropy. A variant of the EM algorithm is developed to minimize the description length criterion in which the structure of the supergraph and the node correspondences between the sample graphs and the supergraph are treated as missing data. To generate new graphs, we assume that the nodes and edges of graphs arise under independent Bernoulli distributions and sample new graphs according to their node and edge occurrence probabilities. Empirical evaluations on real-world databases demonstrate the practical utility of the proposed algorithm and show the effectiveness of the generative model for the tasks of graph classification, graph clustering and generating new sample graphs.