Graph construction plays a vital role in improving the performance of graph-based dimension reduction (DR) algorithms. In this paper, we propose a novel graph construction method, and we name the graph constructed from such method as samples’ inner structure based graph (SISG). Instead of determining the k-nearest neighbors of each sample by calculating the Euclidean distance between vectorized sample pairs, our new method employs the newly defined sample similarities to calculate the neighbors of each sample, and the newly defined sample similarities are based on the samples’ inner structure information. The SISG not only reveals the inner structure information of the original sample matrix, but also avoids predefining the parameter k as used in the k-nearest neighbor method. In order to demonstrate the effectiveness of SISG, we apply it to an unsupervised DR algorithm, locality preserving projection (LPP). Experimental results on several benchmark face databases verify the feasibility and effectiveness of SISG.