Note on the computational complexity of Gromov-Wasserstein distance.
problem Computational difficulty of Gromov-Wasserstein distance.
method Analysis of the optimization problem structure and providing explicit examples.
result Gromov-Wasserstein distance optimization problem is non-convex quadratic.
Study of Gaussian distributions using entropic Gromov-Wasserstein and inner product Gromov-Wasserstein.
problem Optimal transportation between Gaussian distributions with different dimensions.
method Entropic Gromov-Wasserstein and inner product Gromov-Wasserstein, with closed-form expressions and von Neumann's trace inequality.
result Closed-form expressions for the entropic IGW and its unbalanced variant between Gaussian distributions.
Stability of Wasserstein spaces under various convergence types.
problem Stability and finiteness of Wasserstein spaces over singular and non-singular spaces.
method Gromov--Hausdorff convergence and equivariant Gromov--Hausdorff convergence.
result Analogue of Perelman's stability theorem on Wasserstein spaces.
We propose a novel fused Gromov-Wasserstein alignment method to jointly learn the Hawkes processes in different event spaces, and align their event types. Given two Hawkes processes, we use fused Gromov-Wasserstein discrepancy to measure their dissimilarity, which considers both the Wasserstein discrepancy based on the…
Method learns graphons from graphs via Gromov-Wasserstein barycenters.
problem Learning nonparametric graph models from finite graphs.
method Approximate graphons with step functions, use Gromov-Wasserstein distance, learn barycenters.
result Proposed method outperforms state-of-the-art on synthetic and real-world data.
New Gromov-Wasserstein metric controls rigidity and incorporates prior knowledge.
problem Inflexible Gromov-Wasserstein distance and lack of feature alignment.
method Augmented Gromov-Wasserstein distance with feature alignments and prior knowledge.
result Improved performance in single-cell multi-omic alignment and transfer learning.
A method for learning embeddings from multi-view data using Gromov-Wasserstein.
problem Challenges in learning low-dimensional representations from multi-view relational data with differing geometries.
method Bary-GWMDS and Mean-GWMDS-C, Gromov-Wasserstein-based methods operating on distance matrices.
result Stable and geometrically meaningful embeddings learned from synthetic and real-world datasets.
A new conformal prediction framework for graph-valued outputs using Z-Gromov-Wasserstein distances.
problem Lack of principled uncertainty quantification for graph-valued supervised prediction.
method Proposes a conformal prediction framework using Z-Gromov-Wasserstein distances for graph-valued outputs.
result Provides distribution-free coverage guarantees for graph-valued outputs.
Paper introduces new Gromov-type distances for comparing Gaussian mixture models.
problem Comparing distributions across different metric spaces using Gromov-Wasserstein distances.
method Incorporates invariance properties into MW2, introducing MGW2 and EW2.
result MGW2 and EW2 are efficient for estimating distances between GMMs in practical applications.
New DR method uses Gromov-Wasserstein distance for high-dimensional data.
problem Analyzing relationships between high-dimensional objects.
method Optimal transportation theory and Gromov-Wasserstein distance.
result Robust and efficient solution for complex high-dimensional datasets.
A new sliced IGW distance for Gromov-Wasserstein alignment.
problem Scalability issues in Gromov-Wasserstein alignment for high-dimensional problems.
method Proposed a sliced IGW distance with rotational invariance.
result Natural rotational invariance of the sliced IGW distance.
Proposes an efficient lower bound for Gromov-Wasserstein discrepancy.
problem Comparing structured data from different metric-measure spaces.
method Orthogonal Gromov-Wasserstein (OGW) discrepancy with efficient closed-form lower bound.
result Efficient and tight lower bounds for Gromov-Wasserstein discrepancy.
New autoencoder improves latent space learning by optimizing sliced Gromov-Wasserstein discrepancies.
problem Improving inner discrepancy between prior and posterior distributions in autoencoders.
method Proposed spherical sliced fused Gromov Wasserstein (SSFG) and variants (MSSFG, PSSFG) to find important directions.
result New autoencoders achieve favorable performance in latent manifold learning, image generation, and reconstruction.
We propose a scalable Gromov-Wasserstein learning (S-GWL) method and establish a novel and theoretically-supported paradigm for large-scale graph analysis. The proposed method is based on the fact that Gromov-Wasserstein discrepancy is a pseudometric on graphs. Given two graphs, the optimal transport associated with th…
Enhances graph comparison by incorporating edge features using Fused Gromov-Wasserstein distance.
problem Graph distances overlook edge attributes, limiting their effectiveness.
method Introduced Fused Gromov-Wasserstein distance for graph comparison with edge features. Proposed algorithms for distance and barycenter computation.
result Empirically validated the effectiveness of the novel distance in graph learning tasks.
Unified framework for DR and clustering using Gromov-Wasserstein.
problem Capturing structure in high-dimensional datasets.
method Distributional reduction framework using Gromov-Wasserstein.
result Unified approach recovers DR and clustering as special cases.
Develops a private synthetic graph generator using Gromov-Wasserstein distance.
problem Creating private synthetic networks for complex data.
method Random connection model, fused Gromov-Wasserstein distance, differential privacy.
result Effective algorithm for generating private synthetic graphs with theoretical guarantees.
Extends subspace detour method to Gromov-Wasserstein problem.
problem Matching shapes using Gromov-Wasserstein distance.
method Project measures onto a subspace, then compute optimal transport plan.
result Connections with Knothe-Rosenblatt rearrangement.
A novel Gromov-Wasserstein learning framework is proposed to jointly match (align) graphs and learn embedding vectors for the associated graph nodes. Using Gromov-Wasserstein discrepancy, we measure the dissimilarity between two graphs and find their correspondence, according to the learned optimal transport. The node …
The paper examines properties of GW optimal transport plans, showing they can be sparse and permutation-supported.
problem Properties of Gromov-Wasserstein optimal transport plans.
method Exploration of sparsity, permutation support, and cyclical monotonicity properties.
result GW optimal plans can be sparse and permutation-supported under certain conditions.
GWIL uses Gromov-Wasserstein distance to align expert and imitation agent states.
problem Cross-domain imitation learning challenges due to different system dimensions and stationary distributions.
method Gromov-Wasserstein Imitation Learning (GWIL) using Gromov-Wasserstein distance.
result GWIL effectively aligns expert and imitation agent states in various continuous control domains.
Paper solves Gromov-Wasserstein for point clouds efficiently.
problem Quantifying similarity between two formations or shapes.
method Reformulates QAP as low-rank concave quadratic optimization problem.
result Global solution for large-scale problems with thousands of points.
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 in…
Proposes Gromov-Wasserstein methods for multi-view embedding.
problem Integrating multiple representations of the same samples in heterogeneous geometries.
method Gromov-Wasserstein optimal transport for multi-view embedding.
result Preserves intrinsic relational structure across views effectively.
GWIB improves counterfactual regression by balancing latent distributions and reducing selection bias.
problem Selection bias between control and treatment groups negatively impacts counterfactual regression performance.
method GWIB uses Gromov-Wasserstein information bottleneck to maximize mutual information between covariates and outcomes while penalizing kernelized mutual information between latent representations and covariates.
result GWIB consistently outperforms state-of-the-art CFR methods in ITE estimation tasks.
This work explores gradient flows and Riemannian structure in Gromov-Wasserstein geometry for data with global structure.
problem Suitable geometry for tasks requiring preservation of global data structure.
method Study of gradient flows and Riemannian structure in Gromov-Wasserstein geometry for distributions on \(\mathbb{R}^d\).
result Established a Benamou-Brenier-like formula for IGW and derived the IGW gradient.
New model optimizes feature alignment, improving statistical and computational efficiency.
problem Statistical and computational challenges in feature alignment.
method Covariance alignment model, Gromov-Wasserstein algorithm.
result Gromov-Wasserstein algorithm is minimax optimal and practical for covariance alignment.
Implementing k-NN classification using Gromov--Wasserstein distances
problem Comparing metric measure spaces
method Gromov--Wasserstein and fused Gromov--Wasserstein distances
result Universal consistency of k-NN classifiers Adapts DR objectives for both sample and feature size reduction.
problem Simultaneously reduce sample and feature sizes.
method Semi-relaxed Gromov-Wasserstein optimal transport.
result OT plan delivers competitive hard clustering.
We propose an SDP relaxation for the Gromov-Wasserstein distance, providing globally optimal solutions.
problem Matching objects between incomparable spaces using the Gromov-Wasserstein distance.
method Semi-definite programming (SDP) relaxation of the GW distance.
result The SDP relaxation provides globally optimal solutions for the GW distance in some instances.
Improved spectral clustering via Gromov-Wasserstein Learning.
problem Optimizing graph partitioning performance.
method Bridge spectral clustering and GWL, using heat kernel for stable node correspondences.
result Improved graph partitioning results without compromising theoretical guarantees.
New algorithms solve partial optimal transport problems for applications like PU learning.
problem Optimal transport constraints on equal mass distributions limit applicability.
method Developed exact algorithms for partial Wasserstein and Gromov-Wasserstein problems.
result Partial Wasserstein metrics show effectiveness in positive-unlabeled learning.
Recently used in various machine learning contexts, the Gromov-Wasserstein distance (GW) allows for comparing distributions whose supports do not necessarily lie in the same metric space. However, this Optimal Transport (OT) distance requires solving a complex non convex quadratic program which is most of the time very…
A new method efficiently approximates Gromov-Wasserstein distance.
problem High computational complexity of Gromov-Wasserstein distance.
method Importance sparsification method to construct a sparse coupling matrix.
result Efficient approximation of GW distance with reduced complexity.
The paper introduces optimal transport kernels for comparing cell complexes.
problem Lack of machine learning methods for CW complexes.
method Derives explicit expression for Wasserstein distance, extends Fused Gromov-Wasserstein, introduces novel kernels.
result Introduced novel kernels for comparing probability measures on CW complexes.
New algorithm for low-rank optimal transport with improved interpretability and efficiency.
problem Quadratic scaling of optimal transport coupling matrix for massive datasets.
method Factor Relaxation with Latent Coupling (FRLC) algorithm.
result Superior performance on diverse applications including graph clustering and spatial transcriptomics.
We introduce a new framework for comparing parametric network families.
problem Comparing and analyzing data modeled as parameterized families of networks.
method A Gromov-Wasserstein variant of optimal transport for defining distances.
result Established foundational properties and theoretical approximation guarantees for the new distances.
Proposes a new metric for comparing shapes in different spaces.
problem Comparing shapes in different metric spaces with unequal mass.
method Developed a Partial Gromov-Wasserstein (PGW) metric and algorithms to solve it.
result PGW is a well-defined metric between metric measure spaces.
CR-UOT improves matching of heterogeneous single-cell omics profiles.
problem Matching nonnegative finite Radon measures across heterogeneous spaces.
method Cost-regularized unbalanced optimal transport (CR-UOT) framework.
result CR-UOT improves alignment of heterogeneous single-cell omics profiles.
Paper introduces a novel framework for supervised graph prediction using Optimal Transport.
problem Supervised labeled graph prediction.
method Fused Gromov-Wasserstein (FGW) loss and FGW barycenter with neural network weights and learned graphs.
result The method can interpolate in the labeled graph space and achieve good performance on difficult problems.
We propose a new nonlinear factorization model for graphs that are with topological structures, and optionally, node attributes. This model is based on a pseudometric called Gromov-Wasserstein (GW) discrepancy, which compares graphs in a relational way. It estimates observed graphs as GW barycenters constructed by a se…
This paper introduces a new formulation of the Conic Gromov-Wasserstein distance for comparing complex network structures.
problem Comparing measures of unequal mass and complex network structures.
method Novel semi-coupling formulation and extension to hypernetworks.
result Establishes fundamental properties and robustness of CGW metric.
Robust GW distance improves graph data alignment.
problem Outliers in GW distance lead to inaccurate comparisons.
method Optimistically perturbed marginal constraints within a Kullback-Leibler divergence-based ambiguity set.
result RGW reduces inaccuracies in graph data alignment.
Novel methods robustify Gromov-Wasserstein distance for cross-domain alignment.
problem Robustifying Gromov-Wasserstein distance for cross-domain alignment.
method Three novel techniques derived from robust statistics to improve GW and its variants.
result Empirical validation shows superior resilience to contamination.
New method aligns brain surfaces based on functional signatures.
problem Inter-individual variability in neuroimaging data.
method Fused Unbalanced Gromov-Wasserstein (FUGW) based on Optimal Transport.
result FUGW significantly increases between-subject correlation of activity.
This work considers the problem of computing distances between structured objects such as undirected graphs, seen as probability distributions in a specific metric space. We consider a new transportation distance (i.e. that minimizes a total cost of transporting probability masses) that unveils the geometric nature of …
New formulations for comparing metric measure spaces with arbitrary positive measures.
problem Comparing metric measure spaces with arbitrary positive measures.
method Two novel formulations: a divergence and a conic lifting approach.
result Efficiently solvable formulations for comparing metric spaces with arbitrary positive measures.
Robustly aligns datasets with partial GW distance to handle contamination.
problem Aligning contaminated datasets using Gromov-Wasserstein distances.
method Proposes a partial GW distance estimator to minimize distortion from outliers.
result The partial GW distance estimator is minimax optimal and near-optimal in finite samples.