Track genomics, neuroscience and molecular biology.
Search papers, labs, and topics across Lattice.
To overcome the prohibitive cubic computational complexity of comparing distributions across non-Euclidean manifolds, the authors develop EGGroW to scale geodesic Gromov-Wasserstein distances via entropic Sinkhorn iterations and random feature expansions. This fills a critical gap where scalable kernel methods existed for flat Euclidean metrics but failed on intrinsic Riemannian manifolds and mesh shortest-path spaces. Evaluated on 3D pose estimation and partial template recovery, the approach maintains a lightweight computational footprint and accurately resolves correspondences in non-rigid regimes where standard Euclidean optimal transport baselines fail.
Non-rigid 3D surface matching can finally scale without sacrificing intrinsic geometry, breaking the cubic-time barrier that previously made geodesic optimal transport intractable.
\textit{Gromov-Wasserstein Distances} (GWDs) provide quantitative ways of comparing probabilistic distributions defined on different metric spaces by applying techniques from the optimal transport theory. As such, GWD can be potentially useful in a large variety of applications ranging from graph matching problems to 3D object detection. However its practical use at scale is significantly limited by cubic time complexity computations involving dense intra-space distance matrices. Even though in the Euclidean metric spaces several techniques (e.g. involving scalable kernel methods) were proposed to address it, to the best of our knowledge, analogous techniques for general geodesic distances on manifolds, or shortest-path distance on graphs in their discretized variants, were not developed. In this paper, we present \textbf{E}fficient \textbf{G}eodesic \textbf{Gro}mov-\textbf{W}asserstein methods (EGGroW), a new class of efficient algorithms designed to calculate geodesic Gromov-Wasserstein distances with entropic Sinkhorn-like approaches, leveraging recently introduced \textit{GenusSink} methods \citep{genussink} and the theory of random features. We provide important downstream applications, namely: 3D pose estimation and 3D template detection. In the latter setting, we formulate a partial 3D template recovery as a staged problem: capacity-constrained scene selection is followed by semi-relaxed recovery of template visibility and correspondence. Our empirical findings show that EGGroW provides accurate solutions when standard Euclidean-based techniques fail and is characterized by light computational footprint, as our theoretical analysis predicts.
DeepMind