We present a novel feature extraction algorithm for face recognition called the uncorrelated and discriminative graph embedding (UDGE) algorithm, which incorporates graph embedding and local scaling method and obtains uncorrelated discriminative vectors in the projected subspace. An optimization objective function is herein defined to make the discriminative projections preserve the intrinsic neighborhood geometry of the within-class samples while enlarging the margins of between-class samples near to the class boundaries. UDGE efficiently dispenses with a prespecified parameter which is data-dependent to balance the objective of the within-class locality and the between-class locality in comparison with the linear extension of graph embedding in a face recognition scenario. Moreover, it can address the small sample-size problem, and its classification accuracy is not sensitive to neighbor samples size and weight value, as well. Extensive experiments on extended YaleB, CMU PIE, and Indian face databases demonstrate the effectiveness of UDGE.