Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem

## Abstract

Abstract Recently, the Gromov-Wasserstein Optimal Transport (GWOT) problem has attracted the special attention of the ML community. In this problem, given two distributions supported on two (possibly different) spaces, one has to find the most isometric map between them. In the discrete variant of GWOT, the task is to learn an assignment between given discrete sets of points. In the more advanced continuous formulation, one aims at recovering a parametric mapping between unknown continuous distributions based on i.i.d. samples derived from them. The clear geometrical intuition behind the GWOT makes it a natural choice for several practical use cases, giving rise to a number of proposed solvers. Some of them claim to solve the continuous version of the problem. At the same time, GWOT is notoriously hard, both theoretically and numerically. Moreover, all existing continuous GWOT solvers still heavily rely on discrete techniques. Natural questions arise: to what extent existing methods unravel GWOT problem, what difficulties they encounter, and under which conditions they are successful. Our benchmark paper is an attempt to answer these questions. We specifically focus on the continuous GWOT as the most interesting and debatable setup. We crash-test existing continuous GWOT approaches on different scenarios, carefully record and analyze the obtained results, and identify issues. Our findings experimentally testify that the scientific community is still missing a reliable continuous GWOT solver, which necessitates further research efforts. As the first step in this direction, we propose a new continuous GWOT method which does not rely on discrete techniques and partially solves some of the problems of the competitors. Our code is available at https://github.com/Ark-130994/GW-Solvers .

## 1 Introduction

Optimal Transport (OT) is a powerful framework that is widely used in machine learning []. A popular application of OT is the domain adaptation of various modalities, including images [, , ], music transcription [], color transfer [], alignment of embedding spaces [, ]. Other applications include generative models [, ], unpaired image-to-image transfer [, ], etc.

Figure: (a) Monge’s OT between distributions $\mathbb{P}$ and $\mathbb{Q}$with inter-domain cost function $c(x,y)$.
Refer to caption: extracted/5672303/images/OT_showcaseV2.png

In the conventional OT problem (Figure 1(a)), one needs to find a map between two data distributions that minimizes a certain “effort” expressed in the form of an *inter-domain* transport cost function. This cost function shows how hard it is to move a point in the source space to a given point in the target space. Thus, in order for the resulting map to possess certain useful properties, one has to incorporate them into the cost function. Unfortunately, this is not always a straightforward task, especially when the data distributions are supported in different spaces.
A popular way to address the above-mentioned issue is to consider the Gromov-Wasserstein (GW) modification [, , ] of the OT problem (Figure 1(b)). Here one assumes that both the source and target spaces are equipped with a structure, e.g., with a metric, and one aims to find a transport map that maximally preserves this structure, i.e., the most isometric map. This clear geometrical intuition behind GW makes it natural in various applications: unsupervised data alignment [, ], single-cell data processing [, , ], 2D and 3D shape analysis [, ], graph data analysis [, , , , ].

Discrete/continuous GW. The GWOT problem is about learning some specific translation that operates with source and target distributions. In practice, these distributions are typically given by empirical datasets. This leads to two possible ways of paving a GWOT map. In the discrete scenario, the learned translation is just a point(s)-to-point(s) assignment (transport matrix). In turn, the continuous GW is about learning a parametric mapping between the underlining (continuous) distributions. In this case, the datasets are treated as i.i.d. samples derived from them.
While existing computational approaches for the GW problem show considerable empirical success, the problem itself is highly non-trivial from different perspectives.

- •
Theory. Finding the most isometric map between probability spaces based just on the inner properties of these spaces may be poorly defined, e.g., the desired transform may be non-unique. This happens where the source (target) space permits some non-trivial isometries that preserve the corresponding source (target) distribution. A simple yet expressive example is the Gaussian case []. Intuitively, non-uniqueness may affect the stability of a GWOT solver.
- •
Computations/algorithms. It is known that the discrete GW yields a non-convex quadratic optimization problem [], which is computationally challenging. To partially alleviate the difficulty, one typical approach is to consider entropic regularization [, , ]. Fortunately, the regularized problem resorts to a sequence of tractable Sinkhorn OT assignments. However, the convergence of the procedure may not hold, see [, Remark 3]. In addition, discrete GWOT scales poorly with the number of input (source or target) samples, which makes some problem setups unmanageable by such kind of solvers. While there are some techniques to reduce the computational burden w.r.t input data size [], they come at the cost of additional restrictions and assumptions.
- •
Methodology. All existing continuous GW methods are based on discrete GW techniques. In particular, they inherit all the computational challenges of the latter. Furthermore, the transition from the discrete to the continuous setup may be questionable from a statistical point of view.

Having said that, one naturally wonders: how do the current continuous GWOT methods manage to overcome these problems and show good practical results? What are the “bad cases” under which the aforementioned difficulties become critical and the solvers struggle? How to fight with these “bad cases”? In our paper, we shed light on these GWOT methods’ ambiguities, specifically focusing on the continuous setup. Our contributions are as follows:

- •
We conduct a deep analysis of existing papers and reveal that one important characteristic that may greatly affect practical performance is the considered data setup. In fact, the majority of works primarily consider datasets with some specific correlations between source and target samples. Formally speaking, such setups disobey the standard i.i.d. assumption on the data and may lead to spoiled conclusions on the solvers’ capabilities.
- •
By following the findings from the previous point, we evaluate the performance of existing continuous GWOT solvers in more statistically fair and practically realistic uncorrelated data setups. Our simple yet expressive experiments witness that (un)correlatedness indeed highly influences the quality of the learned GWOT maps. Changing the data setup may greatly deteriorate the performance of the solvers.
- •
To alleviate the dependence on the mutual statistical characteristics of the source and target training data, we propose a novel continuous neural GW solver. On the one hand, our method is not based on discrete GW. It may be learned on arbitrarily large datasets and shows reasonably good results even on the fair uncorrelated data setup. On the other hand, the method is $\min$-$\max$-$\min$ adversarial, which negatively impacts stability and requires plenty of data for training.

Overall, our findings reveal that the empirical success of the existing GWOT solvers seems to be a bit over-estimated and requires to be treated more critically. Constructing a reliable continuous GWOT method is a not-yet-solved challenge. We encourage the researchers to further work out on this quite interesting direction. We hope, that our work is a good amigo in this thorny path.

Notations.
Throughout the paper, $\mathbb{R}^{d_{x}}$ and $\mathbb{R}^{d_{y}}$ are the source and target data spaces, respectively. The set of Borel probability distributions on $\mathbb{R}^{d_{x}}$ is $\mathcal{P}(\mathbb{R}^{d_{x}})$. The dot product of vectors $\textbf{x},\textbf{x}^{\prime}\in\mathbb{R}^{d_{x}}$ is $\langle\textbf{x},\textbf{x}^{\prime}\rangle_{d_{x}}$. For a measurable map $T\colon\mathbb{R}^{d_{x}}\to\mathbb{R}^{d_{y}}$, we denote the corresponding *push-forward* operator by $T_{\sharp}$.
For $\mathbb{P}\in\mathcal{P}(\mathbb{R}^{d_{x}})$ and $\mathbb{Q}\in\mathcal{P}(\mathbb{R}^{d_{y}})$, we denote the set of all couplings between them by $\Pi(\mathbb{P},\mathbb{Q})$, i.e., distributions $\pi$ on $\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}$ with the corresponding marginals equal to $\mathbb{P}$ and $\mathbb{Q}$.

## 2 Background

In this section, we first explain the conventional OT setup [, , , ] and then introduce the Gromov-Wasserstein OT formulation [, ]. Finally, we clarify our considered practical learning setup under which these problems are considered.

### 2.1 Optimal Transport (OT) problem

Given two probability distributions $\mathbb{P}\in\mathcal{P}(\mathbb{R}^{d_{x}})$, $\mathbb{Q}\in\mathcal{P}(\mathbb{R}^{d_{y}})$ and a cost function $c\colon\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\rightarrow\mathbb{R}$, the OT problem is defined as follows:

