Using Graph Algebra to Optimize Neighborhood for Isometric Mapping

Guihua Wen, Lijun Jiang ,Nigel R Shadbolt

Most nonlinear dimensionality reduction approaches such as Isomap heavily depend on the neighborhood structure of manifold. They determine the neighborhood graph using Euclidean distance so that they often fail to nicely deal with sparsely sampled or noise contaminated data. This paper applies the graph algebra to optimize the neighborhood structure for Isomap. The improved Isomap outperforms the classic Isomap in visualization and time complexity, as it provides good neighborhood structure that can speed up the subsequent dimensionality reducing process. It also has stronger topological stability and less sensitive to parameters. This indicates that the more complicated or even time-consuming approaches can be applied to construct the better neighborhood structure whilst the whole time complexity will not raise .The conducted experiments on benchmark data sets have validated the proposed approach.