Graph embedding techniques attempt to construct a high locality projection in such a way that projected same class samples should be close to each other. However, estimation of population data locality could be severely biased due to limited number of training samples. This biased estimation could trigger overfitting problem, leading to poor generalization. In this paper, we propose three new dimensionality reduction techniques. Projection features are regularized by utilizing a local Laplacian matrix to better approach true data locality for higher locality preserving. These techniques are developed based on the manipulation of locality regularization. The difference between them would be the adoption of different local Laplacian matrices. In view of this, a common name is given, which is Locality Regularization Graph Embedding (denoted as LRGE). The robustness of these techniques is tested on CMU PIE and FERET databases. Experimental results validate the effectiveness of these techniques in face verification