{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:12:38Z","timestamp":1760242358621,"version":"build-2065373602"},"reference-count":55,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2017,5,9]],"date-time":"2017-05-09T00:00:00Z","timestamp":1494288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Representing patterns as labeled graphs is becoming increasingly common in the broad field of computational intelligence. Accordingly, a wide repertoire of pattern recognition tools, such as classifiers and knowledge discovery procedures, are nowadays available and tested for various datasets of labeled graphs. However, the design of effective learning procedures operating in the space of labeled graphs is still a challenging problem, especially from the computational complexity viewpoint. In this paper, we present a major improvement of a general-purpose classifier for graphs, which is conceived on an interplay between dissimilarity representation, clustering, information-theoretic techniques, and evolutionary optimization algorithms. The improvement focuses on a specific key subroutine devised to compress the input data. We prove different theorems which are fundamental to the setting of the parameters controlling such a compression operation. We demonstrate the effectiveness of the resulting classifier by benchmarking the developed variants on well-known datasets of labeled graphs, considering as distinct performance indicators the classification accuracy, computing time, and parsimony in terms of structural complexity of the synthesized classification models. The results show state-of-the-art standards in terms of test set accuracy and a considerable speed-up for what concerns the computing time.<\/jats:p>","DOI":"10.3390\/e19050216","type":"journal-article","created":{"date-parts":[[2017,5,9]],"date-time":"2017-05-09T11:50:48Z","timestamp":1494330648000},"page":"216","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Designing Labeled Graph Classifiers by Exploiting the R\u00e9nyi Entropy of the Dissimilarity Representation"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6384-4743","authenticated-orcid":false,"given":"Lorenzo","family":"Livi","sequence":"first","affiliation":[{"name":"Department of Computer Science, College of Engineering, Mathematics and Physical Sciences, University of Exeter, Exeter EX4 4QF, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,5,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s10044-012-0284-8","article-title":"The graph matching problem","volume":"16","author":"Livi","year":"2013","journal-title":"Pattern Anal. Appl."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1109\/TCSI.2012.2215780","article-title":"Kron Reduction of Graphs With Applications to Electrical Networks","volume":"60","author":"Bullo","year":"2013","journal-title":"IEEE Trans. Circuits Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3170","DOI":"10.1109\/TCSI.2008.925357","article-title":"Synchronization in random weighted directed networks","volume":"55","author":"Porfiri","year":"2008","journal-title":"IEEE Trans. Circuits Syst. I Regul. Pap."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.ins.2015.07.043","article-title":"Toward a multilevel representation of protein molecules: Comparative approaches to the aggregation\/folding propensity problem","volume":"326","author":"Livi","year":"2016","journal-title":"Inf. Sci."},{"key":"ref_5","first-page":"1598","article-title":"Protein contact networks: An emerging paradigm in chemistry","volume":"113","author":"Paci","year":"2012","journal-title":"Chem. Rev."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Bianchi, F.M., Livi, L., and Rizzi, A. (2013, January 4\u20139). Matching of Time-Varying Labeled Graphs. Proceedings of the 2013 International Joint Conference on Neural Networks (IJCNN), Dallas, TX, USA.","DOI":"10.1109\/IJCNN.2013.6706939"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2493","DOI":"10.1016\/j.eswa.2012.10.071","article-title":"Component retrieval based on a database of graphs for hand-written electronic-scheme digitalisation","volume":"40","author":"Serratosa","year":"2013","journal-title":"Expert Syst. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1159","DOI":"10.1016\/j.patcog.2011.08.017","article-title":"Interactive image segmentation by matching attributed relational graphs","volume":"45","author":"Noma","year":"2012","journal-title":"Pattern Recognit."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1007\/s13042-013-0210-4","article-title":"EM-type method for measuring graph dissimilarity","volume":"5","author":"Chen","year":"2014","journal-title":"Int. J. Mach. Learn. Cybern."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/s13042-014-0230-8","article-title":"Hybrid neural network for classification of graph structured data","volume":"6","author":"Jothi","year":"2015","journal-title":"Int. J. Mach. Learn. Cybern."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ins.2014.01.005","article-title":"Optimized dissimilarity space embedding for labeled graphs","volume":"266","author":"Livi","year":"2014","journal-title":"Inf. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/s00500-013-1065-z","article-title":"A Granular Computing approach to the design of optimized graph classification systems","volume":"18","author":"Bianchi","year":"2014","journal-title":"Soft Comput."},{"key":"ref_13","first-page":"399","article-title":"Graph-Based Representations in Pattern Recognition and Computational Intelligence","volume":"Volume 5517","author":"Cabestany","year":"2009","journal-title":"Bio-Inspired Systems: Computational and Ambient Intelligence"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2867","DOI":"10.1016\/S0031-3203(01)00232-1","article-title":"Inexact graph matching by means of estimation of distribution algorithms","volume":"35","author":"Bengoetxea","year":"2002","journal-title":"Pattern Recognit."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2099","DOI":"10.1016\/j.patcog.2005.05.007","article-title":"Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms","volume":"38","author":"Cesar","year":"2005","journal-title":"Pattern Recognit."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1016\/j.patcog.2005.10.008","article-title":"Protein classification by matching and clustering surface graphs","volume":"39","author":"Lozano","year":"2006","journal-title":"Pattern Recognit."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/s10851-012-0383-6","article-title":"Graph Kernels from the Jensen\u2013Shannon Divergence","volume":"47","author":"Bai","year":"2013","journal-title":"J. Math. Imaging Vis."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"3187","DOI":"10.1109\/TNNLS.2015.2418332","article-title":"Entropic One-Class Classifiers","volume":"26","author":"Livi","year":"2015","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_19","first-page":"90","article-title":"Information-Theoretic Dissimilarities for Graphs","volume":"Volume 7953","author":"Hancock","year":"2013","journal-title":"Similarity-Based Pattern Recognition"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1109\/TPAMI.2012.226","article-title":"A Game-Theoretic Approach to Hypergraph Clustering","volume":"35","author":"Pelillo","year":"2013","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_21","first-page":"2539","article-title":"Weisfeiler-Lehman Graph Kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.neucom.2013.01.015","article-title":"Graph matching and clustering using kernel attributes","volume":"113","author":"Lozano","year":"2013","journal-title":"Neurocomputing"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/j.patcog.2014.03.028","article-title":"A quantum Jensen\u2013Shannon graph kernel for unattributed graphs","volume":"48","author":"Bai","year":"2015","journal-title":"Pattern Recognit."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1016\/j.patrec.2011.04.017","article-title":"Towards the unification of structural and statistical pattern recognition","volume":"33","author":"Bunke","year":"2012","journal-title":"Pattern Recognit. Lett."},{"key":"ref_25","first-page":"180","article-title":"Fifty years of graph matching, network alignment and network comparison","volume":"346","author":"Dehmer","year":"2016","journal-title":"Inf. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"3072","DOI":"10.1016\/j.patcog.2012.01.009","article-title":"Graph embedding in vector spaces by node attribute statistics","volume":"45","author":"Gibert","year":"2012","journal-title":"Pattern Recognit."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Riesen, K., and Bunke, H. (2010). Graph Classification and Clustering Based on Vector Space Embedding, World Scientific.","DOI":"10.1142\/9789814304726"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1016\/j.patcog.2006.05.031","article-title":"A Riemannian approach to graph embedding","volume":"40","author":"Hancock","year":"2007","journal-title":"Pattern Recognit."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Escolano, F., Bonev, B., and Lozano, M. (2011, January 18\u201320). Information-Geometric Graph Indexing from Bags of Partial Node Coverages. Proceedings of the International Workshop on Graph-Based Representations in Pattern Recognition, M\u00fcnster, Germany.","DOI":"10.1007\/978-3-642-20844-7_6"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1016\/j.patcog.2012.07.029","article-title":"Fuzzy multilevel graph embedding","volume":"46","author":"Luqman","year":"2013","journal-title":"Pattern Recognit."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1648","DOI":"10.1016\/j.patcog.2012.11.020","article-title":"Discriminative prototype selection methods for graph embedding","volume":"46","author":"Borzeshi","year":"2013","journal-title":"Pattern Recognit."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1109\/TNN.2010.2091969","article-title":"Graph Characterization via Ihara Coefficients","volume":"22","author":"Ren","year":"2011","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-3-642-36530-0_7","article-title":"Combining Graph Seriation and Substructures Mining for Graph Recognition","volume":"Volume 204","author":"Fred","year":"2013","journal-title":"Pattern Recognition\u2014Applications and Methods"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.dam.2016.06.027","article-title":"On the geometry of graph spaces","volume":"214","author":"Jain","year":"2016","journal-title":"Discret. Appl. Math."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1016\/j.patcog.2016.06.023","article-title":"Statistical graph space analysis","volume":"60","author":"Jain","year":"2016","journal-title":"Pattern Recognit."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1016\/j.patrec.2011.08.012","article-title":"Pattern analysis with graphs: Parallel work at Bern and York","volume":"33","author":"Hancock","year":"2012","journal-title":"Pattern Recognit. Lett."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"P\u0229kalska, E., and Duin, R.P.W. (2005). The Dissimilarity Representation for Pattern Recognition: Foundations and Applications, World Scientific.","DOI":"10.1142\/9789812703170"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2039","DOI":"10.1162\/NECO_a_00770","article-title":"Indefinite Proximity Learning: A Review","volume":"27","author":"Schleif","year":"2015","journal-title":"Neural Comput."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Pr\u00edncipe, J.C. (2010). Information Theoretic Learning: Renyi\u2019s Entropy and Kernel Perspectives, Springer.","DOI":"10.1007\/978-1-4419-1570-2"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Livi, L., Bianchi, F.M., Rizzi, A., and Sadeghian, A. (2004, January 17). Dissimilarity space embedding of labeled graphs by a clustering-based compression procedure. Proceedings of the 2013 International Joint Conference on Neural Networks (IJCNN), Turku, Finland.","DOI":"10.1109\/IJCNN.2013.6706937"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s10044-008-0107-0","article-title":"Feature selection, mutual information, and the classification of high-dimensional patterns","volume":"11","author":"Bonev","year":"2008","journal-title":"Pattern Anal. Appl."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1921","DOI":"10.1109\/18.782114","article-title":"Asymptotic theory of greedy approximations to minimal k-point random graphs","volume":"45","author":"Hero","year":"1999","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1109\/72.991426","article-title":"Adaptive resolution min-max classifiers","volume":"13","author":"Rizzi","year":"2002","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.patcog.2007.05.018","article-title":"A survey of kernel and spectral methods for clustering","volume":"41","author":"Filippone","year":"2008","journal-title":"Pattern Recognit."},{"key":"ref_45","first-page":"9","article-title":"On the Problem of Modeling Structured Data with the MinSOD Representative","volume":"6","author":"Livi","year":"2014","journal-title":"Int. J. Comput. Theory Eng."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-540-89689-0_33","article-title":"IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning","volume":"Volume 5342","author":"Kasparis","year":"2008","journal-title":"Structural, Syntactic, and Statistical Pattern Recognition"},{"key":"ref_47","unstructured":"Livi, L., Del Vescovo, G., Rizzi, A., and Frattale Mascioli, F.M. (2014). Building Pattern Recognition Applications with the SPARE Library. arXiv."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1109\/TSMCB.2009.2019264","article-title":"Graph classification by means of Lipschitz embedding","volume":"39","author":"Riesen","year":"2009","journal-title":"IEEE Trans. Syst. Man Cybern. Part B"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.engappai.2008.04.006","article-title":"Reducing the dimensionality of dissimilarity space embedding graph kernels","volume":"22","author":"Riesen","year":"2009","journal-title":"Eng. Appl. Artif. Int."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"1928","DOI":"10.1016\/j.patcog.2010.05.016","article-title":"Improving vector space embedding of graphs through feature selection algorithms","volume":"44","author":"Bunke","year":"2011","journal-title":"Pattern Recognit."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-3-642-14980-1_10","article-title":"Learning Graph Quantization","volume":"Volume 6218","author":"Hancock","year":"2010","journal-title":"Structural, Syntactic, and Statistical Pattern Recognition"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Jiang, X., Ferrer, M., and Torsello, A. (2011, January 18\u201320). Maximum Likelihood for Gaussians on Graphs. Proceedings of the International Workshop on Graph-Based Representations in Pattern Recognition, M\u00fcnster, Germany.","DOI":"10.1007\/978-3-642-20844-7"},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Rizzi, A., Colabrese, S., and Baiocchi, A. (2013, January 1\u20135). Low complexity, high performance neuro-fuzzy system for Internet traffic flows early classification. Proceedings of the 2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC), Sardinia, Italy.","DOI":"10.1109\/IWCMC.2013.6583538"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"2255","DOI":"10.1109\/TPAMI.2014.2316836","article-title":"Spherical and Hyperbolic Embeddings of Data","volume":"36","author":"Wilson","year":"2014","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.patrec.2016.10.001","article-title":"Graph edit distance as a quadratic assignment problem","volume":"87","author":"Bougleux","year":"2017","journal-title":"Pattern Recognit. Lett."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/5\/216\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:35:13Z","timestamp":1760207713000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/5\/216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,9]]},"references-count":55,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2017,5]]}},"alternative-id":["e19050216"],"URL":"https:\/\/doi.org\/10.3390\/e19050216","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2017,5,9]]}}}