Dimension reduction techniques typically seek an embedding of a high-dimensional point cloud into a low-dimensional Euclidean space which optimally preserves the geometry of the input data. Based on expert knowledge, one may instead wish to embed the data into some other manifold or metric space in order to better reflect the geometry or topology of the point cloud. We propose a general method for manifold-valued multidimensional scaling based on concepts from optimal transport. In particular, we establish theoretical connections between the recently introduced semi-relaxed Gromov-Wasserstein (srGW) framework and multidimensional scaling by solving the Monge problem in this setting. We also derive novel connections between srGW distance and Gromov-Hausdorff distance. We apply our computational framework to analyze ensembles of political redistricting plans for states with two Congressional districts, achieving an effective visualization of the ensemble as a distribution on a circle which can be used to characterize typical neutral plans, and to flag outliers.

The Gromov-Wasserstein (GW) distance is a powerful tool for comparing metric measure spaces which has found broad applications in data science and machine learning. Driven by the need to analyze data sets whose objects have increasingly complex structure (such as node and edge-attributed graphs), several variants of GW distance have been introduced in the recent literature. With a view toward establishing a general framework for the theory of GW-like distances, this paper considers a vast generalization of the notion of a metric measure space: for an arbitrary metric space $Z$, we define a $Z$-network to be a measure space endowed with a kernel valued in $Z$. We introduce a method for comparing $Z$-networks by defining a generalization of GW distance, which we refer to as $Z$-Gromov-Wasserstein ($Z$-GW) distance. This construction subsumes many previously known metrics and offers a unified approach to understanding their shared properties. This paper demonstrates that the $Z$-GW distance defines a metric on the space of $Z$-networks which retains desirable properties of $Z$, such as separability, completeness, and geodesicity. Many of these properties were unknown for existing variants of GW distance that fall under our framework. Our focus is on foundational theory, but our results also include computable lower bounds and approximations of the distance which will be useful for practical applications.

In this paper, we present a flexible and probabilistic framework for tracking topological features in time-varying scalar fields using merge trees and partial optimal transport. Merge trees are topological descriptors that record the evolution of connected components in the sublevel sets of scalar fields. We present a new technique for modeling and comparing merge trees using tools from partial optimal transport. In particular, we model a merge tree as a measure network, that is, a network equipped with a probability distribution, and define a notion of distance on the space of merge trees inspired by partial optimal transport. Such a distance offers a new and flexible perspective for encoding intrinsic and extrinsic information in the comparative measures of merge trees. More importantly, it gives rise to a partial matching between topological features in time-varying data, thus enabling flexible topology tracking for scientific simulations. Furthermore, such partial matching may be interpreted as probabilistic coupling between features at adjacent time steps, which gives rise to probabilistic tracking graphs. We derive a stability result for our distance and provide numerous experiments indicating the efficacy of our framework in extracting meaningful feature tracks.

Given a map $f:X \to M$ from a topological space $X$ to a metric space $M$, a decorated Reeb space consists of the Reeb space, together with an attribution function whose values recover geometric information lost during the construction of the Reeb space. For example, when $M=\mathbb{R}$ is the real line, the Reeb space is the well-known Reeb graph, and the attributions may consist of persistence diagrams summarizing the level set topology of $f$. In this paper, we introduce decorated Reeb spaces in various flavors and prove that our constructions are Gromov-Hausdorff stable. We also provide results on approximating decorated Reeb spaces from finite samples and leverage these to develop a computational framework for applying these constructions to point cloud data.

This paper provides developments in statistical shape analysis of shape graphs, and demonstrates them using such complex objects as Retinal Blood Vessel (RBV) networks and neurons. The shape graphs are represented by sets of nodes and edges (articulated curves) connecting some nodes. The goals are to utilize nodes (locations, connectivity) and edges (edge weights and shapes) to: (1) characterize shapes, (2) quantify shape differences, and (3) model statistical variability. We develop a mathematical representation, elastic Riemannian metrics, and associated tools for shape graphs. Specifically, we derive tools for shape graph registration, geodesics, statistical summaries, shape modeling, and shape synthesis. Geodesics are convenient for visualizing optimal deformations, and PCA helps in dimension reduction and statistical modeling. One key challenge lies in comparing shape graphs with vastly different complexities (in number of nodes and edges). This paper introduces a novel multi-scale representation to handle this challenge. Using the notions of (1) "effective resistance" to cluster nodes and (2) elastic shape averaging of edge curves, it reduces graph complexity while retaining overall structures. This allows shape comparisons by bringing graphs to similar complexities. We demonstrate these ideas on 2D RBV networks from the STARE and DRIVE databases and 3D neurons from the NeuroMorpho database.

This paper uses sample data to study the problem of comparing populations on finite-dimensional parallelizable Riemannian manifolds and more general trivial vector bundles. Utilizing triviality, our framework represents populations as mixtures of Gaussians on vector bundles and estimates the population parameters using a mode-based clustering algorithm. We derive a Wasserstein-type metric between Gaussian mixtures, adapted to the manifold geometry, in order to compare estimated distributions. Our contributions include an identifiability result for Gaussian mixtures on manifold domains and a convenient characterization of optimal couplings of Gaussian mixtures under the derived metric. We demonstrate these tools on some example domains, including the preshape space of planar closed curves, with applications to the shape space of triangles and populations of nanoparticles. In the nanoparticle application, we consider a sequence of populations of particle shapes arising from a manufacturing process and utilize the Wasserstein-type distance to perform change-point detection.

We establish a bridge between spectral clustering and Gromov-Wasserstein Learning (GWL), a recent optimal transport-based approach to graph partitioning. This connection both explains and improves upon the state-of-the-art performance of GWL. The Gromov-Wasserstein framework provides probabilistic correspondences between nodes of source and target graphs via a quadratic programming relaxation of the node matching problem. Our results utilize and connect the observations that the GW geometric structure remains valid for any rank-2 tensor, in particular the adjacency, distance, and various kernel matrices on graphs, and that the heat kernel outperforms the adjacency matrix in producing stable and informative node correspondences. Using the heat kernel in the GWL framework provides new multiscale graph comparisons without compromising theoretical guarantees, while immediately yielding improved empirical results. A key insight of the GWL framework toward graph partitioning was to compute GW correspondences from a source graph to a template graph with isolated, self-connected nodes. We show that when comparing against a two-node template graph using the heat kernel at the infinite time limit, the resulting partition agrees with the partition produced by the Fiedler vector. This in turn yields a new insight into the k-cut graph partitioning problem through the lens of optimal transport. Our experiments on a range of real-world networks achieve comparable results to, and in many cases outperform, the state-of-the-art achieved by GWL.

In the shape analysis approach to computer vision problems, one treats shapes as points in an infinite-dimensional Riemannian manifold, thereby facilitating algorithms for statistical calculations such as geodesic distance between shapes and averaging of a collection of shapes. The performance of these algorithms depends heavily on the choice of the Riemannian metric. In the setting of plane curve shapes, attention has largely been focused on a two-parameter family of first order Sobolev metrics, referred to as elastic metrics. They are particularly useful due to the existence of simplifying coordinate transformations for particular parameter values, such as the well-known square-root velocity transform. In this paper, we extend the transformations appearing in the existing literature to a family of isometries, which take any elastic metric to the flat $L^2$ metric. We also extend the transforms to treat piecewise linear curves and demonstrate the existence of optimal matchings over the diffeomorphism group in this setting. We conclude the paper with multiple examples of shape geodesics for open and closed curves. We also show the benefits of our approach in a simple classification experiment.