$$ $\text{OT}_{c}(\mathbb{P},\mathbb{Q})\stackrel{{\scriptstyle\text{def}}}{{=}} \inf_{T_{\sharp}\mathbb{P}=\mathbb{Q}}\int_{\mathbb{R}^{d_{x}}}c(\textbf{x},T( \textbf{x}))d\mathbb{P}(\textbf{x}).$ (1) $$

This is known as Monge’s formulation of the OT problem. Intuitively, it can be understood as finding an optimal transport map $T^{*}:\mathbb{R}^{d_{x}}\rightarrow\mathbb{R}^{d_{y}}$ that transforms $\mathbb{P}$ to $\mathbb{Q}$ and minimizes the total transportation expenses w.r.t. cost $c$, see Figure 1(a). There have been developed a lot of methods for solving OT (1) in its discrete [, , ] and continuous [, , , , , , , , ] variants.

The cost function $c$ in (1) is commonly the Euclidean distance. In this case, problem (1) is exclusively defined for spaces of the same dimensions. Dealing with two incomparable spaces ($d_{x}\neq d_{y}$) may require manually defining some more complex inter-domain cost function $c$. It is not a trivial task.

### 2.2 Gromov-Wasserstein OT (GWOT) problem

The GWOT problem is an extension of the optimal transport problem that aims to compare and transport probability distributions supported on different spaces. This problem is particularly useful when the underlying spaces do not align directly, but we still want to measure and align their intrinsic geometric structures. In what follows, we introduce the discrete and continuous variants of GWOT.

Discrete Gromov-Wasserstein formulation.
Let $N_{x}$ and $N_{y}$ be the number of training samples in the source and target domains, respectively. Let $\textbf{C}^{x}\in\mathbb{R}^{N_{x}\times N_{x}}$ and $\textbf{C}^{y}\in\mathbb{R}^{N_{y}\times N_{y}}$ be the corresponding source and target intra-domain cost matrices. These matrices measure the pairwise distance or similarity between the samples for a given function, i.e., cosine similarity, Euclidean distance, inner product, etc. The discrete GWOT problem is defined as:

$$ $\textbf{T}^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\operatornamewithlimits{ argmin}_{\textbf{T}\in\mathcal{C}_{N_{x},N_{y}}}\,\sum_{i,j,k,l}|\textbf{C}^{x }_{i,k}-\textbf{C}^{y}_{j,l}|^{p}\textbf{T}_{i,j}\textbf{T}_{k,l},$ (2) $$

where $\mathcal{C}_{N_{x},N_{y}}\stackrel{{\scriptstyle\text{def}}}{{=}}\{\textbf{T}
\in\mathbb{R}^{N_{x}\times N_{y}}_{+}\,\big{|}\,\textbf{T}^{T}\mathds{1}_{N_{x
}}=\frac{1}{N_{y}}\mathds{1}_{N_{y}};\textbf{T}\mathds{1}_{N_{y}}=\frac{1}{N_{
x}}\mathds{1}_{N_{x}}\}$ is the set of coupling matrices between source and target spaces; $\mathds{1}_{N}=[1,\dots,1]^{T}\in\mathbb{R}^{N}$.
The loss function $|\cdot-\cdot|^{p}$ in (2) is used to account for the misfit between the similarity matrices, a typical choice for the degree factor is $p=2$ (quadratic loss). Further details can be found in [, , ].

Continuous Gromov-Wasserstein formulation. Let $\mathbb{P}\in\mathcal{P}(\mathbb{R}^{d_{x}})$, $\mathbb{Q}\in\mathcal{P}(\mathbb{R}^{d_{y}})$ be two distributions. Let $c_{\mathcal{X}}:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{x}}\rightarrow\mathbb{R}$ and $c_{\mathcal{Y}}:\mathbb{R}^{d_{y}}\times\mathbb{R}^{d_{y}}\rightarrow\mathbb{R}$ be two intra-domain cost functions for the source ($\mathbb{R}^{d_{x}}$) and target ($\mathbb{R}^{d_{y}}$) domains, respectively. The Monge’s GWOT problem is defined as:

$$ $\text{GWOT}^{p}_{p}(\mathbb{P},\mathbb{Q})\stackrel{{\scriptstyle\text{def}}}{ {=}}\inf_{T_{\sharp}\mathbb{P}=\mathbb{Q}}\int_{\mathbb{R}^{d_{x}}}\int_{ \mathbb{R}^{d_{x}}}\left|c_{\mathcal{X}}(\textbf{x},\textbf{x}^{\prime})-c_{ \mathcal{Y}}(T(\textbf{x}),T(\textbf{x}^{\prime}))\right|^{p}d\mathbb{P}( \textbf{x})d\mathbb{P}(\textbf{x}^{\prime}).$ (3) $$

An intuitive illustration of problem (3) can be found in Figure 1(b). In this continuous setup, the objective is to find an optimal transport map $T^{*}:\mathbb{R}^{d_{x}}\rightarrow\mathbb{R}^{d_{y}}$ that allows to transform (align) the source distribution to the target distribution. While in (1) we search for a map that sends $\mathbb{P}$ to $\mathbb{Q}$ minimizing the total transport cost, (3) aims to find the most isometric map w.r.t. the costs $c_{\mathcal{X}}$ and $c_{\mathcal{Y}}$, i.e., the map that maximally preserves the pairwise intra-domain costs. The commonly studied case [, ] is $p=2$ with the Euclidean distance $c(\cdot,\cdot)=\|\cdot-\cdot\|^{2}$ or inner product $c(\cdot,\cdot)=\langle\cdot,\cdot\rangle$ as intra-domain cost functions. In what follows, we will use innerGW to denote the latter case.

### 2.3 Practical Learning Setup

In practical scenarios, the source and target distributions $\mathbb{P}$ and $\mathbb{Q}$ are typically accessible by empirical samples (datasets) $X=\{\textbf{x}_{i}\}_{i=1}^{N_{x}}\sim\mathbb{P}$ and $Y=\{\textbf{y}_{i}\}_{i=1}^{N_{y}}\sim\mathbb{Q}$. Under the discrete GWOT formulation, these samples are directly used to compute intra-domain cost matrices $\textbf{C}^{x}$, $\textbf{C}^{y}$. These matrices are then fed to optimization problem (2). Having been solved, problem (2) yields a coupling matrix $\textbf{T}^{*}$ which defines the GWOT correspondence between $X$ and $Y$. Importantly, discrete GWOT operates with discrete empirical measures $\hat{\mathbb{P}}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{i=1}^{N_{x}}
\frac{1}{N_{x}}\delta(\textbf{x}-\textbf{x}_{i})$, $\hat{\mathbb{Q}}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{i=1}^{N_{y}}
\frac{1}{N_{y}}\delta(\textbf{y}-\textbf{y}_{i})$ rather than original ones.
In turn, under the continuous formulation, the aim is to recover some parametric map $T^{*}:\mathbb{R}^{d_{x}}\rightarrow\mathbb{R}^{d_{y}}$ between the original source and target distributions $\mathbb{P}$ and $\mathbb{Q}$.
In most practical scenarios, the latter is preferable, as it naturally allows out-of-sample estimation, i.e., provides GWOT mapping for new (unseen) samples $\textbf{x}\sim\mathbb{P}$. In our paper, we deal with continuous setup.

## 3 Existing continuous Gromov-Wasserstein solvers

In this section, we outline the current progress in solving GWOT problem specifically focusing on the continuous formulation. Most of the GWOT solvers are only discrete or adapted to emulate a continuous behaviour by implementing some specific out-of-sample estimation method on top of the results of some discrete solver. The initial approach to solve the GWOT problem in discrete case (\wasyparagraph2.2) was introduced in [, ]. Below we only detail the methods which specifically aim to solve the continuous formulation and somehow provide the out-of-sample estimation.

