Research map / Learning theory and algorithms / Clustering
Clustering by Mining Density Distributions and Splitting Manifold Structure
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MDMSC, which builds density-based pseudo-clusters from local k-NN leader structures, splits them using a manifold-curvature criterion, and runs spectral clustering on the resulting micro-clusters for scalable clustering.
Problem
Spectral clustering is O(n^3) and granular-ball based acceleration (GBSC) degrades on unevenly distributed or structurally complex, non-convex data.
Approach
Replace granular-balls with density-peak-style pseudo-clusters (connected components of a leader graph), split them only when manifold curvature (MST path distance over endpoint Euclidean distance) is high and compactness improves, then build a shared-nearest-neighbor and centroid-distance similarity between pseudo-clusters for spectral clustering.
Key results
- MDMSC achieves best ARI on 10 of 13 UCI datasets listed in the main table, e.g., ARI 96.53 on Kdd9 versus 86.08 for the next best method.
- On pengleukEW MDMSC reaches ARI 35.85 and ACC 80.56, outperforming GBSC (2.96 ARI) and most baselines.
- Friedman test on ACC gives statistic 49.37 (P=2.10e-08); Nemenyi CD=2.10 is used for pairwise significance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use density-based local pseudo-clusters rather than the whole dataset as the initial pseudo-cluster (ablation) | MDMSC · mfea-fac, Kdd9, balance-scale, pengleukEW, optical_test, semeionEW, vote | ARI: 71.28 -> 86.28; 84.93 -> 96.53; 14.40 -> 24.60; 29.61 -> 35.85; 63.56 -> 84.08; 34.90 -> 52.62; 54.34 -> 57.10 | Helped |
| Split pseudo-clusters using manifold curvature and compactness (ablation) | MDMSC · mfea-fac, Kdd9, balance-scale, pengleukEW, optical_test, semeionEW, vote | ARI: 71.72 -> 86.28; 84.93 -> 96.53; 19.61 -> 24.60; -5.84 -> 35.85; 78.11 -> 84.08; 46.57 -> 52.62; 53.00 -> 57.10 | Mixed |
| Use manifold curvature as well as compactness to split pseudo-clusters, instead of compactness alone (ablation) | MDMSC · mfea-fac, Kdd9, balance-scale, pengleukEW, optical_test, semeionEW, vote | ARI: 84.40 -> 86.28; 96.53 -> 96.53; 22.46 -> 24.60; 23.79 -> 35.85; 81.53 -> 84.08; 48.12 -> 52.62; 53.00 -> 57.10 | Mixed |
| Replace GBSC with MDMSC | MDMSC versus GBSC · Real-world datasets, ARI | ARI | Helped |
Surprising findings
- GBSC achieves near-zero or negative ARI on several datasets (e.g., -3.08 on car, -0.83 on vote), far below the proposed method.
Limitations
- Hyperparameters (k, beta) are searched per dataset, and the method's sensitivity to k is noticeable for small k.
- Experiments run on a modest GPU and laptop CPU; scalability to ultra-large datasets is not demonstrated.
- Performance is not best on all datasets (e.g., landsatEW, soybean_test, car NMI).
Experimental setup
Datasets: Aggregation Spiral Jain db2 border mfea-fac Kdd9 landsatEW balance-scale pengleukEW Pendigits energy-y2
Benchmarks: Aggregation Spiral Jain db2 border mfea-fac Kdd9 landsatEW balance-scale pengleukEW Pendigits energy-y2
Metrics: ARI NMI ACC
Baselines: GBSC GB-DP LDP-MST U-SPEC spectral clustering DPC DEMOS DPC-DBFN
Builds on: granular-ball computing (GBSC) density peaks clustering (DPC) spectral clustering U-SPEC
Closest papers by meaning
- A Tighter Analysis of Spectral Clustering, and Beyond (ICML 2022 · similarity 0.87)
- Local and Global Optimization Techniques in Graph-Based Clustering (CVPR 2018 · similarity 0.87)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.86)
- Graph Clustering Methods Derived from Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.85)
- Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.84)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.