Graph-based semi-supervised learning (SSL), which performs well in hyperspectral image classification with a small amount of labeled samples, has drawn a lot of attention in the past few years. The key step of graph-based SSL is to construct a good graph to represent original data structures. Among the existing graph construction methods, sparse representation (SR) based methods have shown impressive performance on graph-based SSL. However, most SR based methods fail to take into consideration the class structure of data. In SSL, we can obtain a probabilistic class structure, which implies the probabilistic relationship between each sample and each class, of the whole data by utilizing a small amount of labeled samples. Such class structure information can help SR model to yield a more discriminative coefficients, which motivates us to exploit this class structure information in order to learn a discriminative graph. In this paper, we present a discriminative graph construction method called probabilistic class structure regularized sparse representation (PCSSR) approach, by incorporating the class structure information into the SR model, PCSSR can learn a discriminative graph from the data. A class structure regularization is developed to make use of the probabilistic class structure, and therefore to improve the discriminability of the graph. We formulate our problem as a constrained sparsity minimization problem and solve it by the alternating direction method with adaptive penalty (ADMAP). The experimental results on Hyperion and AVIRIS hyperspectral data show that our method outperforms state of the art. (C) 2016 Elsevier Ltd. All rights reserved.