StructuredGW []. In this paper, the authors focus on providing an iterative algorithm to solve a discrete entropy-regularized version of the inner product case of (3) for $p=2$ using the equivalent reformulation by [, maxOT]. Every iteration, the coupling matrix T is updated using Sinkhorn iterations and an auxiliary rotation matrix updates using different possible methods. The authors propose different regularization alternatives for the problem, this directly impacts the way the auxiliary matrix is updated. To perform the out-of-sample estimation, the authors extend their method by drawing inspiration from entropic maps in [, ]. Their developed StructuredGW method uses one of the dual potentials learned during the updates of T to perform this entropic mapping.

FlowGW []. The framework proposed in this work consists in fitting a discrete GW solver inspired by [] to obtain a coupling matrix T. This coupling matrix helps to figure out the best way to match available samples from source to target domains. Weighted pairs of source and target samples are constructed using the distribution described by the coupling matrix. Then these samples are used to train a Conditional Flow Matching (CFM) model [] with the noise outsourcing technique from []. The inference process is done by solving the ODE given by the CFM model.

AlignGW []. This work proposes a discrete solver for the alignment of word embeddings. The authors use Sinkhorn iterations to compute the updates on the coupling matrix instead of a linear search implemented in the Python Optimal Transport library [] that is inspired by [, ]. This change significantly improves the stability of the solver. In spite of being a totally discrete method, we consider it due to its performance in challenging tasks. In order to allow out-of-sample estimations, we train a Multi-Layer Perceptron (MLP) model on the barycentric projections derived from the learned coupling matrix T.

### 3.1 Toy 3D → → \rightarrow → 2D experiment

To illustrate the capabilities of the solvers and as a necessary sanity check for the implementations, we propose a toy experiment. In this setup, the source distribution is a mixture of Gaussians in $\mathbb{R}^{3}$ and the target is also a mixture of Gaussians but in $\mathbb{R}^{2}$, see Figure 2(a). By choosing this experiment on incomparable spaces, we ensure the solvers are actually capable of dealing with a real Gromov-Wasserstein problem. The obtained results for the baselines could be found in Figure 2(c). As we can see, for all methods a component of the source distribution is mostly mapped to a component/neighbouring components of the target distribution, indicating the correct GW alignment.

Figure: (a) Source and target distributions.
Refer to caption: extracted/5672303/images/source_target.png

## 4 Limitations of existing methods

As it was mentioned before, all existing Gromov-Wasserstein approaches explicitly or implicitly resort to discrete GWOT formulation, see \wasyparagraph2.2. Naturally, the computations required to solve (2) increase significantly as the numbers of training samples $N_{x}$ and $N_{y}$ grow. This dependency renders some datasets to hardly be manageable by discrete solvers. However, in our paper, we specifically focus on the other source of potential failures for GWOT. It stems from the practical data setups under which the methods actually work. Below, we give a detailed description of this problem.

### 4.1 Pitfalls of practical data setup

To begin with, we introduce the notion of (un)correlatedness of data which undergoes Gromov-Wasserstein alignment.
To fit a GWOT solver, a practitioner typically has two training datasets, $X=\{\textbf{x}_{i}\}_{i=1}^{N_{x}}$ and $Y=\{\textbf{y}_{i}\}_{i=1}^{N_{y}}$. They are sampled from the reference source ($\mathbb{P}$) and target ($\mathbb{Q}$) distributions, see our training setup, \wasyparagraph2.3. In what follows, without loss of generality, we will assume $N_{x}=N_{y}\stackrel{{\scriptstyle\text{def}}}{{=}}N$. The natural statistical assumption on samples $X$ and $Y$ is that they are mutually independent.
We define this data setup as uncorrelated. Simultaneously, we introduce an alternative setup under which the source and target datasets $X$ and $Y$ turn out to be connected by some specific statistical relationships. Let us assume that there is a coupling $\pi\in\Pi(\mathbb{P},\mathbb{Q})$, $\pi\neq\mathbb{P}\otimes\mathbb{Q}$. Practically, we expect that samples from the coupling are meaningfully dependent, i.e., $\pi$ is “significantly” different from the independent coupling $\mathbb{P}\otimes\mathbb{Q}$. In particular, coupling $\pi$ may even set a one-to-one correspondence between the domains. Then, we call the training samples $X$ and $Y$ to be correlated if they are obtained with the following procedure:

- 1.
First, we jointly sample $X$ and $\widetilde{Y}=\{\widetilde{\textbf{y}}_{i}\}_{i=1}^{N}\subset\mathbb{R}^{d_{y}}$ from coupling $\pi$, i.e.: $X\times\widetilde{Y}\sim\pi$.
- 2.
Secondly, we apply an unknown permutation $\sigma$ of indices to $\widetilde{Y}$ yielding $Y$, i.e.: $Y=\sigma\circ\widetilde{Y}$.

We found that the majority of the experimental test cases, on which the existing GWOT solvers are validated, frequently follow exactly the correlated data setup. For instance, in the problem of learning cross-lingual word embedding correspondence [, ], the underlining coupling $\pi$ could be understood as the distribution of dictionary pairs. The other example is the bone marrow dataset [, ]. In this case, the source and target samples are generated using two different methods to profile gene expressions on the same donors.
Interestingly, the correlated data setup suits well the discrete GWOT formulation, because the optimization problem in this case boils down to the search for the permutation $\sigma$ that spawned the target dataset $Y$. This leads to the natural hypothesis that for uncorrelated training datasets $X$ and $Y$ the performance of existing GWOT solvers may be poor. To test this hypothesis, we propose the experimental framework described in the next paragraphs.

Modeling (un)correlatedness in practice.
Let $X=\{\textbf{x}_{1},\dots,\textbf{x}_{N}\}\sim\mathbb{P}$ and $Y=\{\textbf{y}_{1},\dots,\textbf{y}_{N}\}\sim\mathbb{Q}$ be the source and target datasets. We assume that $X$ and $Y$ are totally paired, i.e., every $i$-th vector in the source set $X$ is the pair of the $i$-th vector in the target set, $Y$. Also, we suppose that the pairing is reasonable, i.e., dictated by the nature of the data on hand. For example, if $X$ and $Y$ are word embeddings, then $\textbf{x}_{i}$ and $\textbf{y}_{i}$ correspond to the same word. We propose a way how to create training data with different levels of correlatedness. Initially, batches of $N$ paired (source and target) samples are randomly selected from the datasets, then split into train and test sets, $N=N_{train}+N_{test}$. The train samples are then divided into two halves and a value $\alpha$, $0\leq\alpha\leq 1$ is set, this value represents the fraction of $N_{train}/2$ samples that will be paired.

Figure: (a) Totally correlated setup.
Refer to caption: extracted/5672303/images/totally.png

The resulting training datasets (both source and target) will totally contain $N_{train}/2$ samples. They are formed by selecting specific indices from the original train sets. Indices from 0 0 to $N_{train}/2$ are taken from the source while indices from target are shifted, we take the $\lceil(1-\alpha)(N_{train}/2)\rceil$ to $\lceil(1-\alpha)N_{train}\rceil$ indices. As a result, setting a value of $\alpha=1$ will represent a totally correlated setup (Figure 3(a)), $0<\alpha<1$ is partially correlated (Figure 3(b)) and $\alpha=0$ is uncorrelated (Figure 3(c)).

To conclude the subsection, we want to emphasize that both correlated and uncorrelated setups are practically important. Some real-world use cases of the former include word embedding assignment and gene expression profiles matching problems, see the details in the text above. In turn, the uncorrelated setup naturally appears when aligning single-cell multi-omics data []. In this problem, one aims at matching different single-cell assays, which are uncorrelated, because applying multiple assays on the same single-cell is typically impossible.

### 4.2 Benchmarking GWOT solvers on (un)correlated data: GloVe experiment

