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 outline an ensemble of methods for dealing with such data,focusing on two specific methods. The first one is simply based on a global alignment approach applied to seriated versions of the graphs. The second one is a two-stages method, which applies a recurrent substructures analysis to the seriated graphs, individuating a set of frequent subsequences, employed for embedding the graphs into a real valued feature vector space. Tests have been performed by synthetically generating a set of classification problem instances with increasing problem hardness, and with a shared benchmarking database of labeled graphs.

Combining Graph Seriation and Substructures Mining for Graph Recognition / Livi, Lorenzo; DEL VESCOVO, Guido; Rizzi, Antonello. - STAMPA. - 204(2013), pp. 79-91. [10.1007/978-3-642-36530-0_7].

Combining Graph Seriation and Substructures Mining for Graph Recognition

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

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 outline an ensemble of methods for dealing with such data,focusing on two specific methods. The first one is simply based on a global alignment approach applied to seriated versions of the graphs. The second one is a two-stages method, which applies a recurrent substructures analysis to the seriated graphs, individuating a set of frequent subsequences, employed for embedding the graphs into a real valued feature vector space. Tests have been performed by synthetically generating a set of classification problem instances with increasing problem hardness, and with a shared benchmarking database of labeled graphs.
Pattern Recognition - Applications and Methods
978-3-642-36529-4
978-3-642-36530-0
978-3-642-36529-4
978-3-642-36530-0
Granular computing, Inexact graph matching, Sequence embedding, Graph embedding
02 Pubblicazione su volume::02a Capitolo o Articolo
Combining Graph Seriation and Substructures Mining for Graph Recognition / Livi, Lorenzo; DEL VESCOVO, Guido; Rizzi, Antonello. - STAMPA. - 204(2013), pp. 79-91. [10.1007/978-3-642-36530-0_7].
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/908231
 Attenzione

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

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