Learning Distances from Data with Normalizing Flows and Score Matching

Peter Sorrenson, Daniel Behrend-Uriarte, Christoph Schnoerr, Ullrich Koethe

TL;DR: This paper revitalizes density-based metric learning by replacing crude nearest-neighbor estimators with modern deep generative models. By combining Normalizing Flows for density estimation and Score Matching for path smoothing, the authors enable "Fermat distances" to scale to high dimensions and converge significantly faster than previous graph-based approaches.

The Challenge of Measuring Distance on Manifolds

In machine learning, measuring the "distance" between two points is fundamental. While Euclidean distance is the default, it often fails to capture the intrinsic structure of data. If your data lies on a curved manifold—like a spiral—a straight-line Euclidean path might cut through empty space where no data exists, failing to represent the true relationship between the points.

Density-Based Distances (DBDs), such as Fermat distances, solve this by treating the data distribution like a refractive medium in optics. Paths are considered "cheaper" to traverse in high-density regions and "expensive" in empty space. Consequently, the shortest path (the geodesic) naturally follows the data manifold.

Density-based shortest path following a spiral data manifold

However, calculating these distances in practice is notoriously difficult. Existing methods typically rely on nearest-neighbor (k-NN) graphs to approximate the manifold. These graph-based approaches suffer from two major flaws:

  1. Poor Convergence: They require an impractical amount of data to produce accurate distance estimates.
  2. The Curse of Dimensionality: In high-dimensional spaces, these graph-based paths become jagged and numerically unstable, failing to find the smooth "true" geodesic.
k-NN graph approximations often result in jagged, inaccurate paths compared to the true geodesic

A Generative Approach to Geodesics

To overcome the limitations of graph-based approximations, the authors propose a hybrid framework leveraging modern deep generative models:

  • Normalizing Flows for Density: Instead of counting neighbors to estimate density, the authors train a Normalizing Flow (an invertible neural network) to learn the underlying probability distribution $p(x)$. This provides much smoother and more accurate edge weights for an initial graph-based path.
  • Score-Based Relaxation: To fix the "jagged path" problem inherent to graphs, they introduce a relaxation algorithm. They learn the "score" (the gradient of the log-density, $\nabla \log p(x)$) using Sliced Score Matching. This score acts as a guide, allowing them to iteratively "pull" and smooth the initial graph path until it satisfies the geodesic differential equation.
  • Constant Euclidean Speed Parameterization: Standard differential equation solvers struggle when a path's velocity changes wildly between dense and sparse regions. The authors reparameterize the geodesic equations to maintain constant Euclidean speed, making numerical optimization significantly more stable.
  • Dimension-Adapted Scaling: The standard Fermat distance parameter ($\beta=1$) causes paths to behave erratically in high dimensions. By scaling this parameter by the dimension ($\beta = 1/D$), the geometry remains consistent regardless of the number of features.

Key Insights and Results

The authors rigorously evaluated their method on 2D toy datasets (like spirals and Gaussian mixtures), high-dimensional synthetic Gaussians (up to 25D), and the 10-dimensional latent space of an MNIST autoencoder.

Density is the Bottleneck: A major theoretical insight from the paper is that the slow convergence of previous methods wasn't due to the graph structure itself, but rather the poor quality of nearest-neighbor density estimates. Replacing these with Normalizing Flows immediately bridges the gap to ground-truth performance.

The Score vs. Density Trade-off: Interestingly, differentiating a trained Normalizing Flow to get a score is often too noisy for path relaxation. The authors found it much more effective to train a dedicated score model, highlighting that what is optimal for estimating probability isn't always optimal for estimating its gradient.

Performance Breakthroughs: * Convergence: On 2D datasets, the proposed method converged to the true geodesic distance at nearly the same rate as if the true density were known, leaving traditional power-weighted graph methods far behind. * High-Dimensional Stability: In 25-dimensional spaces where graph-based methods failed completely, the score-based relaxation method maintained high accuracy. It effectively bypassed the curse of dimensionality by relying on the smooth, learned score field. * Meaningful Latent Geodesics: When applied to MNIST, the method produced smooth, interpretable transitions between digits in latent space. A geodesic between a '3' and an '8' passes through intermediate shapes that look like plausible morphed digits, safely staying within the high-density regions of the latent manifold.

Limitations and Future Work

While powerful, the method currently requires a two-step training process: a Normalizing Flow for the initial graph and a separate Score Model for relaxation. Unifying these into a single, efficient framework is a clear next step. Furthermore, while the method excels on toy distributions and latent spaces, scaling it directly to raw, high-dimensional real-world data (like high-resolution images) remains an open challenge tied to the broader frontiers of generative modeling.

Summary updated

Abstract

Density-based distances (DBDs) provide a principled approach to metric learning by defining distances in terms of the underlying data distribution. By employing a Riemannian metric that increases in regions of low probability density, shortest paths naturally follow the data manifold. Fermat distances, a specific type of DBD, have attractive properties, but existing estimators based on nearest neighbor graphs suffer from poor convergence due to inaccurate density estimates. Moreover, graph-based methods scale poorly to high dimensions, as the proposed geodesics are often insufficiently smooth. We address these challenges in two key ways. First, we learn densities using normalizing flows. Second, we refine geodesics through relaxation, guided by a learned score model. Additionally, we introduce a dimension-adapted Fermat distance that scales intuitively to high dimensions and improves numerical stability. Our work paves the way for the practical use of density-based distances, especially in high-dimensional spaces.
BibTeX
@inproceedings{sorrenson2025learning,
  author = {Peter Sorrenson and Daniel Behrend-Uriarte and Christoph Schnoerr and Ullrich Koethe},
  title = {{Learning Distances from Data with Normalizing Flows and Score Matching}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=SOwcmZ91Sl},
}
Figure