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

Prototype
Graph in graph theory
Experiments
Mutual Information
Coding
Experiment
Framework

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). Berlin (DE): Springer. https://doi.org/10.1007/978-3-642-34166-3_4
Han, Lin ; Rossi, Luca ; Torsello, Andrea ; Wilson, Richard C. ; Hancock, Edwin R. / Information theoretic prototype selection for unattributed graphs. Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings. editor / Georgy Gimel’farb ; Edwin Hancock ; Atsushi Imiya ; et al. Berlin (DE) : Springer, 2012. pp. 33-41 (Lecture notes in computer science).
@inproceedings{a484a9cc2b864f999de5b167a4f49352,
title = "Information theoretic prototype selection for unattributed graphs",
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.",
keywords = "importance sampling, mutual information, partition function, prototype selection",
author = "Lin Han and Luca Rossi and Andrea Torsello and Wilson, {Richard C.} and Hancock, {Edwin R.}",
year = "2012",
doi = "10.1007/978-3-642-34166-3_4",
language = "English",
isbn = "978-3-642-34165-6",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "33--41",
editor = "Georgy Gimel’farb and Edwin Hancock and Atsushi Imiya and {et al}",
booktitle = "Structural, Syntactic, and Statistical Pattern Recognition",
address = "Germany",

}

Han, L, Rossi, L, Torsello, A, Wilson, RC & Hancock, ER 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. Lecture notes in computer science, vol. 7626, Springer, Berlin (DE), pp. 33-41, Joint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition, Hiroshima, Japan, 7/11/12. https://doi.org/10.1007/978-3-642-34166-3_4

Information theoretic prototype selection for unattributed graphs. / Han, Lin; Rossi, Luca; Torsello, Andrea; Wilson, Richard C.; Hancock, Edwin R.

Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings. ed. / Georgy Gimel’farb; Edwin Hancock; Atsushi Imiya; et al. Berlin (DE) : Springer, 2012. p. 33-41 (Lecture notes in computer science; Vol. 7626).

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

TY - GEN

T1 - Information theoretic prototype selection for unattributed graphs

AU - Han, Lin

AU - Rossi, Luca

AU - Torsello, Andrea

AU - Wilson, Richard C.

AU - Hancock, Edwin R.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - importance sampling

KW - mutual information

KW - partition function

KW - prototype selection

UR - http://www.scopus.com/inward/record.url?scp=84868133985&partnerID=8YFLogxK

UR - http://link.springer.com/chapter/10.1007%2F978-3-642-34166-3_4

U2 - 10.1007/978-3-642-34166-3_4

DO - 10.1007/978-3-642-34166-3_4

M3 - Conference contribution

AN - SCOPUS:84868133985

SN - 978-3-642-34165-6

T3 - Lecture notes in computer science

SP - 33

EP - 41

BT - Structural, Syntactic, and Statistical Pattern Recognition

A2 - Gimel’farb, Georgy

A2 - Hancock, Edwin

A2 - Imiya, Atsushi

A2 - et al,

PB - Springer

CY - Berlin (DE)

ER -

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