Weighted Geodesic Distance Following Fermat's Principle

Facundo Sapienza, Pablo Groisman, Matthieu JonckheereWorkshops @ ICLR 2018

Introduction

In machine learning tasks like clustering or dimensionality reduction, accurately measuring the "closeness" of two points is critical. Standard Euclidean distance—a straight line—often fails when data lives on a curved surface or "manifold," such as the classic Swiss Roll dataset.

Existing tools like Isomap attempt to solve this by calculating "geodesic distances," which are paths that follow the contours of the manifold. However, Isomap fundamentally assumes that data points are spread out uniformly. In real-world scenarios, data is rarely uniform; some regions are dense, while others are sparse. When density varies, standard geodesic estimators struggle to distinguish between actual distinct clusters and the noisy "bridges" of sparse points that might connect them.

To address this, researchers have introduced the $d$-distance, a novel density-based estimator for calculating distances between points on a manifold. By raising local distances to a power $d > 1$, the algorithm naturally favors paths through high-density regions. This approach is heavily inspired by optics—specifically Fermat’s Principle—and leads to significantly better performance in clustering and dimensionality reduction for non-uniform datasets.

The $d$-Distance Estimator and Fermat's Principle

The authors propose the $d$-distance estimator to redefine how we measure paths. Given a set of points, the distance between two points $\mathbf{p}$ and $\mathbf{q}$ is defined as the minimum sum of local distances raised to the power $d$:

$$\mathcal{D}_{\mathbb{X}_N}(\mathbf{p}, \mathbf{q}) = \min \sum \ell(\mathbf{x}_i, \mathbf{x}_{i+1})^d$$

The Optics Analogy

The core innovation here is an elegant analogy to physics. In optics, Fermat’s Principle states that light travels between two points along the path that takes the least time. If light moves through a medium with a varying refractive index, it "bends" toward regions where it can travel faster.

By setting the parameter $d > 1$, the estimator heavily penalizes large jumps between sparse points. To minimize the total "cost" of the path, the algorithm is forced to take many small steps through high-density regions rather than a few large steps through empty space. Mathematically, as the number of points $N$ approaches infinity, this estimator converges to a weighted geodesic distance where the underlying data density acts as the "refractive index."

Computational Feasibility

To make this computationally practical, the authors demonstrate that it is unnecessary to check every possible path in the dataset. By restricting the search to a $k$-nearest neighbor ($k$-NN) graph, the computational complexity is reduced to $O(N^2 (\log N)^2)$ without sacrificing the estimator's accuracy.

Experimental Results

The paper evaluates the $d$-distance method using synthetic datasets specifically designed to highlight the challenges of varying density. A primary example is the Non-uniform Swiss Roll, a 3D manifold where points are sampled from four distinct Gaussian clusters rather than a uniform distribution.

Data distribution and clustering performance metrics on the non-uniform Swiss Roll dataset as the parameter d varies.

Key Insights and Performance

  • Density as a Guide: Unlike standard methods that treat varying density as a nuisance, the $d$-distance uses it as a feature. High-density regions act as "highways" for the shortest path.
  • Bridge Breaking: In clustering, sparse "bridges" of noisy points often cause algorithms to mistakenly merge distinct groups. Because the $d$-distance penalizes the large jumps required to cross these low-density bridges, it effectively "cuts" them, keeping true clusters distinct.
  • Superior Clustering: When compared against Isomap and $C$-Isomap using $K$-medoids clustering on the non-uniform Swiss Roll, the $d$-distance significantly outperformed the baselines across multiple metrics, including Adjusted Mutual Information, Adjusted Rand Index, and F1 Score.
  • The Optimal Range for $d$: The experiments revealed an "optimal region" for the parameter $d$ (typically between 1.7 and 3.2) where clustering performance was both highest and most stable.

The authors also tested the metric on a "Rings" dataset—concentric circles sometimes connected by thin bridges of points—where the $d$-distance successfully recovered the clear separation between the circles even when they appeared close in standard Euclidean space.

Limitations and Future Work

While the $d$-distance offers a powerful new perspective on manifold learning, the authors note a few areas for future exploration:

  • Parameter Selection: Although the paper proves that $d > 1$ is highly beneficial, there is not yet a strict, formal rule for selecting the absolute "perfect" $d$ for any arbitrary real-world dataset.
  • Theoretical Proofs: The mathematical proof for the estimator's consistency is currently provided for cases where density is constant. While empirical simulations clearly show it works for non-constant densities, a full mathematical proof for the general varying-density case remains future work.
  • Real-world Scaling: The current experiments focus on synthetic 2D and 3D manifolds. Testing the algorithm's performance and scalability on very high-dimensional real-world data, such as images or genomics, is an exciting open area for exploration.

Summary updated

BibTeX
@inproceedings{sapienza2018weighted,
  author = {Facundo Sapienza and Pablo Groisman and Matthieu Jonckheere},
  title = {{Weighted Geodesic Distance Following Fermat's Principle}},
  booktitle = {Workshops @ ICLR},
  year = {2018},
}
Figure