Top

Soft Computing

Published in:

01-02-2014 | Methodologies and Application

A Granular Computing approach to the design of optimized graph classification systems

Authors: Filippo Maria Bianchi, Lorenzo Livi, Antonello Rizzi, Alireza Sadeghian

Published in: Soft Computing | Issue 2/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Research on Graph-based pattern recognition and Soft Computing systems has attracted many scientists and engineers in several different contexts. This fact is motivated by the reason that graphs are general structures able to encode both topological and semantic information in data. While the data modeling properties of graphs are of indisputable power, there are still different concerns about the best way to compute similarity functions in an effective and efficient manner. To this end, suited transformation procedures are usually conceived to address the well-known Inexact Graph Matching problem in an explicit embedding space. In this paper, we propose two graph embedding algorithms based on the Granular Computing paradigm, which are engineered as key procedures of a general-purpose graph classification system. Tests have been conducted on benchmarking datasets relying on both synthetic and real-world data, achieving competitive results in terms of test set classification accuracy.

previous article A study in facial regions saliency: a fuzzy measure approach

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Bargiela A, Pedrycz W (2003) Granular Computing: an introduction. Number v. 2002 in Kluwer international series in engineering and computer science. Kluwer, London. ISBN 9781402072734

Batista L, Granger E, Sabourin R (2010) Applying dissimilarity representation to off-line signature verification. In: Proceedings of the 2010 20th international conference on pattern recognition, ICPR ’10. IEEE Computer Society, Washington, DC, pp 1293–1297. doi:10.1109/ICPR.2010.322. ISBN 978-0-7695-4109-9

Bello R, Falcón R, Pedrycz W, Kacprzyk J (2008) Granular Computing: at the junction of rough sets and fuzzy sets. Studies in Fuzziness and Soft Computing. Springer, Berlin. ISBN 9783540769729

Borgwardt KM, Ong CS, Schönauer S, Vishwanathan SVN, Smola AJ, Kriegel H-P (2005) Protein function prediction via graph kernels. Bioinformatics 21:47–56. doi:10.1093/bioinformatics. ISSN 1367-4803

Carli A, Castellani U, Bicego M, Murino V (2010) Dissimilarity-based representation for local parts. In: Workshop on cognitive information processing, pp 299–303. June. ISBN 978-1-4244-6457-9

Carli A, Figueiredo MAT, Bicego M, Murino V (2012) Generative embeddings based on Rician mixtures: application to kernel-based discriminative classification of magnetic resonance images. In: Proceedings of the first international conference on pattern recognition applications and methods 2012, vol 1, pp 113–122

Cinti A, Rizzi A (2011) Neurofuzzy min-max networks implementation on FPGA. In: International joint conference on computational intalligence (IJCCI). Neural Comput Theories Anal. ISBN 978-989-8425-84-3

Del Vescovo G, Rizzi A (2007a) Automatic classification of graphs by symbolic histograms. In: Proceedings of the 2007 IEEE international conference on granular computing, GRC ’07. IEEE Computer Society, pp 410–416. doi:10.1109/GRC.2007.46. ISBN 0-7695-3032-X

Del Vescovo G, Rizzi A (2007b) Online handwriting recognition by the symbolic histograms approach. In: Proceedings of the 2007 IEEE international conference on granular computing, GRC ’07. IEEE Computer Society, Washington, DC, pp 686–700. doi:10.1109/GRC.2007.116. ISBN 0-7695-3032-X

Del Vescovo G, Livi L, Rizzi A, Frattale Mascioli FM (2011) Clustering structured data with the SPARE library. In: Proceedings of 2011 4th IEEE international conference on computer science and information technology, vol 9, pp 413–417. ISBN 978-1-61284-834-1

Escolano F, Bonev B, Lozano M (2011) Information-geometric graph indexing from bags of partial node coverages. In: Jiang X, Ferrer M, Torsello A (eds) Graph-based representations in pattern recognition, volume 6658 of LNCS. Springer Berlin, pp 52–61. doi:10.1007/978-3-642-20844-7_6. ISBN 978-3-642-20843-0.

