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/Report/Conference proceedingConference contribution

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 - 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
Abbreviated titleSSPR 2012 / SPR 2012
CountryJapan
CityHiroshima
Period7/11/129/11/12

    Fingerprint

Keywords

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

Cite this

Han, L., Rossi, L., Torsello, A., Wilson, R. C., & Hancock, E. R. (2012). Information theoretic prototype selection for unattributed graphs. In G. Gimel’farb, E. Hancock, A. Imiya, & et al (Eds.), Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings (pp. 33-41). (Lecture notes in computer science; Vol. 7626). Springer. https://doi.org/10.1007/978-3-642-34166-3_4