Last week I recurrent the paper: Ranking on Data Manifold.
I created these 2-moon shape data randomly and added some noise on it. The left plot has 50 random 2-moon shape nodes, while the right one has 100 (the following plots correspond to these two).
Then as the paper said, "Sort the pairwise distances among points in ascending order. Repeat connecting the two points with an edge according the order until a connected graph is obtained."
But the time complexity is n cube, which is terrible. Dr. Pless and Hone both suggest me use the MST to improve the time complexity. The method is to find an MST of the graph, and connect all the edges that are shorter than the longest edge of the MST. Then we can get a graph the same as before, and the time complexity has been extremely refined to ElgV, which is pretty good.
Then I did the Manifold Ranking algorithm to this graph to query one point, and we can get a beautiful plot which is different from the weight we get from Euclidean distance.
I will upload the code after I complete the improvement to my code structure and comment, for anyone who would like to use manifold ranking in their work.
Hong had given me his data onto 8k images which have 64 dimensions. I think my next step is to find whether the manifold ranking will work well on high-dimension space.