Spectral 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. The individual patterns are defined by vectors and so the individual features of the pattern are well defined. In contrast, very little work has been done with generative models of graphs because graphs do not have a straightforward vectorial representation. Because of this, simple statistical quantities such as mean and variance are difficult to define for a group of graphs. While we can define statistical quantities of individual edges, it is not so straightforward to define how sets of edges in graphs are related. In this paper we examine the problem of creating generative distributions over sets of graphs. We use the spectral representation of the graphs to construct a dual vector space for the graphs. The spectral decomposition of a graph can be used to extract information about the relationship of edges and parts in a graph. Distributions are then defined on the vector spaces and used to generate new samples. Finally, these points must be used to reconstruct the sampled graph.