In order to check how existing continuous GW solvers perform under uncorrelated, partially and totally correlated setups, we utilize the GloVe (Global Vectors for Word Representation) dataset(^1^11https://radimrehurek.com/gensim/downloader.html). This dataset is a collection of pre-trained word vectors obtained from large text corpora such as Wikipedia, Gigaword, Common Crawl or Twitter. The vector embeddings of words are generated using the GloVe algorithm []. Its main advantage is that the embedded vectors capture semantic relationships and exhibit linear substructures in the vector space. This allows meaningful computation of distances and alignments, which is central to the GWOT framework.

The paired samples out of GloVe are constructed by picking embeddings of different dimensions from the Wikipedia-Gigaword corpora.
The following blends of dimensionalities are considered: 100$\rightarrow$50, 50$\rightarrow$100, 50$\rightarrow$25 and 25$\rightarrow$50.
We test three baseline solvers introduced in \wasyparagraph3: StructuredGW, AlignGW and FlowGW. We fit every solver for different values of $\alpha$ (different levels of correlatedness). The values of $\alpha$ range from 0.0 to 1.0 in increments of 0.1. For each value of $\alpha$, we perform five fitting repetitions with different random seeds following the process described in \wasyparagraph4.1. We use $N_{train}=6K$, i.e., every experiment run exploits source and target datasets containing $N_{train}/2=3K$ training samples. Note that the only reason why we choose such a relatively small size for the training datasets is computational complexity. The discrete optimization procedures runned at the backend of baseline solvers hardly could be adopted to reasonably larger values of $N_{train}$.

For evaluation, we use the following test metrics: Top $k$-accuracy $\uparrow$, cosine similarities $\uparrow$ and FOSCTTM $\downarrow$, the details are given in Appendix B.1. The metrics are computed on (unseen) test data.
The results of the experiments for the combinations 100$\rightarrow$50 and 50$\rightarrow$25 are shown in the plots below, Figure 4. For additional experimental results on other dimension pairs, see Appendix B.

Figure: (a) Source: 100 $\rightarrow$ Target:50
Refer to caption: extracted/5672303/images/100_50_discrete_star.png

Conclusions. The results indicate that all the baseline solvers perform very well in totally correlated scenarios, even when evaluated on unseen data. This demonstrates their ability to learn and capture the inner structures when the data is highly correlated. However, their performance drops significantly as the value of $\alpha$ decreases. We conjecture that the observed behaviour is mainly due to the small sizes of training sets dictated by the discrete nature of the solvers. Indeed, relatively small samples hardly could express the intrinsic geometry of the data, which complicates the faithful GW alignment of the domains. To address the problem, we propose a new continuous solver which does not rely on discrete techniques. Therefore, it can better capture the inner geometry and structure of the data without the strict need of training on correlated data.

## 5 Towards solving issues of current GWOT approaches: NeuralGW solver

In this section, we propose NeuralGW, a novel scalable method to solve the continuous GWOT problem. The theoretical derivations and practical optimization schemes are given in \wasyparagraph5.1. The performance on toy 3D$\rightarrow$ 2D experiment and GloVe benchmark is in \wasyparagraph5.2.

### 5.1 Proposed Neural Gromov-Wasserstein Solver

In this subsection, we conduct the theoretical and algorithmic derivation of our proposed approach. Our method is developed for innerGW, i.e., problem (3) with $c_{\mathcal{X}}=\langle\cdot,\cdot\rangle_{d_{x}}$, $c_{\mathcal{Y}}=\langle\cdot,\cdot\rangle_{d_{y}}$ and $p=2$:

$$ $\operatorname{innerGW}^{2}_{2}(\mathbb{P},\mathbb{Q})\stackrel{{\scriptstyle \text{def}}}{{=}}\min_{T_{\sharp}\mathbb{P}=\mathbb{Q}}\int_{\mathbb{R}^{d_{x} }}\int_{\mathbb{R}^{d_{x}}}\Big{|}\langle\textbf{x},\textbf{x}^{\prime}\rangle _{d_{x}}-\langle T(\textbf{x}),T(\textbf{x}^{\prime})\rangle_{d_{y}}\Big{|}^{2 }d\mathbb{P}(\textbf{x})d\mathbb{P}(\textbf{x}^{\prime}).$ (4) $$

We base our method on the theoretical insights about GW from []. According to [, Theorem 4.2.1], when $\int\|\textbf{x}\|_{2}^{4}d\mathbb{P}(\textbf{x})<+\infty$, $\int\|\textbf{y}\|_{2}^{4}d\mathbb{Q}(\textbf{y})<+\infty$, the problem (4) is equivalent to

$$ $\operatorname{innerGW}^{2}_{2}(\mathbb{P},\mathbb{Q})=\operatorname{Const}( \mathbb{P},\mathbb{Q})-\max_{\pi\in\Pi(\mathbb{P},\mathbb{Q})}\max_{P\in F_{d_ {x},d_{y}}}\int\langle\textbf{P}\textbf{x},\textbf{y}\rangle_{d_{y}}d\pi( \textbf{x},\textbf{y}),$ (5) $$

where $F_{d_{x},d_{y}}\!\!\stackrel{{\scriptstyle\text{def}}}{{=}}\!\{\textbf{P}\in
\mathbb{R}^{d_{x}\times d_{y}}\>|\>\|\textbf{P}\|_{\mathcal{F}}\!=\!\min(\sqrt
{d_{x}},\sqrt{d_{y}})\}$ are the matrices of fixed Frobenius norm.

Our following lemma reformulates the innerGW problem as a minimax optimization problem. This reformulation is inspired by well-celebrated dual OT solvers such as [, , ].

###### Lemma 5.1 (InnerGW as a minimax optimization)

It holds that (5) is equivalent to

$$ $\operatorname{innerGW}_{2}^{2}(\mathbb{P},\mathbb{Q})=\operatorname{Const}{( \mathbb{P},\mathbb{Q})}+\min_{P\in F_{d_{x},d_{y}}}\,\max_{f:\mathbb{R}^{d_{y} }\rightarrow\mathbb{R}}\,\,\min_{T\!\colon\!\mathbb{R}^{d_{x}}\to\mathbb{R}^{d _{y}}}\mathcal{L}(\textbf{P},f,T),$ (6) $$

where

$$ $\mathcal{L}(\textbf{P},f,T)=\int_{\mathbb{R}^{d_{y}}}f(\textbf{y})d\mathbb{Q}( \textbf{y})-\int_{\mathbb{R}^{d_{x}}}\left[\langle\textbf{P}\textbf{x},T( \textbf{x})\rangle_{d_{y}}+f(T(\textbf{x}))\right]d\mathbb{P}(\textbf{x}).$ $$

The following theorem provides a theoretical foundation that validates the minimax optimization framework for solving the GW problem. It shows that under certain conditions, the solution $T^{*}$ of the minimax problem (4) brings an optimal GW mapping.

###### Theorem 5.2 (Optimal maps solve the minimax problem)

Assume that there exists at least one GW map $T^{*}$. For any matrix $\textbf{P}^{*}$ and any potential $f^{*}$ that solve (6), i.e.,

$$ $\textbf{P}^{*}\in\operatornamewithlimits{argmin}\limits_{P\in F_{d_{x},d_{y}}} \max\limits_{f}\min\limits_{T\colon\mathbb{R}^{d_{x}}\to\mathbb{R}^{d_{y}}} \mathcal{L}(P,f,T)\hskip 14.22636pt\text{and}\hskip 14.22636ptf^{*}\in \operatornamewithlimits{argmax}\limits_{f}\min\limits_{T\colon\mathbb{R}^{d_{x }}\to\mathbb{R}^{d_{y}}}\mathcal{L}(\textbf{P}^{*},f,T),$ $$

and for any GW map $T^{*}$, we have:

$$ $T^{*}\in\operatornamewithlimits{argmin}_{T\colon\mathbb{R}^{d_{x}}\to\mathbb{R }^{d_{y}}}\mathcal{L}(\textbf{P}^{*},f^{*},T).$ (7) $$

To optimize 6 we follow the best practices from the field of continuous OT [, , , , , , ] and simply parameterize $f$ and $T$ with neural networks. In turn, P is a learnable matrix of fixed Frobenius norm. We use the alternating stochastic gradient ascent/descent/ascent method to train their parameters. The learning algorithm is detailed in the Appendix C. We call the method NeuralGW. Note that in comparison to other continuous GWOT approaches, our method does not rely on discrete OT in any form. In particular, the training process assumes access to just random samples from $\mathbb{P},\mathbb{Q}$; it does not use/need any pairing between them.

###### Lemma 5.1 (InnerGW as a minimax optimization)

###### Theorem 5.2 (Optimal maps solve the minimax problem)

### 5.2 Practical performance of NeuralGW

To begin with, we show how our NeuralGW performs in toy setup from \wasyparagraph3.1, see Figure 2(b).

Next, in the GloVe case, we consider the same data preparation process as in \wasyparagraph4.2. The only difference is that for our NeuralGW we take $N_{train}=400K$ samples instead of the 6K used for the baseline solvers. Therefore, each repetition consists in training the models with the same data ($200K$ samples) but using different initialization parameters for the neural networks. Results for NeuralGW and the other baselines (in grey) can be found in Figure 5. While the comparison of the methods trained on $3K$ samples (baselines) and $200K$ samples (our approach) might seem a bit unfair, we stress that the sizes of datasets are selected based on the computational capabilities of the solvers. NeuralGW is the only method which may deal with large datasets, because it is based on conventional stochastic learning with batches.
For the sake of completeness, we provide the GloVe experimental performance for our method trained on $3K$ in Appendix B.1. The results are bad, which is expected because NeuralGW is based on complex adversarial procedure while the dataset is small.

Figure: (a) Source: 100 $\rightarrow$ Target:50
Refer to caption: extracted/5672303/images/100_50_NGW_star.png

Conclusions. Our proposed method (NeuralGW) is the first known solver for the GWOT problem that does not rely on discrete approximations and hence can handle realistic setups with uncorrelated data. Specifically, we attract the readers’ attention to metrics’ values at $\alpha=0$ which are highlighted with the star $\star$ symbol. In all the cases, our method outscores competitors by a large barrier. Our NeuralGW supports gradient ascent-descent batch training on large datasets. This capability enables the solver to learn intricate substructures even when trained on uncorrelated data. The initial results for our method suggest the potential to develop a general GWOT solver that is independent of data correlation, a significant advantage given that real-world datasets often lack such correlation.

Despite achieving the best performance on uncorrelated data, the results are inconsistent with respect to the initialization parameters, as evidenced by a high standard deviation among repetitions. This inconsistency may be due to the minimax nature of the optimization problem. Additionally, adversarial methods like our NeuralGW are known to require large amounts of data for training, which can lead to issues when working with small datasets. We explore more general problems for baseline and NeuralGW solvers in Appendix B.

## 6 Discussions

The general scope of our paper is conducting in-depth analyses of machine learning challenges that yield important new insight. In particular, we analyze the sphere of Gromov-Wasserstein Optimal Transport solvers, identify the problems and propose some solutions.

General conclusions. Our work clearly shows that while existing Gromov-Wasserstein Optimal Transport methods exhibit considerable success when solving downstream task, their performance may severely depend on the intrinsic properties of the training data. We partially address the issue by introducing our novel NeuralGW method. However, it has its own disadvantages. Thereby, our work witnesses that GWOT challenge in Machine Learning still awaits its hero who will manage to propose a reliable general-purpose method tackling the problem.

## Appendix A Proofs of theorems and lemmas.

Proof of Lemma 5.1. First, we recall the dual formulation of (1):

$$ $\text{OT}(\mathbb{P},\mathbb{Q})\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{ f}\left[\min_{T}\int\big{(}c(\textbf{x},T(\textbf{x}))-f(T(\textbf{x}))\big{)} d\mathbb{P}(\textbf{x})+\int f(\textbf{y})d\mathbb{Q}(\textbf{y})\right],$ (8) $$

respectively. These expressions are taken from []. Our proof starts with (5). For each P, we rewrite the inner optimization over P using (8) for the cost $c(\textbf{x},\textbf{y})=-\langle\textbf{P}\textbf{x},\textbf{y}\rangle$:

$$ $\displaystyle\operatorname{Const}{(\mathbb{P},\mathbb{Q})}-\text{innerGW}^{2}_ {2}(\mathbb{P},\mathbb{Q})=\max_{\textbf{P}\in F_{d_{x},d_{y}}}\max_{\pi\in\Pi (\mathbb{P},\mathbb{Q})}\int\limits_{\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y} }}\langle\textbf{P}\textbf{x},\textbf{y}\rangle_{n}d\pi(\textbf{x},\textbf{y})=$ $\displaystyle-\min_{\textbf{P}\in F_{m,n}}\left[\min_{\pi\in\Pi(\mathbb{P}, \mathbb{Q})}\int\limits_{\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}}-\langle \textbf{P}\textbf{x},\textbf{y}\rangle_{d_{y}}d\pi(\textbf{x},\textbf{y}) \right]=$ $\displaystyle-\min_{\textbf{P}\in F_{d_{x},d_{y}}}\left[\max_{f}\int\limits_{ \mathbb{R}^{d_{x}}}f(\textbf{y})d\mathbb{Q}(\textbf{y})+\min_{T\colon\mathbb{R }^{d_{x}}\to\mathbb{R}^{d_{y}}}\int\limits_{\mathbb{R}^{d_{x}}}-\langle\textbf {P}\textbf{x},T(\textbf{x})\rangle_{d_{y}}-f(T(\textbf{x}))d\mathbb{P}(\textbf {x})\right]=$ $\displaystyle-\min_{\textbf{P}\in F_{d_{x},d_{y}}}\max_{f}\min_{T}\mathcal{L}( \textbf{P},f,T).$ $$

