More Like this

1. Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms

   García_Trillos, Nicolás; Little, Anna; McKenzie, Daniel; Murphy, James (June 2024, Journal of machine learning research)

   We analyze the convergence properties of Fermat distances, a family of density-driven metrics defined on Riemannian manifolds with an associated probability measure. Fermat distances may be defined either on discrete samples from the underlying measure, in which case they are random, or in the continuum setting, where they are induced by geodesics under a density-distorted Riemannian metric. We prove that discrete, sample-based Fermat distances converge to their continuum analogues in small neighborhoods with a precise rate that depends on the intrinsic dimensionality of the data and the parameter governing the extent of density weighting in Fermat distances. This is done by leveraging novel geometric and statistical arguments in percolation theory that allow for non-uniform densities and curved domains. Our results are then used to prove that discrete graph Laplacians based on discrete, sample-driven Fermat distances converge to corresponding continuum operators. In particular, we show the discrete eigenvalues and eigenvectors converge to their continuum analogues at a dimension-dependent rate, which allows us to interpret the efficacy of discrete spectral clustering using Fermat distances in terms of the resulting continuum limit. The perspective afforded by our discrete-to-continuum Fermat distance analysis leads to new clustering algorithms for data and related insights into efficient computations associated to density-driven spectral clustering. Our theoretical analysis is supported with numerical simulations and experiments on synthetic and real image data. 

   more » « less
2. Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation.

   https://doi.org/10.1007/978-3-030-93302-9_4  

   Craig, Katy; Garcia Trillos, Nicolas; Slepcev, Dejan (December 2021, Modeling and simulation in science engineering technology)

   Bellomo, N.; Carrillo, J.A.; Tadmor, E. (Ed.)

   In this work, we build a unifying framework to interpolate between density-driven and geometry-based algorithms for data clustering and, specifically, to connect the mean shift algorithm with spectral clustering at discrete and continuum levels. We seek this connection through the introduction of Fokker–Planck equations on data graphs. Besides introducing new forms of mean shift algorithms on graphs, we provide new theoretical insights on the behavior of the family of diffusion maps in the large sample limit as well as provide new connections between diffusion maps and mean shift dynamics on a fixed graph. Several numerical examples illustrate our theoretical findings and highlight the benefits of interpolating density-driven and geometry-based clustering algorithms. 

   more » « less
3. Learning by Unsupervised Nonlinear Diffusion

   Maggioni, Mauro; Murphy, James M. (January 2019, Journal of machine learning research)

   This paper proposes and analyzes a novel clustering algorithm, called \emph{learning by unsupervised nonlinear diffusion (LUND)}, that combines graph-based diffusion geometry with techniques based on density and mode estimation. LUND is suitable for data generated from mixtures of distributions with densities that are both multimodal and supported near nonlinear sets. A crucial aspect of this algorithm is the use of time of a data-adapted diffusion process, and associated diffusion distances, as a scale parameter that is different from the local spatial scale parameter used in many clustering algorithms. We prove estimates for the behavior of diffusion distances with respect to this time parameter under a flexible nonparametric data model, identifying a range of times in which the mesoscopic equilibria of the underlying process are revealed, corresponding to a gap between within-cluster and between-cluster diffusion distances. These structures may be missed by the top eigenvectors of the graph Laplacian, commonly used in spectral clustering. This analysis is leveraged to prove sufficient conditions guaranteeing the accuracy of LUND. We implement LUND and confirm its theoretical properties on illustrative data sets, demonstrating its theoretical and empirical advantages over both spectral and density-based clustering. 

   more » « less
4. Nonlocal-Interaction Equation on Graphs: Gradient Flow Structure and Continuum Limit

   https://doi.org/10.1007/s00205-021-01631-w  

   Esposito, Antonio; Patacchini, Francesco S.; Schlichting, André; Slepčev, Dejan (May 2021, Archive for Rational Mechanics and Analysis)

   null (Ed.)

   Abstract We consider dynamics driven by interaction energies on graphs. We introduce graph analogues of the continuum nonlocal-interaction equation and interpret them as gradient flows with respect to a graph Wasserstein distance. The particular Wasserstein distance we consider arises from the graph analogue of the Benamou–Brenier formulation where the graph continuity equation uses an upwind interpolation to define the density along the edges. While this approach has both theoretical and computational advantages, the resulting distance is only a quasi-metric. We investigate this quasi-metric both on graphs and on more general structures where the set of “vertices” is an arbitrary positive measure. We call the resulting gradient flow of the nonlocal-interaction energy the nonlocal nonlocal-interaction equation (NL $$^2$$ 2 IE). We develop the existence theory for the solutions of the NL $$^2$$ 2 IE as curves of maximal slope with respect to the upwind Wasserstein quasi-metric. Furthermore, we show that the solutions of the NL $$^2$$ 2 IE on graphs converge as the empirical measures of the set of vertices converge weakly, which establishes a valuable discrete-to-continuum convergence result. 

   more » « less
5. Tight Stability Bounds for Entropic Brenier Maps

   https://doi.org/10.1093/imrn/rnaf078  

   Divol, Vincent; Niles-Weed, Jonathan; Pooladian, Aram-Alexandre (April 2025, International Mathematics Research Notices)

   Abstract Entropic Brenier maps are regularized analogues of Brenier maps (optimal transport maps) which converge to Brenier maps as the regularization parameter shrinks. In this work, we prove quantitative stability bounds between entropic Brenier maps under variations of the target measure. In particular, when all measures have bounded support, we establish the optimal Lipschitz constant for the mapping from probability measures to entropic Brenier maps. This provides an exponential improvement to a result of Carlier, Chizat, and Laborde (2024). As an application, we prove near-optimal bounds for the stability of semi-discrete unregularized Brenier maps for a family of discrete target measures. 

   more » « less