Research map / Optimization / Nonconvex and smooth optimization
A Non–Convex Optimization Approach to Correlation Clustering
Erik Thiel, Morteza Haghir Chehreghani, Devdatt Dubhashi
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 |
|---|---|---|---|
| Frank-Wolfe local search instead of VOTE (best heuristic baseline) | correlation clustering · 20 Newsgroups data1 | CC objective: 171163.20 -> 179456.94 | Improved |
| Frank-Wolfe local search instead of VOTE | correlation clustering · 20 Newsgroups data3 | NMI: 0.51 -> 0.56 | Improved |
| Frank-Wolfe instead of PIVOT | correlation clustering · 20 Newsgroups data2 | NMI: 0.12 -> 0.39 | Improved |
| subsample gradient with small ratio q=0.1 (b=20) (ablation) | stochastic block FW · 20 newsgroups subset | passes to reach max objective | Improved |
| too small batch size (b=10) in subsampling (ablation) | stochastic block FW · 20 newsgroups subset | CC objective | Hurt |
| add SAGA variance reduction with batch size 10 (ablation) | stochastic block FW · synthetic n=300,k=10,p=0.3 | CC objective | Improved |
| add variance reduction at subsampling ratio above 0.1 (ablation) | stochastic block FW · 20 newsgroups subset | CC objective | No clear effect |
| initialize with k = n clusters | FW local search · synthetic k=5 | estimated number of clusters | Improved |
Closest papers by meaning
- Efficient Testing for Correlation Clustering: Improved Algorithms and Optimal Bounds (ICLR 2026 · similarity 0.89)
- Partial Optimality in Cubic Correlation Clustering (ICML 2023 · similarity 0.88)
- Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut (ICML 2026 · similarity 0.88)
- Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.88)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.87)
- Achieving Optimal Clustering in Gaussian Mixture Models with Anisotropic Covariance Structures (NeurIPS 2024 · 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.
