A graph optimization method for dimensionality reduction with pairwise constraints

Graph is at the heart of many dimensionality reduction (DR) methods. Despite its importance, how to establish a high-quality graph is currently a pursued problem. Recently, a new DR algorithm called graph-optimized locality preserving projections (GoLPP) was proposed to perform graph construction with DR simultaneously in a unified objective function, resulting in an automatically optimized graph rather than pre-specified one as involved in typical LPP. However, GoLPP is unsupervised and can not naturally incorporate supervised information due to a strong sum-to-one constraint of weights of graph in its model. To address this problem, in this paper we give an improved GoLPP model by relaxing the constraint, and then develop a semi-supervised GoLPP (S-GoLPP) algorithm by incorporating pairwise constraint information into its modeling. Interestingly, we obtain a semi-supervised closed-form graph-updating formulation with natural possibility explanation. The feasibility and effectiveness of the proposed method is verified on several publicly available UCI and face data sets.