Facundo Mémoli

JMLR Journal 2025 Journal Article

Geometry and Stability of Supervised Learning Problems

• Facundo Mémoli
• Brantley Vose
• Robert C. Williamson

We introduce a notion of distance between supervised learning problems, which we call the Risk distance. This distance, inspired by optimal transport, facilitates stability results; one can quantify how seriously issues like sampling bias, noise, limited data, and approximations might change a given problem by bounding how much these modifications can move the problem under the Risk distance. With the distance established, we explore the geometry of the resulting space of supervised learning problems, providing explicit geodesics and proving that the set of classification problems is dense in a larger class of problems. We also provide two variants of the Risk distance: one that incorporates specified weights on a problem's predictors, and one that is more sensitive to the contours of a problem's risk landscape. [abs] [ pdf ][ bib ] &copy JMLR 2025. ( edit, beta )

JMLR Journal 2025 Journal Article

The Z-Gromov-Wasserstein Distance

• Martin Bauer
• Facundo Mémoli
• Tom Needham
• Mao Nishino

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. [abs] [ pdf ][ bib ] &copy JMLR 2025. ( edit, beta )

ICML Conference 2022 Conference Paper

Weisfeiler-Lehman Meets Gromov-Wasserstein

• Samantha Chen 0001
• Sunhyuk Lim
• Facundo Mémoli
• Zhengchao Wan
• Yusu Wang 0001

The Weisfeiler-Lehman (WL) test is a classical procedure for graph isomorphism testing. The WL test has also been widely used both for designing graph kernels and for analyzing graph neural networks. In this paper, we propose the Weisfeiler-Lehman (WL) distance, a notion of distance between labeled measure Markov chains (LMMCs), of which labeled graphs are special cases. The WL distance is polynomial time computable and is also compatible with the WL test in the sense that the former is positive if and only if the WL test can distinguish the two involved graphs. The WL distance captures and compares subtle structures of the underlying LMMCs and, as a consequence of this, it is more discriminating than the distance between graphs used for defining the state-of-the-art Wasserstein Weisfeiler-Lehman graph kernel. Inspired by the structure of the WL distance we identify a neural network architecture on LMMCs which turns out to be universal w. r. t. continuous functions defined on the space of all LMMCs (which includes all graphs) endowed with the WL distance. Finally, the WL distance turns out to be stable w. r. t. a natural variant of the Gromov-Wasserstein (GW) distance for comparing metric Markov chains that we identify. Hence, the WL distance can also be construed as a polynomial time lower bound for the GW distance which is in general NP-hard to compute.

ICML Conference 2019 Conference Paper

The Wasserstein Transform

• Facundo Mémoli
• Zane T. Smith
• Zhengchao Wan

We introduce the Wasserstein transform, a method for enhancing and denoising datasets defined on general metric spaces. The construction draws inspiration from Optimal Transportation ideas. We establish the stability of our method under data perturbation and, when the dataset is assumed to be Euclidean, we also exhibit a precise connection between the Wasserstein transform and the mean shift family of algorithms. We then use this connection to prove that mean shift also inherits stability under perturbations. We study the performance of the Wasserstein transform method on different datasets as a preprocessing step prior to clustering and classification tasks.

SODA Conference 2018 Conference Paper

Persistent Path Homology of Directed Networks

• Samir Chowdhury 0001
• Facundo Mémoli

While standard persistent homology has been successful in extracting information from metric datasets, its applicability to more general data, e. g. directed networks, is hindered by its natural insensitivity to asymmetry. We extend a construction of homology of digraphs due to Grigoryan, Lin, Muranov and Yau to the persistent framework. The result, which we call persistent path homology or PPH, encodes a rich level of detail about the asymmetric structure of the input directed network. For example, we prove that PPH identifies a class of directed cyclic networks as directed analogues of the circle. In general, PPH produces signatures that differ from natural extensions of Rips or Čech persistence to the directed setting, but we prove that PPH agrees with Čech persistence on symmetric spaces. Additionally, we prove that PPH agrees with Čech persistence on directed networks satisfying a local condition that we call square-freeness. We prove stability of PPH by utilizing a separate theory of homotopy of digraphs that is compatible with path homology. Finally, we study computational aspects of PPH, and derive an algorithm showing that over field coefficients, computing PPH requires the same worst case running time as standard persistent homology.

