Partial Wasserstein helps overcoming some of the limitations of Optimal Transport when the distributions at stake differ in mass, contain noise or outliers or exhibit mass mismatches across distribution modes. We introduce PAWL, a novel algorithm designed to efficiently compute exact PArtial Wasserstein distances on the Line. PAWL not only solves the partial transportation problem for a specified amount of mass to be transported, but _for all_ admissible mass amounts. This flexibility is valuable for machine learning tasks where the level of noise is uncertain and needs to be determined through cross-validation, for example. By achieving $O(n \log n)$ time complexity for the partial 1-Wasserstein problem on the line, it enables practical applications with large scale datasets. Additionally, we introduce a novel slicing strategy tailored to Partial Wasserstein, which does not permit transporting mass between outliers or noisy data points. We demonstrate the advantages of PAWL in terms of computational efficiency and performance in downstream tasks, outperforming existing (sliced) Partial Optimal Transport techniques.

Optimal Transport (OT) has attracted significant interest in the machine learning community, not only for its ability to define meaningful distances between probability distributions -- such as the Wasserstein distance -- but also for its formulation of OT plans. Its computational complexity remains a bottleneck, though, and slicing techniques have been developed to scale OT to large datasets. Recently, a novel slicing scheme, dubbed min-SWGG, lifts a single one-dimensional plan back to the original multidimensional space, finally selecting the slice that yields the lowest Wasserstein distance as an approximation of the full OT plan. Despite its computational and theoretical advantages, min-SWGG inherits typical limitations of slicing methods: (i) the number of required slices grows exponentially with the data dimension, and (ii) it is constrained to linear projections. Here, we reformulate min-SWGG as a bilevel optimization problem and propose a differentiable approximation scheme to efficiently identify the optimal slice, even in high-dimensional settings. We furthermore define its generalized extension for accommodating data living on manifolds. Finally, we demonstrate the practical value of our approach in various applications, including gradient flows on manifolds and high-dimensional spaces, as well as a novel sliced OT-based conditional flow matching for image generation -- where fast computation of transport plans is essential.

Trees and the associated shortest-path tree metrics provide a powerful framework for representing hierarchical and combinatorial structures in data. Given an arbitrary metric space, its deviation from a tree metric can be quantified by Gromov’s $\delta$-hyperbolicity. Nonetheless, designing algorithms that bridge an arbitrary metric to its closest tree metric is still a vivid subject of interest, as most common approaches are either heuristical and lack guarantees, or perform moderately well. In this work, we introduce a novel differentiable optimization framework, coined DeltaZero, that solves this problem. Our method leverages a smooth surrogate for Gromov’s $\delta$-hyperbolicity which enables a gradient-based optimization, with a tractable complexity. The corresponding optimization procedure is derived from a problem with better worst case guarantees than existing bounds, and is justified statistically. Experiments on synthetic and real-world datasets demonstrate that our method consistently achieves state-of-the-art distortion.

Abstract In many computer vision applications, datasets often exhibit an underlying taxonomy within the label space. To adhere to this hierarchical structure, hyperbolic spaces have emerged as an effective manifold for representation learning, thanks to their ability to encode hierarchical relationships, with little distortion, even for low-dimensional embeddings. Hyperbolic prototypical learning, where class labels are represented by prototypes, has recently demonstrated strong potential in this setting. However, existing methods generally assume a uniform distribution of prototypes, overlooking the hierarchical organization of labels that may be available for a given task. To better exploit this prior knowledge, we propose a hierarchically informed method for prototype positioning. Our approach leverages the Gromov-Wasserstein distance to align the hierarchical relationships between labels with the initial uniform spherical distribution of prototypes, leading to more structured and semantically meaningful representations. Additionally, within a deep learning framework, we propose an alternative characterization of decision boundaries using horospheres, which are level sets of the Busemann function. Geometrically, horospheres correspond to spheres tangent to the boundary of hyperbolic space at a virtual point analogous to a prototype, which makes them a compliant tool in the prototypical learning context. Accordingly, we define a new horospherical layer that can be adapted to any neural network backbone. This layer is particularly advantageous when the number of prototypes exceeds the number of classes, offering enhanced flexibility to the classifier. Through our experiments, we demonstrate that the combination of proper initialization and optimized prototype positioning significantly enhances baseline performance for image classification on hierarchical datasets. Additionally, we validate our approach in two semantic segmentation tasks, using both image and point cloud datasets, confirming its effectiveness in leveraging hierarchical label structures for improved classification performance.