Proof of Theorem 5.2. We expand $\mathcal{L}(\textbf{P}^{*},f^{*},T^{*})$ and use the fact that $T^{*}$ is the OT map.

$$ $\mathcal{L}(\textbf{P}^{*},f^{*},T^{*})=\int\limits_{\mathbb{R}^{d_{y}}}f^{*}( \textbf{y})d\mathbb{Q}(\textbf{y})-\int\limits_{\mathbb{R}^{d_{x}}}\langle \textbf{P}^{*}\textbf{x},T^{*}(\textbf{x})\rangle_{d_{y}}+f^{*}\big{(}T^{*}( \textbf{x})\big{)}d\mathbb{P}(\textbf{x}).$ (9) $$

Since $T^{*}$ is an OT map, we have $T^{*}_{\sharp}\mathbb{P}=\mathbb{Q}$, and by the change of variables formula we get:

$$ $\int\limits_{\mathbb{R}^{d_{x}}}f^{*}\big{(}T^{*}(\textbf{x})\big{)}d\mathbb{P }(\textbf{x})=\int\limits_{\mathbb{R}^{d_{y}}}f^{*}(\textbf{y})d\mathbb{Q}( \textbf{y}).$ $$

Plugging this into (9), we get:

$$ $\mathcal{L}(\textbf{P}^{*},f^{*},T^{*})=-\int\limits_{\mathbb{R}^{d_{x}}} \langle\textbf{P}^{*}\textbf{x},T^{*}(\textbf{x})\rangle_{d_{y}}d\mathbb{P}( \textbf{x}).$ $$

Here, we once again use the fact that $T^{*}$ is the optimal transport map. Now, since $P^{*}$ and $f^{*}$ solve (4), we get the following:

$$ $\operatorname{innerGW}^{2}_{2}(\mathbb{P},\mathbb{Q})=\operatorname{Const}( \mathbb{P},\mathbb{Q})+\min\limits_{T_{\sharp}\mathbb{P}=\mathbb{Q}}\mathcal{L }(\textbf{P}^{*},f^{*},T)$ $$

Finally, from the fact that $\pi^{*}=[\text{id}_{\mathbb{R}^{d_{x}}},T^{*}]_{\sharp}\mathbb{P}$ is optimal and (A), we have:

