Gem++: a tool for solving substitution-tolerant subgraph isomorphism

Julien Lerouge, Pierre Le Bodic, Pierre Héroux, Sébastien Adam

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

The substitution-tolerant subgraph isomorphism is a particular error-tolerant subgraph matching that allows label substitutions for both vertices and edges. Such a matching is often required in pattern recognition applications since graphs extracted from images are generally labeled with features vectors computed from raw data which are naturally subject to noise. This paper describes an extended version of a Binary Linear Program (BLP) for solving this class of graph matching problem. The paper also presents GEM++, a software framework that implements the BLP and that we have made available for the research community. GEM++ allows the processing of different sub-problems (induced isomorphism or not, directed graphs or not) with complex labelling of vertices and edges. We also present some datasets available for evaluating future contributions in this field.
Original languageEnglish
Title of host publicationGraph-Based Representations in Pattern Recognition
Subtitle of host publication10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015 Proceedings
EditorsCheng-Lin Liu, Bin Luo, Walter G. Kropatsch, Jian Cheng
Place of PublicationCham Switzerland
PublisherSpringer
Pages128-137
Number of pages10
ISBN (Electronic)9783319182247
ISBN (Print)9783319182230
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventIAPR TC-15 Workshop on Graph-based Representation in Pattern Recognition 2015 - Chinese Academy of Sciences, Beijing, China
Duration: 13 May 201515 May 2015
Conference number: 10th
http://www.nlpr.ia.ac.cn/gbr2015/
http://www.springer.com/gp/book/9783319182230 (Springer proceedings)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume9069
ISSN (Print)0302-9743

Workshop

WorkshopIAPR TC-15 Workshop on Graph-based Representation in Pattern Recognition 2015
Abbreviated titleGbRPR 2015
Country/TerritoryChina
CityBeijing
Period13/05/1515/05/15
OtherGraph-Based Representations in Pattern Recognition
10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Proceedings
Internet address

Keywords

  • Binary linear programming
  • Subgraph isomorphism
  • Graph matching toolkit
  • Graph datasets

Cite this