Evaluation of the Sample Clustering Process on Graphs

An increasing number of networks are becoming large-scale and continuously growing in nature, such that clustering on them in their entirety could be intractable. A feasible way to overcome this problem is to sample a representative subgraph and exploit its clustering structure (namely, sample clustering process). However, there are two issues that we should address in current studies. One underlying question is how to evaluate the clustering quality of the entire sample clustering process. Another non-trivial issue is that multiple ground-truths exist in networks, thus evaluating the clustering results in such scenario is also a challenging task. In this paper, first we utilize the set-matching methodology to quantitatively evaluate how differently the clusters of the sampled counterpart correspond to the ground-truth(s) in the original graph, and propose several new quality metrics to capture the differences of clustering structure in various aspects. Second, we put forward an evaluation framework for the general problems of evaluating the clustering quality on graph samples. Extensive experiments on various synthetic and real-world graphs demonstrate that our new quality metrics are more accurate and insightful for the sample clustering evaluation than conventional metrics (e.g., NMI). Thus the evaluation framework is effective and practical to assess the clustering quality of the sample clustering process on massive graphs.