Fankhauser S, Riesen K, Bunke H (2011) Speeding up graph edit distance computation through fast bipartite matching. In: Jiang X, Ferrer M, Torsello A (eds) Graph-based representations in pattern recognition, volume 6658 of LNCS. Springer Berlin, pp 102–111. doi:10.1007/978-3-642-20844-7_11. ISBN 978-3-642-20843-0

Gao X, Xiao B, Tao D, Li X (2008) Image categorization: graph edit direction histogram. Pattern Recognit 41(10):3179–3191. doi:10.1016/j.patcog.2008.03.025. ISSN 0031-3203

Gao X, Xiao B, Tao D, Li X (2010) A survey of graph edit distance. Pattern Anal Appl 13(1):113–129. doi:10.1007/s10044-008-0141-y. ISSN 1433-7541

Gärtner T (2008) Kernels for structured data. Number v. 72 in Kernels For Structured Data. World Scientific, Singapore. ISBN 9789812814555

Gibert J, Valveny E, Bunke H (2011) Dimensionality reduction for graph of words embedding. In: Jiang X, Ferrer M, Torsello A, (eds) Graph-based representations in pattern recognition, volume 6658 of LNCS. Springer, Berlin, pp 22–31. doi:10.1007/978-3-642-20844-7_3. ISBN 978-3-642-20843-0

Jain B, Obermayer K (2011) Maximum likelihood for gaussians on graphs. In: Jiang X, Ferrer M, Torsello A (eds) Graph-based representations in pattern recognition, volume 6658 of LNCS. Springer, Berlin, pp 62–71. doi:10.1007/978-3-642-20844-7_7. ISBN 978-3-642-20843-0

Jain BJ, Srinivasan SD, Tissen A, Obermayer K (2010) Learning graph quantization. In: Proceedings of the 2010 joint IAPR international conference on structural, syntactic, and statistical pattern recognition, SSPR&SPR’10. Springer, Berlin, pp 109–118. ISBN 3-642-14979-0, 978-3-642-14979-5

Kashima H, Tsuda K, Inokuchi A (2003) Marginalized kernels between labeled graphs. In: Proceedings of the twentieth international conference on machine learning. AAAI Press, pp 321–328

Livi L, Rizzi A (2012) The graph matching problem. Pattern Anal Appl. doi:10.1007/s10044-012-0284-8. ISSN 1433-7541

Livi L, Rizzi A (2012) Parallel algorithms for tensor product-based Inexact Graph Matching. In: Proceedings of the 2012 international joint conference on neural networks (IJCNN). IEEE, Berlin, pp 2276–2283. June. doi:10.1109/IJCNN.2012.6252681. ISBN 978-1-4673-1489-3

Livi L, Del Vescovo G, Rizzi A (2012a) Graph recognition by seriation and frequent substructures mining. In: Proceedings of the first international conference on pattern recognition applications and methods, vol 1, pp 186–191, Feb. doi:10.5220/0003733201860191. ISBN 978-989-8425-98-0

Livi L, Del Vescovo G, Rizzi A (2012b) Inexact Graph Matching through graph coverage. In: Proceedings of the first international conference on pattern recognition applications and methods, vol 1, pp 269–272, Feb. doi:10.5220/0003732802690272. ISBN 978-989-8425-98-0

Livi L, Del Vescovo G, Rizzi A (2012c) Combining graph seriation and substructures mining for graph recognition. Advances in Intelligent and Soft Computing. Springer, Berlin. http://dx.doi.org/10.1007/978-3-642-36530-0_7

Martins AFT, Smith NA, Xing EP, Aguiar PMQ, Figueiredo MAT (2009) Nonextensive information theoretic kernels on measures. J Mach Learn Res 10:935–975. ISSN 1532-4435

Neuhaus M, Bunke H (2007) Bridging the gap between graph edit distance and kernel machines. Series in machine perception and artificial intelligence. World Scientific, Singapore. ISBN 9789812708175

Neuhaus M, Riesen K, Bunke H (2006) Fast suboptimal algorithms for the computation of graph edit distance. In: Structural, syntactic, and statistical pattern recognition. LNCS. Springer, Berlin, pp 163–172

Pekalska E, Duin R (2005) The dissimilarity representation for pattern recognition: foundations and applications. Series in machine perception and artificial intelligence. World Scientific, Singapore. ISBN 9789812565303

