Research map / Learning theory and algorithms / Clustering
SEC: More Accurate Clustering Algorithm via Structural Entropy
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 SEC, a non-neural clustering algorithm that builds a sparse k-NN/threshold graph, lifts data with iterative structural-entropy encoding trees, and iteratively deletes and reassigns "fringe points" during k-means-style optimization.
Problem
Clustering methods rely heavily on local neighborhood information and Euclidean distance/density, which fails on datasets with irregular or stripe-like patterns and on points lying on cluster boundaries (fringe points).
Approach
Combine a sparse graph embedding with a height-restricted encoding tree from structural entropy to append global structural features as new dimensions to the data, then run k-means++-based clustering with an iterative fringe-set deletion and reassignment step based on projective distance.
Key results
- On synthetic datasets SEC improves average ACC by 1.7% and NMI by 7.9% over the best prior method per dataset.
- On real-world UCI datasets SEC improves average ACC by 12.3% and NMI by 5.2% over the state-of-the-art baseline per the abstract; vs. k-means++ the average ACC gain is 21.9%.
- SEC achieves ACC of 1.0 on aggre and 0.972 on compound among synthetic datasets, outperforming all baselines on 8 of 9 synthetic datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SEC with global structural features and fringe-point pre-deletion/reassignment instead of the compared clustering methods | SEC · synthetic datasets | ACC: +1.7% | Helped |
| Use SEC with global structural features and fringe-point pre-deletion/reassignment instead of the compared clustering methods | SEC · synthetic datasets | NMI: +7.9% | Helped |
| Use SEC with global structural features and fringe-point pre-deletion/reassignment instead of the compared clustering methods | SEC · real-world datasets | ACC: +12.3% | Helped |
| Use SEC with global structural features and fringe-point pre-deletion/reassignment instead of the compared clustering methods | SEC · real-world datasets | NMI: +5.2% | Helped |
Surprising findings
- Structural-entropy feature lifting alone raised k-means ACC from 0.25-0.74 to 1.0 on four stripe-shaped 2D datasets without fringe sets.
Limitations
- Evaluated only on small 2D synthetic and low-dimensional UCI datasets (up to 10992 instances).
- Fringe-point deletion and reassignment is heuristic and depends on the parameter delta; the full version with ablations is referenced but not included.
Experimental setup
Datasets: square5 compound ds4c2sc8 threenorm aggre 2d-3c-no123 2d-20c-no0 s4 sizes5 iris wine glass
Benchmarks: square5 compound ds4c2sc8 threenorm aggre 2d-3c-no123 2d-20c-no0 s4 sizes5 iris wine glass
Metrics: ACC NMI
Baselines: k-means++ fuzzy k-means DBSCAN HCDC LDP-MST
Builds on: k-means++ structural entropy LDP-MST HCDC
Closest papers by meaning
- Hyperbolic Continuous Structural Entropy for Hierarchical Clustering (AAAI 2026 · similarity 0.88)
- Hierarchical Clustering Beyond the Worst-Case (NeurIPS 2017 · similarity 0.88)
- Near-Optimal $k$-Clustering in the Sliding Window Model (NeurIPS 2023 · similarity 0.87)
- Efficient Parameter-Free Clustering Using First Neighbor Relations (CVPR 2019 · similarity 0.87)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.86)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.85)
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.