A Supergraph-based Generative Model

Abstract

This paper describes a method for constructing a generative model for sets of graphs. The method is posed in terms of learning a supergraph from which the samples can be obtained by edit operations. We construct a probability distribution for the occurrence of nodes and edges over the supergraph. We use the EM algorithm to learn both the structure of the supergraph and the correspondences between the nodes of the sample graphs and those of the supergraph, which are treated as missing data. In the experimental evaluation of the method, we a) prove that our supergraph learning method can lead to an optimal or suboptimal supergraph, and b) show that our proposed generative model gives good graph classification results.