$$ $\displaystyle-\mathcal{L}(\textbf{P}^{*},f^{*},T^{*})=\int\limits_{\mathbb{R}^ {d_{x}}\times\mathbb{R}^{d_{y}}}\langle\textbf{P}^{*}\textbf{x},\textbf{y} \rangle_{d_{y}}d\pi^{*}(\textbf{x},\textbf{y})=\max_{\pi\in\Pi(\mathbb{P}, \mathbb{Q})}\int\limits_{\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}}\langle \textbf{P}^{*}\textbf{x},\textbf{y}\rangle_{d_{y}}d\pi(\textbf{x},\textbf{y})=$ $\displaystyle-\min_{T_{\sharp}\mathbb{P}=\mathbb{Q}}\mathcal{L}(\textbf{P}^{*} ,f^{*},T^{*}),$ $$

which completes the proof.

## Appendix B Extended experiments

Metrics. We consider two metrics to report: Top $k$-accuracy and FOSCTTM. In both cases, we require to know the true pairs of the source vectors in the target domain, under this assumption the metrics can be defined as follows:

- •
Top $k$-accuracy ($\uparrow$). Considering the set of $N_{test}=m$ vectors from the source distribution and their predictions. For each predicted vectors we compute the $k$-closest samples in the full (400K samples) target dataset (closest in terms of L2 distance) and get a sorted set of $k$ indices $\{c_{1},c_{2},\dots,c_{k}\}$. As we know the indices of the optimal pairs, we can take the label of the expected optimal pair for any vector in the source data, this label will be denoted as $l_{i}$. Therefore, we can define the top $k$-accuracy as follows:
$\text{Top }k\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{m}\sum_{j=1}^{m}
\mathbbm{1}\{l_{j}\in\{c_{1},c_{2},\dots,c_{k}\}\}$
- •
Fraction of Samples Closed Than the True Match (FOSCTTM). ($\downarrow$) We calculate the Euclidean distances from a designated transported point ($\textbf{y}=T(\textbf{x})$) to every data point in the target domain. Using these distances, we then compute the proportion of samples that are nearer to the true pair (this information is known). Finally, we take the average of these proportions for all samples. Perfect alignment would mean that every sample is closest to its true counterpart, producing an average FOSCTTM of zero.
- •
Cosine similarity ($\uparrow$). It is computed between the predicted vector and the expected (optimal pair) vector in the target space.

Accuracy is computed in the whole target data distribution space (400K samples), to speed-up the process we use the faiss [] library.

### B.1 GloVe

Here we provide the following additional experiments: low-to-high dimension combinations for baselines models and NeuraGW as well as experiments for NeuralGW working with a small dataset.

Additional experiments in low-to-high dimension for baselines. We consider the combinations 50$\rightarrow$100 and 25$\rightarrow$25, results are presented as in the experiments section \wasyparagraph4.2, see Figure 6).

Figure: (a) Source: 50 $\rightarrow$ Target:100
Refer to caption: extracted/5672303/images/50_100_discrete_star.png

Additional experiments in low-to-high dimension for our NeuralGW ($N_{train}=$400K). We consider the combinations 50$\rightarrow$100 and 25$\rightarrow$25, here the results are shown in Table 1.

**Table 1: Low-to-high dimension experiment with NeuralGW**
|  | Correlatedness | Top 1 | Top 5 | Top 10 | Cosine similarity | FOSCTTM |
| --- | --- | --- | --- | --- | --- | --- |
| 50$\rightarrow$100 | $\alpha=0.2$ | 0.000 | 0.000 | 0.002 | 0.082 | 0.457 |
| $\alpha=0.5$ | 0.000 | 0.001 | 0.002 | 0.084 | 0.459 |  |
| $\alpha=1.0$ | 0.000 | 0.002 | 0.004 | 0.089 | 0.450 |  |
| 25$\rightarrow$50 | $\alpha=0.2$ | 0.002 | 0.006 | 0.011 | 0.243 | 0.340 |
| $\alpha=0.5$ | 0.000 | 0.002 | 0.003 | 0.191 | 0.371 |  |
| $\alpha=1.0$ | 0.000 | 0.002 | 0.003 | 0.195 | 0.367 |  |

Additional experiments for NeuralGW for high-to-low dimension in small dataset ($N_{train}=$6K). Here we consider the same setup used for the baseline methods in \wasyparagraph4.2 to show how a neural approach performs when it is trained using a limited amount of samples, $N_{train}=$6K, see Table 2.

**Table 2: Small dataset experiments with NeuralGW**
| Dimensions | Correlatedness | Top 1 | Top 5 | Top 10 | Cosine similarity | FOSCTTM |
| --- | --- | --- | --- | --- | --- | --- |
| 100$\rightarrow$50 | $\alpha=0.2$ | 0.000 | 0.000 | 0.003 | 0.100 | 0.462 |
| $\alpha=0.5$ | 0.000 | 0.001 | 0.004 | 0.107 | 0.470 |  |
| $\alpha=1.0$ | 0.000 | 0.003 | 0.005 | 0.117 | 0.447 |  |
| 50$\rightarrow$25 | $\alpha=0.2$ | 0.000 | 0.001 | 0.003 | 0.165 | 0.441 |
| $\alpha=0.5$ | 0.001 | 0.004 | 0.007 | 0.176 | 0.423 |  |
| $\alpha=1.0$ | 0.000 | 0.000 | 0.004 | 0.174 | 0.435 |  |
| 50$\rightarrow$100 | $\alpha=0.2$ | 0.000 | 0.002 | 0.003 | 0.086 | 0.455 |
| $\alpha=0.5$ | 0.000 | 0.003 | 0.005 | 0.084 | 0.459 |  |
| $\alpha=1.0$ | 0.000 | 0.002 | 0.003 | 0.089 | 0.450 |  |
| 25$\rightarrow$50 | $\alpha=0.2$ | 0.000 | 0.002 | 0.005 | 0.113 | 0.440 |
| $\alpha=0.5$ | 0.000 | 0.000 | 0.001 | 0.095 | 0.464 |  |
| $\alpha=1.0$ | 0.001 | 0.003 | 0.005 | 0.124 | 0.436 |  |

Conclusion. For low-to-high experiments, baseline models performance is similar to the high-to-low case showed in \wasyparagraph4.2 of the main work. NeuralGW cannot properly keep the isometry of the probability space when these are learned from a lower dimension.

Finally, NeuralGW is unable to model the inner structures when the number of training samples is small (6K). In general, adversarial algorithms like the used to train NeuralGW require plenty of data to obtain meaningful results.

### B.2 Biological dataset

As seen in the previous experiments, the baselines and NeuralGW solvers have their own limitations and drawbacks heavily linked to their nature. However, in spite of their independent performance, they could partially recover the inner geometry of the domains. In this section we propose a stress test scenario in which the solvers of the conventional GWOT problem yield poor results.

We explore the performance of the baselines solvers and NeuralGW in a biological dataset called bone marrow [] which is considered in the FlowGW paper []. This dataset consists of 6224 samples of two different RNA profiling methods (ATAC+GEX and ADT+GEX), the samples in each domain belong to the same donors, therefore, the real pairs are known. The dimensionality for source and target domains are 38 and 50, respectively. Results can be found in Table 3. All the solvers are tested using 5000 samples for training and the rest for testing.

**Table 3: Results for bone marrow dataset.**
|  | FlowGW | AlignGW | StructuredGW | NeuralGW |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\alpha$ | Top 10 | FOSCTTM | Top 10 | FOSCTTM | Top 10 | FOSCTTM | Top 10 | FOSCTTM |
| 0.2 | 0.004 | 0.486 | 0.004 | 0.488 | 0.001 | 0.489 | 0.003 | 0.479 |
| 0.5 | 0.004 | 0.489 | 0.004 | 0.483 | 0.004 | 0.487 | 0.003 | 0.514 |
| 1.0 | 0.004 | 0.49 | 0.004 | 0.484 | 0.004 | 0.49 | 0.003 | 0.459 |

