This paper introduces a graph-based semi-supervised embedding method as well as its kernelized version for generic classification and recognition tasks. The aim is to combine the merits of flexible manifold embedding and nonlinear graph-based embedding for semi-supervised learning. The proposed linear method will be flexible since it estimates a nonlinear manifold that is the closest one to a linear embedding. The proposed kernelized method will also be flexible since it estimates a kernel-based embedding that is the closest to a nonlinear manifold. In both proposed methods, the nonlinear manifold and the mapping (linear transform for the linear method and the kernel multipliers for the kernelized method) are simultaneously estimated, which overcomes the shortcomings of a cascaded estimation. The dimension of the final embedding obtained by the two proposed methods is not limited to the number of classes. They can be used by any kind of classifiers once the data are embedded into the new subspaces. Unlike nonlinear dimensionality reduction approaches, which suffer from out-of-sample problem, our proposed methods have an obvious advantage that the learnt subspace has a direct out-of-sample extension to novel samples, and are thus easily generalized to the entire high-dimensional input space. We provide extensive experiments on seven public databases in order to study the performance of the proposed methods. These experiments demonstrate much improvement over the state-of-the-art algorithms that are based on label propagation or graph-based semi-supervised embedding.