These methods work great on the examples shown in the paper, and are indeed powerful Non-Linear DImensionality reduction tools.

However, it would be interesting to see how they deal with noise -- for example, if there is a small, thin bridge connecting two adjacent layers of the swiss roll... would they go completely berserk? Or will they still be able to do something intelligent? I somehow suspect the former, specially for LLE.