Minimum Description Length based Granular-Ball Tree Regularization for Spectral Clustering

Abstract

This paper proposes Minimum Description Length based Granular-Ball Tree Regularized Spectral Clustering (MDL-GBTRSC), a fixed-K method that uses granular balls as regional descriptors for sample-level affinity construction rather than as reduced graph nodes. A reciprocal-neighborhood continuity term is incorporated into an MDL-based refinement criterion to construct a granular-ball hierarchy, and the structural scales of the terminal regions are transferred to the original sample graph before spectral partitioning. Experiments on 18 real and 20 synthetic datasets, comprising 109,969 samples in total, compare MDL-GBTRSC with nine competing methods. On the 17 real datasets completed by all methods, MDL-GBTRSC achieves mean ARI and NMI values of 0.5998 and 0.6613, compared with the next-highest means of 0.5792 and 0.6285, respectively. On the 20 synthetic datasets, it achieves mean ARI and NMI values of 0.9618 and 0.9688, compared with the next-highest means of 0.7921 and 0.8306, and is best or tied on 15 datasets for both metrics. These results indicate that MDL-selected regional structure provides useful local information for affinity construction while preserving the resolution of the original spectral graph. Source code and experimental materials are available at https://github.com/AnonymousUser0816/MDL-GBTRSC.

38 pages, 17 figures, 10 tables