Mixing spectral representations of 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 has been done with generative models of graphs. Graphs are not naturally represented in a vector space since there is no natural labelling of the vertices of the graphs different labellings lead to different representations of the graph structure. 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. The spectral decomposition of a graph can be used to extract information about the relationship of edges and parts in a graph. In this paper we look at the problem of mixing graphs by using the spectral representation of a graph as an intermediate step. The spectral representation allows us to mix different structural features from each of the graphs to create new combinations. We can also define an averaging process on the spectral representations which generates a graph close to the graph median.

Original languageEnglish
Title of host publication18th International Conference on Pattern Recognition, Vol 4, Proceedings
EditorsYY Tang, SP Wang, G Lorette, DS Yeung, H Yan
Place of PublicationLOS ALAMITOS
PublisherIEEE Computer Society
Pages140-144
Number of pages5
ISBN (Print)0-7695-2521-0
Publication statusPublished - 20 Aug 2006
Event18th International Conference on Pattern Recognition (ICPR 2006) - Hong Kong
Duration: 20 Aug 200624 Aug 2006

Conference

Conference18th International Conference on Pattern Recognition (ICPR 2006)
CityHong Kong
Period20/08/0624/08/06

Keywords

  • DISTANCE

Cite this