Spectral generative models for graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publication14TH INTERNATIONAL CONFERENCE ON IMAGE ANALYSIS AND PROCESSING, PROCEEDINGS
Place of PublicationLOS ALAMITOS
PublisherIEEE Computer Society
Pages35-40
Number of pages6
ISBN (Print)978-0-7695-2877-9
Publication statusPublished - 2007
Event14th International Conference on Image Analysis and Processing - Modena
Duration: 10 Sept 200714 Sept 2007

Conference

Conference14th International Conference on Image Analysis and Processing
CityModena
Period10/09/0714/09/07

Keywords

  • DISTANCE

Cite this