Summary: We explore the problem of robust visual representation and enhanced label prediction. Technically, a Discriminative Sparse Flexible Manifold Embedding (SparseFME) method with novel graph is proposed. SparseFME enhances the representation and label prediction powers of FME by improving the reliability and robustness of distance metric, such as using the \(l_{2,1}\)-norm to measure the flexible regression residue encoding the mismatch between embedded features and the soft labels, and regularizing the \(l_{2,1}\)-norm on the soft labels directly to boost the discriminating power so that less unfavorable mixed signs that may result in negative effects on performance are included. Besides, our SparseFME replaces the noise-sensitive Frobenius norm used in FME by \(l_{2,1}\)-norm to encode the projection that maps data into soft labels, so the projection can be ensured to be sparse in rows so that discriminative soft labels can be learnt in the latent subspace. Thus, more accurate identification of hard labels can be obtained. To obtain high inter-class separation and high intra-class compactness of the predicted soft labels, and encode the neighborhood of each sample more accurately, we also propose a novel graph weight construction method by integrating class information and considering a certain kind of similarity/dissimilarity of samples so that the true neighborhoods can be discovered. The theoretical convergence analysis and connection to other models are also presented. State-of-art performances are delivered by our SparseFME compared with several related criteria.