Riemannian manifold has attracted an increasing amount of attention for visual classification tasks, especially for video or image set classification. Covariance matrices are the natural second-order statistics of image sets. However, nonsingular covariance matrices, known as symmetric positive defined (SPD) matrices, lie on the non-Euclidean Riemannian manifold (SPD manifold). Covariance discriminative learning (CDL) is an effective discriminative learning method that employs the Riemannian manifold in the SPD kernel space. However, in practice, the discriminative learning of CDL often suffers from the problems of poor generalization and overfitting caused by a finite number of training samples and noise corruption. Hence, we propose to address these problems by importing eigenspectrum regularization and graph-embedded frameworks. Discriminative learning with SPD manifold is generalized by the graph-embedded framework, which combines with eigenspectrum regularization in the SPD kernel space. Three local Laplacian graphs of graph-embedded framework and two eigenspectrum regularized models are incorporated to the proposed method. Comprehensive mathematical deduction of the proposed method is depicted with the “kernel tricks.” Experimental results on set-based face recognition and object categorization tasks reveal the effectiveness of the proposed method.