NeurIPS Conference 2016 Conference Paper

Improved Error Bounds for Tree Representations of Metric Spaces

• Samir Chowdhury
• Facundo Mémoli
• Zane Smith

Estimating optimal phylogenetic trees or hierarchical clustering trees from metric data is an important problem in evolutionary biology and data analysis. Intuitively, the goodness-of-fit of a metric space to a tree depends on its inherent treeness, as well as other metric properties such as intrinsic dimension. Existing algorithms for embedding metric spaces into tree metrics provide distortion bounds depending on cardinality. Because cardinality is a simple property of any set, we argue that such bounds do not fully capture the rich structure endowed by the metric. We consider an embedding of a metric space into a tree proposed by Gromov. By proving a stability result, we obtain an improved additive distortion bound depending only on the hyperbolicity and doubling dimension of the metric. We observe that Gromov's method is dual to the well-known single linkage hierarchical clustering (SLHC) method. By means of this duality, we are able to transport our results to the setting of SLHC, where such additive distortion bounds were previously unknown.

SODA Conference 2016 Conference Paper

Multiscale Mapper: Topological Summarization via Codomain Covers

• Tamal K. Dey
• Facundo Mémoli
• Yusu Wang 0001

ICML Conference 2014 Conference Paper

Hierarchical Quasi-Clustering Methods for Asymmetric Networks

• Gunnar E. Carlsson
• Facundo Mémoli
• Alejandro Ribeiro
• Santiago Segarra

This paper introduces hierarchical quasi-clustering methods, a generalization of hierarchical clustering for asymmetric networks where the output structure preserves the asymmetry of the input data. We show that this output structure is equivalent to a finite quasi-ultrametric space and study admissibility with respect to two desirable properties. We prove that a modified version of single linkage is the only admissible quasi-clustering method. Moreover, we show stability of the proposed method and we establish invariance properties fulfilled by it. Algorithms are further developed and the value of quasi-clustering analysis is illustrated with a study of internal migration within United States.

JMLR Journal 2010 Journal Article

Characterization, Stability and Convergence of Hierarchical Clustering Methods

• Gunnar Carlsson
• Facundo Mémoli

We study hierarchical clustering schemes under an axiomatic view. We show that within this framework, one can prove a theorem analogous to one of Kleinberg (2002), in which one obtains an existence and uniqueness theorem instead of a non-existence result. We explore further properties of this unique scheme: stability and convergence are established. We represent dendrograms as ultrametric spaces and use tools from metric geometry, namely the Gromov-Hausdorff distance, to quantify the degree to which perturbations in the input metric space affect the result of hierarchical methods. [abs] [ pdf ][ bib ] &copy JMLR 2010. ( edit, beta )

YNIMG Journal 2004 Journal Article

Implicit brain imaging

• Facundo Mémoli
• Guillermo Sapiro
• Paul Thompson

We describe how implicit surface representations can be used to solve fundamental problems in brain imaging. This kind of representation is not only natural following the state-of-the-art segmentation algorithms reported in the literature to extract the different brain tissues, but it is also, as shown in this paper, the most appropriate one from the computational point of view. Examples are provided for finding constrained special curves on the cortex, such as sulcal beds, regularizing surface-based measures, such as cortical thickness, and for computing warping fields between surfaces such as the brain cortex. All these result from efficiently solving partial differential equations (PDEs) and variational problems on surfaces represented in implicit form. The implicit framework avoids the need to construct intermediate mappings between 3-D anatomical surfaces and parametric objects such planes or spheres, a complex step that introduces errors and is required by many other cortical processing approaches.