Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties

Abstract

Optimal transport theory has recently found many applications in machine learning thanks to its capacity for comparing various machine learning objects considered as distributions. The Kantorovitch formulation, leading to the Wasserstein distance, focuses on the features of the elements of the objects but treat them independently, whereas the Gromov-Wasserstein distance focuses only on the relations between the elements, depicting the structure of the object, yet discarding its features. In this paper we propose to extend these distances in order to encode simultaneously both the feature and structure informations, resulting in the Fused Gromov-Wasserstein distance. We develop the mathematical framework for this novel distance, 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 contexts where structured objects are involved.

References in corpus (3)

• Learning Convolutional Neural Networks for Graphs
• Soft-DTW: a Differentiable Loss Function for Time-Series
• SparseMAP: Differentiable Sparse Structured Inference

Cited by in corpus (15)

• Gromov-Wasserstein Learning for Graph Matching and Node Embedding
• Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching
• Domain Adaptation for Robust Workload Level Alignment Between Sessions and Subjects using fNIRS
• The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
• Learning Autoencoders with Relational Regularization
• Generalized Spectral Clustering via Gromov-Wasserstein Learning
• Partial Optimal Transport with Applications on Positive-Unlabeled Learning
• Aligning individual brains with Fused Unbalanced Gromov-Wasserstein
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
• Fused Gromov-Wasserstein Alignment for Hawkes Processes
• Unsupervised Hierarchy Matching with Optimal Transport over Hyperbolic Spaces
• Learning Graphons via Structured Gromov-Wasserstein Barycenters
• Online Graph Dictionary Learning
• Heterogeneous Wasserstein Discrepancy for Incomparable Distributions
• Hawkes Processes on Graphons