Research map / Learning theory and algorithms / Clustering
Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees
Solveig Klepper, Christian Elbracht, Diego Fioravanti, Jakob Kneip, Luca Rendsburg, Maximilian Teegen, Ulrike von Luxburg
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| raise agreement parameter from 1/3 to 2/3 of smallest cluster size (ablation) | Tangles · Binary questionnaire, unbalanced clusters | NMI | Improved |
| prune tangle search tree paths of length 1 (ablation) | Tangles · Binary questionnaire with useless questions | NMI | Improved |
| add useless random questions | Tangles · Binary questionnaire (noise 0.15) | NMI | No clear effect |
| increase initial cuts from 20 (2 KL iterations) to 100 (100 iterations) (ablation) | Tangles · Synthetic SBM graph clustering | NMI: 20 -> 100 | No clear effect |
| increase the number of cuts (ablation) | Tangles · Synthetic SBM graph clustering | NMI | Improved |
| use tangles instead of k-means with known k as noise grows | k-means · Binary questionnaire, unbalanced clusters | NMI | Mixed |
| use tangles instead of normalized spectral clustering | Spectral clustering · Synthetic SBM graph clustering | NMI | No clear effect |
| use tangles instead of k-means | k-means · Mixture of 4 Gaussians | NMI: 0.797 -> 0.829 | Improved |
| use tangles instead of spectral clustering | Spectral clustering · Mixture of 4 Gaussians | NMI: 0.805 -> 0.829 | Improved |
Closest papers by meaning
- Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs (NeurIPS 2021 · similarity 0.87)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.86)
- Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach (NeurIPS 2025 · similarity 0.85)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.85)
- Online Sparsification of Bipartite-Like Clusters in Graphs (ICML 2025 · similarity 0.85)
- Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges (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.
