How to design a reasonable classification method to identify the states is a critical step in rolling bearing fault diagnosis. Along with labeled samples, the Laplacian regularization (LapR) classification method, a graph-based semi-supervised learning algorithm, can also exploit the wealth of numerous cheap unlabeled samples to obtain acceptable performance. Based on the LapR classification method, a novel fault diagnosis method of rolling bearing is put forward. First, the vibration datasets or feature datasets are constructed into an undirected and weighted K-nearest neighbor graph, which can fully reflect the similarity between dataset elements. Then, the labels of all the dataset elements are interpreted as graph signals which are indexed by the represented graph's vertices. Finally, when the constraint given by the known dataset elements is satisfied, the labels of the unknown dataset elements can be determined by finding a graph signal with minimal total variation. Experimental results reveal that whether the vibration datasets or feature datasets are analyzed, the LapR classification method is obviously superior to the popularly known classification methods in identifying the rolling bearing states especially when there are very few known samples. (C) 2021 Elsevier B.V. All rights reserved.