ISOMAP algorithm for Nonlinear Dimensionality Reduction

By | June 3, 2023

Step 2 – Compute Geodesic Distances

In Step 2, we compute the shortest path between all pairs of points (i.e., the geodesic distances) using the neighborhood graph created in Step 1. This is known as the all-pairs shortest path problem.

In our graph, each point is connected to its neighbors by edges, and each edge has a weight equal to the Euclidean distance between the points it connects (as per our “weight_matrix”). The shortest path between two points is the path that connects them with the smallest total weight.

For this step, we commonly use an algorithm called Floyd-Warshall algorithm, which iteratively improves an estimate of the shortest path distances. This algorithm works well for this task since it’s designed for graphs with positive weights and can handle the “infinity” weights we assigned to pairs of points that aren’t neighbors.

Let’s illustrate the idea behind the Floyd-Warshall algorithm with a smaller version of our example:

We have 3 data points (nodes): A, B, C. Assume the following Euclidean distances (weights) from Step 1:

dist_matrix = [[0, 1, inf],
               [1, 0, 1],
               [inf, 1, 0]]

The matrix represents the distances: dist(A, B) = 1, dist(B, C) = 1, and A and C aren’t neighbors, so dist(A, C) = inf.

Now, we apply the Floyd-Warshall algorithm, which works as follows:

  1. Initialize the shortest-path distance matrix, shortest_path_matrix, to be equal to the weight matrix, weight_matrix.
  2. For each node k, update shortest_path_matrix[i, j] to be the minimum of shortest_path_matrix[i, j] and shortest_path_matrix[i, k] + shortest_path_matrix[k, j] for all pairs of nodes i and j. This checks if going from i to j via k is shorter than the current shortest path from i to j.

In matrix notation, the update rule is:

shortest_path_matrix = min(shortest_path_matrix, shortest_path_matrix[i, k] + shortest_path_matrix[k, j])

Using this rule, the algorithm computes the shortest path between all pairs of nodes.

Applying this to our 3-node graph:

After initializing with dist_matrix, we get:

shortest_path_matrix = [[0, 1, inf],
                        [1, 0, 1],
                        [inf, 1, 0]]

Next, for node A (k=1), we find no shorter path via A, so the matrix remains unchanged.

For node B (k=2), we find that we can reach C from A via B with a cost of 2 (1+1), which is less than the current cost of ‘inf’. Thus, we update shortest_path_matrix[1, 3] and shortest_path_matrix[3, 1] to 2:

shortest_path_matrix = [[0, 1, 2],
                        [1, 0, 1],
                        [2, 1, 0]]

Finally, for node C (k=3), we don’t find any shorter path via C, so the matrix stays the same. Thus, shortest_path_matrix now represents the shortest-path (geodesic) distances between all pairs of nodes.

The interpretation of this is that we can use the paths in the neighborhood graph to “get around” the limitation that we only directly connected each point to its neighbors in Step 1. By taking paths through the graph, we can compute

the distances between all pairs of points as if we had directly connected them all in the first place, which allows us to capture the underlying manifold structure of the data.

Leave a Reply

Your email address will not be published. Required fields are marked *