Conclusions. In all the cases, the solvers could not properly replicate the inner geometry of the distributions even for totally correlated setups, this leaded to get metrics corresponding to random guessing, i.e. accuracies close to 0 and FOSCTTM close to 0.5. There is one case of success for a solver trained on this dataset which corresponds to FlowGW [], however, the reported results in their paper were obtained using a fused-GW solver instead of a conventional GW.

Finally, we can state that there is no general solver for the GWOT problem, all the currently available methods struggle when dealing with real world scenarios, i.e. uncorrelated data, or with real world datasets, i.e. not consistent inner structures.

## Appendix C Solvers’ implementation details

All the experiments were done without any normalization for the source and target vectors and for all the studied methods (baselines and NeuralGW). A total of five repetitions were performed.

StructuredGW.[] We used the code from the official repository:

[https://github.com/othmanesebbouh/prox_rot_aistats](https://github.com/othmanesebbouh/prox_rot_aistats)

As specified in Section \wasyparagraph3, the algorithm uses an iterative solver that updates the cost matrix T by implementing several methods depending on the type of regularization, we only use the exact computation without any regularization. The plan $\pi$ is also updated every iteration by performing Sinkhorn iterations, we set this number of iterations to 1000. The entropy is set to $\varepsilon=$1e-4. The total number of iterations is set to 200 or until convergence.

In this implementation, the authors use the Optimal Transport Tools (OTT) library []. The computation time per repetition until convergence was 30 minutes in average on a CPU.

AlignGW.[] We use the official implementation of the method taken from the repository:

[https://github.com/dmelis/otalign](https://github.com/dmelis/otalign)

We set the entropy term to $\varepsilon=$1e-4 and use the cosine similarity to compute the source and target intra-cost matrices $\textbf{C}^{x}$ and $\textbf{C}^{y}$. We later normalize them by dividing them by their respective means as proposed in the original implementation. The model was trained on a CPU and the average training time was 30 minutes per repetition. The implementation uses the POT library. We train a scikit-learn’s MLPRegressor on top of it as inference method for test data, the parameters are: hidden_layer_sizes=256, random_state=1, max_iter=500.

FlowGW. [] Our implementation of this solver uses Pytorch to model the vector field and the Python Optimal Transport library [] for the Gromov-Wasserstein solver. For the vector field we use the instructions from Appendix \wasyparagraphF.1 in [], we use the following hyperparameters: Number of frequencies: 128, layers per block: 8, hidden dimension: 1024, activation function: silu, optimizer: AdamW (lr=1e-4)

The Gromov-Wasserstein solver was implemented using the Python Optimal Transport (POT) library [] with entropy $\varepsilon=$1e-3 and using cosine similarity distance to compute the intra-domain matrices.

### C.1 NeuralGW.

The innerGW problem in (4) can be optimized using our Algorithm 1.

Figure: Algorithm 1 Training algorithm for Neural Gromov-Wasserstein OT

Every experiment runs for 200 epochs. Each epoch iterates over the whole dataset (400K or 6K samples). $f$ and $T$ are parametrized using multi-layer perceptrons with $n_{l}$ with width $h$, P is taken from the matrix of weights of a linear layer, these models are trained for $k_{f},k_{T}$ and $k_{p}$ iterations, respectively. The implementation details can be seen in Table 4. The batch size is 512 for the experiments with 400K samples and 64 for the experiments with 6K. Our code is written in PyTorch, it can be found at [https://github.com/Ark-130994/GW-Solvers](https://github.com/Ark-130994/GW-Solvers).

**Table 4: Parameters for NeuralGW.**
|  | Model | $k$ | $n_{l}$ | $h$ | lr |
| --- | --- | --- | --- | --- | --- |
| 100$\rightarrow$50<br>50$\rightarrow$25<br>25$\rightarrow$50 | $f$ | $k_{f}=$1 | 4 | 512 | 1e-4 |
| $T$ | $k_{T}=$10 |  |  |  |  |
| $P$ | $k_{P}=$1 |  |  |  |  |
| 50$\rightarrow$25 | $f$ | $k_{f}=$1 | 4 | 256 | 1e-4 |
| $T$ | $k_{T}=$10 |  |  |  |  |
| $P$ | $k_{P}=$1 |  |  |  |  |

Every epoch takes around to 3 minutes running on a GPU NVIDIA Tesla V100.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - Given the high data requirements of NeuralGW's adversarial optimization, would you consider alternate training methods or adaptations to improve performance on smaller datasets? Further clarification on the trade-offs between data size and performance stability would also be insightful.
- Would it be possible to see an empirical or theoretical comparison between NeuralGW and other continuous GWOT methods, particularly on tasks where preserving intra-domain structure is less critical?
- Line 311, indices from the target are incorrect.
- Why were Top k-accuracy, cosine similarity, and FOSCTTM chosen for evaluation?
soundness: 2
strengths: - Analysis of existing GWOT solvers.
- Fill a gap in GWOT literature by questioning the assumptions under which existing solvers operate.
- Proposed partial solution for defined issues.
summary: The paper discusses the challenges of solving the Continuous Gromov-Wasserstein Optimal Transport (GWOT) problem and emphasizes the need for a reliable and general-purpose method to address these issues. The authors claim that current solvers rely on discrete methods and struggle when dealing with uncorrelated data. They then introduce NeuralGW, which is claimed as a method that does not depend on discrete approximations and can therefore handle realistic scenarios with uncorrelated data. However, their method is unstable and requires a large amount of data for training.
weaknesses: - `Diversity`: The evaluation focuses on the GloVe dataset and the biological dataset. It's better to expand experiments to cover additional domains.
- ~The paper still has some issues that need to be addressed in order to support its claims~
- Lack of experiment setup details.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. The authors state that some of the methods are trained on 3K samples whereas their method is trained on 200K samples. While it is acknowledged that this yields an unfair comparison, the difference is a consequence of the poor scaling of the other solvers. This begs the question of why experiments on a smaller scale were not performed to compare the methods fairly. 

2. It appears that the neural entropic Gromov-Wasserstein solver from T. Wang and Z. Goldfeld, Neural Entropic Gromov-Wasserstein Alignment, arXiv, 2023. would serve as a good method to compare to as no structure is assumed on the data generating process.
soundness: 3
strengths: The paper accurately identifies a deficiency in certain GW solvers related to training based on paired samples. The proposed neural network-based GW solver appears to be a reasonable way of dealing with this issue as evidenced by the numerical experiments.
summary: This paper studies the problem of solving the Gromov-Wasserstein (GW) problem numerically. It is shown, in particular, that the case where two datasets are sampled i.i.d. from distributions are particularly challenging for currently available methods.The paper also proposes a neural network-based solver which, in experiments, is seen to outperform other standard methods in the case that correlation between paired training samples is low.
weaknesses: I believe the findings of this paper are not very surprising. Indeed, many of the methods in the paper explicitly assume the setting of paired samples. Furthermore, the GW problem is, in general a computationally hard problem due to its nonconvexity. 

Other than the above empirical observation, the paper does not present many results. Indeed, Lemma 5.1 and Theorem 5.2 are well-known in the literature; these are the only theoretical results provided. As such, the proposed neural approach is not coupled with any guarantees, I believe this severely limits the impact of this paper.

Finally, the numerical experiments are interesting, but are not very conclusive. Indeed, only one experiment is provided. On a related note, half of the methods to which the approach is being compared are labelled as "other methods" in the graphs; this is quite baffling to me and should be rectified.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: See above.
soundness: 2
strengths: The paper points out some issues that have been largely dismissed in the OT and GW community. First the discrete GW solver, when only having access to small batches of datasets that does not have a priori good matching but does have one on a large scale, could have inhomogeneous performance and could be hard to generalize (one such existing attempt is unbalanced GW). Another insight is on the apparent scalability of typical GW solvers, which makes the application of neural networks convincing. The experiments seem thorough, comparing several existing computational method of GW.
summary: The paper proposes to study the continuous Gromov-Wasserstein (GW) problem, i.e. focusing on the scenario when discrete GW solver may not be scalable or not generate to unseen data. Specifically the paper discusses the applicability of GW to various tasks where a latently matched dataset is in place or not, resulting in different performance. The paper then proposes an algorithm with min/max/min formulation that solves the GWOT problem that is compatible with large scale data and does not rely on discrete GW solvers, thus mitigating the aforementioned issues.
weaknesses: 1. Soundness of the theoretical claims:
A major concern is on the main theorems (5.1, 5.2). These results use standard duality and reformulations that involve the optimal Monge map, but the existence is never justified. In particular, it is well known that GW or inner product GW does not necessarily have optimal map, i.e. the minimum may not be achieved [1]. Same for the existence of the optimal potential, see [2]. Thus the claims mostly only serve as heuristics, as theorem 5.2 is solely on characterization of the optimal map. More need to be discussion regarding why parametrizing by neural network is valid when the optimum may not be achieved.


2. Discussion of existing methods and novelty of the proposed algorithm: 
The paper claims to be the first in a comprehensive discussion of continuous GW, and the proposed statistical correlatedness is novel. However the paper is missing many discussions on related works. Most of the paper's missing claims on existence and regularity of Gromov-Monge map have been studied in [1],[3],[4]. The statistics question in section 1 " transition from the discrete to the continuous setup may be questionable from a statistical point of view" is discussed in [2]. Neural network based GW solvers have appeared in [5],[6], both claiming similar applicability to large scale data as mentioned in this paper. The existence of a discrete Gromov-Monge map is first shown in [7]. Detailed discussions on related methods should be added to further strengthen the proposed benchmark.


3. A minor comment on the presentation of Section 4: the paper made several claims about discrete GW problems, ranging from practical statistical assumptions to computational difficulties, but it is not entirely lucid what the main issue is: is it the learned map through extrapolation not generalizing, or the sample complexity is bad, or the optimization is harder with uncorrelated data? The argument could be strengthened with discussions on its relation to other classical learning concepts like generalization error, statistical sample complexity, optimization complexity etc.


[1] Dumont, Théo, Théo Lacombe, and François-Xavier Vialard. "On the existence of Monge maps for the Gromov–Wasserstein problem." Foundations of Computational Mathematics (2024): 1-48.

[2] Zhang, Zhengxin, et al. "Gromov–Wasserstein distances: Entropic regularization, duality and sample complexity." The Annals of Statistics 52.4 (2024): 1616-1645.

[3] Mémoli, Facundo, and Tom Needham. "Comparison results for Gromov–Wasserstein and Gromov–Monge distances." ESAIM: Control, Optimisation and Calculus of Variations 30 (2024): 78.

[4] Mémoli, Facundo, and Tom Needham. "Distance distributions and inverse problems for metric measure spaces." Studies in Applied Mathematics 149.4 (2022): 943-1001.

[5] Hur, YoonHaeng, Wenxuan Guo, and Tengyuan Liang. "Reversible Gromov–Monge sampler for simulation-based inference." SIAM Journal on Mathematics of Data Science 6.2 (2024): 283-310.

[6] Zhang, Zhengxin, et al. "Cycle consistent probability divergences across different spaces." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

[7] Titouan, Vayer, et al. "Sliced gromov-wasserstein." Advances in Neural Information Processing Systems 32 (2019).

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: - I think the Toy 3D->2D problem section needs better explanation. I was quite lost when trying to understand the objective of the experiment or what was being done. Were the mixed Gaussian distributions in the 3D and 2D spaces the same? What do the colors in the plot represent? It might be better to move this part to the appendix because this step merely seems to be a way to validate the implementation of various solvers.
- Not much discussion or insight is present into the reason behind the performance seen in the simulation. What is the reason behind the better performance of NeuralGW when the source and target samples are uncorrelated? Does the smoothness of the underlying distributions affect the variance seen in repetitions? 
- Is there some way to quantify the algorithm's sensitivity to the optimization parameters?
soundness: 4
strengths: - The results seem consistent (or unaffected) by the correlatedness of the source and target samples. This is a significant advantage as the data preprocessing burden is reduced.
- Moreover, this method is proposed for continuous GWOT problems, which other solvers currently do not handle.
summary: The paper considers the continuous GWOT problem and presents a min-max optimization approach as a solution.
The authors focus on two main problems in the paper:
- establishing deficiencies in the existing solvers. In particular, the focus of this discussion is on the quality (or correlatedness) of training samples.
- proposing a solver that addresses the above-mentioned deficiencies by utilizing the smoothness of the underlying distributions.

The paper is well-written and clear. Moreover, the authors established the motivation for the problem and the scope of the study well. The results presented within are clear and concise. 

Having said that, I have the following comments. 
- This work seems to be one of the first to address this problem in a continuous setting. Thus, comparative studies are difficult, and hence, the significance of the work is hard to gauge.
- Moreover, the proposed method performs well in some aspects and poorly in others when compared to existing solvers. Hence, although the insight into the drawbacks of other solvers and the subsequent solution are interesting, I am uncertain if the results are important enough to recommend an acceptance strongly.
weaknesses: Based on my understanding, the following could be considered limitations of this approach:
- Since the method is exclusively for the continuous GWOT problem, the approach presented here would not be helpful in applications where a discrete measure makes better sense. 
- As the authors themselves identified, the method requires large datasets for training, and in general, the results seem to be sensitive to optimization parameters and training data variation.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: Please see the weakness part.
soundness: 3
strengths: The paper conducts a deep analysis of existing papers and reveal that one important characteristic that may greatly affect practical performance is the considered data setup. By following these findings, the authors evaluate the performance of existing continuous GWOT solvers in more statistically fair and practically realistic uncorrelated data setups. To alleviate the dependence on the mutual statistical characteristics of the source and target training data, a continuous neural GW solver was proposed and performed well in practice.
summary: This paper is an attempt to answer the promising question of solving continuous Gromov-Wasserstein Optimal Transport (GWOT) problem. The authors crash-test existing continuous GWOT approaches on different scenarios, carefully record and analyze the obtained results, and identify issues. Their findings experimentally testify that the scientific community is still missing a reliable continuous GWOT
solver, which necessitates further research efforts. As the first step in this direction, the authors propose a neural continuous GWOT method which does not rely on discrete techniques. Their method is based on the key observation that the reformulation of dual continuous GWOT problem can be solved as a min-max-min optimization problem. By simply parameterization with neural networks, the authors use the alternating stochastic gradient ascent/descent/ascent method to train their parameters. The empirical performance is encouraging.
weaknesses: 1. The findings of this paper are interesting and reveal that the empirical success of the existing GWOT solvers seems to be a bit
over-estimated and requires to be treated more critically. However, the interpretation is not thorough. Does this limitation only come from that all existing continuous GWOT solvers heavily rely on discrete techniques? 

2. Your continuous neural GW solver is insightful. Could you provide some theoretical guarantee? I do not think the complexity analysis is necessary but at least your method needs to be guaranteed to converge under certain condition.

Meta-review: The paper addresses the continuous Gromov-Wasserstein Optimal Transport (GWOT) problem and proposes a benchmark alongside a NeuralGW solver to mitigate issues in existing methods. Despite the novelty of focusing on continuous GWOT, the reviewers highlighted several weaknesses that persisted even after the rebuttal. A major concern is the lack of clear motivation and relevance for machine learning (ML) applications. The paper does not convincingly show how the findings provide new insights into ML problems or improve practical scenarios where OT is applied. The theoretical claims, such as the existence of the Gromov-Monge map, are based on heuristics and remain unsubstantiated for non-compact or asymmetric domains. Experimentally, the benchmarks are narrow, focusing on limited datasets (e.g., GloVe embeddings), and fail to include real-world tasks relevant to ML. Additionally, the NeuralGW solver shows poor scalability and high sensitivity to hyperparameters, requiring large datasets to achieve meaningful results. While some new experiments were added, they primarily reinforce the paper’s findings without addressing these broader concerns. The combined lack of theoretical depth, practical relevance, and diversity in experimentation limits the paper’s contributions.

Decision: Reject