Parts based generative models for graphs

Generative models are well known in the domain of statistical pattern recognition. Typically, they describe the probability distribution of patterns in a vector space. In contrast, very little work has been done with generative models of graphs because graphs do not have a straight-forward vectorial representation. In this paper we examine the problem of creating generative distributions over sets of graphs. We model the variation in a set of graphs by observing which subgraphs are present in each graph and how these subgraphs are connected. By performing clustering on the subgraphs we can group those with similar structure. Distributions are then defined on the clusters present in each graph, which subgraphs are present in each cluster and the way subgraphs are connected. New graphs can then be generated by sampling from the distributions. We show the utility of our approach on synthetically generated point sets and point sets derived from real-world imagery of articulated objects.