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

• URL: http://arxiv.org/abs/2605.22410v1
• Date: Thu, 21 May 2026 12:36:24 GMT
• Title: Minimum Description Length based Granular-Ball Tree Regularization for Spectral Clustering
• Abstract summary: This paper proposes a Minimum Description Length based Granular-Ball Tree-Regularized Spectral Clustering method.<n>The proposed method constructs a granular-ball tree through local MDL model selection, with reciprocal neighborhood continuity used to discourage splits that break reliable local connections.<n> Experiments on real and synthetic datasets show that MDL-GBTRSC achieves the best average ARI and NMI under the adopted fixed-configuration protocol.
• Score: 5.432653808002268
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spectral clustering largely depends on the affinity graph, yet constructing a graph that preserves reliable local connectivity while adapting to heterogeneous data structures remains challenging. Existing granular-ball-based spectral clustering methods usually reduce graph complexity by using coarse-grained representatives. However, the learned local regions are often treated as graph nodes or anchors, and their structural information is not sufficiently used to regularize the original sample-level graph. To address this issue, this paper proposes a Minimum Description Length based Granular-Ball Tree-Regularized Spectral Clustering method, termed MDL-GBTRSC. The proposed method constructs a granular-ball tree through local MDL model selection, with reciprocal neighborhood continuity used to discourage splits that break reliable local connections. The stable leaf balls obtained from the tree provide coding-scale information for regularizing the sample-level affinity graph. In addition, a shared-neighbor bridge code is introduced to adjust weak local bridge relations without requiring an additional user-specified threshold. In this way, MDL-GBTRSC connects interpretable local representation learning with affinity graph construction in a unified spectral clustering framework. Experiments on real and synthetic datasets show that MDL-GBTRSC achieves the best average ARI and NMI under the adopted fixed-configuration protocol compared with classical spectral clustering baselines and representative granular-ball, micro-cluster, and anchor-based methods.

Related papers

• CuBAS: Information Geometric Curvature-Based Adaptive Sampling for Supervised Classification [52.452902154360565]
  CuBAS is an information-geometric framework for adaptive data selection in supervised classification.<n>A labeled dataset can be viewed as a statistical manifold, on which local curvature, estimated via the ratio of second to first-order observed Fisher information, faithfully encodes the geometric complexity of the data distribution.
  arXiv  Detail & Related papers  (2026-07-03T09:36:02Z)
• Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression [55.51959317490934]
  Large language models (LLMs) have demonstrated promising capabilities in Text-Attributed Graph (TAG) understanding.<n>We argue that graphs inherently contain rich structural and semantic information, and that their effective exploitation can unlock potential gains in LLMs reasoning performance.<n>We propose Homophily-aware Structural and Semantic Compression for LLMs (HS2C), a framework centered on exploiting graph homophily.
  arXiv  Detail & Related papers  (2026-01-13T03:35:18Z)
• Scalable Context-Preserving Model-Aware Deep Clustering for Hyperspectral Images [51.95768218975529]
  Subspace clustering has become widely adopted for the unsupervised analysis of hyperspectral images (HSIs)<n>Recent model-aware deep subspace clustering methods often use a two-stage framework, involving the calculation of a self-representation matrix with complexity of O(n2), followed by spectral clustering.<n>We propose a scalable, context-preserving deep clustering method based on basis representation, which jointly captures local and non-local structures for efficient HSI clustering.
  arXiv  Detail & Related papers  (2025-06-12T16:43:09Z)
• Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods [3.7936990167037723]
  Local clustering aims to identify specific substructures within a large graph without any additional structural information of the graph.<n>We first propose a method for identifying specific local clusters when very few labeled data are given, which we term semi-supervised local clustering.<n>We then extend this approach to the unsupervised setting when no prior information on labels is available.
  arXiv  Detail & Related papers  (2025-04-28T02:10:18Z)
• IsoSEL: Isometric Structural Entropy Learning for Deep Graph Clustering in Hyperbolic Space [57.036143666293334]
  Graph clustering is a longstanding topic in machine learning.<n>In this paper, we study a challenging yet practical problem: deep graph clustering without K considering the imbalance in reality.<n>We present a novel IsoSEL framework for deep graph clustering, where we design a hyperbolic neural network to learn partitioning tree in the Lorentz model of hyperbolic space.
  arXiv  Detail & Related papers  (2025-04-14T08:21:41Z)
• Locally Regularized Sparse Graph by Fast Proximal Gradient Descent [6.882546996728011]
  We propose a novel Regularized Sparse Graph abbreviated SRSG. Sparse graphs have been shown to be effective in clustering high-dimensional data. We show that SRSG is superior to other clustering methods.
  arXiv  Detail & Related papers  (2024-09-25T16:57:47Z)
• Clustering by Mining Density Distributions and Splitting Manifold Structure [2.3759432635713895]
  A top-down approach was recently proposed to improve the efficiency of spectral clustering.<n>This paper proposes to start from local structures to obtain micro-clusters.<n>A novel similarity measure between micro-clusters is then proposed for the final spectral clustering.
  arXiv  Detail & Related papers  (2024-08-20T02:22:59Z)
• MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion [0.6906005491572401]
  spectral clustering is popular and attractive due to the remarkable performance, easy implementation, and strong adaptability. We propose MeanCut as the objective function and greedily optimize it in degree descending order for a nondestructive graph partition. The validity of our algorithm is demonstrated by testifying on real-world benchmarks and application of face recognition.
  arXiv  Detail & Related papers  (2023-12-07T06:19:39Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
  arXiv  Detail & Related papers  (2020-04-25T17:52:05Z)
• Robust spectral clustering using LASSO regularization [0.0]
  This paper presents a variant of spectral clustering, called 1-spectral clustering, performed on a new random model closely related to block model. Its goal is to promote a sparse eigenbasis solution of a 1 minimization problem revealing the natural structure of the graph.
  arXiv  Detail & Related papers  (2020-04-08T07:12:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.