Many interesting applications of Pattern Recognition techniques can take advantage in dealing with labeled graphs as input patterns. To this aim the most important issue is the definition of a dissimilarity measure between graphs. In this paper we propose a representation technique able to characterize the input graphs as real valued feature vectors, allowing the use of standard classification systems. This procedure consists in two distinct stages. In the first step a labeled graph is transformed into a sequence of its vertices, ordered according to a given criterion. In a second step this sequence is mapped into a real valued vector. To perform the latter stage, we propose a novel Granular Computing procedure searching for frequent substructures, called GRADIS. This algorithm is in charge of the inexact substructures identification and of the embedding of the sequenced graphs using the symbolic histogram approach. Tests have been performed by synthetically generating a set of graph classification problem instances with the aim to measure system performances when dealing with different types of graphs, as well when increasing problem hardness.

Graph recognition by seriation and frequent substructures mining / Livi, Lorenzo; DEL VESCOVO, Guido; Rizzi, Antonello. - 1:(2012), pp. 186-191. ((Intervento presentato al convegno 1st International Conference on Pattern Recognition Applications and Methods, ICPRAM 2012 tenutosi a Vilamoura; Portugal nel 2012 [10.5220/0003733201860191].

Graph recognition by seriation and frequent substructures mining

LIVI, LORENZO;DEL VESCOVO, Guido;RIZZI, Antonello
2012

Abstract

Many interesting applications of Pattern Recognition techniques can take advantage in dealing with labeled graphs as input patterns. To this aim the most important issue is the definition of a dissimilarity measure between graphs. In this paper we propose a representation technique able to characterize the input graphs as real valued feature vectors, allowing the use of standard classification systems. This procedure consists in two distinct stages. In the first step a labeled graph is transformed into a sequence of its vertices, ordered according to a given criterion. In a second step this sequence is mapped into a real valued vector. To perform the latter stage, we propose a novel Granular Computing procedure searching for frequent substructures, called GRADIS. This algorithm is in charge of the inexact substructures identification and of the embedding of the sequenced graphs using the symbolic histogram approach. Tests have been performed by synthetically generating a set of graph classification problem instances with the aim to measure system performances when dealing with different types of graphs, as well when increasing problem hardness.
1st International Conference on Pattern Recognition Applications and Methods, ICPRAM 2012
Classification; Embedding; Frequent substructures mining; Granular computing; Graph seriation; Inexact graph matching;
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Graph recognition by seriation and frequent substructures mining / Livi, Lorenzo; DEL VESCOVO, Guido; Rizzi, Antonello. - 1:(2012), pp. 186-191. ((Intervento presentato al convegno 1st International Conference on Pattern Recognition Applications and Methods, ICPRAM 2012 tenutosi a Vilamoura; Portugal nel 2012 [10.5220/0003733201860191].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/908190
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? ND
social impact