Since computational complexities of the existing methods such as classic GN algorithm are too costly to cluster large-scale graphs

this paper studies sampling algorithms of large-scale graphs

and proposes a clustering-structure representative sampling (CRS) which can effectively maintain the clustering structure of original graphs. It can produce high quality clustering-representative nodes in samples and expand according to the corresponding expansion criteria. Then

we propose a fast population clustering inference (PCI) method on the original graphs and deduce clustering assignments of the population using the clustering labels of the sampled subgraph. Experiment results show that in comparison with state-of-the-art methods

the proposed algorithm achieves better efficiency as well as clustering accuracy on large-scale graphs.