{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:08:18Z","timestamp":1760242098119,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T00:00:00Z","timestamp":1545091200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Post Doctor Research Foundation China with Grant","award":["45649"],"award-info":[{"award-number":["45649"]}]},{"name":"National Science Foundation (NSF) China with Grant","award":["61701502"],"award-info":[{"award-number":["61701502"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Graph kernels are of vital importance in the field of graph comparison and classification. However, how to compare and evaluate graph kernels and how to choose an optimal kernel for a practical classification problem remain open problems. In this paper, a comprehensive evaluation framework of graph kernels is proposed for unattributed graph classification. According to the kernel design methods, the whole graph kernel family can be categorized in five different dimensions, and then several representative graph kernels are chosen from these categories to perform the evaluation. With plenty of real-world and synthetic datasets, kernels are compared by many criteria such as classification accuracy, F1 score, runtime cost, scalability and applicability. Finally, quantitative conclusions are discussed based on the analyses of the extensive experimental results. The main contribution of this paper is that a comprehensive evaluation framework of graph kernels is proposed, which is significant for graph-classification applications and the future kernel research.<\/jats:p>","DOI":"10.3390\/e20120984","type":"journal-article","created":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T05:47:45Z","timestamp":1545112065000},"page":"984","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Comprehensive Evaluation of Graph Kernels for Unattributed Graphs"],"prefix":"10.3390","volume":"20","author":[{"given":"Yi","family":"Zhang","sequence":"first","affiliation":[{"name":"State Key Laboratory of Complex Electromagnetic Environment Effects on Electronics and Information System, Luoyang 471003, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lulu","family":"Wang","sequence":"additional","affiliation":[{"name":"National Innovation Institute of Defense Technology, Academy of Military Science, Beijing 100071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liandong","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Complex Electromagnetic Environment Effects on Electronics and Information System, Luoyang 471003, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1016\/j.patcog.2008.10.029","article-title":"Graph-based tools for microscopic cellular image segmentation","volume":"42","author":"Ta","year":"2009","journal-title":"Pattern Recognit."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1021271615909","article-title":"Maximum common subgraph isomorphism algorithms for the matching of chemical structures","volume":"16","author":"Raymond","year":"2002","journal-title":"J. Comput.-Aided Mol. Des."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Fan, W. (2012, January 26\u201329). Graph pattern matching revised for social network analysis. Proceedings of the International Conference on Database Theory, Berlin, Germany.","DOI":"10.1145\/2274576.2274578"},{"key":"ref_4","unstructured":"Ngomo, A.C.N., and Schumacher, F. (2009, January 1\u20137). BorderFlow: A Local Graph Clustering Algorithm for Natural Language Processing. Proceedings of the International Conference on Computational Linguistics and Intelligent Text Processing, Mexico City, Mexico."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10994-008-5086-2","article-title":"Graph kernels based on tree patterns for molecules","volume":"75","author":"Vert","year":"2009","journal-title":"Mach. Learn."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1109\/TNNLS.2013.2248093","article-title":"Backtrackless walks on a graph","volume":"24","author":"Aziz","year":"2013","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Neuhaus, M., and Bunke, H. (2007). Bridging the Gap between Graph Edit Distance and Kernel Machines, World Scientific.","DOI":"10.1142\/9789812770202"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Torresani, L., Kolmogorov, V., and Rother, C. (2008, January 12\u201318). Feature correspondence via graph matching: Models and global optimization. Proceedings of the Computer Vision\u2014ECCV, Marseille, France.","DOI":"10.1007\/978-3-540-88688-4_44"},{"key":"ref_9","first-page":"2539","article-title":"Weisfeiler-lehman graph kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_10","unstructured":"Shervashidze, N., Vishwanathan, S.V., Petri, T., Mehlhorn, K., and Borgwardt, K. (2009, January 16\u201318). Efficient graphlet kernels for large graph comparison. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, Clearwater Beach, FL, USA."},{"key":"ref_11","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_12","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.patrec.2016.08.019","article-title":"Quantum kernels for unattributed graphs using discrete-time quantum walks","volume":"87","author":"Bai","year":"2017","journal-title":"Pattern Recognit. Lett."},{"key":"ref_13","unstructured":"Orsini, F., Frasconi, P., and De Raedt, L. (2015, January 25\u201330). Graph invariant kernels. Proceedings of the 24th International Conference on Artificial Intelligence (AAAI 2015), Austin, TX, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Morris, C., Kriege, N.M., Kersting, K., and Mutzel, P. (2016, January 12\u201315). Faster kernels for graphs with continuous attributes via hashing. Proceedings of the IEEE 16th International Conference on Data Mining (ICDM 2016), Barcelona, Spain.","DOI":"10.1109\/ICDM.2016.0142"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"14689","DOI":"10.1073\/pnas.0305199101","article-title":"Local graph alignment and motif search in biological networks","volume":"101","author":"Berg","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s00020-009-1680-3","article-title":"Eigenvalues of integral operators defined by smooth positive definite kernels","volume":"64","author":"Ferreira","year":"2009","journal-title":"Integral Equ. Oper. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., and Blum, A. (2006, January 25\u201319). On a theory of learning with similarity functions. Proceedings of the International Conference on Machine Learning, Pittsburgh, PA, USA.","DOI":"10.1145\/1143844.1143854"},{"key":"ref_18","unstructured":"Chen, Y., Gupta, M.R., and Recht, B. (, January 14\u201318). Learning kernels from indefinite similarities. Proceedings of the International Conference on Machine Learning, Montreal, QC, Canada."},{"key":"ref_19","unstructured":"Haussler, D. (1999). Convolution Kernels on Discrete Structures, Department of Computer Science, University of California at Santa Cruz."},{"key":"ref_20","unstructured":"Bai, L. (2014). Information Theoretic Graph Kernels, University of York."},{"key":"ref_21","unstructured":"Bai, L., Rossi, L., Zhang, Z., and Hancock, E. (2015, January 6\u201311). An aligned subtree kernel for weighted graphs. Proceedings of the International Conference on Machine Learning (ICML 2015), Lille, France."},{"key":"ref_22","unstructured":"G\u00e4rtner, T., Flach, P., and Wrobel, S. (2003, January 24\u201327). On graph kernels: Hardness results and efficient alternatives. Proceedings of the Learning Theory and Kernel Machines 16th Annual Conference on Learning Theory and 7th Kernel Workshop (COLT\/Kernel 2003), Washington, DC, USA."},{"key":"ref_23","unstructured":"Borgwardt, K.M., and Kriegel, H.P. (2005, January 27\u201330). Shortest-path kernels on graphs. Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005), Houston, TX, USA."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"022815","DOI":"10.1103\/PhysRevE.91.022815","article-title":"Measuring Graph Similarity through Continuous-Time Quantum Walks and the Quantum Jensen-Shannon Divergence","volume":"91","author":"Rossi","year":"2015","journal-title":"Phys. Rev. E"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Bai, L., Rossi, L., Bunke, H., and Hancock, E.R. (2014, January 15\u201319). Hancock: Attributed Graph Kernels Using the Jensen-Tsallis q-Differences. Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Nancy, France.","DOI":"10.1007\/978-3-662-44848-9_7"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/s10851-012-0383-6","article-title":"Hancock: Graph Kernels from the Jensen-Shannon Divergence","volume":"47","author":"Bai","year":"2013","journal-title":"J. Math. Imaging Vis."},{"key":"ref_27","unstructured":"Bai, L., Zhang, Z., Wang, C., Bai, X., and Hancock, E.R. (2015, January 25\u201331). Hancock: A Graph Kernel Based on the Jensen-Shannon Representation Alignment. Proceedings of the IJCAI, Buenos Aires, Argentina."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"3357","DOI":"10.1016\/j.patcog.2015.03.018","article-title":"Unfolding Kernel Embeddings of Graphs: Enhancing Class Separation through Manifold Learning","volume":"48","author":"Rossi","year":"2015","journal-title":"Pattern Recognit."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Fr\u00f6hlich, H., Wegner, J.K., Sieker, F., and Zell, A. (2005, January 6\u201311). Optimal assignment kernels for attributed molecular graphs. Proceedings of the 22nd International Conference on Machine Learning (ICML 2005), Lille, France.","DOI":"10.1145\/1102351.1102380"},{"key":"ref_30","unstructured":"Vert, J.P. (arXiv, 2008). The optimal assignment kernel is not positive definite, arXiv."},{"key":"ref_31","unstructured":"Kriege, N.M., Giscard, P.L., and Wilson, R. (2016, January 5\u201310). On valid optimal assignment kernels and applications to graph classification. Proceedings of the Advances in Neural Information Processing Systems (NIPS 2016), Barcelona, Spain."},{"key":"ref_32","unstructured":"Johansson, F., Jethava, V., Dubhashi, D., and Bhattacharyya, C. (2014, January 21\u201326). Global graph kernels using geometric embeddings. Proceedings of the 31st International Conference on Machine Learning (ICML 2014), Beijing, China."},{"key":"ref_33","unstructured":"Kondor, R., and Pan, H. (2016, January 5\u201310). The multiscale Laplacian graph kernel. Proceedings of the Advances in Neural Information Processing Systems (NIPS 2016), Barcelona, Spain."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"180501","DOI":"10.1103\/PhysRevLett.102.180501","article-title":"Universal computation by quantum walk","volume":"102","author":"Childs","year":"2009","journal-title":"Phys. Rev. Lett."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Bai, L., Zhang, Z., Ren, P., Rossi, L., and Hancock, E.R. (2015, January 7\u201311). An edge-based matching kernel through discrete-time quantum walks. Proceedings of the International Conference on Image Analysis and Processing (ICIAP 2015), Genoa, Italy.","DOI":"10.1007\/978-3-319-23231-7_3"},{"key":"ref_36","unstructured":"Feragen, A., Kasenburg, N., Petersen, J., de Bruijne, M., and Borgwardt, K. (2013, January 5\u20138). Scalable kernels for graphs with continuous attributes. Proceedings of the Advances in Neural Information Processing Systems (NIPS 2013), Lake Tahoe, NV, USA."},{"key":"ref_37","unstructured":"Costa, F., and de Grave, K. (2010, January 21\u201324). Fast neighborhood subgraph pairwise distance kernel. Proceedings of the ICML, Haifa, Israel."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Horv\u00e1th, T., G\u00e4rtner, T., and Wrobel, S. (2004, January 22\u201325). Cyclic pattern kernels for predictive graph mining. Proceedings of the KDD, Seattle, WA, USA.","DOI":"10.1145\/1014052.1014072"},{"key":"ref_39","unstructured":"(2018, June 15). The Graph Kernel Benchmarks. Available online: https:\/\/ls11-www.cs.tu-dortmund.de\/staff\/morris\/graphkerneldatasets."},{"key":"ref_40","unstructured":"(2018, September 10). The Datasets and the Matlab Codes. Available online: https:\/\/github.com\/YiZhangNUDT\/graph_kernel_test."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1961189.1961199","article-title":"LIBSVM: A library for support vector machines","volume":"2","author":"Chang","year":"2011","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Liu, X., Dou, Y., Yin, J., Wang, L., and Zhu, E. (2016, January 12\u201317). Multiple Kernel k-Means Clustering with Matrix-Induced Regularization. Proceedings of the AAAI 2016, Phoenix, AZ, USA.","DOI":"10.1609\/aaai.v30i1.10249"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/12\/984\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:34:43Z","timestamp":1760196883000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/12\/984"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,18]]},"references-count":42,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2018,12]]}},"alternative-id":["e20120984"],"URL":"https:\/\/doi.org\/10.3390\/e20120984","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2018,12,18]]}}}