Research map / Learning theory and algorithms / Clustering
Near-Optimal Comparison Based Clustering
Michaël Perrot, Pascal Esser, Debarghya Ghoshdastidar
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 |
|---|---|---|---|
| use the proposed comparison-based similarity instead of existing multiplicative kernels, measured by comparisons needed for exact planted-cluster recovery | SDP clustering with proposed triplet/quadruplet similarities · Simulated planted clusters (n=1000, k=4) | comparisons needed for exact recovery (ARI): n(ln n)^4.5 and n(ln n)^5.5 -> n(ln n)^3 | Improved |
| use proposed triplet similarity instead of baseline kernel under high crowd noise | SDP clustering with proposed triplet similarity · Simulated planted clusters, n(ln n)^4 comparisons | ARI exact recovery vs noise level epsilon: epsilon > 0.9 -> epsilon as small as 0.25 | Improved |
| change inner/outer similarity distributions to Uniform+Beta or Uniform+Normal (ablation) | Proposed triplet similarity · Simulated planted clusters | ARI | Mixed |
| compare proposed triplet similarity with quadruplet similarity | SDP clustering with comparison-based similarities · Simulated planted clusters | ARI | No clear effect |
| reduce triplet budget on MNIST 1vs.7 from n(ln n)^3 to n(ln n)^2 | Proposed triplet similarity vs baseline kernel · MNIST 1vs.7 (n=2163) | ARI: n(ln n)^3 -> n(ln n)^2 | Improved |
| use SPUR-estimated number of clusters instead of known k (ablation) | Proposed triplet similarity · MNIST 1vs.7 | ARI | No clear effect |
| use SPUR-estimated k instead of known k at low triplet budget (ablation) | Proposed triplet similarity · MNIST 10 (n=2000), n(ln n)^2 triplets | ARI | Hurt |
| increase triplets from n(ln n)^2 to n(ln n)^4 (ablation) | Proposed triplet similarity with SPUR · MNIST 10 | estimated number of clusters / ARI: 3 -> 9 | Improved |
| use ordinal methods at n(ln n)^4 triplets versus k-means on original data | All ordinal methods · MNIST 10 | ARI | No clear effect |
| set k=3 rather than SPUR-estimated k=2 (ablation) | Proposed triplet similarity · Car dataset (12112 triplets) | ARI agreement with true labels: k=2 -> k=3 | Improved |
Closest papers by meaning
- Foundations of Comparison-Based Hierarchical Clustering (NeurIPS 2019 · similarity 0.90)
- An Evaluative Measure of Clustering Methods Incorporating Hyperparameter Sensitivity (AAAI 2022 · similarity 0.88)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.87)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.87)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.86)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.86)
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.
