Incremental Isometric Embedding of High-Dimensional Data Using Connected Neighborhood Graphs
Most nonlinear data embedding methods use bottom-up approaches for capturing the underlying structure of data distributed on a manifold in high-dimensional space. These methods often share the first step, which defines neighbor points of every data point by building a connected neighborhood graph so that all data points can be embedded into a single coordinate system. These methods are required to work incrementally for dimensionality reduction in many applications. Because the input data stream may be undersampled or skewed from time to time, building a connected neighborhood graph is crucial to the success of incremental data embedding using these methods. This paper presents algorithms for updating k-edge-connected and k-connected neighborhood graphs after a new data point is added or an old data point is deleted. It further utilizes a simple algorithm for updating all-pair shortest distances on the neighborhood graph. Together with incremental classical multidimensional scaling using iterative subspace approximation, this paper devises an incremental version of Isomap with enhancements to deal with undersampled or unevenly distributed data. Experiments on both synthetic and real-world data sets show that the algorithm is efficient and maintains low-dimensional configurations of high-dimensional data under various data distributions.
neighborhood graph dimensionality reduction isomap incremental learning manifold learning