In traditional graph embedding methods, graph construction is sensitive to high-dimensional data with noise and outliers, making an effective exploration of the neighborhood structure of the data difficult. Besides, with these methods, constructing graphs and reducing dimensions are disconnected and cannot be mutually optimized. To address these problems, we propose an unsupervised dimensionality reduction method based on bipartite graph, named unsupervised adaptive bipartite graph embedding (UABGE). First, the anchors are generated from the raw data by K-means or random sampling. Second, the bipartite graph, which is constructed between the samples and the anchors in the low-dimensional subspace, utilizes the adaptive allocation method to assign neighbors for each sample, so that the local structure of high-dimensional data can be captured effectively. Third, we present an objective function that combines bipartite graph construction and projection matrix learning to achieve mutual optimization between them, which can be solved with an alternating optimization algorithm. Finally, the computational complexity and the convergence of the algorithm are analyzed. Experimental results on synthetic data and publicly available datasets illustrate the effectiveness of the proposed method.

Graph embedding is a widely used method for dimensionality reduction due to its computational effectiveness. The quality of the graph and the efficiency of graph construction will directly affect the performance and the efficiency of the graph embedding methods. However, in the unsupervised graph embedding methods, the graph is not considered as an optimized graph since there is no label that can be used to construct this graph. In addition, the running of traditional graph embedding methods become very time-consuming on large-scale datasets due to the high computational cost in the step of graph construction. Aiming to solve these problems, we propose an unsupervised dimensionality reduction method based on bipartite graph, called Unsupervised Optimized Bipartite Graph Embedding (UOBGE). Representative anchors are firstly identified in the data. Then, we construct the bipartite graph between the projected samples and the projected anchors and the intrinsic graph connecting all the projected sample pairs with equal weights, which keep the local and global geometric structures of the data, respectively. Finally, the bipartite graph and the projection matrix are optimized simultaneously by introducing an alternating optimization procedure. Extensive experiments on several datasets demonstrate that the effectiveness and efficiency of the proposed method.