{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T00:09:01Z","timestamp":1787011741039,"version":"3.56.0"},"reference-count":65,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T00:00:00Z","timestamp":1598832000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Optimal transport theory has recently found many applications in machine learning thanks to its capacity to meaningfully compare various machine learning objects that are viewed as distributions. The Kantorovitch formulation, leading to the Wasserstein distance, focuses on the features of the elements of the objects, but treats them independently, whereas the Gromov\u2013Wasserstein distance focuses on the relations between the elements, depicting the structure of the object, yet discarding its features. In this paper, we study the Fused Gromov-Wasserstein distance that extends the Wasserstein and Gromov\u2013Wasserstein distances in order to encode simultaneously both the feature and structure information. We provide the mathematical framework for this distance in the continuous setting, prove its metric and interpolation properties, and provide a concentration result for the convergence of finite samples. We also illustrate and interpret its use in various applications, where structured objects are involved.<\/jats:p>","DOI":"10.3390\/a13090212","type":"journal-article","created":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T11:53:49Z","timestamp":1598874829000},"page":"212","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":96,"title":["Fused Gromov-Wasserstein Distance for Structured Objects"],"prefix":"10.3390","volume":"13","author":[{"given":"Titouan","family":"Vayer","sequence":"first","affiliation":[{"name":"CNRS, IRISA, Universit\u00e9 Bretagne-Sud, F-56000 Vannes, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laetitia","family":"Chapel","sequence":"additional","affiliation":[{"name":"CNRS, IRISA, Universit\u00e9 Bretagne-Sud, F-56000 Vannes, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Remi","family":"Flamary","sequence":"additional","affiliation":[{"name":"CNRS, OCA Lagrange, Universit\u00e9 C\u00f4te d\u2019Azur, F-06000 Nice, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Romain","family":"Tavenard","sequence":"additional","affiliation":[{"name":"CNRS, LETG, Universit\u00e9 Rennes, F-35000 Rennes, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Courty","sequence":"additional","affiliation":[{"name":"CNRS, IRISA, Universit\u00e9 Bretagne-Sud, F-56000 Vannes, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,31]]},"reference":[{"key":"ref_1","unstructured":"Battaglia, P.W., Hamrick, J.B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., and Faulkner, R. (2018). Relational inductive biases, deep learning, and graph networks. arXiv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0004-3702(86)90072-X","article-title":"Fusion, Propagation, and Structuring in Belief Networks","volume":"29","author":"Pearl","year":"1986","journal-title":"Artif. Intell."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Pearl, J. (2009). Causality: Models, Reasoning and Inference, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9780511803161"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1007694015589","article-title":"Relational Reinforcement Learning","volume":"43","author":"Driessens","year":"2001","journal-title":"Mach. Learn."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Hjort, N., Holmes, C., Mueller, P., and Walker, S. (2010). Bayesian Nonparametrics: Principles and Practice, Cambridge University Press.","DOI":"10.1017\/CBO9780511802478"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1038\/nature14539","article-title":"Deep learning","volume":"521","author":"LeCun","year":"2015","journal-title":"Nature"},{"key":"ref_7","unstructured":"Goodfellow, I., Bengio, Y., and Courville, A. (2016). Deep Learning, MIT Press."},{"key":"ref_8","first-page":"2539","article-title":"Weisfeiler-Lehman Graph Kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_9","unstructured":"Niepert, M., Ahmed, M., and Kutzkov, K. (2016, January 20\u201322). Learning Convolutional Neural Networks for Graphs. Proceedings of the International Conference on Machine Learning Research, New York, NY, USA."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bakir, G.H., Hofmann, T., Sch\u00f6lkopf, B., Smola, A.J., Taskar, B., and Vishwanathan, S.V.N. (2007). Predicting Structured Data (Neural Information Processing), The MIT Press.","DOI":"10.7551\/mitpress\/7443.001.0001"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/TASSP.1978.1163055","article-title":"Dynamic programming algorithm optimization for spoken word recognition","volume":"26","author":"Sakoe","year":"1978","journal-title":"IEEE Trans. Acoust. Speech Signal Process."},{"key":"ref_12","unstructured":"Cuturi, M., and Blondel, M. (2017, January 6\u201311). Soft-DTW: A Differentiable Loss Function for Time-Series. Proceedings of the 34th International Conference on Machine Learning (ICML 2017), Sydney, Australia."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Nowozin, S., Gehler, P.V., Jancsary, J., and Lampert, C.H. (2014). Advanced Structured Prediction, The MIT Press.","DOI":"10.7551\/mitpress\/9969.001.0001"},{"key":"ref_14","unstructured":"Niculae, V., Martins, A., Blondel, M., and Cardie, C. (2018, January 10\u201315). SparseMAP: Differentiable Sparse Structured Inference. Proceedings of the 35th International Conference on Machine Learning, Stockholm, Sweden."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Villani, C. (2008). Optimal Transport: Old and New, Springer. [2009th ed.]. Grundlehren der Mathematischen Wissenschaften.","DOI":"10.1007\/978-3-540-71050-9"},{"key":"ref_16","unstructured":"Sturm, K.T. (2012). The space of spaces: Curvature bounds and gradient flows on the space of metric measure spaces. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Memoli, F. (2011). Gromov Wasserstein Distances and the Metric Approach to Object Matching. Found. Comput. Math., 1\u201371.","DOI":"10.1007\/s10208-011-9093-5"},{"key":"ref_18","unstructured":"Vayer, T., Courty, N., Tavenard, R., Chapel, L., and Flamary, R. (2019, January 10\u201315). Optimal Transport for structured data with application on graphs. Proceedings of the 36th International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_19","unstructured":"Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (2017). Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs. Advances in Neural Information Processing Systems, Curran Associates, Inc."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1023\/A:1026543900054","article-title":"The Earth Mover\u2019s Distance as a Metric for Image Retrieval","volume":"40","author":"Rubner","year":"2000","journal-title":"Int. J. Comput. Vis."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1561\/2200000073","article-title":"Computational Optimal Transport","volume":"11","author":"Cuturi","year":"2019","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"72:1","DOI":"10.1145\/2897824.2925903","article-title":"Entropic Metric Alignment for Correspondence Problems","volume":"35","author":"Solomon","year":"2016","journal-title":"ACM Trans. Graph."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1111\/cgf.13244","article-title":"GWCNN: A Metric Alignment Layer for Deep Shape Analysis","volume":"36","author":"Ezuz","year":"2017","journal-title":"Comput. Graph. Forum"},{"key":"ref_24","unstructured":"Bunne, C., Alvarez-Melis, D., Krause, A., and Jegelka, S. (2019, January 9\u201315). Learning Generative Models across Incomparable Spaces. Proceedings of the 36th International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Demetci, P., Santorella, R., Sandstede, B., Noble, W.S., and Singh, R. (2020). Gromov-Wasserstein optimal transport to align single-cell multi-omics data. bioRxiv.","DOI":"10.1101\/2020.04.28.066787"},{"key":"ref_26","unstructured":"Peyr\u00e9, G., Cuturi, M., and Solomon, J. (2016, January 19\u201324). Gromov-Wasserstein averaging of kernel and distance matrices. Proceedings of the 33rd International Conference on Machine Learning (ICML 2016), New York, NY, USA."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Rasmussen, C.E., B\u00fclthoff, H.H., Sch\u00f6lkopf, B., and Giese, M.A. (2004). Learning with Distance Substitution Kernels. Pattern Recognition, Springer.","DOI":"10.1007\/b99676"},{"key":"ref_28","unstructured":"Borg, I., and Groenen, P. (2005). Modern Multidimensional Scaling: Theory and Applications, Springer."},{"key":"ref_29","unstructured":"Bachem, O., Lucic, M., and Krause, A. (2017). Practical Coreset Constructions for Machine Learning. arXiv."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10851-017-0726-4","article-title":"A Transportation Lp Distance for Signal Analysis","volume":"59","author":"Thorpe","year":"2017","journal-title":"J. Math. Imaging Vis."},{"key":"ref_31","unstructured":"Jonathan Weed, F.B. (2017). Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. arXiv."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s002110050002","article-title":"A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem","volume":"84","author":"Benamou","year":"2000","journal-title":"Numer. Math."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Bonneel, N., van de Panne, M., Paris, S., and Heidrich, W. (2011, January 11\u201315). Displacement Interpolation Using Lagrangian Mass Transport. Proceedings of the 2011 SIGGRAPH Asia Conference, Hong Kong, China.","DOI":"10.1145\/2070752.2024192"},{"key":"ref_34","unstructured":"Chizat, L., and Bach, F. (2018, January 3\u20138). On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport. Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canada."},{"key":"ref_35","unstructured":"Zhang, R., Chen, C., Li, C., and Duke, L.C. (2018, January 10\u201315). Policy Optimization as Wasserstein Gradient Flows. Proceedings of the 35th International Conference on Machine Learning, Stockholm, Sweden."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1853","DOI":"10.1137\/130929886","article-title":"Regularized discrete optimal transport","volume":"7","author":"Ferradans","year":"2014","journal-title":"SIAM J. Imaging Sci."},{"key":"ref_37","unstructured":"Flamary, R., Courty, N., Tuia, D., and Rakotomamonjy, A. (2014). Optimal transport with Laplacian regularization: Applications to domain adaptation and shape matching. NIPS Workshop on Optimal Transport and Machine Learning, OTML."},{"key":"ref_38","unstructured":"Lacoste-Julien, S. (2016). Convergence rate of Frank-Wolfe for non-convex objectives. arXiv."},{"key":"ref_39","unstructured":"Maron, H., and Lipman, Y. (2018, January 3\u20138). (Probably) Concave Graph Matching. Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canada."},{"key":"ref_40","unstructured":"Redko, I., Vayer, T., Flamary, R., and Courty, N. (2020). CO-Optimal Transport. arXiv."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1137\/100805741","article-title":"Barycenters in the Wasserstein space","volume":"43","author":"Agueh","year":"2011","journal-title":"SIAM J. Math. Anal."},{"key":"ref_42","unstructured":"Cuturi, M., and Doucet, A. (2014, January 22\u201324). Fast Computation of Wasserstein Barycenters. Proceedings of the 31st International Conference on Machine Learning, Bejing, China."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02289694","article-title":"Nonmetric multidimensional scaling: A numerical method","volume":"29","author":"Kruskal","year":"1964","journal-title":"Psychometrika"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1906","DOI":"10.1021\/ci034143r","article-title":"Spline-fitting with a genetic algorithm: A method for developing classification structure-activity relationships","volume":"43","author":"Sutherland","year":"2003","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"ref_45","unstructured":"Borgwardt, K.M., and Kriegel, H.P. (2005, January 27\u201330). Shortest-Path Kernels on Graphs. Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM\u201905), Houston, TX, USA."},{"key":"ref_46","unstructured":"Kriege, N., Fey, M., Fisseler, D., Mutzel, P., and Weichert, F. (2018, January 3\u20135). Recognizing Cuneiform Signs Using Graph Based Methods. Proceedings of the International Workshop on Cost-Sensitive Learning (COST), San Diego, CA, USA."},{"key":"ref_47","unstructured":"Feragen, A., Kasenburg, N., Petersen, J., de Bruijne, M., and Borgwardt, K. (2013, January 5\u201310). Scalable kernels for graphs with continuous attributes. Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems, Lake Tahoe, NV, USA."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1021\/jm00106a046","article-title":"Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity","volume":"34","author":"Debnath","year":"1991","journal-title":"J. Med. Chem."},{"key":"ref_49","unstructured":"Kriege, N.M., Giscard, P., and Wilson, R.C. (2016, January 5\u201310). On Valid Optimal Assignment Kernels and Applications to Graph Classification. Proceedings of the Advances in Neural Information Processing Systems, Barcelona, Spain."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10115-007-0103-5","article-title":"Comparison of descriptor spaces for chemical compound retrieval and classification","volume":"14","author":"Wale","year":"2008","journal-title":"Knowl. Inf. Syst."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Yanardag, P., and Vishwanathan, S. (2015, January 10\u201313). Deep Graph Kernels. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, Australia.","DOI":"10.1145\/2783258.2783417"},{"key":"ref_52","unstructured":"Kersting, K., Kriege, N.M., Morris, C., Mutzel, P., and Neumann, M. (2020, August 26). Benchmark Data Sets for Graph Kernels. Available online: https:\/\/ls11-www.cs.tu-dortmund.de\/staff\/morris\/graphkerneldatasets."},{"key":"ref_53","first-page":"1201","article-title":"Graph Kernels","volume":"11","author":"Vishwanathan","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"ref_54","unstructured":"Luss, R., and d\u2019Aspremont, A. (2007, January 3). Support Vector Machine Classification with Indefinite Kernels. Proceedings of the 20th International Conference on Neural Information Processing Systems, Kitakyushu, Japan."},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, T., Flach, P., and Wrobel, S. (2003). On graph kernels: Hardness results and efficient alternatives. Learning Theory and Kernel Machines, Springer.","DOI":"10.1007\/978-3-540-45167-9_11"},{"key":"ref_56","unstructured":"Shervashidze, N., Vishwanathan, S.V.N., Petri, T.H., Mehlhorn, K., and Borgwardt, K. (2009). Efficient graphlet kernels for large graph comparison. Artificial Intelligence and Statistics, Hilton Clearwater Beach Resort."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s10994-015-5517-9","article-title":"Propagation kernels: Efficient graph kernels from propagated information","volume":"102","author":"Neumann","year":"2016","journal-title":"Mach. Learn."},{"key":"ref_58","unstructured":"Siglidis, G., Nikolentzos, G., Limnios, S., Giatsidis, C., Skianis, K., and Vazirgianis, M. (2018). GraKeL: A Graph Kernel Library in Python. arXiv."},{"key":"ref_59","unstructured":"Shchur, O., Mumme, M., Bojchevski, A., and G\u00fcnnemann, S. (2018). Pitfalls of Graph Neural Network Evaluation. arXiv."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1080\/01621459.1987.10478385","article-title":"Stochastic blockmodels for directed graphs","volume":"82","author":"Wang","year":"1987","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1198\/016214501753208735","article-title":"Estimation and prediction for stochastic blockstructures","volume":"96","author":"Nowicki","year":"2001","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_62","doi-asserted-by":"crossref","unstructured":"Billingsley, P. (1999). Convergence of Probability Measures, John Wiley & Sons Inc.. [2nd ed.]. Wiley Series in Probability and Statistics: Probability and Statistics.","DOI":"10.1002\/9780470316962"},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Santambrogio, F. (2015). Optimal Transport for Applied Mathematicians, Birk\u00e4user.","DOI":"10.1007\/978-3-319-20828-2"},{"key":"ref_64","unstructured":"Ambrosio, L., Gigli, N., and Savare, G. (2005). Gradient Flows in Metric Spaces and in the Space of Probability Measures, Springer Science & Business Media."},{"key":"ref_65","unstructured":"Ambrosio, L., Gigli, N., and Savare, G. (2005). Gradient Flows: In Metric Spaces and in the Space of Probability Measures, ETH Z\u00fcrich, Birkh\u00e4user. Lectures in Mathematics."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/212\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:05:13Z","timestamp":1760177113000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,31]]},"references-count":65,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090212"],"URL":"https:\/\/doi.org\/10.3390\/a13090212","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,31]]}}}