In this paper, we first investigate the nonnegative block value decomposition (NBVD) approach through graph-based representation for clustering called G-NBVD. Then, we propose our three-step graph and sparse-based robust NBVD (GSR-NBVD) via robust NBVD (R-NBVD) framework. The robustness to outliers is obtained by converting the Frobenius norm of error function to the ℓ _2,1 -norm for NBVD structure that compensates the effect of samples that are not conforming to NBVD. To exploit the connection between the learning matrix and its corresponding coefficients through sparse representation, we enforce the sparse constraints on the middle matrix in the R-NBVD framework called SR-NBVD. To enhance the geometrical information from data space to the new space, we add a term to our objective minimization function through a regularized graph representation compact form called GSR-NBVD. Then, we prove the convergence of our proposed methods and show a visualization of the effectiveness of G-NBVD and GSR-NBVD step-by-step. Finally, we evaluate our proposed clustering methods over different kinds of data sets. The experimental results confirm that our methods outperforms several state-of-the-art methods through different metrics.