Research map / Learning theory and algorithms / Clustering
The Cluster Description Problem - Complexity Results, Formulations and Approximations
Ian Davidson, Antoine Gourru, S Ravi
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 |
|---|---|---|---|
| add cover-or-forget (ignore up to I instances) to the basic ILP (ablation) | Cluster description ILP · Twitter 1000 users, 2 communities | feasibility | Improved |
| add Together/Apart composition constraints derived from hashtag co-occurrence (ablation) | Cover-or-forget ILP · Twitter 1000 users, 2 communities | description consistency (qualitative) | Improved |
| increase number of nodes (and clusters) from 1000 to 5000 | Cover-or-forget ILP · Twitter scalability | solver time (s): 0.5 -> 88.1 | Hurt |
| increase number of tags from 25 to 136 (5000 nodes, k=32) (ablation) | Cover-or-forget ILP · Twitter scalability | solver time (s): 232.1 -> 88.1 | Improved |
| increase number of tags from 25 to 136 (ablation) | Cover-or-forget ILP · Twitter scalability | nodes forgotten: 783 -> 123 | Improved |
Closest papers by meaning
- Efficient Algorithms for Generating Provably Near-Optimal Cluster Descriptors for Explainability (AAAI 2020 · similarity 0.86)
- Nearly-Tight and Oblivious Algorithms for Explainable Clustering (NeurIPS 2021 · similarity 0.85)
- SpEx: A Spectral Approach to Explainable Clustering (NeurIPS 2025 · similarity 0.85)
- THESAURUS: Contrastive Graph Clustering by Swapping Fused Gromov-Wasserstein Couplings (AAAI 2025 · similarity 0.83)
- Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm (NeurIPS 2025 · similarity 0.83)
- Explaining Kernel Clustering via Decision Trees (ICLR 2024 · similarity 0.82)
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.