Pedrycz W (2010) Human centricity in computing with fuzzy sets: an interpretability quest for higher order granular constructs. J Ambient Intell Human Comput 1:65–74. doi:10.1007/s12652-009-0008-0. ISSN 1868-5137

Príncipe JC (2010) Information theoretic learning: Renyi’s entropy and Kernel perspectives. Information Science and Statistics. Springer, Berlin. ISBN 9781441915696

Riesen K, Bunke H (2008) IAM graph database repository for graph based pattern recognition and machine learning. In: Proceedings of the 2008 joint IAPR international workshop on structural, syntactic, and statistical pattern recognition, SSPR & SPR ’08. Springer, Berlin, pp 287–297. doi:10.1007/978-3-540-89689-0_33. ISBN 978-3-540-89688-3

Riesen K, Bunke H (2009a) Graph classification by means of Lipschitz embedding. IEEE Trans Syst Man Cybern Part B 39:1472–1483. doi:10.1109/TSMCB.2009.2019264. ISSN 1083-4419

Riesen K, Bunke H (2009b) Approximate graph edit distance computation by means of bipartite graph matching. Image Vis Comput 27:950–959. doi:10.1016/j.imavis.2008.04.004. ISSN 0262-8856

Riesen K, Bunke H (2010) Graph classification and clustering based on vector space embedding. Series in Machine Perception and Artificial Intelligence. World Scientific Pub Co Inc, Singapore. ISBN 9789814304719

Rizzi A, Del Vescovo G (2006) Automatic image classification by a granular computing approach. In: Proceedings of the 2006 16th IEEE signal processing society workshop on machine learning for signal processing, pp 33–38. doi:10.1109/MLSP.2006.275517

Rizzi A, Panella M, Frattale Mascioli FM (2002) Adaptive resolution min-max classifiers. IEEE Trans Neural Netw 13:402–414. ISSN 1045-9227

Robles-Kelly A, Hancock ER (2005) Graph edit distance from spectral seriation. IEEE Trans Pattern Anal Mach Intell 27:365–378. doi:10.1109/TPAMI.2005.56. ISSN 0162-8828

Robles-Kelly A, Hancock ER (2007) A Riemannian approach to graph embedding. Pattern Recognit 40(3):1042–1056CrossRefMATH

Sakoe H (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoust Speech Signal Process 26:43–49CrossRefMATH

Schölkopf B, Smola A (2002) Learning with kernels: support vector machines, regularization, optimization, and beyond. Adaptive computation and machine learning. MIT Press. ISBN 9780262194754

Theodoridis S, Koutroumbas K (2006) Pattern recognition. Elsevier/Academic Press. ISBN 9780123695314

Tun K, Dhar P, Palumbo M, Giuliani A (2006) Metabolic pathways variability and sequence/networks comparisons. BMC Bioinform 7(1):24. doi:10.1186/1471-2105-7-24. ISSN 1471-2105

Xiao B, Gao X, Tao D, Li X (2008) HMM-based graph edit distance for image indexing. Int J Imaging Syst Technol 18(2–3):209–218. doi:10.1002/ima.20146 CrossRef

Yu H, Hancock ER (2006) String Kernels for matching seriated graphs. In: Proceedings of the 18th international conference on pattern recognition, volume 4 of ICPR ’06, IEEE Computer Society, Washington, DC, pp 224–228. doi:10.1109/ICPR.2006.1081. ISBN 0-7695-2521-0

Zhao Z, Wang L, Liu H, Ye J (2011) On similarity preserving feature selection. IEEE Trans Knowl Data Eng 99. ISSN 1041-4347. doi:10.1109/TKDE.2011.222 (pre print)

Title: A Granular Computing approach to the design of optimized graph classification systems
Authors: Filippo Maria Bianchi
Lorenzo Livi
Antonello Rizzi
Alireza Sadeghian
Publication date: 01-02-2014
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 2/2014
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-013-1065-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2014

Approximate optimal solution of the DTHJB equation for a class of nonlinear affine systems with unknown dead-zone constraints

Fault diagnosis of rolling element bearing by using multinomial logistic regression and wavelet packet transform

Patent value analysis using support vector machines

A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks

Neuro-fuzzy system with weighted attributes

On the order-theoretic properties of lower concept formula systems

Premium Partner