This letter introduces a framework for graph-based semi-supervised learning by estimating a flexible non-linear projection and its linear regression model. Unlike existing works, the proposed framework jointly estimates the graph structure, the non-linear projection, and the linear regression model. By adopting this joint estimation an overall optimality can be reached. A series of experiments are conducted on five image datasets in order to compare the proposed method with some state-of-art semi-supervised methods. This evaluation demonstrates the effectiveness of the proposed embedding method. These experiments show the superiority of the proposed framework over the joint estimation of the graph and soft labels.