Nonlinear Dimensionality Reduction for Data with Disconnected Neighborhood Graph

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

6 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)697-716
Journal / PublicationNeural Processing Letters
Issue number2
Online published3 Aug 2017
Publication statusPublished - Apr 2018


Neighborhood graph based nonlinear dimensionality reduction algorithms, such as Isomap and LLE, perform well under an assumption that the neighborhood graph is connected. However, for datasets consisting of multiple clusters or lying on multiple manifolds, the neighborhood graphs are often disconnected, or in other words, have multiple connected components. Neighborhood graph based dimensionality reduction techniques cannot recognize both the local and global properties of such datasets. In this paper, a new method, called enhanced neighborhood graph, is proposed to solve the problem. The concept is to add edges to the neighborhood graph adaptively and iteratively until it becomes connected. Nonlinear dimensionality reduction can then be performed based on the enhanced neighborhood graph. As a result, both local and global properties of the data can be exactly recognized. In this study, thorough simulations on synthetic datasets and natural datasets are conducted. The experimental results corroborate that the proposed method provides significant improvements on dimensionality reduction for data with disconnected neighborhood graph.

Research Area(s)

  • Disconnected graph, Enhanced neighborhood graph, Isomap, LLE, Multiple manifolds, Nonlinear dimensionality reduction

Bibliographic Note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).