Information theoretic prototype selection for unattributed graphs

Lin Han*, Luca Rossi, Andrea Torsello, Richard C. Wilson, Edwin R. Hancock

*Corresponding author for this work

Research output: Chapter in Book/Published conference outputConference publication

Abstract

In this paper we propose a prototype size selection method for a set of sample graphs. Our first contribution is to show how approximate set coding can be extended from the vector to graph domain. With this framework to hand we show how prototype selection can be posed as optimizing the mutual information between two partitioned sets of sample graphs. We show how the resulting method can be used for prototype graph size selection. In our experiments, we apply our method to a real-world dataset and investigate its performance on prototype size selection tasks.

Original languageEnglish
Title of host publicationStructural, Syntactic, and Statistical Pattern Recognition
Subtitle of host publicationjoint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings
EditorsGeorgy Gimel’farb, Edwin Hancock, Atsushi Imiya, et al
Place of PublicationBerlin (DE)
PublisherSpringer
Pages33-41
Number of pages9
ISBN (Electronic)978-3-642-34166-3
ISBN (Print)978-3-642-34165-6
DOIs
Publication statusPublished - 2012
EventJoint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition 2012 - Hiroshima, Japan
Duration: 7 Nov 20129 Nov 2012

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume7626
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopJoint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition 2012
Abbreviated titleSSPR 2012 / SPR 2012
Country/TerritoryJapan
CityHiroshima
Period7/11/129/11/12

Keywords

  • importance sampling
  • mutual information
  • partition function
  • prototype selection

Fingerprint

Dive into the research topics of 'Information theoretic prototype selection for unattributed graphs'. Together they form a unique fingerprint.
  • Approximate axial symmetries from continuous time quantum walks

    Rossi, L., Torsello, A. & Hancock, E. R., 2012, Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings. Gimel’farb, G., Hancock, E., Imiya, A. & et al (eds.). Berlin (DE): Springer, p. 144-152 9 p. (Lecture notes in computer science; vol. 7626).

    Research output: Chapter in Book/Published conference outputConference publication

Cite this