Abstract: Graph-based semi-supervised methods define a graph where the nodes are labeled and unlabeled examples in the dataset, and edges reflect the similarity of examples. These methods usually assume label smoothness over the graph. Graph methods are nonparametric, discriminative, and transductive in nature. These methods take high classification accuracy on variant data distributions. But the computation complexity is very high. As the size of dataset grows, the graph will be too large to compute and this limits the extension of its usage. In this paper, we propose a novel method for fast computation based on local clustering, which is very efficient for reduction of graph size and can maintain the accuracy at the same time. The local clustering method is of low computation complexity and the data structure can be preserved by a newly designed distance function. Experimental results show that this approach can preserve the accuracy of purely graph-based methods and significantly reduce computational cost.