Research map / Graph learning / Graph algorithms and clustering
Exact Clustering of Weighted Graphs via Semidefinite Programming
Aleksis Pirinen, Brendan Ames
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 |
|---|---|---|---|
| replace dense noise with sparse between-cluster noise (q = 1/sqrt(n)) | SDP relaxation of densest k-disjoint clique via ADMM · planted cluster model, n=1000 | minimum cluster size for exact recovery | Improved |
Closest papers by meaning
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.88)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.88)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.87)
- Densest k-Subgraph Mining via a Provably Tight Relaxation (AAAI 2025 · similarity 0.87)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.87)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.87)
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.
