More Like this

1. On Scalable and Efficient Computation of Large Scale Optimal Transport

   Xie, Yujia; Chen, Minshuo; Jiang, Haoming; Zhao, Tuo; Zha, Hongyuan (June 2019, International Conference on Machine Learning)

   Optimal Transport (OT) naturally arises in many machine learning applications, yet the heavy computational burden limits its wide-spread uses. To address the scalability issue, we propose an implicit generative learning-based framework called SPOT (Scalable Push-forward of Optimal Transport). Specifically, we approximate the optimal transport plan by a pushforward of a reference distribution, and cast the optimal transport problem into a minimax problem. We then can solve OT problems efficiently using primal dual stochastic gradient-type algorithms. We also show that we can recover the density of the optimal transport plan using neural ordinary differential equations. Numerical experiments on both synthetic and real datasets illustrate that SPOT is robust and has favorable convergence behavior. SPOT also allows us to efficiently sample from the optimal transport plan, which benefits downstream applications such as domain adaptation. 

   more » « less
2. Projection‐based techniques for high‐dimensional optimal transport problems

   https://doi.org/10.1002/wics.1587  

   Zhang, Jingyi; Ma, Ping; Zhong, Wenxuan; Meng, Cheng (May 2022, WIREs Computational Statistics)

   Abstract Optimal transport (OT) methods seek a transformation map (or plan) between two probability measures, such that the transformation has the minimum transportation cost. Such a minimum transport cost, with a certain power transform, is called the Wasserstein distance. Recently, OT methods have drawn great attention in statistics, machine learning, and computer science, especially in deep generative neural networks. Despite its broad applications, the estimation of high‐dimensional Wasserstein distances is a well‐known challenging problem owing to the curse‐of‐dimensionality. There are some cutting‐edge projection‐based techniques that tackle high‐dimensional OT problems. Three major approaches of such techniques are introduced, respectively, the slicing approach, the iterative projection approach, and the projection robust OT approach. Open challenges are discussed at the end of the review. This article is categorized under:Statistical and Graphical Methods of Data Analysis > Dimension ReductionStatistical Learning and Exploratory Methods of the Data Sciences > Manifold Learning 

   more » « less
3. Optimal Transport using GANs for Lineage Tracing

   Prasad, N. (January 2020, Proceedings of Machine Learning Research)

   null (Ed.)

   In this paper, we present Super-OT, a novel approach to computational lineage tracing that combines a supervised learning framework with optimal transport based on Generative Adver-sarial Networks (GANs). Unlike previous ap-proaches to lineage tracing, Super-OT has the flexibility to integrate paired data. We bench-mark Super-OT based on single-cell RNA-seq data against Waddington-OT, a popular approach for lineage tracing that also employs optimal trans-port. We show that Super-OT achieves gains overWaddington-OT in predicting the class outcome of cells during differentiation, since it allows the inte-gration of additional information during training. 

   more » « less
4. Improving Approximate Optimal Transport Distances using Quantization

   Beugnot, Gaspard; Genevay, Aude; Greenewald, Kristjan; Solomon, Justin (July 2021, Uncertainty in Artificial Intelligence)

   Optimal transport (OT) is a popular tool in machine learning to compare probability measures geometrically, but it comes with substantial computational burden. Linear programming algorithms for computing OT distances scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access. We also provide a variant of our algorithm to improve the performance of approximate solvers, focusing on those for entropy-regularized transport. We give theoretical guarantees on the benefits of this quantization step and display experiments showing that it behaves well in practice, providing a practical approximation algorithm that can be used as a drop-in replacement for existing OT estimators. 

   more » « less
5. PARROT: Position-Aware Regularized Optimal Transport for Network Alignment

   https://doi.org/10.1145/3543507.3583357  

   Zeng, Zhichen; Zhang, Si; Xia, Yinglong; Tong, Hanghang (April 2023, WWW '23: Proceedings of the ACM Web Conference 2023)

   Network alignment is a critical steppingstone behind a variety of multi-network mining tasks. Most of the existing methods essentially optimize a Frobenius-like distance or ranking-based loss, ignoring the underlying geometry of graph data. Optimal transport (OT), together with Wasserstein distance, has emerged to be a powerful approach accounting for the underlying geometry explicitly. Promising as it might be, the state-of-the-art OT-based alignment methods suffer from two fundamental limitations, including (1) effectiveness due to the insufficient use of topology and consistency information and (2) scalability due to the non-convex formulation and repeated computationally costly loss calculation. In this paper, we propose a position-aware regularized optimal transport framework for network alignment named PARROT. To tackle the effectiveness issue, the proposed PARROT captures topology information by random walk with restart, with three carefully designed consistency regularization terms. To tackle the scalability issue, the regularized OT problem is decomposed into a series of convex subproblems and can be efficiently solved by the proposed constrained proximal point method with guaranteed convergence. Extensive experiments show that our algorithm achieves significant improvements in both effectiveness and scalability, outperforming the state-of-the-art network alignment methods and speeding up existing OT-based methods by up to 100 times. 

   more » « less