The computer vision community is increasingly interested in exploring hyperbolic space for image representation, as hyperbolic approaches have demonstrated outstanding results in efficiently representing data with an underlying hierarchy. This interest arises from the intrinsic hierarchical nature among images. However, despite the hierarchical nature of remote sensing (RS) images, the investigation of hyperbolic spaces within the RS community has been relatively limited. The objective of this study is therefore to examine the relevance of hyperbolic embeddings of RS data, focusing on scene embedding. Using a Variational Auto-Encoder, we project the data into a hyperbolic latent space while ensuring numerical stability with a feature clipping technique. Experiments conducted on the NWPU-RESISC45 image dataset demonstrate the superiority of hyperbolic embeddings over the Euclidean counterparts in a classification task. Our study highlights the potential of operating in hyperbolic space as a promising approach for embedding RS data.

Wasserstein distance (WD) and the associated optimal transport plan have been proven useful in many applications where probability measures are at stake. In this paper, we propose a new proxy of the squared WD, coined $\textnormal{min-SWGG}$, that is based on the transport map induced by an optimal one-dimensional projection of the two input distributions. We draw connections between $\textnormal{min-SWGG}$, and Wasserstein generalized geodesics in which the pivot measure is supported on a line. We notably provide a new closed form for the exact Wasserstein distance in the particular case of one of the distributions supported on a line allowing us to derive a fast computational scheme that is amenable to gradient descent optimization. We show that $\textnormal{min-SWGG}$, is an upper bound of WD and that it has a complexity similar to as Sliced-Wasserstein, with the additional feature of providing an associated transport plan. We also investigate some theoretical properties such as metricity, weak convergence, computational and topological properties. Empirical evidences support the benefits of $\textnormal{min-SWGG}$, in various contexts, from gradient flows, shape matching and image colorization, among others.

This paper addresses the problem of Unbalanced Optimal Transport (UOT) in which the marginal conditions are relaxed (using weighted penalties in lieu of equality) and no additional regularization is enforced on the OT plan. In this context, we show that the corresponding optimization problem can be reformulated as a non-negative penalized linear regression problem. This reformulation allows us to propose novel algorithms inspired from inverse problems and nonnegative matrix factorization. In particular, we consider majorization-minimization which leads in our setting to efficient multiplicative updates for a variety of penalties. Furthermore, we derive for the first time an efficient algorithm to compute the regularization path of UOT with quadratic penalties. The proposed algorithm provides a continuity of piece-wise linear OT plans converging to the solution of balanced OT (corresponding to infinite penalty weights). We perform several numerical experiments on simulated and real data illustrating the new algorithms, and provide a detailed discussion about more sophisticated optimization tools that can further be used to solve OT problems thanks to our reformulation.

Optimal transport has recently been reintroduced to the machine learning community thanks in part to novel efficient optimization procedures allowing for medium to large scale applications. We propose a Python toolbox that implements several key optimal transport ideas for the machine learning community. The toolbox contains implementations of a number of founding works of OT for machine learning such as Sinkhorn algorithm and Wasserstein barycenters, but also provides generic solvers that can be used for conducting novel fundamental research. This toolbox, named POT for Python Optimal Transport, is open source with an MIT license.

