Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem

• URL: http://arxiv.org/abs/2303.05978v2
• Date: Mon, 17 Jun 2024 13:10:00 GMT
• Title: Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem
• Authors: Xavier Aramayo Carrasco, Maksim Nekrashevich, Petr Mokrov, Evgeny Burnaev, Alexander Korotin,
• Abstract summary: The Gromov-Wasserstein Optimal Transport (GWOT) problem has attracted the special attention of the ML community. We crash-test existing continuous GWOT approaches on different scenarios, carefully record and analyze the obtained results, and identify issues. We propose a new continuous GWOT method which does not rely on discrete techniques and partially solves some of the problems of competitors.
• Score: 63.99794069984492
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• A Contrastive Variational Graph Auto-Encoder for Node Clustering [10.52321770126932]
  State-of-the-art clustering methods have numerous challenges. Existing VGAEs do not account for the discrepancy between the inference and generative models. Our solution has two mechanisms to control the trade-off between Feature Randomness and Feature Drift.
  arXiv  Detail & Related papers  (2023-12-28T05:07:57Z)
• Stable Differentiable Causal Discovery [2.0249250133493195]
  We propose Stable Differentiable Causal Discovery (SDCD) for referring causal relationships as directed acyclic graphs (DAGs) We first derive SDCD and prove its stability and correctness. We then evaluate it with both observational and interventional data and on both small-scale and large-scale settings. We find that SDCD outperforms existing methods in both convergence speed and accuracy and can scale to thousands of variables.
  arXiv  Detail & Related papers  (2023-11-17T01:14:24Z)
• Latent SDEs on Homogeneous Spaces [9.361372513858043]
  We consider the problem of variational Bayesian inference in a latent variable model where a (possibly complex) observed geometric process is governed by the solution of a latent differential equation (SDE) Experiments demonstrate that a latent SDE of the proposed type can be learned efficiently by means of an existing one-step Euler-Maruyama scheme.
  arXiv  Detail & Related papers  (2023-06-28T14:18:52Z)
• Building the Bridge of Schr\"odinger: A Continuous Entropic Optimal Transport Benchmark [96.06787302688595]
  We propose a novel way to create pairs of probability distributions for which the ground truth OT solution is known by the construction. We use these benchmark pairs to test how well existing neural EOT/SB solvers actually compute the EOT solution.
  arXiv  Detail & Related papers  (2023-06-16T20:03:36Z)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  We propose a novel approach to approximate the gradient of parameters involved in generating discrete latent variables. We propose ReinMax, which achieves second-order accuracy by integrating Heun's method, a second-order numerical method for solving ODEs.
  arXiv  Detail & Related papers  (2023-04-17T20:59:49Z)
• Learning to Solve PDE-constrained Inverse Problems with Graph Networks [51.89325993156204]
  In many application domains across science and engineering, we are interested in solving inverse problems with constraints defined by a partial differential equation (PDE) Here we explore GNNs to solve such PDE-constrained inverse problems. We demonstrate computational speedups of up to 90x using GNNs compared to principled solvers.
  arXiv  Detail & Related papers  (2022-06-01T18:48:01Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Geometric Entropic Exploration [52.67987687712534]
  We introduce a new algorithm that maximises the geometry-aware Shannon entropy of state-visits in both discrete and continuous domains. Our key theoretical contribution is casting geometry-aware MSVE exploration as a tractable problem of optimising a simple and novel noise-contrastive objective function. In our experiments, we show the efficiency of GEM in solving several RL problems with sparse rewards, compared against other deep RL exploration approaches.
  arXiv  Detail & Related papers  (2021-01-06T14:15:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.