We consider the clustering problem for the labeled stochastic block model (LSBM) with non-uniform class priors. We introduce a novel relaxation of the maximum a posteriory (MAP) estimator for the cluster labels and develop an algorithm for the numerical solution of this relaxation, assuming that the number of clusters, the class priors, and the label distributions are known in advance. Semi-supervised operation is enabled by allowing each node to have a distinct prior. Numerical experiments confirm that our method outperforms state-of-the-art approaches in terms of clustering accuracy.