Source-linked AI summary
Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties
Titouan Vayer, Laetita Chapel, Rémi Flamary, Romain Tavenard, Nicolas Courty
TL;DR
Structured-object comparison requires representing both feature information and the relations among elements, since Wasserstein and Gromov-Wasserstein distances focus on only one of these aspects. The paper introduces Fused Gromov-Wasserstein distance, develops its theoretical properties, and illustrates applications including graph barycenters, clustering, and mesh interpolation.
Problem
Wasserstein and Gromov-Wasserstein distances separately focus on feature and structure marginals, so they fail to compare structured objects in their entirety.
Method
The paper represents structured objects as distributions and introduces Fused Gromov-Wasserstein distance to encode feature information and inherent relations simultaneously.
Results
The paper establishes that FGW is a metric in a given case, derives concentration, interpolation, and geodesic results, and illustrates applications to graph barycenters, clustering, and mesh interpolation.
Takeaways & Limitations
FGW compares structured objects using both their features and their structures, with demonstrations on structured-object applications.
Takeaways & Limitations
The geodesic is difficult to handle in practice because it requires computing the Cartesian product X0 × X1, motivating a Fréchet-mean extension.
Abstract
from arXiv · showhide
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.
2 Structured objects as distributions and Fused Gromov Wasserstein distance
The section covers comparison of structured objects, optimal transport distances, and the fused Gromov-Wasserstein distance.
- 2.1 Comparing structured objects: The section includes a discussion of comparing structured objects.
- 2.2 Background on OT distances: It introduces background on optimal transport distances.
- 2.3 Fused Gromov-Wasserstein distance: It presents the fused Gromov-Wasserstein distance.
1. Introduction
The paper frames structured objects as entities defined by both features and relationships, motivating optimal-transport representations that compare these aspects jointly. It introduces the Fused Gromov-Wasserstein distance and develops its theoretical foundations for such comparisons.
- Motivation: Structured objects combine feature information, such as labels or signals, with structure information describing relationships among elements.Examples include graph node labels, time-series signal values, spatial positions in shape analysis, and local color histograms in images.
- Motivation: Including structural knowledge can support more generalizable machine-learning models and learning from small amounts of data.The paper cites graphical models, relational reinforcement learning, and Bayesian nonparametrics as contexts where entities and interactions matter.
- Related approaches: Existing approaches incorporate structure in object-dependent ways, while other methods compare features or predict structure as an output.Examples include graph-classification methods, Dynamic Time Warping for time series, image segmentation, and natural-language sentence prediction.
- Optimal-transport representation: Optimal transport compares probability distributions by using cost functions that capture geometric properties of their underlying spaces.The paper uses distributions as representations of machine-learning objects within the optimal-transport framework.
- Contribution: Wasserstein distance compares feature information and Gromov-Wasserstein distance compares structural information, but neither compares the entire structured object.The paper therefore proposes the Fused Gromov-Wasserstein distance to encode both types of information simultaneously.
- Mathematical setup: A structured object can be represented as a fully supported probability measure over the product of feature and structure spaces, with marginals for each component.The framework defines couplings between probability measures and assumes metric spaces are Polish, non-trivial, with Borel measures.
2. Structured objects as distributions and Fused Gromov Wasserstein distance
The paper represents structured objects as probability distributions carrying both feature information and metric structure, then introduces FGW to compare these jointly. FGW combines feature and structural costs, extending Wasserstein and Gromov-Wasserstein comparisons while distinguishing objects that those distances may identify separately.
- Structured-object representation: Structured objects are represented as labelled vertices with features organized by intrinsic relations encoded through a metric.In the discrete case, a labelled graph is described by vertex representations and feature labels, with the vertex metric encoding relations.
- Structured-object representation: A structured object is a triplet consisting of a compact metric structure space, a compact feature set, and a fully supported probability measure over their product.The measure can assign relative importance to elements, such as node weights in a graph.
- Structured-object representation: The joint measure contains the whole structured object, whereas its structure and feature marginals retain only partial information.The feature sets share a common ambient space, making features directly comparable, but separate marginals omit their joint organization.
- Comparing structured objects: Wasserstein compares feature distributions, while Gromov-Wasserstein compares metric structures; each alone can miss information from the complete structured object.The paper motivates FGW as a joint alternative to these separate comparisons.
- Comparing structured objects: Equivalence requires a measure-preserving map whose structure component is an isometry and whose feature component is the identity.Thus, isometric structures with identical individual features can still fail to be equivalent when feature-structure correspondences differ.
- Fused Gromov-Wasserstein distance: FGW uses a convex combination of feature and structure costs, with α controlling their trade-off and enabling interpolation between the two types of information.The paper states that this formulation supports topology, geodesic properties, and gradient flows on structured objects.
3. Mathematical properties of FGW
The paper establishes FGW as a mathematically well-behaved distance for structured objects, combining feature and structural information. It proves metric, interpolation, convergence, concentration, and geodesic properties, while identifying practical limitations of geodesic computation.
- Metric properties: FGW is symmetric; it satisfies the triangle inequality for q = 1, while q ⩾2 yields a relaxed inequality with factor 2q−1.
- Metric properties: FGW is a distance on structured-object space modulo measure-preserving maps that preserve features and structure through an isometry.Its value vanishes exactly when structured objects are equivalent under the paper’s feature- and structure-preserving relation.
- Finite-sample convergence: Finite samples are shown to converge in the FGW sense, and the paper presents a concentration result for Gromov-Wasserstein distance that it identifies as the first of its kind.The authors note that the bound is not necessarily sharp compared with the Wasserstein case, but supports sampling continuous distributions for GW and FGW.
- Interpolation properties: As α tends to zero, FGW recovers the Wasserstein distance for feature information, whereas α tending to one recovers Gromov-Wasserstein for structure information.Thus, α interpolates between feature-based and structure-based comparisons and can be tuned to the data properties.
- Geodesic properties: The FGW space has geodesics, and for p = 1 and q ⩾2, each geodesic in H(Rd) has the form specified by Eq. (3.11).The dynamic formulation represents optimal transport as a minimum-length curve of measures, supporting interpolation along geodesic paths.
- Geodesic properties: The practical geodesic is difficult to handle because it requires computing the Cartesian product X0 × X1; a Fréchet-mean extension is proposed to overcome this obstacle.The definition and properties of associated velocity fields are postponed to future work.
4. Examples and applications for the discrete case
The paper illustrates FGW on images, time series, graphs, and meshes, showing how it combines feature and structural information in comparisons, barycenters, and interpolations.
- Illustrations of FGW: FGW retrieves transport matrices that respect both feature clusters and noisy temporal structure, unlike Wasserstein or Gromov-Wasserstein alone.In the 1D example, Wasserstein respects clustering but ignores temporal structure, while Gromov-Wasserstein does the reverse.
- Illustrations of FGW: FGW aligns recentered MNIST digits while recovering pixel order, whereas Wasserstein and Gromov-Wasserstein fail to provide meaningful transportation maps.Wasserstein and Gromov-Wasserstein distances are both zero in this example, while FGW distinguishes the images.
- Illustrations of FGW: A reasonable intermediate α produces the most discriminant time-series embedding by balancing temporal alignment with similarity of signal values.Wasserstein assigns samples independently of temporal position, while Gromov-Wasserstein aligns positions but discards signal values.
- Structured Optimal Transport Barycenter: FGW barycenters seek structured objects minimizing weighted FGW distances to input objects, combining their features and structures.The barycenter formulation can vary feature values and the structure relating them, under fixed histogram assumptions in the presented setting.
- Structured Optimal Transport Barycenter: For graph samples, FGW barycenters recover compressed or high-resolution graph representations while providing node correspondences through the transport matrix.The experiment uses shortest-path structure and feature distances to compute barycenters from noisy circle and 8-shaped graphs.
- Structured Optimal Transport Barycenter: FGW mesh interpolation preserves manifold consistency more effectively when structural information receives high weight than when only 3D distances match vertices.The deer and cat meshes have 460 and 989 vertices respectively, and feature-only matching can pair different mesh regions because of density differences.
5. Proofs of the mathematical properties
The proofs establish existence of optimal FGW couplings, characterize when FGW vanishes, and derive symmetry, triangle-type, convergence, and geodesic properties. They also show how these results follow from compactness, Lipschitz continuity, coupling constructions, and standard inequalities.
- Geodesic properties: FGW interpolation changes the balance between feature and structure information: high α accounts for structure, whereas very low α nearly ignores mesh structure.The cat–deer mesh interpolation illustrates the effect of α on the resulting geodesic.
- Convergence and concentration: The FGW distance converges under weak convergence of empirical measures, with concentration obtained by applying the finite-sample bound to measures in the same ground space.The convergence argument follows from weak convergence and the minimization lemma.
- Existence of optimal couplings: An optimal coupling exists for FGW for all p,q ⩾1.The proof rewrites the FGW objective as an integral over a compact product space and applies sequential compactness and a minimization lemma.
- Metric properties: FGW,α,p,q(µ,ν) = 0 iff a feature- and structure-preserving map satisfying (3.1), (3.3), and (3.2) exists.The converse uses vanishing Gromov-Wasserstein loss and full support to conclude that the feature map is the identity on the feature space.
- Metric properties: FGW,α,p,q is symmetric; for q = 1 it satisfies the triangle inequality, while for q ⩾2 the triangle inequality is relaxed by a factor 2^q−1.The proof uses the gluing lemma to combine optimal couplings and Minkowski’s inequality.
- Geodesic properties: The constructed coupling along the geodesic is optimal between its endpoints, and the geodesic is equivalent to the interpolating structured object defined from the endpoint coupling.This establishes the stated geodesic equivalence under the structured-object equivalence relation.
6. Conclusion
The paper introduces FGW as an optimal-transport distance for structured objects that combines feature information with relations among elements. It develops mathematical properties including metric behavior and interpolation for this combined representation.
- Conclusion: FGW compares structured objects using both feature information in a common ground space and inherent relations defining their structure.The distance is designed to combine the feature and structural information that Wasserstein and Gromov-Wasserstein approaches treat separately.
- Conclusion: The paper establishes mathematical results for FGW, including metric and interpolation properties.These results provide the theoretical framework for the proposed structured-object distance.