Classical optimal transport problem seeks a transportation map that preserves the total mass between two probability distributions, requiring their masses to be equal. This may be too restrictive in some applications such as color or shape matching, since the distributions may have arbitrary masses and/or only a fraction of the total mass has to be transported. In this paper, we address the partial Wasserstein and Gromov-Wasserstein problems and propose exact algorithms to solve them. We showcase the new formulation in a positive-unlabeled (PU) learning application. To the best of our knowledge, this is the first application of optimal transport in this context and we first highlight that partial Wasserstein-based metrics prove effective in usual PU learning settings. We then demonstrate that partial Gromov-Wasserstein metrics are efficient in scenarii in which the samples from the positive and the unlabeled datasets come from different domains or have different features.

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 the structured objects space. Unlike Wasserstein or Gromov-Wasserstein metrics that focus solely and respectively on features (by considering a metric in the feature space) or structure (by seeing structure as a metric space), our new distance exploits jointly both information, and is consequently called Fused Gromov-Wasserstein (FGW). After discussing its properties and computational aspects, we show results on a graph classification task, where our method outperforms both graph kernels and deep graph convolutional networks. Exploiting further on the metric properties of FGW, interesting geometric objects such as Fr{é}chet means or barycenters of graphs are illustrated and discussed in a clustering context.

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 costly both in time and memory. Contrary to GW, the Wasserstein distance (W) enjoys several properties ({\em e.g.} duality) that permit large scale optimization. Among those, the solution of W on the real line, that only requires sorting discrete samples in 1D, allows defining the Sliced Wasserstein (SW) distance. This paper proposes a new divergence based on GW akin to SW. We first derive a closed form for GW when dealing with 1D distributions, based on a new result for the related quadratic assignment problem. We then define a novel OT discrepancy that can deal with large scale distributions via a slicing approach and we show how it relates to the GW distance while being $O(n\log(n))$ to compute. We illustrate the behavior of this so called Sliced Gromov-Wasserstein (SGW) discrepancy in experiments where we demonstrate its ability to tackle similar problems as GW while being several order of magnitudes faster to compute.

Automatic land cover classification from satellite image time series is of paramount relevance to assess vegetation and crop status, with important implications in agriculture, biofuels, and food. However, due to the high cost and human resources needed to characterize and classify land cover through field campaigns, a recurrent limiting factor is the lack of available labeled data. On top of this, the biophysical-geophysical variables exhibit particular temporal structures that need to be exploited. Land cover classification based on image time series is very complex because of the data manifold distortions through time. We propose the use of the kernel manifold alignment (KEMA) method for domain adaptation of remote sensing time series before classification. KEMA is nonlinear and semisupervised and reduces to solve a simple generalized eigenproblem. We give empirical evidence of performance through classification of biophysical (leaf area index, fraction of absorbed photosynthetically active radiation, fractional vegetation cover, and normalized difference vegetation index) time series on a global scale.

Mapping croplands is a challenging problem in a context of climate change and evolving agricultural calendars. Classification based on MODIS vegetation index time series is performed in order to map crop types in the Brazilian state of Mato Grosso. We used the recently developed Dense Bag-of-Temporal-SIFT-Words algorithm, which is able to capture temporal locality of the data. It allows the accurate detection of around 70% of the agricultural areas. It leads to better classification rates than a baseline algorithm, discriminating more accurately classes with similar profiles.

A new classification technique, PerTurbo, has been investigated in the context on hyperspectral remote sensing images context. In this framework, each class is characterised by its Laplace-Beltrami operator, then approximated by the spectrum of K(S), whose terms are derived from the Gaussian kernel. The method is very simple, easy to implement and involves few parameters to tune. It also allows the definition of a simple multi-class strategy, and, as a class-wise classification method, the addition of a new class does not requires the re-training of the pre-existing class models. We conducted experiments on two datasets: results for Pavia Centre dataset are encouraging, while results obtained on Pavia University show that SVM clearly outperforms PerTurbo. Nevertheless, we believe that this difference comes from a bad parametrization of the algorithm (for which we used a rule of thumb, contrarily to the SVM procedure which was fully optimized). Hence, a systematic search for the optimal value of the parameter would improve the results. Moreover, there are several other possible improvements coming from the fields of regularization methods of dimensionality reduction techniques which let us think that this first experiment is promising. In the near future, we also plan to investigate rules leading to a better choice of s. We are also interested in studying the behavior of PerTurbo when the classes are heterogeneous with only few training samples available, or when the classes in the training set are highly unbalanced.

Modern distributed applications and communication services have become increasingly complex, composed of diverse heterogeneous sub-systems, and it is progressively more unrealistic that the users of these systems will be able to manage them in a holistic end-to-end manner. In particular, it is increasingly difficult to understand how such systems operate, the meaning of errors, and how they can be manipulated in a managed way, cognisant of the end-to-end nature of these systems. This paper describes an approach to semantically enrich monitoring information, events and faults, and management actions in such a way that they can be presented to a manager in manner that can be understood and leveraged. This work is based on one of the key scenarios FAME research project.