ReConcept Lab
English 中文
Graph connections

Draft

Isomap

Preserve distances along a neighbor graph so a curved manifold can be unfolded into a low-dimensional map.

algorithm intermediate machine-learningdimensionality-reductionmanifold-learning

Hook problem: straight lines can cut through the fold

Imagine points lying on a curled sheet. Two points may be close through the air but far apart if you have to walk along the sheet.

Raw MDS uses straight distances, so it can flatten the wrong neighbors together. Isomap repairs that by measuring distance along a neighbor graph.

Walk along the surfaceIsomap replaces straight-line shortcuts with shortest paths on a neighbor graph.
Straight shortcutA1 -> B3

too eager on a curved surface

Neighbor walkA1 -> A2 -> A3 -> B1 -> B2 -> B3

approximates geodesic distance

Repair

Run MDS on graph shortest paths, not raw straight-line distances.

First naive idea: run MDS on Euclidean distances

That works when the structure is already flat. It becomes painful when the important geometry is curved, because Euclidean distance takes shortcuts through empty space.

Core invention: local graph first, layout second

Isomap has three moves:

  1. connect each point to nearby neighbors;
  2. compute graph shortest-path distances, written $D_{geo}(i,j)$;
  3. run MDS on that geodesic distance table.
Y=MDS(Dgeo)Y = MDS(D_{geo})

The neighbor graph is the bet: local distances are trustworthy, and long distances should be assembled from local walks.

Trace lab

IsomapUse neighbor-graph shortest paths before applying an MDS-style layout.
Step 1/3: Connect local neighbors

Euclidean shortcuts can cut through a curved manifold, so Isomap first builds a neighbor graph.

Working formulak-nearest-neighbor graph

local edges only

Implementation sketch

build a k-nearest-neighbor graph;
weight each edge by local distance;
run all-pairs shortest paths on the graph;
apply MDS to the graph-distance matrix;

Common confusions

  • Isomap is sensitive to the neighbor parameter.
  • Disconnected neighbor graphs break the shortest-path table.
  • It preserves manifold distance, not arbitrary class separation.
Dimensionality reduction pathLinear projections, distance-preserving maps, supervised discriminants, and neighbor embeddings solve different pains.
PCA

Keep the directions where centered data varies most.

MDS

Place points so low-dimensional distances imitate the original distance table.

Isomap

Use neighbor-graph shortest paths before applying an MDS-style layout.

LDA

Use labels to find projections that separate class means while keeping classes tight.

QDA

Let each class keep its own covariance, creating quadratic boundaries rather than one shared projection.

SNE

Match neighbor probabilities between high and low dimensions.

t-SNE

Repair SNE's crowding problem with a heavy-tailed low-dimensional similarity.

UMAP

Build a fuzzy neighbor graph, then optimize a low-dimensional graph with similar membership strengths.

Exercises

  1. Why does Isomap not trust long straight-line distances?
  2. What happens if the neighbor graph is disconnected?
  3. Which part of Isomap is inherited from MDS?

Graph connections : Isomap