{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T16:51:27Z","timestamp":1778172687420,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T00:00:00Z","timestamp":1651017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T00:00:00Z","timestamp":1651017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Competence center for machine learning ML2R"},{"DOI":"10.13039\/501100008131","name":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008131","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>After more than one decade, Weisfeiler-Lehman graph kernels are still among the most prevalent graph kernels due to their remarkable predictive performance and time complexity. They are based on a fast iterative partitioning of vertices, originally designed for deciding graph isomorphism with one-sided error. The Weisfeiler-Lehman graph kernels retain this idea and compare such labels with respect to equality. This binary valued comparison is, however, arguably too rigid for defining suitable graph kernels for certain graph classes. To overcome this limitation, we propose a generalization of Weisfeiler-Lehman graph kernels which takes into account a more natural and finer grade of similarity between Weisfeiler-Lehman labels than equality. We show that the proposed similarity can be calculated efficiently by means of the Wasserstein distance between certain vectors representing Weisfeiler-Lehman labels. This and other facts give rise to the natural choice of partitioning the vertices with the Wasserstein k-means algorithm. We empirically demonstrate on the Weisfeiler-Lehman subtree kernel, which is one of the most prominent Weisfeiler-Lehman graph kernels, that our generalization significantly outperforms this and other state-of-the-art graph kernels in terms of predictive performance on datasets which contain structurally more complex graphs beyond the typically considered molecular graphs.<\/jats:p>","DOI":"10.1007\/s10994-022-06131-w","type":"journal-article","created":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T17:02:53Z","timestamp":1651078973000},"page":"2601-2629","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["A generalized Weisfeiler-Lehman graph kernel"],"prefix":"10.1007","volume":"111","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3163-325X","authenticated-orcid":false,"given":"Till Hendrik","family":"Schulz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6852-6939","authenticated-orcid":false,"given":"Tam\u00e1s","family":"Horv\u00e1th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2123-3781","authenticated-orcid":false,"given":"Pascal","family":"Welke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Wrobel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,27]]},"reference":[{"key":"6131_CR1","doi-asserted-by":"crossref","unstructured":"Al-Rfou, R., Perozzi, B., & Zelle, D. (2019). DDGK: learning graph representations for deep divergence graph kernels. In: The World Wide Web Conference 2019, ACM, pp. 37\u201348.","DOI":"10.1145\/3308558.3313668"},{"key":"6131_CR2","unstructured":"Babai, L., & Kucera, L. (1979). Graph canonization in linear average time. In: FOCS, pp. 39\u201346."},{"issue":"1\u20133","key":"6131_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P Bille","year":"2005","unstructured":"Bille, P. (2005). A survey on tree edit distance and related problems. Theoretical Computer Science, 337(1\u20133), 217\u2013239.","journal-title":"Theoretical Computer Science"},{"key":"6131_CR4","doi-asserted-by":"crossref","unstructured":"Borgwardt, K. M., & Kriegel, H. P. (2005). Shortest-path kernels on graphs. In: ICDM \u201905, pp 74 \u2014 81.","DOI":"10.1109\/ICDM.2005.132"},{"key":"6131_CR5","first-page":"15868","volume":"2019","author":"Z Chen","year":"2019","unstructured":"Chen, Z., Villar, S., Chen, L., & Bruna, J. (2019). On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in Neural Information Processing Systems, 2019, 15868\u201315876.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6131_CR6","unstructured":"Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. In: Advances in Neural Information Processing Systems, pp. 2292\u20132300."},{"key":"6131_CR7","unstructured":"Cuturi, M., & Doucet, A. (2014). Fast computation of wasserstein barycenters. In: International Conference on Machine Learning, pp. 685\u2013693."},{"key":"6131_CR8","doi-asserted-by":"crossref","unstructured":"Da San Martino, G., Navarin, N., & Sperduti, A. (2012). A tree-based kernel for graphs. In: SIAM International Conference on Data Mining, pp. 975\u2013986.","DOI":"10.1137\/1.9781611972825.84"},{"key":"6131_CR9","unstructured":"Dell, H., Grohe, M., & Rattan, G. (2018). Lov\u00e1sz meets Weisfeiler and Leman. In: International Colloquium on Automata, Languages and Programming, pp. 40:1\u201340:14."},{"key":"6131_CR10","first-page":"175","volume":"2020","author":"F Errica","year":"2020","unstructured":"Errica, F., Bacciu, D., & Micheli, A. (2020). Theoretically expressive and edge-aware graph learning. ESANN, 2020, 175\u2013180.","journal-title":"ESANN"},{"key":"6131_CR11","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, T., Flach, P., & Wrobel, S. (2003). On graph kernels: Hardness results and efficient alternatives. In: COLT\/Kernel, pp. 129\u2013143.","DOI":"10.1007\/978-3-540-45167-9_11"},{"key":"6131_CR12","unstructured":"Haussler, D. (1999). Convolution kernels on discrete structures. Technical report, Department of Computer Science, University of California at Santa Cruz."},{"issue":"7","key":"6131_CR13","doi-asserted-by":"publisher","first-page":"3351","DOI":"10.1016\/j.eswa.2013.12.001","volume":"41","author":"A Irpino","year":"2014","unstructured":"Irpino, A., Verde, R., & de Carvalho, F. A. T. (2014). Dynamic clustering of histogram data based on adaptive squared Wasserstein distances. Expert Systems with Applications, 41(7), 3351\u20133366.","journal-title":"Expert Systems with Applications"},{"key":"6131_CR14","unstructured":"Kriege, N. M., Giscard, P., & Wilson, R. C. (2016). On valid optimal assignment kernels and applications to graph classification. In: Advances in Neural Information Processing Systems, pp. 1615\u20131623."},{"issue":"1","key":"6131_CR15","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/s41109-019-0195-3","volume":"5","author":"NM Kriege","year":"2020","unstructured":"Kriege, N. M., Johansson, F. D., & Morris, C. (2020). A survey on graph kernels. Applied Network Science, 5(1), 6.","journal-title":"Applied Network Science"},{"key":"6131_CR16","first-page":"3530","volume":"97","author":"A Kroshnin","year":"2019","unstructured":"Kroshnin, A., Tupitsa, N., Dvinskikh, D., Dvurechensky, P., Gasnikov, A., & Uribe, C. (2019). On the complexity of approximating Wasserstein barycenters. Proceedings of the International Conference on Machine Learning, 97, 3530\u20133540.","journal-title":"Proceedings of the International Conference on Machine Learning"},{"key":"6131_CR17","unstructured":"Leskovec, J., & Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"issue":"2","key":"6131_CR18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129\u2013137. https:\/\/doi.org\/10.1109\/TIT.1982.1056489.","journal-title":"IEEE Transactions on Information Theory"},{"key":"6131_CR19","doi-asserted-by":"publisher","first-page":"4602","DOI":"10.1609\/aaai.v33i01.33014602","volume":"2019","author":"C Morris","year":"2019","unstructured":"Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. (2019). Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 4602\u20134609.","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"6131_CR20","unstructured":"Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., & Neumann, M. (2020). Tudataset: A collection of benchmark datasets for learning with graphs. In: GRL+@ICML, arXiv:2007.08663."},{"key":"6131_CR21","unstructured":"Rieck, B., Bock, C., & Borgwardt, K. (2019). A persistent Weisfeiler-Lehman procedure for graph classification. In: International Conference on Machine Learning, pp. 5448\u20135458."},{"issue":"12","key":"6131_CR22","doi-asserted-by":"publisher","first-page":"1540","DOI":"10.1109\/TPAMI.2003.1251147","volume":"25","author":"V Roth","year":"2003","unstructured":"Roth, V., Laub, J., Kawanabe, M., & Buhmann, J. (2003). Optimal cluster preserving embedding of nonmetric proximity data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(12), 1540\u20131551. https:\/\/doi.org\/10.1109\/TPAMI.2003.1251147.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"6131_CR23","unstructured":"Shervashidze, N., Vishwanathan, S. V. N., Petri, T., Mehlhorn, K., & Borgwardt, K. M. (2009). Efficient graphlet kernels for large graph comparison. In: Artificial Intelligence and Statistics, pp. 488\u2013495."},{"key":"6131_CR24","first-page":"2539","volume":"12","author":"N Shervashidze","year":"2011","unstructured":"Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., & Borgwardt, K. M. (2011). Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12, 2539\u20132561.","journal-title":"Journal of Machine Learning Research"},{"key":"6131_CR25","unstructured":"Siglidis, G., Nikolentzos, G., Limnios, S., Giatsidis, C., Skianis, K., & Vazirgiannis, M. (2018). GraKel: A graph kernel library in Python. arXiv preprint arXiv:1806.02193. https:\/\/github.com\/ysig\/GraKeL."},{"key":"6131_CR26","unstructured":"Smola, A. J., & Vishwanathan, S. (2003). Fast kernels for string and tree matching. In: Kernel Methods in Computational Biology, pp. 585\u2013592."},{"key":"6131_CR27","unstructured":"Togninalli, M., Ghisu, E., Llinares-L\u00f3pez, F., Rieck, B., & Borgwardt, K. (2019). Wasserstein Weisfeiler-Lehman graph kernels. In: Advances in Neural Information Processing Systems, pp. 6439\u20136449."},{"issue":"397","key":"6131_CR28","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1080\/01621459.1987.10478385","volume":"82","author":"YJ Wang","year":"1987","unstructured":"Wang, Y. J., & Wong, G. Y. (1987). Stochastic blockmodels for directed graphs. Journal of the American Statistical Association, 82(397), 8\u201319.","journal-title":"Journal of the American Statistical Association"},{"key":"6131_CR29","unstructured":"Weisfeiler, B., & Lehman, A. A. (1968). A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia, 2(9)."},{"key":"6131_CR30","unstructured":"Wu, G., Chang, E. Y., & Zhang, Z. (2005). An analysis of transformation on non-positive semidefinite similarity matrix for kernel machines. In: Proceedings of the 22nd International Conference on Machine Learning."},{"key":"6131_CR31","unstructured":"Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How powerful are graph neural networks? In: ICLR 2019."},{"key":"6131_CR32","unstructured":"Zafarani, R., & Liu, H. (2009).Social computing data repository at ASU. http:\/\/socialcomputing.asu.edu, accessed: 2019-06-25, offline at the time of submission."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06131-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-022-06131-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06131-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T21:08:49Z","timestamp":1657055329000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-022-06131-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,27]]},"references-count":32,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["6131"],"URL":"https:\/\/doi.org\/10.1007\/s10994-022-06131-w","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,27]]},"assertion":[{"value":"31 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This study was funded by Competence Center for Machine Learning Rhine-Ruhr (see above). The authors have no other financial or proprietary interests in any material discussed in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The authors assure that all potential conflicts of interest have been disclosed above. All research performed in this article was done in accordance with the ethical standards of the Springer ethics code of conduct.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"All listed authors have agreed to submitting the attached article to the Machine Learning Journal.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable. (The authors assure that no figures, tables and text passages have been obtained from third party authors.)","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}