Manifold Aware Similarity via Graph Shortest Paths

This direction is split into other directions: geodesic distance preservation. Its last version stays readable and citable here.

Version 1 of 1181 papers227 conceptsfrozen 2026-10-04

In high-dimensional machine learning, we often rely on Euclidean distance or cosine similarity to tell us how "close" two data points are. However, these metrics assume that data is distributed uniformly across a flat space. In reality, complex data—like natural images, human poses, or semantic embeddings—usually resides on a manifold: a curved, lower-dimensional surface embedded within the high-dimensional space.

When data lies on a manifold, straight-line Euclidean distance becomes a poor proxy for similarity. It creates "shortcuts" through empty regions of the space where no valid data exists. To truly understand the relationship between two points, we must measure the distance along the surface of the data. This is known as the geodesic distance.

The Intuition: The Shortcut Problem

Imagine two points on a "Swiss Roll" manifold. In 3D Euclidean space, they might appear very close because they are physically near each other across a gap. However, to travel from one to the other while staying on the fabric of the roll, you would have to travel a long distance.

As Ali Ghodsi and colleagues explain in Multidimensional Scaling, Sammon Mapping, and Isomap: Tutorial and Survey, capturing this intrinsic geometry is the key to "unrolling" the manifold. By replacing straight-line distances with geodesic ones, we can transform a non-linear, tangled distribution into a linear, interpretable one.

Building the Geodesic Bridge

Since we rarely have a mathematical formula for the manifold's surface, we must approximate it using the data points we have. The standard mechanism across this research direction involves three steps:

  1. Construct a Neighborhood Graph: Connect each data point to its $k$-nearest neighbors. This graph serves as a "skeleton" of the manifold.
  2. Assign Local Weights: Weight the edges of the graph using local Euclidean distances. Over very small distances, the curvature of the manifold is negligible, so Euclidean distance is a safe approximation.
  3. Find the Shortest Path: To find the distance between two distant points, calculate the shortest path through the graph (typically using Dijkstra’s algorithm).

This shortest-path distance serves as an estimate of the geodesic. Xuxin Cheng and the team at Peking University used this in CCLG to improve cross-lingual understanding, arguing that geodesic distances capture semantic relatedness far more accurately than linear metrics.

Why It Works: Connectivity as Semantic Signal

The power of this approach lies in its ability to leverage unlabeled data to "fill the gaps." In Using Text to Teach Image Retrieval, Haoyu Dong and Qiang Qiu demonstrate that by adding text samples into an image embedding space, they can create a denser graph. This density makes the shortest-path calculations more robust, effectively "teaching" the model the shape of the visual manifold using linguistic cues.

Similarly, in Label Propagation for Zero-shot Classification with Vision-Language Models, researchers show that a model can correctly classify an image that is "far" from a text prompt by traversing a chain of intermediate image-to-image similarities. The manifold acts as a bridge, allowing information to flow between samples that appear unrelated in a raw Euclidean sense.

Beyond Simple Graphs: Diffusion and Fields

While $k$-NN graphs are the most common tool, recent work has introduced more sophisticated ways to measure manifold distance:

  • Diffusion Distances: Alexander Tong and Amine Natik introduced Diffusion Earth Mover's Distance, which uses graph-based diffusion to compare distributions. This is more robust to noise than simple shortest paths because it considers all possible paths between points, not just the single shortest one.
  • Neural Distance Fields: In Pose-NDF, Garvita Tiwari and colleagues model the manifold of human poses as a continuous "distance field." Instead of a discrete graph, they learn a function that outputs the distance from any arbitrary point to the nearest valid pose on the manifold.
  • Density-Weighted Paths: Some methods, like those discussed by Frédéric Chazal in his work on Fermat distance, weight the paths by the local density of data. This forces the "geodesic" to stay within high-confidence regions of the data distribution, effectively ignoring outliers.

Applications Across Domains

The shift from Euclidean to manifold-aware distance has proven transformative in diverse fields:

  • Summarization: Somnath Basu Roy Chowdhury developed GeoSumm, which uses geodesics on a sentence manifold to find the most "representative" opinions in a sea of reviews.
  • Explainability: Minh N. Vu used manifold-based perturbations in EMaP to ensure that AI explanations are based on realistic data variations rather than impossible "off-manifold" noise.
  • Neuroscience: Researchers like Sabine Oligschläger use geodesic distances along the folded surface of the cerebral cortex to map brain connectivity, acknowledging that biological "wiring costs" follow the manifold of the brain's physical shape.

By respecting the intrinsic geometry of data, these methods move us away from the "flat earth" assumption of standard vector spaces and toward a more nuanced, topologically faithful understanding of machine learning representations.

Papers in this version

Showing 60 of 181 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_manifold_aware_similarity_via_graph_shor_84d44648,
  title = {Manifold Aware Similarity via Graph Shortest Paths},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/manifold-aware-similarity-via-graph-shortest-paths/rdr_84d44648e0da41a58383d1c66a4a837c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_manifold_aware_similarity_via_graph_shor_84d44648_v1,
  title = {Manifold Aware Similarity via Graph Shortest Paths},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/manifold-aware-similarity-via-graph-shortest-paths/rdr_84d44648e0da41a58383d1c66a4a837c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}