## 1 Introduction  
Many real-world pattern classification and data mining applications are often confronted with a typical problem that is lacking of sufficient labeled data, since labeling samples usually requires domain-specific experts [1, 2]. Supervised classifiers, trained only on such scarcely labeled samples, often can not have a good generalization ability. With the development of high-throughput techniques, a large number of unlabeled data can be easily accumulated. If we take these labeled samples as unlabeled ones and train unsupervised learners (_i.e._, clustering) on all the unlabeled samples, the valuable information in labeledsamples is wasted. That is because the label information should be regarded as prior information, which can be used to boost the performance of a classifier [3]. Therefore, it is important to develop techniques that leverage both labeled and unlabeled samples. Semi-supervised learning aims to leverage labeled and unlabeled samples to achieve a learner with good generalization ability [1]. In this paper, we focus on semi-supervised classification, and more specifically on graph-based semi-supervised classification (GSSC). In GSSC, labeled and unlabeled samples are taken as nodes (or vertices) of a weighted graph, and the edge weights reflect the similarity between samples [1]. Various effective GSSC methods have been proposed in the last decade. To name a few, [PERSON] _et al._[4] utilized Gaussian fields and harmonic functions (GFHF) on a \(k\) nearest neighborhood (\(k\)NN) graph to predict the labels of unlabeled samples via label propagation on the graph. [PERSON] _et al._[5] studied a learning with local and global consistence (LGC) approach on a completely connected graph based on the consistency assumption. These two methods can be regarded as label propagation on a graph under different assumptions or schemes [1]. Most GSSC methods focus on how to leverage labeled and unlabeled samples but pay little attention to construct a well-structure graph that faithfully reflects the distribution of samples. For low dimensional samples, these GSSC methods can achieve good performance by using a simple \(k\)NN graph. When dealing with high dimensional instances, their performance often drops sharply, since the noisy and redundant features of high dimensional samples destroy the underlying distance (or similarity) between samples [3,6]. Recently, researchers recognized the importance of graph in GSSC and proposed various graph optimization based semi-supervised classification methods [1,7, 8, 9, 10]. [PERSON] [1] gave a comprehensive literature review on semi-supervised learning. Here, we just name a few most related and representative methods, which will be used for experimental comparison. [PERSON] _et al._[11] used an \(l_{2}\) graph [12], optimized by minimizing the \(l_{2}\)-norm regularized reconstruction error of locally linear embedding [13], and studied a linear neighborhood propagation (LNP) approach. [PERSON] _et al._[7] took advantage of iterative nonparametric matrix learning to construct a symmetric adjacent graph and proposed a robust multi-class graph transductive (RMGT) classification method. In addition, [PERSON] _et al._[9] constructed an \(l_{1}\) graph by the coefficients of \(l_{1}\)-norm regularized sparse representation [14] to perform semi-supervised classification. [PERSON] _et al._[10] suggested a compact graph based semi-supervised learning (CGSSL) method for image annotation. This method constructs a compact \(l_{2}\) graph by utilizing not only the neighborhood samples of a sample, but also the neighborhood samples of its reciprocal neighbors. However, the effectiveness of these methods is not as good as expected when dealing with high dimensional data, since high dimensional data have a lot of noisy and redundant features, and it is difficult to optimize a graph distorted by these noisy features [2,15].